claw::trie< T, Comp > Class Template Reference

This class is a trie tree. More...

#include <trie.hpp>

List of all members.

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

Detailed Description

template<class T, class Comp = std::equal_to<T>>
class claw::trie< T, Comp >

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.


Member Typedef Documentation

template<class T, class Comp = std::equal_to<T>>
typedef trie_node* claw::trie< T, Comp >::trie_node_ptr [private]

Definition at line 95 of file trie.hpp.

template<class T, class Comp = std::equal_to<T>>
typedef Comp claw::trie< T, Comp >::value_equal_to

Definition at line 92 of file trie.hpp.

template<class T, class Comp = std::equal_to<T>>
typedef const T claw::trie< T, Comp >::value_type

Definition at line 91 of file trie.hpp.


Constructor & Destructor Documentation

template<class T , class Comp >
claw::trie< T, Comp >::trie (  )  [inline]

Trie constructor.

Postcondition:
empty()

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.

00079 {
00080   m_size = 0;
00081   m_tree = NULL;
00082 
00083   assert(empty());
00084 } // trie() [constructor]

template<class T , class Comp >
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.

00092 {
00093   if (that.m_tree)
00094     m_tree = new trie_node( *that.m_tree );
00095   else
00096     m_tree = NULL;
00097 
00098   m_size = that.m_size;
00099 } // trie() [copy constructor]

template<class T , class Comp >
claw::trie< T, Comp >::~trie (  )  [inline]

Trie destructor.

Definition at line 106 of file trie.tpp.

References claw::trie< T, Comp >::m_tree.

00107 {
00108   if (m_tree)
00109     delete m_tree;
00110 } // ~trie() [destructor]


Member Function Documentation

template<class T , class Comp >
void claw::trie< T, Comp >::clear (  )  [inline]

Clear the trie.

Postcondition:
this->empty() == true

Definition at line 138 of file trie.tpp.

References claw::trie< T, Comp >::m_size, and claw::trie< T, Comp >::m_tree.

00139 {
00140   if (m_tree)
00141     {
00142       delete m_tree;
00143       m_tree = NULL;
00144       m_size = 0;
00145     }
00146 } // clear()

template<class T , class Comp >
template<class InputIterator >
unsigned int claw::trie< T, Comp >::count ( InputIterator  first,
InputIterator  last 
) [inline]

Gets a word count.

Remarks:
Type requirements :
  • *InputIterator is T.
Parameters:
first First item of the word.
last Item just after the last to find.
Precondition:
first != last

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

template<class T , class Comp >
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()

template<class T , class Comp >
template<class InputIterator >
void claw::trie< T, Comp >::insert ( InputIterator  first,
InputIterator  last 
) [inline]

Add a word to the structure.

Remarks:
Type requirements :
  • *InputIterator is T.
Parameters:
first First item of the word.
last Item just after the last to add.
Precondition:
first != last
Postcondition:
!empty() && count(first, last) == old(count(first, last)) + 1

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

template<class T , class Comp >
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()


Member Data Documentation

template<class T, class Comp = std::equal_to<T>>
unsigned int claw::trie< T, Comp >::m_size [private]
template<class T, class Comp = std::equal_to<T>>
trie_node_ptr claw::trie< T, Comp >::m_tree [private]
template<class T, class Comp = std::equal_to<T>>
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().


The documentation for this class was generated from the following files:

Generated on 9 Nov 2009 for CLAW Library (a C++ Library Absolutely Wonderful) by  doxygen 1.6.1