Generated on Thu Jul 6 07:06:41 2006 for Gecode by doxygen 1.4.7

mult.icc

Go to the documentation of this file.
00001 /*
00002  *  Main authors:
00003  *     Christian Schulte <schulte@gecode.org>
00004  *
00005  *  Copyright:
00006  *     Christian Schulte, 2004
00007  *
00008  *  Last modified:
00009  *     $Date: 2006-05-29 09:42:21 +0200 (Mon, 29 May 2006) $ by $Author: schulte $
00010  *     $Revision: 3246 $
00011  *
00012  *  This file is part of Gecode, the generic constraint
00013  *  development environment:
00014  *     http://www.gecode.org
00015  *
00016  *  See the file "LICENSE" for information on usage and
00017  *  redistribution of this file, and for a
00018  *     DISCLAIMER OF ALL WARRANTIES.
00019  *
00020  */
00021 
00022 #include <cmath>
00023 
00024 namespace Gecode { namespace Int { namespace Arithmetic {
00025 
00026   /*
00027    * Arithmetic help functions
00028    *
00029    */
00030 
00032   forceinline double 
00033   m(int a, int b) {
00034     return static_cast<double>(a)*static_cast<double>(b);
00035   }
00036 
00038   forceinline int
00039   f_d(int x, int y) {
00040     return static_cast<int>(floor(static_cast<double>(x) /
00041                                   static_cast<double>(y)));
00042   }
00043 
00045   forceinline int
00046   c_d(int x, int y) {
00047     return static_cast<int>(ceil(static_cast<double>(x) /
00048                                  static_cast<double>(y)));
00049   }
00050 
00052   template <class View>
00053   forceinline bool 
00054   p(const View& x) {
00055     return x.min() > 0;
00056   }
00058   template <class View>
00059   forceinline bool 
00060   n(const View& x) {
00061     return x.max() < 0;
00062   }
00064   template <class View>
00065   forceinline bool 
00066   x(const View& x) {
00067     return (x.min() <= 0) && (x.max() >= 0);
00068   }
00069 
00070 
00072 #define GECODE_CM(TELL)                         \
00073 {                                               \
00074   ModEvent me = (TELL);                         \
00075   if (me_failed(me))   return ES_FAILED;        \
00076   if (me_modified(me)) mod = true;              \
00077 }
00078 
00079 
00080   /*
00081    * Positive bounds-consistent squaring
00082    *
00083    */
00084   template <class VA, class VB>
00085   forceinline
00086   SquarePlus<VA,VB>::SquarePlus(Space* home, VA y0, VB y1) 
00087     : Propagator(home), x0(y0), x1(y1) {
00088     x0.subscribe(home,this,PC_INT_BND);
00089     x1.subscribe(home,this,PC_INT_BND);
00090   }
00091 
00092   template <class VA, class VB>
00093   forceinline ExecStatus
00094   SquarePlus<VA,VB>::post(Space* home, VA x0, VB x1) {
00095     (void) new (home) SquarePlus<VA,VB>(home,x0,x1);
00096     return ES_OK;
00097   }
00098 
00099   template <class VA, class VB>
00100   forceinline
00101   SquarePlus<VA,VB>::SquarePlus(Space* home, bool share, SquarePlus<VA,VB>& p)
00102     : Propagator(home,share,p) {
00103     x0.update(home,share,p.x0);
00104     x1.update(home,share,p.x1);
00105   }
00106   
00107   template <class VA, class VB>
00108   Actor*
00109   SquarePlus<VA,VB>::copy(Space* home, bool share) {
00110     return new (home) SquarePlus<VA,VB>(home,share,*this);
00111   }
00112 
00113   template <class VA, class VB>
00114   PropCost
00115   SquarePlus<VA,VB>::cost(void) const {
00116     return PC_TERNARY_HI;
00117   }
00118   
00119   template <class VA, class VB>
00120   ExecStatus
00121   SquarePlus<VA,VB>::propagate(Space* home) {
00122     bool mod;
00123     do {
00124       mod = false;
00125       GECODE_CM(x0.lq(home,floor(sqrt(static_cast<double>(x1.max())))));
00126       GECODE_CM(x0.gq(home,ceil(sqrt(static_cast<double>(x1.min())))));
00127       GECODE_CM(x1.lq(home,x0.max()*x0.max()));
00128       GECODE_CM(x1.gq(home,x0.min()*x0.min()));
00129     } while (mod);
00130     return x0.assigned() ? ES_SUBSUMED : ES_FIX;
00131   }
00132   
00133   template <class VA, class VB>
00134   size_t
00135   SquarePlus<VA,VB>::dispose(Space* home) {
00136     assert(!home->failed());
00137     x0.cancel(home,this,PC_INT_BND);
00138     x1.cancel(home,this,PC_INT_BND);
00139     (void) Propagator::dispose(home);
00140     return sizeof(*this);
00141   }
00142   
00143   
00144   /*
00145    * Bounds-consistent Square
00146    *
00147    */
00148 
00149   template <class View>
00150   forceinline
00151   Square<View>::Square(Space* home, View x0, View x1)
00152     : BinaryPropagator<View,PC_INT_BND>(home,x0,x1) {}
00153 
00154   template <class View>
00155   forceinline ExecStatus
00156   Square<View>::post(Space* home, View x0, View x1) {
00157     GECODE_ME_CHECK(x1.gq(home,0));
00158     GECODE_ME_CHECK(x0.lq(home,floor(sqrt(static_cast<double>
00159                                           (Limits::Int::int_max)))));
00160     //    GECODE_ME_CHECK(x0.gq(home,floor(-sqrt(static_cast<double>
00161     //                                     (-Limits::Int::int_min)))));
00162     if (x0.min() >= 0)
00163       return SquarePlus<IntView,IntView>::post(home,x0,x1);
00164     if (x0.max() <= 0)
00165       return SquarePlus<MinusView,IntView>::post(home,x0,x1);
00166     (void) new (home) Square<View>(home,x0,x1);
00167     return ES_OK;
00168   }
00169 
00170   template <class View>
00171   forceinline
00172   Square<View>::Square(Space* home, bool share, Square<View>& p)
00173     : BinaryPropagator<View,PC_INT_BND>(home,share,p) {}
00174 
00175   template <class View>
00176   Actor*
00177   Square<View>::copy(Space* home, bool share) {
00178     return new (home) Square<View>(home,share,*this);
00179   }
00180 
00181   template <class View>
00182   PropCost
00183   Square<View>::cost(void) const {
00184     return PC_BINARY_HI;
00185   }
00186 
00187   template <class View>
00188   ExecStatus
00189   Square<View>::propagate(Space* home) {
00190     // x0 * x0 = x1
00191     assert(x1.min() >= 0);
00192     if (x0.min() >= 0)
00193       return (SquarePlus<IntView,IntView>::post(home,x0,x1) 
00194               == ES_FAILED) ? ES_FAILED : ES_SUBSUMED;
00195     if (x0.max() <= 0)
00196       return (SquarePlus<MinusView,IntView>::post(home,x0,x1) 
00197               == ES_FAILED) ? ES_FAILED : ES_SUBSUMED;
00198 
00199     GECODE_ME_CHECK(x1.lq(home,std::max(x0.min()*x0.min(),
00200                                         x0.max()*x0.max())));
00201 
00202     int s = static_cast<int>(floor(sqrt(static_cast<double>(x1.max()))));
00203 
00204     GECODE_ME_CHECK(x0.gq(home,-s));
00205     GECODE_ME_CHECK(x0.lq(home,s));
00206 
00207     if (x0.assigned() && x1.assigned())
00208       return (x0.val()*x0.val() == x1.val()) ? ES_SUBSUMED : ES_FAILED;
00209 
00210     return ES_NOFIX;
00211   }
00212 
00213 
00214   /*
00215    * Positive bounds-consistent multiplication
00216    *
00217    */
00218   template <class VA, class VB, class VC>
00219   inline
00220   MultPlus<VA,VB,VC>::MultPlus(Space* home, VA y0, VB y1, VC y2) 
00221     : Propagator(home), x0(y0), x1(y1), x2(y2) {
00222     x0.subscribe(home,this,PC_INT_BND);
00223     x1.subscribe(home,this,PC_INT_BND);
00224     x2.subscribe(home,this,PC_INT_BND);
00225   }
00226 
00227   template <class VA, class VB, class VC>
00228   inline ExecStatus
00229   MultPlus<VA,VB,VC>::post(Space* home, VA x0, VB x1, VC x2) {
00230     GECODE_ME_CHECK(x0.gr(home,0));
00231     GECODE_ME_CHECK(x1.gr(home,0));
00232     GECODE_ME_CHECK(x2.gr(home,0));
00233     (void) new (home) MultPlus<VA,VB,VC>(home,x0,x1,x2);
00234     return ES_OK;
00235   }
00236 
00237   template <class VA, class VB, class VC>
00238   forceinline
00239   MultPlus<VA,VB,VC>::MultPlus(Space* home, bool share, MultPlus<VA,VB,VC>& p)
00240     : Propagator(home,share,p) {
00241     x0.update(home,share,p.x0);
00242     x1.update(home,share,p.x1);
00243     x2.update(home,share,p.x2);
00244   }
00245   
00246   template <class VA, class VB, class VC>
00247   Actor*
00248   MultPlus<VA,VB,VC>::copy(Space* home, bool share) {
00249     return new (home) MultPlus<VA,VB,VC>(home,share,*this);
00250   }
00251 
00252   template <class VA, class VB, class VC>
00253   PropCost
00254   MultPlus<VA,VB,VC>::cost(void) const {
00255     return PC_TERNARY_HI;
00256   }
00257   
00258   template <class VA, class VB, class VC>
00259   ExecStatus
00260   MultPlus<VA,VB,VC>::propagate(Space* home) {
00261     assert(p(x0) && p(x1) && p(x2));
00262     bool mod;
00263     do {
00264       mod = false;
00265       GECODE_CM(x2.lq(home,m(x0.max(),x1.max())));
00266       GECODE_CM(x2.gq(home,m(x0.min(),x1.min())));
00267       GECODE_CM(x0.lq(home,f_d(x2.max(),x1.min())));
00268       GECODE_CM(x0.gq(home,c_d(x2.min(),x1.max())));
00269       GECODE_CM(x1.lq(home,f_d(x2.max(),x0.min())));
00270       GECODE_CM(x1.gq(home,c_d(x2.min(),x0.max())));
00271     } while (mod);
00272     return x0.assigned() && x1.assigned() ? ES_SUBSUMED : ES_FIX;
00273   }
00274   
00275   template <class VA, class VB, class VC>
00276   size_t
00277   MultPlus<VA,VB,VC>::dispose(Space* home) {
00278     assert(!home->failed());
00279     x0.cancel(home,this,PC_INT_BND);
00280     x1.cancel(home,this,PC_INT_BND);
00281     x2.cancel(home,this,PC_INT_BND);
00282     (void) Propagator::dispose(home);
00283     return sizeof(*this);
00284   }
00285   
00286   
00287   /*
00288    * Bounds-consistent multiplication
00289    *
00290    */
00291 
00292   template <class View>
00293   forceinline
00294   Mult<View>::Mult(Space* home, View x0, View x1, View x2)
00295     : TernaryPropagator<View,PC_INT_BND>(home,x0,x1,x2) {}
00296 
00297   template <class View>
00298   forceinline
00299   Mult<View>::Mult(Space* home, bool share, Mult<View>& p)
00300     : TernaryPropagator<View,PC_INT_BND>(home,share,p) {}
00301 
00302   template <class View>
00303   Actor*
00304   Mult<View>::copy(Space* home, bool share) {
00305     return new (home) Mult<View>(home,share,*this);
00306   }
00307 
00308   template <class View>
00309   PropCost
00310   Mult<View>::cost(void) const {
00311     return PC_TERNARY_HI;
00312   }
00313 
00314   template <class View>
00315   ExecStatus
00316   Mult<View>::propagate(Space* home) {
00317     if (p(x0)) {
00318       if (p(x1) || p(x2)) goto rewrite_ppp;
00319       if (n(x1) || n(x2)) goto rewrite_pnn;
00320       goto prop_pxx;
00321     }
00322     if (n(x0)) {
00323       if (n(x1) || p(x2)) goto rewrite_nnp;
00324       if (p(x1) || n(x2)) goto rewrite_npn;
00325       goto prop_nxx; 
00326     }
00327     if (p(x1)) {
00328       if (p(x2)) goto rewrite_ppp;
00329       if (n(x2)) goto rewrite_npn;
00330       goto prop_xpx; 
00331     }
00332     if (n(x1)) {
00333       if (p(x2)) goto rewrite_nnp;
00334       if (n(x2)) goto rewrite_pnn;
00335       goto prop_xnx; 
00336     }
00337 
00338     assert(x(x0) && x(x1));
00339     GECODE_ME_CHECK(x2.lq(home,std::max(m(x0.max(),x1.max()),
00340                                         m(x0.min(),x1.min()))));
00341     GECODE_ME_CHECK(x2.gq(home,std::min(m(x0.min(),x1.max()),
00342                                         m(x0.max(),x1.min()))));
00343 
00344     if (x0.assigned()) {
00345       assert((x0.val() == 0) && (x2.val() == 0));
00346       return ES_SUBSUMED;
00347     }
00348 
00349     if (x1.assigned()) {
00350       assert((x1.val() == 0) && (x2.val() == 0));
00351       return ES_SUBSUMED;
00352     }
00353 
00354     return ES_NOFIX;
00355 
00356   prop_xpx:
00357     std::swap(x0,x1);
00358   prop_pxx:
00359     assert(p(x0) && x(x1) && x(x2));
00360 
00361     GECODE_ME_CHECK(x2.lq(home,m(x0.max(),x1.max())));
00362     GECODE_ME_CHECK(x2.gq(home,m(x0.max(),x1.min())));
00363     
00364     if (p(x2)) goto rewrite_ppp;
00365     if (n(x2)) goto rewrite_pnn;
00366     
00367     GECODE_ME_CHECK(x1.lq(home,f_d(x2.max(),x0.min())));
00368     GECODE_ME_CHECK(x1.gq(home,c_d(x2.min(),x0.min())));
00369     
00370     if (x0.assigned() && x1.assigned()) {
00371       GECODE_ME_CHECK(x2.eq(home,m(x0.val(),x1.val())));
00372       return ES_SUBSUMED;
00373     }
00374 
00375     return ES_NOFIX;
00376 
00377   prop_xnx:
00378     std::swap(x0,x1);
00379   prop_nxx:
00380     assert(n(x0) && x(x1) && x(x2));
00381 
00382     GECODE_ME_CHECK(x2.lq(home,m(x0.min(),x1.min())));
00383     GECODE_ME_CHECK(x2.gq(home,m(x0.min(),x1.max())));
00384     
00385     if (p(x2)) goto rewrite_nnp;
00386     if (n(x2)) goto rewrite_npn;
00387     
00388     GECODE_ME_CHECK(x1.lq(home,f_d(x2.min(),x0.max())));
00389     GECODE_ME_CHECK(x1.gq(home,c_d(x2.max(),x0.max())));
00390     
00391     if (x0.assigned() && x1.assigned()) {
00392       GECODE_ME_CHECK(x2.eq(home,m(x0.val(),x1.val())));
00393       return ES_SUBSUMED;
00394     }
00395 
00396     return ES_NOFIX;
00397 
00398   rewrite_ppp:
00399     return (MultPlus<IntView,IntView,IntView>::post(home,x0,x1,x2) 
00400             == ES_FAILED) ? ES_FAILED : ES_SUBSUMED;
00401 
00402   rewrite_nnp:
00403     return (MultPlus<MinusView,MinusView,IntView>::post(home,x0,x1,x2) 
00404             == ES_FAILED) ? ES_FAILED : ES_SUBSUMED;
00405 
00406   rewrite_pnn:
00407     std::swap(x0,x1);   
00408   rewrite_npn:
00409     return (MultPlus<MinusView,IntView,MinusView>::post(home,x0,x1,x2) 
00410             == ES_FAILED) ? ES_FAILED : ES_SUBSUMED;
00411 
00412   }
00413 
00414   template <class View>
00415   ExecStatus
00416   Mult<View>::post(Space* home, View x0, View x1, View x2) {
00417     if (same(x0,x1))
00418       return Square<View>::post(home,x0,x2);
00419     if (p(x0)) {
00420       if (p(x1) || p(x2)) goto post_ppp;
00421       if (n(x1) || n(x2)) goto post_pnn;
00422     } else if (n(x0)) {
00423       if (n(x1) || p(x2)) goto post_nnp;
00424       if (p(x1) || n(x2)) goto post_npn;
00425     } else if (p(x1)) {
00426       if (p(x2)) goto post_ppp;
00427       if (n(x2)) goto post_npn;
00428     } else if (n(x1)) {
00429       if (p(x2)) goto post_nnp;
00430       if (n(x2)) goto post_pnn;
00431     }
00432     (void) new (home) Mult<View>(home,x0,x1,x2);
00433     return ES_OK;
00434 
00435   post_ppp:
00436     return MultPlus<IntView,IntView,IntView>::post(home,x0,x1,x2);
00437   post_nnp:
00438     return MultPlus<MinusView,MinusView,IntView>::post(home,x0,x1,x2);
00439   post_pnn:
00440     std::swap(x0,x1);   
00441   post_npn:
00442     return MultPlus<MinusView,IntView,MinusView>::post(home,x0,x1,x2);
00443   }
00444 
00445 
00446 #undef GECODE_CM
00447 
00448 }}}
00449 
00450 // STATISTICS: int-prop
00451