Overview Usage Performance Notes Links | tst 0.68 - 23 Jan 2009 |
Implements tree in-order bidirectional iteration. If the optional template parameter KeyTrackerT
is provided, it is a BackInsertionSequence that accepts NodeListT
node::char_type
values. (back insertables are eg std::string, vector etc, but here the only methods used are push_back
and empty
)
Public Types | |
typedef NodeListT::value_type | node |
typedef NodeListT::size_type | node_index |
typedef StringT | string_type |
Static Public Member Functions | |
static node_index | find_first_endnode (const NodeListT &nodes, node_index pos, string_type &str) |
Starting from node pos, walk lowest or eq path to next terminal node NOTE: does not increment if pos indexes an end-node! | |
static node_index | find_last_endnode (const NodeListT &nodes, node_index pos, string_type &str) |
Starting from node pos, walk rightmost path to next terminal node - takes us from root to end-value in log time -- Pre: tree is not empty(); Post: m_nodes[nid].at_end() == node::terminal. | |
static node_index | find_forward_path (const NodeListT &nodes, node_index pos, string_type &str) |
Examine parent(s) to find next decrementable path not leading here. Tracks current key value by push_back and erase-end when descending/ascending tree. | |
static node_index | find_backward_path (const NodeListT &nodes, node_index pos, string_type &str) |
Walk backward until find a node with untrodden path (not pointing to current subtree). |
typedef NodeListT::value_type node |
typedef NodeListT::size_type node_index |
typedef StringT string_type |
static node_index find_first_endnode | ( | const NodeListT & | nodes, | |
node_index | pos, | |||
string_type & | str | |||
) | [inline, static] |
Starting from node pos, walk lowest or eq path to next terminal node NOTE: does not increment if pos indexes an end-node!
static node_index find_last_endnode | ( | const NodeListT & | nodes, | |
node_index | pos, | |||
string_type & | str | |||
) | [inline, static] |
Starting from node pos, walk rightmost path to next terminal node - takes us from root to end-value in log time -- Pre: tree is not empty(); Post: m_nodes[nid].at_end() == node::terminal.
static node_index find_forward_path | ( | const NodeListT & | nodes, | |
node_index | pos, | |||
string_type & | str | |||
) | [inline, static] |
Examine parent(s) to find next decrementable path not leading here. Tracks current key value by push_back and erase-end when descending/ascending tree.
static node_index find_backward_path | ( | const NodeListT & | nodes, | |
node_index | pos, | |||
string_type & | str | |||
) | [inline, static] |
Walk backward until find a node with untrodden path (not pointing to current subtree).
Input is a node index where either [nid].at_end() OR parent.at_end() and parent.hikid == nid. Returns index to node where (a) m_current.node = current_node().parent AND m_current.path = m_current.path + 1 (b) m_current.node == m_current.path == invalid_node
Tracks current key value by push_back and pop_back when descending/ascending tree.
ternary_tree 0.68 -- by rasmus ekman -- Page generated with Doxygen 1.5.6 on 23 Jan 2009 |