Generated on Thu Jul 6 07:06:46 2006 for Gecode by doxygen 1.4.7

dfa.cc

Go to the documentation of this file.
00001 /*
00002  *  Main authors:
00003  *     Christian Schulte <schulte@gecode.org>
00004  *
00005  *  Copyright:
00006  *     Christian Schulte, 2004
00007  *
00008  *  Last modified:
00009  *     $Date: 2006-04-11 15:58:37 +0200 (Tue, 11 Apr 2006) $ by $Author: tack $
00010  *     $Revision: 3188 $
00011  *
00012  *  This file is part of Gecode, the generic constraint
00013  *  development environment:
00014  *     http://www.gecode.org
00015  *
00016  *  See the file "LICENSE" for information on usage and
00017  *  redistribution of this file, and for a
00018  *     DISCLAIMER OF ALL WARRANTIES.
00019  *
00020  */
00021 
00022 #include "gecode/int.hh"
00023 #include "gecode/support/sort.hh"
00024 #include "gecode/support/static-stack.hh"
00025 
00026 
00027 namespace Gecode { namespace Int { namespace Regular {
00028 
00032   class TransByI_State {
00033   public:
00034     forceinline bool
00035     operator()(const DFA::Transition& x, const DFA::Transition& y) {
00036       return x.i_state < y.i_state;
00037     }
00038     forceinline static void
00039     sort(DFA::Transition t[], int n) {
00040       TransByI_State tbis;
00041       Support::quicksort<DFA::Transition,TransByI_State>(t,n,tbis);
00042     }
00043   };
00044 
00048   class TransBySymbol {
00049   public:
00050     forceinline bool
00051     operator()(const DFA::Transition& x, const DFA::Transition& y) {
00052       return x.symbol < y.symbol;
00053     }
00054     forceinline static void
00055     sort(DFA::Transition t[], int n) {
00056       TransBySymbol tbs;
00057       Support::quicksort<DFA::Transition,TransBySymbol>(t,n,tbs);
00058     }
00059   };
00060 
00064   class TransBySymbolI_State {
00065   public:
00066     forceinline bool
00067     operator()(const DFA::Transition& x, const DFA::Transition& y) {
00068       return ((x.symbol < y.symbol) ||
00069               (x.symbol == y.symbol) && (x.i_state < y.i_state));
00070     }
00071     forceinline static void
00072     sort(DFA::Transition t[], int n) {
00073       TransBySymbolI_State tbsi;
00074       Support::quicksort<DFA::Transition,TransBySymbolI_State>(t,n,tbsi);
00075     }
00076   };
00077 
00081   class TransByO_State {
00082   public:
00083     forceinline bool
00084     operator()(const DFA::Transition& x, const DFA::Transition& y) {
00085       return x.o_state < y.o_state;
00086     }
00087     forceinline static void
00088     sort(DFA::Transition t[], int n) {
00089       TransByO_State tbos;
00090       Support::quicksort<DFA::Transition,TransByO_State>(t,n,tbos);
00091     }
00092   };
00093 
00094 
00098   class StateGroup {
00099   public:
00100     int state;
00101     int group;
00102   };
00103 
00107   class StateGroupByGroup {
00108   public:
00109     forceinline bool
00110     operator()(const StateGroup& x, const StateGroup& y) {
00111       return ((x.group < y.group) ||
00112               (x.group == y.group) && (x.state < y.state));
00113     }
00114     static void
00115     sort(StateGroup sg[], int n) {
00116       StateGroupByGroup o;
00117       Support::quicksort<StateGroup,StateGroupByGroup>(sg,n,o);
00118     }
00119   };
00120 
00124   class GroupStates {
00125   public:
00126     StateGroup* fst;
00127     StateGroup* lst;
00128   };
00129 
00131 #define S_NONE       0
00133 #define S_FROM_START 1
00135 #define S_TO_FINAL   2
00137 #define S_FINAL      4
00138 
00139 }}}
00140 
00141 namespace Gecode {
00142 
00143   void
00144   DFA::init(int start, Transition t_spec[], int f_spec[], bool minimize) {
00145     using namespace Int;
00146     using namespace Regular;
00147     // Compute number of states and transitions
00148     int n_states = start;
00149     int n_trans  = 0;
00150     for (Transition* t = &t_spec[0]; t->i_state >= 0; t++) {
00151       n_states = std::max(n_states,t->i_state);
00152       n_states = std::max(n_states,t->o_state);
00153       n_trans++;
00154     }
00155     for (int* f = &f_spec[0]; *f >= 0; f++)
00156       n_states = std::max(n_states,*f);
00157     n_states++;
00158 
00159     // Temporary structure for transitions
00160     GECODE_AUTOARRAY(Transition, trans, n_trans);
00161     for (int i = n_trans; i--; )
00162       trans[i] = t_spec[i];
00163     // Temporary structures for finals
00164     GECODE_AUTOARRAY(int,  final,    n_states+1);
00165     GECODE_AUTOARRAY(bool, is_final, n_states+1);
00166     int n_finals = 0;
00167     for (int i = n_states+1; i--; )
00168       is_final[i] = false;
00169     for (int* f = &f_spec[0]; *f != -1; f++) {
00170       is_final[*f]      = true;
00171       final[n_finals++] = *f;
00172     }
00173 
00174     if (minimize) {
00175       // Sort transitions by symbol and i_state
00176       TransBySymbolI_State::sort(trans, n_trans);
00177       GECODE_AUTOARRAY(Transition*, idx, n_trans+1);
00178       //  idx[i]...idx[i+1]-1 gives where transitions for symbol i start
00179       int n_symbols = 0;
00180       {
00181         int j = 0;
00182         while (j < n_trans) {
00183           idx[n_symbols++] = &trans[j];
00184           int s = trans[j].symbol;
00185           while ((j < n_trans) && (s == trans[j].symbol))
00186             j++;
00187         }
00188         idx[n_symbols] = &trans[j];
00189         assert(j == n_trans);
00190       }
00191       // Map states to groups
00192       GECODE_AUTOARRAY(int,         s2g,  n_states+1);
00193       GECODE_AUTOARRAY(StateGroup,  part, n_states+1);
00194       GECODE_AUTOARRAY(GroupStates, g2s,  n_states+1);
00195       // Initialize: final states is group one, all other group zero
00196       for (int i = n_states+1; i--; ) {
00197         part[i].state = i;
00198         part[i].group = is_final[i] ? 1 : 0;
00199         s2g[i]        = part[i].group;
00200       }
00201       // Important: the state n_state is the dead state, conceptually
00202       // if there is no transition for a symbol and input state, it is
00203       // assumed that there is an implicit transition to n_state
00204 
00205       // Set up the indexing data structure, sort by group
00206       StateGroupByGroup::sort(part,n_states+1);
00207       int n_groups;
00208       if (part[0].group == part[n_states].group) {
00209         // No final states, just one group
00210         g2s[0].fst = &part[0]; g2s[0].lst = &part[n_states+1];
00211         n_groups = 1;
00212       } else  {
00213         int i = 0;
00214         assert(part[0].group == 0);
00215         do i++; while (part[i].group == 0);
00216         g2s[0].fst = &part[0]; g2s[0].lst = &part[i];
00217         g2s[1].fst = &part[i]; g2s[1].lst = &part[n_states+1];
00218         n_groups = 2;
00219       }
00220 
00221       // Do the refinement
00222       {
00223         int m_groups;
00224         do {
00225           m_groups = n_groups;
00226           // Iterate over symbols
00227           for (int sidx = n_symbols; sidx--; ) {
00228             // Iterate over groups
00229             for (int g = n_groups; g--; ) {
00230               // Ignore singleton groups
00231               if (g2s[g].lst-g2s[g].fst > 1) {
00232                 // Apply transitions to group states
00233                 // This exploits that both transitions as well as
00234                 // stategroups are sorted by (input) state
00235                 Transition* t     = idx[sidx];
00236                 Transition* t_lst = idx[sidx+1];
00237                 for (StateGroup* sg = g2s[g].fst; sg<g2s[g].lst; sg++) {
00238                   while ((t < t_lst) && (t->i_state < sg->state))
00239                     t++;
00240                   // Compute group resulting from transition
00241                   if ((t < t_lst) && (t->i_state == sg->state))
00242                     sg->group = s2g[t->o_state];
00243                   else
00244                     sg->group = s2g[n_states]; // Go to dead state
00245                 }
00246                 // Sort group by groups from transitions
00247                 StateGroupByGroup::sort(g2s[g].fst, 
00248                                         static_cast<int>(g2s[g].lst-g2s[g].fst));
00249                 // Group must be split?
00250                 if (g2s[g].fst->group != (g2s[g].lst-1)->group) {
00251                   // Skip first group
00252                   StateGroup* sg = g2s[g].fst+1;
00253                   while ((sg-1)->group == sg->group)
00254                     sg++;
00255                   // Start splitting
00256                   StateGroup* lst = g2s[g].lst;
00257                   g2s[g].lst = sg;
00258                   while (sg < lst) {
00259                     s2g[sg->state] = n_groups;
00260                     g2s[n_groups].fst  = sg++;
00261                     while ((sg < lst) && ((sg-1)->group == sg->group)) {
00262                       s2g[sg->state] = n_groups; sg++;
00263                     }
00264                     g2s[n_groups++].lst = sg;
00265                   }
00266                 }
00267               }
00268             }
00269           }
00270         } while (n_groups != m_groups);
00271         // New start state
00272         start = s2g[start];
00273         // Compute new final states
00274         n_finals = 0;
00275         for (int g = n_groups; g--; )
00276           for (StateGroup* sg = g2s[g].fst; sg < g2s[g].lst; sg++)
00277             if (is_final[sg->state]) {
00278               final[n_finals++] = g;
00279               break;
00280             }
00281         // Compute representatives
00282         GECODE_AUTOARRAY(int, s2r, n_states+1);
00283         for (int i = n_states+1; i--; )
00284           s2r[i] = -1;
00285         for (int g = n_groups; g--; )
00286           s2r[g2s[g].fst->state] = g;
00287         // Clean transitions
00288         int j = 0;
00289         for (int i = 0; i<n_trans; i++)
00290           if (s2r[trans[i].i_state] != -1) {
00291             trans[j].i_state = s2g[trans[i].i_state];
00292             trans[j].symbol  = trans[i].symbol;
00293             trans[j].o_state = s2g[trans[i].o_state];
00294             j++;
00295           }
00296         n_trans  = j;
00297         n_states = n_groups;
00298       }
00299     }
00300 
00301     // Do a reachability analysis for all states starting from start state
00302     Support::StaticStack<int> visit(n_states);
00303     GECODE_AUTOARRAY(int, state, n_states);
00304     for (int i=n_states; i--; )
00305       state[i] = S_NONE;
00306 
00307     {
00308       // Sort all transitions according to i_state and create index structure
00309       //  idx[i]...idx[i+1]-1 gives where transitions for state i start
00310       TransByI_State::sort(trans, n_trans);
00311       GECODE_AUTOARRAY(Transition*, idx, n_states+1);
00312       {
00313         int j = 0;
00314         for (int i=0; i<n_states; i++) {
00315           idx[i] = &trans[j];
00316           while ((j < n_trans) && (i == trans[j].i_state))
00317             j++;
00318         }
00319         idx[n_states] = &trans[j];
00320         assert(j == n_trans);
00321       }
00322 
00323       state[start] = S_FROM_START;
00324       visit.push(start);
00325       while (!visit.empty()) {
00326         int s = visit.pop();
00327         for (Transition* t = idx[s]; t < idx[s+1]; t++)
00328           if (!(state[t->o_state] & S_FROM_START)) {
00329             state[t->o_state] |= S_FROM_START;
00330             visit.push(t->o_state);
00331           }
00332       }
00333     }
00334 
00335     // Do a reachability analysis for all states to a final state
00336     {
00337       // Sort all transitions according to o_state and create index structure
00338       //  idx[i]...idx[i+1]-1 gives where transitions for state i start
00339       TransByO_State::sort(trans, n_trans);
00340       GECODE_AUTOARRAY(Transition*, idx, n_states+1);
00341       {
00342         int j = 0;
00343         for (int i=0; i<n_states; i++) {
00344           idx[i] = &trans[j];
00345           while ((j < n_trans) && (i == trans[j].o_state))
00346             j++;
00347         }
00348         idx[n_states] = &trans[j];
00349         assert(j == n_trans);
00350       }
00351 
00352       for (int i = n_finals; i--; ) {
00353         state[final[i]] |= (S_TO_FINAL | S_FINAL);
00354         visit.push(final[i]);
00355       }
00356       while (!visit.empty()) {
00357         int s = visit.pop();
00358         for (Transition* t = idx[s]; t < idx[s+1]; t++)
00359           if (!(state[t->i_state] & S_TO_FINAL)) {
00360             state[t->i_state] |= S_TO_FINAL;
00361             visit.push(t->i_state);
00362           }
00363       }
00364     }
00365 
00366     // Now all reachable states are known (also the final ones)
00367     GECODE_AUTOARRAY(int, re, n_states);
00368     for (int i = n_states; i--; )
00369       re[i] = -1;
00370 
00371     // Renumber states
00372     int m_states = 0;
00373     // Start state gets zero
00374     re[start] = m_states++;
00375 
00376     // Renumber final states
00377     for (int i = n_states; i--; )
00378       if ((state[i] == (S_FINAL | S_FROM_START | S_TO_FINAL)) && (re[i] < 0))
00379         re[i] = m_states++;
00380     // If start state is final, final states start from zero, otherwise from one
00381     int final_fst = (state[start] & S_FINAL) ? 0 : 1;
00382     int final_lst = m_states;
00383     // final_fst...final_lst-1 are the final states
00384 
00385     // Renumber remaining states
00386     for (int i = n_states; i--; )
00387       if ((state[i] == (S_FROM_START | S_TO_FINAL)) && (re[i] < 0))
00388         re[i] = m_states++;
00389 
00390     // Count number of remaining transitions
00391     int m_trans = 0;
00392     for (int i = n_trans; i--; )
00393       if ((re[trans[i].i_state] >= 0) && (re[trans[i].o_state] >= 0))
00394         m_trans++;
00395 
00396     // All done... Construct the automaton
00397     DFAI* d = reinterpret_cast<DFAI*>
00398       (Memory::malloc(sizeof(DFAI) + sizeof(Transition)*(m_trans-1)));
00399     d->use_cnt   = 1;
00400     d->n_states  = m_states;
00401     d->n_trans   = m_trans;
00402     d->final_fst = final_fst;
00403     d->final_lst = final_lst;
00404     {
00405       int j = 0;
00406       Transition* r = &d->trans[0];
00407       for (int i = 0; i<n_trans; i++)
00408         if ((re[trans[i].i_state] >= 0) && (re[trans[i].o_state] >= 0)) {
00409           r[j].symbol  = trans[i].symbol;
00410           r[j].i_state = re[trans[i].i_state];
00411           r[j].o_state = re[trans[i].o_state];
00412           j++;
00413         }
00414       TransBySymbol::sort(r,m_trans);
00415     }
00416     dfai = d;
00417   }
00418 
00419 }
00420 
00421 std::ostream&
00422 operator<<(std::ostream& os, const Gecode::DFA& dfa) {
00423   os << "Start state: 0" << std::endl
00424      << "States:      0..." << dfa.n_states()-1 << std::endl
00425      << "Transitions:";
00426   for (int s = 0; s < static_cast<int>(dfa.n_states()); s++) {
00427     Gecode::DFA::Transitions t(dfa);
00428     int n = 0;
00429     while (t()) {
00430       if (t.transition()->i_state == s) {
00431         if ((n % 4) == 0)
00432           os << std::endl << "\t";
00433         os << "[" << t.transition()->i_state << "]"
00434            << "- " << t.transition()->symbol << " >"
00435            << "[" << t.transition()->o_state << "]  ";
00436         ++n;
00437       }
00438       ++t;
00439     }
00440   }
00441   os << std::endl << "Final states: "
00442      << std::endl
00443      << "\t[" << dfa.final_fst() << "] ... ["
00444      << dfa.final_lst()-1 << "]"
00445      << std::endl;
00446   return os;
00447 }
00448 
00449 namespace Gecode {
00450 
00451   DFA::DFAI*
00452   DFA::DFAI::copy(void) {
00453     DFAI* d = reinterpret_cast<DFAI*>
00454       (Memory::malloc(sizeof(DFAI) + sizeof(Transition)*(n_trans-1)));
00455     d->use_cnt   = 1;
00456     d->n_states  = n_states;
00457     d->n_trans   = n_trans;
00458     d->final_fst = final_fst;
00459     d->final_lst = final_lst;
00460     memcpy(&d->trans[0], &trans[0], sizeof(Transition)*n_trans);
00461     return d;
00462   }
00463 
00464 }
00465 
00466 // STATISTICS: int-prop
00467