00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026 namespace Gecode { namespace Int {
00027
00028
00029
00030
00031
00032
00033 #define RL2PD(r) reinterpret_cast<ptrdiff_t>(r)
00034 #define PD2RL(p) reinterpret_cast<RangeList*>(p)
00035
00036 forceinline
00037 IntVarImp::RangeList::RangeList(void) {}
00038
00039 forceinline
00040 IntVarImp::RangeList::RangeList(int min, int max)
00041 : _min(min), _max(max) {}
00042
00043 forceinline
00044 IntVarImp::RangeList::RangeList(int min, int max, RangeList* p, RangeList* n)
00045 : _min(min), _max(max) {
00046 _next = PD2RL(RL2PD(p)^RL2PD(n));
00047 }
00048
00049 forceinline IntVarImp::RangeList*
00050 IntVarImp::RangeList::next(const RangeList* p) const {
00051 return PD2RL(RL2PD(_next)^RL2PD(p));
00052 }
00053 forceinline IntVarImp::RangeList*
00054 IntVarImp::RangeList::prev(const RangeList* n) const {
00055 return PD2RL(RL2PD(_next)^RL2PD(n));
00056 }
00057 forceinline void
00058 IntVarImp::RangeList::prevnext(RangeList* p, RangeList* n) {
00059 _next = PD2RL(RL2PD(p)^RL2PD(n));
00060 }
00061 forceinline void
00062 IntVarImp::RangeList::next(RangeList* o, RangeList* n) {
00063 _next = PD2RL(RL2PD(_next)^(RL2PD(o)^RL2PD(n)));
00064 }
00065 forceinline void
00066 IntVarImp::RangeList::prev(RangeList* o, RangeList* n) {
00067 _next = PD2RL(RL2PD(_next)^(RL2PD(o)^RL2PD(n)));
00068 }
00069 forceinline void
00070 IntVarImp::RangeList::fix(RangeList* n) {
00071 _next = n;
00072 }
00073
00074 forceinline void
00075 IntVarImp::RangeList::min(int n) {
00076 _min = n;
00077 }
00078 forceinline void
00079 IntVarImp::RangeList::max(int n) {
00080 _max = n;
00081 }
00082
00083 forceinline int
00084 IntVarImp::RangeList::min(void) const {
00085 return _min;
00086 }
00087 forceinline int
00088 IntVarImp::RangeList::max(void) const {
00089 return _max;
00090 }
00091 forceinline unsigned int
00092 IntVarImp::RangeList::width(void) const {
00093 return _max - _min + 1;
00094 }
00095
00096
00097 forceinline void
00098 IntVarImp::RangeList::operator delete(void*) {}
00099
00100 forceinline void
00101 IntVarImp::RangeList::operator delete(void*, Space*) {
00102 assert(false);
00103 }
00104
00105 forceinline void*
00106 IntVarImp::RangeList::operator new(size_t s, Space* home) {
00107 assert(s == sizeof(RangeList));
00108 return home->fl_alloc<sizeof(RangeList)>();
00109 }
00110
00111 forceinline void
00112 IntVarImp::RangeList::dispose(Space* home, RangeList* p, RangeList* l) {
00113 RangeList* c = this;
00114 while (c != l) {
00115 RangeList* n = c->next(p);
00116 c->fix(n);
00117 p=c; c=n;
00118 }
00119 home->fl_dispose<sizeof(RangeList)>(this,l);
00120 }
00121
00122 forceinline void
00123 IntVarImp::RangeList::dispose(Space* home, RangeList* l) {
00124 home->fl_dispose<sizeof(RangeList)>(this,l);
00125 }
00126
00127 forceinline void
00128 IntVarImp::RangeList::dispose(Space* home) {
00129 home->fl_dispose<sizeof(RangeList)>(this,this);
00130 }
00131
00132 #undef RL2PD
00133 #undef PD2RL
00134
00135
00136
00137
00138
00139
00140 forceinline IntVarImp::RangeList*
00141 IntVarImp::fst(void) const {
00142 return dom.next(NULL);
00143 }
00144
00145 forceinline void
00146 IntVarImp::fst(IntVarImp::RangeList* f) {
00147 dom.prevnext(NULL,f);
00148 }
00149
00150 forceinline IntVarImp::RangeList*
00151 IntVarImp::lst(void) const {
00152 return _lst;
00153 }
00154
00155 forceinline void
00156 IntVarImp::lst(IntVarImp::RangeList* l) {
00157 _lst = l;
00158 }
00159
00160
00161
00162
00163
00164
00165 forceinline
00166 IntVarImp::IntVarImp(Space* home, int min, int max)
00167 : Variable<VTI_INT,PC_INT_DOM>(home),
00168 dom(min,max,NULL,NULL), holes(0) {}
00169
00170 forceinline
00171 IntVarImp::IntVarImp(Space* home, const IntSet& d)
00172 : Variable<VTI_INT,PC_INT_DOM>(home),
00173 dom(d.min(),d.max()) {
00174 if (d.size() > 1) {
00175 int n = d.size();
00176 RangeList* r = reinterpret_cast<RangeList*>
00177 (home->alloc(sizeof(RangeList)*n));
00178 fst(r); lst(r+n-1);
00179 unsigned int h = d.max()-d.min()+1;
00180 for (int i = n; i--; ) {
00181 h -= d.width(i);
00182 r[i].min(d.min(i)); r[i].max(d.max(i));
00183 r[i].prevnext(&r[i-1],&r[i+1]);
00184 }
00185 r[0].prev(&r[-1],NULL);
00186 r[n-1].next(&r[n],NULL);
00187 holes = h;
00188 } else {
00189 fst(NULL); holes = 0;
00190 }
00191 }
00192
00193
00194
00195
00196
00197
00198
00199 forceinline int
00200 IntVarImp::min(void) const {
00201 return dom.min();
00202 }
00203 forceinline int
00204 IntVarImp::max(void) const {
00205 return dom.max();
00206 }
00207 forceinline int
00208 IntVarImp::val(void) const {
00209 assert(dom.min() == dom.max());
00210 return dom.min();
00211 }
00212
00213 forceinline bool
00214 IntVarImp::range(void) const {
00215 return fst() == NULL;
00216 }
00217 forceinline bool
00218 IntVarImp::assigned(void) const {
00219 return dom.min() == dom.max();
00220 }
00221
00222
00223 forceinline unsigned int
00224 IntVarImp::width(void) const {
00225 return dom.width();
00226 }
00227
00228 forceinline unsigned int
00229 IntVarImp::size(void) const {
00230 return dom.width() - holes;
00231 }
00232
00233 forceinline unsigned int
00234 IntVarImp::regret_min(void) const {
00235 if (fst() == NULL) {
00236 return (dom.min() == dom.max()) ? 0 : 1;
00237 } else if (dom.min() == fst()->max()) {
00238 return fst()->next(NULL)->min()-dom.min();
00239 } else {
00240 return 1;
00241 }
00242 }
00243 forceinline unsigned int
00244 IntVarImp::regret_max(void) const {
00245 if (lst() == NULL) {
00246 return (dom.min() == dom.max()) ? 0 : 1;
00247 } else if (dom.max() == lst()->min()) {
00248 return dom.max()-lst()->prev(NULL)->max();
00249 } else {
00250 return 1;
00251 }
00252 }
00253
00254
00255
00256
00257
00258
00259
00260
00261 forceinline bool
00262 IntVarImp::in(int n) const {
00263 if ((n < dom.min()) || (n > dom.max()))
00264 return false;
00265 return (fst() == NULL) || in_full(n);
00266 }
00267 forceinline bool
00268 IntVarImp::in(double n) const {
00269 if ((n < dom.min()) || (n > dom.max()))
00270 return false;
00271 return (fst() == NULL) || in_full(static_cast<int>(n));
00272 }
00273
00274
00275
00276
00277
00278
00279
00280 forceinline const IntVarImp::RangeList*
00281 IntVarImp::ranges_fwd(void) const {
00282 return (fst() == NULL) ? &dom : fst();
00283 }
00284
00285 forceinline const IntVarImp::RangeList*
00286 IntVarImp::ranges_bwd(void) const {
00287 return (fst() == NULL) ? &dom : lst();
00288 }
00289
00290
00291
00292
00293
00294
00295
00296
00297 forceinline ModEvent
00298 IntVarImp::gq(Space* home, int n) {
00299 if (n <= dom.min()) return ME_INT_NONE;
00300 if (n > dom.max()) return ME_INT_FAILED;
00301 gq_full(home,n);
00302 if (assigned())
00303 return ME_INT_VAL;
00304 return ME_INT_BND;
00305 }
00306 forceinline ModEvent
00307 IntVarImp::gq(Space* home, double n) {
00308 if (n <= dom.min()) return ME_INT_NONE;
00309 if (n > dom.max()) return ME_INT_FAILED;
00310 gq_full(home,static_cast<int>(n));
00311 if (assigned())
00312 return ME_INT_VAL;
00313 return ME_INT_BND;
00314 }
00315
00316
00317 forceinline ModEvent
00318 IntVarImp::lq(Space* home, int n) {
00319 if (n >= dom.max()) return ME_INT_NONE;
00320 if (n < dom.min()) return ME_INT_FAILED;
00321 lq_full(home,n);
00322 if (dom.min() == n)
00323 return ME_INT_VAL;
00324 return ME_INT_BND;
00325 }
00326 forceinline ModEvent
00327 IntVarImp::lq(Space* home, double n) {
00328 if (n >= dom.max()) return ME_INT_NONE;
00329 if (n < dom.min()) return ME_INT_FAILED;
00330 lq_full(home,static_cast<int>(n));
00331 if (dom.max() == n)
00332 return ME_INT_VAL;
00333 return ME_INT_BND;
00334 }
00335
00336
00337 forceinline ModEvent
00338 IntVarImp::eq(Space* home, int n) {
00339 if ((n < dom.min()) || (n > dom.max()))
00340 return ME_INT_FAILED;
00341 if ((n == dom.min()) && (n == dom.max()))
00342 return ME_INT_NONE;
00343 eq_full(home,n);
00344 if (dom.min() == Limits::Int::int_max+1)
00345 return ME_INT_FAILED;
00346 return ME_INT_VAL;
00347 }
00348 forceinline ModEvent
00349 IntVarImp::eq(Space* home, double n) {
00350 if ((n < dom.min()) || (n > dom.max()))
00351 return ME_INT_FAILED;
00352 if ((n == dom.min()) && (n == dom.max()))
00353 return ME_INT_NONE;
00354 eq_full(home,static_cast<int>(n));
00355 if (dom.min() == Limits::Int::int_max+1)
00356 return ME_INT_FAILED;
00357 return ME_INT_VAL;
00358 }
00359
00360
00361 forceinline ModEvent
00362 IntVarImp::nq(Space* home, int n) {
00363 if ((n < dom.min()) || (n > dom.max())) return ME_INT_NONE;
00364 return nq_full(home,n);
00365 }
00366 forceinline ModEvent
00367 IntVarImp::nq(Space* home, double d) {
00368 if ((d < dom.min()) || (d > dom.max())) return ME_INT_NONE;
00369 return nq_full(home,static_cast<int>(d));
00370 }
00371
00372
00373
00374
00375
00376
00377
00378 template <class I>
00379 forceinline ModEvent
00380 IntVarImp::narrow(Space* home, I& ri) {
00381
00382 if (!ri())
00383 return ME_INT_FAILED;
00384 int min0 = ri.min();
00385 int max0 = ri.max();
00386 ++ri;
00387
00388 if (!ri()) {
00389
00390
00391 if (fst()) {
00392 fst()->dispose(home,NULL,lst());
00393 fst(NULL); holes = 0;
00394 }
00395 const int min1 = dom.min(); dom.min(min0);
00396 const int max1 = dom.max(); dom.max(max0);
00397 if ((min0 == min1) && (max0 == max1))
00398 return ME_INT_NONE;
00399 if (min0 == max0) {
00400 notify(home,ME_INT_VAL);
00401 return ME_INT_VAL;
00402 }
00403 } else {
00404
00405 RangeList* f = new (home) RangeList(min0,max0,NULL,NULL);
00406 RangeList* l = f;
00407 unsigned int s = max0-min0+1;
00408 do {
00409 RangeList* n = new (home) RangeList(ri.min(),ri.max(),l,NULL);
00410 l->next(NULL,n);
00411 l = n;
00412 s += ri.width();
00413 ++ri;
00414 } while (ri());
00415 if (fst() != NULL)
00416 fst()->dispose(home,NULL,lst());
00417 fst(f); lst(l);
00418
00419 if (size() == s)
00420 return ME_INT_NONE;
00421 const int min1 = dom.min(); min0 = f->min(); dom.min(min0);
00422 const int max1 = dom.max(); max0 = l->max(); dom.max(max0);
00423 holes = width() - s;
00424 if ((min0 == min1) && (max0 == max1)) {
00425 notify(home,ME_INT_DOM);
00426 return ME_INT_DOM;
00427 }
00428 }
00429 notify(home,ME_INT_BND);
00430 return ME_INT_BND;
00431 }
00432
00433
00434
00435
00436
00437
00438 forceinline IntVarImp*
00439 IntVarImp::copy(Space* home, bool share) {
00440 return copied() ? static_cast<IntVarImp*>(forward())
00441 : perform_copy(home,share);
00442 }
00443
00444
00445
00446
00447
00448
00449
00450
00451 forceinline void
00452 IntVarImp::t_zero_none(Space* home) {
00453 assert((dom.min() == 0) && (dom.max() == 1));
00454 dom.max(0);
00455 notify_unmodified(home,ME_INT_VAL);
00456 }
00457
00458 forceinline void
00459 IntVarImp::t_one_none(Space* home) {
00460 assert((dom.min() == 0) && (dom.max() == 1));
00461 dom.min(1);
00462 notify_unmodified(home,ME_INT_VAL);
00463 }
00464
00465
00466
00467
00468
00469
00470
00471 forceinline
00472 IntVarImpFwd::IntVarImpFwd(void) {}
00473 forceinline
00474 IntVarImpFwd::IntVarImpFwd(const IntVarImp* x)
00475 : p(NULL), c(x->ranges_fwd()) {}
00476 forceinline void
00477 IntVarImpFwd::init(const IntVarImp* x) {
00478 p=NULL; c=x->ranges_fwd();
00479 }
00480
00481 forceinline bool
00482 IntVarImpFwd::operator()(void) const {
00483 return c != NULL;
00484 }
00485 forceinline void
00486 IntVarImpFwd::operator++(void) {
00487 const IntVarImp::RangeList* n=c->next(p); p=c; c=n;
00488 }
00489
00490 forceinline int
00491 IntVarImpFwd::min(void) const {
00492 return c->min();
00493 }
00494 forceinline int
00495 IntVarImpFwd::max(void) const {
00496 return c->max();
00497 }
00498 forceinline unsigned int
00499 IntVarImpFwd::width(void) const {
00500 return c->width();
00501 }
00502
00503
00504
00505
00506
00507
00508
00509 forceinline
00510 IntVarImpBwd::IntVarImpBwd(void) {}
00511 forceinline
00512 IntVarImpBwd::IntVarImpBwd(const IntVarImp* x)
00513 : n(NULL), c(x->ranges_bwd()) {}
00514 forceinline void
00515 IntVarImpBwd::init(const IntVarImp* x) {
00516 n=NULL; c=x->ranges_bwd();
00517 }
00518
00519 forceinline bool
00520 IntVarImpBwd::operator()(void) const {
00521 return c != NULL;
00522 }
00523 forceinline void
00524 IntVarImpBwd::operator++(void) {
00525 const IntVarImp::RangeList* p=c->prev(n); n=c; c=p;
00526 }
00527
00528 forceinline int
00529 IntVarImpBwd::min(void) const {
00530 return c->min();
00531 }
00532 forceinline int
00533 IntVarImpBwd::max(void) const {
00534 return c->max();
00535 }
00536 forceinline unsigned int
00537 IntVarImpBwd::width(void) const {
00538 return c->width();
00539 }
00540
00541
00542
00543
00544
00545
00546 template <class I>
00547 forceinline ModEvent
00548 IntVarImp::inter(Space* home, I& i) {
00549 IntVarImpFwd j(this);
00550 Iter::Ranges::Inter<I,IntVarImpFwd> ij(i,j);
00551 return narrow(home,ij);
00552 }
00553
00554 template <class I>
00555 forceinline ModEvent
00556 IntVarImp::minus(Space* home, I& i) {
00557 IntVarImpFwd j(this);
00558 Iter::Ranges::Diff<IntVarImpFwd,I> ij(j,i);
00559 return narrow(home,ij);
00560 }
00561
00562 }}
00563
00564
00565