87 void toString(std::ostringstream& os)
const;
91 static void*
operator new(size_t);
92 static void operator delete(
void*);
106 REG::Exp::operator
new(
size_t s) {
107 return heap.ralloc(s);
110 REG::Exp::operator
delete(
void*) {
115 REG::Exp::dispose(
void) {
119 while (!todo.empty()) {
124 if ((e->data.kids[1] !=
nullptr) && (--e->data.kids[1]->use_cnt == 0))
125 todo.push(e->data.kids[1]);
127 if ((e->data.kids[0] !=
nullptr) && (--e->data.kids[0]->use_cnt == 0))
128 todo.push(e->data.kids[0]);
142 if ((e !=
nullptr) && (--e->use_cnt == 0))
149 return (e !=
nullptr) ? e->_n_pos : 0;
156 os <<
"[" <<
data.symbol <<
"]";
160 bool par = ((
data.kids[0] !=
nullptr) &&
163 os << (par ?
"*(" :
"*");
164 if (
data.kids[0]==
nullptr) {
167 data.kids[0]->toString(os);
169 os << (par ?
")" :
"");
174 bool par0 = ((
data.kids[0] !=
nullptr) &&
176 os << (par0 ?
"(" :
"");
177 if (
data.kids[0]==
nullptr) {
180 data.kids[0]->toString(os);
182 os << (par0 ?
")+" :
"+");
183 bool par1 = ((
data.kids[1] !=
nullptr) &&
185 os << (par1 ?
"(" :
"");
186 if (
data.kids[1]==
nullptr) {
189 data.kids[1]->toString(os);
191 os << (par1 ?
")" :
"");
195 if (
data.kids[0]==
nullptr) {
198 data.kids[0]->toString(os);
201 if (
data.kids[1]==
nullptr) {
204 data.kids[1]->toString(os);
215 std::ostringstream os;
263 for (
int i=n; i--; ) {
268 a[i]->data.symbol =
x[i];
271 for (
int m=n; m>1; ) {
280 a[0]->data.kids[0] = e1;
281 a[0]->data.kids[1] = e2;
284 for (
int i=0; i<m; i++) {
291 a[i]->data.kids[0] = e1;
292 a[i]->data.kids[1] = e2;
329 if (e ==
nullptr)
return r2;
330 if (r2.e ==
nullptr)
return *
this;
375 if ((n>m) || (m == 0))
388 unsigned int i = m-n;
425 REG::toString(
void)
const {
475 for (
const PosSet* ps =
this; ps !=
nullptr; ps = ps->next)
478 }
else if (ps->pos < p) {
486 while ((ps1 !=
nullptr) && (ps2 !=
nullptr)) {
504 while ((ps1 !=
nullptr) && (ps2 !=
nullptr)) {
509 *p = n; p = &n->
next;
510 if (ps1->
pos == ps2->
pos) {
513 }
else if (ps1->
pos > ps2->
pos) {
519 *p = (ps1 !=
nullptr) ? ps1 : ps2;
579 if (todo.
top().exp ==
nullptr) {
581 done.
push(NodeInfo(
true,
nullptr,
nullptr));
583 switch (todo.
top().exp->type) {
586 pi[p].symbol = todo.
pop().exp->data.symbol;
587 PosSet* ps =
new (psm) PosSet(p++);
588 done.
push(NodeInfo(
false,ps,ps));
592 if (todo.
top().open) {
594 todo.
top().open =
false;
595 todo.
push(todo.
top().exp->data.kids[0]);
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));
606 if (todo.
top().open) {
608 todo.
top().open =
false;
610 todo.
push(e->data.kids[1]);
611 todo.
push(e->data.kids[0]);
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,
621 PosSet::cup(psm,ni0.firstpos,ni1.firstpos) : ni0.firstpos,
623 PosSet::cup(psm,ni0.lastpos,ni1.lastpos) : ni1.lastpos));
627 if (todo.
top().open) {
629 todo.
top().open =
false;
631 todo.
push(e->data.kids[1]);
632 todo.
push(e->data.kids[0]);
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)));
645 }
while (!todo.
empty());
646 return done.
top().firstpos;
684 bool empty(
void)
const;
698 root.right =
nullptr;
712 return next ==
nullptr;
728 }
while (n !=
nullptr);
745 operator ()(
int x,
int y) {
766 void add(
int,
int,
int);
776 t[n].i_state = i_state;
777 t[n].symbol = symbol;
778 t[n].o_state = o_state;
844 PosSetAllocator psm(region);
845 StatePoolAllocator spm(
heap);
849 PosInfo*
pi = region.
alloc<PosInfo>(n_pos);
850 for (
int i=n_pos; i--; )
851 pi[i].followpos =
nullptr;
853 PosSet* firstpos =
r.e->followpos(psm,&
pi[0]);
856 int* symbols = region.
alloc<
int>(n_pos);
857 for (
int i=n_pos; i--; )
858 symbols[i] =
pi[i].symbol;
860 SymbolsInc::sort(&symbols[0],n_pos-1);
862 for (
int i = 1; i<n_pos-1; i++)
863 if (symbols[i-1] != symbols[i])
864 symbols[n_symbols++] = symbols[i];
868 StatePool sp(firstpos);
869 while (!sp.empty()) {
870 StateNode* sn = sp.pop();
871 for (
int i = n_symbols; i--; ) {
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);
877 tb.add(sn->state,symbols[i],sp.state(spm,u));
884 for (StateNode* n = sp.all; n !=
nullptr; n = n->next)
885 if (n->pos->in(n_pos-1))
889 return DFA(0,tb.transitions(),fb.finals(),
true);
Specification of a DFA transition.
Deterministic finite automaton (DFA)
Passing integer arguments.
ExpInfo(REG::Exp *e=nullptr)
For collecting final states while constructing a DFA.
Node information computed during traversal of the expressions.
NodeInfo(bool n=false, PosSet *fp=nullptr, PosSet *lp=nullptr)
Information on positions collected during traversal.
static PosSet * cup(PosSetAllocator &, PosSet *, PosSet *)
static PosSetCmp cmp(PosSet *, PosSet *)
Node together with state information
State pool combines a tree of states together with yet unprocessed states
int state(StatePoolAllocator &, PosSet *)
static void sort(int s[], int n)
Exception: Too few arguments available in argument array
For collecting transitions while constructing a DFA.
DFA::Transition * transitions(void)
Implementation of the actual expression tree.
std::string toString(void) const
Print expression.
MiniModel::PosSet * followpos(MiniModel::PosSetAllocator &, MiniModel::PosInfo *)
Compute the follow positions.
Exp * kids[2]
Subexpressions.
ExpType type
Type of regular expression.
static int n_pos(Exp *e)
Return number of positions of e.
unsigned int use_cnt
Reference counter.
union Gecode::REG::Exp::@006363043156204252347047222243062210172322043104 data
Symbol or subexpressions.
static void dec(Exp *e)
Decrement use counter of e.
void toString(std::ostringstream &os) const
Print expression to os.
static void inc(Exp *e)
Increment use counter of e.
int _n_pos
Number of positions.
ExpType
Type of regular expression.
Regular expressions over integer values.
REG operator*(void)
Return expression for: this expression arbitrarily often (Kleene star)
const REG & operator=(const REG &r)
Assign to regular expression r.
REG & operator+=(const REG &r)
This expression is followed by r.
REG & operator|=(const REG &r)
This expression or r.
friend class MiniModel::ExpInfo
REG(void)
Initialize as empty sequence (epsilon)
REG operator()(unsigned int n, unsigned int m)
Return expression for: this expression at least n and at most m times.
REG operator+(void)
Return expression for: this expression at least once.
REG operator|(const REG &r)
Return expression for: this expression or r.
T * alloc(long unsigned int n)
Allocate block of n objects of type T from region.
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.
Heap heap
The single global heap.
const int max
Largest allowed integer value.
Minimalistic modeling support.
Support::BlockAllocator< PosSet, Region > PosSetAllocator
Allocator for position sets.
Support::BlockAllocator< StateNode, Heap > StatePoolAllocator
Allocator for state nodes.
PosSetCmp
Order on position sets.
void quicksort(Type *l, Type *r, Less &less)
Standard quick sort.
Gecode toplevel namespace
Post propagator for SetVar SetOpType SetVar SetRelType r
Post propagator for SetVar SetOpType SetVar y
Post propagator for SetVar x
#define GECODE_NEVER
Assert that this command is never executed.