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;
91 static void*
operator new(size_t);
92 static void operator delete(
void*);
106 REG::Exp::operator
new(
size_t s) {
110 REG::Exp::operator
delete(
void*) {
115 REG::Exp::dispose(
void) {
118 while (!todo.
empty()) {
141 if ((e != NULL) && (--e->
use_cnt == 0))
148 return (e != NULL) ? e->
_n_pos : 0;
155 os <<
"[" << data.symbol <<
"]";
159 bool par = ((data.kids[0] != NULL) &&
160 ((data.kids[0]->type == ET_CONC) ||
161 (data.kids[0]->type == ET_OR)));
162 os << (par ?
"*(" :
"*");
163 if (data.kids[0]==NULL) {
166 data.kids[0]->toString(os);
168 os << (par ?
")" :
"");
173 bool par0 = ((data.kids[0] != NULL) &&
174 (data.kids[0]->type == ET_OR));
175 os << (par0 ?
"(" :
"");
176 if (data.kids[0]==NULL) {
179 data.kids[0]->toString(os);
181 os << (par0 ?
")+" :
"+");
182 bool par1 = ((data.kids[1] != NULL) &&
183 (data.kids[1]->type == ET_OR));
184 os << (par1 ?
"(" :
"");
185 if (data.kids[1]==NULL) {
188 data.kids[1]->toString(os);
190 os << (par1 ?
")" :
"");
194 if (data.kids[0]==NULL) {
197 data.kids[0]->toString(os);
200 if (data.kids[1]==NULL) {
203 data.kids[1]->toString(os);
214 std::ostringstream os;
261 for (
int i=n;
i--; ) {
269 for (
int m=n; m>1; ) {
282 for (
int i=0;
i<m;
i++) {
328 if (e == NULL)
return r2;
329 if (r2.e == NULL)
return *
this;
374 if ((n>m) || (m == 0))
387 unsigned int i = m-
n;
424 REG::toString(
void)
const {
431 namespace MiniModel {
467 PosSet::PosSet(
void) {}
469 PosSet::PosSet(
int p) :
pos(p), next(NULL) {}
474 for (
const PosSet* ps =
this; ps != NULL; ps = ps->
next)
477 }
else if (ps->pos < p) {
485 while ((ps1 != NULL) && (ps2 != NULL)) {
503 while ((ps1 != NULL) && (ps2 != NULL)) {
508 *p =
n; p = &n->
next;
509 if (ps1->
pos == ps2->
pos) {
512 }
else if (ps1->
pos > ps2->
pos) {
518 *p = (ps1 != NULL) ? ps1 : ps2;
552 : nullable(n), firstpos(fp), lastpos(lp) {}
556 :
exp(e), open(true) {}
576 if (todo.
top().exp == NULL) {
578 done.
push(NodeInfo(
true,NULL,NULL));
580 switch (todo.
top().exp->type) {
584 PosSet* ps =
new (psm) PosSet(p++);
585 done.
push(NodeInfo(
false,ps,ps));
589 if (todo.
top().open) {
591 todo.
top().open =
false;
592 todo.
push(todo.
top().exp->data.kids[0]);
595 NodeInfo ni = done.
pop();
596 for (PosSet* ps = ni.lastpos; ps != NULL; ps = ps->next)
599 done.
push(NodeInfo(
true,ni.firstpos,ni.lastpos));
603 if (todo.
top().open) {
605 todo.
top().open =
false;
611 NodeInfo ni1 = done.
pop();
612 NodeInfo ni0 = done.
pop();
613 for (PosSet* ps = ni0.lastpos; ps != NULL; ps = ps->next)
616 done.
push(NodeInfo(ni0.nullable & ni1.nullable,
618 PosSet::cup(psm,ni0.firstpos,ni1.firstpos) : ni0.firstpos,
620 PosSet::cup(psm,ni0.lastpos,ni1.lastpos) : ni1.lastpos));
624 if (todo.
top().open) {
626 todo.
top().open =
false;
632 NodeInfo ni1 = done.
pop();
633 NodeInfo ni0 = done.
pop();
634 done.
push(NodeInfo(ni0.nullable | ni1.nullable,
642 }
while (!todo.
empty());
643 return done.
top().firstpos;
647 namespace MiniModel {
681 bool empty(
void)
const;
683 int state(StatePoolAllocator&,
PosSet*);
728 n->
state = n_states++;
742 operator ()(
int x,
int y) {
748 Support::quicksort<int,SymbolsInc>(s,
n,o);
763 void add(
int,
int,
int);
773 t[n].i_state = i_state;
774 t[n].symbol = symbol;
775 t[n].o_state = o_state;
846 for (
int i=n_pos;
i--; )
847 pi[
i].followpos = NULL;
849 PosSet* firstpos = r.e->
followpos(psm,&pi[0]);
853 for (
int i=n_pos;
i--; )
854 symbols[
i] = pi[
i].symbol;
858 for (
int i = 1;
i<n_pos-1;
i++)
859 if (symbols[
i-1] != symbols[
i])
860 symbols[n_symbols++] = symbols[
i];
864 StatePool sp(firstpos);
865 while (!sp.empty()) {
866 StateNode* sn = sp.pop();
867 for (
int i = n_symbols; i--; ) {
869 for (PosSet* ps = sn->pos; ps != NULL; ps = ps->next)
870 if (pi[ps->pos].symbol == symbols[i])
873 tb.add(sn->state,symbols[i],sp.state(spm,u));
880 for (StateNode* n = sp.all; n != NULL; n = n->next)
881 if (n->pos->in(n_pos-1))
887 return DFA(0,tb.transitions(),fb.finals(),
true);
Information on positions collected during traversal.
int state(StatePoolAllocator &, PosSet *)
int size(void) const
Return size of array (number of elements)
PosSetCmp
Order on position sets.
static PosSet * cup(PosSetAllocator &, PosSet *, PosSet *)
ExpInfo(REG::Exp *e=NULL)
static PosSetCmp cmp(PosSet *, PosSet *)
void rfree(void *p)
Free memory block starting at p.
Regular expressions over integer values.
Exception: Too few arguments available in argument array
Support::BlockAllocator< StateNode, Heap > StatePoolAllocator
Allocator for state nodes.
bool pos(const View &x)
Test whether x is postive.
REG & operator|=(const REG &r)
This expression or r.
Exp * kids[2]
Subexpressions.
void * ralloc(size_t s)
Allocate s bytes from heap.
Support::BlockAllocator< PosSet, Heap > PosSetAllocator
Allocator for position sets.
Array with arbitrary number of elements.
const int max
Largest allowed integer value.
std::string toString(void) const
Print expression.
Manage memory organized into block lists (allocator)
Deterministic finite automaton (DFA)
int p
Number of positive literals for node type.
T * alloc(long unsigned int n)
Allocate block of n objects of type T from heap.
Gecode::IntArgs i(4, 1, 2, 3, 4)
int n
Number of negative literals for node type.
const REG & operator=(const REG &r)
Assign to regular expression r.
static void dec(Exp *e)
Decrement use counter of e.
REG & operator+=(const REG &r)
This expression is followed by r.
static int n_pos(Exp *e)
Return number of positions of e.
REG(void)
Initialize as empty sequence (epsilon)
State pool combines a tree of states together with yet unprocessed states
T pop(void)
Pop topmost element from stack and return it.
ExpType type
Type of regular expression.
REG operator|(const REG &r)
Return expression for: this expression or r.
Specification of a DFA transition.
static void inc(Exp *e)
Increment use counter of e.
union Gecode::@585::NNF::@62 u
Union depending on nodetype t.
unsigned int use_cnt
Reference counter.
Passing integer arguments.
Post propagator for SetVar SetOpType SetVar SetRelType r
MiniModel::PosSet * followpos(MiniModel::PosSetAllocator &, MiniModel::PosInfo *)
Compute the follow positions.
Post propagator for f(x \diamond_{\mathit{op}} y) \sim_r z \f$ void rel(Home home
ExpType
Type of regular expression.
Post propagator for SetVar SetOpType SetVar y
T & top(void) const
Return element on top of stack.
void free(T *b, long unsigned int n)
Delete n objects starting at b.
struct Gecode::@585::NNF::@62::@64 a
For atomic nodes.
DFA::Transition * transitions(void)
Client for block allocator of type T.
REG operator*(void)
Return expression for: this expression arbitrarily often (Kleene star)
Heap heap
The single global heap.
Stack with arbitrary number of elements.
Post propagator for SetVar x
Implementation of the actual expression tree.
union Gecode::REG::Exp::@67 data
Symbol or subexpressions.
For collecting transitions while constructing a DFA.
Node information computed during traversal of the expressions.
REG operator+(void)
Return expression for: this expression at least once.
void toString(std::ostringstream &os) const
Print expression to os.
Gecode toplevel namespace
REG operator()(unsigned int n, unsigned int m)
Return expression for: this expression at least n and at most m times.
void exp(Home home, FloatVar x0, FloatVar x1)
Post propagator for .
NodeInfo(bool n=false, PosSet *fp=NULL, PosSet *lp=NULL)
bool empty(void) const
Test whether stack is empty.
#define GECODE_NEVER
Assert that this command is never executed.
static void sort(int s[], int n)
int _n_pos
Number of positions.
Node together with state information
void push(const T &x)
Push element x on top of stack.
For collecting final states while constructing a DFA.