Classes | Public Types | Public Member Functions | Static Public Member Functions | Public Attributes | Protected Types | Private Member Functions | Private Attributes

tree< T, tree_node_allocator > Class Template Reference

#include <tree.hh>

Inheritance diagram for tree< T, tree_node_allocator >:
Collaboration diagram for tree< T, tree_node_allocator >:

List of all members.

Classes

class  breadth_first_queued_iterator
 Breadth-first iterator, using a queue. More...
class  compare_nodes
 Comparator class for two nodes of a tree (used for sorting and searching). 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
breadth_first_queued_iterator 
breadth_first_iterator
typedef pre_order_iterator iterator
 The default iterator types throughout the tree class.
typedef T value_type
 Value of the data stored at a node.

Public Member Functions

 tree ()
 tree (const T &)
 tree (const tree< T, tree_node_allocator > &)
 tree (const iterator_base &)
 ~tree ()
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 append_child (iter position, const T &x)
 Insert node as last/first child of node pointed to by position.
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 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.
MY_FORCE_INLINE pre_order_iterator begin () const
 Return iterator to the beginning of the tree.
sibling_iterator begin (const iterator_base &) const
 Return sibling iterator to the first child of given node.
breadth_first_queued_iterator begin_breadth_first () const
 Return breadth-first iterator to the first node at a given depth.
fixed_depth_iterator begin_fixed (const iterator_base &, unsigned int) const
 Return fixed-depth iterator to the first node at a given depth.
leaf_iterator begin_leaf () const
 Return leaf iterator to the first leaf of the tree.
post_order_iterator begin_post () const
 Return post-order iterator to the beginning of the tree.
sibling_iterator child (const iterator_base &position, unsigned int) const
 Inverse of 'index': return the n-th child of the node at position.
void clear ()
 Erase all nodes of the tree.
int depth (const iterator_base &) const
 Compute the depth to the root.
bool empty () const
 Check if tree is empty.
sibling_iterator end (const iterator_base &) const
 Return sibling iterator to the end of the children of a given node.
MY_FORCE_INLINE pre_order_iterator end () const
 Return iterator to the end of the tree.
breadth_first_queued_iterator end_breadth_first () const
 Return breadth-first iterator to end of the nodes at given depth.
fixed_depth_iterator end_fixed (const iterator_base &, unsigned int) const
 Return fixed-depth iterator to end of the nodes at given depth.
leaf_iterator end_leaf () const
 Return leaf iterator to the last leaf of the tree.
post_order_iterator end_post () const
 Return post-order iterator to the end of the tree.
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 , class BinaryPredicate >
bool equal_subtree (const iter &one, const iter &two, BinaryPredicate) const
template<typename iter >
bool equal_subtree (const iter &one, const iter &two) const
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 flatten (iter position)
 Move all children of node at 'position' to be siblings, returns position.
unsigned int index (sibling_iterator it) const
 Determine the index of a node in the range of siblings to which it belongs.
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_after (iter position, const T &x)
 Insert node as next sibling of node pointed to by position.
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.
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.
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.
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').
template<typename iter >
iter next_at_same_depth (iter) const
 Return iterator to the next node at a given depth.
template<typename iter >
iter next_sibling (iter) const
 Return iterator to the next sibling of a node.
unsigned int number_of_siblings (const iterator_base &) const
 Count the number of 'next' siblings of node at iterator.
void operator= (const tree< T, tree_node_allocator > &)
template<typename iter >
iter prepend_child (iter position)
template<typename iter >
iter prepend_child (iter position, const T &x)
template<typename iter >
iter prepend_child (iter position, iter other_position)
template<typename iter >
iter prepend_children (iter position, sibling_iterator from, sibling_iterator to)
template<typename iter >
iter previous_sibling (iter) const
 Return iterator to the previous sibling of a node.
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 replace (iter position, const T &x)
 Replace node at 'position' with other node (keeping same children); 'position' becomes invalid.
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 replace (iter position, const iterator_base &from)
 Replace node at 'position' with subtree starting at 'from' (do not erase subtree at 'from'); see above.
pre_order_iterator set_head (const T &x)
 Short-hand to insert topmost node in otherwise empty tree.
int size () const
 Count the total number of nodes.
template<class StrictWeakOrdering >
void sort (sibling_iterator from, sibling_iterator to, StrictWeakOrdering comp, bool deep=false)
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).
void subtree (tree &, sibling_iterator from, sibling_iterator to) 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 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).
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.

Static Public Member Functions

static unsigned int number_of_children (const iterator_base &)
 Count the number of children of node at position.
template<typename iter >
static iter parent (iter)
 Return iterator to the parent of a node.

Public Attributes

tree_nodefeet
tree_nodehead

Protected Types

typedef tree_node_< T > tree_node

Private Member Functions

void copy_ (const tree< T, tree_node_allocator > &other)
void head_initialise_ ()

Private Attributes

tree_node_allocator alloc_

Detailed Description

template<class T, class tree_node_allocator = std::allocator<tree_node_<T> >>
class tree< T, tree_node_allocator >

Definition at line 126 of file tree.hh.


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

Generated on Sat Aug 7 2010 15:43:29 for VooDoo cIRCle by doxygen 1.7.1

Get VooDoo cIRCle at SourceForge.net. Fast, secure and Free Open Source software downloads