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