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

Basic automaton structure. More...

#include <automaton.hpp>

List of all members.

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_typeresult_state_list
 The return type of the methods returning states.
typedef std::vector< edge_typeresult_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_comparem_alphabet
 The set of symbols in the alphabet.
avl< state_type, state_comparem_initial_states
 The set of initial states.
avl< state_type, state_comparem_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

Template parameters

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 
) [inline]

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.

00052 {
00053   add_state(s1);
00054   add_state(s2);
00055 
00056   m_states[s1].insert(typename neighbours_list::value_type(e,s2));
00057   m_alphabet.insert(e);
00058 } // 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  )  [inline]

Add a final state.

Parameters:
s The state to add.

Definition at line 121 of file automaton.tpp.

00122 {
00123   add_state(s);
00124   m_final_states.insert(s);
00125 } // 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  )  [inline]

Add an initial state.

Parameters:
s The state to add.

Definition at line 108 of file automaton.tpp.

00109 {
00110   add_state(s);
00111   m_initial_states.insert(s);
00112 } // 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  )  [inline]

Add a state in the automaton.

Parameters:
s The state to add.

Definition at line 90 of file automaton.tpp.

00091 {
00092   std::pair<state_type, neighbours_list> p;
00093 
00094   if (m_states.find(s) == m_states.end())
00095     {
00096       p.first = s;
00097       m_states.insert(p);
00098     }
00099 } // 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 [inline]

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.

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

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 [inline]

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.

00354 {
00355   CLAW_PRECOND( state_exists(s1) );
00356 
00357   typename adjacent_list::const_iterator it_s = m_states.find(s1);
00358 
00359   l.clear();
00360   l.resize( it_s->second.count(e) );
00361 
00362   std::transform( it_s->second.lower_bound(e),
00363                   it_s->second.upper_bound(e), l.begin(),
00364                   claw::first<edge_type, state_type>() );
00365 } // automaton::edges()

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 [inline]

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.

00326 {
00327   CLAW_PRECOND( state_exists(s1) );
00328   CLAW_PRECOND( state_exists(s2) );
00329 
00330   typename adjacent_list::const_iterator it_s = m_states.find(s1);
00331   typename neighbours_list::const_iterator it;
00332 
00333   l.clear();
00334   l.reserve( it_s->second.size() ); // pessimistic
00335 
00336   for (it = it_s->second.begin(); it != it_s->second.end(); ++it )
00337     if ( !( s_state_compare(it->second, s2) 
00338             || s_state_compare(s2, it->second) ) )
00339       l.push_back(it->first);
00340 } // 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 [inline]

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.

00194 {
00195   v.clear();
00196   v.resize( m_final_states.size() );
00197   std::copy( m_final_states.begin(), m_final_states.end(), v.begin() );
00198 } // 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 [inline]

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.

00209 {
00210   v.clear();
00211   v.resize( m_initial_states.size() );
00212   std::copy( m_initial_states.begin(), m_initial_states.end(), v.begin() );
00213 } // 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 [inline]

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.

00240 {
00241   bool ok = false;
00242   typename claw::avl<state_type>::const_iterator it;
00243   
00244   for ( it=m_initial_states.begin(); (it!=m_initial_states.end()) && !ok; ++it )
00245     ok = match_aux(*it, first, last);
00246 
00247   return ok;
00248 } // 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 [inline, 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.

00385 {
00386   CLAW_PRECOND( state_exists(s) );
00387 
00388   bool ok = false;
00389   
00390   if ( first == last )
00391     ok = state_is_final(s);
00392   else
00393     {
00394       typename neighbours_list::const_iterator candidate, last_candidate;
00395       InputIterator next_symbol = first;
00396       ++next_symbol;
00397 
00398       candidate = m_states.find(s)->second.lower_bound(*first);
00399       last_candidate = m_states.find(s)->second.upper_bound(*first);
00400 
00401       for (; (candidate != last_candidate) && !ok; ++candidate )
00402         ok = match_aux(candidate->second, next_symbol, last);
00403     }
00404 
00405   return ok;
00406 } // 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 [inline]

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

00298 {
00299   CLAW_PRECOND( state_exists(s) );
00300 
00301   typename adjacent_list::const_iterator it_s = m_states.find(s);
00302   typename neighbours_list::const_iterator it;
00303   claw::avl<state_type, state_compare> reachable_states;
00304 
00305   for (it = it_s->second.begin(); it != it_s->second.end(); ++it)
00306     reachable_states.insert( it->second );
00307 
00308   l.clear();
00309   l.resize( reachable_states.size() );
00310 
00311   std::copy( reachable_states.begin(), reachable_states.end(), l.begin() );
00312 } // 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 [inline]

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.

00274 {
00275   CLAW_PRECOND( state_exists(s) );
00276 
00277   typename adjacent_list::const_iterator it = m_states.find(s);
00278 
00279   l.clear();
00280   l.resize( it->second.count(e) );
00281 
00282   std::transform( it->second.lower_bound(e), it->second.upper_bound(e),
00283                   l.begin(), claw::second<edge_type, state_type>() );
00284 } // 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 
) [inline]

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.

00070 {
00071   typename neighbours_list::iterator it = m_states[s1].lower_bound(e);
00072   bool ok = false;
00073 
00074   while( (it != m_states[s1].upper_bound(e)) && !ok )
00075     if ( it->second == s2 ) 
00076       ok = true; 
00077     else 
00078       ++it;
00079 
00080   if (ok) m_states[s1].erase(it);  
00081 } // 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 [inline]

Tell of the automaton contains a given state.

Parameters:
s The state to check.

Definition at line 134 of file automaton.tpp.

00135 {
00136   return (m_states.find(s) != m_states.end());
00137 } // 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 [inline]

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.

00148 {
00149   CLAW_PRECOND( state_exists(s) );
00150 
00151   return m_final_states.find(s) != m_final_states.end();
00152 } // 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 [inline]

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.

00163 {
00164   CLAW_PRECOND( state_exists(s) );
00165 
00166   return m_initial_states.find(s) != m_initial_states.end();
00167 } // 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 [inline]

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.

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

template<class State , class Edge , class StateComp , class EdgeComp >
unsigned int claw::automaton< State, Edge, StateComp, EdgeComp >::states_count (  )  const [inline]

Get the number of states.

Definition at line 256 of file automaton.tpp.

References claw::automaton< State, Edge, StateComp, EdgeComp >::m_states.

00257 {
00258   return m_states.size(); 
00259 } // 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.

Referenced by claw::automaton< State, Edge, StateComp, EdgeComp >::states_count().

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 [inline, 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:

Generated on 9 Nov 2009 for CLAW Library (a C++ Library Absolutely Wonderful) by  doxygen 1.6.1