Claw  1.7.3
automaton.tpp
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 */
25 /**
26  * \file automaton.tpp
27  * \brief Implementation of the claw::automaton class.
28  * \author Julien Jorge
29  */
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 >
39 typename claw::automaton<State, Edge, StateComp, EdgeComp>::state_compare
40 claw::automaton<State, Edge, StateComp, EdgeComp>::s_state_compare;
41 
42 /*----------------------------------------------------------------------------*/
43 /**
44  * \brief Add an edge in the automaton.
45  * \param s1 Source state.
46  * \param s2 Target state.
47  * \param e The label on the edge.
48  */
49 template<class State, class Edge, class StateComp, class EdgeComp >
50 void claw::automaton<State, Edge, StateComp, EdgeComp>::add_edge
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 /*----------------------------------------------------------------------------*/
61 /**
62  * \brief Remove an edge from the atomaton.
63  * \param s1 Source state.
64  * \param s2 Target state.
65  * \param e The label on the edge.
66  */
67 template<class State, class Edge, class StateComp, class EdgeComp >
68 void claw::automaton<State, Edge, StateComp, EdgeComp>::remove_edge
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 /*----------------------------------------------------------------------------*/
84 /**
85  * \brief Add a state in the automaton.
86  * \param s The state to add.
87  */
88 template<class State, class Edge, class StateComp, class EdgeComp >
89 void claw::automaton<State, Edge, StateComp, EdgeComp>::add_state
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 /*----------------------------------------------------------------------------*/
102 /**
103  * \brief Add an initial state.
104  * \param s The state to add.
105  */
106 template<class State, class Edge, class StateComp, class EdgeComp >
107 void claw::automaton<State, Edge, StateComp, EdgeComp>::add_initial_state
108 ( const state_type& s )
109 {
110  add_state(s);
111  m_initial_states.insert(s);
112 } // automaton::add_initial_state()
113 
114 /*----------------------------------------------------------------------------*/
115 /**
116  * \brief Add a final state.
117  * \param s The state to add.
118  */
119 template<class State, class Edge, class StateComp, class EdgeComp >
120 void claw::automaton<State, Edge, StateComp, EdgeComp>::add_final_state
121 ( const state_type& s )
122 {
123  add_state(s);
124  m_final_states.insert(s);
125 } // automaton::add_final_state()
126 
127 /*----------------------------------------------------------------------------*/
128 /**
129  * \brief Tell of the automaton contains a given state.
130  * \param s The state to check.
131  */
132 template<class State, class Edge, class StateComp, class EdgeComp >
133 bool claw::automaton<State, Edge, StateComp, EdgeComp>::state_exists
134 ( const state_type& s ) const
135 {
136  return (m_states.find(s) != m_states.end());
137 } // automaton::state_exists()
138 
139 /*----------------------------------------------------------------------------*/
140 /**
141  * \brief Tell if a state is final.
142  * \param s The state to check.
143  * \pre state_exists(s) == true
144  */
145 template<class State, class Edge, class StateComp, class EdgeComp >
146 bool claw::automaton<State, Edge, StateComp, EdgeComp>::state_is_final
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 /*----------------------------------------------------------------------------*/
155 /**
156  * \brief Tell if a state is an initial state.
157  * \param s The state to check.
158  * \pre state_exists(s) == true
159  */
160 template<class State, class Edge, class StateComp, class EdgeComp >
161 bool claw::automaton<State, Edge, StateComp, EdgeComp>::state_is_initial
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 /*----------------------------------------------------------------------------*/
170 /**
171  * \brief Get the states in the automaton.
172  * \param v (out) The container in which to add the states.
173  * \todo Remove this method and add iterator types.
174  */
175 template<class State, class Edge, class StateComp, class EdgeComp >
176 void claw::automaton<State, Edge, StateComp, EdgeComp>::states
177 (result_state_list& v) const
178 {
179  v.clear();
180  v.resize( m_states.size() );
181  std::transform( m_states.begin(), m_states.end(), v.begin(),
182  const_first<state_type, neighbours_list>() );
183 } // automaton::states()
184 
185 /*----------------------------------------------------------------------------*/
186 /**
187  * \brief Get the final states.
188  * \param v (out) The container in which to add the states.
189  * \todo Remove this method and add iterator types.
190  */
191 template<class State, class Edge, class StateComp, class EdgeComp >
192 void claw::automaton<State, Edge, StateComp, EdgeComp>::final_states
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 /*----------------------------------------------------------------------------*/
201 /**
202  * \brief Get the final states.
203  * \param v (out) The container in which to add the states.
204  * \todo Remove this method and add iterator types.
205  */
206 template<class State, class Edge, class StateComp, class EdgeComp >
207 void claw::automaton<State, Edge, StateComp, EdgeComp>::initial_states
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 /*----------------------------------------------------------------------------*/
216 /**
217  * \brief Get all symbols in the alphabet.
218  * \param v (out) The container in which to add the symbols
219  * \todo Remove this method and add iterator types.
220  */
221 template<class State, class Edge, class StateComp, class EdgeComp >
222 void claw::automaton<State, Edge, StateComp, EdgeComp>::alphabet
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 /*----------------------------------------------------------------------------*/
231 /**
232  * \brief Tell if the automaton recognizes a given pattern.
233  * \param first Iterator on the first symbol in the pattern.
234  * \param last Iterator after the last symbol in the pattern.
235  */
236 template<class State, class Edge, class StateComp, class EdgeComp >
237 template<class InputIterator>
238 bool claw::automaton<State, Edge, StateComp, EdgeComp>::match
239 (InputIterator first, InputIterator last) const
240 {
241  bool ok = false;
242  typename claw::avl<state_type>::const_iterator it;
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 /*----------------------------------------------------------------------------*/
251 /**
252  * \brief Get the number of states.
253  */
254 template<class State, class Edge, class StateComp, class EdgeComp >
255 unsigned int
256 claw::automaton<State, Edge, StateComp, EdgeComp>::states_count() const
257 {
258  return m_states.size();
259 } // automaton::states_count()
260 
261 /*----------------------------------------------------------------------------*/
262 /**
263  * \brief Get the states that can be reached from a given state with a given
264  * symbol.
265  * \param s Initial state.
266  * \param e The symbol on the edge.
267  * \param l (out) The list of reachable states.
268  * \pre state_exists(s) == true
269  * \todo Remove this method and add iterator types.
270  */
271 template<class State, class Edge, class StateComp, class EdgeComp >
272 void claw::automaton<State, Edge, StateComp, EdgeComp>::reachables
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),
283  l.begin(), claw::second<edge_type, state_type>() );
284 } // automaton::reachables()
285 
286 /*----------------------------------------------------------------------------*/
287 /**
288  * \brief Get the states that can be reached from a given state, no matter the
289  * symbol.
290  * \param s Initial state.
291  * \param l (out) The list of reachable states.
292  * \pre state_exists(s) == true
293  * \todo Remove this method and add iterator types.
294  */
295 template<class State, class Edge, class StateComp, class EdgeComp >
296 void claw::automaton<State, Edge, StateComp, EdgeComp>::reachables
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 /*----------------------------------------------------------------------------*/
315 /**
316  * \brief Get all the edges between two states.
317  * \param s1 Source state.
318  * \param s2 Target state.
319  * \param l (out) The list of edges.
320  * \pre (state_exists(s1) == true) && (state_exists(s2) == true)
321  * \todo Remove this method and add iterator types.
322  */
323 template<class State, class Edge, class StateComp, class EdgeComp >
324 void claw::automaton<State, Edge, StateComp, EdgeComp>::edges
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 /*----------------------------------------------------------------------------*/
343 /**
344  * \brief Get all out-edges of a given state, labeled with a given symbol.
345  * \param s1 The source state of the edges.
346  * \param e The symbol on the edges.
347  * \param l (out) The list of edges.
348  * \pre state_exists(s1) == true
349  * \todo Remove this method and add iterator types.
350  */
351 template<class State, class Edge, class StateComp, class EdgeComp >
352 void claw::automaton<State, Edge, StateComp, EdgeComp>::edges
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(),
364  claw::first<edge_type, state_type>() );
365 } // automaton::edges()
366 
367 
368 
369 /*================================== private =================================*/
370 
371 
372 
373 
374 /*----------------------------------------------------------------------------*/
375 /**
376  * \brief Recognize a pattern (recursive and auxiliary method).
377  * \param s The state on which we start the search.
378  * \param first Iterator on the first symbol to recognize.
379  * \param last Iterator past the last symbol to recognize.
380  */
381 template<class State, class Edge, class StateComp, class EdgeComp >
382 template<class InputIterator>
383 bool claw::automaton<State, Edge, StateComp, EdgeComp>::match_aux
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()