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.
Private Member Functions
template<class InputIterator >
bool	match_aux (const state_type &s, InputIterator first, InputIterator last) const
	Recognize a pattern (recursive and auxiliary method).
Private Attributes
avl< edge_type, edge_compare >	m_alphabet
	The set of symbols in the alphabet.
avl< state_type, state_compare >	m_initial_states
	The set of initial states.
avl< state_type, state_compare >	m_final_states
	The set of final states.
adjacent_list	m_states
	The adjacency list (the set of transitions).
Static Private Attributes
static state_compare	s_state_compare
	The predicate used to compare states.

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 Typedef Documentation

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

typedef std::map<state_type, neighbours_list, state_compare> claw::automaton< State, Edge, StateComp, EdgeComp >::adjacent_list

Each state is given a set of reachable states with a neighbours list.

Definition at line 77 of file automaton.hpp.

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

typedef EdgeComp claw::automaton< State, Edge, StateComp, EdgeComp >::edge_compare

The type of the operator used to compare edge symbols.

Definition at line 70 of file automaton.hpp.

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

typedef Edge claw::automaton< State, Edge, StateComp, EdgeComp >::edge_type

The type of the symbols on the edges.

Definition at line 64 of file automaton.hpp.

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

typedef std::multimap<edge_type, state_type, edge_compare> claw::automaton< State, Edge, StateComp, EdgeComp >::neighbours_list

The neighbours list associates states to edge symbols.

Definition at line 73 of file automaton.hpp.

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

typedef std::vector<edge_type> claw::automaton< State, Edge, StateComp, EdgeComp >::result_edge_list

The return type of the methods returning edges.

Definition at line 83 of file automaton.hpp.

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

typedef std::vector<state_type> claw::automaton< State, Edge, StateComp, EdgeComp >::result_state_list

The return type of the methods returning states.

Definition at line 80 of file automaton.hpp.

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

typedef StateComp claw::automaton< State, Edge, StateComp, EdgeComp >::state_compare

The type of the operator used to compare states.

Definition at line 67 of file automaton.hpp.

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

typedef State claw::automaton< State, Edge, StateComp, EdgeComp >::state_type

The type of the states.

Definition at line 61 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.

{
  add_state(s1);
  add_state(s2);

  m_states[s1].insert(typename neighbours_list::value_type(e,s2));
  m_alphabet.insert(e);
} // automaton::add_edge()

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.

{
  add_state(s);
  m_final_states.insert(s);
} // automaton::add_final_state()

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.

{
  add_state(s);
  m_initial_states.insert(s);
} // automaton::add_initial_state()

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.

{
  std::pair<state_type, neighbours_list> p;

  if (m_states.find(s) == m_states.end())
    {
      p.first = s;
      m_states.insert(p);
    }
} // automaton::add_state()

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.

{
  v.clear();
  v.resize( m_alphabet.size() );
  std::copy( m_alphabet.begin(), m_alphabet.end(), v.begin() );
} // automaton::alphabet()

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.

{
  CLAW_PRECOND( state_exists(s1) );
  CLAW_PRECOND( state_exists(s2) );

  typename adjacent_list::const_iterator it_s = m_states.find(s1);
  typename neighbours_list::const_iterator it;

  l.clear();
  l.reserve( it_s->second.size() ); // pessimistic

  for (it = it_s->second.begin(); it != it_s->second.end(); ++it )
    if ( !( s_state_compare(it->second, s2) 
            || s_state_compare(s2, it->second) ) )
      l.push_back(it->first);
} // automaton::edges()

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.

{
  CLAW_PRECOND( state_exists(s1) );

  typename adjacent_list::const_iterator it_s = m_states.find(s1);

  l.clear();
  l.resize( it_s->second.count(e) );

  std::transform( it_s->second.lower_bound(e),
                  it_s->second.upper_bound(e), l.begin(),
                  claw::first<edge_type, state_type>() );
} // automaton::edges()

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.

{
  v.clear();
  v.resize( m_final_states.size() );
  std::copy( m_final_states.begin(), m_final_states.end(), v.begin() );
} // automaton::final_states()

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.

{
  v.clear();
  v.resize( m_initial_states.size() );
  std::copy( m_initial_states.begin(), m_initial_states.end(), v.begin() );
} // automaton::initial_states()

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.

{
  bool ok = false;
  typename claw::avl<state_type>::const_iterator it;
  
  for ( it=m_initial_states.begin(); (it!=m_initial_states.end()) && !ok; ++it )
    ok = match_aux(*it, first, last);

  return ok;
} // automaton::match()

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

template<class InputIterator >

bool claw::automaton< State, Edge, StateComp, EdgeComp >::match_aux	(	const state_type &	s,
		InputIterator	first,
		InputIterator	last
	)		const `[private]`

Recognize a pattern (recursive and auxiliary method).

Parameters:

s	The state on which we start the search.
first	Iterator on the first symbol to recognize.
last	Iterator past the last symbol to recognize.

Definition at line 384 of file automaton.tpp.

References CLAW_PRECOND.

{
  CLAW_PRECOND( state_exists(s) );

  bool ok = false;
  
  if ( first == last )
    ok = state_is_final(s);
  else
    {
      typename neighbours_list::const_iterator candidate, last_candidate;
      InputIterator next_symbol = first;
      ++next_symbol;

      candidate = m_states.find(s)->second.lower_bound(*first);
      last_candidate = m_states.find(s)->second.upper_bound(*first);

      for (; (candidate != last_candidate) && !ok; ++candidate )
        ok = match_aux(candidate->second, next_symbol, last);
    }

  return ok;
} // automaton::match_aux()

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().

{
  CLAW_PRECOND( state_exists(s) );

  typename adjacent_list::const_iterator it_s = m_states.find(s);
  typename neighbours_list::const_iterator it;
  claw::avl<state_type, state_compare> reachable_states;

  for (it = it_s->second.begin(); it != it_s->second.end(); ++it)
    reachable_states.insert( it->second );

  l.clear();
  l.resize( reachable_states.size() );

  std::copy( reachable_states.begin(), reachable_states.end(), l.begin() );
} // automaton::reachables_states()

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.

{
  CLAW_PRECOND( state_exists(s) );

  typename adjacent_list::const_iterator it = m_states.find(s);

  l.clear();
  l.resize( it->second.count(e) );

  std::transform( it->second.lower_bound(e), it->second.upper_bound(e),
                  l.begin(), claw::second<edge_type, state_type>() );
} // automaton::reachables()

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.

{
  typename neighbours_list::iterator it = m_states[s1].lower_bound(e);
  bool ok = false;

  while( (it != m_states[s1].upper_bound(e)) && !ok )
    if ( it->second == s2 ) 
      ok = true; 
    else 
      ++it;

  if (ok) m_states[s1].erase(it);  
} // automaton::remove_edge()

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.

{
  return (m_states.find(s) != m_states.end());
} // automaton::state_exists()

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.

{
  CLAW_PRECOND( state_exists(s) );

  return m_final_states.find(s) != m_final_states.end();
} // automaton::state_is_final()

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.

{
  CLAW_PRECOND( state_exists(s) );

  return m_initial_states.find(s) != m_initial_states.end();
} // automaton::state_is_initial

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.

{
  v.clear();
  v.resize( m_states.size() );
  std::transform( m_states.begin(), m_states.end(), v.begin(), 
                  const_first<state_type, neighbours_list>() );
} // automaton::states()

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

unsigned int claw::automaton< State, Edge, StateComp, EdgeComp >::states_count ( ) const

Get the number of states.

Definition at line 256 of file automaton.tpp.

{
  return m_states.size(); 
} // automaton::states_count()

Member Data Documentation

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

avl<edge_type, edge_compare> claw::automaton< State, Edge, StateComp, EdgeComp >::m_alphabet [private]

The set of symbols in the alphabet.

Definition at line 129 of file automaton.hpp.

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

avl<state_type, state_compare> claw::automaton< State, Edge, StateComp, EdgeComp >::m_final_states [private]

The set of final states.

Definition at line 135 of file automaton.hpp.

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

avl<state_type, state_compare> claw::automaton< State, Edge, StateComp, EdgeComp >::m_initial_states [private]

The set of initial states.

Definition at line 132 of file automaton.hpp.

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

adjacent_list claw::automaton< State, Edge, StateComp, EdgeComp >::m_states [private]

The adjacency list (the set of transitions).

Definition at line 138 of file automaton.hpp.

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

claw::automaton< State, Edge, StateComp, EdgeComp >::state_compare claw::automaton< State, Edge, StateComp, EdgeComp >::s_state_compare [static, private]

The predicate used to compare states.

Definition at line 126 of file automaton.hpp.

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

automaton.hpp
impl/automaton.tpp

claw::automaton< State, Edge, StateComp, EdgeComp > Class Template Reference

Public Types

Public Member Functions

Private Member Functions

Private Attributes

Static Private Attributes

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 Typedef Documentation

Member Function Documentation

Member Data Documentation

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