Generated on Fri Oct 19 11:25:07 2018 for Gecode by doxygen 1.6.3

int-ter.hpp

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