int.hpp
Go to the documentation of this file.
/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
/*
* Main authors:
* Christian Schulte <schulte@gecode.org>
*
* Contributing authors:
* Guido Tack <tack@gecode.org>
*
* Copyright:
* Christian Schulte, 2003
* 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.
*
*/
namespace Gecode { namespace Int {
/*
* Range lists
*
*/
#define GECODE_INT_RL2PD(r) reinterpret_cast<ptrdiff_t>(r)
#define GECODE_INT_PD2RL(p) reinterpret_cast<RangeList*>(p)
forceinline
IntVarImp::RangeList::RangeList(void) {}
forceinline
IntVarImp::RangeList::RangeList(int min, int max)
: _min(min), _max(max) {}
forceinline
IntVarImp::RangeList::RangeList(int min, int max, RangeList* p, RangeList* n)
: _min(min), _max(max) {
_next = GECODE_INT_PD2RL(GECODE_INT_RL2PD(p)^GECODE_INT_RL2PD(n));
}
forceinline IntVarImp::RangeList*
IntVarImp::RangeList::next(const RangeList* p) const {
return GECODE_INT_PD2RL(GECODE_INT_RL2PD(_next)^GECODE_INT_RL2PD(p));
}
forceinline IntVarImp::RangeList*
IntVarImp::RangeList::prev(const RangeList* n) const {
return GECODE_INT_PD2RL(GECODE_INT_RL2PD(_next)^GECODE_INT_RL2PD(n));
}
forceinline void
IntVarImp::RangeList::prevnext(RangeList* p, RangeList* n) {
_next = GECODE_INT_PD2RL(GECODE_INT_RL2PD(p)^GECODE_INT_RL2PD(n));
}
forceinline void
IntVarImp::RangeList::next(RangeList* o, RangeList* n) {
_next = GECODE_INT_PD2RL(GECODE_INT_RL2PD(_next)^
(GECODE_INT_RL2PD(o)^GECODE_INT_RL2PD(n)));
}
forceinline void
IntVarImp::RangeList::prev(RangeList* o, RangeList* n) {
_next = GECODE_INT_PD2RL(GECODE_INT_RL2PD(_next)^
(GECODE_INT_RL2PD(o)^GECODE_INT_RL2PD(n)));
}
forceinline void
IntVarImp::RangeList::fix(RangeList* n) {
_next = n;
}
forceinline void
IntVarImp::RangeList::min(int n) {
_min = n;
}
forceinline void
IntVarImp::RangeList::max(int n) {
_max = n;
}
forceinline int
IntVarImp::RangeList::min(void) const {
return _min;
}
forceinline int
IntVarImp::RangeList::max(void) const {
return _max;
}
forceinline unsigned int
IntVarImp::RangeList::width(void) const {
return static_cast<unsigned int>(_max - _min) + 1;
}
forceinline void
IntVarImp::RangeList::operator delete(void*) {}
forceinline void
IntVarImp::RangeList::operator delete(void*, Space&) {
GECODE_NEVER;
}
forceinline void
IntVarImp::RangeList::operator delete(void*, void*) {
GECODE_NEVER;
}
forceinline void*
IntVarImp::RangeList::operator new(size_t, Space& home) {
return home.fl_alloc<sizeof(RangeList)>();
}
forceinline void*
IntVarImp::RangeList::operator new(size_t, void* p) {
return p;
}
forceinline void
IntVarImp::RangeList::dispose(Space& home, RangeList* p, RangeList* l) {
RangeList* c = this;
while (c != l) {
RangeList* n = c->next(p);
c->fix(n);
p=c; c=n;
}
home.fl_dispose<sizeof(RangeList)>(this,l);
}
forceinline void
IntVarImp::RangeList::dispose(Space& home, RangeList* l) {
home.fl_dispose<sizeof(RangeList)>(this,l);
}
forceinline void
IntVarImp::RangeList::dispose(Space& home) {
home.fl_dispose<sizeof(RangeList)>(this,this);
}
#undef GECODE_INT_RL2PD
#undef GECODE_INT_PD2RL
/*
* Mainitaining range lists for variable domain
*
*/
forceinline IntVarImp::RangeList*
IntVarImp::fst(void) const {
return dom.next(NULL);
}
forceinline void
IntVarImp::fst(IntVarImp::RangeList* f) {
dom.prevnext(NULL,f);
}
forceinline IntVarImp::RangeList*
IntVarImp::lst(void) const {
return _lst;
}
forceinline void
IntVarImp::lst(IntVarImp::RangeList* l) {
_lst = l;
}
/*
* Creation of new variable implementations
*
*/
forceinline
IntVarImp::IntVarImp(Space& home, int min, int max)
: IntVarImpBase(home), dom(min,max,NULL,NULL), holes(0) {}
forceinline
IntVarImp::IntVarImp(Space& home, const IntSet& d)
: IntVarImpBase(home), dom(d.min(),d.max()) {
if (d.ranges() > 1) {
int n = d.ranges();
assert(n >= 2);
RangeList* r = home.alloc<RangeList>(n);
fst(r); lst(r+n-1);
unsigned int h = static_cast<unsigned int>(d.max()-d.min())+1;
h -= d.width(0);
r[0].min(d.min(0)); r[0].max(d.max(0));
r[0].prevnext(NULL,&r[1]);
for (int i = 1; i < n-1; i++) {
h -= d.width(i);
r[i].min(d.min(i)); r[i].max(d.max(i));
r[i].prevnext(&r[i-1],&r[i+1]);
}
h -= d.width(n-1);
r[n-1].min(d.min(n-1)); r[n-1].max(d.max(n-1));
r[n-1].prevnext(&r[n-2],NULL);
holes = h;
} else {
fst(NULL); holes = 0;
}
}
/*
* Operations on integer variable implementations
*
*/
forceinline int
IntVarImp::min(void) const {
return dom.min();
}
forceinline int
IntVarImp::max(void) const {
return dom.max();
}
forceinline int
IntVarImp::val(void) const {
assert(dom.min() == dom.max());
return dom.min();
}
forceinline bool
IntVarImp::range(void) const {
return fst() == NULL;
}
forceinline bool
IntVarImp::assigned(void) const {
return dom.min() == dom.max();
}
forceinline unsigned int
IntVarImp::width(void) const {
return dom.width();
}
forceinline unsigned int
IntVarImp::size(void) const {
return dom.width() - holes;
}
forceinline unsigned int
IntVarImp::regret_min(void) const {
if (fst() == NULL) {
return (dom.min() == dom.max()) ? 0U : 1U;
} else if (dom.min() == fst()->max()) {
return static_cast<unsigned int>(fst()->next(NULL)->min()-dom.min());
} else {
return 1U;
}
}
forceinline unsigned int
IntVarImp::regret_max(void) const {
if (fst() == NULL) {
return (dom.min() == dom.max()) ? 0U : 1U;
} else if (dom.max() == lst()->min()) {
return static_cast<unsigned int>(dom.max()-lst()->prev(NULL)->max());
} else {
return 1U;
}
}
/*
* Tests
*
*/
forceinline bool
IntVarImp::in(int n) const {
if ((n < dom.min()) || (n > dom.max()))
return false;
return (fst() == NULL) || in_full(n);
}
forceinline bool
IntVarImp::in(long long int n) const {
if ((n < dom.min()) || (n > dom.max()))
return false;
return (fst() == NULL) || in_full(static_cast<int>(n));
}
/*
* Accessing rangelists for iteration
*
*/
forceinline const IntVarImp::RangeList*
IntVarImp::ranges_fwd(void) const {
return (fst() == NULL) ? &dom : fst();
}
forceinline const IntVarImp::RangeList*
IntVarImp::ranges_bwd(void) const {
return (fst() == NULL) ? &dom : lst();
}
/*
* Support for delta information
*
*/
forceinline int
IntVarImp::min(const Delta& d) {
return static_cast<const IntDelta&>(d).min();
}
forceinline int
IntVarImp::max(const Delta& d) {
return static_cast<const IntDelta&>(d).max();
}
forceinline unsigned int
IntVarImp::width(const Delta& d) {
return static_cast<const IntDelta&>(d).width();
}
forceinline bool
IntVarImp::any(const Delta& d) {
return static_cast<const IntDelta&>(d).any();
}
/*
* Tell operations (to be inlined: performing bounds checks first)
*
*/
forceinline ModEvent
IntVarImp::gq(Space& home, int n) {
if (n <= dom.min()) return ME_INT_NONE;
if (n > dom.max()) return fail(home);
ModEvent me = gq_full(home,n);
GECODE_ASSUME((me == ME_INT_FAILED) |
(me == ME_INT_VAL) |
(me == ME_INT_BND));
return me;
}
forceinline ModEvent
IntVarImp::gq(Space& home, long long int n) {
if (n <= dom.min()) return ME_INT_NONE;
if (n > dom.max()) return fail(home);
ModEvent me = gq_full(home,static_cast<int>(n));
GECODE_ASSUME((me == ME_INT_FAILED) |
(me == ME_INT_VAL) |
(me == ME_INT_BND));
return me;
}
forceinline ModEvent
IntVarImp::lq(Space& home, int n) {
if (n >= dom.max()) return ME_INT_NONE;
if (n < dom.min()) return fail(home);
ModEvent me = lq_full(home,n);
GECODE_ASSUME((me == ME_INT_FAILED) |
(me == ME_INT_VAL) |
(me == ME_INT_BND));
return me;
}
forceinline ModEvent
IntVarImp::lq(Space& home, long long int n) {
if (n >= dom.max()) return ME_INT_NONE;
if (n < dom.min()) return fail(home);
ModEvent me = lq_full(home,static_cast<int>(n));
GECODE_ASSUME((me == ME_INT_FAILED) |
(me == ME_INT_VAL) |
(me == ME_INT_BND));
return me;
}
forceinline ModEvent
IntVarImp::eq(Space& home, int n) {
if ((n < dom.min()) || (n > dom.max()))
return fail(home);
if ((n == dom.min()) && (n == dom.max()))
return ME_INT_NONE;
ModEvent me = eq_full(home,n);
GECODE_ASSUME((me == ME_INT_FAILED) | (me == ME_INT_VAL));
return me;
}
forceinline ModEvent
IntVarImp::eq(Space& home, long long int m) {
if ((m < dom.min()) || (m > dom.max()))
return fail(home);
int n = static_cast<int>(m);
if ((n == dom.min()) && (n == dom.max()))
return ME_INT_NONE;
ModEvent me = eq_full(home,n);
GECODE_ASSUME((me == ME_INT_FAILED) | (me == ME_INT_VAL));
return me;
}
forceinline ModEvent
IntVarImp::nq(Space& home, int n) {
if ((n < dom.min()) || (n > dom.max()))
return ME_INT_NONE;
return nq_full(home,n);
}
forceinline ModEvent
IntVarImp::nq(Space& home, long long int d) {
if ((d < dom.min()) || (d > dom.max()))
return ME_INT_NONE;
return nq_full(home,static_cast<int>(d));
}
/*
* Forward range iterator for rangelists
*
*/
forceinline
IntVarImpFwd::IntVarImpFwd(void) {}
forceinline
IntVarImpFwd::IntVarImpFwd(const IntVarImp* x)
: p(NULL), c(x->ranges_fwd()) {}
forceinline void
IntVarImpFwd::init(const IntVarImp* x) {
p=NULL; c=x->ranges_fwd();
}
forceinline bool
IntVarImpFwd::operator ()(void) const {
return c != NULL;
}
forceinline void
IntVarImpFwd::operator ++(void) {
const IntVarImp::RangeList* n=c->next(p); p=c; c=n;
}
forceinline int
IntVarImpFwd::min(void) const {
return c->min();
}
forceinline int
IntVarImpFwd::max(void) const {
return c->max();
}
forceinline unsigned int
IntVarImpFwd::width(void) const {
return c->width();
}
/*
* Backward range iterator for rangelists
*
*/
forceinline
IntVarImpBwd::IntVarImpBwd(void) {}
forceinline
IntVarImpBwd::IntVarImpBwd(const IntVarImp* x)
: n(NULL), c(x->ranges_bwd()) {}
forceinline void
IntVarImpBwd::init(const IntVarImp* x) {
n=NULL; c=x->ranges_bwd();
}
forceinline bool
IntVarImpBwd::operator ()(void) const {
return c != NULL;
}
forceinline void
IntVarImpBwd::operator ++(void) {
const IntVarImp::RangeList* p=c->prev(n); n=c; c=p;
}
forceinline int
IntVarImpBwd::min(void) const {
return c->min();
}
forceinline int
IntVarImpBwd::max(void) const {
return c->max();
}
forceinline unsigned int
IntVarImpBwd::width(void) const {
return c->width();
}
/*
* Iterator-based domain operations
*
*/
template<class I>
forceinline ModEvent
IntVarImp::narrow_r(Space& home, I& ri, bool depends) {
// Is new domain empty?
if (!ri())
return fail(home);
int min0 = ri.min();
int max0 = ri.max();
++ri;
ModEvent me;
// Is new domain range?
if (!ri()) {
// Remove possible rangelist (if it was not a range, the domain
// must have been narrowed!)
if (fst()) {
fst()->dispose(home,NULL,lst());
fst(NULL); holes = 0;
}
const int min1 = dom.min(); dom.min(min0);
const int max1 = dom.max(); dom.max(max0);
if ((min0 == min1) && (max0 == max1))
return ME_INT_NONE;
me = (min0 == max0) ? ME_INT_VAL : ME_INT_BND;
goto notify;
}
if (depends || range()) {
// Construct new rangelist
RangeList* f = new (home) RangeList(min0,max0,NULL,NULL);
RangeList* l = f;
unsigned int s = static_cast<unsigned int>(max0-min0+1);
do {
RangeList* n = new (home) RangeList(ri.min(),ri.max(),l,NULL);
l->next(NULL,n);
l = n;
s += ri.width();
++ri;
} while (ri());
if (fst() != NULL)
fst()->dispose(home,NULL,lst());
fst(f); lst(l);
// Check for modification
if (size() == s)
return ME_INT_NONE;
const int min1 = dom.min(); min0 = f->min(); dom.min(min0);
const int max1 = dom.max(); max0 = l->max(); dom.max(max0);
holes = width() - s;
me = ((min0 == min1) && (max0 == max1)) ? ME_INT_DOM : ME_INT_BND;
goto notify;
} else {
// Set up two sentinel elements
RangeList f, l;
// Put all ranges between sentinels
f.prevnext(NULL,fst()); l.prevnext(lst(),NULL);
fst()->prev(NULL,&f); lst()->next(NULL,&l);
// Number of values removed (potential holes)
unsigned int h = 0;
// The previous range
RangeList* p = &f;
// The current range
RangeList* r = f.next(NULL);
while (true) {
assert((r != &f) && (r != &l));
if (r->max() < min0) {
// Entire range removed
h += r->width();
RangeList* n=r->next(p);
p->next(r,n); n->prev(r,p);
r->dispose(home);
r=n;
if (r == &l)
goto done;
} else if ((r->min() == min0) && (r->max() == max0)) {
// Range unchanged
RangeList* n=r->next(p); p=r; r=n;
if (r == &l)
goto done;
if (!ri())
goto done;
min0=ri.min(); max0=ri.max(); ++ri;
} else {
// Range might have been split into many small ranges
assert((r->min() <= min0) && (max0 <= r->max()));
h += r->width();
int end = r->max();
// Copy first range
r->min(min0); r->max(max0);
assert(h > r->width());
h -= r->width();
{
RangeList* n=r->next(p); p=r; r=n;
}
while (true) {
if (!ri())
goto done;
min0=ri.min(); max0=ri.max(); ++ri;
if (max0 > end)
break;
assert(h > static_cast<unsigned int>(max0-min0+1));
h -= max0-min0+1;
RangeList* n = new (home) RangeList(min0,max0,p,r);
p->next(r,n); r->prev(p,n);
p=n;
}
if (r == &l)
goto done;
}
}
done:
// Remove remaining ranges
while (r != &l) {
h += r->width();
RangeList* n=r->next(p);
p->next(r,n); n->prev(r,p);
r->dispose(home);
r=n;
}
assert((r == &l) && !ri());
// New first and last ranges
RangeList* fn = f.next(NULL);
RangeList* ln = l.prev(NULL);
// All ranges pruned?
assert(fn != &l);
// Only a single range left?
assert(fn != ln);
// The number of removed values
holes += h;
// Unlink sentinel ranges
fn->prev(&f,NULL); ln->next(&l,NULL);
// How many values where removed at the bounds
unsigned int b = (static_cast<unsigned int>(fn->min()-dom.min()) +
static_cast<unsigned int>(dom.max()-ln->max()));
// Set new first and last ranges
fst(fn); lst(ln);
if (b > 0) {
assert((dom.min() != fn->min()) || (dom.max() != ln->max()));
dom.min(fn->min()); dom.max(ln->max());
holes -= b;
me = ME_INT_BND; goto notify;
}
if (h > 0) {
assert((dom.min() == fn->min()) && (dom.max() == ln->max()));
me = ME_INT_DOM; goto notify;
}
return ME_INT_NONE;
}
notify:
IntDelta d;
return notify(home,me,d);
}
template<class I>
forceinline ModEvent
IntVarImp::inter_r(Space& home, I& i, bool) {
IntVarImpFwd j(this);
Iter::Ranges::Inter<I,IntVarImpFwd> ij(i,j);
return narrow_r(home,ij,true);
}
template<class I>
forceinline ModEvent
IntVarImp::minus_r(Space& home, I& i, bool depends) {
if (depends) {
IntVarImpFwd j(this);
Iter::Ranges::Diff<IntVarImpFwd,I> ij(j,i);
return narrow_r(home,ij,true);
}
// Skip all ranges that are too small
while (i() && (i.max() < dom.min()))
++i;
// Is there no range left or all are too large?
if (!i() || (i.min() > dom.max()))
return ME_INT_NONE;
int i_min = i.min();
int i_max = i.max();
++i;
if ((i_min <= dom.min()) && (i_max >= dom.max()))
return fail(home);
if ((i_min > dom.min()) && (i_max >= dom.max()))
return lq(home,i_min-1);
if ((i_min <= dom.min()) && (i_max < dom.max()) &&
(!i() || (i.min() > dom.max())))
return gq(home,i_max+1);
// Set up two sentinel elements
RangeList f, l;
// Put all ranges between sentinels
if (range()) {
// Create a new rangelist just for simplicity
RangeList* n = new (home) RangeList(min(),max(),&f,&l);
f.prevnext(NULL,n); l.prevnext(n,NULL);
} else {
// Link the two sentinel elements
f.prevnext(NULL,fst()); l.prevnext(lst(),NULL);
fst()->prev(NULL,&f); lst()->next(NULL,&l);
}
// Number of values removed (potential holes)
unsigned int h = 0;
// The previous range
RangeList* p = &f;
// The current range
RangeList* r = f.next(NULL);
while (true) {
assert((r != &f) && (r != &l));
if (i_min > r->max()) {
RangeList* n=r->next(p); p=r; r=n;
if (r == &l)
break;
} else if (i_max < r->min()) {
if (!i())
break;
i_min = i.min();
i_max = i.max();
++i;
} else if ((i_min <= r->min()) && (r->max() <= i_max)) {
// r is included in i: remove entire range r
h += r->width();
RangeList* n=r->next(p);
p->next(r,n); n->prev(r,p);
r->dispose(home);
r=n;
if (r == &l)
break;
} else if ((i_min > r->min()) && (i_max < r->max())) {
// i is included in r: create new range before the current one
h += static_cast<unsigned int>(i_max - i_min) + 1;
RangeList* n = new (home) RangeList(r->min(),i_min-1,p,r);
r->min(i_max+1);
p->next(r,n); r->prev(p,n);
p=n;
if (!i())
break;
i_min = i.min();
i_max = i.max();
++i;
} else if (i_max < r->max()) {
assert(i_min <= r->min());
// i ends before r: adjust minimum of r
h += i_max-r->min()+1;
r->min(i_max+1);
if (!i())
break;
i_min = i.min();
i_max = i.max();
++i;
} else {
assert((i_max >= r->max()) && (r->min() < i_min));
// r ends before i: adjust maximum of r
h += r->max()-i_min+1;
r->max(i_min-1);
RangeList* n=r->next(p); p=r; r=n;
if (r == &l)
break;
}
}
// New first and last ranges
RangeList* fn = f.next(NULL);
RangeList* ln = l.prev(NULL);
// All ranges pruned?
if (fn == &l) {
fst(NULL); lst(NULL); holes=0;
return fail(home);
}
ModEvent me;
unsigned int b;
// Only a single range left?
if (fn == ln) {
assert(h > 0);
dom.min(fn->min()); dom.max(fn->max());
fn->dispose(home);
fst(NULL); lst(NULL);
holes = 0;
me = assigned() ? ME_INT_VAL : ME_INT_BND;
goto notify;
}
// The number of removed values
holes += h;
// Unlink sentinel ranges
fn->prev(&f,NULL); ln->next(&l,NULL);
// How many values where removed at the bounds
b = (static_cast<unsigned int>(fn->min()-dom.min()) +
static_cast<unsigned int>(dom.max()-ln->max()));
// Set new first and last ranges
fst(fn); lst(ln);
if (b > 0) {
assert((dom.min() != fn->min()) || (dom.max() != ln->max()));
dom.min(fn->min()); dom.max(ln->max());
holes -= b;
me = ME_INT_BND; goto notify;
}
if (h > 0) {
assert((dom.min() == fn->min()) && (dom.max() == ln->max()));
me = ME_INT_DOM; goto notify;
}
return ME_INT_NONE;
notify:
IntDelta d;
return notify(home,me,d);
}
template<class I>
forceinline ModEvent
IntVarImp::narrow_v(Space& home, I& i, bool depends) {
Iter::Values::ToRanges<I> r(i);
return narrow_r(home,r,depends);
}
template<class I>
forceinline ModEvent
IntVarImp::inter_v(Space& home, I& i, bool depends) {
Iter::Values::ToRanges<I> r(i);
return inter_r(home,r,depends);
}
template<class I>
forceinline ModEvent
IntVarImp::minus_v(Space& home, I& i, bool depends) {
if (depends) {
Iter::Values::ToRanges<I> r(i);
return minus_r(home, r, true);
}
// Skip all values that are too small
while (i() && (i.val() < dom.min()))
++i;
// Is there no value left or all are too large?
if (!i() || (i.val() > dom.max()))
return ME_INT_NONE;
int v = i.val();
// Skip values that are the same
do {
++i;
} while (i() && (i.val() == v));
// Is there only a single value to be pruned?
if (!i() || (i.val() > dom.max()))
return nq_full(home,v);
// Set up two sentinel elements
RangeList f, l;
// Put all ranges between sentinels
if (range()) {
// Create a new rangelist just for simplicity
RangeList* n = new (home) RangeList(min(),max(),&f,&l);
f.prevnext(NULL,n); l.prevnext(n,NULL);
} else {
// Link the two sentinel elements
f.prevnext(NULL,fst()); l.prevnext(lst(),NULL);
fst()->prev(NULL,&f); lst()->next(NULL,&l);
}
// Number of values removed (potential holes)
unsigned int h = 0;
// The previous range
RangeList* p = &f;
// The current range
RangeList* r = f.next(NULL);
while (true) {
assert((r != &f) && (r != &l));
if (v > r->max()) {
// Move to next range
RangeList* n=r->next(p); p=r; r=n;
if (r == &l)
break;
} else {
if ((v == r->min()) && (v == r->max())) {
// Remove range
h++;
RangeList* n=r->next(p);
p->next(r,n); n->prev(r,p);
r->dispose(home);
r=n;
if (r == &l)
break;
} else if (v == r->min()) {
h++; r->min(v+1);
} else if (v == r->max()) {
h++; r->max(v-1);
RangeList* n=r->next(p); p=r; r=n;
if (r == &l)
break;
} else if (v > r->min()) {
// Create new range before the current one
assert(v < r->max());
h++;
RangeList* n = new (home) RangeList(r->min(),v-1,p,r);
r->min(v+1);
p->next(r,n); r->prev(p,n);
p=n;
}
if (!i())
break;
// Move to next value
v = i.val(); ++i;
}
}
assert((r == &l) || !i());
// New first and last ranges
RangeList* fn = f.next(NULL);
RangeList* ln = l.prev(NULL);
// All ranges pruned?
if (fn == &l) {
fst(NULL); lst(NULL); holes=0;
return fail(home);
}
IntDelta d;
// Only a single range left?
if (fn == ln) {
assert(h > 0);
dom.min(fn->min()); dom.max(fn->max());
fn->dispose(home);
fst(NULL); lst(NULL);
holes = 0;
if (assigned())
return notify(home,ME_INT_VAL,d);
else
return notify(home,ME_INT_BND,d);
}
// The number of removed values
holes += h;
// Unlink sentinel ranges
fn->prev(&f,NULL); ln->next(&l,NULL);
// How many values where removed at the bounds
unsigned int b = (static_cast<unsigned int>(fn->min()-dom.min()) +
static_cast<unsigned int>(dom.max()-ln->max()));
// Set new first and last ranges
fst(fn); lst(ln);
if (b > 0) {
assert((dom.min() != fn->min()) || (dom.max() != ln->max()));
dom.min(fn->min()); dom.max(ln->max());
holes -= b;
return notify(home,ME_INT_BND,d);
}
if (h > 0) {
assert((dom.min() == fn->min()) && (dom.max() == ln->max()));
return notify(home,ME_INT_DOM,d);
}
return ME_INT_NONE;
}
/*
* Copying a variable
*
*/
forceinline IntVarImp*
IntVarImp::copy(Space& home) {
return copied() ? static_cast<IntVarImp*>(forward())
: perform_copy(home);
}
forceinline ModEventDelta
IntVarImp::med(ModEvent me) {
return IntVarImpBase::med(me);
}
}}
// STATISTICS: int-var
Gecode::Delta
Generic domain change information to be supplied to advisors.
Definition core.hpp:204
Gecode::FreeList::next
FreeList * next(void) const
Return next freelist object.
Definition manager.hpp:248
Gecode::FreeList::_next
FreeList * _next
Pointer to next freelist object.
Definition manager.hpp:101
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::Int::IntDelta
Integer delta information for advisors.
Definition var-imp.hpp:51
Gecode::Int::IntVarImpBase::IntVarImpBase
IntVarImpBase(Gecode::Space &home, IntVarImpBase &x)
Constructor for cloning x.
Definition var-imp.hpp:239
Gecode::Int::IntVarImpBase::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:261
Gecode::Int::IntVarImpBwd::width
unsigned int width(void) const
Return width of range (distance between minimum and maximum).
Definition int.hpp:492
Gecode::Int::IntVarImpBwd::operator++
void operator++(void)
Move iterator to previous range (if possible).
Definition int.hpp:479
Gecode::Int::IntVarImpBwd::max
int max(void) const
Return largest value of range.
Definition int.hpp:488
Gecode::Int::IntVarImpBwd::operator()
bool operator()(void) const
Test whether iterator is still at a range or done.
Definition int.hpp:475
Gecode::Int::IntVarImpBwd::min
int min(void) const
Return smallest value of range.
Definition int.hpp:484
Gecode::Int::IntVarImpBwd::init
void init(const IntVarImp *x)
Initialize with ranges from variable implementation x.
Definition int.hpp:470
Gecode::Int::IntVarImpBwd::IntVarImpBwd
IntVarImpBwd(void)
Default constructor.
Definition int.hpp:465
Gecode::Int::IntVarImpFwd::init
void init(const IntVarImp *x)
Initialize with ranges from variable implementation x.
Definition int.hpp:432
Gecode::Int::IntVarImpFwd::IntVarImpFwd
IntVarImpFwd(void)
Default constructor.
Definition int.hpp:427
Gecode::Int::IntVarImpFwd::operator()
bool operator()(void) const
Test whether iterator is still at a range or done.
Definition int.hpp:437
Gecode::Int::IntVarImpFwd::width
unsigned int width(void) const
Return width of range (distance between minimum and maximum).
Definition int.hpp:454
Gecode::Int::IntVarImpFwd::min
int min(void) const
Return smallest value of range.
Definition int.hpp:446
Gecode::Int::IntVarImpFwd::operator++
void operator++(void)
Move iterator to next range (if possible).
Definition int.hpp:441
Gecode::Int::IntVarImpFwd::max
int max(void) const
Return largest value of range.
Definition int.hpp:450
Gecode::Int::IntVarImp::RangeList
Lists of ranges (intervals).
Definition var-imp.hpp:102
Gecode::Int::IntVarImp::RangeList::width
unsigned int width(void) const
Return width (distance between maximum and minimum).
Definition int.hpp:106
Gecode::Int::IntVarImp::RangeList::fix
void fix(RangeList *n)
Restore simple link to next element (so that it becomes a true free list).
Definition int.hpp:84
Gecode::Int::IntVarImp::RangeList::_max
int _max
Maximum of range.
Definition var-imp.hpp:107
Gecode::Int::IntVarImp::RangeList::_min
int _min
Minimum of range.
Definition var-imp.hpp:105
Gecode::Int::IntVarImp::RangeList::RangeList
RangeList(void)
Default constructor (noop).
Definition int.hpp:49
Gecode::Int::IntVarImp::RangeList::min
int min(void) const
Return minimum.
Definition int.hpp:98
Gecode::Int::IntVarImp::RangeList::prevnext
void prevnext(RangeList *p, RangeList *n)
Set previous element to p and next element to n.
Definition int.hpp:70
Gecode::Int::IntVarImp::RangeList::prev
RangeList * prev(const RangeList *n) const
Return previous element (from next n).
Definition int.hpp:66
Gecode::Int::IntVarImp::RangeList::next
RangeList * next(const RangeList *p) const
Return next element (from previous p).
Definition int.hpp:62
Gecode::Int::IntVarImp::RangeList::max
int max(void) const
Return maximum.
Definition int.hpp:102
Gecode::Int::IntVarImp::RangeList::dispose
void dispose(Space &home, RangeList *p, RangeList *l)
Free memory for all elements between this and l (inclusive).
Definition int.hpp:134
Gecode::Int::IntVarImp
Integer variable implementation.
Definition var-imp.hpp:89
Gecode::Int::IntVarImp::ranges_bwd
const RangeList * ranges_bwd(void) const
Return range list for backward iteration.
Definition int.hpp:310
Gecode::Int::IntVarImp::_lst
RangeList * _lst
Link the last element.
Definition var-imp.hpp:190
Gecode::Int::IntVarImp::lst
RangeList * lst(void) const
Return last element of rangelist.
Definition int.hpp:173
Gecode::Int::IntVarImp::width
unsigned int width(void) const
Return width of domain (distance between maximum and minimum).
Definition int.hpp:248
Gecode::Int::IntVarImp::eq
ModEvent eq(Space &home, int n)
Restrict domain values to be equal to n.
Definition int.hpp:386
Gecode::Int::IntVarImp::med
int med(void) const
Return median of domain (greatest element not greater than the median).
Definition int.cpp:46
Gecode::Int::IntVarImp::narrow_v
ModEvent narrow_v(Space &home, I &i, bool depends=true)
Replace domain by values described by i.
Definition int.hpp:835
Gecode::Int::IntVarImp::regret_max
unsigned int regret_max(void) const
Return regret of domain maximum (distance to next smaller value).
Definition int.hpp:268
Gecode::Int::IntVarImp::inter_v
ModEvent inter_v(Space &home, I &i, bool depends=true)
Intersect domain with values described by i.
Definition int.hpp:842
Gecode::Int::IntVarImp::in
bool in(int n) const
Test whether n is contained in domain.
Definition int.hpp:286
Gecode::Int::IntVarImp::copy
IntVarImp * copy(Space &home)
Return copy of this variable.
Definition int.hpp:991
Gecode::Int::IntVarImp::assigned
bool assigned(void) const
Test whether variable is assigned.
Definition int.hpp:242
Gecode::Int::IntVarImp::lq
ModEvent lq(Space &home, int n)
Restrict domain values to be less or equal than n.
Definition int.hpp:365
Gecode::Int::IntVarImp::nq
ModEvent nq(Space &home, int n)
Restrict domain values to be different from n.
Definition int.hpp:408
Gecode::Int::IntVarImp::max
int max(void) const
Return maximum of domain.
Definition int.hpp:228
Gecode::Int::IntVarImp::minus_v
ModEvent minus_v(Space &home, I &i, bool depends=true)
Remove from domain the values described by i.
Definition int.hpp:849
Gecode::Int::IntVarImp::val
int val(void) const
Return assigned value (only if assigned).
Definition int.hpp:232
Gecode::Int::IntVarImp::fst
RangeList * fst(void) const
Return first element of rangelist.
Definition int.hpp:163
Gecode::Int::IntVarImp::size
unsigned int size(void) const
Return size (cardinality) of domain.
Definition int.hpp:253
Gecode::Int::IntVarImp::min
int min(void) const
Return minimum of domain.
Definition int.hpp:224
Gecode::Int::IntVarImp::regret_min
unsigned int regret_min(void) const
Return regret of domain minimum (distance to next larger value).
Definition int.hpp:258
Gecode::Int::IntVarImp::dom
RangeList dom
Domain information.
Definition var-imp.hpp:188
Gecode::Int::IntVarImp::holes
unsigned int holes
Size of holes in the domain.
Definition var-imp.hpp:200
Gecode::Int::IntVarImp::range
bool range(void) const
Test whether domain is a range.
Definition int.hpp:238
Gecode::Int::IntVarImp::narrow_r
ModEvent narrow_r(Space &home, I &i, bool depends=true)
Replace domain by ranges described by i.
Definition int.hpp:503
Gecode::Int::IntVarImp::IntVarImp
IntVarImp(Space &home, IntVarImp &x)
Constructor for cloning x.
Definition int.cpp:317
Gecode::Int::IntVarImp::inter_r
ModEvent inter_r(Space &home, I &i, bool depends=true)
Intersect domain with ranges described by i.
Definition int.hpp:670
Gecode::Int::IntVarImp::IntVarImpFwd
friend class IntVarImpFwd
Definition var-imp.hpp:90
Gecode::Int::IntVarImp::minus_r
ModEvent minus_r(Space &home, I &i, bool depends=true)
Remove from domain the ranges described by i.
Definition int.hpp:678
Gecode::Int::IntVarImp::gq
ModEvent gq(Space &home, int n)
Restrict domain values to be greater or equal than n.
Definition int.hpp:344
Gecode::Int::IntVarImp::ranges_fwd
const RangeList * ranges_fwd(void) const
Return range list for forward iteration.
Definition int.hpp:305
Gecode::Int::IntVarImp::any
static bool any(const Delta &d)
Test whether arbitrary values got pruned.
Definition int.hpp:333
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::Values::ToRanges
Range iterator from value iterator.
Definition values-ranges.hpp:46
Gecode::Space
Computation spaces.
Definition core.hpp:1742
Gecode::Space::fl_dispose
void fl_dispose(FreeList *f, FreeList *l)
Return freelist-managed memory to freelist.
Definition core.hpp:2827
Gecode::VarImp< Gecode::Int::IntVarImpConf >::fail
ModEvent fail(Space &home)
Definition core.hpp:4570
Gecode::VarImp< Gecode::Int::IntVarImpConf >::copied
bool copied(void) const
Definition core.hpp:4222
Gecode::VarImp< Gecode::Int::IntVarImpConf >::forward
VarImp * forward(void) const
Definition core.hpp:4228
Gecode::VarImp< Gecode::Int::IntVarImpConf >::me
static ModEvent me(const ModEventDelta &med)
Definition core.hpp:4270
Gecode::VarImp< Gecode::Int::IntVarImpConf >::med
static ModEventDelta med(ModEvent me)
Definition core.hpp:4276
Test::Base::next
Base * next(void) const
Return next test.
Definition test.hpp:58
GECODE_INT_RL2PD
#define GECODE_INT_RL2PD(r)
Definition int.hpp:45
GECODE_INT_PD2RL
#define GECODE_INT_PD2RL(p)
Definition int.hpp:46
Gecode::ModEventDelta
int ModEventDelta
Modification event deltas.
Definition core.hpp:89
Gecode::Int
Finite domain integers.
Gecode::Int::ME_INT_BND
const Gecode::ModEvent ME_INT_BND
Domain operation has changed the minimum or maximum of the domain.
Definition var-type.hpp:65
Gecode::Int::ME_INT_FAILED
const Gecode::ModEvent ME_INT_FAILED
Domain operation has resulted in failure.
Definition var-type.hpp:52
Gecode::Int::ME_INT_VAL
const Gecode::ModEvent ME_INT_VAL
Domain operation has resulted in a value (assigned variable).
Definition var-type.hpp:56
Gecode::Int::ME_INT_DOM
const Gecode::ModEvent ME_INT_DOM
Domain operation has changed the domain.
Definition var-type.hpp:72
Gecode::Int::ME_INT_NONE
const Gecode::ModEvent ME_INT_NONE
Domain operation has not changed domain.
Definition var-type.hpp:54
Gecode
Gecode toplevel namespace
Gecode::ModEvent
int ModEvent
Type for modification events.
Definition core.hpp:62
forceinline
#define forceinline
Definition config.hpp:187
GECODE_NEVER
#define GECODE_NEVER
Assert that this command is never executed.
Definition macros.hpp:56
GECODE_ASSUME
#define GECODE_ASSUME(p)
Assert certain property.
Definition macros.hpp:114