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: 2010-03-03 17:32:21 +0100 (Wed, 03 Mar 2010) $ by $Author: schulte $
00011  *     $Revision: 10364 $
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>
00200   forceinline
00201   ReEqBin<Val,A,B,Ctrl>::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>
00205   ExecStatus
00206   ReEqBin<Val,A,B,Ctrl>::post(Home home, A x0, B x1, Val c, Ctrl b) {
00207     (void) new (home) ReEqBin<Val,A,B,Ctrl>(home,x0,x1,c,b);
00208     return ES_OK;
00209   }
00210 
00211 
00212   template<class Val, class A, class B, class Ctrl>
00213   forceinline
00214   ReEqBin<Val,A,B,Ctrl>::ReEqBin(Space& home, bool share,
00215                                  ReEqBin<Val,A,B,Ctrl>& p)
00216     : ReLinBin<Val,A,B,PC_INT_BND,Ctrl>(home,share,p) {}
00217 
00218   template<class Val, class A, class B, class Ctrl>
00219   Actor*
00220   ReEqBin<Val,A,B,Ctrl>::copy(Space& home, bool share) {
00221     return new (home) ReEqBin<Val,A,B,Ctrl>(home,share,*this);
00222   }
00223 
00224   template<class Val, class A, class B, class Ctrl>
00225   ExecStatus
00226   ReEqBin<Val,A,B,Ctrl>::propagate(Space& home, const ModEventDelta&) {
00227     if (b.zero())
00228       GECODE_REWRITE(*this,(NqBin<Val,A,B>::post(home(*this),x0,x1,c)));
00229     if (b.one())
00230       GECODE_REWRITE(*this,(EqBin<Val,A,B>::post(home(*this),x0,x1,c)));
00231     if ((x0.min() + x1.min() > c) || (x0.max() + x1.max() < c)) {
00232       GECODE_ME_CHECK(b.zero_none(home)); return home.ES_SUBSUMED(*this);
00233     }
00234     if (x0.assigned() && x1.assigned()) {
00235       assert(x0.val() + x1.val() == c);
00236       GECODE_ME_CHECK(b.one_none(home)); return home.ES_SUBSUMED(*this);
00237     }
00238     return ES_FIX;
00239   }
00240 
00241 
00242 
00243 
00244   /*
00245    * Binary domain consistent linear disequality
00246    *
00247    */
00248   template<class Val, class A, class B>
00249   forceinline
00250   NqBin<Val,A,B>::NqBin(Home home, A x0, B x1, Val c)
00251     : LinBin<Val,A,B,PC_INT_VAL>(home,x0,x1,c) {}
00252 
00253   template<class Val, class A, class B>
00254   ExecStatus
00255   NqBin<Val,A,B>::post(Home home, A x0, B x1, Val c) {
00256     (void) new (home) NqBin<Val,A,B>(home,x0,x1,c);
00257     return ES_OK;
00258   }
00259 
00260 
00261   template<class Val, class A, class B>
00262   forceinline
00263   NqBin<Val,A,B>::NqBin(Space& home, bool share, NqBin<Val,A,B>& p)
00264     : LinBin<Val,A,B,PC_INT_VAL>(home,share,p) {}
00265 
00266   template<class Val, class A, class B>
00267   Actor*
00268   NqBin<Val,A,B>::copy(Space& home, bool share) {
00269     return new (home) NqBin<Val,A,B>(home,share,*this);
00270   }
00271 
00272   template<class Val, class A, class B>
00273   forceinline
00274   NqBin<Val,A,B>::NqBin(Space& home, bool share, Propagator& p,
00275                         A x0, B x1, Val c)
00276     : LinBin<Val,A,B,PC_INT_VAL>(home,share,p,x0,x1,c) {}
00277 
00278 
00279 
00280   template<class Val, class A, class B>
00281   PropCost
00282   NqBin<Val,A,B>::cost(const Space&, const ModEventDelta&) const {
00283     return PropCost::unary(PropCost::LO);
00284   }
00285 
00286   template<class Val, class A, class B>
00287   ExecStatus
00288   NqBin<Val,A,B>::propagate(Space& home, const ModEventDelta&) {
00289     if (x0.assigned()) {
00290       GECODE_ME_CHECK(x1.nq(home,c-x0.val()));
00291     } else {
00292       assert(x1.assigned());
00293       GECODE_ME_CHECK(x0.nq(home,c-x1.val()));
00294     }
00295     return home.ES_SUBSUMED(*this);
00296   }
00297 
00298 
00299   /*
00300    * Binary domain consistent less equal
00301    *
00302    */
00303 
00304   template<class Val, class A, class B>
00305   forceinline
00306   LqBin<Val,A,B>::LqBin(Home home, A x0, B x1, Val c)
00307     : LinBin<Val,A,B,PC_INT_BND>(home,x0,x1,c) {}
00308 
00309   template<class Val, class A, class B>
00310   ExecStatus
00311   LqBin<Val,A,B>::post(Home home, A x0, B x1, Val c) {
00312     (void) new (home) LqBin<Val,A,B>(home,x0,x1,c);
00313     return ES_OK;
00314   }
00315 
00316 
00317   template<class Val, class A, class B>
00318   forceinline
00319   LqBin<Val,A,B>::LqBin(Space& home, bool share, LqBin<Val,A,B>& p)
00320     : LinBin<Val,A,B,PC_INT_BND>(home,share,p) {}
00321 
00322   template<class Val, class A, class B>
00323   Actor*
00324   LqBin<Val,A,B>::copy(Space& home, bool share) {
00325     return new (home) LqBin<Val,A,B>(home,share,*this);
00326   }
00327 
00328   template<class Val, class A, class B>
00329   forceinline
00330   LqBin<Val,A,B>::LqBin(Space& home, bool share, Propagator& p,
00331                         A x0, B x1, Val c)
00332     : LinBin<Val,A,B,PC_INT_BND>(home,share,p,x0,x1,c) {}
00333 
00334   template<class Val, class A, class B>
00335   ExecStatus
00336   LqBin<Val,A,B>::propagate(Space& home, const ModEventDelta&) {
00337     GECODE_ME_CHECK(x0.lq(home,c-x1.min()));
00338     GECODE_ME_CHECK(x1.lq(home,c-x0.min()));
00339     return (x0.max()+x1.max() <= c) ? home.ES_SUBSUMED(*this) : ES_FIX;
00340   }
00341 
00342 
00343 
00344 
00345   /*
00346    * Binary domain consistent greater equal
00347    *
00348    */
00349 
00350   template<class Val, class A, class B>
00351   forceinline
00352   GqBin<Val,A,B>::GqBin(Home home, A x0, B x1, Val c)
00353     : LinBin<Val,A,B,PC_INT_BND>(home,x0,x1,c) {}
00354 
00355   template<class Val, class A, class B>
00356   ExecStatus
00357   GqBin<Val,A,B>::post(Home home, A x0, B x1, Val c) {
00358     (void) new (home) GqBin<Val,A,B>(home,x0,x1,c);
00359     return ES_OK;
00360   }
00361 
00362 
00363   template<class Val, class A, class B>
00364   forceinline
00365   GqBin<Val,A,B>::GqBin(Space& home, bool share, GqBin<Val,A,B>& p)
00366     : LinBin<Val,A,B,PC_INT_BND>(home,share,p) {}
00367 
00368   template<class Val, class A, class B>
00369   Actor*
00370   GqBin<Val,A,B>::copy(Space& home, bool share) {
00371     return new (home) GqBin<Val,A,B>(home,share,*this);
00372   }
00373 
00374   template<class Val, class A, class B>
00375   forceinline
00376   GqBin<Val,A,B>::GqBin(Space& home, bool share, Propagator& p,
00377                         A x0, B x1, Val c)
00378     : LinBin<Val,A,B,PC_INT_BND>(home,share,p,x0,x1,c) {}
00379 
00380   template<class Val, class A, class B>
00381   ExecStatus
00382   GqBin<Val,A,B>::propagate(Space& home, const ModEventDelta&) {
00383     GECODE_ME_CHECK(x0.gq(home,c-x1.max()));
00384     GECODE_ME_CHECK(x1.gq(home,c-x0.max()));
00385     return (x0.min()+x1.min() >= c) ? home.ES_SUBSUMED(*this) : ES_FIX;
00386   }
00387 
00388 
00389 
00390 
00391   /*
00392    * Reified binary domain consistent less equal
00393    *
00394    */
00395 
00396   template<class Val, class A, class B>
00397   forceinline
00398   ReLqBin<Val,A,B>::ReLqBin(Home home, A x0, B x1, Val c, BoolView b)
00399     : ReLinBin<Val,A,B,PC_INT_BND,BoolView>(home,x0,x1,c,b) {}
00400 
00401   template<class Val, class A, class B>
00402   ExecStatus
00403   ReLqBin<Val,A,B>::post(Home home, A x0, B x1, Val c, BoolView b) {
00404     (void) new (home) ReLqBin<Val,A,B>(home,x0,x1,c,b);
00405     return ES_OK;
00406   }
00407 
00408 
00409   template<class Val, class A, class B>
00410   forceinline
00411   ReLqBin<Val,A,B>::ReLqBin(Space& home, bool share, ReLqBin<Val,A,B>& p)
00412     : ReLinBin<Val,A,B,PC_INT_BND,BoolView>(home,share,p) {}
00413 
00414   template<class Val, class A, class B>
00415   Actor*
00416   ReLqBin<Val,A,B>::copy(Space& home, bool share) {
00417     return new (home) ReLqBin<Val,A,B>(home,share,*this);
00418   }
00419 
00420   template<class Val, class A, class B>
00421   ExecStatus
00422   ReLqBin<Val,A,B>::propagate(Space& home, const ModEventDelta&) {
00423     if (b.one())
00424       GECODE_REWRITE(*this,(LqBin<Val,A,B>::post(home(*this),x0,x1,c)));
00425     if (b.zero())
00426       GECODE_REWRITE(*this,(GqBin<Val,A,B>::post(home(*this),x0,x1,c+1)));
00427     if (x0.max() + x1.max() <= c) {
00428       GECODE_ME_CHECK(b.one_none(home)); return home.ES_SUBSUMED(*this);
00429     }
00430     if (x0.min() + x1.min() > c) {
00431       GECODE_ME_CHECK(b.zero_none(home)); return home.ES_SUBSUMED(*this);
00432     }
00433     return ES_FIX;
00434   }
00435 
00436 }}}
00437 
00438 // STATISTICS: int-prop
00439