determinize.h

00001 /*
00002  * ASTL - the Automaton Standard Template Library.
00003  * C++ generic components for Finite State Automata handling.
00004  * Copyright (C) 2000-2005 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_DETERMINIZE_H
00023 #define ASTL_DETERMINIZE_H
00024 
00025 #include <astl.h>
00026 #include <closure.h>
00027 #include <set> 
00028 #include <iterator>     // insert_iterator 
00029 
00030 using namespace std; 
00031 
00032 namespace astl { 
00033 
00034 // Map a set of tag to a single tag (tag determinization)
00035 template <typename NFA>
00036 struct default_tag_mapper 
00037 { 
00038   typedef empty result_type; 
00039 
00040   // Requirements on types:
00041   // InputIterator::value_type == NFA::state_type
00042   template <typename InputIterator> 
00043   result_type operator()(const NFA&, InputIterator, 
00044                          InputIterator) const { 
00045     return empty();
00046   } 
00047 }; 
00048 
00055 template <typename NFA, typename TagMapper = default_tag_mapper<NFA> > 
00056 class dcursor : public cursor_concept 
00057 { 
00058 public: 
00059   typedef dcursor                         self; 
00060   typedef set<typename NFA::state_type>   state_type; 
00061   typedef typename TagMapper::result_type tag_type; 
00062   typedef typename NFA::char_traits       char_traits; 
00063   typedef typename NFA::char_type         char_type; 
00064 
00065 protected: 
00066   const NFA *nfa; 
00067   state_type q; 
00068 
00069 public: 
00070   dcursor() 
00071   { } 
00072 
00073   dcursor(const NFA &a) 
00074     : nfa(&a) 
00075   { } 
00076  
00077   dcursor(const NFA &a, typename NFA::state_type p) 
00078     : nfa(&a) { 
00079     if (p != a.null_state) q.insert(p);
00080   } 
00081 
00082   dcursor(const NFA &a, const state_type& p) 
00083     : nfa(&a), q(p) 
00084   { } 
00085 
00086   state_type src() const { return q; } 
00087 
00088   self& operator=(const typename NFA::state_type& p) { 
00089     q.clear();
00090     q.insert(p);
00091     return *this; 
00092   } 
00093 
00094   self& operator=(const state_type& p) { 
00095     q = p; 
00096     return *this; 
00097   } 
00098 
00099   self& operator=(const self &x) { 
00100     nfa = x.nfa; 
00101     q = x.q; 
00102     return *this; 
00103   } 
00104 
00105   bool operator==(const self &x) const { return q == x.q && nfa == x.nfa; } 
00106 
00107   bool sink() const { return q.empty(); } 
00108 
00109   state_type sink_state() const { return state_type(); } 
00110   
00111   bool forward(const char_type& a) { 
00112     state_type p; 
00113     insert_iterator<state_type> j(p, p.begin()); 
00114     for(typename state_type::const_iterator i = q.begin(); i != q.end(); ++i) 
00115       nfa->delta1(*i, a, j); 
00116     q.swap(p);   // constant time assignment 
00117     return !sink(); 
00118   } 
00119   
00120   bool src_final() const { 
00121     for(typename state_type::const_iterator i = q.begin(); i != q.end(); ++i) 
00122       if (nfa->final(*i)) return true; 
00123     return false; 
00124   } 
00125 
00126   tag_type src_tag() const { return TagMapper()(*nfa, q.begin(), q.end()); } 
00127   
00128   bool exists(const char_type& a) const { 
00129     state_type p; 
00130     insert_iterator<state_type> j(p, p.begin()); 
00131     for(typename state_type::const_iterator i = q.begin(); i != q.end(); ++i) { 
00132       nfa->delta1(*i, a, j); 
00133       if (!p.empty()) return true; 
00134     } 
00135     return false; 
00136   } 
00137 }; 
00138 
00145 template <typename NFA, typename TagMapper = default_tag_mapper<NFA> > 
00146 class forward_dcursor 
00147   : public dcursor<NFA, TagMapper>, public forward_cursor_concept 
00148 { 
00149 public: 
00150   typedef forward_dcursor             self; 
00151   typedef dcursor<NFA, TagMapper>     super; 
00152   typedef typename super::char_traits char_traits;
00153   typedef typename super::tag_type    tag_type;
00154   typedef typename super::char_type   char_type;
00155   typedef typename super::state_type  state_type;
00156   typedef forward_cursor_concept      concept;
00157 
00158 
00159 protected: 
00160   char_type a;
00161   state_type p; 
00162 
00163 public: 
00164   forward_dcursor() 
00165   { } 
00166 
00167   forward_dcursor(const NFA &n) 
00168     : super(n) 
00169   { } 
00170 
00171   forward_dcursor(const NFA &n, typename NFA::state_type p) 
00172     : super(n, p) 
00173   { } 
00174 
00175   forward_dcursor(const NFA &n, const state_type& s) 
00176     : super(n, s) 
00177   { } 
00178   
00179   self& operator=(const self &x) { 
00180     super::operator=(x); 
00181     a = x.a;
00182     p = x.p;
00183     return *this; 
00184   } 
00185 
00186   self& operator=(const state_type &x) { 
00187     super::operator=(x); 
00188     return *this; 
00189   } 
00190 
00191   self& operator=(typename NFA::state_type x) { 
00192     super::operator=(x); 
00193     return *this; 
00194   } 
00195 
00196   bool operator==(const self &x) const { 
00197     return super::operator==(x) && super::char_traits::eq(a, x.a)
00198       && p == x.p;
00199   } 
00200 
00201   char_type letter() const { return a;} 
00202 
00203   bool first() { 
00204     p.clear();
00205     insert_iterator<state_type> j(p, p.begin()); 
00206 
00207     typename state_type::const_iterator i;
00208     typename NFA::edges_type::const_iterator first 
00209       = nfa->delta2(*q.begin()).end();
00210     typename NFA::edges_type::const_iterator last = first, k;
00211     for(i = q.begin(); i != q.end(); ++i) {
00212       k = nfa->delta2(*i).begin();
00213       if (k != nfa->delta2(*i).end()) 
00214         if (first == last || super::char_traits::lt((*k).first, (*first).first)) 
00215           first = k;
00216     }
00217 
00218     if (first == last) return false;
00219     a = (*first).first;
00220     for(i = q.begin(); i != q.end(); ++i)
00221       nfa->delta1(*i, a, j);
00222       
00223     return !p.empty();
00224   } 
00225 
00226   bool next() { 
00227     p.clear();
00228     insert_iterator<state_type> j(p, p.begin()); 
00229     char_type tmp = a;
00230 
00231     typename state_type::const_iterator i;
00232     typename NFA::edges_type::const_iterator k;
00233     for(i = q.begin(); i != q.end(); ++i) {
00234       k = nfa->delta2(*i).upper_bound(tmp);
00235       if (k != nfa->delta2(*i).end())
00236         if (tmp == a || super::char_traits::lt((*k).first, a)) 
00237           a = (*k).first;
00238     }
00239 
00240     if (a == tmp) return false;
00241     for(i = q.begin(); i != q.end(); ++i)
00242       nfa->delta1(*i, a, j);
00243 
00244     return !p.empty();
00245   }                
00246 
00247   void forward() { q.swap(p); } 
00248 
00249   bool forward(const char_type& c) { return super::forward(c); }
00250 
00251   bool find(const char_type& c) {
00252     p.clear();
00253     insert_iterator<state_type> j(p, p.begin()); 
00254     a = c;
00255 
00256     for(typename state_type::const_iterator i = q.begin(); 
00257         i != q.end(); ++i) 
00258       nfa->delta1(*i, c, j); 
00259 
00260     return !p.empty();
00261   } 
00262 
00263   state_type aim() const { return p; } 
00264 
00265   bool aim_final() const { 
00266     for(typename state_type::const_iterator i = p.begin(); i != p.end(); ++i) 
00267       if (nfa->final(*i)) return true; 
00268     return false; 
00269   } 
00270                  
00271   tag_type aim_tag() const { 
00272     return TagMapper()(*nfa, p.begin(), p.end()); 
00273   } 
00274 
00275 protected:
00276   using super::nfa;
00277   using super::q;
00278 }; 
00279 
00280 template <typename NFA, typename TagMapper = default_tag_mapper<NFA> >
00281 class async_forward_dcursor : public forward_dcursor<NFA, TagMapper>
00282 {
00283 public:
00284   typedef async_forward_dcursor           self;
00285   typedef forward_dcursor<NFA, TagMapper> super;
00286   typedef typename super::char_type       char_type;
00287   typedef typename super::state_type      state_type;
00288 
00289 protected:
00290   char_type x;
00291 
00292 public:
00293   async_forward_dcursor()
00294     : super()
00295   { }
00296 
00297   async_forward_dcursor(const NFA& n, const char_type &a)
00298     : super(n), x(a)
00299   { }
00300 
00301   async_forward_dcursor(const NFA &n, const char_type &a, 
00302                         typename NFA::state_type p) 
00303     : super(n, p), x(a) { 
00304     epsilon_closure(q);
00305   } 
00306 
00307   async_forward_dcursor(const NFA &n, const char_type &a, const state_type& s) 
00308     : super(n, s), x(a) { 
00309     epsilon_closure(q);
00310   } 
00311   
00312   self& operator=(const self &y) { 
00313     super::operator=(y);
00314     x = y.x;
00315     return *this; 
00316   } 
00317 
00318   self& operator=(const state_type &y) { 
00319     super::operator=(y);
00320     epsilon_closure(q);
00321     return *this; 
00322   } 
00323 
00324   self& operator=(typename NFA::state_type y) { 
00325     super::operator=(y);
00326     epsilon_closure(q);
00327     return *this; 
00328   } 
00329 
00330   void forward() { super::forward(); }
00331     
00332   bool forward(const char_type& a) {
00333     if (super::forward(a)) {
00334       epsilon_closure(q);
00335       return true;
00336     }
00337     return false;
00338   }
00339 
00340   bool find(const char_type& a) {
00341     if (super::find(a)) {
00342       epsilon_closure(p);
00343       return true;
00344     }
00345     return false;
00346   }
00347       
00348   bool first() {
00349     if (super::first()) {
00350       if (super::letter() == x)
00351         return next();
00352       else {
00353         epsilon_closure(p);
00354         return true;
00355       }
00356     }
00357     return false;
00358   }
00359       
00360   bool next() {
00361     if (super::next()) {
00362       if (super::letter() == x) 
00363         return next();
00364       else {
00365         epsilon_closure(p);
00366         return true;
00367       }
00368     }
00369     return false;
00370   }      
00371 
00372 protected:
00373   using super::q;
00374   using super::nfa;
00375   using super::p;
00376 
00377   void epsilon_closure(state_type &s) {
00378     state_type tmp = s;
00379     insert_iterator<state_type> c(s, s.begin());
00380     closure_cursor<transition_cursor<NFA> > t(transitionc(*nfa, NFA::null_state), x);
00381     for(typename state_type::const_iterator i = tmp.begin(); i != tmp.end(); ++i) {
00382       t = *i;
00383       crop(c, dfirst_markc(t));
00384     }
00385   }
00386 };
00387 
00391 template <typename NFA>
00392 inline
00393 dcursor<NFA> plaindc(const NFA &a) {
00394   return dcursor<NFA>(a, a.initial());
00395 }
00396 
00400 template <typename NFA>
00401 inline
00402 dcursor<NFA> plaindc(const NFA &a, typename NFA::state_type q) {
00403   return dcursor<NFA>(a, q);
00404 }
00405 
00409 template <typename NFA>
00410 inline
00411 forward_dcursor<NFA> forwarddc(const NFA &a) {
00412   return forward_dcursor<NFA>(a, a.initial());
00413 }
00414 
00418 template <typename NFA>
00419 inline
00420 forward_dcursor<NFA> forwarddc(const NFA &a, typename NFA::state_type q) {
00421   return forward_dcursor<NFA>(a, q);
00422 }
00423 
00424 template <typename NFA>
00425 inline
00426 async_forward_dcursor<NFA> 
00427 async_forwarddc(const NFA &a, const typename NFA::char_type &c) {
00428   return async_forward_dcursor<NFA>(a, c, a.initial());
00429 }
00430 
00431 template <typename NFA>
00432 inline
00433 async_forward_dcursor<NFA> 
00434 async_forwarddc(const NFA &a, const typename NFA::char_type &c,
00435                 typename NFA::state_type q) {
00436   return async_forward_dcursor<NFA>(a, c, q);
00437 }
00438 
00439 #ifdef NEWSCHOOL
00440 template <typename TransitionCursor, typename TagMapper = default_tag_mapper<NFA> > 
00441 class forward_dcursor 
00442   : public public forward_cursor_concept 
00443 { 
00444 public: 
00445   struct transitionc_order : public binary_function<TransitionCursor, TransitionCursor, bool>
00446   {
00447     bool operator()(const TransitionCursor &x, const TransitionCursor &y) const {
00448       return x.src() < y.src();
00449     }
00450   };
00451   typedef forward_dcursor             self; 
00452   typedef typename TransitionCursor::char_traits char_traits;
00453   typedef typename TagMapper::result_type tag_type; 
00454   typedef typename TransitionCursor::char_type   char_type;
00455   typedef typename set<TransitionCursor, transitionc_order>  state_type;
00456   typedef forward_cursor_concept      concept;
00457 
00458 
00459 protected:
00460   
00461 };
00462 
00463 #endif
00464 
00465 } // namespace astl 
00466 
00467 #endif // ASTL_DETERMINIZE_H
00468 
00469 
00470 
00471 

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