Overview     Usage     Performance Notes     Links tst 0.68 - 23 Jan 2009

tst_iterator_base Class Template Reference

List of all members.


Detailed Description

template<class NodeListT, class StringT, class TraitsT = inorder_seek<NodeListT, StringT>>
class containers::tst_detail::tst_iterator_base< NodeListT, StringT, TraitsT >

Implements forward and backward iteration in lexical order.

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_typereference
typedef const value_typeconst_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_typekey () 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_typekey () 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 nodecurrent_node () const
const NodeListnodes () const
node_index node_count () const
const nodecurrent_node () const
const nodeget_node (node_index nid) const
const NodeListnodes () 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_typeretrieve_key_string (node_index nid)
 Recover key string by walking nodes backward, starting from an end-node.

Private Attributes

const NodeListm_nodes
node_index m_current_node
string_type m_current_key

Friends

class ternary_tree< StringT, DataT, CompT, AllocT >


Member Typedef Documentation

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 const value_type& const_reference

typedef ternary_tree<StringT, DataT, CompT, AllocT> tst [private]

typedef tst::node node [private]

typedef tst::NodeList NodeList [private]


Constructor & Destructor Documentation

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]


Member Function Documentation

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


Friends And Related Function Documentation

friend class ternary_tree< StringT, DataT, CompT, AllocT > [friend]


Member Data Documentation

const NodeList * m_nodes [private]


ternary_tree 0.68 -- by rasmus ekman -- Page generated with Doxygen 1.5.6 on 23 Jan 2009