regina::NTypeTrie< nTypes > Class Template Reference
Vertex Enumeration

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

## Detailed Description

### template<int nTypes>
class regina::NTypeTrie< nTypes >

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 (to appear), DOI 10.1007/s00453-012-9645-3.

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

Precondition
  nTypes is at most 256. The typical value for nTypes for normal surface enumeration is nTypes = 4.

Python:
  Not present.

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

- enumerate/ntypetrie.h

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