bool-scale.hpp
Go to the documentation of this file.
00001 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */ 00002 /* 00003 * Main authors: 00004 * Christian Schulte <schulte@gecode.org> 00005 * 00006 * Copyright: 00007 * Christian Schulte, 2006 00008 * 00009 * Last modified: 00010 * $Date: 2010-03-03 17:32:21 +0100 (Wed, 03 Mar 2010) $ by $Author: schulte $ 00011 * $Revision: 10364 $ 00012 * 00013 * This file is part of Gecode, the generic constraint 00014 * development environment: 00015 * http://www.gecode.org 00016 * 00017 * Permission is hereby granted, free of charge, to any person obtaining 00018 * a copy of this software and associated documentation files (the 00019 * "Software"), to deal in the Software without restriction, including 00020 * without limitation the rights to use, copy, modify, merge, publish, 00021 * distribute, sublicense, and/or sell copies of the Software, and to 00022 * permit persons to whom the Software is furnished to do so, subject to 00023 * the following conditions: 00024 * 00025 * The above copyright notice and this permission notice shall be 00026 * included in all copies or substantial portions of the Software. 00027 * 00028 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, 00029 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF 00030 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND 00031 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE 00032 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION 00033 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION 00034 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. 00035 * 00036 */ 00037 00038 namespace Gecode { namespace Int { namespace Linear { 00039 00040 /* 00041 * Array of scale Boolean views 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 * Empty array of scale Boolean views 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 * Base-class for Boolean constraints with coefficients 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 * Boolean equality with coefficients 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; // Lower bound, computed positive 00243 int su_n = 0; // Upper bound, computed negative 00244 if (BoolView::me(med) == ME_BOOL_VAL) { 00245 // Eliminate assigned positive views while keeping order 00246 { 00247 // Skip not assigned views 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 // Copy unassigned views to t 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 // Eliminate assigned negative views while keeping order 00266 { 00267 // Skip not assigned views 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 // Copy unassigned views to t 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 // Propagate lower bound for positive Boolean views 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 // Propagate lower bound for negative Boolean views 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 // Propagate lower bound for integer view 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 // Propagate upper bound for positive Boolean views 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 // Propagate upper bound for negative Boolean views 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 // Propagate upper bound for integer view 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 * Boolean inequality with coefficients 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 // Eliminate assigned positive views while keeping order 00460 { 00461 // Skip not assigned views 00462 ScaleBool* f = p.fst(); 00463 ScaleBool* l = p.lst(); 00464 while ((f < l) && f->x.none()) 00465 f++; 00466 // Copy unassigned views to t 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 // Eliminate assigned negative views while keeping order 00479 { 00480 // Skip not assigned views 00481 ScaleBool* f = n.fst(); 00482 ScaleBool* l = n.lst(); 00483 while ((f < l) && f->x.none()) { 00484 sl += f->a; f++; 00485 } 00486 // Copy unassigned views to t 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 // Propagate upper bound for positive Boolean views 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 // Propagate lower bound for negative Boolean views 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 // Propagate lower bound for integer view 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 * Boolean disequality with coefficients 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 // Eliminate assigned positive views 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 // Eliminate assigned negative views 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 // STATISTICS: int-prop 00695