CLAW Library (a C++ Library Absolutely Wonderful) 1.5.5
|
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 | ||
) |
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.
{ add_state(s1); add_state(s2); m_states[s1].insert(typename neighbours_list::value_type(e,s2)); m_alphabet.insert(e); } // automaton::add_edge()
void claw::automaton< State, Edge, StateComp, EdgeComp >::add_final_state | ( | const state_type & | s | ) |
Add a final state.
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()
void claw::automaton< State, Edge, StateComp, EdgeComp >::add_initial_state | ( | const state_type & | s | ) |
Add an initial state.
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()
void claw::automaton< State, Edge, StateComp, EdgeComp >::add_state | ( | const state_type & | s | ) |
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 |
Get all symbols in the alphabet.
v | (out) The container in which to add the symbols |
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()
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.
s1 | Source state. |
s2 | Target state. |
l | (out) The list of edges. |
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()
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.
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.
{ 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()
void claw::automaton< State, Edge, StateComp, EdgeComp >::final_states | ( | result_state_list & | v | ) | const |
Get the final states.
v | (out) The container in which to add the states. |
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()
void claw::automaton< State, Edge, StateComp, EdgeComp >::initial_states | ( | result_state_list & | v | ) | const |
Get the final states.
v | (out) The container in which to add the states. |
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()
bool claw::automaton< State, Edge, StateComp, EdgeComp >::match | ( | InputIterator | first, |
InputIterator | last | ||
) | const |
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.
{ 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()
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).
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()
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.
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().
{ 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()
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.
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.
{ 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()
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.
s1 | Source state. |
s2 | Target state. |
e | The label on the edge. |
Definition at line 69 of file automaton.tpp.
bool claw::automaton< State, Edge, StateComp, EdgeComp >::state_exists | ( | const state_type & | s | ) | const |
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 |
Tell if a state is final.
s | The state to check. |
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()
bool claw::automaton< State, Edge, StateComp, EdgeComp >::state_is_initial | ( | const state_type & | s | ) | const |
Tell if a state is an initial state.
s | The state to check. |
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
void claw::automaton< State, Edge, StateComp, EdgeComp >::states | ( | result_state_list & | v | ) | const |
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 |
Get the number of states.
Definition at line 256 of file automaton.tpp.
{ return m_states.size(); } // 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.
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.