A trie that stores a set of type vectors of a fixed length. More...

#include <enumerate/typetrie.h>

Inheritance diagram for regina::TypeTrie< nTypes >:

Public Member Functions
	TypeTrie ()=default
	Creates an empty trie. More...

	TypeTrie (const TypeTrie &src)
	Creates a new copy of the given trie. More...

	TypeTrie (TypeTrie &&src) noexcept
	Moves the contents of the given trie into this new trie. More...

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

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

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

bool	operator== (const TypeTrie &other) const
	Determines whether this and the given trie store exactly the same type vectors. More...

bool	operator!= (const TypeTrie &other) const
	Determines whether this and the given trie do not store exactly the same type vectors. More...

void	clear ()
	Resets this to the empty trie. More...

void	insert (const char *entry, size_t len)
	Inserts the given type vector into this trie. More...

bool	dominates (const char *vec, size_t len) const
	Determines whether the given type vector dominates any vector in this trie. 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

template<int nTypes>
class regina::TypeTrie< 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 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.

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. However, be aware that the cost of moving is linear in the template parameter nTypes (which, as noted below, is usually very small).

Precondition: nTypes is between 1 and 256 inclusive. The typical value for nTypes for normal surface enumeration is either 4 or 7 (depending upon whether we are supporting almost normal surfaces).

Python: This is available only for the template parameters nTypes = 4 and 7, under the names TypeTrie4 and TypeTrie7 respectively.

Constructor & Destructor Documentation

◆ TypeTrie() [1/3]

template<int nTypes>

regina::TypeTrie< nTypes >::TypeTrie ( )

default

Creates an empty trie.

◆ TypeTrie() [2/3]

template<int nTypes>

regina::TypeTrie< nTypes >::TypeTrie ( const TypeTrie< nTypes > & src )

Creates a new copy of the given trie.

This will induce a deep copy of src.

Parameters

src	the trie to copy.

◆ TypeTrie() [3/3]

template<int nTypes>

regina::TypeTrie< nTypes >::TypeTrie ( TypeTrie< nTypes > && src )

inlinenoexcept

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

This is operation is constant time in the size of the trie, but linear time in the template parameter nTypes.

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

Parameters

src	the trie whose contents should be moved.

Member Function Documentation

◆ clear()

template<int nTypes>

void regina::TypeTrie< nTypes >::clear

inline

Resets this to the empty trie.

◆ detail()

std::string regina::Output< TypeTrie< nTypes > , 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.

◆ dominates()

template<int nTypes>

bool regina::TypeTrie< nTypes >::dominates	(	const char *	vec,
		size_t	len
	)		const

Determines whether the given type vector dominates any vector in this trie.

Precondition: The given length len is non-zero, and is fixed throughout the life of this trie; that is, it is the same every time insert() or dominates() is called.

Python: Instead of the arguments vec and len, you should pass a single argument which is a python sequence of length len. This list should be a type vector, and each list element should be between 0 and (nTypes - 1) inclusive.

Parameters

vec	the type vector to test.
len	the number of elements in the given type vector.

Returns: true if and only if vec dominates some type vector stored in this trie.

◆ insert()

template<int nTypes>

void regina::TypeTrie< nTypes >::insert	(	const char *	entry,
		size_t	len
	)

Inserts the given type vector into this trie.

Precondition: The given length len is non-zero, and is fixed throughout the life of this trie; that is, it is the same every time insert() or dominates() is called.

Python: Instead of the arguments entry and len, you should pass a single argument which is a python sequence of length len. This list should be a type vector, and each list element should be between 0 and (nTypes - 1) inclusive.

Parameters

entry	the type vector to insert.
len	the number of elements in the given type vector.

◆ operator!=()

template<int nTypes>

bool regina::TypeTrie< nTypes >::operator!= ( const TypeTrie< nTypes > & other ) const

inline

Determines whether this and the given trie do not store exactly the same type vectors.

Parameters

other the trie to compare with this.

Returns: true if and only if both tries do not store the same type vectors.

◆ operator=() [1/2]

template<int nTypes>

TypeTrie< nTypes > & regina::TypeTrie< nTypes >::operator= ( const TypeTrie< nTypes > & src )

Sets this to be a copy of the given trie.

This will induce a deep copy of src.

Parameters

src	the trie to copy.

Returns: a reference to this trie.

◆ operator=() [2/2]

template<int nTypes>

TypeTrie< nTypes > & regina::TypeTrie< nTypes >::operator= ( TypeTrie< nTypes > && src )

inlinenoexcept

Moves the contents of the given trie into this trie.

This is operation is constant time in the size of the trie, but linear time in the template parameter nTypes.

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

Parameters

src	the trie whose contents should be moved.

Returns: a reference to this trie.

◆ operator==()

template<int nTypes>

bool regina::TypeTrie< nTypes >::operator== ( const TypeTrie< nTypes > & other ) const

Determines whether this and the given trie store exactly the same type vectors.

Parameters

other the trie to compare with this.

Returns: true if and only if both tries store the same type vectors.

◆ str()

std::string regina::Output< TypeTrie< nTypes > , 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()

template<int nTypes>

void regina::TypeTrie< nTypes >::swap ( TypeTrie< nTypes > & other )

inlinenoexcept

Swaps the contents of this and the given trie.

Parameters

other the trie whose contents should be swapped with this.

◆ utf8()

std::string regina::Output< TypeTrie< nTypes > , 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()

template<int nTypes>

void regina::TypeTrie< nTypes >::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()

template<int nTypes>

void regina::TypeTrie< nTypes >::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:

enumerate/typetrie.h

Public Member Functions

Detailed Description

Constructor & Destructor Documentation

◆ TypeTrie() [1/3]

◆ TypeTrie() [2/3]

◆ TypeTrie() [3/3]

Member Function Documentation

◆ clear()

◆ detail()

◆ dominates()

◆ insert()

◆ operator!=()

◆ operator=() [1/2]

◆ operator=() [2/2]

◆ operator==()

◆ str()

◆ swap()

◆ utf8()

◆ writeTextLong()

◆ writeTextShort()