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