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

#include <tree.hpp>

Data Structures
class	const_postfix_iterator
	The iterator type over structure of the tree following postorder traversal. More...

class	const_prefix_iterator
	The iterator type over structure of the tree following preorder traversal. More...

class	const_structure_iterator
	The iterator type over structure of the tree representing nodes and node_ends. More...

Public Types
typedef ext::vector< tree >::const_iterator	const_children_iterator
	The iterator type over children of the node. More...

typedef ext::vector< tree >::iterator	children_iterator
	The iterator type over children of the node. More...

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

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

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

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

ext::vector< tree > &	getChildren ()
	Getter of children of the root node. More...

const ext::vector< tree > &	getChildren () const
	Getter of children of the root node. More...

const_children_iterator	insert (const_children_iterator position, tree< T > &&value)
	Inserts a subtree into a tree. More...

const_children_iterator	insert (const_children_iterator position, const tree< T > &value)
	Inserts a subtree into a tree. More...

const_children_iterator	insert (const_children_iterator position, const_children_iterator begin, const_children_iterator end)
	Inserts subtrees given by range of values at specified position. More...

template<class Iterator >
const_children_iterator	insert (const_children_iterator position, Iterator begin, Iterator end)
	Inserts a subtrees into a tree. The subtrees are nullary nodes having value given by values in the range begin to end. More...

	tree (T &&data, ext::vector< tree > &&children)
	Constructor of the tree from value to be stored in the root node and children trees. More...

	tree (const T &data, const ext::vector< tree > &subtrees)
	Constructor of the tree from value to be stored in the root node and children trees. More...

template<typename ... Types>
	tree (const T &data, Types ... subtrees)
	Constructor of the tree from value to be stored in the root node and pack of children trees. More...

template<typename ... Types>
	tree (T &&data, Types ... subtrees)
	Constructor of the tree from value to be stored in the root node and pack of children trees. More...

template<typename Iterator >
	tree (const T &data, Iterator begin, Iterator end)
	Constructor of the tree from value to be stored in the root node and range of values to construct nullary nodes from range of values. More...

	tree (const T &data, const_children_iterator begin, const_children_iterator end)
	Constructor of the tree from value to be stored in the root node and range of subtrees. More...

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

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

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

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

tree &	operator= (tree &&node) noexcept
	Move operator of assignment of the tree. 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...

const_prefix_iterator	prefix_begin () const
	Getter of the prefix iterator to the root node. More...

const_prefix_iterator	prefix_end () const
	Getter of the prefix iterator one after the last node in the prefix traversal. More...

const_postfix_iterator	postfix_begin () const
	Getter of the postfix iterator to the first node in the postfix traversal. More...

const_postfix_iterator	postfix_end () const
	Getter of the postfix iterator one after the last node in the postfix traversal. More...

const_structure_iterator	structure_begin () const
	Getter of the structure iterator to the first node in the traversal. More...

const_structure_iterator	structure_end () const
	Getter of the structure iterator to one after the last node in the traversal. More...

void	push_back (ext::tree< T > &&value)
	Pushbacks a subtree after last child of a tree. More...

void	push_back (const ext::tree< T > &value)
	Pushbacks a subtree after last child of a tree. More...

void	push_back (T &&value)
	Pushbacks a nullary node after last child of a tree. More...

void	push_back (const T &value)
	Pushbacks a nullary node after last child of a tree. More...

children_iterator	erase (const_children_iterator position)
	Erases a subtree from a tree on given by `position`. More...

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

const T &	operator() (std::initializer_list< size_t > indexes) const
	Access value given indexes of chindren allong the selection path. More...

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

T &	operator() (std::initializer_list< size_t > indexes)
	Access value given indexes of chindren allong the selection path. More...

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

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

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

auto	operator<=> (const tree &other) const -> decltype(std::declval< T >()<=> std::declval< T >())
	Greater or equal comparison operator. More...

ext::ostream &	nicePrint (ext::ostream &os) const
	Method of printing a tree into a stream. More...

Friends
void	swap (tree &first, tree &second)
	Swap method of two trees. More...

Detailed Description

template<class T>
class ext::tree< T >

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

The tree is a hierarchical structure of nodes with parent child relationship, where the children are ordered and indexed by integers.

Template Parameters

T	the type of values inside nodes of the tree

Member Typedef Documentation

◆ children_iterator

template<class T >

typedef ext::vector<tree>::iterator ext::tree< T >::children_iterator

The iterator type over children of the node.

◆ const_children_iterator

template<class T >

typedef ext::vector<tree>::const_iterator ext::tree< T >::const_children_iterator

The iterator type over children of the node.

Constructor & Destructor Documentation

◆ tree() [1/8]

template<class T >

ext::tree< T >::tree	(	T &&	data,
		ext::vector< tree< T > > &&	children
	)

inline

Constructor of the tree from value to be stored in the root node and children trees.

Parameters

data	the value to be stored in the root
children	list of subtrees

Here is the caller graph for this function:

◆ tree() [2/8]

template<class T >

ext::tree< T >::tree	(	const T &	data,
		const ext::vector< tree< T > > &	subtrees
	)

inline

Constructor of the tree from value to be stored in the root node and children trees.

Parameters

data	the value to be stored in the root
children	list of subtrees

◆ tree() [3/8]

template<class T >

template<typename ... Types>

ext::tree< T >::tree	(	const T &	data,
		Types ...	subtrees
	)

inline

Constructor of the tree from value to be stored in the root node and pack of children trees.

Template Parameters

Types ... pack of types convertible to tree

Parameters

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

◆ tree() [4/8]

template<class T >

template<typename ... Types>

ext::tree< T >::tree	(	T &&	data,
		Types ...	subtrees
	)

inline

Constructor of the tree from value to be stored in the root node and pack of children trees.

Template Parameters

Types ... pack of types convertible to tree

Parameters

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

◆ tree() [5/8]

template<class T >

template<typename Iterator >

ext::tree< T >::tree	(	const T &	data,
		Iterator	begin,
		Iterator	end
	)

inline

Constructor of the tree from value to be stored in the root node and range of values to construct nullary nodes from range of values.

Parameters

data	the value to be stored in the root
begin	the iterator to the begining of values range
end	the iterator to the end of values range

◆ tree() [6/8]

template<class T >

ext::tree< T >::tree	(	const T &	data,
		const_children_iterator	begin,
		const_children_iterator	end
	)

inline

Constructor of the tree from value to be stored in the root node and range of subtrees.

Parameters

data	the value to be stored in the root
begin	the iterator to the begining of subtree range
end	the iterator to the end of subtree range

◆ ~tree()

template<class T >

ext::tree< T >::~tree ( )

defaultnoexcept

Dectructor of the tree.

◆ tree() [7/8]

template<class T >

ext::tree< T >::tree ( const tree< T > & other )

inline

Copy constructor of the tree.

Parameters

other the other instace of the tree

◆ tree() [8/8]

template<class T >

ext::tree< T >::tree ( tree< T > && other )

inlinenoexcept

Move constructor of the tree.

Parameters

other the other instace of the tree

Member Function Documentation

◆ begin() [1/2]

template<class T >

children_iterator ext::tree< T >::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 T >

const_children_iterator ext::tree< T >::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 T >

bool ext::tree< T >::checkStructure ( ) const

inline

Helper method to traverse the tree 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 T >

bool ext::tree< T >::checkStructure ( const tree< T > & node ) const

inline

Helper method to traverse the tree 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 T >

children_iterator ext::tree< T >::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 T >

const_children_iterator ext::tree< T >::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 T >

children_iterator ext::tree< T >::erase ( const_children_iterator position )

inline

Erases a subtree from a tree on given by position.

Parameters

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

Here is the call graph for this function:

◆ getChildren() [1/2]

template<class T >

ext::vector< tree > & ext::tree< T >::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 T >

const ext::vector< tree > & ext::tree< T >::getChildren ( ) const

inline

Getter of children of the root node.

Returns: children of the root node

◆ getData() [1/2]

template<class T >

T & ext::tree< T >::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 T >

const T & ext::tree< T >::getData ( ) const

inline

Getter of the value in the root node.

Returns: the value in the root node

◆ getParent() [1/2]

template<class T >

tree * ext::tree< T >::getParent ( )

inline

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

Returns: pointer to the parent node

Here is the caller graph for this function:

◆ getParent() [2/2]

template<class T >

const tree * ext::tree< T >::getParent ( ) const

inline

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

Returns: pointer to the parent node

◆ insert() [1/4]

template<class T >

const_children_iterator ext::tree< T >::insert	(	const_children_iterator	position,
		const tree< T > &	value
	)

inline

Inserts a subtree into a tree.

Parameters

position	the specification of position in children of the node where to add subtrees
value	a subtree to insert

Returns: updated position iterator pointing to the first node inserted

Here is the call graph for this function:

◆ insert() [2/4]

template<class T >

const_children_iterator ext::tree< T >::insert	(	const_children_iterator	position,
		const_children_iterator	begin,
		const_children_iterator	end
	)

inline

Inserts subtrees given by range of values at specified position.

Parameters

position	the specification of position in children of the node where to add subtrees
begin	the start of the range of subtrees
end	the end of the range of subtrees

Returns: updated position iterator pointing to the first node inserted

Here is the call graph for this function:

◆ insert() [3/4]

template<class T >

template<class Iterator >

const_children_iterator ext::tree< T >::insert	(	const_children_iterator	position,
		Iterator	begin,
		Iterator	end
	)

inline

Inserts a subtrees into a tree. The subtrees are nullary nodes having value given by values in the range begin to end.

Template Parameters

Iterator the type of iterators forming the range

Parameters

position	the specification of position in children of the node where to add subtrees
begin	the start of the range of values
end	the end of the range of values

Returns: updated position iterator pointing to the first node inserted

Here is the call graph for this function:

◆ insert() [4/4]

template<class T >

const_children_iterator ext::tree< T >::insert	(	const_children_iterator	position,
		tree< T > &&	value
	)

inline

Inserts a subtree into a tree.

Parameters

position	the specification of position in children of the node where to add subtrees
value	a subtree 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 T >

ext::ostream & ext::tree< T >::nicePrint ( ext::ostream & os ) const

inline

Method of printing a tree into a stream.

The tree is printed hierarchically.

Example tree a ( b ( c ), b ( c ) ) would be printed like

-a | |-b | | | -c | -b | -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 T >

template<class ... Indexes>

T & ext::tree< T >::operator() ( Indexes ... indexes )

inline

Access value given indexes of chindren allong the selection path.

Template Parameters

Indexes ... types of child indexes

Parameters

indexes actual values of child indexes

Returns: the value in the selected node

Here is the call graph for this function:

◆ operator()() [2/4]

template<class T >

template<class ... Indexes>

const T & ext::tree< T >::operator() ( Indexes ... indexes ) const

inline

Access value given indexes of chindren allong the selection path.

Template Parameters

Indexes ... types of child indexes

Parameters

indexes actual values of child indexes

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

T & ext::tree< T >::operator() ( std::initializer_list< size_t > indexes )

inline

Access value given indexes of chindren allong the selection path.

Parameters

indexes actual values of child indexes

Returns: the value in the selected node

◆ operator()() [4/4]

template<class T >

const T & ext::tree< T >::operator() ( std::initializer_list< size_t > indexes ) const

inline

Access value given indexes of chindren allong the selection path.

Parameters

indexes actual values of child indexes

Returns: the value in the selected node

◆ operator<=>()

template<class T >

auto ext::tree< T >::operator<=> ( const tree< T > & other ) const -> decltype ( std::declval < T > ( ) <=> std::declval < T > ( ) )

inline

Greater or equal comparison operator.

Parameters

other the other instance to compare with

Returns: true if this instance is greater or equal than other instance, false othervise

Here is the call graph for this function:

◆ operator=() [1/2]

template<class T >

tree & ext::tree< T >::operator= ( const tree< T > & node )

inline

Copy operator of assignment of the tree.

Parameters

other the other instace of the tree

Returns: the assigned to instance

Here is the call graph for this function:

◆ operator=() [2/2]

template<class T >

tree & ext::tree< T >::operator= ( tree< T > && node )

inlinenoexcept

Move operator of assignment of the tree.

Parameters

other the other instace of the tree

Returns: the assigned to instance

◆ operator==()

template<class T >

bool ext::tree< T >::operator== ( const tree< T > & 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:

◆ postfix_begin()

template<class T >

const_postfix_iterator ext::tree< T >::postfix_begin ( ) const

inline

Getter of the postfix iterator to the first node in the postfix traversal.

Returns: prefix iterator to the first node in the postfix traversal

◆ postfix_end()

template<class T >

const_postfix_iterator ext::tree< T >::postfix_end ( ) const

inline

Getter of the postfix iterator one after the last node in the postfix traversal.

Returns: prefix iterator one after the last node in the postfix traversal

◆ prefix_begin()

template<class T >

const_prefix_iterator ext::tree< T >::prefix_begin ( ) const

inline

Getter of the prefix iterator to the root node.

Returns: prefix iterator to the root

Here is the caller graph for this function:

◆ prefix_end()

template<class T >

const_prefix_iterator ext::tree< T >::prefix_end ( ) const

inline

Getter of the prefix iterator one after the last node in the prefix traversal.

Returns: prefix iterator one after the last node in the prefix traversal

Here is the caller graph for this function:

◆ push_back() [1/4]

template<class T >

void ext::tree< T >::push_back ( const ext::tree< T > & value )

inline

Pushbacks a subtree after last child of a tree.

Parameters

value a subtree to pushback to child list

Here is the call graph for this function:

◆ push_back() [2/4]

template<class T >

void ext::tree< T >::push_back ( const T & value )

inline

Pushbacks a nullary node after last child of a tree.

Parameters

value a value to store in nullary node push-backed to the child list

Here is the call graph for this function:

◆ push_back() [3/4]

template<class T >

void ext::tree< T >::push_back ( ext::tree< T > && value )

inline

Pushbacks a subtree after last child of a tree.

Parameters

value a subtree to pushback to child list

Here is the caller graph for this function:

◆ push_back() [4/4]

template<class T >

void ext::tree< T >::push_back ( T && value )

inline

Pushbacks a nullary node after last child of a tree.

Parameters

value a value to store in nullary node push-backed to the child list

Here is the call graph for this function:

◆ structure_begin()

template<class T >

const_structure_iterator ext::tree< T >::structure_begin ( ) const

inline

Getter of the structure iterator to the first node in the traversal.

Returns: prefix iterator to the first node in the traversal

◆ structure_end()

template<class T >

const_structure_iterator ext::tree< T >::structure_end ( ) const

inline

Getter of the structure iterator to one after the last node in the traversal.

Returns: prefix iterator to one after the last node in the traversal

Friends And Related Function Documentation

◆ swap

template<class T >

void swap	(	tree< T > &	first,
		tree< T > &	second
	)

friend

Swap method of two trees.

Parameters

first	the first tree to swap
second	the second tree to swap

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

alib2std/src/extensions/container/tree.hpp

Data Structures

Public Types

Public Member Functions

Friends

Detailed Description

Member Typedef Documentation

◆ children_iterator

◆ const_children_iterator

Constructor & Destructor Documentation

◆ tree() [1/8]

◆ tree() [2/8]

◆ tree() [3/8]

◆ tree() [4/8]

◆ tree() [5/8]

◆ tree() [6/8]

◆ ~tree()

◆ tree() [7/8]

◆ tree() [8/8]

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/4]

◆ insert() [2/4]

◆ insert() [3/4]

◆ insert() [4/4]

◆ nicePrint()

◆ operator()() [1/4]

◆ operator()() [2/4]

◆ operator()() [3/4]

◆ operator()() [4/4]

◆ operator<=>()

◆ operator=() [1/2]

◆ operator=() [2/2]

◆ operator==()

◆ postfix_begin()

◆ postfix_end()

◆ prefix_begin()

◆ prefix_end()

◆ push_back() [1/4]

◆ push_back() [2/4]

◆ push_back() [3/4]

◆ push_back() [4/4]

◆ structure_begin()

◆ structure_end()

Friends And Related Function Documentation

◆ swap