or.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, 2004 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 Bool { 00039 00041 template<class BV> 00042 class OrTrueSubsumed : public BoolBinary<BV,BV> { 00043 protected: 00044 using BoolBinary<BV,BV>::x0; 00045 using BoolBinary<BV,BV>::x1; 00047 OrTrueSubsumed(Space& home, bool share, OrTrueSubsumed& p); 00049 static ExecStatus post(Home home, BV b0, BV b1); 00050 public: 00052 OrTrueSubsumed(Home home, BV b0, BV b1); 00054 OrTrueSubsumed(Space& home, bool share, Propagator& p, 00055 BV b0, BV b1); 00057 virtual Actor* copy(Space& home, bool share); 00059 virtual ExecStatus propagate(Space& home, const ModEventDelta& med); 00060 }; 00061 00062 template<class BV> 00063 forceinline 00064 OrTrueSubsumed<BV>::OrTrueSubsumed 00065 (Home home, BV b0, BV b1) 00066 : BoolBinary<BV,BV>(home,b0,b1) {} 00067 00068 template<class BV> 00069 forceinline ExecStatus 00070 OrTrueSubsumed<BV>::post(Home home, BV b0, BV b1) { 00071 (void) new (home) OrTrueSubsumed(home,b0,b1); 00072 return ES_OK; 00073 } 00074 00075 template<class BV> 00076 forceinline 00077 OrTrueSubsumed<BV>::OrTrueSubsumed 00078 (Space& home, bool share, OrTrueSubsumed<BV>& p) 00079 : BoolBinary<BV,BV>(home,share,p) {} 00080 00081 template<class BV> 00082 forceinline 00083 OrTrueSubsumed<BV>::OrTrueSubsumed(Space& home, bool share, Propagator& p, 00084 BV b0, BV b1) 00085 : BoolBinary<BV,BV>(home,share,p,b0,b1) {} 00086 00087 template<class BV> 00088 Actor* 00089 OrTrueSubsumed<BV>::copy(Space& home, bool share) { 00090 return new (home) OrTrueSubsumed<BV>(home,share,*this); 00091 } 00092 00093 template<class BV> 00094 ExecStatus 00095 OrTrueSubsumed<BV>::propagate(Space& home, const ModEventDelta&) { 00096 return home.ES_SUBSUMED(*this); 00097 } 00098 00099 00100 /* 00101 * Binary Boolean disjunction propagator (true) 00102 * 00103 */ 00104 00105 template<class BVA, class BVB> 00106 forceinline 00107 BinOrTrue<BVA,BVB>::BinOrTrue(Home home, BVA b0, BVB b1) 00108 : BoolBinary<BVA,BVB>(home,b0,b1) {} 00109 00110 template<class BVA, class BVB> 00111 forceinline 00112 BinOrTrue<BVA,BVB>::BinOrTrue(Space& home, bool share, BinOrTrue<BVA,BVB>& p) 00113 : BoolBinary<BVA,BVB>(home,share,p) {} 00114 00115 template<class BVA, class BVB> 00116 forceinline 00117 BinOrTrue<BVA,BVB>::BinOrTrue(Space& home, bool share, Propagator& p, 00118 BVA b0, BVB b1) 00119 : BoolBinary<BVA,BVB>(home,share,p,b0,b1) {} 00120 00121 template<class BVA, class BVB> 00122 Actor* 00123 BinOrTrue<BVA,BVB>::copy(Space& home, bool share) { 00124 return new (home) BinOrTrue<BVA,BVB>(home,share,*this); 00125 } 00126 00127 template<class BVA, class BVB> 00128 inline ExecStatus 00129 BinOrTrue<BVA,BVB>::post(Home home, BVA b0, BVB b1) { 00130 switch (bool_test(b0,b1)) { 00131 case BT_SAME: 00132 GECODE_ME_CHECK(b0.one(home)); 00133 break; 00134 case BT_COMP: 00135 break; 00136 case BT_NONE: 00137 if (b0.zero()) { 00138 GECODE_ME_CHECK(b1.one(home)); 00139 } else if (b1.zero()) { 00140 GECODE_ME_CHECK(b0.one(home)); 00141 } else if (!b0.one() && !b1.one()) { 00142 (void) new (home) BinOrTrue<BVA,BVB>(home,b0,b1); 00143 } 00144 break; 00145 default: GECODE_NEVER; 00146 } 00147 return ES_OK; 00148 } 00149 00150 template<class BVA, class BVB> 00151 ExecStatus 00152 BinOrTrue<BVA,BVB>::propagate(Space& home, const ModEventDelta&) { 00153 #define GECODE_INT_STATUS(S0,S1) \ 00154 ((BVA::S0<<(1*BVA::BITS))|(BVB::S1<<(0*BVB::BITS))) 00155 switch ((x0.status() << (1*BVA::BITS)) | (x1.status() << (0*BVB::BITS))) { 00156 case GECODE_INT_STATUS(NONE,NONE): 00157 GECODE_NEVER; 00158 case GECODE_INT_STATUS(NONE,ZERO): 00159 GECODE_ME_CHECK(x0.one_none(home)); break; 00160 case GECODE_INT_STATUS(NONE,ONE): 00161 break; 00162 case GECODE_INT_STATUS(ZERO,NONE): 00163 GECODE_ME_CHECK(x1.one_none(home)); break; 00164 case GECODE_INT_STATUS(ZERO,ZERO): 00165 return ES_FAILED; 00166 case GECODE_INT_STATUS(ZERO,ONE): 00167 case GECODE_INT_STATUS(ONE,NONE): 00168 case GECODE_INT_STATUS(ONE,ZERO): 00169 case GECODE_INT_STATUS(ONE,ONE): 00170 break; 00171 default: 00172 GECODE_NEVER; 00173 } 00174 return home.ES_SUBSUMED(*this); 00175 #undef GECODE_INT_STATUS 00176 } 00177 00178 /* 00179 * Boolean disjunction propagator (true) 00180 * 00181 */ 00182 00183 template<class BV> 00184 forceinline 00185 TerOrTrue<BV>::TerOrTrue(Home home, BV b0, BV b1, BV b2) 00186 : BoolBinary<BV,BV>(home,b0,b1), x2(b2) {} 00187 00188 template<class BV> 00189 forceinline size_t 00190 TerOrTrue<BV>::dispose(Space& home) { 00191 (void) BoolBinary<BV,BV>::dispose(home); 00192 return sizeof(*this); 00193 } 00194 00195 template<class BV> 00196 forceinline 00197 TerOrTrue<BV>::TerOrTrue(Space& home, bool share, TerOrTrue<BV>& p) 00198 : BoolBinary<BV,BV>(home,share,p) { 00199 x2.update(home,share,p.x2); 00200 } 00201 00202 template<class BV> 00203 forceinline 00204 TerOrTrue<BV>::TerOrTrue(Space& home, bool share, Propagator& p, 00205 BV b0, BV b1, BV b2) 00206 : BoolBinary<BV,BV>(home,share,p,b0,b1) { 00207 x2.update(home,share,b2); 00208 } 00209 00210 template<class BV> 00211 Actor* 00212 TerOrTrue<BV>::copy(Space& home, bool share) { 00213 assert(x0.none() && x1.none()); 00214 if (x2.one()) 00215 return new (home) OrTrueSubsumed<BV>(home,share,*this,x0,x1); 00216 else if (x2.zero()) 00217 return new (home) BinOrTrue<BV,BV>(home,share,*this,x0,x1); 00218 else 00219 return new (home) TerOrTrue<BV>(home,share,*this); 00220 } 00221 00222 template<class BV> 00223 forceinline ExecStatus 00224 TerOrTrue<BV>::post(Home home, BV b0, BV b1, BV b2) { 00225 (void) new (home) TerOrTrue<BV>(home,b0,b1,b2); 00226 return ES_OK; 00227 } 00228 00229 template<class BV> 00230 ExecStatus 00231 TerOrTrue<BV>::propagate(Space& home, const ModEventDelta&) { 00232 #define GECODE_INT_STATUS(S0,S1,S2) \ 00233 ((BV::S0<<(2*BV::BITS))|(BV::S1<<(1*BV::BITS))|(BV::S2<<(0*BV::BITS))) 00234 switch ((x0.status() << (2*BV::BITS)) | (x1.status() << (1*BV::BITS)) | 00235 (x2.status() << (0*BV::BITS))) { 00236 case GECODE_INT_STATUS(NONE,NONE,NONE): 00237 case GECODE_INT_STATUS(NONE,NONE,ZERO): 00238 case GECODE_INT_STATUS(NONE,NONE,ONE): 00239 GECODE_NEVER; 00240 case GECODE_INT_STATUS(NONE,ZERO,NONE): 00241 std::swap(x1,x2); x1.subscribe(home,*this,PC_BOOL_VAL); 00242 return ES_FIX; 00243 case GECODE_INT_STATUS(NONE,ZERO,ZERO): 00244 GECODE_ME_CHECK(x0.one_none(home)); break; 00245 case GECODE_INT_STATUS(NONE,ZERO,ONE): 00246 case GECODE_INT_STATUS(NONE,ONE,NONE): 00247 case GECODE_INT_STATUS(NONE,ONE,ZERO): 00248 case GECODE_INT_STATUS(NONE,ONE,ONE): 00249 break; 00250 case GECODE_INT_STATUS(ZERO,NONE,NONE): 00251 std::swap(x0,x2); x0.subscribe(home,*this,PC_BOOL_VAL); 00252 return ES_FIX; 00253 case GECODE_INT_STATUS(ZERO,NONE,ZERO): 00254 GECODE_ME_CHECK(x1.one_none(home)); break; 00255 case GECODE_INT_STATUS(ZERO,NONE,ONE): 00256 break; 00257 case GECODE_INT_STATUS(ZERO,ZERO,NONE): 00258 GECODE_ME_CHECK(x2.one_none(home)); break; 00259 case GECODE_INT_STATUS(ZERO,ZERO,ZERO): 00260 return ES_FAILED; 00261 case GECODE_INT_STATUS(ZERO,ZERO,ONE): 00262 case GECODE_INT_STATUS(ZERO,ONE,NONE): 00263 case GECODE_INT_STATUS(ZERO,ONE,ZERO): 00264 case GECODE_INT_STATUS(ZERO,ONE,ONE): 00265 case GECODE_INT_STATUS(ONE,NONE,NONE): 00266 case GECODE_INT_STATUS(ONE,NONE,ZERO): 00267 case GECODE_INT_STATUS(ONE,NONE,ONE): 00268 case GECODE_INT_STATUS(ONE,ZERO,NONE): 00269 case GECODE_INT_STATUS(ONE,ZERO,ZERO): 00270 case GECODE_INT_STATUS(ONE,ZERO,ONE): 00271 case GECODE_INT_STATUS(ONE,ONE,NONE): 00272 case GECODE_INT_STATUS(ONE,ONE,ZERO): 00273 case GECODE_INT_STATUS(ONE,ONE,ONE): 00274 break; 00275 default: 00276 GECODE_NEVER; 00277 } 00278 return home.ES_SUBSUMED(*this); 00279 #undef GECODE_INT_STATUS 00280 } 00281 00282 /* 00283 * Boolean disjunction propagator (true) 00284 * 00285 */ 00286 00287 template<class BV> 00288 forceinline 00289 QuadOrTrue<BV>::QuadOrTrue(Home home, BV b0, BV b1, BV b2, BV b3) 00290 : BoolBinary<BV,BV>(home,b0,b1), x2(b2), x3(b3) {} 00291 00292 template<class BV> 00293 forceinline size_t 00294 QuadOrTrue<BV>::dispose(Space& home) { 00295 (void) BoolBinary<BV,BV>::dispose(home); 00296 return sizeof(*this); 00297 } 00298 00299 template<class BV> 00300 forceinline 00301 QuadOrTrue<BV>::QuadOrTrue(Space& home, bool share, QuadOrTrue<BV>& p) 00302 : BoolBinary<BV,BV>(home,share,p) { 00303 x2.update(home,share,p.x2); 00304 x3.update(home,share,p.x3); 00305 } 00306 00307 template<class BV> 00308 forceinline 00309 QuadOrTrue<BV>::QuadOrTrue(Space& home, bool share, Propagator& p, 00310 BV b0, BV b1, BV b2, BV b3) 00311 : BoolBinary<BV,BV>(home,share,p,b0,b1) { 00312 x2.update(home,share,b2); 00313 x3.update(home,share,b3); 00314 } 00315 00316 template<class BV> 00317 Actor* 00318 QuadOrTrue<BV>::copy(Space& home, bool share) { 00319 assert(x0.none() && x1.none()); 00320 if (x2.one() || x3.one()) 00321 return new (home) OrTrueSubsumed<BV>(home,share,*this,x0,x1); 00322 else if (x2.zero() && x3.zero()) 00323 return new (home) BinOrTrue<BV,BV>(home,share,*this,x0,x1); 00324 else if (x2.zero()) 00325 return new (home) TerOrTrue<BV>(home,share,*this,x0,x1,x3); 00326 else if (x3.zero()) 00327 return new (home) TerOrTrue<BV>(home,share,*this,x0,x1,x2); 00328 else 00329 return new (home) QuadOrTrue<BV>(home,share,*this); 00330 } 00331 00332 template<class BV> 00333 forceinline ExecStatus 00334 QuadOrTrue<BV>::post(Home home, BV b0, BV b1, BV b2, BV b3) { 00335 (void) new (home) QuadOrTrue<BV>(home,b0,b1,b2,b3); 00336 return ES_OK; 00337 } 00338 00339 template<class BV> 00340 ExecStatus 00341 QuadOrTrue<BV>::propagate(Space& home, const ModEventDelta&) { 00342 #define GECODE_INT_STATUS(S0,S1,S2,S3) \ 00343 ((BV::S0 << (3*BV::BITS)) | (BV::S1 << (2*BV::BITS)) | \ 00344 (BV::S2 << (1*BV::BITS)) | (BV::S3 << (0*BV::BITS))) 00345 switch ((x0.status() << (3*BV::BITS)) | (x1.status() << (2*BV::BITS)) | 00346 (x2.status() << (1*BV::BITS)) | (x3.status() << (0*BV::BITS))) { 00347 case GECODE_INT_STATUS(NONE,NONE,NONE,NONE): 00348 case GECODE_INT_STATUS(NONE,NONE,NONE,ZERO): 00349 case GECODE_INT_STATUS(NONE,NONE,NONE,ONE): 00350 case GECODE_INT_STATUS(NONE,NONE,ZERO,NONE): 00351 case GECODE_INT_STATUS(NONE,NONE,ZERO,ZERO): 00352 case GECODE_INT_STATUS(NONE,NONE,ZERO,ONE): 00353 case GECODE_INT_STATUS(NONE,NONE,ONE,NONE): 00354 case GECODE_INT_STATUS(NONE,NONE,ONE,ZERO): 00355 case GECODE_INT_STATUS(NONE,NONE,ONE,ONE): 00356 GECODE_NEVER; 00357 case GECODE_INT_STATUS(NONE,ZERO,NONE,NONE): 00358 case GECODE_INT_STATUS(NONE,ZERO,NONE,ZERO): 00359 std::swap(x1,x2); x1.subscribe(home,*this,PC_BOOL_VAL,false); 00360 return ES_FIX; 00361 case GECODE_INT_STATUS(NONE,ZERO,NONE,ONE): 00362 break; 00363 case GECODE_INT_STATUS(NONE,ZERO,ZERO,NONE): 00364 std::swap(x1,x3); x1.subscribe(home,*this,PC_BOOL_VAL,false); 00365 return ES_FIX; 00366 case GECODE_INT_STATUS(NONE,ZERO,ZERO,ZERO): 00367 GECODE_ME_CHECK(x0.one_none(home)); break; 00368 case GECODE_INT_STATUS(NONE,ZERO,ZERO,ONE): 00369 case GECODE_INT_STATUS(NONE,ZERO,ONE,NONE): 00370 case GECODE_INT_STATUS(NONE,ZERO,ONE,ZERO): 00371 case GECODE_INT_STATUS(NONE,ZERO,ONE,ONE): 00372 case GECODE_INT_STATUS(NONE,ONE,NONE,NONE): 00373 case GECODE_INT_STATUS(NONE,ONE,NONE,ZERO): 00374 case GECODE_INT_STATUS(NONE,ONE,NONE,ONE): 00375 case GECODE_INT_STATUS(NONE,ONE,ZERO,NONE): 00376 case GECODE_INT_STATUS(NONE,ONE,ZERO,ZERO): 00377 case GECODE_INT_STATUS(NONE,ONE,ZERO,ONE): 00378 case GECODE_INT_STATUS(NONE,ONE,ONE,NONE): 00379 case GECODE_INT_STATUS(NONE,ONE,ONE,ZERO): 00380 case GECODE_INT_STATUS(NONE,ONE,ONE,ONE): 00381 break; 00382 case GECODE_INT_STATUS(ZERO,NONE,NONE,NONE): 00383 case GECODE_INT_STATUS(ZERO,NONE,NONE,ZERO): 00384 std::swap(x0,x2); x0.subscribe(home,*this,PC_BOOL_VAL,false); 00385 return ES_FIX; 00386 case GECODE_INT_STATUS(ZERO,NONE,NONE,ONE): 00387 break; 00388 case GECODE_INT_STATUS(ZERO,NONE,ZERO,NONE): 00389 std::swap(x0,x3); x0.subscribe(home,*this,PC_BOOL_VAL,false); 00390 return ES_FIX; 00391 case GECODE_INT_STATUS(ZERO,NONE,ZERO,ZERO): 00392 GECODE_ME_CHECK(x1.one_none(home)); break; 00393 case GECODE_INT_STATUS(ZERO,NONE,ZERO,ONE): 00394 case GECODE_INT_STATUS(ZERO,NONE,ONE,NONE): 00395 case GECODE_INT_STATUS(ZERO,NONE,ONE,ZERO): 00396 case GECODE_INT_STATUS(ZERO,NONE,ONE,ONE): 00397 break; 00398 case GECODE_INT_STATUS(ZERO,ZERO,NONE,NONE): 00399 std::swap(x0,x2); x0.subscribe(home,*this,PC_BOOL_VAL,false); 00400 std::swap(x1,x3); x1.subscribe(home,*this,PC_BOOL_VAL,false); 00401 return ES_FIX; 00402 case GECODE_INT_STATUS(ZERO,ZERO,NONE,ZERO): 00403 GECODE_ME_CHECK(x2.one_none(home)); break; 00404 case GECODE_INT_STATUS(ZERO,ZERO,NONE,ONE): 00405 break; 00406 case GECODE_INT_STATUS(ZERO,ZERO,ZERO,NONE): 00407 GECODE_ME_CHECK(x3.one_none(home)); break; 00408 case GECODE_INT_STATUS(ZERO,ZERO,ZERO,ZERO): 00409 return ES_FAILED; 00410 case GECODE_INT_STATUS(ZERO,ZERO,ZERO,ONE): 00411 case GECODE_INT_STATUS(ZERO,ZERO,ONE,NONE): 00412 case GECODE_INT_STATUS(ZERO,ZERO,ONE,ZERO): 00413 case GECODE_INT_STATUS(ZERO,ZERO,ONE,ONE): 00414 case GECODE_INT_STATUS(ZERO,ONE,NONE,NONE): 00415 case GECODE_INT_STATUS(ZERO,ONE,NONE,ZERO): 00416 case GECODE_INT_STATUS(ZERO,ONE,NONE,ONE): 00417 case GECODE_INT_STATUS(ZERO,ONE,ZERO,NONE): 00418 case GECODE_INT_STATUS(ZERO,ONE,ZERO,ZERO): 00419 case GECODE_INT_STATUS(ZERO,ONE,ZERO,ONE): 00420 case GECODE_INT_STATUS(ZERO,ONE,ONE,NONE): 00421 case GECODE_INT_STATUS(ZERO,ONE,ONE,ZERO): 00422 case GECODE_INT_STATUS(ZERO,ONE,ONE,ONE): 00423 case GECODE_INT_STATUS(ONE,NONE,NONE,NONE): 00424 case GECODE_INT_STATUS(ONE,NONE,NONE,ZERO): 00425 case GECODE_INT_STATUS(ONE,NONE,NONE,ONE): 00426 case GECODE_INT_STATUS(ONE,NONE,ZERO,NONE): 00427 case GECODE_INT_STATUS(ONE,NONE,ZERO,ZERO): 00428 case GECODE_INT_STATUS(ONE,NONE,ZERO,ONE): 00429 case GECODE_INT_STATUS(ONE,NONE,ONE,NONE): 00430 case GECODE_INT_STATUS(ONE,NONE,ONE,ZERO): 00431 case GECODE_INT_STATUS(ONE,NONE,ONE,ONE): 00432 case GECODE_INT_STATUS(ONE,ZERO,NONE,NONE): 00433 case GECODE_INT_STATUS(ONE,ZERO,NONE,ZERO): 00434 case GECODE_INT_STATUS(ONE,ZERO,NONE,ONE): 00435 case GECODE_INT_STATUS(ONE,ZERO,ZERO,NONE): 00436 case GECODE_INT_STATUS(ONE,ZERO,ZERO,ZERO): 00437 case GECODE_INT_STATUS(ONE,ZERO,ZERO,ONE): 00438 case GECODE_INT_STATUS(ONE,ZERO,ONE,NONE): 00439 case GECODE_INT_STATUS(ONE,ZERO,ONE,ZERO): 00440 case GECODE_INT_STATUS(ONE,ZERO,ONE,ONE): 00441 case GECODE_INT_STATUS(ONE,ONE,NONE,NONE): 00442 case GECODE_INT_STATUS(ONE,ONE,NONE,ZERO): 00443 case GECODE_INT_STATUS(ONE,ONE,NONE,ONE): 00444 case GECODE_INT_STATUS(ONE,ONE,ZERO,NONE): 00445 case GECODE_INT_STATUS(ONE,ONE,ZERO,ZERO): 00446 case GECODE_INT_STATUS(ONE,ONE,ZERO,ONE): 00447 case GECODE_INT_STATUS(ONE,ONE,ONE,NONE): 00448 case GECODE_INT_STATUS(ONE,ONE,ONE,ZERO): 00449 case GECODE_INT_STATUS(ONE,ONE,ONE,ONE): 00450 break; 00451 default: 00452 GECODE_NEVER; 00453 } 00454 return home.ES_SUBSUMED(*this); 00455 #undef GECODE_INT_STATUS 00456 } 00457 00458 /* 00459 * Boolean disjunction propagator 00460 * 00461 */ 00462 00463 template<class BVA, class BVB, class BVC> 00464 forceinline 00465 Or<BVA,BVB,BVC>::Or(Home home, BVA b0, BVB b1, BVC b2) 00466 : BoolTernary<BVA,BVB,BVC>(home,b0,b1,b2) {} 00467 00468 template<class BVA, class BVB, class BVC> 00469 forceinline 00470 Or<BVA,BVB,BVC>::Or(Space& home, bool share, Or<BVA,BVB,BVC>& p) 00471 : BoolTernary<BVA,BVB,BVC>(home,share,p) {} 00472 00473 template<class BVA, class BVB, class BVC> 00474 forceinline 00475 Or<BVA,BVB,BVC>::Or(Space& home, bool share, Propagator& p, 00476 BVA b0, BVB b1, BVC b2) 00477 : BoolTernary<BVA,BVB,BVC>(home,share,p,b0,b1,b2) {} 00478 00479 template<class BVA, class BVB, class BVC> 00480 Actor* 00481 Or<BVA,BVB,BVC>::copy(Space& home, bool share) { 00482 if (x2.one()) { 00483 assert(x0.none() && x1.none()); 00484 return new (home) BinOrTrue<BVA,BVB>(home,share,*this,x0,x1); 00485 } else if (x0.zero()) { 00486 assert(x1.none() && x2.none()); 00487 return new (home) Eq<BVB,BVC>(home,share,*this,x1,x2); 00488 } else if (x1.zero()) { 00489 assert(x0.none() && x2.none()); 00490 return new (home) Eq<BVA,BVC>(home,share,*this,x0,x2); 00491 } else { 00492 return new (home) Or<BVA,BVB,BVC>(home,share,*this); 00493 } 00494 } 00495 00496 template<class BVA, class BVB, class BVC> 00497 inline ExecStatus 00498 Or<BVA,BVB,BVC>::post(Home home, BVA b0, BVB b1, BVC b2) { 00499 if (b2.zero()) { 00500 GECODE_ME_CHECK(b0.zero(home)); 00501 GECODE_ME_CHECK(b1.zero(home)); 00502 } else if (b2.one()) { 00503 return BinOrTrue<BVA,BVB>::post(home,b0,b1); 00504 } else { 00505 switch (bool_test(b0,b1)) { 00506 case BT_SAME: 00507 return Eq<BVA,BVC>::post(home,b0,b2); 00508 case BT_COMP: 00509 GECODE_ME_CHECK(b2.one(home)); 00510 break; 00511 case BT_NONE: 00512 if (b0.one() || b1.one()) { 00513 GECODE_ME_CHECK(b2.one(home)); 00514 } else if (b0.zero()) { 00515 return Eq<BVB,BVC>::post(home,b1,b2); 00516 } else if (b1.zero()) { 00517 return Eq<BVA,BVC>::post(home,b0,b2); 00518 } else { 00519 (void) new (home) Or<BVA,BVB,BVC>(home,b0,b1,b2); 00520 } 00521 break; 00522 default: GECODE_NEVER; 00523 } 00524 } 00525 return ES_OK; 00526 } 00527 00528 template<class BVA, class BVB, class BVC> 00529 ExecStatus 00530 Or<BVA,BVB,BVC>::propagate(Space& home, const ModEventDelta&) { 00531 #define GECODE_INT_STATUS(S0,S1,S2) \ 00532 ((BVA::S0<<(2*BVA::BITS))|(BVB::S1<<(1*BVB::BITS))|(BVC::S2<<(0*BVC::BITS))) 00533 switch ((x0.status() << (2*BVA::BITS)) | (x1.status() << (1*BVB::BITS)) | 00534 (x2.status() << (0*BVC::BITS))) { 00535 case GECODE_INT_STATUS(NONE,NONE,NONE): 00536 GECODE_NEVER; 00537 case GECODE_INT_STATUS(NONE,NONE,ZERO): 00538 GECODE_ME_CHECK(x0.zero_none(home)); 00539 GECODE_ME_CHECK(x1.zero_none(home)); 00540 break; 00541 case GECODE_INT_STATUS(NONE,NONE,ONE): 00542 return ES_FIX; 00543 case GECODE_INT_STATUS(NONE,ZERO,NONE): 00544 switch (bool_test(x0,x2)) { 00545 case BT_SAME: return home.ES_SUBSUMED(*this); 00546 case BT_COMP: return ES_FAILED; 00547 case BT_NONE: return ES_FIX; 00548 default: GECODE_NEVER; 00549 } 00550 GECODE_NEVER; 00551 case GECODE_INT_STATUS(NONE,ZERO,ZERO): 00552 GECODE_ME_CHECK(x0.zero_none(home)); break; 00553 case GECODE_INT_STATUS(NONE,ZERO,ONE): 00554 GECODE_ME_CHECK(x0.one_none(home)); break; 00555 case GECODE_INT_STATUS(NONE,ONE,NONE): 00556 GECODE_ME_CHECK(x2.one_none(home)); break; 00557 case GECODE_INT_STATUS(NONE,ONE,ZERO): 00558 return ES_FAILED; 00559 case GECODE_INT_STATUS(NONE,ONE,ONE): 00560 break; 00561 case GECODE_INT_STATUS(ZERO,NONE,NONE): 00562 switch (bool_test(x1,x2)) { 00563 case BT_SAME: return home.ES_SUBSUMED(*this); 00564 case BT_COMP: return ES_FAILED; 00565 case BT_NONE: return ES_FIX; 00566 default: GECODE_NEVER; 00567 } 00568 GECODE_NEVER; 00569 case GECODE_INT_STATUS(ZERO,NONE,ZERO): 00570 GECODE_ME_CHECK(x1.zero_none(home)); break; 00571 case GECODE_INT_STATUS(ZERO,NONE,ONE): 00572 GECODE_ME_CHECK(x1.one_none(home)); break; 00573 case GECODE_INT_STATUS(ZERO,ZERO,NONE): 00574 GECODE_ME_CHECK(x2.zero_none(home)); break; 00575 case GECODE_INT_STATUS(ZERO,ZERO,ZERO): 00576 break; 00577 case GECODE_INT_STATUS(ZERO,ZERO,ONE): 00578 return ES_FAILED; 00579 case GECODE_INT_STATUS(ZERO,ONE,NONE): 00580 GECODE_ME_CHECK(x2.one_none(home)); break; 00581 case GECODE_INT_STATUS(ZERO,ONE,ZERO): 00582 return ES_FAILED; 00583 case GECODE_INT_STATUS(ZERO,ONE,ONE): 00584 break; 00585 case GECODE_INT_STATUS(ONE,NONE,NONE): 00586 GECODE_ME_CHECK(x2.one_none(home)); break; 00587 case GECODE_INT_STATUS(ONE,NONE,ZERO): 00588 return ES_FAILED; 00589 case GECODE_INT_STATUS(ONE,NONE,ONE): 00590 break; 00591 case GECODE_INT_STATUS(ONE,ZERO,NONE): 00592 GECODE_ME_CHECK(x2.one_none(home)); break; 00593 case GECODE_INT_STATUS(ONE,ZERO,ZERO): 00594 return ES_FAILED; 00595 case GECODE_INT_STATUS(ONE,ZERO,ONE): 00596 break; 00597 case GECODE_INT_STATUS(ONE,ONE,NONE): 00598 GECODE_ME_CHECK(x2.one_none(home)); break; 00599 case GECODE_INT_STATUS(ONE,ONE,ZERO): 00600 return ES_FAILED; 00601 case GECODE_INT_STATUS(ONE,ONE,ONE): 00602 break; 00603 default: 00604 GECODE_NEVER; 00605 } 00606 return home.ES_SUBSUMED(*this); 00607 #undef GECODE_INT_STATUS 00608 } 00609 00610 /* 00611 * N-ary Boolean disjunction propagator (true) 00612 * 00613 */ 00614 00615 template<class BV> 00616 forceinline 00617 NaryOrTrue<BV>::NaryOrTrue(Home home, ViewArray<BV>& b) 00618 : BinaryPropagator<BV,PC_BOOL_VAL>(home, 00619 b[b.size()-2], 00620 b[b.size()-1]), x(b) { 00621 assert(x.size() > 2); 00622 x.size(x.size()-2); 00623 } 00624 00625 template<class BV> 00626 PropCost 00627 NaryOrTrue<BV>::cost(const Space&, const ModEventDelta&) const { 00628 return PropCost::binary(PropCost::LO); 00629 } 00630 00631 template<class BV> 00632 forceinline 00633 NaryOrTrue<BV>::NaryOrTrue(Space& home, bool share, NaryOrTrue<BV>& p) 00634 : BinaryPropagator<BV,PC_BOOL_VAL>(home,share,p) { 00635 x.update(home,share,p.x); 00636 } 00637 00638 template<class BV> 00639 Actor* 00640 NaryOrTrue<BV>::copy(Space& home, bool share) { 00641 int n = x.size(); 00642 if (n > 0) { 00643 // Eliminate all zeros and find a one 00644 for (int i=n; i--; ) 00645 if (x[i].one()) { 00646 // Only keep the one 00647 x[0]=x[i]; x.size(1); 00648 return new (home) OrTrueSubsumed<BV>(home,share,*this,x0,x1); 00649 } else if (x[i].zero()) { 00650 // Eliminate the zero 00651 x[i]=x[--n]; 00652 } 00653 x.size(n); 00654 } 00655 switch (n) { 00656 case 0: 00657 return new (home) BinOrTrue<BV,BV>(home,share,*this,x0,x1); 00658 case 1: 00659 return new (home) TerOrTrue<BV>(home,share,*this,x0,x1,x[0]); 00660 case 2: 00661 return new (home) QuadOrTrue<BV>(home,share,*this,x0,x1,x[0],x[1]); 00662 default: 00663 return new (home) NaryOrTrue<BV>(home,share,*this); 00664 } 00665 } 00666 00667 template<class BV> 00668 inline ExecStatus 00669 NaryOrTrue<BV>::post(Home home, ViewArray<BV>& b) { 00670 for (int i=b.size(); i--; ) 00671 if (b[i].one()) 00672 return ES_OK; 00673 else if (b[i].zero()) 00674 b.move_lst(i); 00675 if (b.size() == 0) 00676 return ES_FAILED; 00677 if (b.size() == 1) { 00678 GECODE_ME_CHECK(b[0].one(home)); 00679 } else if (b.size() == 2) { 00680 return BinOrTrue<BV,BV>::post(home,b[0],b[1]); 00681 } else if (b.size() == 3) { 00682 return TerOrTrue<BV>::post(home,b[0],b[1],b[2]); 00683 } else if (b.size() == 4) { 00684 return QuadOrTrue<BV>::post(home,b[0],b[1],b[2],b[3]); 00685 } else { 00686 (void) new (home) NaryOrTrue(home,b); 00687 } 00688 return ES_OK; 00689 } 00690 00691 template<class BV> 00692 forceinline size_t 00693 NaryOrTrue<BV>::dispose(Space& home) { 00694 (void) BinaryPropagator<BV,PC_BOOL_VAL>::dispose(home); 00695 return sizeof(*this); 00696 } 00697 00698 template<class BV> 00699 forceinline ExecStatus 00700 NaryOrTrue<BV>::resubscribe(Space& home, BV& x0, BV x1) { 00701 if (x0.zero()) { 00702 int n = x.size(); 00703 for (int i=n; i--; ) 00704 if (x[i].one()) { 00705 return home.ES_SUBSUMED(*this); 00706 } else if (x[i].zero()) { 00707 x[i] = x[--n]; 00708 } else { 00709 // Rewrite if there is just one view left 00710 if (i == 0) { 00711 GECODE_REWRITE(*this, 00712 (BinOrTrue<BV,BV>::post(home(*this),x1,x[0]))); 00713 } 00714 // Move to x0 and subscribe 00715 x0=x[i]; x[i]=x[--n]; 00716 x.size(n); 00717 x0.subscribe(home,*this,PC_BOOL_VAL,false); 00718 return ES_FIX; 00719 } 00720 // All views have been assigned! 00721 GECODE_ME_CHECK(x1.one(home)); 00722 return home.ES_SUBSUMED(*this); 00723 } 00724 return ES_FIX; 00725 } 00726 00727 template<class BV> 00728 ExecStatus 00729 NaryOrTrue<BV>::propagate(Space& home, const ModEventDelta&) { 00730 if (x0.one()) 00731 return home.ES_SUBSUMED(*this); 00732 if (x1.one()) 00733 return home.ES_SUBSUMED(*this); 00734 GECODE_ES_CHECK(resubscribe(home,x0,x1)); 00735 GECODE_ES_CHECK(resubscribe(home,x1,x0)); 00736 return ES_FIX; 00737 } 00738 00739 00740 /* 00741 * N-ary Boolean disjunction propagator 00742 * 00743 */ 00744 00745 template<class VX, class VY> 00746 forceinline 00747 NaryOr<VX,VY>::NaryOr(Home home, ViewArray<VX>& x, VY y) 00748 : MixNaryOnePropagator<VX,PC_BOOL_NONE,VY,PC_BOOL_VAL>(home,x,y), 00749 n_zero(0), c(home) { 00750 x.subscribe(home,*new (home) Advisor(home,*this,c)); 00751 } 00752 00753 template<class VX, class VY> 00754 forceinline 00755 NaryOr<VX,VY>::NaryOr(Space& home, bool share, NaryOr<VX,VY>& p) 00756 : MixNaryOnePropagator<VX,PC_BOOL_NONE,VY,PC_BOOL_VAL>(home,share,p), 00757 n_zero(p.n_zero) { 00758 c.update(home,share,p.c); 00759 } 00760 00761 template<class VX, class VY> 00762 Actor* 00763 NaryOr<VX,VY>::copy(Space& home, bool share) { 00764 assert(n_zero < x.size()); 00765 if (n_zero > 0) { 00766 int n=x.size(); 00767 // Eliminate all zeros 00768 for (int i=n; i--; ) 00769 if (x[i].zero()) 00770 x[i]=x[--n]; 00771 x.size(n); 00772 n_zero = 0; 00773 } 00774 assert(n_zero < x.size()); 00775 return new (home) NaryOr<VX,VY>(home,share,*this); 00776 } 00777 00778 template<class VX, class VY> 00779 inline ExecStatus 00780 NaryOr<VX,VY>::post(Home home, ViewArray<VX>& x, VY y) { 00781 assert(!x.shared(home)); 00782 if (y.one()) 00783 return NaryOrTrue<VX>::post(home,x); 00784 if (y.zero()) { 00785 for (int i=x.size(); i--; ) 00786 GECODE_ME_CHECK(x[i].zero(home)); 00787 return ES_OK; 00788 } 00789 for (int i=x.size(); i--; ) 00790 if (x[i].one()) { 00791 GECODE_ME_CHECK(y.one_none(home)); 00792 return ES_OK; 00793 } else if (x[i].zero()) { 00794 x.move_lst(i); 00795 } 00796 if (x.size() == 0) { 00797 GECODE_ME_CHECK(y.zero_none(home)); 00798 } else if (x.size() == 1) { 00799 return Eq<VX,VY>::post(home,x[0],y); 00800 } else if (x.size() == 2) { 00801 return Or<VX,VX,VY>::post(home,x[0],x[1],y); 00802 } else { 00803 (void) new (home) NaryOr(home,x,y); 00804 } 00805 return ES_OK; 00806 } 00807 00808 template<class VX, class VY> 00809 PropCost 00810 NaryOr<VX,VY>::cost(const Space&, const ModEventDelta&) const { 00811 return PropCost::unary(PropCost::LO); 00812 } 00813 00814 template<class VX, class VY> 00815 ExecStatus 00816 NaryOr<VX,VY>::advise(Space&, Advisor&, const Delta& d) { 00817 // Decides whether the propagator must be run 00818 if (VX::zero(d) && (++n_zero < x.size())) 00819 return ES_FIX; 00820 else 00821 return ES_NOFIX; 00822 } 00823 00824 template<class VX, class VY> 00825 forceinline size_t 00826 NaryOr<VX,VY>::dispose(Space& home) { 00827 Advisors<Advisor> as(c); 00828 x.cancel(home,as.advisor()); 00829 c.dispose(home); 00830 (void) MixNaryOnePropagator<VX,PC_BOOL_NONE,VY,PC_BOOL_VAL> 00831 ::dispose(home); 00832 return sizeof(*this); 00833 } 00834 00835 template<class VX, class VY> 00836 ExecStatus 00837 NaryOr<VX,VY>::propagate(Space& home, const ModEventDelta&) { 00838 if (y.one()) 00839 GECODE_REWRITE(*this,NaryOrTrue<VX>::post(home(*this),x)); 00840 if (y.zero()) { 00841 // Note that this might trigger the advisor of this propagator! 00842 for (int i = x.size(); i--; ) 00843 GECODE_ME_CHECK(x[i].zero(home)); 00844 } else if (n_zero == x.size()) { 00845 // All views are zero 00846 GECODE_ME_CHECK(y.zero_none(home)); 00847 } else { 00848 // There is exactly one view which is one 00849 GECODE_ME_CHECK(y.one_none(home)); 00850 } 00851 return home.ES_SUBSUMED(*this); 00852 } 00853 00854 }}} 00855 00856 // STATISTICS: int-prop 00857