Generated on Fri Oct 19 11:25:14 2018 for Gecode by doxygen 1.6.3

reg.cpp

Go to the documentation of this file.
00001 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
00002 /*
00003  *  Main authors:
00004  *     Christian Schulte <schulte@gecode.org>
00005  *
00006  *  Copyright:
00007  *     Christian Schulte, 2004
00008  *
00009  *  This file is part of Gecode, the generic constraint
00010  *  development environment:
00011  *     http://www.gecode.org
00012  *
00013  *  Permission is hereby granted, free of charge, to any person obtaining
00014  *  a copy of this software and associated documentation files (the
00015  *  "Software"), to deal in the Software without restriction, including
00016  *  without limitation the rights to use, copy, modify, merge, publish,
00017  *  distribute, sublicense, and/or sell copies of the Software, and to
00018  *  permit persons to whom the Software is furnished to do so, subject to
00019  *  the following conditions:
00020  *
00021  *  The above copyright notice and this permission notice shall be
00022  *  included in all copies or substantial portions of the Software.
00023  *
00024  *  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
00025  *  EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
00026  *  MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
00027  *  NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
00028  *  LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
00029  *  OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
00030  *  WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
00031  *
00032  */
00033 
00034 #include <gecode/minimodel.hh>
00035 
00036 namespace Gecode {
00037 
00038   namespace MiniModel {
00039 
00040     class PosSet;
00044     typedef Support::BlockAllocator<PosSet,Region> PosSetAllocator;
00045 
00046     class NodeInfo;
00047     class PosInfo;
00048 
00049   }
00050 
00052   class REG::Exp {
00053   public:
00055     unsigned int use_cnt;
00057     int _n_pos;
00061     enum ExpType {
00062       ET_SYMBOL,
00063       ET_CONC,
00064       ET_OR,
00065       ET_STAR
00066     };
00068     ExpType type;
00070     union {
00072       int  symbol;
00074       Exp* kids[2];
00075     } data;
00076 
00078     MiniModel::PosSet*
00079     followpos(MiniModel::PosSetAllocator&,MiniModel::PosInfo*);
00081     static void inc(Exp* e);
00083     static void dec(Exp* e);
00085     static int n_pos(Exp* e);
00087     void toString(std::ostringstream& os) const;
00089     std::string toString(void) const;
00090 
00091     static void* operator new(size_t);
00092     static void  operator delete(void*);
00093   private:
00095     void dispose(void);
00096   };
00097 
00098 
00099   /*
00100    * Operations on expression nodes
00101    *
00102    */
00103 
00104 
00105   forceinline void*
00106   REG::Exp::operator new(size_t s) {
00107     return heap.ralloc(s);
00108   }
00109   forceinline void
00110   REG::Exp::operator delete(void*) {
00111     // Deallocation happens in dispose
00112   }
00113 
00114   void
00115   REG::Exp::dispose(void) {
00116     Region region;
00117     Support::DynamicStack<Exp*,Region> todo(region);
00118     todo.push(this);
00119     while (!todo.empty()) {
00120       Exp* e = todo.pop();
00121       switch (e->type) {
00122       case ET_OR:
00123       case ET_CONC:
00124         if ((e->data.kids[1] != NULL) && (--e->data.kids[1]->use_cnt == 0))
00125           todo.push(e->data.kids[1]);
00126       case ET_STAR:
00127         if ((e->data.kids[0] != NULL) && (--e->data.kids[0]->use_cnt == 0))
00128           todo.push(e->data.kids[0]);
00129       default: ;
00130       }
00131       heap.rfree(e);
00132     }
00133   }
00134 
00135   forceinline void
00136   REG::Exp::inc(Exp* e) {
00137     if (e != NULL)
00138       e->use_cnt++;
00139   }
00140   forceinline void
00141   REG::Exp::dec(Exp* e) {
00142     if ((e != NULL) && (--e->use_cnt == 0))
00143       e->dispose();
00144   }
00145 
00146 
00147   forceinline int
00148   REG::Exp::n_pos(Exp* e) {
00149     return (e != NULL) ? e->_n_pos : 0;
00150   }
00151 
00152   void
00153   REG::Exp::toString(std::ostringstream& os) const {
00154     switch (type) {
00155     case ET_SYMBOL:
00156       os << "[" << data.symbol << "]";
00157       return;
00158     case ET_STAR:
00159       {
00160         bool par = ((data.kids[0] != NULL) &&
00161                     ((data.kids[0]->type == ET_CONC) ||
00162                      (data.kids[0]->type == ET_OR)));
00163         os << (par ? "*(" : "*");
00164         if (data.kids[0]==NULL) {
00165           os << "[]";
00166         } else {
00167           data.kids[0]->toString(os);
00168         }
00169         os << (par ? ")" : "");
00170         return;
00171       }
00172     case ET_CONC:
00173       {
00174         bool par0 = ((data.kids[0] != NULL) &&
00175                      (data.kids[0]->type == ET_OR));
00176         os << (par0 ? "(" : "");
00177         if (data.kids[0]==NULL) {
00178           os << "[]";
00179         } else {
00180           data.kids[0]->toString(os);
00181         }
00182         os << (par0 ? ")+" : "+");
00183         bool par1 = ((data.kids[1] != NULL) &&
00184                      (data.kids[1]->type == ET_OR));
00185         os << (par1 ? "(" : "");
00186         if (data.kids[1]==NULL) {
00187           os << "[]";
00188         } else {
00189           data.kids[1]->toString(os);
00190         }
00191         os << (par1 ? ")" : "");
00192         return;
00193       }
00194     case ET_OR:
00195       if (data.kids[0]==NULL) {
00196         os << "[]";
00197       } else {
00198         data.kids[0]->toString(os);
00199       }
00200       os << "|";
00201       if (data.kids[1]==NULL) {
00202         os << "[]";
00203       } else {
00204         data.kids[1]->toString(os);
00205       }
00206       return;
00207     default: GECODE_NEVER;
00208     }
00209     GECODE_NEVER;
00210     return;
00211   }
00212 
00213   std::string
00214   REG::Exp::toString(void) const {
00215     std::ostringstream os;
00216     toString(os);
00217     return os.str();
00218   }
00219 
00220 
00221   /*
00222    * Regular expressions
00223    *
00224    */
00225 
00226   forceinline
00227   REG::REG(Exp* f) : e(f) {}
00228 
00229   REG::REG(void) : e(NULL) {}
00230 
00231   REG::REG(const REG& r) : e(r.e) {
00232     REG::Exp::inc(e);
00233   }
00234 
00235   const REG&
00236   REG::operator =(const REG& r) {
00237     if (&r != this) {
00238       REG::Exp::inc(r.e);
00239       REG::Exp::dec(e);
00240       e = r.e;
00241     }
00242     return *this;
00243   }
00244 
00245   REG::~REG(void) {
00246     REG::Exp::dec(e);
00247   }
00248 
00249   REG::REG(int s) : e(new Exp) {
00250     e->use_cnt     = 1;
00251     e->_n_pos      = 1;
00252     e->type        = REG::Exp::ET_SYMBOL;
00253     e->data.symbol = s;
00254   }
00255 
00256   REG::REG(const IntArgs& x) {
00257     int n = x.size();
00258     if (n < 1)
00259       throw MiniModel::TooFewArguments("REG");
00260     Region region;
00261     Exp** a = region.alloc<Exp*>(n);
00262     // Initialize with symbols
00263     for (int i=n; i--; ) {
00264       a[i] = new Exp();
00265       a[i]->use_cnt     = 1;
00266       a[i]->_n_pos      = 1;
00267       a[i]->type        = REG::Exp::ET_SYMBOL;
00268       a[i]->data.symbol = x[i];
00269     }
00270     // Build a balanced tree of alternative nodes
00271     for (int m=n; m>1; ) {
00272       if (m & 1) {
00273         m -= 1;
00274         Exp* e1 = a[m];
00275         Exp* e2 = a[0];
00276         a[0] = new Exp;
00277         a[0]->use_cnt      = 1;
00278         a[0]->_n_pos       = REG::Exp::n_pos(e1) + REG::Exp::n_pos(e2);
00279         a[0]->type         = REG::Exp::ET_OR;
00280         a[0]->data.kids[0] = e1;
00281         a[0]->data.kids[1] = e2;
00282       } else {
00283         m >>= 1;
00284         for (int i=0; i<m; i++) {
00285           Exp* e1 = a[2*i];
00286           Exp* e2 = a[2*i+1];
00287           a[i] = new Exp;
00288           a[i]->use_cnt      = 1;
00289           a[i]->_n_pos       = REG::Exp::n_pos(e1) + REG::Exp::n_pos(e2);
00290           a[i]->type         = REG::Exp::ET_OR;
00291           a[i]->data.kids[0] = e1;
00292           a[i]->data.kids[1] = e2;
00293         }
00294       }
00295     }
00296     e = a[0];
00297   }
00298 
00299   REG
00300   REG::operator |(const REG& r2) {
00301     if (e == r2.e)
00302       return *this;
00303     Exp* f = new Exp();
00304     f->use_cnt      = 1;
00305     f->_n_pos       = REG::Exp::n_pos(e) + REG::Exp::n_pos(r2.e);
00306     f->type         = REG::Exp::ET_OR;
00307     f->data.kids[0] = e;    REG::Exp::inc(e);
00308     f->data.kids[1] = r2.e; REG::Exp::inc(r2.e);
00309     REG r(f);
00310     return r;
00311   }
00312 
00313   REG&
00314   REG::operator |=(const REG& r2) {
00315     if (e == r2.e)
00316       return *this;
00317     Exp* f = new Exp();
00318     f->use_cnt      = 1;
00319     f->_n_pos       = REG::Exp::n_pos(e) + REG::Exp::n_pos(r2.e);
00320     f->type         = REG::Exp::ET_OR;
00321     f->data.kids[0] = e;
00322     f->data.kids[1] = r2.e; REG::Exp::inc(r2.e);
00323     e=f;
00324     return *this;
00325   }
00326 
00327   REG
00328   REG::operator +(const REG& r2) {
00329     if (e == NULL)    return r2;
00330     if (r2.e == NULL) return *this;
00331     Exp* f = new Exp();
00332     f->use_cnt      = 1;
00333     f->_n_pos       = REG::Exp::n_pos(e) + REG::Exp::n_pos(r2.e);
00334     f->type         = REG::Exp::ET_CONC;
00335     f->data.kids[0] = e;    REG::Exp::inc(e);
00336     f->data.kids[1] = r2.e; REG::Exp::inc(r2.e);
00337     REG r(f);
00338     return r;
00339   }
00340 
00341   REG&
00342   REG::operator +=(const REG& r2) {
00343     if (r2.e == NULL)
00344       return *this;
00345     if (e == NULL) {
00346       e=r2.e; REG::Exp::inc(e);
00347     } else {
00348       Exp* f = new Exp();
00349       f->use_cnt      = 1;
00350       f->_n_pos       = REG::Exp::n_pos(e) + REG::Exp::n_pos(r2.e);
00351       f->type         = REG::Exp::ET_CONC;
00352       f->data.kids[0] = e;
00353       f->data.kids[1] = r2.e; REG::Exp::inc(r2.e);
00354       e=f;
00355     }
00356     return *this;
00357   }
00358 
00359   REG
00360   REG::operator *(void) {
00361     if ((e == NULL) || (e->type == REG::Exp::ET_STAR))
00362       return *this;
00363     Exp* f = new Exp();
00364     f->use_cnt      = 1;
00365     f->_n_pos       = REG::Exp::n_pos(e);
00366     f->type         = REG::Exp::ET_STAR;
00367     f->data.kids[0] = e; REG::Exp::inc(e);
00368     REG r(f);
00369     return r;
00370   }
00371 
00372   REG
00373   REG::operator ()(unsigned int n, unsigned int m) {
00374     REG r;
00375     if ((n>m) || (m == 0))
00376       return r;
00377     if (n>0) {
00378       unsigned int i = n;
00379       REG r0 = *this;
00380       while (i>0)
00381         if (i & 1) {
00382           r = r0+r; i--;
00383         } else {
00384           r0 = r0+r0; i >>= 1;
00385         }
00386     }
00387     if (m > n) {
00388       unsigned int i = m-n;
00389       REG s0;
00390       s0 = s0 | *this;
00391       REG s;
00392       while (i>0)
00393         if (i & 1) {
00394           s = s0+s; i--;
00395         } else {
00396           s0 = s0+s0; i >>= 1;
00397         }
00398       r = r + s;
00399     }
00400     return r;
00401   }
00402 
00403   REG
00404   REG::operator ()(unsigned int n) {
00405     REG r;
00406     if (n > 0) {
00407       REG r0 = *this;
00408       unsigned int i = n;
00409       while (i>0)
00410         if (i & 1) {
00411           r = r0+r; i--;
00412         } else {
00413           r0 = r0+r0; i >>= 1;
00414         }
00415     }
00416     return r+**this;
00417   }
00418 
00419   REG
00420   REG::operator +(void) {
00421     return this->operator ()(1);
00422   }
00423 
00424   std::string
00425   REG::toString(void) const {
00426     if (e==NULL) {
00427       return "[]";
00428     }
00429     return e->toString();
00430   }
00431 
00432   namespace MiniModel {
00433 
00434     /*
00435      * Sets of positions
00436      *
00437      */
00438 
00442     enum PosSetCmp {
00443       PSC_LE,
00444       PSC_EQ,
00445       PSC_GR
00446     };
00447 
00451     class PosSet : public Support::BlockClient<PosSet,Region> {
00452       // Maintain sets of positions in inverse order
00453       // This makes the check whether the last position is included
00454       // more efficient.
00455     public:
00456       int pos; PosSet* next;
00457 
00458       PosSet(void);
00459       PosSet(int);
00460 
00461       bool in(int) const;
00462       static PosSetCmp cmp(PosSet*,PosSet*);
00463       static PosSet*   cup(PosSetAllocator&,PosSet*,PosSet*);
00464     };
00465 
00466 
00467     forceinline
00468     PosSet::PosSet(void) {}
00469     forceinline
00470     PosSet::PosSet(int p) : pos(p), next(NULL) {}
00471 
00472 
00473     forceinline bool
00474     PosSet::in(int p) const {
00475       for (const PosSet* ps = this; ps != NULL; ps = ps->next)
00476         if (ps->pos == p) {
00477           return true;
00478         } else if (ps->pos < p) {
00479           return false;
00480         }
00481       return false;
00482     }
00483 
00484     forceinline PosSetCmp
00485     PosSet::cmp(PosSet* ps1, PosSet* ps2) {
00486       while ((ps1 != NULL) && (ps2 != NULL)) {
00487         if (ps1 == ps2)
00488           return PSC_EQ;
00489         if (ps1->pos < ps2->pos)
00490           return PSC_LE;
00491         if (ps1->pos > ps2->pos)
00492           return PSC_GR;
00493         ps1 = ps1->next; ps2 = ps2->next;
00494       }
00495       if (ps1 == ps2)
00496         return PSC_EQ;
00497       return ps1 == NULL ? PSC_LE : PSC_GR;
00498     }
00499 
00500     PosSet*
00501     PosSet::cup(PosSetAllocator& psm, PosSet* ps1, PosSet* ps2) {
00502       PosSet*  ps;
00503       PosSet** p = &ps;
00504       while ((ps1 != NULL) && (ps2 != NULL)) {
00505         if (ps1 == ps2) {
00506           *p = ps1; return ps;
00507         }
00508         PosSet* n = new (psm) PosSet;
00509         *p = n; p = &n->next;
00510         if (ps1->pos == ps2->pos) {
00511           n->pos = ps1->pos;
00512           ps1 = ps1->next; ps2 = ps2->next;
00513         } else if (ps1->pos > ps2->pos) {
00514           n->pos = ps1->pos; ps1 = ps1->next;
00515         } else {
00516           n->pos = ps2->pos; ps2 = ps2->next;
00517         }
00518       }
00519       *p = (ps1 != NULL) ? ps1 : ps2;
00520       return ps;
00521     }
00522 
00523 
00525     class NodeInfo {
00526     public:
00527       bool    nullable;
00528       PosSet* firstpos;
00529       PosSet* lastpos;
00530       NodeInfo(bool n=false, PosSet* fp=NULL, PosSet* lp=NULL);
00531     };
00532 
00534     class ExpInfo {
00535     public:
00536       REG::Exp* exp;
00537       bool open;
00538       ExpInfo(REG::Exp* e=NULL);
00539     };
00540 
00545     class PosInfo {
00546     public:
00547       int     symbol;
00548       PosSet* followpos;
00549     };
00550 
00551     forceinline
00552     NodeInfo::NodeInfo(bool n, PosSet* fp, PosSet* lp)
00553       : nullable(n), firstpos(fp), lastpos(lp) {}
00554 
00555     forceinline
00556     ExpInfo::ExpInfo(REG::Exp* e)
00557       : exp(e), open(true) {}
00558 
00559   }
00560 
00561   forceinline MiniModel::PosSet*
00562   REG::Exp::followpos(MiniModel::PosSetAllocator& psm,
00563                       MiniModel::PosInfo* pi) {
00564     int p=0;
00565 
00566     using MiniModel::PosSet;
00567     using MiniModel::NodeInfo;
00568     using MiniModel::ExpInfo;
00569 
00570     Region region;
00571 
00572     Support::DynamicStack<ExpInfo,Region> todo(region);
00573     Support::DynamicStack<NodeInfo,Region> done(region);
00574 
00575     // Start with first expression to be processed
00576     todo.push(ExpInfo(this));
00577 
00578     do {
00579       if (todo.top().exp == NULL) {
00580         todo.pop();
00581         done.push(NodeInfo(true,NULL,NULL));
00582       } else {
00583         switch (todo.top().exp->type) {
00584         case ET_SYMBOL:
00585           {
00586             pi[p].symbol = todo.pop().exp->data.symbol;
00587             PosSet* ps = new (psm) PosSet(p++);
00588             done.push(NodeInfo(false,ps,ps));
00589           }
00590           break;
00591         case ET_STAR:
00592           if (todo.top().open) {
00593             // Evaluate subexpression recursively
00594             todo.top().open = false;
00595             todo.push(todo.top().exp->data.kids[0]);
00596           } else {
00597             todo.pop();
00598             NodeInfo ni = done.pop();
00599             for (PosSet* ps = ni.lastpos; ps != NULL; ps = ps->next)
00600               pi[ps->pos].followpos =
00601                 PosSet::cup(psm,pi[ps->pos].followpos,ni.firstpos);
00602             done.push(NodeInfo(true,ni.firstpos,ni.lastpos));
00603           }
00604           break;
00605         case ET_CONC:
00606           if (todo.top().open) {
00607             // Evaluate subexpressions recursively
00608             todo.top().open = false;
00609             REG::Exp* e = todo.top().exp;
00610             todo.push(e->data.kids[1]);
00611             todo.push(e->data.kids[0]);
00612           } else {
00613             todo.pop();
00614             NodeInfo ni1 = done.pop();
00615             NodeInfo ni0 = done.pop();
00616             for (PosSet* ps = ni0.lastpos; ps != NULL; ps = ps->next)
00617               pi[ps->pos].followpos =
00618                 PosSet::cup(psm,pi[ps->pos].followpos,ni1.firstpos);
00619             done.push(NodeInfo(ni0.nullable & ni1.nullable,
00620                                ni0.nullable ?
00621                                PosSet::cup(psm,ni0.firstpos,ni1.firstpos) : ni0.firstpos,
00622                                ni1.nullable ?
00623                                PosSet::cup(psm,ni0.lastpos,ni1.lastpos) : ni1.lastpos));
00624           }
00625           break;
00626         case ET_OR:
00627           if (todo.top().open) {
00628             // Evaluate subexpressions recursively
00629             todo.top().open = false;
00630             REG::Exp* e = todo.top().exp;
00631             todo.push(e->data.kids[1]);
00632             todo.push(e->data.kids[0]);
00633           } else {
00634             todo.pop();
00635             NodeInfo ni1 = done.pop();
00636             NodeInfo ni0 = done.pop();
00637             done.push(NodeInfo(ni0.nullable | ni1.nullable,
00638                                PosSet::cup(psm,ni0.firstpos,ni1.firstpos),
00639                                PosSet::cup(psm,ni0.lastpos,ni1.lastpos)));
00640           }
00641           break;
00642         default: GECODE_NEVER;
00643         }
00644       }
00645     } while (!todo.empty());
00646     return done.top().firstpos;
00647   }
00648 
00649 
00650   namespace MiniModel {
00651 
00652     class StateNode;
00653 
00657     typedef Support::BlockAllocator<StateNode,Heap> StatePoolAllocator;
00658 
00662     class StateNode : public Support::BlockClient<StateNode,Heap> {
00663     public:
00664       PosSet*    pos;
00665       int        state;
00666       StateNode* next;
00667       StateNode* left;
00668       StateNode* right;
00669     };
00670 
00674     class StatePool {
00675     public:
00676       int   n_states;
00677       StateNode  root;
00678       StateNode* next;
00679       StateNode* all;
00680 
00681       StatePool(PosSet*);
00682 
00683       StateNode* pop(void);
00684       bool empty(void) const;
00685 
00686       int state(StatePoolAllocator&, PosSet*);
00687     };
00688 
00689     forceinline
00690     StatePool::StatePool(PosSet* ps) {
00691       next     = &root;
00692       all      = NULL;
00693       n_states = 1;
00694       root.pos   = ps;
00695       root.state = 0;
00696       root.next  = NULL;
00697       root.left  = NULL;
00698       root.right = NULL;
00699     }
00700 
00701     forceinline StateNode*
00702     StatePool::pop(void) {
00703       StateNode* n = next;
00704       next = n->next;
00705       n->next = all;
00706       all = n;
00707       return n;
00708     }
00709 
00710     forceinline bool
00711     StatePool::empty(void) const {
00712       return next == NULL;
00713     }
00714 
00715     forceinline int
00716     StatePool::state(StatePoolAllocator& spm, PosSet* ps) {
00717       int d = 0;
00718       StateNode** p = NULL;
00719       StateNode*  n = &root;
00720       do {
00721         switch (PosSet::cmp(ps,n->pos)) {
00722         case PSC_EQ: return n->state;
00723         case PSC_LE: p = &n->left;  n = *p; break;
00724         case PSC_GR: p = &n->right; n = *p; break;
00725         default: GECODE_NEVER;
00726         }
00727         d++;
00728       } while (n != NULL);
00729       n = new (spm) StateNode; *p = n;
00730       n->pos   = ps;
00731       n->state = n_states++;
00732       n->next  = next;
00733       n->left  = NULL;
00734       n->right = NULL;
00735       next = n;
00736       return n->state;
00737     }
00738 
00742     class SymbolsInc {
00743     public:
00744       forceinline bool
00745       operator ()(int x, int y) {
00746         return x < y;
00747       }
00748       forceinline static void
00749       sort(int s[], int n) {
00750         SymbolsInc o;
00751         Support::quicksort<int,SymbolsInc>(s,n,o);
00752       }
00753     };
00754 
00755 
00760     class TransitionBag {
00761     private:
00762       Support::DynamicArray<DFA::Transition,Heap> t;
00763       int n;
00764     public:
00765       TransitionBag(void);
00766       void add(int,int,int);
00767       void finish(void);
00768       DFA::Transition* transitions(void);
00769     };
00770 
00771     forceinline
00772     TransitionBag::TransitionBag(void) : t(heap), n(0) {}
00773 
00774     forceinline void
00775     TransitionBag::add(int i_state, int symbol, int o_state) {
00776       t[n].i_state = i_state;
00777       t[n].symbol  = symbol;
00778       t[n].o_state = o_state;
00779       n++;
00780     }
00781 
00782     forceinline void
00783     TransitionBag::finish(void) {
00784       t[n].i_state = -1;
00785     }
00786 
00787     forceinline DFA::Transition*
00788     TransitionBag::transitions(void) {
00789       return &t[0];
00790     }
00791 
00792 
00797     class FinalBag {
00798     private:
00799       Support::DynamicArray<int,Heap> f;
00800       int n;
00801     public:
00802       FinalBag(void);
00803       void add(int);
00804       void finish(void);
00805       int* finals(void);
00806     };
00807 
00808     forceinline
00809     FinalBag::FinalBag(void) : f(heap), n(0) {}
00810 
00811     forceinline void
00812     FinalBag::add(int state) {
00813       f[n++] = state;
00814     }
00815 
00816     forceinline void
00817     FinalBag::finish(void) {
00818       f[n] = -1;
00819     }
00820 
00821     forceinline int*
00822     FinalBag::finals(void) {
00823       return &f[0];
00824     }
00825 
00826   }
00827 
00828   REG::operator DFA(void) {
00829     using MiniModel::PosSetAllocator;
00830     using MiniModel::StatePoolAllocator;
00831     using MiniModel::PosInfo;
00832     using MiniModel::PosSet;
00833     using MiniModel::NodeInfo;
00834 
00835     using MiniModel::StatePool;
00836     using MiniModel::StateNode;
00837 
00838     using MiniModel::TransitionBag;
00839     using MiniModel::FinalBag;
00840 
00841     using MiniModel::SymbolsInc;
00842 
00843     Region region;
00844     PosSetAllocator    psm(region);
00845     StatePoolAllocator spm(heap);
00846     REG r = *this + REG(Int::Limits::max+1);
00847     int n_pos = REG::Exp::n_pos(r.e);
00848 
00849     PosInfo* pi = region.alloc<PosInfo>(n_pos);
00850     for (int i=n_pos; i--; )
00851       pi[i].followpos = NULL;
00852 
00853     PosSet* firstpos = r.e->followpos(psm,&pi[0]);
00854 
00855     // Compute symbols
00856     int* symbols = region.alloc<int>(n_pos);
00857     for (int i=n_pos; i--; )
00858       symbols[i] = pi[i].symbol;
00859 
00860     SymbolsInc::sort(&symbols[0],n_pos-1);
00861     int n_symbols = 1;
00862     for (int i = 1; i<n_pos-1; i++)
00863       if (symbols[i-1] != symbols[i])
00864         symbols[n_symbols++] = symbols[i];
00865 
00866     // Compute states and transitions
00867     TransitionBag tb;
00868     StatePool sp(firstpos);
00869     while (!sp.empty()) {
00870       StateNode* sn = sp.pop();
00871       for (int i = n_symbols; i--; ) {
00872         PosSet* u = NULL;
00873         for (PosSet* ps = sn->pos; ps != NULL; ps = ps->next)
00874           if (pi[ps->pos].symbol == symbols[i])
00875             u = PosSet::cup(psm,u,pi[ps->pos].followpos);
00876         if (u != NULL)
00877           tb.add(sn->state,symbols[i],sp.state(spm,u));
00878       }
00879     }
00880     tb.finish();
00881 
00882     // Compute final states
00883     FinalBag fb;
00884     for (StateNode* n = sp.all; n != NULL; n = n->next)
00885       if (n->pos->in(n_pos-1))
00886         fb.add(n->state);
00887     fb.finish();
00888 
00889     return DFA(0,tb.transitions(),fb.finals(),true);
00890   }
00891 
00892 }
00893 
00894 // STATISTICS: minimodel-any
00895