This class represents a tree. More...

#include <carlTree.h>

Collaboration diagram for carl::tree< T >:

[legend]

Public Types
using	value_type = T

using	Node = tree_detail::Node< T >

template<bool reverse>
using	PreorderIterator = tree_detail::PreorderIterator< T, reverse >

template<bool reverse>
using	PostorderIterator = tree_detail::PostorderIterator< T, reverse >

template<bool reverse>
using	LeafIterator = tree_detail::LeafIterator< T, reverse >

template<bool reverse>
using	DepthIterator = tree_detail::DepthIterator< T, reverse >

template<bool reverse>
using	ChildrenIterator = tree_detail::ChildrenIterator< T, reverse >

using	PathIterator = tree_detail::PathIterator< T >

using	iterator = PreorderIterator< false >

Public Member Functions
	tree ()=default

	tree (const tree &t)=default

	tree (tree &&t) noexcept=default

tree &	operator= (const tree &t)=default

tree &	operator= (tree &&t) noexcept=default

void	debug () const

iterator	begin () const

iterator	end () const

iterator	rbegin () const

iterator	rend () const

PreorderIterator< false >	begin_preorder () const

PreorderIterator< false >	end_preorder () const

PreorderIterator< true >	rbegin_preorder () const

PreorderIterator< true >	rend_preorder () const

PostorderIterator< false >	begin_postorder () const

PostorderIterator< false >	end_postorder () const

PostorderIterator< true >	rbegin_postorder () const

PostorderIterator< true >	rend_postorder () const

LeafIterator< false >	begin_leaf () const

LeafIterator< false >	end_leaf () const

LeafIterator< true >	rbegin_leaf () const

LeafIterator< true >	rend_leaf () const

DepthIterator< false >	begin_depth (std::size_t depth) const

DepthIterator< false >	end_depth () const

DepthIterator< true >	rbegin_depth (std::size_t depth) const

DepthIterator< true >	rend_depth () const

template<typename Iterator >
ChildrenIterator< false >	begin_children (const Iterator &it) const

template<typename Iterator >
ChildrenIterator< false >	end_children (const Iterator &it) const

template<typename Iterator >
ChildrenIterator< true >	rbegin_children (const Iterator &it) const

template<typename Iterator >
ChildrenIterator< true >	rend_children (const Iterator &it) const

template<typename Iterator >
PathIterator	begin_path (const Iterator &it) const

PathIterator	end_path () const

std::size_t	max_depth () const
	Retrieves the maximum depth of all elements. More...

template<typename Iterator >
std::size_t	max_depth (const Iterator &it) const

template<typename Iterator >
bool	is_leaf (const Iterator &it) const
	Check if the given element is a leaf. More...

template<typename Iterator >
bool	is_leftmost (const Iterator &it) const
	Check if the given element is a leftmost child. More...

template<typename Iterator >
bool	is_rightmost (const Iterator &it) const
	Check if the given element is a rightmost child. More...

template<typename Iterator >
bool	is_valid (const Iterator &it) const

template<typename Iterator >
Iterator	get_parent (const Iterator &it) const
	Retrieves the parent of an element. More...

template<typename Iterator >
Iterator	left_sibling (const Iterator &it) const

iterator	setRoot (const T &data)
	Sets the value of the root element. More...

iterator	setRoot (T &&data)

void	clear ()
	Clears the tree. More...

iterator	append (const T &data)
	Add the given data as last child of the root element. More...

template<typename Iterator >
Iterator	append (Iterator parent, const T &data)
	Add the given data as last child of the given element. More...

template<typename Iterator >
Iterator	insert (Iterator position, const T &data)
	Insert element before the given position. More...

iterator	append (tree &&tree)
	Append another tree as last child of the root element. More...

template<typename Iterator >
Iterator	append (Iterator position, tree &&data)
	Append another tree as last child of the given element. More...

template<typename Iterator >
const Iterator &	replace (const Iterator &position, const T &data)

template<typename Iterator >
Iterator	erase (Iterator position)
	Erase the element at the given position. More...

template<typename Iterator >
void	eraseChildren (const Iterator &position)
	Erase all children of the given element. More...

bool	is_consistent () const

bool	is_consistent (std::size_t node) const

Private Member Functions
std::size_t	newNode (T &&data, std::size_t parent, std::size_t depth)

std::size_t	createNode (const T &data, std::size_t parent, std::size_t depth)

void	eraseChildren (std::size_t id)

void	eraseNode (std::size_t id)

Private Attributes
std::vector< Node >	nodes

std::size_t	emptyNodes = MAXINT

Static Private Attributes
static constexpr std::size_t	MAXINT = tree_detail::MAXINT

Friends
template<typename TT , typename Iterator , bool reverse>
struct	tree_detail::BaseIterator

Detailed Description

template<typename T>
class carl::tree< T >

This class represents a tree.

It tries to stick to the STL style as close as possible.

Definition at line 559 of file carlTree.h.

Member Typedef Documentation

◆ ChildrenIterator

template<typename T >

template<bool reverse>

using carl::tree< T >::ChildrenIterator = tree_detail::ChildrenIterator<T,reverse>

Definition at line 573 of file carlTree.h.

◆ DepthIterator

template<typename T >

template<bool reverse>

using carl::tree< T >::DepthIterator = tree_detail::DepthIterator<T,reverse>

Definition at line 571 of file carlTree.h.

◆ iterator

template<typename T >

using carl::tree< T >::iterator = PreorderIterator<false>

Definition at line 584 of file carlTree.h.

◆ LeafIterator

template<typename T >

template<bool reverse>

using carl::tree< T >::LeafIterator = tree_detail::LeafIterator<T,reverse>

Definition at line 569 of file carlTree.h.

◆ Node

template<typename T >

using carl::tree< T >::Node = tree_detail::Node<T>

Definition at line 562 of file carlTree.h.

◆ PathIterator

template<typename T >

using carl::tree< T >::PathIterator = tree_detail::PathIterator<T>

Definition at line 574 of file carlTree.h.

◆ PostorderIterator

template<typename T >

template<bool reverse>

using carl::tree< T >::PostorderIterator = tree_detail::PostorderIterator<T,reverse>

Definition at line 567 of file carlTree.h.

◆ PreorderIterator

template<typename T >

template<bool reverse>

using carl::tree< T >::PreorderIterator = tree_detail::PreorderIterator<T,reverse>

Definition at line 565 of file carlTree.h.

◆ value_type

template<typename T >

using carl::tree< T >::value_type = T

Definition at line 561 of file carlTree.h.

Constructor & Destructor Documentation

◆ tree() [1/3]

template<typename T >

carl::tree< T >::tree ( )

default

◆ tree() [2/3]

template<typename T >

carl::tree< T >::tree ( const tree< T > & t )

default

◆ tree() [3/3]

template<typename T >

carl::tree< T >::tree ( tree< T > && t )

defaultnoexcept

Member Function Documentation

◆ append() [1/4]

template<typename T >

iterator carl::tree< T >::append ( const T & data )

inline

Add the given data as last child of the root element.

Parameters

data Data.

Returns: Iterator to inserted element.

Definition at line 785 of file carlTree.h.

Here is the call graph for this function:

◆ append() [2/4]

template<typename T >

template<typename Iterator >

Iterator carl::tree< T >::append	(	Iterator	parent,
		const T &	data
	)

inline

Add the given data as last child of the given element.

Parameters

parent	Parent element.
data	Data.

Returns: Iterator to inserted element.

Definition at line 797 of file carlTree.h.

Here is the call graph for this function:

◆ append() [3/4]

template<typename T >

template<typename Iterator >

Iterator carl::tree< T >::append	(	Iterator	position,
		tree< T > &&	data
	)

inline

Append another tree as last child of the given element.

Parameters

position	Element.
tree	Tree.

Returns: Iterator to root of inserted subtree.

Definition at line 847 of file carlTree.h.

◆ append() [4/4]

template<typename T >

iterator carl::tree< T >::append ( tree< T > && tree )

inline

Append another tree as last child of the root element.

Parameters

tree Tree.

Returns: Iterator to root of inserted subtree.

Definition at line 836 of file carlTree.h.

Here is the call graph for this function:

◆ begin()

template<typename T >

iterator carl::tree< T >::begin ( ) const

inline

Definition at line 597 of file carlTree.h.

◆ begin_children()

template<typename T >

template<typename Iterator >

ChildrenIterator<false> carl::tree< T >::begin_children ( const Iterator & it ) const

inline

Definition at line 667 of file carlTree.h.

◆ begin_depth()

template<typename T >

DepthIterator<false> carl::tree< T >::begin_depth ( std::size_t depth ) const

inline

Definition at line 654 of file carlTree.h.

Here is the call graph for this function:

◆ begin_leaf()

template<typename T >

LeafIterator<false> carl::tree< T >::begin_leaf ( ) const

inline

Definition at line 638 of file carlTree.h.

Here is the call graph for this function:

◆ begin_path()

template<typename T >

template<typename Iterator >

PathIterator carl::tree< T >::begin_path ( const Iterator & it ) const

inline

Definition at line 683 of file carlTree.h.

◆ begin_postorder()

template<typename T >

PostorderIterator<false> carl::tree< T >::begin_postorder ( ) const

inline

Definition at line 624 of file carlTree.h.

Here is the call graph for this function:

◆ begin_preorder()

template<typename T >

PreorderIterator<false> carl::tree< T >::begin_preorder ( ) const

inline

Definition at line 610 of file carlTree.h.

Here is the caller graph for this function:

◆ clear()

template<typename T >

void carl::tree< T >::clear ( )

inline

Clears the tree.

Definition at line 776 of file carlTree.h.

Here is the call graph for this function:

◆ createNode()

template<typename T >

std::size_t carl::tree< T >::createNode	(	const T &	data,
		std::size_t	parent,
		std::size_t	depth
	)

inlineprivate

Definition at line 919 of file carlTree.h.

Here is the call graph for this function:

◆ debug()

template<typename T >

void carl::tree< T >::debug ( ) const

inline

Definition at line 592 of file carlTree.h.

◆ end()

template<typename T >

iterator carl::tree< T >::end ( ) const

inline

Definition at line 600 of file carlTree.h.

◆ end_children()

template<typename T >

template<typename Iterator >

ChildrenIterator<false> carl::tree< T >::end_children ( const Iterator & it ) const

inline

Definition at line 671 of file carlTree.h.

◆ end_depth()

template<typename T >

DepthIterator<false> carl::tree< T >::end_depth ( ) const

inline

Definition at line 657 of file carlTree.h.

◆ end_leaf()

template<typename T >

LeafIterator<false> carl::tree< T >::end_leaf ( ) const

inline

Definition at line 643 of file carlTree.h.

◆ end_path()

template<typename T >

PathIterator carl::tree< T >::end_path ( ) const

inline

Definition at line 686 of file carlTree.h.

◆ end_postorder()

template<typename T >

PostorderIterator<false> carl::tree< T >::end_postorder ( ) const

inline

Definition at line 629 of file carlTree.h.

◆ end_preorder()

template<typename T >

PreorderIterator<false> carl::tree< T >::end_preorder ( ) const

inline

Definition at line 613 of file carlTree.h.

Here is the caller graph for this function:

◆ erase()

template<typename T >

template<typename Iterator >

Iterator carl::tree< T >::erase ( Iterator position )

inline

Erase the element at the given position.

Returns an iterator to the next position.

Parameters

position Element.

Returns: Next element.

Definition at line 873 of file carlTree.h.

Here is the call graph for this function:

◆ eraseChildren() [1/2]

template<typename T >

template<typename Iterator >

void carl::tree< T >::eraseChildren ( const Iterator & position )

inline

Erase all children of the given element.

Parameters

position Element.

Definition at line 901 of file carlTree.h.

◆ eraseChildren() [2/2]

template<typename T >

void carl::tree< T >::eraseChildren ( std::size_t id )

inlineprivate

Definition at line 934 of file carlTree.h.

Here is the call graph for this function:

◆ eraseNode()

template<typename T >

void carl::tree< T >::eraseNode ( std::size_t id )

inlineprivate

Definition at line 945 of file carlTree.h.

Here is the call graph for this function:

◆ get_parent()

template<typename T >

template<typename Iterator >

Iterator carl::tree< T >::get_parent ( const Iterator & it ) const

inline

Retrieves the parent of an element.

Parameters

it Iterator.

Returns: Parent of it.

Definition at line 749 of file carlTree.h.

Here is the call graph for this function:

◆ insert()

template<typename T >

template<typename Iterator >

Iterator carl::tree< T >::insert	(	Iterator	position,
		const T &	data
	)

inline

Insert element before the given position.

Parameters

position	Position to insert before.
data	Element to insert.

Returns: PreorderIterator to inserted element.

Definition at line 810 of file carlTree.h.

Here is the call graph for this function:

◆ is_consistent() [1/2]

template<typename T >

bool carl::tree< T >::is_consistent ( ) const

inline

Definition at line 954 of file carlTree.h.

◆ is_consistent() [2/2]

template<typename T >

bool carl::tree< T >::is_consistent ( std::size_t node ) const

inline

Definition at line 960 of file carlTree.h.

Here is the call graph for this function:

◆ is_leaf()

template<typename T >

template<typename Iterator >

bool carl::tree< T >::is_leaf ( const Iterator & it ) const

inline

Check if the given element is a leaf.

Parameters

it Iterator.

Returns: If it is a leaf.

Definition at line 717 of file carlTree.h.

Here is the call graph for this function:

◆ is_leftmost()

template<typename T >

template<typename Iterator >

bool carl::tree< T >::is_leftmost ( const Iterator & it ) const

inline

Check if the given element is a leftmost child.

Parameters

it Iterator.

Returns: If it is a leftmost child.

Definition at line 726 of file carlTree.h.

Here is the call graph for this function:

◆ is_rightmost()

template<typename T >

template<typename Iterator >

bool carl::tree< T >::is_rightmost ( const Iterator & it ) const

inline

Check if the given element is a rightmost child.

Parameters

it Iterator.

Returns: If it is a rightmost child.

Definition at line 735 of file carlTree.h.

Here is the call graph for this function:

◆ is_valid()

template<typename T >

template<typename Iterator >

bool carl::tree< T >::is_valid ( const Iterator & it ) const

inline

Definition at line 739 of file carlTree.h.

Here is the call graph for this function:

◆ left_sibling()

template<typename T >

template<typename Iterator >

Iterator carl::tree< T >::left_sibling ( const Iterator & it ) const

inline

Definition at line 753 of file carlTree.h.

Here is the call graph for this function:

◆ max_depth() [1/2]

template<typename T >

std::size_t carl::tree< T >::max_depth ( ) const

inline

Retrieves the maximum depth of all elements.

Returns: Maximum depth.

Definition at line 694 of file carlTree.h.

◆ max_depth() [2/2]

template<typename T >

template<typename Iterator >

std::size_t carl::tree< T >::max_depth ( const Iterator & it ) const

inline

Definition at line 702 of file carlTree.h.

◆ newNode()

template<typename T >

std::size_t carl::tree< T >::newNode	(	T &&	data,
		std::size_t	parent,
		std::size_t	depth
	)

inlineprivate

Definition at line 905 of file carlTree.h.

Here is the call graph for this function:

◆ operator=() [1/2]

template<typename T >

tree& carl::tree< T >::operator= ( const tree< T > & t )

default

◆ operator=() [2/2]

template<typename T >

tree& carl::tree< T >::operator= ( tree< T > && t )

defaultnoexcept

◆ rbegin()

template<typename T >

iterator carl::tree< T >::rbegin ( ) const

inline

Definition at line 603 of file carlTree.h.

◆ rbegin_children()

template<typename T >

template<typename Iterator >

ChildrenIterator<true> carl::tree< T >::rbegin_children ( const Iterator & it ) const

inline

Definition at line 675 of file carlTree.h.

◆ rbegin_depth()

template<typename T >

DepthIterator<true> carl::tree< T >::rbegin_depth ( std::size_t depth ) const

inline

Definition at line 660 of file carlTree.h.

Here is the call graph for this function:

◆ rbegin_leaf()

template<typename T >

LeafIterator<true> carl::tree< T >::rbegin_leaf ( ) const

inline

Definition at line 646 of file carlTree.h.

Here is the call graph for this function:

◆ rbegin_postorder()

template<typename T >

PostorderIterator<true> carl::tree< T >::rbegin_postorder ( ) const

inline

Definition at line 632 of file carlTree.h.

◆ rbegin_preorder()

template<typename T >

PreorderIterator<true> carl::tree< T >::rbegin_preorder ( ) const

inline

Definition at line 616 of file carlTree.h.

Here is the call graph for this function:

◆ rend()

template<typename T >

iterator carl::tree< T >::rend ( ) const

inline

Definition at line 606 of file carlTree.h.

◆ rend_children()

template<typename T >

template<typename Iterator >

ChildrenIterator<true> carl::tree< T >::rend_children ( const Iterator & it ) const

inline

Definition at line 679 of file carlTree.h.

◆ rend_depth()

template<typename T >

DepthIterator<true> carl::tree< T >::rend_depth ( ) const

inline

Definition at line 663 of file carlTree.h.

◆ rend_leaf()

template<typename T >

LeafIterator<true> carl::tree< T >::rend_leaf ( ) const

inline

Definition at line 651 of file carlTree.h.

◆ rend_postorder()

template<typename T >

PostorderIterator<true> carl::tree< T >::rend_postorder ( ) const

inline

Definition at line 635 of file carlTree.h.

◆ rend_preorder()

template<typename T >

PreorderIterator<true> carl::tree< T >::rend_preorder ( ) const

inline

Definition at line 621 of file carlTree.h.

◆ replace()

template<typename T >

template<typename Iterator >

const Iterator& carl::tree< T >::replace	(	const Iterator &	position,
		const T &	data
	)

inline

Definition at line 861 of file carlTree.h.

Here is the call graph for this function:

◆ setRoot() [1/2]

template<typename T >

iterator carl::tree< T >::setRoot ( const T & data )

inline

Sets the value of the root element.

Parameters

data Data.

Returns: Iterator to the root.

Definition at line 765 of file carlTree.h.

◆ setRoot() [2/2]

template<typename T >

iterator carl::tree< T >::setRoot ( T && data )

inline

Definition at line 768 of file carlTree.h.

Here is the call graph for this function:

Friends And Related Function Documentation

◆ tree_detail::BaseIterator

template<typename T >

template<typename TT , typename Iterator , bool reverse>

friend struct tree_detail::BaseIterator

friend

Definition at line 577 of file carlTree.h.

Field Documentation

◆ emptyNodes

template<typename T >

std::size_t carl::tree< T >::emptyNodes = MAXINT

private

Definition at line 581 of file carlTree.h.

◆ MAXINT

template<typename T >

const std::size_t carl::tree< T >::MAXINT = tree_detail::MAXINT

staticconstexprprivate

Definition at line 579 of file carlTree.h.

◆ nodes

template<typename T >

std::vector<Node> carl::tree< T >::nodes

private

Definition at line 580 of file carlTree.h.

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

carl-common/datastructures/carlTree.h

Public Types

Public Member Functions

Private Member Functions

Private Attributes

Static Private Attributes

Friends

Detailed Description

template<typename T> class carl::tree< T >

Member Typedef Documentation

◆ ChildrenIterator

◆ DepthIterator

◆ iterator

◆ LeafIterator

◆ Node

◆ PathIterator

◆ PostorderIterator

◆ PreorderIterator

◆ value_type

Constructor & Destructor Documentation

◆ tree() [1/3]

◆ tree() [2/3]

◆ tree() [3/3]

Member Function Documentation

◆ append() [1/4]

◆ append() [2/4]

◆ append() [3/4]

◆ append() [4/4]

◆ begin()

◆ begin_children()

◆ begin_depth()

◆ begin_leaf()

◆ begin_path()

◆ begin_postorder()

◆ begin_preorder()

◆ clear()

◆ createNode()

◆ debug()

◆ end()

◆ end_children()

◆ end_depth()

◆ end_leaf()

◆ end_path()

◆ end_postorder()

◆ end_preorder()

◆ erase()

◆ eraseChildren() [1/2]

◆ eraseChildren() [2/2]

◆ eraseNode()

◆ get_parent()

◆ insert()

◆ is_consistent() [1/2]

◆ is_consistent() [2/2]

◆ is_leaf()

◆ is_leftmost()

◆ is_rightmost()

◆ is_valid()

◆ left_sibling()

◆ max_depth() [1/2]

◆ max_depth() [2/2]

◆ newNode()

◆ operator=() [1/2]

◆ operator=() [2/2]

◆ rbegin()

◆ rbegin_children()

◆ rbegin_depth()

◆ rbegin_leaf()

◆ rbegin_postorder()

◆ rbegin_preorder()

◆ rend()

◆ rend_children()

◆ rend_depth()

◆ rend_leaf()

◆ rend_postorder()

◆ rend_preorder()

◆ replace()

◆ setRoot() [1/2]

◆ setRoot() [2/2]

Friends And Related Function Documentation

◆ tree_detail::BaseIterator

Field Documentation

template<typename T>
class carl::tree< T >