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