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