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.

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

ant
antagonize
antagonism
ant It will use as much memory space as
antagonize
antagonism Nodes for "ant" are shared between words, likewise for "antagoni" for the two last word, and a counter is set for each word. So "ant" will have a count of 2.
Remarks:
Type requirements :
- T is EquallyComparable ;
- Comp is a binary predicate such that Comp(T a,T b) == true if a == b.
Invariant:
empty <=> (size()==0)

Author:
Julien Jorge

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:

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.

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

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.

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