00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
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
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
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
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
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
00321
00322
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
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
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
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
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
00735