Generated on Tue Feb 11 2025 17:33:26 for Gecode by doxygen 1.12.0
reg.cpp
Go to the documentation of this file.
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;
45
46 class NodeInfo;
47 class PosInfo;
48
49 }
50
52 class REG::Exp {
53 public:
55 unsigned int use_cnt;
57 int _n_pos;
70 union {
72 int symbol;
74 Exp* kids[2];
76
81 static void inc(Exp* e);
83 static void dec(Exp* e);
85 static int n_pos(Exp* e);
87 void toString(std::ostringstream& os) const;
89 std::string toString(void) const;
90
91 static void* operator new(size_t);
92 static void operator delete(void*);
93 private:
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;
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 case ET_STAR:
127 if ((e->data.kids[0] != nullptr) && (--e->data.kids[0]->use_cnt == 0))
128 todo.push(e->data.kids[0]);
129 default: ;
130 }
131 heap.rfree(e);
132 }
133 }
134
135 forceinline void
137 if (e != nullptr)
138 e->use_cnt++;
139 }
140 forceinline void
142 if ((e != nullptr) && (--e->use_cnt == 0))
143 e->dispose();
144 }
145
146
147 forceinline int
149 return (e != nullptr) ? e->_n_pos : 0;
150 }
151
152 void
153 REG::Exp::toString(std::ostringstream& os) const {
154 switch (type) {
155 case ET_SYMBOL:
156 os << "[" << data.symbol << "]";
157 return;
158 case ET_STAR:
159 {
160 bool par = ((data.kids[0] != nullptr) &&
161 ((data.kids[0]->type == ET_CONC) ||
162 (data.kids[0]->type == ET_OR)));
163 os << (par ? "*(" : "*");
164 if (data.kids[0]==nullptr) {
165 os << "[]";
166 } else {
167 data.kids[0]->toString(os);
168 }
169 os << (par ? ")" : "");
170 return;
171 }
172 case ET_CONC:
173 {
174 bool par0 = ((data.kids[0] != nullptr) &&
175 (data.kids[0]->type == ET_OR));
176 os << (par0 ? "(" : "");
177 if (data.kids[0]==nullptr) {
178 os << "[]";
179 } else {
180 data.kids[0]->toString(os);
181 }
182 os << (par0 ? ")+" : "+");
183 bool par1 = ((data.kids[1] != nullptr) &&
184 (data.kids[1]->type == ET_OR));
185 os << (par1 ? "(" : "");
186 if (data.kids[1]==nullptr) {
187 os << "[]";
188 } else {
189 data.kids[1]->toString(os);
190 }
191 os << (par1 ? ")" : "");
192 return;
193 }
194 case ET_OR:
195 if (data.kids[0]==nullptr) {
196 os << "[]";
197 } else {
198 data.kids[0]->toString(os);
199 }
200 os << "|";
201 if (data.kids[1]==nullptr) {
202 os << "[]";
203 } else {
204 data.kids[1]->toString(os);
205 }
206 return;
207 default: GECODE_NEVER;
208 }
210 return;
211 }
212
213 std::string
214 REG::Exp::toString(void) const {
215 std::ostringstream os;
216 toString(os);
217 return os.str();
218 }
219
220
221 /*
222 * Regular expressions
223 *
224 */
225
227 REG::REG(Exp* f) : e(f) {}
228
229 REG::REG(void) : e(nullptr) {}
230
231 REG::REG(const REG& r) : e(r.e) {
232 REG::Exp::inc(e);
233 }
234
235 const REG&
237 if (&r != this) {
238 REG::Exp::inc(r.e);
239 REG::Exp::dec(e);
240 e = r.e;
241 }
242 return *this;
243 }
244
245 REG::~REG(void) {
246 REG::Exp::dec(e);
247 }
248
249 REG::REG(int s) : e(new Exp) {
250 e->use_cnt = 1;
251 e->_n_pos = 1;
253 e->data.symbol = s;
254 }
255
257 int n = x.size();
258 if (n < 1)
259 throw MiniModel::TooFewArguments("REG");
260 Region region;
261 Exp** a = region.alloc<Exp*>(n);
262 // Initialize with symbols
263 for (int i=n; i--; ) {
264 a[i] = new Exp();
265 a[i]->use_cnt = 1;
266 a[i]->_n_pos = 1;
267 a[i]->type = REG::Exp::ET_SYMBOL;
268 a[i]->data.symbol = x[i];
269 }
270 // Build a balanced tree of alternative nodes
271 for (int m=n; m>1; ) {
272 if (m & 1) {
273 m -= 1;
274 Exp* e1 = a[m];
275 Exp* e2 = a[0];
276 a[0] = new Exp;
277 a[0]->use_cnt = 1;
278 a[0]->_n_pos = REG::Exp::n_pos(e1) + REG::Exp::n_pos(e2);
279 a[0]->type = REG::Exp::ET_OR;
280 a[0]->data.kids[0] = e1;
281 a[0]->data.kids[1] = e2;
282 } else {
283 m >>= 1;
284 for (int i=0; i<m; i++) {
285 Exp* e1 = a[2*i];
286 Exp* e2 = a[2*i+1];
287 a[i] = new Exp;
288 a[i]->use_cnt = 1;
289 a[i]->_n_pos = REG::Exp::n_pos(e1) + REG::Exp::n_pos(e2);
290 a[i]->type = REG::Exp::ET_OR;
291 a[i]->data.kids[0] = e1;
292 a[i]->data.kids[1] = e2;
293 }
294 }
295 }
296 e = a[0];
297 }
298
299 REG
300 REG::operator |(const REG& r2) {
301 if (e == r2.e)
302 return *this;
303 Exp* f = new Exp();
304 f->use_cnt = 1;
305 f->_n_pos = REG::Exp::n_pos(e) + REG::Exp::n_pos(r2.e);
306 f->type = REG::Exp::ET_OR;
307 f->data.kids[0] = e; REG::Exp::inc(e);
308 f->data.kids[1] = r2.e; REG::Exp::inc(r2.e);
309 REG r(f);
310 return r;
311 }
312
313 REG&
315 if (e == r2.e)
316 return *this;
317 Exp* f = new Exp();
318 f->use_cnt = 1;
319 f->_n_pos = REG::Exp::n_pos(e) + REG::Exp::n_pos(r2.e);
320 f->type = REG::Exp::ET_OR;
321 f->data.kids[0] = e;
322 f->data.kids[1] = r2.e; REG::Exp::inc(r2.e);
323 e=f;
324 return *this;
325 }
326
327 REG
328 REG::operator +(const REG& r2) {
329 if (e == nullptr) return r2;
330 if (r2.e == nullptr) return *this;
331 Exp* f = new Exp();
332 f->use_cnt = 1;
333 f->_n_pos = REG::Exp::n_pos(e) + REG::Exp::n_pos(r2.e);
334 f->type = REG::Exp::ET_CONC;
335 f->data.kids[0] = e; REG::Exp::inc(e);
336 f->data.kids[1] = r2.e; REG::Exp::inc(r2.e);
337 REG r(f);
338 return r;
339 }
340
341 REG&
343 if (r2.e == nullptr)
344 return *this;
345 if (e == nullptr) {
346 e=r2.e; REG::Exp::inc(e);
347 } else {
348 Exp* f = new Exp();
349 f->use_cnt = 1;
350 f->_n_pos = REG::Exp::n_pos(e) + REG::Exp::n_pos(r2.e);
351 f->type = REG::Exp::ET_CONC;
352 f->data.kids[0] = e;
353 f->data.kids[1] = r2.e; REG::Exp::inc(r2.e);
354 e=f;
355 }
356 return *this;
357 }
358
359 REG
361 if ((e == nullptr) || (e->type == REG::Exp::ET_STAR))
362 return *this;
363 Exp* f = new Exp();
364 f->use_cnt = 1;
365 f->_n_pos = REG::Exp::n_pos(e);
366 f->type = REG::Exp::ET_STAR;
367 f->data.kids[0] = e; REG::Exp::inc(e);
368 REG r(f);
369 return r;
370 }
371
372 REG
373 REG::operator ()(unsigned int n, unsigned int m) {
374 REG r;
375 if ((n>m) || (m == 0))
376 return r;
377 if (n>0) {
378 unsigned int i = n;
379 REG r0 = *this;
380 while (i>0)
381 if (i & 1) {
382 r = r0+r; i--;
383 } else {
384 r0 = r0+r0; i >>= 1;
385 }
386 }
387 if (m > n) {
388 unsigned int i = m-n;
389 REG s0;
390 s0 = s0 | *this;
391 REG s;
392 while (i>0)
393 if (i & 1) {
394 s = s0+s; i--;
395 } else {
396 s0 = s0+s0; i >>= 1;
397 }
398 r = r + s;
399 }
400 return r;
401 }
402
403 REG
404 REG::operator ()(unsigned int n) {
405 REG r;
406 if (n > 0) {
407 REG r0 = *this;
408 unsigned int i = n;
409 while (i>0)
410 if (i & 1) {
411 r = r0+r; i--;
412 } else {
413 r0 = r0+r0; i >>= 1;
414 }
415 }
416 return r+**this;
417 }
418
419 REG
421 return this->operator ()(1);
422 }
423
424 std::string
425 REG::toString(void) const {
426 if (e==nullptr) {
427 return "[]";
428 }
429 return e->toString();
430 }
431
432 namespace MiniModel {
433
434 /*
435 * Sets of positions
436 *
437 */
438
447
451 class PosSet : public Support::BlockClient<PosSet,Region> {
452 // Maintain sets of positions in inverse order
453 // This makes the check whether the last position is included
454 // more efficient.
455 public:
457
458 PosSet(void);
459 PosSet(int);
460
461 bool in(int) const;
462 static PosSetCmp cmp(PosSet*,PosSet*);
464 };
465
466
470 PosSet::PosSet(int p) : pos(p), next(nullptr) {}
471
472
473 forceinline bool
474 PosSet::in(int p) const {
475 for (const PosSet* ps = this; ps != nullptr; ps = ps->next)
476 if (ps->pos == p) {
477 return true;
478 } else if (ps->pos < p) {
479 return false;
480 }
481 return false;
482 }
483
486 while ((ps1 != nullptr) && (ps2 != nullptr)) {
487 if (ps1 == ps2)
488 return PSC_EQ;
489 if (ps1->pos < ps2->pos)
490 return PSC_LE;
491 if (ps1->pos > ps2->pos)
492 return PSC_GR;
493 ps1 = ps1->next; ps2 = ps2->next;
494 }
495 if (ps1 == ps2)
496 return PSC_EQ;
497 return ps1 == nullptr ? PSC_LE : PSC_GR;
498 }
499
500 PosSet*
502 PosSet* ps;
503 PosSet** p = &ps;
504 while ((ps1 != nullptr) && (ps2 != nullptr)) {
505 if (ps1 == ps2) {
506 *p = ps1; return ps;
507 }
508 PosSet* n = new (psm) PosSet;
509 *p = n; p = &n->next;
510 if (ps1->pos == ps2->pos) {
511 n->pos = ps1->pos;
512 ps1 = ps1->next; ps2 = ps2->next;
513 } else if (ps1->pos > ps2->pos) {
514 n->pos = ps1->pos; ps1 = ps1->next;
515 } else {
516 n->pos = ps2->pos; ps2 = ps2->next;
517 }
518 }
519 *p = (ps1 != nullptr) ? ps1 : ps2;
520 return ps;
521 }
522
523
525 class NodeInfo {
526 public:
530 NodeInfo(bool n=false, PosSet* fp=nullptr, PosSet* lp=nullptr);
531 };
532
534 class ExpInfo {
535 public:
537 bool open;
538 ExpInfo(REG::Exp* e=nullptr);
539 };
540
545 class PosInfo {
546 public:
549 };
550
553 : nullable(n), firstpos(fp), lastpos(lp) {}
554
557 : exp(e), open(true) {}
558
559 }
560
564 int p=0;
565
566 using MiniModel::PosSet;
568 using MiniModel::ExpInfo;
569
570 Region region;
571
574
575 // Start with first expression to be processed
576 todo.push(ExpInfo(this));
577
578 do {
579 if (todo.top().exp == nullptr) {
580 todo.pop();
581 done.push(NodeInfo(true,nullptr,nullptr));
582 } else {
583 switch (todo.top().exp->type) {
584 case ET_SYMBOL:
585 {
586 pi[p].symbol = todo.pop().exp->data.symbol;
587 PosSet* ps = new (psm) PosSet(p++);
588 done.push(NodeInfo(false,ps,ps));
589 }
590 break;
591 case ET_STAR:
592 if (todo.top().open) {
593 // Evaluate subexpression recursively
594 todo.top().open = false;
595 todo.push(todo.top().exp->data.kids[0]);
596 } else {
597 todo.pop();
598 NodeInfo ni = done.pop();
599 for (PosSet* ps = ni.lastpos; ps != nullptr; ps = ps->next)
600 pi[ps->pos].followpos =
601 PosSet::cup(psm,pi[ps->pos].followpos,ni.firstpos);
602 done.push(NodeInfo(true,ni.firstpos,ni.lastpos));
603 }
604 break;
605 case ET_CONC:
606 if (todo.top().open) {
607 // Evaluate subexpressions recursively
608 todo.top().open = false;
609 REG::Exp* e = todo.top().exp;
610 todo.push(e->data.kids[1]);
611 todo.push(e->data.kids[0]);
612 } else {
613 todo.pop();
614 NodeInfo ni1 = done.pop();
615 NodeInfo ni0 = done.pop();
616 for (PosSet* ps = ni0.lastpos; ps != nullptr; ps = ps->next)
617 pi[ps->pos].followpos =
618 PosSet::cup(psm,pi[ps->pos].followpos,ni1.firstpos);
619 done.push(NodeInfo(ni0.nullable & ni1.nullable,
620 ni0.nullable ?
621 PosSet::cup(psm,ni0.firstpos,ni1.firstpos) : ni0.firstpos,
622 ni1.nullable ?
623 PosSet::cup(psm,ni0.lastpos,ni1.lastpos) : ni1.lastpos));
624 }
625 break;
626 case ET_OR:
627 if (todo.top().open) {
628 // Evaluate subexpressions recursively
629 todo.top().open = false;
630 REG::Exp* e = todo.top().exp;
631 todo.push(e->data.kids[1]);
632 todo.push(e->data.kids[0]);
633 } else {
634 todo.pop();
635 NodeInfo ni1 = done.pop();
636 NodeInfo ni0 = done.pop();
637 done.push(NodeInfo(ni0.nullable | ni1.nullable,
638 PosSet::cup(psm,ni0.firstpos,ni1.firstpos),
639 PosSet::cup(psm,ni0.lastpos,ni1.lastpos)));
640 }
641 break;
642 default: GECODE_NEVER;
643 }
644 }
645 } while (!todo.empty());
646 return done.top().firstpos;
647 }
648
649
650 namespace MiniModel {
651
652 class StateNode;
653
658
662 class StateNode : public Support::BlockClient<StateNode,Heap> {
663 public:
665 int state;
669 };
670
674 class StatePool {
675 public:
680
682
683 StateNode* pop(void);
684 bool empty(void) const;
685
686 int state(StatePoolAllocator&, PosSet*);
687 };
688
690 StatePool::StatePool(PosSet* ps) {
691 next = &root;
692 all = nullptr;
693 n_states = 1;
694 root.pos = ps;
695 root.state = 0;
696 root.next = nullptr;
697 root.left = nullptr;
698 root.right = nullptr;
699 }
700
702 StatePool::pop(void) {
703 StateNode* n = next;
704 next = n->next;
705 n->next = all;
706 all = n;
707 return n;
708 }
709
710 forceinline bool
711 StatePool::empty(void) const {
712 return next == nullptr;
713 }
714
715 forceinline int
716 StatePool::state(StatePoolAllocator& spm, PosSet* ps) {
717 int d = 0;
718 StateNode** p = nullptr;
719 StateNode* n = &root;
720 do {
721 switch (PosSet::cmp(ps,n->pos)) {
722 case PSC_EQ: return n->state;
723 case PSC_LE: p = &n->left; n = *p; break;
724 case PSC_GR: p = &n->right; n = *p; break;
725 default: GECODE_NEVER;
726 }
727 d++;
728 } while (n != nullptr);
729 n = new (spm) StateNode; *p = n;
730 n->pos = ps;
731 n->state = n_states++;
732 n->next = next;
733 n->left = nullptr;
734 n->right = nullptr;
735 next = n;
736 return n->state;
737 }
738
743 public:
744 forceinline bool
745 operator ()(int x, int y) {
746 return x < y;
747 }
748 forceinline static void
749 sort(int s[], int n) {
750 SymbolsInc o;
751 Support::quicksort<int,SymbolsInc>(s,n,o);
752 }
753 };
754
755
761 private:
763 int n;
764 public:
765 TransitionBag(void);
766 void add(int,int,int);
767 void finish(void);
768 DFA::Transition* transitions(void);
769 };
770
772 TransitionBag::TransitionBag(void) : t(heap), n(0) {}
773
774 forceinline void
775 TransitionBag::add(int i_state, int symbol, int o_state) {
776 t[n].i_state = i_state;
777 t[n].symbol = symbol;
778 t[n].o_state = o_state;
779 n++;
780 }
781
782 forceinline void
784 t[n].i_state = -1;
785 }
786
789 return &t[0];
790 }
791
792
797 class FinalBag {
798 private:
800 int n;
801 public:
802 FinalBag(void);
803 void add(int);
804 void finish(void);
805 int* finals(void);
806 };
807
809 FinalBag::FinalBag(void) : f(heap), n(0) {}
810
811 forceinline void
812 FinalBag::add(int state) {
813 f[n++] = state;
814 }
815
816 forceinline void
818 f[n] = -1;
819 }
820
821 forceinline int*
823 return &f[0];
824 }
825
826 }
827
828 REG::operator DFA(void) {
831 using MiniModel::PosInfo;
832 using MiniModel::PosSet;
834
837
840
842
843 Region region;
844 PosSetAllocator psm(region);
845 StatePoolAllocator spm(heap);
846 REG r = *this + REG(Int::Limits::max+1);
847 int n_pos = REG::Exp::n_pos(r.e);
848
849 PosInfo* pi = region.alloc<PosInfo>(n_pos);
850 for (int i=n_pos; i--; )
851 pi[i].followpos = nullptr;
852
853 PosSet* firstpos = r.e->followpos(psm,&pi[0]);
854
855 // Compute symbols
856 int* symbols = region.alloc<int>(n_pos);
857 for (int i=n_pos; i--; )
858 symbols[i] = pi[i].symbol;
859
860 SymbolsInc::sort(&symbols[0],n_pos-1);
861 int n_symbols = 1;
862 for (int i = 1; i<n_pos-1; i++)
863 if (symbols[i-1] != symbols[i])
864 symbols[n_symbols++] = symbols[i];
865
866 // Compute states and transitions
867 TransitionBag tb;
868 StatePool sp(firstpos);
869 while (!sp.empty()) {
870 StateNode* sn = sp.pop();
871 for (int i = n_symbols; i--; ) {
872 PosSet* u = nullptr;
873 for (PosSet* ps = sn->pos; ps != nullptr; ps = ps->next)
874 if (pi[ps->pos].symbol == symbols[i])
875 u = PosSet::cup(psm,u,pi[ps->pos].followpos);
876 if (u != nullptr)
877 tb.add(sn->state,symbols[i],sp.state(spm,u));
878 }
879 }
880 tb.finish();
881
882 // Compute final states
883 FinalBag fb;
884 for (StateNode* n = sp.all; n != nullptr; n = n->next)
885 if (n->pos->in(n_pos-1))
886 fb.add(n->state);
887 fb.finish();
888
889 return DFA(0,tb.transitions(),fb.finals(),true);
890 }
891
892}
893
894// STATISTICS: minimodel-any
895
union Gecode::@603::NNF::@65 u
Union depending on nodetype t.
NodeType t
Type of node.
int p
Number of positive literals for node type.
int n
Number of negative literals for node type.
struct Gecode::@603::NNF::@65::@67 a
For atomic nodes.
Node * x
Pointer to corresponding Boolean expression node.
Specification of a DFA transition.
Definition int.hh:2058
Deterministic finite automaton (DFA)
Definition int.hh:2049
void rfree(void *p)
Free memory block starting at p.
Definition heap.hpp:371
void * ralloc(size_t s)
Allocate s bytes from heap.
Definition heap.hpp:357
Passing integer arguments.
Definition int.hh:628
Expression information.
Definition reg.cpp:534
ExpInfo(REG::Exp *e=nullptr)
Definition reg.cpp:556
For collecting final states while constructing a DFA.
Definition reg.cpp:797
Node information computed during traversal of the expressions.
Definition reg.cpp:525
NodeInfo(bool n=false, PosSet *fp=nullptr, PosSet *lp=nullptr)
Definition reg.cpp:552
Information on positions collected during traversal.
Definition reg.cpp:545
Sets of positions.
Definition reg.cpp:451
static PosSet * cup(PosSetAllocator &, PosSet *, PosSet *)
Definition reg.cpp:501
bool in(int) const
Definition reg.cpp:474
static PosSetCmp cmp(PosSet *, PosSet *)
Definition reg.cpp:485
Node together with state information
Definition reg.cpp:662
State pool combines a tree of states together with yet unprocessed states
Definition reg.cpp:674
static void sort(int s[], int n)
Definition reg.cpp:749
Exception: Too few arguments available in argument array
Definition exception.hpp:45
For collecting transitions while constructing a DFA.
Definition reg.cpp:760
DFA::Transition * transitions(void)
Definition reg.cpp:788
void add(int, int, int)
Definition reg.cpp:775
Implementation of the actual expression tree.
Definition reg.cpp:52
std::string toString(void) const
Print expression.
Definition reg.cpp:214
MiniModel::PosSet * followpos(MiniModel::PosSetAllocator &, MiniModel::PosInfo *)
Compute the follow positions.
Definition reg.cpp:562
Exp * kids[2]
Subexpressions.
Definition reg.cpp:74
ExpType type
Type of regular expression.
Definition reg.cpp:68
static int n_pos(Exp *e)
Return number of positions of e.
Definition reg.cpp:148
unsigned int use_cnt
Reference counter.
Definition reg.cpp:55
static void dec(Exp *e)
Decrement use counter of e.
Definition reg.cpp:141
union Gecode::REG::Exp::@70 data
Symbol or subexpressions.
int symbol
Symbol.
Definition reg.cpp:72
void toString(std::ostringstream &os) const
Print expression to os.
Definition reg.cpp:153
static void inc(Exp *e)
Increment use counter of e.
Definition reg.cpp:136
int _n_pos
Number of positions.
Definition reg.cpp:57
ExpType
Type of regular expression.
Definition reg.cpp:61
Regular expressions over integer values.
~REG(void)
Destructor.
Definition reg.cpp:245
REG operator*(void)
Return expression for: this expression arbitrarily often (Kleene star)
Definition reg.cpp:360
const REG & operator=(const REG &r)
Assign to regular expression r.
Definition reg.cpp:236
REG & operator+=(const REG &r)
This expression is followed by r.
Definition reg.cpp:342
REG & operator|=(const REG &r)
This expression or r.
Definition reg.cpp:314
friend class MiniModel::ExpInfo
REG(void)
Initialize as empty sequence (epsilon)
Definition reg.cpp:229
REG operator()(unsigned int n, unsigned int m)
Return expression for: this expression at least n and at most m times.
Definition reg.cpp:373
REG operator+(void)
Return expression for: this expression at least once.
Definition reg.cpp:420
REG operator|(const REG &r)
Return expression for: this expression or r.
Definition reg.cpp:300
Handle to region.
Definition region.hpp:55
T * alloc(long unsigned int n)
Allocate block of n objects of type T from region.
Definition region.hpp:386
Manage memory organized into block lists (allocator)
Client for block allocator of type T.
Array with arbitrary number of elements.
Stack with arbitrary number of elements.
void push(const T &x)
Push element x on top of stack.
bool empty(void) const
Test whether stack is empty.
T pop(void)
Pop topmost element from stack and return it.
T & top(void) const
Return element on top of stack.
const int * pi[]
Definition photo.cpp:14262
Heap heap
The single global heap.
Definition heap.cpp:44
const int max
Largest allowed integer value.
Definition int.hh:116
Support::BlockAllocator< PosSet, Region > PosSetAllocator
Allocator for position sets.
Definition reg.cpp:44
PosSetCmp
Order on position sets.
Definition reg.cpp:442
Gecode toplevel namespace
Post propagator for SetVar SetOpType SetVar SetRelType r
Definition set.hh:767
Post propagator for SetVar SetOpType SetVar y
Definition set.hh:767
void exp(Home home, FloatVar x0, FloatVar x1)
Post propagator for .
Post propagator for SetVar x
Definition set.hh:767
#define forceinline
Definition config.hpp:187
#define GECODE_NEVER
Assert that this command is never executed.
Definition macros.hpp:56