Generated on Wed Jan 4 17:49:08 2006 for Gecode by doxygen 1.4.6

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: 2005-11-23 21:29:36 +0100 (Wed, 23 Nov 2005) $ by $Author: schulte $
00010  *     $Revision: 2628 $
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   SquarePlus<VA,VB>::~SquarePlus(void) {
00135     x0.cancel(this,PC_INT_BND);
00136     x1.cancel(this,PC_INT_BND);
00137   }
00138   
00139   
00140   /*
00141    * Bounds-consistent Square
00142    *
00143    */
00144 
00145   template <class View>
00146   forceinline
00147   Square<View>::Square(Space* home, View x0, View x1)
00148     : BinaryPropagator<View,PC_INT_BND>(home,x0,x1) {}
00149 
00150   template <class View>
00151   forceinline ExecStatus
00152   Square<View>::post(Space* home, View x0, View x1) {
00153     GECODE_ME_CHECK(x1.gq(home,0));
00154     GECODE_ME_CHECK(x0.lq(home,floor(sqrt(static_cast<double>(Limits::Int::int_max)))));
00155     if (x0.min() >= 0)
00156       return SquarePlus<IntView,IntView>::post(home,x0,x1);
00157     if (x0.max() <= 0)
00158       return SquarePlus<MinusView,IntView>::post(home,x0,x1);
00159     (void) new (home) Square<View>(home,x0,x1);
00160     return ES_OK;
00161   }
00162 
00163   template <class View>
00164   forceinline
00165   Square<View>::Square(Space* home, bool share, Square<View>& p)
00166     : BinaryPropagator<View,PC_INT_BND>(home,share,p) {}
00167 
00168   template <class View>
00169   Actor*
00170   Square<View>::copy(Space* home, bool share) {
00171     return new (home) Square<View>(home,share,*this);
00172   }
00173 
00174   template <class View>
00175   PropCost
00176   Square<View>::cost(void) const {
00177     return PC_BINARY_HI;
00178   }
00179 
00180   template <class View>
00181   ExecStatus
00182   Square<View>::propagate(Space* home) {
00183     // x0 * x0 = x1
00184     assert(x1.min() >= 0);
00185     if (x0.min() >= 0)
00186       return (SquarePlus<IntView,IntView>::post(home,x0,x1) 
00187               == ES_FAILED) ? ES_FAILED : ES_SUBSUMED;
00188     if (x0.max() <= 0)
00189       return (SquarePlus<MinusView,IntView>::post(home,x0,x1) 
00190               == ES_FAILED) ? ES_FAILED : ES_SUBSUMED;
00191 
00192     bool mod;
00193     do {
00194       mod = false;
00195       GECODE_CM(x1.lq(home,std::max(x0.min()*x0.min(),x0.max()*x0.max())));
00196       int s = static_cast<int>(floor(sqrt(static_cast<double>(x1.max()))));
00197       GECODE_CM(x0.gq(home,-s));
00198       GECODE_CM(x0.lq(home,s));
00199     } while (mod);
00200     return x0.assigned() && x1.assigned() ? ES_SUBSUMED : ES_FIX;
00201   }
00202 
00203 
00204   /*
00205    * Positive bounds-consistent multiplication
00206    *
00207    */
00208   template <class VA, class VB, class VC>
00209   inline
00210   MultPlus<VA,VB,VC>::MultPlus(Space* home, VA y0, VB y1, VC y2) 
00211     : Propagator(home), x0(y0), x1(y1), x2(y2) {
00212     x0.subscribe(home,this,PC_INT_BND);
00213     x1.subscribe(home,this,PC_INT_BND);
00214     x2.subscribe(home,this,PC_INT_BND);
00215   }
00216 
00217   template <class VA, class VB, class VC>
00218   inline ExecStatus
00219   MultPlus<VA,VB,VC>::post(Space* home, VA x0, VB x1, VC x2) {
00220     GECODE_ME_CHECK(x0.gr(home,0));
00221     GECODE_ME_CHECK(x1.gr(home,0));
00222     GECODE_ME_CHECK(x2.gr(home,0));
00223     (void) new (home) MultPlus<VA,VB,VC>(home,x0,x1,x2);
00224     return ES_OK;
00225   }
00226 
00227   template <class VA, class VB, class VC>
00228   forceinline
00229   MultPlus<VA,VB,VC>::MultPlus(Space* home, bool share, MultPlus<VA,VB,VC>& p)
00230     : Propagator(home,share,p) {
00231     x0.update(home,share,p.x0);
00232     x1.update(home,share,p.x1);
00233     x2.update(home,share,p.x2);
00234   }
00235   
00236   template <class VA, class VB, class VC>
00237   Actor*
00238   MultPlus<VA,VB,VC>::copy(Space* home, bool share) {
00239     return new (home) MultPlus<VA,VB,VC>(home,share,*this);
00240   }
00241 
00242   template <class VA, class VB, class VC>
00243   PropCost
00244   MultPlus<VA,VB,VC>::cost(void) const {
00245     return PC_TERNARY_HI;
00246   }
00247   
00248   template <class VA, class VB, class VC>
00249   ExecStatus
00250   MultPlus<VA,VB,VC>::propagate(Space* home) {
00251     assert(p(x0) && p(x1) && p(x2));
00252     bool mod;
00253     do {
00254       mod = false;
00255       GECODE_CM(x2.lq(home,m(x0.max(),x1.max())));
00256       GECODE_CM(x2.gq(home,m(x0.min(),x1.min())));
00257       GECODE_CM(x0.lq(home,f_d(x2.max(),x1.min())));
00258       GECODE_CM(x0.gq(home,c_d(x2.min(),x1.max())));
00259       GECODE_CM(x1.lq(home,f_d(x2.max(),x0.min())));
00260       GECODE_CM(x1.gq(home,c_d(x2.min(),x0.max())));
00261     } while (mod);
00262     return x0.assigned() && x1.assigned() ? ES_SUBSUMED : ES_FIX;
00263   }
00264   
00265   template <class VA, class VB, class VC>
00266   MultPlus<VA,VB,VC>::~MultPlus(void) {
00267     x0.cancel(this,PC_INT_BND);
00268     x1.cancel(this,PC_INT_BND);
00269     x2.cancel(this,PC_INT_BND);
00270   }
00271   
00272   
00273   /*
00274    * Bounds-consistent multiplication
00275    *
00276    */
00277 
00278   template <class View>
00279   forceinline
00280   Mult<View>::Mult(Space* home, View x0, View x1, View x2)
00281     : TernaryPropagator<View,PC_INT_BND>(home,x0,x1,x2) {}
00282 
00283   template <class View>
00284   forceinline
00285   Mult<View>::Mult(Space* home, bool share, Mult<View>& p)
00286     : TernaryPropagator<View,PC_INT_BND>(home,share,p) {}
00287 
00288   template <class View>
00289   Actor*
00290   Mult<View>::copy(Space* home, bool share) {
00291     return new (home) Mult<View>(home,share,*this);
00292   }
00293 
00294   template <class View>
00295   PropCost
00296   Mult<View>::cost(void) const {
00297     return PC_TERNARY_HI;
00298   }
00299 
00300   template <class View>
00301   ExecStatus
00302   Mult<View>::propagate(Space* home) {
00303     if (p(x0)) {
00304       if (p(x1) || p(x2)) goto rewrite_ppp;
00305       if (n(x1) || n(x2)) goto rewrite_pnn;
00306       goto prop_pxx;
00307     }
00308     if (n(x0)) {
00309       if (n(x1) || p(x2)) goto rewrite_nnp;
00310       if (p(x1) || n(x2)) goto rewrite_npn;
00311       goto prop_nxx; 
00312     }
00313     if (p(x1)) {
00314       if (p(x2)) goto rewrite_ppp;
00315       if (n(x2)) goto rewrite_npn;
00316       goto prop_xpx; 
00317     }
00318     if (n(x1)) {
00319       if (p(x2)) goto rewrite_nnp;
00320       if (n(x2)) goto rewrite_pnn;
00321       goto prop_xnx; 
00322     }
00323 
00324     assert(x(x0) && x(x1));
00325     GECODE_ME_CHECK(x2.lq(home,std::max(m(x0.max(),x1.max()),
00326                                         m(x0.min(),x1.min()))));
00327     GECODE_ME_CHECK(x2.gq(home,std::min(m(x0.min(),x1.max()),
00328                                         m(x0.max(),x1.min()))));
00329 
00330     if (x0.assigned()) {
00331       assert((x0.val() == 0) && (x2.val() == 0));
00332       return ES_SUBSUMED;
00333     }
00334 
00335     if (x1.assigned()) {
00336       assert((x1.val() == 0) && (x2.val() == 0));
00337       return ES_SUBSUMED;
00338     }
00339 
00340     return ES_NOFIX;
00341 
00342   prop_xpx:
00343     std::swap(x0,x1);
00344   prop_pxx:
00345     assert(p(x0) && x(x1) && x(x2));
00346 
00347     GECODE_ME_CHECK(x2.lq(home,m(x0.max(),x1.max())));
00348     GECODE_ME_CHECK(x2.gq(home,m(x0.max(),x1.min())));
00349     
00350     if (p(x2)) goto rewrite_ppp;
00351     if (n(x2)) goto rewrite_pnn;
00352     
00353     GECODE_ME_CHECK(x1.lq(home,f_d(x2.max(),x0.min())));
00354     GECODE_ME_CHECK(x1.gq(home,c_d(x2.min(),x0.min())));
00355     
00356     if (x0.assigned() && x1.assigned()) {
00357       GECODE_ME_CHECK(x2.eq(home,m(x0.val(),x1.val())));
00358       return ES_SUBSUMED;
00359     }
00360 
00361     return ES_NOFIX;
00362 
00363   prop_xnx:
00364     std::swap(x0,x1);
00365   prop_nxx:
00366     assert(n(x0) && x(x1) && x(x2));
00367 
00368     GECODE_ME_CHECK(x2.lq(home,m(x0.min(),x1.min())));
00369     GECODE_ME_CHECK(x2.gq(home,m(x0.min(),x1.max())));
00370     
00371     if (p(x2)) goto rewrite_nnp;
00372     if (n(x2)) goto rewrite_npn;
00373     
00374     GECODE_ME_CHECK(x1.lq(home,f_d(x2.min(),x0.max())));
00375     GECODE_ME_CHECK(x1.gq(home,c_d(x2.max(),x0.max())));
00376     
00377     if (x0.assigned() && x1.assigned()) {
00378       GECODE_ME_CHECK(x2.eq(home,m(x0.val(),x1.val())));
00379       return ES_SUBSUMED;
00380     }
00381 
00382     return ES_NOFIX;
00383 
00384   rewrite_ppp:
00385     return (MultPlus<IntView,IntView,IntView>::post(home,x0,x1,x2) 
00386             == ES_FAILED) ? ES_FAILED : ES_SUBSUMED;
00387 
00388   rewrite_nnp:
00389     return (MultPlus<MinusView,MinusView,IntView>::post(home,x0,x1,x2) 
00390             == ES_FAILED) ? ES_FAILED : ES_SUBSUMED;
00391 
00392   rewrite_pnn:
00393     std::swap(x0,x1);   
00394   rewrite_npn:
00395     return (MultPlus<MinusView,IntView,MinusView>::post(home,x0,x1,x2) 
00396             == ES_FAILED) ? ES_FAILED : ES_SUBSUMED;
00397 
00398   }
00399 
00400   template <class View>
00401   ExecStatus
00402   Mult<View>::post(Space* home, View x0, View x1, View x2) {
00403     if (same(x0,x1))
00404       return Square<View>::post(home,x0,x2);
00405     if (p(x0)) {
00406       if (p(x1) || p(x2)) goto post_ppp;
00407       if (n(x1) || n(x2)) goto post_pnn;
00408     } else if (n(x0)) {
00409       if (n(x1) || p(x2)) goto post_nnp;
00410       if (p(x1) || n(x2)) goto post_npn;
00411     } else if (p(x1)) {
00412       if (p(x2)) goto post_ppp;
00413       if (n(x2)) goto post_npn;
00414     } else if (n(x1)) {
00415       if (p(x2)) goto post_nnp;
00416       if (n(x2)) goto post_pnn;
00417     }
00418     (void) new (home) Mult<View>(home,x0,x1,x2);
00419     return ES_OK;
00420 
00421   post_ppp:
00422     return MultPlus<IntView,IntView,IntView>::post(home,x0,x1,x2);
00423   post_nnp:
00424     return MultPlus<MinusView,MinusView,IntView>::post(home,x0,x1,x2);
00425   post_pnn:
00426     std::swap(x0,x1);   
00427   post_npn:
00428     return MultPlus<MinusView,IntView,MinusView>::post(home,x0,x1,x2);
00429   }
00430 
00431 
00432 #undef GECODE_CM
00433 
00434 }}}
00435 
00436 // STATISTICS: int-prop
00437