00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
00031
00032
00033
00034
00035
00036
00037
00038 #include <gecode/minimodel.hh>
00039
00040 namespace Gecode {
00041
00042 namespace MiniModel {
00043
00044 class PosSet;
00048 typedef Support::BlockAllocator<PosSet,Heap> PosSetAllocator;
00049
00050 class NodeInfo;
00051 class PosInfo;
00052
00053 }
00054
00056 class REG::Exp {
00057 public:
00059 unsigned int use_cnt;
00061 int _n_pos;
00065 enum ExpType {
00066 ET_SYMBOL,
00067 ET_CONC,
00068 ET_OR,
00069 ET_STAR
00070 };
00072 ExpType type;
00074 union {
00076 int symbol;
00078 Exp* kids[2];
00079 } data;
00080
00081 MiniModel::PosSet*
00082 followpos(MiniModel::PosSetAllocator&,MiniModel::PosInfo*);
00083 void inc(void);
00084 void dec(void);
00085 int n_pos(void) const;
00087 template<class Char, class Traits>
00088 std::basic_ostream<Char,Traits>&
00089 print(std::basic_ostream<Char,Traits>& os) const;
00090
00091 static void* operator new(size_t);
00092 static void operator delete(void*);
00093 private:
00094 void dispose(void);
00095 };
00096
00097
00098
00099
00100
00101
00102
00103
00104 forceinline void*
00105 REG::Exp::operator new(size_t s) {
00106 return heap.ralloc(s);
00107 }
00108 forceinline void
00109 REG::Exp::operator delete(void*) {
00110
00111 }
00112
00113 void
00114 REG::Exp::dispose(void) {
00115 Support::DynamicStack<Exp*,Heap> todo(heap);
00116 todo.push(this);
00117 while (!todo.empty()) {
00118 Exp* e = todo.pop();
00119 switch (e->type) {
00120 case ET_OR:
00121 case ET_CONC:
00122 if ((e->data.kids[1] != NULL) && (--e->data.kids[1]->use_cnt == 0))
00123 todo.push(e->data.kids[1]);
00124 case ET_STAR:
00125 if ((e->data.kids[0] != NULL) && (--e->data.kids[0]->use_cnt == 0))
00126 todo.push(e->data.kids[0]);
00127 default: ;
00128 }
00129 heap.rfree(e);
00130 }
00131 }
00132
00133 forceinline void
00134 REG::Exp::inc(void) {
00135 if (this != NULL)
00136 use_cnt++;
00137 }
00138 forceinline void
00139 REG::Exp::dec(void) {
00140 if ((this != NULL) && (--use_cnt == 0))
00141 dispose();
00142 }
00143
00144
00145 forceinline int
00146 REG::Exp::n_pos(void) const {
00147 return (this != NULL) ? _n_pos : 0;
00148 }
00149
00150
00151
00152
00153
00154
00155
00156 forceinline
00157 REG::REG(Exp* f) : e(f) {}
00158
00159 REG::REG(void) : e(NULL) {}
00160
00161 REG::REG(const REG& r) : e(r.e) {
00162 e->inc();
00163 }
00164
00165 const REG&
00166 REG::operator =(const REG& r) {
00167 if (&r != this) {
00168 r.e->inc();
00169 e->dec();
00170 e = r.e;
00171 }
00172 return *this;
00173 }
00174
00175 REG::~REG(void) {
00176 e->dec();
00177 }
00178
00179 REG::REG(int s) : e(new Exp) {
00180 e->use_cnt = 1;
00181 e->_n_pos = 1;
00182 e->type = REG::Exp::ET_SYMBOL;
00183 e->data.symbol = s;
00184 }
00185
00186 REG::REG(const IntArgs& x) {
00187 int n = x.size();
00188 if (n < 1)
00189 throw MiniModel::TooFewArguments("REG");
00190 Exp** a = heap.alloc<Exp*>(n);
00191
00192 for (int i=n; i--; ) {
00193 a[i] = new Exp();
00194 a[i]->use_cnt = 1;
00195 a[i]->_n_pos = 1;
00196 a[i]->type = REG::Exp::ET_SYMBOL;
00197 a[i]->data.symbol = x[i];
00198 }
00199
00200 for (int m=n; m>1; ) {
00201 if (m & 1) {
00202 m -= 1;
00203 Exp* e1 = a[m];
00204 Exp* e2 = a[0];
00205 a[0] = new Exp;
00206 a[0]->use_cnt = 1;
00207 a[0]->_n_pos = e1->n_pos() + e2->n_pos();
00208 a[0]->type = REG::Exp::ET_OR;
00209 a[0]->data.kids[0] = e1;
00210 a[0]->data.kids[1] = e2;
00211 } else {
00212 m >>= 1;
00213 for (int i=0; i<m; i++) {
00214 Exp* e1 = a[2*i];
00215 Exp* e2 = a[2*i+1];
00216 a[i] = new Exp;
00217 a[i]->use_cnt = 1;
00218 a[i]->_n_pos = e1->n_pos() + e2->n_pos();
00219 a[i]->type = REG::Exp::ET_OR;
00220 a[i]->data.kids[0] = e1;
00221 a[i]->data.kids[1] = e2;
00222 }
00223 }
00224 }
00225 e = a[0];
00226 heap.free<Exp*>(a,n);
00227 }
00228
00229 REG
00230 REG::operator |(const REG& r2) {
00231 if (e == r2.e)
00232 return *this;
00233 Exp* f = new Exp();
00234 f->use_cnt = 1;
00235 f->_n_pos = e->n_pos() + r2.e->n_pos();
00236 f->type = REG::Exp::ET_OR;
00237 f->data.kids[0] = e; e->inc();
00238 f->data.kids[1] = r2.e; r2.e->inc();
00239 REG r(f);
00240 return r;
00241 }
00242
00243 REG&
00244 REG::operator |=(const REG& r2) {
00245 if (e == r2.e)
00246 return *this;
00247 Exp* f = new Exp();
00248 f->use_cnt = 1;
00249 f->_n_pos = e->n_pos() + r2.e->n_pos();
00250 f->type = REG::Exp::ET_OR;
00251 f->data.kids[0] = e;
00252 f->data.kids[1] = r2.e; r2.e->inc();
00253 e=f;
00254 return *this;
00255 }
00256
00257 REG
00258 REG::operator +(const REG& r2) {
00259 if (e == NULL) return r2;
00260 if (r2.e == NULL) return *this;
00261 Exp* f = new Exp();
00262 f->use_cnt = 1;
00263 f->_n_pos = e->n_pos() + r2.e->n_pos();
00264 f->type = REG::Exp::ET_CONC;
00265 f->data.kids[0] = e; e->inc();
00266 f->data.kids[1] = r2.e; r2.e->inc();
00267 REG r(f);
00268 return r;
00269 }
00270
00271 REG&
00272 REG::operator +=(const REG& r2) {
00273 if (r2.e == NULL)
00274 return *this;
00275 if (e == NULL) {
00276 e=r2.e; e->inc();
00277 } else {
00278 Exp* f = new Exp();
00279 f->use_cnt = 1;
00280 f->_n_pos = e->n_pos() + r2.e->n_pos();
00281 f->type = REG::Exp::ET_CONC;
00282 f->data.kids[0] = e;
00283 f->data.kids[1] = r2.e; r2.e->inc();
00284 e=f;
00285 }
00286 return *this;
00287 }
00288
00289 REG
00290 REG::operator *(void) {
00291 if ((e == NULL) || (e->type == REG::Exp::ET_STAR))
00292 return *this;
00293 Exp* f = new Exp();
00294 f->use_cnt = 1;
00295 f->_n_pos = e->n_pos();
00296 f->type = REG::Exp::ET_STAR;
00297 f->data.kids[0] = e; e->inc();
00298 REG r(f);
00299 return r;
00300 }
00301
00302 REG
00303 REG::operator ()(unsigned int n, unsigned int m) {
00304 REG r;
00305 if ((n>m) || (m == 0))
00306 return r;
00307 if (n>0) {
00308 unsigned int i = n;
00309 REG r0 = *this;
00310 while (i>0)
00311 if (i & 1) {
00312 r = r0+r; i--;
00313 } else {
00314 r0 = r0+r0; i >>= 1;
00315 }
00316 }
00317 if (m > n) {
00318 unsigned int i = m-n;
00319 REG s0;
00320 s0 = s0 | *this;
00321 REG s;
00322 while (i>0)
00323 if (i & 1) {
00324 s = s0+s; i--;
00325 } else {
00326 s0 = s0+s0; i >>= 1;
00327 }
00328 r = r + s;
00329 }
00330 return r;
00331 }
00332
00333 REG
00334 REG::operator ()(unsigned int n) {
00335 REG r;
00336 if (n > 0) {
00337 REG r0 = *this;
00338 unsigned int i = n;
00339 while (i>0)
00340 if (i & 1) {
00341 r = r0+r; i--;
00342 } else {
00343 r0 = r0+r0; i >>= 1;
00344 }
00345 }
00346 return r+**this;
00347 }
00348
00349 REG
00350 REG::operator +(void) {
00351 return this->operator ()(1);
00352 }
00353
00354
00355 namespace MiniModel {
00356
00357
00358
00359
00360
00361
00365 enum PosSetCmp {
00366 PSC_LE,
00367 PSC_EQ,
00368 PSC_GR
00369 };
00370
00374 class PosSet : public Support::BlockClient<PosSet,Heap> {
00375
00376
00377
00378 public:
00379 int pos; PosSet* next;
00380
00381 PosSet(void);
00382 PosSet(int);
00383
00384 bool in(int) const;
00385 static PosSetCmp cmp(PosSet*,PosSet*);
00386 static PosSet* cup(PosSetAllocator&,PosSet*,PosSet*);
00387 };
00388
00389
00390 forceinline
00391 PosSet::PosSet(void) {}
00392 forceinline
00393 PosSet::PosSet(int p) : pos(p), next(NULL) {}
00394
00395
00396 forceinline bool
00397 PosSet::in(int p) const {
00398 for (const PosSet* ps = this; ps != NULL; ps = ps->next)
00399 if (ps->pos == p) {
00400 return true;
00401 } else if (ps->pos < p) {
00402 return false;
00403 }
00404 return false;
00405 }
00406
00407 forceinline PosSetCmp
00408 PosSet::cmp(PosSet* ps1, PosSet* ps2) {
00409 while ((ps1 != NULL) && (ps2 != NULL)) {
00410 if (ps1 == ps2)
00411 return PSC_EQ;
00412 if (ps1->pos < ps2->pos)
00413 return PSC_LE;
00414 if (ps1->pos > ps2->pos)
00415 return PSC_GR;
00416 ps1 = ps1->next; ps2 = ps2->next;
00417 }
00418 if (ps1 == ps2)
00419 return PSC_EQ;
00420 return ps1 == NULL ? PSC_LE : PSC_GR;
00421 }
00422
00423 PosSet*
00424 PosSet::cup(PosSetAllocator& psm, PosSet* ps1, PosSet* ps2) {
00425 PosSet* ps;
00426 PosSet** p = &ps;
00427 while ((ps1 != NULL) && (ps2 != NULL)) {
00428 if (ps1 == ps2) {
00429 *p = ps1; return ps;
00430 }
00431 PosSet* n = new (psm) PosSet;
00432 *p = n; p = &n->next;
00433 if (ps1->pos == ps2->pos) {
00434 n->pos = ps1->pos;
00435 ps1 = ps1->next; ps2 = ps2->next;
00436 } else if (ps1->pos > ps2->pos) {
00437 n->pos = ps1->pos; ps1 = ps1->next;
00438 } else {
00439 n->pos = ps2->pos; ps2 = ps2->next;
00440 }
00441 }
00442 *p = (ps1 != NULL) ? ps1 : ps2;
00443 return ps;
00444 }
00445
00446
00448 class NodeInfo {
00449 public:
00450 bool nullable;
00451 PosSet* firstpos;
00452 PosSet* lastpos;
00453 NodeInfo(bool n=false, PosSet* fp=NULL, PosSet* lp=NULL);
00454 };
00455
00457 class ExpInfo {
00458 public:
00459 REG::Exp* exp;
00460 bool open;
00461 ExpInfo(REG::Exp* e=NULL);
00462 };
00463
00468 class PosInfo {
00469 public:
00470 int symbol;
00471 PosSet* followpos;
00472 };
00473
00474 forceinline
00475 NodeInfo::NodeInfo(bool n, PosSet* fp, PosSet* lp)
00476 : nullable(n), firstpos(fp), lastpos(lp) {}
00477
00478 forceinline
00479 ExpInfo::ExpInfo(REG::Exp* e)
00480 : exp(e), open(true) {}
00481
00482 }
00483
00484 forceinline MiniModel::PosSet*
00485 REG::Exp::followpos(MiniModel::PosSetAllocator& psm,
00486 MiniModel::PosInfo* pi) {
00487 int p=0;
00488
00489 using MiniModel::PosSet;
00490 using MiniModel::NodeInfo;
00491 using MiniModel::ExpInfo;
00492
00493 Support::DynamicStack<ExpInfo,Heap> todo(heap);
00494 Support::DynamicStack<NodeInfo,Heap> done(heap);
00495
00496
00497 todo.push(ExpInfo(this));
00498
00499 do {
00500 if (todo.top().exp == NULL) {
00501 todo.pop();
00502 done.push(NodeInfo(true,NULL,NULL));
00503 } else {
00504 switch (todo.top().exp->type) {
00505 case ET_SYMBOL:
00506 {
00507 pi[p].symbol = todo.pop().exp->data.symbol;
00508 PosSet* ps = new (psm) PosSet(p++);
00509 done.push(NodeInfo(false,ps,ps));
00510 }
00511 break;
00512 case ET_STAR:
00513 if (todo.top().open) {
00514
00515 todo.top().open = false;
00516 todo.push(todo.top().exp->data.kids[0]);
00517 } else {
00518 todo.pop();
00519 NodeInfo ni = done.pop();
00520 for (PosSet* ps = ni.lastpos; ps != NULL; ps = ps->next)
00521 pi[ps->pos].followpos =
00522 PosSet::cup(psm,pi[ps->pos].followpos,ni.firstpos);
00523 done.push(NodeInfo(true,ni.firstpos,ni.lastpos));
00524 }
00525 break;
00526 case ET_CONC:
00527 if (todo.top().open) {
00528
00529 todo.top().open = false;
00530 REG::Exp* e = todo.top().exp;
00531 todo.push(e->data.kids[1]);
00532 todo.push(e->data.kids[0]);
00533 } else {
00534 todo.pop();
00535 NodeInfo ni1 = done.pop();
00536 NodeInfo ni0 = done.pop();
00537 for (PosSet* ps = ni0.lastpos; ps != NULL; ps = ps->next)
00538 pi[ps->pos].followpos =
00539 PosSet::cup(psm,pi[ps->pos].followpos,ni1.firstpos);
00540 done.push(NodeInfo(ni0.nullable & ni1.nullable,
00541 ni0.nullable ?
00542 PosSet::cup(psm,ni0.firstpos,ni1.firstpos) : ni0.firstpos,
00543 ni1.nullable ?
00544 PosSet::cup(psm,ni0.lastpos,ni1.lastpos) : ni1.lastpos));
00545 }
00546 break;
00547 case ET_OR:
00548 if (todo.top().open) {
00549
00550 todo.top().open = false;
00551 REG::Exp* e = todo.top().exp;
00552 todo.push(e->data.kids[1]);
00553 todo.push(e->data.kids[0]);
00554 } else {
00555 todo.pop();
00556 NodeInfo ni1 = done.pop();
00557 NodeInfo ni0 = done.pop();
00558 done.push(NodeInfo(ni0.nullable | ni1.nullable,
00559 PosSet::cup(psm,ni0.firstpos,ni1.firstpos),
00560 PosSet::cup(psm,ni0.lastpos,ni1.lastpos)));
00561 }
00562 break;
00563 default: GECODE_NEVER;
00564 }
00565 }
00566 } while (!todo.empty());
00567 return done.top().firstpos;
00568 }
00569
00570
00571 namespace MiniModel {
00572
00573 class StateNode;
00574
00578 typedef Support::BlockAllocator<StateNode,Heap> StatePoolAllocator;
00579
00583 class StateNode : public Support::BlockClient<StateNode,Heap> {
00584 public:
00585 PosSet* pos;
00586 int state;
00587 StateNode* next;
00588 StateNode* left;
00589 StateNode* right;
00590 };
00591
00595 class StatePool {
00596 public:
00597 int n_states;
00598 StateNode root;
00599 StateNode* next;
00600 StateNode* all;
00601
00602 StatePool(PosSet*);
00603
00604 StateNode* pop(void);
00605 bool empty(void) const;
00606
00607 int state(StatePoolAllocator&, PosSet*);
00608 };
00609
00610 forceinline
00611 StatePool::StatePool(PosSet* ps) {
00612 next = &root;
00613 all = NULL;
00614 n_states = 1;
00615 root.pos = ps;
00616 root.state = 0;
00617 root.next = NULL;
00618 root.left = NULL;
00619 root.right = NULL;
00620 }
00621
00622 forceinline StateNode*
00623 StatePool::pop(void) {
00624 StateNode* n = next;
00625 next = n->next;
00626 n->next = all;
00627 all = n;
00628 return n;
00629 }
00630
00631 forceinline bool
00632 StatePool::empty(void) const {
00633 return next == NULL;
00634 }
00635
00636 forceinline int
00637 StatePool::state(StatePoolAllocator& spm, PosSet* ps) {
00638 int d = 0;
00639 StateNode** p = NULL;
00640 StateNode* n = &root;
00641 do {
00642 switch (PosSet::cmp(ps,n->pos)) {
00643 case PSC_EQ: return n->state;
00644 case PSC_LE: p = &n->left; n = *p; break;
00645 case PSC_GR: p = &n->right; n = *p; break;
00646 default: GECODE_NEVER;
00647 }
00648 d++;
00649 } while (n != NULL);
00650 n = new (spm) StateNode; *p = n;
00651 n->pos = ps;
00652 n->state = n_states++;
00653 n->next = next;
00654 n->left = NULL;
00655 n->right = NULL;
00656 next = n;
00657 return n->state;
00658 }
00659
00663 class SymbolsInc {
00664 public:
00665 forceinline bool
00666 operator ()(int x, int y) {
00667 return x < y;
00668 }
00669 forceinline static void
00670 sort(int s[], int n) {
00671 SymbolsInc o;
00672 Support::quicksort<int,SymbolsInc>(s,n,o);
00673 }
00674 };
00675
00676
00681 class TransitionBag {
00682 private:
00683 Support::DynamicArray<DFA::Transition,Heap> t;
00684 int n;
00685 public:
00686 TransitionBag(void);
00687 void add(int,int,int);
00688 void finish(void);
00689 DFA::Transition* transitions(void);
00690 };
00691
00692 forceinline
00693 TransitionBag::TransitionBag(void) : t(heap), n(0) {}
00694
00695 forceinline void
00696 TransitionBag::add(int i_state, int symbol, int o_state) {
00697 t[n].i_state = i_state;
00698 t[n].symbol = symbol;
00699 t[n].o_state = o_state;
00700 n++;
00701 }
00702
00703 forceinline void
00704 TransitionBag::finish(void) {
00705 t[n].i_state = -1;
00706 }
00707
00708 forceinline DFA::Transition*
00709 TransitionBag::transitions(void) {
00710 return &t[0];
00711 }
00712
00713
00718 class FinalBag {
00719 private:
00720 Support::DynamicArray<int,Heap> f;
00721 int n;
00722 public:
00723 FinalBag(void);
00724 void add(int);
00725 void finish(void);
00726 int* finals(void);
00727 };
00728
00729 forceinline
00730 FinalBag::FinalBag(void) : f(heap), n(0) {}
00731
00732 forceinline void
00733 FinalBag::add(int state) {
00734 f[n++] = state;
00735 }
00736
00737 forceinline void
00738 FinalBag::finish(void) {
00739 f[n] = -1;
00740 }
00741
00742 forceinline int*
00743 FinalBag::finals(void) {
00744 return &f[0];
00745 }
00746
00747 }
00748
00749 REG::operator DFA(void) {
00750 using MiniModel::PosSetAllocator;
00751 using MiniModel::StatePoolAllocator;
00752 using MiniModel::PosInfo;
00753 using MiniModel::PosSet;
00754 using MiniModel::NodeInfo;
00755
00756 using MiniModel::StatePool;
00757 using MiniModel::StateNode;
00758
00759 using MiniModel::TransitionBag;
00760 using MiniModel::FinalBag;
00761
00762 using MiniModel::SymbolsInc;
00763
00764 PosSetAllocator psm(heap);
00765 StatePoolAllocator spm(heap);
00766 REG r = *this + REG(Int::Limits::max+1);
00767 int n_pos = r.e->n_pos();
00768
00769 PosInfo* pi = heap.alloc<PosInfo>(n_pos);
00770 for (int i=n_pos; i--; )
00771 pi[i].followpos = NULL;
00772
00773 PosSet* firstpos = r.e->followpos(psm,&pi[0]);
00774
00775
00776 int* symbols = heap.alloc<int>(n_pos);
00777 for (int i=n_pos; i--; )
00778 symbols[i] = pi[i].symbol;
00779
00780 SymbolsInc::sort(&symbols[0],n_pos-1);
00781 int n_symbols = 1;
00782 for (int i = 1; i<n_pos-1; i++)
00783 if (symbols[i-1] != symbols[i])
00784 symbols[n_symbols++] = symbols[i];
00785
00786
00787 TransitionBag tb;
00788 StatePool sp(firstpos);
00789 while (!sp.empty()) {
00790 StateNode* sn = sp.pop();
00791 for (int i = n_symbols; i--; ) {
00792 PosSet* u = NULL;
00793 for (PosSet* ps = sn->pos; ps != NULL; ps = ps->next)
00794 if (pi[ps->pos].symbol == symbols[i])
00795 u = PosSet::cup(psm,u,pi[ps->pos].followpos);
00796 if (u != NULL)
00797 tb.add(sn->state,symbols[i],sp.state(spm,u));
00798 }
00799 }
00800 tb.finish();
00801
00802
00803 FinalBag fb;
00804 for (StateNode* n = sp.all; n != NULL; n = n->next)
00805 if (n->pos->in(n_pos-1))
00806 fb.add(n->state);
00807 fb.finish();
00808
00809 heap.free<PosInfo>(pi,n_pos);
00810 heap.free<int>(symbols,n_pos);
00811 return DFA(0,tb.transitions(),fb.finals(),true);
00812 }
00813
00814 }
00815
00816
00817