LibOFX
|
Data Structures | |
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 the actual node content, not pointer values). 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 type throughout the tree class. | |
Public Member Functions | |
tree (const T &) | |
tree (const iterator_base &) | |
tree (const tree< T, tree_node_allocator > &) | |
void | 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 iterator to the end 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. | |
fixed_depth_iterator | end_fixed (const iterator_base &, unsigned int) const |
Return fixed-depth iterator to end of the nodes at given depth. | |
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 iterator to the end of the children of a given node. | |
template<typename iter > | |
iter | parent (iter) const |
Return iterator to the parent of a 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 child of node pointed to by position. | |
template<typename iter > | |
iter | append_child (iter position, const T &x) |
Insert node as last child of node pointed to by position. | |
template<typename iter > | |
iter | append_child (iter position, iter other_position) |
Append the node (plus its children) at other_position as a child of position. | |
template<typename iter > | |
iter | append_children (iter position, sibling_iterator from, sibling_iterator to) |
Append the nodes in the from-to range (plus their children) as children of position. | |
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 | 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 | 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'. | |
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). | |
int | size () const |
Count the total number of nodes. | |
bool | empty () const |
Check if tree is empty. | |
int | depth (const iterator_base &) const |
Compute the depth to the root. | |
unsigned int | number_of_children (const iterator_base &) const |
Count the number of children of node at position. | |
unsigned int | number_of_siblings (const iterator_base &) const |
Count the number of 'next' siblings of node at iterator. | |
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. | |
unsigned int | index (sibling_iterator it) const |
Determine the index of a node in the range of siblings to which it belongs. | |
sibling_iterator | child (const iterator_base &position, unsigned int) const |
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 |
typedef pre_order_iterator tree< T, tree_node_allocator >::iterator |
|
protected |
typedef T tree< T, tree_node_allocator >::value_type |
tree< T, tree_node_allocator >::tree | ( | const iterator_base & | other | ) |
iter tree< T, tree_node_allocator >::append_child | ( | iter | position | ) |
Insert empty node as last child of node pointed to by position.
Definition at line 741 of file tree.hh.
Referenced by tree< T, tree_node_allocator >::append_child(), tree< T, tree_node_allocator >::merge(), and tree< T, tree_node_allocator >::replace().
iter tree< T, tree_node_allocator >::append_child | ( | iter | position, |
const T & | x | ||
) |
iter tree< T, tree_node_allocator >::append_child | ( | iter | position, |
iter | other_position | ||
) |
iter tree< T, tree_node_allocator >::append_children | ( | iter | position, |
sibling_iterator | from, | ||
sibling_iterator | to | ||
) |
|
inline |
Return iterator to the beginning of the tree.
Definition at line 580 of file tree.hh.
Referenced by tree< T, tree_node_allocator >::empty(), OfxMainContainer::gen_event(), tree< T, tree_node_allocator >::is_in_subtree(), tree< T, tree_node_allocator >::reparent(), tree< T, tree_node_allocator >::size(), and tree< T, tree_node_allocator >::subtree().
tree< T, tree_node_allocator >::sibling_iterator tree< T, tree_node_allocator >::begin | ( | const iterator_base & | pos | ) | const |
tree< T, tree_node_allocator >::fixed_depth_iterator tree< T, tree_node_allocator >::begin_fixed | ( | const iterator_base & | pos, |
unsigned int | dp | ||
) | const |
tree< T, tree_node_allocator >::sibling_iterator tree< T, tree_node_allocator >::child | ( | const iterator_base & | position, |
unsigned int | num | ||
) | const |
void tree< T, tree_node_allocator >::clear |
int tree< T, tree_node_allocator >::depth | ( | const iterator_base & | it | ) | const |
bool tree< T, tree_node_allocator >::empty |
|
inline |
Return iterator to the end of the tree.
Definition at line 586 of file tree.hh.
Referenced by tree< T, tree_node_allocator >::begin(), tree< T, tree_node_allocator >::empty(), OfxMainContainer::gen_event(), tree< T, tree_node_allocator >::is_in_subtree(), tree< T, tree_node_allocator >::reparent(), tree< T, tree_node_allocator >::reparent(), tree< T, tree_node_allocator >::size(), and tree< T, tree_node_allocator >::subtree().
tree< T, tree_node_allocator >::sibling_iterator tree< T, tree_node_allocator >::end | ( | const iterator_base & | pos | ) | const |
tree< T, tree_node_allocator >::fixed_depth_iterator tree< T, tree_node_allocator >::end_fixed | ( | const iterator_base & | pos, |
unsigned int | dp | ||
) | const |
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).
Definition at line 1345 of file tree.hh.
Referenced by tree< T, tree_node_allocator >::equal().
bool tree< T, tree_node_allocator >::equal | ( | const iter & | one, |
const iter & | two, | ||
const iter & | three, | ||
BinaryPredicate | fun | ||
) | const |
bool tree< T, tree_node_allocator >::equal_subtree | ( | const iter & | one, |
const iter & | two | ||
) | const |
bool tree< T, tree_node_allocator >::equal_subtree | ( | const iter & | one, |
const iter & | two, | ||
BinaryPredicate | fun | ||
) | const |
iter tree< T, tree_node_allocator >::erase | ( | iter | it | ) |
Erase element at position pointed to by iterator, return incremented iterator.
Definition at line 549 of file tree.hh.
Referenced by tree< T, tree_node_allocator >::clear(), tree< T, tree_node_allocator >::move_ontop(), and tree< T, tree_node_allocator >::replace().
void tree< T, tree_node_allocator >::erase_children | ( | const iterator_base & | it | ) |
Erase all children of the node pointed to by iterator.
Definition at line 530 of file tree.hh.
Referenced by tree< T, tree_node_allocator >::erase(), tree< T, tree_node_allocator >::erase_children(), and tree< T, tree_node_allocator >::replace().
iter tree< T, tree_node_allocator >::flatten | ( | iter | position | ) |
unsigned int tree< T, tree_node_allocator >::index | ( | sibling_iterator | it | ) | const |
iter 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 828 of file tree.hh.
Referenced by tree< T, tree_node_allocator >::insert_subtree(), and tree< T, tree_node_allocator >::set_head().
tree< T, tree_node_allocator >::sibling_iterator tree< T, tree_node_allocator >::insert | ( | sibling_iterator | position, |
const T & | x | ||
) |
iter tree< T, tree_node_allocator >::insert_after | ( | iter | position, |
const T & | x | ||
) |
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.
Definition at line 915 of file tree.hh.
Referenced by tree< T, tree_node_allocator >::append_children(), tree< T, tree_node_allocator >::merge(), and tree< T, tree_node_allocator >::replace().
bool tree< T, tree_node_allocator >::is_in_subtree | ( | const iterator_base & | position, |
const iterator_base & | begin, | ||
const iterator_base & | end | ||
) | const |
bool tree< T, tree_node_allocator >::is_valid | ( | const iterator_base & | it | ) | const |
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.
Definition at line 1242 of file tree.hh.
Referenced by tree< T, tree_node_allocator >::merge().
iter tree< T, tree_node_allocator >::move_after | ( | iter | target, |
iter | source | ||
) |
iter tree< T, tree_node_allocator >::move_before | ( | iter | target, |
iter | source | ||
) |
iter tree< T, tree_node_allocator >::move_ontop | ( | iter | target, |
iter | source | ||
) |
iter tree< T, tree_node_allocator >::next_at_same_depth | ( | iter | position | ) | const |
iter tree< T, tree_node_allocator >::next_sibling | ( | iter | position | ) | const |
unsigned int tree< T, tree_node_allocator >::number_of_children | ( | const iterator_base & | it | ) | const |
unsigned int tree< T, tree_node_allocator >::number_of_siblings | ( | const iterator_base & | it | ) | const |
iter tree< T, tree_node_allocator >::parent | ( | iter | position | ) | const |
Return iterator to the parent of a node.
Definition at line 668 of file tree.hh.
Referenced by tree< T, tree_node_allocator >::merge(), and tree< T, tree_node_allocator >::replace().
iter tree< T, tree_node_allocator >::previous_sibling | ( | iter | position | ) | const |
iter tree< T, tree_node_allocator >::reparent | ( | iter | position, |
iter | from | ||
) |
iter 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 1094 of file tree.hh.
Referenced by tree< T, tree_node_allocator >::reparent().
iter tree< T, tree_node_allocator >::replace | ( | iter | position, |
const iterator_base & | from | ||
) |
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.
Definition at line 935 of file tree.hh.
Referenced by tree< T, tree_node_allocator >::append_child(), tree< T, tree_node_allocator >::insert_subtree(), and tree< T, tree_node_allocator >::subtree().
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 | ||
) |
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.
Definition at line 820 of file tree.hh.
Referenced by tree< T, tree_node_allocator >::subtree().
int tree< T, tree_node_allocator >::size |
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).
Definition at line 1271 of file tree.hh.
Referenced by tree< T, tree_node_allocator >::sort().
void tree< T, tree_node_allocator >::sort | ( | sibling_iterator | from, |
sibling_iterator | to, | ||
StrictWeakOrdering | comp, | ||
bool | deep = false |
||
) |
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.
Definition at line 1391 of file tree.hh.
Referenced by tree< T, tree_node_allocator >::insert_subtree().
void tree< T, tree_node_allocator >::subtree | ( | tree< T, tree_node_allocator > & | tmp, |
sibling_iterator | from, | ||
sibling_iterator | to | ||
) | const |
void tree< T, tree_node_allocator >::swap | ( | sibling_iterator | it | ) |