dfa_min.h

00001 #ifndef ASTL_DFA_MIN_H
00002 #define ASTL_DFA_MIN_H
00003 
00004 // Descrition:  
00005 //   ASTL 2.0 Determinisic Finite Automaton Class Template DFA_min
00006 //   Dynamic minimal acyclic DFA
00007 //   This class has a limited interface: words can be added with the
00008 //   insert method but no direct state/transition creations are
00009 //   supported.
00010 //   Sorry, words removal is not implemented yet!
00011 
00012 #include <astl.h>
00013 #include <match.h>
00014 #include <iostream>
00015 #include <set>
00016 #include <vector>
00017 #include <functional>
00018 #include <string>
00019 #include <cstring>    // memcpy
00020 #include <bitset>
00021 #include <iterator>
00022 #include <utility>    // pair<>
00023 
00024 using namespace std;
00025 
00026 namespace astl {
00027 
00028 typedef bitset<32> bitset_type; 
00029 
00030 // ** CharType shall be a POD type **
00031 template <typename CharType>
00032 class transition
00033 {
00034 protected:
00035   pair<CharType, unsigned int> letter_aim;
00036 
00037 public:
00038   typedef CharType char_type;
00039 
00040   transition(CharType a = 0, unsigned int aim = 0)
00041     : letter_aim(a, aim)
00042   { }
00043 
00044   char_type letter() const { return letter_aim.first; }
00045 
00046   unsigned int aim() const { return letter_aim.second; }
00047 
00048   void aim(unsigned int new_aim) { letter_aim.second = new_aim; }
00049 
00050   bool operator<(const transition<char_type> &x) const {// lexicographical compare states
00051     return letter_aim < x.letter_aim;
00052   }
00053 
00054   const pair<char_type, unsigned int>& make_pair() const {
00055     return letter_aim;
00056   }
00057 };
00058 
00059 // Specialization for char alphabet
00060 // 32 bits for a transition: 8 bits for the letter, 24 bits for the aim state
00061 // Hence the following limitations: 256 characters max, about 16
00062 // million states max
00063 
00064 const bitset_type letter_mask(0xFF000000);
00065 const bitset_type aim_mask(0x00FFFFFF);
00066 const unsigned long LETTER_SHIFT = 24;
00067 
00068 template <>
00069 class transition<char>
00070 {
00071 protected:
00072   bitset_type data;  
00073 
00074 public:
00075   typedef char char_type;
00076 
00077   transition()
00078     : data(0UL) 
00079   { }
00080 
00081   transition(char a, unsigned int aim = 0)
00082     : data((bitset_type(a) << LETTER_SHIFT) | bitset_type(aim))
00083   { }
00084 
00085   char letter() const {
00086     return (char) (((data & letter_mask) >> LETTER_SHIFT).to_ulong());
00087   }
00088 
00089   unsigned int aim() const { return (data & aim_mask).to_ulong(); }
00090 
00091   void aim(unsigned int new_aim) {
00092     data &= letter_mask;  
00093     data |= bitset_type(new_aim); 
00094   }
00095 
00096   bool operator<(const transition<char> &x) const {// lexicographical compare states
00097     return data.to_ulong() < x.data.to_ulong();
00098   }
00099 
00100   pair<char, unsigned int> make_pair() const { return std::make_pair(letter(), aim()); }
00101 };
00102 
00103 template <>
00104 class transition<unsigned char>
00105 {
00106 protected:
00107   bitset_type data;  
00108 
00109 public:
00110   typedef unsigned char char_type;
00111 
00112   transition()
00113     : data(0UL) 
00114   { }
00115 
00116   transition(unsigned char a, unsigned int aim = 0)
00117     : data((bitset_type(a) << LETTER_SHIFT) | bitset_type(aim))
00118   { }
00119 
00120   unsigned char letter() const {
00121     return (unsigned char) (((data & letter_mask) >> LETTER_SHIFT).to_ulong());
00122   }
00123 
00124   unsigned int aim() const { return (data & aim_mask).to_ulong(); }
00125 
00126   void aim(unsigned int new_aim) {
00127     data &= letter_mask;  
00128     data |= bitset_type(new_aim); 
00129   }
00130 
00131   bool operator<(const transition<unsigned char> &x) const {// lexicographical compare states
00132     return data.to_ulong() < x.data.to_ulong();
00133   }
00134 
00135   pair<unsigned char, unsigned int> make_pair() const { 
00136     return std::make_pair(letter(), aim()); 
00137   }
00138 };
00139 
00140 // This order relation is used to access transitions by binary search,
00141 // it does not take in account the aim state:
00142 template <typename Transition>
00143 struct lower_transition : public binary_function<Transition, Transition, bool>
00144 {
00145   bool operator()(const Transition &x, const Transition &y) const {
00146     return x.letter() < y.letter();
00147   }
00148 };
00149 
00150 // Implementation notes
00151 // A state has the following attributes:
00152 // - A in-degree (incoming transitions count)
00153 // - A boolean (final or not)
00154 // - A height (length of the longest word recognized by the state)
00155 // - A out-degree (outgoing transitions count)
00156 // 
00157 // The in-degree and the final flag are stored in a 32 bits array: the
00158 // first 31 bits are reserved for the in-degree. The height and
00159 // out-degree are stored in a 32 bits array: the first 12 bits are
00160 // reserved for the height and the last 20 bits for the out-degree.
00161 // Hence the following limitations: word length max is 4096 
00162 // and alphabet's max size is 1048576
00163 // Optimization: when out-degree is 1, the outgoing transition is stored in the
00164 // array pointer.
00165 
00166 static const bitset_type   final_mask(1);
00167 static const bitset_type   degree_in_mask(0xFFFFFFFF << 1);
00168 static const bitset_type   card_mask(0x000FFFFF);
00169 static const bitset_type   height_mask(0xFFF00000);
00170 static const unsigned long DEGREE_IN_SHIFT = 1;
00171 static const unsigned long HEIGHT_SHIFT = 20;
00172 
00173 template <typename Transition, typename Tag>
00174 class state_base
00175 {
00176 public:
00177   typedef Tag tag_type;
00178   tag_type& tag() { return data; }
00179   const tag_type& tag() const { return data; }
00180 
00181 protected:
00182   tag_type data;
00183 };
00184 
00185 template <typename Transition>
00186 class state_base<Transition, empty_tag> // empty object for optimizing
00187 {
00188 public:
00189   typedef empty_tag tag_type;
00190   empty_tag& tag() { return data; }
00191   const empty_tag& tag() const { return data; }
00192 
00193 protected:
00194   static empty_tag data;
00195 };
00196 
00197 template <typename Transition>
00198 empty_tag state_base<Transition, empty_tag>::data;
00199 
00200 template <typename Transition, typename Tag = empty_tag>
00201 class state  : public state_base<Transition, Tag>
00202 {
00203 public:
00204   class bool_reference;
00205   friend class bool_reference;
00206 
00207 protected:
00208   bitset_type degree_in_final;
00209   bitset_type height_card; 
00210   union dummy_name {   // VC++ does not support methods in unnamed union
00211   private:
00212     // the sorted transitions array (order relation is given by
00213     // lower_than_transition):
00214     Transition *_t;
00215     char _tr[sizeof(Transition)]; // when there is only one transition
00216   public:
00217     Transition*& t() { return _t; }
00218     Transition& tr() { return *((Transition*) _tr); }
00219     Transition* const & t() const { return _t; }
00220     const Transition& tr() const { return *((Transition*) _tr); }
00221   } tunion;
00222 
00223 public:
00224   typedef Transition*       iterator;
00225   typedef const Transition* const_iterator;
00226 
00227   state()
00228     : degree_in_final(0UL), height_card(0UL) { 
00229     tunion.t() = NULL;
00230   }
00231 
00232   state(const state &x)
00233     : degree_in_final(x.degree_in_final), height_card(x.height_card) 
00234   {
00235     state_base<Transition, Tag>::tag() = x.tag();
00236     degree_in_final &= final_mask; // in-degree is 0
00237     unsigned int n = x.card();
00238     switch (n) {
00239     case        0 : tunion.t() = NULL; break;
00240     case        1 : tunion.tr() = x.tunion.tr(); break;
00241     default :
00242       tunion.t() = new Transition[n];
00243       memcpy(tunion.t(), x.tunion.t(), sizeof(Transition) * n); 
00244       // Warning: DFA_min is responsible for in-degree updating
00245     }
00246   }
00247 
00248   ~state() {
00249     if (card() > 1) delete [] tunion.t();
00250   }
00251 
00252   unsigned int delta1(typename Transition::char_type a) const {
00253     const_iterator where = lower_bound(begin(), end(), Transition(a), 
00254                                        lower_transition<Transition>());
00255     return (where == end() || (*where).letter() != a) ? 0 : (*where).aim();
00256   }
00257 
00258   const_iterator begin() const {
00259     return card() == 1 ? &(tunion.tr()) : tunion.t();
00260   }
00261 
00262   const_iterator end() const {
00263     return card() == 1 ? &(tunion.tr()) + 1 : (tunion.t() + card());
00264   }
00265 
00266   iterator begin() {
00267     return card() == 1 ? &(tunion.tr()) : tunion.t();
00268   }
00269 
00270   iterator end() {
00271     return card() == 1 ? &(tunion.tr()) + 1 : (tunion.t() + card());
00272   }
00273 
00274   unsigned int size() const {
00275     return card();
00276   }
00277 
00278   const_iterator find(typename Transition::char_type a) const {
00279     const_iterator where = lower_bound(begin(), end(), Transition(a), 
00280                                        lower_transition<Transition>());
00281     return (where == end() || (*where).letter() != a) ? end() : where;
00282   }
00283 
00284   iterator find(typename Transition::char_type a) {
00285     iterator where = lower_bound(begin(), end(), Transition(a), 
00286                                  lower_transition<Transition>());
00287     return (where == end() || (*where).letter() != a) ? end() : where;
00288   }
00289 
00290   void insert(const Transition &x) {  // Precond: transition does not exist
00291     unsigned int n = card();
00292     if (n == 0) 
00293       tunion.tr() = x; 
00294     else {
00295       iterator where = lower_bound(begin(), end(), x, lower_transition<Transition>());
00296       unsigned int i = where - begin();
00297       Transition *tmp = new Transition[n + 1];
00298       memcpy(tmp, begin(), i * sizeof(Transition));
00299       tmp[i] = x;
00300       memcpy(tmp + i + 1, where, (end() - where) * sizeof(Transition));
00301       if (n > 1) delete [] tunion.t();
00302       tunion.t() = tmp;
00303     }
00304     inc_card();
00305   }
00306 
00307   void change_trans(const Transition &x) {   // Precond: transition is defined
00308     (*(lower_bound(begin(), end(), x, lower_transition<Transition>()))) = x;
00309   }
00310 
00311   void erase(const Transition &x) {  // Precond: the transition is defined
00312     unsigned int n = card();
00313     switch (n) {
00314     case 1 : tunion.t() = NULL; break;
00315     case 2 : 
00316       {
00317         Transition *tmp = tunion.t();
00318         tunion.tr() = x.letter() < tmp[1].letter() ? tmp[1] : tmp[0];
00319         delete [] tmp;
00320         break;
00321       }
00322     default :
00323       {
00324         iterator where = lower_bound(begin(), end(), x, 
00325                                      lower_transition<Transition>());
00326         Transition *tmp = new Transition[n - 1];
00327         memcpy(tmp, begin(), (where - begin()) * sizeof(Transition));
00328         memcpy(tmp + (where - begin()), where + 1, 
00329                (end() - (where + 1)) * sizeof(Transition));
00330         delete [] tunion.t();
00331         tunion.t() = tmp;
00332       }
00333     }
00334     dec_card();
00335   }
00336 
00337   unsigned int degree_in() const {
00338     return ((degree_in_final & degree_in_mask) >> DEGREE_IN_SHIFT).to_ulong();
00339   }
00340 
00341   void inc_degree_in() {
00342     unsigned int d = degree_in() + 1;
00343     degree_in_final &= final_mask; 
00344     degree_in_final |= bitset_type(d) << DEGREE_IN_SHIFT;
00345   }
00346 
00347   void dec_degree_in() {
00348     unsigned int d = degree_in() - 1;
00349     degree_in_final &= final_mask;
00350     degree_in_final |= bitset_type(d) << DEGREE_IN_SHIFT;
00351   }
00352 
00353   unsigned int card() const {
00354     return (height_card & card_mask).to_ulong();
00355   }
00356 
00357   void inc_card() {
00358     unsigned int c = card() + 1;
00359     height_card &= height_mask;
00360     height_card |= bitset_type(c);
00361   }
00362 
00363   void dec_card() {
00364     unsigned int c = card() - 1;
00365     height_card &= height_mask;
00366     height_card |= bitset_type(c);
00367   }
00368                 
00369   unsigned int height() const {
00370     return ((height_card & height_mask) >> HEIGHT_SHIFT).to_ulong();
00371   }
00372 
00373   void height(unsigned int h) {
00374     height_card &= card_mask;
00375     height_card |= bitset_type(h) << HEIGHT_SHIFT;
00376   }
00377 
00378   bool final() const {
00379     return (degree_in_final & final_mask).to_ulong() == 1;
00380   }
00381 
00382   class bool_reference
00383   {
00384     bitset_type &r;
00385   public:
00386     bool_reference(bitset_type &ref)
00387       : r(ref)
00388     { }
00389     
00390     operator bool() const {
00391       return (r & final_mask).to_ulong() == 1;
00392     }
00393 
00394     bool_reference& operator=(const bool_reference &x) {
00395       if (x == true) r |= final_mask;
00396       else r &= degree_in_mask;
00397       return *this;
00398     }
00399 
00400     bool_reference& operator=(bool b) {
00401       if (b == true) r |= final_mask;
00402       else r &= degree_in_mask;
00403       return *this;
00404     }
00405 
00406     bool operator==(const bool_reference &x) const {
00407       return (r & final_mask) == (x.r & final_mask);
00408     }
00409 
00410     bool operator==(bool b) const {
00411       return ((r & final_mask).to_ulong() != 0) == b;
00412     }
00413   };
00414 
00415   bool_reference final() {
00416     return bool_reference(degree_in_final);
00417   }
00418 
00419   // This strict weak order relation defines equivalent states:
00420   // Let q, p be two states. We have (q == p) <=> !(q < p) && !(p < q)
00421   // It compares two states lexicographicaly
00422 //   bool operator< (const state<Transition, Tag> &x) const {
00423 //     if (final() < x.final()) return true;
00424 //     if (final() == x.final()) {
00425 //       if (size() < x.size()) return true;
00426 //       else
00427 //      if (size() == x.size()) { 
00428 //        const_iterator i = begin(), j = end(), k = x.begin();
00429 //        while (i != j)
00430 //          if (*i < *k) return true;
00431 //          else if (*k < *i) return false;
00432 //          else { ++i; ++k; }
00433 //        return false;
00434 //      }
00435 //     }
00436 //     return false;
00437 //   }
00438 };
00439 
00440   // This strict weak order relation defines equivalent states:
00441   // Let q, p be two states. We have (q == p) <=> !(q < p) && !(p < q)
00442   // It compares two states lexicographicaly
00443 template <typename Transition, typename Tag>
00444 inline
00445 bool operator<(const state<Transition, Tag> &x, const state<Transition, Tag> &y) {
00446   if (x.final() < y.final()) return true;
00447   if (x.final() == y.final()) {
00448     if (x.size() < y.size()) return true;
00449     else
00450       if (x.size() == y.size()) { 
00451         typename state<Transition, Tag>::const_iterator i = x.begin(), j = x.end(), k = y.begin();
00452         while (i != j)
00453           if (*i < *k) return true;
00454           else if (*k < *i) return false;
00455           else { ++i; ++k; }
00456         return false; // equivalent, not lower than
00457       }
00458   }
00459   return false;
00460 }
00461 
00462 // Compare two states given their ID (map ID -> state structure)
00463 // Needed to use sets of state ID
00464 template <typename Transition, typename Tag>
00465 struct compare_state 
00466   : public binary_function<typename vector<state<Transition, Tag>*>::size_type, 
00467                            typename vector<state<Transition, Tag>*>::size_type, bool> 
00468 {
00469   const vector<state<Transition, Tag>*> &Q;
00470   compare_state(const vector<state<Transition, Tag>*> &r)
00471     : Q(r)
00472   { }
00473   bool operator() (typename vector<state<Transition, Tag>*>::size_type x, 
00474                    typename vector<state<Transition, Tag>*>::size_type y) const {
00475     return *Q[x] < *Q[y];
00476   }
00477 };
00478 
00479 // ** CharType shall be a POD type **
00480 
00496 template <typename CharTraits = plain, typename Tag = empty_tag>
00497 class DFA_min : public DFA_concept
00498 {
00499 public:
00500   typedef transition<typename CharTraits::char_type> transition_type;
00501   typedef CharTraits                                 char_traits;
00502   typedef Tag                                        tag_type;
00503   typedef unsigned int                               state_type;
00504   typedef typename CharTraits::char_type             char_type;
00505   typedef DFA_min                                    self;
00506 
00507 
00508 #ifndef _MSC_VER
00509   static const state_type null_state = 0;
00510 #else
00511   static const state_type null_state;
00512 #endif
00513 
00514 protected:
00515   state_type          i;
00516   bool                ready;
00517   unsigned int       _state_count, _trans_count;
00518 
00519   typedef set<state_type, compare_state<transition_type, tag_type> >   container;
00520   vector<container*>                       _pool;  // each height has its set
00521   vector<state<transition_type, tag_type>*> Q;
00522   compare_state<transition_type, tag_type>                            cmp_state;
00523   state_type                               hole;  // 1st free in state vector
00524   unsigned int                            wc_; // word count
00525 
00526   // statistics:
00527   unsigned long state_creation, state_copy, state_merge;
00528 
00529   container& pool(unsigned int h) { 
00530     for(; _pool.size() < h + 1; _pool.push_back(new container(cmp_state))); 
00531     return *(_pool[h]);
00532   }
00533 
00534   void prepare();
00535 
00536   typename state<transition_type, tag_type>::bool_reference final(state_type q) {
00537     return Q[q]->final();
00538   }
00539 
00540   void initial(state_type q) {
00541     i = q;
00542   }
00543 
00544   state_type new_state() { return new_state_(); }
00545 
00546   // for duplicating states:
00547   state_type new_state(const state<transition_type, tag_type> &q) { return new_state_(&q); }
00548 
00549   state_type new_state_(const state<transition_type, tag_type> *s = NULL) {
00550     if (s == NULL) ++state_creation;
00551     else ++state_copy;
00552 
00553     ++_state_count;
00554     while (hole < Q.size())
00555       if (Q[hole] == NULL) {
00556         Q[hole] = s == NULL ? new state<transition_type, tag_type> : new state<transition_type, tag_type>(*s);
00557         return hole++;
00558       }
00559       else ++hole;
00560     Q.push_back(s == NULL ? new state<transition_type, tag_type> : new state<transition_type, tag_type>(*s));
00561     ++hole;
00562     return Q.size() - 1;
00563   }
00564 
00565 public:
00566   tag_type& tag(state_type q) { return Q[q]->tag(); }
00567 
00568   const tag_type& tag(state_type q) const { return Q[q]->tag(); }
00569 
00570 protected:
00571   void reset() {
00572     freeze();
00573     typename vector<state<transition_type, tag_type>*>::iterator ii = 
00574       Q.begin(), j = Q.end();
00575     for(; ii != j; ++ii)
00576       delete *ii;
00577     
00578     i = 0;
00579     _state_count = 0;
00580     _trans_count = 0;
00581     Q.resize(1);
00582     hole = 2;
00583     wc_ = 0;
00584   }      
00585 
00586   void del_state(state_type q) {
00587     ++state_merge;
00588 
00589     --_state_count;
00590     _trans_count -= Q[q]->size();
00591     typename state<transition_type, tag_type>::iterator i = Q[q]->begin(), 
00592       j = Q[q]->end();
00593     for(; i != j; ++i)
00594       Q[(*i).aim()]->dec_degree_in();
00595     delete Q[q];
00596     Q[q] = NULL;
00597     hole = min__(hole, q);
00598   }
00599 
00600   void set_trans(state_type q, char_type a, state_type p) {
00601     ++_trans_count;
00602     Q[q]->insert(transition_type(a, p));
00603     Q[p]->inc_degree_in();
00604   }
00605 
00606   state_type duplicate_state(state_type q) {
00607     _trans_count += Q[q]->size();
00608     state_type p = new_state(*Q[q]);
00609     typename state<transition_type, tag_type>::iterator i = Q[p]->begin(), j = Q[p]->end();
00610     for(; i != j; ++i)
00611       Q[(*i).aim()]->inc_degree_in();
00612     return p;
00613   }
00614         
00615   void del_trans(state_type q, char_type a) {
00616     --_trans_count;
00617     Q[Q[q]->delta1(a)]->dec_degree_in();
00618     Q[q]->erase(transition_type(a));
00619   }
00620 
00621   void change_trans(state_type q, char_type a, state_type p) {
00622     Q[Q[q]->delta1(a)]->dec_degree_in();
00623     Q[q]->change_trans(transition_type(a,p));
00624     Q[p]->inc_degree_in();
00625   }
00626 
00627 public: // TMP
00628   void height(state_type q, unsigned int h) {
00629     Q[q]->height(h);
00630   }
00631 
00632   unsigned int height(state_type q) const {
00633     return Q[q]->height();
00634   }
00635 
00636   unsigned int degree_in(state_type q) const {
00637     return Q[q]->degree_in();
00638   }
00639 
00640   void degree_in(state_type q, unsigned int d) {
00641     Q[q]->degree_in(d);
00642   }
00643 
00647   unsigned int wc() const { return wc_; }
00648 
00649 public:
00650   typedef skip_blanks_iterator<state<transition_type, tag_type> > const_iterator;
00651 
00652   DFA_min()
00653     : i(0),  ready(false),
00654       _state_count(0), _trans_count(0), Q(1, (state<transition_type, tag_type>*) 0), 
00655       cmp_state(Q), hole(2), wc_(0),
00656       state_creation(0), state_copy(0), state_merge(0)
00657   { 
00658     i = new_state();
00659   }
00660 
00661   ostream& stats(ostream &out) const {
00662     out << "word count " << wc() << endl << "states " << state_count();
00663     out << endl << "transitions " << trans_count() << endl;
00664     out << "state creations " << state_creation << endl;
00665     out << "state copies    " << state_copy << endl;
00666     return out << "state merges    " << state_merge << endl;
00667   }
00668 
00669   const_iterator begin() const {
00670     return const_iterator(&Q, initial());
00671   }
00672 
00673   const_iterator end() const {
00674     return const_iterator(&Q, Q.size());
00675   }
00676 
00677   ~DFA_min() { reset(); }
00678 
00682   void clear() {
00683     reset();
00684     i = new_state();
00685   }
00686 
00687   bool final(state_type q) const {
00688     return Q[q]->final();
00689   }
00690         
00696   void freeze() { 
00697     for(typename vector<container*>::iterator i = _pool.begin(); 
00698         i != _pool.end(); ++i)
00699       delete *i;
00700     _pool.clear();
00701     ready = false;
00702   }
00703 
00711   template <class ForwardI>
00712   bool insert(ForwardI, ForwardI);
00713 
00720   bool insert(const basic_string<char_type> &s) {
00721     return insert(s.begin(), s.end());
00722   }
00723         
00724   state_type initial() const { return i; }
00725 
00726   state_type delta1(state_type q, char_type a) const {
00727     return Q[q]->delta1(a);
00728   }
00729 
00730   class edges_type
00731   {
00732   protected:
00733     state<transition_type, tag_type> *q;
00734 
00735   public:
00736     typedef int                               difference_type;
00737     typedef char_type                         key_type;
00738     typedef state_type                        data_type;
00739     typedef pair<const char_type, state_type> value_type;
00740 
00741     edges_type(state<transition_type, tag_type> *p)
00742       : q(p)
00743     { }
00744 
00745     edges_type()
00746     {}
00747 
00748     bool empty() const {
00749       return q->size() == 0;
00750     }
00751 
00752     unsigned int size() const {
00753       return q->size();
00754     }
00755 
00756     class const_iterator 
00757       : public iterator<bidirectional_iterator_tag, 
00758                         pair<char_type, state_type> >
00759     {
00760     protected:
00761       typename state<transition_type, tag_type>::const_iterator i;
00762 
00763     public:
00764       typedef const_iterator self;
00765 
00766       const_iterator()
00767       { }
00768       const_iterator(typename state<transition_type, tag_type>::const_iterator j)
00769         : i(j)
00770       { }
00771       pair<char_type, unsigned int> operator* () const {
00772         return i->make_pair(); // make_pair((*i).letter(), (*i).aim());
00773       }
00774       self& operator++ () {
00775         ++i;
00776         return *this;
00777       }
00778       self operator++ (int) {
00779         self tmp = *this;
00780         ++*this;
00781         return tmp;
00782       }
00783       bool operator== (const self &x) const {
00784         return i == x.i;
00785       }
00786       self& operator--() {
00787         --i;
00788         return *this;
00789       }
00790       self operator-- (int) {
00791         self tmp = *this;
00792         --*this;
00793         return tmp;
00794       }
00795     };
00796                 
00797     const_iterator begin() const {
00798       return const_iterator(q->begin());
00799     }
00800 
00801     const_iterator end() const {
00802       return const_iterator(q->end());
00803     }
00804 
00805     const_iterator find(char_type a) const {
00806       return const_iterator(q->find(a));
00807     }
00808   };
00809 
00810   edges_type delta2(state_type q) const { return edges_type(Q[q]); }
00811 
00812   unsigned int state_count() const { return _state_count;  }
00813   unsigned int trans_count() const { return _trans_count; }
00814 
00817   unsigned int size() const { return wc_; }
00818 };
00819 
00820 #ifndef _MSC_VER
00821 template <typename C, typename T>
00822 const typename DFA_min<C, T>::state_type DFA_min<C, T>::null_state;
00823 #else
00824 template <typename C, typename T>
00825 const typename DFA_min<C, T>::state_type DFA_min<C, T>::null_state = 0;
00826 #endif
00827 
00828 template <typename CharTraits, typename Tag>
00829 void DFA_min<CharTraits, Tag>::prepare() {
00830   const_iterator first = begin(), last = end();
00831   for(; first != last; ++first)
00832     pool(height(*first)).insert(*first);
00833   ready = true;
00834 }
00835 
00836 template <class CharTraits, typename Tag> 
00837 template <class InputIterator>
00838 bool DFA_min<CharTraits, Tag>::insert(InputIterator first, 
00839                                       InputIterator last)
00840 {
00841   {
00842     cursor<DFA_min<CharTraits, Tag> > c(*this);
00843     if (match(c, first, last)) return false;  // word exists ?
00844   }
00845   if (!ready) prepare();  // build the structure if necessary
00846   stack_cursor<forward_cursor<self> > c(forwardc(*this));
00847   bool duplicating;
00848 
00849   for(duplicating = false; first != last; ++first) {
00850     if (!duplicating)
00851       pool(height(c.src())).erase(c.src());
00852 
00853     if (!c.find(*first)) {
00854       set_trans(c.src(), *first, new_state());
00855       duplicating = true;
00856       c.find(*first);
00857     }
00858     else 
00859       if (Q[c.aim()]->degree_in() > 1) {
00860         change_trans(c.src(), *first, duplicate_state(c.aim())); 
00861         duplicating = true;
00862         c.find(*first);
00863       }
00864     c.forward();
00865   }
00866 
00867   if (!duplicating) 
00868     pool(height(c.src())).erase(c.src());
00869 
00870   final(c.src()) = true;
00871   unsigned int h = height(c.src());
00872 
00873   for(; c.backward(); ) {
00874     // try to insert the current state in its height pool
00875     // if an equivalent state is found its ID is returned, otherwise
00876     // it is inserted 
00877     pair<typename container::iterator, bool> i = 
00878       pool(height(c.aim())).insert(c.aim());
00879     if (i.second == false) {  // found an equivalent state ?
00880       state_type tmp = c.aim(); 
00881       // redirect the transition towards equivalent state
00882       change_trans(c.src(), c.letter(), *i.first);
00883       del_state(tmp);
00884     }
00885     h = max__(height(c.src()), h+1); //Precond: states height initialized with 0
00886     height(c.src(), h);
00887   }
00888   pool(height(initial())).insert(initial());
00889   ++wc_;
00890   return true;
00891 }
00892 
00893 } // namespace astl
00894 
00895 #endif // ASTL_CLASS_DFA_MIN
00896 
00897   

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