DFA_min Class Template Reference

A dynamic minimal acyclic DFA container class. More...

#include <dfa_min.h>

Inheritance diagram for DFA_min:

List of all members.

Public Member Functions
void	clear ()
void	freeze ()
	Get rid of the extra data used for maintaining the automaton minimality.
bool	insert (const basic_string< char_type > &s)
	Add a word defined by a character string.
template<class ForwardI >
bool	insert (ForwardI, ForwardI)
	Add a word defined by a range on a sequence of characters of type char_type.
unsigned int	size () const
unsigned int	wc () const
	word count.

---

Detailed Description

template<typename CharTraits = plain, typename Tag = empty_tag>
class astl::DFA_min< CharTraits, Tag >

A dynamic minimal acyclic DFA container class.

Words can be added keeping the automaton minimal. It does not define the standard DFA interface but a restricted one that allows only word insertions and read-only operations thus enforcing the invariants for the structure integrity to be guaranteed.

Template parameters

Parameter	Description	Default	Requirements
CharTraits	Character traits describing the alphabet that the words are built with.	plain	CharTraits is a model of Alphabet and CharTraits::char_type is a POD type
Tag	The type of the data attached to states.	empty_tag

---

Member Function Documentation

void clear

(

)

Postcondition:

 wc() == 0 

void freeze

(

)

Get rid of the extra data used for maintaining the automaton minimality.

Once frozen, words can still be added but the next insertion will take more time to rebuild the necessary data structure that had been disposed of.

bool insert

(

const basic_string< char_type > &

s

)

Add a word defined by a character string.

Returns:

true if the word has been actually added, false if the word already exists and that the operation left the automaton unchanged.

Postcondition:

the automaton is minimal.

bool insert	(	ForwardI	,
		ForwardI
	)

Add a word defined by a range on a sequence of characters of type char_type.

Returns:

true if the word has been actually added, false if the word already exists and that the operation left the automaton unchanged.

Postcondition:

the automaton is minimal.

Reimplemented in DFA_min_hash.

Referenced by DFA_min< CharTraits, astl::hash_tag >::insert().

unsigned int size

(

)

const

Returns:

wc()

unsigned int wc

(

)

const

word count.

Returns:

a count of the words in the automaton language

Referenced by DFA_min_hash::insert().