00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
00031
00032
00033
00034
00035
00036
00037
00038 #include <cmath>
00039
00040 namespace Gecode { namespace Int { namespace Arithmetic {
00041
00042
00043
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(Space* 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(Space* 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 void
00101 SqrtBnd<View>::post(Space* home, Reflection::VarMap& vars,
00102 const Reflection::ActorSpec& spec) {
00103 spec.checkArity(2);
00104 View x0(home, vars, spec[0]);
00105 View x1(home, vars, spec[1]);
00106 (void) new (home) SqrtBnd<View>(home,x0,x1);
00107 }
00108
00109 template <class View>
00110 forceinline
00111 SqrtBnd<View>::SqrtBnd(Space* home, bool share, SqrtBnd<View>& p)
00112 : BinaryPropagator<View,PC_INT_BND>(home,share,p) {}
00113
00114 template <class View>
00115 Actor*
00116 SqrtBnd<View>::copy(Space* home, bool share) {
00117 return new (home) SqrtBnd<View>(home,share,*this);
00118 }
00119
00120 template <class View>
00121 ExecStatus
00122 SqrtBnd<View>::propagate(Space* home, ModEventDelta) {
00123 GECODE_ES_CHECK(prop_sqrt_bnd(home,x0,x1));
00124 return x1.assigned() ? ES_SUBSUMED(this,home) : ES_FIX;
00125 }
00126
00127 template <class View>
00128 Support::Symbol
00129 SqrtBnd<View>::ati(void) {
00130 return Reflection::mangle<View>("Gecode::Int::Arithmetic::SqrtBnd");
00131 }
00132
00133 template <class View>
00134 Reflection::ActorSpec
00135 SqrtBnd<View>::spec(const Space* home, Reflection::VarMap& m) const {
00136 return BinaryPropagator<View,PC_INT_BND>::spec(home, m, ati());
00137 }
00138
00139
00140
00141
00142
00143
00145 class RangesMapSqr {
00146 public:
00148 forceinline int min(int n) const {
00149 return n*n;
00150 }
00152 forceinline int max(int n) const {
00153 return (n+1)*(n+1)-1;
00154 }
00155 };
00156
00158 class RangesMapSqrt {
00159 public:
00161 forceinline int min(int n) const {
00162 return static_cast<int>(floor(::sqrt(static_cast<double>(n))));
00163 }
00165 forceinline int max(int n) const {
00166 return static_cast<int>(floor(::sqrt(static_cast<double>(n))));
00167 }
00168 };
00169
00170 template <class View>
00171 forceinline
00172 SqrtDom<View>::SqrtDom(Space* home, View x0, View x1)
00173 : BinaryPropagator<View,PC_INT_DOM>(home,x0,x1) {}
00174
00175 template <class View>
00176 forceinline ExecStatus
00177 SqrtDom<View>::post(Space* home, View x0, View x1) {
00178 GECODE_ME_CHECK(x0.gq(home,0));
00179 if (same(x0,x1)) {
00180 GECODE_ME_CHECK(x1.lq(home,1));
00181 } else {
00182 GECODE_ME_CHECK(x1.gq(home,0));
00183 GECODE_ES_CHECK(prop_sqrt_bnd(home,x0,x1));
00184 (void) new (home) SqrtDom<View>(home,x0,x1);
00185 }
00186 return ES_OK;
00187 }
00188
00189 template <class View>
00190 forceinline void
00191 SqrtDom<View>::post(Space* home, Reflection::VarMap& vars,
00192 const Reflection::ActorSpec& spec) {
00193 spec.checkArity(2);
00194 View x0(home, vars, spec[0]);
00195 View x1(home, vars, spec[1]);
00196 (void) new (home) SqrtDom<View>(home,x0,x1);
00197 }
00198
00199 template <class View>
00200 forceinline
00201 SqrtDom<View>::SqrtDom(Space* home, bool share, SqrtDom<View>& p)
00202 : BinaryPropagator<View,PC_INT_DOM>(home,share,p) {}
00203
00204 template <class View>
00205 Actor*
00206 SqrtDom<View>::copy(Space* home, bool share) {
00207 return new (home) SqrtDom<View>(home,share,*this);
00208 }
00209
00210 template <class View>
00211 PropCost
00212 SqrtDom<View>::cost(ModEventDelta med) const {
00213 if (View::me(med) == ME_INT_VAL)
00214 return PC_UNARY_LO;
00215 if (View::me(med) == ME_INT_DOM)
00216 return PC_BINARY_HI;
00217 return PC_BINARY_LO;
00218 }
00219
00220 template <class View>
00221 ExecStatus
00222 SqrtDom<View>::propagate(Space* home, ModEventDelta med) {
00223 if (View::me(med) != ME_INT_DOM) {
00224 GECODE_ES_CHECK(prop_sqrt_bnd(home,x0,x1));
00225 return x1.assigned() ? ES_SUBSUMED(this,home)
00226 : ES_NOFIX_PARTIAL(this,View::med(ME_INT_DOM));
00227 }
00228
00229 {
00230 ViewRanges<View> r(x0);
00231 Iter::Ranges::Map<ViewRanges<View>,RangesMapSqrt,false> m(r);
00232 GECODE_ME_CHECK(x1.inter_r(home,m,false));
00233 }
00234
00235 {
00236 ViewRanges<View> r(x1);
00237 Iter::Ranges::Map<ViewRanges<View>,RangesMapSqr,true> m(r);
00238 GECODE_ME_CHECK(x0.inter_r(home,m,false));
00239 }
00240
00241 return x1.assigned() ? ES_SUBSUMED(this,home) : ES_FIX;
00242 }
00243
00244 template <class View>
00245 Support::Symbol
00246 SqrtDom<View>::ati(void) {
00247 return Reflection::mangle<View>("Gecode::Int::Arithmetic::SqrtDom");
00248 }
00249
00250 template <class View>
00251 Reflection::ActorSpec
00252 SqrtDom<View>::spec(const Space* home, Reflection::VarMap& m) const {
00253 return BinaryPropagator<View,PC_INT_DOM>::spec(home, m, ati());
00254 }
00255
00256
00257 }}}
00258
00259
00260