matador::tree< T > Class Template Reference

A STL like tree class. More...

#include <tree.hpp>

Public Types
typedef t_tree_node< T >	t_node
typedef T	value_type
typedef tree_iterator< T >	iterator
typedef const_tree_iterator< T >	const_iterator
typedef tree_sibling_iterator< T >	sibling_iterator
typedef const_tree_sibling_iterator< T >	const_sibling_iterator
typedef tree_subtree_iterator< T >	subtree_iterator
typedef const_tree_subtree_iterator< T >	const_subtree_iterator
typedef tree_leaf_iterator< T >	leaf_iterator
typedef const_tree_leaf_iterator< T >	const_leaf_iterator
typedef std::reverse_iterator< iterator >	reverse_iterator
typedef std::reverse_iterator< const_iterator >	const_reverse_iterator
typedef T &	reference
typedef T *	pointer
typedef const T &	const_reference
typedef const T *	const_pointer
typedef std::pair< sibling_iterator, sibling_iterator >	range_pair

Public Member Functions
	tree ()
	~tree ()
iterator	begin ()
iterator	end ()
const_iterator	begin () const
const_iterator	end () const
reverse_iterator	rbegin ()
reverse_iterator	rend ()
const_reverse_iterator	rbegin () const
const_reverse_iterator	rend () const
sibling_iterator	begin (const tree_iterator_base< T > &i)
sibling_iterator	end (const tree_iterator_base< T > &i)
const_sibling_iterator	begin (const tree_iterator_base< T > &i) const
const_sibling_iterator	end (const tree_iterator_base< T > &i) const
subtree_iterator	begin_subtree (const tree_iterator_base< T > &i)
subtree_iterator	end_subtree (const tree_iterator_base< T > &i)
const_subtree_iterator	begin_subtree (const const_tree_iterator_base< T > &i) const
const_subtree_iterator	begin_subtree (const tree_iterator_base< T > &i) const
const_subtree_iterator	end_subtree (const const_tree_iterator_base< T > &i) const
const_subtree_iterator	end_subtree (const tree_iterator_base< T > &i) const
leaf_iterator	begin_leaf ()
const_leaf_iterator	begin_leaf () const
leaf_iterator	end_leaf ()
const_leaf_iterator	end_leaf () const
size_t	size () const
size_t	size (const tree_iterator_base< T > &i) const
bool	empty () const
bool	empty (const tree_iterator_base< T > &x) const
void	clear ()
template<typename iter >
iter	erase (iter i)
template<typename iter >
void	move (iter a, iter b)
template<typename iter >
iter	insert (iter i, const T &x)
template<typename iter >
iter	push_back_child (iter i, const T &v)
template<typename iter >
iter	push_front_child (iter i, const T &v)
void	sort_children (tree_iterator_base< T > &i)
template<typename CMP >
void	sort_children (tree_iterator_base< T > &i, CMP cmp)
void	sort ()
template<typename CMP >
void	sort (CMP cmp)
template<typename Predicate >
range_pair	equal_range (const tree_iterator_base< T > &i, Predicate predicate) const
iterator	parent (const tree_iterator_base< T > &i) const
template<typename iter , typename Predicate >
iterator	find_in_path (iter pfirst, iter plast, Predicate predicate)
size_t	depth (const tree_iterator_base< T > &i) const
size_t	depth (const const_tree_iterator_base< T > &i) const
size_t	depth (const reverse_iterator &i) const
size_t	depth (const const_reverse_iterator &i) const

Detailed Description

template<class T>
class matador::tree< T >

A STL like tree class.

The tree class provides a container with an STL like interface. One can store data in it a like tree. There are several iterator types, find methods and modify (insert, push_back/front) methods. Access is provide via iterators.

Member Typedef Documentation

const_iterator

template<class T >

typedef const_tree_iterator<T> matador::tree< T >::const_iterator

Shortcut to default const iterator type

const_leaf_iterator

template<class T >

typedef const_tree_leaf_iterator<T> matador::tree< T >::const_leaf_iterator

Shortcut to const leaf iterator type

const_pointer

template<class T >

typedef const T* matador::tree< T >::const_pointer

Shortcut to value const pointer type

const_reference

template<class T >

typedef const T& matador::tree< T >::const_reference

Shortcut to value const reference type

const_reverse_iterator

template<class T >

typedef std::reverse_iterator<const_iterator> matador::tree< T >::const_reverse_iterator

Shortcut to const reverse iterator type

const_sibling_iterator

template<class T >

typedef const_tree_sibling_iterator<T> matador::tree< T >::const_sibling_iterator

Shortcut to const sibling iterator type

const_subtree_iterator

template<class T >

typedef const_tree_subtree_iterator<T> matador::tree< T >::const_subtree_iterator

Shortcut to const subtree iterator type

iterator

template<class T >

typedef tree_iterator<T> matador::tree< T >::iterator

Shortcut to default iterator type

leaf_iterator

template<class T >

typedef tree_leaf_iterator<T> matador::tree< T >::leaf_iterator

Shortcut to leaf iterator type

pointer

template<class T >

typedef T* matador::tree< T >::pointer

Shortcut to value pointer type

range_pair

template<class T >

typedef std::pair<sibling_iterator, sibling_iterator> matador::tree< T >::range_pair

Shortcut to a range pair type

reference

template<class T >

typedef T& matador::tree< T >::reference

Shortcut to value reference type

reverse_iterator

template<class T >

typedef std::reverse_iterator<iterator> matador::tree< T >::reverse_iterator

Shortcut to reverse iterator type

sibling_iterator

template<class T >

typedef tree_sibling_iterator<T> matador::tree< T >::sibling_iterator

Shortcut to sibling iterator type

subtree_iterator

template<class T >

typedef tree_subtree_iterator<T> matador::tree< T >::subtree_iterator

Shortcut to subtree iterator type

t_node

template<class T >

typedef t_tree_node<T> matador::tree< T >::t_node

Shortcut to node type

value_type

template<class T >

typedef T matador::tree< T >::value_type

Shortcut to value type

Constructor & Destructor Documentation

tree()

template<class T >

matador::tree< T >::tree

(

)

Creates an empty tree of type T.

~tree()

template<class T >

matador::tree< T >::~tree

(

)

Cleans up the tree but not the stored data.

Member Function Documentation

begin() [1/4]

template<class T >

iterator matador::tree< T >::begin ( )

inline

Returns the begin iterator of the tree

Returns

begin iterator of the tree

begin() [2/4]

template<class T >

const_iterator matador::tree< T >::begin ( ) const

inline

Returns the constant begin iterator of the tree

Returns

constant begin iterator of the tree

begin() [3/4]

template<class T >

sibling_iterator matador::tree< T >::begin ( const tree_iterator_base< T > &  i )

inline

Returns the sibling begin iterator for a node (iterator)

Parameters

i

Returns

sibling begin iterator

begin() [4/4]

template<class T >

const_sibling_iterator matador::tree< T >::begin ( const tree_iterator_base< T > &  i ) const

inline

Returns the constant sibling begin iterator for a node (iterator)

Parameters

i

Returns

constant sibling begin iterator

begin_leaf() [1/2]

template<class T >

leaf_iterator matador::tree< T >::begin_leaf ( )

inline

Return the first leaf node as iterator

Returns

leaf begin iterator

begin_leaf() [2/2]

template<class T >

const_leaf_iterator matador::tree< T >::begin_leaf ( ) const

inline

Return the first leaf node as constant iterator

Returns

constant leaf begin iterator

begin_subtree() [1/3]

template<class T >

const_subtree_iterator matador::tree< T >::begin_subtree ( const const_tree_iterator_base< T > &  i ) const

inline

Returns the constant subtree begin iterator for a node (iterator)

Parameters

i

Returns

constant subtree begin iterator

begin_subtree() [2/3]

template<class T >

subtree_iterator matador::tree< T >::begin_subtree ( const tree_iterator_base< T > &  i )

inline

Returns the subtree begin iterator for a node (iterator)

Parameters

i

Returns

subtree begin iterator

begin_subtree() [3/3]

template<class T >

const_subtree_iterator matador::tree< T >::begin_subtree ( const tree_iterator_base< T > &  i ) const

inline

Returns the constant subtree begin iterator for a node (iterator)

Parameters

i

Returns

constant subtree begin iterator

clear()

template<class T >

void matador::tree< T >::clear

(

)

Empties the tree

depth() [1/4]

template<class T >

size_t matador::tree< T >::depth ( const const_reverse_iterator &  i ) const

inline

Returns the depth of the given node constant reverse iterator i

Parameters

i	constant reverse iterator for which the depth is returned

Returns

depth of iterator (root is 0 (zero))

depth() [2/4]

template<class T >

size_t matador::tree< T >::depth

(

const const_tree_iterator_base< T > &

i

)

const

Returns the depth of the given node constant iterator i

Parameters

i	constant iterator for which the depth is returned

Returns

depth of iterator (root is 0 (zero))

depth() [3/4]

template<class T >

size_t matador::tree< T >::depth ( const reverse_iterator &  i ) const

inline

Returns the depth of the given node reverse iterator i

Parameters

i	reverse iterator for which the depth is returned

Returns

depth of iterator (root is 0 (zero))

depth() [4/4]

template<class T >

size_t matador::tree< T >::depth

(

const tree_iterator_base< T > &

i

)

const

Returns the depth of the given node iterator i

Parameters

i	iterator for which the depth is returned

Returns

depth of iterator (root is 0 (zero))

empty() [1/2]

template<class T >

bool matador::tree< T >::empty ( ) const

inline

Returns wether the tree is empty or not

Returns

wether the tree is empty

empty() [2/2]

template<class T >

bool matador::tree< T >::empty ( const tree_iterator_base< T > &  x ) const

inline

Returns if iterator has children

Parameters

x	iterator used for empty check

Returns

wether the node has children

end() [1/4]

template<class T >

iterator matador::tree< T >::end ( )

inline

Returns the end iterator of the tree

Returns

end iterator of the tree

end() [2/4]

template<class T >

const_iterator matador::tree< T >::end ( ) const

inline

Returns the constant end iterator of the tree

Returns

constant end iterator of the tree

end() [3/4]

template<class T >

sibling_iterator matador::tree< T >::end ( const tree_iterator_base< T > &  i )

inline

Returns the sibling end iterator for a node (iterator)

Parameters

i

Returns

sibling end iterator

end() [4/4]

template<class T >

const_sibling_iterator matador::tree< T >::end ( const tree_iterator_base< T > &  i ) const

inline

Returns the constant sibling end iterator for a node (iterator)

Parameters

i

Returns

constant sibling end iterator

end_leaf() [1/2]

template<class T >

leaf_iterator matador::tree< T >::end_leaf ( )

inline

Return the end leaf node as iterator

Returns

leaf end iterator

end_leaf() [2/2]

template<class T >

const_leaf_iterator matador::tree< T >::end_leaf ( ) const

inline

Return the first leaf node as constant iterator

Returns

constant leaf begin iterator

end_subtree() [1/3]

template<class T >

const_subtree_iterator matador::tree< T >::end_subtree ( const const_tree_iterator_base< T > &  i ) const

inline

Returns the constant subtree end iterator for a node (iterator)

Parameters

i

Returns

constant subtree end iterator

end_subtree() [2/3]

template<class T >

subtree_iterator matador::tree< T >::end_subtree ( const tree_iterator_base< T > &  i )

inline

Returns the subtree end iterator for a node (iterator)

Parameters

i

Returns

subtree end iterator

end_subtree() [3/3]

template<class T >

const_subtree_iterator matador::tree< T >::end_subtree ( const tree_iterator_base< T > &  i ) const

inline

Returns the constant subtree end iterator for a node (iterator)

Parameters

i

Returns

constant subtree end iterator

equal_range()

template<class T >

template<typename Predicate >

range_pair matador::tree< T >::equal_range	(	const tree_iterator_base< T > &	i,
		Predicate	predicate
	)		const

Returns two iterators representing a range of children nodes which equals a given predicate (e.g. same name) Note: children must be sorted, otherwise a range of all nodes equaling the predicate can't be guaranted!

Parameters

i	parent iterator of future range children
predicate	which all range children must equal

Returns

range of children (as range_pair, first and last iterator)

erase()

template<class T >

template<typename iter >

iter matador::tree< T >::erase

(

iter

i

)

Erase iterator i from tree include the complete subtree

Parameters

i	the iterator to erase

Returns

the next valid node as iterator

find_in_path()

template<class T >

template<typename iter , typename Predicate >

iterator matador::tree< T >::find_in_path	(	iter	pfirst,
		iter	plast,
		Predicate	predicate
	)

Search a node within a given path. Path comes as two iterators pfirst and plast over which can be iterated.

Parameters

pfirst	the first iterator of path
plast	the last iterator of path
predicate	the search rule for the node to find

Returns

the first iterator which equals the predicate

insert()

template<class T >

template<typename iter >

iter matador::tree< T >::insert	(	iter	i,
		const T &	x
	)

Insert as previous sibling of i and returns new node iterator

Parameters

i	next sibling of new node
x	new node of type T

Returns

new iterator of node x

move()

template<class T >

template<typename iter >

void matador::tree< T >::move	(	iter	a,
		iter	b
	)

Moves subtree represented by iterator a and insert before iterator b

Parameters

a	iterator to move
b	iterator where insertion takes place (before)

parent()

template<class T >

iterator matador::tree< T >::parent

(

const tree_iterator_base< T > &

i

)

const

Returns the parent node of iterator. if iterator hasn't a parent node end() is returned

Parameters

i	iterator to get the parent from

Returns

the parent iterator

push_back_child()

template<class T >

template<typename iter >

iter matador::tree< T >::push_back_child	(	iter	i,
		const T &	v
	)

Insert as last child of i and returns new node iterator

Parameters

i	parent children of new node of type T
v	new node of type T

Returns

new iterator of node x

push_front_child()

template<class T >

template<typename iter >

iter matador::tree< T >::push_front_child	(	iter	i,
		const T &	v
	)

Insert as first child of i and returns new node iterator

Parameters

i	parent children of new node of type T
v	new node of type T

Returns

new iterator of node x

rbegin() [1/2]

template<class T >

reverse_iterator matador::tree< T >::rbegin ( )

inline

Returns the reverse begin iterator of the tree

Returns

reverse begin iterator of the tree

rbegin() [2/2]

template<class T >

const_reverse_iterator matador::tree< T >::rbegin ( ) const

inline

Returns the constant reverse begin iterator of the tree

Returns

constant reverse begin iterator of the tree

rend() [1/2]

template<class T >

reverse_iterator matador::tree< T >::rend ( )

inline

Returns the reverse end iterator of the tree

Returns

reverse end iterator of the tree

rend() [2/2]

template<class T >

const_reverse_iterator matador::tree< T >::rend ( ) const

inline

Returns the constant reverse end iterator of the tree

Returns

constant reverse end iterator of the tree

size() [1/2]

template<class T >

size_t matador::tree< T >::size ( ) const

inline

Returns the current size of the tree (takes linear amount of time)

Returns

size of tree

size() [2/2]

template<class T >

size_t matador::tree< T >::size ( const tree_iterator_base< T > &  i ) const

inline

Returns the current amount of children of the given node (takes linear amount of time)

Returns

size of children under node

sort() [1/2]

template<class T >

void matador::tree< T >::sort

(

)

Sorts the complete tree with the standard compare method. But the sorting is done for all siblings (children of a node) discretely

sort() [2/2]

template<class T >

template<typename CMP >

void matador::tree< T >::sort

(

CMP

cmp

)

Sorts the complete tree with the given compare method. But the sorting is done for all siblings (children of a node) discretely

Parameters

cmp	compare operator

sort_children() [1/2]

template<class T >

void matador::tree< T >::sort_children

(

tree_iterator_base< T > &

i

)

Sort children of iterator node i with standard compare operator

Parameters

i	parent node of children to sort

sort_children() [2/2]

template<class T >

template<typename CMP >

void matador::tree< T >::sort_children	(	tree_iterator_base< T > &	i,
		CMP	cmp
	)

Sort children of iterator node i with compare operator of type CMP

Parameters

i	parent node of children to sort
cmp	compare operator

---

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

• matador/utils/tree.hpp