or.hpp

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: 2011-07-07 14:43:42 +0200 (Thu, 07 Jul 2011) $ by $Author: schulte $
00011  *     $Revision: 12161 $
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,b[0],b[1]), x(b) {
00619     assert(x.size() > 2);
00620     x.drop_fst(2);
00621   }
00622 
00623   template<class BV>
00624   PropCost
00625   NaryOrTrue<BV>::cost(const Space&, const ModEventDelta&) const {
00626     return PropCost::binary(PropCost::LO);
00627   }
00628 
00629   template<class BV>
00630   forceinline
00631   NaryOrTrue<BV>::NaryOrTrue(Space& home, bool share, NaryOrTrue<BV>& p)
00632     : BinaryPropagator<BV,PC_BOOL_VAL>(home,share,p) {
00633     x.update(home,share,p.x);
00634   }
00635 
00636   template<class BV>
00637   Actor*
00638   NaryOrTrue<BV>::copy(Space& home, bool share) {
00639     int n = x.size();
00640     if (n > 0) {
00641       // Eliminate all zeros and find a one
00642       for (int i=n; i--; )
00643         if (x[i].one()) {
00644           // Only keep the one
00645           x[0]=x[i]; x.size(1);
00646           return new (home) OrTrueSubsumed<BV>(home,share,*this,x0,x1);
00647         } else if (x[i].zero()) {
00648           // Eliminate the zero
00649           x[i]=x[--n];
00650         }
00651       x.size(n);
00652     }
00653     switch (n) {
00654     case 0:
00655       return new (home) BinOrTrue<BV,BV>(home,share,*this,x0,x1);
00656     case 1:
00657       return new (home) TerOrTrue<BV>(home,share,*this,x0,x1,x[0]);
00658     case 2:
00659       return new (home) QuadOrTrue<BV>(home,share,*this,x0,x1,x[0],x[1]);
00660     default:
00661       return new (home) NaryOrTrue<BV>(home,share,*this);
00662     }
00663   }
00664 
00665   template<class BV>
00666   inline ExecStatus
00667   NaryOrTrue<BV>::post(Home home, ViewArray<BV>& b) {
00668     for (int i=b.size(); i--; )
00669       if (b[i].one())
00670         return ES_OK;
00671       else if (b[i].zero())
00672         b.move_lst(i);
00673     if (b.size() == 0)
00674       return ES_FAILED;
00675     if (b.size() == 1) {
00676       GECODE_ME_CHECK(b[0].one(home));
00677     } else if (b.size() == 2) {
00678        return BinOrTrue<BV,BV>::post(home,b[0],b[1]);
00679     } else if (b.size() == 3) {
00680        return TerOrTrue<BV>::post(home,b[0],b[1],b[2]);
00681     } else if (b.size() == 4) {
00682        return QuadOrTrue<BV>::post(home,b[0],b[1],b[2],b[3]);
00683     } else {
00684       (void) new (home) NaryOrTrue(home,b);
00685     }
00686     return ES_OK;
00687   }
00688 
00689   template<class BV>
00690   forceinline size_t
00691   NaryOrTrue<BV>::dispose(Space& home) {
00692     (void) BinaryPropagator<BV,PC_BOOL_VAL>::dispose(home);
00693     return sizeof(*this);
00694   }
00695 
00696   template<class BV>
00697   forceinline ExecStatus
00698   NaryOrTrue<BV>::resubscribe(Space& home, BV& x0, BV x1) {
00699     if (x0.zero()) {
00700       int n = x.size();
00701       for (int i=n; i--; )
00702         if (x[i].one()) {
00703           return home.ES_SUBSUMED(*this);
00704         } else if (x[i].zero()) {
00705           x[i] = x[--n];
00706         } else {
00707           // Move to x0 and subscribe
00708           x0=x[i]; x[i]=x[--n];
00709           x.size(n);
00710           x0.subscribe(home,*this,PC_BOOL_VAL,false);
00711           return ES_FIX;
00712         }
00713       // All views have been assigned!
00714       GECODE_ME_CHECK(x1.one(home));
00715       return home.ES_SUBSUMED(*this);
00716     }
00717     return ES_FIX;
00718   }
00719 
00720   template<class BV>
00721   ExecStatus
00722   NaryOrTrue<BV>::propagate(Space& home, const ModEventDelta&) {
00723     if (x0.one())
00724       return home.ES_SUBSUMED(*this);
00725     if (x1.one())
00726       return home.ES_SUBSUMED(*this);
00727     GECODE_ES_CHECK(resubscribe(home,x0,x1));
00728     GECODE_ES_CHECK(resubscribe(home,x1,x0));
00729     return ES_FIX;
00730   }
00731 
00732 
00733   /*
00734    * N-ary Boolean disjunction propagator
00735    *
00736    */
00737 
00738   template<class VX, class VY>
00739   forceinline
00740   NaryOr<VX,VY>::NaryOr(Home home, ViewArray<VX>& x, VY y)
00741     : MixNaryOnePropagator<VX,PC_BOOL_NONE,VY,PC_BOOL_VAL>(home,x,y),
00742       n_zero(0), c(home) {
00743     x.subscribe(home,*new (home) Advisor(home,*this,c));
00744   }
00745 
00746   template<class VX, class VY>
00747   forceinline
00748   NaryOr<VX,VY>::NaryOr(Space& home, bool share, NaryOr<VX,VY>& p)
00749     : MixNaryOnePropagator<VX,PC_BOOL_NONE,VY,PC_BOOL_VAL>(home,share,p),
00750       n_zero(p.n_zero) {
00751     c.update(home,share,p.c);
00752   }
00753 
00754   template<class VX, class VY>
00755   Actor*
00756   NaryOr<VX,VY>::copy(Space& home, bool share) {
00757     assert(n_zero < x.size());
00758     if (n_zero > 0) {
00759       int n=x.size();
00760       // Eliminate all zeros
00761       for (int i=n; i--; )
00762         if (x[i].zero())
00763           x[i]=x[--n];
00764       x.size(n);
00765       n_zero = 0;
00766     }
00767     assert(n_zero < x.size());
00768     return new (home) NaryOr<VX,VY>(home,share,*this);
00769   }
00770 
00771   template<class VX, class VY>
00772   inline ExecStatus
00773   NaryOr<VX,VY>::post(Home home, ViewArray<VX>& x, VY y) {
00774     assert(!x.shared(home));
00775     if (y.one())
00776       return NaryOrTrue<VX>::post(home,x);
00777     if (y.zero()) {
00778       for (int i=x.size(); i--; )
00779         GECODE_ME_CHECK(x[i].zero(home));
00780       return ES_OK;
00781     }
00782     for (int i=x.size(); i--; )
00783       if (x[i].one()) {
00784         GECODE_ME_CHECK(y.one_none(home));
00785         return ES_OK;
00786       } else if (x[i].zero()) {
00787         x.move_lst(i);
00788       }
00789     if (x.size() == 0) {
00790       GECODE_ME_CHECK(y.zero_none(home));
00791     } else if (x.size() == 1) {
00792       return Eq<VX,VY>::post(home,x[0],y);
00793     } else if (x.size() == 2) {
00794       return Or<VX,VX,VY>::post(home,x[0],x[1],y);
00795     } else {
00796       (void) new (home) NaryOr(home,x,y);
00797     }
00798     return ES_OK;
00799   }
00800 
00801   template<class VX, class VY>
00802   PropCost
00803   NaryOr<VX,VY>::cost(const Space&, const ModEventDelta&) const {
00804     return PropCost::unary(PropCost::LO);
00805   }
00806 
00807   template<class VX, class VY>
00808   ExecStatus
00809   NaryOr<VX,VY>::advise(Space&, Advisor&, const Delta& d) {
00810     // Decides whether the propagator must be run
00811     if (VX::zero(d) && (++n_zero < x.size()))
00812       return ES_FIX;
00813     else
00814       return ES_NOFIX;
00815   }
00816 
00817   template<class VX, class VY>
00818   forceinline size_t
00819   NaryOr<VX,VY>::dispose(Space& home) {
00820     Advisors<Advisor> as(c);
00821     x.cancel(home,as.advisor());
00822     c.dispose(home);
00823     (void) MixNaryOnePropagator<VX,PC_BOOL_NONE,VY,PC_BOOL_VAL>
00824       ::dispose(home);
00825     return sizeof(*this);
00826   }
00827 
00828   template<class VX, class VY>
00829   ExecStatus
00830   NaryOr<VX,VY>::propagate(Space& home, const ModEventDelta&) {
00831     if (y.one())
00832       GECODE_REWRITE(*this,NaryOrTrue<VX>::post(home(*this),x));
00833     if (y.zero()) {
00834       // Note that this might trigger the advisor of this propagator!
00835       for (int i = x.size(); i--; )
00836         GECODE_ME_CHECK(x[i].zero(home));
00837     } else if (n_zero == x.size()) {
00838       // All views are zero
00839       GECODE_ME_CHECK(y.zero_none(home));
00840     } else {
00841       // There is exactly one view which is one
00842       GECODE_ME_CHECK(y.one_none(home));
00843     }
00844     return home.ES_SUBSUMED(*this);
00845   }
00846 
00847 }}}
00848 
00849 // STATISTICS: int-prop
00850