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