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_node * | feet
tree_node * | head

## 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

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

## ◆ tree() [2/4]

template<class T , class tree_node_allocator >

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

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

## ◆ tree() [3/4]

template<class T , class tree_node_allocator >

tree< T, tree_node_allocator >::tree | ( | const iterator_base & | other | ) |

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

## ◆ tree() [4/4]

template<class T , class tree_node_allocator >

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

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

## ◆ ~tree()

template<class T , class tree_node_allocator >

tree< T, tree_node_allocator >::~tree

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

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

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

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

Referenced by tree< T, tree_node_allocator >::append_child(), tree< T, tree_node_allocator >::merge(), Origin750Parser::readProjectTreeFolder(), Origin810Parser::readProjectTreeFolder(), and tree< T, tree_node_allocator >::replace().

## ◆ 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
| ) |  |

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

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

## ◆ 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

Return iterator to the beginning of the tree.

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

Referenced by tree< T, tree_node_allocator >::copy_(), tree< T, tree_node_allocator >::empty(), tree< T, tree_node_allocator >::equal_subtree(), tree< T, tree_node_allocator >::is_in_subtree(), tree< T, tree_node_allocator >::max_depth(), tree< T, tree_node_allocator >::breadth_first_queued_iterator::operator++(), Origin750Parser::readProjectTree(), tree< T, tree_node_allocator >::reparent(), tree< T, tree_node_allocator >::size(), tree< T, tree_node_allocator >::sort(), tree< T, tree_node_allocator >::subtree(), and tree< T, tree_node_allocator >::tree().

## ◆ 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

Return leaf iterator to the first leaf of the tree.

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

## ◆ begin_post()

template<class T , class tree_node_allocator >

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

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

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

## ◆ 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

Erase all nodes of the tree.

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

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

## ◆ copy_()

template<class T , class tree_node_allocator >

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

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

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

## ◆ 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

Check if tree is empty.

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

## ◆ 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

Return iterator to the end of the tree.

References tree< T, tree_node_allocator >::feet.

Referenced by tree< T, tree_node_allocator >::iterator_base::begin(), tree< T, tree_node_allocator >::begin(), tree< T, tree_node_allocator >::copy_(), tree< T, tree_node_allocator >::empty(), tree< T, tree_node_allocator >::equal_subtree(), tree< T, tree_node_allocator >::is_in_subtree(), tree< T, tree_node_allocator >::breadth_first_queued_iterator::operator++(), Origin750Parser::readProjectTree(), tree< T, tree_node_allocator >::reparent(), tree< T, tree_node_allocator >::size(), tree< T, tree_node_allocator >::sort(), and tree< T, tree_node_allocator >::subtree().

## ◆ 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

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

## ◆ 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

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

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

## ◆ 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

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

## ◆ erase()

template<class T , class tree_node_allocator >
template<class iter >

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

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

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

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

## ◆ erase_children()

template<class T , class tree_node_allocator >

void tree< T, tree_node_allocator >::erase_children | ( | const iterator_base & | it | ) |

Erase all children of the node pointed to by iterator.

References tree< T, tree_node_allocator >::alloc_, tree_node_< T >::data, kp::destructor(), tree< T, tree_node_allocator >::erase_children(), tree_node_< T >::first_child, and tree_node_< T >::next_sibling.

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

## ◆ 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

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

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

## ◆ 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 node as previous sibling of node pointed to by position.

References tree< T, tree_node_allocator >::alloc_, kp::constructor(), tree_node_< T >::data, tree< T, tree_node_allocator >::feet, 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.

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

## ◆ 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
| ) |  |

Specialisation of previous member.

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

## ◆ 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 node as next sibling of node pointed to by position.

References tree< T, tree_node_allocator >::alloc_, kp::constructor(), tree_node_< T >::data, 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.

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

## ◆ 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 node (with children) pointed to by subtree as previous sibling of node pointed to by position.

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

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

## ◆ 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

Determine the maximal depth of the tree.

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

Referenced by 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`
| ) |  |

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

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

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

## ◆ 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
| ) |  |

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

## ◆ 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

Count the number of 'next' siblings of node at iterator.

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

## ◆ operator=()

template<class T , class tree_node_allocator >

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

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

## ◆ 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 | ) |

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

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

## ◆ 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
| ) |  |

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

## ◆ 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
| ) |  |

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

## ◆ 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
| ) |  |

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

## ◆ 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
| ) |  |

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

References tree< T, tree_node_allocator >::begin(), tree< T, tree_node_allocator >::end(), tree_node_< T >::last_child, 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 >::reparent(), and tree< T, tree_node_allocator >::wrap().

## ◆ 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 node at 'position' with subtree starting at 'from' (do not erase subtree at 'from'); see above.

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

## ◆ 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 node at 'position' with other node (keeping same children); 'position' becomes invalid.

References kp::constructor(), and kp::destructor().

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

## ◆ 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 | ) |

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

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

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

## ◆ 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`
| ) |  |

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

## ◆ 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

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

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

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

## ◆ 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

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

## ◆ swap() [1/2]

template<class T , class tree_node_allocator >

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

Exchange two nodes (plus subtrees)

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

## ◆ 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

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

## ◆ feet

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

tree_node * tree< T, tree_node_allocator >::feet

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

## ◆ head

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

tree_node* tree< T, tree_node_allocator >::head

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

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

- /tmp/slackdce/slackrepo.5NA6jZ/build_liborigin/liborigin/tree.hh