mult.icc

00001 /*
00002  *  Main authors:
00003  *     Christian Schulte <schulte@gecode.org>
00004  *
00005  *  Copyright:
00006  *     Christian Schulte, 2004
00007  *
00008  *  Last modified:
00009  *     $Date: 2006-08-04 16:03:26 +0200 (Fri, 04 Aug 2006) $ by $Author: schulte $
00010  *     $Revision: 3512 $
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 
00071 
00072   /*
00073    * Positive bounds-consistent squaring
00074    *
00075    */
00076   template <class VA, class VB>
00077   forceinline
00078   SquarePlus<VA,VB>::SquarePlus(Space* home, VA y0, VB y1)
00079     : Propagator(home), x0(y0), x1(y1) {
00080     x0.subscribe(home,this,PC_INT_BND);
00081     x1.subscribe(home,this,PC_INT_BND);
00082   }
00083 
00084   template <class VA, class VB>
00085   forceinline ExecStatus
00086   SquarePlus<VA,VB>::post(Space* home, VA x0, VB x1) {
00087     (void) new (home) SquarePlus<VA,VB>(home,x0,x1);
00088     return ES_OK;
00089   }
00090 
00091   template <class VA, class VB>
00092   forceinline
00093   SquarePlus<VA,VB>::SquarePlus(Space* home, bool share, SquarePlus<VA,VB>& p)
00094     : Propagator(home,share,p) {
00095     x0.update(home,share,p.x0);
00096     x1.update(home,share,p.x1);
00097   }
00098 
00099   template <class VA, class VB>
00100   Actor*
00101   SquarePlus<VA,VB>::copy(Space* home, bool share) {
00102     return new (home) SquarePlus<VA,VB>(home,share,*this);
00103   }
00104 
00105   template <class VA, class VB>
00106   PropCost
00107   SquarePlus<VA,VB>::cost(void) const {
00108     return PC_TERNARY_HI;
00109   }
00110 
00111   template <class VA, class VB>
00112   ExecStatus
00113   SquarePlus<VA,VB>::propagate(Space* home) {
00114     bool mod;
00115     do {
00116       mod = false;
00117       {
00118         ModEvent me = x0.lq(home,floor(sqrt(static_cast<double>(x1.max()))));
00119         if (me_failed(me)) return ES_FAILED;
00120         mod |= me_modified(me);
00121       }
00122       {
00123         ModEvent me = x0.gq(home,ceil(sqrt(static_cast<double>(x1.min()))));
00124         if (me_failed(me)) return ES_FAILED;
00125         mod |= me_modified(me);
00126       }
00127       {
00128         ModEvent me = x1.lq(home,x0.max()*x0.max());
00129         if (me_failed(me)) return ES_FAILED;
00130         mod |= me_modified(me);
00131       }
00132       {
00133         ModEvent me = x1.gq(home,x0.min()*x0.min());
00134         if (me_failed(me)) return ES_FAILED;
00135         mod |= me_modified(me);
00136       }
00137     } while (mod);
00138     return x0.assigned() ? ES_SUBSUMED : ES_FIX;
00139   }
00140 
00141   template <class VA, class VB>
00142   size_t
00143   SquarePlus<VA,VB>::dispose(Space* home) {
00144     assert(!home->failed());
00145     x0.cancel(home,this,PC_INT_BND);
00146     x1.cancel(home,this,PC_INT_BND);
00147     (void) Propagator::dispose(home);
00148     return sizeof(*this);
00149   }
00150 
00151 
00152   /*
00153    * Bounds-consistent Square
00154    *
00155    */
00156 
00157   template <class View>
00158   forceinline
00159   Square<View>::Square(Space* home, View x0, View x1)
00160     : BinaryPropagator<View,PC_INT_BND>(home,x0,x1) {}
00161 
00162   template <class View>
00163   forceinline ExecStatus
00164   Square<View>::post(Space* home, View x0, View x1) {
00165     GECODE_ME_CHECK(x1.gq(home,0));
00166     GECODE_ME_CHECK(x0.lq(home,floor(sqrt(static_cast<double>
00167                                           (Limits::Int::int_max)))));
00168     if (x0.min() >= 0)
00169       return SquarePlus<IntView,IntView>::post(home,x0,x1);
00170     if (x0.max() <= 0)
00171       return SquarePlus<MinusView,IntView>::post(home,x0,x1);
00172     (void) new (home) Square<View>(home,x0,x1);
00173     return ES_OK;
00174   }
00175 
00176   template <class View>
00177   forceinline
00178   Square<View>::Square(Space* home, bool share, Square<View>& p)
00179     : BinaryPropagator<View,PC_INT_BND>(home,share,p) {}
00180 
00181   template <class View>
00182   Actor*
00183   Square<View>::copy(Space* home, bool share) {
00184     return new (home) Square<View>(home,share,*this);
00185   }
00186 
00187   template <class View>
00188   PropCost
00189   Square<View>::cost(void) const {
00190     return PC_BINARY_HI;
00191   }
00192 
00193   template <class View>
00194   ExecStatus
00195   Square<View>::propagate(Space* home) {
00196     // x0 * x0 = x1
00197     assert(x1.min() >= 0);
00198     if (x0.min() >= 0)
00199       return (SquarePlus<IntView,IntView>::post(home,x0,x1)
00200               == ES_FAILED) ? ES_FAILED : ES_SUBSUMED;
00201     if (x0.max() <= 0)
00202       return (SquarePlus<MinusView,IntView>::post(home,x0,x1)
00203               == ES_FAILED) ? ES_FAILED : ES_SUBSUMED;
00204 
00205     GECODE_ME_CHECK(x1.lq(home,std::max(x0.min()*x0.min(),
00206                                         x0.max()*x0.max())));
00207 
00208     int s = static_cast<int>(floor(sqrt(static_cast<double>(x1.max()))));
00209 
00210     GECODE_ME_CHECK(x0.gq(home,-s));
00211     GECODE_ME_CHECK(x0.lq(home,s));
00212 
00213     if (x0.assigned() && x1.assigned())
00214       return (x0.val()*x0.val() == x1.val()) ? ES_SUBSUMED : ES_FAILED;
00215 
00216     return ES_NOFIX;
00217   }
00218 
00219 
00220   /*
00221    * Positive bounds-consistent multiplication
00222    *
00223    */
00224   template <class VA, class VB, class VC>
00225   inline
00226   MultPlus<VA,VB,VC>::MultPlus(Space* home, VA y0, VB y1, VC y2)
00227     : Propagator(home), x0(y0), x1(y1), x2(y2) {
00228     x0.subscribe(home,this,PC_INT_BND);
00229     x1.subscribe(home,this,PC_INT_BND);
00230     x2.subscribe(home,this,PC_INT_BND);
00231   }
00232 
00233   template <class VA, class VB, class VC>
00234   inline ExecStatus
00235   MultPlus<VA,VB,VC>::post(Space* home, VA x0, VB x1, VC x2) {
00236     GECODE_ME_CHECK(x0.gr(home,0));
00237     GECODE_ME_CHECK(x1.gr(home,0));
00238     GECODE_ME_CHECK(x2.gr(home,0));
00239     (void) new (home) MultPlus<VA,VB,VC>(home,x0,x1,x2);
00240     return ES_OK;
00241   }
00242 
00243   template <class VA, class VB, class VC>
00244   forceinline
00245   MultPlus<VA,VB,VC>::MultPlus(Space* home, bool share, MultPlus<VA,VB,VC>& p)
00246     : Propagator(home,share,p) {
00247     x0.update(home,share,p.x0);
00248     x1.update(home,share,p.x1);
00249     x2.update(home,share,p.x2);
00250   }
00251 
00252   template <class VA, class VB, class VC>
00253   Actor*
00254   MultPlus<VA,VB,VC>::copy(Space* home, bool share) {
00255     return new (home) MultPlus<VA,VB,VC>(home,share,*this);
00256   }
00257 
00258   template <class VA, class VB, class VC>
00259   PropCost
00260   MultPlus<VA,VB,VC>::cost(void) const {
00261     return PC_TERNARY_HI;
00262   }
00263 
00264   template <class VA, class VB, class VC>
00265   ExecStatus
00266   MultPlus<VA,VB,VC>::propagate(Space* home) {
00267     assert(p(x0) && p(x1) && p(x2));
00268     bool mod;
00269     do {
00270       mod = false;
00271       {
00272         ModEvent me = x2.lq(home,m(x0.max(),x1.max()));
00273         if (me_failed(me)) return ES_FAILED;
00274         mod |= me_modified(me);
00275       }
00276       {
00277         ModEvent me = x2.gq(home,m(x0.min(),x1.min()));
00278         if (me_failed(me)) return ES_FAILED;
00279         mod |= me_modified(me);
00280       }
00281       {
00282         ModEvent me = x0.lq(home,f_d(x2.max(),x1.min()));
00283         if (me_failed(me)) return ES_FAILED;
00284         mod |= me_modified(me);
00285       }
00286       {
00287         ModEvent me = x0.gq(home,c_d(x2.min(),x1.max()));
00288         if (me_failed(me)) return ES_FAILED;
00289         mod |= me_modified(me);
00290       }
00291       {
00292         ModEvent me = x1.lq(home,f_d(x2.max(),x0.min()));
00293         if (me_failed(me)) return ES_FAILED;
00294         mod |= me_modified(me);
00295       }
00296       {
00297         ModEvent me = x1.gq(home,c_d(x2.min(),x0.max()));
00298         if (me_failed(me)) return ES_FAILED;
00299         mod |= me_modified(me);
00300       }
00301     } while (mod);
00302     return x0.assigned() && x1.assigned() ? ES_SUBSUMED : ES_FIX;
00303   }
00304 
00305   template <class VA, class VB, class VC>
00306   size_t
00307   MultPlus<VA,VB,VC>::dispose(Space* home) {
00308     assert(!home->failed());
00309     x0.cancel(home,this,PC_INT_BND);
00310     x1.cancel(home,this,PC_INT_BND);
00311     x2.cancel(home,this,PC_INT_BND);
00312     (void) Propagator::dispose(home);
00313     return sizeof(*this);
00314   }
00315 
00316 
00317   /*
00318    * Bounds-consistent multiplication
00319    *
00320    */
00321 
00322   template <class View>
00323   forceinline
00324   Mult<View>::Mult(Space* home, View x0, View x1, View x2)
00325     : TernaryPropagator<View,PC_INT_BND>(home,x0,x1,x2) {}
00326 
00327   template <class View>
00328   forceinline
00329   Mult<View>::Mult(Space* home, bool share, Mult<View>& p)
00330     : TernaryPropagator<View,PC_INT_BND>(home,share,p) {}
00331 
00332   template <class View>
00333   Actor*
00334   Mult<View>::copy(Space* home, bool share) {
00335     return new (home) Mult<View>(home,share,*this);
00336   }
00337 
00338   template <class View>
00339   PropCost
00340   Mult<View>::cost(void) const {
00341     return PC_TERNARY_HI;
00342   }
00343 
00344   template <class View>
00345   ExecStatus
00346   Mult<View>::propagate(Space* home) {
00347     if (p(x0)) {
00348       if (p(x1) || p(x2)) goto rewrite_ppp;
00349       if (n(x1) || n(x2)) goto rewrite_pnn;
00350       goto prop_pxx;
00351     }
00352     if (n(x0)) {
00353       if (n(x1) || p(x2)) goto rewrite_nnp;
00354       if (p(x1) || n(x2)) goto rewrite_npn;
00355       goto prop_nxx;
00356     }
00357     if (p(x1)) {
00358       if (p(x2)) goto rewrite_ppp;
00359       if (n(x2)) goto rewrite_npn;
00360       goto prop_xpx;
00361     }
00362     if (n(x1)) {
00363       if (p(x2)) goto rewrite_nnp;
00364       if (n(x2)) goto rewrite_pnn;
00365       goto prop_xnx;
00366     }
00367 
00368     assert(x(x0) && x(x1));
00369     GECODE_ME_CHECK(x2.lq(home,std::max(m(x0.max(),x1.max()),
00370                                         m(x0.min(),x1.min()))));
00371     GECODE_ME_CHECK(x2.gq(home,std::min(m(x0.min(),x1.max()),
00372                                         m(x0.max(),x1.min()))));
00373 
00374     if (x0.assigned()) {
00375       assert((x0.val() == 0) && (x2.val() == 0));
00376       return ES_SUBSUMED;
00377     }
00378 
00379     if (x1.assigned()) {
00380       assert((x1.val() == 0) && (x2.val() == 0));
00381       return ES_SUBSUMED;
00382     }
00383 
00384     return ES_NOFIX;
00385 
00386   prop_xpx:
00387     std::swap(x0,x1);
00388   prop_pxx:
00389     assert(p(x0) && x(x1) && x(x2));
00390 
00391     GECODE_ME_CHECK(x2.lq(home,m(x0.max(),x1.max())));
00392     GECODE_ME_CHECK(x2.gq(home,m(x0.max(),x1.min())));
00393 
00394     if (p(x2)) goto rewrite_ppp;
00395     if (n(x2)) goto rewrite_pnn;
00396 
00397     GECODE_ME_CHECK(x1.lq(home,f_d(x2.max(),x0.min())));
00398     GECODE_ME_CHECK(x1.gq(home,c_d(x2.min(),x0.min())));
00399 
00400     if (x0.assigned() && x1.assigned()) {
00401       GECODE_ME_CHECK(x2.eq(home,m(x0.val(),x1.val())));
00402       return ES_SUBSUMED;
00403     }
00404 
00405     return ES_NOFIX;
00406 
00407   prop_xnx:
00408     std::swap(x0,x1);
00409   prop_nxx:
00410     assert(n(x0) && x(x1) && x(x2));
00411 
00412     GECODE_ME_CHECK(x2.lq(home,m(x0.min(),x1.min())));
00413     GECODE_ME_CHECK(x2.gq(home,m(x0.min(),x1.max())));
00414 
00415     if (p(x2)) goto rewrite_nnp;
00416     if (n(x2)) goto rewrite_npn;
00417 
00418     GECODE_ME_CHECK(x1.lq(home,f_d(x2.min(),x0.max())));
00419     GECODE_ME_CHECK(x1.gq(home,c_d(x2.max(),x0.max())));
00420 
00421     if (x0.assigned() && x1.assigned()) {
00422       GECODE_ME_CHECK(x2.eq(home,m(x0.val(),x1.val())));
00423       return ES_SUBSUMED;
00424     }
00425 
00426     return ES_NOFIX;
00427 
00428   rewrite_ppp:
00429     return (MultPlus<IntView,IntView,IntView>::post(home,x0,x1,x2)
00430             == ES_FAILED) ? ES_FAILED : ES_SUBSUMED;
00431 
00432   rewrite_nnp:
00433     return (MultPlus<MinusView,MinusView,IntView>::post(home,x0,x1,x2)
00434             == ES_FAILED) ? ES_FAILED : ES_SUBSUMED;
00435 
00436   rewrite_pnn:
00437     std::swap(x0,x1);
00438   rewrite_npn:
00439     return (MultPlus<MinusView,IntView,MinusView>::post(home,x0,x1,x2)
00440             == ES_FAILED) ? ES_FAILED : ES_SUBSUMED;
00441 
00442   }
00443 
00444   template <class View>
00445   ExecStatus
00446   Mult<View>::post(Space* home, View x0, View x1, View x2) {
00447     if (same(x0,x1))
00448       return Square<View>::post(home,x0,x2);
00449     if (p(x0)) {
00450       if (p(x1) || p(x2)) goto post_ppp;
00451       if (n(x1) || n(x2)) goto post_pnn;
00452     } else if (n(x0)) {
00453       if (n(x1) || p(x2)) goto post_nnp;
00454       if (p(x1) || n(x2)) goto post_npn;
00455     } else if (p(x1)) {
00456       if (p(x2)) goto post_ppp;
00457       if (n(x2)) goto post_npn;
00458     } else if (n(x1)) {
00459       if (p(x2)) goto post_nnp;
00460       if (n(x2)) goto post_pnn;
00461     }
00462     (void) new (home) Mult<View>(home,x0,x1,x2);
00463     return ES_OK;
00464 
00465   post_ppp:
00466     return MultPlus<IntView,IntView,IntView>::post(home,x0,x1,x2);
00467   post_nnp:
00468     return MultPlus<MinusView,MinusView,IntView>::post(home,x0,x1,x2);
00469   post_pnn:
00470     std::swap(x0,x1);
00471   post_npn:
00472     return MultPlus<MinusView,IntView,MinusView>::post(home,x0,x1,x2);
00473   }
00474 
00475 }}}
00476 
00477 // STATISTICS: int-prop
00478