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

reg.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 
00024 #include "gecode/support/sort.hh"
00025 #include "gecode/support/block-allocator.hh"
00026 #include "gecode/support/dynamic-stack.hh"
00027 #include "gecode/support/dynamic-array.hh"
00028 
00029 namespace Gecode { 
00030 
00031   namespace Int { namespace Regular {
00032 
00033     class PosSet;
00037     typedef Support::BlockAllocator<PosSet> PosSetAllocator;
00038     
00039     class NodeInfo;
00040     class PosInfo;
00041     
00042   }}
00043 
00045   class REG::Exp {
00046   public:
00047     unsigned int use_cnt;
00048     unsigned int _n_pos;
00052     enum ExpType {
00053       ET_SYMBOL,
00054       ET_CONC,
00055       ET_OR,
00056       ET_STAR
00057     };
00058     ExpType type;
00059     union {
00060       int  symbol;
00061       Exp* kids[2];
00062     } data;
00063     
00064     void followpos(Int::Regular::PosSetAllocator&,
00065                    Int::Regular::NodeInfo&,
00066                    Int::Regular::PosInfo*,
00067                    int&);
00068     void inc(void);
00069     void dec(void);
00070     unsigned int n_pos(void) const;
00071     std::ostream& print(std::ostream&) const;
00072 
00073     static void* operator new(size_t);
00074     static void  operator delete(void*);
00075   private:
00076     void dispose(void);
00077   };
00078 
00079 
00080   /*
00081    * Operations on expression nodes
00082    *
00083    */
00084   
00085   
00086   forceinline void*
00087   REG::Exp::operator new(size_t s) {
00088     return Memory::malloc(s);
00089   }
00090   forceinline void
00091   REG::Exp::operator delete(void*) {
00092     // Deallocation happens in dispose
00093   }
00094   
00095   void
00096   REG::Exp::dispose(void) {
00097     Support::DynamicStack<Exp*> todo;
00098     todo.push(this);
00099     while (!todo.empty()) {
00100       Exp* e = todo.pop();
00101       switch (e->type) {
00102       case ET_OR:
00103       case ET_CONC:
00104         if ((e->data.kids[1] != NULL) && (--e->data.kids[1]->use_cnt == 0))
00105           todo.push(e->data.kids[1]);
00106       case ET_STAR:
00107         if ((e->data.kids[0] != NULL) && (--e->data.kids[0]->use_cnt == 0))
00108           todo.push(e->data.kids[0]);
00109       default: ;
00110       }
00111       Memory::free(e);
00112     }
00113   }
00114   
00115   forceinline void
00116   REG::Exp::inc(void) {
00117     if (this != NULL)
00118       use_cnt++;
00119   }
00120   forceinline void
00121   REG::Exp::dec(void) {
00122     if ((this != NULL) && (--use_cnt == 0))
00123       dispose();
00124   }
00125   
00126   
00127   forceinline unsigned int
00128   REG::Exp::n_pos(void) const {
00129     return (this != NULL) ? _n_pos : 0;
00130   }
00131   
00132   std::ostream&
00133   REG::Exp::print(std::ostream& os) const {
00134     if (this == NULL)
00135       return os << "[]";
00136     switch (type) {
00137     case ET_SYMBOL:
00138       return os << "[" << data.symbol << "]";
00139     case ET_STAR:
00140       {
00141         bool par = ((data.kids[0] != NULL) &&
00142                     ((data.kids[0]->type == ET_CONC) ||
00143                      (data.kids[0]->type == ET_OR)));
00144         return data.kids[0]->print(os << (par ? "*(" : "*"))
00145                                       << (par ? ")" : "");
00146       }
00147     case ET_CONC:
00148       {
00149         bool par0 = ((data.kids[0] != NULL) &&
00150                      (data.kids[0]->type == ET_OR));
00151         std::ostream& os1 = data.kids[0]->print(os << (par0 ? "(" : ""))
00152                                                    << (par0 ? ")+" : "+");
00153         bool par1 = ((data.kids[1] != NULL) &&
00154                      (data.kids[1]->type == ET_OR));
00155         return data.kids[1]->print(os1 << (par1 ? "(" : "") )
00156                                        << (par1 ? ")" : "");
00157       }
00158     case ET_OR:
00159       return data.kids[1]->print(data.kids[0]->print(os) << "|");
00160     }
00161     assert(0);
00162     return os;
00163   }
00164   
00165   
00166   /*
00167    * Regular expressions
00168    *
00169    */
00170   
00171   forceinline
00172   REG::REG(Exp* f) : e(f) {}
00173   
00174   REG::REG(void) : e(NULL) {}
00175   
00176   REG::REG(const REG& r) : e(r.e) {
00177     e->inc();
00178   }
00179   
00180   std::ostream&
00181   REG::print(std::ostream& os) const {
00182     return e->print(os);
00183   }
00184   
00185   const REG&
00186   REG::operator=(const REG& r) {
00187     if (&r != this) {
00188       r.e->inc();
00189       e->dec();
00190       e = r.e;
00191     }
00192     return *this;
00193   }
00194   
00195   REG::~REG(void) {
00196     e->dec();
00197   }
00198   
00199   REG::REG(int s) : e(new Exp) {
00200     e->use_cnt     = 1;
00201     e->_n_pos      = 1;
00202     e->type        = REG::Exp::ET_SYMBOL;
00203     e->data.symbol = s;
00204   }
00205   
00206   REG
00207   REG::operator|(const REG& r2) {
00208     if (e == r2.e)
00209       return *this;
00210     Exp* f = new Exp();
00211     f->use_cnt      = 1;
00212     f->_n_pos       = e->n_pos() + r2.e->n_pos();
00213     f->type         = REG::Exp::ET_OR;
00214     f->data.kids[0] = e;    e->inc();
00215     f->data.kids[1] = r2.e; r2.e->inc();
00216     REG r(f);
00217     return r;
00218   }
00219   
00220   REG
00221   REG::operator+(const REG& r2) {
00222     if (e == NULL)    return r2;
00223     if (r2.e == NULL) return *this;
00224     Exp* f = new Exp();
00225     f->use_cnt      = 1;
00226     f->_n_pos       = e->n_pos() + r2.e->n_pos();
00227     f->type         = REG::Exp::ET_CONC;
00228     f->data.kids[0] = e;    e->inc();
00229     f->data.kids[1] = r2.e; r2.e->inc();
00230     REG r(f);
00231     return r;
00232   }
00233   
00234   REG
00235   REG::operator*(void) {
00236     if ((e == NULL) || (e->type == REG::Exp::ET_STAR))
00237       return *this;
00238     Exp* f = new Exp();
00239     f->use_cnt      = 1;
00240     f->_n_pos       = e->n_pos();
00241     f->type         = REG::Exp::ET_STAR;
00242     f->data.kids[0] = e; e->inc();
00243     REG r(f);
00244     return r;
00245   }
00246   
00247   REG
00248   REG::operator()(unsigned int n, unsigned int m) {
00249     REG r;
00250     if ((n>m) || (m == 0))
00251       return r;
00252     if (n>0) {
00253       int i = n;
00254       REG r0 = *this;
00255       while (i>0)
00256         if (i & 1) {
00257           r = r0+r; i--;
00258         } else {
00259           r0 = r0+r0; i >>= 1;
00260         }
00261     }
00262     if (m > n) {
00263       int i = m-n;
00264       REG s0;
00265       s0 = s0 | *this;
00266       REG s;
00267       while (i>0)
00268         if (i & 1) {
00269           s = s0+s; i--;
00270         } else {
00271           s0 = s0+s0; i >>= 1;
00272         }
00273       r = r + s;
00274     }
00275     return r;
00276   }
00277   
00278   REG
00279   REG::operator()(unsigned int n) {
00280     REG r;
00281     if (n > 0) {
00282       REG r0 = *this;
00283       int i = n;
00284       while (i>0)
00285         if (i & 1) {
00286           r = r0+r; i--;
00287         } else {
00288           r0 = r0+r0; i >>= 1;
00289         }
00290     }
00291     return r+**this;
00292   }
00293 
00294   REG
00295   REG::operator+(void) {
00296     return this->operator()(1);
00297   }
00298   
00299 
00300   namespace Int { namespace Regular {
00301 
00302     /*
00303      * Sets of positions
00304      *
00305      */
00306 
00310     enum PosSetCmp {
00311       PSC_LE,
00312       PSC_EQ,
00313       PSC_GR
00314     };
00315 
00319     class PosSet : public Support::BlockClient<PosSet> {
00320       // Maintain sets of positions in inverse order
00321       // This makes the check whether the last position is included
00322       // more efficient.
00323     public:
00324       int pos; PosSet* next;
00325 
00326       PosSet(void);
00327       PosSet(int);
00328 
00329       bool in(int) const;
00330       static PosSetCmp cmp(PosSet*,PosSet*);
00331       static PosSet*   cup(PosSetAllocator&,PosSet*,PosSet*);
00332     };
00333 
00334 
00335     forceinline
00336     PosSet::PosSet(void) {}
00337     forceinline
00338     PosSet::PosSet(int p) : pos(p), next(NULL) {}
00339 
00340 
00341     forceinline bool
00342     PosSet::in(int p) const {
00343       for (const PosSet* ps = this; ps != NULL; ps = ps->next)
00344         if (ps->pos == p) {
00345           return true;
00346         } else if (ps->pos < p) {
00347           return false;
00348         }
00349       return false;
00350     }
00351 
00352     forceinline PosSetCmp
00353     PosSet::cmp(PosSet* ps1, PosSet* ps2) {
00354       while ((ps1 != NULL) && (ps2 != NULL)) {
00355         if (ps1 == ps2)
00356           return PSC_EQ;
00357         if (ps1->pos < ps2->pos)
00358           return PSC_LE;
00359         if (ps1->pos > ps2->pos)
00360           return PSC_GR;
00361         ps1 = ps1->next; ps2 = ps2->next;
00362       }
00363       if (ps1 == ps2)
00364         return PSC_EQ;
00365       return ps1 == NULL ? PSC_LE : PSC_GR;
00366     }
00367 
00368     PosSet*
00369     PosSet::cup(PosSetAllocator& psm, PosSet* ps1, PosSet* ps2) {
00370       PosSet*  ps;
00371       PosSet** p = &ps;
00372       while ((ps1 != NULL) && (ps2 != NULL)) {
00373         if (ps1 == ps2) {
00374           *p = ps1; return ps;
00375         }
00376         PosSet* n = new (psm) PosSet;
00377         *p = n; p = &n->next;
00378         if (ps1->pos == ps2->pos) {
00379           n->pos = ps1->pos;
00380           ps1 = ps1->next; ps2 = ps2->next;
00381         } else if (ps1->pos > ps2->pos) {
00382           n->pos = ps1->pos; ps1 = ps1->next;
00383         } else {
00384           n->pos = ps2->pos; ps2 = ps2->next;
00385         }
00386       }
00387       *p = (ps1 != NULL) ? ps1 : ps2;
00388       return ps;
00389     }
00390 
00391 
00396     class NodeInfo {
00397     public:
00398       bool    nullable;
00399       PosSet* firstpos;
00400       PosSet* lastpos;
00401     };
00402 
00403 
00408     class PosInfo {
00409     public:
00410       int     symbol;
00411       PosSet* followpos;
00412     };
00413 
00414   }}
00415 
00416   void
00417   REG::Exp::followpos(Int::Regular::PosSetAllocator& psm, 
00418                       Int::Regular::NodeInfo& ni, 
00419                       Int::Regular::PosInfo* pi, int& p) {
00420     using Int::Regular::PosSet;
00421     using Int::Regular::NodeInfo;
00422     if (this == NULL) {
00423       ni.nullable = true;
00424       ni.firstpos = NULL;
00425       ni.lastpos  = NULL;
00426       return;
00427     }
00428     switch (type) {
00429     case ET_SYMBOL:
00430       {
00431         pi[p].symbol = data.symbol;
00432         PosSet* ps = new (psm) PosSet(p);
00433         p++;
00434         ni.nullable = false;
00435         ni.firstpos = ps;
00436         ni.lastpos  = ps;
00437       }
00438       break;
00439     case ET_STAR:
00440       {
00441         data.kids[0]->followpos(psm, ni, pi, p);
00442         ni.nullable = true;
00443         for (PosSet* ps = ni.lastpos; ps != NULL; ps = ps->next)
00444           pi[ps->pos].followpos =
00445             PosSet::cup(psm,pi[ps->pos].followpos, ni.firstpos);
00446       }
00447       break;
00448     case ET_CONC:
00449       {
00450         NodeInfo ni0; data.kids[0]->followpos(psm, ni0, pi, p);
00451         data.kids[1]->followpos(psm, ni, pi, p);
00452         for (PosSet* ps = ni0.lastpos; ps != NULL; ps = ps->next)
00453           pi[ps->pos].followpos =
00454             PosSet::cup(psm,pi[ps->pos].followpos,ni.firstpos);
00455         ni.firstpos =
00456           ni0.nullable ? PosSet::cup(psm,ni0.firstpos,ni.firstpos)
00457           : ni0.firstpos;
00458         ni.lastpos =
00459           ni.nullable ? PosSet::cup(psm,ni0.lastpos,ni.lastpos)
00460           : ni.lastpos;
00461         ni.nullable &= ni0.nullable;
00462       }
00463       break;
00464     case ET_OR:
00465       {
00466         NodeInfo ni0; data.kids[0]->followpos(psm, ni0, pi, p);
00467         data.kids[1]->followpos(psm, ni, pi, p);
00468         ni.nullable |= ni0.nullable;
00469         ni.firstpos = PosSet::cup(psm,ni0.firstpos,ni.firstpos);
00470         ni.lastpos  = PosSet::cup(psm,ni0.lastpos,ni.lastpos);
00471       }
00472       break;
00473     }
00474   }
00475 
00476 
00477   namespace Int { namespace Regular {
00478 
00479     class StateNode;
00480 
00484     typedef Support::BlockAllocator<StateNode> StatePoolAllocator;
00485     
00489     class StateNode : public Support::BlockClient<StateNode> {
00490     public:
00491       PosSet*    pos;
00492       int        state;
00493       StateNode* next;
00494       StateNode* left;
00495       StateNode* right;
00496     };
00497 
00501     class StatePool {
00502     public:
00503       int   n_states;
00504       StateNode  root;
00505       StateNode* next;
00506       StateNode* all;
00507 
00508       StatePool(PosSet*);
00509 
00510       StateNode* pop(void);
00511       bool empty(void) const;
00512 
00513       int state(StatePoolAllocator&, PosSet*);
00514     };
00515 
00516     forceinline
00517     StatePool::StatePool(PosSet* ps) {
00518       next     = &root;
00519       all      = NULL;
00520       n_states = 1;
00521       root.pos   = ps;
00522       root.state = 0;
00523       root.next  = NULL;
00524       root.left  = NULL;
00525       root.right = NULL;
00526     }
00527 
00528     forceinline StateNode*
00529     StatePool::pop(void) {
00530       StateNode* n = next;
00531       next = n->next;
00532       n->next = all;
00533       all = n;
00534       return n;
00535     }
00536 
00537     forceinline bool
00538     StatePool::empty(void) const {
00539       return next == NULL;
00540     }
00541 
00542     forceinline int
00543     StatePool::state(StatePoolAllocator& spm, PosSet* ps) {
00544       int d = 0;
00545       StateNode** p = NULL;
00546       StateNode*  n = &root;
00547       do {
00548         switch (PosSet::cmp(ps,n->pos)) {
00549         case PSC_EQ: return n->state;
00550         case PSC_LE: p = &n->left;  n = *p; break;
00551         case PSC_GR: p = &n->right; n = *p; break;
00552         }
00553         d++;
00554       } while (n != NULL);
00555       n = new (spm) StateNode; *p = n;
00556       n->pos   = ps;
00557       n->state = n_states++;
00558       n->next  = next;
00559       n->left  = NULL;
00560       n->right = NULL;
00561       next = n;
00562       return n->state;
00563     }
00564 
00568     class SymbolsInc {
00569     public:
00570       forceinline bool
00571       operator()(int x, int y) {
00572         return x < y;
00573       }
00574       forceinline static void
00575       sort(int s[], int n) {
00576         SymbolsInc o;
00577         Support::quicksort<int,SymbolsInc>(s,n,o);
00578       }
00579     };
00580 
00581 
00586     class TransitionBag {
00587     private:
00588       Support::DynamicArray<DFA::Transition> t;
00589       int n;
00590     public:
00591       TransitionBag(void);
00592       void add(int,int,int);
00593       void finish(void);
00594       DFA::Transition* transitions(void);
00595     };
00596     
00597     forceinline
00598     TransitionBag::TransitionBag(void) : n(0) {}
00599     
00600     forceinline void
00601     TransitionBag::add(int i_state, int symbol, int o_state) {
00602       t[n].i_state = i_state;
00603       t[n].symbol  = symbol;
00604       t[n].o_state = o_state;
00605       n++;
00606     }
00607     
00608     forceinline void
00609     TransitionBag::finish(void) {
00610       t[n].i_state = -1;
00611     }
00612     
00613     forceinline DFA::Transition*
00614     TransitionBag::transitions(void) {
00615       return &t[0];
00616     }
00617     
00618     
00623     class FinalBag {
00624     private:
00625       Support::DynamicArray<int> f;
00626       int n;
00627     public:
00628       FinalBag(void);
00629       void add(int);
00630       void finish(void);
00631       int* finals(void);
00632     };
00633     
00634     forceinline
00635     FinalBag::FinalBag(void) : n(0) {}
00636     
00637     forceinline void
00638     FinalBag::add(int state) {
00639       f[n++] = state;
00640     }
00641     
00642     forceinline void
00643     FinalBag::finish(void) {
00644       f[n] = -1;
00645     }
00646     
00647     forceinline int*
00648     FinalBag::finals(void) {
00649       return &f[0];
00650     }
00651     
00652   }}
00653 
00654   DFA::DFA(REG& r0) {
00655     using Int::Regular::PosSetAllocator;
00656     using Int::Regular::StatePoolAllocator;
00657     using Int::Regular::PosInfo;
00658     using Int::Regular::PosSet;
00659     using Int::Regular::NodeInfo;
00660 
00661     using Int::Regular::StatePool;
00662     using Int::Regular::StateNode;
00663 
00664     using Int::Regular::TransitionBag;
00665     using Int::Regular::FinalBag;
00666 
00667     using Int::Regular::SymbolsInc;
00668 
00669     PosSetAllocator    psm;
00670     StatePoolAllocator spm;
00671     REG r = r0 + REG(Limits::Int::int_max+1);
00672     int n_pos = r.e->n_pos();
00673 
00674     GECODE_AUTOARRAY(PosInfo, pi, n_pos);
00675     for (int i=n_pos; i--; )
00676       pi[i].followpos = NULL;
00677 
00678     NodeInfo ni_root;
00679     int n_p = 0;
00680     r.e->followpos(psm,ni_root,&pi[0],n_p);
00681     assert(n_p == n_pos);
00682 
00683     // Compute symbols
00684     GECODE_AUTOARRAY(int, symbols, n_pos);
00685     for (int i=n_pos; i--; )
00686       symbols[i] = pi[i].symbol;
00687 
00688     SymbolsInc::sort(&symbols[0],n_pos-1);
00689     int n_symbols = 1;
00690     for (int i = 1; i<n_pos-1; i++)
00691       if (symbols[i-1] != symbols[i])
00692         symbols[n_symbols++] = symbols[i];
00693 
00694     // Compute states and transitions
00695     TransitionBag tb;
00696     StatePool sp(ni_root.firstpos);
00697     while (!sp.empty()) {
00698       StateNode* sn = sp.pop();
00699       for (int i = n_symbols; i--; ) {
00700         PosSet* u = NULL;
00701         for (PosSet* ps = sn->pos; ps != NULL; ps = ps->next)
00702           if (pi[ps->pos].symbol == symbols[i])
00703             u = PosSet::cup(psm,u,pi[ps->pos].followpos);
00704         if (u != NULL)
00705           tb.add(sn->state,symbols[i],sp.state(spm,u));
00706       }
00707     }
00708     tb.finish();
00709 
00710     // Compute final states
00711     FinalBag fb;
00712     for (StateNode* n = sp.all; n != NULL; n = n->next)
00713       if (n->pos->in(n_pos-1))
00714         fb.add(n->state);
00715     fb.finish();
00716 
00717     init(0,tb.transitions(),fb.finals(),true);
00718   }
00719 
00720 }
00721 
00722 /*
00723  * Computing with expressions
00724  *
00725  */
00726 
00727 
00728 std::ostream&
00729 operator<<(std::ostream& os, const Gecode::REG& r) {
00730   return r.print(os);
00731 }
00732 
00733 
00734 // STATISTICS: int-prop
00735