38namespace Gecode {
namespace Int {
45#define GECODE_INT_RL2PD(r) reinterpret_cast<ptrdiff_t>(r)
46#define GECODE_INT_PD2RL(p) reinterpret_cast<RangeList*>(p)
53 : _min(min), _max(max) {}
57 : _min(min), _max(max) {
107 return static_cast<unsigned int>(_max - _min) + 1;
112 IntVarImp::RangeList::operator
delete(
void*) {}
115 IntVarImp::RangeList::operator
delete(
void*,
Space&) {
119 IntVarImp::RangeList::operator
delete(
void*,
void*) {
124 IntVarImp::RangeList::operator
new(size_t,
Space& home) {
125 return home.fl_alloc<
sizeof(
RangeList)>();
129 IntVarImp::RangeList::operator
new(size_t,
void*
p) {
154#undef GECODE_INT_RL2PD
155#undef GECODE_INT_PD2RL
163 IntVarImp::fst(
void)
const {
164 return dom.next(NULL);
169 dom.prevnext(NULL,f);
173 IntVarImp::lst(
void)
const {
178 IntVarImp::lst(IntVarImp::RangeList*
l) {
188 IntVarImp::IntVarImp(Space& home,
int min,
int max)
192 IntVarImp::IntVarImp(Space& home,
const IntSet& d)
199 unsigned int h =
static_cast<unsigned int>(
d.
max()-
d.
min())+1;
202 r[0].prevnext(NULL,&
r[1]);
203 for (
int i = 1;
i <
n-1;
i++) {
206 r[
i].prevnext(&
r[i-1],&
r[i+1]);
210 r[
n-1].prevnext(&
r[
n-2],NULL);
213 fst(NULL); holes = 0;
224 IntVarImp::min(
void)
const {
228 IntVarImp::max(
void)
const {
232 IntVarImp::val(
void)
const {
233 assert(
dom.min() ==
dom.max());
238 IntVarImp::range(
void)
const {
239 return fst() == NULL;
242 IntVarImp::assigned(
void)
const {
243 return dom.min() ==
dom.max();
248 IntVarImp::width(
void)
const {
253 IntVarImp::size(
void)
const {
254 return dom.width() - holes;
258 IntVarImp::regret_min(
void)
const {
260 return (
dom.min() ==
dom.max()) ? 0U : 1U;
261 }
else if (
dom.min() == fst()->
max()) {
262 return static_cast<unsigned int>(fst()->next(NULL)->min()-
dom.min());
268 IntVarImp::regret_max(
void)
const {
270 return (
dom.min() ==
dom.max()) ? 0U : 1U;
271 }
else if (
dom.max() == lst()->
min()) {
272 return static_cast<unsigned int>(
dom.max()-lst()->prev(NULL)->max());
286 IntVarImp::in(
int n)
const {
287 if ((
n <
dom.min()) || (
n >
dom.max()))
289 return (fst() == NULL) || in_full(
n);
292 IntVarImp::in(
long long int n)
const {
293 if ((
n <
dom.min()) || (
n >
dom.max()))
295 return (fst() == NULL) || in_full(
static_cast<int>(
n));
305 IntVarImp::ranges_fwd(
void)
const {
306 return (fst() == NULL) ? &
dom : fst();
310 IntVarImp::ranges_bwd(
void)
const {
311 return (fst() == NULL) ? &
dom : lst();
321 IntVarImp::min(
const Delta& d) {
322 return static_cast<const IntDelta&
>(
d).
min();
325 IntVarImp::max(
const Delta& d) {
326 return static_cast<const IntDelta&
>(
d).
max();
329 IntVarImp::width(
const Delta& d) {
330 return static_cast<const IntDelta&
>(
d).width();
333 IntVarImp::any(
const Delta& d) {
334 return static_cast<const IntDelta&
>(
d).
any();
344 IntVarImp::gq(Space& home,
int n) {
346 if (
n >
dom.max())
return fail(home);
354 IntVarImp::gq(Space& home,
long long int n) {
356 if (
n >
dom.max())
return fail(home);
365 IntVarImp::lq(Space& home,
int n) {
367 if (
n <
dom.min())
return fail(home);
375 IntVarImp::lq(Space& home,
long long int n) {
377 if (
n <
dom.min())
return fail(home);
386 IntVarImp::eq(Space& home,
int n) {
387 if ((
n <
dom.min()) || (
n >
dom.max()))
389 if ((
n ==
dom.min()) && (
n ==
dom.max()))
396 IntVarImp::eq(Space& home,
long long int m) {
397 if ((m <
dom.min()) || (m >
dom.max()))
399 int n =
static_cast<int>(m);
400 if ((
n ==
dom.min()) && (
n ==
dom.max()))
408 IntVarImp::nq(Space& home,
int n) {
409 if ((
n <
dom.min()) || (
n >
dom.max()))
411 return nq_full(home,
n);
414 IntVarImp::nq(Space& home,
long long int d) {
415 if ((d <
dom.min()) || (d >
dom.max()))
417 return nq_full(home,
static_cast<int>(d));
427 IntVarImpFwd::IntVarImpFwd(
void) {}
429 IntVarImpFwd::IntVarImpFwd(
const IntVarImp*
x)
430 :
p(NULL),
c(
x->ranges_fwd()) {}
432 IntVarImpFwd::init(
const IntVarImp*
x) {
433 p=NULL;
c=
x->ranges_fwd();
437 IntVarImpFwd::operator ()(
void)
const {
441 IntVarImpFwd::operator ++(
void) {
442 const IntVarImp::RangeList*
n=
c->next(
p);
p=
c;
c=
n;
446 IntVarImpFwd::min(
void)
const {
450 IntVarImpFwd::max(
void)
const {
454 IntVarImpFwd::width(
void)
const {
465 IntVarImpBwd::IntVarImpBwd(
void) {}
467 IntVarImpBwd::IntVarImpBwd(
const IntVarImp*
x)
468 :
n(NULL),
c(
x->ranges_bwd()) {}
470 IntVarImpBwd::init(
const IntVarImp*
x) {
471 n=NULL;
c=
x->ranges_bwd();
475 IntVarImpBwd::operator ()(
void)
const {
479 IntVarImpBwd::operator ++(
void) {
480 const IntVarImp::RangeList*
p=
c->prev(
n);
n=
c;
c=
p;
484 IntVarImpBwd::min(
void)
const {
488 IntVarImpBwd::max(
void)
const {
492 IntVarImpBwd::width(
void)
const {
503 IntVarImp::narrow_r(Space& home, I& ri,
bool depends) {
519 fst()->dispose(home,NULL,lst());
520 fst(NULL); holes = 0;
522 const int min1 =
dom.min();
dom.min(min0);
523 const int max1 =
dom.max();
dom.max(max0);
524 if ((min0 == min1) && (max0 == max1))
530 if (depends ||
range()) {
532 RangeList*
f =
new (home) RangeList(min0,max0,NULL,NULL);
534 unsigned int s =
static_cast<unsigned int>(max0-min0+1);
536 RangeList*
n =
new (home) RangeList(ri.min(),ri.max(),
l,NULL);
543 fst()->dispose(home,NULL,lst());
550 const int min1 =
dom.min(); min0 =
f->min();
dom.min(min0);
551 const int max1 =
dom.max(); max0 =
l->max();
dom.max(max0);
560 f.prevnext(NULL,fst());
l.prevnext(lst(),NULL);
561 fst()->prev(NULL,&f); lst()->
next(NULL,&
l);
568 RangeList*
r =
f.
next(NULL);
571 assert((
r != &f) && (
r != &
l));
572 if (
r->max() < min0) {
575 RangeList*
n=
r->next(
p);
576 p->next(
r,
n);
n->prev(
r,
p);
581 }
else if ((
r->min() == min0) && (
r->max() == max0)) {
583 RangeList*
n=
r->next(
p);
p=
r;
r=
n;
588 min0=ri.min(); max0=ri.max(); ++ri;
591 assert((
r->min() <= min0) && (max0 <= r->
max()));
595 r->min(min0);
r->max(max0);
596 assert(h >
r->width());
599 RangeList*
n=
r->next(
p);
p=
r;
r=
n;
604 min0=ri.min(); max0=ri.max(); ++ri;
607 assert(h >
static_cast<unsigned int>(max0-min0+1));
609 RangeList*
n =
new (home) RangeList(min0,max0,
p,
r);
610 p->next(
r,
n);
r->prev(
p,
n);
622 RangeList*
n=
r->next(
p);
623 p->next(
r,
n);
n->prev(
r,
p);
628 assert((
r == &
l) && !ri());
631 RangeList* fn =
f.
next(NULL);
632 RangeList* ln =
l.prev(NULL);
643 fn->prev(&f,NULL); ln->next(&
l,NULL);
645 unsigned int b = (
static_cast<unsigned int>(fn->min()-
dom.min()) +
646 static_cast<unsigned int>(
dom.max()-ln->max()));
651 assert((
dom.min() != fn->min()) || (
dom.max() != ln->max()));
652 dom.min(fn->min());
dom.max(ln->max());
658 assert((
dom.min() == fn->min()) && (
dom.max() == ln->max()));
670 IntVarImp::inter_r(Space& home, I& i,
bool) {
671 IntVarImpFwd j(
this);
672 Iter::Ranges::Inter<I,IntVarImpFwd> ij(i,j);
673 return narrow_r(home,ij,
true);
678 IntVarImp::minus_r(Space& home, I& i,
bool depends) {
680 IntVarImpFwd j(
this);
681 Iter::Ranges::Diff<IntVarImpFwd,I> ij(j,i);
682 return narrow_r(home,ij,
true);
686 while (
i() && (
i.max() <
dom.min()))
690 if (!
i() || (
i.min() >
dom.max()))
697 if ((i_min <=
dom.min()) && (i_max >=
dom.max()))
700 if ((i_min >
dom.min()) && (i_max >=
dom.max()))
701 return lq(home,i_min-1);
703 if ((i_min <=
dom.min()) && (i_max <
dom.max()) &&
704 (!
i() || (
i.min() >
dom.max())))
705 return gq(home,i_max+1);
712 RangeList*
n =
new (home) RangeList(
min(),
max(),&
f,&
l);
713 f.prevnext(NULL,
n);
l.prevnext(
n,NULL);
716 f.prevnext(NULL,fst());
l.prevnext(lst(),NULL);
717 fst()->prev(NULL,&f); lst()->
next(NULL,&
l);
725 RangeList*
r =
f.
next(NULL);
728 assert((
r != &f) && (
r != &
l));
729 if (i_min >
r->max()) {
730 RangeList*
n=
r->next(
p);
p=
r;
r=
n;
733 }
else if (i_max < r->
min()) {
739 }
else if ((i_min <= r->
min()) && (
r->max() <= i_max)) {
742 RangeList*
n=
r->next(
p);
743 p->next(
r,
n);
n->prev(
r,
p);
748 }
else if ((i_min >
r->min()) && (i_max < r->
max())) {
750 h +=
static_cast<unsigned int>(i_max - i_min) + 1;
751 RangeList*
n =
new (home) RangeList(
r->min(),i_min-1,
p,
r);
753 p->next(
r,
n);
r->prev(
p,
n);
760 }
else if (i_max < r->
max()) {
761 assert(i_min <= r->
min());
763 h += i_max-
r->min()+1;
771 assert((i_max >=
r->max()) && (
r->min() < i_min));
773 h +=
r->max()-i_min+1;
775 RangeList*
n=
r->next(
p);
p=
r;
r=
n;
782 RangeList* fn =
f.
next(NULL);
783 RangeList* ln =
l.prev(NULL);
787 fst(NULL); lst(NULL); holes=0;
797 dom.min(fn->min());
dom.max(fn->max());
799 fst(NULL); lst(NULL);
808 fn->prev(&f,NULL); ln->next(&
l,NULL);
810 b = (
static_cast<unsigned int>(fn->min()-
dom.min()) +
811 static_cast<unsigned int>(
dom.max()-ln->max()));
816 assert((
dom.min() != fn->min()) || (
dom.max() != ln->max()));
817 dom.min(fn->min());
dom.max(ln->max());
823 assert((
dom.min() == fn->min()) && (
dom.max() == ln->max()));
835 IntVarImp::narrow_v(Space& home, I& i,
bool depends) {
836 Iter::Values::ToRanges<I>
r(i);
837 return narrow_r(home,
r,depends);
842 IntVarImp::inter_v(Space& home, I& i,
bool depends) {
843 Iter::Values::ToRanges<I>
r(i);
844 return inter_r(home,
r,depends);
849 IntVarImp::minus_v(Space& home, I& i,
bool depends) {
851 Iter::Values::ToRanges<I>
r(i);
852 return minus_r(home,
r,
true);
856 while (
i() && (
i.val() <
dom.min()))
860 if (!
i() || (
i.val() >
dom.max()))
867 }
while (
i() && (
i.val() == v));
870 if (!
i() || (
i.val() >
dom.max()))
871 return nq_full(home,v);
878 RangeList*
n =
new (home) RangeList(
min(),
max(),&
f,&
l);
879 f.prevnext(NULL,
n);
l.prevnext(
n,NULL);
882 f.prevnext(NULL,fst());
l.prevnext(lst(),NULL);
883 fst()->prev(NULL,&f); lst()->
next(NULL,&
l);
891 RangeList*
r =
f.
next(NULL);
894 assert((
r != &f) && (
r != &
l));
897 RangeList*
n=
r->next(
p);
p=
r;
r=
n;
901 if ((v ==
r->min()) && (v ==
r->max())) {
904 RangeList*
n=
r->next(
p);
905 p->next(
r,
n);
n->prev(
r,
p);
910 }
else if (v ==
r->min()) {
912 }
else if (v ==
r->max()) {
914 RangeList*
n=
r->next(
p);
p=
r;
r=
n;
917 }
else if (v >
r->min()) {
919 assert(v < r->
max());
921 RangeList*
n =
new (home) RangeList(
r->min(),
v-1,
p,
r);
923 p->next(
r,
n);
r->prev(
p,
n);
932 assert((
r == &
l) || !
i());
935 RangeList* fn =
f.
next(NULL);
936 RangeList* ln =
l.prev(NULL);
940 fst(NULL); lst(NULL); holes=0;
949 dom.min(fn->min());
dom.max(fn->max());
951 fst(NULL); lst(NULL);
962 fn->prev(&f,NULL); ln->next(&
l,NULL);
964 unsigned int b = (
static_cast<unsigned int>(fn->min()-
dom.min()) +
965 static_cast<unsigned int>(
dom.max()-ln->max()));
970 assert((
dom.min() != fn->min()) || (
dom.max() != ln->max()));
971 dom.min(fn->min());
dom.max(ln->max());
977 assert((
dom.min() == fn->min()) && (
dom.max() == ln->max()));
991 IntVarImp::copy(Space& home) {
993 : perform_copy(home);
struct Gecode::@603::NNF::@65::@66 b
For binary nodes (and, or, eqv)
int p
Number of positive literals for node type.
int n
Number of negative literals for node type.
friend FloatVal max(const FloatVal &x, const FloatVal &y)
friend FloatVal min(const FloatVal &x, const FloatVal &y)
FreeList * next(void) const
Return next freelist object.
FreeList * _next
Pointer to next freelist object.
int min(int i) const
Return minimum of range at position i.
int max(int i) const
Return maximum of range at position i.
int ranges(void) const
Return number of ranges of the specification.
unsigned int width(int i) const
Return width of range at position i.
IntVarImpBase(void)
Constructor for creating static instance of variable.
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...
Lists of ranges (intervals)
unsigned int width(void) const
Return width (distance between maximum and minimum)
void fix(RangeList *n)
Restore simple link to next element (so that it becomes a true free list)
RangeList(void)
Default constructor (noop)
int min(void) const
Return minimum.
void prevnext(RangeList *p, RangeList *n)
Set previous element to p and next element to n.
RangeList * prev(const RangeList *n) const
Return previous element (from next n)
int max(void) const
Return maximum.
void dispose(Space &home, RangeList *p, RangeList *l)
Free memory for all elements between this and l (inclusive)
void fl_dispose(FreeList *f, FreeList *l)
Return freelist-managed memory to freelist.
ModEvent fail(Space &home)
Run advisors to be run on failure and returns ME_GEN_FAILED.
bool copied(void) const
Is variable already copied.
VarImp * forward(void) const
Use forward pointer if variable already copied.
static ModEvent me(const ModEventDelta &med)
Project modification event for this variable type from med.
static ModEventDelta med(ModEvent me)
Translate modification event me into modification event delta.
Base * next(void) const
Return next test.
#define GECODE_INT_RL2PD(r)
#define GECODE_INT_PD2RL(p)
int ModEventDelta
Modification event deltas.
bool any(const View &x)
Test whether x is neither positive nor negative.
const FloatNum max
Largest allowed float value.
const FloatNum min
Smallest allowed float value.
bool assigned(View x, int v)
Whether x is assigned to value v.
const Gecode::ModEvent ME_INT_BND
Domain operation has changed the minimum or maximum of the domain.
const Gecode::ModEvent ME_INT_FAILED
Domain operation has resulted in failure.
const Gecode::ModEvent ME_INT_VAL
Domain operation has resulted in a value (assigned variable)
const Gecode::ModEvent ME_INT_DOM
Domain operation has changed the domain.
const Gecode::ModEvent ME_INT_NONE
Domain operation has not changed domain.
unsigned int size(I &i)
Size of all ranges of range iterator i.
Gecode toplevel namespace
Post propagator for SetVar SetOpType SetVar SetRelType r
void dom(Home home, FloatVar x, FloatVal n)
Propagates .
void range(Home home, const IntVarArgs &x, SetVar y, SetVar z)
Post constraint .
Post propagator for SetVar x
int ModEvent
Type for modification events.
Gecode::FloatVal c(-8, 8)
Gecode::IntArgs i({1, 2, 3, 4})
#define GECODE_NEVER
Assert that this command is never executed.
#define GECODE_ASSUME(p)
Assert certain property.