binary.icc

00001 /*
00002  *  Main authors:
00003  *     Christian Schulte <schulte@gecode.org>
00004  *
00005  *  Copyright:
00006  *     Christian Schulte, 2003
00007  *
00008  *  Last modified:
00009  *     $Date: 2006-08-04 16:03:26 +0200 (Fri, 04 Aug 2006) $ by $Author: schulte $
00010  *     $Revision: 3512 $
00011  *
00012  *  This file is part of Gecode, the generic constraint
00013  *  development environment:
00014  *     http://www.gecode.org
00015  *
00016  *  See the file "LICENSE" for information on usage and
00017  *  redistribution of this file, and for a
00018  *     DISCLAIMER OF ALL WARRANTIES.
00019  *
00020  */
00021 
00022 namespace Gecode { namespace Int { namespace Linear {
00023 
00024   /*
00025    * Binary linear propagators
00026    *
00027    */
00028   template <class Val, class A, class B, PropCond pc>
00029   forceinline
00030   LinBin<Val,A,B,pc>::LinBin(Space* home, A y0, B y1, Val c0)
00031     : Propagator(home), x0(y0), x1(y1), c(c0) {
00032     x0.subscribe(home,this,pc);
00033     x1.subscribe(home,this,pc);
00034   }
00035 
00036   template <class Val, class A, class B, PropCond pc>
00037   forceinline
00038   LinBin<Val,A,B,pc>::LinBin(Space* home, bool share, LinBin<Val,A,B,pc>& p)
00039     : Propagator(home,share,p), c(p.c) {
00040     x0.update(home,share,p.x0);
00041     x1.update(home,share,p.x1);
00042   }
00043 
00044   template <class Val, class A, class B, PropCond pc>
00045   forceinline
00046   LinBin<Val,A,B,pc>::LinBin(Space* home, bool share, Propagator& p,
00047                              A y0, B y1, Val c0)
00048     : Propagator(home,share,p), c(c0) {
00049     x0.update(home,share,y0);
00050     x1.update(home,share,y1);
00051   }
00052 
00053   template <class Val, class A, class B, PropCond pc>
00054   PropCost
00055   LinBin<Val,A,B,pc>::cost(void) const {
00056     return PC_BINARY_LO;
00057   }
00058 
00059   template <class Val, class A, class B, PropCond pc>
00060   size_t
00061   LinBin<Val,A,B,pc>::dispose(Space* home) {
00062     assert(!home->failed());
00063     x0.cancel(home,this,pc);
00064     x1.cancel(home,this,pc);
00065     (void) Propagator::dispose(home);
00066     return sizeof(*this);
00067   }
00068 
00069 
00070   /*
00071    * Binary reified linear propagators
00072    *
00073    */
00074   template <class Val, class A, class B, PropCond pc, class Ctrl>
00075   forceinline
00076   ReLinBin<Val,A,B,pc,Ctrl>::ReLinBin(Space* home, A y0, B y1, Val c0, Ctrl b0)
00077     : Propagator(home), x0(y0), x1(y1), c(c0), b(b0) {
00078     x0.subscribe(home,this,pc);
00079     x1.subscribe(home,this,pc);
00080     b.subscribe(home,this,PC_INT_VAL);
00081   }
00082 
00083   template <class Val, class A, class B, PropCond pc, class Ctrl>
00084   forceinline
00085   ReLinBin<Val,A,B,pc,Ctrl>::ReLinBin(Space* home, bool share,
00086                                       ReLinBin<Val,A,B,pc,Ctrl>& p)
00087     : Propagator(home,share,p), c(p.c) {
00088     x0.update(home,share,p.x0);
00089     x1.update(home,share,p.x1);
00090     b.update(home,share,p.b);
00091   }
00092 
00093   template <class Val, class A, class B, PropCond pc, class Ctrl>
00094   PropCost
00095   ReLinBin<Val,A,B,pc,Ctrl>::cost(void) const {
00096     return PC_BINARY_LO;
00097   }
00098 
00099   template <class Val, class A, class B, PropCond pc, class Ctrl>
00100   size_t
00101   ReLinBin<Val,A,B,pc,Ctrl>::dispose(Space* home) {
00102     assert(!home->failed());
00103     x0.cancel(home,this,pc);
00104     x1.cancel(home,this,pc);
00105     b.cancel(home,this,PC_INT_VAL);
00106     (void) Propagator::dispose(home);
00107     return sizeof(*this);
00108   }
00109 
00110 
00111   /*
00112    * Binary bounds-consistent linear equality
00113    *
00114    */
00115 
00116   template <class Val, class A, class B>
00117   forceinline
00118   EqBin<Val,A,B>::EqBin(Space* home, A x0, B x1, Val c)
00119     : LinBin<Val,A,B,PC_INT_BND>(home,x0,x1,c) {}
00120 
00121   template <class Val, class A, class B>
00122   ExecStatus
00123   EqBin<Val,A,B>::post(Space* home, A x0, B x1, Val c) {
00124     (void) new (home) EqBin<Val,A,B>(home,x0,x1,c);
00125     return ES_OK;
00126   }
00127 
00128 
00129   template <class Val, class A, class B>
00130   forceinline
00131   EqBin<Val,A,B>::EqBin(Space* home, bool share, EqBin<Val,A,B>& p)
00132     : LinBin<Val,A,B,PC_INT_BND>(home,share,p) {}
00133 
00134   template <class Val, class A, class B>
00135   forceinline
00136   EqBin<Val,A,B>::EqBin(Space* home, bool share, Propagator& p,
00137                         A x0, B x1, Val c)
00138     : LinBin<Val,A,B,PC_INT_BND>(home,share,p,x0,x1,c) {}
00139 
00140   template <class Val, class A, class B>
00141   Actor*
00142   EqBin<Val,A,B>::copy(Space* home, bool share) {
00143     return new (home) EqBin<Val,A,B>(home,share,*this);
00144   }
00145 
00147   enum BinMod {
00148     BM_X0_MIN = 1<<0,
00149     BM_X0_MAX = 1<<1,
00150     BM_X1_MIN = 1<<2,
00151     BM_X1_MAX = 1<<3,
00152     BM_ALL    = BM_X0_MIN|BM_X0_MAX|BM_X1_MIN|BM_X1_MAX
00153   };
00154 
00155 #define GECODE_INT_PV(CASE,TELL,UPDATE)         \
00156   if (bm & (CASE)) {                            \
00157     bm -= (CASE); ModEvent me = (TELL);         \
00158     if (me_failed(me))   return ES_FAILED;      \
00159     if (me_modified(me)) bm |= (UPDATE);        \
00160   }
00161 
00162   template <class Val, class A, class B>
00163   ExecStatus
00164   EqBin<Val,A,B>::propagate(Space* home) {
00165     int bm = BM_ALL;
00166     do {
00167       GECODE_INT_PV(BM_X0_MIN, x0.gq(home,c-x1.max()), BM_X1_MAX);
00168       GECODE_INT_PV(BM_X1_MIN, x1.gq(home,c-x0.max()), BM_X0_MAX);
00169       GECODE_INT_PV(BM_X0_MAX, x0.lq(home,c-x1.min()), BM_X1_MIN);
00170       GECODE_INT_PV(BM_X1_MAX, x1.lq(home,c-x0.min()), BM_X0_MIN);
00171     } while (bm);
00172     return x0.assigned() ? ES_SUBSUMED : ES_FIX;
00173   }
00174 
00175 #undef GECODE_INT_PV
00176 
00177 
00178 
00179 
00180 
00181   /*
00182    * Reified binary bounds-consistent linear equality
00183    *
00184    */
00185 
00186   template <class Val, class A, class B, class Ctrl>
00187   forceinline
00188   ReEqBin<Val,A,B,Ctrl>::ReEqBin(Space* home, A x0, B x1, Val c, Ctrl b)
00189     : ReLinBin<Val,A,B,PC_INT_BND,Ctrl>(home,x0,x1,c,b) {}
00190 
00191   template <class Val, class A, class B, class Ctrl>
00192   ExecStatus
00193   ReEqBin<Val,A,B,Ctrl>::post(Space* home, A x0, B x1, Val c, Ctrl b) {
00194     (void) new (home) ReEqBin<Val,A,B,Ctrl>(home,x0,x1,c,b);
00195     return ES_OK;
00196   }
00197 
00198 
00199   template <class Val, class A, class B, class Ctrl>
00200   forceinline
00201   ReEqBin<Val,A,B,Ctrl>::ReEqBin(Space* home, bool share,
00202                                  ReEqBin<Val,A,B,Ctrl>& p)
00203     : ReLinBin<Val,A,B,PC_INT_BND,Ctrl>(home,share,p) {}
00204 
00205   template <class Val, class A, class B, class Ctrl>
00206   Actor*
00207   ReEqBin<Val,A,B,Ctrl>::copy(Space* home, bool share) {
00208     return new (home) ReEqBin<Val,A,B,Ctrl>(home,share,*this);
00209   }
00210 
00211 
00212   template <class Val, class A, class B, class Ctrl>
00213   ExecStatus
00214   ReEqBin<Val,A,B,Ctrl>::propagate(Space* home) {
00215     if (b.zero())
00216       return (NqBin<Val,A,B>::post(home,x0,x1,c) == ES_FAILED) ?
00217         ES_FAILED : ES_SUBSUMED;
00218     if (b.one())
00219       return (EqBin<Val,A,B>::post(home,x0,x1,c) == ES_FAILED) ?
00220         ES_FAILED : ES_SUBSUMED;
00221     if ((x0.min() + x1.min() > c) || (x0.max() + x1.max() < c)) {
00222       b.t_zero_none(home); return ES_SUBSUMED;
00223     }
00224     if (x0.assigned() && x1.assigned()) {
00225       assert(x0.val() + x1.val() == c);
00226       b.t_one_none(home); return ES_SUBSUMED;
00227     }
00228     return ES_FIX;
00229   }
00230 
00231 
00232 
00233 
00234   /*
00235    * Binary domain-consistent linear disequality
00236    *
00237    */
00238 
00239   template <class Val, class A, class B>
00240   forceinline
00241   NqBin<Val,A,B>::NqBin(Space* home, A x0, B x1, Val c)
00242     : LinBin<Val,A,B,PC_INT_VAL>(home,x0,x1,c) {}
00243 
00244   template <class Val, class A, class B>
00245   ExecStatus
00246   NqBin<Val,A,B>::post(Space* home, A x0, B x1, Val c) {
00247     (void) new (home) NqBin<Val,A,B>(home,x0,x1,c);
00248     return ES_OK;
00249   }
00250 
00251 
00252   template <class Val, class A, class B>
00253   forceinline
00254   NqBin<Val,A,B>::NqBin(Space* home, bool share, NqBin<Val,A,B>& p)
00255     : LinBin<Val,A,B,PC_INT_VAL>(home,share,p) {}
00256 
00257   template <class Val, class A, class B>
00258   Actor*
00259   NqBin<Val,A,B>::copy(Space* home, bool share) {
00260     return new (home) NqBin<Val,A,B>(home,share,*this);
00261   }
00262 
00263   template <class Val, class A, class B>
00264   forceinline
00265   NqBin<Val,A,B>::NqBin(Space* home, bool share, Propagator& p,
00266                         A x0, B x1, Val c)
00267     : LinBin<Val,A,B,PC_INT_VAL>(home,share,p,x0,x1,c) {}
00268 
00269 
00270 
00271   template <class Val, class A, class B>
00272   PropCost
00273   NqBin<Val,A,B>::cost(void) const {
00274     return PC_UNARY_LO;
00275   }
00276 
00277   template <class Val, class A, class B>
00278   ExecStatus
00279   NqBin<Val,A,B>::propagate(Space* home) {
00280     if (x0.assigned()) {
00281       GECODE_ME_CHECK(x1.nq(home,c-x0.val()));
00282     } else {
00283       assert(x1.assigned());
00284       GECODE_ME_CHECK(x0.nq(home,c-x1.val()));
00285     }
00286     return ES_SUBSUMED;
00287   }
00288 
00289 
00290 
00291 
00292   /*
00293    * Binary domain-consistent less equal
00294    *
00295    */
00296 
00297   template <class Val, class A, class B>
00298   forceinline
00299   LqBin<Val,A,B>::LqBin(Space* home, A x0, B x1, Val c)
00300     : LinBin<Val,A,B,PC_INT_BND>(home,x0,x1,c) {}
00301 
00302   template <class Val, class A, class B>
00303   ExecStatus
00304   LqBin<Val,A,B>::post(Space* home, A x0, B x1, Val c) {
00305     (void) new (home) LqBin<Val,A,B>(home,x0,x1,c);
00306     return ES_OK;
00307   }
00308 
00309 
00310   template <class Val, class A, class B>
00311   forceinline
00312   LqBin<Val,A,B>::LqBin(Space* home, bool share, LqBin<Val,A,B>& p)
00313     : LinBin<Val,A,B,PC_INT_BND>(home,share,p) {}
00314 
00315   template <class Val, class A, class B>
00316   Actor*
00317   LqBin<Val,A,B>::copy(Space* home, bool share) {
00318     return new (home) LqBin<Val,A,B>(home,share,*this);
00319   }
00320 
00321   template <class Val, class A, class B>
00322   forceinline
00323   LqBin<Val,A,B>::LqBin(Space* home, bool share, Propagator& p,
00324                         A x0, B x1, Val c)
00325     : LinBin<Val,A,B,PC_INT_BND>(home,share,p,x0,x1,c) {}
00326 
00327 
00328 
00329   template <class Val, class A, class B>
00330   ExecStatus
00331   LqBin<Val,A,B>::propagate(Space* home) {
00332     GECODE_ME_CHECK(x0.lq(home,c-x1.min()));
00333     GECODE_ME_CHECK(x1.lq(home,c-x0.min()));
00334     return (x0.max()+x1.max() <= c) ? ES_SUBSUMED : ES_FIX;
00335   }
00336 
00337 
00338 
00339 
00340   /*
00341    * Binary domain-consistent greater equal
00342    *
00343    */
00344 
00345   template <class Val, class A, class B>
00346   forceinline
00347   GqBin<Val,A,B>::GqBin(Space* home, A x0, B x1, Val c)
00348     : LinBin<Val,A,B,PC_INT_BND>(home,x0,x1,c) {}
00349 
00350   template <class Val, class A, class B>
00351   ExecStatus
00352   GqBin<Val,A,B>::post(Space* home, A x0, B x1, Val c) {
00353     (void) new (home) GqBin<Val,A,B>(home,x0,x1,c);
00354     return ES_OK;
00355   }
00356 
00357 
00358   template <class Val, class A, class B>
00359   forceinline
00360   GqBin<Val,A,B>::GqBin(Space* home, bool share, GqBin<Val,A,B>& p)
00361     : LinBin<Val,A,B,PC_INT_BND>(home,share,p) {}
00362 
00363   template <class Val, class A, class B>
00364   Actor*
00365   GqBin<Val,A,B>::copy(Space* home, bool share) {
00366     return new (home) GqBin<Val,A,B>(home,share,*this);
00367   }
00368 
00369   template <class Val, class A, class B>
00370   forceinline
00371   GqBin<Val,A,B>::GqBin(Space* home, bool share, Propagator& p,
00372                         A x0, B x1, Val c)
00373     : LinBin<Val,A,B,PC_INT_BND>(home,share,p,x0,x1,c) {}
00374 
00375 
00376 
00377   template <class Val, class A, class B>
00378   ExecStatus
00379   GqBin<Val,A,B>::propagate(Space* home) {
00380     GECODE_ME_CHECK(x0.gq(home,c-x1.max()));
00381     GECODE_ME_CHECK(x1.gq(home,c-x0.max()));
00382     return (x0.min()+x1.min() >= c) ? ES_SUBSUMED : ES_FIX;
00383   }
00384 
00385 
00386 
00387 
00388   /*
00389    * Refied binary domain-consistent less equal
00390    *
00391    */
00392 
00393   template <class Val, class A, class B>
00394   forceinline
00395   ReLqBin<Val,A,B>::ReLqBin(Space* home, A x0, B x1, Val c, BoolView b)
00396     : ReLinBin<Val,A,B,PC_INT_BND,BoolView>(home,x0,x1,c,b) {}
00397 
00398   template <class Val, class A, class B>
00399   ExecStatus
00400   ReLqBin<Val,A,B>::post(Space* home, A x0, B x1, Val c, BoolView b) {
00401     (void) new (home) ReLqBin<Val,A,B>(home,x0,x1,c,b);
00402     return ES_OK;
00403   }
00404 
00405 
00406   template <class Val, class A, class B>
00407   forceinline
00408   ReLqBin<Val,A,B>::ReLqBin(Space* home, bool share, ReLqBin<Val,A,B>& p)
00409     : ReLinBin<Val,A,B,PC_INT_BND,BoolView>(home,share,p) {}
00410 
00411   template <class Val, class A, class B>
00412   Actor*
00413   ReLqBin<Val,A,B>::copy(Space* home, bool share) {
00414     return new (home) ReLqBin<Val,A,B>(home,share,*this);
00415   }
00416 
00417 
00418   template <class Val, class A, class B>
00419   ExecStatus
00420   ReLqBin<Val,A,B>::propagate(Space* home) {
00421     if (b.one())
00422       return (LqBin<Val,A,B>::post(home,x0,x1,c) == ES_FAILED) ?
00423         ES_FAILED : ES_SUBSUMED;
00424     if (b.zero())
00425       return (GqBin<Val,A,B>::post(home,x0,x1,c+1) == ES_FAILED) ?
00426         ES_FAILED : ES_SUBSUMED;
00427     if (x0.max() + x1.max() <= c) {
00428       b.t_one_none(home); return ES_SUBSUMED;
00429     }
00430     if (x0.min() + x1.min() > c) {
00431       b.t_zero_none(home); return ES_SUBSUMED;
00432     }
00433     return ES_FIX;
00434   }
00435 
00436 }}}
00437 
00438 // STATISTICS: int-prop
00439