Basic automaton structure. More...

#include <automaton.hpp>

Public Types
typedef State	state_type
	The type of the states.
typedef Edge	edge_type
	The type of the symbols on the edges.
typedef StateComp	state_compare
	The type of the operator used to compare states.
typedef EdgeComp	edge_compare
	The type of the operator used to compare edge symbols.
typedef std::multimap < edge_type, state_type, edge_compare >	neighbours_list
	The neighbours list associates states to edge symbols.
typedef std::map< state_type, neighbours_list, state_compare >	adjacent_list
	Each state is given a set of reachable states with a neighbours list.
typedef std::vector< state_type >	result_state_list
	The return type of the methods returning states.
typedef std::vector< edge_type >	result_edge_list
	The return type of the methods returning edges.

Public Member Functions
void	add_edge (const state_type &s1, const state_type &s2, const edge_type &e)
	Add an edge in the automaton.
void	remove_edge (const state_type &s1, const state_type &s2, const edge_type &e)
	Remove an edge from the atomaton.
void	add_state (const state_type &s)
	Add a state in the automaton.
void	add_initial_state (const state_type &s)
	Add an initial state.
void	add_final_state (const state_type &s)
	Add a final state.
bool	state_exists (const state_type &s) const
	Tell of the automaton contains a given state.
bool	state_is_final (const state_type &s) const
	Tell if a state is final.
bool	state_is_initial (const state_type &s) const
	Tell if a state is an initial state.
void	states (result_state_list &v) const
	Get the states in the automaton.
void	final_states (result_state_list &v) const
	Get the final states.
void	initial_states (result_state_list &v) const
	Get the final states.
void	alphabet (result_edge_list &v) const
	Get all symbols in the alphabet.
template<class InputIterator >
bool	match (InputIterator first, InputIterator last) const
	Tell if the automaton recognizes a given pattern.
unsigned int	states_count () const
	Get the number of states.
void	reachables (const state_type &s, const edge_type &e, result_state_list &l) const
	Get the states that can be reached from a given state with a given symbol.
void	reachables (const state_type &s, result_state_list &l) const
	Get the states that can be reached from a given state, no matter the symbol.
void	edges (const state_type &s1, const state_type &s2, result_edge_list &l) const
	Get all the edges between two states.
void	edges (const state_type &s1, const edge_type &edge, result_edge_list &l) const
	Get all out-edges of a given state, labeled with a given symbol.

Detailed Description

template<class State, class Edge, class StateComp = std::less<State>, class EdgeComp = std::less<Edge>>
class claw::automaton< State, Edge, StateComp, EdgeComp >

Basic automaton structure.

An automaton is a quintuplet (A, E, I ,F, T) where

A is the set of symbols,
E is the set of states,
I is the set of initial states,
F is the set of finalstates,
T is the set of transitions (labeled edges)

Template parameters

State The type of the states.
Edge The type of the symbols in the alphabet.

Definition at line 57 of file automaton.hpp.

Member Function Documentation

template<class State , class Edge , class StateComp , class EdgeComp >

void claw::automaton< State, Edge, StateComp, EdgeComp >::add_edge	(	const state_type &	s1,
		const state_type &	s2,
		const edge_type &	e
	)

Add an edge in the automaton.

Parameters

s1	Source state.
s2	Target state.
e	The label on the edge.

Definition at line 51 of file automaton.tpp.

template<class State , class Edge , class StateComp , class EdgeComp >

void claw::automaton< State, Edge, StateComp, EdgeComp >::add_final_state ( const state_type & s )

Add a final state.

Parameters

s	The state to add.

Definition at line 121 of file automaton.tpp.

template<class State , class Edge , class StateComp , class EdgeComp >

void claw::automaton< State, Edge, StateComp, EdgeComp >::add_initial_state ( const state_type & s )

Add an initial state.

Parameters

s	The state to add.

Definition at line 108 of file automaton.tpp.

template<class State , class Edge , class StateComp , class EdgeComp >

void claw::automaton< State, Edge, StateComp, EdgeComp >::add_state ( const state_type & s )

Add a state in the automaton.

Parameters

s	The state to add.

Definition at line 90 of file automaton.tpp.

template<class State , class Edge , class StateComp , class EdgeComp >

void claw::automaton< State, Edge, StateComp, EdgeComp >::alphabet ( result_edge_list & v ) const

Get all symbols in the alphabet.

Parameters

v	(out) The container in which to add the symbols

Todo:: Remove this method and add iterator types.

Definition at line 223 of file automaton.tpp.

template<class State , class Edge , class StateComp , class EdgeComp >

void claw::automaton< State, Edge, StateComp, EdgeComp >::edges	(	const state_type &	s1,
		const state_type &	s2,
		result_edge_list &	l
	)		const

Get all the edges between two states.

Parameters

s1	Source state.
s2	Target state.
l	(out) The list of edges.

Precondition: (state_exists(s1) == true) && (state_exists(s2) == true)

Todo:: Remove this method and add iterator types.

Definition at line 325 of file automaton.tpp.

References CLAW_PRECOND.

template<class State , class Edge , class StateComp , class EdgeComp >

void claw::automaton< State, Edge, StateComp, EdgeComp >::edges	(	const state_type &	s1,
		const edge_type &	e,
		result_edge_list &	l
	)		const

Get all out-edges of a given state, labeled with a given symbol.

Parameters

s1	The source state of the edges.
e	The symbol on the edges.
l	(out) The list of edges.

Precondition: state_exists(s1) == true

Todo:: Remove this method and add iterator types.

Definition at line 353 of file automaton.tpp.

References CLAW_PRECOND.

template<class State , class Edge , class StateComp , class EdgeComp >

void claw::automaton< State, Edge, StateComp, EdgeComp >::final_states ( result_state_list & v ) const

Get the final states.

Parameters

v	(out) The container in which to add the states.

Todo:: Remove this method and add iterator types.

Definition at line 193 of file automaton.tpp.

template<class State , class Edge , class StateComp , class EdgeComp >

void claw::automaton< State, Edge, StateComp, EdgeComp >::initial_states ( result_state_list & v ) const

Get the final states.

Parameters

v	(out) The container in which to add the states.

Todo:: Remove this method and add iterator types.

Definition at line 208 of file automaton.tpp.

template<class State , class Edge , class StateComp , class EdgeComp >

template<class InputIterator >

bool claw::automaton< State, Edge, StateComp, EdgeComp >::match	(	InputIterator	first,
		InputIterator	last
	)		const

Tell if the automaton recognizes a given pattern.

Parameters

first	Iterator on the first symbol in the pattern.
last	Iterator after the last symbol in the pattern.

Definition at line 239 of file automaton.tpp.

template<class State , class Edge , class StateComp , class EdgeComp >

void claw::automaton< State, Edge, StateComp, EdgeComp >::reachables	(	const state_type &	s,
		const edge_type &	e,
		result_state_list &	l
	)		const

Get the states that can be reached from a given state with a given symbol.

Parameters

s	Initial state.
e	The symbol on the edge.
l	(out) The list of reachable states.

Precondition: state_exists(s) == true

Todo:: Remove this method and add iterator types.

Definition at line 273 of file automaton.tpp.

References CLAW_PRECOND.

template<class State , class Edge , class StateComp , class EdgeComp >

void claw::automaton< State, Edge, StateComp, EdgeComp >::reachables	(	const state_type &	s,
		result_state_list &	l
	)		const

Get the states that can be reached from a given state, no matter the symbol.

Parameters

s	Initial state.
l	(out) The list of reachable states.

Precondition: state_exists(s) == true

Todo:: Remove this method and add iterator types.

Definition at line 297 of file automaton.tpp.

References claw::avl< K, Comp >::begin(), CLAW_PRECOND, claw::avl< K, Comp >::end(), claw::avl< K, Comp >::insert(), and claw::avl< K, Comp >::size().

template<class State , class Edge , class StateComp , class EdgeComp >

void claw::automaton< State, Edge, StateComp, EdgeComp >::remove_edge	(	const state_type &	s1,
		const state_type &	s2,
		const edge_type &	e
	)

Remove an edge from the atomaton.

Parameters

s1	Source state.
s2	Target state.
e	The label on the edge.

Definition at line 69 of file automaton.tpp.

template<class State , class Edge , class StateComp , class EdgeComp >

bool claw::automaton< State, Edge, StateComp, EdgeComp >::state_exists ( const state_type & s ) const

Tell of the automaton contains a given state.

Parameters

s	The state to check.

Definition at line 134 of file automaton.tpp.

template<class State , class Edge , class StateComp , class EdgeComp >

bool claw::automaton< State, Edge, StateComp, EdgeComp >::state_is_final ( const state_type & s ) const

Tell if a state is final.

Parameters

s	The state to check.

Precondition: state_exists(s) == true

Definition at line 147 of file automaton.tpp.

References CLAW_PRECOND.

template<class State , class Edge , class StateComp , class EdgeComp >

bool claw::automaton< State, Edge, StateComp, EdgeComp >::state_is_initial ( const state_type & s ) const

Tell if a state is an initial state.

Parameters

s	The state to check.

Precondition: state_exists(s) == true

Definition at line 162 of file automaton.tpp.

References CLAW_PRECOND.

template<class State , class Edge , class StateComp , class EdgeComp >

void claw::automaton< State, Edge, StateComp, EdgeComp >::states ( result_state_list & v ) const

Get the states in the automaton.

Parameters

v	(out) The container in which to add the states.

Todo:: Remove this method and add iterator types.

Definition at line 177 of file automaton.tpp.

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

automaton.hpp
impl/automaton.tpp

Public Types

Public Member Functions

Detailed Description

template<class State, class Edge, class StateComp = std::less<State>, class EdgeComp = std::less<Edge>> class claw::automaton< State, Edge, StateComp, EdgeComp >

Member Function Documentation

template<class State, class Edge, class StateComp = std::less<State>, class EdgeComp = std::less<Edge>>
class claw::automaton< State, Edge, StateComp, EdgeComp >