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