tree< T, tree_node_allocator > Class Template Reference

Classes
class	breadth_first_queued_iterator
	Breadth-first iterator, using a queue. More...
class	fixed_depth_iterator
	Iterator which traverses only the nodes at a given depth from the root. More...
class	iterator_base
	Base class for iterators, only pointers stored, no traversal logic. More...
class	iterator_base_less
	Comparator class for iterators (compares pointer values; why doesn't this work automatically?) More...
class	leaf_iterator
	Iterator which traverses only the leaves. More...
class	post_order_iterator
	Depth-first iterator, first accessing the children, then the node itself. More...
class	pre_order_iterator
	Depth-first iterator, first accessing the node, then its children. More...
class	sibling_iterator
	Iterator which traverses only the nodes which are siblings of each other. More...

Public Types
typedef T	value_type
	Value of the data stored at a node.
typedef pre_order_iterator	iterator
	The default iterator types throughout the tree class.
typedef breadth_first_queued_iterator	breadth_first_iterator

Public Member Functions
	tree (const T &)
	tree (const iterator_base &)
	tree (const tree< T, tree_node_allocator > &)
tree< T, tree_node_allocator > &	operator= (const tree< T, tree_node_allocator > &)
pre_order_iterator	begin () const
	Return iterator to the beginning of the tree.
pre_order_iterator	end () const
	Return iterator to the end of the tree.
post_order_iterator	begin_post () const
	Return post-order iterator to the beginning of the tree.
post_order_iterator	end_post () const
	Return post-order end iterator of the tree.
fixed_depth_iterator	begin_fixed (const iterator_base &, unsigned int) const
	Return fixed-depth iterator to the first node at a given depth from the given iterator.
fixed_depth_iterator	end_fixed (const iterator_base &, unsigned int) const
	Return fixed-depth end iterator.
breadth_first_queued_iterator	begin_breadth_first () const
	Return breadth-first iterator to the first node at a given depth.
breadth_first_queued_iterator	end_breadth_first () const
	Return breadth-first end iterator.
sibling_iterator	begin (const iterator_base &) const
	Return sibling iterator to the first child of given node.
sibling_iterator	end (const iterator_base &) const
	Return sibling end iterator for children of given node.
leaf_iterator	begin_leaf () const
	Return leaf iterator to the first leaf of the tree.
leaf_iterator	end_leaf () const
	Return leaf end iterator for entire tree.
leaf_iterator	begin_leaf (const iterator_base &top) const
	Return leaf iterator to the first leaf of the subtree at the given node.
leaf_iterator	end_leaf (const iterator_base &top) const
	Return leaf end iterator for the subtree at the given node.
template<typename iter >
iter	previous_sibling (iter) const
	Return iterator to the previous sibling of a node.
template<typename iter >
iter	next_sibling (iter) const
	Return iterator to the next sibling of a node.
template<typename iter >
iter	next_at_same_depth (iter) const
	Return iterator to the next node at a given depth.
void	clear ()
	Erase all nodes of the tree.
template<typename iter >
iter	erase (iter)
	Erase element at position pointed to by iterator, return incremented iterator.
void	erase_children (const iterator_base &)
	Erase all children of the node pointed to by iterator.
template<typename iter >
iter	append_child (iter position)
	Insert empty node as last/first child of node pointed to by position.
template<typename iter >
iter	prepend_child (iter position)
template<typename iter >
iter	append_child (iter position, const T &x)
	Insert node as last/first child of node pointed to by position.
template<typename iter >
iter	prepend_child (iter position, const T &x)
template<typename iter >
iter	append_child (iter position, iter other_position)
	Append the node (plus its children) at other_position as last/first child of position.
template<typename iter >
iter	prepend_child (iter position, iter other_position)
template<typename iter >
iter	append_children (iter position, sibling_iterator from, sibling_iterator to)
	Append the nodes in the from-to range (plus their children) as last/first children of position.
template<typename iter >
iter	prepend_children (iter position, sibling_iterator from, sibling_iterator to)
pre_order_iterator	set_head (const T &x)
	Short-hand to insert topmost node in otherwise empty tree.
template<typename iter >
iter	insert (iter position, const T &x)
	Insert node as previous sibling of node pointed to by position.
sibling_iterator	insert (sibling_iterator position, const T &x)
	Specialisation of previous member.
template<typename iter >
iter	insert_subtree (iter position, const iterator_base &subtree)
	Insert node (with children) pointed to by subtree as previous sibling of node pointed to by position.
template<typename iter >
iter	insert_after (iter position, const T &x)
	Insert node as next sibling of node pointed to by position.
template<typename iter >
iter	insert_subtree_after (iter position, const iterator_base &subtree)
	Insert node (with children) pointed to by subtree as next sibling of node pointed to by position.
template<typename iter >
iter	replace (iter position, const T &x)
	Replace node at 'position' with other node (keeping same children); 'position' becomes invalid.
template<typename iter >
iter	replace (iter position, const iterator_base &from)
	Replace node at 'position' with subtree starting at 'from' (do not erase subtree at 'from'); see above.
sibling_iterator	replace (sibling_iterator orig_begin, sibling_iterator orig_end, sibling_iterator new_begin, sibling_iterator new_end)
	Replace string of siblings (plus their children) with copy of a new string (with children); see above.
template<typename iter >
iter	flatten (iter position)
	Move all children of node at 'position' to be siblings, returns position.
template<typename iter >
iter	reparent (iter position, sibling_iterator begin, sibling_iterator end)
	Move nodes in range to be children of 'position'.
template<typename iter >
iter	reparent (iter position, iter from)
	Move all child nodes of 'from' to be children of 'position'.
template<typename iter >
iter	wrap (iter position, const T &x)
	Replace node with a new node, making the old node a child of the new node.
template<typename iter >
iter	move_after (iter target, iter source)
	Move 'source' node (plus its children) to become the next sibling of 'target'.
template<typename iter >
iter	move_before (iter target, iter source)
	Move 'source' node (plus its children) to become the previous sibling of 'target'.
sibling_iterator	move_before (sibling_iterator target, sibling_iterator source)
template<typename iter >
iter	move_ontop (iter target, iter source)
	Move 'source' node (plus its children) to become the node at 'target' (erasing the node at 'target').
void	merge (sibling_iterator, sibling_iterator, sibling_iterator, sibling_iterator, bool duplicate_leaves=false)
	Merge with other tree, creating new branches and leaves only if they are not already present.
void	sort (sibling_iterator from, sibling_iterator to, bool deep=false)
	Sort (std::sort only moves values of nodes, this one moves children as well).
template<class StrictWeakOrdering >
void	sort (sibling_iterator from, sibling_iterator to, StrictWeakOrdering comp, bool deep=false)
template<typename iter >
bool	equal (const iter &one, const iter &two, const iter &three) const
	Compare two ranges of nodes (compares nodes as well as tree structure).
template<typename iter , class BinaryPredicate >
bool	equal (const iter &one, const iter &two, const iter &three, BinaryPredicate) const
template<typename iter >
bool	equal_subtree (const iter &one, const iter &two) const
template<typename iter , class BinaryPredicate >
bool	equal_subtree (const iter &one, const iter &two, BinaryPredicate) const
tree	subtree (sibling_iterator from, sibling_iterator to) const
	Extract a new tree formed by the range of siblings plus all their children.
void	subtree (tree &, sibling_iterator from, sibling_iterator to) const
void	swap (sibling_iterator it)
	Exchange the node (plus subtree) with its sibling node (do nothing if no sibling present).
void	swap (iterator, iterator)
	Exchange two nodes (plus subtrees)
size_t	size () const
	Count the total number of nodes.
size_t	size (const iterator_base &) const
	Count the total number of nodes below the indicated node (plus one).
bool	empty () const
	Check if tree is empty.
int	max_depth () const
	Determine the maximal depth of the tree. An empty tree has max_depth=-1.
int	max_depth (const iterator_base &) const
	Determine the maximal depth of the tree with top node at the given position.
unsigned int	number_of_siblings (const iterator_base &) const
	Count the number of siblings (left and right) of node at iterator. Total nodes at this level is +1.
bool	is_in_subtree (const iterator_base &position, const iterator_base &begin, const iterator_base &end) const
	Determine whether node at position is in the subtrees with root in the range.
bool	is_valid (const iterator_base &) const
	Determine whether the iterator is an 'end' iterator and thus not actually pointing to a node.
iterator	lowest_common_ancestor (const iterator_base &, const iterator_base &) const
unsigned int	index (sibling_iterator it) const
	Determine the index of a node in the range of siblings to which it belongs.
sibling_iterator	sibling (const iterator_base &position, unsigned int)
	Return iterator to the sibling indicated by index.
void	debug_verify_consistency () const

Static Public Member Functions
template<typename iter >
static iter	parent (iter)
	Return iterator to the parent of a node.
static int	depth (const iterator_base &)
	Compute the depth to the root or to a fixed other iterator.
static int	depth (const iterator_base &, const iterator_base &)
static unsigned int	number_of_children (const iterator_base &)
	Count the number of children of node at position.
static sibling_iterator	child (const iterator_base &position, unsigned int)
	Inverse of 'index': return the n-th child of the node at position.

Public Attributes
tree_node *	head
tree_node *	feet

Protected Types
typedef tree_node_< T >	tree_node

Member Function Documentation

template<class T , class tree_node_allocator >

void tree< T, tree_node_allocator >::debug_verify_consistency

(

)

const

For debugging only: verify internal consistency by inspecting all pointers in the tree (which will also trigger a valgrind error in case something got corrupted).

template<class T , class tree_node_allocator >

tree< T, tree_node_allocator >::iterator tree< T, tree_node_allocator >::lowest_common_ancestor	(	const iterator_base &	one,
		const iterator_base &	two
	)		const

Find the lowest common ancestor of two nodes, that is, the deepest node such that both nodes are descendants of it.

---

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

• src/tree.hh