gecode » int » linear
int-bin.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-14 12:19:49 +0200 (Wed, 14 Oct 2009) $ by $Author: schulte $
00011  *     $Revision: 9909 $
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    * Binary linear propagators
00042    *
00043    */
00044   template<class Val, class A, class B, PropCond pc>
00045   forceinline
00046   LinBin<Val,A,B,pc>::LinBin(Home home, A y0, B y1, Val c0)
00047     : Propagator(home), x0(y0), x1(y1), c(c0) {
00048     x0.subscribe(home,*this,pc);
00049     x1.subscribe(home,*this,pc);
00050   }
00051 
00052   template<class Val, class A, class B, PropCond pc>
00053   forceinline
00054   LinBin<Val,A,B,pc>::LinBin(Space& home, bool share, LinBin<Val,A,B,pc>& p)
00055     : Propagator(home,share,p), c(p.c) {
00056     x0.update(home,share,p.x0);
00057     x1.update(home,share,p.x1);
00058   }
00059 
00060   template<class Val, class A, class B, PropCond pc>
00061   forceinline
00062   LinBin<Val,A,B,pc>::LinBin(Space& home, bool share, Propagator& p,
00063                              A y0, B y1, Val c0)
00064     : Propagator(home,share,p), c(c0) {
00065     x0.update(home,share,y0);
00066     x1.update(home,share,y1);
00067   }
00068 
00069   template<class Val, class A, class B, PropCond pc>
00070   PropCost
00071   LinBin<Val,A,B,pc>::cost(const Space&, const ModEventDelta&) const {
00072     return PropCost::binary(PropCost::LO);
00073   }
00074 
00075   template<class Val, class A, class B, PropCond pc>
00076   forceinline size_t
00077   LinBin<Val,A,B,pc>::dispose(Space& home) {
00078     assert(!home.failed());
00079     x0.cancel(home,*this,pc);
00080     x1.cancel(home,*this,pc);
00081     (void) Propagator::dispose(home);
00082     return sizeof(*this);
00083   }
00084 
00085 
00086   /*
00087    * Binary reified linear propagators
00088    *
00089    */
00090   template<class Val, class A, class B, PropCond pc, class Ctrl>
00091   forceinline
00092   ReLinBin<Val,A,B,pc,Ctrl>::ReLinBin(Home home, A y0, B y1, Val c0, Ctrl b0)
00093     : Propagator(home), x0(y0), x1(y1), c(c0), b(b0) {
00094     x0.subscribe(home,*this,pc);
00095     x1.subscribe(home,*this,pc);
00096     b.subscribe(home,*this,PC_INT_VAL);
00097   }
00098 
00099   template<class Val, class A, class B, PropCond pc, class Ctrl>
00100   forceinline
00101   ReLinBin<Val,A,B,pc,Ctrl>::ReLinBin(Space& home, bool share,
00102                                       ReLinBin<Val,A,B,pc,Ctrl>& p)
00103     : Propagator(home,share,p), c(p.c) {
00104     x0.update(home,share,p.x0);
00105     x1.update(home,share,p.x1);
00106     b.update(home,share,p.b);
00107   }
00108 
00109   template<class Val, class A, class B, PropCond pc, class Ctrl>
00110   PropCost
00111   ReLinBin<Val,A,B,pc,Ctrl>::cost(const Space&, const ModEventDelta&) const {
00112     return PropCost::binary(PropCost::LO);
00113   }
00114 
00115   template<class Val, class A, class B, PropCond pc, class Ctrl>
00116   forceinline size_t
00117   ReLinBin<Val,A,B,pc,Ctrl>::dispose(Space& home) {
00118     assert(!home.failed());
00119     x0.cancel(home,*this,pc);
00120     x1.cancel(home,*this,pc);
00121     b.cancel(home,*this,PC_BOOL_VAL);
00122     (void) Propagator::dispose(home);
00123     return sizeof(*this);
00124   }
00125 
00126   /*
00127    * Binary bounds consistent linear equality
00128    *
00129    */
00130 
00131   template<class Val, class A, class B>
00132   forceinline
00133   EqBin<Val,A,B>::EqBin(Home home, A x0, B x1, Val c)
00134     : LinBin<Val,A,B,PC_INT_BND>(home,x0,x1,c) {}
00135 
00136   template<class Val, class A, class B>
00137   ExecStatus
00138   EqBin<Val,A,B>::post(Home home, A x0, B x1, Val c) {
00139     (void) new (home) EqBin<Val,A,B>(home,x0,x1,c);
00140     return ES_OK;
00141   }
00142 
00143 
00144   template<class Val, class A, class B>
00145   forceinline
00146   EqBin<Val,A,B>::EqBin(Space& home, bool share, EqBin<Val,A,B>& p)
00147     : LinBin<Val,A,B,PC_INT_BND>(home,share,p) {}
00148 
00149   template<class Val, class A, class B>
00150   forceinline
00151   EqBin<Val,A,B>::EqBin(Space& home, bool share, Propagator& p,
00152                         A x0, B x1, Val c)
00153     : LinBin<Val,A,B,PC_INT_BND>(home,share,p,x0,x1,c) {}
00154 
00155   template<class Val, class A, class B>
00156   Actor*
00157   EqBin<Val,A,B>::copy(Space& home, bool share) {
00158     return new (home) EqBin<Val,A,B>(home,share,*this);
00159   }
00160 
00162   enum BinMod {
00163     BM_X0_MIN = 1<<0,
00164     BM_X0_MAX = 1<<1,
00165     BM_X1_MIN = 1<<2,
00166     BM_X1_MAX = 1<<3,
00167     BM_ALL    = BM_X0_MIN|BM_X0_MAX|BM_X1_MIN|BM_X1_MAX
00168   };
00169 
00170 #define GECODE_INT_PV(CASE,TELL,UPDATE)         \
00171   if (bm & (CASE)) {                            \
00172     bm -= (CASE); ModEvent me = (TELL);         \
00173     if (me_failed(me))   return ES_FAILED;      \
00174     if (me_modified(me)) bm |= (UPDATE);        \
00175   }
00176 
00177   template<class Val, class A, class B>
00178   ExecStatus
00179   EqBin<Val,A,B>::propagate(Space& home, const ModEventDelta&) {
00180     int bm = BM_ALL;
00181     do {
00182       GECODE_INT_PV(BM_X0_MIN, x0.gq(home,c-x1.max()), BM_X1_MAX);
00183       GECODE_INT_PV(BM_X1_MIN, x1.gq(home,c-x0.max()), BM_X0_MAX);
00184       GECODE_INT_PV(BM_X0_MAX, x0.lq(home,c-x1.min()), BM_X1_MIN);
00185       GECODE_INT_PV(BM_X1_MAX, x1.lq(home,c-x0.min()), BM_X0_MIN);
00186     } while (bm);
00187     return x0.assigned() ? ES_SUBSUMED(*this,sizeof(*this)) : ES_FIX;
00188   }
00189 
00190 #undef GECODE_INT_PV
00191 
00192 
00193 
00194 
00195 
00196   /*
00197    * Reified binary bounds consistent linear equality
00198    *
00199    */
00200 
00201   template<class Val, class A, class B, class Ctrl>
00202   forceinline
00203   ReEqBin<Val,A,B,Ctrl>::ReEqBin(Home home, A x0, B x1, Val c, Ctrl b)
00204     : ReLinBin<Val,A,B,PC_INT_BND,Ctrl>(home,x0,x1,c,b) {}
00205 
00206   template<class Val, class A, class B, class Ctrl>
00207   ExecStatus
00208   ReEqBin<Val,A,B,Ctrl>::post(Home home, A x0, B x1, Val c, Ctrl b) {
00209     (void) new (home) ReEqBin<Val,A,B,Ctrl>(home,x0,x1,c,b);
00210     return ES_OK;
00211   }
00212 
00213 
00214   template<class Val, class A, class B, class Ctrl>
00215   forceinline
00216   ReEqBin<Val,A,B,Ctrl>::ReEqBin(Space& home, bool share,
00217                                  ReEqBin<Val,A,B,Ctrl>& p)
00218     : ReLinBin<Val,A,B,PC_INT_BND,Ctrl>(home,share,p) {}
00219 
00220   template<class Val, class A, class B, class Ctrl>
00221   Actor*
00222   ReEqBin<Val,A,B,Ctrl>::copy(Space& home, bool share) {
00223     return new (home) ReEqBin<Val,A,B,Ctrl>(home,share,*this);
00224   }
00225 
00226   template<class Val, class A, class B, class Ctrl>
00227   ExecStatus
00228   ReEqBin<Val,A,B,Ctrl>::propagate(Space& home, const ModEventDelta&) {
00229     if (b.zero())
00230       GECODE_REWRITE(*this,(NqBin<Val,A,B>::post(home(*this),x0,x1,c)));
00231     if (b.one())
00232       GECODE_REWRITE(*this,(EqBin<Val,A,B>::post(home(*this),x0,x1,c)));
00233     if ((x0.min() + x1.min() > c) || (x0.max() + x1.max() < c)) {
00234       GECODE_ME_CHECK(b.zero_none(home)); return ES_SUBSUMED(*this,home);
00235     }
00236     if (x0.assigned() && x1.assigned()) {
00237       assert(x0.val() + x1.val() == c);
00238       GECODE_ME_CHECK(b.one_none(home)); return ES_SUBSUMED(*this,home);
00239     }
00240     return ES_FIX;
00241   }
00242 
00243 
00244 
00245 
00246   /*
00247    * Binary domain consistent linear disequality
00248    *
00249    */
00250   template<class Val, class A, class B>
00251   forceinline
00252   NqBin<Val,A,B>::NqBin(Home home, A x0, B x1, Val c)
00253     : LinBin<Val,A,B,PC_INT_VAL>(home,x0,x1,c) {}
00254 
00255   template<class Val, class A, class B>
00256   ExecStatus
00257   NqBin<Val,A,B>::post(Home home, A x0, B x1, Val c) {
00258     (void) new (home) NqBin<Val,A,B>(home,x0,x1,c);
00259     return ES_OK;
00260   }
00261 
00262 
00263   template<class Val, class A, class B>
00264   forceinline
00265   NqBin<Val,A,B>::NqBin(Space& home, bool share, NqBin<Val,A,B>& p)
00266     : LinBin<Val,A,B,PC_INT_VAL>(home,share,p) {}
00267 
00268   template<class Val, class A, class B>
00269   Actor*
00270   NqBin<Val,A,B>::copy(Space& home, bool share) {
00271     return new (home) NqBin<Val,A,B>(home,share,*this);
00272   }
00273 
00274   template<class Val, class A, class B>
00275   forceinline
00276   NqBin<Val,A,B>::NqBin(Space& home, bool share, Propagator& p,
00277                         A x0, B x1, Val c)
00278     : LinBin<Val,A,B,PC_INT_VAL>(home,share,p,x0,x1,c) {}
00279 
00280 
00281 
00282   template<class Val, class A, class B>
00283   PropCost
00284   NqBin<Val,A,B>::cost(const Space&, const ModEventDelta&) const {
00285     return PropCost::unary(PropCost::LO);
00286   }
00287 
00288   template<class Val, class A, class B>
00289   ExecStatus
00290   NqBin<Val,A,B>::propagate(Space& home, const ModEventDelta&) {
00291     if (x0.assigned()) {
00292       GECODE_ME_CHECK(x1.nq(home,c-x0.val()));
00293     } else {
00294       assert(x1.assigned());
00295       GECODE_ME_CHECK(x0.nq(home,c-x1.val()));
00296     }
00297     return ES_SUBSUMED(*this,home);
00298   }
00299 
00300 
00301   /*
00302    * Binary domain consistent less equal
00303    *
00304    */
00305 
00306   template<class Val, class A, class B>
00307   forceinline
00308   LqBin<Val,A,B>::LqBin(Home home, A x0, B x1, Val c)
00309     : LinBin<Val,A,B,PC_INT_BND>(home,x0,x1,c) {}
00310 
00311   template<class Val, class A, class B>
00312   ExecStatus
00313   LqBin<Val,A,B>::post(Home home, A x0, B x1, Val c) {
00314     (void) new (home) LqBin<Val,A,B>(home,x0,x1,c);
00315     return ES_OK;
00316   }
00317 
00318 
00319   template<class Val, class A, class B>
00320   forceinline
00321   LqBin<Val,A,B>::LqBin(Space& home, bool share, LqBin<Val,A,B>& p)
00322     : LinBin<Val,A,B,PC_INT_BND>(home,share,p) {}
00323 
00324   template<class Val, class A, class B>
00325   Actor*
00326   LqBin<Val,A,B>::copy(Space& home, bool share) {
00327     return new (home) LqBin<Val,A,B>(home,share,*this);
00328   }
00329 
00330   template<class Val, class A, class B>
00331   forceinline
00332   LqBin<Val,A,B>::LqBin(Space& home, bool share, Propagator& p,
00333                         A x0, B x1, Val c)
00334     : LinBin<Val,A,B,PC_INT_BND>(home,share,p,x0,x1,c) {}
00335 
00336   template<class Val, class A, class B>
00337   ExecStatus
00338   LqBin<Val,A,B>::propagate(Space& home, const ModEventDelta&) {
00339     GECODE_ME_CHECK(x0.lq(home,c-x1.min()));
00340     GECODE_ME_CHECK(x1.lq(home,c-x0.min()));
00341     return (x0.max()+x1.max() <= c) ? ES_SUBSUMED(*this,home) : ES_FIX;
00342   }
00343 
00344 
00345 
00346 
00347   /*
00348    * Binary domain consistent greater equal
00349    *
00350    */
00351 
00352   template<class Val, class A, class B>
00353   forceinline
00354   GqBin<Val,A,B>::GqBin(Home home, A x0, B x1, Val c)
00355     : LinBin<Val,A,B,PC_INT_BND>(home,x0,x1,c) {}
00356 
00357   template<class Val, class A, class B>
00358   ExecStatus
00359   GqBin<Val,A,B>::post(Home home, A x0, B x1, Val c) {
00360     (void) new (home) GqBin<Val,A,B>(home,x0,x1,c);
00361     return ES_OK;
00362   }
00363 
00364 
00365   template<class Val, class A, class B>
00366   forceinline
00367   GqBin<Val,A,B>::GqBin(Space& home, bool share, GqBin<Val,A,B>& p)
00368     : LinBin<Val,A,B,PC_INT_BND>(home,share,p) {}
00369 
00370   template<class Val, class A, class B>
00371   Actor*
00372   GqBin<Val,A,B>::copy(Space& home, bool share) {
00373     return new (home) GqBin<Val,A,B>(home,share,*this);
00374   }
00375 
00376   template<class Val, class A, class B>
00377   forceinline
00378   GqBin<Val,A,B>::GqBin(Space& home, bool share, Propagator& p,
00379                         A x0, B x1, Val c)
00380     : LinBin<Val,A,B,PC_INT_BND>(home,share,p,x0,x1,c) {}
00381 
00382   template<class Val, class A, class B>
00383   ExecStatus
00384   GqBin<Val,A,B>::propagate(Space& home, const ModEventDelta&) {
00385     GECODE_ME_CHECK(x0.gq(home,c-x1.max()));
00386     GECODE_ME_CHECK(x1.gq(home,c-x0.max()));
00387     return (x0.min()+x1.min() >= c) ? ES_SUBSUMED(*this,home) : ES_FIX;
00388   }
00389 
00390 
00391 
00392 
00393   /*
00394    * Reified binary domain consistent less equal
00395    *
00396    */
00397 
00398   template<class Val, class A, class B>
00399   forceinline
00400   ReLqBin<Val,A,B>::ReLqBin(Home home, A x0, B x1, Val c, BoolView b)
00401     : ReLinBin<Val,A,B,PC_INT_BND,BoolView>(home,x0,x1,c,b) {}
00402 
00403   template<class Val, class A, class B>
00404   ExecStatus
00405   ReLqBin<Val,A,B>::post(Home home, A x0, B x1, Val c, BoolView b) {
00406     (void) new (home) ReLqBin<Val,A,B>(home,x0,x1,c,b);
00407     return ES_OK;
00408   }
00409 
00410 
00411   template<class Val, class A, class B>
00412   forceinline
00413   ReLqBin<Val,A,B>::ReLqBin(Space& home, bool share, ReLqBin<Val,A,B>& p)
00414     : ReLinBin<Val,A,B,PC_INT_BND,BoolView>(home,share,p) {}
00415 
00416   template<class Val, class A, class B>
00417   Actor*
00418   ReLqBin<Val,A,B>::copy(Space& home, bool share) {
00419     return new (home) ReLqBin<Val,A,B>(home,share,*this);
00420   }
00421 
00422   template<class Val, class A, class B>
00423   ExecStatus
00424   ReLqBin<Val,A,B>::propagate(Space& home, const ModEventDelta&) {
00425     if (b.one())
00426       GECODE_REWRITE(*this,(LqBin<Val,A,B>::post(home(*this),x0,x1,c)));
00427     if (b.zero())
00428       GECODE_REWRITE(*this,(GqBin<Val,A,B>::post(home(*this),x0,x1,c+1)));
00429     if (x0.max() + x1.max() <= c) {
00430       GECODE_ME_CHECK(b.one_none(home)); return ES_SUBSUMED(*this,home);
00431     }
00432     if (x0.min() + x1.min() > c) {
00433       GECODE_ME_CHECK(b.zero_none(home)); return ES_SUBSUMED(*this,home);
00434     }
00435     return ES_FIX;
00436   }
00437 
00438 }}}
00439 
00440 // STATISTICS: int-prop
00441