Generated on Wed Jan 4 17:49:10 2006 for Gecode by doxygen 1.4.6

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: 2005-11-01 16:35:02 +0100 (Tue, 01 Nov 2005) $ by $Author: schulte $
00010  *     $Revision: 2467 $
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   PropCost
00046   LinBin<Val,A,B,pc>::cost(void) const {
00047     return PC_BINARY_LO;
00048   }
00049 
00050   template <class Val, class A, class B, PropCond pc>
00051   inline
00052   LinBin<Val,A,B,pc>::~LinBin(void) {
00053     x0.cancel(this,pc); 
00054     x1.cancel(this,pc);
00055   }
00056 
00057 
00058   /*
00059    * Binary reified linear propagators
00060    *
00061    */
00062   template <class Val, class A, class B, PropCond pc, class Ctrl>
00063   forceinline
00064   ReLinBin<Val,A,B,pc,Ctrl>::ReLinBin(Space* home, A y0, B y1, Val c0, Ctrl b0)
00065     : Propagator(home), x0(y0), x1(y1), c(c0), b(b0) {
00066     x0.subscribe(home,this,pc); 
00067     x1.subscribe(home,this,pc);
00068     b.subscribe(home,this,PC_INT_VAL);
00069   }
00070 
00071   template <class Val, class A, class B, PropCond pc, class Ctrl>
00072   forceinline
00073   ReLinBin<Val,A,B,pc,Ctrl>::ReLinBin(Space* home, bool share,
00074                                       ReLinBin<Val,A,B,pc,Ctrl>& p)
00075     : Propagator(home,share,p), c(p.c) {
00076     x0.update(home,share,p.x0);
00077     x1.update(home,share,p.x1);
00078     b.update(home,share,p.b);
00079   }
00080 
00081   template <class Val, class A, class B, PropCond pc, class Ctrl>
00082   PropCost
00083   ReLinBin<Val,A,B,pc,Ctrl>::cost(void) const {
00084     return PC_BINARY_LO;
00085   }
00086 
00087   template <class Val, class A, class B, PropCond pc, class Ctrl>
00088   inline
00089   ReLinBin<Val,A,B,pc,Ctrl>::~ReLinBin(void) {
00090     x0.cancel(this,pc); 
00091     x1.cancel(this,pc);
00092     b.cancel(this,PC_INT_VAL);
00093   }
00094 
00095 
00096   /*
00097    * Binary bounds-consistent linear equality
00098    *
00099    */
00100 
00101   template <class Val, class A, class B>
00102   forceinline
00103   EqBin<Val,A,B>::EqBin(Space* home, A x0, B x1, Val c)
00104     : LinBin<Val,A,B,PC_INT_BND>(home,x0,x1,c) {}
00105 
00106   template <class Val, class A, class B>
00107   ExecStatus
00108   EqBin<Val,A,B>::post(Space* home, A x0, B x1, Val c) {
00109     (void) new (home) EqBin<Val,A,B>(home,x0,x1,c);
00110     return ES_OK;
00111   }
00112 
00113 
00114   template <class Val, class A, class B>
00115   forceinline
00116   EqBin<Val,A,B>::EqBin(Space* home, bool share, EqBin<Val,A,B>& p)
00117     : LinBin<Val,A,B,PC_INT_BND>(home,share,p) {}
00118 
00119   template <class Val, class A, class B>
00120   Actor*
00121   EqBin<Val,A,B>::copy(Space* home, bool share) {
00122     return new (home) EqBin<Val,A,B>(home,share,*this);
00123   }
00124 
00125 
00126 #define BM_X0_MIN 1
00127 #define BM_X0_MAX 2
00128 #define BM_X1_MIN 4
00129 #define BM_X1_MAX 8
00130 #define BM_ALL    (BM_X0_MIN|BM_X0_MAX|BM_X1_MIN|BM_X1_MAX)
00131 
00132 #define PV(CASE,TELL,UPDATE)                    \
00133   if (bm & (CASE)) {                            \
00134     bm -= (CASE);                               \
00135     ModEvent me = (TELL);                       \
00136     if (me_failed(me))    return ES_FAILED;     \
00137     if (me_modified(me)) bm |= (UPDATE);        \
00138   }
00139 
00140   template <class Val, class A, class B>
00141   ExecStatus
00142   EqBin<Val,A,B>::propagate(Space* home) {
00143     int bm = BM_ALL;
00144     do {
00145       PV(BM_X0_MIN, x0.gq(home,c-x1.max()), BM_X1_MAX);
00146       PV(BM_X1_MIN, x1.gq(home,c-x0.max()), BM_X0_MAX);
00147       PV(BM_X0_MAX, x0.lq(home,c-x1.min()), BM_X1_MIN);
00148       PV(BM_X1_MAX, x1.lq(home,c-x0.min()), BM_X0_MIN);
00149     } while (bm);
00150     return x0.assigned() ? ES_SUBSUMED : ES_FIX;
00151   }
00152 
00153 #undef BM_X0_MIN
00154 #undef BM_X0_MAX
00155 #undef BM_X1_MIN
00156 #undef BM_X1_MAX
00157 #undef BM_ALL
00158 
00159 #undef PV
00160 
00161 
00162 
00163 
00164 
00165   /*
00166    * Reified binary bounds-consistent linear equality
00167    *
00168    */
00169 
00170   template <class Val, class A, class B, class Ctrl>
00171   forceinline
00172   ReEqBin<Val,A,B,Ctrl>::ReEqBin(Space* home, A x0, B x1, Val c, Ctrl b)
00173     : ReLinBin<Val,A,B,PC_INT_BND,Ctrl>(home,x0,x1,c,b) {}
00174 
00175   template <class Val, class A, class B, class Ctrl>
00176   ExecStatus
00177   ReEqBin<Val,A,B,Ctrl>::post(Space* home, A x0, B x1, Val c, Ctrl b) {
00178     (void) new (home) ReEqBin<Val,A,B,Ctrl>(home,x0,x1,c,b);
00179     return ES_OK;
00180   }
00181 
00182 
00183   template <class Val, class A, class B, class Ctrl>
00184   forceinline
00185   ReEqBin<Val,A,B,Ctrl>::ReEqBin(Space* home, bool share, 
00186                                  ReEqBin<Val,A,B,Ctrl>& p)
00187     : ReLinBin<Val,A,B,PC_INT_BND,Ctrl>(home,share,p) {}
00188 
00189   template <class Val, class A, class B, class Ctrl>
00190   Actor*
00191   ReEqBin<Val,A,B,Ctrl>::copy(Space* home, bool share) {
00192     return new (home) ReEqBin<Val,A,B,Ctrl>(home,share,*this);
00193   }
00194 
00195 
00196   template <class Val, class A, class B, class Ctrl>
00197   ExecStatus
00198   ReEqBin<Val,A,B,Ctrl>::propagate(Space* home) {
00199     if (b.zero())
00200       return (NqBin<Val,A,B>::post(home,x0,x1,c) == ES_FAILED) ?
00201         ES_FAILED : ES_SUBSUMED;
00202     if (b.one())
00203       return (EqBin<Val,A,B>::post(home,x0,x1,c) == ES_FAILED) ?
00204         ES_FAILED : ES_SUBSUMED;
00205     if ((x0.min() + x1.min() > c) || (x0.max() + x1.max() < c)) {
00206       b.t_zero_none(home); return ES_SUBSUMED;
00207     }
00208     if (x0.assigned() && x1.assigned()) {
00209       assert(x0.val() + x1.val() == c);
00210       b.t_one_none(home); return ES_SUBSUMED;
00211     }
00212     return ES_FIX;
00213   }
00214 
00215 
00216 
00217 
00218   /*
00219    * Binary domain-consistent linear disequality
00220    *
00221    */
00222 
00223   template <class Val, class A, class B>
00224   forceinline
00225   NqBin<Val,A,B>::NqBin(Space* home, A x0, B x1, Val c)
00226     : LinBin<Val,A,B,PC_INT_VAL>(home,x0,x1,c) {}
00227 
00228   template <class Val, class A, class B>
00229   ExecStatus
00230   NqBin<Val,A,B>::post(Space* home, A x0, B x1, Val c) {
00231     (void) new (home) NqBin<Val,A,B>(home,x0,x1,c);
00232     return ES_OK;
00233   }
00234 
00235 
00236   template <class Val, class A, class B>
00237   forceinline
00238   NqBin<Val,A,B>::NqBin(Space* home, bool share, NqBin<Val,A,B>& p)
00239     : LinBin<Val,A,B,PC_INT_VAL>(home,share,p) {}
00240 
00241   template <class Val, class A, class B>
00242   Actor*
00243   NqBin<Val,A,B>::copy(Space* home, bool share) {
00244     return new (home) NqBin<Val,A,B>(home,share,*this);
00245   }
00246 
00247 
00248   template <class Val, class A, class B>
00249   PropCost
00250   NqBin<Val,A,B>::cost(void) const {
00251     return PC_UNARY_LO;
00252   }
00253 
00254   template <class Val, class A, class B>
00255   ExecStatus
00256   NqBin<Val,A,B>::propagate(Space* home) {
00257     if (x0.assigned()) {
00258       GECODE_ME_CHECK(x1.nq(home,c-x0.val()));
00259     } else {
00260       assert(x1.assigned());
00261       GECODE_ME_CHECK(x0.nq(home,c-x1.val()));
00262     }
00263     return ES_SUBSUMED;
00264   }
00265 
00266 
00267 
00268 
00269   /*
00270    * Binary domain-consistent less equal
00271    *
00272    */
00273 
00274   template <class Val, class A, class B>
00275   forceinline
00276   LqBin<Val,A,B>::LqBin(Space* home, A x0, B x1, Val c)
00277     : LinBin<Val,A,B,PC_INT_BND>(home,x0,x1,c) {}
00278 
00279   template <class Val, class A, class B>
00280   ExecStatus
00281   LqBin<Val,A,B>::post(Space* home, A x0, B x1, Val c) {
00282     (void) new (home) LqBin<Val,A,B>(home,x0,x1,c);
00283     return ES_OK;
00284   }
00285 
00286 
00287   template <class Val, class A, class B>
00288   forceinline
00289   LqBin<Val,A,B>::LqBin(Space* home, bool share, LqBin<Val,A,B>& p)
00290     : LinBin<Val,A,B,PC_INT_BND>(home,share,p) {}
00291 
00292   template <class Val, class A, class B>
00293   Actor*
00294   LqBin<Val,A,B>::copy(Space* home, bool share) {
00295     return new (home) LqBin<Val,A,B>(home,share,*this);
00296   }
00297 
00298 
00299   template <class Val, class A, class B>
00300   ExecStatus
00301   LqBin<Val,A,B>::propagate(Space* home) {
00302     GECODE_ME_CHECK(x0.lq(home,c-x1.min()));
00303     GECODE_ME_CHECK(x1.lq(home,c-x0.min()));
00304     return (x0.max()+x1.max() <= c) ? ES_SUBSUMED : ES_FIX;
00305   }
00306 
00307 
00308 
00309 
00310   /*
00311    * Binary domain-consistent greater equal
00312    *
00313    */
00314 
00315   template <class Val, class A, class B>
00316   forceinline
00317   GqBin<Val,A,B>::GqBin(Space* home, A x0, B x1, Val c)
00318     : LinBin<Val,A,B,PC_INT_BND>(home,x0,x1,c) {}
00319 
00320   template <class Val, class A, class B>
00321   ExecStatus
00322   GqBin<Val,A,B>::post(Space* home, A x0, B x1, Val c) {
00323     (void) new (home) GqBin<Val,A,B>(home,x0,x1,c);
00324     return ES_OK;
00325   }
00326 
00327 
00328   template <class Val, class A, class B>
00329   forceinline
00330   GqBin<Val,A,B>::GqBin(Space* home, bool share, GqBin<Val,A,B>& p)
00331     : LinBin<Val,A,B,PC_INT_BND>(home,share,p) {}
00332 
00333   template <class Val, class A, class B>
00334   Actor*
00335   GqBin<Val,A,B>::copy(Space* home, bool share) {
00336     return new (home) GqBin<Val,A,B>(home,share,*this);
00337   }
00338 
00339 
00340   template <class Val, class A, class B>
00341   ExecStatus
00342   GqBin<Val,A,B>::propagate(Space* home) {
00343     GECODE_ME_CHECK(x0.gq(home,c-x1.max()));
00344     GECODE_ME_CHECK(x1.gq(home,c-x0.max()));
00345     return (x0.min()+x1.min() >= c) ? ES_SUBSUMED : ES_FIX;
00346   }
00347 
00348 
00349 
00350 
00351   /*
00352    * Refied binary domain-consistent less equal
00353    *
00354    */
00355 
00356   template <class Val, class A, class B>
00357   forceinline
00358   ReLqBin<Val,A,B>::ReLqBin(Space* home, A x0, B x1, Val c, BoolView b)
00359     : ReLinBin<Val,A,B,PC_INT_BND,BoolView>(home,x0,x1,c,b) {}
00360 
00361   template <class Val, class A, class B>
00362   ExecStatus
00363   ReLqBin<Val,A,B>::post(Space* home, A x0, B x1, Val c, BoolView b) {
00364     (void) new (home) ReLqBin<Val,A,B>(home,x0,x1,c,b);
00365     return ES_OK;
00366   }
00367 
00368 
00369   template <class Val, class A, class B>
00370   forceinline
00371   ReLqBin<Val,A,B>::ReLqBin(Space* home, bool share, ReLqBin<Val,A,B>& p)
00372     : ReLinBin<Val,A,B,PC_INT_BND,BoolView>(home,share,p) {}
00373 
00374   template <class Val, class A, class B>
00375   Actor*
00376   ReLqBin<Val,A,B>::copy(Space* home, bool share) {
00377     return new (home) ReLqBin<Val,A,B>(home,share,*this);
00378   }
00379 
00380 
00381   template <class Val, class A, class B>
00382   ExecStatus
00383   ReLqBin<Val,A,B>::propagate(Space* home) {
00384     if (b.one())
00385       return (LqBin<Val,A,B>::post(home,x0,x1,c) == ES_FAILED) ?
00386         ES_FAILED : ES_SUBSUMED;
00387     if (b.zero())
00388       return (GqBin<Val,A,B>::post(home,x0,x1,c+1) == ES_FAILED) ?
00389         ES_FAILED : ES_SUBSUMED;
00390     if (x0.max() + x1.max() <= c) {
00391       b.t_one_none(home); return ES_SUBSUMED;
00392     }
00393     if (x0.min() + x1.min() > c) {
00394       b.t_zero_none(home); return ES_SUBSUMED;
00395     }
00396     return ES_FIX;
00397   }
00398 
00399 }}}
00400 
00401 // STATISTICS: int-prop
00402