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. |
Basic automaton structure.
An automaton is a quintuplet (A, E, I ,F, T) where
Template parameters
Definition at line 57 of file automaton.hpp.
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.
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.
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.
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.
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.
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.
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.
typedef State claw::automaton< State, Edge, StateComp, EdgeComp >::state_type |
The type of the states.
Definition at line 61 of file automaton.hpp.
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.
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()
void claw::automaton< State, Edge, StateComp, EdgeComp >::add_final_state | ( | const state_type & | s | ) | [inline] |
Add a final state.
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()
void claw::automaton< State, Edge, StateComp, EdgeComp >::add_initial_state | ( | const state_type & | s | ) | [inline] |
Add an initial state.
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()
void claw::automaton< State, Edge, StateComp, EdgeComp >::add_state | ( | const state_type & | s | ) | [inline] |
Add a state in the automaton.
s | The state to add. |
Definition at line 90 of file automaton.tpp.
void claw::automaton< State, Edge, StateComp, EdgeComp >::alphabet | ( | result_edge_list & | v | ) | const [inline] |
Get all symbols in the alphabet.
v | (out) The container in which to add the symbols |
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()
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.
s1 | The source state of the edges. | |
e | The symbol on the edges. | |
l | (out) The list of edges. |
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()
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.
s1 | Source state. | |
s2 | Target state. | |
l | (out) The list of edges. |
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()
void claw::automaton< State, Edge, StateComp, EdgeComp >::final_states | ( | result_state_list & | v | ) | const [inline] |
Get the final states.
v | (out) The container in which to add the states. |
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()
void claw::automaton< State, Edge, StateComp, EdgeComp >::initial_states | ( | result_state_list & | v | ) | const [inline] |
Get the final states.
v | (out) The container in which to add the states. |
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()
bool claw::automaton< State, Edge, StateComp, EdgeComp >::match | ( | InputIterator | first, | |
InputIterator | last | |||
) | const [inline] |
Tell if the automaton recognizes a given pattern.
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()
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).
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()
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.
s | Initial state. | |
l | (out) The list of reachable states. |
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()
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.
s | Initial state. | |
e | The symbol on the edge. | |
l | (out) The list of reachable states. |
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()
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.
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()
bool claw::automaton< State, Edge, StateComp, EdgeComp >::state_exists | ( | const state_type & | s | ) | const [inline] |
Tell of the automaton contains a given state.
s | The state to check. |
Definition at line 134 of file automaton.tpp.
bool claw::automaton< State, Edge, StateComp, EdgeComp >::state_is_final | ( | const state_type & | s | ) | const [inline] |
Tell if a state is final.
s | The state to check. |
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()
bool claw::automaton< State, Edge, StateComp, EdgeComp >::state_is_initial | ( | const state_type & | s | ) | const [inline] |
Tell if a state is an initial state.
s | The state to check. |
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
void claw::automaton< State, Edge, StateComp, EdgeComp >::states | ( | result_state_list & | v | ) | const [inline] |
Get the states in the automaton.
v | (out) The container in which to add the states. |
Definition at line 177 of file automaton.tpp.
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()
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.
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.
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.
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().
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.