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

ternary.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    * Ternary linear propagators
00026    *
00027    */
00028   template <class Val, class A, class B, class C, PropCond pc>
00029   forceinline
00030   LinTer<Val,A,B,C,pc>::LinTer(Space* home, A y0, B y1, C y2, Val c0)
00031     : Propagator(home), x0(y0), x1(y1), x2(y2), c(c0) {
00032     x0.subscribe(home,this,pc); 
00033     x1.subscribe(home,this,pc); 
00034     x2.subscribe(home,this,pc);
00035   }
00036 
00037   template <class Val, class A, class B, class C, PropCond pc>
00038   forceinline
00039   LinTer<Val,A,B,C,pc>::LinTer(Space* home, bool share,
00040                                LinTer<Val,A,B,C,pc>& p)
00041     : Propagator(home,share,p), c(p.c) {
00042     x0.update(home,share,p.x0);
00043     x1.update(home,share,p.x1);
00044     x2.update(home,share,p.x2);
00045   }
00046 
00047   template <class Val, class A, class B, class C, PropCond pc>
00048   forceinline
00049   LinTer<Val,A,B,C,pc>::LinTer(Space* home, bool share, Propagator& p,
00050                                A y0, B y1, C y2, Val c0)
00051     : Propagator(home,share,p), c(c0) {
00052     x0.update(home,share,y0);
00053     x1.update(home,share,y1);
00054     x2.update(home,share,y2);
00055   }
00056 
00057   template <class Val, class A, class B, class C, PropCond pc>
00058   PropCost
00059   LinTer<Val,A,B,C,pc>::cost(void) const {
00060     return PC_TERNARY_LO;
00061   }
00062 
00063   template <class Val, class A, class B, class C, PropCond pc>
00064   size_t
00065   LinTer<Val,A,B,C,pc>::dispose(Space* home) {
00066     assert(!home->failed());
00067     x0.cancel(home,this,pc); 
00068     x1.cancel(home,this,pc); 
00069     x2.cancel(home,this,pc);
00070     (void) Propagator::dispose(home);
00071     return sizeof(*this);
00072   }
00073 
00074   /*
00075    * Equality propagator
00076    *
00077    */
00078 
00079   template <class Val, class A, class B, class C>
00080   forceinline
00081   EqTer<Val,A,B,C>::EqTer(Space* home, A x0, B x1, C x2, Val c)
00082     : LinTer<Val,A,B,C,PC_INT_BND>(home,x0,x1,x2,c) {}
00083 
00084   template <class Val, class A, class B, class C>
00085   ExecStatus
00086   EqTer<Val,A,B,C>::post(Space* home, A x0, B x1, C x2, Val c) {
00087     (void) new (home) EqTer<Val,A,B,C>(home,x0,x1,x2,c);
00088     return ES_OK;
00089   }
00090 
00091 
00092   template <class Val, class A, class B, class C>
00093   forceinline
00094   EqTer<Val,A,B,C>::EqTer(Space* home, bool share, EqTer<Val,A,B,C>& p)
00095     : LinTer<Val,A,B,C,PC_INT_BND>(home,share,p) {}
00096 
00097   template <class Val, class A, class B, class C>
00098   forceinline
00099   EqTer<Val,A,B,C>::EqTer(Space* home, bool share, Propagator& p,
00100                           A x0, B x1, C x2, Val c)
00101     : LinTer<Val,A,B,C,PC_INT_BND>(home,share,p,x0,x1,x2,c) {}
00102 
00103   template <class Val, class A, class B, class C>
00104   Actor*
00105   EqTer<Val,A,B,C>::copy(Space* home, bool share) {
00106     return new (home) EqTer<Val,A,B,C>(home,share,*this);
00107   }
00108 
00109 #define BM_X0_MIN 1
00110 #define BM_X0_MAX 2
00111 #define BM_X1_MIN 4
00112 #define BM_X1_MAX 8
00113 #define BM_X2_MIN 16
00114 #define BM_X2_MAX 32
00115 #define BM_ALL (BM_X0_MIN|BM_X0_MAX|BM_X1_MIN|BM_X1_MAX|BM_X2_MIN|BM_X2_MAX)
00116 
00117 #define PV(CASE,TELL,UPDATE)                    \
00118   if (bm & (CASE)) {                            \
00119     bm -= (CASE);                               \
00120     ModEvent me = (TELL);                       \
00121     if (me_failed(me))   return ES_FAILED;      \
00122     if (me_modified(me)) bm |= (UPDATE);        \
00123   }
00124 
00125   template <class Val, class A, class B, class C>
00126   ExecStatus
00127   EqTer<Val,A,B,C>::propagate(Space* home) {
00128     int bm = BM_ALL;
00129     do {
00130       PV(BM_X0_MIN, x0.gq(home,c-x1.max()-x2.max()), BM_X1_MAX | BM_X2_MAX);
00131       PV(BM_X1_MIN, x1.gq(home,c-x0.max()-x2.max()), BM_X0_MAX | BM_X2_MAX);
00132       PV(BM_X2_MIN, x2.gq(home,c-x0.max()-x1.max()), BM_X0_MAX | BM_X1_MAX);
00133       PV(BM_X0_MAX, x0.lq(home,c-x1.min()-x2.min()), BM_X1_MIN | BM_X2_MIN);
00134       PV(BM_X1_MAX, x1.lq(home,c-x0.min()-x2.min()), BM_X0_MIN | BM_X2_MIN);
00135       PV(BM_X2_MAX, x2.lq(home,c-x0.min()-x1.min()), BM_X0_MIN | BM_X1_MIN);
00136     } while (bm);
00137     return (x0.assigned() && x1.assigned()) ? ES_SUBSUMED : ES_FIX;
00138   }
00139 
00140 #undef BM_X0_MIN
00141 #undef BM_X0_MAX
00142 #undef BM_X1_MIN
00143 #undef BM_X1_MAX
00144 #undef BM_X2_MIN
00145 #undef BM_X2_MAX
00146 #undef BM_ALL
00147 
00148 #undef PV
00149 
00150 
00151 
00152   /*
00153    * Disequality propagator
00154    *
00155    */
00156 
00157   template <class Val, class A, class B, class C>
00158   forceinline
00159   NqTer<Val,A,B,C>::NqTer(Space* home, A x0, B x1, C x2, Val c)
00160     : LinTer<Val,A,B,C,PC_INT_VAL>(home,x0,x1,x2,c) {}
00161 
00162   template <class Val, class A, class B, class C>
00163   ExecStatus
00164   NqTer<Val,A,B,C>::post(Space* home, A x0, B x1, C x2, Val c) {
00165     (void) new (home) NqTer<Val,A,B,C>(home,x0,x1,x2,c);
00166     return ES_OK;
00167   }
00168 
00169 
00170   template <class Val, class A, class B, class C>
00171   forceinline
00172   NqTer<Val,A,B,C>::NqTer(Space* home, bool share, NqTer<Val,A,B,C>& p)
00173     : LinTer<Val,A,B,C,PC_INT_VAL>(home,share,p) {}
00174 
00175   template <class Val, class A, class B, class C>
00176   Actor*
00177   NqTer<Val,A,B,C>::copy(Space* home, bool share) {
00178     return new (home) NqTer<Val,A,B,C>(home,share,*this);
00179   }
00180 
00181   template <class Val, class A, class B, class C>
00182   forceinline
00183   NqTer<Val,A,B,C>::NqTer(Space* home, bool share, Propagator& p,
00184                           A x0, B x1, C x2, Val c)
00185     : LinTer<Val,A,B,C,PC_INT_VAL>(home,share,p,x0,x1,x2,c) {}
00186 
00187 
00188   template <class Val, class A, class B, class C>
00189   ExecStatus
00190   NqTer<Val,A,B,C>::propagate(Space* home) {
00191     if (x0.assigned() && x1.assigned()) {
00192       GECODE_ME_CHECK(x2.nq(home,c-x0.val()-x1.val()));
00193       return ES_SUBSUMED;
00194     }
00195     if (x0.assigned() && x2.assigned()) {
00196       GECODE_ME_CHECK(x1.nq(home,c-x0.val()-x2.val()));
00197       return ES_SUBSUMED;
00198     }
00199     if (x1.assigned() && x2.assigned()) {
00200       GECODE_ME_CHECK(x0.nq(home,c-x1.val()-x2.val()));
00201       return ES_SUBSUMED;
00202     }
00203     return ES_FIX;
00204   }
00205 
00206 
00207 
00208   /*
00209    * Inequality propagator
00210    *
00211    */
00212 
00213   template <class Val, class A, class B, class C>
00214   forceinline
00215   LqTer<Val,A,B,C>::LqTer(Space* home, A x0, B x1, C x2, Val c)
00216     : LinTer<Val,A,B,C,PC_INT_BND>(home,x0,x1,x2,c) {}
00217 
00218   template <class Val, class A, class B, class C>
00219   ExecStatus
00220   LqTer<Val,A,B,C>::post(Space* home, A x0, B x1, C x2, Val c) {
00221     (void) new (home) LqTer<Val,A,B,C>(home,x0,x1,x2,c);
00222     return ES_OK;
00223   }
00224 
00225 
00226   template <class Val, class A, class B, class C>
00227   forceinline
00228   LqTer<Val,A,B,C>::LqTer(Space* home, bool share, LqTer<Val,A,B,C>& p)
00229     : LinTer<Val,A,B,C,PC_INT_BND>(home,share,p) {}
00230 
00231   template <class Val, class A, class B, class C>
00232   Actor*
00233   LqTer<Val,A,B,C>::copy(Space* home, bool share) {
00234     return new (home) LqTer<Val,A,B,C>(home,share,*this);
00235   }
00236 
00237   template <class Val, class A, class B, class C>
00238   forceinline
00239   LqTer<Val,A,B,C>::LqTer(Space* home, bool share, Propagator& p,
00240                           A x0, B x1, C x2, Val c)
00241     : LinTer<Val,A,B,C,PC_INT_BND>(home,share,p,x0,x1,x2,c) {}
00242 
00243   template <class Val, class A, class B, class C>
00244   ExecStatus
00245   LqTer<Val,A,B,C>::propagate(Space* home) {
00246     GECODE_ME_CHECK(x0.lq(home,c-x1.min()-x2.min()));
00247     GECODE_ME_CHECK(x1.lq(home,c-x0.min()-x2.min()));
00248     GECODE_ME_CHECK(x2.lq(home,c-x0.min()-x1.min()));
00249     return (x0.max()+x1.max()+x2.max() <= c) ? ES_SUBSUMED : ES_FIX;
00250   }
00251 
00252 }}}
00253 
00254 // STATISTICS: int-prop
00255