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

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

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

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.

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.

---

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

• trie.hpp
• impl/trie.tpp