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

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: 2005-08-05 23:04:58 +0200 (Fri, 05 Aug 2005) $ by $Author: schulte $
00010  *     $Revision: 2152 $
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   PropCost
00049   LinTer<Val,A,B,C,pc>::cost(void) const {
00050     return PC_TERNARY_LO;
00051   }
00052 
00053   template <class Val, class A, class B, class C, PropCond pc>
00054   inline
00055   LinTer<Val,A,B,C,pc>::~LinTer(void) {
00056     x0.cancel(this,pc); 
00057     x1.cancel(this,pc); 
00058     x2.cancel(this,pc);
00059   }
00060 
00061   /*
00062    * Equality propagator
00063    *
00064    */
00065 
00066   template <class Val, class A, class B, class C>
00067   forceinline
00068   EqTer<Val,A,B,C>::EqTer(Space* home, A x0, B x1, C x2, Val c)
00069     : LinTer<Val,A,B,C,PC_INT_BND>(home,x0,x1,x2,c) {}
00070 
00071   template <class Val, class A, class B, class C>
00072   ExecStatus
00073   EqTer<Val,A,B,C>::post(Space* home, A x0, B x1, C x2, Val c) {
00074     (void) new (home) EqTer<Val,A,B,C>(home,x0,x1,x2,c);
00075     return ES_OK;
00076   }
00077 
00078 
00079   template <class Val, class A, class B, class C>
00080   forceinline
00081   EqTer<Val,A,B,C>::EqTer(Space* home, bool share, EqTer<Val,A,B,C>& p)
00082     : LinTer<Val,A,B,C,PC_INT_BND>(home,share,p) {}
00083 
00084   template <class Val, class A, class B, class C>
00085   Actor*
00086   EqTer<Val,A,B,C>::copy(Space* home, bool share) {
00087     return new (home) EqTer<Val,A,B,C>(home,share,*this);
00088   }
00089 
00090 #define BM_X0_MIN 1
00091 #define BM_X0_MAX 2
00092 #define BM_X1_MIN 4
00093 #define BM_X1_MAX 8
00094 #define BM_X2_MIN 16
00095 #define BM_X2_MAX 32
00096 #define BM_ALL (BM_X0_MIN|BM_X0_MAX|BM_X1_MIN|BM_X1_MAX|BM_X2_MIN|BM_X2_MAX)
00097 
00098 #define PV(CASE,TELL,UPDATE)                    \
00099   if (bm & (CASE)) {                            \
00100     bm -= (CASE);                               \
00101     ModEvent me = (TELL);                       \
00102     if (me_failed(me))   return ES_FAILED;      \
00103     if (me_modified(me)) bm |= (UPDATE);        \
00104   }
00105 
00106   template <class Val, class A, class B, class C>
00107   ExecStatus
00108   EqTer<Val,A,B,C>::propagate(Space* home) {
00109     int bm = BM_ALL;
00110     do {
00111       PV(BM_X0_MIN, x0.gq(home,c-x1.max()-x2.max()), BM_X1_MAX | BM_X2_MAX);
00112       PV(BM_X1_MIN, x1.gq(home,c-x0.max()-x2.max()), BM_X0_MAX | BM_X2_MAX);
00113       PV(BM_X2_MIN, x2.gq(home,c-x0.max()-x1.max()), BM_X0_MAX | BM_X1_MAX);
00114       PV(BM_X0_MAX, x0.lq(home,c-x1.min()-x2.min()), BM_X1_MIN | BM_X2_MIN);
00115       PV(BM_X1_MAX, x1.lq(home,c-x0.min()-x2.min()), BM_X0_MIN | BM_X2_MIN);
00116       PV(BM_X2_MAX, x2.lq(home,c-x0.min()-x1.min()), BM_X0_MIN | BM_X1_MIN);
00117     } while (bm);
00118     return (x0.assigned() && x1.assigned()) ? ES_SUBSUMED : ES_FIX;
00119   }
00120 
00121 #undef BM_X0_MIN
00122 #undef BM_X0_MAX
00123 #undef BM_X1_MIN
00124 #undef BM_X1_MAX
00125 #undef BM_X2_MIN
00126 #undef BM_X2_MAX
00127 #undef BM_ALL
00128 
00129 #undef PV
00130 
00131 
00132 
00133   /*
00134    * Disequality propagator
00135    *
00136    */
00137 
00138   template <class Val, class A, class B, class C>
00139   forceinline
00140   NqTer<Val,A,B,C>::NqTer(Space* home, A x0, B x1, C x2, Val c)
00141     : LinTer<Val,A,B,C,PC_INT_VAL>(home,x0,x1,x2,c) {}
00142 
00143   template <class Val, class A, class B, class C>
00144   ExecStatus
00145   NqTer<Val,A,B,C>::post(Space* home, A x0, B x1, C x2, Val c) {
00146     (void) new (home) NqTer<Val,A,B,C>(home,x0,x1,x2,c);
00147     return ES_OK;
00148   }
00149 
00150 
00151   template <class Val, class A, class B, class C>
00152   forceinline
00153   NqTer<Val,A,B,C>::NqTer(Space* home, bool share, NqTer<Val,A,B,C>& p)
00154     : LinTer<Val,A,B,C,PC_INT_VAL>(home,share,p) {}
00155 
00156   template <class Val, class A, class B, class C>
00157   Actor*
00158   NqTer<Val,A,B,C>::copy(Space* home, bool share) {
00159     return new (home) NqTer<Val,A,B,C>(home,share,*this);
00160   }
00161 
00162 
00163   template <class Val, class A, class B, class C>
00164   ExecStatus
00165   NqTer<Val,A,B,C>::propagate(Space* home) {
00166     if (x0.assigned() && x1.assigned()) {
00167       GECODE_ME_CHECK(x2.nq(home,c-x0.val()-x1.val()));
00168       return ES_SUBSUMED;
00169     }
00170     if (x0.assigned() && x2.assigned()) {
00171       GECODE_ME_CHECK(x1.nq(home,c-x0.val()-x2.val()));
00172       return ES_SUBSUMED;
00173     }
00174     if (x1.assigned() && x2.assigned()) {
00175       GECODE_ME_CHECK(x0.nq(home,c-x1.val()-x2.val()));
00176       return ES_SUBSUMED;
00177     }
00178     return ES_FIX;
00179   }
00180 
00181 
00182 
00183   /*
00184    * Inequality propagator
00185    *
00186    */
00187 
00188   template <class Val, class A, class B, class C>
00189   forceinline
00190   LqTer<Val,A,B,C>::LqTer(Space* home, A x0, B x1, C x2, Val c)
00191     : LinTer<Val,A,B,C,PC_INT_BND>(home,x0,x1,x2,c) {}
00192 
00193   template <class Val, class A, class B, class C>
00194   ExecStatus
00195   LqTer<Val,A,B,C>::post(Space* home, A x0, B x1, C x2, Val c) {
00196     (void) new (home) LqTer<Val,A,B,C>(home,x0,x1,x2,c);
00197     return ES_OK;
00198   }
00199 
00200 
00201   template <class Val, class A, class B, class C>
00202   forceinline
00203   LqTer<Val,A,B,C>::LqTer(Space* home, bool share, LqTer<Val,A,B,C>& p)
00204     : LinTer<Val,A,B,C,PC_INT_BND>(home,share,p) {}
00205 
00206   template <class Val, class A, class B, class C>
00207   Actor*
00208   LqTer<Val,A,B,C>::copy(Space* home, bool share) {
00209     return new (home) LqTer<Val,A,B,C>(home,share,*this);
00210   }
00211 
00212   template <class Val, class A, class B, class C>
00213   ExecStatus
00214   LqTer<Val,A,B,C>::propagate(Space* home) {
00215     GECODE_ME_CHECK(x0.lq(home,c-x1.min()-x2.min()));
00216     GECODE_ME_CHECK(x1.lq(home,c-x0.min()-x2.min()));
00217     GECODE_ME_CHECK(x2.lq(home,c-x0.min()-x1.min()));
00218     return (x0.max()+x1.max()+x2.max() <= c) ? ES_SUBSUMED : ES_FIX;
00219   }
00220 
00221 }}}
00222 
00223 // STATISTICS: int-prop
00224