85 int n_pos(
void)
const;
87 template<
class Char,
class Traits>
88 std::basic_ostream<Char,Traits>&
89 print(std::basic_ostream<Char,Traits>& os)
const;
91 static void*
operator new(size_t);
92 static void operator delete(
void*);
105 REG::Exp::operator
new(
size_t s) {
109 REG::Exp::operator
delete(
void*) {
114 REG::Exp::dispose(
void) {
117 while (!todo.empty()) {
140 if ((
this != NULL) && (--use_cnt == 0))
147 return (
this != NULL) ? _n_pos : 0;
192 for (
int i=
n;
i--; ) {
197 a[
i]->data.symbol =
x[
i];
200 for (
int m=
n; m>1; ) {
209 a[0]->data.kids[0] = e1;
210 a[0]->data.kids[1] = e2;
213 for (
int i=0;
i<m;
i++) {
220 a[
i]->data.kids[0] = e1;
221 a[
i]->data.kids[1] = e2;
259 if (e == NULL)
return r2;
260 if (r2.e == NULL)
return *
this;
305 if ((
n>m) || (m == 0))
318 unsigned int i = m-
n;
355 namespace MiniModel {
398 for (
const PosSet* ps =
this; ps != NULL; ps = ps->
next)
401 }
else if (ps->pos <
p) {
409 while ((ps1 != NULL) && (ps2 != NULL)) {
427 while ((ps1 != NULL) && (ps2 != NULL)) {
432 *
p =
n;
p = &
n->next;
433 if (ps1->
pos == ps2->
pos) {
436 }
else if (ps1->
pos > ps2->
pos) {
442 *
p = (ps1 != NULL) ? ps1 : ps2;
476 : nullable(
n), firstpos(fp), lastpos(lp) {}
480 :
exp(e), open(true) {}
497 todo.
push(ExpInfo(
this));
500 if (todo.
top().exp == NULL) {
502 done.
push(NodeInfo(
true,NULL,NULL));
504 switch (todo.
top().exp->type) {
508 PosSet* ps =
new (psm) PosSet(
p++);
509 done.
push(NodeInfo(
false,ps,ps));
513 if (todo.
top().open) {
515 todo.
top().open =
false;
516 todo.
push(todo.
top().exp->data.kids[0]);
519 NodeInfo ni = done.
pop();
520 for (PosSet* ps = ni.lastpos; ps != NULL; ps = ps->next)
522 PosSet::cup(psm,pi[ps->pos].
followpos,ni.firstpos);
523 done.
push(NodeInfo(
true,ni.firstpos,ni.lastpos));
527 if (todo.
top().open) {
529 todo.
top().open =
false;
535 NodeInfo ni1 = done.
pop();
536 NodeInfo ni0 = done.
pop();
537 for (PosSet* ps = ni0.lastpos; ps != NULL; ps = ps->next)
539 PosSet::cup(psm,pi[ps->pos].
followpos,ni1.firstpos);
540 done.
push(NodeInfo(ni0.nullable & ni1.nullable,
542 PosSet::cup(psm,ni0.firstpos,ni1.firstpos) : ni0.firstpos,
544 PosSet::cup(psm,ni0.lastpos,ni1.lastpos) : ni1.lastpos));
548 if (todo.
top().open) {
550 todo.
top().open =
false;
556 NodeInfo ni1 = done.
pop();
557 NodeInfo ni0 = done.
pop();
558 done.
push(NodeInfo(ni0.nullable | ni1.nullable,
559 PosSet::cup(psm,ni0.firstpos,ni1.firstpos),
560 PosSet::cup(psm,ni0.lastpos,ni1.lastpos)));
566 }
while (!todo.
empty());
567 return done.
top().firstpos;
571 namespace MiniModel {
605 bool empty(
void)
const;
623 StatePool::pop(
void) {
632 StatePool::empty(
void)
const {
642 switch (PosSet::cmp(ps,
n->pos)) {
652 n->state = n_states++;
672 Support::quicksort<int,SymbolsInc>(s,
n,o);
687 void add(
int,
int,
int);
693 TransitionBag::TransitionBag(
void) :
t(
heap),
n(0) {}
697 t[n].i_state = i_state;
698 t[n].symbol = symbol;
699 t[n].o_state = o_state;
767 int n_pos =
r.e->n_pos();
769 PosInfo* pi =
heap.
alloc<PosInfo>(n_pos);
770 for (
int i=n_pos;
i--; )
771 pi[
i].followpos = NULL;
773 PosSet* firstpos =
r.e->followpos(psm,&pi[0]);
777 for (
int i=n_pos;
i--; )
778 symbols[
i] = pi[
i].symbol;
782 for (
int i = 1;
i<n_pos-1;
i++)
783 if (symbols[
i-1] != symbols[
i])
784 symbols[n_symbols++] = symbols[
i];
788 StatePool sp(firstpos);
789 while (!sp.empty()) {
790 StateNode* sn = sp.pop();
791 for (
int i = n_symbols;
i--; ) {
793 for (PosSet* ps = sn->pos; ps != NULL; ps = ps->next)
794 if (pi[ps->pos].symbol == symbols[
i])
795 u = PosSet::cup(psm,
u,pi[ps->pos].followpos);
797 tb.add(sn->state,symbols[
i],sp.state(spm,
u));
804 for (StateNode*
n = sp.all;
n != NULL;
n =
n->next)
805 if (
n->pos->in(n_pos-1))
811 return DFA(0,tb.transitions(),fb.finals(),
true);
Information on positions collected during traversal.
PosSetCmp
Order on position sets.
static PosSet * cup(PosSetAllocator &, PosSet *, PosSet *)
ExpInfo(REG::Exp *e=NULL)
union Gecode::REG::Exp::@59 data
Symbol or subexpressions.
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.
Heap heap
The single global heap.
Manage memory organized into block lists (allocator)
void sort(TaskViewArray< TaskView > &t)
Sort task view array t according to sto and inc (increasing or decreasing)
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.
REG & operator+=(const REG &r)
This expression is followed by r.
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.
unsigned int use_cnt
Reference counter.
Passing integer arguments.
struct Gecode::@511::NNF::@54::@56 a
For atomic nodes.
MiniModel::PosSet * followpos(MiniModel::PosSetAllocator &, MiniModel::PosInfo *)
ExpType
Type of regular expression.
T & top(void) const
Return element on top of stack.
void free(T *b, long unsigned int n)
Delete n objects starting at b.
Node * x
Pointer to corresponding Boolean expression node.
union Gecode::@511::NNF::@54 u
Union depending on nodetype t.
DFA::Transition * transitions(void)
Client for block allocator of type T.
REG operator *(void)
Return expression for: this expression arbitrarily often (Kleene star)
Stack with arbitrary number of elements.
Implementation of the actual expression tree.
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.
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.
std::basic_ostream< Char, Traits > & print(std::basic_ostream< Char, Traits > &os) const
Print expression.