Regina Calculation Engine
|
A trie that stores a set of type vectors of a fixed length. More...
#include <enumerate/ntypetrie.h>
Public Member Functions | |
NTypeTrie () | |
Initialises an empty trie. More... | |
~NTypeTrie () | |
Destroys this trie. More... | |
void | clear () |
Resets this to the empty trie. More... | |
void | insert (const char *entry, unsigned len) |
Inserts the given type vector into this trie. More... | |
bool | dominates (const char *vec, unsigned len) const |
Determines whether the given type vector dominates any vector in this trie. More... | |
A trie that stores a set of type vectors of a fixed length.
This class forms part of the tree traversal algorithm for enumerating vertex normal surfaces, as described in "A tree traversal algorithm for decision problems in knot theory and 3-manifold topology", Burton and Ozlen, Algorithmica 65:4 (2013), pp. 772-801.
A type vector is a sequence of digits, each between 0 and nTypes-1 inclusive. Type vectors are represented as arrays of characters: these are not strings, but simply sequences of one-byte integers. In particular, you cannot print them (since they use raw integer values, not ASCII digits). The length of a type vector must be passed alongside it (i.e., there is no special terminating character).
A type vector v is said to dominate u if, for each position i, either v[i] == u[i] or else u[i] == 0. So, for instance, (1,0,2,3) dominates (1,0,2,0), which in turn dominates (1,0,0,0). Domination is a partial order, not a total order: for instance, neither of (1,0,2,0) or (1,0,3,0) dominates the other.
We assume that all type vectors used in this trie have the same length. This is important, since we optimise the implementation by ignoring trailing zeroes, which means that this trie cannot distinguish between a vector v and the same vector with additional zeroes appended to its end.
Internally, each node of the trie is represented by a separate NTypeTrie object, each of which is responsible for managing the lifespan of its descendant nodes. Externally, a user only needs to create and manage a single NTypeTrie object (which becomes the root of the trie).