CLAW Library (a C++ Library Absolutely Wonderful) 1.5.5
Public Types | Public Member Functions | Private Types | Static Private Attributes

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

A class to manage sets of ordered items. More...

#include <ordered_set.hpp>

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

List of all members.

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

Static Private Attributes

static Comp s_key_comp
 Function object used to compare keys.

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.


Member Typedef Documentation

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 51 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 54 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 53 of file ordered_set.hpp.

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

Definition at line 48 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 52 of file ordered_set.hpp.


Member Function Documentation

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

Inclusion or equality.

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

Definition at line 223 of file ordered_set.tpp.

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

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

{
  bool ok = super::size() >= that.size();
  const_iterator it_this( super::begin() );
  const_iterator it_that( that.begin() );

  while ( ok && (it_that != that.end()) && (it_this != super::end()) )
    if ( s_key_comp( *it_this, *it_that ) )
      ++it_this;
    else if ( s_key_comp( *it_that, *it_this ) )
      ok = false;
    else
      {
        ++it_this;
        ++it_that;
      }

  return it_that == that.end();
} // ordered_set::contains()
template<class K , class Comp >
claw::math::ordered_set< K, Comp > & claw::math::ordered_set< K, Comp >::difference ( const ordered_set< K, Comp > &  that)

Difference.

Parameters:
thatThe instance from which to remove items.

Definition at line 184 of file ordered_set.tpp.

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

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

{
  std::list<K> remove_us;
  const_iterator it;
  
  for (it=super::begin(); it!=super::end(); ++it)
    if ( that.find( *it ) != that.end() )
      remove_us.push_front( *it );

  typename std::list<K>::const_iterator remove_it;

  for (remove_it=remove_us.begin(); remove_it!=remove_us.end(); ++remove_it)
    super::erase( *remove_it );

  return *this;
} // ordered_set::difference()
template<class K , class Comp >
claw::math::ordered_set< K, Comp > & claw::math::ordered_set< K, Comp >::intersection ( const ordered_set< K, Comp > &  that)

Intersection.

Parameters:
thatThe instance to intersect from.

Definition at line 143 of file ordered_set.tpp.

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

{
  std::list<K> remove_us;
  const_iterator it;
  
  for (it=super::begin(); it!=super::end(); ++it)
    if ( that.find( *it ) == that.end() )
      remove_us.push_front( *it );

  typename std::list<K>::const_iterator remove_it;

  for (remove_it=remove_us.begin(); remove_it!=remove_us.end(); ++remove_it)
    super::erase( *remove_it );

  return *this;
} // 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)

Union.

Parameters:
thatThe instance to join with.

Definition at line 167 of file ordered_set.tpp.

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

{
  const_iterator it;
  
  for (it=that.begin(); it!=that.end(); ++it)
    super::insert( *it );

  return *this;
} // ordered_set::join()
template<class K , class Comp >
claw::math::ordered_set< K, Comp > & claw::math::ordered_set< K, Comp >::operator*= ( const ordered_set< K, Comp > &  that)

Intersection.

Parameters:
thatThe instance to intersect from.

Definition at line 43 of file ordered_set.tpp.

{
  return intersection( that );
} // 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)

Union.

Parameters:
thatThe instance to join with.

Definition at line 55 of file ordered_set.tpp.

{
  return join( that );
} // 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)

Difference.

Parameters:
thatThe instance from which to remove items.

Definition at line 67 of file ordered_set.tpp.

{
  return difference( that );
} // 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)

Symetric difference.

Parameters:
thatThe instance to differ from.

Definition at line 79 of file ordered_set.tpp.

{
  return symetric_difference( that );
} // ordered_set::operator/=()
template<class K , class Comp >
bool claw::math::ordered_set< K, Comp >::operator< ( const ordered_set< K, Comp > &  that) const

Inclusion.

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

Definition at line 118 of file ordered_set.tpp.

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

{
  return that.strictly_contains( *this );
} // ordered_set::operator<()
template<class K , class Comp >
bool claw::math::ordered_set< K, Comp >::operator<= ( const ordered_set< K, Comp > &  that) const

Inclusion or equality.

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

Definition at line 131 of file ordered_set.tpp.

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

{
  return that.contains( *this );
} // ordered_set::operator<=()
template<class K , class Comp >
bool claw::math::ordered_set< K, Comp >::operator> ( const ordered_set< K, Comp > &  that) const

Inclusion.

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

Definition at line 92 of file ordered_set.tpp.

{
  return strictly_contains( that );
} // ordered_set::operator>()
template<class K , class Comp >
bool claw::math::ordered_set< K, Comp >::operator>= ( const ordered_set< K, Comp > &  that) const

Inclusion or equality.

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

Definition at line 105 of file ordered_set.tpp.

{
  return contains( that );
} // ordered_set::operator>=()
template<class K , class Comp >
bool claw::math::ordered_set< K, Comp >::strictly_contains ( const ordered_set< K, Comp > &  that) const

Inclusion.

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

Definition at line 252 of file ordered_set.tpp.

References claw::avl< K, Comp >::size().

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

{
  return contains(that) && ( super::size() > that.size() );
} // ordered_set::strictly_contains()
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)

Symetric difference.

Parameters:
thatThe instance to differ from.

Definition at line 208 of file ordered_set.tpp.

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

{
  ordered_set<K, Comp> my_copy(*this), his_copy(that);

  return difference( that ).join( his_copy.difference(my_copy) );
} // ordered_set::symetric_difference()

Member Data Documentation

template<class K, class Comp = std::less<K>>
Comp claw::math::ordered_set< K, Comp >::s_key_comp [static, private]

Function object used to compare keys.

Definition at line 77 of file ordered_set.hpp.


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