Claw  1.7.3
Classes | Public Types | Public Member Functions | List of all members
claw::trie< T, Comp > Class Template Reference

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.

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.

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.

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.

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.

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.

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.


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