element.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 <gecode/minimodel.hh>
#include "test/set.hh"
using namespace Gecode;
namespace Test { namespace Set {
namespace Element {
static IntSet ds_12(-1,2);
static IntSet ds_13(-1,3);
class ElementUnion : public SetTest {
public:
ElementUnion(const char* t)
: SetTest(t,5,ds_12,false) {}
virtual bool solution(const SetAssignment& x) const {
int selected = 0;
for (CountableSetValues sel2(x.lub, x[3]); sel2();
++sel2, selected++) {}
CountableSetValues x4v(x.lub, x[4]);
if (selected==0)
return !x4v();
CountableSetRanges* sel = new CountableSetRanges[selected];
CountableSetValues selector(x.lub, x[3]);
for (int i=selected; i--;++selector) {
if (selector.val()>=3 || selector.val()<0) {
delete[] sel;
return false;
}
sel[i].init(x.lub, x[selector.val()]);
}
bool ret;
{
Region r;
Iter::Ranges::NaryUnion u(r, sel, selected);
CountableSetRanges z(x.lub, x[4]);
ret = Iter::Ranges::equal(u, z);
}
delete[] sel;
return ret;
}
virtual void post(Space& home, SetVarArray& x, IntVarArray&) {
SetVarArgs xs(x.size()-2);
for (int i=x.size()-2; i--;)
xs[i]=x[i];
Gecode::element(home, SOT_UNION, xs, x[x.size()-2], x[x.size()-1]);
}
};
ElementUnion _elementunion("Element::Union");
class ElementUnionConst : public SetTest {
private:
const IntSet i0;
const IntSet i1;
const IntSet i2;
public:
ElementUnionConst(const char* t)
: SetTest(t,2,ds_13,false), i0(-3,-3), i1(-1,1), i2(0,2) {}
virtual bool solution(const SetAssignment& x) const {
int selected = 0;
for (CountableSetValues sel2(x.lub, x[0]); sel2();
++sel2, selected++) {}
CountableSetValues x4v(x.lub, x[1]);
if (selected==0)
return !x4v();
IntSet iss[] = {i0, i1, i2};
IntSetRanges* sel = new IntSetRanges[selected];
CountableSetValues selector(x.lub, x[0]);
for (int i=selected; i--;++selector) {
if (selector.val()>=3 || selector.val()<0) {
delete[] sel;
return false;
}
sel[i].init(iss[selector.val()]);
}
bool ret;
{
Region r;
Iter::Ranges::NaryUnion u(r, sel, selected);
CountableSetRanges z(x.lub, x[1]);
ret = Iter::Ranges::equal(u, z);
}
delete[] sel;
return ret;
}
virtual void post(Space& home, SetVarArray& x, IntVarArray&) {
IntSetArgs xs(3);
xs[0] = i0; xs[1] = i1; xs[2] = i2;
Gecode::element(home, SOT_UNION, xs, x[0], x[1]);
}
};
ElementUnionConst _elementunionconst("Element::UnionConst");
class ElementInter : public SetTest {
public:
ElementInter(const char* t)
: SetTest(t,5,ds_12,false) {}
virtual bool solution(const SetAssignment& x) const {
int selected = 0;
for (CountableSetValues sel2(x.lub, x[3]); sel2();
++sel2, selected++) {}
CountableSetRanges x4r(x.lub, x[4]);
if (selected==0)
return Iter::Ranges::size(x4r)==Gecode::Set::Limits::card;
CountableSetRanges* sel = new CountableSetRanges[selected];
CountableSetValues selector(x.lub, x[3]);
for (int i=selected; i--;++selector) {
if (selector.val()>=3 || selector.val()<0) {
delete[] sel;
return false;
}
sel[i].init(x.lub, x[selector.val()]);
}
bool ret;
{
Region r;
Iter::Ranges::NaryInter u(r, sel, selected);
CountableSetRanges z(x.lub, x[4]);
ret = Iter::Ranges::equal(u, z);
}
delete [] sel;
return ret;
}
virtual void post(Space& home, SetVarArray& x, IntVarArray&) {
SetVarArgs xs(x.size()-2);
for (int i=x.size()-2; i--;)
xs[i]=x[i];
Gecode::element(home, SOT_INTER, xs, x[x.size()-2], x[x.size()-1]);
}
};
ElementInter _elementinter("Element::Inter");
class ElementInterIn : public SetTest {
public:
ElementInterIn(const char* t)
: SetTest(t,5,ds_12,false) {}
virtual bool solution(const SetAssignment& x) const {
int selected = 0;
for (CountableSetValues sel2(x.lub, x[3]); sel2();
++sel2, selected++) {}
CountableSetRanges x4r(x.lub, x[4]);
if (selected==0)
return Iter::Ranges::size(x4r)==4;
CountableSetRanges* sel = new CountableSetRanges[selected];
CountableSetValues selector(x.lub, x[3]);
for (int i=selected; i--;++selector) {
if (selector.val()>=3 || selector.val()<0) {
delete[] sel;
return false;
}
sel[i].init(x.lub, x[selector.val()]);
}
bool ret;
{
Region r;
Iter::Ranges::NaryInter u(r,sel, selected);
CountableSetRanges z(x.lub, x[4]);
ret = Iter::Ranges::equal(u, z);
}
delete [] sel;
return ret;
}
virtual void post(Space& home, SetVarArray& x, IntVarArray&) {
SetVarArgs xs(x.size()-2);
for (int i=x.size()-2; i--;)
xs[i]=x[i];
Gecode::element(home, SOT_INTER, xs, x[x.size()-2], x[x.size()-1],
ds_12);
}
};
ElementInterIn _elementinterin("Element::InterIn");
class ElementDisjoint : public SetTest {
public:
ElementDisjoint(const char* t)
: SetTest(t,5,ds_12,false) {}
virtual bool solution(const SetAssignment& x) const {
int selected = 0;
for (CountableSetValues sel2(x.lub, x[3]); sel2();
++sel2, selected++) {
if (sel2.val() < 0)
return false;
}
CountableSetValues x4v(x.lub, x[4]);
if (selected == 0)
return !x4v();
CountableSetRanges* sel = new CountableSetRanges[selected];
CountableSetValues selector(x.lub, x[3]);
unsigned int cardsum = 0;
for (int i=selected; i--;++selector) {
if (selector.val()>=3 || selector.val()<0) {
delete[] sel;
return false;
}
sel[i].init(x.lub, x[selector.val()]);
CountableSetRanges xicard(x.lub, x[selector.val()]);
cardsum += Iter::Ranges::size(xicard);
}
bool ret;
{
Region r;
Iter::Ranges::NaryUnion u(r, sel, selected);
ret = Iter::Ranges::size(u) == cardsum;
u.reset();
CountableSetRanges z(x.lub, x[4]);
ret &= Iter::Ranges::equal(u, z);
}
delete[] sel;
return ret;
}
virtual void post(Space& home, SetVarArray& x, IntVarArray&) {
SetVarArgs xs(x.size()-2);
for (int i=x.size()-2; i--;)
xs[i]=x[i];
Gecode::element(home, SOT_DUNION, xs, x[x.size()-2], x[x.size()-1]);
}
};
ElementDisjoint _elementdisjoint("Element::Disjoint");
class ElementSet : public SetTest {
public:
ElementSet(const char* t)
: SetTest(t,4,ds_12,false,true) {}
virtual bool solution(const SetAssignment& x) const {
if (x.intval() < 0 || x.intval() > 2)
return false;
CountableSetRanges z(x.lub, x[3]);
CountableSetRanges y(x.lub, x[x.intval()]);
return Iter::Ranges::equal(y, z);
}
virtual void post(Space& home, SetVarArray& x, IntVarArray& y) {
SetVarArgs xs(x.size()-1);
for (int i=x.size()-1; i--;)
xs[i]=x[i];
Gecode::element(home, xs, y[0], x[x.size()-1]);
}
};
ElementSet _elementset("Element::Set");
class ElementSetConst : public SetTest {
private:
const IntSet i0;
const IntSet i1;
const IntSet i2;
public:
ElementSetConst(const char* t)
: SetTest(t,1,ds_13,false,true), i0(-3,-3), i1(-1,1), i2(0,2) {}
virtual bool solution(const SetAssignment& x) const {
if (x.intval() < 0 || x.intval() > 2)
return false;
CountableSetRanges xr(x.lub, x[0]);
IntSet iss[] = {i0, i1, i2};
IntSetRanges isr(iss[x.intval()]);
return Iter::Ranges::equal(xr, isr);
}
virtual void post(Space& home, SetVarArray& x, IntVarArray& y) {
IntSetArgs xs(3);
xs[0] = i0; xs[1] = i1; xs[2] = i2;
Gecode::element(home, xs, y[0], x[0]);
}
};
ElementSetConst _elementsetconst("Element::SetConst");
class MatrixIntSet : public SetTest {
protected:
Gecode::IntSetArgs tm;
public:
MatrixIntSet(void)
: SetTest("Element::Matrix::IntSet",1,IntSet(0,3),false,2),
tm(4) {
tm[0]=IntSet(0,0); tm[1]=IntSet(1,1);
tm[2]=IntSet(2,2); tm[3]=IntSet(3,3);
}
virtual bool solution(const SetAssignment& x) const {
// Get integer assignment
const Int::Assignment& y = x.ints();
// x-coordinate: y[0], y-coordinate: y[1], result: x[0]
using namespace Gecode;
if ((y[0] > 1) || (y[1] > 1))
return false;
Matrix<IntSetArgs> m(tm,2,2);
IntSetRanges a(m(y[0],y[1]));
CountableSetRanges b(x.lub, x[0]);
return Iter::Ranges::equal(a,b);
}
virtual void post(Gecode::Space& home, Gecode::SetVarArray& x,
Gecode::IntVarArray& y) {
// x-coordinate: x[0], y-coordinate: x[1], result: x[2]
using namespace Gecode;
Matrix<IntSetArgs> m(tm,2,2);
element(home, m, y[0], y[1], x[0]);
}
};
MatrixIntSet _emis;
}}}
// STATISTICS: test-set
Gecode::IntSetRanges
Range iterator for integer sets.
Definition int.hh:292
Gecode::IntSetRanges::init
void init(const IntSet &s)
Initialize with ranges for set s.
Definition int-set-1.hpp:237
Gecode::IntSet
Integer sets.
Definition int.hh:174
Gecode::IntVarArray
Integer variable array.
Definition int.hh:763
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::RangeListIter::reset
void reset(void)
Reset iterator to start.
Definition ranges-list.hpp:240
Gecode::Matrix
Matrix-interface for arrays.
Definition minimodel.hh:2161
Gecode::SetVarArgs
Passing set variables.
Definition set.hh:488
Gecode::SetVarArray
Set variable array
Definition set.hh:570
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::Int::Assignment
Base class for assignments
Definition int.hh:59
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::CountableSetValues
Value iterator producing subsets of an IntSet.
Definition set.hh:60
Test::Set::CountableSetValues::val
int val(void) const
Return current value.
Definition set.hh:94
Test::Set::Element::ElementDisjoint
Test for ElementDisjoint constraint
Definition element.cpp:238
Test::Set::Element::ElementDisjoint::solution
virtual bool solution(const SetAssignment &x) const
Test whether x is solution
Definition element.cpp:244
Test::Set::Element::ElementDisjoint::post
virtual void post(Space &home, SetVarArray &x, IntVarArray &)
Post constraint on x.
Definition element.cpp:280
Test::Set::Element::ElementDisjoint::ElementDisjoint
ElementDisjoint(const char *t)
Create and register test.
Definition element.cpp:241
Test::Set::Element::ElementInterIn
Test for ElementInter constraint
Definition element.cpp:193
Test::Set::Element::ElementInterIn::ElementInterIn
ElementInterIn(const char *t)
Create and register test.
Definition element.cpp:196
Test::Set::Element::ElementInterIn::post
virtual void post(Space &home, SetVarArray &x, IntVarArray &)
Post constraint on x.
Definition element.cpp:227
Test::Set::Element::ElementInterIn::solution
virtual bool solution(const SetAssignment &x) const
Test whether x is solution
Definition element.cpp:199
Test::Set::Element::ElementInter
Test for ElementInter constraint
Definition element.cpp:149
Test::Set::Element::ElementInter::solution
virtual bool solution(const SetAssignment &x) const
Test whether x is solution
Definition element.cpp:155
Test::Set::Element::ElementInter::ElementInter
ElementInter(const char *t)
Create and register test.
Definition element.cpp:152
Test::Set::Element::ElementInter::post
virtual void post(Space &home, SetVarArray &x, IntVarArray &)
Post constraint on x.
Definition element.cpp:183
Test::Set::Element::ElementSetConst
Test for ElementSetConst constraint
Definition element.cpp:314
Test::Set::Element::ElementSetConst::solution
virtual bool solution(const SetAssignment &x) const
Test whether x is solution
Definition element.cpp:324
Test::Set::Element::ElementSetConst::post
virtual void post(Space &home, SetVarArray &x, IntVarArray &y)
Post constraint on x.
Definition element.cpp:333
Test::Set::Element::ElementSetConst::ElementSetConst
ElementSetConst(const char *t)
Create and register test.
Definition element.cpp:321
Test::Set::Element::ElementSet
Test for ElementSet constraint
Definition element.cpp:290
Test::Set::Element::ElementSet::ElementSet
ElementSet(const char *t)
Create and register test.
Definition element.cpp:293
Test::Set::Element::ElementSet::post
virtual void post(Space &home, SetVarArray &x, IntVarArray &y)
Post constraint on x.
Definition element.cpp:304
Test::Set::Element::ElementSet::solution
virtual bool solution(const SetAssignment &x) const
Test whether x is solution
Definition element.cpp:296
Test::Set::Element::ElementUnionConst
Test for ElementUnionConst constraint
Definition element.cpp:100
Test::Set::Element::ElementUnionConst::solution
virtual bool solution(const SetAssignment &x) const
Test whether x is solution
Definition element.cpp:110
Test::Set::Element::ElementUnionConst::ElementUnionConst
ElementUnionConst(const char *t)
Create and register test.
Definition element.cpp:107
Test::Set::Element::ElementUnionConst::post
virtual void post(Space &home, SetVarArray &x, IntVarArray &)
Post constraint on x.
Definition element.cpp:140
Test::Set::Element::ElementUnion
Test for ElementUnion constraint
Definition element.cpp:55
Test::Set::Element::ElementUnion::solution
virtual bool solution(const SetAssignment &x) const
Test whether x is solution
Definition element.cpp:61
Test::Set::Element::ElementUnion::post
virtual void post(Space &home, SetVarArray &x, IntVarArray &)
Post constraint on x.
Definition element.cpp:90
Test::Set::Element::ElementUnion::ElementUnion
ElementUnion(const char *t)
Create and register test.
Definition element.cpp:58
Test::Set::Element::MatrixIntSet
Test for matrix element with integer set array and set variable
Definition element.cpp:342
Test::Set::Element::MatrixIntSet::tm
Gecode::IntSetArgs tm
Array for test matrix.
Definition element.cpp:345
Test::Set::Element::MatrixIntSet::post
virtual void post(Gecode::Space &home, Gecode::SetVarArray &x, Gecode::IntVarArray &y)
Post constraint on x and y.
Definition element.cpp:368
Test::Set::Element::MatrixIntSet::MatrixIntSet
MatrixIntSet(void)
Create and register test.
Definition element.cpp:348
Test::Set::Element::MatrixIntSet::solution
virtual bool solution(const SetAssignment &x) const
Test whether x is solution
Definition element.cpp:355
Test::Set::SetAssignment
Generate all set assignments.
Definition set.hh:142
Test::Set::SetAssignment::intval
int intval(void) const
Return value for first integer variable.
Definition set.hh:169
Test::Set::SetAssignment::ints
const Test::Int::Assignment & ints(void) const
Return assignment for integer variables.
Definition set.hh:171
Test::Set::SetAssignment::lub
Gecode::IntSet lub
The common superset for all domains.
Definition set.hh:154
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::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
minimodel.hh
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::IntSetArgs
ArgArray< IntSet > IntSetArgs
Passing set arguments.
Definition int.hh:619
Gecode::element
void element(Home home, IntSharedArray n, IntVar x0, IntVar x1, IntPropLevel ipl=IPL_DEF)
Post domain consistent propagator for .
Definition element.cpp:39
Test::Set::Element
Tests for set element constraints
Definition element.cpp:43
Test::Set::Element::_elementinter
ElementInter _elementinter("Element::Inter")
Test::Set::Element::_elementinterin
ElementInterIn _elementinterin("Element::InterIn")
Test::Set::Element::_elementsetconst
ElementSetConst _elementsetconst("Element::SetConst")
Test::Set::Element::_elementunionconst
ElementUnionConst _elementunionconst("Element::UnionConst")
Test::Set::Element::_emis
MatrixIntSet _emis
Definition element.cpp:377
Test::Set::Element::_elementdisjoint
ElementDisjoint _elementdisjoint("Element::Disjoint")
Test::Set::Element::_elementunion
ElementUnion _elementunion("Element::Union")
Test::Set::Element::_elementset
ElementSet _elementset("Element::Set")
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
set.hh