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(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
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
00217