Generated on Fri May 13 2011 22:41:15 for Gecode by doxygen 1.7.1

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