Claw  1.7.3
automaton.tpp
Go to the documentation of this file.
1 /*
2  CLAW - a C++ Library Absolutely Wonderful
3 
4  CLAW is a free library without any particular aim but being useful to
5  anyone.
6 
7  Copyright (C) 2005-2011 Julien Jorge
8 
9  This library is free software; you can redistribute it and/or
10  modify it under the terms of the GNU Lesser General Public
11  License as published by the Free Software Foundation; either
12  version 2.1 of the License, or (at your option) any later version.
13 
14  This library is distributed in the hope that it will be useful,
15  but WITHOUT ANY WARRANTY; without even the implied warranty of
16  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
17  Lesser General Public License for more details.
18 
19  You should have received a copy of the GNU Lesser General Public
20  License along with this library; if not, write to the Free Software
21  Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
22 
23  contact: julien.jorge@gamned.org
24 */
30 #include <algorithm>
31 #include <claw/functional.hpp>
32 #include <claw/assert.hpp>
33 
34 //***************************** automate **************************************
35 
36 
37 /*----------------------------------------------------------------------------*/
38 template<class State, class Edge, class StateComp, class EdgeComp >
41 
42 /*----------------------------------------------------------------------------*/
49 template<class State, class Edge, class StateComp, class EdgeComp >
51 ( const state_type& s1, const state_type& s2, const edge_type& e )
52 {
53  add_state(s1);
54  add_state(s2);
55 
56  m_states[s1].insert(typename neighbours_list::value_type(e,s2));
57  m_alphabet.insert(e);
58 } // automaton::add_edge()
59 
60 /*----------------------------------------------------------------------------*/
67 template<class State, class Edge, class StateComp, class EdgeComp >
69 ( const state_type& s1, const state_type& s2, const edge_type& e )
70 {
71  typename neighbours_list::iterator it = m_states[s1].lower_bound(e);
72  bool ok = false;
73 
74  while( (it != m_states[s1].upper_bound(e)) && !ok )
75  if ( it->second == s2 )
76  ok = true;
77  else
78  ++it;
79 
80  if (ok) m_states[s1].erase(it);
81 } // automaton::remove_edge()
82 
83 /*----------------------------------------------------------------------------*/
88 template<class State, class Edge, class StateComp, class EdgeComp >
90 ( const state_type& s )
91 {
92  std::pair<state_type, neighbours_list> p;
93 
94  if (m_states.find(s) == m_states.end())
95  {
96  p.first = s;
97  m_states.insert(p);
98  }
99 } // automaton::add_state()
100 
101 /*----------------------------------------------------------------------------*/
106 template<class State, class Edge, class StateComp, class EdgeComp >
108 ( const state_type& s )
109 {
110  add_state(s);
111  m_initial_states.insert(s);
112 } // automaton::add_initial_state()
113 
114 /*----------------------------------------------------------------------------*/
119 template<class State, class Edge, class StateComp, class EdgeComp >
121 ( const state_type& s )
122 {
123  add_state(s);
124  m_final_states.insert(s);
125 } // automaton::add_final_state()
126 
127 /*----------------------------------------------------------------------------*/
132 template<class State, class Edge, class StateComp, class EdgeComp >
134 ( const state_type& s ) const
135 {
136  return (m_states.find(s) != m_states.end());
137 } // automaton::state_exists()
138 
139 /*----------------------------------------------------------------------------*/
145 template<class State, class Edge, class StateComp, class EdgeComp >
147 ( const state_type& s ) const
148 {
149  CLAW_PRECOND( state_exists(s) );
150 
151  return m_final_states.find(s) != m_final_states.end();
152 } // automaton::state_is_final()
153 
154 /*----------------------------------------------------------------------------*/
160 template<class State, class Edge, class StateComp, class EdgeComp >
162 ( const state_type& s ) const
163 {
164  CLAW_PRECOND( state_exists(s) );
165 
166  return m_initial_states.find(s) != m_initial_states.end();
167 } // automaton::state_is_initial
168 
169 /*----------------------------------------------------------------------------*/
175 template<class State, class Edge, class StateComp, class EdgeComp >
178 {
179  v.clear();
180  v.resize( m_states.size() );
181  std::transform( m_states.begin(), m_states.end(), v.begin(),
183 } // automaton::states()
184 
185 /*----------------------------------------------------------------------------*/
191 template<class State, class Edge, class StateComp, class EdgeComp >
193 ( result_state_list& v ) const
194 {
195  v.clear();
196  v.resize( m_final_states.size() );
197  std::copy( m_final_states.begin(), m_final_states.end(), v.begin() );
198 } // automaton::final_states()
199 
200 /*----------------------------------------------------------------------------*/
206 template<class State, class Edge, class StateComp, class EdgeComp >
208 ( result_state_list& v ) const
209 {
210  v.clear();
211  v.resize( m_initial_states.size() );
212  std::copy( m_initial_states.begin(), m_initial_states.end(), v.begin() );
213 } // automaton::initial_states()
214 
215 /*----------------------------------------------------------------------------*/
221 template<class State, class Edge, class StateComp, class EdgeComp >
223 ( result_edge_list& v ) const
224 {
225  v.clear();
226  v.resize( m_alphabet.size() );
227  std::copy( m_alphabet.begin(), m_alphabet.end(), v.begin() );
228 } // automaton::alphabet()
229 
230 /*----------------------------------------------------------------------------*/
236 template<class State, class Edge, class StateComp, class EdgeComp >
237 template<class InputIterator>
239 (InputIterator first, InputIterator last) const
240 {
241  bool ok = false;
243 
244  for ( it=m_initial_states.begin(); (it!=m_initial_states.end()) && !ok; ++it )
245  ok = match_aux(*it, first, last);
246 
247  return ok;
248 } // automaton::match()
249 
250 /*----------------------------------------------------------------------------*/
254 template<class State, class Edge, class StateComp, class EdgeComp >
255 unsigned int
257 {
258  return m_states.size();
259 } // automaton::states_count()
260 
261 /*----------------------------------------------------------------------------*/
271 template<class State, class Edge, class StateComp, class EdgeComp >
273 ( const state_type& s, const edge_type& e, result_state_list& l ) const
274 {
275  CLAW_PRECOND( state_exists(s) );
276 
277  typename adjacent_list::const_iterator it = m_states.find(s);
278 
279  l.clear();
280  l.resize( it->second.count(e) );
281 
282  std::transform( it->second.lower_bound(e), it->second.upper_bound(e),
284 } // automaton::reachables()
285 
286 /*----------------------------------------------------------------------------*/
295 template<class State, class Edge, class StateComp, class EdgeComp >
297 ( const state_type& s, result_state_list& l ) const
298 {
299  CLAW_PRECOND( state_exists(s) );
300 
301  typename adjacent_list::const_iterator it_s = m_states.find(s);
302  typename neighbours_list::const_iterator it;
303  claw::avl<state_type, state_compare> reachable_states;
304 
305  for (it = it_s->second.begin(); it != it_s->second.end(); ++it)
306  reachable_states.insert( it->second );
307 
308  l.clear();
309  l.resize( reachable_states.size() );
310 
311  std::copy( reachable_states.begin(), reachable_states.end(), l.begin() );
312 } // automaton::reachables_states()
313 
314 /*----------------------------------------------------------------------------*/
323 template<class State, class Edge, class StateComp, class EdgeComp >
325 ( const state_type& s1, const state_type& s2, result_edge_list& l ) const
326 {
327  CLAW_PRECOND( state_exists(s1) );
328  CLAW_PRECOND( state_exists(s2) );
329 
330  typename adjacent_list::const_iterator it_s = m_states.find(s1);
331  typename neighbours_list::const_iterator it;
332 
333  l.clear();
334  l.reserve( it_s->second.size() ); // pessimistic
335 
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);
340 } // automaton::edges()
341 
342 /*----------------------------------------------------------------------------*/
351 template<class State, class Edge, class StateComp, class EdgeComp >
353 ( const state_type& s1, const edge_type& e, result_edge_list& l ) const
354 {
355  CLAW_PRECOND( state_exists(s1) );
356 
357  typename adjacent_list::const_iterator it_s = m_states.find(s1);
358 
359  l.clear();
360  l.resize( it_s->second.count(e) );
361 
362  std::transform( it_s->second.lower_bound(e),
363  it_s->second.upper_bound(e), l.begin(),
365 } // automaton::edges()
366 
367 
368 
369 /*================================== private =================================*/
370 
371 
372 
373 
374 /*----------------------------------------------------------------------------*/
381 template<class State, class Edge, class StateComp, class EdgeComp >
382 template<class InputIterator>
384 (const state_type& s, InputIterator first, InputIterator last) const
385 {
386  CLAW_PRECOND( state_exists(s) );
387 
388  bool ok = false;
389 
390  if ( first == last )
391  ok = state_is_final(s);
392  else
393  {
394  typename neighbours_list::const_iterator candidate, last_candidate;
395  InputIterator next_symbol = first;
396  ++next_symbol;
397 
398  candidate = m_states.find(s)->second.lower_bound(*first);
399  last_candidate = m_states.find(s)->second.upper_bound(*first);
400 
401  for (; (candidate != last_candidate) && !ok; ++candidate )
402  ok = match_aux(candidate->second, next_symbol, last);
403  }
404 
405  return ok;
406 } // automaton::match_aux()