Claw  1.7.3
Classes | Public Types | Public Member Functions
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.

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: