Generated on Thu Jul 6 07:06:45 2006 for Gecode by doxygen 1.4.7

binary.icc

Go to the documentation of this file.
00001 /*
00002  *  Main authors:
00003  *     Christian Schulte <schulte@gecode.org>
00004  *
00005  *  Copyright:
00006  *     Christian Schulte, 2003
00007  *
00008  *  Last modified:
00009  *     $Date: 2006-05-29 09:42:21 +0200 (Mon, 29 May 2006) $ by $Author: schulte $
00010  *     $Revision: 3246 $
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 
00146 
00147 #define BM_X0_MIN 1
00148 #define BM_X0_MAX 2
00149 #define BM_X1_MIN 4
00150 #define BM_X1_MAX 8
00151 #define BM_ALL    (BM_X0_MIN|BM_X0_MAX|BM_X1_MIN|BM_X1_MAX)
00152 
00153 #define PV(CASE,TELL,UPDATE)                    \
00154   if (bm & (CASE)) {                            \
00155     bm -= (CASE);                               \
00156     ModEvent me = (TELL);                       \
00157     if (me_failed(me))    return ES_FAILED;     \
00158     if (me_modified(me)) bm |= (UPDATE);        \
00159   }
00160 
00161   template <class Val, class A, class B>
00162   ExecStatus
00163   EqBin<Val,A,B>::propagate(Space* home) {
00164     int bm = BM_ALL;
00165     do {
00166       PV(BM_X0_MIN, x0.gq(home,c-x1.max()), BM_X1_MAX);
00167       PV(BM_X1_MIN, x1.gq(home,c-x0.max()), BM_X0_MAX);
00168       PV(BM_X0_MAX, x0.lq(home,c-x1.min()), BM_X1_MIN);
00169       PV(BM_X1_MAX, x1.lq(home,c-x0.min()), BM_X0_MIN);
00170     } while (bm);
00171     return x0.assigned() ? ES_SUBSUMED : ES_FIX;
00172   }
00173 
00174 #undef BM_X0_MIN
00175 #undef BM_X0_MAX
00176 #undef BM_X1_MIN
00177 #undef BM_X1_MAX
00178 #undef BM_ALL
00179 
00180 #undef PV
00181 
00182 
00183 
00184 
00185 
00186   /*
00187    * Reified binary bounds-consistent linear equality
00188    *
00189    */
00190 
00191   template <class Val, class A, class B, class Ctrl>
00192   forceinline
00193   ReEqBin<Val,A,B,Ctrl>::ReEqBin(Space* home, A x0, B x1, Val c, Ctrl b)
00194     : ReLinBin<Val,A,B,PC_INT_BND,Ctrl>(home,x0,x1,c,b) {}
00195 
00196   template <class Val, class A, class B, class Ctrl>
00197   ExecStatus
00198   ReEqBin<Val,A,B,Ctrl>::post(Space* home, A x0, B x1, Val c, Ctrl b) {
00199     (void) new (home) ReEqBin<Val,A,B,Ctrl>(home,x0,x1,c,b);
00200     return ES_OK;
00201   }
00202 
00203 
00204   template <class Val, class A, class B, class Ctrl>
00205   forceinline
00206   ReEqBin<Val,A,B,Ctrl>::ReEqBin(Space* home, bool share, 
00207                                  ReEqBin<Val,A,B,Ctrl>& p)
00208     : ReLinBin<Val,A,B,PC_INT_BND,Ctrl>(home,share,p) {}
00209 
00210   template <class Val, class A, class B, class Ctrl>
00211   Actor*
00212   ReEqBin<Val,A,B,Ctrl>::copy(Space* home, bool share) {
00213     return new (home) ReEqBin<Val,A,B,Ctrl>(home,share,*this);
00214   }
00215 
00216 
00217   template <class Val, class A, class B, class Ctrl>
00218   ExecStatus
00219   ReEqBin<Val,A,B,Ctrl>::propagate(Space* home) {
00220     if (b.zero())
00221       return (NqBin<Val,A,B>::post(home,x0,x1,c) == ES_FAILED) ?
00222         ES_FAILED : ES_SUBSUMED;
00223     if (b.one())
00224       return (EqBin<Val,A,B>::post(home,x0,x1,c) == ES_FAILED) ?
00225         ES_FAILED : ES_SUBSUMED;
00226     if ((x0.min() + x1.min() > c) || (x0.max() + x1.max() < c)) {
00227       b.t_zero_none(home); return ES_SUBSUMED;
00228     }
00229     if (x0.assigned() && x1.assigned()) {
00230       assert(x0.val() + x1.val() == c);
00231       b.t_one_none(home); return ES_SUBSUMED;
00232     }
00233     return ES_FIX;
00234   }
00235 
00236 
00237 
00238 
00239   /*
00240    * Binary domain-consistent linear disequality
00241    *
00242    */
00243 
00244   template <class Val, class A, class B>
00245   forceinline
00246   NqBin<Val,A,B>::NqBin(Space* home, A x0, B x1, Val c)
00247     : LinBin<Val,A,B,PC_INT_VAL>(home,x0,x1,c) {}
00248 
00249   template <class Val, class A, class B>
00250   ExecStatus
00251   NqBin<Val,A,B>::post(Space* home, A x0, B x1, Val c) {
00252     (void) new (home) NqBin<Val,A,B>(home,x0,x1,c);
00253     return ES_OK;
00254   }
00255 
00256 
00257   template <class Val, class A, class B>
00258   forceinline
00259   NqBin<Val,A,B>::NqBin(Space* home, bool share, NqBin<Val,A,B>& p)
00260     : LinBin<Val,A,B,PC_INT_VAL>(home,share,p) {}
00261 
00262   template <class Val, class A, class B>
00263   Actor*
00264   NqBin<Val,A,B>::copy(Space* home, bool share) {
00265     return new (home) NqBin<Val,A,B>(home,share,*this);
00266   }
00267 
00268   template <class Val, class A, class B>
00269   forceinline
00270   NqBin<Val,A,B>::NqBin(Space* home, bool share, Propagator& p,
00271                         A x0, B x1, Val c)
00272     : LinBin<Val,A,B,PC_INT_VAL>(home,share,p,x0,x1,c) {}
00273 
00274 
00275 
00276   template <class Val, class A, class B>
00277   PropCost
00278   NqBin<Val,A,B>::cost(void) const {
00279     return PC_UNARY_LO;
00280   }
00281 
00282   template <class Val, class A, class B>
00283   ExecStatus
00284   NqBin<Val,A,B>::propagate(Space* home) {
00285     if (x0.assigned()) {
00286       GECODE_ME_CHECK(x1.nq(home,c-x0.val()));
00287     } else {
00288       assert(x1.assigned());
00289       GECODE_ME_CHECK(x0.nq(home,c-x1.val()));
00290     }
00291     return ES_SUBSUMED;
00292   }
00293 
00294 
00295 
00296 
00297   /*
00298    * Binary domain-consistent less equal
00299    *
00300    */
00301 
00302   template <class Val, class A, class B>
00303   forceinline
00304   LqBin<Val,A,B>::LqBin(Space* home, A x0, B x1, Val c)
00305     : LinBin<Val,A,B,PC_INT_BND>(home,x0,x1,c) {}
00306 
00307   template <class Val, class A, class B>
00308   ExecStatus
00309   LqBin<Val,A,B>::post(Space* home, A x0, B x1, Val c) {
00310     (void) new (home) LqBin<Val,A,B>(home,x0,x1,c);
00311     return ES_OK;
00312   }
00313 
00314 
00315   template <class Val, class A, class B>
00316   forceinline
00317   LqBin<Val,A,B>::LqBin(Space* home, bool share, LqBin<Val,A,B>& p)
00318     : LinBin<Val,A,B,PC_INT_BND>(home,share,p) {}
00319 
00320   template <class Val, class A, class B>
00321   Actor*
00322   LqBin<Val,A,B>::copy(Space* home, bool share) {
00323     return new (home) LqBin<Val,A,B>(home,share,*this);
00324   }
00325 
00326   template <class Val, class A, class B>
00327   forceinline
00328   LqBin<Val,A,B>::LqBin(Space* home, bool share, Propagator& p,
00329                         A x0, B x1, Val c)
00330     : LinBin<Val,A,B,PC_INT_BND>(home,share,p,x0,x1,c) {}
00331 
00332 
00333 
00334   template <class Val, class A, class B>
00335   ExecStatus
00336   LqBin<Val,A,B>::propagate(Space* home) {
00337     GECODE_ME_CHECK(x0.lq(home,c-x1.min()));
00338     GECODE_ME_CHECK(x1.lq(home,c-x0.min()));
00339     return (x0.max()+x1.max() <= c) ? ES_SUBSUMED : ES_FIX;
00340   }
00341 
00342 
00343 
00344 
00345   /*
00346    * Binary domain-consistent greater equal
00347    *
00348    */
00349 
00350   template <class Val, class A, class B>
00351   forceinline
00352   GqBin<Val,A,B>::GqBin(Space* home, A x0, B x1, Val c)
00353     : LinBin<Val,A,B,PC_INT_BND>(home,x0,x1,c) {}
00354 
00355   template <class Val, class A, class B>
00356   ExecStatus
00357   GqBin<Val,A,B>::post(Space* home, A x0, B x1, Val c) {
00358     (void) new (home) GqBin<Val,A,B>(home,x0,x1,c);
00359     return ES_OK;
00360   }
00361 
00362 
00363   template <class Val, class A, class B>
00364   forceinline
00365   GqBin<Val,A,B>::GqBin(Space* home, bool share, GqBin<Val,A,B>& p)
00366     : LinBin<Val,A,B,PC_INT_BND>(home,share,p) {}
00367 
00368   template <class Val, class A, class B>
00369   Actor*
00370   GqBin<Val,A,B>::copy(Space* home, bool share) {
00371     return new (home) GqBin<Val,A,B>(home,share,*this);
00372   }
00373 
00374   template <class Val, class A, class B>
00375   forceinline
00376   GqBin<Val,A,B>::GqBin(Space* home, bool share, Propagator& p,
00377                         A x0, B x1, Val c)
00378     : LinBin<Val,A,B,PC_INT_BND>(home,share,p,x0,x1,c) {}
00379 
00380 
00381 
00382   template <class Val, class A, class B>
00383   ExecStatus
00384   GqBin<Val,A,B>::propagate(Space* home) {
00385     GECODE_ME_CHECK(x0.gq(home,c-x1.max()));
00386     GECODE_ME_CHECK(x1.gq(home,c-x0.max()));
00387     return (x0.min()+x1.min() >= c) ? ES_SUBSUMED : ES_FIX;
00388   }
00389 
00390 
00391 
00392 
00393   /*
00394    * Refied binary domain-consistent less equal
00395    *
00396    */
00397 
00398   template <class Val, class A, class B>
00399   forceinline
00400   ReLqBin<Val,A,B>::ReLqBin(Space* home, A x0, B x1, Val c, BoolView b)
00401     : ReLinBin<Val,A,B,PC_INT_BND,BoolView>(home,x0,x1,c,b) {}
00402 
00403   template <class Val, class A, class B>
00404   ExecStatus
00405   ReLqBin<Val,A,B>::post(Space* home, A x0, B x1, Val c, BoolView b) {
00406     (void) new (home) ReLqBin<Val,A,B>(home,x0,x1,c,b);
00407     return ES_OK;
00408   }
00409 
00410 
00411   template <class Val, class A, class B>
00412   forceinline
00413   ReLqBin<Val,A,B>::ReLqBin(Space* home, bool share, ReLqBin<Val,A,B>& p)
00414     : ReLinBin<Val,A,B,PC_INT_BND,BoolView>(home,share,p) {}
00415 
00416   template <class Val, class A, class B>
00417   Actor*
00418   ReLqBin<Val,A,B>::copy(Space* home, bool share) {
00419     return new (home) ReLqBin<Val,A,B>(home,share,*this);
00420   }
00421 
00422 
00423   template <class Val, class A, class B>
00424   ExecStatus
00425   ReLqBin<Val,A,B>::propagate(Space* home) {
00426     if (b.one())
00427       return (LqBin<Val,A,B>::post(home,x0,x1,c) == ES_FAILED) ?
00428         ES_FAILED : ES_SUBSUMED;
00429     if (b.zero())
00430       return (GqBin<Val,A,B>::post(home,x0,x1,c+1) == ES_FAILED) ?
00431         ES_FAILED : ES_SUBSUMED;
00432     if (x0.max() + x1.max() <= c) {
00433       b.t_one_none(home); return ES_SUBSUMED;
00434     }
00435     if (x0.min() + x1.min() > c) {
00436       b.t_zero_none(home); return ES_SUBSUMED;
00437     }
00438     return ES_FIX;
00439   }
00440 
00441 }}}
00442 
00443 // STATISTICS: int-prop
00444