integerset.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>
* 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 {
/*
* BndSet
*
*/
forceinline
BndSet::BndSet(void) :
first(NULL), last(NULL), _size(0), _card(0) {}
forceinline RangeList*
BndSet::fst(void) const {
return first;
}
forceinline RangeList*
BndSet::lst(void) const {
return last;
}
forceinline void
BndSet::dispose(Space& home) {
if (fst()!=NULL)
fst()->dispose(home,lst());
}
forceinline void
BndSet::fst(RangeList* f) {
first = f;
}
forceinline void
BndSet::lst(RangeList* l) {
last = l;
}
forceinline
BndSet::BndSet(Space& home, int mn, int mx) {
if (mn>mx) {
fst(NULL); lst(NULL); _size = 0;
} else {
RangeList* p =
new (home) RangeList(mn,mx,NULL);
fst(p); lst(p);
_size = static_cast<unsigned int>(mx-mn+1);
}
}
forceinline RangeList*
BndSet::ranges(void) const {
return fst();
}
forceinline unsigned int
BndSet::size(void) const {
return _size;
}
forceinline bool
BndSet::empty(void) const {
return (_size==0);
}
forceinline int
BndSet::min(void) const {
if (fst()==NULL)
return MIN_OF_EMPTY;
else
return fst()->min();
}
forceinline int
BndSet::max(void) const {
if (lst()==NULL)
return MAX_OF_EMPTY;
else
return lst()->max();
}
// nth smallest element
forceinline int
BndSet::minN(unsigned int n) const {
for (RangeList* c = fst(); c != NULL; c = c->next()) {
if (c->width() > n)
return static_cast<int>(c->min() + n);
n -= c->width();
}
return MIN_OF_EMPTY;
}
forceinline unsigned int
BndSet::card(void) const {
return _card;
}
forceinline void
BndSet::card(unsigned int c) {
_card = c;
}
forceinline void
BndSet::update(Space& home, BndSet& d) {
if (d.fst() == fst())
return;
if (fst() != NULL)
fst()->dispose(home,lst());
_size = d.size();
if (_size == 0) {
fst(NULL); lst(NULL);
return;
}
int n=0;
for (RangeList* c = d.fst(); c != NULL; c = c->next())
n++;
RangeList* r = home.alloc<RangeList>(n);
fst(r); lst(r+n-1);
{
RangeList* c = d.fst();
for (int i=0; i<n; i++) {
r[i].min(c->min());
r[i].max(c->max());
r[i].next(&r[i+1]);
c = c->next();
}
}
r[n-1].next(NULL);
}
template<class I> forceinline bool
BndSet::overwrite(Space& home, I& ri) {
// Is new domain empty?
if (!ri()) {
//Was it empty?
if (fst()==NULL)
return false;
fst()->dispose(home,lst());
_size=0; fst(NULL); lst(NULL);
return true;
}
RangeList* f =
new (home) RangeList(ri.min(),ri.max(),NULL);
RangeList* l = f;
unsigned int s = ri.width();
++ri;
while (ri()) {
RangeList *n = new (home) RangeList(ri.min(),ri.max(),NULL);
l->next(n);
l=n;
s += ri.width();
++ri;
}
if (fst() != NULL)
fst()->dispose(home,lst());
fst(f); lst(l);
// If the size did not change, nothing changed, as overwriting
// must not at the same time include and exclude elements.
if (size() == s)
return false;
_size = s;
return true;
}
forceinline void
BndSet::become(Space& home, const BndSet& that) {
if (fst()!=NULL) {
assert(lst()!=NULL);
assert(fst()!= that.fst());
fst()->dispose(home,lst());
}
fst(that.fst());
lst(that.lst());
_size = that.size();
assert(isConsistent());
}
forceinline bool
BndSet::in(int i) const {
for (RangeList* c = fst(); c != NULL; c = c->next()) {
if (c->min() <= i && c->max() >= i)
return true;
if (c->min() > i)
return false;
}
return false;
}
/*
* Range iterator for BndSets
*
*/
forceinline
BndSetRanges::BndSetRanges(void) {}
forceinline
BndSetRanges::BndSetRanges(const BndSet& s)
: Iter::Ranges::RangeList(s.ranges()) {}
forceinline void
BndSetRanges::init(const BndSet& s) {
Iter::Ranges::RangeList::init(s.ranges());
}
/*
* GLBndSet
*
*/
forceinline
GLBndSet::GLBndSet(void) {}
forceinline
GLBndSet::GLBndSet(Space&) {}
forceinline
GLBndSet::GLBndSet(Space& home, int mi, int ma)
: BndSet(home,mi,ma) {}
forceinline
GLBndSet::GLBndSet(Space& home, const IntSet& s)
: BndSet(home,s) {}
forceinline void
GLBndSet::init(Space& home) {
dispose(home);
fst(NULL);
lst(NULL);
_size = 0;
}
forceinline bool
GLBndSet::include(Space& home, int mi, int ma, SetDelta& d) {
assert(ma >= mi);
if (fst()==NULL) {
RangeList* p = new (home) RangeList(mi,ma,NULL);
fst(p);
lst(p);
_size=static_cast<unsigned int>(ma-mi+1);
d._glbMin = mi;
d._glbMax = ma;
return true;
}
bool ret = include_full(home, mi, ma, d);
assert(isConsistent());
return ret;
}
template<class I> bool
GLBndSet::includeI(Space& home, I& i) {
if (!i())
return false;
BndSetRanges j(*this);
Iter::Ranges::Union<BndSetRanges,I> ij(j,i);
bool me = overwrite(home, ij);
assert(isConsistent());
return me;
}
/*
* LUBndSet
*
*/
forceinline
LUBndSet::LUBndSet(void) {}
forceinline
LUBndSet::LUBndSet(Space& home)
: BndSet(home,Limits::min,Limits::max) {}
forceinline
LUBndSet::LUBndSet(Space& home, int mi, int ma)
: BndSet(home,mi,ma) {}
forceinline
LUBndSet::LUBndSet(Space& home, const IntSet& s)
: BndSet(home,s) {}
forceinline void
LUBndSet::init(Space& home) {
RangeList *p =
new (home) RangeList(Limits::min,
Limits::max,
NULL);
fst(p);
lst(p);
_size = Limits::card;
}
forceinline bool
LUBndSet::exclude(Space& home, int mi, int ma, SetDelta& d) {
assert(ma >= mi);
if ((mi > max()) || (ma < min())) { return false; }
if (mi <= min() && ma >= max() ) { //the range covers the whole set
d._lubMin = min();
d._lubMax = max();
fst()->dispose(home,lst()); fst(NULL); lst(NULL);
_size=0;
return true;
}
bool ret = exclude_full(home, mi, ma, d);
assert(isConsistent());
return ret;
}
forceinline bool
LUBndSet::intersect(Space& home, int mi, int ma) {
assert(ma >= mi);
if ((mi <= min()) && (ma >= max())) { return false; }
if (_size == 0) return false;
if (ma < min() || mi > max() ) { // empty the whole set
fst()->dispose(home,lst()); fst(NULL); lst(NULL);
_size=0;
return true;
}
bool ret = intersect_full(home, mi, ma);
assert(isConsistent());
return ret;
}
template<class I> bool
LUBndSet::intersectI(Space& home, I& i) {
if (fst()==NULL) { return false; }
if (!i()) {
fst()->dispose(home,lst()); fst(NULL); lst(NULL);
_size=0;
return true;
}
BndSetRanges j(*this);
Iter::Ranges::Inter<BndSetRanges,I> ij(j,i);
bool ret = overwrite(home, ij);
assert(isConsistent());
return ret;
}
template<class I> bool
LUBndSet::excludeI(Space& home, I& i) {
if (!i()) { return false; }
BndSetRanges j(*this);
Iter::Ranges::Diff<BndSetRanges,I> ij(j,i);
bool ret = overwrite(home, ij);
assert(isConsistent());
return ret;
}
forceinline void
LUBndSet::excludeAll(Space& home) {
fst()->dispose(home,lst()); fst(NULL); lst(NULL);
_size=0;
}
/*
* A complement iterator spezialized for the BndSet limits
*
*/
template<class I>
RangesCompl<I>::RangesCompl(void) {}
template<class I>
RangesCompl<I>::RangesCompl(I& i)
: Iter::Ranges::Compl<Limits::min,
Limits::max,
I>(i) {}
template<class I> void
RangesCompl<I>::init(I& i) {
Iter::Ranges::Compl<Limits::min,
Limits::max,I>::init(i);
}
}}
// STATISTICS: set-var
Gecode::FloatVal::max
friend FloatVal max(const FloatVal &x, const FloatVal &y)
Definition val.hpp:386
Gecode::FloatVal::min
friend FloatVal min(const FloatVal &x, const FloatVal &y)
Definition val.hpp:398
Gecode::IntSet
Integer sets.
Definition int.hh:174
Gecode::IntSet::size
unsigned int size(void) const
Return size (cardinality) of set.
Definition int-set-1.hpp:198
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, Gecode::Set::LubRanges< Gecode::ValSelCommitBase< typenameValSel::View, typenameValSel::Val >::View > >::i
Gecode::Set::LubRanges< Gecode::ValSelCommitBase< typenameValSel::View, typenameValSel::Val >::View > i
Definition ranges-compl.hpp:52
Gecode::Iter::Ranges::Compl< Limits::min, Limits::max, I >::Compl
Compl(void)
Definition ranges-compl.hpp:135
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::MinMax::max
int max(void) const
Return largest value of range.
Definition ranges-minmax.hpp:103
Gecode::Iter::Ranges::RangeList::init
void init(const Gecode::RangeList *s)
Initialize with range list s.
Definition ranges-rangelist.hpp:86
Gecode::Iter::Ranges::RangeList::RangeList
RangeList(void)
Default constructor.
Definition ranges-rangelist.hpp:80
Gecode::Iter::Ranges::Union
Range iterator for computing union (binary).
Definition ranges-union.hpp:44
Gecode::RangeList
Lists of ranges (intervals).
Definition range-list.hpp:49
Gecode::RangeList::max
int max(void) const
Return maximum.
Definition range-list.hpp:168
Gecode::RangeList::min
int min(void) const
Return minimum.
Definition range-list.hpp:164
Gecode::RangeList::dispose
void dispose(Space &home, RangeList *l)
Free memory for all elements between this and l (inclusive).
Definition range-list.hpp:201
Gecode::RangeList::next
RangeList * next(void) const
Return next element.
Definition range-list.hpp:141
Gecode::RangeList::width
unsigned int width(void) const
Return width (distance between maximum and minimum).
Definition range-list.hpp:172
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
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::fst
void fst(RangeList *r)
Set first range to r.
Definition integerset.hpp:66
Gecode::Set::BndSet::size
unsigned int size(void) const
Return size.
Definition integerset.hpp:93
Gecode::Set::BndSet::lst
void lst(RangeList *r)
Set last range to r.
Definition integerset.hpp:71
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::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::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::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::Space
Computation spaces.
Definition core.hpp:1742
Gecode::Space::alloc
T * alloc(long unsigned int n)
Allocate block of n objects of type T from space heap.
Definition core.hpp:2837
Gecode::Int::Limits
Numerical limits for integer variables.
Definition int.hh:114
Gecode::Iter
Range and value iterators.
Definition iter.hh:41
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
forceinline
#define forceinline
Definition config.hpp:187