GiNaCRA  0.6.4
Data Structures | Public Types | Public Member Functions | Static Public Member Functions | Data Fields | Protected Types | Private Member Functions | Private Attributes
GiNaCRA::tree< T, tree_node_allocator > Class Template Reference

#include <tree.h>

Inheritance diagram for GiNaCRA::tree< T, tree_node_allocator >:
Inheritance graph
[legend]
Collaboration diagram for GiNaCRA::tree< T, tree_node_allocator >:
Collaboration graph
[legend]

Data Structures

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 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 ()
 tree (const T &)
 tree (const iterator_base &)
 tree (const tree< T, tree_node_allocator > &)
 ~tree ()
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
 Find the lowest common ancestor of two nodes, that is, the deepest node such that both nodes are descendants of it.
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
 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).

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.

Data Fields

tree_node * head
tree_node * feet

Protected Types

typedef tree_node_< T > tree_node

Private Member Functions

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

Private Attributes

tree_node_allocator alloc_

Detailed Description

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

Definition at line 77 of file tree.h.

Member Typedef Documentation

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

Definition at line 200 of file tree.h.

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

The default iterator types throughout the tree class.

Definition at line 199 of file tree.h.

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

Definition at line 80 of file tree.h.

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

Value of the data stored at a node.

Definition at line 83 of file tree.h.

Constructor & Destructor Documentation

template<class T , class tree_node_allocator >
GiNaCRA::tree< T, tree_node_allocator >::tree ( )

Definition at line 513 of file tree.h.

References GiNaCRA::tree< T, tree_node_allocator >::head_initialise_().

template<class T, class tree_node_allocator >
GiNaCRA::tree< T, tree_node_allocator >::tree ( const T &  x)

Definition at line 520 of file tree.h.

References GiNaCRA::tree< T, tree_node_allocator >::head_initialise_(), and GiNaCRA::tree< T, tree_node_allocator >::set_head().

template<class T, class tree_node_allocator >
GiNaCRA::tree< T, tree_node_allocator >::tree ( const iterator_base &  other)

Definition at line 528 of file tree.h.

References GiNaCRA::tree< T, tree_node_allocator >::begin(), GiNaCRA::tree< T, tree_node_allocator >::head_initialise_(), GiNaCRA::tree< T, tree_node_allocator >::replace(), and GiNaCRA::tree< T, tree_node_allocator >::set_head().

template<class T, class tree_node_allocator>
GiNaCRA::tree< T, tree_node_allocator >::tree ( const tree< T, tree_node_allocator > &  other)

Definition at line 579 of file tree.h.

References GiNaCRA::tree< T, tree_node_allocator >::copy_(), and GiNaCRA::tree< T, tree_node_allocator >::head_initialise_().

template<class T , class tree_node_allocator >
GiNaCRA::tree< T, tree_node_allocator >::~tree ( )

Definition at line 537 of file tree.h.

References GiNaCRA::tree< T, tree_node_allocator >::alloc_, GiNaCRA::tree< T, tree_node_allocator >::clear(), GiNaCRA::tree< T, tree_node_allocator >::feet, and GiNaCRA::tree< T, tree_node_allocator >::head.

Member Function Documentation

template<class T , class tree_node_allocator >
template<typename iter >
iter GiNaCRA::tree< T, tree_node_allocator >::append_child ( iter  position)

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

Definition at line 946 of file tree.h.

References GiNaCRA::tree< T, tree_node_allocator >::alloc_, GiNaCRA::tree< T, tree_node_allocator >::feet, GiNaCRA::tree_node_< T >::first_child, GiNaCRA::tree< T, tree_node_allocator >::head, GiNaCRA::tree_node_< T >::last_child, GiNaCRA::tree_node_< T >::next_sibling, GiNaCRA::tree_node_< T >::parent, and GiNaCRA::tree_node_< T >::prev_sibling.

Referenced by GiNaCRA::tree< T, tree_node_allocator >::append_child(), GiNaCRA::CAD::liftCheck(), GiNaCRA::tree< T, tree_node_allocator >::merge(), and GiNaCRA::tree< T, tree_node_allocator >::replace().

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

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

Definition at line 1012 of file tree.h.

References GiNaCRA::tree< T, tree_node_allocator >::alloc_, GiNaCRA::tree< T, tree_node_allocator >::feet, GiNaCRA::tree_node_< T >::first_child, GiNaCRA::tree< T, tree_node_allocator >::head, GiNaCRA::tree_node_< T >::last_child, GiNaCRA::tree_node_< T >::next_sibling, GiNaCRA::tree_node_< T >::parent, and GiNaCRA::tree_node_< T >::prev_sibling.

template<class T, class tree_node_allocator >
template<class iter >
iter GiNaCRA::tree< T, tree_node_allocator >::append_child ( iter  position,
iter  other_position 
)

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

Definition at line 1082 of file tree.h.

References GiNaCRA::tree< T, tree_node_allocator >::append_child(), GiNaCRA::tree< T, tree_node_allocator >::feet, GiNaCRA::tree< T, tree_node_allocator >::head, and GiNaCRA::tree< T, tree_node_allocator >::replace().

template<class T , class tree_node_allocator >
template<class iter >
iter GiNaCRA::tree< T, tree_node_allocator >::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.

Definition at line 1108 of file tree.h.

References GiNaCRA::tree< T, tree_node_allocator >::feet, GiNaCRA::tree< T, tree_node_allocator >::head, and GiNaCRA::tree< T, tree_node_allocator >::insert_subtree().

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

Return iterator to the beginning of the tree.

Definition at line 686 of file tree.h.

References GiNaCRA::tree< T, tree_node_allocator >::head, and GiNaCRA::tree_node_< T >::next_sibling.

Referenced by GiNaCRA::CAD::CAD(), GiNaCRA::CAD::check(), GiNaCRA::tree< T, tree_node_allocator >::copy_(), GiNaCRA::tree< T, tree_node_allocator >::debug_verify_consistency(), GiNaCRA::tree< T, tree_node_allocator >::empty(), GiNaCRA::tree< T, tree_node_allocator >::equal_subtree(), GiNaCRA::tree< T, tree_node_allocator >::is_in_subtree(), GiNaCRA::tree< T, tree_node_allocator >::breadth_first_queued_iterator::operator++(), GiNaCRA::CAD::printSampleTree(), GiNaCRA::tree< T, tree_node_allocator >::reparent(), GiNaCRA::CAD::samples(), GiNaCRA::tree< T, tree_node_allocator >::size(), GiNaCRA::tree< T, tree_node_allocator >::sort(), GiNaCRA::tree< T, tree_node_allocator >::subtree(), and GiNaCRA::tree< T, tree_node_allocator >::tree().

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

Return sibling iterator to the first child of given node.

Definition at line 804 of file tree.h.

References GiNaCRA::tree< T, tree_node_allocator >::end().

template<class T , class tree_node_allocator >
tree< T, tree_node_allocator >::breadth_first_queued_iterator GiNaCRA::tree< T, tree_node_allocator >::begin_breadth_first ( ) const

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

Definition at line 700 of file tree.h.

References GiNaCRA::tree< T, tree_node_allocator >::head, and GiNaCRA::tree_node_< T >::next_sibling.

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

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

Definition at line 736 of file tree.h.

References GiNaCRA::tree_node_< T >::first_child, GiNaCRA::tree_node_< T >::next_sibling, GiNaCRA::tree< T, tree_node_allocator >::iterator_base::node, GiNaCRA::tree_node_< T >::parent, and GiNaCRA::tree< T, tree_node_allocator >::fixed_depth_iterator::top_node.

template<class T , class tree_node_allocator >
tree< T, tree_node_allocator >::leaf_iterator GiNaCRA::tree< T, tree_node_allocator >::begin_leaf ( ) const

Return leaf iterator to the first leaf of the tree.

Definition at line 827 of file tree.h.

References GiNaCRA::tree< T, tree_node_allocator >::feet, GiNaCRA::tree_node_< T >::first_child, GiNaCRA::tree< T, tree_node_allocator >::head, and GiNaCRA::tree_node_< T >::next_sibling.

Referenced by GiNaCRA::CAD::samples().

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

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

Definition at line 849 of file tree.h.

References GiNaCRA::tree_node_< T >::first_child.

template<class T , class tree_node_allocator >
tree< T, tree_node_allocator >::post_order_iterator GiNaCRA::tree< T, tree_node_allocator >::begin_post ( ) const

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

Definition at line 714 of file tree.h.

References GiNaCRA::tree< T, tree_node_allocator >::feet, GiNaCRA::tree_node_< T >::first_child, GiNaCRA::tree< T, tree_node_allocator >::head, and GiNaCRA::tree_node_< T >::next_sibling.

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

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

Definition at line 2356 of file tree.h.

References GiNaCRA::tree_node_< T >::next_sibling.

template<class T , class tree_node_allocator >
void GiNaCRA::tree< T, tree_node_allocator >::clear ( )

Erase all nodes of the tree.

Definition at line 614 of file tree.h.

References GiNaCRA::tree< T, tree_node_allocator >::erase(), GiNaCRA::tree< T, tree_node_allocator >::feet, GiNaCRA::tree< T, tree_node_allocator >::head, and GiNaCRA::tree_node_< T >::next_sibling.

Referenced by GiNaCRA::tree< T, tree_node_allocator >::copy_(), and GiNaCRA::tree< T, tree_node_allocator >::~tree().

template<class T, class tree_node_allocator>
void GiNaCRA::tree< T, tree_node_allocator >::copy_ ( const tree< T, tree_node_allocator > &  other) [private]

Definition at line 587 of file tree.h.

References GiNaCRA::tree< T, tree_node_allocator >::begin(), GiNaCRA::tree< T, tree_node_allocator >::clear(), GiNaCRA::tree< T, tree_node_allocator >::end(), GiNaCRA::tree< T, tree_node_allocator >::insert(), GiNaCRA::tree< T, tree_node_allocator >::replace(), and GiNaCRA::tree< T, tree_node_allocator >::iterator_base::skip_children().

Referenced by GiNaCRA::tree< T, tree_node_allocator >::operator=(), and GiNaCRA::tree< T, tree_node_allocator >::tree().

template<class T , class tree_node_allocator >
void GiNaCRA::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).

Definition at line 2329 of file tree.h.

References GiNaCRA::tree< T, tree_node_allocator >::begin(), GiNaCRA::tree< T, tree_node_allocator >::end(), GiNaCRA::tree_node_< T >::next_sibling, GiNaCRA::tree< T, tree_node_allocator >::iterator_base::node, GiNaCRA::tree_node_< T >::parent, and GiNaCRA::tree_node_< T >::prev_sibling.

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

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

Definition at line 1985 of file tree.h.

References GiNaCRA::tree_node_< T >::parent.

Referenced by GiNaCRA::CAD::printSampleTree().

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

Definition at line 2002 of file tree.h.

References GiNaCRA::tree_node_< T >::parent.

template<class T , class tree_node_allocator >
bool GiNaCRA::tree< T, tree_node_allocator >::empty ( ) const

Check if tree is empty.

Definition at line 1977 of file tree.h.

References GiNaCRA::tree< T, tree_node_allocator >::begin(), and GiNaCRA::tree< T, tree_node_allocator >::end().

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

Return iterator to the end of the tree.

Definition at line 693 of file tree.h.

References GiNaCRA::tree< T, tree_node_allocator >::feet.

Referenced by GiNaCRA::tree< T, tree_node_allocator >::iterator_base::begin(), GiNaCRA::tree< T, tree_node_allocator >::begin(), GiNaCRA::tree< T, tree_node_allocator >::copy_(), GiNaCRA::tree< T, tree_node_allocator >::debug_verify_consistency(), GiNaCRA::tree< T, tree_node_allocator >::empty(), GiNaCRA::tree< T, tree_node_allocator >::equal_subtree(), GiNaCRA::CAD::liftCheck(), GiNaCRA::tree< T, tree_node_allocator >::breadth_first_queued_iterator::operator++(), GiNaCRA::CAD::printSampleTree(), GiNaCRA::tree< T, tree_node_allocator >::reparent(), GiNaCRA::tree< T, tree_node_allocator >::size(), GiNaCRA::tree< T, tree_node_allocator >::sort(), and GiNaCRA::tree< T, tree_node_allocator >::subtree().

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

Return sibling end iterator for children of given node.

Definition at line 818 of file tree.h.

References GiNaCRA::tree< T, tree_node_allocator >::sibling_iterator::parent_.

template<class T , class tree_node_allocator >
tree< T, tree_node_allocator >::breadth_first_queued_iterator GiNaCRA::tree< T, tree_node_allocator >::end_breadth_first ( ) const

Return breadth-first end iterator.

Definition at line 707 of file tree.h.

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

Return fixed-depth end iterator.

Definition at line 779 of file tree.h.

References GiNaCRA::tree_node_< T >::first_child, and GiNaCRA::tree_node_< T >::next_sibling.

template<class T , class tree_node_allocator >
tree< T, tree_node_allocator >::leaf_iterator GiNaCRA::tree< T, tree_node_allocator >::end_leaf ( ) const

Return leaf end iterator for entire tree.

Definition at line 842 of file tree.h.

References GiNaCRA::tree< T, tree_node_allocator >::feet.

Referenced by GiNaCRA::CAD::samples().

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

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

Definition at line 861 of file tree.h.

template<class T , class tree_node_allocator >
tree< T, tree_node_allocator >::post_order_iterator GiNaCRA::tree< T, tree_node_allocator >::end_post ( ) const

Return post-order end iterator of the tree.

Definition at line 729 of file tree.h.

References GiNaCRA::tree< T, tree_node_allocator >::feet.

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

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

Definition at line 1870 of file tree.h.

Referenced by GiNaCRA::tree< T, tree_node_allocator >::equal_subtree().

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

Definition at line 1888 of file tree.h.

References GiNaCRA::tree< T, tree_node_allocator >::is_valid(), and GiNaCRA::tree< T, tree_node_allocator >::iterator_base::number_of_children().

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

Definition at line 1879 of file tree.h.

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

Definition at line 1912 of file tree.h.

References GiNaCRA::tree< T, tree_node_allocator >::begin(), GiNaCRA::tree< T, tree_node_allocator >::end(), GiNaCRA::tree< T, tree_node_allocator >::equal(), and GiNaCRA::tree< T, tree_node_allocator >::number_of_children().

template<class T , class tree_node_allocator >
template<class iter >
iter GiNaCRA::tree< T, tree_node_allocator >::erase ( iter  it)

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

Definition at line 649 of file tree.h.

References GiNaCRA::tree< T, tree_node_allocator >::alloc_, GiNaCRA::tree< T, tree_node_allocator >::erase_children(), GiNaCRA::tree< T, tree_node_allocator >::head, GiNaCRA::tree_node_< T >::next_sibling, GiNaCRA::tree_node_< T >::parent, and GiNaCRA::tree_node_< T >::prev_sibling.

Referenced by GiNaCRA::tree< T, tree_node_allocator >::clear(), GiNaCRA::tree< T, tree_node_allocator >::move_ontop(), and GiNaCRA::tree< T, tree_node_allocator >::replace().

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

Erase all children of the node pointed to by iterator.

Definition at line 623 of file tree.h.

References GiNaCRA::tree< T, tree_node_allocator >::alloc_, and GiNaCRA::tree_node_< T >::next_sibling.

Referenced by GiNaCRA::tree< T, tree_node_allocator >::erase(), and GiNaCRA::tree< T, tree_node_allocator >::replace().

template<class T , class tree_node_allocator >
template<typename iter >
iter GiNaCRA::tree< T, tree_node_allocator >::flatten ( iter  position)

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

Definition at line 1453 of file tree.h.

References GiNaCRA::tree_node_< T >::first_child, GiNaCRA::tree_node_< T >::next_sibling, and GiNaCRA::tree_node_< T >::parent.

template<class T , class tree_node_allocator >
void GiNaCRA::tree< T, tree_node_allocator >::head_initialise_ ( ) [private]

Definition at line 548 of file tree.h.

References GiNaCRA::tree< T, tree_node_allocator >::alloc_, GiNaCRA::tree< T, tree_node_allocator >::feet, GiNaCRA::tree_node_< T >::first_child, GiNaCRA::tree< T, tree_node_allocator >::head, GiNaCRA::tree_node_< T >::last_child, GiNaCRA::tree_node_< T >::next_sibling, GiNaCRA::tree_node_< T >::parent, and GiNaCRA::tree_node_< T >::prev_sibling.

Referenced by GiNaCRA::tree< T, tree_node_allocator >::tree().

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

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

Definition at line 2270 of file tree.h.

References GiNaCRA::tree< T, tree_node_allocator >::head, GiNaCRA::tree< T, tree_node_allocator >::iterator_base::node, GiNaCRA::tree_node_< T >::parent, and GiNaCRA::tree_node_< T >::prev_sibling.

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

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

Definition at line 1156 of file tree.h.

References GiNaCRA::tree< T, tree_node_allocator >::alloc_, GiNaCRA::tree< T, tree_node_allocator >::feet, GiNaCRA::tree_node_< T >::first_child, GiNaCRA::tree_node_< T >::last_child, GiNaCRA::tree_node_< T >::next_sibling, GiNaCRA::tree_node_< T >::parent, and GiNaCRA::tree_node_< T >::prev_sibling.

Referenced by GiNaCRA::CAD::CAD(), GiNaCRA::tree< T, tree_node_allocator >::copy_(), GiNaCRA::tree< T, tree_node_allocator >::insert_subtree(), GiNaCRA::CAD::liftCheck(), GiNaCRA::tree< T, tree_node_allocator >::set_head(), and GiNaCRA::tree< T, tree_node_allocator >::wrap().

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

Specialisation of previous member.

Definition at line 1189 of file tree.h.

References GiNaCRA::tree< T, tree_node_allocator >::alloc_, GiNaCRA::tree_node_< T >::first_child, GiNaCRA::tree_node_< T >::last_child, GiNaCRA::tree_node_< T >::next_sibling, GiNaCRA::tree< T, tree_node_allocator >::iterator_base::node, GiNaCRA::tree_node_< T >::parent, GiNaCRA::tree< T, tree_node_allocator >::sibling_iterator::parent_, GiNaCRA::tree_node_< T >::prev_sibling, and GiNaCRA::tree< T, tree_node_allocator >::sibling_iterator::range_last().

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

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

Definition at line 1228 of file tree.h.

References GiNaCRA::tree< T, tree_node_allocator >::alloc_, GiNaCRA::tree_node_< T >::first_child, GiNaCRA::tree_node_< T >::last_child, GiNaCRA::tree_node_< T >::next_sibling, GiNaCRA::tree_node_< T >::parent, and GiNaCRA::tree_node_< T >::prev_sibling.

Referenced by GiNaCRA::tree< T, tree_node_allocator >::insert_subtree_after().

template<class T , class tree_node_allocator >
template<class iter >
iter GiNaCRA::tree< T, tree_node_allocator >::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.

Definition at line 1258 of file tree.h.

References GiNaCRA::tree< T, tree_node_allocator >::insert(), and GiNaCRA::tree< T, tree_node_allocator >::replace().

Referenced by GiNaCRA::tree< T, tree_node_allocator >::append_children(), GiNaCRA::tree< T, tree_node_allocator >::merge(), GiNaCRA::tree< T, tree_node_allocator >::prepend_children(), and GiNaCRA::tree< T, tree_node_allocator >::replace().

template<class T , class tree_node_allocator >
template<class iter >
iter GiNaCRA::tree< T, tree_node_allocator >::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.

Definition at line 1269 of file tree.h.

References GiNaCRA::tree< T, tree_node_allocator >::insert_after(), and GiNaCRA::tree< T, tree_node_allocator >::replace().

template<class T , class tree_node_allocator >
bool GiNaCRA::tree< T, tree_node_allocator >::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.

Definition at line 2212 of file tree.h.

References GiNaCRA::tree< T, tree_node_allocator >::begin().

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

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

Definition at line 2230 of file tree.h.

References GiNaCRA::tree< T, tree_node_allocator >::feet, and GiNaCRA::tree< T, tree_node_allocator >::head.

Referenced by GiNaCRA::tree< T, tree_node_allocator >::equal(), and GiNaCRA::tree< T, tree_node_allocator >::lowest_common_ancestor().

template<class T , class tree_node_allocator >
tree< T, tree_node_allocator >::iterator GiNaCRA::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.

Definition at line 2239 of file tree.h.

References GiNaCRA::tree< T, tree_node_allocator >::is_valid(), and GiNaCRA::tree< T, tree_node_allocator >::parent().

template<class T , class tree_node_allocator >
int GiNaCRA::tree< T, tree_node_allocator >::max_depth ( ) const

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

Definition at line 2019 of file tree.h.

References GiNaCRA::tree< T, tree_node_allocator >::feet, GiNaCRA::tree< T, tree_node_allocator >::head, and GiNaCRA::tree_node_< T >::next_sibling.

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

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

Definition at line 2031 of file tree.h.

References GiNaCRA::tree< T, tree_node_allocator >::feet, GiNaCRA::tree_node_< T >::first_child, GiNaCRA::tree< T, tree_node_allocator >::head, GiNaCRA::tree_node_< T >::next_sibling, and GiNaCRA::tree_node_< T >::parent.

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

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

Definition at line 1749 of file tree.h.

References GiNaCRA::tree< T, tree_node_allocator >::append_child(), GiNaCRA::tree< T, tree_node_allocator >::iterator_base::begin(), GiNaCRA::tree< T, tree_node_allocator >::iterator_base::end(), GiNaCRA::tree< T, tree_node_allocator >::insert_subtree(), and GiNaCRA::tree< T, tree_node_allocator >::parent().

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

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

Definition at line 1577 of file tree.h.

References GiNaCRA::tree_node_< T >::next_sibling, GiNaCRA::tree_node_< T >::parent, and GiNaCRA::tree_node_< T >::prev_sibling.

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

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

Definition at line 1613 of file tree.h.

References GiNaCRA::tree_node_< T >::next_sibling, GiNaCRA::tree_node_< T >::parent, and GiNaCRA::tree_node_< T >::prev_sibling.

template<class T , class tree_node_allocator >
tree< T, tree_node_allocator >::sibling_iterator GiNaCRA::tree< T, tree_node_allocator >::move_before ( sibling_iterator  target,
sibling_iterator  source 
)

Definition at line 1651 of file tree.h.

References GiNaCRA::tree_node_< T >::first_child, GiNaCRA::tree_node_< T >::last_child, GiNaCRA::tree_node_< T >::next_sibling, GiNaCRA::tree< T, tree_node_allocator >::iterator_base::node, GiNaCRA::tree_node_< T >::parent, GiNaCRA::tree< T, tree_node_allocator >::sibling_iterator::parent_, and GiNaCRA::tree_node_< T >::prev_sibling.

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

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

Definition at line 1702 of file tree.h.

References GiNaCRA::tree< T, tree_node_allocator >::erase(), GiNaCRA::tree_node_< T >::first_child, GiNaCRA::tree_node_< T >::last_child, GiNaCRA::tree_node_< T >::next_sibling, GiNaCRA::tree_node_< T >::parent, and GiNaCRA::tree_node_< T >::prev_sibling.

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

Return iterator to the next node at a given depth.

Definition at line 900 of file tree.h.

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

Return iterator to the next sibling of a node.

Definition at line 889 of file tree.h.

Referenced by GiNaCRA::tree< T, tree_node_allocator >::sibling_iterator::operator++().

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

Count the number of children of node at position.

Definition at line 2072 of file tree.h.

References GiNaCRA::tree_node_< T >::next_sibling.

Referenced by GiNaCRA::tree< T, tree_node_allocator >::equal_subtree().

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

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

Definition at line 2092 of file tree.h.

References GiNaCRA::tree< T, tree_node_allocator >::feet, GiNaCRA::tree< T, tree_node_allocator >::head, GiNaCRA::tree_node_< T >::next_sibling, and GiNaCRA::tree_node_< T >::prev_sibling.

template<class T, class tree_node_allocator>
tree< T, tree_node_allocator > & GiNaCRA::tree< T, tree_node_allocator >::operator= ( const tree< T, tree_node_allocator > &  other)

Definition at line 569 of file tree.h.

References GiNaCRA::tree< T, tree_node_allocator >::copy_().

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

Return iterator to the parent of a node.

Definition at line 869 of file tree.h.

Referenced by GiNaCRA::CAD::constructSampleAt(), GiNaCRA::tree< T, tree_node_allocator >::lowest_common_ancestor(), GiNaCRA::tree< T, tree_node_allocator >::merge(), GiNaCRA::tree< T, tree_node_allocator >::replace(), and GiNaCRA::tree< T, tree_node_allocator >::sibling_iterator::set_parent_().

template<class T , class tree_node_allocator >
template<typename iter >
iter GiNaCRA::tree< T, tree_node_allocator >::prepend_child ( iter  position)

Definition at line 979 of file tree.h.

References GiNaCRA::tree< T, tree_node_allocator >::alloc_, GiNaCRA::tree< T, tree_node_allocator >::feet, GiNaCRA::tree_node_< T >::first_child, GiNaCRA::tree< T, tree_node_allocator >::head, GiNaCRA::tree_node_< T >::last_child, GiNaCRA::tree_node_< T >::next_sibling, GiNaCRA::tree_node_< T >::parent, and GiNaCRA::tree_node_< T >::prev_sibling.

Referenced by GiNaCRA::tree< T, tree_node_allocator >::prepend_child().

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

Definition at line 1049 of file tree.h.

References GiNaCRA::tree< T, tree_node_allocator >::alloc_, GiNaCRA::tree< T, tree_node_allocator >::feet, GiNaCRA::tree_node_< T >::first_child, GiNaCRA::tree< T, tree_node_allocator >::head, GiNaCRA::tree_node_< T >::last_child, GiNaCRA::tree_node_< T >::next_sibling, GiNaCRA::tree_node_< T >::parent, and GiNaCRA::tree_node_< T >::prev_sibling.

template<class T, class tree_node_allocator >
template<class iter >
iter GiNaCRA::tree< T, tree_node_allocator >::prepend_child ( iter  position,
iter  other_position 
)

Definition at line 1095 of file tree.h.

References GiNaCRA::tree< T, tree_node_allocator >::feet, GiNaCRA::tree< T, tree_node_allocator >::head, GiNaCRA::tree< T, tree_node_allocator >::prepend_child(), and GiNaCRA::tree< T, tree_node_allocator >::replace().

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

Definition at line 1128 of file tree.h.

References GiNaCRA::tree< T, tree_node_allocator >::feet, GiNaCRA::tree< T, tree_node_allocator >::head, and GiNaCRA::tree< T, tree_node_allocator >::insert_subtree().

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

Return iterator to the previous sibling of a node.

Definition at line 878 of file tree.h.

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

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

Definition at line 1488 of file tree.h.

References GiNaCRA::tree< T, tree_node_allocator >::begin(), GiNaCRA::tree_node_< T >::last_child, GiNaCRA::tree_node_< T >::next_sibling, GiNaCRA::tree< T, tree_node_allocator >::iterator_base::node, GiNaCRA::tree_node_< T >::parent, and GiNaCRA::tree_node_< T >::prev_sibling.

Referenced by GiNaCRA::tree< T, tree_node_allocator >::reparent(), and GiNaCRA::tree< T, tree_node_allocator >::wrap().

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

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

Definition at line 1556 of file tree.h.

References GiNaCRA::tree< T, tree_node_allocator >::end(), and GiNaCRA::tree< T, tree_node_allocator >::reparent().

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

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

Definition at line 1290 of file tree.h.

Referenced by GiNaCRA::tree< T, tree_node_allocator >::append_child(), GiNaCRA::tree< T, tree_node_allocator >::copy_(), GiNaCRA::tree< T, tree_node_allocator >::insert_subtree(), GiNaCRA::tree< T, tree_node_allocator >::insert_subtree_after(), GiNaCRA::CAD::liftCheck(), GiNaCRA::tree< T, tree_node_allocator >::prepend_child(), GiNaCRA::tree< T, tree_node_allocator >::subtree(), and GiNaCRA::tree< T, tree_node_allocator >::tree().

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

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

Definition at line 1303 of file tree.h.

References GiNaCRA::tree< T, tree_node_allocator >::alloc_, GiNaCRA::tree< T, tree_node_allocator >::append_child(), GiNaCRA::tree_node_< T >::data, GiNaCRA::tree< T, tree_node_allocator >::erase_children(), GiNaCRA::tree_node_< T >::first_child, GiNaCRA::tree< T, tree_node_allocator >::head, GiNaCRA::tree_node_< T >::last_child, GiNaCRA::tree_node_< T >::next_sibling, GiNaCRA::tree_node_< T >::parent, GiNaCRA::tree< T, tree_node_allocator >::parent(), and GiNaCRA::tree_node_< T >::prev_sibling.

template<class T , class tree_node_allocator >
tree< T, tree_node_allocator >::sibling_iterator GiNaCRA::tree< T, tree_node_allocator >::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.

Definition at line 1391 of file tree.h.

References GiNaCRA::tree< T, tree_node_allocator >::erase(), GiNaCRA::tree< T, tree_node_allocator >::insert_subtree(), GiNaCRA::tree_node_< T >::next_sibling, and GiNaCRA::tree< T, tree_node_allocator >::iterator_base::node.

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

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

Definition at line 1147 of file tree.h.

References GiNaCRA::tree< T, tree_node_allocator >::feet, GiNaCRA::tree< T, tree_node_allocator >::head, GiNaCRA::tree< T, tree_node_allocator >::insert(), and GiNaCRA::tree_node_< T >::next_sibling.

Referenced by GiNaCRA::tree< T, tree_node_allocator >::subtree(), and GiNaCRA::tree< T, tree_node_allocator >::tree().

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

Return iterator to the sibling indicated by index.

Definition at line 2297 of file tree.h.

References GiNaCRA::tree< T, tree_node_allocator >::head, and GiNaCRA::tree_node_< T >::next_sibling.

template<class T , class tree_node_allocator >
size_t GiNaCRA::tree< T, tree_node_allocator >::size ( ) const

Count the total number of nodes.

Definition at line 1943 of file tree.h.

References GiNaCRA::tree< T, tree_node_allocator >::begin(), and GiNaCRA::tree< T, tree_node_allocator >::end().

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

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

Definition at line 1959 of file tree.h.

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

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

Definition at line 1782 of file tree.h.

Referenced by GiNaCRA::tree< T, tree_node_allocator >::sort().

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

Definition at line 1791 of file tree.h.

References GiNaCRA::tree< T, tree_node_allocator >::begin(), GiNaCRA::tree< T, tree_node_allocator >::end(), GiNaCRA::tree_node_< T >::next_sibling, GiNaCRA::tree< T, tree_node_allocator >::iterator_base::node, GiNaCRA::tree_node_< T >::parent, GiNaCRA::tree_node_< T >::prev_sibling, and GiNaCRA::tree< T, tree_node_allocator >::sort().

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

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

Definition at line 1925 of file tree.h.

References GiNaCRA::tree< T, tree_node_allocator >::begin(), GiNaCRA::tree< T, tree_node_allocator >::end(), GiNaCRA::tree< T, tree_node_allocator >::replace(), and GiNaCRA::tree< T, tree_node_allocator >::set_head().

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

Definition at line 1935 of file tree.h.

References GiNaCRA::tree< T, tree_node_allocator >::begin(), GiNaCRA::tree< T, tree_node_allocator >::end(), GiNaCRA::tree< T, tree_node_allocator >::replace(), and GiNaCRA::tree< T, tree_node_allocator >::set_head().

template<class T , class tree_node_allocator >
void GiNaCRA::tree< T, tree_node_allocator >::swap ( sibling_iterator  it)

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

Definition at line 2122 of file tree.h.

References GiNaCRA::tree_node_< T >::next_sibling, GiNaCRA::tree< T, tree_node_allocator >::iterator_base::node, GiNaCRA::tree_node_< T >::parent, and GiNaCRA::tree_node_< T >::prev_sibling.

Referenced by GiNaCRA::tree< T, tree_node_allocator >::swap().

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

Exchange two nodes (plus subtrees)

Definition at line 2151 of file tree.h.

References GiNaCRA::tree_node_< T >::first_child, GiNaCRA::tree_node_< T >::last_child, GiNaCRA::tree_node_< T >::next_sibling, GiNaCRA::tree< T, tree_node_allocator >::iterator_base::node, GiNaCRA::tree_node_< T >::parent, GiNaCRA::tree_node_< T >::prev_sibling, and GiNaCRA::tree< T, tree_node_allocator >::swap().

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

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

Definition at line 1565 of file tree.h.

References GiNaCRA::tree< T, tree_node_allocator >::insert(), and GiNaCRA::tree< T, tree_node_allocator >::reparent().

Field Documentation

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

Definition at line 446 of file tree.h.

Referenced by GiNaCRA::tree< T, tree_node_allocator >::append_child(), GiNaCRA::tree< T, tree_node_allocator >::erase(), GiNaCRA::tree< T, tree_node_allocator >::erase_children(), GiNaCRA::tree< T, tree_node_allocator >::head_initialise_(), GiNaCRA::tree< T, tree_node_allocator >::insert(), GiNaCRA::tree< T, tree_node_allocator >::insert_after(), GiNaCRA::tree< T, tree_node_allocator >::prepend_child(), GiNaCRA::tree< T, tree_node_allocator >::replace(), and GiNaCRA::tree< T, tree_node_allocator >::~tree().

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

Definition at line 444 of file tree.h.

Referenced by GiNaCRA::tree< T, tree_node_allocator >::append_child(), GiNaCRA::tree< T, tree_node_allocator >::append_children(), GiNaCRA::tree< T, tree_node_allocator >::begin_leaf(), GiNaCRA::tree< T, tree_node_allocator >::begin_post(), GiNaCRA::tree< T, tree_node_allocator >::clear(), GiNaCRA::tree< T, tree_node_allocator >::end(), GiNaCRA::tree< T, tree_node_allocator >::end_leaf(), GiNaCRA::tree< T, tree_node_allocator >::end_post(), GiNaCRA::tree< T, tree_node_allocator >::head_initialise_(), GiNaCRA::tree< T, tree_node_allocator >::insert(), GiNaCRA::tree< T, tree_node_allocator >::is_valid(), GiNaCRA::tree< T, tree_node_allocator >::max_depth(), GiNaCRA::tree< T, tree_node_allocator >::number_of_siblings(), GiNaCRA::tree< T, tree_node_allocator >::prepend_child(), GiNaCRA::tree< T, tree_node_allocator >::prepend_children(), GiNaCRA::tree< T, tree_node_allocator >::set_head(), and GiNaCRA::tree< T, tree_node_allocator >::~tree().

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

Definition at line 444 of file tree.h.

Referenced by GiNaCRA::tree< T, tree_node_allocator >::append_child(), GiNaCRA::tree< T, tree_node_allocator >::append_children(), GiNaCRA::tree< T, tree_node_allocator >::begin(), GiNaCRA::tree< T, tree_node_allocator >::begin_breadth_first(), GiNaCRA::tree< T, tree_node_allocator >::begin_leaf(), GiNaCRA::tree< T, tree_node_allocator >::begin_post(), GiNaCRA::CAD::check(), GiNaCRA::tree< T, tree_node_allocator >::clear(), GiNaCRA::tree< T, tree_node_allocator >::erase(), GiNaCRA::tree< T, tree_node_allocator >::head_initialise_(), GiNaCRA::tree< T, tree_node_allocator >::index(), GiNaCRA::tree< T, tree_node_allocator >::is_valid(), GiNaCRA::tree< T, tree_node_allocator >::max_depth(), GiNaCRA::tree< T, tree_node_allocator >::number_of_siblings(), GiNaCRA::tree< T, tree_node_allocator >::prepend_child(), GiNaCRA::tree< T, tree_node_allocator >::prepend_children(), GiNaCRA::tree< T, tree_node_allocator >::replace(), GiNaCRA::CAD::samples(), GiNaCRA::tree< T, tree_node_allocator >::set_head(), GiNaCRA::tree< T, tree_node_allocator >::sibling(), and GiNaCRA::tree< T, tree_node_allocator >::~tree().

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