00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00030 #include <algorithm>
00031 #include <claw/functional.hpp>
00032 #include <claw/assert.hpp>
00033
00034
00035
00036
00037
00038 template<class State, class Edge, class StateComp, class EdgeComp >
00039 typename claw::automaton<State, Edge, StateComp, EdgeComp>::state_compare
00040 claw::automaton<State, Edge, StateComp, EdgeComp>::s_state_compare;
00041
00042
00049 template<class State, class Edge, class StateComp, class EdgeComp >
00050 void claw::automaton<State, Edge, StateComp, EdgeComp>::add_edge
00051 ( const state_type& s1, const state_type& s2, const edge_type& e )
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 }
00059
00060
00067 template<class State, class Edge, class StateComp, class EdgeComp >
00068 void claw::automaton<State, Edge, StateComp, EdgeComp>::remove_edge
00069 ( const state_type& s1, const state_type& s2, const edge_type& e )
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 }
00082
00083
00088 template<class State, class Edge, class StateComp, class EdgeComp >
00089 void claw::automaton<State, Edge, StateComp, EdgeComp>::add_state
00090 ( const state_type& s )
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 }
00100
00101
00106 template<class State, class Edge, class StateComp, class EdgeComp >
00107 void claw::automaton<State, Edge, StateComp, EdgeComp>::add_initial_state
00108 ( const state_type& s )
00109 {
00110 add_state(s);
00111 m_initial_states.insert(s);
00112 }
00113
00114
00119 template<class State, class Edge, class StateComp, class EdgeComp >
00120 void claw::automaton<State, Edge, StateComp, EdgeComp>::add_final_state
00121 ( const state_type& s )
00122 {
00123 add_state(s);
00124 m_final_states.insert(s);
00125 }
00126
00127
00132 template<class State, class Edge, class StateComp, class EdgeComp >
00133 bool claw::automaton<State, Edge, StateComp, EdgeComp>::state_exists
00134 ( const state_type& s ) const
00135 {
00136 return (m_states.find(s) != m_states.end());
00137 }
00138
00139
00145 template<class State, class Edge, class StateComp, class EdgeComp >
00146 bool claw::automaton<State, Edge, StateComp, EdgeComp>::state_is_final
00147 ( const state_type& s ) const
00148 {
00149 CLAW_PRECOND( state_exists(s) );
00150
00151 return m_final_states.find(s) != m_final_states.end();
00152 }
00153
00154
00160 template<class State, class Edge, class StateComp, class EdgeComp >
00161 bool claw::automaton<State, Edge, StateComp, EdgeComp>::state_is_initial
00162 ( const state_type& s ) const
00163 {
00164 CLAW_PRECOND( state_exists(s) );
00165
00166 return m_initial_states.find(s) != m_initial_states.end();
00167 }
00168
00169
00175 template<class State, class Edge, class StateComp, class EdgeComp >
00176 void claw::automaton<State, Edge, StateComp, EdgeComp>::states
00177 (result_state_list& v) const
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 }
00184
00185
00191 template<class State, class Edge, class StateComp, class EdgeComp >
00192 void claw::automaton<State, Edge, StateComp, EdgeComp>::final_states
00193 ( result_state_list& v ) const
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 }
00199
00200
00206 template<class State, class Edge, class StateComp, class EdgeComp >
00207 void claw::automaton<State, Edge, StateComp, EdgeComp>::initial_states
00208 ( result_state_list& v ) const
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 }
00214
00215
00221 template<class State, class Edge, class StateComp, class EdgeComp >
00222 void claw::automaton<State, Edge, StateComp, EdgeComp>::alphabet
00223 ( result_edge_list& v ) const
00224 {
00225 v.clear();
00226 v.resize( m_alphabet.size() );
00227 std::copy( m_alphabet.begin(), m_alphabet.end(), v.begin() );
00228 }
00229
00230
00236 template<class State, class Edge, class StateComp, class EdgeComp >
00237 template<class InputIterator>
00238 bool claw::automaton<State, Edge, StateComp, EdgeComp>::match
00239 (InputIterator first, InputIterator last) const
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 }
00249
00250
00254 template<class State, class Edge, class StateComp, class EdgeComp >
00255 unsigned int
00256 claw::automaton<State, Edge, StateComp, EdgeComp>::states_count() const
00257 {
00258 return m_states.size();
00259 }
00260
00261
00271 template<class State, class Edge, class StateComp, class EdgeComp >
00272 void claw::automaton<State, Edge, StateComp, EdgeComp>::reachables
00273 ( const state_type& s, const edge_type& e, result_state_list& l ) const
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 }
00285
00286
00295 template<class State, class Edge, class StateComp, class EdgeComp >
00296 void claw::automaton<State, Edge, StateComp, EdgeComp>::reachables
00297 ( const state_type& s, result_state_list& l ) const
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 }
00313
00314
00323 template<class State, class Edge, class StateComp, class EdgeComp >
00324 void claw::automaton<State, Edge, StateComp, EdgeComp>::edges
00325 ( const state_type& s1, const state_type& s2, result_edge_list& l ) const
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() );
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 }
00341
00342
00351 template<class State, class Edge, class StateComp, class EdgeComp >
00352 void claw::automaton<State, Edge, StateComp, EdgeComp>::edges
00353 ( const state_type& s1, const edge_type& e, result_edge_list& l ) const
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 }
00366
00367
00368
00369
00370
00371
00372
00373
00374
00381 template<class State, class Edge, class StateComp, class EdgeComp >
00382 template<class InputIterator>
00383 bool claw::automaton<State, Edge, StateComp, EdgeComp>::match_aux
00384 (const state_type& s, InputIterator first, InputIterator last) const
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 }