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
00027
00028
00029
00030
00031
00032
00033
00034 namespace Gecode { namespace Int { namespace Linear {
00035
00036
00037
00038
00039
00040 forceinline
00041 ScaleBoolArray::ScaleBoolArray(void) {}
00042 forceinline
00043 ScaleBoolArray::ScaleBoolArray(Space& home, int n) {
00044 if (n > 0) {
00045 _fst = home.alloc<ScaleBool>(n);
00046 _lst = _fst+n;
00047 } else {
00048 _fst = _lst = NULL;
00049 }
00050 }
00051 forceinline void
00052 ScaleBoolArray::subscribe(Space& home, Propagator& p) {
00053 for (ScaleBool* f = _fst; f < _lst; f++)
00054 f->x.subscribe(home,p,PC_BOOL_VAL);
00055 }
00056 forceinline void
00057 ScaleBoolArray::cancel(Space& home, Propagator& p) {
00058 for (ScaleBool* f = _fst; f < _lst; f++)
00059 f->x.cancel(home,p,PC_BOOL_VAL);
00060 }
00061 forceinline void
00062 ScaleBoolArray::reschedule(Space& home, Propagator& p) {
00063 for (ScaleBool* f = _fst; f < _lst; f++)
00064 f->x.reschedule(home,p,PC_BOOL_VAL);
00065 }
00066 forceinline void
00067 ScaleBoolArray::update(Space& home, ScaleBoolArray& sba) {
00068 int n = static_cast<int>(sba._lst - sba._fst);
00069 if (n > 0) {
00070 _fst = home.alloc<ScaleBool>(n);
00071 _lst = _fst+n;
00072 for (int i=n; i--; ) {
00073 _fst[i].a = sba._fst[i].a;
00074 _fst[i].x.update(home,sba._fst[i].x);
00075 }
00076 } else {
00077 _fst = _lst = NULL;
00078 }
00079 }
00080 forceinline ScaleBool*
00081 ScaleBoolArray::fst(void) const {
00082 return _fst;
00083 }
00084 forceinline ScaleBool*
00085 ScaleBoolArray::lst(void) const {
00086 return _lst;
00087 }
00088 forceinline void
00089 ScaleBoolArray::fst(ScaleBool* f) {
00090 _fst = f;
00091 }
00092 forceinline void
00093 ScaleBoolArray::lst(ScaleBool* l) {
00094 _lst = l;
00095 }
00096 forceinline bool
00097 ScaleBoolArray::empty(void) const {
00098 return _fst == _lst;
00099 }
00100 forceinline int
00101 ScaleBoolArray::size(void) const {
00102 return static_cast<int>(_lst - _fst);
00103 }
00104 forceinline bool
00105 ScaleBoolArray::ScaleDec::operator ()(const ScaleBool& x,
00106 const ScaleBool& y) {
00107 return x.a > y.a;
00108 }
00109
00110 inline void
00111 ScaleBoolArray::sort(void) {
00112 ScaleDec scale_dec;
00113 Support::quicksort<ScaleBool,ScaleDec>(fst(), size(), scale_dec);
00114 }
00115
00116
00117
00118
00119
00120
00121 forceinline
00122 EmptyScaleBoolArray::EmptyScaleBoolArray(void) {}
00123 forceinline
00124 EmptyScaleBoolArray::EmptyScaleBoolArray(Space&, int) {}
00125 forceinline void
00126 EmptyScaleBoolArray::subscribe(Space&, Propagator&) {}
00127 forceinline void
00128 EmptyScaleBoolArray::cancel(Space&, Propagator&) {}
00129 forceinline void
00130 EmptyScaleBoolArray::reschedule(Space&, Propagator&) {}
00131 forceinline void
00132 EmptyScaleBoolArray::update(Space&, EmptyScaleBoolArray&) {}
00133 forceinline ScaleBool*
00134 EmptyScaleBoolArray::fst(void) const { return NULL; }
00135 forceinline ScaleBool*
00136 EmptyScaleBoolArray::lst(void) const { return NULL; }
00137 forceinline void
00138 EmptyScaleBoolArray::fst(ScaleBool*) {}
00139 forceinline void
00140 EmptyScaleBoolArray::lst(ScaleBool*) {}
00141 forceinline bool
00142 EmptyScaleBoolArray::empty(void) const { return true; }
00143 forceinline int
00144 EmptyScaleBoolArray::size(void) const { return 0; }
00145 forceinline void
00146 EmptyScaleBoolArray::sort(void) {}
00147
00148
00149
00150
00151
00152
00153
00154 template<class SBAP, class SBAN, class VX, PropCond pcx>
00155 forceinline
00156 LinBoolScale<SBAP,SBAN,VX,pcx>::LinBoolScale(Home home,
00157 SBAP& p0, SBAN& n0,
00158 VX x0, int c0)
00159 : Propagator(home), p(p0), n(n0), x(x0), c(c0) {
00160 x.subscribe(home,*this,pcx);
00161 p.subscribe(home,*this);
00162 n.subscribe(home,*this);
00163 }
00164
00165 template<class SBAP, class SBAN, class VX, PropCond pcx>
00166 PropCost
00167 LinBoolScale<SBAP,SBAN,VX,pcx>::cost(const Space&,
00168 const ModEventDelta&) const {
00169 return PropCost::linear(PropCost::LO, p.size() + n.size());
00170 }
00171
00172 template<class SBAP, class SBAN, class VX, PropCond pcx>
00173 void
00174 LinBoolScale<SBAP,SBAN,VX,pcx>::reschedule(Space& home) {
00175 x.reschedule(home,*this,pcx);
00176 p.reschedule(home,*this);
00177 n.reschedule(home,*this);
00178 }
00179
00180 template<class SBAP, class SBAN, class VX, PropCond pcx>
00181 forceinline size_t
00182 LinBoolScale<SBAP,SBAN,VX,pcx>::dispose(Space& home) {
00183 x.cancel(home,*this,pcx);
00184 p.cancel(home,*this);
00185 n.cancel(home,*this);
00186 (void) Propagator::dispose(home);
00187 return sizeof(*this);
00188 }
00189
00190 template<class SBAP, class SBAN, class VX, PropCond pcx>
00191 forceinline
00192 LinBoolScale<SBAP,SBAN,VX,pcx>::LinBoolScale(Space& home,
00193 Propagator& pr,
00194 SBAP& p0, SBAN& n0,
00195 VX x0, int c0)
00196 : Propagator(home,pr), c(c0) {
00197 x.update(home,x0);
00198 p.update(home,p0);
00199 n.update(home,n0);
00200 }
00201
00202
00203
00204
00205
00206
00207 template<class SBAP, class SBAN, class VX>
00208 forceinline
00209 EqBoolScale<SBAP,SBAN,VX>::EqBoolScale(Home home,
00210 SBAP& p, SBAN& n,
00211 VX x, int c)
00212 : LinBoolScale<SBAP,SBAN,VX,PC_INT_BND>(home,p,n,x,c) {}
00213
00214 template<class SBAP, class SBAN, class VX>
00215 forceinline
00216 EqBoolScale<SBAP,SBAN,VX>::EqBoolScale(Space& home,
00217 Propagator& pr,
00218 SBAP& p, SBAN& n,
00219 VX x, int c)
00220 : LinBoolScale<SBAP,SBAN,VX,PC_INT_BND>(home,pr,p,n,x,c) {}
00221
00222 template<class SBAP, class SBAN, class VX>
00223 Actor*
00224 EqBoolScale<SBAP,SBAN,VX>::copy(Space& home) {
00225 if (p.empty()) {
00226 EmptyScaleBoolArray ep;
00227 if (x.assigned()) {
00228 ZeroIntView z;
00229 return new (home) EqBoolScale<EmptyScaleBoolArray,SBAN,ZeroIntView>
00230 (home,*this,ep,n,z,c+x.val());
00231 } else {
00232 return new (home) EqBoolScale<EmptyScaleBoolArray,SBAN,VX>
00233 (home,*this,ep,n,x,c);
00234 }
00235 } else if (n.empty()) {
00236 EmptyScaleBoolArray en;
00237 if (x.assigned()) {
00238 ZeroIntView z;
00239 return new (home) EqBoolScale<SBAP,EmptyScaleBoolArray,ZeroIntView>
00240 (home,*this,p,en,z,c+x.val());
00241 } else {
00242 return new (home) EqBoolScale<SBAP,EmptyScaleBoolArray,VX>
00243 (home,*this,p,en,x,c);
00244 }
00245 } else {
00246 return new (home) EqBoolScale<SBAP,SBAN,VX>(home,*this,p,n,x,c);
00247 }
00248 }
00249
00250 template<class SBAP, class SBAN, class VX>
00251 ExecStatus
00252 EqBoolScale<SBAP,SBAN,VX>::propagate(Space& home, const ModEventDelta& med) {
00253 int sl_p = 0;
00254 int su_n = 0;
00255 if (BoolView::me(med) == ME_BOOL_VAL) {
00256
00257 {
00258
00259 ScaleBool* f = p.fst();
00260 ScaleBool* l = p.lst();
00261 while ((f < l) && f->x.none()) {
00262 su_n += f->a; f++;
00263 }
00264
00265 ScaleBool* t = f;
00266 while (f < l) {
00267 if (f->x.one()) {
00268 c -= f->a;
00269 } else if (f->x.none()) {
00270 su_n += f->a; *t = *f; t++;
00271 }
00272 f++;
00273 }
00274 p.lst(t);
00275 }
00276
00277 {
00278
00279 ScaleBool* f = n.fst();
00280 ScaleBool* l = n.lst();
00281 while ((f < l) && f->x.none()) {
00282 sl_p += f->a; f++;
00283 }
00284
00285 ScaleBool* t = f;
00286 while (f < l) {
00287 if (f->x.one()) {
00288 c += f->a;
00289 } else if (f->x.none()) {
00290 sl_p += f->a; *t = *f; t++;
00291 }
00292 f++;
00293 }
00294 n.lst(t);
00295 }
00296 } else {
00297 for (ScaleBool* f=p.fst(); f<p.lst(); f++)
00298 su_n += f->a;
00299 for (ScaleBool* f=n.fst(); f<n.lst(); f++)
00300 sl_p += f->a;
00301 }
00302
00303 if (p.empty() && n.empty()) {
00304 GECODE_ME_CHECK(x.eq(home,-c));
00305 return home.ES_SUBSUMED(*this);
00306 }
00307
00308 sl_p += x.max() + c;
00309 su_n -= x.min() + c;
00310
00311 const int MOD_SL = 1 << 0;
00312 const int MOD_SU = 1 << 1;
00313
00314 int mod = MOD_SL | MOD_SU;
00315
00316 do {
00317 if ((mod & MOD_SL) != 0) {
00318 mod -= MOD_SL;
00319
00320 {
00321 ScaleBool* f=p.fst();
00322 for (ScaleBool* l=p.lst(); (f < l) && (f->a > sl_p); f++) {
00323 GECODE_ME_CHECK(f->x.zero_none(home));
00324 su_n -= f->a;
00325 }
00326 if (f > p.fst()) {
00327 p.fst(f); mod |= MOD_SU;
00328 }
00329 }
00330
00331 {
00332 ScaleBool* f=n.fst();
00333 for (ScaleBool* l=n.lst(); (f < l) && (f->a > sl_p); f++) {
00334 GECODE_ME_CHECK(f->x.one_none(home)); c += f->a;
00335 su_n -= f->a;
00336 }
00337 if (f > n.fst()) {
00338 n.fst(f); mod |= MOD_SU;
00339 }
00340 }
00341
00342 {
00343 const int x_min = x.min();
00344 ModEvent me = x.gq(home,x.max() - sl_p);
00345 if (me_failed(me))
00346 return ES_FAILED;
00347 if (me_modified(me)) {
00348 su_n -= x.min() - x_min;
00349 mod |= MOD_SU;
00350 }
00351 }
00352 }
00353 if ((mod & MOD_SU) != 0) {
00354 mod -= MOD_SU;
00355
00356 {
00357 ScaleBool* f=p.fst();
00358 for (ScaleBool* l=p.lst(); (f < l) && (f->a > su_n); f++) {
00359 GECODE_ME_CHECK(f->x.one_none(home)); c -= f->a;
00360 sl_p -= f->a;
00361 }
00362 if (f > p.fst()) {
00363 p.fst(f); mod |= MOD_SL;;
00364 }
00365 }
00366
00367 {
00368 ScaleBool* f=n.fst();
00369 for (ScaleBool* l=n.lst(); (f < l) && (f->a > su_n); f++) {
00370 GECODE_ME_CHECK(f->x.zero_none(home));
00371 sl_p -= f->a;
00372 }
00373 if (f > n.fst()) {
00374 n.fst(f); mod |= MOD_SL;;
00375 }
00376 }
00377
00378 {
00379 const int x_max = x.max();
00380 ModEvent me = x.lq(home,x.min() + su_n);
00381 if (me_failed(me))
00382 return ES_FAILED;
00383 if (me_modified(me)) {
00384 sl_p += x.max() - x_max;
00385 mod |= MOD_SL;;
00386 }
00387 }
00388 }
00389 } while (mod != 0);
00390
00391 return (sl_p == -su_n) ? home.ES_SUBSUMED(*this) : ES_FIX;
00392 }
00393
00394
00395
00396 template<class SBAP, class SBAN, class VX>
00397 ExecStatus
00398 EqBoolScale<SBAP,SBAN,VX>::post(Home home,
00399 SBAP& p, SBAN& n, VX x, int c) {
00400 p.sort(); n.sort();
00401 if (p.empty()) {
00402 EmptyScaleBoolArray ep;
00403 (void) new (home) EqBoolScale<EmptyScaleBoolArray,SBAN,VX>
00404 (home,ep,n,x,c);
00405 } else if (n.empty()) {
00406 EmptyScaleBoolArray en;
00407 (void) new (home) EqBoolScale<SBAP,EmptyScaleBoolArray,VX>
00408 (home,p,en,x,c);
00409 } else {
00410 (void) new (home) EqBoolScale<SBAP,SBAN,VX>
00411 (home,p,n,x,c);
00412 }
00413 return ES_OK;
00414 }
00415
00416
00417
00418
00419
00420
00421
00422 template<class SBAP, class SBAN, class VX>
00423 forceinline
00424 LqBoolScale<SBAP,SBAN,VX>::LqBoolScale(Home home,
00425 SBAP& p, SBAN& n,
00426 VX x, int c)
00427 : LinBoolScale<SBAP,SBAN,VX,PC_INT_BND>(home,p,n,x,c) {}
00428
00429 template<class SBAP, class SBAN, class VX>
00430 forceinline
00431 LqBoolScale<SBAP,SBAN,VX>::LqBoolScale(Space& home,
00432 Propagator& pr,
00433 SBAP& p, SBAN& n,
00434 VX x, int c)
00435 : LinBoolScale<SBAP,SBAN,VX,PC_INT_BND>(home,pr,p,n,x,c) {}
00436
00437 template<class SBAP, class SBAN, class VX>
00438 Actor*
00439 LqBoolScale<SBAP,SBAN,VX>::copy(Space& home) {
00440 if (p.empty()) {
00441 EmptyScaleBoolArray ep;
00442 if (x.assigned()) {
00443 ZeroIntView z;
00444 return new (home) LqBoolScale<EmptyScaleBoolArray,SBAN,ZeroIntView>
00445 (home,*this,ep,n,z,c+x.val());
00446 } else {
00447 return new (home) LqBoolScale<EmptyScaleBoolArray,SBAN,VX>
00448 (home,*this,ep,n,x,c);
00449 }
00450 } else if (n.empty()) {
00451 EmptyScaleBoolArray en;
00452 if (x.assigned()) {
00453 ZeroIntView z;
00454 return new (home) LqBoolScale<SBAP,EmptyScaleBoolArray,ZeroIntView>
00455 (home,*this,p,en,z,c+x.val());
00456 } else {
00457 return new (home) LqBoolScale<SBAP,EmptyScaleBoolArray,VX>
00458 (home,*this,p,en,x,c);
00459 }
00460 } else {
00461 return new (home) LqBoolScale<SBAP,SBAN,VX>(home,*this,p,n,x,c);
00462 }
00463 }
00464
00465 template<class SBAP, class SBAN, class VX>
00466 ExecStatus
00467 LqBoolScale<SBAP,SBAN,VX>::propagate(Space& home, const ModEventDelta& med) {
00468 int sl = 0;
00469 if (BoolView::me(med) == ME_BOOL_VAL) {
00470
00471 {
00472
00473 ScaleBool* f = p.fst();
00474 ScaleBool* l = p.lst();
00475 while ((f < l) && f->x.none())
00476 f++;
00477
00478 ScaleBool* t = f;
00479 while (f < l) {
00480 if (f->x.one()) {
00481 c -= f->a;
00482 } else if (f->x.none()) {
00483 *t = *f; t++;
00484 }
00485 f++;
00486 }
00487 p.lst(t);
00488 }
00489
00490 {
00491
00492 ScaleBool* f = n.fst();
00493 ScaleBool* l = n.lst();
00494 while ((f < l) && f->x.none()) {
00495 sl += f->a; f++;
00496 }
00497
00498 ScaleBool* t = f;
00499 while (f < l) {
00500 if (f->x.one()) {
00501 c += f->a;
00502 } else if (f->x.none()) {
00503 sl += f->a; *t = *f; t++;
00504 }
00505 f++;
00506 }
00507 n.lst(t);
00508 }
00509 } else {
00510 for (ScaleBool* f=n.fst(); f<n.lst(); f++)
00511 sl += f->a;
00512 }
00513
00514 sl += x.max() + c;
00515
00516
00517 {
00518 ScaleBool* f=p.fst();
00519 for (ScaleBool* l=p.lst(); (f < l) && (f->a > sl); f++)
00520 GECODE_ME_CHECK(f->x.zero_none(home));
00521 p.fst(f);
00522 }
00523
00524 {
00525 ScaleBool* f=n.fst();
00526 for (ScaleBool* l=n.lst(); (f < l) && (f->a > sl); f++) {
00527 c += f->a;
00528 GECODE_ME_CHECK(f->x.one_none(home));
00529 }
00530 n.fst(f);
00531 }
00532 ExecStatus es = ES_FIX;
00533
00534 {
00535 const int slx = x.max() - sl;
00536 ModEvent me = x.gq(home,slx);
00537 if (me_failed(me))
00538 return ES_FAILED;
00539 if (me_modified(me) && (slx != x.min()))
00540 es = ES_NOFIX;
00541 }
00542
00543 if (p.empty() && n.empty())
00544 return home.ES_SUBSUMED(*this);
00545
00546 return es;
00547 }
00548
00549
00550
00551 template<class SBAP, class SBAN, class VX>
00552 ExecStatus
00553 LqBoolScale<SBAP,SBAN,VX>::post(Home home,
00554 SBAP& p, SBAN& n, VX x, int c) {
00555 p.sort(); n.sort();
00556 if (p.empty()) {
00557 EmptyScaleBoolArray ep;
00558 (void) new (home) LqBoolScale<EmptyScaleBoolArray,SBAN,VX>
00559 (home,ep,n,x,c);
00560 } else if (n.empty()) {
00561 EmptyScaleBoolArray en;
00562 (void) new (home) LqBoolScale<SBAP,EmptyScaleBoolArray,VX>
00563 (home,p,en,x,c);
00564 } else {
00565 (void) new (home) LqBoolScale<SBAP,SBAN,VX>
00566 (home,p,n,x,c);
00567 }
00568 return ES_OK;
00569 }
00570
00571
00572
00573
00574
00575
00576 template<class SBAP, class SBAN, class VX>
00577 forceinline
00578 NqBoolScale<SBAP,SBAN,VX>::NqBoolScale(Home home,
00579 SBAP& p, SBAN& n,
00580 VX x, int c)
00581 : LinBoolScale<SBAP,SBAN,VX,PC_INT_VAL>(home,p,n,x,c) {}
00582
00583 template<class SBAP, class SBAN, class VX>
00584 forceinline
00585 NqBoolScale<SBAP,SBAN,VX>::NqBoolScale(Space& home,
00586 Propagator& pr,
00587 SBAP& p, SBAN& n,
00588 VX x, int c)
00589 : LinBoolScale<SBAP,SBAN,VX,PC_INT_VAL>(home,pr,p,n,x,c) {}
00590
00591 template<class SBAP, class SBAN, class VX>
00592 Actor*
00593 NqBoolScale<SBAP,SBAN,VX>::copy(Space& home) {
00594 if (p.empty()) {
00595 EmptyScaleBoolArray ep;
00596 if (x.assigned()) {
00597 ZeroIntView z;
00598 return new (home) NqBoolScale<EmptyScaleBoolArray,SBAN,ZeroIntView>
00599 (home,*this,ep,n,z,c+x.val());
00600 } else {
00601 return new (home) NqBoolScale<EmptyScaleBoolArray,SBAN,VX>
00602 (home,*this,ep,n,x,c);
00603 }
00604 } else if (n.empty()) {
00605 EmptyScaleBoolArray en;
00606 if (x.assigned()) {
00607 ZeroIntView z;
00608 return new (home) NqBoolScale<SBAP,EmptyScaleBoolArray,ZeroIntView>
00609 (home,*this,p,en,z,c+x.val());
00610 } else {
00611 return new (home) NqBoolScale<SBAP,EmptyScaleBoolArray,VX>
00612 (home,*this,p,en,x,c);
00613 }
00614 } else {
00615 return new (home) NqBoolScale<SBAP,SBAN,VX>(home,*this,p,n,x,c);
00616 }
00617 }
00618
00619 template<class SBAP, class SBAN, class VX>
00620 ExecStatus
00621 NqBoolScale<SBAP,SBAN,VX>::propagate(Space& home, const ModEventDelta& med) {
00622 if (BoolView::me(med) == ME_BOOL_VAL) {
00623
00624 {
00625 ScaleBool* f = p.fst();
00626 ScaleBool* t = f;
00627 ScaleBool* l = p.lst();
00628 while (f < l) {
00629 if (f->x.one()) {
00630 c -= f->a; *f = *(t++);
00631 } else if (f->x.zero()) {
00632 *f = *(t++);
00633 }
00634 f++;
00635 }
00636 p.fst(t);
00637 }
00638
00639 {
00640 ScaleBool* f = n.fst();
00641 ScaleBool* t = f;
00642 ScaleBool* l = n.lst();
00643 while (f < l) {
00644 if (f->x.one()) {
00645 c += f->a; *f = *(t++);
00646 } else if (f->x.zero()) {
00647 *f = *(t++);
00648 }
00649 f++;
00650 }
00651 n.fst(t);
00652 }
00653 }
00654
00655 if (p.empty() && n.empty()) {
00656 GECODE_ME_CHECK(x.nq(home,-c));
00657 return home.ES_SUBSUMED(*this);
00658 }
00659
00660 if (x.assigned()) {
00661 int r = x.val()+c;
00662 if (p.empty() && (n.size() == 1)) {
00663 if (r == -n.fst()->a) {
00664 GECODE_ME_CHECK(n.fst()->x.zero_none(home));
00665 } else if (r == 0) {
00666 GECODE_ME_CHECK(n.fst()->x.one_none(home));
00667 }
00668 return home.ES_SUBSUMED(*this);
00669 }
00670 if ((p.size() == 1) && n.empty()) {
00671 if (r == p.fst()->a) {
00672 GECODE_ME_CHECK(p.fst()->x.zero_none(home));
00673 } else if (r == 0) {
00674 GECODE_ME_CHECK(p.fst()->x.one_none(home));
00675 }
00676 return home.ES_SUBSUMED(*this);
00677 }
00678 }
00679 return ES_FIX;
00680 }
00681
00682
00683
00684 template<class SBAP, class SBAN, class VX>
00685 ExecStatus
00686 NqBoolScale<SBAP,SBAN,VX>::post(Home home,
00687 SBAP& p, SBAN& n, VX x, int c) {
00688 if (p.empty()) {
00689 EmptyScaleBoolArray ep;
00690 (void) new (home) NqBoolScale<EmptyScaleBoolArray,SBAN,VX>
00691 (home,ep,n,x,c);
00692 } else if (n.empty()) {
00693 EmptyScaleBoolArray en;
00694 (void) new (home) NqBoolScale<SBAP,EmptyScaleBoolArray,VX>
00695 (home,p,en,x,c);
00696 } else {
00697 (void) new (home) NqBoolScale<SBAP,SBAN,VX>
00698 (home,p,n,x,c);
00699 }
00700 return ES_OK;
00701 }
00702
00703 }}}
00704
00705
00706