this repo has no description
dekker.one
1/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2/*
3 * Main authors:
4 * Christian Schulte <schulte@gecode.org>
5 *
6 * Copyright:
7 * Christian Schulte, 2004
8 *
9 * This file is part of Gecode, the generic constraint
10 * development environment:
11 * http://www.gecode.org
12 *
13 * Permission is hereby granted, free of charge, to any person obtaining
14 * a copy of this software and associated documentation files (the
15 * "Software"), to deal in the Software without restriction, including
16 * without limitation the rights to use, copy, modify, merge, publish,
17 * distribute, sublicense, and/or sell copies of the Software, and to
18 * permit persons to whom the Software is furnished to do so, subject to
19 * the following conditions:
20 *
21 * The above copyright notice and this permission notice shall be
22 * included in all copies or substantial portions of the Software.
23 *
24 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
25 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
26 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
27 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
28 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
29 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
30 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
31 *
32 */
33
34#include <gecode/minimodel.hh>
35
36namespace Gecode {
37
38 namespace MiniModel {
39
40 class PosSet;
41 /**
42 * \brief Allocator for position sets
43 */
44 typedef Support::BlockAllocator<PosSet,Region> PosSetAllocator;
45
46 class NodeInfo;
47 class PosInfo;
48
49 }
50
51 /// Implementation of the actual expression tree
52 class REG::Exp {
53 public:
54 /// Reference counter
55 unsigned int use_cnt;
56 /// Number of positions
57 int _n_pos;
58 /**
59 * \brief Type of regular expression
60 */
61 enum ExpType {
62 ET_SYMBOL,
63 ET_CONC,
64 ET_OR,
65 ET_STAR
66 };
67 /// Type of regular expression
68 ExpType type;
69 /// Symbol or subexpressions
70 union {
71 /// Symbol
72 int symbol;
73 /// Subexpressions
74 Exp* kids[2];
75 } data;
76
77 /// Compute the follow positions
78 MiniModel::PosSet*
79 followpos(MiniModel::PosSetAllocator&,MiniModel::PosInfo*);
80 /// Increment use counter of \a e
81 static void inc(Exp* e);
82 /// Decrement use counter of \a e
83 static void dec(Exp* e);
84 /// Return number of positions of \a e
85 static int n_pos(Exp* e);
86 /// Print expression to \a os
87 void toString(std::ostringstream& os) const;
88 /// Print expression
89 std::string toString(void) const;
90
91 static void* operator new(size_t);
92 static void operator delete(void*);
93 private:
94 /// Deallocate memory
95 void dispose(void);
96 };
97
98
99 /*
100 * Operations on expression nodes
101 *
102 */
103
104
105 forceinline void*
106 REG::Exp::operator new(size_t s) {
107 return heap.ralloc(s);
108 }
109 forceinline void
110 REG::Exp::operator delete(void*) {
111 // Deallocation happens in dispose
112 }
113
114 void
115 REG::Exp::dispose(void) {
116 Region region;
117 Support::DynamicStack<Exp*,Region> todo(region);
118 todo.push(this);
119 while (!todo.empty()) {
120 Exp* e = todo.pop();
121 switch (e->type) {
122 case ET_OR:
123 case ET_CONC:
124 if ((e->data.kids[1] != nullptr) && (--e->data.kids[1]->use_cnt == 0))
125 todo.push(e->data.kids[1]);
126 // fall through
127 case ET_STAR:
128 if ((e->data.kids[0] != nullptr) && (--e->data.kids[0]->use_cnt == 0))
129 todo.push(e->data.kids[0]);
130 default: ;
131 }
132 heap.rfree(e);
133 }
134 }
135
136 forceinline void
137 REG::Exp::inc(Exp* e) {
138 if (e != nullptr)
139 e->use_cnt++;
140 }
141 forceinline void
142 REG::Exp::dec(Exp* e) {
143 if ((e != nullptr) && (--e->use_cnt == 0))
144 e->dispose();
145 }
146
147
148 forceinline int
149 REG::Exp::n_pos(Exp* e) {
150 return (e != nullptr) ? e->_n_pos : 0;
151 }
152
153 void
154 REG::Exp::toString(std::ostringstream& os) const {
155 switch (type) {
156 case ET_SYMBOL:
157 os << "[" << data.symbol << "]";
158 return;
159 case ET_STAR:
160 {
161 bool par = ((data.kids[0] != nullptr) &&
162 ((data.kids[0]->type == ET_CONC) ||
163 (data.kids[0]->type == ET_OR)));
164 os << (par ? "*(" : "*");
165 if (data.kids[0]==nullptr) {
166 os << "[]";
167 } else {
168 data.kids[0]->toString(os);
169 }
170 os << (par ? ")" : "");
171 return;
172 }
173 case ET_CONC:
174 {
175 bool par0 = ((data.kids[0] != nullptr) &&
176 (data.kids[0]->type == ET_OR));
177 os << (par0 ? "(" : "");
178 if (data.kids[0]==nullptr) {
179 os << "[]";
180 } else {
181 data.kids[0]->toString(os);
182 }
183 os << (par0 ? ")+" : "+");
184 bool par1 = ((data.kids[1] != nullptr) &&
185 (data.kids[1]->type == ET_OR));
186 os << (par1 ? "(" : "");
187 if (data.kids[1]==nullptr) {
188 os << "[]";
189 } else {
190 data.kids[1]->toString(os);
191 }
192 os << (par1 ? ")" : "");
193 return;
194 }
195 case ET_OR:
196 if (data.kids[0]==nullptr) {
197 os << "[]";
198 } else {
199 data.kids[0]->toString(os);
200 }
201 os << "|";
202 if (data.kids[1]==nullptr) {
203 os << "[]";
204 } else {
205 data.kids[1]->toString(os);
206 }
207 return;
208 default: GECODE_NEVER;
209 }
210 GECODE_NEVER;
211 return;
212 }
213
214 std::string
215 REG::Exp::toString(void) const {
216 std::ostringstream os;
217 toString(os);
218 return os.str();
219 }
220
221
222 /*
223 * Regular expressions
224 *
225 */
226
227 forceinline
228 REG::REG(Exp* f) : e(f) {}
229
230 REG::REG(void) : e(nullptr) {}
231
232 REG::REG(const REG& r) : e(r.e) {
233 REG::Exp::inc(e);
234 }
235
236 const REG&
237 REG::operator =(const REG& r) {
238 if (&r != this) {
239 REG::Exp::inc(r.e);
240 REG::Exp::dec(e);
241 e = r.e;
242 }
243 return *this;
244 }
245
246 REG::~REG(void) {
247 REG::Exp::dec(e);
248 }
249
250 REG::REG(int s) : e(new Exp) {
251 e->use_cnt = 1;
252 e->_n_pos = 1;
253 e->type = REG::Exp::ET_SYMBOL;
254 e->data.symbol = s;
255 }
256
257 REG::REG(const IntArgs& x) {
258 int n = x.size();
259 if (n < 1)
260 throw MiniModel::TooFewArguments("REG");
261 Region region;
262 Exp** a = region.alloc<Exp*>(n);
263 // Initialize with symbols
264 for (int i=n; i--; ) {
265 a[i] = new Exp();
266 a[i]->use_cnt = 1;
267 a[i]->_n_pos = 1;
268 a[i]->type = REG::Exp::ET_SYMBOL;
269 a[i]->data.symbol = x[i];
270 }
271 // Build a balanced tree of alternative nodes
272 for (int m=n; m>1; ) {
273 if (m & 1) {
274 m -= 1;
275 Exp* e1 = a[m];
276 Exp* e2 = a[0];
277 a[0] = new Exp;
278 a[0]->use_cnt = 1;
279 a[0]->_n_pos = REG::Exp::n_pos(e1) + REG::Exp::n_pos(e2);
280 a[0]->type = REG::Exp::ET_OR;
281 a[0]->data.kids[0] = e1;
282 a[0]->data.kids[1] = e2;
283 } else {
284 m >>= 1;
285 for (int i=0; i<m; i++) {
286 Exp* e1 = a[2*i];
287 Exp* e2 = a[2*i+1];
288 a[i] = new Exp;
289 a[i]->use_cnt = 1;
290 a[i]->_n_pos = REG::Exp::n_pos(e1) + REG::Exp::n_pos(e2);
291 a[i]->type = REG::Exp::ET_OR;
292 a[i]->data.kids[0] = e1;
293 a[i]->data.kids[1] = e2;
294 }
295 }
296 }
297 e = a[0];
298 }
299
300 REG
301 REG::operator |(const REG& r2) {
302 if (e == r2.e)
303 return *this;
304 Exp* f = new Exp();
305 f->use_cnt = 1;
306 f->_n_pos = REG::Exp::n_pos(e) + REG::Exp::n_pos(r2.e);
307 f->type = REG::Exp::ET_OR;
308 f->data.kids[0] = e; REG::Exp::inc(e);
309 f->data.kids[1] = r2.e; REG::Exp::inc(r2.e);
310 REG r(f);
311 return r;
312 }
313
314 REG&
315 REG::operator |=(const REG& r2) {
316 if (e == r2.e)
317 return *this;
318 Exp* f = new Exp();
319 f->use_cnt = 1;
320 f->_n_pos = REG::Exp::n_pos(e) + REG::Exp::n_pos(r2.e);
321 f->type = REG::Exp::ET_OR;
322 f->data.kids[0] = e;
323 f->data.kids[1] = r2.e; REG::Exp::inc(r2.e);
324 e=f;
325 return *this;
326 }
327
328 REG
329 REG::operator +(const REG& r2) {
330 if (e == nullptr) return r2;
331 if (r2.e == nullptr) return *this;
332 Exp* f = new Exp();
333 f->use_cnt = 1;
334 f->_n_pos = REG::Exp::n_pos(e) + REG::Exp::n_pos(r2.e);
335 f->type = REG::Exp::ET_CONC;
336 f->data.kids[0] = e; REG::Exp::inc(e);
337 f->data.kids[1] = r2.e; REG::Exp::inc(r2.e);
338 REG r(f);
339 return r;
340 }
341
342 REG&
343 REG::operator +=(const REG& r2) {
344 if (r2.e == nullptr)
345 return *this;
346 if (e == nullptr) {
347 e=r2.e; REG::Exp::inc(e);
348 } else {
349 Exp* f = new Exp();
350 f->use_cnt = 1;
351 f->_n_pos = REG::Exp::n_pos(e) + REG::Exp::n_pos(r2.e);
352 f->type = REG::Exp::ET_CONC;
353 f->data.kids[0] = e;
354 f->data.kids[1] = r2.e; REG::Exp::inc(r2.e);
355 e=f;
356 }
357 return *this;
358 }
359
360 REG
361 REG::operator *(void) {
362 if ((e == nullptr) || (e->type == REG::Exp::ET_STAR))
363 return *this;
364 Exp* f = new Exp();
365 f->use_cnt = 1;
366 f->_n_pos = REG::Exp::n_pos(e);
367 f->type = REG::Exp::ET_STAR;
368 f->data.kids[0] = e; REG::Exp::inc(e);
369 REG r(f);
370 return r;
371 }
372
373 REG
374 REG::operator ()(unsigned int n, unsigned int m) {
375 REG r;
376 if ((n>m) || (m == 0))
377 return r;
378 if (n>0) {
379 unsigned int i = n;
380 REG r0 = *this;
381 while (i>0)
382 if (i & 1) {
383 r = r0+r; i--;
384 } else {
385 r0 = r0+r0; i >>= 1;
386 }
387 }
388 if (m > n) {
389 unsigned int i = m-n;
390 REG s0;
391 s0 = s0 | *this;
392 REG s;
393 while (i>0)
394 if (i & 1) {
395 s = s0+s; i--;
396 } else {
397 s0 = s0+s0; i >>= 1;
398 }
399 r = r + s;
400 }
401 return r;
402 }
403
404 REG
405 REG::operator ()(unsigned int n) {
406 REG r;
407 if (n > 0) {
408 REG r0 = *this;
409 unsigned int i = n;
410 while (i>0)
411 if (i & 1) {
412 r = r0+r; i--;
413 } else {
414 r0 = r0+r0; i >>= 1;
415 }
416 }
417 return r+**this;
418 }
419
420 REG
421 REG::operator +(void) {
422 return this->operator ()(1);
423 }
424
425 std::string
426 REG::toString(void) const {
427 if (e==nullptr) {
428 return "[]";
429 }
430 return e->toString();
431 }
432
433 namespace MiniModel {
434
435 /*
436 * Sets of positions
437 *
438 */
439
440 /**
441 * \brief Order on position sets
442 */
443 enum PosSetCmp {
444 PSC_LE,
445 PSC_EQ,
446 PSC_GR
447 };
448
449 /**
450 * \brief Sets of positions
451 */
452 class PosSet : public Support::BlockClient<PosSet,Region> {
453 // Maintain sets of positions in inverse order
454 // This makes the check whether the last position is included
455 // more efficient.
456 public:
457 int pos; PosSet* next;
458
459 PosSet(void);
460 PosSet(int);
461
462 bool in(int) const;
463 static PosSetCmp cmp(PosSet*,PosSet*);
464 static PosSet* cup(PosSetAllocator&,PosSet*,PosSet*);
465 };
466
467
468 forceinline
469 PosSet::PosSet(void) {}
470 forceinline
471 PosSet::PosSet(int p) : pos(p), next(nullptr) {}
472
473
474 forceinline bool
475 PosSet::in(int p) const {
476 for (const PosSet* ps = this; ps != nullptr; ps = ps->next)
477 if (ps->pos == p) {
478 return true;
479 } else if (ps->pos < p) {
480 return false;
481 }
482 return false;
483 }
484
485 forceinline PosSetCmp
486 PosSet::cmp(PosSet* ps1, PosSet* ps2) {
487 while ((ps1 != nullptr) && (ps2 != nullptr)) {
488 if (ps1 == ps2)
489 return PSC_EQ;
490 if (ps1->pos < ps2->pos)
491 return PSC_LE;
492 if (ps1->pos > ps2->pos)
493 return PSC_GR;
494 ps1 = ps1->next; ps2 = ps2->next;
495 }
496 if (ps1 == ps2)
497 return PSC_EQ;
498 return ps1 == nullptr ? PSC_LE : PSC_GR;
499 }
500
501 PosSet*
502 PosSet::cup(PosSetAllocator& psm, PosSet* ps1, PosSet* ps2) {
503 PosSet* ps;
504 PosSet** p = &ps;
505 while ((ps1 != nullptr) && (ps2 != nullptr)) {
506 if (ps1 == ps2) {
507 *p = ps1; return ps;
508 }
509 PosSet* n = new (psm) PosSet;
510 *p = n; p = &n->next;
511 if (ps1->pos == ps2->pos) {
512 n->pos = ps1->pos;
513 ps1 = ps1->next; ps2 = ps2->next;
514 } else if (ps1->pos > ps2->pos) {
515 n->pos = ps1->pos; ps1 = ps1->next;
516 } else {
517 n->pos = ps2->pos; ps2 = ps2->next;
518 }
519 }
520 *p = (ps1 != nullptr) ? ps1 : ps2;
521 return ps;
522 }
523
524
525 /// Node information computed during traversal of the expressions
526 class NodeInfo {
527 public:
528 bool nullable;
529 PosSet* firstpos;
530 PosSet* lastpos;
531 NodeInfo(bool n=false, PosSet* fp=nullptr, PosSet* lp=nullptr);
532 };
533
534 /// Expression information
535 class ExpInfo {
536 public:
537 REG::Exp* exp;
538 bool open;
539 ExpInfo(REG::Exp* e=nullptr);
540 };
541
542 /**
543 * \brief Information on positions collected during traversal
544 *
545 */
546 class PosInfo {
547 public:
548 int symbol;
549 PosSet* followpos;
550 };
551
552 forceinline
553 NodeInfo::NodeInfo(bool n, PosSet* fp, PosSet* lp)
554 : nullable(n), firstpos(fp), lastpos(lp) {}
555
556 forceinline
557 ExpInfo::ExpInfo(REG::Exp* e)
558 : exp(e), open(true) {}
559
560 }
561
562 forceinline MiniModel::PosSet*
563 REG::Exp::followpos(MiniModel::PosSetAllocator& psm,
564 MiniModel::PosInfo* pi) {
565 int p=0;
566
567 using MiniModel::PosSet;
568 using MiniModel::NodeInfo;
569 using MiniModel::ExpInfo;
570
571 Region region;
572
573 Support::DynamicStack<ExpInfo,Region> todo(region);
574 Support::DynamicStack<NodeInfo,Region> done(region);
575
576 // Start with first expression to be processed
577 todo.push(ExpInfo(this));
578
579 do {
580 if (todo.top().exp == nullptr) {
581 todo.pop();
582 done.push(NodeInfo(true,nullptr,nullptr));
583 } else {
584 switch (todo.top().exp->type) {
585 case ET_SYMBOL:
586 {
587 pi[p].symbol = todo.pop().exp->data.symbol;
588 PosSet* ps = new (psm) PosSet(p++);
589 done.push(NodeInfo(false,ps,ps));
590 }
591 break;
592 case ET_STAR:
593 if (todo.top().open) {
594 // Evaluate subexpression recursively
595 todo.top().open = false;
596 todo.push(todo.top().exp->data.kids[0]);
597 } else {
598 todo.pop();
599 NodeInfo ni = done.pop();
600 for (PosSet* ps = ni.lastpos; ps != nullptr; ps = ps->next)
601 pi[ps->pos].followpos =
602 PosSet::cup(psm,pi[ps->pos].followpos,ni.firstpos);
603 done.push(NodeInfo(true,ni.firstpos,ni.lastpos));
604 }
605 break;
606 case ET_CONC:
607 if (todo.top().open) {
608 // Evaluate subexpressions recursively
609 todo.top().open = false;
610 REG::Exp* e = todo.top().exp;
611 todo.push(e->data.kids[1]);
612 todo.push(e->data.kids[0]);
613 } else {
614 todo.pop();
615 NodeInfo ni1 = done.pop();
616 NodeInfo ni0 = done.pop();
617 for (PosSet* ps = ni0.lastpos; ps != nullptr; ps = ps->next)
618 pi[ps->pos].followpos =
619 PosSet::cup(psm,pi[ps->pos].followpos,ni1.firstpos);
620 done.push(NodeInfo(ni0.nullable & ni1.nullable,
621 ni0.nullable ?
622 PosSet::cup(psm,ni0.firstpos,ni1.firstpos) : ni0.firstpos,
623 ni1.nullable ?
624 PosSet::cup(psm,ni0.lastpos,ni1.lastpos) : ni1.lastpos));
625 }
626 break;
627 case ET_OR:
628 if (todo.top().open) {
629 // Evaluate subexpressions recursively
630 todo.top().open = false;
631 REG::Exp* e = todo.top().exp;
632 todo.push(e->data.kids[1]);
633 todo.push(e->data.kids[0]);
634 } else {
635 todo.pop();
636 NodeInfo ni1 = done.pop();
637 NodeInfo ni0 = done.pop();
638 done.push(NodeInfo(ni0.nullable | ni1.nullable,
639 PosSet::cup(psm,ni0.firstpos,ni1.firstpos),
640 PosSet::cup(psm,ni0.lastpos,ni1.lastpos)));
641 }
642 break;
643 default: GECODE_NEVER;
644 }
645 }
646 } while (!todo.empty());
647 return done.top().firstpos;
648 }
649
650
651 namespace MiniModel {
652
653 class StateNode;
654
655 /**
656 * \brief Allocator for state nodes
657 */
658 typedef Support::BlockAllocator<StateNode,Heap> StatePoolAllocator;
659
660 /**
661 * \brief %Node together with state information
662 */
663 class StateNode : public Support::BlockClient<StateNode,Heap> {
664 public:
665 PosSet* pos;
666 int state;
667 StateNode* next;
668 StateNode* left;
669 StateNode* right;
670 };
671
672 /**
673 * \brief %State pool combines a tree of states together with yet unprocessed states
674 */
675 class StatePool {
676 public:
677 int n_states;
678 StateNode root;
679 StateNode* next;
680 StateNode* all;
681
682 StatePool(PosSet*);
683
684 StateNode* pop(void);
685 bool empty(void) const;
686
687 int state(StatePoolAllocator&, PosSet*);
688 };
689
690 forceinline
691 StatePool::StatePool(PosSet* ps) {
692 next = &root;
693 all = nullptr;
694 n_states = 1;
695 root.pos = ps;
696 root.state = 0;
697 root.next = nullptr;
698 root.left = nullptr;
699 root.right = nullptr;
700 }
701
702 forceinline StateNode*
703 StatePool::pop(void) {
704 StateNode* n = next;
705 next = n->next;
706 n->next = all;
707 all = n;
708 return n;
709 }
710
711 forceinline bool
712 StatePool::empty(void) const {
713 return next == nullptr;
714 }
715
716 forceinline int
717 StatePool::state(StatePoolAllocator& spm, PosSet* ps) {
718 int d = 0;
719 StateNode** p = nullptr;
720 StateNode* n = &root;
721 do {
722 switch (PosSet::cmp(ps,n->pos)) {
723 case PSC_EQ: return n->state;
724 case PSC_LE: p = &n->left; n = *p; break;
725 case PSC_GR: p = &n->right; n = *p; break;
726 default: GECODE_NEVER;
727 }
728 d++;
729 } while (n != nullptr);
730 n = new (spm) StateNode; *p = n;
731 n->pos = ps;
732 n->state = n_states++;
733 n->next = next;
734 n->left = nullptr;
735 n->right = nullptr;
736 next = n;
737 return n->state;
738 }
739
740 /**
741 * \brief Sort symbols
742 */
743 class SymbolsInc {
744 public:
745 forceinline bool
746 operator ()(int x, int y) {
747 return x < y;
748 }
749 forceinline static void
750 sort(int s[], int n) {
751 SymbolsInc o;
752 Support::quicksort<int,SymbolsInc>(s,n,o);
753 }
754 };
755
756
757 /**
758 * \brief For collecting transitions while constructing a %DFA
759 *
760 */
761 class TransitionBag {
762 private:
763 Support::DynamicArray<DFA::Transition,Heap> t;
764 int n;
765 public:
766 TransitionBag(void);
767 void add(int,int,int);
768 void finish(void);
769 DFA::Transition* transitions(void);
770 };
771
772 forceinline
773 TransitionBag::TransitionBag(void) : t(heap), n(0) {}
774
775 forceinline void
776 TransitionBag::add(int i_state, int symbol, int o_state) {
777 t[n].i_state = i_state;
778 t[n].symbol = symbol;
779 t[n].o_state = o_state;
780 n++;
781 }
782
783 forceinline void
784 TransitionBag::finish(void) {
785 t[n].i_state = -1;
786 }
787
788 forceinline DFA::Transition*
789 TransitionBag::transitions(void) {
790 return &t[0];
791 }
792
793
794 /**
795 * \brief For collecting final states while constructing a %DFA
796 *
797 */
798 class FinalBag {
799 private:
800 Support::DynamicArray<int,Heap> f;
801 int n;
802 public:
803 FinalBag(void);
804 void add(int);
805 void finish(void);
806 int* finals(void);
807 };
808
809 forceinline
810 FinalBag::FinalBag(void) : f(heap), n(0) {}
811
812 forceinline void
813 FinalBag::add(int state) {
814 f[n++] = state;
815 }
816
817 forceinline void
818 FinalBag::finish(void) {
819 f[n] = -1;
820 }
821
822 forceinline int*
823 FinalBag::finals(void) {
824 return &f[0];
825 }
826
827 }
828
829 REG::operator DFA(void) {
830 using MiniModel::PosSetAllocator;
831 using MiniModel::StatePoolAllocator;
832 using MiniModel::PosInfo;
833 using MiniModel::PosSet;
834 using MiniModel::NodeInfo;
835
836 using MiniModel::StatePool;
837 using MiniModel::StateNode;
838
839 using MiniModel::TransitionBag;
840 using MiniModel::FinalBag;
841
842 using MiniModel::SymbolsInc;
843
844 Region region;
845 PosSetAllocator psm(region);
846 StatePoolAllocator spm(heap);
847 REG r = *this + REG(Int::Limits::max+1);
848 int n_pos = REG::Exp::n_pos(r.e);
849
850 PosInfo* pi = region.alloc<PosInfo>(n_pos);
851 for (int i=n_pos; i--; )
852 pi[i].followpos = nullptr;
853
854 PosSet* firstpos = r.e->followpos(psm,&pi[0]);
855
856 // Compute symbols
857 int* symbols = region.alloc<int>(n_pos);
858 for (int i=n_pos; i--; )
859 symbols[i] = pi[i].symbol;
860
861 SymbolsInc::sort(&symbols[0],n_pos-1);
862 int n_symbols = 1;
863 for (int i = 1; i<n_pos-1; i++)
864 if (symbols[i-1] != symbols[i])
865 symbols[n_symbols++] = symbols[i];
866
867 // Compute states and transitions
868 TransitionBag tb;
869 StatePool sp(firstpos);
870 while (!sp.empty()) {
871 StateNode* sn = sp.pop();
872 for (int i = n_symbols; i--; ) {
873 PosSet* u = nullptr;
874 for (PosSet* ps = sn->pos; ps != nullptr; ps = ps->next)
875 if (pi[ps->pos].symbol == symbols[i])
876 u = PosSet::cup(psm,u,pi[ps->pos].followpos);
877 if (u != nullptr)
878 tb.add(sn->state,symbols[i],sp.state(spm,u));
879 }
880 }
881 tb.finish();
882
883 // Compute final states
884 FinalBag fb;
885 for (StateNode* n = sp.all; n != nullptr; n = n->next)
886 if (n->pos->in(n_pos-1))
887 fb.add(n->state);
888 fb.finish();
889
890 return DFA(0,tb.transitions(),fb.finals(),true);
891 }
892
893}
894
895// STATISTICS: minimodel-any
896