int-ter.hpp

00001 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
00002 /*
00003  *  Main authors:
00004  *     Christian Schulte <schulte@gecode.org>
00005  *
00006  *  Copyright:
00007  *     Christian Schulte, 2003
00008  *
00009  *  Last modified:
00010  *     $Date: 2010-03-03 17:32:21 +0100 (Wed, 03 Mar 2010) $ by $Author: schulte $
00011  *     $Revision: 10364 $
00012  *
00013  *  This file is part of Gecode, the generic constraint
00014  *  development environment:
00015  *     http://www.gecode.org
00016  *
00017  *  Permission is hereby granted, free of charge, to any person obtaining
00018  *  a copy of this software and associated documentation files (the
00019  *  "Software"), to deal in the Software without restriction, including
00020  *  without limitation the rights to use, copy, modify, merge, publish,
00021  *  distribute, sublicense, and/or sell copies of the Software, and to
00022  *  permit persons to whom the Software is furnished to do so, subject to
00023  *  the following conditions:
00024  *
00025  *  The above copyright notice and this permission notice shall be
00026  *  included in all copies or substantial portions of the Software.
00027  *
00028  *  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
00029  *  EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
00030  *  MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
00031  *  NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
00032  *  LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
00033  *  OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
00034  *  WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
00035  *
00036  */
00037 
00038 namespace Gecode { namespace Int { namespace Linear {
00039 
00040   /*
00041    * Ternary linear propagators
00042    *
00043    */
00044   template<class Val, class A, class B, class C, PropCond pc>
00045   forceinline
00046   LinTer<Val,A,B,C,pc>::LinTer(Home home, A y0, B y1, C y2, Val c0)
00047     : Propagator(home), x0(y0), x1(y1), x2(y2), c(c0) {
00048     x0.subscribe(home,*this,pc);
00049     x1.subscribe(home,*this,pc);
00050     x2.subscribe(home,*this,pc);
00051   }
00052 
00053   template<class Val, class A, class B, class C, PropCond pc>
00054   forceinline
00055   LinTer<Val,A,B,C,pc>::LinTer(Space& home, bool share,
00056                                LinTer<Val,A,B,C,pc>& p)
00057     : Propagator(home,share,p), c(p.c) {
00058     x0.update(home,share,p.x0);
00059     x1.update(home,share,p.x1);
00060     x2.update(home,share,p.x2);
00061   }
00062 
00063   template<class Val, class A, class B, class C, PropCond pc>
00064   forceinline
00065   LinTer<Val,A,B,C,pc>::LinTer(Space& home, bool share, Propagator& p,
00066                                A y0, B y1, C y2, Val c0)
00067     : Propagator(home,share,p), c(c0) {
00068     x0.update(home,share,y0);
00069     x1.update(home,share,y1);
00070     x2.update(home,share,y2);
00071   }
00072 
00073   template<class Val, class A, class B, class C, PropCond pc>
00074   PropCost
00075   LinTer<Val,A,B,C,pc>::cost(const Space&, const ModEventDelta&) const {
00076     return PropCost::ternary(PropCost::LO);
00077   }
00078 
00079   template<class Val, class A, class B, class C, PropCond pc>
00080   forceinline size_t
00081   LinTer<Val,A,B,C,pc>::dispose(Space& home) {
00082     x0.cancel(home,*this,pc);
00083     x1.cancel(home,*this,pc);
00084     x2.cancel(home,*this,pc);
00085     (void) Propagator::dispose(home);
00086     return sizeof(*this);
00087   }
00088 
00089   /*
00090    * Equality propagator
00091    *
00092    */
00093 
00094   template<class Val, class A, class B, class C>
00095   forceinline
00096   EqTer<Val,A,B,C>::EqTer(Home home, A x0, B x1, C x2, Val c)
00097     : LinTer<Val,A,B,C,PC_INT_BND>(home,x0,x1,x2,c) {}
00098 
00099   template<class Val, class A, class B, class C>
00100   ExecStatus
00101   EqTer<Val,A,B,C>::post(Home home, A x0, B x1, C x2, Val c) {
00102     (void) new (home) EqTer<Val,A,B,C>(home,x0,x1,x2,c);
00103     return ES_OK;
00104   }
00105 
00106 
00107   template<class Val, class A, class B, class C>
00108   forceinline
00109   EqTer<Val,A,B,C>::EqTer(Space& home, bool share, EqTer<Val,A,B,C>& p)
00110     : LinTer<Val,A,B,C,PC_INT_BND>(home,share,p) {}
00111 
00112   template<class Val, class A, class B, class C>
00113   forceinline
00114   EqTer<Val,A,B,C>::EqTer(Space& home, bool share, Propagator& p,
00115                           A x0, B x1, C x2, Val c)
00116     : LinTer<Val,A,B,C,PC_INT_BND>(home,share,p,x0,x1,x2,c) {}
00117 
00118   template<class Val, class A, class B, class C>
00119   Actor*
00120   EqTer<Val,A,B,C>::copy(Space& home, bool share) {
00121     return new (home) EqTer<Val,A,B,C>(home,share,*this);
00122   }
00123 
00125   enum TerMod {
00126     TM_X0_MIN = 1<<0,
00127     TM_X0_MAX = 1<<1,
00128     TM_X1_MIN = 1<<2,
00129     TM_X1_MAX = 1<<3,
00130     TM_X2_MIN = 1<<4,
00131     TM_X2_MAX = 1<<5,
00132     TM_ALL    = TM_X0_MIN|TM_X0_MAX|TM_X1_MIN|TM_X1_MAX|TM_X2_MIN|TM_X2_MAX
00133   };
00134 
00135 #define GECODE_INT_PV(CASE,TELL,UPDATE)                \
00136   if (bm & (CASE)) {                                \
00137     bm -= (CASE); ModEvent me = (TELL);                \
00138     if (me_failed(me))   return ES_FAILED;        \
00139     if (me_modified(me)) bm |= (UPDATE);        \
00140   }
00141 
00142   template<class Val, class A, class B, class C>
00143   ExecStatus
00144   EqTer<Val,A,B,C>::propagate(Space& home, const ModEventDelta&) {
00145     int bm = TM_ALL;
00146     do {
00147       GECODE_INT_PV(TM_X0_MIN, x0.gq(home,c-x1.max()-x2.max()),
00148                     TM_X1_MAX | TM_X2_MAX);
00149       GECODE_INT_PV(TM_X1_MIN, x1.gq(home,c-x0.max()-x2.max()),
00150                     TM_X0_MAX | TM_X2_MAX);
00151       GECODE_INT_PV(TM_X2_MIN, x2.gq(home,c-x0.max()-x1.max()),
00152                     TM_X0_MAX | TM_X1_MAX);
00153       GECODE_INT_PV(TM_X0_MAX, x0.lq(home,c-x1.min()-x2.min()),
00154                     TM_X1_MIN | TM_X2_MIN);
00155       GECODE_INT_PV(TM_X1_MAX, x1.lq(home,c-x0.min()-x2.min()),
00156                     TM_X0_MIN | TM_X2_MIN);
00157       GECODE_INT_PV(TM_X2_MAX, x2.lq(home,c-x0.min()-x1.min()),
00158                     TM_X0_MIN | TM_X1_MIN);
00159     } while (bm);
00160     return (x0.assigned() && x1.assigned()) ?
00161       home.ES_SUBSUMED(*this) : ES_FIX;
00162   }
00163 
00164 #undef GECODE_INT_PV
00165 
00166 
00167 
00168   /*
00169    * Disequality propagator
00170    *
00171    */
00172 
00173   template<class Val, class A, class B, class C>
00174   forceinline
00175   NqTer<Val,A,B,C>::NqTer(Home home, A x0, B x1, C x2, Val c)
00176     : LinTer<Val,A,B,C,PC_INT_VAL>(home,x0,x1,x2,c) {}
00177 
00178   template<class Val, class A, class B, class C>
00179   ExecStatus
00180   NqTer<Val,A,B,C>::post(Home home, A x0, B x1, C x2, Val c) {
00181     (void) new (home) NqTer<Val,A,B,C>(home,x0,x1,x2,c);
00182     return ES_OK;
00183   }
00184 
00185 
00186   template<class Val, class A, class B, class C>
00187   forceinline
00188   NqTer<Val,A,B,C>::NqTer(Space& home, bool share, NqTer<Val,A,B,C>& p)
00189     : LinTer<Val,A,B,C,PC_INT_VAL>(home,share,p) {}
00190 
00191   template<class Val, class A, class B, class C>
00192   Actor*
00193   NqTer<Val,A,B,C>::copy(Space& home, bool share) {
00194     return new (home) NqTer<Val,A,B,C>(home,share,*this);
00195   }
00196 
00197   template<class Val, class A, class B, class C>
00198   forceinline
00199   NqTer<Val,A,B,C>::NqTer(Space& home, bool share, Propagator& p,
00200                           A x0, B x1, C x2, Val c)
00201     : LinTer<Val,A,B,C,PC_INT_VAL>(home,share,p,x0,x1,x2,c) {}
00202 
00203 
00204   template<class Val, class A, class B, class C>
00205   ExecStatus
00206   NqTer<Val,A,B,C>::propagate(Space& home, const ModEventDelta&) {
00207     if (x0.assigned() && x1.assigned()) {
00208       GECODE_ME_CHECK(x2.nq(home,c-x0.val()-x1.val()));
00209       return home.ES_SUBSUMED(*this);
00210     }
00211     if (x0.assigned() && x2.assigned()) {
00212       GECODE_ME_CHECK(x1.nq(home,c-x0.val()-x2.val()));
00213       return home.ES_SUBSUMED(*this);
00214     }
00215     if (x1.assigned() && x2.assigned()) {
00216       GECODE_ME_CHECK(x0.nq(home,c-x1.val()-x2.val()));
00217       return home.ES_SUBSUMED(*this);
00218     }
00219     return ES_FIX;
00220   }
00221 
00222 
00223 
00224   /*
00225    * Inequality propagator
00226    *
00227    */
00228 
00229   template<class Val, class A, class B, class C>
00230   forceinline
00231   LqTer<Val,A,B,C>::LqTer(Home home, A x0, B x1, C x2, Val c)
00232     : LinTer<Val,A,B,C,PC_INT_BND>(home,x0,x1,x2,c) {}
00233 
00234   template<class Val, class A, class B, class C>
00235   ExecStatus
00236   LqTer<Val,A,B,C>::post(Home home, A x0, B x1, C x2, Val c) {
00237     (void) new (home) LqTer<Val,A,B,C>(home,x0,x1,x2,c);
00238     return ES_OK;
00239   }
00240 
00241 
00242   template<class Val, class A, class B, class C>
00243   forceinline
00244   LqTer<Val,A,B,C>::LqTer(Space& home, bool share, LqTer<Val,A,B,C>& p)
00245     : LinTer<Val,A,B,C,PC_INT_BND>(home,share,p) {}
00246 
00247   template<class Val, class A, class B, class C>
00248   Actor*
00249   LqTer<Val,A,B,C>::copy(Space& home, bool share) {
00250     return new (home) LqTer<Val,A,B,C>(home,share,*this);
00251   }
00252 
00253 
00254   template<class Val, class A, class B, class C>
00255   forceinline
00256   LqTer<Val,A,B,C>::LqTer(Space& home, bool share, Propagator& p,
00257                           A x0, B x1, C x2, Val c)
00258     : LinTer<Val,A,B,C,PC_INT_BND>(home,share,p,x0,x1,x2,c) {}
00259 
00260   template<class Val, class A, class B, class C>
00261   ExecStatus
00262   LqTer<Val,A,B,C>::propagate(Space& home, const ModEventDelta&) {
00263     GECODE_ME_CHECK(x0.lq(home,c-x1.min()-x2.min()));
00264     GECODE_ME_CHECK(x1.lq(home,c-x0.min()-x2.min()));
00265     GECODE_ME_CHECK(x2.lq(home,c-x0.min()-x1.min()));
00266     return (x0.max()+x1.max()+x2.max() <= c) ?
00267       home.ES_SUBSUMED(*this) : ES_FIX;
00268   }
00269 
00270 }}}
00271 
00272 // STATISTICS: int-prop
00273