Regina Calculation Engine
Public Member Functions | List of all members
regina::NTrieSet< T > Class Template Reference

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

#include <utilities/ntrieset.h>

Public Member Functions

 NTrieSet ()
 Constructs an empty collection of sets. More...
 
 ~NTrieSet ()
 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...
 

Detailed Description

template<typename T>
class regina::NTrieSet< T >

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.

Precondition
The template argument T is one of Regina's bitmask types, such as NBitmask, NBitmask1 or NBitmask2.
Python:
Not present.

Constructor & Destructor Documentation

template<typename T >
regina::NTrieSet< T >::NTrieSet ( )
inline

Constructs an empty collection of sets.

template<typename T >
regina::NTrieSet< T >::~NTrieSet ( )
inline

Destroys this collection of sets.

Member Function Documentation

template<typename T >
bool regina::NTrieSet< T >::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.
Parameters
subsetthe object of the query: we are searching this collection for a (non-strict) superset of this argument.
exc1the first set in the collection to be excluded from this search.
exc2the second set in the collection to be excluded from this search.
universeSizethe number of elements in the underlying universe (and therefore the lowest possible level in the search tree). Note that this is always 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.
template<typename T >
bool regina::NTrieSet< T >::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.

Parameters
supersetthe object of the query: we are searching this collection for a (non-strict) subset of this argument.
universeSizethe number of elements in the underlying universe (and therefore the lowest possible level in the search tree). Note that this is always 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.
template<typename T >
void regina::NTrieSet< T >::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.

Parameters
entrythe new set to insert.

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

Copyright © 1999-2013, The Regina development team
This software is released under the GNU General Public License, with some additional permissions; see the source code for details.
For further information, or to submit a bug or other problem, please contact Ben Burton (bab@debian.org).