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