sqr.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-07-28 16:13:53 +0200 (Wed, 28 Jul 2010) $ by $Author: schulte $ 00011 * $Revision: 11292 $ 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 * Positive bounds consistent squaring 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 * Bounds consistent squaring 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 * Value mappings for squaring and square root 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 * Positive domain consistent squaring 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 * Domain consistent squaring 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<Negative<ViewValues<View> > > m(r,n); 00353 00354 Map<Positive<ViewValues<View> >,ValuesMapSqr,true> sp(p); 00355 Map<Minus<Negative<ViewValues<View> > >,ValuesMapSqr,true> sm(m); 00356 Union<Map<Positive<ViewValues<View> >,ValuesMapSqr,true>, 00357 Map<Minus<Negative<ViewValues<View> > >,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<Map<ViewValues<View>,ValuesMapSqrt,true> > mi(r,si); 00366 Union<Minus<Map<ViewValues<View>,ValuesMapSqrt,true> >, 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 // STATISTICS: int-prop 00377