Top-level trie class-template using an adjaceny table. More...

Inheritance diagram for moot::TrieVector< DataT, CharT, UCharT >:

Collaboration diagram for moot::TrieVector< DataT, CharT, UCharT >:

Public Types
typedef DataT	data_type

typedef CharT	char_type

typedef UCharT	uchar_type

typedef TrieVector< data_type, char_type, uchar_type >	trie_type

typedef TrieVectorNode< data_type, char_type, uchar_type >	node_type

typedef std::vector< node_type >	vector_type

typedef vector_type::iterator	iterator

typedef vector_type::const_iterator	const_iterator

typedef std::string	string_type

typedef string_type::iterator	string_iterator

typedef string_type::const_iterator	const_string_iterator

typedef string_type::reverse_iterator	reverse_string_iterator

typedef string_type::const_reverse_iterator	const_reverse_string_iterator

typedef std::map< string_type, NodeId >	map_type

typedef map_type::iterator	map_iterator

typedef map_type::const_iterator	const_map_iterator

Public Types inherited from moot::TrieVectorBase
typedef size_t	NodeId

Public Member Functions
Constructors etc.
	TrieVector (size_t max_len=NoMaxLen, bool use_case=false)

	~TrieVector (void)

void	clear (void)

Accessors
const size_t &	maxlen (void) const

size_t &	maxlen (void)

bool	compiled (void) const

void	ensure_compiled (void)

const DataT &	default_data (void) const

DataT &	default_data (void)

Utilties
string_type	trie_canonicalize (string_type &s) const

void	trie_key (const string_type &s, const size_t max_len, string_type &dst) const

string_type	trie_key (const string_type &s, const size_t max_len) const

string_type	trie_key (const string_type &s) const

void	trie_rkey (const string_type &s, const size_t max_len, string_type &dst) const

string_type	trie_rkey (const string_type &s, size_t max_len) const

string_type	trie_rkey (const string_type &s) const

Insert
void	trie_insert (const string_type &s, size_t max_len)

void	trie_insert (const string_type &s)

void	trie_rinsert (const string_type &s, size_t max_len)

void	trie_rinsert (const string_type &s)

Low-Level Utilities
iterator	find_dtr (const node_type &from, CharT label)

const_iterator	find_dtr (const node_type &from, CharT label) const

NodeId	find_dtr_id (NodeId fromid, CharT label) const

iterator	first_dtr (const node_type &from)

const_iterator	first_dtr (const node_type &from) const

iterator	find_mother (const node_type &to)

const_iterator	find_mother (const node_type &to) const

NodeId	find_mother_id (NodeId toid) const

string_type	node_rstring (const node_type &node) const

string_type	node_rstring (NodeId nodeid) const

string_type	node_string (const node_type &node) const

string_type	node_string (NodeId nodeid) const

size_t	node_depth (const node_type &node) const

size_t	node_depth (NodeId nodeid) const

Compilation
void	compile (void)

Lookup
iterator	find_longest (const string_type &s, size_t *matchlen=__null)

const_iterator	find_longest (const string_type &s, size_t *matchlen=__null) const

iterator	rfind_longest (const string_type &s, size_t *matchlen=__null)

const_iterator	rfind_longest (const string_type &s, size_t *matchlen=__null) const

Public Member Functions inherited from moot::TrieVectorBase
	TrieVectorBase (size_t maxlen=NoMaxLen, bool use_case=false)

Public Attributes
map_type	trie_pending
	pending insertions More...

data_type	trie_default_data
	default data More...

Public Attributes inherited from moot::TrieVectorBase
size_t	trie_maxlen
	maximum trie depth More...

bool	trie_use_case
	whether to use case More...

Additional Inherited Members
Static Public Attributes inherited from moot::TrieVectorBase
static const NodeId	NoNode = static_cast<size_t>(-1)

static const size_t	NoMaxLen = static_cast<size_t>(-1)

Detailed Description

template<class DataT, typename CharT = char, typename UCharT = unsigned char>
class moot::TrieVector< DataT, CharT, UCharT >

Requirements for DataT:

must have a default constructor

Requirements for CharT

should support implicit conversion from integer constants (esp. zero)

Requirements for UCharT

must be an unsigned type
should be at least as wide as CharT

Member Typedef Documentation

◆ data_type

template<class DataT, typename CharT = char, typename UCharT = unsigned char>

typedef DataT moot::TrieVector< DataT, CharT, UCharT >::data_type

◆ char_type

template<class DataT, typename CharT = char, typename UCharT = unsigned char>

typedef CharT moot::TrieVector< DataT, CharT, UCharT >::char_type

◆ uchar_type

template<class DataT, typename CharT = char, typename UCharT = unsigned char>

typedef UCharT moot::TrieVector< DataT, CharT, UCharT >::uchar_type

◆ trie_type

template<class DataT, typename CharT = char, typename UCharT = unsigned char>

typedef TrieVector<data_type,char_type,uchar_type> moot::TrieVector< DataT, CharT, UCharT >::trie_type

◆ node_type

template<class DataT, typename CharT = char, typename UCharT = unsigned char>

typedef TrieVectorNode<data_type,char_type,uchar_type> moot::TrieVector< DataT, CharT, UCharT >::node_type

◆ vector_type

template<class DataT, typename CharT = char, typename UCharT = unsigned char>

typedef std::vector<node_type> moot::TrieVector< DataT, CharT, UCharT >::vector_type

◆ iterator

template<class DataT, typename CharT = char, typename UCharT = unsigned char>

typedef vector_type::iterator moot::TrieVector< DataT, CharT, UCharT >::iterator

◆ const_iterator

template<class DataT, typename CharT = char, typename UCharT = unsigned char>

typedef vector_type::const_iterator moot::TrieVector< DataT, CharT, UCharT >::const_iterator

◆ string_type

template<class DataT, typename CharT = char, typename UCharT = unsigned char>

typedef std::string moot::TrieVector< DataT, CharT, UCharT >::string_type

◆ string_iterator

template<class DataT, typename CharT = char, typename UCharT = unsigned char>

typedef string_type::iterator moot::TrieVector< DataT, CharT, UCharT >::string_iterator

◆ const_string_iterator

template<class DataT, typename CharT = char, typename UCharT = unsigned char>

typedef string_type::const_iterator moot::TrieVector< DataT, CharT, UCharT >::const_string_iterator

◆ reverse_string_iterator

template<class DataT, typename CharT = char, typename UCharT = unsigned char>

typedef string_type::reverse_iterator moot::TrieVector< DataT, CharT, UCharT >::reverse_string_iterator

◆ const_reverse_string_iterator

template<class DataT, typename CharT = char, typename UCharT = unsigned char>

typedef string_type::const_reverse_iterator moot::TrieVector< DataT, CharT, UCharT >::const_reverse_string_iterator

◆ map_type

template<class DataT, typename CharT = char, typename UCharT = unsigned char>

typedef std::map<string_type,NodeId> moot::TrieVector< DataT, CharT, UCharT >::map_type

◆ map_iterator

template<class DataT, typename CharT = char, typename UCharT = unsigned char>

typedef map_type::iterator moot::TrieVector< DataT, CharT, UCharT >::map_iterator

◆ const_map_iterator

template<class DataT, typename CharT = char, typename UCharT = unsigned char>

typedef map_type::const_iterator moot::TrieVector< DataT, CharT, UCharT >::const_map_iterator

Constructor & Destructor Documentation

◆ TrieVector()

template<class DataT, typename CharT = char, typename UCharT = unsigned char>

moot::TrieVector< DataT, CharT, UCharT >::TrieVector	(	size_t	max_len = `NoMaxLen`,
		bool	use_case = `false`
	)

inline

Default constructor

◆ ~TrieVector()

template<class DataT, typename CharT = char, typename UCharT = unsigned char>

moot::TrieVector< DataT, CharT, UCharT >::~TrieVector ( void )

inline

Destructor

Member Function Documentation

◆ clear()

template<class DataT, typename CharT = char, typename UCharT = unsigned char>

void moot::TrieVector< DataT, CharT, UCharT >::clear ( void )

inline

Clear

Referenced by mootBinIO::Item< SuffixTrie >::load().

◆ maxlen() [1/2]

template<class DataT, typename CharT = char, typename UCharT = unsigned char>

const size_t& moot::TrieVector< DataT, CharT, UCharT >::maxlen ( void ) const

inline

Get maximum length for this trie (read-only)

◆ maxlen() [2/2]

template<class DataT, typename CharT = char, typename UCharT = unsigned char>

size_t& moot::TrieVector< DataT, CharT, UCharT >::maxlen ( void )

inline

Get maximum length for this trie (read/write)

◆ compiled()

template<class DataT, typename CharT = char, typename UCharT = unsigned char>

bool moot::TrieVector< DataT, CharT, UCharT >::compiled ( void ) const

inline

Check whether this trie is compiled

◆ ensure_compiled()

template<class DataT, typename CharT = char, typename UCharT = unsigned char>

void moot::TrieVector< DataT, CharT, UCharT >::ensure_compiled ( void )

inline

Ensure that this trie is compiled

◆ default_data() [1/2]

template<class DataT, typename CharT = char, typename UCharT = unsigned char>

const DataT& moot::TrieVector< DataT, CharT, UCharT >::default_data ( void ) const

inline

Get default data (read-only)

◆ default_data() [2/2]

template<class DataT, typename CharT = char, typename UCharT = unsigned char>

DataT& moot::TrieVector< DataT, CharT, UCharT >::default_data ( void )

inline

Get default data (read-write)

◆ trie_canonicalize()

template<class DataT, typename CharT = char, typename UCharT = unsigned char>

string_type moot::TrieVector< DataT, CharT, UCharT >::trie_canonicalize ( string_type & s ) const

inline

Canonicalize case of a string

◆ trie_key() [1/3]

template<class DataT, typename CharT = char, typename UCharT = unsigned char>

void moot::TrieVector< DataT, CharT, UCharT >::trie_key	(	const string_type &	s,
		const size_t	max_len,
		string_type &	dst
	)		const

inline

Assign valid prefix-key of up to characters from to

◆ trie_key() [2/3]

template<class DataT, typename CharT = char, typename UCharT = unsigned char>

string_type moot::TrieVector< DataT, CharT, UCharT >::trie_key	(	const string_type &	s,
		const size_t	max_len
	)		const

inline

Create and return a valid prefix-key of up to characters from

◆ trie_key() [3/3]

template<class DataT, typename CharT = char, typename UCharT = unsigned char>

string_type moot::TrieVector< DataT, CharT, UCharT >::trie_key ( const string_type & s ) const

inline

Create and return a valid prefix-key of up to characters from

◆ trie_rkey() [1/3]

template<class DataT, typename CharT = char, typename UCharT = unsigned char>

void moot::TrieVector< DataT, CharT, UCharT >::trie_rkey	(	const string_type &	s,
		const size_t	max_len,
		string_type &	dst
	)		const

inline

Assign valid suffix-key of up to characters from to

◆ trie_rkey() [2/3]

template<class DataT, typename CharT = char, typename UCharT = unsigned char>

string_type moot::TrieVector< DataT, CharT, UCharT >::trie_rkey	(	const string_type &	s,
		size_t	max_len
	)		const

inline

Create and return a valid suffix-key of up to characters from

◆ trie_rkey() [3/3]

template<class DataT, typename CharT = char, typename UCharT = unsigned char>

string_type moot::TrieVector< DataT, CharT, UCharT >::trie_rkey ( const string_type & s ) const

inline

Create and return a valid suffix-key of up to characters from

◆ trie_insert() [1/2]

template<class DataT, typename CharT = char, typename UCharT = unsigned char>

void moot::TrieVector< DataT, CharT, UCharT >::trie_insert	(	const string_type &	s,
		size_t	max_len
	)

inline

Insert a prefix-key into the pending-queue, giving maximum length

◆ trie_insert() [2/2]

template<class DataT, typename CharT = char, typename UCharT = unsigned char>

void moot::TrieVector< DataT, CharT, UCharT >::trie_insert ( const string_type & s )

inline

Insert a prefix-key into the pending-queue, using trie-internal maximum length

◆ trie_rinsert() [1/2]

template<class DataT, typename CharT = char, typename UCharT = unsigned char>

void moot::TrieVector< DataT, CharT, UCharT >::trie_rinsert	(	const string_type &	s,
		size_t	max_len
	)

inline

Insert a suffix-key into the pending-queue, giving maximum length

◆ trie_rinsert() [2/2]

template<class DataT, typename CharT = char, typename UCharT = unsigned char>

void moot::TrieVector< DataT, CharT, UCharT >::trie_rinsert ( const string_type & s )

inline

Insert a suffix-key into the pending-queue, using trie-internal maximum length

◆ find_dtr() [1/2]

template<class DataT, typename CharT = char, typename UCharT = unsigned char>

iterator moot::TrieVector< DataT, CharT, UCharT >::find_dtr	(	const node_type &	from,
		CharT	label
	)

inline

Daughter lookup, iterator, read/write

Find the daughter of the node on label . On success, returns an iterator pointing to the daughter. Returns end() if no such daughter exists.

Requires a compiled transition table.
should be a valid node

◆ find_dtr() [2/2]

template<class DataT, typename CharT = char, typename UCharT = unsigned char>

const_iterator moot::TrieVector< DataT, CharT, UCharT >::find_dtr	(	const node_type &	from,
		CharT	label
	)		const

inline

Daughter lookup, iterator, read-only

◆ find_dtr_id()

template<class DataT, typename CharT = char, typename UCharT = unsigned char>

NodeId moot::TrieVector< DataT, CharT, UCharT >::find_dtr_id	(	NodeId	fromid,
		CharT	label
	)		const

inline

Daughter lookup, NodeId, read-only

◆ first_dtr() [1/2]

template<class DataT, typename CharT = char, typename UCharT = unsigned char>

iterator moot::TrieVector< DataT, CharT, UCharT >::first_dtr ( const node_type & from )

inline

Daughter iteration, read/write

Find the first daughter of the node . On success, returns an iterator pointing to the daughter. Returns end() if no such daughter exists.

Requires a compiled transition table.
should be a valid node

◆ first_dtr() [2/2]

template<class DataT, typename CharT = char, typename UCharT = unsigned char>

const_iterator moot::TrieVector< DataT, CharT, UCharT >::first_dtr ( const node_type & from ) const

inline

Daughter lookup, iterator, read-only

◆ find_mother() [1/2]

template<class DataT, typename CharT = char, typename UCharT = unsigned char>

iterator moot::TrieVector< DataT, CharT, UCharT >::find_mother ( const node_type & to )

inline

Mother lookup, iterator, read/write

Find the mother of the node . On success, returns an iterator pointing to the mother. Returns end() if is the root node.

Requires a compiled transition table.
should be a valid node

◆ find_mother() [2/2]

template<class DataT, typename CharT = char, typename UCharT = unsigned char>

const_iterator moot::TrieVector< DataT, CharT, UCharT >::find_mother ( const node_type & to ) const

inline

Mother lookup, iterator, read-only

◆ find_mother_id()

template<class DataT, typename CharT = char, typename UCharT = unsigned char>

NodeId moot::TrieVector< DataT, CharT, UCharT >::find_mother_id ( NodeId toid ) const

inline

Mother lookup, NodeId, read-only

◆ node_rstring() [1/2]

template<class DataT, typename CharT = char, typename UCharT = unsigned char>

string_type moot::TrieVector< DataT, CharT, UCharT >::node_rstring ( const node_type & node ) const

inline

Get full path to node as a reverse string

◆ node_rstring() [2/2]

template<class DataT, typename CharT = char, typename UCharT = unsigned char>

string_type moot::TrieVector< DataT, CharT, UCharT >::node_rstring ( NodeId nodeid ) const

inline

Get full path to node with id as a string

◆ node_string() [1/2]

template<class DataT, typename CharT = char, typename UCharT = unsigned char>

string_type moot::TrieVector< DataT, CharT, UCharT >::node_string ( const node_type & node ) const

inline

Get full path to node as a string

◆ node_string() [2/2]

template<class DataT, typename CharT = char, typename UCharT = unsigned char>

string_type moot::TrieVector< DataT, CharT, UCharT >::node_string ( NodeId nodeid ) const

inline

Get full path to node with id as a string

◆ node_depth() [1/2]

template<class DataT, typename CharT = char, typename UCharT = unsigned char>

size_t moot::TrieVector< DataT, CharT, UCharT >::node_depth ( const node_type & node ) const

inline

Get depth of node

◆ node_depth() [2/2]

template<class DataT, typename CharT = char, typename UCharT = unsigned char>

size_t moot::TrieVector< DataT, CharT, UCharT >::node_depth ( NodeId nodeid ) const

inline

Get depth of node with id

◆ compile()

template<class DataT, typename CharT = char, typename UCharT = unsigned char>

void moot::TrieVector< DataT, CharT, UCharT >::compile ( void )

inline

Build transition table from the map of pending keys

◆ find_longest() [1/2]

template<class DataT, typename CharT = char, typename UCharT = unsigned char>

iterator moot::TrieVector< DataT, CharT, UCharT >::find_longest	(	const string_type &	s,
		size_t *	matchlen = `__null`
	)

inline

Forward lookup, read/write

Lookup longest match (of up to characters) for string , reading from left to right. Returns a iterator pointing to the deepest matching node and sets * to the number of characters actually matched. Returns end() on failure.

◆ find_longest() [2/2]

template<class DataT, typename CharT = char, typename UCharT = unsigned char>

const_iterator moot::TrieVector< DataT, CharT, UCharT >::find_longest	(	const string_type &	s,
		size_t *	matchlen = `__null`
	)		const

inline

Forward lookup, read-only

◆ rfind_longest() [1/2]

template<class DataT, typename CharT = char, typename UCharT = unsigned char>

iterator moot::TrieVector< DataT, CharT, UCharT >::rfind_longest	(	const string_type &	s,
		size_t *	matchlen = `__null`
	)

inline

Reverse lookup, read/write

Like find_longest(), but reads backwards from the end of .

◆ rfind_longest() [2/2]

template<class DataT, typename CharT = char, typename UCharT = unsigned char>

const_iterator moot::TrieVector< DataT, CharT, UCharT >::rfind_longest	(	const string_type &	s,
		size_t *	matchlen = `__null`
	)		const

inline

Reverse lookup, read-only

Member Data Documentation

◆ trie_pending

template<class DataT, typename CharT = char, typename UCharT = unsigned char>

map_type moot::TrieVector< DataT, CharT, UCharT >::trie_pending

◆ trie_default_data

template<class DataT, typename CharT = char, typename UCharT = unsigned char>

data_type moot::TrieVector< DataT, CharT, UCharT >::trie_default_data

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

mootTrieVector.h

Public Types

Public Member Functions

Public Attributes

Additional Inherited Members

Detailed Description

template<class DataT, typename CharT = char, typename UCharT = unsigned char> class moot::TrieVector< DataT, CharT, UCharT >

Member Typedef Documentation

◆ data_type

◆ char_type

◆ uchar_type

◆ trie_type

◆ node_type

◆ vector_type

◆ iterator

◆ const_iterator

◆ string_type

◆ string_iterator

◆ const_string_iterator

◆ reverse_string_iterator

◆ const_reverse_string_iterator

◆ map_type

◆ map_iterator

◆ const_map_iterator

Constructor & Destructor Documentation

◆ TrieVector()

◆ ~TrieVector()

Member Function Documentation

◆ clear()

◆ maxlen() [1/2]

◆ maxlen() [2/2]

◆ compiled()

◆ ensure_compiled()

◆ default_data() [1/2]

◆ default_data() [2/2]

◆ trie_canonicalize()

◆ trie_key() [1/3]

◆ trie_key() [2/3]

◆ trie_key() [3/3]

◆ trie_rkey() [1/3]

◆ trie_rkey() [2/3]

◆ trie_rkey() [3/3]

◆ trie_insert() [1/2]

◆ trie_insert() [2/2]

◆ trie_rinsert() [1/2]

◆ trie_rinsert() [2/2]

◆ find_dtr() [1/2]

◆ find_dtr() [2/2]

◆ find_dtr_id()

◆ first_dtr() [1/2]

◆ first_dtr() [2/2]

◆ find_mother() [1/2]

◆ find_mother() [2/2]

◆ find_mother_id()

◆ node_rstring() [1/2]

◆ node_rstring() [2/2]

◆ node_string() [1/2]

◆ node_string() [2/2]

◆ node_depth() [1/2]

◆ node_depth() [2/2]

◆ compile()

◆ find_longest() [1/2]

◆ find_longest() [2/2]

◆ rfind_longest() [1/2]

◆ rfind_longest() [2/2]

Member Data Documentation

◆ trie_pending

◆ trie_default_data

template<class DataT, typename CharT = char, typename UCharT = unsigned char>
class moot::TrieVector< DataT, CharT, UCharT >