CLAW Library (a C++ Library Absolutely Wonderful) 1.5.5
Classes | Public Types | Public Member Functions | Private Types | Private Attributes | Static Private Attributes

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

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.

{
  m_size = 0;
  m_tree = NULL;

  assert(empty());
} // trie() [constructor]
template<class T , class Comp >
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.

{
  if (that.m_tree)
    m_tree = new trie_node( *that.m_tree );
  else
    m_tree = NULL;

  m_size = that.m_size;
} // trie() [copy constructor]
template<class T , class Comp >
claw::trie< T, Comp >::~trie ( )

Trie destructor.

Definition at line 106 of file trie.tpp.

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

{
  if (m_tree)
    delete m_tree;
} // ~trie() [destructor]

Member Function Documentation

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

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.

{
  if (m_tree)
    {
      delete m_tree;
      m_tree = NULL;
      m_size = 0;
    }
} // clear()
template<class T , class Comp >
template<class InputIterator >
unsigned int claw::trie< T, Comp >::count ( InputIterator  first,
InputIterator  last 
)

Gets a word count.

Remarks:
Type requirements :
  • *InputIterator is T.
Parameters:
firstFirst item of the word.
lastItem 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.

{
  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()
template<class T , class Comp >
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()
template<class T , class Comp >
template<class InputIterator >
void claw::trie< T, Comp >::insert ( InputIterator  first,
InputIterator  last 
)

Add a word to the structure.

Remarks:
Type requirements :
  • *InputIterator is T.
Parameters:
firstFirst item of the word.
lastItem 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.

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

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 [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: