60 return (((x[0] == 0) || (x[0] == 2)) &&
61 ((x[1] == -1) || (x[1] == 1)) &&
62 ((x[2] == 0) || (x[2] == 1)) &&
63 ((x[3] == 0) || (x[3] == 1)));
83 return (
x[0]<
x[1]) && (
x[1]<
x[2]) && (
x[2]<
x[3]);
107 while (pos < s &&
x[pos] == 0) ++pos;
108 if (pos + 4 > s)
return false;
110 for (
int i = 0; i < 2; ++i, ++pos)
111 if (
x[pos] != 1)
return false;
112 if (pos + 2 > s)
return false;
114 for (
int i = 0; i < 1; ++i, ++pos)
115 if (
x[pos] != 0)
return false;
116 while (pos < s &&
x[pos] == 0) ++pos;
117 if (pos + 1 > s)
return false;
119 for (
int i = 0; i < 1; ++i, ++pos)
120 if (
x[pos] != 1)
return false;
121 while (pos < s)
if (
x[pos++] != 0)
return false;
140 for (
int i=0; i<
x.size(); i++) {
141 if ((
x[i] < 0) || (
x[i] > 3))
143 for (
int j=i+1; j<
x.size(); j++)
185 :
Test(
"Extensional::Reg::Roland::"+
str(n),n,0,1) {}
190 ((n > 1) && (
x[n-2] == 0)) ||
191 ((n > 0) && (
x[n-1] == 0));
209 return (((
x[0] == 0) || (
x[0] == 2)) &&
210 ((
x[1] == -1) || (
x[1] == 1)) &&
211 ((
x[2] == 0) || (
x[2] == 1)) &&
212 ((
x[3] == 0) || (
x[3] == 1)));
218 for (
int i=0; i<4; i++)
236 return (((
x[0] == 0) || (
x[0] == 2)) &&
237 ((
x[1] == -1) || (
x[1] == 1)) &&
238 ((
x[2] == 0) || (
x[2] == 1)) &&
239 ((
x[3] == 0) || (
x[3] == 1)));
245 for (
int i=0; i<4; i++)
246 y[i]=
y[i+4]=
y[i+8]=
x[i];
263 return (
x[1]==1) && (
x[2]==0) && (
x[3]==1);
269 for (
int i=0; i<4; i++)
284 return (
x[1]==1) && (
x[2]==0) && (
x[3]==1);
290 for (
int i=0; i<4; i++)
344 :
Test(
"Extensional::Reg::Opt::"+
str(n0),1,0,15),
n(n0) {}
347 return (
x[0] <
n) && ((
x[0] & 1) == 0);
354 int* f =
new int[
n+1];
356 for (
int i=0; i<
n; i++) {
367 DFA d(0, t, f,
false);
379 for (
int i = 0; i<ts.
tuples(); i++) {
381 for (
int j = 0; j<ts.
arity(); j++) {
400 :
Test(
"Extensional::TupleSet::" +
str(p) +
"::Base",
408 t.add(t1).add(t1).add(t2).add(t2)
409 .add(t3).add(t3).add(t4).add(t4)
410 .add(t5).add(t5).add(t5).add(t5)
411 .add(t5).add(t5).add(t5).add(t5)
412 .add(t1).add(t1).add(t2).add(t2)
413 .add(t3).add(t3).add(t4).add(t4)
414 .add(t5).add(t5).add(t5).add(t5)
415 .add(t5).add(t5).add(t5).add(t5)
420 return pos == ((
x[0] == 1 &&
x[1] == 3 &&
x[2] == 2 &&
x[3] == 3) ||
421 (
x[0] == 2 &&
x[1] == 1 &&
x[2] == 2 &&
x[3] == 4) ||
422 (
x[0] == 2 &&
x[1] == 2 &&
x[2] == 1 &&
x[3] == 4) ||
423 (
x[0] == 3 &&
x[1] == 3 &&
x[2] == 3 &&
x[3] == 2) ||
424 (
x[0] == 4 &&
x[1] == 3 &&
x[2] == 4 &&
x[3] == 1));
453 :
Test(
"Extensional::TupleSet::" +
str(p) +
"::" + s,
460 for (
int i=
ts.tuples(); i--; ) {
463 for (
int j=0; (j <
ts.arity()) &&
same; j++)
513 :
Test(
"Extensional::TupleSet::" +
str(p) +
"::Large",
521 for (
int i = 5; i--; ) tuple[i] = ass[i];
531 for (
int i = 0; i <
t.tuples(); ++i) {
534 for (
int j = 0; j <
t.arity() &&
same; ++j)
535 if (l[j] !=
x[j])
same =
false;
564 :
Test(
"Extensional::TupleSet::" +
str(p) +
"::Bool",
565 5,0,1,true),
pos(p),
t(5) {
572 for (
int i = 5; i--; ) tuple[i] = ass[i];
582 for (
int i = 0; i <
t.tuples(); ++i) {
585 for (
int j = 0; j <
t.arity() &&
same; ++j)
597 for (
int i =
x.size(); i--; )
606 for (
int i =
x.size(); i--; )
621 while (n_tuples < size) {
628 for (
int i = size; i--; ) {
631 for (
int j = arity; j--; ) tuple[j] = ass[j];
636 assert(ts.
tuples() == size);
650 for (
int i = n; i--; ) tuple[i] = ass[i];
665 for (
bool pos : {
false,
true }) {
668 ts.
add({2, 1, 2, 4}).add({2, 2, 1, 4})
669 .add({4, 3, 4, 1}).add({1, 3, 2, 3})
670 .add({3, 3, 3, 2}).add({5, 1, 4, 4})
671 .add({2, 5, 1, 5}).add({4, 3, 5, 1})
672 .add({1, 5, 2, 5}).add({5, 3, 3, 2})
683 for (
int n=1024*16; n--; )
690 ts.
add({1}).add({2}).add({3}).finalize();
696 ts.
add({m+0,m+1,m+2}).add({m+4,m+1,m+3})
697 .add({m+2,m+3,m+0}).add({m+2,m+3,m+0})
698 .add({m+1,m+2,m+5}).add({m+2,m+3,m+0})
699 .add({m+3,m+6,m+5}).finalize();
705 ts.
add({M-0,M-1,M-2}).add({M-4,M-1,M-3})
706 .add({M-2,M-3,M-0}).add({M-2,M-3,M-0})
707 .add({M-1,M-2,M-5}).add({M-2,M-3,M-0})
708 .add({M-3,M-6,M-5}).finalize();
715 ts.
add({M-0,m+1,M-2}).add({m+4,M-1,M-3})
716 .add({m+2,M-3,m+0}).add({M-2,M-3,M-0})
724 for (
int i = 0; i < 10000; i++) {
726 for (
int j = 0; j < 7; j++) {
735 for (
int i = 0; i <= 64*6; i+=32)
752 for (
int i = 4; i--; ) tuple[i] = ass[i];
764 t.
add({ass[0],0,ass[1],ass[2]});
778 for (
int i = 9; i--; ) tuple[i+1] = ass[i];
783 t.
add({1,1,1,1,1,1,1,1,1,1});
784 t.
add({1,2,3,4,4,2,1,2,3,3});
Passing Boolean variables.
Specification of a DFA transition.
int o_state
output state Default constructor
Deterministic finite automaton (DFA)
Passing integer arguments.
Passing integer variables.
Regular expressions over integer values.
Reification specification.
Class represeting a set of tuples.
int tuples(void) const
Number of tuples.
TupleSet & add(const IntArgs &t)
Add tuple t to tuple set.
int * Tuple
Type of a tuple.
void finalize(void)
Finalize tuple set.
int arity(void) const
Arity of tuple set.
static Gecode::Support::RandomGenerator rand
Random number generator.
Base class for assignments
Generate all assignments.
Help class to create and register tests.
Create(void)
Perform creation and registration.
RandomTupleSetTest(const std::string &s, bool p, Gecode::IntSet d0, Gecode::TupleSet ts0)
Create and register test.
virtual Assignment * assignment(void) const
Create and register initial assignment.
Test with regular expression for distinct constraint
virtual void post(Gecode::Space &home, Gecode::IntVarArray &x)
Post constraint on x.
RegDistinct(void)
Create and register test.
virtual bool solution(const Assignment &x) const
Test whether x is solution
RegEmptyDFA(void)
Create and register test.
virtual void post(Gecode::Space &home, Gecode::IntVarArray &x)
Post constraint on x.
virtual bool solution(const Assignment &x) const
Test whether x is solution
Test for empty regular expression
virtual void post(Gecode::Space &home, Gecode::IntVarArray &x)
Post constraint on x.
RegEmptyREG(void)
Create and register test.
virtual bool solution(const Assignment &x) const
Test whether x is solution
virtual void post(Gecode::Space &home, Gecode::IntVarArray &x)
Post constraint on x.
virtual bool solution(const Assignment &x) const
Test whether x is solution
RegOpt(int n0)
Create and register test.
int n
DFA size characteristic.
Test with simple regular expression from Roland Yap
virtual bool solution(const Assignment &x) const
Test whether x is solution
virtual void post(Gecode::Space &home, Gecode::IntVarArray &x)
Post constraint on x.
RegRoland(int n)
Create and register test.
Test with simple regular expression and shared variables (uses unsharing)
virtual bool solution(const Assignment &x) const
Test whether x is solution
RegSharedA(void)
Create and register test.
virtual void post(Gecode::Space &home, Gecode::IntVarArray &x)
Post constraint on x.
Test with simple regular expression and shared variables (uses unsharing)
RegSharedB(void)
Create and register test.
virtual void post(Gecode::Space &home, Gecode::IntVarArray &x)
Post constraint on x.
virtual bool solution(const Assignment &x) const
Test whether x is solution
Test with simple regular expression and shared variables (uses unsharing)
virtual bool solution(const Assignment &x) const
Test whether x is solution
RegSharedC(void)
Create and register test.
virtual void post(Gecode::Space &home, Gecode::IntVarArray &x)
Post constraint on x.
Test with simple regular expression and shared variables (uses unsharing)
virtual void post(Gecode::Space &home, Gecode::IntVarArray &x)
Post constraint on x.
RegSharedD(void)
Create and register test.
virtual bool solution(const Assignment &x) const
Test whether x is solution
Test with simple regular expression
virtual bool solution(const Assignment &x) const
Test whether x is solution
virtual void post(Gecode::Space &home, Gecode::IntVarArray &x)
Post constraint on x.
RegSimpleA(void)
Create and register test.
Test with simple regular expression
virtual bool solution(const Assignment &x) const
Test whether x is solution
RegSimpleB(void)
Create and register test.
virtual void post(Gecode::Space &home, Gecode::IntVarArray &x)
Post constraint on x.
Test with simple regular expression
virtual void post(Gecode::Space &home, Gecode::IntVarArray &x)
Post constraint on x.
RegSimpleC(void)
Create and register test.
virtual bool solution(const Assignment &x) const
Test whether x is solution
bool pos
Whether the table is positive or negative.
virtual bool solution(const Assignment &x) const
Test whether x is solution
TupleSetBase(bool p)
Create and register test.
virtual void post(Gecode::Space &home, Gecode::IntVarArray &x, Gecode::Reify r)
Post reified constraint on x for r.
Gecode::TupleSet t
Simple test tupleset.
virtual void post(Gecode::Space &home, Gecode::IntVarArray &x)
Post constraint on x.
Gecode::TupleSet t
Tupleset used for testing.
virtual void post(Gecode::Space &home, Gecode::IntVarArray &x)
Post constraint on x.
virtual bool solution(const Assignment &x) const
Test whether x is solution
bool pos
Whether the table is positive or negative.
TupleSetBool(double prob, bool p)
Create and register test.
virtual void post(Gecode::Space &home, Gecode::IntVarArray &x, Gecode::Reify r)
Post reified constraint on x for r.
Test with large tuple set
bool pos
Whether the table is positive or negative.
virtual void post(Gecode::Space &home, Gecode::IntVarArray &x, Gecode::Reify r)
Post reified constraint on x for r.
virtual void post(Gecode::Space &home, Gecode::IntVarArray &x)
Post constraint on x.
Gecode::TupleSet t
Tupleset used for testing.
virtual bool solution(const Assignment &x) const
Test whether x is solution
TupleSetLarge(double prob, bool p)
Create and register test.
Help class to create and register tests with a fixed table size.
TupleSetTestSize(int size, bool pos)
Perform creation and registration.
virtual bool solution(const Assignment &x) const
Test whether x is solution
bool toDFA
Whether to validate dfa2tupleset.
virtual void post(Gecode::Space &home, Gecode::IntVarArray &x, Gecode::Reify r)
Post reified constraint on x for r.
Gecode::TupleSet ts
The tuple set to use.
bool pos
Whether the table is positive or negative.
TupleSetTest(const std::string &s, bool p, Gecode::IntSet d0, Gecode::TupleSet ts0, bool td)
Create and register test.
virtual void post(Gecode::Space &home, Gecode::IntVarArray &x)
Post constraint on x.
Generate random selection of assignments.
bool testsearch
Whether to perform search test.
Gecode::IntPropLevel ipl
Propagation level.
int arity
Number of variables.
static std::string str(Gecode::IntPropLevel ipl)
Map integer propagation level to string.
Gecode::IntSet dom
Domain of variables.
void extensional(Home home, const IntVarArgs &x, DFA d, IntPropLevel ipl=IPL_DEF)
Post domain consistent propagator for extensional constraint described by a DFA.
@ IPL_DOM
Domain propagation Options: basic versus advanced propagation.
const int min
Smallest allowed integer value.
const int max
Largest allowed integer value.
Gecode toplevel namespace
void channel(Home home, FloatVar x0, IntVar x1)
Post propagator for channeling a float and an integer variable .
void min(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
bool same(VarArgArray< Var > x, VarArgArray< Var > y)
Post propagator for SetVar SetOpType SetVar y
void unshare(Home home, IntVarArgs &x, IntPropLevel ipl=IPL_DEF)
Replace multiple variable occurences in x by fresh variables.
void max(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Post propagator for SetVar x
Tests for extensional (relation) constraints
Gecode::DFA tupleset2dfa(Gecode::TupleSet ts)
% Transform a TupleSet into a DFA
RegOpt ro7(static_cast< int >(USHRT_MAX))
RegOpt ro2(static_cast< int >(UCHAR_MAX-1))
Gecode::TupleSet randomTupleSet(int n, int min, int max, double prob)
RegOpt ro6(static_cast< int >(USHRT_MAX-1))
RegOpt ro3(static_cast< int >(UCHAR_MAX))
Testing finite domain integers.