tree< T, tree_node_allocator > Class Template Reference

#include <tree.hh>

List of all members.

Classes

class  breadth_first_queued_iterator
 Breadth-first iterator, using a queue. More...
class  children_iterator
 Iterator which traverses only the nodes which are siblings of each other. 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.
typedef T value_type
 Value of the data stored at a node.

Public Member Functions

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_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)
 Insert empty node as last/first child of node pointed to by 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.
sibling_iterator begin (const iterator_base &) const
 Return sibling iterator to the first child of given node.
pre_order_iterator begin () const
 Return iterator to the beginning of the tree.
breadth_first_queued_iterator begin_breadth_first () const
 Return breadth-first iterator to the first node at a given depth.
breadth_first_queued_iterator begin_breadth_first_iterator (const iterator_base &) const
 Return breadth-first iterator based on a iterator.
children_iterator begin_children_iterator (const iterator_base &) const
 Return children iterator to the first child of given node.
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.
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 begin_leaf () const
 Return leaf iterator to the first leaf of the tree.
leaf_iterator begin_leaf_iterator (const iterator_base &top) const
 Return leaf iterator to the first leaf of the subtree at the given node.
post_order_iterator begin_post () const
 Return post-order iterator to the beginning of the tree.
post_order_iterator begin_post_order_iterator (const iterator_base &) const
 Return post-order iterator to the beginning of the tree.
pre_order_iterator begin_pre_order_iterator (const iterator_base &) const
 Return iterator to the beginning of the tree.
void clear ()
 Erase all nodes of the tree.
void clear ()
 Erase all nodes of the tree.
void debug_verify_consistency () const
bool empty () const
 Check if tree is empty.
bool empty () const
 Check if tree is empty.
sibling_iterator end (const iterator_base &) const
 Return sibling end iterator for children of given node.
pre_order_iterator end () const
 Return iterator to the end of the tree.
breadth_first_queued_iterator end_breadth_first () const
 Return breadth-first end iterator.
breadth_first_queued_iterator end_breadth_first_iterator (const iterator_base &) const
 Return breadth-first end iterator.
children_iterator end_children_iterator (const iterator_base &) const
 Return children end iterator for children of given node.
fixed_depth_iterator end_fixed (const iterator_base &, unsigned int) const
 Return fixed-depth end iterator.
leaf_iterator end_leaf (const iterator_base &top) const
 Return leaf end iterator for the subtree at the given node.
leaf_iterator end_leaf () const
 Return leaf end iterator for entire tree.
leaf_iterator end_leaf_iterator (const iterator_base &top) const
 Return leaf end iterator for the subtree at the given node.
post_order_iterator end_post () const
 Return post-order end iterator of the tree.
post_order_iterator end_post_order_iterator (const iterator_base &) const
 Return post-order end iterator of the tree.
pre_order_iterator end_pre_order_iterator (const iterator_base &) const
 Return iterator to the end of the tree.
template<typename iter , class BinaryPredicate >
bool equal (const iter &one, const iter &two, const iter &three, BinaryPredicate) const
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_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.
template<typename iter >
iter erase (iter)
 Erase element at position pointed to by iterator, return incremented iterator.
void erase_branch (const iterator_base &)
 Erase a full branch of the tree, find the parrent from witch the branch started and remove all nodes in it.
void erase_children (const iterator_base &)
 Erase all children of the node pointed to by 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 (children_iterator it) const
 Determine the index of a node in the range of siblings to which it belongs.
unsigned int index (sibling_iterator it) const
 Determine the index of a node in the range of siblings to which it belongs.
sibling_iterator insert (sibling_iterator position, const T &x)
 Specialisation of previous member.
template<typename iter >
iter insert (iter position, const T &x)
 Insert node 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_after (iter position, const T &x)
 Insert node as next sibling of node pointed to by position.
template<typename iter >
iter insert_before (iter position, const T &x)
 Insert node as previous 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.
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.
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.
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
int max_depth (const iterator_base &) const
 Determine the maximal depth of the tree with top node at the given position.
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.
int max_depth () const
 Determine the maximal depth of the tree. An empty tree has max_depth=-1.
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_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_before (iter target, iter source)
 Move 'source' node (plus its children) to become the previous sibling of 'target'.
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 move_ontop_same_branch (iter target, iter source)
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.
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 siblings (left and right) of node at iterator. Total nodes at this level is +1.
tree< T, tree_node_allocator > & operator= (const tree< T, tree_node_allocator > &)
tree< T, tree_node_allocator > & operator= (const tree< T, tree_node_allocator > &)
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_child (iter position, const T &x)
template<typename iter >
iter prepend_child (iter 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 previous_sibling (iter) const
 Return iterator to the previous sibling of a node.
template<typename iter >
iter reparent (iter position, iter from)
 Move all child nodes of 'from' to be children of 'position'.
template<typename iter >
iter reparent (iter position, sibling_iterator begin, sibling_iterator end)
 Move nodes in range to be children of 'position'.
pre_order_iterator reparent_root (const T &x)
 set X as the new head of the tree, the old head will be a child of new head.
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.
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.
template<typename iter >
iter replace (iter position, const T &x)
 Replace node at 'position' with other node (keeping same children); 'position' becomes invalid.
pre_order_iterator root () const
 Return iterator to the beginning of the tree.
pre_order_iterator set_head (const T &x)
 Short-hand to insert topmost node in otherwise empty tree.
pre_order_iterator set_root (const T &x)
 Short-hand to insert_before topmost node in otherwise empty tree.
sibling_iterator sibling (const iterator_base &position, unsigned int)
 Return iterator to the sibling indicated by index.
size_t size (const iterator_base &) const
 Count the total number of nodes below the indicated node (plus one).
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).
size_t 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 (iterator, iterator)
 Exchange two nodes (plus subtrees).
void swap (sibling_iterator it)
 Exchange the node (plus subtree) with its sibling node (do nothing if no sibling present).
 tree (const tree< T, tree_node_allocator > &)
 tree (const T &)
 tree ()
 tree (const tree< T, tree_node_allocator > &)
 tree (const iterator_base &)
 tree (const T &)
 tree ()
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.
 ~tree ()
 ~tree ()

Static Public Member Functions

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

Public Attributes

tree_node * feet
tree_node * head
bool need_layout
bool ready_from_draw

Protected Types

typedef tree_node_< T > tree_node
typedef tree_node_< T > tree_node

Private Member Functions

void copy_ (const tree< T, tree_node_allocator > &other)
void copy_ (const tree< T, tree_node_allocator > &other)
void head_initialise_ ()
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 71 of file tree.hh.

Member Typedef Documentation

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

Definition at line 185 of file tree.hh.

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

The default iterator types throughout the tree class.

Definition at line 184 of file tree.hh.

template<class T, class tree_node_allocator = std::allocator<tree_node_<T> >>
typedef tree_node_<T> tree< T, tree_node_allocator >::tree_node [protected]

Definition at line 90 of file tree_new.hh.

template<class T, class tree_node_allocator = std::allocator<tree_node_<T> >>
typedef tree_node_<T> tree< T, tree_node_allocator >::tree_node [protected]

Definition at line 73 of file tree.hh.

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

Value of the data stored at a node.

Definition at line 93 of file tree_new.hh.

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

Value of the data stored at a node.

Definition at line 76 of file tree.hh.

Constructor & Destructor Documentation

template<class T , class tree_node_allocator >
tree< T, tree_node_allocator >::tree (  )  [inline]

Definition at line 508 of file tree.hh.

template<class T, class tree_node_allocator >
tree< T, tree_node_allocator >::tree ( const T &  x  )  [inline]

Definition at line 514 of file tree.hh.

template<class T, class tree_node_allocator >
tree< T, tree_node_allocator >::tree ( const iterator_base &  other  )  [inline]

Definition at line 521 of file tree.hh.

template<class T, class tree_node_allocator>
tree< T, tree_node_allocator >::tree ( const tree< T, tree_node_allocator > &  other  )  [inline]

Definition at line 568 of file tree.hh.

template<class T , class tree_node_allocator >
tree< T, tree_node_allocator >::~tree (  )  [inline]

Definition at line 529 of file tree.hh.

template<class T, class tree_node_allocator = std::allocator<tree_node_<T> >>
tree< T, tree_node_allocator >::tree (  ) 
template<class T, class tree_node_allocator = std::allocator<tree_node_<T> >>
tree< T, tree_node_allocator >::tree ( const T &   ) 
template<class T, class tree_node_allocator = std::allocator<tree_node_<T> >>
tree< T, tree_node_allocator >::tree ( const tree< T, tree_node_allocator > &   ) 
template<class T, class tree_node_allocator = std::allocator<tree_node_<T> >>
tree< T, tree_node_allocator >::~tree (  ) 

Member Function Documentation

template<class T, class tree_node_allocator = std::allocator<tree_node_<T> >>
template<typename iter >
iter tree< T, tree_node_allocator >::append_child ( iter  position,
const T &  x 
) [inline]

Insert node as last/first child of node pointed to by position.

template<class T, class tree_node_allocator >
template<class iter >
iter tree< T, tree_node_allocator >::append_child ( iter  position,
iter  other_position 
) [inline]

Append the node (plus its children) at other_position as last/first child of position.

Definition at line 983 of file tree.hh.

template<class T, class tree_node_allocator >
template<class iter >
iter tree< T, tree_node_allocator >::append_child ( iter  position,
const T &  x 
) [inline]

Insert node as last/first child of node pointed to by position.

Definition at line 925 of file tree.hh.

template<class T , class tree_node_allocator >
template<typename iter >
iter tree< T, tree_node_allocator >::append_child ( iter  position  )  [inline]

Insert empty node as last/first child of node pointed to by position.

Definition at line 871 of file tree.hh.

template<class T , class tree_node_allocator >
template<class iter >
iter tree< T, tree_node_allocator >::append_children ( iter  position,
sibling_iterator  from,
sibling_iterator  to 
) [inline]

Append the nodes in the from-to range (plus their children) as last/first children of position.

Definition at line 1007 of file tree.hh.

template<class T , class tree_node_allocator >
tree< T, tree_node_allocator >::sibling_iterator tree< T, tree_node_allocator >::begin ( const iterator_base &  pos  )  const [inline]

Return sibling iterator to the first child of given node.

Definition at line 747 of file tree.hh.

template<class T , class tree_node_allocator >
tree< T, tree_node_allocator >::pre_order_iterator tree< T, tree_node_allocator >::begin (  )  const [inline]

Return iterator to the beginning of the tree.

Definition at line 657 of file tree.hh.

template<class T , class tree_node_allocator >
tree< T, tree_node_allocator >::breadth_first_queued_iterator tree< T, tree_node_allocator >::begin_breadth_first (  )  const [inline]

Return breadth-first iterator to the first node at a given depth.

Definition at line 669 of file tree.hh.

template<class T , class tree_node_allocator >
tree< T, tree_node_allocator >::breadth_first_queued_iterator tree< T, tree_node_allocator >::begin_breadth_first_iterator ( const iterator_base &  pos  )  const [inline]

Return breadth-first iterator based on a iterator.

Definition at line 511 of file tree_new.hh.

template<class T , class tree_node_allocator >
tree< T, tree_node_allocator >::children_iterator tree< T, tree_node_allocator >::begin_children_iterator ( const iterator_base &  pos  )  const [inline]

Return children iterator to the first child of given node.

Definition at line 542 of file tree_new.hh.

template<class T , class tree_node_allocator >
tree< T, tree_node_allocator >::fixed_depth_iterator tree< T, tree_node_allocator >::begin_fixed ( const iterator_base &  pos,
unsigned int  dp 
) const [inline]

Return fixed-depth iterator to the first node at a given depth from the given iterator.

Definition at line 698 of file tree.hh.

template<class T , class tree_node_allocator >
tree< T, tree_node_allocator >::leaf_iterator tree< T, tree_node_allocator >::begin_leaf ( const iterator_base &  top  )  const [inline]

Return leaf iterator to the first leaf of the subtree at the given node.

Definition at line 782 of file tree.hh.

template<class T , class tree_node_allocator >
tree< T, tree_node_allocator >::leaf_iterator tree< T, tree_node_allocator >::begin_leaf (  )  const [inline]

Return leaf iterator to the first leaf of the tree.

Definition at line 765 of file tree.hh.

template<class T , class tree_node_allocator >
tree< T, tree_node_allocator >::leaf_iterator tree< T, tree_node_allocator >::begin_leaf_iterator ( const iterator_base &  top  )  const [inline]

Return leaf iterator to the first leaf of the subtree at the given node.

Definition at line 560 of file tree_new.hh.

template<class T , class tree_node_allocator >
tree< T, tree_node_allocator >::post_order_iterator tree< T, tree_node_allocator >::begin_post (  )  const [inline]

Return post-order iterator to the beginning of the tree.

Definition at line 681 of file tree.hh.

template<class T , class tree_node_allocator >
tree< T, tree_node_allocator >::post_order_iterator tree< T, tree_node_allocator >::begin_post_order_iterator ( const iterator_base &  pos  )  const [inline]

Return post-order iterator to the beginning of the tree.

Definition at line 524 of file tree_new.hh.

template<class T , class tree_node_allocator >
tree< T, tree_node_allocator >::pre_order_iterator tree< T, tree_node_allocator >::begin_pre_order_iterator ( const iterator_base &  pos  )  const [inline]

Return iterator to the beginning of the tree.

Definition at line 497 of file tree_new.hh.

template<class T, class tree_node_allocator = std::allocator<tree_node_<T> >>
static children_iterator tree< T, tree_node_allocator >::child ( const iterator_base &  position,
unsigned  int 
) [static]

Inverse of 'index': return the n-th child of the node at position.

template<class T , class tree_node_allocator >
tree< T, tree_node_allocator >::children_iterator tree< T, tree_node_allocator >::child ( const iterator_base &  position,
unsigned int  num 
) [inline, static]

Inverse of 'index': return the n-th child of the node at position.

Definition at line 2021 of file tree.hh.

template<class T, class tree_node_allocator = std::allocator<tree_node_<T> >>
void tree< T, tree_node_allocator >::clear (  ) 

Erase all nodes of the tree.

template<class T , class tree_node_allocator >
void tree< T, tree_node_allocator >::clear ( void   )  [inline]

Erase all nodes of the tree.

Definition at line 596 of file tree.hh.

template<class T, class tree_node_allocator = std::allocator<tree_node_<T> >>
void tree< T, tree_node_allocator >::copy_ ( const tree< T, tree_node_allocator > &  other  )  [private]
template<class T, class tree_node_allocator>
void tree< T, tree_node_allocator >::copy_ ( const tree< T, tree_node_allocator > &  other  )  [inline, private]

Definition at line 575 of file tree.hh.

template<class T , class tree_node_allocator >
void tree< T, tree_node_allocator >::debug_verify_consistency (  )  const [inline]

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).

Definition at line 2002 of file tree.hh.

template<class T, class tree_node_allocator = std::allocator<tree_node_<T> >>
static int tree< T, tree_node_allocator >::depth ( const iterator_base &  ,
const iterator_base &   
) [static]
template<class T, class tree_node_allocator = std::allocator<tree_node_<T> >>
static int tree< T, tree_node_allocator >::depth ( const iterator_base &   )  [static]

Compute the depth to the root or to a fixed other iterator.

template<class T , class tree_node_allocator >
int tree< T, tree_node_allocator >::depth ( const iterator_base &  it,
const iterator_base &  root 
) [inline, static]

Definition at line 1758 of file tree.hh.

template<class T , class tree_node_allocator >
int tree< T, tree_node_allocator >::depth ( const iterator_base &  it  )  [inline, static]

Compute the depth to the root or to a fixed other iterator.

Definition at line 1745 of file tree.hh.

template<class T, class tree_node_allocator = std::allocator<tree_node_<T> >>
bool tree< T, tree_node_allocator >::empty (  )  const

Check if tree is empty.

template<class T , class tree_node_allocator >
bool tree< T, tree_node_allocator >::empty (  )  const [inline]

Check if tree is empty.

Definition at line 1738 of file tree.hh.

template<class T , class tree_node_allocator >
tree< T, tree_node_allocator >::sibling_iterator tree< T, tree_node_allocator >::end ( const iterator_base &  pos  )  const [inline]

Return sibling end iterator for children of given node.

Definition at line 757 of file tree.hh.

template<class T , class tree_node_allocator >
tree< T, tree_node_allocator >::pre_order_iterator tree< T, tree_node_allocator >::end (  )  const [inline]

Return iterator to the end of the tree.

Definition at line 663 of file tree.hh.

template<class T , class tree_node_allocator >
tree< T, tree_node_allocator >::breadth_first_queued_iterator tree< T, tree_node_allocator >::end_breadth_first (  )  const [inline]

Return breadth-first end iterator.

Definition at line 675 of file tree.hh.

template<class T , class tree_node_allocator >
tree< T, tree_node_allocator >::breadth_first_queued_iterator tree< T, tree_node_allocator >::end_breadth_first_iterator ( const iterator_base &  pos  )  const [inline]

Return breadth-first end iterator.

Definition at line 517 of file tree_new.hh.

template<class T , class tree_node_allocator >
tree< T, tree_node_allocator >::children_iterator tree< T, tree_node_allocator >::end_children_iterator ( const iterator_base &  pos  )  const [inline]

Return children end iterator for children of given node.

Definition at line 552 of file tree_new.hh.

template<class T , class tree_node_allocator >
tree< T, tree_node_allocator >::fixed_depth_iterator tree< T, tree_node_allocator >::end_fixed ( const iterator_base &  pos,
unsigned int  dp 
) const [inline]

Return fixed-depth end iterator.

Definition at line 729 of file tree.hh.

template<class T , class tree_node_allocator >
tree< T, tree_node_allocator >::leaf_iterator tree< T, tree_node_allocator >::end_leaf ( const iterator_base &  top  )  const [inline]

Return leaf end iterator for the subtree at the given node.

Definition at line 791 of file tree.hh.

template<class T , class tree_node_allocator >
tree< T, tree_node_allocator >::leaf_iterator tree< T, tree_node_allocator >::end_leaf (  )  const [inline]

Return leaf end iterator for entire tree.

Definition at line 776 of file tree.hh.

template<class T , class tree_node_allocator >
tree< T, tree_node_allocator >::leaf_iterator tree< T, tree_node_allocator >::end_leaf_iterator ( const iterator_base &  top  )  const [inline]

Return leaf end iterator for the subtree at the given node.

Definition at line 569 of file tree_new.hh.

template<class T , class tree_node_allocator >
tree< T, tree_node_allocator >::post_order_iterator tree< T, tree_node_allocator >::end_post (  )  const [inline]

Return post-order end iterator of the tree.

Definition at line 692 of file tree.hh.

template<class T , class tree_node_allocator >
tree< T, tree_node_allocator >::post_order_iterator tree< T, tree_node_allocator >::end_post_order_iterator ( const iterator_base &  pos  )  const [inline]

Return post-order end iterator of the tree.

Definition at line 535 of file tree_new.hh.

template<class T , class tree_node_allocator >
tree< T, tree_node_allocator >::pre_order_iterator tree< T, tree_node_allocator >::end_pre_order_iterator ( const iterator_base &  pos  )  const [inline]

Return iterator to the end of the tree.

Definition at line 503 of file tree_new.hh.

template<class T , class tree_node_allocator >
template<typename iter , class BinaryPredicate >
bool tree< T, tree_node_allocator >::equal ( const iter &  one,
const iter &  two,
const iter &  three,
BinaryPredicate  fun 
) const [inline]

Definition at line 1667 of file tree.hh.

template<class T , class tree_node_allocator >
template<typename iter >
bool tree< T, tree_node_allocator >::equal ( const iter &  one,
const iter &  two,
const iter &  three 
) const [inline]

Compare two ranges of nodes (compares nodes as well as tree structure).

Definition at line 1651 of file tree.hh.

template<class T , class tree_node_allocator >
template<typename iter , class BinaryPredicate >
bool tree< T, tree_node_allocator >::equal_subtree ( const iter &  one,
const iter &  two,
BinaryPredicate  fun 
) const [inline]

Definition at line 1686 of file tree.hh.

template<class T , class tree_node_allocator >
template<typename iter >
bool tree< T, tree_node_allocator >::equal_subtree ( const iter &  one,
const iter &  two 
) const [inline]

Definition at line 1659 of file tree.hh.

template<class T, class tree_node_allocator = std::allocator<tree_node_<T> >>
template<typename iter >
iter tree< T, tree_node_allocator >::erase ( iter   )  [inline]

Erase element at position pointed to by iterator, return incremented iterator.

template<class T , class tree_node_allocator >
template<class iter >
iter tree< T, tree_node_allocator >::erase ( iter  it  )  [inline]

Erase element at position pointed to by iterator, return incremented iterator.

Definition at line 627 of file tree.hh.

template<class T , class tree_node_allocator >
void tree< T, tree_node_allocator >::erase_branch ( const iterator_base &  it  )  [inline]

Erase a full branch of the tree, find the parrent from witch the branch started and remove all nodes in it.

Definition at line 489 of file tree.hh.

template<class T, class tree_node_allocator = std::allocator<tree_node_<T> >>
void tree< T, tree_node_allocator >::erase_children ( const iterator_base &   ) 

Erase all children of the node pointed to by iterator.

template<class T , class tree_node_allocator >
void tree< T, tree_node_allocator >::erase_children ( const iterator_base &  it  )  [inline]

Erase all children of the node pointed to by iterator.

Definition at line 604 of file tree.hh.

template<class T , class tree_node_allocator >
template<typename iter >
iter tree< T, tree_node_allocator >::flatten ( iter  position  )  [inline]

Move all children of node at 'position' to be siblings, returns position.

Definition at line 1285 of file tree.hh.

template<class T, class tree_node_allocator = std::allocator<tree_node_<T> >>
void tree< T, tree_node_allocator >::head_initialise_ (  )  [private]
template<class T , class tree_node_allocator >
void tree< T, tree_node_allocator >::head_initialise_ (  )  [inline, private]

Definition at line 539 of file tree.hh.

template<class T , class tree_node_allocator >
unsigned int tree< T, tree_node_allocator >::index ( children_iterator  it  )  const [inline]

Determine the index of a node in the range of siblings to which it belongs.

Definition at line 1010 of file tree_new.hh.

template<class T , class tree_node_allocator >
unsigned int tree< T, tree_node_allocator >::index ( sibling_iterator  it  )  const [inline]

Determine the index of a node in the range of siblings to which it belongs.

Definition at line 1961 of file tree.hh.

template<class T, class tree_node_allocator >
tree< T, tree_node_allocator >::sibling_iterator tree< T, tree_node_allocator >::insert ( sibling_iterator  position,
const T &  x 
) [inline]

Specialisation of previous member.

Definition at line 1075 of file tree.hh.

template<class T, class tree_node_allocator >
template<class iter >
iter tree< T, tree_node_allocator >::insert ( iter  position,
const T &  x 
) [inline]

Insert node as previous sibling of node pointed to by position.

Definition at line 1048 of file tree.hh.

template<class T, class tree_node_allocator = std::allocator<tree_node_<T> >>
template<typename iter >
iter tree< T, tree_node_allocator >::insert_after ( iter  position,
const T &  x 
) [inline]

Insert node as next sibling of node pointed to by position.

template<class T, class tree_node_allocator >
template<class iter >
iter tree< T, tree_node_allocator >::insert_after ( iter  position,
const T &  x 
) [inline]

Insert node as next sibling of node pointed to by position.

Definition at line 1106 of file tree.hh.

template<class T, class tree_node_allocator >
template<class iter >
iter tree< T, tree_node_allocator >::insert_before ( iter  position,
const T &  x 
) [inline]

Insert node as previous sibling of node pointed to by position.

Definition at line 666 of file tree_new.hh.

template<class T , class tree_node_allocator >
template<class iter >
iter tree< T, tree_node_allocator >::insert_subtree ( iter  position,
const iterator_base &  subtree 
) [inline]

Insert node (with children) pointed to by subtree as previous sibling of node pointed to by position.

Definition at line 1131 of file tree.hh.

template<class T , class tree_node_allocator >
template<class iter >
iter tree< T, tree_node_allocator >::insert_subtree_after ( iter  position,
const iterator_base &  subtree 
) [inline]

Insert node (with children) pointed to by subtree as next sibling of node pointed to by position.

Definition at line 1141 of file tree.hh.

template<class T , class tree_node_allocator >
bool tree< T, tree_node_allocator >::is_in_subtree ( const iterator_base &  position,
const iterator_base &  begin,
const iterator_base &  end 
) const [inline]

Determine whether node at position is in the subtrees with root in the range.

Definition at line 1918 of file tree.hh.

template<class T, class tree_node_allocator = std::allocator<tree_node_<T> >>
bool tree< T, tree_node_allocator >::is_valid ( const iterator_base &   )  const

Determine whether the iterator is an 'end' iterator and thus not actually pointing to a node.

template<class T , class tree_node_allocator >
bool tree< T, tree_node_allocator >::is_valid ( const iterator_base &  it  )  const [inline]

Determine whether the iterator is an 'end' iterator and thus not actually pointing to a node.

Definition at line 1931 of file tree.hh.

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 [inline]

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

Definition at line 1938 of file tree.hh.

template<class T, class tree_node_allocator = std::allocator<tree_node_<T> >>
int tree< T, tree_node_allocator >::max_depth ( const iterator_base &   )  const

Determine the maximal depth of the tree with top node at the given position.

template<class T, class tree_node_allocator = std::allocator<tree_node_<T> >>
int tree< T, tree_node_allocator >::max_depth (  )  const

Determine the maximal depth of the tree. An empty tree has max_depth=-1.

template<class T , class tree_node_allocator >
int tree< T, tree_node_allocator >::max_depth ( const iterator_base &  pos  )  const [inline]

Determine the maximal depth of the tree with top node at the given position.

Definition at line 1782 of file tree.hh.

template<class T , class tree_node_allocator >
int tree< T, tree_node_allocator >::max_depth (  )  const [inline]

Determine the maximal depth of the tree. An empty tree has max_depth=-1.

Definition at line 1771 of file tree.hh.

template<class T , class tree_node_allocator >
void tree< T, tree_node_allocator >::merge ( sibling_iterator  to1,
sibling_iterator  to2,
sibling_iterator  from1,
sibling_iterator  from2,
bool  duplicate_leaves = false 
) [inline]

Merge with other tree, creating new branches and leaves only if they are not already present.

Definition at line 1559 of file tree.hh.

template<class T, class tree_node_allocator = std::allocator<tree_node_<T> >>
template<typename iter >
iter tree< T, tree_node_allocator >::move_after ( iter  target,
iter  source 
) [inline]

Move 'source' node (plus its children) to become the next sibling of 'target'.

template<class T , class tree_node_allocator >
template<typename iter >
iter tree< T, tree_node_allocator >::move_after ( iter  target,
iter  source 
) [inline]

Move 'source' node (plus its children) to become the next sibling of 'target'.

Definition at line 1382 of file tree.hh.

template<class T, class tree_node_allocator = std::allocator<tree_node_<T> >>
template<typename iter >
iter tree< T, tree_node_allocator >::move_before ( iter  target,
iter  source 
) [inline]

Move 'source' node (plus its children) to become the previous sibling of 'target'.

template<class T , class tree_node_allocator >
tree< T, tree_node_allocator >::sibling_iterator tree< T, tree_node_allocator >::move_before ( sibling_iterator  target,
sibling_iterator  source 
) [inline]

Definition at line 1441 of file tree.hh.

template<class T , class tree_node_allocator >
template<typename iter >
iter tree< T, tree_node_allocator >::move_before ( iter  target,
iter  source 
) [inline]

Move 'source' node (plus its children) to become the previous sibling of 'target'.

Definition at line 1411 of file tree.hh.

template<class T , class tree_node_allocator >
template<typename iter >
iter tree< T, tree_node_allocator >::move_ontop ( iter  target,
iter  source 
) [inline]

Move 'source' node (plus its children) to become the node at 'target' (erasing the node at 'target').

Definition at line 1478 of file tree.hh.

template<class T , class tree_node_allocator >
template<typename iter >
iter tree< T, tree_node_allocator >::move_ontop_same_branch ( iter  target,
iter  source 
) [inline]

Definition at line 1517 of file tree.hh.

template<class T , class tree_node_allocator >
template<typename iter >
iter tree< T, tree_node_allocator >::next_at_same_depth ( iter  position  )  const [inline]

Return iterator to the next node at a given depth.

Definition at line 826 of file tree.hh.

template<class T, class tree_node_allocator = std::allocator<tree_node_<T> >>
template<typename iter >
iter tree< T, tree_node_allocator >::next_sibling ( iter   )  const [inline]

Return iterator to the next sibling of a node.

template<class T , class tree_node_allocator >
template<typename iter >
iter tree< T, tree_node_allocator >::next_sibling ( iter  position  )  const [inline]

Return iterator to the next sibling of a node.

Definition at line 816 of file tree.hh.

template<class T, class tree_node_allocator = std::allocator<tree_node_<T> >>
static unsigned int tree< T, tree_node_allocator >::number_of_children ( const iterator_base &   )  [static]

Count the number of children of node at position.

template<class T , class tree_node_allocator >
unsigned int tree< T, tree_node_allocator >::number_of_children ( const iterator_base &  it  )  [inline, static]

Count the number of children of node at position.

Definition at line 1810 of file tree.hh.

template<class T , class tree_node_allocator >
unsigned int tree< T, tree_node_allocator >::number_of_siblings ( const iterator_base &  it  )  const [inline]

Count the number of siblings (left and right) of node at iterator. Total nodes at this level is +1.

Definition at line 1826 of file tree.hh.

template<class T, class tree_node_allocator = std::allocator<tree_node_<T> >>
tree<T,tree_node_allocator>& tree< T, tree_node_allocator >::operator= ( const tree< T, tree_node_allocator > &   ) 
template<class T, class tree_node_allocator>
tree< T, tree_node_allocator > & tree< T, tree_node_allocator >::operator= ( const tree< T, tree_node_allocator > &  other  )  [inline]

Definition at line 560 of file tree.hh.

template<class T, class tree_node_allocator = std::allocator<tree_node_<T> >>
template<typename iter >
static iter tree< T, tree_node_allocator >::parent ( iter   )  [inline, static]

Return iterator to the parent of a node.

template<class T , class tree_node_allocator >
template<typename iter >
iter tree< T, tree_node_allocator >::parent ( iter  position  )  [inline, static]

Return iterator to the parent of a node.

Definition at line 798 of file tree.hh.

template<class T, class tree_node_allocator = std::allocator<tree_node_<T> >>
template<typename iter >
iter tree< T, tree_node_allocator >::prepend_child ( iter  position,
const T &  x 
) [inline]
template<class T, class tree_node_allocator >
template<class iter >
iter tree< T, tree_node_allocator >::prepend_child ( iter  position,
iter  other_position 
) [inline]

Definition at line 995 of file tree.hh.

template<class T, class tree_node_allocator >
template<class iter >
iter tree< T, tree_node_allocator >::prepend_child ( iter  position,
const T &  x 
) [inline]

Definition at line 956 of file tree.hh.

template<class T , class tree_node_allocator >
template<typename iter >
iter tree< T, tree_node_allocator >::prepend_child ( iter  position  )  [inline]

Definition at line 898 of file tree.hh.

template<class T , class tree_node_allocator >
template<class iter >
iter tree< T, tree_node_allocator >::prepend_children ( iter  position,
sibling_iterator  from,
sibling_iterator  to 
) [inline]

Definition at line 1024 of file tree.hh.

template<class T, class tree_node_allocator = std::allocator<tree_node_<T> >>
template<typename iter >
iter tree< T, tree_node_allocator >::previous_sibling ( iter   )  const [inline]

Return iterator to the previous sibling of a node.

template<class T , class tree_node_allocator >
template<typename iter >
iter tree< T, tree_node_allocator >::previous_sibling ( iter  position  )  const [inline]

Return iterator to the previous sibling of a node.

Definition at line 806 of file tree.hh.

template<class T , class tree_node_allocator >
template<typename iter >
iter tree< T, tree_node_allocator >::reparent ( iter  position,
iter  from 
) [inline]

Move all child nodes of 'from' to be children of 'position'.

Definition at line 1361 of file tree.hh.

template<class T , class tree_node_allocator >
template<typename iter >
iter tree< T, tree_node_allocator >::reparent ( iter  position,
sibling_iterator  begin,
sibling_iterator  end 
) [inline]

Move nodes in range to be children of 'position'.

Definition at line 1313 of file tree.hh.

template<class T, class tree_node_allocator >
tree< T, tree_node_allocator >::pre_order_iterator tree< T, tree_node_allocator >::reparent_root ( const T &  x  )  [inline]

set X as the new head of the tree, the old head will be a child of new head.

Definition at line 794 of file tree_new.hh.

template<class T, class tree_node_allocator = std::allocator<tree_node_<T> >>
template<typename iter >
iter tree< T, tree_node_allocator >::replace ( iter  position,
const iterator_base &  from 
) [inline]

Replace node at 'position' with subtree starting at 'from' (do not erase subtree at 'from'); see above.

template<class T, class tree_node_allocator = std::allocator<tree_node_<T> >>
template<typename iter >
iter tree< T, tree_node_allocator >::replace ( iter  position,
const T &  x 
) [inline]

Replace node at 'position' with other node (keeping same children); 'position' becomes invalid.

template<class T , class tree_node_allocator >
tree< T, tree_node_allocator >::sibling_iterator tree< T, tree_node_allocator >::replace ( sibling_iterator  orig_begin,
sibling_iterator  orig_end,
sibling_iterator  new_begin,
sibling_iterator  new_end 
) [inline]

Replace string of siblings (plus their children) with copy of a new string (with children); see above.

Definition at line 1239 of file tree.hh.

template<class T, class tree_node_allocator >
template<class iter >
iter tree< T, tree_node_allocator >::replace ( iter  position,
const iterator_base &  from 
) [inline]

Replace node at 'position' with subtree starting at 'from' (do not erase subtree at 'from'); see above.

Definition at line 1173 of file tree.hh.

template<class T, class tree_node_allocator >
template<class iter >
iter tree< T, tree_node_allocator >::replace ( iter  position,
const T &  x 
) [inline]

Replace node at 'position' with other node (keeping same children); 'position' becomes invalid.

Definition at line 1161 of file tree.hh.

template<class T , class tree_node_allocator >
tree< T, tree_node_allocator >::pre_order_iterator tree< T, tree_node_allocator >::root (  )  const [inline]

Return iterator to the beginning of the tree.

Definition at line 490 of file tree_new.hh.

template<class T, class tree_node_allocator >
tree< T, tree_node_allocator >::pre_order_iterator tree< T, tree_node_allocator >::set_head ( const T &  x  )  [inline]

Short-hand to insert topmost node in otherwise empty tree.

Definition at line 1040 of file tree.hh.

template<class T, class tree_node_allocator >
tree< T, tree_node_allocator >::pre_order_iterator tree< T, tree_node_allocator >::set_root ( const T &  x  )  [inline]

Short-hand to insert_before topmost node in otherwise empty tree.

Definition at line 658 of file tree_new.hh.

template<class T , class tree_node_allocator >
tree< T, tree_node_allocator >::sibling_iterator tree< T, tree_node_allocator >::sibling ( const iterator_base &  position,
unsigned int  num 
) [inline]

Return iterator to the sibling indicated by index.

Definition at line 1980 of file tree.hh.

template<class T, class tree_node_allocator = std::allocator<tree_node_<T> >>
size_t tree< T, tree_node_allocator >::size ( const iterator_base &   )  const

Count the total number of nodes below the indicated node (plus one).

template<class T, class tree_node_allocator = std::allocator<tree_node_<T> >>
size_t tree< T, tree_node_allocator >::size (  )  const

Count the total number of nodes.

template<class T , class tree_node_allocator >
size_t tree< T, tree_node_allocator >::size ( const iterator_base &  top  )  const [inline]

Count the total number of nodes below the indicated node (plus one).

Definition at line 1724 of file tree.hh.

template<class T , class tree_node_allocator >
size_t tree< T, tree_node_allocator >::size (  )  const [inline]

Count the total number of nodes.

Definition at line 1712 of file tree.hh.

template<class T , class tree_node_allocator >
template<class StrictWeakOrdering >
void tree< T, tree_node_allocator >::sort ( sibling_iterator  from,
sibling_iterator  to,
StrictWeakOrdering  comp,
bool  deep = false 
) [inline]

Definition at line 1591 of file tree.hh.

template<class T , class tree_node_allocator >
void tree< T, tree_node_allocator >::sort ( sibling_iterator  from,
sibling_iterator  to,
bool  deep = false 
) [inline]

Sort (std::sort only moves values of nodes, this one moves children as well).

Definition at line 1583 of file tree.hh.

template<class T , class tree_node_allocator >
void tree< T, tree_node_allocator >::subtree ( tree< T, tree_node_allocator > &  tmp,
sibling_iterator  from,
sibling_iterator  to 
) const [inline]

Definition at line 1705 of file tree.hh.

template<class T , class tree_node_allocator >
tree< T, tree_node_allocator > tree< T, tree_node_allocator >::subtree ( sibling_iterator  from,
sibling_iterator  to 
) const [inline]

Extract a new tree formed by the range of siblings plus all their children.

Definition at line 1696 of file tree.hh.

template<class T , class tree_node_allocator >
void tree< T, tree_node_allocator >::swap ( iterator  one,
iterator  two 
) [inline]

Exchange two nodes (plus subtrees).

Definition at line 1871 of file tree.hh.

template<class T , class tree_node_allocator >
void tree< T, tree_node_allocator >::swap ( sibling_iterator  it  )  [inline]

Exchange the node (plus subtree) with its sibling node (do nothing if no sibling present).

Definition at line 1850 of file tree.hh.

template<class T, class tree_node_allocator >
template<typename iter >
iter tree< T, tree_node_allocator >::wrap ( iter  position,
const T &  x 
) [inline]

Replace node with a new node, making the old node a child of the new node.

Definition at line 1371 of file tree.hh.

Member Data Documentation

template<class T, class tree_node_allocator = std::allocator<tree_node_<T> >>
tree_node_allocator tree< T, tree_node_allocator >::alloc_ [private]

Definition at line 427 of file tree.hh.

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

Definition at line 425 of file tree.hh.

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

Definition at line 425 of file tree.hh.

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

Definition at line 78 of file tree.hh.

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

Definition at line 77 of file tree.hh.

The documentation for this class was generated from the following files:
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines

mtt
Author(s): Jorge Almeida
autogenerated on Wed Jul 23 04:34:58 2014