Generated on Thu Mar 22 10:39:33 2012 for Gecode by doxygen 1.6.3

sqrt.hpp

Go to the documentation of this file.
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, 2008
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 #include <cmath>
00039 
00040 namespace Gecode { namespace Int { namespace Arithmetic {
00041 
00042   /*
00043    * Bounds consistent square root
00044    *
00045    */
00046 
00047   template<class View>
00048   forceinline ExecStatus
00049   prop_sqrt_bnd(Space& home, View x0, View x1) {
00050     bool mod;
00051     do {
00052       mod = false;
00053       {
00054         ModEvent me =
00055           x1.lq(home,floor(::sqrt(static_cast<double>(x0.max()))));
00056         if (me_failed(me)) return ES_FAILED;
00057         mod |= me_modified(me);
00058       }
00059       {
00060         ModEvent me =
00061           x1.gq(home,floor(::sqrt(static_cast<double>(x0.min()))));
00062         if (me_failed(me)) return ES_FAILED;
00063         mod |= me_modified(me);
00064         }
00065       {
00066         double next = static_cast<double>(x1.max()+1);
00067         ModEvent me = x0.le(home,next*next);
00068         if (me_failed(me)) return ES_FAILED;
00069         mod |= me_modified(me);
00070       }
00071       {
00072         ModEvent me = x0.gq(home,x1.min()*x1.min());
00073         if (me_failed(me)) return ES_FAILED;
00074         mod |= me_modified(me);
00075       }
00076     } while (mod);
00077     return ES_OK;
00078   }
00079 
00080   template<class View>
00081   forceinline
00082   SqrtBnd<View>::SqrtBnd(Home home, View x0, View x1)
00083     : BinaryPropagator<View,PC_INT_BND>(home,x0,x1) {}
00084 
00085   template<class View>
00086   forceinline ExecStatus
00087   SqrtBnd<View>::post(Home home, View x0, View x1) {
00088     GECODE_ME_CHECK(x0.gq(home,0));
00089     if (same(x0,x1)) {
00090       GECODE_ME_CHECK(x1.lq(home,1));
00091     } else {
00092       GECODE_ME_CHECK(x1.gq(home,0));
00093       GECODE_ES_CHECK(prop_sqrt_bnd(home,x0,x1));
00094       (void) new (home) SqrtBnd<View>(home,x0,x1);
00095     }
00096     return ES_OK;
00097   }
00098 
00099   template<class View>
00100   forceinline
00101   SqrtBnd<View>::SqrtBnd(Space& home, bool share, SqrtBnd<View>& p)
00102     : BinaryPropagator<View,PC_INT_BND>(home,share,p) {}
00103 
00104   template<class View>
00105   Actor*
00106   SqrtBnd<View>::copy(Space& home, bool share) {
00107     return new (home) SqrtBnd<View>(home,share,*this);
00108   }
00109 
00110   template<class View>
00111   ExecStatus
00112   SqrtBnd<View>::propagate(Space& home, const ModEventDelta&) {
00113     GECODE_ES_CHECK(prop_sqrt_bnd(home,x0,x1));
00114     return x1.assigned() ? home.ES_SUBSUMED(*this) : ES_FIX;
00115   }
00116 
00117 
00118   /*
00119    * Domain consistent square root
00120    *
00121    */
00123   class RangesMapSqr {
00124   public:
00126     forceinline int min(int n) const {
00127       return n*n;
00128     }
00130     forceinline int max(int n) const {
00131       return (n+1)*(n+1)-1;
00132     }
00133   };
00134 
00136   class RangesMapSqrt {
00137   public:
00139     forceinline int min(int n) const {
00140       return static_cast<int>(floor(::sqrt(static_cast<double>(n))));
00141     }
00143     forceinline int max(int n) const {
00144       return static_cast<int>(floor(::sqrt(static_cast<double>(n))));
00145     }
00146  };
00147 
00148   template<class View>
00149   forceinline
00150   SqrtDom<View>::SqrtDom(Home home, View x0, View x1)
00151     : BinaryPropagator<View,PC_INT_DOM>(home,x0,x1) {}
00152 
00153   template<class View>
00154   forceinline ExecStatus
00155   SqrtDom<View>::post(Home home, View x0, View x1) {
00156     GECODE_ME_CHECK(x0.gq(home,0));
00157     if (same(x0,x1)) {
00158       GECODE_ME_CHECK(x1.lq(home,1));
00159     } else {
00160       GECODE_ME_CHECK(x1.gq(home,0));
00161       GECODE_ES_CHECK(prop_sqrt_bnd(home,x0,x1));
00162       (void) new (home) SqrtDom<View>(home,x0,x1);
00163     }
00164     return ES_OK;
00165   }
00166 
00167   template<class View>
00168   forceinline
00169   SqrtDom<View>::SqrtDom(Space& home, bool share, SqrtDom<View>& p)
00170     : BinaryPropagator<View,PC_INT_DOM>(home,share,p) {}
00171 
00172   template<class View>
00173   Actor*
00174   SqrtDom<View>::copy(Space& home, bool share) {
00175     return new (home) SqrtDom<View>(home,share,*this);
00176   }
00177 
00178   template<class View>
00179   PropCost
00180   SqrtDom<View>::cost(const Space&, const ModEventDelta& med) const {
00181     if (View::me(med) == ME_INT_VAL)
00182       return PropCost::unary(PropCost::LO);
00183     else if (View::me(med) == ME_INT_DOM)
00184       return PropCost::binary(PropCost::HI);
00185     else
00186       return PropCost::binary(PropCost::LO);
00187   }
00188 
00189   template<class View>
00190   ExecStatus
00191   SqrtDom<View>::propagate(Space& home, const ModEventDelta& med) {
00192     if (View::me(med) != ME_INT_DOM) {
00193       GECODE_ES_CHECK(prop_sqrt_bnd(home,x0,x1));
00194       return x1.assigned() ? home.ES_SUBSUMED(*this)
00195         : home.ES_NOFIX_PARTIAL(*this,View::med(ME_INT_DOM));
00196     }
00197 
00198     {
00199       ViewRanges<View> r(x0);
00200       Iter::Ranges::Map<ViewRanges<View>,RangesMapSqrt,false> m(r);
00201       GECODE_ME_CHECK(x1.inter_r(home,m,false));
00202     }
00203 
00204     {
00205       ViewRanges<View> r(x1);
00206       Iter::Ranges::Map<ViewRanges<View>,RangesMapSqr,true> m(r);
00207       GECODE_ME_CHECK(x0.inter_r(home,m,false));
00208     }
00209 
00210     return x1.assigned() ? home.ES_SUBSUMED(*this) : ES_FIX;
00211   }
00212 
00213 
00214 }}}
00215 
00216 // STATISTICS: int-prop
00217