reg.cpp
Go to the documentation of this file.
/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
/*
* Main authors:
* Christian Schulte <schulte@gecode.org>
*
* Copyright:
* Christian Schulte, 2004
*
* This file is part of Gecode, the generic constraint
* development environment:
* http://www.gecode.org
*
* Permission is hereby granted, free of charge, to any person obtaining
* a copy of this software and associated documentation files (the
* "Software"), to deal in the Software without restriction, including
* without limitation the rights to use, copy, modify, merge, publish,
* distribute, sublicense, and/or sell copies of the Software, and to
* permit persons to whom the Software is furnished to do so, subject to
* the following conditions:
*
* The above copyright notice and this permission notice shall be
* included in all copies or substantial portions of the Software.
*
* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
* EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
* MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
* NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
* LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
* OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
* WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
*
*/
#include <gecode/minimodel.hh>
namespace Gecode {
namespace MiniModel {
class PosSet;
typedef Support::BlockAllocator<PosSet,Region> PosSetAllocator;
class NodeInfo;
class PosInfo;
}
class REG::Exp {
public:
unsigned int use_cnt;
int _n_pos;
enum ExpType {
ET_SYMBOL,
ET_CONC,
ET_OR,
ET_STAR
};
ExpType type;
union {
int symbol;
Exp* kids[2];
} data;
MiniModel::PosSet*
followpos(MiniModel::PosSetAllocator&,MiniModel::PosInfo*);
static void inc(Exp* e);
static void dec(Exp* e);
static int n_pos(Exp* e);
void toString(std::ostringstream& os) const;
std::string toString(void) const;
static void* operator new(size_t);
static void operator delete(void*);
private:
void dispose(void);
};
/*
* Operations on expression nodes
*
*/
forceinline void*
REG::Exp::operator new(size_t s) {
return heap.ralloc(s);
}
forceinline void
REG::Exp::operator delete(void*) {
// Deallocation happens in dispose
}
void
REG::Exp::dispose(void) {
Region region;
Support::DynamicStack<Exp*,Region> todo(region);
todo.push(this);
while (!todo.empty()) {
Exp* e = todo.pop();
switch (e->type) {
case ET_OR:
case ET_CONC:
if ((e->data.kids[1] != nullptr) && (--e->data.kids[1]->use_cnt == 0))
todo.push(e->data.kids[1]);
case ET_STAR:
if ((e->data.kids[0] != nullptr) && (--e->data.kids[0]->use_cnt == 0))
todo.push(e->data.kids[0]);
default: ;
}
heap.rfree(e);
}
}
forceinline void
REG::Exp::inc(Exp* e) {
if (e != nullptr)
e->use_cnt++;
}
forceinline void
REG::Exp::dec(Exp* e) {
if ((e != nullptr) && (--e->use_cnt == 0))
e->dispose();
}
forceinline int
REG::Exp::n_pos(Exp* e) {
return (e != nullptr) ? e->_n_pos : 0;
}
void
REG::Exp::toString(std::ostringstream& os) const {
switch (type) {
case ET_SYMBOL:
os << "[" << data.symbol << "]";
return;
case ET_STAR:
{
bool par = ((data.kids[0] != nullptr) &&
((data.kids[0]->type == ET_CONC) ||
(data.kids[0]->type == ET_OR)));
os << (par ? "*(" : "*");
if (data.kids[0]==nullptr) {
os << "[]";
} else {
data.kids[0]->toString(os);
}
os << (par ? ")" : "");
return;
}
case ET_CONC:
{
bool par0 = ((data.kids[0] != nullptr) &&
(data.kids[0]->type == ET_OR));
os << (par0 ? "(" : "");
if (data.kids[0]==nullptr) {
os << "[]";
} else {
data.kids[0]->toString(os);
}
os << (par0 ? ")+" : "+");
bool par1 = ((data.kids[1] != nullptr) &&
(data.kids[1]->type == ET_OR));
os << (par1 ? "(" : "");
if (data.kids[1]==nullptr) {
os << "[]";
} else {
data.kids[1]->toString(os);
}
os << (par1 ? ")" : "");
return;
}
case ET_OR:
if (data.kids[0]==nullptr) {
os << "[]";
} else {
data.kids[0]->toString(os);
}
os << "|";
if (data.kids[1]==nullptr) {
os << "[]";
} else {
data.kids[1]->toString(os);
}
return;
default: GECODE_NEVER;
}
GECODE_NEVER;
return;
}
std::string
REG::Exp::toString(void) const {
std::ostringstream os;
toString(os);
return os.str();
}
/*
* Regular expressions
*
*/
forceinline
REG::REG(Exp* f) : e(f) {}
REG::REG(void) : e(nullptr) {}
REG::REG(const REG& r) : e(r.e) {
REG::Exp::inc(e);
}
const REG&
REG::operator =(const REG& r) {
if (&r != this) {
REG::Exp::inc(r.e);
REG::Exp::dec(e);
e = r.e;
}
return *this;
}
REG::~REG(void) {
REG::Exp::dec(e);
}
REG::REG(int s) : e(new Exp) {
e->use_cnt = 1;
e->_n_pos = 1;
e->type = REG::Exp::ET_SYMBOL;
e->data.symbol = s;
}
REG::REG(const IntArgs& x) {
int n = x.size();
if (n < 1)
throw MiniModel::TooFewArguments("REG");
Region region;
Exp** a = region.alloc<Exp*>(n);
// Initialize with symbols
for (int i=n; i--; ) {
a[i] = new Exp();
a[i]->use_cnt = 1;
a[i]->_n_pos = 1;
a[i]->type = REG::Exp::ET_SYMBOL;
a[i]->data.symbol = x[i];
}
// Build a balanced tree of alternative nodes
for (int m=n; m>1; ) {
if (m & 1) {
m -= 1;
Exp* e1 = a[m];
Exp* e2 = a[0];
a[0] = new Exp;
a[0]->use_cnt = 1;
a[0]->_n_pos = REG::Exp::n_pos(e1) + REG::Exp::n_pos(e2);
a[0]->type = REG::Exp::ET_OR;
a[0]->data.kids[0] = e1;
a[0]->data.kids[1] = e2;
} else {
m >>= 1;
for (int i=0; i<m; i++) {
Exp* e1 = a[2*i];
Exp* e2 = a[2*i+1];
a[i] = new Exp;
a[i]->use_cnt = 1;
a[i]->_n_pos = REG::Exp::n_pos(e1) + REG::Exp::n_pos(e2);
a[i]->type = REG::Exp::ET_OR;
a[i]->data.kids[0] = e1;
a[i]->data.kids[1] = e2;
}
}
}
e = a[0];
}
REG
REG::operator |(const REG& r2) {
if (e == r2.e)
return *this;
Exp* f = new Exp();
f->use_cnt = 1;
f->_n_pos = REG::Exp::n_pos(e) + REG::Exp::n_pos(r2.e);
f->type = REG::Exp::ET_OR;
f->data.kids[0] = e; REG::Exp::inc(e);
f->data.kids[1] = r2.e; REG::Exp::inc(r2.e);
REG r(f);
return r;
}
REG&
REG::operator |=(const REG& r2) {
if (e == r2.e)
return *this;
Exp* f = new Exp();
f->use_cnt = 1;
f->_n_pos = REG::Exp::n_pos(e) + REG::Exp::n_pos(r2.e);
f->type = REG::Exp::ET_OR;
f->data.kids[0] = e;
f->data.kids[1] = r2.e; REG::Exp::inc(r2.e);
e=f;
return *this;
}
REG
REG::operator +(const REG& r2) {
if (e == nullptr) return r2;
if (r2.e == nullptr) return *this;
Exp* f = new Exp();
f->use_cnt = 1;
f->_n_pos = REG::Exp::n_pos(e) + REG::Exp::n_pos(r2.e);
f->type = REG::Exp::ET_CONC;
f->data.kids[0] = e; REG::Exp::inc(e);
f->data.kids[1] = r2.e; REG::Exp::inc(r2.e);
REG r(f);
return r;
}
REG&
REG::operator +=(const REG& r2) {
if (r2.e == nullptr)
return *this;
if (e == nullptr) {
e=r2.e; REG::Exp::inc(e);
} else {
Exp* f = new Exp();
f->use_cnt = 1;
f->_n_pos = REG::Exp::n_pos(e) + REG::Exp::n_pos(r2.e);
f->type = REG::Exp::ET_CONC;
f->data.kids[0] = e;
f->data.kids[1] = r2.e; REG::Exp::inc(r2.e);
e=f;
}
return *this;
}
REG
REG::operator *(void) {
if ((e == nullptr) || (e->type == REG::Exp::ET_STAR))
return *this;
Exp* f = new Exp();
f->use_cnt = 1;
f->_n_pos = REG::Exp::n_pos(e);
f->type = REG::Exp::ET_STAR;
f->data.kids[0] = e; REG::Exp::inc(e);
REG r(f);
return r;
}
REG
REG::operator ()(unsigned int n, unsigned int m) {
REG r;
if ((n>m) || (m == 0))
return r;
if (n>0) {
unsigned int i = n;
REG r0 = *this;
while (i>0)
if (i & 1) {
r = r0+r; i--;
} else {
r0 = r0+r0; i >>= 1;
}
}
if (m > n) {
unsigned int i = m-n;
REG s0;
s0 = s0 | *this;
REG s;
while (i>0)
if (i & 1) {
s = s0+s; i--;
} else {
s0 = s0+s0; i >>= 1;
}
r = r + s;
}
return r;
}
REG
REG::operator ()(unsigned int n) {
REG r;
if (n > 0) {
REG r0 = *this;
unsigned int i = n;
while (i>0)
if (i & 1) {
r = r0+r; i--;
} else {
r0 = r0+r0; i >>= 1;
}
}
return r+**this;
}
REG
REG::operator +(void) {
return this->operator ()(1);
}
std::string
REG::toString(void) const {
if (e==nullptr) {
return "[]";
}
return e->toString();
}
namespace MiniModel {
/*
* Sets of positions
*
*/
enum PosSetCmp {
PSC_LE,
PSC_EQ,
PSC_GR
};
class PosSet : public Support::BlockClient<PosSet,Region> {
// Maintain sets of positions in inverse order
// This makes the check whether the last position is included
// more efficient.
public:
int pos; PosSet* next;
PosSet(void);
PosSet(int);
bool in(int) const;
static PosSetCmp cmp(PosSet*,PosSet*);
static PosSet* cup(PosSetAllocator&,PosSet*,PosSet*);
};
forceinline
PosSet::PosSet(void) {}
forceinline
PosSet::PosSet(int p) : pos(p), next(nullptr) {}
forceinline bool
PosSet::in(int p) const {
for (const PosSet* ps = this; ps != nullptr; ps = ps->next)
if (ps->pos == p) {
return true;
} else if (ps->pos < p) {
return false;
}
return false;
}
forceinline PosSetCmp
PosSet::cmp(PosSet* ps1, PosSet* ps2) {
while ((ps1 != nullptr) && (ps2 != nullptr)) {
if (ps1 == ps2)
return PSC_EQ;
if (ps1->pos < ps2->pos)
return PSC_LE;
if (ps1->pos > ps2->pos)
return PSC_GR;
ps1 = ps1->next; ps2 = ps2->next;
}
if (ps1 == ps2)
return PSC_EQ;
return ps1 == nullptr ? PSC_LE : PSC_GR;
}
PosSet*
PosSet::cup(PosSetAllocator& psm, PosSet* ps1, PosSet* ps2) {
PosSet* ps;
PosSet** p = &ps;
while ((ps1 != nullptr) && (ps2 != nullptr)) {
if (ps1 == ps2) {
*p = ps1; return ps;
}
PosSet* n = new (psm) PosSet;
*p = n; p = &n->next;
if (ps1->pos == ps2->pos) {
n->pos = ps1->pos;
ps1 = ps1->next; ps2 = ps2->next;
} else if (ps1->pos > ps2->pos) {
n->pos = ps1->pos; ps1 = ps1->next;
} else {
n->pos = ps2->pos; ps2 = ps2->next;
}
}
*p = (ps1 != nullptr) ? ps1 : ps2;
return ps;
}
class NodeInfo {
public:
bool nullable;
PosSet* firstpos;
PosSet* lastpos;
NodeInfo(bool n=false, PosSet* fp=nullptr, PosSet* lp=nullptr);
};
class ExpInfo {
public:
REG::Exp* exp;
bool open;
ExpInfo(REG::Exp* e=nullptr);
};
class PosInfo {
public:
int symbol;
PosSet* followpos;
};
forceinline
NodeInfo::NodeInfo(bool n, PosSet* fp, PosSet* lp)
: nullable(n), firstpos(fp), lastpos(lp) {}
forceinline
ExpInfo::ExpInfo(REG::Exp* e)
: exp(e), open(true) {}
}
forceinline MiniModel::PosSet*
REG::Exp::followpos(MiniModel::PosSetAllocator& psm,
MiniModel::PosInfo* pi) {
int p=0;
using MiniModel::PosSet;
using MiniModel::NodeInfo;
using MiniModel::ExpInfo;
Region region;
Support::DynamicStack<ExpInfo,Region> todo(region);
Support::DynamicStack<NodeInfo,Region> done(region);
// Start with first expression to be processed
todo.push(ExpInfo(this));
do {
if (todo.top().exp == nullptr) {
todo.pop();
done.push(NodeInfo(true,nullptr,nullptr));
} else {
switch (todo.top().exp->type) {
case ET_SYMBOL:
{
pi[p].symbol = todo.pop().exp->data.symbol;
PosSet* ps = new (psm) PosSet(p++);
done.push(NodeInfo(false,ps,ps));
}
break;
case ET_STAR:
if (todo.top().open) {
// Evaluate subexpression recursively
todo.top().open = false;
todo.push(todo.top().exp->data.kids[0]);
} else {
todo.pop();
NodeInfo ni = done.pop();
for (PosSet* ps = ni.lastpos; ps != nullptr; ps = ps->next)
pi[ps->pos].followpos =
PosSet::cup(psm,pi[ps->pos].followpos,ni.firstpos);
done.push(NodeInfo(true,ni.firstpos,ni.lastpos));
}
break;
case ET_CONC:
if (todo.top().open) {
// Evaluate subexpressions recursively
todo.top().open = false;
REG::Exp* e = todo.top().exp;
todo.push(e->data.kids[1]);
todo.push(e->data.kids[0]);
} else {
todo.pop();
NodeInfo ni1 = done.pop();
NodeInfo ni0 = done.pop();
for (PosSet* ps = ni0.lastpos; ps != nullptr; ps = ps->next)
pi[ps->pos].followpos =
PosSet::cup(psm,pi[ps->pos].followpos,ni1.firstpos);
done.push(NodeInfo(ni0.nullable & ni1.nullable,
ni0.nullable ?
PosSet::cup(psm,ni0.firstpos,ni1.firstpos) : ni0.firstpos,
ni1.nullable ?
PosSet::cup(psm,ni0.lastpos,ni1.lastpos) : ni1.lastpos));
}
break;
case ET_OR:
if (todo.top().open) {
// Evaluate subexpressions recursively
todo.top().open = false;
REG::Exp* e = todo.top().exp;
todo.push(e->data.kids[1]);
todo.push(e->data.kids[0]);
} else {
todo.pop();
NodeInfo ni1 = done.pop();
NodeInfo ni0 = done.pop();
done.push(NodeInfo(ni0.nullable | ni1.nullable,
PosSet::cup(psm,ni0.firstpos,ni1.firstpos),
PosSet::cup(psm,ni0.lastpos,ni1.lastpos)));
}
break;
default: GECODE_NEVER;
}
}
} while (!todo.empty());
return done.top().firstpos;
}
namespace MiniModel {
class StateNode;
typedef Support::BlockAllocator<StateNode,Heap> StatePoolAllocator;
class StateNode : public Support::BlockClient<StateNode,Heap> {
public:
PosSet* pos;
int state;
StateNode* next;
StateNode* left;
StateNode* right;
};
class StatePool {
public:
int n_states;
StateNode root;
StateNode* next;
StateNode* all;
StatePool(PosSet*);
StateNode* pop(void);
bool empty(void) const;
int state(StatePoolAllocator&, PosSet*);
};
forceinline
StatePool::StatePool(PosSet* ps) {
next = &root;
all = nullptr;
n_states = 1;
root.pos = ps;
root.state = 0;
root.next = nullptr;
root.left = nullptr;
root.right = nullptr;
}
forceinline StateNode*
StatePool::pop(void) {
StateNode* n = next;
next = n->next;
n->next = all;
all = n;
return n;
}
forceinline bool
StatePool::empty(void) const {
return next == nullptr;
}
forceinline int
StatePool::state(StatePoolAllocator& spm, PosSet* ps) {
int d = 0;
StateNode** p = nullptr;
StateNode* n = &root;
do {
switch (PosSet::cmp(ps,n->pos)) {
case PSC_EQ: return n->state;
case PSC_LE: p = &n->left; n = *p; break;
case PSC_GR: p = &n->right; n = *p; break;
default: GECODE_NEVER;
}
d++;
} while (n != nullptr);
n = new (spm) StateNode; *p = n;
n->pos = ps;
n->state = n_states++;
n->next = next;
n->left = nullptr;
n->right = nullptr;
next = n;
return n->state;
}
class SymbolsInc {
public:
forceinline bool
operator ()(int x, int y) {
return x < y;
}
forceinline static void
sort(int s[], int n) {
SymbolsInc o;
Support::quicksort<int,SymbolsInc>(s,n,o);
}
};
class TransitionBag {
private:
Support::DynamicArray<DFA::Transition,Heap> t;
int n;
public:
TransitionBag(void);
void add(int,int,int);
void finish(void);
DFA::Transition* transitions(void);
};
forceinline
TransitionBag::TransitionBag(void) : t(heap), n(0) {}
forceinline void
TransitionBag::add(int i_state, int symbol, int o_state) {
t[n].i_state = i_state;
t[n].symbol = symbol;
t[n].o_state = o_state;
n++;
}
forceinline void
TransitionBag::finish(void) {
t[n].i_state = -1;
}
forceinline DFA::Transition*
TransitionBag::transitions(void) {
return &t[0];
}
class FinalBag {
private:
Support::DynamicArray<int,Heap> f;
int n;
public:
FinalBag(void);
void add(int);
void finish(void);
int* finals(void);
};
forceinline
FinalBag::FinalBag(void) : f(heap), n(0) {}
forceinline void
FinalBag::add(int state) {
f[n++] = state;
}
forceinline void
FinalBag::finish(void) {
f[n] = -1;
}
forceinline int*
FinalBag::finals(void) {
return &f[0];
}
}
REG::operator DFA(void) {
using MiniModel::PosSetAllocator;
using MiniModel::StatePoolAllocator;
using MiniModel::PosInfo;
using MiniModel::PosSet;
using MiniModel::NodeInfo;
using MiniModel::StatePool;
using MiniModel::StateNode;
using MiniModel::TransitionBag;
using MiniModel::FinalBag;
using MiniModel::SymbolsInc;
Region region;
PosSetAllocator psm(region);
StatePoolAllocator spm(heap);
REG r = *this + REG(Int::Limits::max+1);
int n_pos = REG::Exp::n_pos(r.e);
PosInfo* pi = region.alloc<PosInfo>(n_pos);
for (int i=n_pos; i--; )
pi[i].followpos = nullptr;
PosSet* firstpos = r.e->followpos(psm,&pi[0]);
// Compute symbols
int* symbols = region.alloc<int>(n_pos);
for (int i=n_pos; i--; )
symbols[i] = pi[i].symbol;
SymbolsInc::sort(&symbols[0],n_pos-1);
int n_symbols = 1;
for (int i = 1; i<n_pos-1; i++)
if (symbols[i-1] != symbols[i])
symbols[n_symbols++] = symbols[i];
// Compute states and transitions
TransitionBag tb;
StatePool sp(firstpos);
while (!sp.empty()) {
StateNode* sn = sp.pop();
for (int i = n_symbols; i--; ) {
PosSet* u = nullptr;
for (PosSet* ps = sn->pos; ps != nullptr; ps = ps->next)
if (pi[ps->pos].symbol == symbols[i])
u = PosSet::cup(psm,u,pi[ps->pos].followpos);
if (u != nullptr)
tb.add(sn->state,symbols[i],sp.state(spm,u));
}
}
tb.finish();
// Compute final states
FinalBag fb;
for (StateNode* n = sp.all; n != nullptr; n = n->next)
if (n->pos->in(n_pos-1))
fb.add(n->state);
fb.finish();
return DFA(0,tb.transitions(),fb.finals(),true);
}
}
// STATISTICS: minimodel-any
Gecode::ArgArrayBase::size
int size(void) const
Return size of array (number of elements).
Definition array.hpp:1607
Gecode::DFA::Transition
Specification of a DFA transition.
Definition int.hh:2058
Gecode::DFA
Deterministic finite automaton (DFA).
Definition int.hh:2049
Gecode::IntArgs
Passing integer arguments.
Definition int.hh:628
Gecode::MiniModel::ExpInfo
Expression information.
Definition reg.cpp:534
Gecode::MiniModel::ExpInfo::exp
REG::Exp * exp
Definition reg.cpp:536
Gecode::MiniModel::ExpInfo::ExpInfo
ExpInfo(REG::Exp *e=nullptr)
Definition reg.cpp:556
Gecode::MiniModel::ExpInfo::open
bool open
Definition reg.cpp:537
Gecode::MiniModel::FinalBag
For collecting final states while constructing a DFA.
Definition reg.cpp:797
Gecode::MiniModel::FinalBag::FinalBag
FinalBag(void)
Definition reg.cpp:809
Gecode::MiniModel::FinalBag::add
void add(int)
Definition reg.cpp:812
Gecode::MiniModel::FinalBag::finals
int * finals(void)
Definition reg.cpp:822
Gecode::MiniModel::FinalBag::finish
void finish(void)
Definition reg.cpp:817
Gecode::MiniModel::NodeInfo
Node information computed during traversal of the expressions.
Definition reg.cpp:525
Gecode::MiniModel::NodeInfo::NodeInfo
NodeInfo(bool n=false, PosSet *fp=nullptr, PosSet *lp=nullptr)
Definition reg.cpp:552
Gecode::MiniModel::NodeInfo::lastpos
PosSet * lastpos
Definition reg.cpp:529
Gecode::MiniModel::NodeInfo::firstpos
PosSet * firstpos
Definition reg.cpp:528
Gecode::MiniModel::NodeInfo::nullable
bool nullable
Definition reg.cpp:527
Gecode::MiniModel::PosInfo
Information on positions collected during traversal.
Definition reg.cpp:545
Gecode::MiniModel::PosInfo::symbol
int symbol
Definition reg.cpp:547
Gecode::MiniModel::PosInfo::followpos
PosSet * followpos
Definition reg.cpp:548
Gecode::MiniModel::PosSet
Sets of positions.
Definition reg.cpp:451
Gecode::MiniModel::PosSet::cup
static PosSet * cup(PosSetAllocator &, PosSet *, PosSet *)
Definition reg.cpp:501
Gecode::MiniModel::PosSet::in
bool in(int) const
Definition reg.cpp:474
Gecode::MiniModel::PosSet::cmp
static PosSetCmp cmp(PosSet *, PosSet *)
Definition reg.cpp:485
Gecode::MiniModel::PosSet::pos
int pos
Definition reg.cpp:456
Gecode::MiniModel::PosSet::PosSet
PosSet(void)
Definition reg.cpp:468
Gecode::MiniModel::PosSet::next
PosSet * next
Definition reg.cpp:456
Gecode::MiniModel::StateNode
Node together with state information
Definition reg.cpp:662
Gecode::MiniModel::StateNode::right
StateNode * right
Definition reg.cpp:668
Gecode::MiniModel::StateNode::pos
PosSet * pos
Definition reg.cpp:664
Gecode::MiniModel::StateNode::left
StateNode * left
Definition reg.cpp:667
Gecode::MiniModel::StateNode::state
int state
Definition reg.cpp:665
Gecode::MiniModel::StateNode::next
StateNode * next
Definition reg.cpp:666
Gecode::MiniModel::StatePool
State pool combines a tree of states together with yet unprocessed states
Definition reg.cpp:674
Gecode::MiniModel::StatePool::all
StateNode * all
Definition reg.cpp:679
Gecode::MiniModel::StatePool::n_states
int n_states
Definition reg.cpp:676
Gecode::MiniModel::StatePool::state
int state(StatePoolAllocator &, PosSet *)
Definition reg.cpp:716
Gecode::MiniModel::StatePool::StatePool
StatePool(PosSet *)
Definition reg.cpp:690
Gecode::MiniModel::StatePool::pop
StateNode * pop(void)
Definition reg.cpp:702
Gecode::MiniModel::StatePool::empty
bool empty(void) const
Definition reg.cpp:711
Gecode::MiniModel::StatePool::root
StateNode root
Definition reg.cpp:677
Gecode::MiniModel::StatePool::next
StateNode * next
Definition reg.cpp:678
Gecode::MiniModel::SymbolsInc
Sort symbols.
Definition reg.cpp:742
Gecode::MiniModel::SymbolsInc::sort
static void sort(int s[], int n)
Definition reg.cpp:749
Gecode::MiniModel::TooFewArguments
Exception: Too few arguments available in argument array
Definition exception.hpp:45
Gecode::MiniModel::TransitionBag
For collecting transitions while constructing a DFA.
Definition reg.cpp:760
Gecode::MiniModel::TransitionBag::transitions
DFA::Transition * transitions(void)
Definition reg.cpp:788
Gecode::MiniModel::TransitionBag::TransitionBag
TransitionBag(void)
Definition reg.cpp:772
Gecode::MiniModel::TransitionBag::add
void add(int, int, int)
Definition reg.cpp:775
Gecode::MiniModel::TransitionBag::finish
void finish(void)
Definition reg.cpp:783
Gecode::REG::Exp
Implementation of the actual expression tree.
Definition reg.cpp:52
Gecode::REG::Exp::toString
std::string toString(void) const
Print expression.
Definition reg.cpp:214
Gecode::REG::Exp::followpos
MiniModel::PosSet * followpos(MiniModel::PosSetAllocator &, MiniModel::PosInfo *)
Compute the follow positions.
Definition reg.cpp:562
Gecode::REG::Exp::kids
Exp * kids[2]
Subexpressions.
Definition reg.cpp:74
Gecode::REG::Exp::type
ExpType type
Type of regular expression.
Definition reg.cpp:68
Gecode::REG::Exp::n_pos
static int n_pos(Exp *e)
Return number of positions of e.
Definition reg.cpp:148
Gecode::REG::Exp::use_cnt
unsigned int use_cnt
Reference counter.
Definition reg.cpp:55
Gecode::REG::Exp::data
union Gecode::REG::Exp::@006363043156204252347047222243062210172322043104 data
Symbol or subexpressions.
Gecode::REG::Exp::dec
static void dec(Exp *e)
Decrement use counter of e.
Definition reg.cpp:141
Gecode::REG::Exp::symbol
int symbol
Symbol.
Definition reg.cpp:72
Gecode::REG::Exp::toString
void toString(std::ostringstream &os) const
Print expression to os.
Definition reg.cpp:153
Gecode::REG::Exp::inc
static void inc(Exp *e)
Increment use counter of e.
Definition reg.cpp:136
Gecode::REG::Exp::_n_pos
int _n_pos
Number of positions.
Definition reg.cpp:57
Gecode::REG::Exp::ExpType
ExpType
Type of regular expression.
Definition reg.cpp:61
Gecode::REG::Exp::ET_CONC
@ ET_CONC
Definition reg.cpp:63
Gecode::REG::Exp::ET_STAR
@ ET_STAR
Definition reg.cpp:65
Gecode::REG::Exp::ET_SYMBOL
@ ET_SYMBOL
Definition reg.cpp:62
Gecode::REG::Exp::ET_OR
@ ET_OR
Definition reg.cpp:64
Gecode::REG
Regular expressions over integer values.
Definition minimodel.hh:1625
Gecode::REG::~REG
~REG(void)
Destructor.
Definition reg.cpp:245
Gecode::REG::operator*
REG operator*(void)
Return expression for: this expression arbitrarily often (Kleene star).
Definition reg.cpp:360
Gecode::REG::operator=
const REG & operator=(const REG &r)
Assign to regular expression r.
Definition reg.cpp:236
Gecode::REG::operator+=
REG & operator+=(const REG &r)
This expression is followed by r.
Definition reg.cpp:342
Gecode::REG::operator|=
REG & operator|=(const REG &r)
This expression or r.
Definition reg.cpp:314
Gecode::REG::ExpInfo
friend class MiniModel::ExpInfo
Definition minimodel.hh:1626
Gecode::REG::REG
REG(void)
Initialize as empty sequence (epsilon).
Definition reg.cpp:229
Gecode::REG::operator()
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
Gecode::REG::operator+
REG operator+(void)
Return expression for: this expression at least once.
Definition reg.cpp:420
Gecode::REG::operator|
REG operator|(const REG &r)
Return expression for: this expression or r.
Definition reg.cpp:300
Gecode::Region
Handle to region.
Definition region.hpp:55
Gecode::Region::alloc
T * alloc(long unsigned int n)
Allocate block of n objects of type T from region.
Definition region.hpp:386
Gecode::Support::BlockAllocator
Manage memory organized into block lists (allocator).
Definition block-allocator.hpp:45
Gecode::Support::BlockClient
Client for block allocator of type T.
Definition block-allocator.hpp:84
Gecode::Support::DynamicArray
Array with arbitrary number of elements.
Definition dynamic-array.hpp:44
Gecode::Support::DynamicStack
Stack with arbitrary number of elements.
Definition dynamic-stack.hpp:42
Gecode::Support::DynamicStack::push
void push(const T &x)
Push element x on top of stack.
Definition dynamic-stack.hpp:140
Gecode::Support::DynamicStack::empty
bool empty(void) const
Test whether stack is empty.
Definition dynamic-stack.hpp:148
Gecode::Support::DynamicStack::pop
T pop(void)
Pop topmost element from stack and return it.
Definition dynamic-stack.hpp:122
Gecode::Support::DynamicStack::top
T & top(void) const
Return element on top of stack.
Definition dynamic-stack.hpp:128
pi
const int * pi[]
Definition photo.cpp:14262
Gecode::heap
Heap heap
The single global heap.
Definition heap.cpp:44
minimodel.hh
Gecode::Int::Limits::max
const int max
Largest allowed integer value.
Definition int.hh:116
Gecode::MiniModel
Minimalistic modeling support.
Definition minimodel.hh:92
Gecode::MiniModel::PosSetAllocator
Support::BlockAllocator< PosSet, Region > PosSetAllocator
Allocator for position sets.
Definition reg.cpp:44
Gecode::MiniModel::StatePoolAllocator
Support::BlockAllocator< StateNode, Heap > StatePoolAllocator
Allocator for state nodes.
Definition reg.cpp:657
Gecode::MiniModel::PosSetCmp
PosSetCmp
Order on position sets.
Definition reg.cpp:442
Gecode::MiniModel::PSC_EQ
@ PSC_EQ
Definition reg.cpp:444
Gecode::MiniModel::PSC_GR
@ PSC_GR
Definition reg.cpp:445
Gecode::MiniModel::PSC_LE
@ PSC_LE
Definition reg.cpp:443
Gecode::Support::quicksort
void quicksort(Type *l, Type *r, Less &less)
Standard quick sort.
Definition sort.hpp:130
Gecode
Gecode toplevel namespace
forceinline
#define forceinline
Definition config.hpp:187
GECODE_NEVER
#define GECODE_NEVER
Assert that this command is never executed.
Definition macros.hpp:56