DFA_matrix_base Class Template Reference

A deterministic automaton container class that stores transitions targets in a matrix state x letter: each state has a line the size of the alphabet. More...

#include <dfa_matrix.h>

Inheritance diagram for DFA_matrix_base:

List of all members.

Public Types
typedef CharTraits	char_traits
	Character traits describing char_type.
typedef CharTraits::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 CharTraits = plain, class Tag = empty_tag, class StateType = unsigned int>
class astl::DFA_matrix_base< CharTraits, Tag, StateType >

A deterministic automaton container class that stores transitions targets in a matrix state x letter: each state has a line the size of the alphabet.

It has a fast constant-time access to transitions but tends to consume too much memory space when the matrix is sparse. It is also not recommended for depth- or breadth-first traversals.

This container is advisable for efficient pattern matching and for almost nothing else.

The constant-time access to transitions is provided by the character traits through the mapping between the alphabet and the integers implemented by CharTraits::to_char_type() and CharTraits::to_int_type().

Template parameters

Parameter	Description	Default	Requirements
CharTraits	Character traits describing the letters that the transitions bear.	plain	CharTraits is a model of EnumerableAlphabet
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