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/*----------------------------------------------------------------------------*/
38template<class State, class Edge, class StateComp, class EdgeComp >
39typename claw::automaton<State, Edge, StateComp, EdgeComp>::state_compare
40claw::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 */
49template<class State, class Edge, class StateComp, class EdgeComp >
50void 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 */
67template<class State, class Edge, class StateComp, class EdgeComp >
68void 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 */
88template<class State, class Edge, class StateComp, class EdgeComp >
89void 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 */
106template<class State, class Edge, class StateComp, class EdgeComp >
107void 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 */
119template<class State, class Edge, class StateComp, class EdgeComp >
120void 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 */
132template<class State, class Edge, class StateComp, class EdgeComp >
133bool 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 */
145template<class State, class Edge, class StateComp, class EdgeComp >
146bool 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 */
160template<class State, class Edge, class StateComp, class EdgeComp >
161bool 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 */
175template<class State, class Edge, class StateComp, class EdgeComp >
176void 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 */
191template<class State, class Edge, class StateComp, class EdgeComp >
192void 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 */
206template<class State, class Edge, class StateComp, class EdgeComp >
207void 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 */
221template<class State, class Edge, class StateComp, class EdgeComp >
222void 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 */
236template<class State, class Edge, class StateComp, class EdgeComp >
237template<class InputIterator>
238bool 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 */
254template<class State, class Edge, class StateComp, class EdgeComp >
255unsigned int
256claw::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 */
271template<class State, class Edge, class StateComp, class EdgeComp >
272void 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 */
295template<class State, class Edge, class StateComp, class EdgeComp >
296void 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 */
323template<class State, class Edge, class StateComp, class EdgeComp >
324void 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 */
351template<class State, class Edge, class StateComp, class EdgeComp >
352void 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 */
381template<class State, class Edge, class StateComp, class EdgeComp >
382template<class InputIterator>
383bool 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()