DFA_bin Class Template Reference

A deterministic automaton container class that stores the transition of a state in a standard sorted vector of pairs of letters and transitions targets. More...

#include <dfa_bin.h>

Inheritance diagram for DFA_bin:

List of all members.

Public Types
typedef Sigma_	char_traits
	Character traits describing char_type.
typedef Sigma_::char_type	char_type
	The type of the transitions letters.
typedef unsigned int	state_type
	The type of the automaton-states identifiers.
typedef Tag_	tag_type
	The type of the data attached to states.
Public Member Functions
const_iterator	begin () const
void	copy_state (state_type from, state_type to)
	Makes the state to an exact copy of the state from.
void	del_state (state_type s)
	Destroyes the state s.
state_type	duplicate_state (state_type q)
	Allocates an exact copy of the state q.
const_iterator	end () const
char &	final (state_type s)
bool	final (state_type s) const
state_type	initial () const
void	initial (state_type s)
	Sets the initial state of the automaton to s.
state_type	new_state ()
	Allocates a new state structure.
unsigned long	state_count () const
const tag_type &	tag (state_type s) const
tag_type &	tag (state_type s)
unsigned long	trans_count () const

---

Detailed Description

template<class Sigma_ = plain, class Tag_ = empty_tag>
class astl::DFA_bin< Sigma_, Tag_ >

A deterministic automaton container class that stores the transition of a state in a standard sorted vector of pairs of letters and transitions targets.

Access is in logarithmic time through a binary search but insertion and deletion are in linear time.

It is the best when it comes to depth- and breadth-first traversals and when saving memory space is important but is slow at building and maintaining.

The ordering used for sorting the transition uses the one defined by the character traits CharTraits::lt().

Template parameters

Parameter	Description	Default	Requirements
CharTraits	Character traits describing the letters that the transitions bear.	plain	CharTraits is a model of Alphabet
Tag	The type of the data attached to states.	empty_tag

---

Member Function Documentation

const_iterator begin

(

)

const [inherited]

Returns:

a forward iterator on the beginning of the sequence of the automaton states of type state_type arranged in an undefined order (probably in allocation order but that is not a requirement).

void copy_state	(	state_type	from,
		state_type	to
	)			[inherited]

Makes the state to an exact copy of the state from.

The tag and the transitions of to are destroyed and the new ones are copy-constructed from those of from.

Precondition:

from has been returned by a previous call to new_state()

to has been returned by a previous call to new_state()

void del_state

(

state_type

s

)

[inherited]

Destroyes the state s.

The tag and the transitions are destroyed.

Precondition:

s has been returned by a previous call to new_state()

state_type duplicate_state

(

state_type

q

)

[inherited]

Allocates an exact copy of the state q.

Returns:

the id of the freshly allocated state

Precondition:

q has been returned by a previous call to new_state()

const_iterator end

(

)

const [inherited]

Returns:

a past-the-end forward iterator on the sequence of the automaton states.

char& final

(

state_type

s

)

[inherited]

Returns:

a reference to a boolean that, if assigned true sets the state s to be a final state and if assigned false sets s to be a non-final state.

Precondition:

s has been returned by a previous call to new_state()

bool final

(

state_type

s

)

const [inherited]

Returns:

true if s is a final state.

Precondition:

s has been returned by a previous call to new_state()

state_type initial

(

)

const [inherited]

Returns:

the initial state of the automaton.

Referenced by DFA_base< Sigma_, Tag_, std::vector< pair< Sigma_::char_traits::char_type, unsigned int > > >::del_state().

void initial

(

state_type

s

)

[inherited]

Sets the initial state of the automaton to s.

Precondition:

s has been returned by a previous call to new_state()

Postcondition:

 initial() == s 

state_type new_state

(

)

[inherited]

Allocates a new state structure.

The newly created state is non-final and has no transitions. The tag is default-constructed.

Returns:

the id of the freshly allocated state

unsigned long state_count

(

)

const [inherited]

Returns:

the number of states in the automaton

const tag_type& tag

(

state_type

s

)

const [inherited]

Returns:

the data attached to the state s

Precondition:

s has been returned by a previous call to new_state()

tag_type& tag

(

state_type

s

)

[inherited]

Returns:

the data attached to the state s

Precondition:

s has been returned by a previous call to new_state()

unsigned long trans_count

(

)

const [inherited]

Returns:

the number of transitions in the automaton