Regina Calculation Engine
|
A trie-like data structure for storing and retriving sets. More...
#include <utilities/trieset.h>
Public Member Functions | |
TrieSet () | |
Constructs an empty collection of sets. More... | |
~TrieSet () | |
Destroys this collection of sets. More... | |
void | insert (const T &entry) |
Insert the given set into this collection. More... | |
bool | hasSubset (const T &superset, unsigned long universeSize) const |
Determines whether this collection of sets contains any subset of the argument superset. More... | |
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... | |
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. Sets are represented as bitmasks of type T (which must be capable of holding bitmasks of length n). 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.