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 <Sawyer/DenseIntegerSet.h>

Inheritance diagram for Sawyer::Container::DenseIntegerSet< T >:

[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.

Public Member Functions
	DenseIntegerSet ()
	Construct an empty set that cannot store any members.

	DenseIntegerSet (const DenseIntegerSet &other)
	Copy constructor.

DenseIntegerSet &	operator= (const DenseIntegerSet &other)
	Assignment operator.

boost::iterator_range< ConstIterator >	values () const
	Iterator range for set members.

bool	isEmpty () const
	Whether the set is empty.

size_t	size () const
	Number of members present.

Interval< Value >	domain () const
	Domain of storable values.

bool	isStorable (Value v) const
	Determines if a value is storable.

bool	exists (const Value &value) const
	Determines whether a value is stored.

template<class SawyerContainer >
bool	existsAny (const SawyerContainer &other) const
	Whether any value exists.

template<class SawyerContainer >
bool	existsAll (const SawyerContainer &other) const
	Whether all values exist.

template<class SawyerContainer >
bool	operator== (const SawyerContainer &other) const
	Whether two sets contain the same members.

template<class SawyerContainer >
bool	operator!= (const SawyerContainer &other) const
	Whether two sets do not contain the same members.

void	clear ()
	Remove all members from this set.

bool	insert (Value value)
	Insert a value.

void	insertAll ()
	Insert all possible members.

template<class SawyerContainer >
DenseIntegerSet	operator& (const SawyerContainer &other) const
	Compute the intersection of this set with another.

template<class SawyerContainer >
DenseIntegerSet	operator- (const SawyerContainer &other) const
	Compute the difference of this set with another.

Value	deref (const ConstIterator &iter) const


	DenseIntegerSet (const Interval< Value > &domain)
	Construct an empty set that can hold values from the specified domain.

	DenseIntegerSet (Value least, Value greatest)
	Construct an empty set that can hold values from the specified domain.

	DenseIntegerSet (Value n)
	Construct an empty set that can hold values from the specified domain.


template<class SawyerContainer >
void	insertMany (const SawyerContainer &other)
	Insert many values from another set.

template<class SawyerContainer >
DenseIntegerSet &	operator\|= (const SawyerContainer &other)
	Insert many values from another set.

template<class SawyerContainer >
DenseIntegerSet &	operator+= (const SawyerContainer &other)
	Insert many values from another set.


bool	erase (Value value)
	Erase a value.

ConstIterator	erase (const ConstIterator &iter)
	Erase a value.


template<class SawyerContainer >
void	eraseMany (const SawyerContainer &other)
	Erase many values.

template<class SawyerContainer >
DenseIntegerSet &	operator-= (const SawyerContainer &other)
	Erase many values.


template<class SawyerContainer >
void	intersect (const SawyerContainer &other)
	Intersect this set with another.

template<class SawyerContainer >
DenseIntegerSet &	operator&= (const SawyerContainer &other)
	Intersect this set with another.


template<class SawyerContainer >
DenseIntegerSet	operator\| (const SawyerContainer &other) const
	Compute the union of this set with another.

template<class SawyerContainer >
DenseIntegerSet	operator+ (const SawyerContainer &other) const
	Compute the union of this set with another.

Member Typedef Documentation

◆ Value

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

◆ DenseIntegerSet() [1/5]

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.

◆ DenseIntegerSet() [2/5]

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.

References Sawyer::Container::DenseIntegerSet< T >::domain().

◆ DenseIntegerSet() [3/5]

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.

References Sawyer::Container::Interval< T >::isEmpty().

◆ DenseIntegerSet() [4/5]

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.

◆ DenseIntegerSet() [5/5]

template<typename T >

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

inline

Copy constructor.

Definition at line 97 of file DenseIntegerSet.h.

References Sawyer::Container::Interval< T >::greatest(), Sawyer::Container::DenseIntegerSet< T >::insert(), Sawyer::Container::Interval< T >::isEmpty(), Sawyer::Container::Interval< T >::least(), and Sawyer::Container::DenseIntegerSet< T >::values().

Member Function Documentation

◆ operator=()

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.

References Sawyer::Container::DenseIntegerSet< T >::domain(), Sawyer::Container::DenseIntegerSet< T >::insert(), and Sawyer::Container::DenseIntegerSet< T >::values().

◆ values()

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< T >::DenseIntegerSet(), Sawyer::Container::Algorithm::graphFindConnectedComponents(), Sawyer::Container::Algorithm::graphIsConnected(), and Sawyer::Container::DenseIntegerSet< T >::operator=().

◆ isEmpty()

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< T >::exists(), Sawyer::Container::Algorithm::graphFindConnectedComponents(), and Sawyer::Container::Algorithm::graphIsConnected().

◆ size()

template<typename T >

size_t Sawyer::Container::DenseIntegerSet< T >::size ( ) 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< T >::operator!=(), and Sawyer::Container::DenseIntegerSet< T >::operator==().

◆ domain()

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< T >::DenseIntegerSet(), Sawyer::Container::DenseIntegerSet< T >::isStorable(), and Sawyer::Container::DenseIntegerSet< T >::operator=().

◆ isStorable()

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.

References Sawyer::Container::DenseIntegerSet< T >::domain().

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

◆ exists()

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.

References Sawyer::Container::DenseIntegerSet< T >::isEmpty(), Sawyer::Container::DenseIntegerSet< T >::isStorable(), and Sawyer::Container::Interval< T >::least().

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

◆ existsAny()

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.

References Sawyer::Container::DenseIntegerSet< T >::exists().

◆ existsAll()

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.

References Sawyer::Container::DenseIntegerSet< T >::exists().

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

◆ 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.

References Sawyer::Container::DenseIntegerSet< T >::existsAll(), and Sawyer::Container::DenseIntegerSet< T >::size().

◆ operator!=()

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.

References Sawyer::Container::DenseIntegerSet< T >::existsAll(), and Sawyer::Container::DenseIntegerSet< T >::size().

◆ clear()

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< T >::intersect().

◆ insert()

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.

References Sawyer::Container::Interval< T >::greatest(), Sawyer::Container::Interval< T >::isEmpty(), Sawyer::Container::DenseIntegerSet< T >::isStorable(), and Sawyer::Container::Interval< T >::least().

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

◆ insertAll()

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().

◆ insertMany()

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.

References Sawyer::Container::DenseIntegerSet< T >::insert().

Referenced by Sawyer::Container::DenseIntegerSet< T >::operator+=(), and Sawyer::Container::DenseIntegerSet< T >::operator|=().

◆ 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.

References Sawyer::Container::DenseIntegerSet< T >::insertMany().

◆ 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 430 of file DenseIntegerSet.h.

References Sawyer::Container::DenseIntegerSet< T >::insertMany().

◆ erase() [1/2]

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 445 of file DenseIntegerSet.h.

References Sawyer::Container::DenseIntegerSet< T >::exists(), and Sawyer::Container::Interval< T >::least().

Referenced by Sawyer::Container::DenseIntegerSet< T >::eraseMany(), Sawyer::Container::Algorithm::graphFindConnectedComponents(), and Sawyer::Container::Algorithm::graphIsConnected().

◆ erase() [2/2]

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 457 of file DenseIntegerSet.h.

◆ eraseMany()

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 479 of file DenseIntegerSet.h.

References Sawyer::Container::DenseIntegerSet< T >::erase().

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

◆ 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 485 of file DenseIntegerSet.h.

References Sawyer::Container::DenseIntegerSet< T >::eraseMany().

◆ intersect()

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 497 of file DenseIntegerSet.h.

References Sawyer::Container::DenseIntegerSet< T >::clear(), Sawyer::Container::DenseIntegerSet< T >::exists(), and Sawyer::Container::DenseIntegerSet< T >::insert().

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

◆ 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 507 of file DenseIntegerSet.h.

References Sawyer::Container::DenseIntegerSet< T >::intersect().

◆ operator&()

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 521 of file DenseIntegerSet.h.

◆ operator|()

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 533 of file DenseIntegerSet.h.

◆ operator+()

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 539 of file DenseIntegerSet.h.

◆ operator-()

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 548 of file DenseIntegerSet.h.

◆ deref()

template<typename T >

Value Sawyer::Container::DenseIntegerSet< T >::deref ( const ConstIterator & iter ) const

inline

Definition at line 559 of file DenseIntegerSet.h.

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

DenseIntegerSet.h

Description

Classes

Public Types

Public Member Functions

Member Typedef Documentation

◆ Value

Constructor & Destructor Documentation

◆ DenseIntegerSet() [1/5]

◆ DenseIntegerSet() [2/5]

◆ DenseIntegerSet() [3/5]

◆ DenseIntegerSet() [4/5]

◆ DenseIntegerSet() [5/5]

Member Function Documentation

◆ operator=()

◆ values()

◆ isEmpty()

◆ size()

◆ domain()

◆ isStorable()

◆ exists()

◆ existsAny()

◆ existsAll()

◆ operator==()

◆ operator!=()

◆ clear()

◆ insert()

◆ insertAll()

◆ insertMany()

◆ operator|=()

◆ operator+=()

◆ erase() [1/2]

◆ erase() [2/2]

◆ eraseMany()

◆ operator-=()

◆ intersect()

◆ operator&=()

◆ operator&()

◆ operator|()

◆ operator+()

◆ operator-()

◆ deref()