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, 2006 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     TIMER_SCOPED("search");
00038     FindBestSearch::search(a, begin, end, eol, f);
00039   }
00040 
00041   template <class InputIterator, class FoundFunctor, class Series, class T>
00042   void
00043   FindBestSearch::search(const Element<Automata<Series>, T>& a,
00044                          const InputIterator& begin,
00045                          const InputIterator& end,
00046                          typename Element<Automata<Series>, T>::
00047                          letter_t eol,
00048                          FoundFunctor& f)
00049   {
00050     WindowedBackSearch::search(a, begin, end, eol, f);
00051   }
00052 
00063   template <class Series, class T, class StatesSet>
00064   static
00065   unsigned int
00066   compute_distances(const Element<Automata<Series>, T>& a,
00067                     std::vector<StatesSet>& distances)
00068   {
00069     precondition(a.initial().size() > 0);
00070     precondition(a.final().size() > 0);
00071     precondition(distances.size() == 0);
00072 
00073     // Typedefs.
00074     typedef typename vcsn::Element<Automata<Series>, T> automaton_t;
00075     AUTOMATON_TYPES(automaton_t);
00076 
00077     // Code.
00078     StatesSet           s_new (a.states().max() + 1);
00079     StatesSet           s_old (a.states().max() + 1);
00080     unsigned int        i = 0;
00081 
00082     s_old.insert(a.initial().begin(), a.initial().end());
00083     for (bool get_out = false; !get_out; ++i)
00084       {
00085         s_new.clear();
00086         distances.push_back(s_old);
00087         if (i > 0)
00088           distances[i].insert(distances[i - 1].begin(),
00089                               distances[i - 1].end());
00090         for (typename StatesSet::const_iterator s = s_old.begin();
00091              s != s_old.end();
00092              ++s)
00093           {
00094             if (a.is_final(*s))
00095               // FIXME: Could be optimized with a return i, but code
00096               // is easier to read this way.
00097               get_out = true;
00098             a.deltac(s_new, *s, delta_kind::states());
00099           }
00100         std::swap(s_new, s_old);
00101       }
00102 
00103     postcondition(i == distances.size());
00104     return i - 1;
00105   }
00106 
00121   template <class InputIterator, class Series, class T, class StatesSet>
00122   static
00123   std::pair<bool, unsigned int>
00124   window_backsearch(const misc::Window<InputIterator,
00125                     typename Element<Automata<Series>, T>::letter_t>& w,
00126                     const Element<Automata<Series>, T>& a,
00127                     const std::vector<StatesSet>& distances)
00128   {
00129     precondition(w.size() > 0);
00130 
00131     // Typedefs.
00132     typedef typename vcsn::Element<Automata<Series>, T>         automaton_t;
00133     AUTOMATON_TYPES(automaton_t);
00134     AUTOMATON_FREEMONOID_TYPES(automaton_t);
00135     typedef typename misc::Window<InputIterator, letter_t>      window_t;
00136     typedef typename window_t::length_t                         length_t;
00137     typedef misc::Bitset                                        bitset_t;
00138 
00139     // Code.
00140     bitset_t    s_new (a.states().max() + 1);
00141     bitset_t    s_old (a.states().max() + 1);
00142     int         pos = w.size();
00143     length_t    critpos = pos;
00144 
00145     s_old.insert(distances[pos].begin(), distances[pos].end());
00146     while ((--pos >= 0) && !s_old.empty())
00147       {
00148         s_new.clear();
00149         for (bitset_t::const_iterator s = s_old.begin(); s != s_old.end(); ++s)
00150           if (distances[pos + 1].find(*s) != distances[pos + 1].end())
00151             {
00152               if (a.is_initial(*s))
00153                 critpos = pos + 1;
00154               a.letter_rdeltac(s_new, *s, w[pos], delta_kind::states());
00155             }
00156         std::swap(s_new, s_old);
00157       }
00158     if (pos < 0)
00159       for (bitset_t::const_iterator s = s_old.begin(); s != s_old.end(); ++s)
00160         if (a.is_initial(*s))
00161           return std::make_pair(true, critpos);
00162     return std::make_pair(false, critpos);
00163   }
00164 
00166   template <class InputIterator, class FoundFunctor, class Series, class T>
00167   static
00168   InputIterator
00169   confirm_and_report_match(const misc::Window<InputIterator,
00170                            typename Element<Automata<Series>, T>::letter_t>& w,
00171                            const Element<Automata<Series>, T>& a,
00172                            FoundFunctor& f)
00173   {
00174     // Typedefs.
00175     typedef typename vcsn::Element<Automata<Series>, T>         automaton_t;
00176     AUTOMATON_TYPES(automaton_t);
00177     AUTOMATON_FREEMONOID_TYPES(automaton_t);
00178     typedef typename misc::Window<InputIterator, letter_t>      window_t;
00179     typedef typename window_t::length_t                         length_t;
00180     typedef typename window_t::iterator_t                       iterator_t;
00181     typedef misc::Bitset                                        bitset_t;
00182 
00183     // Code.
00184     bitset_t    s_old (a.states().max() + 1);
00185     bitset_t    s_new (a.states().max() + 1);
00186     iterator_t  pos = w.stream();
00187     iterator_t  last = pos;
00188 
00189     s_old.insert(a.initial().begin(), a.initial().end());
00190     while (!s_old.empty() && (*pos != w.eol_value()))
00191       {
00192         s_new.clear();
00193         for (bitset_t::const_iterator s = s_old.begin(); s != s_old.end(); ++s)
00194           {
00195             if (a.is_final(*s))
00196               last = pos - 1;
00197             a.letter_deltac(s_new, *s, *pos, delta_kind::states());
00198           }
00199         std::swap(s_old, s_new);
00200         ++pos;
00201       }
00202     for (bitset_t::const_iterator s = s_old.begin(); s != s_old.end(); ++s)
00203       if (a.is_final(*s))
00204         last = pos - 1;
00205     if (last != pos)
00206       return f(w.begin(), w.stream(), last);
00207     else
00208       return w.stream();
00209   }
00210 
00213   template <class InputIterator, class FoundFunctor, class Series, class T>
00214   void
00215   WindowedBackSearch::search(const Element<Automata<Series>, T>& a,
00216                              const InputIterator& begin,
00217                              const InputIterator& end,
00218                              typename Element<Automata<Series>, T>::
00219                              letter_t eol,
00220                              FoundFunctor& f)
00221   {
00222     // Typedefs.
00223     typedef typename vcsn::Element<Automata<Series>, T>         automaton_t;
00224     AUTOMATON_TYPES(automaton_t);
00225     AUTOMATON_FREEMONOID_TYPES(automaton_t);
00226     typedef typename misc::Window<InputIterator, letter_t>      window_t;
00227     typedef typename window_t::length_t                         length_t;
00228     typedef misc::Bitset                                        bitset_t;
00229 
00230     // Code.
00231     std::vector<bitset_t>       distances;
00232     length_t                    wl = compute_distances(a, distances);
00233 
00234     if (wl == 0)
00235       WARNING("Search match every position in the stream, ignored.");
00236     else
00237       {
00238         window_t                w (begin, end, eol, wl);
00239         InputIterator           it;
00240 
00241         while (!w.eof())
00242           {
00243             if (w.size() != wl)
00244               w.shift();
00245             else
00246               {
00247                 std::pair<bool, length_t> p =
00248                   window_backsearch(w, a, distances);
00249                 if (p.first &&
00250                     (it = confirm_and_report_match(w, a, f)) != w.stream())
00251                   w.moveto(it);
00252                 else
00253                   w.shift(p.second);
00254               }
00255           }
00256       }
00257   }
00258 
00259 } // vcsn
00260 
00261 #endif // ! VCSN_ALGORITHMS_SEARCH_HXX

Generated on Sun Jul 29 19:35:29 2007 for Vaucanson by  doxygen 1.5.2