Overview     Usage     Performance Notes     Links tst 0.68 - 23 Jan 2009

inorder_seek Struct Template Reference

List of all members.


Detailed Description

template<class NodeListT, class StringT>
struct containers::tst_detail::inorder_seek< NodeListT, StringT >

tst in-order iterator

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


Member Typedef Documentation

typedef NodeListT::value_type node

typedef NodeListT::size_type node_index

typedef StringT string_type


Member Function Documentation

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