claw::math::ordered_set< K, Comp > Class Template Reference

#include <ordered_set.hpp>

Inheritance diagram for claw::math::ordered_set< K, Comp >:

claw::avl< K, Comp >

List of all members.


Detailed Description

template<class K, class Comp = std::less<K>>
class claw::math::ordered_set< K, Comp >

A class to manage sets of ordered items.

Author:
Julien Jorge

Definition at line 44 of file ordered_set.hpp.


Public Types

typedef super::const_iterator const_iterator
typedef super::value_type value_type
typedef super::referent_type referent_type
typedef super::const_reference const_reference

Public Member Functions

ordered_setoperator*= (const ordered_set &that)
 Intersection.
ordered_setoperator+= (const ordered_set &that)
 Union.
ordered_setoperator-= (const ordered_set &that)
 Difference.
ordered_setoperator/= (const ordered_set &that)
 Symetric difference.
bool operator> (const ordered_set &that) const
 Inclusion.
bool operator>= (const ordered_set &that) const
 Inclusion or equality.
bool operator< (const ordered_set &that) const
 Inclusion.
bool operator<= (const ordered_set &that) const
 Inclusion or equality.
ordered_setintersection (const ordered_set &that)
 Intersection.
ordered_setjoin (const ordered_set &that)
 Union.
ordered_setdifference (const ordered_set &that)
 Difference.
ordered_setsymetric_difference (const ordered_set &that)
 Symetric difference.
bool contains (const ordered_set &that) const
 Inclusion or equality.
bool strictly_contains (const ordered_set &that) const
 Inclusion.

Private Types

typedef avl< K, Comp > super

Member Typedef Documentation

template<class K, class Comp = std::less<K>>
typedef avl<K, Comp> claw::math::ordered_set< K, Comp >::super [private]

Definition at line 47 of file ordered_set.hpp.

template<class K, class Comp = std::less<K>>
typedef super::const_iterator claw::math::ordered_set< K, Comp >::const_iterator

Reimplemented from claw::avl< K, Comp >.

Definition at line 50 of file ordered_set.hpp.

template<class K, class Comp = std::less<K>>
typedef super::value_type claw::math::ordered_set< K, Comp >::value_type

Reimplemented from claw::avl< K, Comp >.

Definition at line 51 of file ordered_set.hpp.

template<class K, class Comp = std::less<K>>
typedef super::referent_type claw::math::ordered_set< K, Comp >::referent_type

Reimplemented from claw::avl< K, Comp >.

Definition at line 52 of file ordered_set.hpp.

template<class K, class Comp = std::less<K>>
typedef super::const_reference claw::math::ordered_set< K, Comp >::const_reference

Reimplemented from claw::avl< K, Comp >.

Definition at line 53 of file ordered_set.hpp.


Member Function Documentation

template<class K, class Comp>
claw::math::ordered_set< K, Comp > & claw::math::ordered_set< K, Comp >::operator*= ( const ordered_set< K, Comp > &  that  )  [inline]

Intersection.

Parameters:
that The instance to intersect from.

Definition at line 39 of file ordered_set.tpp.

References claw::math::ordered_set< K, Comp >::intersection().

00040 {
00041   return intersection( that );
00042 } // ordered_set::operator*=()

template<class K, class Comp>
claw::math::ordered_set< K, Comp > & claw::math::ordered_set< K, Comp >::operator+= ( const ordered_set< K, Comp > &  that  )  [inline]

Union.

Parameters:
that The instance to join with.

Definition at line 51 of file ordered_set.tpp.

References claw::math::ordered_set< K, Comp >::join().

00052 {
00053   return join( that );
00054 } // ordered_set::operator+=()

template<class K, class Comp>
claw::math::ordered_set< K, Comp > & claw::math::ordered_set< K, Comp >::operator-= ( const ordered_set< K, Comp > &  that  )  [inline]

Difference.

Parameters:
that The instance from which to remove items.

Definition at line 63 of file ordered_set.tpp.

References claw::math::ordered_set< K, Comp >::difference().

00064 {
00065   return difference( that );
00066 } // ordered_set::operator-=()

template<class K, class Comp>
claw::math::ordered_set< K, Comp > & claw::math::ordered_set< K, Comp >::operator/= ( const ordered_set< K, Comp > &  that  )  [inline]

Symetric difference.

Parameters:
that The instance to differ from.

Definition at line 75 of file ordered_set.tpp.

References claw::math::ordered_set< K, Comp >::symetric_difference().

00076 {
00077   return symetric_difference( that );
00078 } // ordered_set::operator/=()

template<class K, class Comp>
bool claw::math::ordered_set< K, Comp >::operator> ( const ordered_set< K, Comp > &  that  )  const [inline]

Inclusion.

Parameters:
that The instance that should be contained.
Returns:
true if that is strictly included in this.

Definition at line 88 of file ordered_set.tpp.

References claw::math::ordered_set< K, Comp >::strictly_contains().

00089 {
00090   return strictly_contains( that );
00091 } // ordered_set::operator>()

template<class K, class Comp>
bool claw::math::ordered_set< K, Comp >::operator>= ( const ordered_set< K, Comp > &  that  )  const [inline]

Inclusion or equality.

Parameters:
that The instance that should be contained.
Returns:
true if that is included in this.

Definition at line 101 of file ordered_set.tpp.

References claw::math::ordered_set< K, Comp >::contains().

00102 {
00103   return contains( that );
00104 } // ordered_set::operator>=()

template<class K, class Comp>
bool claw::math::ordered_set< K, Comp >::operator< ( const ordered_set< K, Comp > &  that  )  const [inline]

Inclusion.

Parameters:
that The instance that should contain.
Returns:
true if that is strictly included in this.

Definition at line 114 of file ordered_set.tpp.

References claw::math::ordered_set< K, Comp >::strictly_contains().

00115 {
00116   return that.strictly_contains( *this );
00117 } // ordered_set::operator<()

template<class K, class Comp>
bool claw::math::ordered_set< K, Comp >::operator<= ( const ordered_set< K, Comp > &  that  )  const [inline]

Inclusion or equality.

Parameters:
that The instance that should be contained.
Returns:
true if that is included in this.

Definition at line 127 of file ordered_set.tpp.

References claw::math::ordered_set< K, Comp >::contains().

00128 {
00129   return that.contains( *this );
00130 } // ordered_set::operator<=()

template<class K, class Comp>
claw::math::ordered_set< K, Comp > & claw::math::ordered_set< K, Comp >::intersection ( const ordered_set< K, Comp > &  that  )  [inline]

Intersection.

Parameters:
that The instance to intersect from.

Definition at line 139 of file ordered_set.tpp.

References claw::avl< K, Comp >::begin(), claw::avl< K, Comp >::end(), claw::avl< K, Comp >::erase(), and claw::avl< K, Comp >::find().

Referenced by claw::math::ordered_set< K, Comp >::operator*=().

00140 {
00141   std::list<K> remove_us;
00142   const_iterator it;
00143   
00144   for (it=super::begin(); it!=super::end(); ++it)
00145     if ( that.find( *it ) == that.end() )
00146       remove_us.push_front( *it );
00147 
00148   typename std::list<K>::const_iterator remove_it;
00149 
00150   for (remove_it=remove_us.begin(); remove_it!=remove_us.end(); ++remove_it)
00151     super::erase( *remove_it );
00152 
00153   return *this;
00154 } // ordered_set::intersection()

template<class K, class Comp>
claw::math::ordered_set< K, Comp > & claw::math::ordered_set< K, Comp >::join ( const ordered_set< K, Comp > &  that  )  [inline]

Union.

Parameters:
that The instance to join with.

Definition at line 163 of file ordered_set.tpp.

References claw::avl< K, Comp >::begin(), claw::avl< K, Comp >::end(), and claw::avl< K, Comp >::insert().

Referenced by claw::math::ordered_set< K, Comp >::operator+=(), and claw::math::ordered_set< K, Comp >::symetric_difference().

00164 {
00165   const_iterator it;
00166   
00167   for (it=that.begin(); it!=that.end(); ++it)
00168     super::insert( *it );
00169 
00170   return *this;
00171 } // ordered_set::join()

template<class K, class Comp>
claw::math::ordered_set< K, Comp > & claw::math::ordered_set< K, Comp >::difference ( const ordered_set< K, Comp > &  that  )  [inline]

Difference.

Parameters:
that The instance from which to remove items.

Definition at line 180 of file ordered_set.tpp.

References claw::avl< K, Comp >::begin(), claw::avl< K, Comp >::end(), claw::avl< K, Comp >::erase(), and claw::avl< K, Comp >::find().

Referenced by claw::math::ordered_set< K, Comp >::operator-=(), and claw::math::ordered_set< K, Comp >::symetric_difference().

00181 {
00182   std::list<K> remove_us;
00183   const_iterator it;
00184   
00185   for (it=super::begin(); it!=super::end(); ++it)
00186     if ( that.find( *it ) != that.end() )
00187       remove_us.push_front( *it );
00188 
00189   typename std::list<K>::const_iterator remove_it;
00190 
00191   for (remove_it=remove_us.begin(); remove_it!=remove_us.end(); ++remove_it)
00192     super::erase( *remove_it );
00193 
00194   return *this;
00195 } // ordered_set::difference()

template<class K, class Comp>
claw::math::ordered_set< K, Comp > & claw::math::ordered_set< K, Comp >::symetric_difference ( const ordered_set< K, Comp > &  that  )  [inline]

Symetric difference.

Parameters:
that The instance to differ from.

Definition at line 204 of file ordered_set.tpp.

References claw::math::ordered_set< K, Comp >::difference(), and claw::math::ordered_set< K, Comp >::join().

Referenced by claw::math::ordered_set< K, Comp >::operator/=().

00205 {
00206   ordered_set<K, Comp> my_copy(*this), his_copy(that);
00207 
00208   return difference( that ).join( his_copy.difference(my_copy) );
00209 } // ordered_set::symetric_difference()

template<class K, class Comp>
bool claw::math::ordered_set< K, Comp >::contains ( const ordered_set< K, Comp > &  that  )  const [inline]

Inclusion or equality.

Parameters:
that The instance that should be contained.
Returns:
true if that is included in this.

Definition at line 219 of file ordered_set.tpp.

References claw::avl< K, Comp >::begin(), claw::avl< K, Comp >::end(), claw::avl< K, Comp >::s_key_less, and claw::avl< K, Comp >::size().

Referenced by claw::math::ordered_set< K, Comp >::operator<=(), claw::math::ordered_set< K, Comp >::operator>=(), and claw::math::ordered_set< K, Comp >::strictly_contains().

00220 {
00221   bool ok = super::size() >= that.size();
00222   const_iterator it_this( super::begin() );
00223   const_iterator it_that( that.begin() );
00224 
00225   while ( ok && (it_that != that.end()) && (it_this != super::end()) )
00226     if ( s_key_less( *it_this, *it_that ) )
00227       ++it_this;
00228     else if ( s_key_less( *it_that, *it_this ) )
00229       ok = false;
00230     else
00231       {
00232         ++it_this;
00233         ++it_that;
00234       }
00235 
00236   return it_that == that.end();
00237 } // ordered_set::contains()

template<class K, class Comp>
bool claw::math::ordered_set< K, Comp >::strictly_contains ( const ordered_set< K, Comp > &  that  )  const [inline]

Inclusion.

Parameters:
that The instance that should contain.
Returns:
true if that is strictly included in this.

Definition at line 248 of file ordered_set.tpp.

References claw::math::ordered_set< K, Comp >::contains(), and claw::avl< K, Comp >::size().

Referenced by claw::math::ordered_set< K, Comp >::operator<(), and claw::math::ordered_set< K, Comp >::operator>().

00249 {
00250   return contains(that) && ( super::size() > that.size() );
00251 } // ordered_set::strictly_contains()


The documentation for this class was generated from the following files:

Generated on Thu Jun 26 09:35:07 2008 for CLAW Library (a C++ Library Absolutely Wonderful) by  doxygen 1.5.6