A trie-like data structure for storing and retriving sets. More...

#include <utilities/trieset.h>

Inheritance diagram for regina::TrieSet:

Public Member Functions
	TrieSet ()=default
	Constructs an empty collection of sets. More...

	TrieSet (const TrieSet &src)
	Creates a new copy of the given collection. More...

	TrieSet (TrieSet &&src) noexcept
	Moves the contents of the given collection into this new collection. More...

TrieSet &	operator= (const TrieSet &src)
	Sets this to be a copy of the given collection. More...

TrieSet &	operator= (TrieSet &&src) noexcept
	Moves the contents of the given collection into this collection. More...

void	swap (TrieSet &other) noexcept
	Swaps the contents of this and the given collection. More...

bool	operator== (const TrieSet &other) const
	Determines whether this and the given collection store exactly the same sets. More...

bool	operator!= (const TrieSet &other) const
	Determines whether this and the given collection do not store exactly the same sets. More...

template<typename T >
void	insert (const T &entry)
	Insert the given set into this collection. More...

template<typename T >
bool	hasSubset (const T &superset, unsigned long universeSize) const
	Determines whether this collection of sets contains any subset of the argument superset. More...

template<typename T >
bool	hasExtraSuperset (const T &subset, const T &exc1, const T &exc2, unsigned long universeSize) const
	Performs the particular superset search required by the double description method. More...

void	writeTextShort (std::ostream &out) const
	Writes a short text representation of this object to the given output stream. More...

void	writeTextLong (std::ostream &out) const
	Writes a detailed text representation of this object to the given output stream. More...

std::string	str () const
	Returns a short text representation of this object. More...

std::string	utf8 () const
	Returns a short text representation of this object using unicode characters. More...

std::string	detail () const
	Returns a detailed text representation of this object. More...

Detailed Description

A trie-like data structure for storing and retriving sets.

This class is useful when the elements of these sets are taken from a fairly small universe, but where the number of sets being stored can be extremely large.

For simplicity, let the universe consist of the integers 0,...,(n-1). Sets are represented as bitmasks of length n (using one of Regina's bitmask types, such as Bitmask, Bitmask1 or Bitmask2). The ith bit of a bitmask indicates whether the integer i belongs to the corresponding set.

To construct an empty trie, simply call the default constructor. To insert a new set into the trie, call insert() (whose running time is linear in n). You can insert the same set into the trie multiple times and the trie will record the number of times that it occurs.

Currently the only searching operations are hasSubset() and hasExtraSuperset(). These operations are slow, but still much faster than searching through a linear list; see the hasSubset() and hasExtraSuperset() documentation for details.

The implementation of this data structure uses a binary tree with depth levels 0,...,n, where each node at level i represents a potential length-i prefix for a bitmask. So, for instance, the root node represents the empty prefix, its children represent prefixes 0 and 1, their children represent prefixes 00, 01, 10 and 11, and so on.

Internally, a set is "stored" at the first node whose prefix in fact describes the entire set. For instance, the bitmask 101100 is stored at the node corresponding to the prefix 1011, which occurs at level 3 of the tree. Regions of the tree that do not store any sets are never explicitly constructed in memory.

This class implements C++ move semantics and adheres to the C++ Swappable requirement. It is designed to avoid deep copies wherever possible, even when passing or returning objects by value.

Constructor & Destructor Documentation

◆ TrieSet() [1/3]

regina::TrieSet::TrieSet ( )

default

Constructs an empty collection of sets.

◆ TrieSet() [2/3]

regina::TrieSet::TrieSet ( const TrieSet & src )

Creates a new copy of the given collection.

This will induce a deep copy of src.

Parameters

src	the collection of sets to copy.

◆ TrieSet() [3/3]

regina::TrieSet::TrieSet ( TrieSet && src )

inlinenoexcept

Moves the contents of the given collection into this new collection.

This is a fast (constant time) operation.

The collection that was passed (src) will no longer be usable.

Parameters

src	the collection of sets whose contents should be moved.

Member Function Documentation

◆ detail()

std::string regina::Output< TrieSet , false >::detail ( ) const

inherited

Returns a detailed text representation of this object.

This text may span many lines, and should provide the user with all the information they could want. It should be human-readable, should not contain extremely long lines (which cause problems for users reading the output in a terminal), and should end with a final newline. There are no restrictions on the underlying character set.

Returns: a detailed text representation of this object.

◆ hasExtraSuperset()

template<typename T >

bool regina::TrieSet::hasExtraSuperset	(	const T &	subset,
		const T &	exc1,
		const T &	exc2,
		unsigned long	universeSize
	)		const

Performs the particular superset search required by the double description method.

This routine asks the following question: In this collection of sets, is there any superset of the argument subset other than exc1 or exc2? Here the sets exc1 and exc2 are explicitly excluded from our search. Supersets need not be proper supersets (so if an exact copy of subset is found in the tree then this will suffice).

This routine has a slow running time, which in pathological cases can grow to either 2^n (where n is the bitmask length) or the number of sets stored in this collection, whichever is smaller. However, for "typical" searches in the context of normal surface enumeration, the running time is often significantly faster.

Precondition: The sets exc1 and exc2 are distinct, and each is contained in this collection precisely once.

Template Parameters

T	One of Regina's bitmask types, such as Bitmask, Bitmask1 or Bitmask2.

Parameters

subset	the object of the query: we are searching this collection for a (non-strict) superset of this argument.
exc1	the first set in the collection to be excluded from this search.
exc2	the second set in the collection to be excluded from this search.
universeSize	the number of elements in the underlying universe (and therefore the lowest possible level in the search tree). This must be less than or equal to the number of bits that the underlying bitmask type T can support.

Returns: true if a superset with the required properties was found, or false otherwise.

◆ hasSubset()

template<typename T >

bool regina::TrieSet::hasSubset	(	const T &	superset,
		unsigned long	universeSize
	)		const

Determines whether this collection of sets contains any subset of the argument superset.

Subsets need not be proper subsets (so if an exact copy of superset is found in the tree then this will suffice).

This routine has a slow running time, which in pathological cases can grow to either 2^n (where n is the bitmask length) or the number of sets stored in this collection, whichever is smaller. However, for "typical" searches in the context of normal surface enumeration, the running time is often significantly faster.

Template Parameters

T	One of Regina's bitmask types, such as Bitmask, Bitmask1 or Bitmask2.

Parameters

superset	the object of the query: we are searching this collection for a (non-strict) subset of this argument.
universeSize	the number of elements in the underlying universe (and therefore the lowest possible level in the search tree). This must be less than or equal to the number of bits that the underlying bitmask type T can support.

Returns: true if a subset was found, or false otherwise.

◆ insert()

template<typename T >

void regina::TrieSet::insert ( const T & entry )

Insert the given set into this collection.

The same set may be insert into this collection multiple times (and this multiplicity will be recorded correctly).

Running time for insertion is O(n), where n is the bitmask length.

Template Parameters

T	One of Regina's bitmask types, such as Bitmask, Bitmask1 or Bitmask2.

Parameters

entry the new set to insert.

◆ operator!=()

bool regina::TrieSet::operator!= ( const TrieSet & other ) const

inline

Determines whether this and the given collection do not store exactly the same sets.

Parameters

other the collection to compare with this.

Returns: true if and only if both collections do not store the same sets.

◆ operator=() [1/2]

TrieSet & regina::TrieSet::operator= ( const TrieSet & src )

Sets this to be a copy of the given collection.

This will induce a deep copy of src.

Parameters

src	the collection of sets to copy.

Returns: a reference to this collection.

◆ operator=() [2/2]

TrieSet & regina::TrieSet::operator= ( TrieSet && src )

inlinenoexcept

Moves the contents of the given collection into this collection.

This is a fast (constant time) operation.

The collection that was passed (src) will no longer be usable.

Parameters

src	the collection of sets whose contents should be moved.

Returns: a reference to this collection.

◆ operator==()

bool regina::TrieSet::operator== ( const TrieSet & other ) const

Determines whether this and the given collection store exactly the same sets.

Parameters

other the collection to compare with this.

Returns: true if and only if both collections store the same sets.

◆ str()

std::string regina::Output< TrieSet , false >::str ( ) const

inherited

Returns a short text representation of this object.

This text should be human-readable, should use plain ASCII characters where possible, and should not contain any newlines.

Within these limits, this short text ouptut should be as information-rich as possible, since in most cases this forms the basis for the Python str() and repr() functions.

Python: The Python "stringification" function str() will use precisely this function, and for most classes the Python repr() function will incorporate this into its output.

Returns: a short text representation of this object.

◆ swap()

void regina::TrieSet::swap ( TrieSet & other )

inlinenoexcept

Swaps the contents of this and the given collection.

Parameters

other the collection whose contents should be swapped with this.

◆ utf8()

std::string regina::Output< TrieSet , false >::utf8 ( ) const

inherited

Returns a short text representation of this object using unicode characters.

Like str(), this text should be human-readable, should not contain any newlines, and (within these constraints) should be as information-rich as is reasonable.

Unlike str(), this function may use unicode characters to make the output more pleasant to read. The string that is returned will be encoded in UTF-8.

Returns: a short text representation of this object.

◆ writeTextLong()

void regina::TrieSet::writeTextLong ( std::ostream & out ) const

Writes a detailed text representation of this object to the given output stream.

Python: Not present; use detail() instead.

Parameters

out	the output stream to which to write.

◆ writeTextShort()

void regina::TrieSet::writeTextShort ( std::ostream & out ) const

inline

Writes a short text representation of this object to the given output stream.

Python: Not present; use str() instead.

Parameters

out	the output stream to which to write.

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

utilities/trieset.h

Public Member Functions

Detailed Description

Constructor & Destructor Documentation

◆ TrieSet() [1/3]

◆ TrieSet() [2/3]

◆ TrieSet() [3/3]

Member Function Documentation

◆ detail()

◆ hasExtraSuperset()

◆ hasSubset()

◆ insert()

◆ operator!=()

◆ operator=() [1/2]

◆ operator=() [2/2]

◆ operator==()

◆ str()

◆ swap()

◆ utf8()

◆ writeTextLong()

◆ writeTextShort()