set.hpp
Go to the documentation of this file.
/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
/*
* Main authors:
* Guido Tack <tack@gecode.org>
* Gabor Szokoli <szokoli@gecode.org>
*
* Contributing authors:
* Christian Schulte <schulte@gecode.org>
*
* Copyright:
* Guido Tack, 2004
* Christian Schulte, 2004
* Gabor Szokoli, 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.
*
*/
namespace Gecode { namespace Set {
/*
* Creation of new variable implementations
*
*/
forceinline
SetVarImp::SetVarImp(Space& home)
: SetVarImpBase(home), lub(home), glb(home) {
lub.card(Limits::card);
assert(lub.card()==lub.size());
}
forceinline
SetVarImp::SetVarImp(Space& home,int lbMin,int lbMax,int ubMin,int ubMax,
unsigned int cardMin, unsigned int cardMax)
: SetVarImpBase(home),
lub(home,ubMin,ubMax), glb(home,lbMin,lbMax) {
glb.card(std::max(cardMin, glb.size() ));
lub.card(std::min(cardMax, lub.size() ));
}
forceinline
SetVarImp::SetVarImp(Space& home,
const IntSet& theGlb,int ubMin,int ubMax,
unsigned int cardMin, unsigned int cardMax)
: SetVarImpBase(home),
lub(home,ubMin,ubMax), glb(home,theGlb) {
glb.card(std::max(cardMin, glb.size() ));
lub.card(std::min(cardMax, lub.size() ));
}
forceinline
SetVarImp::SetVarImp(Space& home,
int lbMin,int lbMax,const IntSet& theLub,
unsigned int cardMin, unsigned int cardMax)
: SetVarImpBase(home),
lub(home,theLub), glb(home,lbMin,lbMax) {
glb.card(std::max(cardMin, glb.size() ));
lub.card(std::min(cardMax, lub.size() ));
}
forceinline
SetVarImp::SetVarImp(Space& home,
const IntSet& theGlb,const IntSet& theLub,
unsigned int cardMin, unsigned int cardMax)
: SetVarImpBase(home), lub(home,theLub), glb(home,theGlb) {
glb.card(std::max(cardMin, glb.size() ));
lub.card(std::min(cardMax, lub.size() ));
}
forceinline bool
SetVarImp::assigned(void) const {
return glb.size() == lub.size();
}
forceinline unsigned int
SetVarImp::cardMin(void) const { return glb.card(); }
forceinline unsigned int
SetVarImp::cardMax(void) const { return lub.card(); }
forceinline bool
SetVarImp::knownIn(int i) const { return (glb.in(i)); }
forceinline bool
SetVarImp::knownOut(int i) const { return !(lub.in(i)); }
forceinline int
SetVarImp::lubMin(void) const { return lub.min(); }
forceinline int
SetVarImp::lubMax(void) const { return lub.max(); }
forceinline int
SetVarImp::lubMinN(unsigned int n) const { return lub.minN(n); }
forceinline int
SetVarImp::glbMin(void) const { return glb.min(); }
forceinline int
SetVarImp::glbMax(void) const { return glb.max(); }
forceinline unsigned int
SetVarImp::glbSize() const { return glb.size(); }
forceinline unsigned int
SetVarImp::lubSize() const { return lub.size(); }
/*
* Support for delta information
*
*/
forceinline int
SetVarImp::glbMin(const Delta& d) {
return static_cast<const SetDelta&>(d).glbMin();
}
forceinline int
SetVarImp::glbMax(const Delta& d) {
return static_cast<const SetDelta&>(d).glbMax();
}
forceinline bool
SetVarImp::glbAny(const Delta& d) {
return static_cast<const SetDelta&>(d).glbAny();
}
forceinline int
SetVarImp::lubMin(const Delta& d) {
return static_cast<const SetDelta&>(d).lubMin();
}
forceinline int
SetVarImp::lubMax(const Delta& d) {
return static_cast<const SetDelta&>(d).lubMax();
}
forceinline bool
SetVarImp::lubAny(const Delta& d) {
return static_cast<const SetDelta&>(d).lubAny();
}
forceinline ModEvent
SetVarImp::cardMin(Space& home,unsigned int newMin) {
if (cardMin() >= newMin)
return ME_SET_NONE;
if (newMin > cardMax())
return fail(home);
glb.card(newMin);
return cardMin_full(home);
}
forceinline ModEvent
SetVarImp::cardMax(Space& home,unsigned int newMax) {
if (cardMax() <= newMax)
return ME_SET_NONE;
if (cardMin() > newMax)
return fail(home);
lub.card(newMax);
return cardMax_full(home);
}
forceinline ModEvent
SetVarImp::intersect(Space& home,int i, int j) {
BndSetRanges lb(glb);
Iter::Ranges::Singleton s(i,j);
Iter::Ranges::Diff<BndSetRanges, Iter::Ranges::Singleton> probe(lb, s);
if (probe())
return fail(home);
if (assigned())
return ME_SET_NONE;
int oldMin = lub.min();
int oldMax = lub.max();
if (lub.intersect(home, i, j)) {
SetDelta d;
if (i == oldMin) {
d._lubMin = lub.max()+1;
d._lubMax = oldMax;
} else if (j == oldMax) {
d._lubMin = oldMin;
d._lubMax = lub.min()-1;
}
return processLubChange(home, d);
}
return ME_SET_NONE;
}
forceinline ModEvent
SetVarImp::intersect(Space& home,int i) {
return intersect(home, i, i);
}
template<class I>
inline ModEvent
SetVarImp::intersectI(Space& home, I& iterator) {
if (assigned()) {
BndSetRanges lbi(glb);
Iter::Ranges::Diff<BndSetRanges,I> probe(lbi,iterator);
if (probe())
return fail(home);
return ME_SET_NONE;
}
if (!iterator()) {
if (cardMin() > 0)
return fail(home);
lub.card(0);
SetDelta d(1, 0, lub.min(), lub.max());
lub.excludeAll(home);
return notify(home, ME_SET_VAL, d);
}
int mi=iterator.min();
int ma=iterator.max();
++iterator;
if (iterator())
return intersectI_full(home, mi, ma, iterator);
else
return intersect(home, mi, ma);
}
template<class I>
ModEvent
SetVarImp::intersectI_full(Space& home, int mi, int ma, I& iterator) {
Iter::Ranges::SingletonAppend<I> si(mi,ma,iterator);
if (lub.intersectI(home, si)) {
BndSetRanges ub(lub);
BndSetRanges lb(glb);
if (!Iter::Ranges::subset(lb,ub)) {
glb.become(home, lub);
glb.card(glb.size());
lub.card(glb.size());
return fail(home);
}
ModEvent me = ME_SET_LUB;
if (cardMax() > lub.size()) {
lub.card(lub.size());
if (cardMin() > cardMax()) {
glb.become(home, lub);
glb.card(glb.size());
lub.card(glb.size());
return fail(home);
}
me = ME_SET_CLUB;
}
if (cardMax() == lub.size() && cardMin() == cardMax()) {
glb.become(home, lub);
me = ME_SET_VAL;
}
SetDelta d;
return notify(home, me, d);
}
return ME_SET_NONE;
}
forceinline ModEvent
SetVarImp::include(Space& home, int i, int j) {
if (j<i)
return ME_SET_NONE;
BndSetRanges ub(lub);
Iter::Ranges::Singleton sij(i,j);
if (!Iter::Ranges::subset(sij,ub)) {
return fail(home);
}
SetDelta d;
if (glb.include(home, i, j, d))
return processGlbChange(home, d);
return ME_SET_NONE;
}
forceinline ModEvent
SetVarImp::include(Space& home, int i) {
return include(home, i, i);
}
template<class I> forceinline ModEvent
SetVarImp::includeI(Space& home, I& iterator) {
if (!iterator()) {
return ME_SET_NONE;
}
if (assigned()) {
BndSetRanges lbi(glb);
Iter::Ranges::Diff<I,BndSetRanges>
probe(iterator,lbi);
return probe() ? fail(home) : ME_SET_NONE;
}
int mi=iterator.min();
int ma=iterator.max();
++iterator;
if (iterator())
return includeI_full(home, mi, ma, iterator);
else
return include(home, mi, ma);
}
template<class I>
ModEvent
SetVarImp::includeI_full(Space& home, int mi, int ma, I& iterator) {
Iter::Ranges::SingletonAppend<I> si(mi,ma,iterator);
if (glb.includeI(home, si)) {
BndSetRanges ub(lub);
BndSetRanges lb(glb);
if (!Iter::Ranges::subset(lb,ub)) {
glb.become(home, lub);
glb.card(glb.size());
lub.card(glb.size());
return fail(home);
}
ModEvent me = ME_SET_GLB;
if (cardMin() < glb.size()) {
glb.card(glb.size());
if (cardMin() > cardMax()) {
glb.become(home, lub);
glb.card(glb.size());
lub.card(glb.size());
return fail(home);
}
me = ME_SET_CGLB;
}
if (cardMin() == glb.size() && cardMin() == cardMax()) {
lub.become(home, glb);
me = ME_SET_VAL;
}
SetDelta d;
return notify(home, me, d);
}
return ME_SET_NONE;
}
forceinline ModEvent
SetVarImp::exclude(Space& home, int i, int j) {
if (j<i)
return ME_SET_NONE;
Iter::Ranges::Singleton sij(i,j);
BndSetRanges lb(glb);
Iter::Ranges::Inter<Iter::Ranges::Singleton,BndSetRanges> probe(sij,lb);
if (probe())
return fail(home);
SetDelta d;
if (lub.exclude(home, i, j, d))
return processLubChange(home, d);
return ME_SET_NONE;
}
forceinline ModEvent
SetVarImp::exclude(Space& home, int i) {
return exclude(home, i, i);
}
template<class I>
inline ModEvent
SetVarImp::excludeI(Space& home, I& iterator) {
if (!iterator())
return ME_SET_NONE;
if (assigned()) {
BndSetRanges ubi(lub);
Iter::Ranges::Inter<BndSetRanges,I> probe(ubi,iterator);
return probe() ? fail(home) : ME_SET_NONE;
}
int mi=iterator.min();
int ma=iterator.max();
++iterator;
if (iterator())
return excludeI_full(home, mi, ma, iterator);
else
return exclude(home, mi, ma);
}
template<class I>
ModEvent
SetVarImp::excludeI_full(Space& home, int mi, int ma, I& iterator) {
Iter::Ranges::SingletonAppend<I> si(mi,ma,iterator);
if (lub.excludeI(home, si)) {
BndSetRanges ub(lub);
BndSetRanges lb(glb);
if (!Iter::Ranges::subset(lb,ub)) {
glb.become(home, lub);
glb.card(glb.size());
lub.card(glb.size());
return fail(home);
}
ModEvent me = ME_SET_LUB;
if (cardMax() > lub.size()) {
lub.card(lub.size());
if (cardMin() > cardMax()) {
glb.become(home, lub);
glb.card(glb.size());
lub.card(glb.size());
return fail(home);
}
me = ME_SET_CLUB;
}
if (cardMax() == lub.size() && cardMin() == cardMax()) {
glb.become(home, lub);
me = ME_SET_VAL;
}
SetDelta d;
return notify(home, me, d);
}
return ME_SET_NONE;
}
/*
* Copying a variable
*
*/
forceinline SetVarImp*
SetVarImp::copy(Space& home) {
return copied() ?
static_cast<SetVarImp*>(forward()) :
perform_copy(home);
}
/*
* Iterator specializations
*
*/
template<>
class LubRanges<SetVarImp*> : public BndSetRanges {
public:
LubRanges(void);
LubRanges(const SetVarImp*);
void init(const SetVarImp*);
};
forceinline
LubRanges<SetVarImp*>::LubRanges(void) {}
forceinline
LubRanges<SetVarImp*>::LubRanges(const SetVarImp* x)
: BndSetRanges(x->lub) {}
forceinline void
LubRanges<SetVarImp*>::init(const SetVarImp* x) {
BndSetRanges::init(x->lub);
}
template<>
class GlbRanges<SetVarImp*> : public BndSetRanges {
public:
GlbRanges(void);
GlbRanges(const SetVarImp* x);
void init(const SetVarImp*);
};
forceinline
GlbRanges<SetVarImp*>::GlbRanges(void) {}
forceinline
GlbRanges<SetVarImp*>::GlbRanges(const SetVarImp* x)
: BndSetRanges(x->glb) {}
forceinline void
GlbRanges<SetVarImp*>::init(const SetVarImp* x) {
BndSetRanges::init(x->glb);
}
}}
// STATISTICS: set-var
Gecode::Delta
Generic domain change information to be supplied to advisors.
Definition core.hpp:204
Gecode::IntSet
Integer sets.
Definition int.hh:174
Gecode::IntSet::min
int min(int i) const
Return minimum of range at position i.
Definition int-set-1.hpp:152
Gecode::IntSet::max
int max(int i) const
Return maximum of range at position i.
Definition int-set-1.hpp:158
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::SingletonAppend
Range iterator for appending a singleton with a range iterator
Definition ranges-singleton-append.hpp:47
Gecode::Iter::Ranges::Singleton
Range iterator for singleton range.
Definition ranges-singleton.hpp:42
Gecode::Set::BndSetRanges
Range iterator for integer sets.
Definition var-imp.hpp:185
Gecode::Set::BndSetRanges::BndSetRanges
BndSetRanges(void)
Default constructor.
Definition integerset.hpp:240
Gecode::Set::BndSetRanges::init
void init(const BndSet &s)
Initialize with BndSet s.
Definition integerset.hpp:247
Gecode::Set::BndSet::size
unsigned int size(void) const
Return size.
Definition integerset.hpp:93
Gecode::Set::BndSet::become
void become(Space &home, const BndSet &s)
Make this set equal to s.
Definition integerset.hpp:211
Gecode::Set::BndSet::card
unsigned int card(void) const
Return cardinality.
Definition integerset.hpp:130
Gecode::Set::GLBndSet::includeI
bool includeI(Space &home, I &i)
Include the set represented by i in this set.
Definition integerset.hpp:296
Gecode::Set::GlbRanges< SetVarImp * >::init
void init(const SetVarImp *)
Initialize with ranges for variable implementation x.
Definition set.hpp:499
Gecode::Set::GlbRanges< SetVarImp * >::GlbRanges
GlbRanges(void)
Default constructor.
Definition set.hpp:492
Gecode::Set::GlbRanges::init
void init(const T &x)
Initialize with greatest lower bound ranges for set variable x.
Gecode::Set::GlbRanges::GlbRanges
GlbRanges(void)
Default constructor.
Gecode::Set::LUBndSet::intersectI
bool intersectI(Space &home, I &i)
Exclude all elements not in the set represented by i from this set.
Definition integerset.hpp:370
Gecode::Set::LUBndSet::excludeI
bool excludeI(Space &home, I &i)
Exclude all elements in the set represented by i from this set.
Definition integerset.hpp:385
Gecode::Set::LubRanges< SetVarImp * >::init
void init(const SetVarImp *)
Initialize with ranges for variable implementation x.
Definition set.hpp:465
Gecode::Set::LubRanges< SetVarImp * >::LubRanges
LubRanges(void)
Default constructor.
Definition set.hpp:458
Gecode::Set::LubRanges::LubRanges
LubRanges(void)
Default constructor.
Gecode::Set::LubRanges::init
void init(const T &x)
Initialize with least upper bound ranges for set variable x.
Gecode::Set::SetDelta
Finite set delta information for advisors.
Definition var-imp.hpp:52
Gecode::Set::SetVarImpBase::SetVarImpBase
SetVarImpBase(Gecode::Space &home, SetVarImpBase &x)
Constructor for cloning x.
Definition var-imp.hpp:343
Gecode::Set::SetVarImpBase::notify
Gecode::ModEvent notify(Gecode::Space &home, Gecode::ModEvent me, Gecode::Delta &d)
Notify that variable implementation has been modified with modification event me and delta informatio...
Definition var-imp.hpp:365
Gecode::Set::SetVarImp
Finite integer set variable implementation.
Definition var-imp.hpp:430
Gecode::Set::SetVarImp::knownIn
bool knownIn(int n) const
Test whether n is contained in greatest lower bound.
Definition set.hpp:105
Gecode::Set::SetVarImp::glbMin
int glbMin(void) const
Return minimum of the greatest lower bound.
Definition set.hpp:120
Gecode::Set::SetVarImp::intersect
ModEvent intersect(Space &home, int n)
Exclude everything but n from the least upper bound.
Definition set.hpp:206
Gecode::Set::SetVarImp::lubMinN
int lubMinN(unsigned int n) const
Return n -th smallest element in the least upper bound.
Definition set.hpp:117
Gecode::Set::SetVarImp::lubAny
static bool lubAny(const Delta &d)
Test whether arbitrary values got pruned from lub.
Definition set.hpp:156
Gecode::Set::SetVarImp::cardMax
unsigned int cardMax(void) const
Return current cardinality maximum.
Definition set.hpp:102
Gecode::Set::SetVarImp::copy
SetVarImp * copy(Space &home)
Return copy of this variable.
Definition set.hpp:424
Gecode::Set::SetVarImp::lubSize
unsigned int lubSize(void) const
Return the size of the least upper bound.
Definition set.hpp:129
Gecode::Set::SetVarImp::lubMin
int lubMin(void) const
Return minimum of the least upper bound.
Definition set.hpp:111
Gecode::Set::SetVarImp::assigned
bool assigned(void) const
Test whether variable is assigned.
Definition set.hpp:94
Gecode::Set::SetVarImp::lubMax
int lubMax(void) const
Return maximum of the least upper bound.
Definition set.hpp:114
Gecode::Set::SetVarImp::glbMax
int glbMax(void) const
Return maximum of the greatest lower bound.
Definition set.hpp:123
Gecode::Set::SetVarImp::excludeI
ModEvent excludeI(Space &home, I &i)
Exclude set described by i from the least upper bound.
Definition set.hpp:367
Gecode::Set::SetVarImp::glbAny
static bool glbAny(const Delta &d)
Test whether arbitrary values got pruned from glb.
Definition set.hpp:144
Gecode::Set::SetVarImp::knownOut
bool knownOut(int) const
Test whether n is not contained in least upper bound.
Definition set.hpp:108
Gecode::Set::SetVarImp::includeI
ModEvent includeI(Space &home, I &i)
Include set described by i in the greatest lower bound.
Definition set.hpp:292
Gecode::Set::SetVarImp::glbSize
unsigned int glbSize(void) const
Return the size of the greatest lower bound.
Definition set.hpp:126
Gecode::Set::SetVarImp::intersectI
ModEvent intersectI(Space &home, I &i)
Exclude everything but set described by i from the least upper bound.
Definition set.hpp:212
Gecode::Set::SetVarImp::exclude
ModEvent exclude(Space &home, int n)
Exclude n from the least upper bound.
Definition set.hpp:361
Gecode::Set::SetVarImp::include
ModEvent include(Space &home, int n)
Include n in the greatest lower bound.
Definition set.hpp:287
Gecode::Set::SetVarImp::cardMin
unsigned int cardMin(void) const
Return current cardinality minimum.
Definition set.hpp:99
Gecode::Set::SetVarImp::SetVarImp
SetVarImp(Space &home, SetVarImp &x)
Constructor for cloning x.
Definition set.cpp:117
Gecode::Space
Computation spaces.
Definition core.hpp:1742
Gecode::VarImp< Gecode::Set::SetVarImpConf >::fail
ModEvent fail(Space &home)
Definition core.hpp:4570
Gecode::VarImp< Gecode::Set::SetVarImpConf >::copied
bool copied(void) const
Definition core.hpp:4222
Gecode::VarImp< Gecode::Set::SetVarImpConf >::forward
VarImp * forward(void) const
Definition core.hpp:4228
Gecode::VarImp< Gecode::Set::SetVarImpConf >::me
static ModEvent me(const ModEventDelta &med)
Definition core.hpp:4270
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::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::Set::ME_SET_CLUB
const Gecode::ModEvent ME_SET_CLUB
Domain operation has changed the least upper bound and the cardinality.
Definition var-type.hpp:179
Gecode::Set::ME_SET_NONE
const Gecode::ModEvent ME_SET_NONE
Domain operation has not changed domain.
Definition var-type.hpp:140
Gecode::Set::ME_SET_VAL
const Gecode::ModEvent ME_SET_VAL
Domain operation has resulted in a value (assigned variable).
Definition var-type.hpp:142
Gecode::Set::ME_SET_GLB
const Gecode::ModEvent ME_SET_GLB
Domain operation has changed the greatest lower bound.
Definition var-type.hpp:164
Gecode::Set::ME_SET_CGLB
const Gecode::ModEvent ME_SET_CGLB
Domain operation has changed the greatest lower bound and the cardinality.
Definition var-type.hpp:186
Gecode::Set::ME_SET_LUB
const Gecode::ModEvent ME_SET_LUB
Domain operation has changed the least upper bound.
Definition var-type.hpp:156
Gecode
Gecode toplevel namespace
Gecode::ModEvent
int ModEvent
Type for modification events.
Definition core.hpp:62
Test::Int::Distinct::d
Gecode::IntSet d(v, 7)
forceinline
#define forceinline
Definition config.hpp:187