ROSE  0.11.145.0
Classes | Public Types | Public Member Functions | List of all members
Sawyer::Container::DenseIntegerSet< T > Class Template Reference

Description

template<typename T>
class Sawyer::Container::DenseIntegerSet< T >

Unordered set of densely-packed integers.

This set is optimized to store integers from a range whose size is close to the cardinality of the set. For instance, if the set is intended to store integers in the range [100,199] and contains nearly 100 values at least at some point in its lifetime, then this is an appropriate container class to use for the set. Insert, erase, and existence testing are constant time, as are obtaining the beginning and end iterators and incrementing an iterator.

It is traditional to use an array or vector of Booleans to represent dense sets, but that approach results in poor iterator performance when the set happens to be sparse. This container avoids the poor iterator performance by also storing the members as a linked list (although it does so in a way that doesn't actually store the member values explicitly). But the "cost" of constant-time iteration is that the members of the set are not traversed in any particular order.

The combination of constant-time insert/erase/lookup and constant-time iterator increment makes this an ideal container for tree search algorithms where the set initially contains all vertex IDs but for most of the search the set is sparse.

Definition at line 39 of file DenseIntegerSet.h.

#include <util/Sawyer/DenseIntegerSet.h>

Inheritance diagram for Sawyer::Container::DenseIntegerSet< T >:
Inheritance graph
[legend]

Classes

class  ConstIterator
 Bidirectional iterates over members of a set. More...
 
struct  Member
 

Public Types

typedef T Value
 Type of values stored in this container. More...
 

Public Member Functions

 DenseIntegerSet ()
 Construct an empty set that cannot store any members. More...
 
 DenseIntegerSet (const DenseIntegerSet &other)
 Copy constructor. More...
 
DenseIntegerSetoperator= (const DenseIntegerSet &other)
 Assignment operator. More...
 
boost::iterator_range< ConstIteratorvalues () const
 Iterator range for set members. More...
 
bool isEmpty () const
 Whether the set is empty. More...
 
size_t size () const
 Number of members present. More...
 
Interval< Valuedomain () const
 Domain of storable values. More...
 
bool isStorable (Value v) const
 Determines if a value is storable. More...
 
bool exists (const Value &value) const
 Determines whether a value is stored. More...
 
template<class SawyerContainer >
bool existsAny (const SawyerContainer &other) const
 Whether any value exists. More...
 
template<class SawyerContainer >
bool existsAll (const SawyerContainer &other) const
 Whether all values exist. More...
 
template<class SawyerContainer >
bool operator== (const SawyerContainer &other) const
 Whether two sets contain the same members. More...
 
template<class SawyerContainer >
bool operator!= (const SawyerContainer &other) const
 Whether two sets do not contain the same members. More...
 
void clear ()
 Remove all members from this set. More...
 
bool insert (Value value)
 Insert a value. More...
 
void insertAll ()
 Insert all possible members. More...
 
template<class SawyerContainer >
DenseIntegerSet operator& (const SawyerContainer &other) const
 Compute the intersection of this set with another. More...
 
template<class SawyerContainer >
DenseIntegerSet operator| (const SawyerContainer &other) const
 Compute the union of this set with another. More...
 
template<class SawyerContainer >
DenseIntegerSet operator- (const SawyerContainer &other) const
 Compute the difference of this set with another. More...
 
Value deref (const ConstIterator &iter) const
 
 DenseIntegerSet (const Interval< Value > &domain)
 Construct an empty set that can hold values from the specified domain. More...
 
 DenseIntegerSet (Value least, Value greatest)
 Construct an empty set that can hold values from the specified domain. More...
 
 DenseIntegerSet (Value n)
 Construct an empty set that can hold values from the specified domain. More...
 
template<class SawyerContainer >
void insertMany (const SawyerContainer &other)
 Insert many values from another set. More...
 
template<class SawyerContainer >
DenseIntegerSetoperator|= (const SawyerContainer &other)
 Insert many values from another set. More...
 
bool erase (Value value)
 Erase a value. More...
 
ConstIterator erase (const ConstIterator &iter)
 Erase a value. More...
 
template<class SawyerContainer >
void eraseMany (const SawyerContainer &other)
 Erase many values. More...
 
template<class SawyerContainer >
DenseIntegerSetoperator-= (const SawyerContainer &other)
 Erase many values. More...
 
template<class SawyerContainer >
void intersect (const SawyerContainer &other)
 Intersect this set with another. More...
 
template<class SawyerContainer >
DenseIntegerSetoperator&= (const SawyerContainer &other)
 Intersect this set with another. More...
 

Member Typedef Documentation

template<typename T>
typedef T Sawyer::Container::DenseIntegerSet< T >::Value

Type of values stored in this container.

Definition at line 55 of file DenseIntegerSet.h.

Constructor & Destructor Documentation

template<typename T>
Sawyer::Container::DenseIntegerSet< T >::DenseIntegerSet ( )
inline

Construct an empty set that cannot store any members.

This object can only represent the empty set, but it's useful to have this default constructor in order to create a set that can be stored in a vector of sets, among other things.

Definition at line 65 of file DenseIntegerSet.h.

template<typename T>
Sawyer::Container::DenseIntegerSet< T >::DenseIntegerSet ( const Interval< Value > &  domain)
inlineexplicit

Construct an empty set that can hold values from the specified domain.

Constructs a set whose members can be chosen from the specified domain. The domain can be specified as an interval, as a least and greated value, or as the number of values. If specified as the number of values, N, then the domain is zero through N-1, inclusive. The set is initially empty.

Definition at line 75 of file DenseIntegerSet.h.

template<typename T>
Sawyer::Container::DenseIntegerSet< T >::DenseIntegerSet ( Value  least,
Value  greatest 
)
inline

Construct an empty set that can hold values from the specified domain.

Constructs a set whose members can be chosen from the specified domain. The domain can be specified as an interval, as a least and greated value, or as the number of values. If specified as the number of values, N, then the domain is zero through N-1, inclusive. The set is initially empty.

Definition at line 82 of file DenseIntegerSet.h.

template<typename T>
Sawyer::Container::DenseIntegerSet< T >::DenseIntegerSet ( Value  n)
inlineexplicit

Construct an empty set that can hold values from the specified domain.

Constructs a set whose members can be chosen from the specified domain. The domain can be specified as an interval, as a least and greated value, or as the number of values. If specified as the number of values, N, then the domain is zero through N-1, inclusive. The set is initially empty.

Definition at line 89 of file DenseIntegerSet.h.

template<typename T>
Sawyer::Container::DenseIntegerSet< T >::DenseIntegerSet ( const DenseIntegerSet< T > &  other)
inline

Copy constructor.

Definition at line 97 of file DenseIntegerSet.h.

Member Function Documentation

template<typename T>
DenseIntegerSet& Sawyer::Container::DenseIntegerSet< T >::operator= ( const DenseIntegerSet< T > &  other)
inline

Assignment operator.

Assignment does not change the domain of the destination. If one of the members of other is outside the domain of this container then an Exception::Domain error is thrown and this object is not modified.

Definition at line 110 of file DenseIntegerSet.h.

template<typename T>
boost::iterator_range<ConstIterator> Sawyer::Container::DenseIntegerSet< T >::values ( ) const
inline

Iterator range for set members.

Returns an iterator range consiting of the begin and end iterators, in constant time.

Definition at line 255 of file DenseIntegerSet.h.

Referenced by Sawyer::Container::DenseIntegerSet< size_t >::DenseIntegerSet(), and Sawyer::Container::DenseIntegerSet< size_t >::operator=().

template<typename T>
bool Sawyer::Container::DenseIntegerSet< T >::isEmpty ( ) const
inline

Whether the set is empty.

Returns true if the set is empty, false if not empty. This is a constant-time operation.

Definition at line 266 of file DenseIntegerSet.h.

Referenced by Sawyer::Container::DenseIntegerSet< size_t >::exists().

template<typename T>
size_t Sawyer::Container::DenseIntegerSet< T >::size ( void  ) const
inline

Number of members present.

Returns the number of values currently contained in this set. This is a constant-time operation.

Definition at line 273 of file DenseIntegerSet.h.

Referenced by Sawyer::Container::DenseIntegerSet< size_t >::operator!=(), and Sawyer::Container::DenseIntegerSet< size_t >::operator==().

template<typename T>
Interval<Value> Sawyer::Container::DenseIntegerSet< T >::domain ( ) const
inline

Domain of storable values.

Returns the set's domain, which is an interval describing which values can be possible members of this set.

Definition at line 280 of file DenseIntegerSet.h.

Referenced by Sawyer::Container::DenseIntegerSet< size_t >::isStorable(), and Sawyer::Container::DenseIntegerSet< size_t >::operator=().

template<typename T>
bool Sawyer::Container::DenseIntegerSet< T >::isStorable ( Value  v) const
inline

Determines if a value is storable.

Returns true if the specified value can be stored in this set, and false otherwise. A storable value is a value that falls within this set's domain.

Definition at line 288 of file DenseIntegerSet.h.

Referenced by Sawyer::Container::DenseIntegerSet< size_t >::exists(), and Sawyer::Container::DenseIntegerSet< size_t >::insert().

template<typename T>
bool Sawyer::Container::DenseIntegerSet< T >::exists ( const Value value) const
inline

Determines whether a value is stored.

Returns true if the specified value is a member of this set, false if the value is not stored in this set. This method returns false if the value is outside this set's domain.

Definition at line 296 of file DenseIntegerSet.h.

Referenced by Sawyer::Container::DenseIntegerSet< size_t >::erase(), Sawyer::Container::DenseIntegerSet< size_t >::existsAll(), Sawyer::Container::DenseIntegerSet< size_t >::existsAny(), and Sawyer::Container::DenseIntegerSet< size_t >::intersect().

template<typename T>
template<class SawyerContainer >
bool Sawyer::Container::DenseIntegerSet< T >::existsAny ( const SawyerContainer &  other) const
inline

Whether any value exists.

Returns true if any of the specified values exist in this set. This operation takes time that is linearly proportional to the number of items in the other container.

Definition at line 308 of file DenseIntegerSet.h.

template<typename T>
template<class SawyerContainer >
bool Sawyer::Container::DenseIntegerSet< T >::existsAll ( const SawyerContainer &  other) const
inline

Whether all values exist.

Returns true if all specified values exist in this set. This operation takes time that is linearly proportaional to teh number of items in the other container.

Definition at line 321 of file DenseIntegerSet.h.

Referenced by Sawyer::Container::DenseIntegerSet< size_t >::operator!=(), and Sawyer::Container::DenseIntegerSet< size_t >::operator==().

template<typename T>
template<class SawyerContainer >
bool Sawyer::Container::DenseIntegerSet< T >::operator== ( const SawyerContainer &  other) const
inline

Whether two sets contain the same members.

Returns true if this set and other contain exactly the same members.

Definition at line 333 of file DenseIntegerSet.h.

template<typename T>
template<class SawyerContainer >
bool Sawyer::Container::DenseIntegerSet< T >::operator!= ( const SawyerContainer &  other) const
inline

Whether two sets do not contain the same members.

Returns true if this set and the other set are not equal.

Definition at line 341 of file DenseIntegerSet.h.

template<typename T>
void Sawyer::Container::DenseIntegerSet< T >::clear ( )
inline

Remove all members from this set.

This operation is linear in the number of members currently present in the set.

Definition at line 352 of file DenseIntegerSet.h.

Referenced by Sawyer::Container::DenseIntegerSet< size_t >::intersect().

template<typename T>
bool Sawyer::Container::DenseIntegerSet< T >::insert ( Value  value)
inline

Insert a value.

Inserts the specified value in constant time. Returns true if the value was inserted and false if the value already existed. If the value is outside the domain then an Exception::DomainError is thrown.

Definition at line 366 of file DenseIntegerSet.h.

Referenced by Sawyer::Container::DenseIntegerSet< size_t >::DenseIntegerSet(), Sawyer::Container::Algorithm::graphIsConnected(), Sawyer::Container::DenseIntegerSet< size_t >::insertMany(), Sawyer::Container::DenseIntegerSet< size_t >::intersect(), and Sawyer::Container::DenseIntegerSet< size_t >::operator=().

template<typename T>
void Sawyer::Container::DenseIntegerSet< T >::insertAll ( )
inline

Insert all possible members.

Causes the set to contain all elements that are part of its domain.

Definition at line 392 of file DenseIntegerSet.h.

Referenced by Sawyer::Container::Algorithm::CommonSubgraphIsomorphism< GraphA, GraphB, SolutionProcessor, EquivalenceP >::reset().

template<typename T>
template<class SawyerContainer >
void Sawyer::Container::DenseIntegerSet< T >::insertMany ( const SawyerContainer &  other)
inline

Insert many values from another set.

Inserts all values of the other container into this set.

Definition at line 418 of file DenseIntegerSet.h.

Referenced by Sawyer::Container::DenseIntegerSet< size_t >::operator|=().

template<typename T>
template<class SawyerContainer >
DenseIntegerSet& Sawyer::Container::DenseIntegerSet< T >::operator|= ( const SawyerContainer &  other)
inline

Insert many values from another set.

Inserts all values of the other container into this set.

Definition at line 424 of file DenseIntegerSet.h.

template<typename T>
bool Sawyer::Container::DenseIntegerSet< T >::erase ( Value  value)
inline

Erase a value.

If a value is specified, then the value is erased and this method returns true if the value existed and false if it didn't exist (in which case this is a no-op). If a non-end iterator is specified, then the pointed to value is erased and the next iterator is returned.

Erasing is a constant-time operation.

Definition at line 439 of file DenseIntegerSet.h.

Referenced by Sawyer::Container::DenseIntegerSet< size_t >::eraseMany().

template<typename T>
ConstIterator Sawyer::Container::DenseIntegerSet< T >::erase ( const ConstIterator iter)
inline

Erase a value.

If a value is specified, then the value is erased and this method returns true if the value existed and false if it didn't exist (in which case this is a no-op). If a non-end iterator is specified, then the pointed to value is erased and the next iterator is returned.

Erasing is a constant-time operation.

Definition at line 451 of file DenseIntegerSet.h.

template<typename T>
template<class SawyerContainer >
void Sawyer::Container::DenseIntegerSet< T >::eraseMany ( const SawyerContainer &  other)
inline

Erase many values.

Erase those values from this set that are members of the other container.

Definition at line 473 of file DenseIntegerSet.h.

Referenced by Sawyer::Container::DenseIntegerSet< size_t >::operator-=().

template<typename T>
template<class SawyerContainer >
DenseIntegerSet& Sawyer::Container::DenseIntegerSet< T >::operator-= ( const SawyerContainer &  other)
inline

Erase many values.

Erase those values from this set that are members of the other container.

Definition at line 479 of file DenseIntegerSet.h.

template<typename T>
template<class SawyerContainer >
void Sawyer::Container::DenseIntegerSet< T >::intersect ( const SawyerContainer &  other)
inline

Intersect this set with another.

Replaces this set with members that are only in this set and the other set.

Definition at line 491 of file DenseIntegerSet.h.

Referenced by Sawyer::Container::DenseIntegerSet< size_t >::operator&=().

template<typename T>
template<class SawyerContainer >
DenseIntegerSet& Sawyer::Container::DenseIntegerSet< T >::operator&= ( const SawyerContainer &  other)
inline

Intersect this set with another.

Replaces this set with members that are only in this set and the other set.

Definition at line 501 of file DenseIntegerSet.h.

template<typename T>
template<class SawyerContainer >
DenseIntegerSet Sawyer::Container::DenseIntegerSet< T >::operator& ( const SawyerContainer &  other) const
inline

Compute the intersection of this set with another.

Returns a new set which has only those members that are common to this set and the other set.

Definition at line 515 of file DenseIntegerSet.h.

template<typename T>
template<class SawyerContainer >
DenseIntegerSet Sawyer::Container::DenseIntegerSet< T >::operator| ( const SawyerContainer &  other) const
inline

Compute the union of this set with another.

Returns a new set containing the union of all members of this set and the other set.

Definition at line 525 of file DenseIntegerSet.h.

template<typename T>
template<class SawyerContainer >
DenseIntegerSet Sawyer::Container::DenseIntegerSet< T >::operator- ( const SawyerContainer &  other) const
inline

Compute the difference of this set with another.

Returns a new set containing those elements of this set that are not members of the other set.

Definition at line 535 of file DenseIntegerSet.h.


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