int.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>
* Christian Schulte <schulte@gecode.org>
*
* Copyright:
* Guido Tack, 2004
* Christian Schulte, 2004
*
* 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/set.hh>
#include <gecode/set/int.hh>
#include <gecode/set/rel.hh>
namespace Gecode {
void
rel(Home home, SetVar s, IntRelType rt, IntVar x) {
GECODE_POST;
switch (rt) {
case IRT_EQ:
{
Gecode::Int::IntView xv(x);
Set::SingletonView xsingle(xv);
GECODE_ES_FAIL(
(Set::Rel::Eq<Set::SetView,Set::SingletonView>
::post(home,s,xsingle)));
}
break;
case IRT_NQ:
{
Gecode::Set::SetView sv(s);
GECODE_ME_FAIL( sv.cardMin(home, 1));
Gecode::Int::IntView xv(x);
Set::SingletonView xsingle(xv);
GECODE_ES_FAIL(
(Set::Rel::NoSubset<Set::SingletonView,Set::SetView>
::post(home,xsingle,sv)));
}
break;
case IRT_LQ:
{
IntVar tmp(home, Int::Limits::min, Int::Limits::max);
rel(home, tmp, IRT_LQ, x);
GECODE_ES_FAIL(Set::Int::MaxElement<Set::SetView>::post(home,s,tmp));
}
break;
case IRT_LE:
{
IntVar tmp(home, Int::Limits::min, Int::Limits::max);
rel(home, tmp, IRT_LE, x);
GECODE_ES_FAIL(Set::Int::MaxElement<Set::SetView>::post(home,s,tmp));
}
break;
case IRT_GQ:
{
IntVar tmp(home, Int::Limits::min, Int::Limits::max);
rel(home, tmp, IRT_GQ, x);
GECODE_ES_FAIL(Set::Int::MinElement<Set::SetView>::post(home,s,tmp));
}
break;
case IRT_GR:
{
IntVar tmp(home, Int::Limits::min, Int::Limits::max);
rel(home, tmp, IRT_GR, x);
GECODE_ES_FAIL(Set::Int::MinElement<Set::SetView>::post(home,s,tmp));
}
break;
default:
throw Int::UnknownRelation("Set::rel");
}
}
}
namespace Gecode { namespace Set { namespace Int {
void remin(Home home, SetVar s, IntVar m, Reify r) {
IntVar c(home, 0, static_cast<int>(Set::Limits::card));
cardinality(home, s, c);
// Whether set is not empty
BoolVar ne(home, 0, 1);
rel(home, c, IRT_GR, 0, ne);
if (r.mode() != RM_PMI)
rel(home, r.var(), BOT_IMP, ne, 1);
min(home, s, m, ne);
}
void remax(Home home, SetVar s, IntVar m, Reify r) {
IntVar c(home, 0, static_cast<int>(Set::Limits::card));
cardinality(home, s, c);
// Whether set is not empty
BoolVar ne(home, 0, 1);
rel(home, c, IRT_GR, 0, ne);
if (r.mode() != RM_PMI)
rel(home, r.var(), BOT_IMP, ne, 1);
max(home, s, m, ne);
}
}}}
namespace Gecode {
void
rel(Home home, SetVar s, IntRelType rt, IntVar x, Reify r) {
GECODE_POST;
switch (rt) {
case IRT_EQ:
{
Gecode::Int::IntView xv(x);
Set::SingletonView xs(xv);
switch (r.mode()) {
case RM_EQV:
GECODE_ES_FAIL((Set::Rel::ReEq<Set::SetView,Set::SingletonView,
Gecode::Int::BoolView,RM_EQV>
::post(home,s,xs,r.var())));
break;
case RM_IMP:
GECODE_ES_FAIL((Set::Rel::ReEq<Set::SetView,Set::SingletonView,
Gecode::Int::BoolView,RM_IMP>
::post(home,s,xs,r.var())));
break;
case RM_PMI:
GECODE_ES_FAIL((Set::Rel::ReEq<Set::SetView,Set::SingletonView,
Gecode::Int::BoolView,RM_PMI>
::post(home,s,xs,r.var())));
break;
default:
throw Gecode::Int::UnknownReifyMode("Set::rel");
}
}
break;
case IRT_NQ:
{
IntVar c(home, 0, static_cast<int>(Set::Limits::card));
cardinality(home, s, c);
// Whether set is not empty
BoolVar ne(home, 0 , 1);
rel(home, c, IRT_GR, 0, ne);
// Whether {x} is a subset of s
BoolVar ss(home, 0 , 1);
rel(home, x, SRT_SUB, s, ss);
BoolVar b;
switch (r.mode()) {
case RM_EQV:
b=r.var();
break;
case RM_IMP:
b=BoolVar(home, 0, 1);
rel(home, r.var(), BOT_IMP, b, 1);
break;
case RM_PMI:
b=BoolVar(home, 0, 1);
rel(home, b, BOT_IMP, r.var(), 1);
break;
default:
throw Gecode::Int::UnknownReifyMode("Set::rel");
}
BoolVarArgs p(1); p[0]=ne;
BoolVarArgs n(1); n[0]=ss;
clause(home, BOT_AND, p, n, b);
}
break;
case IRT_LQ:
{
IntVar tmp(home, Int::Limits::min, Int::Limits::max);
rel(home, tmp, IRT_LQ, x, r);
Gecode::Set::Int::remax(home, s, tmp, r);
}
break;
case IRT_LE:
{
IntVar tmp(home, Int::Limits::min, Int::Limits::max);
rel(home, tmp, IRT_LE, x, r);
Gecode::Set::Int::remax(home, s, tmp, r);
}
break;
case IRT_GQ:
{
IntVar tmp(home, Int::Limits::min, Int::Limits::max);
rel(home, tmp, IRT_GQ, x, r);
Gecode::Set::Int::remin(home, s, tmp, r);
}
break;
case IRT_GR:
{
IntVar tmp(home, Int::Limits::min, Int::Limits::max);
rel(home, tmp, IRT_GR, x, r);
Gecode::Set::Int::remin(home, s, tmp, r);
}
break;
default:
throw Int::UnknownRelation("Set::rel");
}
}
void
min(Home home, SetVar s, IntVar x) {
GECODE_POST;
GECODE_ES_FAIL(Set::Int::MinElement<Set::SetView>::post(home,s,x));
}
void
notMin(Home home, SetVar s, IntVar x) {
GECODE_POST;
GECODE_ES_FAIL(Set::Int::NotMinElement<Set::SetView>::post(home,s,x));
}
void
min(Home home, SetVar s, IntVar x, Reify r) {
GECODE_POST;
switch (r.mode()) {
case RM_EQV:
GECODE_ES_FAIL((Set::Int::ReMinElement<Set::SetView,RM_EQV>
::post(home,s,x,r.var())));
break;
case RM_IMP:
GECODE_ES_FAIL((Set::Int::ReMinElement<Set::SetView,RM_IMP>
::post(home,s,x,r.var())));
break;
case RM_PMI:
GECODE_ES_FAIL((Set::Int::ReMinElement<Set::SetView,RM_PMI>
::post(home,s,x,r.var())));
break;
default: throw Gecode::Int::UnknownReifyMode("Set::min");
}
}
void
max(Home home, SetVar s, IntVar x) {
GECODE_POST;
GECODE_ES_FAIL(Set::Int::MaxElement<Set::SetView>::post(home,s,x));
}
void
notMax(Home home, SetVar s, IntVar x) {
GECODE_POST;
GECODE_ES_FAIL(Set::Int::NotMaxElement<Set::SetView>::post(home,s,x));
}
void
max(Home home, SetVar s, IntVar x, Reify r) {
GECODE_POST;
switch (r.mode()) {
case RM_EQV:
GECODE_ES_FAIL((Set::Int::ReMaxElement<Set::SetView,RM_EQV>
::post(home,s,x,r.var())));
break;
case RM_IMP:
GECODE_ES_FAIL((Set::Int::ReMaxElement<Set::SetView,RM_IMP>
::post(home,s,x,r.var())));
break;
case RM_PMI:
GECODE_ES_FAIL((Set::Int::ReMaxElement<Set::SetView,RM_PMI>
::post(home,s,x,r.var())));
break;
default: throw Gecode::Int::UnknownReifyMode("Set::max");
}
}
void weights(Home home, IntSharedArray elements, IntSharedArray weights,
SetVar x, IntVar y) {
GECODE_POST;
GECODE_ES_FAIL(Set::Int::Weights<Set::SetView>::post(home,elements,
weights,x,y));
}
}
// STATISTICS: set-post
Gecode::BoolVarArgs
Passing Boolean variables.
Definition int.hh:712
Gecode::BoolVar
Boolean integer variables.
Definition int.hh:512
Gecode::Home
Home class for posting propagators
Definition core.hpp:856
Gecode::IntVar
Integer variables.
Definition int.hh:371
Gecode::Int::BoolView
Boolean view for Boolean variables.
Definition view.hpp:1380
Gecode::Int::IntView
Integer view for integer variables.
Definition view.hpp:129
Gecode::Int::UnknownReifyMode
Exception: Unknown reification mode passed as argument
Definition exception.hpp:115
Gecode::Int::UnknownRelation
Exception: Unknown relation passed as argument
Definition exception.hpp:87
Gecode::Reify
Reification specification.
Definition int.hh:876
Gecode::SetVar
Set variables
Definition set.hh:127
Gecode::Set::Int::MaxElement::post
static ExecStatus post(Home home, View s, Gecode::Int::IntView x)
Post propagator for x is the largest element of s.
Definition minmax.hpp:408
Gecode::Set::Int::MinElement::post
static ExecStatus post(Home home, View s, Gecode::Int::IntView x)
Post propagator for x is the minimal element of s.
Definition minmax.hpp:53
Gecode::Set::Int::NotMaxElement::post
static ExecStatus post(Home home, View s, Gecode::Int::IntView x)
Post propagator for x is not the largest element of s.
Definition minmax.hpp:457
Gecode::Set::Int::NotMinElement::post
static ExecStatus post(Home home, View s, Gecode::Int::IntView x)
Post propagator for x is not the minimal element of s.
Definition minmax.hpp:141
Gecode::Set::Int::ReMaxElement
Reified propagator for maximum element
Definition int.hh:200
Gecode::Set::Int::ReMinElement
Propagator for reified minimum element
Definition int.hh:113
Gecode::Set::Int::Weights::post
static ExecStatus post(Home home, const SharedArray< int > &elements, const SharedArray< int > &weights, View x, Gecode::Int::IntView y)
Post propagator for .
Definition weights.hpp:167
Gecode::Set::Rel::Eq
Propagator for set equality
Definition rel.hh:150
Gecode::Set::Rel::NoSubset
Propagator for the negated subset constraint
Definition rel.hh:91
Gecode::Set::Rel::ReEq
Reified equality propagator
Definition rel.hh:174
Gecode::Set::SetView
Set view for set variables
Definition view.hpp:56
Gecode::Set::SetView::cardMin
unsigned int cardMin(void) const
Return minimum cardinality.
Definition set.hpp:82
Gecode::Set::SingletonView
Singleton set view.
Definition view.hpp:594
int.hh
set.hh
GECODE_POST
#define GECODE_POST
Check for failure in a constraint post function.
Definition macros.hpp:40
GECODE_ES_FAIL
#define GECODE_ES_FAIL(es)
Check whether execution status es is failed, and fail space home.
Definition macros.hpp:103
GECODE_ME_FAIL
#define GECODE_ME_FAIL(me)
Check whether modification event me is failed, and fail space home.
Definition macros.hpp:77
Gecode::rel
void rel(Home home, FloatVar x0, FloatRelType frt, FloatVar x1)
Post propagator for .
Definition rel.cpp:68
Gecode::clause
void clause(Home home, BoolOpType o, const BoolVarArgs &x, const BoolVarArgs &y, BoolVar z, IntPropLevel ipl=IPL_DEF)
Post domain consistent propagator for Boolean clause with positive variables x and negative variables...
Definition bool.cpp:955
Gecode::IntRelType
IntRelType
Relation types for integers.
Definition int.hh:925
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_IMP
@ BOT_IMP
Implication.
Definition int.hh:953
Gecode::BOT_AND
@ BOT_AND
Conjunction.
Definition int.hh:951
Gecode::weights
void weights(Home home, IntSharedArray elements, IntSharedArray weights, SetVar x, IntVar y)
Post propagator for .
Definition int.cpp:292
Gecode::notMin
void notMin(Home home, SetVar s, IntVar x)
Post propagator that x is not the minimal element of s.
Definition int.cpp:235
Gecode::notMax
void notMax(Home home, SetVar s, IntVar x)
Post propagator that x is not the maximal element of s.
Definition int.cpp:267
Gecode::SRT_SUB
@ SRT_SUB
Subset ( ).
Definition set.hh:646
Gecode::Int::Limits::min
const int min
Smallest allowed integer value.
Definition int.hh:118
Gecode::Int::Limits::max
const int max
Largest allowed integer value.
Definition int.hh:116
Gecode::Set::Int
Propagators connecting set and int variables.
Definition int.cpp:105
Gecode::Set::Int::remax
void remax(Home home, SetVar s, IntVar m, Reify r)
Reify m to be the maximum of s.
Definition int.cpp:120
Gecode::Set::Int::remin
void remin(Home home, SetVar s, IntVar m, Reify r)
Reify m to be the minimum of s.
Definition int.cpp:108
Gecode::Set::Limits::card
const unsigned int card
Maximum cardinality of an integer set.
Definition set.hh:101
Gecode::Set
Finite integer sets.
Definition var-imp.hpp:137
Gecode
Gecode toplevel namespace
Gecode::IntSharedArray
SharedArray< int > IntSharedArray
Arrays of integers that can be shared among several element constraints.
Definition int.hh:1477
Gecode::min
void min(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Definition arithmetic.cpp:67
Gecode::post
TFE post(PropagatorGroup g)
Only post functions (but not propagators) from g are considered.
Definition filter.cpp:138
Gecode::max
void max(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Definition arithmetic.cpp:49
Gecode::cardinality
LinIntExpr cardinality(const SetExpr &)
Cardinality of set expression.
Definition set-expr.cpp:817
rel.hh