CLAW Library (a C++ Library Absolutely Wonderful) 1.5.5
|
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-2010 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()