Overview Usage Performance Notes Links | tst 0.68 - 23 Jan 2009 |
Iteration is slightly expensive as it needs to walk nodes, and backtrack to find next value. Complexity of increment is amortized constant time. Actual time taken is O(n) in average length of strings minus string common prefixes.
tst_iterator_base is constructible from a node list and a node index; this is used with values returned from wildcard-match and neighbour-match searches.
iteration_policy defines methods:
Iteration is slightly expensive as it needs to walk nodes, and backtrack to find next value. Complexity of increment is amortized constant time. Actual time taken is O(n) in average length of strings minus string common prefixes.
tst_iterator_base is constructible from a node list and a node index; this is used with values returned from wildcard-match and neighbour-match searches.
Public Types | |
typedef NodeListT::value_type | node |
typedef NodeListT::size_type | node_index |
typedef StringT | string_type |
typedef node::value_type | value_type |
typedef value_type & | reference |
typedef const value_type & | const_reference |
typedef tst::mapped_type | mapped_type |
typedef tst::value_type | value_type |
typedef tst::reference | reference |
typedef tst::const_reference | const_reference |
typedef tst::pointer | pointer |
typedef tst::const_pointer | const_pointer |
typedef tst::node_index | node_index |
typedef tst::key_type | key_type |
typedef tst::char_type | char_type |
typedef tst::string_type | string_type |
Public Member Functions | |
tst_iterator_base () | |
tst_iterator_base (const NodeList &nodes) | |
tst_iterator_base (const NodeList &nodes, node_index index) | |
tst_iterator_base () | |
tst_iterator_base (const NodeList &nodes) | |
tst_iterator_base (const NodeList &nodes, node_index nid, const key_type &key, bool seekend=true) | |
tst_iterator_base (const NodeList &nodes, node_index index) | |
publicly usable interface | |
const string_type & | key () const |
Returns the key at current iterator position - this value changes when iterator is incremented or decremented. | |
reference | value () |
Returns a mutable reference to the value associated with current key. | |
const_reference | value () const |
Returns a const reference to the value associated with current key. | |
iterator_wrapper interface | |
reference | dereference () const |
Called from iterator wrappers - note that mutable reference is returned even though method is const: the iterator wrapper const_traits policy must manage client access rights. | |
void | increment () |
Seek to next end-of-string node (or set to invalid node) Precondition: current node is at_end(). | |
void | decrement () |
Seek to next end-of-string node (or set to invalid node) Precondition: current node is at_end(). | |
bool | equal (const tst_iterator_base &other) const |
void | swap (tst_iterator_base &rhs) |
bool | empty () const |
node_index | tree_position () const |
publicly usable interface | |
const key_type & | key () const |
Returns the key at current iterator position - this value changes when iterator is incremented or decremented. | |
reference | value () |
Returns a mutable reference to the value associated with current key. | |
const_reference | value () const |
Returns a const reference to the value associated with current key. | |
iterator_wrapper interface | |
reference | dereference () const |
Called from iterator wrappers - note that mutable reference is returned even though method is const: the iterator wrapper const_traits policy must manage client access rights. | |
void | increment () |
Seek to next end-of-string node (or set to invalid node) Precondition: current node is at_end(). | |
void | decrement () |
Seek to next end-of-string node (or set to invalid node) Precondition: current node is at_end(). | |
bool | equal (const tst_iterator_base &other) const |
void | swap (tst_iterator_base &rhs) |
bool | empty () const |
node_index | tree_position () const |
Private Types | |
typedef NodeListT | NodeList |
typedef TraitsT | iter_traits |
typedef key_access< NodeListT, StringT > | key_access |
typedef ternary_tree< StringT, DataT, CompT, AllocT > | tst |
typedef tst::node | node |
typedef tst::NodeList | NodeList |
Private Member Functions | |
const node & | current_node () const |
const NodeList & | nodes () const |
node_index | node_count () const |
const node & | current_node () const |
const node & | get_node (node_index nid) const |
const NodeList & | nodes () const |
void | clear () |
node_index | find_forward_path () |
Walk backward until find a node with untrodden path (not pointing to current subtree). | |
node_index | find_last_endnode (node_index nid) |
Starting from node, 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. | |
node_index | find_first_endnode () |
Starting from node, walk lowest or eq path to next terminal node NOTE: does not increment if nid indexes an end-node! | |
node_index | find_backward_path () |
Examine parent(s) to find next decrementable path not leading here. | |
node_index | retrieve_eq_chars (string_type &key, node_index nid) |
Collects all characters until reaching a branch in node tree (parent != self - 1). | |
node_index | skip_non_eq_nodes (node_index nid) const |
Skips over branches in node tree, stopping when parent == self - 1. | |
string_type & | retrieve_key_string (node_index nid) |
Recover key string by walking nodes backward, starting from an end-node. | |
Private Attributes | |
const NodeList * | m_nodes |
node_index | m_current_node |
string_type | m_current_key |
Friends | |
class | ternary_tree< StringT, DataT, CompT, AllocT > |
typedef NodeListT NodeList [private] |
typedef TraitsT iter_traits [private] |
typedef key_access<NodeListT, StringT> key_access [private] |
typedef NodeListT::value_type node |
typedef NodeListT::size_type node_index |
typedef StringT string_type |
typedef node::value_type value_type |
typedef value_type& reference |
typedef const value_type& const_reference |
typedef ternary_tree<StringT, DataT, CompT, AllocT> tst [private] |
typedef tst::NodeList NodeList [private] |
typedef tst::mapped_type mapped_type |
typedef tst::value_type value_type |
typedef tst::reference reference |
typedef tst::const_reference const_reference |
typedef tst::pointer pointer |
typedef tst::const_pointer const_pointer |
typedef tst::node_index node_index |
typedef tst::key_type key_type |
typedef tst::char_type char_type |
typedef tst::string_type string_type |
tst_iterator_base | ( | ) | [inline] |
tst_iterator_base | ( | const NodeList & | nodes | ) | [inline, explicit] |
tst_iterator_base | ( | const NodeList & | nodes, | |
node_index | index | |||
) | [inline] |
tst_iterator_base | ( | ) | [inline] |
tst_iterator_base | ( | const NodeList & | nodes | ) | [inline, explicit] |
tst_iterator_base | ( | const NodeList & | nodes, | |
node_index | nid, | |||
const key_type & | key, | |||
bool | seekend = true | |||
) | [inline] |
tst_iterator_base | ( | const NodeList & | nodes, | |
node_index | index | |||
) | [inline] |
const string_type& key | ( | ) | const [inline] |
Returns the key at current iterator position - this value changes when iterator is incremented or decremented.
reference value | ( | ) | [inline] |
Returns a mutable reference to the value associated with current key.
const_reference value | ( | ) | const [inline] |
Returns a const reference to the value associated with current key.
reference dereference | ( | ) | const [inline] |
Called from iterator wrappers - note that mutable reference is returned even though method is const: the iterator wrapper const_traits policy must manage client access rights.
void increment | ( | ) | [inline] |
Seek to next end-of-string node (or set to invalid node) Precondition: current node is at_end().
void decrement | ( | ) | [inline] |
Seek to next end-of-string node (or set to invalid node) Precondition: current node is at_end().
bool equal | ( | const tst_iterator_base< NodeListT, StringT, TraitsT > & | other | ) | const [inline] |
void swap | ( | tst_iterator_base< NodeListT, StringT, TraitsT > & | rhs | ) | [inline] |
bool empty | ( | ) | const [inline] |
node_index tree_position | ( | ) | const [inline] |
const node& current_node | ( | ) | const [inline, private] |
const NodeList& nodes | ( | ) | const [inline, private] |
const key_type& key | ( | ) | const [inline] |
Returns the key at current iterator position - this value changes when iterator is incremented or decremented.
reference value | ( | ) | [inline] |
Returns a mutable reference to the value associated with current key.
const_reference value | ( | ) | const [inline] |
Returns a const reference to the value associated with current key.
reference dereference | ( | ) | const [inline] |
Called from iterator wrappers - note that mutable reference is returned even though method is const: the iterator wrapper const_traits policy must manage client access rights.
void increment | ( | ) | [inline] |
Seek to next end-of-string node (or set to invalid node) Precondition: current node is at_end().
void decrement | ( | ) | [inline] |
Seek to next end-of-string node (or set to invalid node) Precondition: current node is at_end().
bool equal | ( | const tst_iterator_base< NodeListT, StringT, TraitsT > & | other | ) | const [inline] |
void swap | ( | tst_iterator_base< NodeListT, StringT, TraitsT > & | rhs | ) | [inline] |
bool empty | ( | ) | const [inline] |
node_index tree_position | ( | ) | const [inline] |
node_index node_count | ( | ) | const [inline, private] |
const node& current_node | ( | ) | const [inline, private] |
const node& get_node | ( | node_index | nid | ) | const [inline, private] |
const NodeList& nodes | ( | ) | const [inline, private] |
void clear | ( | ) | [inline, private] |
node_index find_forward_path | ( | ) | [inline, private] |
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
node_index find_last_endnode | ( | node_index | nid | ) | [inline, private] |
Starting from node, 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.
node_index find_first_endnode | ( | ) | [inline, private] |
Starting from node, walk lowest or eq path to next terminal node NOTE: does not increment if nid indexes an end-node!
node_index find_backward_path | ( | ) | [inline, private] |
Examine parent(s) to find next decrementable path not leading here.
node_index retrieve_eq_chars | ( | string_type & | key, | |
node_index | nid | |||
) | [inline, private] |
Collects all characters until reaching a branch in node tree (parent != self - 1).
node_index skip_non_eq_nodes | ( | node_index | nid | ) | const [inline, private] |
Skips over branches in node tree, stopping when parent == self - 1.
string_type& retrieve_key_string | ( | node_index | nid | ) | [inline, private] |
Recover key string by walking nodes backward, starting from an end-node.
Complexity is key length + log(tree size).
friend class ternary_tree< StringT, DataT, CompT, AllocT > [friend] |
node_index m_current_node [private] |
string_type m_current_key [private] |
ternary_tree 0.68 -- by rasmus ekman -- Page generated with Doxygen 1.5.6 on 23 Jan 2009 |