Vaucanson  1.4.1
search.hxx
1 // search.hxx: this file is part of the Vaucanson project.
2 //
3 // Vaucanson, a generic library for finite state machines.
4 //
5 // Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2008 The Vaucanson Group.
6 //
7 // This program is free software; you can redistribute it and/or
8 // modify it under the terms of the GNU General Public License
9 // as published by the Free Software Foundation; either version 2
10 // of the License, or (at your option) any later version.
11 //
12 // The complete GNU General Public Licence Notice can be found as the
13 // `COPYING' file in the root directory.
14 //
15 // The Vaucanson Group consists of people listed in the `AUTHORS' file.
16 //
17 #ifndef VCSN_ALGORITHMS_SEARCH_HXX
18 # define VCSN_ALGORITHMS_SEARCH_HXX
19 
20 # include <vaucanson/algorithms/search.hh>
21 
22 # include <vaucanson/misc/window.hh>
23 # include <vaucanson/misc/bitset.hh>
24 
25 # include <vector>
26 
27 namespace vcsn {
28 
29  template <typename InputIterator, typename FoundFunctor, typename Series, typename Kind, typename T>
30  void
31  search(const Element<Automata<Series, Kind>, T>& a,
32  const InputIterator& begin,
33  const InputIterator& end,
34  typename Element<Automata<Series, Kind>, T>::letter_t eol,
35  FoundFunctor& f)
36  {
37  BENCH_TASK_SCOPED("search");
38  FindBestSearch::search(a, begin, end, eol, f);
39  }
40 
41  template <typename InputIterator, typename FoundFunctor, typename Series, typename Kind, typename T>
42  void
43  FindBestSearch::search(const Element<Automata<Series, Kind>, T>& a,
44  const InputIterator& begin,
45  const InputIterator& end,
46  typename Element<Automata<Series, Kind>, T>::
47  letter_t eol,
48  FoundFunctor& f)
49  {
50  WindowedBackSearch::search(a, begin, end, eol, f);
51  }
52 
63  template <typename Series, typename Kind, typename T, typename StatesSet>
64  static
65  unsigned int
66  compute_distances(const Element<Automata<Series, Kind>, T>& a,
67  std::vector<StatesSet>& distances)
68  {
69  precondition(a.initial().size() > 0);
70  precondition(a.final().size() > 0);
71  precondition(distances.size() == 0);
72 
73  // Typedefs.
74  typedef typename vcsn::Element<Automata<Series, Kind>, T> automaton_t;
75  AUTOMATON_TYPES(automaton_t);
76 
77  // Code.
78  StatesSet s_new (a.states().back() + 1);
79  StatesSet s_old (a.states().back() + 1);
80 
81  s_old.insert(a.initial().begin(), a.initial().end());
82  for (unsigned int i = 0; true; ++i)
83  {
84  s_new.clear();
85  distances.push_back(s_old);
86  if (i > 0)
87  distances[i].insert(distances[i - 1].begin(),
88  distances[i - 1].end());
89  for (typename StatesSet::const_iterator s = s_old.begin();
90  s != s_old.end();
91  ++s)
92  {
93  if (a.is_final(*s))
94  {
95  postcondition(i == distances.size());
96  return i;
97  }
98  for (delta_iterator i(a.value(), *s);
99  ! i.done();
100  i.next())
101  s_new.insert(a.dst_of(*i));
102  s_old = s_new;
103  }
104  }
105  }
106 
121  template <typename InputIterator, typename Series, typename Kind, typename T, typename StatesSet>
122  static
123  std::pair<bool, unsigned int>
124  window_backsearch(const misc::Window<InputIterator,
125  typename Element<Automata<Series, Kind>, T>::letter_t>& w,
126  const Element<Automata<Series, Kind>, T>& a,
127  const std::vector<StatesSet>& distances)
128  {
129  precondition(w.size() > 0);
130 
131  // Typedefs.
132  typedef typename vcsn::Element<Automata<Series, Kind>, T> automaton_t;
133  AUTOMATON_TYPES(automaton_t);
134  AUTOMATON_FREEMONOID_TYPES(automaton_t);
135  typedef typename misc::Window<InputIterator, letter_t> window_t;
136  typedef typename window_t::length_t length_t;
137  typedef misc::Bitset bitset_t;
138 
139  // Code.
140  bitset_t s_new (a.states().back() + 1);
141  bitset_t s_old (a.states().back() + 1);
142  int pos = w.size();
143  length_t critpos = pos;
144 
145  s_old.insert(distances[pos].begin(), distances[pos].end());
146  while ((--pos >= 0) && !s_old.empty())
147  {
148  s_new.clear();
149  for (bitset_t::const_iterator s = s_old.begin(); s != s_old.end(); ++s)
150  if (distances[pos + 1].find(*s) != distances[pos + 1].end())
151  {
152  if (a.is_initial(*s))
153  critpos = pos + 1;
154  std::insert_iterator<bitset_t> i(s_new, s_new.begin());
155  for (delta_iterator t(a.value(), *s); ! t.done(); t.next())
156  {
157  monoid_elt_t w(a.series_of(*t).structure().monoid(), w[pos]);
158  if (a.series_of(*t).get(w) != a.series().semiring().wzero_)
159  *i++ = a.src_of(*t);
160  }
161  }
162  std::swap(s_new, s_old);
163  }
164  if (pos < 0)
165  for (bitset_t::const_iterator s = s_old.begin(); s != s_old.end(); ++s)
166  if (a.is_initial(*s))
167  return std::make_pair(true, critpos);
168  return std::make_pair(false, critpos);
169  }
170 
172  template <typename InputIterator, typename FoundFunctor, typename Series, typename Kind, typename T>
173  static
174  InputIterator
175  confirm_and_report_match(const misc::Window<InputIterator,
176  typename Element<Automata<Series, Kind>, T>::letter_t>& w,
177  const Element<Automata<Series, Kind>, T>& a,
178  FoundFunctor& f)
179  {
180  // Typedefs.
181  typedef typename vcsn::Element<Automata<Series, Kind>, T> automaton_t;
182  AUTOMATON_TYPES(automaton_t);
183  AUTOMATON_FREEMONOID_TYPES(automaton_t);
184  typedef typename misc::Window<InputIterator, letter_t> window_t;
185  typedef typename window_t::length_t length_t;
186  typedef typename window_t::iterator_t iterator_t;
187  typedef misc::Bitset bitset_t;
188 
189  // Code.
190  bitset_t s_old (a.states().back() + 1);
191  bitset_t s_new (a.states().back() + 1);
192  iterator_t pos = w.stream();
193  iterator_t last = pos;
194 
195  s_old.insert(a.initial().begin(), a.initial().end());
196  while (!s_old.empty() && (*pos != w.eol_value()))
197  {
198  s_new.clear();
199  for (bitset_t::const_iterator s = s_old.begin(); s != s_old.end(); ++s)
200  {
201  if (a.is_final(*s))
202  last = pos - 1;
203  std::insert_iterator<bitset_t> i(s_new, s_new.begin());
204  for (delta_iterator t(a.value(), *s); ! t.done(); t.next())
205  {
206  monoid_elt_t w(a.series_of(*t).structure().monoid(), *pos);
207  if (a.series_of(*t).get(w) != a.series().semiring().wzero_)
208  *i++ = a.dst_of(*t);
209  }
210  }
211  std::swap(s_old, s_new);
212  ++pos;
213  }
214  for (bitset_t::const_iterator s = s_old.begin(); s != s_old.end(); ++s)
215  if (a.is_final(*s))
216  last = pos - 1;
217  if (last != pos)
218  return f(w.begin(), w.stream(), last);
219  else
220  return w.stream();
221  }
222 
225  template <typename InputIterator, typename FoundFunctor, typename Series, typename Kind, typename T>
226  void
227  WindowedBackSearch::search(const Element<Automata<Series, Kind>, T>& a,
228  const InputIterator& begin,
229  const InputIterator& end,
230  typename Element<Automata<Series, Kind>, T>::
231  letter_t eol,
232  FoundFunctor& f)
233  {
234  // Typedefs.
235  typedef typename vcsn::Element<Automata<Series, Kind>, T> automaton_t;
236  AUTOMATON_TYPES(automaton_t);
237  AUTOMATON_FREEMONOID_TYPES(automaton_t);
238  typedef typename misc::Window<InputIterator, letter_t> window_t;
239  typedef typename window_t::length_t length_t;
240  typedef misc::Bitset bitset_t;
241 
242  // Code.
243  std::vector<bitset_t> distances;
244  length_t wl = compute_distances(a, distances);
245 
246  if (wl == 0)
247  WARNING("Search match every position in the stream, ignored.");
248  else
249  {
250  window_t w (begin, end, eol, wl);
251  InputIterator it;
252 
253  while (!w.eof())
254  {
255  if (w.size() != wl)
256  w.shift();
257  else
258  {
259  std::pair<bool, length_t> p =
260  window_backsearch(w, a, distances);
261  if (p.first &&
262  (it = confirm_and_report_match(w, a, f)) != w.stream())
263  w.moveto(it);
264  else
265  w.shift(p.second);
266  }
267  }
268  }
269  }
270 
271 } // vcsn
272 
273 #endif // ! VCSN_ALGORITHMS_SEARCH_HXX
Generated on Sat Jul 14 2012 18:46:40 for Vaucanson by   doxygen 1.8.1.1