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 template<class VA, class VB>
00047 forceinline ExecStatus
00048 prop_sqr_plus_bnd(Space& home, VA x0, VB x1) {
00049 bool mod;
00050 do {
00051 mod = false;
00052 {
00053 ModEvent me = x0.lq(home,floor(::sqrt(static_cast<double>(x1.max()))));
00054 if (me_failed(me)) return ES_FAILED;
00055 mod |= me_modified(me);
00056 }
00057 {
00058 ModEvent me = x0.gq(home,ceil(::sqrt(static_cast<double>(x1.min()))));
00059 if (me_failed(me)) return ES_FAILED;
00060 mod |= me_modified(me);
00061 }
00062 {
00063 ModEvent me = x1.lq(home,x0.max()*x0.max());
00064 if (me_failed(me)) return ES_FAILED;
00065 mod |= me_modified(me);
00066 }
00067 {
00068 ModEvent me = x1.gq(home,x0.min()*x0.min());
00069 if (me_failed(me)) return ES_FAILED;
00070 mod |= me_modified(me);
00071 }
00072 } while (mod);
00073 return ES_OK;
00074 }
00075
00076 template<class VA, class VB>
00077 forceinline
00078 SqrPlusBnd<VA,VB>::SqrPlusBnd(Home home, VA x0, VB x1)
00079 : MixBinaryPropagator<VA,PC_INT_BND,VB,PC_INT_BND>(home,x0,x1) {}
00080
00081 template<class VA, class VB>
00082 forceinline ExecStatus
00083 SqrPlusBnd<VA,VB>::post(Home home, VA x0, VB x1) {
00084 GECODE_ES_CHECK(prop_sqr_plus_bnd(home,x0,x1));
00085 (void) new (home) SqrPlusBnd<VA,VB>(home,x0,x1);
00086 return ES_OK;
00087 }
00088
00089 template<class VA, class VB>
00090 forceinline
00091 SqrPlusBnd<VA,VB>::SqrPlusBnd(Space& home, bool share, SqrPlusBnd<VA,VB>& p)
00092 : MixBinaryPropagator<VA,PC_INT_BND,VB,PC_INT_BND>(home,share,p) {}
00093
00094 template<class VA, class VB>
00095 Actor*
00096 SqrPlusBnd<VA,VB>::copy(Space& home, bool share) {
00097 return new (home) SqrPlusBnd<VA,VB>(home,share,*this);
00098 }
00099
00100 template<class VA, class VB>
00101 ExecStatus
00102 SqrPlusBnd<VA,VB>::propagate(Space& home, const ModEventDelta&) {
00103 GECODE_ES_CHECK(prop_sqr_plus_bnd(home,x0,x1));
00104 return x0.assigned() ? home.ES_SUBSUMED(*this) : ES_FIX;
00105 }
00106
00107
00108
00109
00110
00111
00112
00113
00114 template<class View>
00115 forceinline
00116 SqrBnd<View>::SqrBnd(Home home, View x0, View x1)
00117 : BinaryPropagator<View,PC_INT_BND>(home,x0,x1) {}
00118
00119 template<class View>
00120 forceinline ExecStatus
00121 SqrBnd<View>::post(Home home, View x0, View x1) {
00122 GECODE_ME_CHECK(x1.gq(home,0));
00123 if (same(x0,x1)) {
00124 GECODE_ME_CHECK(x1.lq(home,1));
00125 } else {
00126 GECODE_ME_CHECK(x0.lq(home,floor(::sqrt(static_cast<double>
00127 (Limits::max)))));
00128 GECODE_ME_CHECK(x0.gq(home,-floor(::sqrt(static_cast<double>
00129 (-Limits::min)))));
00130 if (x0.min() >= 0)
00131 return SqrPlusBnd<IntView,IntView>::post(home,x0,x1);
00132 if (x0.max() <= 0)
00133 return SqrPlusBnd<MinusView,IntView>::post(home,MinusView(x0),x1);
00134 GECODE_ME_CHECK(x1.lq(home,
00135 std::max(x0.min()*x0.min(),x0.max()*x0.max())));
00136 (void) new (home) SqrBnd<View>(home,x0,x1);
00137 }
00138 return ES_OK;
00139 }
00140
00141 template<class View>
00142 forceinline
00143 SqrBnd<View>::SqrBnd(Space& home, bool share, SqrBnd<View>& p)
00144 : BinaryPropagator<View,PC_INT_BND>(home,share,p) {}
00145
00146 template<class View>
00147 Actor*
00148 SqrBnd<View>::copy(Space& home, bool share) {
00149 return new (home) SqrBnd<View>(home,share,*this);
00150 }
00151
00152 template<class View>
00153 ExecStatus
00154 SqrBnd<View>::propagate(Space& home, const ModEventDelta&) {
00155 assert(x1.min() >= 0);
00156 if (x0.min() >= 0)
00157 GECODE_REWRITE(*this,(SqrPlusBnd<IntView,IntView>::post(home(*this),x0,x1)));
00158 if (x0.max() <= 0)
00159 GECODE_REWRITE(*this,(SqrPlusBnd<MinusView,IntView>::post(home(*this),
00160 MinusView(x0),x1)));
00161
00162 GECODE_ME_CHECK(x1.lq(home,std::max(x0.min()*x0.min(),
00163 x0.max()*x0.max())));
00164
00165 int s = static_cast<int>(floor(::sqrt(static_cast<double>(x1.max()))));
00166
00167 GECODE_ME_CHECK(x0.gq(home,-s));
00168 GECODE_ME_CHECK(x0.lq(home,s));
00169
00170 if (x0.assigned() && x1.assigned())
00171 return (x0.val()*x0.val() == x1.val()) ?
00172 home.ES_SUBSUMED(*this) : ES_FAILED;
00173
00174 return ES_NOFIX;
00175 }
00176
00177
00178
00179
00180
00181
00183 class ValuesMapSqr {
00184 public:
00186 forceinline int val(int n) const {
00187 return n*n;
00188 }
00189 };
00190
00192 class ValuesMapSqrt {
00193 public:
00195 forceinline int val(int n) const {
00196 return static_cast<int>(floor(::sqrt(static_cast<double>(n))));
00197 }
00198 };
00199
00200
00201
00202
00203
00204
00205 template<class VA, class VB>
00206 forceinline
00207 SqrPlusDom<VA,VB>::SqrPlusDom(Home home, VA x0, VB x1)
00208 : MixBinaryPropagator<VA,PC_INT_DOM,VB,PC_INT_DOM>(home,x0,x1) {}
00209
00210 template<class VA, class VB>
00211 forceinline ExecStatus
00212 SqrPlusDom<VA,VB>::post(Home home, VA x0, VB x1) {
00213 GECODE_ES_CHECK(prop_sqr_plus_bnd(home,x0,x1));
00214 (void) new (home) SqrPlusDom<VA,VB>(home,x0,x1);
00215 return ES_OK;
00216 }
00217
00218 template<class VA, class VB>
00219 forceinline
00220 SqrPlusDom<VA,VB>::SqrPlusDom(Space& home, bool share, SqrPlusDom<VA,VB>& p)
00221 : MixBinaryPropagator<VA,PC_INT_DOM,VB,PC_INT_DOM>(home,share,p) {}
00222
00223 template<class VA, class VB>
00224 Actor*
00225 SqrPlusDom<VA,VB>::copy(Space& home, bool share) {
00226 return new (home) SqrPlusDom<VA,VB>(home,share,*this);
00227 }
00228
00229 template<class VA, class VB>
00230 PropCost
00231 SqrPlusDom<VA,VB>::cost(const Space&, const ModEventDelta& med) const {
00232 if (VA::me(med) == ME_INT_VAL)
00233 return PropCost::unary(PropCost::LO);
00234 else if (VA::me(med) == ME_INT_DOM)
00235 return PropCost::binary(PropCost::HI);
00236 else
00237 return PropCost::binary(PropCost::LO);
00238 }
00239
00240 template<class VA, class VB>
00241 ExecStatus
00242 SqrPlusDom<VA,VB>::propagate(Space& home, const ModEventDelta& med) {
00243 if (VA::me(med) != ME_INT_DOM) {
00244 GECODE_ES_CHECK(prop_sqr_plus_bnd(home,x0,x1));
00245 return x0.assigned() ?
00246 home.ES_SUBSUMED(*this)
00247 : home.ES_NOFIX_PARTIAL(*this,VA::med(ME_INT_DOM));
00248 }
00249
00250 {
00251 ViewValues<VA> v0(x0);
00252 Iter::Values::Map<ViewValues<VA>,ValuesMapSqr> s0(v0);
00253 GECODE_ME_CHECK(x1.inter_v(home,s0,false));
00254 }
00255
00256 {
00257 ViewValues<VB> v1(x1);
00258 Iter::Values::Map<ViewValues<VB>,ValuesMapSqrt> s1(v1);
00259 GECODE_ME_CHECK(x0.inter_v(home,s1,false));
00260 }
00261
00262 return x0.assigned() ? home.ES_SUBSUMED(*this) : ES_FIX;
00263 }
00264
00265
00266
00267
00268
00269
00270
00271 template<class View>
00272 forceinline
00273 SqrDom<View>::SqrDom(Home home, View x0, View x1)
00274 : BinaryPropagator<View,PC_INT_DOM>(home,x0,x1) {}
00275
00276 template<class View>
00277 forceinline ExecStatus
00278 SqrDom<View>::post(Home home, View x0, View x1) {
00279 GECODE_ME_CHECK(x1.gq(home,0));
00280 if (same(x0,x1)) {
00281 GECODE_ME_CHECK(x1.lq(home,1));
00282 } else {
00283 GECODE_ME_CHECK(x0.lq(home,floor(::sqrt(static_cast<double>
00284 (Limits::max)))));
00285 GECODE_ME_CHECK(x0.gq(home,-floor(::sqrt(static_cast<double>
00286 (-Limits::min)))));
00287 if (x0.min() >= 0)
00288 return SqrPlusDom<IntView,IntView>::post(home,x0,x1);
00289 if (x0.max() <= 0)
00290 return SqrPlusDom<MinusView,IntView>::post(home,MinusView(x0),x1);
00291 GECODE_ME_CHECK(x1.lq(home,
00292 std::max(x0.min()*x0.min(),x0.max()*x0.max())));
00293 (void) new (home) SqrDom<View>(home,x0,x1);
00294 }
00295 return ES_OK;
00296 }
00297
00298 template<class View>
00299 forceinline
00300 SqrDom<View>::SqrDom(Space& home, bool share, SqrDom<View>& p)
00301 : BinaryPropagator<View,PC_INT_DOM>(home,share,p) {}
00302
00303 template<class View>
00304 Actor*
00305 SqrDom<View>::copy(Space& home, bool share) {
00306 return new (home) SqrDom<View>(home,share,*this);
00307 }
00308
00309 template<class View>
00310 PropCost
00311 SqrDom<View>::cost(const Space&, const ModEventDelta& med) const {
00312 if (View::me(med) == ME_INT_VAL)
00313 return PropCost::unary(PropCost::LO);
00314 else if (View::me(med) == ME_INT_DOM)
00315 return PropCost::binary(PropCost::HI);
00316 else
00317 return PropCost::binary(PropCost::LO);
00318 }
00319
00320 template<class View>
00321 ExecStatus
00322 SqrDom<View>::propagate(Space& home, const ModEventDelta& med) {
00323 assert(x1.min() >= 0);
00324 if (View::me(med) != ME_INT_DOM) {
00325 if (x0.min() >= 0)
00326 GECODE_REWRITE(*this,(SqrPlusDom<IntView,IntView>::post(home(*this),x0,x1)));
00327 if (x0.max() <= 0)
00328 GECODE_REWRITE(*this,(SqrPlusDom<MinusView,IntView>::post(home(*this),
00329 MinusView(x0),x1)));
00330
00331 GECODE_ME_CHECK(x1.lq(home,std::max(x0.min()*x0.min(),
00332 x0.max()*x0.max())));
00333
00334 int s = static_cast<int>(floor(::sqrt(static_cast<double>(x1.max()))));
00335
00336 GECODE_ME_CHECK(x0.gq(home,-s));
00337 GECODE_ME_CHECK(x0.lq(home,s));
00338
00339 if (x0.assigned() && x1.assigned())
00340 return (x0.val()*x0.val() == x1.val()) ?
00341 home.ES_SUBSUMED(*this) : ES_FAILED;
00342 return home.ES_NOFIX_PARTIAL(*this,View::med(ME_INT_DOM));
00343
00344 }
00345
00346 Region r(home);
00347 {
00348 ViewValues<View> i(x0), j(x0);
00349 using namespace Iter::Values;
00350 Positive<ViewValues<View> > p(i);
00351 Negative<ViewValues<View> > n(j);
00352 Minus m(r,n);
00353
00354 Map<Positive<ViewValues<View> >,ValuesMapSqr,true> sp(p);
00355 Map<Minus,ValuesMapSqr,true> sm(m);
00356 Union<Map<Positive<ViewValues<View> >,ValuesMapSqr,true>,
00357 Map<Minus,ValuesMapSqr,true> > u(sp,sm);
00358 GECODE_ME_CHECK(x1.inter_v(home,u,false));
00359 }
00360
00361 {
00362 ViewValues<View> i(x1), j(x1);
00363 using namespace Iter::Values;
00364 Map<ViewValues<View>,ValuesMapSqrt,true> si(i), sj(j);
00365 Minus mi(r,si);
00366 Union<Minus,
00367 Map<ViewValues<View>,ValuesMapSqrt,true> > u(mi,sj);
00368 GECODE_ME_CHECK(x0.inter_v(home,u,false));
00369 }
00370
00371 return x0.assigned() ? home.ES_SUBSUMED(*this) : ES_FIX;
00372 }
00373
00374 }}}
00375
00376
00377