integerset.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, 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>
namespace Gecode { namespace Set {
BndSet::BndSet(Space& home, const IntSet& is) {
if (is.ranges()==0) {
fst(NULL); lst(NULL); _size = 0;
} else {
int n = is.ranges();
RangeList* r = home.alloc<RangeList>(n);
fst(r); lst(r+n-1);
unsigned int s = 0;
for (int i = n; i--; ) {
s += is.width(i);
r[i].min(is.min(i)); r[i].max(is.max(i));
r[i].next(&r[i+1]);
}
r[n-1].next(NULL);
_size = s;
}
assert(isConsistent());
}
bool
GLBndSet::include_full(Space& home, int mi, int ma, SetDelta& d) {
assert(ma >= mi);
assert(fst() != NULL);
RangeList* p = NULL;
RangeList* c = fst();
while (c != NULL) {
if (c->max() >= mi-1) {
if (c->min() > ma+1) { //in a hole before c
_size+=(ma-mi+1);
d._glbMin = mi;
d._glbMax = ma;
RangeList* q = new (home) RangeList(mi,ma,c);
if (p==NULL)
//the new range is the first
fst(q);
else
p->next(q);
return true;
}
//if the range starts before c, update c->min and size
bool result = false;
if (c->min()>mi) {
_size+=(c->min()-mi);
c->min(mi);
d._glbMin = mi;
result = true;
} else {
d._glbMin = c->max()+1;
}
assert(c->min()<=mi);
assert(c->max()+1>=mi);
if (c->max() >= ma) {
d._glbMax = c->min()-1;
return result;
}
RangeList* q = c;
//sum up the size of holes eaten
int prevMax = c->max();
int growth = 0;
// invariant: q->min()<=ma+1
while (q->next() != NULL && q->next()->min() <= ma+1) {
q = q->next();
growth += q->min()-prevMax-1;
prevMax = q->max();
}
assert(growth>=0);
_size+=growth;
if (q->max() < ma) {
_size += ma-q->max();
d._glbMax = ma;
} else {
d._glbMax = q->min()-1;
}
c->max(std::max(ma,q->max()));
if (c!=q) {
RangeList* oldCNext = c->next();
assert(oldCNext!=NULL); //q would have stayed c if c was last.
c->next(q->next());
if (q->next()==NULL) {
assert(q==lst());
lst(c);
}
oldCNext->dispose(home,q);
}
return true;
}
RangeList* nc = c->next();
p=c; c=nc;
}
//the new range is disjoint from the old domain and we add it as last:
assert(mi>max()+1);
RangeList* q = new (home) RangeList(mi, ma, NULL);
lst()->next(q);
lst(q);
_size+= q->width();
d._glbMin = mi;
d._glbMax = ma;
return true;
}
bool
LUBndSet::intersect_full(Space& home, int mi, int ma) {
RangeList* p = NULL;
RangeList* c = fst();
assert(c != NULL); // Never intersect with an empty set
// Skip ranges that are before mi
while (c != NULL && c->max() < mi) {
_size -= c->width();
RangeList *nc = c->next();
p=c; c=nc;
}
if (c == NULL) {
// Delete entire domain
fst()->dispose(home, lst());
fst(NULL); lst(NULL);
return true;
}
bool changed = false;
if (c != fst()) {
fst()->dispose(home, p);
fst(c);
p = NULL;
changed = true;
}
// We have found the first range that intersects with [mi,ma]
if (mi > c->min()) {
_size -= mi-c->min();
c->min(mi);
changed = true;
}
while (c != NULL && c->max() <= ma) {
RangeList *nc = c->next();
p=c; c=nc;
}
if (c == NULL)
return changed;
RangeList* newlst = p;
if (ma >= c->min()) {
_size -= c->max() - ma;
c->max(ma);
newlst = c;
RangeList* nc = c->next();
c->next(NULL);
p=c; c=nc;
} else if (p != NULL) {
p->next(NULL);
}
if (c != NULL) {
for (RangeList* cc = c ; cc != NULL; cc = cc->next())
_size -= cc->width();
c->dispose(home, lst());
}
lst(newlst);
if (newlst==NULL)
fst(NULL);
return true;
}
bool
LUBndSet::exclude_full(Space& home, int mi, int ma, SetDelta& d) {
assert(ma >= mi);
assert(mi <= max() && ma >= min() &&
(mi > min() || ma < max()));
bool result=false;
RangeList* p = NULL;
RangeList* c = fst();
d._lubMin = Limits::max+1;
while (c != NULL) {
if (c->max() >= mi) {
if (c->min() > ma) { return result; } //in a hole
if (c->min()<mi && c->max() > ma) { //Range split:
RangeList* q =
new (home) RangeList(ma+1,c->max(),c->next());
c->max(mi-1);
if (c == lst()) {
lst(q);
}
c->next(q);
_size -= (ma-mi+1);
d._lubMin = mi;
d._lubMax = ma;
return true;
}
if (c->max() > ma) { //start of range clipped, end remains
d._lubMin = std::min(d._lubMin, c->min());
d._lubMax = ma;
_size-=(ma-c->min()+1);
c->min(ma+1);
return true;
}
if (c->min() < mi) { //end of range clipped, start remains
_size-=(c->max()-mi+1);
d._lubMin = mi;
d._lubMax = c->max();
c->max(mi-1);
result=true;
} else { //range *c destroyed
d._lubMin = c->min();
_size-=c->width();
RangeList *cend = c;
while ((cend->next()!=NULL) && (cend->next()->max()<=ma)) {
cend = cend->next();
_size-=cend->width();
}
d._lubMax = cend->max();
if (fst()==c) {
fst(cend->next());
} else {
p->next(cend->next());
}
if (lst()==cend) {
lst(p);
}
RangeList* nc=cend->next(); //performs loop step!
c->dispose(home,cend);
p=cend;
c=nc;
if (c != NULL && c->min() <= ma ) {
//start of range clipped, end remains
_size-=(ma-c->min()+1);
c->min(ma+1);
d._lubMax = ma;
}
return true;
}
}
RangeList *nc = c->next();
p=c; c=nc;
}
return result;
}
#ifndef NDEBUG
using namespace Gecode::Int;
#endif
bool
BndSet::isConsistent(void) const {
#ifndef NDEBUG
if (fst()==NULL) {
if (lst()!=NULL || size()!=0) {
std::cerr<<"Strange empty set.\n";
return false;
} else return true;
}
if (fst()!=NULL && lst()==NULL) {
std::cerr<<"First is not null, last is.\n";
return false;
}
RangeList *p=NULL;
RangeList *c=fst();
int min = c->min();
int max = c->max();
if (max<min) {
std::cerr << "Single range list twisted: ("<<min<<","<<max<<")" ;
return false;
}
RangeList *nc=c->next();
p=c; c=nc;
while (c) {
if (max<min) {
std::cerr << "1";
return false;
}
if ((max+1)>=c->min()) {
std::cerr << "2";
return false;
}
if (c->next()==NULL && c!=lst()) {
std::cerr << "3";
return false;
}
min = c->min();
max = c->max();
nc=c->next();
p=c; c=nc;
}
#endif
return true;
}
}}
// 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::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::IntSet::ranges
int ranges(void) const
Return number of ranges of the specification.
Definition int-set-1.hpp:171
Gecode::IntSet::width
unsigned int width(int i) const
Return width of range at position i.
Definition int-set-1.hpp:164
Gecode::RangeList
Lists of ranges (intervals).
Definition range-list.hpp:49
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::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::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::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::max
int max(void) const
Return greatest element.
Definition integerset.hpp:111
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::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
set.hh
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
Test::Float::Arithmetic::c
Gecode::FloatVal c(-8, 8)
Test::Int::Distinct::d
Gecode::IntSet d(v, 7)