Overview     Usage     Performance Notes     Links tst 0.68 - 23 Jan 2009

ternary_tree Class Template Reference

List of all members.


Detailed Description

template<class StringT, class DataT, class CompT = std::less<typename StringT::value_type>, class AllocT = std::allocator<DataT>>
class containers::ternary_tree< StringT, DataT, CompT, AllocT >

Ternary search tree (trie) is a sorted container for strings, with advanced search possibilities (wildcard and near-match searches), and fast lookup (similar to hash_map, 3-6 times faster than map) - It is typically used for dictionaries.

A ternary tree is a Structured Associative Container. This means that its key type is required to be a Forward Container, and that the tree uses a comparator to establish a strict weak ordering among key::value_type elements (rather than on whole keys). This allows searches involving parts of keys, ie with shared prefix or with shared middle parts.

ternary_tree is a Unique Associative Container. Note that it is not Pair Associative, so the value that is returned when dereferencing an iterator is not a std::pair<const Key, Data> as for map or unsorted_map. Instead the Data value is returned. To get the key that a ternary_tree iterator is positioned at, iterator specifies member function key() - see tst_detail::iter_method_forward.

ternary_tree is a Sorted, and thus by implication a Reversible Container. While iteration is amortized constant time, it is often slower than other Associative containers since it must walk several key element nodes to find next key endnode. The iteration cost factor is proportional to node_count() / total_key_length().

Exception safety

ternary_tree generally conforms to standard Associative Container exception guarantees:

Controlling macros

See further Implementation Details

Balanced and unbalanced trees

It should be noted that insertion order affects tree performance: After sorted (lexicographical) insertion, lookup is sometimes 50-100% slower, while iterators are (always) 50-90% faster than with random-order string insertion. There is currently no support for rebalancing the tree.

Public Types

enum  { wildcard_char = char_type('?') }
 Default wildcard for partial_match_search. More...
typedef StringT key_type
typedef StringT::value_type char_type
typedef CompT char_compare
typedef DataT value_type
typedef DataT mapped_type
typedef AllocT allocator_type
typedef AllocT::pointer pointer
typedef AllocT::const_pointer const_pointer
typedef AllocT::reference reference
typedef AllocT::const_reference const_reference
typedef AllocT::difference_type difference_type
typedef AllocT::size_type size_type
typedef node::node_index node_index
 Dependent type, defined by the macro TST_NODE_COUNT_TYPE (default: size_type).
typedef std::vector< node,
typename
allocator_type::template
rebind< node >::other > 
NodeList
 Impl note: nodes are stored in vector, effectively working as pool allocator. node_index vector offsets are used instead of pointers.
typedef
tst_detail::tst_iterator_base
< NodeList, string_type
tst_iterator_base
 typedef tst_detail::tst_iterator_base<StringT, DataT, CompT, AllocT> tst_iterator_base;
typedef
TST_ITERATOR_FACADE_BEGIN
iterators::iterator_wrapper
< tst_iterator_base,
iterators::nonconst_traits
< value_type >
> TST_ITERATOR_FACADE_END 
iterator
typedef
TST_ITERATOR_FACADE_BEGIN
iterators::iterator_wrapper
< tst_iterator_base,
iterators::const_traits
< value_type >
> TST_ITERATOR_FACADE_END 
const_iterator
typedef std::reverse_iterator
< iterator
reverse_iterator
typedef std::reverse_iterator
< const_iterator
const_reverse_iterator
typedef search_results_list
< ternary_tree, iterator
search_results_list

Public Member Functions

Construct, copy, destroy
 ternary_tree (const char_compare &comp=char_compare(), const allocator_type &alloc=allocator_type())
template<class InputIterator>
 ternary_tree (InputIterator first, InputIterator last, const char_compare &comp=char_compare(), const allocator_type &alloc=allocator_type())
 ternary_tree (const ternary_tree &other)
 ~ternary_tree ()
ternary_treeoperator= (const ternary_tree &other)
allocator_type get_allocator () const
 Returns a copy of the allocator used to construct the tree.
Iterators
Includes C++0x methods cbegin, cend, crbegin, crend to make it easier to access const iterators.

iterator begin ()
const_iterator begin () const
iterator end ()
const_iterator end () const
reverse_iterator rbegin ()
const_reverse_iterator rbegin () const
reverse_iterator rend ()
const_reverse_iterator rend () const
const_iterator cbegin () const
const_iterator cend () const
const_reverse_iterator crbegin () const
const_reverse_iterator crend () const
Capacity
bool empty () const
size_type size () const
size_type max_size () const
Element access
mapped_typeoperator[] (const key_type &key)
 Inserts a key into the tree and returns a mutable reference to its mapped_value.
Modifiers
std::pair< iterator, bool > insert (const std::pair< key_type, value_type > &val)
 Returns a pair whose bool component returns true if an insertion was made and false if the tree already contained an an equivalent key.
template<class InputIterator>
void insert (InputIterator first, InputIterator last)
 Insert a range from another ternary_tree (or any iterator to pair with same key_type, mapped_type).
void insert (const_iterator first, const_iterator last)
iterator insert (iterator where, const std::pair< key_type, value_type > &val)
 Associative Container method, we do not use hint, so pointless.
size_type erase (const key_type &key)
 Makes key unreachable, but usually does not reclaim nodes to memory pool.
iterator erase (iterator it)
 Makes key unreachable, but usually does not reclaim nodes to memory pool.
iterator erase (iterator first, iterator last)
 Erases a range of values - makes keys unreachable, but usually does not reclaim nodes to memory pool (currently just removes each in a loop, could try better wholesale node removal).
void swap (ternary_tree &other)
void clear ()
Sorted Associative Container methods.
const_iterator find (const key_type &key) const
 Returns const_iterator to key, or end() if not found.
iterator find (const key_type &key)
 Returns mutable iterator to key, or end() if not found.
iterator lower_bound (const key_type &key)
 Returns an iterator to the first element in a map with a key value that is equal to or greater than that of the specified key.
iterator upper_bound (const key_type &key)
 Returns an iterator to the first element in a map with a key value that is greater than the specified key.
const_iterator lower_bound (const key_type &key) const
const_iterator upper_bound (const key_type &key) const
std::pair< iterator, iteratorequal_range (const key_type &key)
 Returns a pair of iterators respectively to the first element in a map with a key that is equal to or greater than the specified key, and a value that is greater than key.
std::pair< const_iterator,
const_iterator
equal_range (const key_type &key) const
size_type count (const key_type &key) const
 Returns count of key values in tree - returns 0 or 1.
Structured Container search methods [deprecated]
These searches are possible by storing key elements in strict weak ordering, anchored at beginning of keys. This allows sub-key searches, ie searching for keys with matching subparts (ie first and last letter of a four-letter string must match, or keys differing from search string in at most n letters).

Complexity of sub-key searches are proportional to the "breadth" of the search. Specifying that more than about 10% of key elements may differ can lead to the search operation traversing large parts of the tree. The front anchoring of key elements also have the consequence that prefix matches are same cost as find operation (log in tree size), while suffix searches are linear in tree size.

std::pair< iterator, iteratorprefix_range (const key_type &prefix)
 Returns a pair of iterators, the first points to the first key that begins with the prefix (or end()), the second to the string following the last string that begins with prefix.
std::pair< const_iterator,
const_iterator
prefix_range (const key_type &prefix) const
template<class CharIter>
iterator longest_match (CharIter &first, CharIter last)
 Returns the longest key that matches the beginning of the key element range (or end(), if none is found).
template<class CharIter>
const_iterator longest_match (CharIter &first, CharIter last) const
search_results_list create_search_results () const
 Factory method for use with wrapper classes.
template<class OutputIter>
OutputIter partial_match_search (const key_type &key, OutputIter results, char_type wildcard=wildcard_char) const
 Partial match search - supports wildcard characters (default: '?') Proxies for iterators to the found strings are pushed at the output iterator.
template<class OutputIter>
OutputIter hamming_search (const key_type &key, OutputIter results, size_type dist) const
 Hamming search: Finds all keys differing from key in at most dist characters (as an extension to strict hamming search, this includes matching but shorter/longer keys).
template<class OutputIter>
OutputIter levenshtein_search (const key_type &key, OutputIter results, size_type dist) const
 Levenshtein search: Finds all strings differing from key in at most dist characters.
template<class OutputIter>
OutputIter combinatorial_search (const key_type &key, OutputIter results, size_type wildcards=0) const
 Combinatorial, or "scrabble" search: Finds all keys containing the characters in the search string.
Observers
ternary_tree defines a key_compare class with same semantics as Sorted Associative Containers.

Note that there is no value_compare type - the value_type does not contain the key.

char_compare char_comp () const
 Returns a copy of the key element comparator object.
key_compare key_comp () const
 Returns a copy of the key_compare class.
size_type node_count () const
 Returns number of nodes in tree.
size_type item_count () const
 Returns number of string-value pairs (alias for size()).
size_type total_key_length () const
 Returns sum of lengths of all keys inserted into tree.
size_type longest_key () const
 Returns length of longest key ever inserted into tree (if key was erased, this value is not updated).
Container comparison.
bool operator== (const ternary_tree &other) const
bool operator< (const ternary_tree &other) const

Static Public Member Functions

static std::ostream & print_node (std::ostream &ostr, const node &n)

Private Types

typedef std::basic_string
< char_type, std::char_traits
< char_type >, typename
allocator_type::template
rebind< char_type >::other > 
string_type
 Used for cached key, since key_type is only req to be Forward Container, and we need push_back(), pop_back() methods (in iterator and in a search method).
typedef
tst_detail::size_policy_node
< char_type, mapped_type,
allocator_type,
TST_NODE_COUNT_TYPE >
::node_type 
node
 Node size only configurable by code change and recompile (FIXME).

Private Member Functions

iterator last_item ()
const_iterator last_item () const
bool less (char_type a, char_type b) const
 test characters for sort order.
template<class CharIter>
find_result find_impl (CharIter &first, CharIter last) const
 This is the iteration master service for insert and partial match, etc.
template<class CharIter>
node_index insert_impl (CharIter first, CharIter last)
 insert chars, returns at_end node index
template<class CharIter>
node_index insert_append (find_result &found, CharIter first, CharIter last)
 append nodes to find_results point
template<class CharIter>
node_index subscript_insert (CharIter first, CharIter last)
 Support operator[].
node_index erase_impl (node_index erasedindex, size_type keylen)
 Returns index of last disabled node (that could not be released).
const_iterator lower_bound_impl (const key_type &key) const
const_iterator upper_bound_impl (const key_type &key) const
std::pair< const_iterator,
const_iterator
equal_range_impl (const key_type &key) const
template<class CharIter>
std::pair< const_iterator,
const_iterator
prefix_range_impl (CharIter first, CharIter last) const
 prefix match implementation
template<class CharIter>
node_index longest_match_impl (CharIter &first, CharIter last) const
 longest match implementation
template<class InputIter, class OutputIter>
void partial_match_search_impl (node_index nid, InputIter first, InputIter last, OutputIter results, char_type wildcard) const
 partial match search implementation
template<class InputIter, class OutputIter>
void hamming_search_impl (node_index nid, InputIter first, InputIter last, OutputIter results, int dist) const
 hamming_search implementation
template<class InputIter, class OutputIter>
bool levenshtein_search_impl (node_index nid, tst_detail::levenshtein_search_info< InputIter > &info, InputIter last, OutputIter results) const
 levenshtein_search implementation
template<class String, class OutputIter>
void combinatorial_search_impl (node_index nid, const String &str, OutputIter results, size_type jokers) const
 combinatorial_search implementation

Private Attributes

NodeList m_nodes
char_compare m_comparator
allocator_type m_allocator
size_type m_item_count
 Keeps stats for tree insertion.
size_type m_total_key_length
 Keeps stats for tree insertion.
size_type m_longest_key
 Keeps stats for tree insertion.
tst_iterator_base m_last_item
 Index to last key endnode: must be maintained to have const-time reverse iteration.

Friends

class tst_detail::tst_iterator_base< NodeList, string_type >
 friend class tst_detail::tst_iterator_base<StringT, DataT, CompT, AllocT>;
struct tst_detail::iter_method_forward< ternary_tree >
 Needed to construct iterators for (eg) structured_multimap.
class search_results_list

Related Functions

(Note that these are not member functions.)

template<class S, class D, class C, class A>
bool operator== (ternary_tree< S, D, C, A > const &x, ternary_tree< S, D, C, A > const &y)
template<class S, class D, class C, class A>
bool operator!= (ternary_tree< S, D, C, A > const &x, ternary_tree< S, D, C, A > const &y)
template<class S, class D, class C, class A>
bool operator< (ternary_tree< S, D, C, A > const &x, ternary_tree< S, D, C, A > const &y)
template<class S, class D, class C, class A>
bool operator> (ternary_tree< S, D, C, A > const &x, ternary_tree< S, D, C, A > const &y)
template<class S, class D, class C, class A>
bool operator<= (ternary_tree< S, D, C, A > const &x, ternary_tree< S, D, C, A > const &y)
template<class S, class D, class C, class A>
bool operator>= (ternary_tree< S, D, C, A > const &x, ternary_tree< S, D, C, A > const &y)
template<class S, class D, class C, class A>
std::ostream & operator<< (std::ostream &ostr, typename ternary_tree< S, D, C, A >::node const &node)

Classes

struct  find_result
class  key_compare
 Key comparator, defined in terms of a lexicographical_compare using the char_compare object. More...


Member Typedef Documentation

typedef StringT key_type

typedef StringT::value_type char_type

typedef CompT char_compare

typedef DataT value_type

typedef DataT mapped_type

typedef AllocT allocator_type

typedef AllocT::pointer pointer

typedef AllocT::const_pointer const_pointer

typedef AllocT::reference reference

typedef AllocT::const_reference const_reference

typedef AllocT::difference_type difference_type

typedef AllocT::size_type size_type

typedef std::basic_string<char_type, std::char_traits<char_type>, typename allocator_type::template rebind<char_type>::other > string_type [private]

Used for cached key, since key_type is only req to be Forward Container, and we need push_back(), pop_back() methods (in iterator and in a search method).

typedef tst_detail::size_policy_node<char_type, mapped_type, allocator_type, TST_NODE_COUNT_TYPE >::node_type node [private]

Node size only configurable by code change and recompile (FIXME).

# typedef tst_detail::node<char_type, mapped_type, allocator_type, size_type> node;

typedef node::node_index node_index

Dependent type, defined by the macro TST_NODE_COUNT_TYPE (default: size_type).

typedef std::vector<node, typename allocator_type::template rebind<node>::other> NodeList

Impl note: nodes are stored in vector, effectively working as pool allocator. node_index vector offsets are used instead of pointers.

typedef tst_detail::tst_iterator_base<StringT, DataT, CompT, AllocT> tst_iterator_base;

typedef TST_ITERATOR_FACADE_BEGIN iterators::iterator_wrapper< tst_iterator_base , iterators::nonconst_traits<value_type> > TST_ITERATOR_FACADE_END iterator

typedef TST_ITERATOR_FACADE_BEGIN iterators::iterator_wrapper< tst_iterator_base , iterators::const_traits<value_type> > TST_ITERATOR_FACADE_END const_iterator

typedef std::reverse_iterator<iterator> reverse_iterator

typedef std::reverse_iterator<const_iterator> const_reverse_iterator


Member Enumeration Documentation

anonymous enum

Default wildcard for partial_match_search.

Enumerator:
wildcard_char 


Constructor & Destructor Documentation

ternary_tree ( const char_compare comp = char_compare(),
const allocator_type alloc = allocator_type() 
) [inline, explicit]

ternary_tree ( InputIterator  first,
InputIterator  last,
const char_compare comp = char_compare(),
const allocator_type alloc = allocator_type() 
) [inline]

ternary_tree ( const ternary_tree< StringT, DataT, CompT, AllocT > &  other  )  [inline]

~ternary_tree (  )  [inline]


Member Function Documentation

ternary_tree& operator= ( const ternary_tree< StringT, DataT, CompT, AllocT > &  other  )  [inline]

allocator_type get_allocator (  )  const [inline]

Returns a copy of the allocator used to construct the tree.

iterator begin (  )  [inline]

const_iterator begin (  )  const [inline]

iterator end (  )  [inline]

const_iterator end (  )  const [inline]

reverse_iterator rbegin (  )  [inline]

const_reverse_iterator rbegin (  )  const [inline]

reverse_iterator rend (  )  [inline]

const_reverse_iterator rend (  )  const [inline]

const_iterator cbegin (  )  const [inline]

const_iterator cend (  )  const [inline]

const_reverse_iterator crbegin (  )  const [inline]

const_reverse_iterator crend (  )  const [inline]

bool empty (  )  const [inline]

size_type size (  )  const [inline]

size_type max_size (  )  const [inline]

mapped_type& operator[] ( const key_type key  )  [inline]

Inserts a key into the tree and returns a mutable reference to its mapped_value.

std::pair<iterator, bool> insert ( const std::pair< key_type, value_type > &  val  )  [inline]

Returns a pair whose bool component returns true if an insertion was made and false if the tree already contained an an equivalent key.

void insert ( InputIterator  first,
InputIterator  last 
) [inline]

Insert a range from another ternary_tree (or any iterator to pair with same key_type, mapped_type).

void insert ( const_iterator  first,
const_iterator  last 
) [inline]

iterator insert ( iterator  where,
const std::pair< key_type, value_type > &  val 
) [inline]

Associative Container method, we do not use hint, so pointless.

size_type erase ( const key_type key  )  [inline]

Makes key unreachable, but usually does not reclaim nodes to memory pool.

Postcondition: find(key) returns end(). Does not invalidate any iterators except those pointing to an erased element. If key exists, item_count() is decremented; node_count() usually does not change. If size() == 1, clear() is called to wipe the slate clean.

iterator erase ( iterator  it  )  [inline]

Makes key unreachable, but usually does not reclaim nodes to memory pool.

Postcondition: find(key) returns end(). Does not invalidate any iterators except those pointing to an erased element. If key exists, item_count() is decremented; node_count() usually does not change. If size() == 1, clear() is called to wipe the slate clean.

iterator erase ( iterator  first,
iterator  last 
) [inline]

Erases a range of values - makes keys unreachable, but usually does not reclaim nodes to memory pool (currently just removes each in a loop, could try better wholesale node removal).

Returns iterator as per C++0x

void swap ( ternary_tree< StringT, DataT, CompT, AllocT > &  other  )  [inline]

void clear (  )  [inline]

const_iterator find ( const key_type key  )  const [inline]

Returns const_iterator to key, or end() if not found.

iterator find ( const key_type key  )  [inline]

Returns mutable iterator to key, or end() if not found.

iterator lower_bound ( const key_type key  )  [inline]

Returns an iterator to the first element in a map with a key value that is equal to or greater than that of the specified key.

If key exists, it is returned, else returns the element that has key for a prefix (or end() if no such element exists).

Complexity is that of a find() operation.

See also:
prefix_range

iterator upper_bound ( const key_type key  )  [inline]

Returns an iterator to the first element in a map with a key value that is greater than the specified key.

If key exists, this returns ++key, else it returns the element that has key for a prefix (or end() if no such element exists).

Complexity is that of a find() operation + one iterator increment.

See also:
prefix_range

const_iterator lower_bound ( const key_type key  )  const [inline]

const_iterator upper_bound ( const key_type key  )  const [inline]

std::pair<iterator, iterator> equal_range ( const key_type key  )  [inline]

Returns a pair of iterators respectively to the first element in a map with a key that is equal to or greater than the specified key, and a value that is greater than key.

The first is the lower_bound of the key, and the second is the upper_bound of the key.

Complexity is that of a find() operation + one iterator increment.

See also:
prefix_range

std::pair<const_iterator, const_iterator> equal_range ( const key_type key  )  const [inline]

size_type count ( const key_type key  )  const [inline]

Returns count of key values in tree - returns 0 or 1.

std::pair<iterator, iterator> prefix_range ( const key_type prefix  )  [inline]

Returns a pair of iterators, the first points to the first key that begins with the prefix (or end()), the second to the string following the last string that begins with prefix.

The first iterator is the lower_bound of the key, while the second is the first key that does not share the prefix. In a container with values { "aa", "aaa" "ab" }, equal_range("aa") returns { "aa", "aaa" }, while prefix_match returns { "aa", "ab" }. Worst-case complexity is that of two find(prefix) operations.

See also:
equal_range

std::pair<const_iterator, const_iterator> prefix_range ( const key_type prefix  )  const [inline]

iterator longest_match ( CharIter &  first,
CharIter  last 
) [inline]

Returns the longest key that matches the beginning of the key element range (or end(), if none is found).

The key element iterator first is advanced to the element following the last matched character.

(This method allows using the TST dictionary as a simple tokenizer over first, last.)

Complexity is that of a single find operation.

const_iterator longest_match ( CharIter &  first,
CharIter  last 
) const [inline]

ternary_tree< S, D, C, A >::search_results_list create_search_results (  )  const [inline]

Factory method for use with wrapper classes.

OutputIter partial_match_search ( const key_type key,
OutputIter  results,
char_type  wildcard = wildcard_char 
) const [inline]

Partial match search - supports wildcard characters (default: '?') Proxies for iterators to the found strings are pushed at the output iterator.

A wildcard in search string entails visiting all subtrees of matched node(s). The worst-case complexity of partial match search is therefore O(m * k) * regular-find, where m is size of alphabet, k is number of wildcard characters in search string, and "regular-find" is lookup cost of the rest of the search string. In practice, only a fraction of the alphabet is present except near root level of the tree, but concrete performance is unpredictable. Typical timings are in order of 10 times find(key) per item returned. See article available at Jon Bentley and Robert Sedgewick site .

OutputIter hamming_search ( const key_type key,
OutputIter  results,
size_type  dist 
) const [inline]

Hamming search: Finds all keys differing from key in at most dist characters (as an extension to strict hamming search, this includes matching but shorter/longer keys).

Proxies for iterators to the found strings are pushed at the output iterator.

Searches on values of dist > 20% of average key length are typically expensive, since a large part of the tree is traversed (expensive may mean several microseconds per call).

See also:
http://wikipedia.org/wiki/Hamming_distance

OutputIter levenshtein_search ( const key_type key,
OutputIter  results,
size_type  dist 
) const [inline]

Levenshtein search: Finds all strings differing from key in at most dist characters.

Proxies for iterators to the found strings are pushed at the output iterator.

Searches on values of dist > 20% of average key length are typically expensive, since a large part of the tree is traversed (expensive may mean several microseconds per call).

See also:
http://wikipedia.org/wiki/Levenshtein_distance

OutputIter combinatorial_search ( const key_type key,
OutputIter  results,
size_type  wildcards = 0 
) const [inline]

Combinatorial, or "scrabble" search: Finds all keys containing the characters in the search string.

The optional wildcard count allows mismatch characters (use with care, it increases complexity of the search dramatically).

char_compare char_comp (  )  const [inline]

Returns a copy of the key element comparator object.

key_compare key_comp (  )  const [inline]

Returns a copy of the key_compare class.

size_type node_count (  )  const [inline]

Returns number of nodes in tree.

size_type item_count (  )  const [inline]

Returns number of string-value pairs (alias for size()).

size_type total_key_length (  )  const [inline]

Returns sum of lengths of all keys inserted into tree.

size_type longest_key (  )  const [inline]

Returns length of longest key ever inserted into tree (if key was erased, this value is not updated).

bool operator== ( const ternary_tree< StringT, DataT, CompT, AllocT > &  other  )  const [inline]

bool operator< ( const ternary_tree< StringT, DataT, CompT, AllocT > &  other  )  const [inline]

static std::ostream& print_node ( std::ostream &  ostr,
const node n 
) [static]

iterator last_item (  )  [inline, private]

const_iterator last_item (  )  const [inline, private]

bool less ( char_type  a,
char_type  b 
) const [inline, private]

test characters for sort order.

ternary_tree< S, D, C, A >::find_result find_impl ( CharIter &  first,
CharIter  last 
) const [inline, private]

This is the iteration master service for insert and partial match, etc.

Ternary tree structure The insert_impl method defines primary tree structure.

Returns a type that holds lookup result: index of the last matched node, and a pointer to a node index. If match was successful, find_result.pnid is null, else it points to the hikid or lokid of the matched node that would point to first unmatched char if it were inserted.

The difference from previous contents is inserted as a "twig", a stretch of nodes, and linked from the longest matching prefix. The resulting invariant is: if a char in search string matches a node char, there exists an adjacent next node with another char to test. The only exception is terminal nodes, ending a key, which have a special marker that ensures they cannot match any char in any possible key.

find and iteration are defined to work with the resulting structure as best they can...

This is mentioned due to the problem with erased nodes: When strings are erased, the invariant is broken, and must be mended with a special case: the erased-endnode. This is an endnode with a special marker. It must be silently bypassed by all parties, always taking the same path.

node_index insert_impl ( CharIter  first,
CharIter  last 
) [inline, private]

insert chars, returns at_end node index

ternary_tree< S, D, C, A >::node_index insert_append ( find_result found,
CharIter  first,
CharIter  last 
) [inline, private]

append nodes to find_results point

node_index subscript_insert ( CharIter  first,
CharIter  last 
) [inline, private]

Support operator[].

ternary_tree< S, D, C, A >::node_index erase_impl ( node_index  nid,
size_type  keylen 
) [inline, private]

Returns index of last disabled node (that could not be released).

Scan twig backward looking for branches, unlink all nodes that are not used.

Three distinct cases:

  1. zero branches: twig can be completely unlinked; the hikid/lokid pointer in twig root is set to invalid_index. Check that twig_root is still used, else erase it recursively.
  2. one branch in all of twig. This in turn has two cases:
    • branch occurs in first twig node: relink from twig_root.hi/lokid directly to branched node, then unlink twig.
    • branch occurs in subsequent twig node: close off branch node and erase subsequent twig nodes. If branch is in lokid, set branch node splitchar to zero and move link to hikid.
  3. two or more branches: Just mark branch node erased.

Finally, if erased nodes happen to be at very end of node vector, erase them from vector. If we wanted even more trouble, we could try to swap the erased nodes with last twig in tree.

This is complicated, somewhat brittle code.

const_iterator lower_bound_impl ( const key_type key  )  const [inline, private]

const_iterator upper_bound_impl ( const key_type key  )  const [inline, private]

std::pair<const_iterator, const_iterator> equal_range_impl ( const key_type key  )  const [inline, private]

std::pair< typename ternary_tree< S, D, C, A >::const_iterator, typename ternary_tree< S, D, C, A >::const_iterator > prefix_range_impl ( CharIter  first,
CharIter  last 
) const [inline, private]

prefix match implementation

ternary_tree< S, D, C, A >::node_index longest_match_impl ( CharIter &  first,
CharIter  last 
) const [inline, private]

longest match implementation

void partial_match_search_impl ( node_index  nid,
InputIter  first,
InputIter  last,
OutputIter  results,
char_type  wildcard 
) const [inline, private]

partial match search implementation

Repeats code from find_impl, recursive over hi-lo-eqkid when a wildcard char is matched.

void hamming_search_impl ( node_index  nid,
InputIter  first,
InputIter  last,
OutputIter  results,
int  dist 
) const [inline, private]

hamming_search implementation

bool levenshtein_search_impl ( node_index  nid,
tst_detail::levenshtein_search_info< InputIter > &  info,
InputIter  last,
OutputIter  results 
) const [inline, private]

levenshtein_search implementation

void combinatorial_search_impl ( node_index  nid,
const String &  str,
OutputIter  results,
size_type  jokers 
) const [inline, private]

combinatorial_search implementation


Friends And Related Function Documentation

friend class tst_detail::tst_iterator_base<StringT, DataT, CompT, AllocT>;

friend struct tst_detail::iter_method_forward< ternary_tree > [friend]

Needed to construct iterators for (eg) structured_multimap.

friend class search_results_list [friend]

bool operator== ( ternary_tree< S, D, C, A > const &  x,
ternary_tree< S, D, C, A > const &  y 
) [related]

bool operator!= ( ternary_tree< S, D, C, A > const &  x,
ternary_tree< S, D, C, A > const &  y 
) [related]

bool operator< ( ternary_tree< S, D, C, A > const &  x,
ternary_tree< S, D, C, A > const &  y 
) [related]

bool operator> ( ternary_tree< S, D, C, A > const &  x,
ternary_tree< S, D, C, A > const &  y 
) [related]

bool operator<= ( ternary_tree< S, D, C, A > const &  x,
ternary_tree< S, D, C, A > const &  y 
) [related]

bool operator>= ( ternary_tree< S, D, C, A > const &  x,
ternary_tree< S, D, C, A > const &  y 
) [related]

std::ostream & operator<< ( std::ostream &  ostr,
typename ternary_tree< S, D, C, A >::node const &  node 
) [related]


Member Data Documentation

NodeList m_nodes [private]

Keeps stats for tree insertion.

Keeps stats for tree insertion.

Keeps stats for tree insertion.

Index to last key endnode: must be maintained to have const-time reverse iteration.


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