rel-op.cpp
Go to the documentation of this file.
/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
/*
* Main authors:
* Guido Tack <tack@gecode.org>
*
* Copyright:
* Guido Tack, 2005
*
* 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 "test/set.hh"
using namespace Gecode;
namespace Test { namespace Set {
namespace RelOp {
static IntSet ds_22(-2,2);
static IntSet ds_12(-1,2);
class Rel : public SetTest {
private:
Gecode::SetOpType sot;
Gecode::SetRelType srt;
int share;
template<class I, class J>
bool
sol(I& i, J& j) const {
switch (srt) {
case SRT_EQ: return Iter::Ranges::equal(i,j);
case SRT_NQ: return !Iter::Ranges::equal(i,j);
case SRT_SUB: return Iter::Ranges::subset(i,j);
case SRT_SUP: return Iter::Ranges::subset(j,i);
case SRT_DISJ:
{
Gecode::Iter::Ranges::Inter<I,J> inter(i,j);
return !inter();
}
case SRT_CMPL:
{
Gecode::Set::RangesCompl<J> jc(j);
return Iter::Ranges::equal(i,jc);
}
default: GECODE_NEVER;
}
return false;
}
public:
Rel(Gecode::SetOpType sot0, Gecode::SetRelType srt0, int share0=0)
: SetTest("RelOp::"+str(sot0)+"::"+str(srt0)+"::S"+str(share0),
share0 == 0 ? 3 : 2,ds_22,false)
, sot(sot0), srt(srt0), share(share0) {}
bool solution(const SetAssignment& x) const {
int a=0, b=0, c=0;
switch (share) {
case 0: a=x[0]; b=x[1]; c=x[2]; break;
case 1: a=x[0]; b=x[0]; c=x[0]; break;
case 2: a=x[0]; b=x[0]; c=x[1]; break;
case 3: a=x[0]; b=x[1]; c=x[0]; break;
case 4: a=x[0]; b=x[1]; c=x[1]; break;
}
CountableSetRanges xr0(x.lub, a);
CountableSetRanges xr1(x.lub, b);
CountableSetRanges xr2(x.lub, c);
switch (sot) {
case SOT_UNION:
{
Iter::Ranges::Union<CountableSetRanges, CountableSetRanges>
u(xr0,xr1);
return sol(u,xr2);
}
break;
case SOT_DUNION:
{
Iter::Ranges::Inter<CountableSetRanges, CountableSetRanges>
inter(xr0,xr1);
if (inter())
return false;
Iter::Ranges::Union<CountableSetRanges, CountableSetRanges>
u(xr0,xr1);
return sol(u,xr2);
}
break;
case SOT_INTER:
{
Iter::Ranges::Inter<CountableSetRanges, CountableSetRanges>
u(xr0,xr1);
return sol(u,xr2);
}
break;
case SOT_MINUS:
{
Iter::Ranges::Diff<CountableSetRanges, CountableSetRanges>
u(xr0,xr1);
return sol(u,xr2);
}
break;
default: GECODE_NEVER;
}
GECODE_NEVER;
return false;
}
void post(Space& home, SetVarArray& x, IntVarArray&) {
SetVar a,b,c;
switch (share) {
case 0: a=x[0]; b=x[1]; c=x[2]; break;
case 1: a=x[0]; b=x[0]; c=x[0]; break;
case 2: a=x[0]; b=x[0]; c=x[1]; break;
case 3: a=x[0]; b=x[1]; c=x[0]; break;
case 4: a=x[0]; b=x[1]; c=x[1]; break;
}
Gecode::rel(home, a, sot, b, srt, c);
}
};
class Create {
public:
Create(void) {
using namespace Gecode;
for (SetRelTypes srts; srts(); ++srts) {
for (SetOpTypes sots; sots(); ++sots) {
for (int i=0; i<=4; i++) {
(void) new Rel(sots.sot(),srts.srt(),i);
}
}
}
}
};
Create c;
class RelN : public SetTest {
private:
Gecode::SetOpType sot;
int n;
int shared;
bool withConst;
IntSet is;
public:
RelN(Gecode::SetOpType sot0, int n0, int shared0, bool withConst0)
: SetTest("RelOp::N::"+str(sot0)+"::"+str(n0)+"::S"+str(shared0)+
"::C"+str(withConst0 ? 1 : 0),
shared0 == 0 ? n0+1 : (shared0 <= 2 ? 3 : 2),ds_12,false)
, sot(sot0), n(n0), shared(shared0), withConst(withConst0)
, is(0,1) {
}
bool solution(const SetAssignment& x) const {
int realN = shared == 0 ? n : 3;
CountableSetRanges* isrs = new CountableSetRanges[realN];
switch (shared) {
case 0:
for (int i=realN; i--; )
isrs[i].init(x.lub, x[i]);
break;
case 1:
isrs[0].init(x.lub, x[0]);
isrs[1].init(x.lub, x[0]);
isrs[2].init(x.lub, x[1]);
break;
case 2:
isrs[0].init(x.lub, x[0]);
isrs[1].init(x.lub, x[1]);
isrs[2].init(x.lub, x[2]);
break;
case 3:
isrs[0].init(x.lub, x[0]);
isrs[1].init(x.lub, x[1]);
isrs[2].init(x.lub, x[0]);
break;
default:
GECODE_NEVER;
}
int result = shared == 0 ? x.size() - 1 : (shared <= 2 ? 2 : 0);
CountableSetRanges xnr(x.lub, x[result]);
switch (sot) {
case SOT_DUNION:
{
if (shared == 1 && (isrs[0]() || isrs[1]())) {
delete[] isrs; return false;
}
if (shared == 3 && (isrs[0]() || isrs[2]())) {
delete[] isrs; return false;
}
unsigned int cardSum = 0;
if (shared == 1 || shared == 3) {
CountableSetRanges x1r(x.lub, x[1]);
cardSum = Iter::Ranges::size(x1r);
} else {
for (int i=0; i<realN; i++) {
CountableSetRanges xir(x.lub, x[i]);
cardSum += Iter::Ranges::size(xir);
}
}
if (withConst)
cardSum += 2;
CountableSetRanges xnr2(x.lub, x[result]);
if (cardSum != Iter::Ranges::size(xnr2)) {
delete[] isrs; return false;
}
}
// fall through to union case
case SOT_UNION:
{
bool eq;
if (withConst) {
Region r;
Iter::Ranges::NaryUnion u(r, isrs, realN);
IntSetRanges isr(is);
Iter::Ranges::Union<IntSetRanges,
Iter::Ranges::NaryUnion> uu(isr, u);
eq = Iter::Ranges::equal(uu, xnr);
} else {
Region r;
Iter::Ranges::NaryUnion u(r, isrs, realN);
eq = Iter::Ranges::equal(u, xnr);
}
delete [] isrs;
return eq;
}
case SOT_INTER:
{
if (withConst) {
bool eq;
{
Region r;
Iter::Ranges::NaryInter u(r, isrs, realN);
IntSetRanges isr(is);
Iter::Ranges::Inter<IntSetRanges,
Iter::Ranges::NaryInter> uu(isr, u);
eq = (realN == 0 ? Iter::Ranges::equal(isr, xnr) :
Iter::Ranges::equal(uu, xnr));
delete [] isrs;
}
return eq;
} else {
if (realN == 0) {
bool ret =
Iter::Ranges::size(xnr) == Gecode::Set::Limits::card;
delete [] isrs;
return ret;
} else {
bool eq;
{
Region r;
Iter::Ranges::NaryInter u(r,isrs, realN);
eq = Iter::Ranges::equal(u, xnr);
}
delete [] isrs;
return eq;
}
}
}
default:
GECODE_NEVER;
}
GECODE_NEVER;
return false;
}
void post(Space& home, SetVarArray& x, IntVarArray&) {
int size = shared == 0 ? x.size()-1 : 3;
SetVarArgs xs(size);
SetVar xn;
switch (shared) {
case 0:
for (int i=x.size()-1; i--;)
xs[i]=x[i];
xn = x[x.size()-1];
break;
case 1:
xs[0] = x[0]; xs[1] = x[0]; xs[2] = x[1]; xn = x[2];
break;
case 2:
xs[0] = x[0]; xs[1] = x[1]; xs[2] = x[2]; xn = x[2];
break;
case 3:
xs[0] = x[0]; xs[1] = x[1]; xs[2] = x[0]; xn = x[0];
break;
default:
GECODE_NEVER;
break;
}
if (!withConst)
Gecode::rel(home, sot, xs, xn);
else
Gecode::rel(home, sot, xs, is, xn);
}
};
class CreateN {
public:
CreateN(void) {
for (int wc=0; wc<=1; wc++) {
for (int i=0; i<=3; i++) {
(void) new RelN(Gecode::SOT_UNION, i, 0, wc);
(void) new RelN(Gecode::SOT_DUNION, i, 0, wc);
(void) new RelN(Gecode::SOT_INTER, i, 0, wc);
if (i>0) {
(void) new RelN(Gecode::SOT_UNION, 0, i, wc);
(void) new RelN(Gecode::SOT_DUNION, 0, i, wc);
(void) new RelN(Gecode::SOT_INTER, 0, i, wc);
}
}
}
}
};
CreateN cn;
class RelIntN : public SetTest {
private:
Gecode::SetOpType sot;
int n;
bool withConst;
IntSet is;
public:
RelIntN(Gecode::SetOpType sot0, int n0, bool withConst0)
: SetTest("RelOp::IntN::"+str(sot0)+"::"+str(n0)+
"::C"+str(withConst0 ? 1 : 0),
1,ds_12,false,n0)
, sot(sot0), n(n0), withConst(withConst0)
, is(0,1) {
}
bool solution(const SetAssignment& x) const {
int* isrs = new int[n];
for (int i=0; i<n; i++)
isrs[i] = x.ints()[i];
IntSet iss(isrs,n);
CountableSetRanges xnr(x.lub, x[0]);
switch (sot) {
case SOT_DUNION:
{
IntSetRanges issr(iss);
unsigned int cardSum = Iter::Ranges::size(issr);
if (cardSum != static_cast<unsigned int>(n)) {
delete[] isrs;
return false;
}
if (withConst) {
IntSetRanges isr(is);
cardSum += Iter::Ranges::size(isr);
}
CountableSetRanges xnr2(x.lub, x[0]);
if (cardSum != Iter::Ranges::size(xnr2)) {
delete[] isrs;
return false;
}
}
// fall through to union case
case SOT_UNION:
{
if (withConst) {
IntSetRanges issr(iss);
IntSetRanges isr(is);
Iter::Ranges::Union<IntSetRanges,IntSetRanges > uu(isr, issr);
delete[] isrs;
return Iter::Ranges::equal(uu, xnr);
} else {
IntSetRanges issr(iss);
delete[] isrs;
return Iter::Ranges::equal(issr, xnr);
}
}
case SOT_INTER:
{
bool allEqual = true;
for (int i=1; i<n; i++) {
if (isrs[i] != isrs[0]) {
allEqual = false;
break;
}
}
if (withConst) {
if (allEqual) {
if (n == 0) {
IntSetRanges isr(is);
delete[] isrs;
return Iter::Ranges::equal(isr, xnr);
} else {
Iter::Ranges::Singleton s(isrs[0],isrs[0]);
IntSetRanges isr(is);
Iter::Ranges::Inter<IntSetRanges,Iter::Ranges::Singleton>
uu(isr, s);
delete[] isrs;
return Iter::Ranges::equal(uu, xnr);
}
} else {
delete[] isrs;
return Iter::Ranges::size(xnr) == 0;
}
} else {
if (allEqual) {
if (n == 0) {
delete[] isrs;
return Iter::Ranges::size(xnr) == Gecode::Set::Limits::card;
} else {
Iter::Ranges::Singleton s(isrs[0],isrs[0]);
delete[] isrs;
return Iter::Ranges::equal(s, xnr);
}
} else {
delete[] isrs;
return Iter::Ranges::size(xnr) == 0;
}
}
}
default:
GECODE_NEVER;
}
GECODE_NEVER;
return false;
}
void post(Space& home, SetVarArray& x, IntVarArray& y) {
if (!withConst)
Gecode::rel(home, sot, y, x[0]);
else
Gecode::rel(home, sot, y, is, x[0]);
}
};
class CreateIntN {
public:
CreateIntN(void) {
for (int wc=0; wc<=1; wc++) {
for (int i=0; i<=3; i++) {
(void) new RelIntN(Gecode::SOT_UNION, i, wc);
(void) new RelIntN(Gecode::SOT_DUNION, i, wc);
(void) new RelIntN(Gecode::SOT_INTER, i, wc);
}
}
}
};
CreateIntN intcn;
}}}
// STATISTICS: test-set
Gecode::IntSetRanges
Range iterator for integer sets.
Definition int.hh:292
Gecode::IntSet
Integer sets.
Definition int.hh:174
Gecode::IntVarArray
Integer variable array.
Definition int.hh:763
Gecode::Iter::Ranges::Diff
Range iterator for computing set difference.
Definition ranges-diff.hpp:43
Gecode::Iter::Ranges::Inter
Range iterator for computing intersection (binary).
Definition ranges-inter.hpp:44
Gecode::Iter::Ranges::NaryInter
Range iterator for intersection of iterators.
Definition ranges-inter.hpp:74
Gecode::Iter::Ranges::NaryUnion
Range iterator for union of iterators.
Definition ranges-union.hpp:74
Gecode::Iter::Ranges::Singleton
Range iterator for singleton range.
Definition ranges-singleton.hpp:42
Gecode::Iter::Ranges::Union
Range iterator for computing union (binary).
Definition ranges-union.hpp:44
Gecode::SetVarArgs
Passing set variables.
Definition set.hh:488
Gecode::SetVarArray
Set variable array
Definition set.hh:570
Gecode::SetVar
Set variables
Definition set.hh:127
Gecode::Set::RangesCompl
A complement iterator spezialized for the BndSet limits.
Definition var-imp.hpp:293
Gecode::Space
Computation spaces.
Definition core.hpp:1742
Gecode::VarArray::size
int size(void) const
Return size of array (number of elements).
Definition array.hpp:926
Test::Region
Test for Region memory area
Definition region.cpp:42
Test::Set::CountableSetRanges
Range iterator producing subsets of an IntSet.
Definition set.hh:99
Test::Set::CountableSetRanges::init
void init(const Gecode::IntSet &d, int cur)
Initialize with set d0 and bit-pattern cur0.
Definition set.hh:111
Test::Set::RelOp::CreateIntN
Help class to create and register tests.
Definition rel-op.cpp:477
Test::Set::RelOp::CreateIntN::CreateIntN
CreateIntN(void)
Perform creation and registration.
Definition rel-op.cpp:480
Test::Set::RelOp::CreateN
Help class to create and register tests.
Definition rel-op.cpp:337
Test::Set::RelOp::CreateN::CreateN
CreateN(void)
Perform creation and registration.
Definition rel-op.cpp:340
Test::Set::RelOp::Create
Help class to create and register tests.
Definition rel-op.cpp:154
Test::Set::RelOp::Create::Create
Create(void)
Perform creation and registration.
Definition rel-op.cpp:157
Test::Set::RelOp::RelIntN
Test for n-ary partition constraint
Definition rel-op.cpp:360
Test::Set::RelOp::RelIntN::solution
bool solution(const SetAssignment &x) const
Test whether x is solution
Definition rel-op.cpp:376
Test::Set::RelOp::RelIntN::RelIntN
RelIntN(Gecode::SetOpType sot0, int n0, bool withConst0)
Create and register test.
Definition rel-op.cpp:368
Test::Set::RelOp::RelIntN::post
void post(Space &home, SetVarArray &x, IntVarArray &y)
Post constraint on x.
Definition rel-op.cpp:468
Test::Set::RelOp::RelN
Test for n-ary partition constraint
Definition rel-op.cpp:172
Test::Set::RelOp::RelN::post
void post(Space &home, SetVarArray &x, IntVarArray &)
Post constraint on x.
Definition rel-op.cpp:306
Test::Set::RelOp::RelN::solution
bool solution(const SetAssignment &x) const
Test whether x is solution
Definition rel-op.cpp:189
Test::Set::RelOp::RelN::RelN
RelN(Gecode::SetOpType sot0, int n0, int shared0, bool withConst0)
Create and register test.
Definition rel-op.cpp:181
Test::Set::RelOp::Rel
Test for ternary relation constraint
Definition rel-op.cpp:53
Test::Set::RelOp::Rel::solution
bool solution(const SetAssignment &x) const
Test whether x is solution
Definition rel-op.cpp:89
Test::Set::RelOp::Rel::Rel
Rel(Gecode::SetOpType sot0, Gecode::SetRelType srt0, int share0=0)
Create and register test.
Definition rel-op.cpp:84
Test::Set::RelOp::Rel::post
void post(Space &home, SetVarArray &x, IntVarArray &)
Post constraint on x.
Definition rel-op.cpp:140
Test::Set::SetAssignment
Generate all set assignments.
Definition set.hh:142
Test::Set::SetAssignment::ints
const Test::Int::Assignment & ints(void) const
Return assignment for integer variables.
Definition set.hh:171
Test::Set::SetAssignment::size
int size(void) const
Return arity.
Definition set.hh:173
Test::Set::SetAssignment::lub
Gecode::IntSet lub
The common superset for all domains.
Definition set.hh:154
Test::Set::SetOpTypes
Iterator for Boolean operation types.
Definition set.hh:352
Test::Set::SetRelTypes
Iterator for set relation types.
Definition set.hh:334
Test::Set::SetTest::str
static std::string str(Gecode::SetRelType srt)
Map set relation to string.
Definition set.hpp:46
Test::Set::SetTest::SetTest
SetTest(const std::string &s, int a, const Gecode::IntSet &d, bool r=false, int w=0)
Constructor.
Definition set.hh:304
Gecode::rel
void rel(Home home, FloatVar x0, FloatRelType frt, FloatVar x1)
Post propagator for .
Definition rel.cpp:68
Gecode::SetOpType
SetOpType
Common operations for sets.
Definition set.hh:660
Gecode::SetRelType
SetRelType
Common relation types for sets.
Definition set.hh:643
Gecode::SOT_MINUS
@ SOT_MINUS
Difference.
Definition set.hh:664
Gecode::SOT_DUNION
@ SOT_DUNION
Disjoint union.
Definition set.hh:662
Gecode::SOT_UNION
@ SOT_UNION
Union.
Definition set.hh:661
Gecode::SOT_INTER
@ SOT_INTER
Intersection
Definition set.hh:663
Gecode::SRT_CMPL
@ SRT_CMPL
Complement.
Definition set.hh:649
Gecode::SRT_NQ
@ SRT_NQ
Disequality ( ).
Definition set.hh:645
Gecode::SRT_EQ
@ SRT_EQ
Equality ( ).
Definition set.hh:644
Gecode::SRT_SUP
@ SRT_SUP
Superset ( ).
Definition set.hh:647
Gecode::SRT_DISJ
@ SRT_DISJ
Disjoint ( ).
Definition set.hh:648
Gecode::SRT_SUB
@ SRT_SUB
Subset ( ).
Definition set.hh:646
Gecode::Iter::Ranges::subset
bool subset(I &i, J &j)
Check whether range iterator i is subset of range iterator j.
Definition ranges-operations.hpp:97
Gecode::Iter::Ranges::size
unsigned int size(I &i)
Size of all ranges of range iterator i.
Definition ranges-operations.hpp:74
Gecode::Iter::Ranges::equal
bool equal(I &i, J &j)
Check whether range iterators i and j are equal.
Definition ranges-operations.hpp:84
Gecode::Set::Limits::card
const unsigned int card
Maximum cardinality of an integer set.
Definition set.hh:101
Gecode
Gecode toplevel namespace
Gecode::inter
SetExpr inter(const SetVarArgs &)
Intersection of set variables.
Definition set-expr.cpp:696
Test::Set::RelOp
Tests for relation/operation constraints
Definition rel-op.cpp:41
Test::Set::RelOp::intcn
CreateIntN intcn
Definition rel-op.cpp:491
Test::Set::RelOp::c
Create c
Definition rel-op.cpp:169
Test::Set::RelOp::cn
CreateN cn
Definition rel-op.cpp:357
Test::Set
Testing finite sets.
Definition set.cpp:42
Test
General test support.
Definition afc.cpp:39
Test::r
Region r
Definition region.cpp:65
GECODE_NEVER
#define GECODE_NEVER
Assert that this command is never executed.
Definition macros.hpp:56
set.hh