CLAW Library (a C++ Library Absolutely Wonderful) 1.5.5
|
This class is a trie tree. More...
#include <trie.hpp>
Classes | |
struct | trie_node |
Node of our trie. Left subtree will be other suggestions for the current position, right subtree will be following items for the word seen from the root to here. More... | |
Public Types | |
typedef const T | value_type |
typedef Comp | value_equal_to |
Public Member Functions | |
trie () | |
Trie constructor. | |
trie (const trie< T, Comp > &that) | |
~trie () | |
Trie destructor. | |
unsigned int | size () const |
Gets size (words count) of the structure. | |
bool | empty () const |
Tell if the structure is empty or not. | |
void | clear () |
Clear the trie. | |
template<class InputIterator > | |
void | insert (InputIterator first, InputIterator last) |
Add a word to the structure. | |
template<class InputIterator > | |
unsigned int | count (InputIterator first, InputIterator last) |
Gets a word count. | |
Private Types | |
typedef trie_node * | trie_node_ptr |
Private Attributes | |
trie_node_ptr | m_tree |
Main structure. | |
unsigned int | m_size |
Words count. | |
Static Private Attributes | |
static value_equal_to | s_value_equal_to |
Function object use to check if nodes have the same value. |
This class is a trie tree.
Trie trees are used for storage and count of linear datas with similar prefixes, typically words. For example, if you insert words
typedef trie_node* claw::trie< T, Comp >::trie_node_ptr [private] |
typedef Comp claw::trie< T, Comp >::value_equal_to |
typedef const T claw::trie< T, Comp >::value_type |
claw::trie< T, Comp >::trie | ( | ) |
Trie constructor.
Definition at line 78 of file trie.tpp.
References claw::trie< T, Comp >::empty(), claw::trie< T, Comp >::m_size, and claw::trie< T, Comp >::m_tree.
claw::trie< T, Comp >::trie | ( | const trie< T, Comp > & | that | ) |
Definition at line 91 of file trie.tpp.
References claw::trie< T, Comp >::m_size, and claw::trie< T, Comp >::m_tree.
claw::trie< T, Comp >::~trie | ( | ) |
void claw::trie< T, Comp >::clear | ( | ) |
Clear the trie.
Definition at line 138 of file trie.tpp.
References claw::trie< T, Comp >::m_size, and claw::trie< T, Comp >::m_tree.
unsigned int claw::trie< T, Comp >::count | ( | InputIterator | first, |
InputIterator | last | ||
) |
Gets a word count.
first | First item of the word. |
last | Item just after the last to find. |
Definition at line 206 of file trie.tpp.
References claw::trie< T, Comp >::trie_node::count, claw::binary_node< U >::left, claw::trie< T, Comp >::m_tree, claw::binary_node< U >::right, and claw::trie< T, Comp >::s_value_equal_to.
{ assert( first != last ); trie_node_ptr* p = & m_tree; // for tree search trie_node_ptr last_node = NULL; // last node of the word // Try to find the word while ( *p && (first!=last) ) if ( s_value_equal_to((*p)->value, *first) ) { last_node = *p; p = & (*p)->right; ++first; } else p = & (*p)->left; // found ? if (first==last) return last_node->count; else return 0; } // count()
bool claw::trie< T, Comp >::empty | ( | ) | const |
Tell if the structure is empty or not.
Definition at line 127 of file trie.tpp.
References claw::trie< T, Comp >::m_tree.
Referenced by claw::trie< T, Comp >::trie().
{ return m_tree==NULL; } // empty()
void claw::trie< T, Comp >::insert | ( | InputIterator | first, |
InputIterator | last | ||
) |
Add a word to the structure.
first | First item of the word. |
last | Item just after the last to add. |
Definition at line 160 of file trie.tpp.
References claw::trie< T, Comp >::trie_node::count, claw::binary_node< U >::left, claw::trie< T, Comp >::m_size, claw::trie< T, Comp >::m_tree, claw::binary_node< U >::right, and claw::trie< T, Comp >::s_value_equal_to.
{ assert( first != last ); trie_node_ptr* p = &m_tree; // for tree search trie_node_ptr last_node = NULL; // last node of the inserted word // Try to insert a maximum of items while ( *p && (first!=last) ) if ( s_value_equal_to((*p)->value, *first) ) { last_node = *p; p = & (*p)->right; ++first; } else p = & (*p)->left; // If we haven't inserted the full word, // create the whole subtree. while (first != last) { *p = new trie_node(*first); last_node = *p; ++first; p = & (*p)->right; } ++(last_node->count); // Don't forget to increase words count. ++m_size; } // insert()
unsigned int claw::trie< T, Comp >::size | ( | ) | const |
Gets size (words count) of the structure.
Definition at line 117 of file trie.tpp.
References claw::trie< T, Comp >::m_size.
{ return m_size; } // size()
unsigned int claw::trie< T, Comp >::m_size [private] |
Words count.
Definition at line 122 of file trie.hpp.
Referenced by claw::trie< T, Comp >::clear(), claw::trie< T, Comp >::insert(), claw::trie< T, Comp >::size(), and claw::trie< T, Comp >::trie().
trie_node_ptr claw::trie< T, Comp >::m_tree [private] |
Main structure.
Definition at line 119 of file trie.hpp.
Referenced by claw::trie< T, Comp >::clear(), claw::trie< T, Comp >::count(), claw::trie< T, Comp >::empty(), claw::trie< T, Comp >::insert(), claw::trie< T, Comp >::trie(), and claw::trie< T, Comp >::~trie().
claw::trie< T, Comp >::value_equal_to claw::trie< T, Comp >::s_value_equal_to [static, private] |
Function object use to check if nodes have the same value.
Definition at line 116 of file trie.hpp.
Referenced by claw::trie< T, Comp >::count(), and claw::trie< T, Comp >::insert().