Generated on Thu Apr 11 13:59:10 2019 for Gecode by doxygen 1.6.3

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