automaton.tpp

Go to the documentation of this file.
00001 /*
00002   CLAW - a C++ Library Absolutely Wonderful
00003 
00004   CLAW is a free library without any particular aim but being useful to 
00005   anyone.
00006 
00007   Copyright (C) 2005-2008 Julien Jorge
00008 
00009   This library is free software; you can redistribute it and/or
00010   modify it under the terms of the GNU Lesser General Public
00011   License as published by the Free Software Foundation; either
00012   version 2.1 of the License, or (at your option) any later version.
00013 
00014   This library is distributed in the hope that it will be useful,
00015   but WITHOUT ANY WARRANTY; without even the implied warranty of
00016   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
00017   Lesser General Public License for more details.
00018 
00019   You should have received a copy of the GNU Lesser General Public
00020   License along with this library; if not, write to the Free Software
00021   Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
00022 
00023   contact: julien_jorge@yahoo.fr
00024 */
00030 #include <algorithm>
00031 #include <claw/functional.hpp>
00032 #include <claw/assert.hpp>
00033 
00034 //***************************** automate **************************************
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 } // automaton::add_edge()
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 } // automaton::remove_edge()
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 } // automaton::add_state()
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 } // automaton::add_initial_state()
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 } // automaton::add_final_state()
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 } // automaton::state_exists()
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 } // automaton::state_is_final()
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 } // automaton::state_is_initial
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 } // automaton::states()
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 } // automaton::final_states()
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 } // automaton::initial_states()
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 } // automaton::alphabet()
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 } // automaton::match()
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 } // automaton::states_count()
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 } // automaton::reachables()
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 } // automaton::reachables_states()
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() ); // 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()
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 } // automaton::edges()
00366 
00367 
00368 
00369 /*================================== private =================================*/
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 } // automaton::match_aux()

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