An object based trie used for parent-child hierarchies. More...

#include <ObjectTrie.hpp>

Classes
class	BreadthIterator
	A breadth first iterator for the trie. More...

class	ConstBreadthIterator
	A breadth first const iterator for the trie. More...

class	ConstDepthIterator
	A depth first const iterator for the trie. More...

class	DepthIterator
	A depth first iterator for the trie. More...

Public Types
using	const_iterator = ConstDepthIterator
	Default (depth first) const iterator. More...

using	iterator = DepthIterator
	Default (depth first) iterator. More...

Public Member Functions
	ObjectTrie ()=default
	Construct the trie with a root value equal to the default construction of T. More...

	ObjectTrie (const T &trieRoot_)
	Construct the trie by making a copy of the supplied root value. More...

	ObjectTrie (T &&trieRoot_)
	Construct the trie by moving the supplied root value. More...

	ObjectTrie (const ObjectTrie< T > &copy)
	Create a trie by copying an existing trie. More...

	ObjectTrie (ObjectTrie< T > &&rhs) noexcept
	Move a trie. More...

template<typename ... ObjectAdderT>
ObjectTrieNode< T > &	add (T &&value, ObjectAdderT &&... childNode)
	Append a child containing the supplied data to the root node, plus children of the new child. More...

ObjectTrieNode< T > &	add (const T &value)
	Append a child containing a copy of the supplied data to the root node. More...

ObjectTrieNode< T > &	add (T &&value)
	Append a child containing the supplied data to the root node. More...

ObjectTrieNode< T > &	addAndReturnChild (const T &value)
	Append a root node child containing a copy of the supplied data. More...

ObjectTrieNode< T > &	addAndReturnChild (T &&value)
	Append a root node child containing a the supplied data. More...

ObjectTrieNode< T > &	addOrReplace (const T &value)
	Append a child containing the supplied data to the root node if a child equal to the supplied value is not present, otherwise replace it. More...

ObjectTrieNode< T > &	addOrReplace (T &&value)
	Append a child containing the supplied data to the root node if a child equal to the supplied value is not present, otherwise replace it. More...

template<typename CompareT >
ObjectTrieNode< T > &	addOrReplace (const T &value, CompareT compare)
	Append a child containing the supplied data to the root node if a child equal to the supplied value is not present, otherwise replace it. More...

template<typename CompareT >
ObjectTrieNode< T > &	addOrReplace (T &&value, CompareT compare)
	Append a child containing the supplied data to the root node if a child equal to the supplied value is not present, otherwise replace it. More...

template<typename CompareT , typename ReplaceT >
ObjectTrieNode< T > &	addOrReplace (const T &value, CompareT compare, ReplaceT replace)
	Append a child containing the supplied data to the root node if a child equal to the supplied value is not present, otherwise replace it. More...

template<typename CompareT , typename ReplaceT >
ObjectTrieNode< T > &	addOrReplace (T &&value, CompareT compare, ReplaceT replace)
	Append a child containing the supplied data to the root node if a child equal to the supplied value is not present, otherwise replace it. More...

ObjectTrieNode< T > &	addOrReplaceAndReturnChild (const T &value)
	Append a root node child containing a copy of the supplied data if a child equal to the supplied value is not present, otherwise replace it. More...

ObjectTrieNode< T > &	addOrReplaceAndReturnChild (T &&value)
	Append a root node child containing a copy of the supplied data if a child equal to the supplied value is not present, otherwise replace it. More...

template<typename CompareT >
ObjectTrieNode< T > &	addOrReplaceAndReturnChild (const T &value, CompareT compare)
	Append a root node child containing a copy of the supplied data if a child equal to the supplied value is not present, otherwise replace it. More...

template<typename CompareT >
ObjectTrieNode< T > &	addOrReplaceAndReturnChild (T &&value, CompareT compare)
	Append a root node child containing a copy of the supplied data if a child equal to the supplied value is not present, otherwise replace it. More...

template<typename CompareT , typename ReplaceT >
ObjectTrieNode< T > &	addOrReplaceAndReturnChild (const T &value, CompareT compare, ReplaceT replace)
	Append a root node child containing a copy of the supplied data if a child equal to the supplied value is not present, otherwise replace it. More...

template<typename CompareT , typename ReplaceT >
ObjectTrieNode< T > &	addOrReplaceAndReturnChild (T &&value, CompareT compare, ReplaceT replace)
	Append a root node child containing a copy of the supplied data if a child equal to the supplied value is not present, otherwise replace it. More...

DepthIterator	begin ()
	Get a depth iterator positioned at the beginning of the trie. More...

ConstDepthIterator	begin () const
	Get a const depth iterator positioned at the beginning of the trie. More...

BreadthIterator	breadthBegin ()
	Get a breadth iterator positioned at the beginning of the trie. More...

ConstBreadthIterator	breadthBegin () const
	Get a const breadth iterator positioned at the beginning of the trie. More...

BreadthIterator	breadthEnd ()
	Get a breadth iterator positioned at the end of the trie. More...

ConstBreadthIterator	breadthEnd () const
	Get a const breadth iterator positioned at the end of the trie. More...

void	cascade (const ObjectTrie< T > &toCascade)
	Cascades the supplied trie onto this trie, copying the values. More...

void	cascade (ObjectTrie< T > &&toCascade)
	Cascades the supplied trie onto this trie, moving the source values. More...

template<typename U >
void	cascade (const ObjectTrie< T > &toCascade, U copyFunction)
	Cascades the supplied trie onto this trie. More...

template<typename U >
void	cascade (ObjectTrie< T > &&toCascade, U moveFunction)
	Cascades the supplied trie onto this trie. More...

size_t	count () const
	Get the number of children in the root node. More...

DepthIterator	depthBegin ()
	Get a depth iterator positioned at the beginning of the trie. More...

ConstDepthIterator	depthBegin () const
	Get a const depth iterator positioned at the beginning of the trie. More...

DepthIterator	depthEnd ()
	Get a depth iterator positioned at the end of the trie. More...

ConstDepthIterator	depthEnd () const
	Get a const depth iterator positioned at the end of the trie. More...

bool	empty () const
	Returns true if the trie is empty. More...

DepthIterator	end ()
	Get a depth iterator positioned at the end of the trie. More...

ConstDepthIterator	end () const
	Get a const depth iterator positioned at the end of the trie. More...

template<typename U , template< typename ... > class ContainerT, typename ... UC>
ObjectTrieNode< T > *	find (const ContainerT< U, UC ... > &values, bool skipRoot=true)
	Descend into the trie, locating matches of the supplied values. More...

template<typename U , template< typename ... > class ContainerT, typename ... UC>
const ObjectTrieNode< T > *	find (const ContainerT< U, UC ... > &values, bool skipRoot=true) const
	Descend into the trie, locating matches of the supplied values. More...

template<typename U , template< typename ... > class ContainerT, typename ... UC, typename CompareT >
ObjectTrieNode< T > *	find (const ContainerT< U, UC ... > &values, CompareT compare, bool skipRoot=true)
	Descend into the trie, locating matches of the supplied values. More...

template<typename U , template< typename ... > class ContainerT, typename ... UC, typename CompareT >
const ObjectTrieNode< T > *	find (const ContainerT< U, UC ... > &values, CompareT compare, bool skipRoot=true) const
	Descend into the trie, locating matches of the supplied values. More...

template<typename U , template< typename ... > class ContainerT, typename ... UC>
ObjectTrieNode< T > *	findNearest (const ContainerT< U, UC ... > &values, bool skipRoot=true)
	Descend into the trie, locating matches of the supplied values. More...

template<typename U , template< typename ... > class ContainerT, typename ... UC>
const ObjectTrieNode< T > *	findNearest (const ContainerT< U, UC ... > &values, bool skipRoot=true) const
	Descend into the trie, locating matches of the supplied values. More...

template<typename U , template< typename ... > class ContainerT, typename ... UC, typename CompareT >
ObjectTrieNode< T > *	findNearest (const ContainerT< U, UC ... > &values, CompareT compare, bool skipRoot=true)
	Descend into the trie, locating matches of the supplied values. More...

template<typename U , template< typename ... > class ContainerT, typename ... UC, typename CompareT >
const ObjectTrieNode< T > *	findNearest (const ContainerT< U, UC ... > &values, CompareT compare, bool skipRoot=true) const
	Descend into the trie, locating matches of the supplied values. More...

template<typename U , template< typename ... > class ContainerT, typename ... UC>
ObjectTrieNode< T > *	findNearestLeaf (const ContainerT< U, UC ... > &values, bool skipRoot=true)
	Descend into the trie, locating matches of the supplied values. More...

template<typename U , template< typename ... > class ContainerT, typename ... UC>
const ObjectTrieNode< T > *	findNearestLeaf (const ContainerT< U, UC ... > &values, bool skipRoot=true) const
	Descend into the trie, locating matches of the supplied values. More...

template<typename U , template< typename ... > class ContainerT, typename ... UC, typename CompareT >
ObjectTrieNode< T > *	findNearestLeaf (const ContainerT< U, UC ... > &values, CompareT compare, bool skipRoot=true)
	Descend into the trie, locating matches of the supplied values. More...

template<typename U , template< typename ... > class ContainerT, typename ... UC, typename CompareT >
const ObjectTrieNode< T > *	findNearestLeaf (const ContainerT< U, UC ... > &values, CompareT compare, bool skipRoot=true) const
	Descend into the trie, locating matches of the supplied values. More...

template<typename U , template< typename ... > class ContainerT, typename ... UC>
ObjectTrieNode< T > &	findOrAdd (const ContainerT< U, UC ... > &values)
	Descend into the trie, locating matches of the supplied values, or creating them if they do not exist. More...

template<typename U , template< typename ... > class ContainerT, typename ... UC, typename CompareT >
ObjectTrieNode< T > &	findOrAdd (const ContainerT< U, UC ... > &values, CompareT compare)
	Descend into the trie, locating matches of the supplied values, or creating them if they do not exist. More...

template<typename U , template< typename ... > class ContainerT, typename ... UC, typename CompareT , typename Create >
ObjectTrieNode< T > &	findOrAdd (const ContainerT< U, UC ... > &values, CompareT compare, Create create)
	Descend into the trie, locating matches of the supplied values, or creating them if they do not exist. More...

ObjectTrie< T > &	operator= (ObjectTrie< T > &&rhs) noexcept
	Move a trie to an existing trie. More...

ObjectTrie< T > &	operator= (const ObjectTrie< T > &rhs)
	Copy a trie to an existing trie. More...

ObjectTrieNode< T > &	operator[] (size_t index)
	Get a reference to the specified child in the root node. More...

const ObjectTrieNode< T > &	operator[] (size_t index) const
	Get a const reference to the specified child in the root node. More...

ObjectTrieNode< T > &	root ()
	Get the root node of the trie. More...

const ObjectTrieNode< T > &	root () const
	Get the root node of the trie. More...

Detailed Description

template<typename T>
class Balau::Container::ObjectTrie< T >

An object based trie used for parent-child hierarchies.

A node's children are ordered in the order of appending.

The trie has depth first and breadth first iterators.

The nodes of an object trie are single linked. If the ancestors of a node are required during iteration, the depth first iterator provides ancestor methods that access the iterator's internal node stack.

This data structure is useful when the parent-child relationships between nodes methods of instances are semantically important and must not be changed via tree balancing. If this is not the case, a B-tree or red–black tree would most likely be more appropriate.

The trie implementation is not optimised or compressed, thus use cases requiring the most optimised trie representation would most likely be better using a non-object based trie implementation.

An object of type T is contained in each trie node. Trie nodes also contain a heap based vector of child nodes.

When using the search algorithms of the object trie, the standard operator == function/method is used for the object type T. Alternative methods are also provided that accept a custom compare function/lambda.

The object type T should normally provide a key type field that is compared within the == operator, and one or more body fields that are not accessed by the object trie logic.

Todo:: Add cascade methods with custom comparators.

Member Typedef Documentation

◆ const_iterator

using const_iterator = ConstDepthIterator

Default (depth first) const iterator.

For breadth first const iteration, use const_breadth_iterator.

◆ iterator

using iterator = DepthIterator

Default (depth first) iterator.

For breadth first iteration, use breadth_iterator.

Constructor & Destructor Documentation

◆ ObjectTrie() [1/5]

ObjectTrie ( )

default

Construct the trie with a root value equal to the default construction of T.

◆ ObjectTrie() [2/5]

ObjectTrie ( const T & trieRoot_ )

inlineexplicit

Construct the trie by making a copy of the supplied root value.

This constructor is used when the object type T does not have a default constructor and the supplied object will be copied.

◆ ObjectTrie() [3/5]

ObjectTrie ( T && trieRoot_ )

inlineexplicit

Construct the trie by moving the supplied root value.

This constructor is used when the object type T does not have a default constructor and the supplied object will be moved.

◆ ObjectTrie() [4/5]

ObjectTrie ( const ObjectTrie< T > & copy )

inline

Create a trie by copying an existing trie.

◆ ObjectTrie() [5/5]

ObjectTrie ( ObjectTrie< T > && rhs )

inlinenoexcept

Move a trie.

Member Function Documentation

◆ add() [1/3]

ObjectTrieNode<T>& add	(	T &&	value,
		ObjectAdderT &&...	childNode
	)

inline

Append a child containing the supplied data to the root node, plus children of the new child.

Returns: the root node, allowing chaining calls to be made

◆ add() [2/3]

ObjectTrieNode<T>& add ( const T & value )

inline

Append a child containing a copy of the supplied data to the root node.

The data is copied into the new value.

Returns: the root node, allowing chaining calls to be made

◆ add() [3/3]

ObjectTrieNode<T>& add ( T && value )

inline

Append a child containing the supplied data to the root node.

The data is moved into the new value.

Returns: the root node, allowing chaining calls to be made

◆ addAndReturnChild() [1/2]

ObjectTrieNode<T>& addAndReturnChild ( const T & value )

inline

Append a root node child containing a copy of the supplied data.

This is an alternative form of the add() method, that returns the newly created child instead of the current node.

The data is copied into the new value.

Returns: the newly created node

◆ addAndReturnChild() [2/2]

ObjectTrieNode<T>& addAndReturnChild ( T && value )

inline

Append a root node child containing a the supplied data.

This is an alternative form of the add() method, that returns the newly created child instead of the current node.

The data is moved into the new value.

Returns: the newly created node

◆ addOrReplace() [1/6]

ObjectTrieNode<T>& addOrReplace ( const T & value )

inline

Append a child containing the supplied data to the root node if a child equal to the supplied value is not present, otherwise replace it.

The operator == method is used to compare values.

The operator = method is used to assign the supplied value to the existing one when a matching value is is found.

The data is copied into the new value.

Returns: the root node, allowing chaining calls to be made

◆ addOrReplace() [2/6]

ObjectTrieNode<T>& addOrReplace ( T && value )

inline

Append a child containing the supplied data to the root node if a child equal to the supplied value is not present, otherwise replace it.

The operator == method is used to compare values.

The operator = method is used to assign the supplied value to the existing one when a matching value is is found.

The data is moved into the new value.

Returns: the root node, allowing chaining calls to be made

◆ addOrReplace() [3/6]

ObjectTrieNode<T>& addOrReplace	(	const T &	value,
		CompareT	compare
	)

inline

Append a child containing the supplied data to the root node if a child equal to the supplied value is not present, otherwise replace it.

The supplied comparator is used to compare values.

The operator = method is used to assign the supplied value to the existing one when a matching value is is found.

The data is copied into the new value.

Returns: the root node, allowing chaining calls to be made

◆ addOrReplace() [4/6]

ObjectTrieNode<T>& addOrReplace	(	T &&	value,
		CompareT	compare
	)

inline

Append a child containing the supplied data to the root node if a child equal to the supplied value is not present, otherwise replace it.

The supplied comparator is used to compare values.

The operator = method is used to assign the supplied value to the existing one when a matching value is is found.

The data is moved into the new value.

Returns: the root node, allowing chaining calls to be made

◆ addOrReplace() [5/6]

ObjectTrieNode<T>& addOrReplace	(	const T &	value,
		CompareT	compare,
		ReplaceT	replace
	)

inline

Append a child containing the supplied data to the root node if a child equal to the supplied value is not present, otherwise replace it.

The supplied comparator is used to compare values.

The supplied replacer is used to perform assignment of the values when a match is found.

The data is copied into the new value.

Returns: the root node, allowing chaining calls to be made

◆ addOrReplace() [6/6]

ObjectTrieNode<T>& addOrReplace	(	T &&	value,
		CompareT	compare,
		ReplaceT	replace
	)

inline

Append a child containing the supplied data to the root node if a child equal to the supplied value is not present, otherwise replace it.

The supplied comparator is used to compare values.

The supplied replacer is used to perform assignment of the values when a match is found.

The data is moved into the new value.

Returns: the root node, allowing chaining calls to be made

◆ addOrReplaceAndReturnChild() [1/6]

ObjectTrieNode<T>& addOrReplaceAndReturnChild ( const T & value )

inline

Append a root node child containing a copy of the supplied data if a child equal to the supplied value is not present, otherwise replace it.

This is an alternative form of the add() method, that returns the newly created child instead of the current node.

The operator == method is used to compare values.

The operator = method is used to assign the supplied value to the existing one when a matching value is is found.

The data is copied into the new value.

Returns: the newly created or replaced node

◆ addOrReplaceAndReturnChild() [2/6]

ObjectTrieNode<T>& addOrReplaceAndReturnChild ( T && value )

inline

Append a root node child containing a copy of the supplied data if a child equal to the supplied value is not present, otherwise replace it.

This is an alternative form of the add() method, that returns the newly created child instead of the current node.

The operator == method is used to compare values.

The operator = method is used to assign the supplied value to the existing one when a matching value is is found.

The data is moved into the new value.

Returns: the newly created or replaced node

◆ addOrReplaceAndReturnChild() [3/6]

ObjectTrieNode<T>& addOrReplaceAndReturnChild	(	const T &	value,
		CompareT	compare
	)

inline

Append a root node child containing a copy of the supplied data if a child equal to the supplied value is not present, otherwise replace it.

This is an alternative form of the add() method, that returns the newly created child instead of the current node.

The supplied comparator is used to compare values.

The operator = method is used to assign the supplied value to the existing one when a matching value is is found.

The data is copied into the new value.

Returns: the newly created or replaced node

◆ addOrReplaceAndReturnChild() [4/6]

ObjectTrieNode<T>& addOrReplaceAndReturnChild	(	T &&	value,
		CompareT	compare
	)

inline

Append a root node child containing a copy of the supplied data if a child equal to the supplied value is not present, otherwise replace it.

This is an alternative form of the add() method, that returns the newly created child instead of the current node.

The supplied comparator is used to compare values.

The operator = method is used to assign the supplied value to the existing one when a matching value is is found.

The data is moved into the new value.

Returns: the newly created or replaced node

◆ addOrReplaceAndReturnChild() [5/6]

ObjectTrieNode<T>& addOrReplaceAndReturnChild	(	const T &	value,
		CompareT	compare,
		ReplaceT	replace
	)

inline

Append a root node child containing a copy of the supplied data if a child equal to the supplied value is not present, otherwise replace it.

This is an alternative form of the add() method, that returns the newly created child instead of the current node.

The supplied comparator is used to compare values.

The operator = method is used to assign the supplied value to the existing one when a matching value is is found.

The data is copied into the new value.

Returns: the newly created or replaced node

◆ addOrReplaceAndReturnChild() [6/6]

ObjectTrieNode<T>& addOrReplaceAndReturnChild	(	T &&	value,
		CompareT	compare,
		ReplaceT	replace
	)

inline

Append a root node child containing a copy of the supplied data if a child equal to the supplied value is not present, otherwise replace it.

This is an alternative form of the add() method, that returns the newly created child instead of the current node.

The supplied comparator is used to compare values.

The operator = method is used to assign the supplied value to the existing one when a matching value is is found.

The data is moved into the new value.

Returns: the newly created or replaced node

◆ begin() [1/2]

DepthIterator begin ( )

inline

Get a depth iterator positioned at the beginning of the trie.

◆ begin() [2/2]

ConstDepthIterator begin ( ) const

inline

Get a const depth iterator positioned at the beginning of the trie.

◆ breadthBegin() [1/2]

BreadthIterator breadthBegin ( )

inline

Get a breadth iterator positioned at the beginning of the trie.

◆ breadthBegin() [2/2]

ConstBreadthIterator breadthBegin ( ) const

inline

Get a const breadth iterator positioned at the beginning of the trie.

◆ breadthEnd() [1/2]

BreadthIterator breadthEnd ( )

inline

Get a breadth iterator positioned at the end of the trie.

◆ breadthEnd() [2/2]

ConstBreadthIterator breadthEnd ( ) const

inline

Get a const breadth iterator positioned at the end of the trie.

◆ cascade() [1/4]

void cascade ( const ObjectTrie< T > & toCascade )

inline

Cascades the supplied trie onto this trie, copying the values.

In order that anything is cascaded, the values of the root nodes must match via the value type's operator ==, otherwise the result is a nop. It is the responsibility of the end developer to use a value type that has a suitable operator ==.

Parameters

toCascade the source trie

◆ cascade() [2/4]

void cascade ( ObjectTrie< T > && toCascade )

inline

Cascades the supplied trie onto this trie, moving the source values.

In order that anything is cascaded, the values of the root nodes must match via the value type's operator ==, otherwise the result is a nop. It is the responsibility of the end developer to use a value type that has a suitable operator ==.

By the end of this call, the source trie's values will be partially or fully emptied.

Parameters

toCascade the source trie

◆ cascade() [3/4]

void cascade	(	const ObjectTrie< T > &	toCascade,
		U	copyFunction
	)

inline

Cascades the supplied trie onto this trie.

The values are copied via the supplied function.

In order that anything is cascaded, the values of the root nodes must match via the value type's operator ==, otherwise the result is a nop. It is the responsibility of the end developer to use a value type that has a suitable operator ==.

Parameters

toCascade	the source trie
moveFunction	the function used to copy the values

◆ cascade() [4/4]

void cascade	(	ObjectTrie< T > &&	toCascade,
		U	moveFunction
	)

inline

Cascades the supplied trie onto this trie.

The values are moved via the supplied function. In order that anything is cascaded, the values of the root nodes must match via the value type's operator ==, otherwise the result is a nop. It is the responsibility of the end developer to use a value type that has a suitable operator ==.

By the end of this call, the source trie's values will be partially or fully emptied.

Parameters

toCascade	the source trie
moveFunction	the function used to move the values

◆ count()

size_t count ( ) const

inline

Get the number of children in the root node.

◆ depthBegin() [1/2]

DepthIterator depthBegin ( )

inline

Get a depth iterator positioned at the beginning of the trie.

◆ depthBegin() [2/2]

ConstDepthIterator depthBegin ( ) const

inline

Get a const depth iterator positioned at the beginning of the trie.

◆ depthEnd() [1/2]

DepthIterator depthEnd ( )

inline

Get a depth iterator positioned at the end of the trie.

◆ depthEnd() [2/2]

ConstDepthIterator depthEnd ( ) const

inline

Get a const depth iterator positioned at the end of the trie.

◆ empty()

bool empty ( ) const

inline

Returns true if the trie is empty.

◆ end() [1/2]

DepthIterator end ( )

inline

Get a depth iterator positioned at the end of the trie.

◆ end() [2/2]

ConstDepthIterator end ( ) const

inline

Get a const depth iterator positioned at the end of the trie.

◆ find() [1/4]

ObjectTrieNode<T>* find	(	const ContainerT< U, UC ... > &	values,
		bool	skipRoot = `true`
	)

inline

Descend into the trie, locating matches of the supplied values.

The default operator == compare function is used to determine equality.

Descends into the trie, locating at each node the first child that matches the next value in the supplied value chain. Returns the exact node if all values were found or nullptr if not all values were matched.

Parameters

values	a vector of values to search for
skipRoot	does not check the first value against the root node of the trie

Returns: a pointer to the matching node or nullptr if no node was found

◆ find() [2/4]

const ObjectTrieNode<T>* find	(	const ContainerT< U, UC ... > &	values,
		bool	skipRoot = `true`
	)		const

inline

Descend into the trie, locating matches of the supplied values.

The default operator == compare function is used to determine equality.

Descends into the trie, locating at each node the first child that matches the next value in the supplied value chain. Returns the exact node if all values were found or nullptr if not all values were matched.

Parameters

values	a vector of values to search for
skipRoot	does not check the first value against the root node of the trie

Returns: a pointer to the matching node or nullptr if no node was found

◆ find() [3/4]

ObjectTrieNode<T>* find	(	const ContainerT< U, UC ... > &	values,
		CompareT	compare,
		bool	skipRoot = `true`
	)

inline

Descend into the trie, locating matches of the supplied values.

The supplied search vector contains values that are used in the custom compare function.

Descends into the trie, locating at each node the first child that matches the next value in the supplied value chain. Returns the exact node if all values were found or nullptr if not all values were matched.

Template Parameters

U	the type of the values used in the compare function
CompareT	the compare function type

Parameters

values	a vector of values to search for
compare	the compare function
skipRoot	does not check the first value against the root node of the trie

Returns: a pointer to the matching node or nullptr if no node was found

◆ find() [4/4]

const ObjectTrieNode<T>* find	(	const ContainerT< U, UC ... > &	values,
		CompareT	compare,
		bool	skipRoot = `true`
	)		const

inline

Descend into the trie, locating matches of the supplied values.

The supplied search vector contains values that are used in the custom compare function.

Descends into the trie, locating at each node the first child that matches the next value in the supplied value chain. Returns the exact node if all values were found or nullptr if not all values were matched.

Template Parameters

U	the type of the values used in the compare function
CompareT	the compare function type

Parameters

values	a vector of values to search for
compare	the compare function
skipRoot	does not check the first value against the root node of the trie

Returns: a pointer to the matching node or nullptr if no node was found

◆ findNearest() [1/4]

ObjectTrieNode<T>* findNearest	(	const ContainerT< U, UC ... > &	values,
		bool	skipRoot = `true`
	)

inline

Descend into the trie, locating matches of the supplied values.

The default operator == compare function is used to determine equality.

Descends into the trie, locating at each node the first child that matches the next value in the supplied value chain. Returns the last matched node or the exact node if all values were found.

Returns nullptr if no matching nodes were found.

Parameters

values	a vector of values to search for
skipRoot	does not check the first value against the root node of the trie

Returns: a pointer to the matching node or nullptr if no node was found

◆ findNearest() [2/4]

const ObjectTrieNode<T>* findNearest	(	const ContainerT< U, UC ... > &	values,
		bool	skipRoot = `true`
	)		const

inline

Descend into the trie, locating matches of the supplied values.

The default operator == compare function is used to determine equality.

Descends into the trie, locating at each node the first child that matches the next value in the supplied value chain. Returns the last matched node or the exact node if all values were found.

Returns nullptr if no matching nodes were found.

Parameters

values	a vector of values to search for
skipRoot	does not check the first value against the root node of the trie

Returns: a pointer to the matching node or nullptr if no node was found

◆ findNearest() [3/4]

ObjectTrieNode<T>* findNearest	(	const ContainerT< U, UC ... > &	values,
		CompareT	compare,
		bool	skipRoot = `true`
	)

inline

Descend into the trie, locating matches of the supplied values.

The supplied comparator is used to determine equality (true == equal).

Descends into the trie, locating at each node the first child that matches the next value in the supplied value chain. Returns the last matched node or the exact node if all values were found.

Returns nullptr if no matching nodes were found.

Template Parameters

U	the type of the values used in the compare function
CompareT	the compare function type

Parameters

values	a vector of values to search for
compare	the compare function
skipRoot	does not check the first value against the root node of the trie

Returns: a pointer to the matching node or nullptr if no node was found

◆ findNearest() [4/4]

const ObjectTrieNode<T>* findNearest	(	const ContainerT< U, UC ... > &	values,
		CompareT	compare,
		bool	skipRoot = `true`
	)		const

inline

Descend into the trie, locating matches of the supplied values.

The supplied comparator is used to determine equality (true == equal).

Descends into the trie, locating at each node the first child that matches the next value in the supplied value chain. Returns the last matched node or the exact node if all values were found.

Returns nullptr if no matching nodes were found.

Template Parameters

U	the type of the values used in the compare function
CompareT	the compare function type

Parameters

values	a vector of values to search for
compare	the compare function
skipRoot	does not check the first value against the root node of the trie

Returns: a pointer to the matching node or nullptr if no node was found

◆ findNearestLeaf() [1/4]

ObjectTrieNode<T>* findNearestLeaf	(	const ContainerT< U, UC ... > &	values,
		bool	skipRoot = `true`
	)

inline

Descend into the trie, locating matches of the supplied values.

The default operator == compare function is used to determine equality.

Descends into the trie, locating at each node the first child that matches the next value in the supplied value chain. Returns the last matched node if the node is a leaf node.

Returns nullptr if no matching leaf node was found.

Parameters

values	a vector of values to search for
skipRoot	does not check the first value against the root node of the trie

Returns: a pointer to the matching node or nullptr if no node was found

◆ findNearestLeaf() [2/4]

const ObjectTrieNode<T>* findNearestLeaf	(	const ContainerT< U, UC ... > &	values,
		bool	skipRoot = `true`
	)		const

inline

Descend into the trie, locating matches of the supplied values.

The default operator == compare function is used to determine equality.

Descends into the trie, locating at each node the first child that matches the next value in the supplied value chain. Returns the last matched node if the node is a leaf node.

Returns nullptr if no matching leaf node was found.

Parameters

values	a vector of values to search for
skipRoot	does not check the first value against the root node of the trie

Returns: a pointer to the matching node or nullptr if no node was found

◆ findNearestLeaf() [3/4]

ObjectTrieNode<T>* findNearestLeaf	(	const ContainerT< U, UC ... > &	values,
		CompareT	compare,
		bool	skipRoot = `true`
	)

inline

Descend into the trie, locating matches of the supplied values.

The supplied comparator is used to determine equality (true == equal).

Descends into the trie, locating at each node the first child that matches the next value in the supplied value chain. Returns the last matched node if the node is a leaf node.

Returns nullptr if no matching leaf node was found.

Template Parameters

U	the type of the values used in the compare function
CompareT	the compare function type

Parameters

values	a vector of values to search for
compare	the compare function
skipRoot	does not check the first value against the root node of the trie

Returns: a pointer to the matching node or nullptr if no node was found

◆ findNearestLeaf() [4/4]

const ObjectTrieNode<T>* findNearestLeaf	(	const ContainerT< U, UC ... > &	values,
		CompareT	compare,
		bool	skipRoot = `true`
	)		const

inline

Descend into the trie, locating matches of the supplied values.

The supplied comparator is used to determine equality (true == equal).

Descends into the trie, locating at each node the first child that matches the next value in the supplied value chain. Returns the last matched node if the node is a leaf node.

Returns nullptr if no matching leaf node was found.

Template Parameters

U	the type of the values used in the compare function
CompareT	the compare function type

Parameters

values	a vector of values to search for
compare	the compare function
skipRoot	does not check the first value against the root node of the trie

Returns: a pointer to the matching node or nullptr if no node was found

◆ findOrAdd() [1/3]

ObjectTrieNode<T>& findOrAdd ( const ContainerT< U, UC ... > & values )

inline

Descend into the trie, locating matches of the supplied values, or creating them if they do not exist.

The default operator == compare function is used to determine equality.

Descends into the trie, locating at each node the first child that matches the next value in the supplied value chain. Any nodes that are not found are created. Returns the node that was found or the created node if the node or one or more of its parent were not present.

As the root node of the trie is fixed, the findOrAdd algorithm never checks the first value against the root node of the trie, i.e. skipRoot is always true.

If the supplied values container is empty, the root node is returned.

Parameters

values a vector of values to search for

Returns: a reference to the matching or created node

◆ findOrAdd() [2/3]

ObjectTrieNode<T>& findOrAdd	(	const ContainerT< U, UC ... > &	values,
		CompareT	compare
	)

inline

Descend into the trie, locating matches of the supplied values, or creating them if they do not exist.

The supplied search vector contains values that are used in the custom compare function.

Descends into the trie, locating at each node the first child that matches the next value in the supplied value chain. Any nodes that are not found are created. Returns the node that was found or the created node if the node or one or more of its parent were not present.

As the root node of the trie is fixed, the findOrAdd algorithm never checks the first value against the root node of the trie, i.e. skipRoot is always true.

If the supplied values container is empty, the root node is returned.

Template Parameters

U	the type of the values used in the compare function
CompareT	the compare function type

Parameters

values	a vector of values to search for
compare	the compare function

Returns: a reference to the matching node or nullptr if no node was found

◆ findOrAdd() [3/3]

ObjectTrieNode<T>& findOrAdd	(	const ContainerT< U, UC ... > &	values,
		CompareT	compare,
		Create	create
	)

inline

Descend into the trie, locating matches of the supplied values, or creating them if they do not exist.

The supplied search vector contains values that are used in the custom compare function.

The create function is used to create new nodes. The create function's argument is the current value as supplied in the values container.

Descends into the trie, locating at each node the first child that matches the next value in the supplied value chain. Any nodes that are not found are created. Returns the node that was found or the created node if the node or one or more of its parent were not present.

As the root node of the trie is fixed, the findOrAdd algorithm never checks the first value against the root node of the trie, i.e. skipRoot is always true.

If the supplied values container is empty, the root node is returned.

Template Parameters

U	the type of the values used in the compare function
CompareT	the compare function type
Create	the function used to create new nodes

Parameters

values	a vector of values to search for
compare	the compare function

Returns: a reference to the matching node or nullptr if no node was found

◆ operator=() [1/2]

ObjectTrie<T>& operator= ( ObjectTrie< T > && rhs )

inlinenoexcept

Move a trie to an existing trie.

◆ operator=() [2/2]

ObjectTrie<T>& operator= ( const ObjectTrie< T > & rhs )

inline

Copy a trie to an existing trie.

◆ operator[]() [1/2]

ObjectTrieNode<T>& operator[] ( size_t index )

inline

Get a reference to the specified child in the root node.

◆ operator[]() [2/2]

const ObjectTrieNode<T>& operator[] ( size_t index ) const

inline

Get a const reference to the specified child in the root node.

◆ root() [1/2]

ObjectTrieNode<T>& root ( )

inline

Get the root node of the trie.

◆ root() [2/2]

const ObjectTrieNode<T>& root ( ) const

inline

Get the root node of the trie.

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

ObjectTrie.hpp (4)

Classes

Public Types

Public Member Functions

Detailed Description

template<typename T> class Balau::Container::ObjectTrie< T >

Member Typedef Documentation

◆ const_iterator

◆ iterator

Constructor & Destructor Documentation

◆ ObjectTrie() [1/5]

◆ ObjectTrie() [2/5]

◆ ObjectTrie() [3/5]

◆ ObjectTrie() [4/5]

◆ ObjectTrie() [5/5]

Member Function Documentation

◆ add() [1/3]

◆ add() [2/3]

◆ add() [3/3]

◆ addAndReturnChild() [1/2]

◆ addAndReturnChild() [2/2]

◆ addOrReplace() [1/6]

◆ addOrReplace() [2/6]

◆ addOrReplace() [3/6]

◆ addOrReplace() [4/6]

◆ addOrReplace() [5/6]

◆ addOrReplace() [6/6]

◆ addOrReplaceAndReturnChild() [1/6]

◆ addOrReplaceAndReturnChild() [2/6]

◆ addOrReplaceAndReturnChild() [3/6]

◆ addOrReplaceAndReturnChild() [4/6]

◆ addOrReplaceAndReturnChild() [5/6]

◆ addOrReplaceAndReturnChild() [6/6]

◆ begin() [1/2]

◆ begin() [2/2]

◆ breadthBegin() [1/2]

◆ breadthBegin() [2/2]

◆ breadthEnd() [1/2]

◆ breadthEnd() [2/2]

◆ cascade() [1/4]

◆ cascade() [2/4]

◆ cascade() [3/4]

◆ cascade() [4/4]

◆ count()

◆ depthBegin() [1/2]

◆ depthBegin() [2/2]

◆ depthEnd() [1/2]

◆ depthEnd() [2/2]

◆ empty()

◆ end() [1/2]

◆ end() [2/2]

◆ find() [1/4]

◆ find() [2/4]

◆ find() [3/4]

◆ find() [4/4]

◆ findNearest() [1/4]

◆ findNearest() [2/4]

◆ findNearest() [3/4]

◆ findNearest() [4/4]

◆ findNearestLeaf() [1/4]

◆ findNearestLeaf() [2/4]

◆ findNearestLeaf() [3/4]

◆ findNearestLeaf() [4/4]

◆ findOrAdd() [1/3]

◆ findOrAdd() [2/3]

◆ findOrAdd() [3/3]

◆ operator=() [1/2]

◆ operator=() [2/2]

◆ operator[]() [1/2]

◆ operator[]() [2/2]

◆ root() [1/2]

◆ root() [2/2]

template<typename T>
class Balau::Container::ObjectTrie< T >