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 * Last modified: 00010 * $Date: 2010-07-26 12:53:58 +0200 (Mon, 26 Jul 2010) $ by $Author: schulte $ 00011 * $Revision: 11279 $ 00012 * 00013 * This file is part of Gecode, the generic constraint 00014 * development environment: 00015 * http://www.gecode.org 00016 * 00017 * Permission is hereby granted, free of charge, to any person obtaining 00018 * a copy of this software and associated documentation files (the 00019 * "Software"), to deal in the Software without restriction, including 00020 * without limitation the rights to use, copy, modify, merge, publish, 00021 * distribute, sublicense, and/or sell copies of the Software, and to 00022 * permit persons to whom the Software is furnished to do so, subject to 00023 * the following conditions: 00024 * 00025 * The above copyright notice and this permission notice shall be 00026 * included in all copies or substantial portions of the Software. 00027 * 00028 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, 00029 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF 00030 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND 00031 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE 00032 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION 00033 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION 00034 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. 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 * Operations on expression nodes 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 // Deallocation happens in dispose 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 * Regular expressions 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 // Initialize with symbols 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 // Build a balanced tree of alternative nodes 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 * Sets of positions 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 // Maintain sets of positions in inverse order 00376 // This makes the check whether the last position is included 00377 // more efficient. 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 // Start with first expression to be processed 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 // Evaluate subexpression recursively 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 // Evaluate subexpressions recursively 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 // Evaluate subexpressions recursively 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 // Compute symbols 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 // Compute states and transitions 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 // Compute final states 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 // STATISTICS: minimodel-any 00817