lazy.h

00001 /*
00002  * ASTL - the Automaton Standard Template Library.
00003  * C++ generic components for Finite State Automata handling.
00004  * Copyright (C) 2000-2003 Vincent Le Maout (vincent.lemaout@chello.fr).
00005  * 
00006  * This library is free software; you can redistribute it and/or
00007  * modify it under the terms of the GNU Lesser General Public
00008  * License as published by the Free Software Foundation; either
00009  * version 2.1 of the License, or (at your option) any later version.
00010  * 
00011  * This library is distributed in the hope that it will be useful,
00012  * but WITHOUT ANY WARRANTY; without even the implied warranty of
00013  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
00014  * Lesser General Public License for more details.
00015  * 
00016  * You should have received a copy of the GNU Lesser General Public
00017  * License along with this library; if not, write to the Free Software
00018  * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
00019  *
00020  */
00021 
00022 #ifndef ASTL_LAZY_H
00023 #define ASTL_LAZY_H
00024 
00025 #include <astl.h>
00026 #include <map>
00027 #include <utility>
00028 
00029 #define CLASSICAL_LAZY
00030 
00031 using namespace std;
00032 
00033 namespace astl {
00034 
00035 
00036 // - solution using template template: the user does not have to instanciate 
00037 //   the DFA by himself, he only has to pass a template as argument
00038 //   for the cursor template (the DFA must be instanciated with Tag ==
00039 //   Cursor::state_type) 
00040 // - This implementation uses a smart pointer to reference the cache
00041 //   and the map between the visited states of the cursor and their copy
00042 //   in the cache for two reasons: 
00043 //   1. We really need a constant time copy constructor
00044 //   2. We want to keep the cache and the mapping as long as the lazy
00045 //      cursor is alive 
00046 template <typename Cursor, 
00047           template <typename Sigma, typename Tag> class DFA = DFA_matrix>
00048 class lazy_cursor : public cursor_concept
00049 {
00050 public:
00051 #ifdef CLASSICAL_LAZY
00052   typedef DFA<typename Cursor::char_traits, typename Cursor::state_type> DFA_type;
00053 #else
00054   typedef DFA<typename Cursor::char_traits, const typename Cursor::state_type*> DFA_type;
00055 #endif
00056 
00057 protected:
00058   typedef map<typename Cursor::state_type, 
00059     safe<typename DFA_type::state_type, DFA_type::null_state> > mapper;
00060   typename DFA_type::state_type my_sink;
00061   Cursor              c;
00062   smart_ptr<DFA_type> dfa;
00063   smart_ptr<mapper>   mapping;  
00064   safe<typename DFA_type::state_type> q;
00065 
00066 public:
00067   typedef lazy_cursor                   self;
00068   typedef typename DFA_type::state_type state_type;
00069   typedef empty_tag                     tag_type;
00070   typedef typename Cursor::char_type    char_type;
00071   typedef typename Cursor::char_traits  char_traits;
00072 
00073   lazy_cursor(const Cursor &x)
00074     : c(x)
00075     { 
00076       if (!x.sink()) 
00077       {
00078         q = dfa->new_state();
00079 #ifdef CLASSICAL_LAZY
00080         dfa->tag(q) = c.src();
00081         (*mapping)[c.src()] = q;
00082 #else
00083         pair<typename mapper::iterator, bool> p = mapping->insert(make_pair(c.src(), q));
00084         dfa->tag(q) = &(p.first->first);
00085 #endif
00086         dfa->final(q) = c.src_final();
00087         dfa->initial(q);
00088         my_sink = dfa->new_state();
00089       }
00090     }
00091 
00092   // @deprecated
00093   const Cursor& cursor() {
00094     c = dfa->tag(q);
00095     return c;
00096   }
00097 
00098   const Cursor& adaptee() {
00099 #ifdef CLASSICAL_LAZY
00100     c = dfa->tag(q);
00101 #else
00102     c = *dfa->tag(q);
00103 #endif
00104     return c;
00105   }
00106 
00107   const DFA_type& cache() const {
00108     return *dfa;
00109   }
00110 
00111   state_type src() const {
00112     return q;
00113   }
00114 
00115   self& operator=(state_type p) {
00116     q = p;
00117     return *this;
00118   }
00119 
00120   bool src_final() const {
00121     return dfa->final(q);
00122   }
00123 
00124   empty_tag src_tag() const {
00125     return empty_tag();
00126   }
00127 
00128   bool sink() const {
00129     return q == DFA_type::null_state;
00130   }
00131 
00132   state_type sink_state() const {
00133     return DFA_type::null_state;
00134   }
00135 
00136   bool exists(const char_type &a) const {
00137     state_type aim = dfa->delta1(q, a);
00138     switch (aim) {
00139     case my_sink :
00140       return false;
00141 
00142     case DFA_type::null_state :
00143       Cursor tmp = c;
00144       tmp = dfa->tag(q);
00145       return tmp.exists(a);
00146 
00147     default :
00148       return true;
00149     }
00150   }
00151 
00152   bool forward(const char_type &a) {
00153     state_type tmp = dfa->delta1(q, a);
00154     if (tmp == my_sink) {
00155       q = DFA_type::null_state;
00156       return false;
00157     }
00158     if (tmp == DFA_type::null_state)     // transition not in the cache ?
00159     {
00160 #ifdef CLASSICAL_LAZY
00161       c = dfa->tag(q);
00162 #else
00163       c = *dfa->tag(q);
00164 #endif
00165       if (c.forward(a))    // any transition labelled with 'a' ?
00166       { 
00167 #ifndef CLASSICAL_LAZY
00168         pair<typename mapper::iterator, bool> p = mapping->insert(make_pair(c.src(), DFA_type::null_state));
00169         if (p.second == true) {
00170           state_type tmp2 = dfa->new_state();
00171           p.first->second = tmp2;
00172           dfa->final(tmp2) = c.src_final();
00173           dfa->tag(tmp2) = &(p.first->first);
00174         }
00175         tmp = p.first->second;
00176 #else
00177         safe<state_type, DFA_type::null_state> &tmp2 = (*mapping)[c.src()];
00178         if (tmp2 == DFA_type::null_state) {   // not already been there ?
00179           tmp2 = dfa->new_state();
00180           dfa->final(tmp2) = c.src_final();
00181           dfa->tag(tmp2) = c.src();
00182           (*mapping)[c.src()] = tmp2;
00183         }
00184         tmp = tmp2;
00185 #endif
00186         dfa->set_trans(q, a, tmp);
00187       }
00188       else {
00189         dfa->set_trans(q, a, my_sink);
00190         q = DFA_type::null_state;
00191         return false;
00192       }
00193     }
00194     q = tmp;
00195     return true;
00196   }
00197 };
00198 
00199 template <class Cursor>
00200 inline
00201 lazy_cursor<Cursor> lazyc(const Cursor &c) {
00202   return lazy_cursor<Cursor>(c);
00203 }
00204 
00205 
00206 // A lazy cursor which copy tags into the cache
00207 template <class Cursor, 
00208           template <class Sigma, class Tag> class DFA = DFA_matrix>
00209 class lazy_cursor_tag : public cursor_concept
00210 {
00211 public:
00212   typedef DFA<typename Cursor::char_traits, 
00213     pair<typename Cursor::tag_type, typename Cursor::state_type> > DFA_type;
00214 
00215 protected:
00216   typedef map<typename Cursor::state_type, 
00217     safe<typename DFA_type::state_type, DFA_type::null_state> > mapper;
00218   typename DFA_type::state_type my_sink;
00219   Cursor              c;
00220   smart_ptr<DFA_type> dfa;
00221   smart_ptr<mapper>   mapping;  
00222   safe<typename DFA_type::state_type, DFA_type::null_state> q;
00223 
00224 public:
00225   typedef lazy_cursor_tag                   self;
00226   typedef typename DFA_type::state_type state_type;
00227   typedef typename Cursor::tag_type     tag_type;
00228   typedef typename Cursor::char_type    char_type;
00229   typedef typename Cursor::char_traits  char_traits;
00230 
00231   lazy_cursor_tag(const Cursor &x)
00232     : c(x)
00233     { 
00234       if (!x.sink()) 
00235       {
00236         q = dfa->new_state();
00237         dfa->tag(q).second = c.src();
00238         dfa->tag(q).first = c.src_tag();
00239         (*mapping)[c.src()] = q;
00240         dfa->final(q) = c.src_final();
00241         dfa->initial(q);
00242         my_sink = dfa->new_state();
00243       }
00244     }
00245 
00246   const DFA_type& cache() const {
00247     return *dfa;
00248   }
00249 
00250   state_type src() const {
00251     return q;
00252   }
00253 
00254   self& operator=(state_type p) {
00255     q = p;
00256     return *this;
00257   }
00258 
00259   bool src_final() const {
00260     return dfa->final(q);
00261   }
00262 
00263   tag_type src_tag() const {
00264     return dfa->tag(q).first;
00265   }
00266 
00267   bool sink() const {
00268     return q == DFA_type::null_state;
00269   }
00270 
00271   state_type sink_state() const {
00272     return DFA_type::null_state;
00273   }
00274 
00275   bool forward(const char_type &a) {
00276     state_type tmp = dfa->delta1(q, a);
00277     if (tmp == my_sink) {
00278       q = DFA_type::null_state;
00279       return false;
00280     }
00281     if (tmp == DFA_type::null_state)     // transition not in the cache ?
00282     {
00283       c = dfa->tag(q).second;
00284       if (c.forward(a))    // any transition labelled with 'a' ?
00285       { 
00286         safe<state_type, DFA_type::null_state> &tmp2 = (*mapping)[c.src()];
00287         if (tmp2 == DFA_type::null_state) {   // not already been there ?
00288           tmp2 = dfa->new_state();
00289           dfa->final(tmp2) = c.src_final();
00290           dfa->tag(tmp2).second = c.src();
00291           dfa->tag(tmp2).first = c.src_tag();
00292           (*mapping)[c.src()] = tmp2;
00293         }
00294         tmp = tmp2;
00295         dfa->set_trans(q, a, tmp);
00296       }
00297       else {
00298         dfa->set_trans(q, a, my_sink);
00299         q = DFA_type::null_state;
00300         return false;
00301       }
00302     }
00303     q = tmp;
00304     return true;
00305   }
00306 };
00307 
00308 template <class Cursor>
00309 inline
00310 lazy_cursor_tag<Cursor> lazyc_tag(const Cursor &c) {
00311   return lazy_cursor_tag<Cursor>(c);
00312 }
00313 
00314 } // namespace astl
00315      
00316 #endif // ASTL_LAZY_H
00317     
00318 
00319 
00320 
00321 
00322 

Generated on Sun Mar 8 02:41:34 2009 for ASTL by  doxygen 1.5.7.1