rel.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 Rel {
static IntSet ds_33(-3,3);
static IntSet ds_03(0,3);
class RelBin : public SetTest {
private:
Gecode::SetRelType srt;
bool shared;
public:
RelBin(Gecode::SetRelType srt0, bool shared0)
: SetTest("Rel::Bin::"+str(srt0)+"::S"+(shared0 ? "1":"0"),
shared0 ? 1 : 2,ds_33,true)
, srt(srt0), shared(shared0){}
int minSymDiff(const SetAssignment& x) const {
int x1 = shared ? x[0] : x[1];
typedef Iter::Ranges::Diff<CountableSetRanges,CountableSetRanges> Diff;
CountableSetRanges xr00(x.lub, x[0]);
CountableSetRanges xr10(x.lub, x1);
Diff a(xr00,xr10);
CountableSetRanges xr01(x.lub, x[0]);
CountableSetRanges xr11(x.lub, x1);
Diff b(xr11,xr01);
Iter::Ranges::Union<Diff,Diff> u(a,b);
return u() ? u.min() : Gecode::Set::Limits::max+1;
}
bool in(int i, CountableSetRanges& c, bool eq=false) const {
if (eq && i==Gecode::Set::Limits::max+1)
return true;
Iter::Ranges::Singleton s(i,i);
return Iter::Ranges::subset(s,c);
}
bool solution(const SetAssignment& x) const {
int x1 = shared ? x[0] : x[1];
CountableSetRanges xr0(x.lub, x[0]);
CountableSetRanges xr1(x.lub, x1);
switch (srt) {
case SRT_EQ: return Iter::Ranges::equal(xr0, xr1);
case SRT_NQ: return !Iter::Ranges::equal(xr0, xr1);
case SRT_LQ: return (!xr0()) || in(minSymDiff(x),xr1,true);
case SRT_LE: return xr0() ? in(minSymDiff(x),xr1) : xr1();
case SRT_GQ: return (!xr1()) || in(minSymDiff(x),xr0,true);
case SRT_GR: return xr1() ? in(minSymDiff(x),xr0) : xr0();
case SRT_SUB: return Iter::Ranges::subset(xr0, xr1);
case SRT_SUP: return Iter::Ranges::subset(xr1, xr0);
case SRT_DISJ:
{
Iter::Ranges::Inter<CountableSetRanges,CountableSetRanges>
inter(xr0,xr1);
return !inter();
}
case SRT_CMPL:
{
Gecode::Set::RangesCompl<CountableSetRanges> rc(xr0);
return Iter::Ranges::equal(rc,xr1);
}
default:
GECODE_NEVER;
}
GECODE_NEVER;
return false;
}
void post(Space& home, SetVarArray& x, IntVarArray&) {
if (!shared)
Gecode::rel(home, x[0], srt, x[1]);
else
Gecode::rel(home, x[0], srt, x[0]);
}
void post(Space& home, SetVarArray& x, IntVarArray&, Reify r) {
if (!shared)
Gecode::rel(home, x[0], srt, x[1], r);
else
Gecode::rel(home, x[0], srt, x[0], r);
}
};
class ITE : public SetTest {
public:
ITE(void)
: SetTest("ITE",3,ds_03,false,1) {}
virtual bool solution(const SetAssignment& x) const {
if ((x.intval() < 0) || (x.intval() > 1))
return false;
if (x.intval() == 1) {
CountableSetRanges xr0(x.lub, x[0]);
CountableSetRanges xr2(x.lub, x[2]);
return Iter::Ranges::equal(xr0,xr2);
} else {
CountableSetRanges xr1(x.lub, x[1]);
CountableSetRanges xr2(x.lub, x[2]);
return Iter::Ranges::equal(xr1,xr2);
}
}
void post(Space& home, SetVarArray& x, IntVarArray& y) {
Gecode::ite(home, Gecode::channel(home,y[0]), x[0], x[1], x[2]);
}
};
RelBin _relbin_eq(Gecode::SRT_EQ,false);
RelBin _relbin_lq(Gecode::SRT_LQ,false);
RelBin _relbin_le(Gecode::SRT_LE,false);
RelBin _relbin_gq(Gecode::SRT_GQ,false);
RelBin _relbin_gr(Gecode::SRT_GR,false);
RelBin _relbin_nq(Gecode::SRT_NQ,false);
RelBin _relbin_sub(Gecode::SRT_SUB,false);
RelBin _relbin_sup(Gecode::SRT_SUP,false);
RelBin _relbin_disj(Gecode::SRT_DISJ,false);
RelBin _relbin_cmpl(Gecode::SRT_CMPL,false);
RelBin _relbin_shared_eq(Gecode::SRT_EQ,true);
RelBin _relbin_shared_lq(Gecode::SRT_LQ,true);
RelBin _relbin_shared_le(Gecode::SRT_LE,true);
RelBin _relbin_shared_gq(Gecode::SRT_GQ,true);
RelBin _relbin_shared_gr(Gecode::SRT_GR,true);
RelBin _relbin_shared_nq(Gecode::SRT_NQ,true);
RelBin _relbin_shared_sub(Gecode::SRT_SUB,true);
RelBin _relbin_shared_sup(Gecode::SRT_SUP,true);
RelBin _relbin_shared_disj(Gecode::SRT_DISJ,true);
RelBin _relbin_shared_cmpl(Gecode::SRT_CMPL,true);
ITE _ite;
}}}
// STATISTICS: test-set
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::MinMax::min
int min(void) const
Return smallest value of range.
Definition ranges-minmax.hpp:99
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::Reify
Reification specification.
Definition int.hh:876
Gecode::SetVarArray
Set variable array
Definition set.hh:570
Gecode::Set::RangesCompl
A complement iterator spezialized for the BndSet limits.
Definition var-imp.hpp:293
Gecode::Space
Computation spaces.
Definition core.hpp:1742
Test::Set::CountableSetRanges
Range iterator producing subsets of an IntSet.
Definition set.hh:99
Test::Set::Rel::ITE
Test for if-then-else-constraint
Definition rel.cpp:133
Test::Set::Rel::ITE::ITE
ITE(void)
Construct and register test.
Definition rel.cpp:136
Test::Set::Rel::ITE::post
void post(Space &home, SetVarArray &x, IntVarArray &y)
Post constraint on x and y.
Definition rel.cpp:153
Test::Set::Rel::ITE::solution
virtual bool solution(const SetAssignment &x) const
Check whether x is a solution.
Definition rel.cpp:139
Test::Set::Rel::RelBin
Test for binary set relation constraint
Definition rel.cpp:55
Test::Set::Rel::RelBin::in
bool in(int i, CountableSetRanges &c, bool eq=false) const
Definition rel.cpp:77
Test::Set::Rel::RelBin::minSymDiff
int minSymDiff(const SetAssignment &x) const
Definition rel.cpp:65
Test::Set::Rel::RelBin::post
void post(Space &home, SetVarArray &x, IntVarArray &, Reify r)
Post reified constraint on x for b.
Definition rel.cpp:124
Test::Set::Rel::RelBin::post
void post(Space &home, SetVarArray &x, IntVarArray &)
Post constraint on x.
Definition rel.cpp:117
Test::Set::Rel::RelBin::solution
bool solution(const SetAssignment &x) const
Test whether x is solution
Definition rel.cpp:84
Test::Set::Rel::RelBin::RelBin
RelBin(Gecode::SetRelType srt0, bool shared0)
Create and register test.
Definition rel.cpp:61
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::lub
Gecode::IntSet lub
The common superset for all domains.
Definition set.hh:154
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::ite
void ite(Home home, BoolVar b, FloatVar x, FloatVar y, FloatVar z)
Post propagator for if-then-else constraint.
Definition bool.cpp:39
Gecode::SetRelType
SetRelType
Common relation types for sets.
Definition set.hh:643
Gecode::SRT_GQ
@ SRT_GQ
Greater or equal ( ).
Definition set.hh:652
Gecode::SRT_CMPL
@ SRT_CMPL
Complement.
Definition set.hh:649
Gecode::SRT_GR
@ SRT_GR
Greater ( ).
Definition set.hh:653
Gecode::SRT_LQ
@ SRT_LQ
Less or equal ( ).
Definition set.hh:650
Gecode::SRT_NQ
@ SRT_NQ
Disequality ( ).
Definition set.hh:645
Gecode::SRT_LE
@ SRT_LE
Less ( ).
Definition set.hh:651
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
minimodel.hh
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::equal
bool equal(I &i, J &j)
Check whether range iterators i and j are equal.
Definition ranges-operations.hpp:84
Gecode::Set::Limits::max
const int max
Largest allowed integer in integer set.
Definition set.hh:97
Gecode
Gecode toplevel namespace
Gecode::channel
void channel(Home home, FloatVar x0, IntVar x1)
Post propagator for channeling a float and an integer variable .
Definition channel.cpp:41
Gecode::inter
SetExpr inter(const SetVarArgs &)
Intersection of set variables.
Definition set-expr.cpp:696
Test::Set::Rel
Tests for relation constraints
Definition rel.cpp:43
Test::Set::Rel::_relbin_shared_nq
RelBin _relbin_shared_nq(Gecode::SRT_NQ, true)
Test::Set::Rel::_relbin_shared_cmpl
RelBin _relbin_shared_cmpl(Gecode::SRT_CMPL, true)
Test::Set::Rel::_relbin_shared_le
RelBin _relbin_shared_le(Gecode::SRT_LE, true)
Test::Set::Rel::_relbin_shared_gq
RelBin _relbin_shared_gq(Gecode::SRT_GQ, true)
Test::Set::Rel::_relbin_gr
RelBin _relbin_gr(Gecode::SRT_GR, false)
Test::Set::Rel::_ite
ITE _ite
Definition rel.cpp:179
Test::Set::Rel::_relbin_shared_disj
RelBin _relbin_shared_disj(Gecode::SRT_DISJ, true)
Test::Set::Rel::_relbin_disj
RelBin _relbin_disj(Gecode::SRT_DISJ, false)
Test::Set::Rel::_relbin_le
RelBin _relbin_le(Gecode::SRT_LE, false)
Test::Set::Rel::_relbin_eq
RelBin _relbin_eq(Gecode::SRT_EQ, false)
Test::Set::Rel::_relbin_shared_gr
RelBin _relbin_shared_gr(Gecode::SRT_GR, true)
Test::Set::Rel::_relbin_cmpl
RelBin _relbin_cmpl(Gecode::SRT_CMPL, false)
Test::Set::Rel::_relbin_shared_eq
RelBin _relbin_shared_eq(Gecode::SRT_EQ, true)
Test::Set::Rel::_relbin_shared_sub
RelBin _relbin_shared_sub(Gecode::SRT_SUB, true)
Test::Set::Rel::_relbin_gq
RelBin _relbin_gq(Gecode::SRT_GQ, false)
Test::Set::Rel::_relbin_sub
RelBin _relbin_sub(Gecode::SRT_SUB, false)
Test::Set::Rel::_relbin_lq
RelBin _relbin_lq(Gecode::SRT_LQ, false)
Test::Set::Rel::_relbin_shared_sup
RelBin _relbin_shared_sup(Gecode::SRT_SUP, true)
Test::Set::Rel::_relbin_shared_lq
RelBin _relbin_shared_lq(Gecode::SRT_LQ, true)
Test::Set::Rel::_relbin_nq
RelBin _relbin_nq(Gecode::SRT_NQ, false)
Test::Set::Rel::_relbin_sup
RelBin _relbin_sup(Gecode::SRT_SUP, false)
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