Class introducing a trie with interface trying to be close to the interface of standard library containers. More...

#include <trie.hpp>

Public Types
typedef ext::map< Key, trie >::iterator	children_iterator
	The iterator type over children of the node. More...

typedef ext::map< Key, trie >::const_iterator	const_children_iterator
	The iterator type over children of the node. More...

Public Member Functions
trie *	getParent ()
	Getter of the parent node. Null if the node is root. More...

const trie *	getParent () const
	Getter of the parent node. Null if the node is root. More...

Value &	getData ()
	Getter of the value in the root node. More...

const Value &	getData () const
	Getter of the value in the root node. More...

ext::map< Key, trie > &	getChildren ()
	Getter of children of the root node. More...

const ext::map< Key, trie > &	getChildren () const
	Getter of children of the root node. More...

const_children_iterator	insert (Key key, trie< Key, Value > &&value)
	Inserts a subtrie into a trie. More...

const_children_iterator	insert (Key key, const trie< Key, Value > &value)
	Inserts a subtrie into a trie. More...

void	insert (const_children_iterator begin, const_children_iterator end)
	Inserts subtries given by range of key-value pairs at specified position. More...

	trie (Value &&data, ext::map< Key, trie > &&children)
	Constructor of the trie from value to be stored in the root node and children tries. More...

	trie (const Value &data, const ext::map< Key, trie > &subtries)
	Constructor of the trie from value to be stored in the root node and children tries. More...

template<typename ... Types>
	trie (const Value &data, Types ... subtries)
	Constructor of the trie from value to be stored in the root node and pack of children tries. More...

template<typename ... Types>
	trie (Value &&data, Types ... subtries)
	Constructor of the trie from value to be stored in the root node and pack of children tries. More...

	trie (const Value &data, const_children_iterator begin, const_children_iterator end)
	Constructor of the trie from value to be stored in the root node and range of key-value pairs to construct nullary nodes. More...

	~trie () noexcept=default
	Dectructor of the trie. More...

	trie (const trie &other)
	Copy constructor of the trie. More...

	trie (trie &&other) noexcept
	Move constructor of the trie. More...

trie &	operator= (const trie &node)
	Copy operator of assignment of the trie. More...

trie &	operator= (trie &&node) noexcept
	Move operator of assignment of the trie. More...

const_children_iterator	begin () const
	Getter of a children iterator to the begining of children. More...

children_iterator	begin ()
	Getter of a children iterator to the begining of children. More...

const_children_iterator	end () const
	Getter of a children iterator one after the last child. More...

children_iterator	end ()
	Getter of a children iterator one after the last child. More...

children_iterator	erase (const_children_iterator position)
	Erases a subtrie from a trie on given by `position`. More...

template<class ... Indexes>
const Value &	operator() (Indexes ... indexes) const
	Access value given indexes to chindren allong the selection path. More...

const Value &	operator() (std::initializer_list< Key > indexes) const
	Access value given key to chindren allong the selection path. More...

template<class ... Indexes>
Value &	operator() (Indexes ... indexes)
	Access value given indexes to chindren allong the selection path. More...

Value &	operator() (std::initializer_list< Key > indexes)
	Access value given key to chindren allong the selection path. More...

bool	checkStructure (const trie &node) const
	Helper method to traverse the trie and check all parent references are set correctly. More...

bool	checkStructure () const
	Helper method to traverse the trie and check all parent references are set correctly. Starts at root node and recursively tests all its child nodes. More...

bool	operator== (const trie &other) const
	Equality comparison operator. More...

auto	operator<=> (const trie &other) const -> std::common_comparison_category_t< decltype(std::declval< Key >()<=> std::declval< Key >()), decltype(std::declval< Value >()<=> std::declval< Value >()) >
	Less comparison operator. More...

ext::ostream &	nicePrint (ext::ostream &os) const
	Internal method of printing a trie into a stream. More...

Friends
void	swap (trie &first, trie &second)
	Swap method of two tries. More...

Detailed Description

template<class Key, class Value>
class ext::trie< Key, Value >

Class introducing a trie with interface trying to be close to the interface of standard library containers.

The trie is a hierarchical structure of nodes with parent child relationship, where the children are accessible by their keys.

Template Parameters

T	the type of values inside nodes of the trie

Member Typedef Documentation

◆ children_iterator

template<class Key , class Value >

typedef ext::map<Key,trie>::iterator ext::trie< Key, Value >::children_iterator

The iterator type over children of the node.

◆ const_children_iterator

template<class Key , class Value >

typedef ext::map<Key,trie>::const_iterator ext::trie< Key, Value >::const_children_iterator

The iterator type over children of the node.

Constructor & Destructor Documentation

◆ trie() [1/7]

template<class Key , class Value >

ext::trie< Key, Value >::trie	(	Value &&	data,
		ext::map< Key, trie< Key, Value > > &&	children
	)

inline

Constructor of the trie from value to be stored in the root node and children tries.

Parameters

data	the value to be stored in the root
children	map of subtries

Here is the caller graph for this function:

◆ trie() [2/7]

template<class Key , class Value >

ext::trie< Key, Value >::trie	(	const Value &	data,
		const ext::map< Key, trie< Key, Value > > &	subtries
	)

inline

Constructor of the trie from value to be stored in the root node and children tries.

Parameters

data	the value to be stored in the root
children	map of subtries

◆ trie() [3/7]

template<class Key , class Value >

template<typename ... Types>

ext::trie< Key, Value >::trie	(	const Value &	data,
		Types ...	subtries
	)

inline

Constructor of the trie from value to be stored in the root node and pack of children tries.

Template Parameters

Types ... pack of types convertible to trie

Parameters

data	the value to be stored in the root
subtries	... pack of subtries

◆ trie() [4/7]

template<class Key , class Value >

template<typename ... Types>

ext::trie< Key, Value >::trie	(	Value &&	data,
		Types ...	subtries
	)

inline

Constructor of the trie from value to be stored in the root node and pack of children tries.

Template Parameters

Types ... pack of types convertible to trie

Parameters

data	the value to be stored in the root
subtries	... pack of subtries

◆ trie() [5/7]

template<class Key , class Value >

ext::trie< Key, Value >::trie	(	const Value &	data,
		const_children_iterator	begin,
		const_children_iterator	end
	)

inline

Constructor of the trie from value to be stored in the root node and range of key-value pairs to construct nullary nodes.

Parameters

data	the value to be stored in the root
begin	the iterator to the begining of key-value pairs range
end	the iterator to the end of key-value pairs range

◆ ~trie()

template<class Key , class Value >

ext::trie< Key, Value >::~trie ( )

defaultnoexcept

Dectructor of the trie.

◆ trie() [6/7]

template<class Key , class Value >

ext::trie< Key, Value >::trie ( const trie< Key, Value > & other )

inline

Copy constructor of the trie.

Parameters

other the other instace of the trie

◆ trie() [7/7]

template<class Key , class Value >

ext::trie< Key, Value >::trie ( trie< Key, Value > && other )

inlinenoexcept

Move constructor of the trie.

Parameters

other the other instace of the trie

Member Function Documentation

◆ begin() [1/2]

template<class Key , class Value >

children_iterator ext::trie< Key, Value >::begin ( )

inline

Getter of a children iterator to the begining of children.

Returns: iterator to the first child

Here is the call graph for this function:

◆ begin() [2/2]

template<class Key , class Value >

const_children_iterator ext::trie< Key, Value >::begin ( ) const

inline

Getter of a children iterator to the begining of children.

Returns: iterator to the first child

Here is the call graph for this function:

Here is the caller graph for this function:

◆ checkStructure() [1/2]

template<class Key , class Value >

bool ext::trie< Key, Value >::checkStructure ( ) const

inline

Helper method to traverse the trie and check all parent references are set correctly. Starts at root node and recursively tests all its child nodes.

Parameters

node	the node to test

Returns: true if the parent child relationship of nodes is sound

Here is the call graph for this function:

Here is the caller graph for this function:

◆ checkStructure() [2/2]

template<class Key , class Value >

bool ext::trie< Key, Value >::checkStructure ( const trie< Key, Value > & node ) const

inline

Helper method to traverse the trie and check all parent references are set correctly.

Parameters

node	the node to test

Returns: true if the parent child relationship of nodes is sound

Here is the call graph for this function:

◆ end() [1/2]

template<class Key , class Value >

children_iterator ext::trie< Key, Value >::end ( )

inline

Getter of a children iterator one after the last child.

Returns: iterator one after the last child

Here is the call graph for this function:

◆ end() [2/2]

template<class Key , class Value >

const_children_iterator ext::trie< Key, Value >::end ( ) const

inline

Getter of a children iterator one after the last child.

Returns: iterator one after the last child

Here is the call graph for this function:

Here is the caller graph for this function:

◆ erase()

template<class Key , class Value >

children_iterator ext::trie< Key, Value >::erase ( const_children_iterator position )

inline

Erases a subtrie from a trie on given by position.

Parameters

position the specification of position in children where to erase the subtrie

Here is the call graph for this function:

◆ getChildren() [1/2]

template<class Key , class Value >

ext::map< Key, trie > & ext::trie< Key, Value >::getChildren ( )

inline

Getter of children of the root node.

Returns: children of the root node

Here is the caller graph for this function:

◆ getChildren() [2/2]

template<class Key , class Value >

const ext::map< Key, trie > & ext::trie< Key, Value >::getChildren ( ) const

inline

Getter of children of the root node.

Returns: children of the root node

◆ getData() [1/2]

template<class Key , class Value >

Value & ext::trie< Key, Value >::getData ( )

inline

Getter of the value in the root node.

Returns: the value in the root node

Here is the caller graph for this function:

◆ getData() [2/2]

template<class Key , class Value >

const Value & ext::trie< Key, Value >::getData ( ) const

inline

Getter of the value in the root node.

Returns: the value in the root node

◆ getParent() [1/2]

template<class Key , class Value >

trie * ext::trie< Key, Value >::getParent ( )

inline

Getter of the parent node. Null if the node is root.

Returns: pointer to the parent node

◆ getParent() [2/2]

template<class Key , class Value >

const trie * ext::trie< Key, Value >::getParent ( ) const

inline

Getter of the parent node. Null if the node is root.

Returns: pointer to the parent node

◆ insert() [1/3]

template<class Key , class Value >

void ext::trie< Key, Value >::insert	(	const_children_iterator	begin,
		const_children_iterator	end
	)

inline

Inserts subtries given by range of key-value pairs at specified position.

Parameters

begin	the start of the range of subtries
end	the end of the range of subtries

Here is the call graph for this function:

◆ insert() [2/3]

template<class Key , class Value >

const_children_iterator ext::trie< Key, Value >::insert	(	Key	key,
		const trie< Key, Value > &	value
	)

inline

Inserts a subtrie into a trie.

Parameters

key	the associating key for the inserted subtrie
value	a subtrie to insert

Returns: updated position iterator pointing to the first node inserted

Here is the call graph for this function:

◆ insert() [3/3]

template<class Key , class Value >

const_children_iterator ext::trie< Key, Value >::insert	(	Key	key,
		trie< Key, Value > &&	value
	)

inline

Inserts a subtrie into a trie.

Parameters

key	the associating key for the inserted subtrie
value	a subtrie to insert

Returns: updated position iterator pointing to the first node inserted

Here is the call graph for this function:

Here is the caller graph for this function:

◆ nicePrint()

template<class Key , class Value >

ext::ostream & ext::trie< Key, Value >::nicePrint ( ext::ostream & os ) const

inline

Internal method of printing a trie into a stream.

The trie is printed hierarchically. Key-value pair components are printed separated by colon.

Example trie a ( k:b ( m:c ), l:b ( n:c ) ) would be printed like

-a | |-k:b | | | -m:c | -l:b | -n:c

Parameters

os	the stream to print to

Returns: the changed output stream

Here is the call graph for this function:

Here is the caller graph for this function:

◆ operator()() [1/4]

template<class Key , class Value >

template<class ... Indexes>

Value & ext::trie< Key, Value >::operator() ( Indexes ... indexes )

inline

Access value given indexes to chindren allong the selection path.

Template Parameters

Indexes ... types of child keys

Parameters

indexes actual keys

Returns: the value in the selected node

Here is the call graph for this function:

◆ operator()() [2/4]

template<class Key , class Value >

template<class ... Indexes>

const Value & ext::trie< Key, Value >::operator() ( Indexes ... indexes ) const

inline

Access value given indexes to chindren allong the selection path.

Template Parameters

Indexes ... types of child keys

Parameters

indexes actual keys

Returns: the value in the selected node

Here is the call graph for this function:

Here is the caller graph for this function:

◆ operator()() [3/4]

template<class Key , class Value >

Value & ext::trie< Key, Value >::operator() ( std::initializer_list< Key > indexes )

inline

Access value given key to chindren allong the selection path.

Parameters

indexes list of actual keys

Returns: the value in the selected node

◆ operator()() [4/4]

template<class Key , class Value >

const Value & ext::trie< Key, Value >::operator() ( std::initializer_list< Key > indexes ) const

inline

Access value given key to chindren allong the selection path.

Parameters

indexes list of actual keys

Returns: the value in the selected node

◆ operator<=>()

template<class Key , class Value >

auto ext::trie< Key, Value >::operator<=> ( const trie< Key, Value > & other ) const -> std::common_comparison_category_t < decltype ( std::declval < Key > ( ) <=> std::declval < Key > ( ) ), decltype ( std::declval < Value > ( ) <=> std::declval < Value > ( ) ) >

inline

Less comparison operator.

Parameters

other the other instance to compare with

Returns: true if this instance is smaller than other instance, false othervise

Here is the call graph for this function:

◆ operator=() [1/2]

template<class Key , class Value >

trie & ext::trie< Key, Value >::operator= ( const trie< Key, Value > & node )

inline

Copy operator of assignment of the trie.

Parameters

other the other instace of the trie

Returns: the assigned to instance

Here is the call graph for this function:

◆ operator=() [2/2]

template<class Key , class Value >

trie & ext::trie< Key, Value >::operator= ( trie< Key, Value > && node )

inlinenoexcept

Move operator of assignment of the trie.

Parameters

other the other instace of the trie

Returns: the assigned to instance

◆ operator==()

template<class Key , class Value >

bool ext::trie< Key, Value >::operator== ( const trie< Key, Value > & other ) const

inline

Equality comparison operator.

Parameters

other the other instance to compare with

Returns: true if this instance is equal to other instance, false othervise

Here is the call graph for this function:

Friends And Related Function Documentation

◆ swap

template<class Key , class Value >

void swap	(	trie< Key, Value > &	first,
		trie< Key, Value > &	second
	)

friend

Swap method of two tries.

Parameters

first	the first forward trie to swap
second	the second forward trie to swap

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

alib2std/src/extensions/container/trie.hpp

Public Types

Public Member Functions

Friends

Detailed Description

Member Typedef Documentation

◆ children_iterator

◆ const_children_iterator

Constructor & Destructor Documentation

◆ trie() [1/7]

◆ trie() [2/7]

◆ trie() [3/7]

◆ trie() [4/7]

◆ trie() [5/7]

◆ ~trie()

◆ trie() [6/7]

◆ trie() [7/7]

Member Function Documentation

◆ begin() [1/2]

◆ begin() [2/2]

◆ checkStructure() [1/2]

◆ checkStructure() [2/2]

◆ end() [1/2]

◆ end() [2/2]

◆ erase()

◆ getChildren() [1/2]

◆ getChildren() [2/2]

◆ getData() [1/2]

◆ getData() [2/2]

◆ getParent() [1/2]

◆ getParent() [2/2]

◆ insert() [1/3]

◆ insert() [2/3]

◆ insert() [3/3]

◆ nicePrint()

◆ operator()() [1/4]

◆ operator()() [2/4]

◆ operator()() [3/4]

◆ operator()() [4/4]

◆ operator<=>()

◆ operator=() [1/2]

◆ operator=() [2/2]

◆ operator==()

Friends And Related Function Documentation

◆ swap