gcc.cpp
Go to the documentation of this file.
/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
/*
* Main authors:
* Patrick Pekczynski <pekczynski@ps.uni-sb.de>
*
* Contributing authors:
* Christian Schulte <schulte@gecode.org>
*
* Copyright:
* Patrick Pekczynski, 2005
* Christian Schulte, 2007
*
* 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/int.hh"
namespace Test { namespace Int {
namespace GCC {
class IntAllMinMax : public Test {
public:
IntAllMinMax(Gecode::IntPropLevel ipl)
: Test("GCC::Int::All::MinMax::"+str(ipl),4,-1,3,false,ipl) {}
virtual bool solution(const Assignment& x) const {
int n[5];
for (int i=5; i--; )
n[i]=0;
for (int i=x.size(); i--; )
n[x[i]+1]++;
if (n[2] > 0)
return false;
for (int i=5; i--;)
if (n[i]>2)
return false;
return true;
}
virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
using namespace Gecode;
IntArgs values(5);
IntSet fixed(0,2);
IntSetArgs cards(5);
for (int i=0; i<5; i++) {
values[i] = i-1; cards[i] = fixed;
}
cards[2] = IntSet(0,0);
count(home, x, cards, values, ipl);
}
};
class IntAllMinMaxDef : public Test {
public:
IntAllMinMaxDef(Gecode::IntPropLevel ipl)
: Test("GCC::Int::All::MinMaxDef::"+str(ipl),4,0,3,false,ipl) {}
virtual bool solution(const Assignment& x) const {
int n[4];
for (int i=4; i--; )
n[i]=0;
for (int i=x.size(); i--; )
n[x[i]]++;
if (n[2] > 0)
return false;
for (int i=4; i--;)
if (n[i]>2)
return false;
return true;
}
virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
using namespace Gecode;
IntSet fixed(0,2);
IntSetArgs cards(4);
for (int i=0; i<4; i++) {
cards[i] = fixed;
}
cards[2] = IntSet(0,0);
count(home, x, cards, ipl);
}
};
class IntAllMax : public Test {
public:
IntAllMax(Gecode::IntPropLevel ipl)
: Test("GCC::Int::All::Max::"+str(ipl), 4, 1,2, false, ipl) {}
virtual bool solution(const Assignment& x) const {
int n[2];
for (int i=2; i--; )
n[i] = 0;
for (int i=x.size(); i--; )
n[x[i] - 1]++;
if (n[0] != 2 || n[1] != 2)
return false;
return true;
}
virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
Gecode::IntArgs values({1,2});
Gecode::count(home, x, Gecode::IntSet(2,2), values, ipl);
}
};
template<bool hole>
class IntSome : public Test {
public:
IntSome(Gecode::IntPropLevel ipl)
: Test(std::string("GCC::Int::Some::")+
(hole ? "::Hole" : "::Full")+str(ipl),4,1,4,false,ipl) {}
virtual bool solution(const Assignment& x) const {
int n[4];
for (int i=4; i--; )
n[i]=0;
for (int i=x.size(); i--; )
n[x[i]-1]++;
if ((n[0] < 2) || (n[1] < 2) || (n[2] > 0) || (n[3] > 0))
return false;
return true;
}
virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
using namespace Gecode;
IntArgs values({1,2});
Gecode::IntSet fixed;
if (!hole) {
fixed = IntSet(0,2);
} else {
int ish[] = {0,2};
fixed = IntSet(ish,2);
}
Gecode::IntSetArgs cards(2);
cards[0]=fixed; cards[1]=fixed;
count(home, x, cards, values, ipl);
}
};
class VarAll : public Test {
protected:
static const int n = 4;
public:
VarAll(Gecode::IntPropLevel ipl)
: Test("GCC::Var::All::"+str(ipl),7,0,2,false,ipl) {}
virtual bool solution(const Assignment& x) const {
// Number of cardinality variables
int m = x.size()-n;
for (int i=0; i<n; i++)
if ((x[i] < 0) || (x[i] > 2))
return false;
int* card = new int[m];
for (int i=0; i<m; i++) {
card[i] = 0;
if ((x[n+i] < 0) || (x[n+i] > 2)) {
delete [] card;
return false;
}
}
for (int i=0; i<n; i++)
card[x[i]]++;
for (int i=0; i<m; i++)
if (card[i] != x[n+i]) {
delete [] card;
return false;
}
delete [] card;
return true;
}
virtual void post(Gecode::Space& home, Gecode::IntVarArray& xy) {
using namespace Gecode;
// Number of cardinality variables
int m = xy.size()-n;
IntVarArgs x(n), y(m);
for (int i=0; i<n; i++)
x[i]=xy[i];
for (int i=0; i<m; i++)
y[i]=xy[n+i];
count(home, x, y, ipl);
}
};
class VarSome : public Test {
protected:
int n;
static const int randomArity = 7;
public:
VarSome(std::string s, int n0, int min, int max,
Gecode::IntPropLevel ipl)
: Test("GCC::Var::Some::"+s+"::"+str(ipl),
n0+(max-min)+1,min,max,false,ipl)
, n(n0)
{
contest = CTL_NONE;
if (arity>randomArity)
testsearch = false;
}
virtual bool solution(const Assignment& x) const {
// Number of cardinality variables
int m = x.size()-n;
int* card = new int[m];
for (int i=0; i<m; i++) {
card[i] = 0;
if ((x[n+i] < 0) || (x[n+i] > n)) {
delete [] card;
return false;
}
}
for (int i=0; i<n; i++)
card[x[i]-dom.min()]++;
for (int i=0; i<m; i++)
if (card[i] != x[n+i]) {
delete [] card;
return false;
}
delete [] card;
return true;
}
virtual Assignment* assignment(void) const {
if (arity > randomArity)
return new RandomAssignment(arity,dom,4000);
else
return new CpltAssignment(arity,dom);
}
virtual void post(Gecode::Space& home, Gecode::IntVarArray& xy) {
using namespace Gecode;
// Number of cardinality variables
int m = xy.size()-n;
IntVarArgs x(n), y(m);
for (int i=0; i<n; i++)
x[i]=xy[i];
for (int i=0; i<m; i++)
y[i]=xy[n+i];
IntArgs values(m);
for (int i=m; i--;)
values[i] = i+dom.min();
count(home,x,y,values,ipl);
}
};
class Create {
public:
Create(void) {
for (IntPropLevels ipls; ipls(); ++ipls) {
(void) new IntAllMinMax(ipls.ipl());
(void) new IntAllMinMaxDef(ipls.ipl());
(void) new IntAllMax(ipls.ipl());
(void) new IntSome<false>(ipls.ipl());
(void) new IntSome<true>(ipls.ipl());
(void) new VarAll(ipls.ipl());
(void) new VarSome("Small",2,-1,3,ipls.ipl());
(void) new VarSome("Large",3,-1,4,ipls.ipl());
}
}
};
Create c;
}
}}
// STATISTICS: test-int
Gecode::IntArgs
Passing integer arguments.
Definition int.hh:628
Gecode::IntSet
Integer sets.
Definition int.hh:174
Gecode::IntVarArgs
Passing integer variables.
Definition int.hh:656
Gecode::IntVarArray
Integer variable array.
Definition int.hh:763
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::Int::Assignment::size
int size(void) const
Return number of variables.
Definition int.hpp:46
Test::Int::CpltAssignment
Generate all assignments.
Definition int.hh:79
Test::Int::GCC::Create
Help class to create and register tests.
Definition gcc.cpp:293
Test::Int::GCC::Create::Create
Create(void)
Perform creation and registration.
Definition gcc.cpp:296
Test::Int::GCC::IntAllMax
Test for integer cardinality with max cardinality for all variables
Definition gcc.cpp:118
Test::Int::GCC::IntAllMax::IntAllMax
IntAllMax(Gecode::IntPropLevel ipl)
Create and register test.
Definition gcc.cpp:121
Test::Int::GCC::IntAllMax::solution
virtual bool solution(const Assignment &x) const
Test whether x is solution
Definition gcc.cpp:124
Test::Int::GCC::IntAllMax::post
virtual void post(Gecode::Space &home, Gecode::IntVarArray &x)
Post constraint on x.
Definition gcc.cpp:135
Test::Int::GCC::IntAllMinMaxDef
Test for integer cardinality with min and max for all variables
Definition gcc.cpp:85
Test::Int::GCC::IntAllMinMaxDef::IntAllMinMaxDef
IntAllMinMaxDef(Gecode::IntPropLevel ipl)
Create and register test.
Definition gcc.cpp:88
Test::Int::GCC::IntAllMinMaxDef::solution
virtual bool solution(const Assignment &x) const
Test whether x is solution
Definition gcc.cpp:91
Test::Int::GCC::IntAllMinMaxDef::post
virtual void post(Gecode::Space &home, Gecode::IntVarArray &x)
Post constraint on x.
Definition gcc.cpp:105
Test::Int::GCC::IntAllMinMax
Test for integer cardinality with min and max for all variables
Definition gcc.cpp:51
Test::Int::GCC::IntAllMinMax::IntAllMinMax
IntAllMinMax(Gecode::IntPropLevel ipl)
Create and register test.
Definition gcc.cpp:54
Test::Int::GCC::IntAllMinMax::post
virtual void post(Gecode::Space &home, Gecode::IntVarArray &x)
Post constraint on x.
Definition gcc.cpp:71
Test::Int::GCC::IntAllMinMax::solution
virtual bool solution(const Assignment &x) const
Test whether x is solution
Definition gcc.cpp:57
Test::Int::GCC::IntSome
Test for integer cardinality for some variables
Definition gcc.cpp:144
Test::Int::GCC::IntSome::solution
virtual bool solution(const Assignment &x) const
Test whether x is solution
Definition gcc.cpp:151
Test::Int::GCC::IntSome::IntSome
IntSome(Gecode::IntPropLevel ipl)
Create and register test.
Definition gcc.cpp:147
Test::Int::GCC::IntSome::post
virtual void post(Gecode::Space &home, Gecode::IntVarArray &x)
Post constraint on x.
Definition gcc.cpp:162
Test::Int::GCC::VarAll
Test for variable cardinality for all cardinality values
Definition gcc.cpp:179
Test::Int::GCC::VarAll::solution
virtual bool solution(const Assignment &x) const
Test whether x is solution
Definition gcc.cpp:188
Test::Int::GCC::VarAll::n
static const int n
Number of non-cardinality variables.
Definition gcc.cpp:182
Test::Int::GCC::VarAll::VarAll
VarAll(Gecode::IntPropLevel ipl)
Create and register test.
Definition gcc.cpp:185
Test::Int::GCC::VarAll::post
virtual void post(Gecode::Space &home, Gecode::IntVarArray &xy)
Post constraint on xy.
Definition gcc.cpp:213
Test::Int::GCC::VarSome
Test for variable cardinality for some cardinality values
Definition gcc.cpp:228
Test::Int::GCC::VarSome::n
int n
Number of non-cardinality variables.
Definition gcc.cpp:231
Test::Int::GCC::VarSome::post
virtual void post(Gecode::Space &home, Gecode::IntVarArray &xy)
Post constraint on xy.
Definition gcc.cpp:276
Test::Int::GCC::VarSome::assignment
virtual Assignment * assignment(void) const
Create and register initial assignment.
Definition gcc.cpp:269
Test::Int::GCC::VarSome::solution
virtual bool solution(const Assignment &x) const
Test whether x is solution
Definition gcc.cpp:247
Test::Int::GCC::VarSome::VarSome
VarSome(std::string s, int n0, int min, int max, Gecode::IntPropLevel ipl)
Create and register test.
Definition gcc.cpp:236
Test::Int::GCC::VarSome::randomArity
static const int randomArity
Arity beyond which to use randomized tests.
Definition gcc.cpp:233
Test::Int::IntPropLevels
Iterator for simple integer propagation levels.
Definition int.hh:332
Test::Int::RandomAssignment
Generate random selection of assignments.
Definition int.hh:96
Test::Int::Test::testsearch
bool testsearch
Whether to perform search test.
Definition int.hh:238
Test::Int::Test::ipl
Gecode::IntPropLevel ipl
Propagation level.
Definition int.hh:234
Test::Int::Test::arity
int arity
Number of variables.
Definition int.hh:226
Test::Int::Test::str
static std::string str(Gecode::IntPropLevel ipl)
Map integer propagation level to string.
Definition int.hpp:209
Test::Int::Test::dom
Gecode::IntSet dom
Domain of variables.
Definition int.hh:228
Test::Int::Test::contest
ConTestLevel contest
Whether to test for certain consistency.
Definition int.hh:236
Gecode::IntPropLevel
IntPropLevel
Propagation levels for integer propagators.
Definition int.hh:974
Gecode
Gecode toplevel namespace
Gecode::IntSetArgs
ArgArray< IntSet > IntSetArgs
Passing set arguments.
Definition int.hh:619
Gecode::count
void count(Home home, const IntVarArgs &x, int n, IntRelType irt, int m, IntPropLevel ipl=IPL_DEF)
Post propagator for .
Definition count.cpp:40
Gecode::min
void min(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Definition arithmetic.cpp:67
Gecode::values
void values(Home home, const IntVarArgs &x, IntSet y, IntPropLevel ipl=IPL_DEF)
Post constraint .
Definition aliases.hpp:143
Gecode::max
void max(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Definition arithmetic.cpp:49
Test::Int::GCC
Tests for counting constraints (global cardinality)
Definition gcc.cpp:43
Test::Int::GCC::c
Create c
Definition gcc.cpp:310
Test::Int
Testing finite domain integers.
Definition int.cpp:40
Test::Int::CTL_NONE
@ CTL_NONE
No consistency-test.
Definition int.hh:140
Test
General test support.
Definition afc.cpp:39
std
Definition flatzinc.cpp:52
int.hh