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: 2016-06-29 17:28:17 +0200 (Wed, 29 Jun 2016) $ by $Author: schulte $
00011  *     $Revision: 15137 $
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   void
00081   LinTer<Val,A,B,C,pc>::reschedule(Space& home) {
00082     x0.reschedule(home,*this,pc);
00083     x1.reschedule(home,*this,pc);
00084     x2.reschedule(home,*this,pc);
00085   }
00086 
00087   template<class Val, class A, class B, class C, PropCond pc>
00088   forceinline size_t
00089   LinTer<Val,A,B,C,pc>::dispose(Space& home) {
00090     x0.cancel(home,*this,pc);
00091     x1.cancel(home,*this,pc);
00092     x2.cancel(home,*this,pc);
00093     (void) Propagator::dispose(home);
00094     return sizeof(*this);
00095   }
00096 
00097   /*
00098    * Equality propagator
00099    *
00100    */
00101 
00102   template<class Val, class A, class B, class C>
00103   forceinline
00104   EqTer<Val,A,B,C>::EqTer(Home home, A x0, B x1, C x2, Val c)
00105     : LinTer<Val,A,B,C,PC_INT_BND>(home,x0,x1,x2,c) {}
00106 
00107   template<class Val, class A, class B, class C>
00108   ExecStatus
00109   EqTer<Val,A,B,C>::post(Home home, A x0, B x1, C x2, Val c) {
00110     (void) new (home) EqTer<Val,A,B,C>(home,x0,x1,x2,c);
00111     return ES_OK;
00112   }
00113 
00114 
00115   template<class Val, class A, class B, class C>
00116   forceinline
00117   EqTer<Val,A,B,C>::EqTer(Space& home, bool share, EqTer<Val,A,B,C>& p)
00118     : LinTer<Val,A,B,C,PC_INT_BND>(home,share,p) {}
00119 
00120   template<class Val, class A, class B, class C>
00121   forceinline
00122   EqTer<Val,A,B,C>::EqTer(Space& home, bool share, Propagator& p,
00123                           A x0, B x1, C x2, Val c)
00124     : LinTer<Val,A,B,C,PC_INT_BND>(home,share,p,x0,x1,x2,c) {}
00125 
00126   template<class Val, class A, class B, class C>
00127   Actor*
00128   EqTer<Val,A,B,C>::copy(Space& home, bool share) {
00129     return new (home) EqTer<Val,A,B,C>(home,share,*this);
00130   }
00131 
00133   enum TerMod {
00134     TM_X0_MIN = 1<<0,
00135     TM_X0_MAX = 1<<1,
00136     TM_X1_MIN = 1<<2,
00137     TM_X1_MAX = 1<<3,
00138     TM_X2_MIN = 1<<4,
00139     TM_X2_MAX = 1<<5,
00140     TM_ALL    = TM_X0_MIN|TM_X0_MAX|TM_X1_MIN|TM_X1_MAX|TM_X2_MIN|TM_X2_MAX
00141   };
00142 
00143 #define GECODE_INT_PV(CASE,TELL,UPDATE)                \
00144   if (bm & (CASE)) {                                \
00145     bm -= (CASE); ModEvent me = (TELL);                \
00146     if (me_failed(me))   return ES_FAILED;        \
00147     if (me_modified(me)) bm |= (UPDATE);        \
00148   }
00149 
00150   template<class Val, class A, class B, class C>
00151   ExecStatus
00152   EqTer<Val,A,B,C>::propagate(Space& home, const ModEventDelta&) {
00153     int bm = TM_ALL;
00154     do {
00155       GECODE_INT_PV(TM_X0_MIN, x0.gq(home,c-x1.max()-x2.max()),
00156                     TM_X1_MAX | TM_X2_MAX);
00157       GECODE_INT_PV(TM_X1_MIN, x1.gq(home,c-x0.max()-x2.max()),
00158                     TM_X0_MAX | TM_X2_MAX);
00159       GECODE_INT_PV(TM_X2_MIN, x2.gq(home,c-x0.max()-x1.max()),
00160                     TM_X0_MAX | TM_X1_MAX);
00161       GECODE_INT_PV(TM_X0_MAX, x0.lq(home,c-x1.min()-x2.min()),
00162                     TM_X1_MIN | TM_X2_MIN);
00163       GECODE_INT_PV(TM_X1_MAX, x1.lq(home,c-x0.min()-x2.min()),
00164                     TM_X0_MIN | TM_X2_MIN);
00165       GECODE_INT_PV(TM_X2_MAX, x2.lq(home,c-x0.min()-x1.min()),
00166                     TM_X0_MIN | TM_X1_MIN);
00167     } while (bm);
00168     return (x0.assigned() && x1.assigned()) ?
00169       home.ES_SUBSUMED(*this) : ES_FIX;
00170   }
00171 
00172 #undef GECODE_INT_PV
00173 
00174 
00175 
00176   /*
00177    * Disequality propagator
00178    *
00179    */
00180 
00181   template<class Val, class A, class B, class C>
00182   forceinline
00183   NqTer<Val,A,B,C>::NqTer(Home home, A x0, B x1, C x2, Val c)
00184     : LinTer<Val,A,B,C,PC_INT_VAL>(home,x0,x1,x2,c) {}
00185 
00186   template<class Val, class A, class B, class C>
00187   ExecStatus
00188   NqTer<Val,A,B,C>::post(Home home, A x0, B x1, C x2, Val c) {
00189     (void) new (home) NqTer<Val,A,B,C>(home,x0,x1,x2,c);
00190     return ES_OK;
00191   }
00192 
00193 
00194   template<class Val, class A, class B, class C>
00195   forceinline
00196   NqTer<Val,A,B,C>::NqTer(Space& home, bool share, NqTer<Val,A,B,C>& p)
00197     : LinTer<Val,A,B,C,PC_INT_VAL>(home,share,p) {}
00198 
00199   template<class Val, class A, class B, class C>
00200   Actor*
00201   NqTer<Val,A,B,C>::copy(Space& home, bool share) {
00202     return new (home) NqTer<Val,A,B,C>(home,share,*this);
00203   }
00204 
00205   template<class Val, class A, class B, class C>
00206   forceinline
00207   NqTer<Val,A,B,C>::NqTer(Space& home, bool share, Propagator& p,
00208                           A x0, B x1, C x2, Val c)
00209     : LinTer<Val,A,B,C,PC_INT_VAL>(home,share,p,x0,x1,x2,c) {}
00210 
00211 
00212   template<class Val, class A, class B, class C>
00213   ExecStatus
00214   NqTer<Val,A,B,C>::propagate(Space& home, const ModEventDelta&) {
00215     if (x0.assigned() && x1.assigned()) {
00216       GECODE_ME_CHECK(x2.nq(home,c-x0.val()-x1.val()));
00217       return home.ES_SUBSUMED(*this);
00218     }
00219     if (x0.assigned() && x2.assigned()) {
00220       GECODE_ME_CHECK(x1.nq(home,c-x0.val()-x2.val()));
00221       return home.ES_SUBSUMED(*this);
00222     }
00223     if (x1.assigned() && x2.assigned()) {
00224       GECODE_ME_CHECK(x0.nq(home,c-x1.val()-x2.val()));
00225       return home.ES_SUBSUMED(*this);
00226     }
00227     return ES_FIX;
00228   }
00229 
00230 
00231 
00232   /*
00233    * Inequality propagator
00234    *
00235    */
00236 
00237   template<class Val, class A, class B, class C>
00238   forceinline
00239   LqTer<Val,A,B,C>::LqTer(Home home, A x0, B x1, C x2, Val c)
00240     : LinTer<Val,A,B,C,PC_INT_BND>(home,x0,x1,x2,c) {}
00241 
00242   template<class Val, class A, class B, class C>
00243   ExecStatus
00244   LqTer<Val,A,B,C>::post(Home home, A x0, B x1, C x2, Val c) {
00245     (void) new (home) LqTer<Val,A,B,C>(home,x0,x1,x2,c);
00246     return ES_OK;
00247   }
00248 
00249 
00250   template<class Val, class A, class B, class C>
00251   forceinline
00252   LqTer<Val,A,B,C>::LqTer(Space& home, bool share, LqTer<Val,A,B,C>& p)
00253     : LinTer<Val,A,B,C,PC_INT_BND>(home,share,p) {}
00254 
00255   template<class Val, class A, class B, class C>
00256   Actor*
00257   LqTer<Val,A,B,C>::copy(Space& home, bool share) {
00258     return new (home) LqTer<Val,A,B,C>(home,share,*this);
00259   }
00260 
00261 
00262   template<class Val, class A, class B, class C>
00263   forceinline
00264   LqTer<Val,A,B,C>::LqTer(Space& home, bool share, Propagator& p,
00265                           A x0, B x1, C x2, Val c)
00266     : LinTer<Val,A,B,C,PC_INT_BND>(home,share,p,x0,x1,x2,c) {}
00267 
00268   template<class Val, class A, class B, class C>
00269   ExecStatus
00270   LqTer<Val,A,B,C>::propagate(Space& home, const ModEventDelta&) {
00271     GECODE_ME_CHECK(x0.lq(home,c-x1.min()-x2.min()));
00272     GECODE_ME_CHECK(x1.lq(home,c-x0.min()-x2.min()));
00273     GECODE_ME_CHECK(x2.lq(home,c-x0.min()-x1.min()));
00274     return (x0.max()+x1.max()+x2.max() <= c) ?
00275       home.ES_SUBSUMED(*this) : ES_FIX;
00276   }
00277 
00278 }}}
00279 
00280 // STATISTICS: int-prop
00281