38 template<
class State,
class Edge,
class StateComp,
class EdgeComp >
49 template<
class State,
class Edge,
class StateComp,
class EdgeComp >
56 m_states[s1].insert(
typename neighbours_list::value_type(e,s2));
67 template<
class State,
class Edge,
class StateComp,
class EdgeComp >
71 typename neighbours_list::iterator it = m_states[s1].lower_bound(e);
74 while( (it != m_states[s1].upper_bound(e)) && !ok )
75 if ( it->second == s2 )
80 if (ok) m_states[s1].erase(it);
88 template<
class State,
class Edge,
class StateComp,
class EdgeComp >
92 std::pair<state_type, neighbours_list> p;
94 if (m_states.find(s) == m_states.end())
106 template<
class State,
class Edge,
class StateComp,
class EdgeComp >
111 m_initial_states.insert(s);
119 template<
class State,
class Edge,
class StateComp,
class EdgeComp >
124 m_final_states.insert(s);
132 template<
class State,
class Edge,
class StateComp,
class EdgeComp >
136 return (m_states.find(s) != m_states.end());
145 template<
class State,
class Edge,
class StateComp,
class EdgeComp >
151 return m_final_states.find(s) != m_final_states.end();
160 template<
class State,
class Edge,
class StateComp,
class EdgeComp >
166 return m_initial_states.find(s) != m_initial_states.end();
175 template<
class State,
class Edge,
class StateComp,
class EdgeComp >
180 v.resize( m_states.size() );
181 std::transform( m_states.begin(), m_states.end(), v.begin(),
191 template<
class State,
class Edge,
class StateComp,
class EdgeComp >
196 v.resize( m_final_states.size() );
197 std::copy( m_final_states.begin(), m_final_states.end(), v.begin() );
206 template<
class State,
class Edge,
class StateComp,
class EdgeComp >
211 v.resize( m_initial_states.size() );
212 std::copy( m_initial_states.begin(), m_initial_states.end(), v.begin() );
221 template<
class State,
class Edge,
class StateComp,
class EdgeComp >
226 v.resize( m_alphabet.size() );
227 std::copy( m_alphabet.begin(), m_alphabet.end(), v.begin() );
236 template<
class State,
class Edge,
class StateComp,
class EdgeComp >
237 template<
class InputIterator>
239 (InputIterator
first, InputIterator last)
const
244 for ( it=m_initial_states.begin(); (it!=m_initial_states.end()) && !ok; ++it )
245 ok = match_aux(*it, first, last);
254 template<
class State,
class Edge,
class StateComp,
class EdgeComp >
258 return m_states.size();
271 template<
class State,
class Edge,
class StateComp,
class EdgeComp >
277 typename adjacent_list::const_iterator it = m_states.find(s);
280 l.resize( it->second.count(e) );
282 std::transform( it->second.lower_bound(e), it->second.upper_bound(e),
295 template<
class State,
class Edge,
class StateComp,
class EdgeComp >
301 typename adjacent_list::const_iterator it_s = m_states.find(s);
302 typename neighbours_list::const_iterator it;
305 for (it = it_s->second.begin(); it != it_s->second.end(); ++it)
306 reachable_states.
insert( it->second );
309 l.resize( reachable_states.
size() );
311 std::copy( reachable_states.
begin(), reachable_states.
end(), l.begin() );
323 template<
class State,
class Edge,
class StateComp,
class EdgeComp >
330 typename adjacent_list::const_iterator it_s = m_states.find(s1);
331 typename neighbours_list::const_iterator it;
334 l.reserve( it_s->second.size() );
336 for (it = it_s->second.begin(); it != it_s->second.end(); ++it )
337 if ( !( s_state_compare(it->second, s2)
338 || s_state_compare(s2, it->second) ) )
339 l.push_back(it->first);
351 template<
class State,
class Edge,
class StateComp,
class EdgeComp >
357 typename adjacent_list::const_iterator it_s = m_states.find(s1);
360 l.resize( it_s->second.count(e) );
362 std::transform( it_s->second.lower_bound(e),
363 it_s->second.upper_bound(e), l.begin(),
381 template<
class State,
class Edge,
class StateComp,
class EdgeComp >
382 template<
class InputIterator>
384 (
const state_type& s, InputIterator first, InputIterator last)
const
391 ok = state_is_final(s);
394 typename neighbours_list::const_iterator candidate, last_candidate;
395 InputIterator next_symbol = first;
398 candidate = m_states.find(s)->second.lower_bound(*first);
399 last_candidate = m_states.find(s)->second.upper_bound(*first);
401 for (; (candidate != last_candidate) && !ok; ++candidate )
402 ok = match_aux(candidate->second, next_symbol, last);
void insert(const K &key)
Add a value in a tree.
unsigned int size() const
Get the size of a tree.
Fuction object to get the second element of a std::pair.
void edges(const state_type &s1, const state_type &s2, result_edge_list &l) const
Get all the edges between two states.
void add_initial_state(const state_type &s)
Add an initial state.
void states(result_state_list &v) const
Get the states in the automaton.
const_iterator end() const
Get an iterator after the end of the tree.
void remove_edge(const state_type &s1, const state_type &s2, const edge_type &e)
Remove an edge from the atomaton.
bool state_is_initial(const state_type &s) const
Tell if a state is an initial state.
bool state_is_final(const state_type &s) const
Tell if a state is final.
Edge edge_type
The type of the symbols on the edges.
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.
StateComp state_compare
The type of the operator used to compare states.
Fuction object to get the first element of a std::pair.
bool state_exists(const state_type &s) const
Tell of the automaton contains a given state.
std::vector< state_type > result_state_list
The return type of the methods returning states.
void final_states(result_state_list &v) const
Get the final states.
void initial_states(result_state_list &v) const
Get the final states.
Basic automaton structure.
State state_type
The type of the states.
void add_edge(const state_type &s1, const state_type &s2, const edge_type &e)
Add an edge in the automaton.
void add_final_state(const state_type &s)
Add a final state.
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.
Some assert macros to strengthen you code.
void alphabet(result_edge_list &v) const
Get all symbols in the alphabet.
std::vector< edge_type > result_edge_list
The return type of the methods returning edges.
Fuction object to get the first element of a std::pair.
void add_state(const state_type &s)
Add a state in the automaton.
#define CLAW_PRECOND(b)
Abort the program if a precondition is not true.
const_iterator begin() const
Get an iterator on the nodes of the tree.
Some function object classes.