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. |
Trie trees are used for storage and count of linear datas with similar prefixes, typically words. For example, if you insert words
Definition at line 62 of file trie.hpp.
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 | ( | ) | [inline] |
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 | ) | [inline] |
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 | ( | ) | [inline] |
void claw::trie< T, Comp >::clear | ( | ) | [inline] |
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 | |||
) | [inline] |
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.
00208 { 00209 assert( first != last ); 00210 00211 trie_node_ptr* p = & m_tree; // for tree search 00212 trie_node_ptr last_node = NULL; // last node of the word 00213 00214 // Try to find the word 00215 while ( *p && (first!=last) ) 00216 if ( s_value_equal_to((*p)->value, *first) ) 00217 { 00218 last_node = *p; 00219 p = & (*p)->right; 00220 ++first; 00221 } 00222 else 00223 p = & (*p)->left; 00224 00225 // found ? 00226 if (first==last) 00227 return last_node->count; 00228 else 00229 return 0; 00230 } // count()
bool claw::trie< T, Comp >::empty | ( | ) | const [inline] |
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().
00128 { 00129 return m_tree==NULL; 00130 } // empty()
void claw::trie< T, Comp >::insert | ( | InputIterator | first, | |
InputIterator | last | |||
) | [inline] |
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.
00161 { 00162 assert( first != last ); 00163 00164 trie_node_ptr* p = &m_tree; // for tree search 00165 trie_node_ptr last_node = NULL; // last node of the inserted word 00166 00167 // Try to insert a maximum of items 00168 while ( *p && (first!=last) ) 00169 if ( s_value_equal_to((*p)->value, *first) ) 00170 { 00171 last_node = *p; 00172 p = & (*p)->right; 00173 ++first; 00174 } 00175 else 00176 p = & (*p)->left; 00177 00178 // If we haven't inserted the full word, 00179 // create the whole subtree. 00180 while (first != last) 00181 { 00182 *p = new trie_node(*first); 00183 last_node = *p; 00184 00185 ++first; 00186 p = & (*p)->right; 00187 } 00188 00189 ++(last_node->count); 00190 00191 // Don't forget to increase words count. 00192 ++m_size; 00193 } // insert()
unsigned int claw::trie< T, Comp >::size | ( | ) | const [inline] |
Gets size (words count) of the structure.
Definition at line 117 of file trie.tpp.
References claw::trie< T, Comp >::m_size.
00118 { 00119 return m_size; 00120 } // 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 [inline, 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().