var-imp.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>
*
* Contributing authors:
* Christian Schulte <schulte@gecode.org>
* Gabor Szokoli <szokoli@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.
*
*/
#include <iostream>
namespace Gecode { namespace Set {
class SetVarImp;
class LUBndSet;
class GLBndSet;
class SetDelta : public Delta {
friend class SetVarImp;
friend class LUBndSet;
friend class GLBndSet;
private:
int _glbMin;
int _glbMax;
int _lubMin;
int _lubMax;
public:
SetDelta(void);
SetDelta(int glbMin, int glbMax, int lubMin, int lubMax);
int glbMin(void) const;
int glbMax(void) const;
int lubMin(void) const;
int lubMax(void) const;
bool glbAny(void) const;
bool lubAny(void) const;
};
}}
#include <gecode/set/var-imp/delta.hpp>
namespace Gecode { namespace Set {
class BndSet {
private:
RangeList* first;
RangeList* last;
protected:
unsigned int _size;
unsigned int _card;
void fst(RangeList* r);
void lst(RangeList* r);
RangeList* fst(void) const;
RangeList* lst(void) const;
public:
static const int MAX_OF_EMPTY = Limits::min-1;
static const int MIN_OF_EMPTY = Limits::max+1;
BndSet(void);
BndSet(Space& home, int i, int j);
GECODE_SET_EXPORT BndSet(Space& home, const IntSet& s);
void dispose(Space& home);
int min(void) const;
int max(void) const;
int minN(unsigned int n) const;
unsigned int size(void) const;
unsigned int card(void) const;
void card(unsigned int c);
bool empty(void) const;
bool in(int i) const;
void become(Space& home, const BndSet& s);
RangeList* ranges(void) const;
protected:
template<class I> bool overwrite(Space& home,I& i);
public:
void update(Space& home, BndSet& x);
GECODE_SET_EXPORT bool isConsistent(void) const;
};
class BndSetRanges : public Iter::Ranges::RangeList {
public:
BndSetRanges(void);
BndSetRanges(const BndSet& s);
void init(const BndSet& s);
};
class GLBndSet : public BndSet {
private:
GECODE_SET_EXPORT bool include_full(Space& home,int,int,SetDelta&);
public:
GLBndSet(void);
GLBndSet(Space&);
GLBndSet(Space& home, int i, int j);
GLBndSet(Space& home, const IntSet& s);
void init(Space& home);
bool include(Space& home,int i,int j,SetDelta& d);
template<class I> bool includeI(Space& home,I& i);
private:
GLBndSet(const GLBndSet&);
const GLBndSet& operator =(const GLBndSet&);
};
class LUBndSet: public BndSet{
private:
GECODE_SET_EXPORT bool exclude_full(Space& home, int, int, SetDelta&);
GECODE_SET_EXPORT bool intersect_full(Space& home, int i, int j);
public:
LUBndSet(void);
LUBndSet(Space& home);
LUBndSet(Space& home, int i, int j);
LUBndSet(Space& home, const IntSet& s);
void init(Space& home);
bool exclude(Space& home, int i, int j, SetDelta& d);
bool intersect(Space& home, int i, int j);
template<class I> bool intersectI(Space& home, I& i);
template<class I> bool excludeI(Space& home, I& i);
void excludeAll(Space& home);
private:
LUBndSet(const LUBndSet&);
const LUBndSet& operator =(const LUBndSet&);
};
/*
* Iterators
*
*/
template<class I>
class RangesCompl :
public Iter::Ranges::Compl<Limits::min, Limits::max, I> {
public:
RangesCompl(void);
RangesCompl(I& i);
void init(I& i);
};
template<class T> class LubRanges {
public:
LubRanges(void);
LubRanges(const T& x);
void init(const T& x);
bool operator ()(void) const;
void operator ++(void);
int min(void) const;
int max(void) const;
unsigned int width(void) const;
};
template<class T> class GlbRanges {
public:
GlbRanges(void);
GlbRanges(const T& x);
void init(const T& x);
bool operator ()(void) const;
void operator ++(void);
int min(void) const;
int max(void) const;
unsigned int width(void) const;
};
template<class T>
class UnknownRanges : public Iter::Ranges::Diff<LubRanges<T>, GlbRanges<T> >{
private:
LubRanges<T> i1;
GlbRanges<T> i2;
public:
UnknownRanges(void);
UnknownRanges(const T& x);
void init(const T& x);
};
}}
#include <gecode/set/var-imp/integerset.hpp>
#include <gecode/set/var-imp/iter.hpp>
namespace Gecode { namespace Set {
class SetVarImp : public SetVarImpBase {
friend class LubRanges<SetVarImp*>;
friend class GlbRanges<SetVarImp*>;
private:
LUBndSet lub;
GLBndSet glb;
protected:
SetVarImp(Space& home, SetVarImp& x);
public:
SetVarImp(Space& home);
SetVarImp(Space& home,int glbMin,int glbMax,int lubMin,int lubMax,
unsigned int cardMin = 0,
unsigned int cardMax = Limits::card);
SetVarImp(Space& home,const IntSet& glbD,int lubMin,int lubMax,
unsigned int cardMin,unsigned int cardMax);
SetVarImp(Space& home,int glbMin,int glbMax,const IntSet& lubD,
unsigned int cardMin,unsigned int cardMax);
SetVarImp(Space& home,const IntSet& glbD,const IntSet& lubD,
unsigned int cardMin,unsigned int cardMax);
unsigned int cardMin(void) const;
unsigned int cardMax(void) const;
int lubMin(void) const;
int lubMax(void) const;
int lubMinN(unsigned int n) const;
int glbMin(void) const;
int glbMax(void) const;
unsigned int glbSize(void) const;
unsigned int lubSize(void) const;
bool assigned(void) const;
bool knownIn(int n) const;
bool knownOut(int) const;
private:
template<class I> ModEvent includeI_full(Space& home,int mi, int ma, I& i);
template<class I> ModEvent excludeI_full(Space& home,int mi, int ma, I& i);
template<class I> ModEvent intersectI_full(Space& home,int mi, int ma, I& i);
GECODE_SET_EXPORT ModEvent processLubChange(Space& home, SetDelta& d);
GECODE_SET_EXPORT ModEvent processGlbChange(Space& home, SetDelta& d);
GECODE_SET_EXPORT ModEvent cardMin_full(Space& home);
GECODE_SET_EXPORT ModEvent cardMax_full(Space& home);
public:
ModEvent include(Space& home,int n);
ModEvent include(Space& home,int i,int j);
ModEvent exclude(Space& home,int n);
ModEvent exclude(Space& home,int i,int j);
ModEvent intersect(Space& home,int n);
ModEvent intersect(Space& home,int i,int j);
ModEvent cardMin(Space& home,unsigned int n);
ModEvent cardMax(Space& home,unsigned int n);
template<class I> ModEvent includeI(Space& home,I& i);
template<class I> ModEvent excludeI(Space& home,I& i);
template<class I> ModEvent intersectI(Space& home,I& i);
public:
GECODE_SET_EXPORT void subscribe(Space& home, Propagator& p, PropCond pc, bool schedule=true);
GECODE_SET_EXPORT void reschedule(Space& home, Propagator& p, PropCond pc);
GECODE_SET_EXPORT void subscribe(Space& home, Advisor& a, bool fail);
private:
GECODE_SET_EXPORT SetVarImp* perform_copy(Space& home);
public:
SetVarImp* copy(Space& home);
static int glbMin(const Delta& d);
static int glbMax(const Delta& d);
static bool glbAny(const Delta& d);
static int lubMin(const Delta& d);
static int lubMax(const Delta& d);
static bool lubAny(const Delta& d);
};
class SetView;
}}
#include <gecode/set/var-imp/set.hpp>
// STATISTICS: set-var
Gecode::Advisor
Base-class for advisors.
Definition core.hpp:1292
Gecode::Delta
Generic domain change information to be supplied to advisors.
Definition core.hpp:204
Gecode::IntSet
Integer sets.
Definition int.hh:174
Gecode::Iter::Ranges::Compl
Range iterator for computing the complement (described by template arguments).
Definition ranges-compl.hpp:49
Gecode::Iter::Ranges::Compl< Limits::min, Limits::max, I >::i
I i
Definition ranges-compl.hpp:52
Gecode::Iter::Ranges::Diff
Range iterator for computing set difference.
Definition ranges-diff.hpp:43
Gecode::Iter::Ranges::RangeList
Range iterator for range lists
Definition ranges-rangelist.hpp:44
Gecode::Propagator
Base-class for propagators.
Definition core.hpp:1064
Gecode::RangeList
Lists of ranges (intervals).
Definition range-list.hpp:49
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
Sets of integers.
Definition var-imp.hpp:89
Gecode::Set::BndSet::min
int min(void) const
Return smallest element.
Definition integerset.hpp:103
Gecode::Set::BndSet::isConsistent
bool isConsistent(void) const
Check whether internal invariants hold.
Definition integerset.cpp:289
Gecode::Set::BndSet::minN
int minN(unsigned int n) const
Return n -th smallest element.
Definition integerset.hpp:120
Gecode::Set::BndSet::overwrite
bool overwrite(Space &home, I &i)
Overwrite the ranges with those represented by i.
Definition integerset.hpp:171
Gecode::Set::BndSet::MAX_OF_EMPTY
static const int MAX_OF_EMPTY
Returned by empty sets when asked for their maximum element.
Definition var-imp.hpp:110
Gecode::Set::BndSet::lst
RangeList * lst(void) const
Return last range.
Definition integerset.hpp:55
Gecode::Set::BndSet::size
unsigned int size(void) const
Return size.
Definition integerset.hpp:93
Gecode::Set::BndSet::BndSet
BndSet(void)
Default constructor. Creates an empty set.
Definition integerset.hpp:46
Gecode::Set::BndSet::update
void update(Space &home, BndSet &x)
Update this set to be a clone of set x.
Definition integerset.hpp:140
Gecode::Set::BndSet::_card
unsigned int _card
The cardinality this set represents.
Definition var-imp.hpp:97
Gecode::Set::BndSet::empty
bool empty(void) const
Test whether this set is empty.
Definition integerset.hpp:98
Gecode::Set::BndSet::in
bool in(int i) const
Test whether i is an element of this set.
Definition integerset.hpp:224
Gecode::Set::BndSet::become
void become(Space &home, const BndSet &s)
Make this set equal to s.
Definition integerset.hpp:211
Gecode::Set::BndSet::MIN_OF_EMPTY
static const int MIN_OF_EMPTY
Returned by empty sets when asked for their minimum element.
Definition var-imp.hpp:112
Gecode::Set::BndSet::max
int max(void) const
Return greatest element.
Definition integerset.hpp:111
Gecode::Set::BndSet::card
unsigned int card(void) const
Return cardinality.
Definition integerset.hpp:130
Gecode::Set::BndSet::ranges
RangeList * ranges(void) const
Return range list for iteration.
Definition integerset.hpp:88
Gecode::Set::BndSet::dispose
void dispose(Space &home)
Free memory used by this set.
Definition integerset.hpp:60
Gecode::Set::BndSet::_size
unsigned int _size
The size of this set.
Definition var-imp.hpp:95
Gecode::Set::BndSet::fst
RangeList * fst(void) const
Return first range.
Definition integerset.hpp:50
Gecode::Set::GLBndSet
Growing sets of integers.
Definition var-imp.hpp:205
Gecode::Set::GLBndSet::GLBndSet
GLBndSet(void)
Default constructor. Creates an empty set.
Definition integerset.hpp:257
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::GLBndSet::init
void init(Space &home)
Initialize as the empty set.
Definition integerset.hpp:271
Gecode::Set::GLBndSet::include
bool include(Space &home, int i, int j, SetDelta &d)
Include the set in this set.
Definition integerset.hpp:279
Gecode::Set::GlbRanges
Range iterator for the greatest lower bound.
Definition var-imp.hpp:359
Gecode::Set::GlbRanges::operator()
bool operator()(void) const
Test whether iterator is still at a range or done.
Gecode::Set::GlbRanges::init
void init(const T &x)
Initialize with greatest lower bound ranges for set variable x.
Gecode::Set::GlbRanges::min
int min(void) const
Return smallest value of range.
Gecode::Set::GlbRanges::max
int max(void) const
Return largest value of range.
Gecode::Set::GlbRanges::width
unsigned int width(void) const
Return width of range (distance between minimum and maximum).
Gecode::Set::GlbRanges::operator++
void operator++(void)
Move iterator to next range (if possible).
Gecode::Set::GlbRanges::GlbRanges
GlbRanges(const T &x)
Initialize with greatest lower bound ranges for set variable x.
Gecode::Set::GlbRanges::GlbRanges
GlbRanges(void)
Default constructor.
Gecode::Set::LUBndSet
Shrinking sets of integers.
Definition var-imp.hpp:243
Gecode::Set::LUBndSet::init
void init(Space &home)
Initialize as the full set including everything between Limits::min and Limits::max.
Definition integerset.hpp:328
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::LUBndSet::LUBndSet
LUBndSet(void)
Default constructor. Creates an empty set.
Definition integerset.hpp:313
Gecode::Set::LUBndSet::intersect
bool intersect(Space &home, int i, int j)
Intersect this set with the set .
Definition integerset.hpp:355
Gecode::Set::LUBndSet::excludeAll
void excludeAll(Space &home)
Exclude all elements from this set.
Definition integerset.hpp:395
Gecode::Set::LUBndSet::exclude
bool exclude(Space &home, int i, int j, SetDelta &d)
Exclude the set from this set.
Definition integerset.hpp:339
Gecode::Set::LubRanges
Range iterator for the least upper bound.
Definition var-imp.hpp:317
Gecode::Set::LubRanges::width
unsigned int width(void) const
Return width of range (distance between minimum and maximum).
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::LubRanges::max
int max(void) const
Return largest value of range.
Gecode::Set::LubRanges::operator()
bool operator()(void) const
Test whether iterator is still at a range or done.
Gecode::Set::LubRanges::operator++
void operator++(void)
Move iterator to next range (if possible).
Gecode::Set::LubRanges::LubRanges
LubRanges(const T &x)
Initialize with least upper bound ranges for set variable x.
Gecode::Set::LubRanges::min
int min(void) const
Return smallest value of range.
Gecode::Set::RangesCompl::init
void init(I &i)
Initialize with iterator i.
Definition integerset.hpp:414
Gecode::Set::RangesCompl::RangesCompl
RangesCompl(void)
Default constructor.
Definition integerset.hpp:405
Gecode::Set::SetDelta
Finite set delta information for advisors.
Definition var-imp.hpp:52
Gecode::Set::SetDelta::glbAny
bool glbAny(void) const
Test whether delta represents any domain change in glb.
Definition delta.hpp:64
Gecode::Set::SetDelta::GLBndSet
friend class GLBndSet
Definition var-imp.hpp:55
Gecode::Set::SetDelta::LUBndSet
friend class LUBndSet
Definition var-imp.hpp:54
Gecode::Set::SetDelta::lubAny
bool lubAny(void) const
Test whether delta represents any domain change in lub.
Definition delta.hpp:68
Gecode::Set::SetDelta::SetVarImp
friend class SetVarImp
Definition var-imp.hpp:53
Gecode::Set::SetDelta::lubMax
int lubMax(void) const
Return lub maximum.
Definition delta.hpp:60
Gecode::Set::SetDelta::glbMin
int glbMin(void) const
Return glb minimum.
Definition delta.hpp:48
Gecode::Set::SetDelta::SetDelta
SetDelta(void)
Create set delta as providing no information (if any is true).
Definition delta.hpp:39
Gecode::Set::SetDelta::lubMin
int lubMin(void) const
Return lub minimum.
Definition delta.hpp:56
Gecode::Set::SetDelta::glbMax
int glbMax(void) const
Return glb maximum.
Definition delta.hpp:52
Gecode::Set::SetVarImpBase::SetVarImpBase
SetVarImpBase(Gecode::Space &home, SetVarImpBase &x)
Constructor for cloning x.
Definition var-imp.hpp:343
Gecode::Set::SetVarImpBase::schedule
static void schedule(Gecode::Space &home, Gecode::Propagator &p, Gecode::ModEvent me)
Schedule propagator p.
Definition var-imp.hpp:356
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::reschedule
void reschedule(Space &home, Propagator &p, PropCond pc)
Re-schedule propagator p with propagation condition pc.
Definition set.cpp:149
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::subscribe
void subscribe(Space &home, Propagator &p, PropCond pc, bool schedule=true)
Subscribe propagator p with propagation condition pc to variable.
Definition set.cpp:140
Gecode::Set::SetVarImp::SetVarImp
SetVarImp(Space &home, SetVarImp &x)
Constructor for cloning x.
Definition set.cpp:117
Gecode::Set::SetView
Set view for set variables
Definition view.hpp:56
Gecode::Set::UnknownRanges::init
void init(const T &x)
Initialize with unknown set ranges for set variable x.
Definition iter.hpp:50
Gecode::Set::UnknownRanges::UnknownRanges
UnknownRanges(void)
Default constructor.
Definition iter.hpp:40
Gecode::Space
Computation spaces.
Definition core.hpp:1742
Gecode::VarImp< Gecode::Set::SetVarImpConf >::fail
ModEvent fail(Space &home)
Definition core.hpp:4570
set.hpp
GECODE_SET_EXPORT
#define GECODE_SET_EXPORT
Definition set.hh:67
integerset.hpp
Gecode::Set::Limits::min
const int min
Smallest allowed integer in integer set.
Definition set.hh:99
Gecode::Set::Limits::card
const unsigned int card
Maximum cardinality of an integer set.
Definition set.hh:101
Gecode::Set::Limits::max
const int max
Largest allowed integer in integer set.
Definition set.hh:97
Gecode::Set
Finite integer sets.
Definition var-imp.hpp:137
Gecode
Gecode toplevel namespace
Gecode::PropCond
int PropCond
Type for propagation conditions.
Definition core.hpp:72
Gecode::ModEvent
int ModEvent
Type for modification events.
Definition core.hpp:62
delta.hpp
iter.hpp