Generated on Mon Jul 6 18:09:05 2009 for Gecode by doxygen 1.5.9
gecode » int » bool

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-03-31 01:48:15 +0200 (Tue, 31 Mar 2009) $ by $Author: tack $
00011  *     $Revision: 8616 $
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(Space& home, BV b0, BV b1);
00050   public:
00052     OrTrueSubsumed(Space& 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   (Space& home, BV b0, BV b1)
00066     : BoolBinary<BV,BV>(home,b0,b1) {}
00067 
00068   template <class BV>
00069   forceinline ExecStatus
00070   OrTrueSubsumed<BV>::post(Space& 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(Space& 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(Space& 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(Space& 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(Space& 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(Space& 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(Space& 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(Space& 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(Space& 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(Space& 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(Space& 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,(BinOrTrue<BV,BV>::post(home,x1,x[0])));
00717           }
00718           // Move to x0 and subscribe
00719           x0=x[i]; x[i]=x[--n];
00720           x.size(n);
00721           x0.subscribe(home,*this,PC_BOOL_VAL,false);
00722           return ES_FIX;
00723         }
00724       // All views have been assigned!
00725       GECODE_ME_CHECK(x1.one(home));
00726       return ES_SUBSUMED(*this,sizeof(*this));
00727     }
00728     return ES_FIX;
00729   }
00730 
00731   template<class BV>
00732   ExecStatus
00733   NaryOrTrue<BV>::propagate(Space& home, const ModEventDelta&) {
00734     if (x0.one()) {
00735       x1.cancel(home,*this,PC_BOOL_VAL);
00736       return ES_SUBSUMED(*this,sizeof(*this));
00737     }
00738     if (x1.one()) {
00739       x0.cancel(home,*this,PC_BOOL_VAL);
00740       return ES_SUBSUMED(*this,sizeof(*this));
00741     }
00742     GECODE_ES_CHECK(resubscribe(home,x0,x1));
00743     GECODE_ES_CHECK(resubscribe(home,x1,x0));
00744     return ES_FIX;
00745   }
00746 
00747   template<class BV>
00748   size_t
00749   NaryOrTrue<BV>::dispose(Space& home) {
00750     (void) BinaryPropagator<BV,PC_BOOL_VAL>::dispose(home);
00751     return sizeof(*this);
00752   }
00753 
00754 
00755   /*
00756    * N-ary Boolean disjunction propagator
00757    *
00758    */
00759 
00760   template<class VX, class VY>
00761   forceinline
00762   NaryOr<VX,VY>::NaryOr(Space& home, ViewArray<VX>& x, VY y)
00763     : MixNaryOnePropagator<VX,PC_BOOL_NONE,VY,PC_BOOL_VAL>(home,x,y),
00764       n_zero(0), c(home) {
00765     x.subscribe(home,*new (home) Advisor(home,*this,c));
00766   }
00767 
00768   template<class VX, class VY>
00769   forceinline
00770   NaryOr<VX,VY>::NaryOr(Space& home, bool share, NaryOr<VX,VY>& p)
00771     : MixNaryOnePropagator<VX,PC_BOOL_NONE,VY,PC_BOOL_VAL>(home,share,p),
00772       n_zero(p.n_zero) {
00773     c.update(home,share,p.c);
00774   }
00775 
00776   template<class VX, class VY>
00777   Actor*
00778   NaryOr<VX,VY>::copy(Space& home, bool share) {
00779     assert(n_zero < x.size());
00780     if (n_zero > 0) {
00781       int n=x.size();
00782       // Eliminate all zeros
00783       for (int i=n; i--; )
00784         if (x[i].zero())
00785           x[i]=x[--n];
00786       x.size(n);
00787       n_zero = 0;
00788     }
00789     assert(n_zero < x.size());
00790     return new (home) NaryOr<VX,VY>(home,share,*this);
00791   }
00792 
00793   template<class VX, class VY>
00794   inline ExecStatus
00795   NaryOr<VX,VY>::post(Space& home, ViewArray<VX>& x, VY y) {
00796     assert(!x.shared(home));
00797     if (y.one())
00798       return NaryOrTrue<VX>::post(home,x);
00799     if (y.zero()) {
00800       for (int i=x.size(); i--; )
00801         GECODE_ME_CHECK(x[i].zero(home));
00802       return ES_OK;
00803     }
00804     for (int i=x.size(); i--; )
00805       if (x[i].one()) {
00806         GECODE_ME_CHECK(y.one_none(home));
00807         return ES_OK;
00808       } else if (x[i].zero()) {
00809         x.move_lst(i);
00810       }
00811     if (x.size() == 0) {
00812       GECODE_ME_CHECK(y.zero_none(home));
00813     } else if (x.size() == 1) {
00814       return Eq<VX,VY>::post(home,x[0],y);
00815     } else if (x.size() == 2) {
00816       return Or<VX,VX,VY>::post(home,x[0],x[1],y);
00817     } else {
00818       (void) new (home) NaryOr(home,x,y);
00819     }
00820     return ES_OK;
00821   }
00822 
00823   template<class VX, class VY>
00824   PropCost
00825   NaryOr<VX,VY>::cost(const Space&, const ModEventDelta&) const {
00826     return PropCost::unary(PropCost::LO);
00827   }
00828 
00829   template<class VX, class VY>
00830   ExecStatus
00831   NaryOr<VX,VY>::advise(Space&, Advisor&, const Delta& d) {
00832     // Decides whether the propagator must be run
00833     if (VX::zero(d) && (++n_zero < x.size()))
00834       return ES_FIX;
00835     else
00836       return ES_NOFIX;
00837   }
00838 
00839   template<class VX, class VY>
00840   ExecStatus
00841   NaryOr<VX,VY>::propagate(Space& home, const ModEventDelta&) {
00842     if (y.one())
00843       GECODE_REWRITE(*this,NaryOrTrue<VX>::post(home,x));
00844     Advisors<Advisor> as(c);
00845     x.cancel(home,as.advisor());
00846     c.dispose(home);
00847     if (y.zero()) {
00848       for (int i = x.size(); i--; )
00849         GECODE_ME_CHECK(x[i].zero(home));
00850     } else if (n_zero == x.size()) {
00851       // All views are zero
00852       GECODE_ME_CHECK(y.zero_none(home));
00853     } else {
00854       // There is exactly one view which is one
00855       GECODE_ME_CHECK(y.one_none(home));
00856     }
00857     return ES_SUBSUMED(*this,sizeof(*this));
00858   }
00859 
00860   template<class VX, class VY>
00861   size_t
00862   NaryOr<VX,VY>::dispose(Space& home) {
00863     Advisors<Advisor> as(c);
00864     x.cancel(home,as.advisor());
00865     c.dispose(home);
00866     (void) MixNaryOnePropagator<VX,PC_BOOL_NONE,VY,PC_BOOL_VAL>
00867       ::dispose(home);
00868     return sizeof(*this);
00869   }
00870 
00871 }}}
00872 
00873 // STATISTICS: int-prop
00874