liborigin 2.0.0
Classes | Public Types | Public Member Functions | Static Public Member Functions | Public Attributes | Protected Types | Private Member Functions | Private Attributes | List of all members
tree< T, tree_node_allocator > Class Template Reference

#include <tree.hh>

Classes

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

Public Types

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

Public Member Functions

template<typename iter >
iter append_child (iter position)
 Insert empty node as last/first child of node pointed to by position. More...
 
template<typename iter >
iter append_child (iter position, const T &x)
 Insert node as last/first child of node pointed to by position. More...
 
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. More...
 
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. More...
 
pre_order_iterator begin () const
 Return iterator to the beginning of the tree. More...
 
sibling_iterator begin (const iterator_base &) const
 Return sibling iterator to the first child of given node. More...
 
breadth_first_queued_iterator begin_breadth_first () const
 Return breadth-first iterator to the first node at a given depth. More...
 
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. More...
 
leaf_iterator begin_leaf () const
 Return leaf iterator to the first leaf of the tree. More...
 
post_order_iterator begin_post () const
 Return post-order iterator to the beginning of the tree. More...
 
sibling_iterator child (const iterator_base &position, unsigned int) const
 Inverse of 'index': return the n-th child of the node at position. More...
 
void clear ()
 Erase all nodes of the tree. More...
 
int depth (const iterator_base &) const
 Compute the depth to the root. More...
 
bool empty () const
 Check if tree is empty. More...
 
pre_order_iterator end () const
 Return iterator to the end of the tree. More...
 
sibling_iterator end (const iterator_base &) const
 Return sibling iterator to the end of the children of a given node. More...
 
breadth_first_queued_iterator end_breadth_first () const
 Return breadth-first iterator to end of the nodes at given depth. More...
 
fixed_depth_iterator end_fixed (const iterator_base &, unsigned int) const
 Return fixed-depth iterator to end of the nodes at given depth from the given iterator. More...
 
leaf_iterator end_leaf () const
 Return leaf iterator to the last leaf of the tree. More...
 
post_order_iterator end_post () const
 Return post-order iterator to the end of the tree. More...
 
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). More...
 
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
 
template<typename iter >
iter erase (iter)
 Erase element at position pointed to by iterator, return incremented iterator. More...
 
void erase_children (const iterator_base &)
 Erase all children of the node pointed to by iterator. More...
 
template<typename iter >
iter flatten (iter position)
 Move all children of node at 'position' to be siblings, returns position. More...
 
unsigned int index (sibling_iterator it) const
 Determine the index of a node in the range of siblings to which it belongs. More...
 
template<typename iter >
iter insert (iter position, const T &x)
 Insert node as previous sibling of node pointed to by position. More...
 
sibling_iterator insert (sibling_iterator position, const T &x)
 Specialisation of previous member. More...
 
template<typename iter >
iter insert_after (iter position, const T &x)
 Insert node as next sibling of node pointed to by position. More...
 
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. More...
 
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. More...
 
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. More...
 
bool is_valid (const iterator_base &) const
 Determine whether the iterator is an 'end' iterator and thus not actually pointing to a node. More...
 
int max_depth () const
 Determine the maximal depth of the tree. More...
 
int max_depth (const iterator_base &) const
 Determine the maximal depth of the tree below a given one. More...
 
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. More...
 
template<typename iter >
iter move_after (iter target, iter source)
 Move 'source' node (plus its children) to become the next sibling of 'target'. More...
 
template<typename iter >
iter move_before (iter target, iter source)
 Move 'source' node (plus its children) to become the previous sibling of 'target'. More...
 
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'). More...
 
template<typename iter >
iter next_at_same_depth (iter) const
 Return iterator to the next node at a given depth. More...
 
template<typename iter >
iter next_sibling (iter) const
 Return iterator to the next sibling of a node. More...
 
unsigned int number_of_siblings (const iterator_base &) const
 Count the number of 'next' siblings of node at iterator. More...
 
void operator= (const tree< T, tree_node_allocator > &)
 
template<typename iter >
iter prepend_child (iter position)
 
template<typename iter >
iter prepend_child (iter position, const T &x)
 
template<typename iter >
iter prepend_child (iter position, iter other_position)
 
template<typename iter >
iter prepend_children (iter position, sibling_iterator from, sibling_iterator to)
 
template<typename iter >
iter previous_sibling (iter) const
 Return iterator to the previous sibling of a node. More...
 
template<typename iter >
iter reparent (iter position, iter from)
 Move all child nodes of 'from' to be children of 'position'. More...
 
template<typename iter >
iter reparent (iter position, sibling_iterator begin, sibling_iterator end)
 Move nodes in range to be children of 'position'. More...
 
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. More...
 
template<typename iter >
iter replace (iter position, const T &x)
 Replace node at 'position' with other node (keeping same children); 'position' becomes invalid. More...
 
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. More...
 
pre_order_iterator set_head (const T &x)
 Short-hand to insert topmost node in otherwise empty tree. More...
 
int size () const
 Count the total number of nodes. More...
 
int size (const iterator_base &) const
 Count the total number of nodes below the indicated node (plus one). More...
 
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). More...
 
template<class StrictWeakOrdering >
void sort (sibling_iterator from, sibling_iterator to, StrictWeakOrdering comp, bool deep=false)
 
tree subtree (sibling_iterator from, sibling_iterator to) const
 Extract a new tree formed by the range of siblings plus all their children. More...
 
void subtree (tree &, sibling_iterator from, sibling_iterator to) const
 
void swap (iterator, iterator)
 Exchange two nodes (plus subtrees) More...
 
void swap (sibling_iterator it)
 Exchange the node (plus subtree) with its sibling node (do nothing if no sibling present). More...
 
 tree ()
 
 tree (const iterator_base &)
 
 tree (const T &)
 
 tree (const tree< T, tree_node_allocator > &)
 
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. More...
 
 ~tree ()
 

Static Public Member Functions

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

Public Attributes

tree_nodefeet
 
tree_nodehead
 

Protected Types

typedef tree_node_< T > tree_node
 

Private Member Functions

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

Private Attributes

tree_node_allocator alloc_
 

Member Typedef Documentation

◆ breadth_first_iterator

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

◆ iterator

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.

◆ tree_node

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

◆ value_type

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.

Constructor & Destructor Documentation

◆ tree() [1/4]

template<class T , class tree_node_allocator >
tree< T, tree_node_allocator >::tree

◆ tree() [2/4]

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

◆ tree() [3/4]

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

◆ tree() [4/4]

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

◆ ~tree()

template<class T , class tree_node_allocator >
tree< T, tree_node_allocator >::~tree

Member Function Documentation

◆ append_child() [1/3]

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

◆ append_child() [2/3]

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

◆ append_child() [3/3]

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

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

◆ append_children()

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 
)

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

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

◆ begin() [1/2]

template<class T , class tree_node_allocator >
tree< T, tree_node_allocator >::pre_order_iterator tree< T, tree_node_allocator >::begin
inline

◆ begin() [2/2]

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

Return sibling iterator to the first child of given node.

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

◆ begin_breadth_first()

template<class T , class tree_node_allocator >
tree< T, tree_node_allocator >::breadth_first_queued_iterator tree< T, tree_node_allocator >::begin_breadth_first

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

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

◆ begin_fixed()

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

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

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

◆ begin_leaf()

template<class T , class tree_node_allocator >
tree< T, tree_node_allocator >::leaf_iterator tree< T, tree_node_allocator >::begin_leaf

◆ begin_post()

template<class T , class tree_node_allocator >
tree< T, tree_node_allocator >::post_order_iterator tree< T, tree_node_allocator >::begin_post

◆ child()

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

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

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

◆ clear()

template<class T , class tree_node_allocator >
void tree< T, tree_node_allocator >::clear

◆ copy_()

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

◆ depth()

template<class T , class tree_node_allocator >
int tree< T, tree_node_allocator >::depth ( const iterator_base it) const

Compute the depth to the root.

References tree_node_< T >::parent.

Referenced by Origin750Parser::readProjectTree().

◆ empty()

template<class T , class tree_node_allocator >
bool tree< T, tree_node_allocator >::empty

◆ end() [1/2]

template<class T , class tree_node_allocator >
tree< T, tree_node_allocator >::pre_order_iterator tree< T, tree_node_allocator >::end
inline

◆ end() [2/2]

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

Return sibling iterator to the end of the children of a given node.

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

◆ end_breadth_first()

template<class T , class tree_node_allocator >
tree< T, tree_node_allocator >::breadth_first_queued_iterator tree< T, tree_node_allocator >::end_breadth_first

Return breadth-first iterator to end of the nodes at given depth.

◆ end_fixed()

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

Return fixed-depth iterator to end of the nodes at given depth from the given iterator.

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

◆ end_leaf()

template<class T , class tree_node_allocator >
tree< T, tree_node_allocator >::leaf_iterator tree< T, tree_node_allocator >::end_leaf

Return leaf iterator to the last leaf of the tree.

References tree< T, tree_node_allocator >::feet.

◆ end_post()

template<class T , class tree_node_allocator >
tree< T, tree_node_allocator >::post_order_iterator tree< T, tree_node_allocator >::end_post

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

References tree< T, tree_node_allocator >::feet.

◆ equal() [1/2]

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

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

References tree< T, tree_node_allocator >::equal().

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

◆ equal() [2/2]

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

◆ equal_subtree() [1/2]

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

◆ equal_subtree() [2/2]

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

◆ erase()

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

◆ erase_children()

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

◆ flatten()

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

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

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

◆ head_initialise_()

template<class T , class tree_node_allocator >
void tree< T, tree_node_allocator >::head_initialise_
private

◆ index()

template<class T , class tree_node_allocator >
unsigned int 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.

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

◆ insert() [1/2]

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

◆ insert() [2/2]

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 
)

◆ insert_after()

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

◆ insert_subtree()

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

◆ insert_subtree_after()

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 
)

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

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

◆ is_in_subtree()

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

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

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

◆ is_valid()

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

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

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

◆ max_depth() [1/2]

template<class T , class tree_node_allocator >
int tree< T, tree_node_allocator >::max_depth

◆ max_depth() [2/2]

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

Determine the maximal depth of the tree below a given one.

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

◆ merge()

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 
)

◆ move_after()

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

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

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

◆ move_before() [1/2]

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

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

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

◆ move_before() [2/2]

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 
)

◆ move_ontop()

template<class T , class tree_node_allocator >
template<typename iter >
iter 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').

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

◆ next_at_same_depth()

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

Return iterator to the next node at a given depth.

◆ next_sibling()

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

Return iterator to the next sibling of a node.

◆ number_of_children()

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

Count the number of children of node at position.

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

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

◆ number_of_siblings()

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

◆ operator=()

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

◆ parent()

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

Return iterator to the parent of a node.

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

◆ prepend_child() [1/3]

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

◆ prepend_child() [2/3]

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

◆ prepend_child() [3/3]

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

◆ prepend_children()

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 
)

◆ previous_sibling()

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

Return iterator to the previous sibling of a node.

◆ reparent() [1/2]

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

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

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

◆ reparent() [2/2]

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 
)

◆ replace() [1/3]

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

◆ replace() [2/3]

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

◆ replace() [3/3]

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 
)

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

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

◆ set_head()

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)

◆ size() [1/2]

template<class T , class tree_node_allocator >
int tree< T, tree_node_allocator >::size

Count the total number of nodes.

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

◆ size() [2/2]

template<class T , class tree_node_allocator >
int tree< T, tree_node_allocator >::size ( const iterator_base top) const

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

References tree< T, tree_node_allocator >::iterator_base::skip_children().

◆ sort() [1/2]

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

References tree< T, tree_node_allocator >::sort().

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

◆ sort() [2/2]

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 
)

◆ subtree() [1/2]

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

◆ subtree() [2/2]

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

◆ swap() [1/2]

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

◆ swap() [2/2]

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

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

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

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

◆ wrap()

template<class T , class tree_node_allocator >
template<typename iter >
iter 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.

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

Member Data Documentation

◆ alloc_

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

◆ feet

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

◆ head

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

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