int.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>
* Mikael Lagerkvist <lagerkvist@gecode.org>
*
* Copyright:
* Christian Schulte, 2005
* Mikael Lagerkvist, 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/int.hh"
#include <algorithm>
namespace Test { namespace Int {
/*
* Complete assignments
*
*/
void
CpltAssignment::operator++(void) {
int i = n-1;
while (true) {
++dsv[i];
if (dsv[i]() || (i == 0))
return;
dsv[i--].init(d);
}
}
/*
* Random assignments
*
*/
void
RandomAssignment::operator++(void) {
for (int i = n; i--; )
vals[i]=randval();
a--;
}
void
RandomMixAssignment::operator++(void) {
for (int i=n-_n1; i--; )
vals[i] = randval(d);
for (int i=_n1; i--; )
vals[n-_n1+i] = randval(_d1);
a--;
}
}}
std::ostream&
operator<<(std::ostream& os, const Test::Int::Assignment& a) {
int n = a.size();
os << "{";
for (int i=0; i<n; i++)
os << a[i] << ((i!=n-1) ? "," : "}");
return os;
}
namespace Test { namespace Int {
TestSpace::TestSpace(int n, Gecode::IntSet& d0, Test* t)
: d(d0), x(*this,n,Gecode::Int::Limits::min,Gecode::Int::Limits::max),
test(t), reified(false) {
Gecode::IntVarArgs _x(*this,n,d);
if (x.size() == 1)
Gecode::dom(*this,x[0],_x[0]);
else
Gecode::dom(*this,x,_x);
Gecode::BoolVar b(*this,0,1);
r = Gecode::Reify(b,Gecode::RM_EQV);
if (opt.log)
olog << ind(2) << "Initial: x[]=" << x
<< std::endl;
}
TestSpace::TestSpace(int n, Gecode::IntSet& d0, Test* t,
Gecode::ReifyMode rm)
: d(d0), x(*this,n,Gecode::Int::Limits::min,Gecode::Int::Limits::max),
test(t), reified(true) {
Gecode::IntVarArgs _x(*this,n,d);
if (x.size() == 1)
Gecode::dom(*this,x[0],_x[0]);
else
Gecode::dom(*this,x,_x);
Gecode::BoolVar b(*this,0,1);
r = Gecode::Reify(b,rm);
if (opt.log)
olog << ind(2) << "Initial: x[]=" << x
<< " b=" << r.var() << std::endl;
}
TestSpace::TestSpace(TestSpace& s)
: Gecode::Space(s), d(s.d), test(s.test), reified(s.reified) {
x.update(*this, s.x);
Gecode::BoolVar b;
Gecode::BoolVar sr(s.r.var());
b.update(*this, sr);
r.var(b); r.mode(s.r.mode());
}
Gecode::Space*
TestSpace::copy(void) {
return new TestSpace(*this);
}
bool
TestSpace::assigned(void) const {
for (int i=x.size(); i--; )
if (!x[i].assigned())
return false;
return true;
}
void
TestSpace::post(void) {
if (reified){
test->post(*this,x,r);
if (opt.log)
olog << ind(3) << "Posting reified propagator" << std::endl;
} else {
test->post(*this,x);
if (opt.log)
olog << ind(3) << "Posting propagator" << std::endl;
}
}
bool
TestSpace::failed(void) {
if (opt.log) {
olog << ind(3) << "Fixpoint: " << x;
bool f=(status() == Gecode::SS_FAILED);
olog << std::endl << ind(3) << " --> " << x << std::endl;
return f;
} else {
return status() == Gecode::SS_FAILED;
}
}
int
TestSpace::rndvar(void) {
assert(!assigned());
// Select variable to be pruned
int i = static_cast<int>(Base::rand(static_cast<unsigned int>(x.size())));
while (x[i].assigned()) {
i = (i+1) % x.size();
}
return i;
}
void
TestSpace::rndrel(const Assignment& a, int i,
Gecode::IntRelType& irt, int& v) {
using namespace Gecode;
// Select mode for pruning
irt = IRT_EQ; // Means do nothing!
switch (Base::rand(3)) {
case 0:
if (a[i] < x[i].max()) {
v=a[i]+1+
static_cast<int>(Base::rand(static_cast
<unsigned int>(x[i].max()-a[i])));
assert((v > a[i]) && (v <= x[i].max()));
irt = IRT_LE;
}
break;
case 1:
if (a[i] > x[i].min()) {
v=x[i].min()+
static_cast<int>(Base::rand(static_cast
<unsigned int>(a[i]-x[i].min())));
assert((v < a[i]) && (v >= x[i].min()));
irt = IRT_GR;
}
break;
default:
{
Gecode::Int::ViewRanges<Gecode::Int::IntView> it(x[i]);
unsigned int skip =
Base::rand(static_cast<unsigned int>(x[i].size()-1));
while (true) {
if (it.width() > skip) {
v = it.min() + static_cast<int>(skip);
if (v == a[i]) {
if (it.width() == 1) {
++it; v = it.min();
} else if (v < it.max()) {
++v;
} else {
--v;
}
}
break;
}
skip -= it.width(); ++it;
}
irt = IRT_NQ;
break;
}
}
}
void
TestSpace::rel(int i, Gecode::IntRelType irt, int n) {
if (opt.log) {
olog << ind(4) << "x[" << i << "] ";
switch (irt) {
case Gecode::IRT_EQ: olog << "="; break;
case Gecode::IRT_NQ: olog << "!="; break;
case Gecode::IRT_LQ: olog << "<="; break;
case Gecode::IRT_LE: olog << "<"; break;
case Gecode::IRT_GQ: olog << ">="; break;
case Gecode::IRT_GR: olog << ">"; break;
}
olog << " " << n << std::endl;
}
Gecode::rel(*this, x[i], irt, n);
}
void
TestSpace::rel(bool sol) {
int n = sol ? 1 : 0;
assert(reified);
if (opt.log)
olog << ind(4) << "b = " << n << std::endl;
Gecode::rel(*this, r.var(), Gecode::IRT_EQ, n);
}
void
TestSpace::assign(const Assignment& a, bool skip) {
using namespace Gecode;
int i = skip ?
static_cast<int>(Base::rand(static_cast<unsigned int>(a.size()))) : -1;
for (int j=a.size(); j--; )
if (i != j) {
rel(j, IRT_EQ, a[j]);
if (Base::fixpoint() && failed())
return;
}
}
void
TestSpace::bound(void) {
using namespace Gecode;
int i = rndvar();
bool min = Base::rand(2);
rel(i, IRT_EQ, min ? x[i].min() : x[i].max());
}
void
TestSpace::prune(int i, bool bounds_only) {
using namespace Gecode;
// Prune values
if (bounds_only) {
if (Base::rand(2) && !x[i].assigned()) {
int v=x[i].min()+1+
static_cast<int>(Base::rand(static_cast
<unsigned int>(x[i].max()-x[i].min())));
assert((v > x[i].min()) && (v <= x[i].max()));
rel(i, Gecode::IRT_LE, v);
}
if (Base::rand(2) && !x[i].assigned()) {
int v=x[i].min()+
static_cast<int>(Base::rand(static_cast
<unsigned int>(x[i].max()-x[i].min())));
assert((v < x[i].max()) && (v >= x[i].min()));
rel(i, Gecode::IRT_GR, v);
}
} else {
for (int vals =
static_cast<int>(Base::rand(static_cast<unsigned int>(x[i].size()-1))+1); vals--; ) {
int v;
Gecode::Int::ViewRanges<Gecode::Int::IntView> it(x[i]);
unsigned int skip = Base::rand(x[i].size()-1);
while (true) {
if (it.width() > skip) {
v = it.min() + static_cast<int>(skip); break;
}
skip -= it.width(); ++it;
}
rel(i, IRT_NQ, v);
}
}
}
void
TestSpace::prune(void) {
prune(rndvar(), false);
}
bool
TestSpace::prune(const Assignment& a, bool testfix) {
using namespace Gecode;
// Select variable to be pruned
int i = rndvar();
// Select mode for pruning
IntRelType irt;
int v;
rndrel(a,i,irt,v);
if (irt != IRT_EQ)
rel(i, irt, v);
if (Base::fixpoint()) {
if (failed() || !testfix)
return true;
TestSpace* c = static_cast<TestSpace*>(clone());
if (opt.log)
olog << ind(3) << "Testing fixpoint on copy" << std::endl;
c->post();
if (c->failed()) {
if (opt.log)
olog << ind(4) << "Copy failed after posting" << std::endl;
delete c; return false;
}
for (int j=x.size(); j--; )
if (x[j].size() != c->x[j].size()) {
if (opt.log)
olog << ind(4) << "Different domain size" << std::endl;
delete c; return false;
}
if (reified && (r.var().size() != c->r.var().size())) {
if (opt.log)
olog << ind(4) << "Different control variable" << std::endl;
delete c; return false;
}
if (opt.log)
olog << ind(3) << "Finished testing fixpoint on copy" << std::endl;
delete c;
}
return true;
}
void
TestSpace::enable(void) {
Gecode::PropagatorGroup::all.enable(*this);
}
void
TestSpace::disable(void) {
Gecode::PropagatorGroup::all.disable(*this);
(void) status();
}
bool
TestSpace::disabled(const Assignment& a, TestSpace& c,
bool testfix) {
using namespace Gecode;
// Disable propagators
c.disable();
// Select variable to be pruned
int i = rndvar();
// Select mode for pruning
IntRelType irt;
int v;
rndrel(a,i,irt,v);
if (irt != IRT_EQ) {
rel(i, irt, v);
c.rel(i, irt, v);
}
// Enable propagators
c.enable();
if (!testfix)
return true;
if (failed()) {
if (!c.failed()) {
if (opt.log)
olog << ind(3) << "No failure on disabled copy" << std::endl;
return false;
}
return true;
}
if (c.failed()) {
if (opt.log)
olog << ind(3) << "Failure on disabled copy" << std::endl;
return false;
}
for (int j=x.size(); j--; ) {
if (x[j].size() != c.x[j].size()) {
if (opt.log)
olog << ind(4) << "Different domain size" << std::endl;
return false;
}
if (reified && (r.var().size() != c.r.var().size())) {
if (opt.log)
olog << ind(4) << "Different control variable" << std::endl;
return false;
}
}
return true;
}
unsigned int
TestSpace::propagators(void) {
return Gecode::PropagatorGroup::all.size(*this);
}
const Gecode::IntPropLevel IntPropLevels::ipls[] =
{Gecode::IPL_DOM,Gecode::IPL_BND,Gecode::IPL_VAL};
const Gecode::IntPropLevel IntPropBasicAdvanced::ipls[] =
{Gecode::IPL_BASIC_ADVANCED,Gecode::IPL_ADVANCED,Gecode::IPL_BASIC};
const Gecode::IntRelType IntRelTypes::irts[] =
{Gecode::IRT_EQ,Gecode::IRT_NQ,Gecode::IRT_LQ,
Gecode::IRT_LE,Gecode::IRT_GQ,Gecode::IRT_GR};
const Gecode::BoolOpType BoolOpTypes::bots[] =
{Gecode::BOT_AND,Gecode::BOT_OR,Gecode::BOT_IMP,
Gecode::BOT_EQV,Gecode::BOT_XOR};
Assignment*
Test::assignment(void) const {
return new CpltAssignment(arity,dom);
}
#define CHECK_TEST(T,M) \
if (opt.log) \
olog << ind(3) << "Check: " << (M) << std::endl; \
if (!(T)) { \
problem = (M); delete s; goto failed; \
}
#define START_TEST(T) \
if (opt.log) { \
olog.str(""); \
olog << ind(2) << "Testing: " << (T) << std::endl; \
} \
test = (T);
bool
Test::ignore(const Assignment&) const {
return false;
}
void
Test::post(Gecode::Space&, Gecode::IntVarArray&,
Gecode::Reify) {}
bool
Test::run(void) {
using namespace Gecode;
const char* test = "NONE";
const char* problem = "NONE";
// Set up assignments
Assignment* ap = assignment();
Assignment& a = *ap;
// Set up space for all solution search
TestSpace* search_s = new TestSpace(arity,dom,this);
post(*search_s,search_s->x);
branch(*search_s,search_s->x,INT_VAR_NONE(),INT_VAL_MIN());
Search::Options search_o;
search_o.threads = 1;
DFS<TestSpace> e_s(search_s,search_o);
delete search_s;
while (a()) {
bool sol = solution(a);
if (opt.log) {
olog << ind(1) << "Assignment: " << a
<< (sol ? " (solution)" : " (no solution)")
<< std::endl;
}
START_TEST("Assignment (after posting)");
{
TestSpace* s = new TestSpace(arity,dom,this);
TestSpace* sc = NULL;
s->post();
switch (Base::rand(2)) {
case 0:
if (opt.log)
olog << ind(3) << "No copy" << std::endl;
sc = s;
s = NULL;
break;
case 1:
if (opt.log)
olog << ind(3) << "Copy" << std::endl;
if (s->status() != SS_FAILED) {
sc = static_cast<TestSpace*>(s->clone());
} else {
sc = s; s = NULL;
}
break;
default: assert(false);
}
sc->assign(a);
if (sol) {
CHECK_TEST(!sc->failed(), "Failed on solution");
CHECK_TEST(sc->propagators()==0, "No subsumption");
} else {
CHECK_TEST(sc->failed(), "Solved on non-solution");
}
delete s; delete sc;
}
START_TEST("Partial assignment (after posting)");
{
TestSpace* s = new TestSpace(arity,dom,this);
s->post();
s->assign(a,true);
(void) s->failed();
s->assign(a);
if (sol) {
CHECK_TEST(!s->failed(), "Failed on solution");
CHECK_TEST(s->propagators()==0, "No subsumption");
} else {
CHECK_TEST(s->failed(), "Solved on non-solution");
}
delete s;
}
START_TEST("Assignment (after posting, disable)");
{
TestSpace* s = new TestSpace(arity,dom,this);
s->post();
s->disable();
s->assign(a);
s->enable();
if (sol) {
CHECK_TEST(!s->failed(), "Failed on solution");
CHECK_TEST(s->propagators()==0, "No subsumption");
} else {
CHECK_TEST(s->failed(), "Solved on non-solution");
}
delete s;
}
START_TEST("Partial assignment (after posting, disable)");
{
TestSpace* s = new TestSpace(arity,dom,this);
s->post();
s->assign(a,true);
s->disable();
(void) s->failed();
s->assign(a);
s->enable();
if (sol) {
CHECK_TEST(!s->failed(), "Failed on solution");
CHECK_TEST(s->propagators()==0, "No subsumption");
} else {
CHECK_TEST(s->failed(), "Solved on non-solution");
}
delete s;
}
START_TEST("Assignment (before posting)");
{
TestSpace* s = new TestSpace(arity,dom,this);
s->assign(a);
s->post();
if (sol) {
CHECK_TEST(!s->failed(), "Failed on solution");
CHECK_TEST(s->propagators()==0, "No subsumption");
} else {
CHECK_TEST(s->failed(), "Solved on non-solution");
}
delete s;
}
START_TEST("Partial assignment (before posting)");
{
TestSpace* s = new TestSpace(arity,dom,this);
s->assign(a,true);
s->post();
(void) s->failed();
s->assign(a);
if (sol) {
CHECK_TEST(!s->failed(), "Failed on solution");
CHECK_TEST(s->propagators()==0, "No subsumption");
} else {
CHECK_TEST(s->failed(), "Solved on non-solution");
}
delete s;
}
START_TEST("Prune");
{
TestSpace* s = new TestSpace(arity,dom,this);
s->post();
while (!s->failed() && !s->assigned())
if (!s->prune(a,testfix)) {
problem = "No fixpoint";
delete s;
goto failed;
}
s->assign(a);
if (sol) {
CHECK_TEST(!s->failed(), "Failed on solution");
CHECK_TEST(s->propagators()==0, "No subsumption");
} else {
CHECK_TEST(s->failed(), "Solved on non-solution");
}
delete s;
}
START_TEST("Prune (disable)");
{
TestSpace* s = new TestSpace(arity,dom,this);
TestSpace* c = static_cast<TestSpace*>(s->clone());
s->post(); c->post();
while (!s->failed() && !s->assigned())
if (!s->disabled(a,*c,testfix)) {
problem = "Different result after re-enable";
delete s; delete c;
goto failed;
}
if (testfix && (s->failed() != c->failed())) {
problem = "Different failure after re-enable";
delete s; delete c;
goto failed;
}
delete s; delete c;
}
if (!ignore(a)) {
if (eqv()) {
{
START_TEST("Assignment reified (rewrite after post, <=>)");
TestSpace* s = new TestSpace(arity,dom,this,RM_EQV);
s->post();
s->rel(sol);
s->assign(a);
CHECK_TEST(!s->failed(), "Failed");
CHECK_TEST(s->propagators()==0, "No subsumption");
delete s;
}
{
START_TEST("Assignment reified (rewrite failure, <=>)");
TestSpace* s = new TestSpace(arity,dom,this,RM_EQV);
s->post();
s->rel(!sol);
s->assign(a);
CHECK_TEST(s->failed(), "Not failed");
delete s;
}
{
START_TEST("Assignment reified (immediate rewrite, <=>)");
TestSpace* s = new TestSpace(arity,dom,this,RM_EQV);
s->rel(sol);
s->post();
s->assign(a);
CHECK_TEST(!s->failed(), "Failed");
CHECK_TEST(s->propagators()==0, "No subsumption");
delete s;
}
{
START_TEST("Assignment reified (immediate failure, <=>)");
TestSpace* s = new TestSpace(arity,dom,this,RM_EQV);
s->rel(!sol);
s->post();
s->assign(a);
CHECK_TEST(s->failed(), "Not failed");
delete s;
}
{
START_TEST("Assignment reified (before posting, <=>)");
TestSpace* s = new TestSpace(arity,dom,this,RM_EQV);
s->assign(a);
s->post();
CHECK_TEST(!s->failed(), "Failed");
CHECK_TEST(s->propagators()==0, "No subsumption");
CHECK_TEST(s->r.var().assigned(), "Control variable unassigned");
if (sol) {
CHECK_TEST(s->r.var().val()==1, "Zero on solution");
} else {
CHECK_TEST(s->r.var().val()==0, "One on non-solution");
}
delete s;
}
{
START_TEST("Assignment reified (after posting, <=>)");
TestSpace* s = new TestSpace(arity,dom,this,RM_EQV);
s->post();
s->assign(a);
CHECK_TEST(!s->failed(), "Failed");
CHECK_TEST(s->propagators()==0, "No subsumption");
CHECK_TEST(s->r.var().assigned(), "Control variable unassigned");
if (sol) {
CHECK_TEST(s->r.var().val()==1, "Zero on solution");
} else {
CHECK_TEST(s->r.var().val()==0, "One on non-solution");
}
delete s;
}
{
START_TEST("Assignment reified (after posting, <=>, disable)");
TestSpace* s = new TestSpace(arity,dom,this,RM_EQV);
s->post();
s->disable();
s->assign(a);
s->enable();
CHECK_TEST(!s->failed(), "Failed");
CHECK_TEST(s->propagators()==0, "No subsumption");
CHECK_TEST(s->r.var().assigned(), "Control variable unassigned");
if (sol) {
CHECK_TEST(s->r.var().val()==1, "Zero on solution");
} else {
CHECK_TEST(s->r.var().val()==0, "One on non-solution");
}
delete s;
}
{
START_TEST("Prune reified, <=>");
TestSpace* s = new TestSpace(arity,dom,this,RM_EQV);
s->post();
while (!s->failed() &&
(!s->assigned() || !s->r.var().assigned()))
if (!s->prune(a,testfix)) {
problem = "No fixpoint";
delete s;
goto failed;
}
CHECK_TEST(!s->failed(), "Failed");
CHECK_TEST(s->propagators()==0, "No subsumption");
CHECK_TEST(s->r.var().assigned(), "Control variable unassigned");
if (sol) {
CHECK_TEST(s->r.var().val()==1, "Zero on solution");
} else {
CHECK_TEST(s->r.var().val()==0, "One on non-solution");
}
delete s;
}
{
START_TEST("Prune reified, <=>, disable");
TestSpace* s = new TestSpace(arity,dom,this,RM_EQV);
TestSpace* c = static_cast<TestSpace*>(s->clone());
s->post(); c->post();
while (!s->failed() &&
(!s->assigned() || !s->r.var().assigned()))
if (!s->disabled(a,*c,testfix)) {
problem = "No fixpoint";
delete s;
delete c;
goto failed;
}
CHECK_TEST(!c->failed(), "Failed");
CHECK_TEST(c->propagators()==0, "No subsumption");
CHECK_TEST(c->r.var().assigned(), "Control variable unassigned");
if (sol) {
CHECK_TEST(c->r.var().val()==1, "Zero on solution");
} else {
CHECK_TEST(c->r.var().val()==0, "One on non-solution");
}
delete s;
delete c;
}
}
if (imp()) {
{
START_TEST("Assignment reified (rewrite after post, =>)");
TestSpace* s = new TestSpace(arity,dom,this,RM_IMP);
s->post();
s->rel(sol);
s->assign(a);
CHECK_TEST(!s->failed(), "Failed");
CHECK_TEST(s->propagators()==0, "No subsumption");
delete s;
}
{
START_TEST("Assignment reified (rewrite failure, =>)");
TestSpace* s = new TestSpace(arity,dom,this,RM_IMP);
s->post();
s->rel(!sol);
s->assign(a);
if (sol) {
CHECK_TEST(!s->failed(), "Failed");
CHECK_TEST(s->propagators()==0, "No subsumption");
} else {
CHECK_TEST(s->failed(), "Not failed");
}
delete s;
}
{
START_TEST("Assignment reified (immediate rewrite, =>)");
TestSpace* s = new TestSpace(arity,dom,this,RM_IMP);
s->rel(sol);
s->post();
s->assign(a);
CHECK_TEST(!s->failed(), "Failed");
CHECK_TEST(s->propagators()==0, "No subsumption");
delete s;
}
{
START_TEST("Assignment reified (immediate failure, =>)");
TestSpace* s = new TestSpace(arity,dom,this,RM_IMP);
s->rel(!sol);
s->post();
s->assign(a);
if (sol) {
CHECK_TEST(!s->failed(), "Failed");
CHECK_TEST(s->propagators()==0, "No subsumption");
} else {
CHECK_TEST(s->failed(), "Not failed");
}
delete s;
}
{
START_TEST("Assignment reified (before posting, =>)");
TestSpace* s = new TestSpace(arity,dom,this,RM_IMP);
s->assign(a);
s->post();
CHECK_TEST(!s->failed(), "Failed");
CHECK_TEST(s->propagators()==0, "No subsumption");
if (sol) {
CHECK_TEST(!s->r.var().assigned(), "Control variable assigned");
} else {
CHECK_TEST(s->r.var().assigned(), "Control variable unassigned");
CHECK_TEST(s->r.var().val()==0, "One on non-solution");
}
delete s;
}
{
START_TEST("Assignment reified (after posting, =>)");
TestSpace* s = new TestSpace(arity,dom,this,RM_IMP);
s->post();
s->assign(a);
CHECK_TEST(!s->failed(), "Failed");
CHECK_TEST(s->propagators()==0, "No subsumption");
if (sol) {
CHECK_TEST(!s->r.var().assigned(), "Control variable assigned");
} else {
CHECK_TEST(s->r.var().assigned(), "Control variable unassigned");
CHECK_TEST(s->r.var().val()==0, "One on non-solution");
}
delete s;
}
{
START_TEST("Assignment reified (after posting, =>, disable)");
TestSpace* s = new TestSpace(arity,dom,this,RM_IMP);
s->post();
s->disable();
s->assign(a);
s->enable();
CHECK_TEST(!s->failed(), "Failed");
CHECK_TEST(s->propagators()==0, "No subsumption");
if (sol) {
CHECK_TEST(!s->r.var().assigned(), "Control variable assigned");
} else {
CHECK_TEST(s->r.var().assigned(), "Control variable unassigned");
CHECK_TEST(s->r.var().val()==0, "One on non-solution");
}
delete s;
}
{
START_TEST("Prune reified, =>");
TestSpace* s = new TestSpace(arity,dom,this,RM_IMP);
s->post();
while (!s->failed() &&
(!s->assigned() || (!sol && !s->r.var().assigned())))
if (!s->prune(a,testfix)) {
problem = "No fixpoint";
delete s;
goto failed;
}
CHECK_TEST(!s->failed(), "Failed");
CHECK_TEST(s->propagators()==0, "No subsumption");
if (sol) {
CHECK_TEST(!s->r.var().assigned(), "Control variable assigned");
} else {
CHECK_TEST(s->r.var().assigned(), "Control variable unassigned");
CHECK_TEST(s->r.var().val()==0, "One on non-solution");
}
delete s;
}
{
START_TEST("Prune reified, =>, disable");
TestSpace* s = new TestSpace(arity,dom,this,RM_IMP);
TestSpace* c = static_cast<TestSpace*>(s->clone());
s->post(); c->post();
while (!s->failed() &&
(!s->assigned() || (!sol && !s->r.var().assigned())))
if (!s->disabled(a,*c,testfix)) {
problem = "No fixpoint";
delete s;
delete c;
goto failed;
}
CHECK_TEST(!c->failed(), "Failed");
CHECK_TEST(c->propagators()==0, "No subsumption");
if (sol) {
CHECK_TEST(!c->r.var().assigned(), "Control variable assigned");
} else {
CHECK_TEST(c->r.var().assigned(), "Control variable unassigned");
CHECK_TEST(c->r.var().val()==0, "One on non-solution");
}
delete s;
delete c;
}
}
if (pmi()) {
{
START_TEST("Assignment reified (rewrite after post, <=)");
TestSpace* s = new TestSpace(arity,dom,this,RM_PMI);
s->post();
s->rel(sol);
s->assign(a);
CHECK_TEST(!s->failed(), "Failed");
CHECK_TEST(s->propagators()==0, "No subsumption");
delete s;
}
{
START_TEST("Assignment reified (rewrite failure, <=)");
TestSpace* s = new TestSpace(arity,dom,this,RM_PMI);
s->post();
s->rel(!sol);
s->assign(a);
if (sol) {
CHECK_TEST(s->failed(), "Not failed");
} else {
CHECK_TEST(!s->failed(), "Failed");
CHECK_TEST(s->propagators()==0, "No subsumption");
}
delete s;
}
{
START_TEST("Assignment reified (immediate rewrite, <=)");
TestSpace* s = new TestSpace(arity,dom,this,RM_PMI);
s->rel(sol);
s->post();
s->assign(a);
CHECK_TEST(!s->failed(), "Failed");
CHECK_TEST(s->propagators()==0, "No subsumption");
delete s;
}
{
START_TEST("Assignment reified (immediate failure, <=)");
TestSpace* s = new TestSpace(arity,dom,this,RM_PMI);
s->rel(!sol);
s->post();
s->assign(a);
if (sol) {
CHECK_TEST(s->failed(), "Not failed");
} else {
CHECK_TEST(!s->failed(), "Failed");
CHECK_TEST(s->propagators()==0, "No subsumption");
}
delete s;
}
{
START_TEST("Assignment reified (before posting, <=)");
TestSpace* s = new TestSpace(arity,dom,this,RM_PMI);
s->assign(a);
s->post();
CHECK_TEST(!s->failed(), "Failed");
CHECK_TEST(s->propagators()==0, "No subsumption");
if (sol) {
CHECK_TEST(s->r.var().assigned(), "Control variable unassigned");
CHECK_TEST(s->r.var().val()==1, "Zero on solution");
} else {
CHECK_TEST(!s->r.var().assigned(), "Control variable assigned");
}
delete s;
}
{
START_TEST("Assignment reified (after posting, <=)");
TestSpace* s = new TestSpace(arity,dom,this,RM_PMI);
s->post();
s->assign(a);
CHECK_TEST(!s->failed(), "Failed");
CHECK_TEST(s->propagators()==0, "No subsumption");
if (sol) {
CHECK_TEST(s->r.var().assigned(), "Control variable unassigned");
CHECK_TEST(s->r.var().val()==1, "Zero on solution");
} else {
CHECK_TEST(!s->r.var().assigned(), "Control variable assigned");
}
delete s;
}
{
START_TEST("Assignment reified (after posting, <=, disable)");
TestSpace* s = new TestSpace(arity,dom,this,RM_PMI);
s->post();
s->disable();
s->assign(a);
s->enable();
CHECK_TEST(!s->failed(), "Failed");
CHECK_TEST(s->propagators()==0, "No subsumption");
if (sol) {
CHECK_TEST(s->r.var().assigned(), "Control variable unassigned");
CHECK_TEST(s->r.var().val()==1, "Zero on solution");
} else {
CHECK_TEST(!s->r.var().assigned(), "Control variable assigned");
}
delete s;
}
{
START_TEST("Prune reified, <=");
TestSpace* s = new TestSpace(arity,dom,this,RM_PMI);
s->post();
while (!s->failed() &&
(!s->assigned() || (sol && !s->r.var().assigned())))
if (!s->prune(a,testfix)) {
problem = "No fixpoint";
delete s;
goto failed;
}
CHECK_TEST(!s->failed(), "Failed");
CHECK_TEST(s->propagators()==0, "No subsumption");
if (sol) {
CHECK_TEST(s->r.var().assigned(), "Control variable unassigned");
CHECK_TEST(s->r.var().val()==1, "Zero on solution");
} else {
CHECK_TEST(!s->r.var().assigned(), "Control variable assigned");
}
delete s;
}
{
START_TEST("Prune reified, <=, disable");
TestSpace* s = new TestSpace(arity,dom,this,RM_PMI);
TestSpace* c = static_cast<TestSpace*>(s->clone());
s->post(); c->post();
while (!s->failed() &&
(!s->assigned() || (sol && !s->r.var().assigned())))
if (!s->disabled(a,*c,testfix)) {
problem = "No fixpoint";
delete s;
delete c;
goto failed;
}
CHECK_TEST(!c->failed(), "Failed");
CHECK_TEST(c->propagators()==0, "No subsumption");
if (sol) {
CHECK_TEST(c->r.var().assigned(), "Control variable unassigned");
CHECK_TEST(c->r.var().val()==1, "Zero on solution");
} else {
CHECK_TEST(!c->r.var().assigned(), "Control variable assigned");
}
delete s;
delete c;
}
}
}
if (testsearch) {
if (sol) {
START_TEST("Search");
TestSpace* s = e_s.next();
CHECK_TEST(s != NULL, "Solutions exhausted");
CHECK_TEST(s->propagators()==0, "No subsumption");
for (int i=a.size(); i--; ) {
CHECK_TEST(s->x[i].assigned(), "Unassigned variable");
CHECK_TEST(a[i] == s->x[i].val(), "Wrong value in solution");
}
delete s;
}
}
++a;
}
if (testsearch) {
test = "Search";
if (e_s.next() != NULL) {
problem = "Excess solutions";
goto failed;
}
}
switch (contest) {
case CTL_NONE: break;
case CTL_DOMAIN: {
START_TEST("Full domain consistency");
TestSpace* s = new TestSpace(arity,dom,this);
s->post();
if (!s->failed()) {
while (!s->failed() && !s->assigned())
s->prune();
CHECK_TEST(!s->failed(), "Failed");
CHECK_TEST(s->propagators()==0, "No subsumption");
}
delete s;
// Fall-through -- domain implies bounds(d) and bounds(z)
}
case CTL_BOUNDS_D: {
START_TEST("Bounds(D)-consistency");
TestSpace* s = new TestSpace(arity,dom,this);
s->post();
for (int i = s->x.size(); i--; )
s->prune(i, false);
if (!s->failed()) {
while (!s->failed() && !s->assigned())
s->bound();
CHECK_TEST(!s->failed(), "Failed");
CHECK_TEST(s->propagators()==0, "No subsumption");
}
delete s;
// Fall-through -- bounds(d) implies bounds(z)
}
case CTL_BOUNDS_Z: {
START_TEST("Bounds(Z)-consistency");
TestSpace* s = new TestSpace(arity,dom,this);
s->post();
for (int i = s->x.size(); i--; )
s->prune(i, true);
if (!s->failed()) {
while (!s->failed() && !s->assigned())
s->bound();
CHECK_TEST(!s->failed(), "Failed");
CHECK_TEST(s->propagators()==0, "No subsumption");
}
delete s;
break;
}
}
delete ap;
return true;
failed:
if (opt.log)
olog << "FAILURE" << std::endl
<< ind(1) << "Test: " << test << std::endl
<< ind(1) << "Problem: " << problem << std::endl;
if (a() && opt.log)
olog << ind(1) << "Assignment: " << a << std::endl;
delete ap;
return false;
}
}}
#undef START_TEST
#undef CHECK_TEST
// STATISTICS: test-int
Gecode::BoolVar
Boolean integer variables.
Definition int.hh:512
Gecode::BoolVar::val
int val(void) const
Return assigned value.
Definition bool.hpp:57
Gecode::DFS
Depth-first search engine.
Definition search.hh:1036
Gecode::FloatVal::size
FloatNum size(void) const
Return size of float value (distance between maximum and minimum).
Definition val.hpp:78
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::Int::ViewRanges
Range iterator for integer views.
Definition view.hpp:54
Gecode::Int::ViewRanges::max
int max(void) const
Return largest value of range.
Gecode::Int::ViewRanges::min
int min(void) const
Return smallest value of range.
Gecode::Int::ViewRanges::width
unsigned int width(void) const
Return width of range (distance between minimum and maximum).
Gecode::Options
Options for scripts
Definition driver.hh:366
Gecode::Options::threads
void threads(double n)
Set number of parallel threads.
Definition options.hpp:292
Gecode::PropagatorGroup::all
static PropagatorGroup all
Group of all propagators.
Definition core.hpp:789
Gecode::Reify
Reification specification.
Definition int.hh:876
Gecode::Reify::var
BoolVar var(void) const
Return Boolean control variable.
Definition reify.hpp:48
Gecode::Reify::mode
ReifyMode mode(void) const
Return reification mode.
Definition reify.hpp:56
Gecode::Search::Base::next
virtual T * next(void)
Return next solution (NULL, if none exists or search has been stopped).
Definition base.hpp:46
Gecode::Space
Computation spaces.
Definition core.hpp:1742
Gecode::Space::c
struct Gecode::Space::@055132133326276162005044145100211202071356247106::@155123175027073262103111264343315000271204104107 c
Data available only during copying.
Gecode::VarArray::assigned
bool assigned(void) const
Test if all variables are assigned.
Definition array.hpp:1026
Gecode::VarArray::size
int size(void) const
Return size of array (number of elements).
Definition array.hpp:926
Gecode::VarImpVar::assigned
bool assigned(void) const
Test whether view is assigned.
Definition var.hpp:111
Test::Base::rand
static Gecode::Support::RandomGenerator rand
Random number generator.
Definition test.hh:134
Test::Base::fixpoint
static bool fixpoint(void)
Throw a coin whether to compute a fixpoint.
Definition test.hpp:66
Test::Int::Assignment
Base class for assignments
Definition int.hh:59
Test::Int::Assignment::d
Gecode::IntSet d
Domain for each variable.
Definition int.hh:62
Test::Int::Assignment::n
int n
Number of variables.
Definition int.hh:61
Test::Int::CpltAssignment
Generate all assignments.
Definition int.hh:79
Test::Int::CpltAssignment::dsv
Gecode::IntSetValues * dsv
Iterator for each variable.
Definition int.hh:81
Test::Int::CpltAssignment::operator++
virtual void operator++(void)
Move to next assignment.
Definition int.cpp:48
Test::Int::RandomAssignment::a
int a
How many assigments still to be generated Generate new value according to domain.
Definition int.hh:99
Test::Int::RandomAssignment::vals
int * vals
The current values for the variables.
Definition int.hh:98
Test::Int::RandomAssignment::randval
int randval(void)
Definition int.hpp:76
Test::Int::RandomAssignment::operator++
virtual void operator++(void)
Move to next assignment.
Definition int.cpp:63
Test::Int::RandomMixAssignment::_n1
int _n1
How many variables in the second set.
Definition int.hh:120
Test::Int::RandomMixAssignment::_d1
Gecode::IntSet _d1
Domain for second set of variables Generate new value according to domain d.
Definition int.hh:121
Test::Int::RandomMixAssignment::a
int a
How many assigments still to be generated.
Definition int.hh:119
Test::Int::RandomMixAssignment::vals
int * vals
The current values for the variables.
Definition int.hh:118
Test::Int::RandomMixAssignment::operator++
virtual void operator++(void)
Move to next assignment.
Definition int.cpp:70
Test::Int::RandomMixAssignment::randval
int randval(const Gecode::IntSet &d)
Definition int.hpp:109
Test::Int::TestSpace
Space for executing tests.
Definition int.hh:149
Test::Int::TestSpace::r
Gecode::Reify r
Reification information.
Definition int.hh:156
Test::Int::TestSpace::TestSpace
TestSpace(int n, Gecode::IntSet &d, Test *t)
Create test space without reification.
Definition int.cpp:91
Test::Int::TestSpace::d
Gecode::IntSet d
Initial domain.
Definition int.hh:152
Test::Int::TestSpace::rndrel
void rndrel(const Assignment &a, int i, Gecode::IntRelType &irt, int &v)
Randomly select a pruning rel for variable i.
Definition int.cpp:181
Test::Int::TestSpace::test
Test * test
The test currently run.
Definition int.hh:158
Test::Int::TestSpace::copy
virtual Gecode::Space * copy(void)
Copy space during cloning.
Definition int.cpp:132
Test::Int::TestSpace::post
void post(void)
Post propagator.
Definition int.cpp:145
Test::Int::TestSpace::assigned
bool assigned(void) const
Test whether all variables are assigned.
Definition int.cpp:137
Test::Int::TestSpace::prune
void prune(void)
Prune some random values for some random variable.
Definition int.cpp:316
Test::Int::TestSpace::bound
void bound(void)
Assing a random variable to a random bound.
Definition int.cpp:272
Test::Int::TestSpace::assign
void assign(const Assignment &a, bool skip=false)
Assign all (or all but one, if skip is true) variables to values in a.
Definition int.cpp:259
Test::Int::TestSpace::failed
bool failed(void)
Compute a fixpoint and check for failure.
Definition int.cpp:158
Test::Int::TestSpace::reified
bool reified
Whether the test is for a reified propagator.
Definition int.hh:160
Test::Int::TestSpace::prune
void prune(int i, bool bounds_only)
Prune some random values from variable i.
Definition int.cpp:280
Test::Int::TestSpace::rndvar
int rndvar(void)
Randomly select an unassigned variable.
Definition int.cpp:170
Test::Int::TestSpace::disabled
bool disabled(const Assignment &a, TestSpace &c, bool testfix)
Prune values also in a space c with disabled propagators, but not those in assignment a.
Definition int.cpp:373
Test::Int::TestSpace::disable
void disable(void)
Disable propagators in space and compute fixpoint (make all idle).
Definition int.cpp:367
Test::Int::TestSpace::x
Gecode::IntVarArray x
Variables to be tested.
Definition int.hh:154
Test::Int::TestSpace::enable
void enable(void)
Enable propagators in space.
Definition int.cpp:362
Test::Int::TestSpace::rel
void rel(int i, Gecode::IntRelType irt, int n)
Perform integer tell operation on x[i].
Definition int.cpp:233
Test::Int::TestSpace::propagators
unsigned int propagators(void)
Return the number of propagators.
Definition int.cpp:421
Test::Int::Test::pmi
bool pmi(void) const
Test whether reverse implication as reification mode is supported.
Definition int.hpp:161
Test::Int::Test::run
virtual bool run(void)
Perform test.
Definition int.cpp:471
Test::Int::Test::ignore
virtual bool ignore(const Assignment &) const
Whether to ignore assignment for reification.
Definition int.cpp:462
Test::Int::Test::testsearch
bool testsearch
Whether to perform search test.
Definition int.hh:238
Test::Int::Test::testfix
bool testfix
Whether to perform fixpoint test.
Definition int.hh:240
Test::Int::Test::post
virtual void post(Gecode::Space &home, Gecode::IntVarArray &x)=0
Post constraint.
Test::Int::Test::eqv
bool eqv(void) const
Test whether equivalence as reification mode is supported.
Definition int.hpp:153
Test::Int::Test::arity
int arity
Number of variables.
Definition int.hh:226
Test::Int::Test::solution
virtual bool solution(const Assignment &) const =0
Check for solution.
Test::Int::Test::assignment
virtual Assignment * assignment(void) const
Create assignment.
Definition int.cpp:440
Test::Int::Test::dom
Gecode::IntSet dom
Domain of variables.
Definition int.hh:228
Test::Int::Test::imp
bool imp(void) const
Test whether implication as reification mode is supported.
Definition int.hpp:157
Test::Int::Test::contest
ConTestLevel contest
Whether to test for certain consistency.
Definition int.hh:236
Test::ind
Simple class for describing identation.
Definition test.hh:66
Gecode::branch
void branch(Home home, const FloatVarArgs &x, FloatVarBranch vars, FloatValBranch vals, FloatBranchFilter bf=nullptr, FloatVarValPrint vvp=nullptr)
Branch over x with variable selection vars and value selection vals.
Definition branch.cpp:39
Gecode::rel
void rel(Home home, FloatVar x0, FloatRelType frt, FloatVar x1)
Post propagator for .
Definition rel.cpp:68
Gecode::IntRelType
IntRelType
Relation types for integers.
Definition int.hh:925
Gecode::ReifyMode
ReifyMode
Mode for reification.
Definition int.hh:848
Gecode::BoolOpType
BoolOpType
Operation types for Booleans.
Definition int.hh:950
Gecode::IntPropLevel
IntPropLevel
Propagation levels for integer propagators.
Definition int.hh:974
Gecode::IRT_EQ
@ IRT_EQ
Equality ( ).
Definition int.hh:926
Gecode::IRT_NQ
@ IRT_NQ
Disequality ( ).
Definition int.hh:927
Gecode::IRT_GQ
@ IRT_GQ
Greater or equal ( ).
Definition int.hh:930
Gecode::IRT_LE
@ IRT_LE
Less ( ).
Definition int.hh:929
Gecode::IRT_GR
@ IRT_GR
Greater ( ).
Definition int.hh:931
Gecode::IRT_LQ
@ IRT_LQ
Less or equal ( ).
Definition int.hh:928
Gecode::RM_IMP
@ RM_IMP
Implication for reification.
Definition int.hh:862
Gecode::RM_PMI
@ RM_PMI
Inverse implication for reification.
Definition int.hh:869
Gecode::RM_EQV
@ RM_EQV
Equivalence for reification (default).
Definition int.hh:855
Gecode::BOT_OR
@ BOT_OR
Disjunction.
Definition int.hh:952
Gecode::BOT_EQV
@ BOT_EQV
Equivalence.
Definition int.hh:954
Gecode::BOT_IMP
@ BOT_IMP
Implication.
Definition int.hh:953
Gecode::BOT_XOR
@ BOT_XOR
Exclusive or.
Definition int.hh:955
Gecode::BOT_AND
@ BOT_AND
Conjunction.
Definition int.hh:951
Gecode::IPL_BASIC
@ IPL_BASIC
Use basic propagation algorithm.
Definition int.hh:981
Gecode::IPL_BASIC_ADVANCED
@ IPL_BASIC_ADVANCED
Use both.
Definition int.hh:983
Gecode::IPL_DOM
@ IPL_DOM
Domain propagation Options: basic versus advanced propagation.
Definition int.hh:979
Gecode::IPL_VAL
@ IPL_VAL
Value propagation.
Definition int.hh:977
Gecode::IPL_ADVANCED
@ IPL_ADVANCED
Use advanced propagation algorithm.
Definition int.hh:982
Gecode::IPL_BND
@ IPL_BND
Bounds propagation.
Definition int.hh:978
Gecode::Space::Space
Space(void)
Default constructor.
Definition core.cpp:115
Gecode::Space::status
SpaceStatus status(StatusStatistics &stat=unused_status)
Query space status.
Definition core.cpp:252
Gecode::Space::clone
Space * clone(CloneStatistics &stat=unused_clone) const
Clone space.
Definition core.hpp:3224
Gecode::SS_FAILED
@ SS_FAILED
Space is failed
Definition core.hpp:1682
Gecode
Gecode toplevel namespace
Gecode::min
void min(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Definition arithmetic.cpp:67
Gecode::INT_VAR_NONE
IntVarBranch INT_VAR_NONE(void)
Select first unassigned variable.
Definition var.hpp:96
Gecode::dom
void dom(Home home, FloatVar x, FloatVal n)
Propagates .
Definition dom.cpp:40
Gecode::INT_VAL_MIN
IntValBranch INT_VAL_MIN(void)
Select smallest value.
Definition val.hpp:55
Gecode::max
void max(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Definition arithmetic.cpp:49
Test::Int
Testing finite domain integers.
Definition int.cpp:40
Test::Int::CTL_BOUNDS_Z
@ CTL_BOUNDS_Z
Test for bounds(z)-consistency.
Definition int.hh:143
Test::Int::CTL_BOUNDS_D
@ CTL_BOUNDS_D
Test for bounds(d)-consistency.
Definition int.hh:142
Test::Int::CTL_NONE
@ CTL_NONE
No consistency-test.
Definition int.hh:140
Test::Int::CTL_DOMAIN
@ CTL_DOMAIN
Test for domain-consistency.
Definition int.hh:141
Test
General test support.
Definition afc.cpp:39
Test::olog
std::ostringstream olog
Stream used for logging.
Definition test.cpp:53
Test::opt
Options opt
The options.
Definition test.cpp:97
START_TEST
#define START_TEST(T)
Start new test.
Definition array.cpp:48
CHECK_TEST
#define CHECK_TEST(T, M)
Check the test result and handle failed test.
Definition array.cpp:40
operator<<
std::ostream & operator<<(std::ostream &os, const Test::Int::Assignment &a)
Definition int.cpp:81
int.hh