search.hxx

00001 // search.hxx: this file is part of the Vaucanson project.
00002 //
00003 // Vaucanson, a generic library for finite state machines.
00004 //
00005 // Copyright (C) 2001, 2002, 2003, 2004, 2005 The Vaucanson Group.
00006 //
00007 // This program is free software; you can redistribute it and/or
00008 // modify it under the terms of the GNU General Public License
00009 // as published by the Free Software Foundation; either version 2
00010 // of the License, or (at your option) any later version.
00011 //
00012 // The complete GNU General Public Licence Notice can be found as the
00013 // `COPYING' file in the root directory.
00014 //
00015 // The Vaucanson Group consists of people listed in the `AUTHORS' file.
00016 //
00017 #ifndef VCSN_ALGORITHMS_SEARCH_HXX
00018 # define VCSN_ALGORITHMS_SEARCH_HXX
00019 
00020 # include <vaucanson/algorithms/search.hh>
00021 
00022 # include <vaucanson/misc/window.hh>
00023 # include <vaucanson/misc/bitset.hh>
00024 
00025 # include <vector>
00026 
00027 namespace vcsn {
00028 
00029   template <class InputIterator, class FoundFunctor, class Series, class T>
00030   void
00031   search(const Element<Automata<Series>, T>& a,
00032          const InputIterator& begin,
00033          const InputIterator& end,
00034          typename Element<Automata<Series>, T>::letter_t eol,
00035          FoundFunctor& f)
00036   {
00037     FindBestSearch::search(a, begin, end, eol, f);
00038   }
00039 
00040   template <class InputIterator, class FoundFunctor, class Series, class T>
00041   void
00042   FindBestSearch::search(const Element<Automata<Series>, T>& a,
00043                          const InputIterator& begin,
00044                          const InputIterator& end,
00045                          typename Element<Automata<Series>, T>::
00046                          letter_t eol,
00047                          FoundFunctor& f)
00048   {
00049     WindowedBackSearch::search(a, begin, end, eol, f);
00050   }
00051 
00062   template <class Series, class T, class StatesSet>
00063   static
00064   unsigned int
00065   compute_distances(const Element<Automata<Series>, T>& a,
00066                     std::vector<StatesSet>& distances)
00067   {
00068     precondition(a.initial().size() > 0);
00069     precondition(a.final().size() > 0);
00070     precondition(distances.size() == 0);
00071 
00072     // Typedefs.
00073     typedef typename vcsn::Element<Automata<Series>, T> automaton_t;
00074     AUTOMATON_TYPES(automaton_t);
00075 
00076     // Code.
00077     StatesSet           s_new (a.states().max() + 1);
00078     StatesSet           s_old (a.states().max() + 1);
00079     unsigned int        i = 0;
00080 
00081     s_old.insert(a.initial().begin(), a.initial().end());
00082     for (bool get_out = false; !get_out; ++i)
00083       {
00084         s_new.clear();
00085         distances.push_back(s_old);
00086         if (i > 0)
00087           distances[i].insert(distances[i - 1].begin(),
00088                               distances[i - 1].end());
00089         for (typename StatesSet::const_iterator s = s_old.begin();
00090              s != s_old.end();
00091              ++s)
00092           {
00093             if (a.is_final(*s))
00094               // FIXME: Could be optimized with a return i, but code
00095               // is easier to read this way.
00096               get_out = true;
00097             a.deltac(s_new, *s, delta_kind::states());
00098           }
00099         std::swap(s_new, s_old);
00100       }
00101 
00102     postcondition(i == distances.size());
00103     return i - 1;
00104   }
00105 
00120   template <class InputIterator, class Series, class T, class StatesSet>
00121   static
00122   std::pair<bool, unsigned int>
00123   window_backsearch(const utility::Window<InputIterator,
00124                     typename Element<Automata<Series>, T>::letter_t>& w,
00125                     const Element<Automata<Series>, T>& a,
00126                     const std::vector<StatesSet>& distances)
00127   {
00128     precondition(w.size() > 0);
00129 
00130     // Typedefs.
00131     typedef typename vcsn::Element<Automata<Series>, T>         automaton_t;
00132     AUTOMATON_TYPES(automaton_t);
00133     AUTOMATON_FREEMONOID_TYPES(automaton_t);
00134     typedef typename utility::Window<InputIterator, letter_t>   window_t;
00135     typedef typename window_t::length_t                         length_t;
00136     typedef utility::Bitset                                     bitset_t;
00137 
00138     // Code.
00139     bitset_t    s_new (a.states().max() + 1);
00140     bitset_t    s_old (a.states().max() + 1);
00141     int         pos = w.size();
00142     length_t    critpos = pos;
00143 
00144     s_old.insert(distances[pos].begin(), distances[pos].end());
00145     while ((--pos >= 0) && !s_old.empty())
00146       {
00147         s_new.clear();
00148         for (bitset_t::const_iterator s = s_old.begin(); s != s_old.end(); ++s)
00149           if (distances[pos + 1].find(*s) != distances[pos + 1].end())
00150             {
00151               if (a.is_initial(*s))
00152                 critpos = pos + 1;
00153               a.letter_rdeltac(s_new, *s, w[pos], delta_kind::states());
00154             }
00155         std::swap(s_new, s_old);
00156       }
00157     if (pos < 0)
00158       for (bitset_t::const_iterator s = s_old.begin(); s != s_old.end(); ++s)
00159         if (a.is_initial(*s))
00160           return std::make_pair(true, critpos);
00161     return std::make_pair(false, critpos);
00162   }
00163 
00165   template <class InputIterator, class FoundFunctor, class Series, class T>
00166   static
00167   InputIterator
00168   confirm_and_report_match(const utility::Window<InputIterator,
00169                            typename Element<Automata<Series>, T>::letter_t>& w,
00170                            const Element<Automata<Series>, T>& a,
00171                            FoundFunctor& f)
00172   {
00173     // Typedefs.
00174     typedef typename vcsn::Element<Automata<Series>, T>         automaton_t;
00175     AUTOMATON_TYPES(automaton_t);
00176     AUTOMATON_FREEMONOID_TYPES(automaton_t);
00177     typedef typename utility::Window<InputIterator, letter_t>   window_t;
00178     typedef typename window_t::length_t                         length_t;
00179     typedef typename window_t::iterator_t                       iterator_t;
00180     typedef utility::Bitset                                     bitset_t;
00181 
00182     // Code.
00183     bitset_t    s_old (a.states().max() + 1);
00184     bitset_t    s_new (a.states().max() + 1);
00185     iterator_t  pos = w.stream();
00186     iterator_t  last = pos;
00187 
00188     s_old.insert(a.initial().begin(), a.initial().end());
00189     while (!s_old.empty() && (*pos != w.eol_value()))
00190       {
00191         s_new.clear();
00192         for (bitset_t::const_iterator s = s_old.begin(); s != s_old.end(); ++s)
00193           {
00194             if (a.is_final(*s))
00195               last = pos - 1;
00196             a.letter_deltac(s_new, *s, *pos, delta_kind::states());
00197           }
00198         std::swap(s_old, s_new);
00199         ++pos;
00200       }
00201     for (bitset_t::const_iterator s = s_old.begin(); s != s_old.end(); ++s)
00202       if (a.is_final(*s))
00203         last = pos - 1;
00204     if (last != pos)
00205       return f(w.begin(), w.stream(), last);
00206     else
00207       return w.stream();
00208   }
00209 
00212   template <class InputIterator, class FoundFunctor, class Series, class T>
00213   void
00214   WindowedBackSearch::search(const Element<Automata<Series>, T>& a,
00215                              const InputIterator& begin,
00216                              const InputIterator& end,
00217                              typename Element<Automata<Series>, T>::
00218                              letter_t eol,
00219                              FoundFunctor& f)
00220   {
00221     // Typedefs.
00222     typedef typename vcsn::Element<Automata<Series>, T>         automaton_t;
00223     AUTOMATON_TYPES(automaton_t);
00224     AUTOMATON_FREEMONOID_TYPES(automaton_t);
00225     typedef typename utility::Window<InputIterator, letter_t>   window_t;
00226     typedef typename window_t::length_t                         length_t;
00227     typedef utility::Bitset                                     bitset_t;
00228 
00229     // Code.
00230     std::vector<bitset_t>       distances;
00231     length_t                    wl = compute_distances(a, distances);
00232 
00233     if (wl == 0)
00234       warning("Search match every position in the stream, ignored.");
00235     else
00236       {
00237         window_t                w (begin, end, eol, wl);
00238         InputIterator           it;
00239 
00240         while (!w.eof())
00241           {
00242             if (w.size() != wl)
00243               w.shift();
00244             else
00245               {
00246                 std::pair<bool, length_t> p =
00247                   window_backsearch(w, a, distances);
00248                 if (p.first &&
00249                     (it = confirm_and_report_match(w, a, f)) != w.stream())
00250                   w.moveto(it);
00251                 else
00252                   w.shift(p.second);
00253               }
00254           }
00255       }
00256   }
00257 
00258 } // vcsn
00259 
00260 #endif // ! VCSN_ALGORITHMS_SEARCH_HXX

Generated on Fri Jul 28 12:18:51 2006 for Vaucanson by  doxygen 1.4.6