Generated on Thu Mar 7 2013 10:21:19 for Gecode by doxygen 1.8.3.1
sqr.hpp
Go to the documentation of this file.
1 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2 /*
3  * Main authors:
4  * Christian Schulte <schulte@gecode.org>
5  *
6  * Copyright:
7  * Christian Schulte, 2008
8  *
9  * Last modified:
10  * $Date: 2011-08-09 02:04:53 +1000 (Tue, 09 Aug 2011) $ by $Author: schulte $
11  * $Revision: 12253 $
12  *
13  * This file is part of Gecode, the generic constraint
14  * development environment:
15  * http://www.gecode.org
16  *
17  * Permission is hereby granted, free of charge, to any person obtaining
18  * a copy of this software and associated documentation files (the
19  * "Software"), to deal in the Software without restriction, including
20  * without limitation the rights to use, copy, modify, merge, publish,
21  * distribute, sublicense, and/or sell copies of the Software, and to
22  * permit persons to whom the Software is furnished to do so, subject to
23  * the following conditions:
24  *
25  * The above copyright notice and this permission notice shall be
26  * included in all copies or substantial portions of the Software.
27  *
28  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
29  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
30  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
31  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
32  * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
33  * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
34  * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
35  *
36  */
37 
38 #include <cmath>
39 
40 namespace Gecode { namespace Int { namespace Arithmetic {
41 
42  /*
43  * Positive bounds consistent squaring
44  *
45  */
46  template<class VA, class VB>
48  prop_sqr_plus_bnd(Space& home, VA x0, VB x1) {
49  bool mod;
50  do {
51  mod = false;
52  {
53  ModEvent me = x0.lq(home,floor(::sqrt(static_cast<double>(x1.max()))));
54  if (me_failed(me)) return ES_FAILED;
55  mod |= me_modified(me);
56  }
57  {
58  ModEvent me = x0.gq(home,ceil(::sqrt(static_cast<double>(x1.min()))));
59  if (me_failed(me)) return ES_FAILED;
60  mod |= me_modified(me);
61  }
62  {
63  ModEvent me = x1.lq(home,x0.max()*x0.max());
64  if (me_failed(me)) return ES_FAILED;
65  mod |= me_modified(me);
66  }
67  {
68  ModEvent me = x1.gq(home,x0.min()*x0.min());
69  if (me_failed(me)) return ES_FAILED;
70  mod |= me_modified(me);
71  }
72  } while (mod);
73  return ES_OK;
74  }
75 
76  template<class VA, class VB>
78  SqrPlusBnd<VA,VB>::SqrPlusBnd(Home home, VA x0, VB x1)
79  : MixBinaryPropagator<VA,PC_INT_BND,VB,PC_INT_BND>(home,x0,x1) {}
80 
81  template<class VA, class VB>
83  SqrPlusBnd<VA,VB>::post(Home home, VA x0, VB x1) {
85  (void) new (home) SqrPlusBnd<VA,VB>(home,x0,x1);
86  return ES_OK;
87  }
88 
89  template<class VA, class VB>
92  : MixBinaryPropagator<VA,PC_INT_BND,VB,PC_INT_BND>(home,share,p) {}
93 
94  template<class VA, class VB>
95  Actor*
96  SqrPlusBnd<VA,VB>::copy(Space& home, bool share) {
97  return new (home) SqrPlusBnd<VA,VB>(home,share,*this);
98  }
99 
100  template<class VA, class VB>
101  ExecStatus
103  GECODE_ES_CHECK(prop_sqr_plus_bnd(home,x0,x1));
104  return x0.assigned() ? home.ES_SUBSUMED(*this) : ES_FIX;
105  }
106 
107 
108 
109  /*
110  * Bounds consistent squaring
111  *
112  */
113 
114  template<class View>
116  SqrBnd<View>::SqrBnd(Home home, View x0, View x1)
117  : BinaryPropagator<View,PC_INT_BND>(home,x0,x1) {}
118 
119  template<class View>
121  SqrBnd<View>::post(Home home, View x0, View x1) {
122  GECODE_ME_CHECK(x1.gq(home,0));
123  if (same(x0,x1)) {
124  GECODE_ME_CHECK(x1.lq(home,1));
125  } else {
126  GECODE_ME_CHECK(x0.lq(home,floor(::sqrt(static_cast<double>
127  (Limits::max)))));
128  GECODE_ME_CHECK(x0.gq(home,-floor(::sqrt(static_cast<double>
129  (-Limits::min)))));
130  if (x0.min() >= 0)
131  return SqrPlusBnd<IntView,IntView>::post(home,x0,x1);
132  if (x0.max() <= 0)
134  GECODE_ME_CHECK(x1.lq(home,
135  std::max(x0.min()*x0.min(),x0.max()*x0.max())));
136  (void) new (home) SqrBnd<View>(home,x0,x1);
137  }
138  return ES_OK;
139  }
140 
141  template<class View>
143  SqrBnd<View>::SqrBnd(Space& home, bool share, SqrBnd<View>& p)
144  : BinaryPropagator<View,PC_INT_BND>(home,share,p) {}
145 
146  template<class View>
147  Actor*
148  SqrBnd<View>::copy(Space& home, bool share) {
149  return new (home) SqrBnd<View>(home,share,*this);
150  }
151 
152  template<class View>
153  ExecStatus
155  assert(x1.min() >= 0);
156  if (x0.min() >= 0)
157  GECODE_REWRITE(*this,(SqrPlusBnd<IntView,IntView>::post(home(*this),x0,x1)));
158  if (x0.max() <= 0)
160  MinusView(x0),x1)));
161 
162  GECODE_ME_CHECK(x1.lq(home,std::max(x0.min()*x0.min(),
163  x0.max()*x0.max())));
164 
165  int s = static_cast<int>(floor(::sqrt(static_cast<double>(x1.max()))));
166 
167  GECODE_ME_CHECK(x0.gq(home,-s));
168  GECODE_ME_CHECK(x0.lq(home,s));
169 
170  if (x0.assigned() && x1.assigned())
171  return (x0.val()*x0.val() == x1.val()) ?
172  home.ES_SUBSUMED(*this) : ES_FAILED;
173 
174  return ES_NOFIX;
175  }
176 
177  /*
178  * Value mappings for squaring and square root
179  *
180  */
181 
183  class ValuesMapSqr {
184  public:
186  forceinline int val(int n) const {
187  return n*n;
188  }
189  };
190 
193  public:
195  forceinline int val(int n) const {
196  return static_cast<int>(floor(::sqrt(static_cast<double>(n))));
197  }
198  };
199 
200 
201  /*
202  * Positive domain consistent squaring
203  *
204  */
205  template<class VA, class VB>
208  : MixBinaryPropagator<VA,PC_INT_DOM,VB,PC_INT_DOM>(home,x0,x1) {}
209 
210  template<class VA, class VB>
212  SqrPlusDom<VA,VB>::post(Home home, VA x0, VB x1) {
213  GECODE_ES_CHECK(prop_sqr_plus_bnd(home,x0,x1));
214  (void) new (home) SqrPlusDom<VA,VB>(home,x0,x1);
215  return ES_OK;
216  }
217 
218  template<class VA, class VB>
221  : MixBinaryPropagator<VA,PC_INT_DOM,VB,PC_INT_DOM>(home,share,p) {}
222 
223  template<class VA, class VB>
224  Actor*
225  SqrPlusDom<VA,VB>::copy(Space& home, bool share) {
226  return new (home) SqrPlusDom<VA,VB>(home,share,*this);
227  }
228 
229  template<class VA, class VB>
230  PropCost
231  SqrPlusDom<VA,VB>::cost(const Space&, const ModEventDelta& med) const {
232  if (VA::me(med) == ME_INT_VAL)
234  else if (VA::me(med) == ME_INT_DOM)
236  else
238  }
239 
240  template<class VA, class VB>
241  ExecStatus
243  if (VA::me(med) != ME_INT_DOM) {
244  GECODE_ES_CHECK(prop_sqr_plus_bnd(home,x0,x1));
245  return x0.assigned() ?
246  home.ES_SUBSUMED(*this)
247  : home.ES_NOFIX_PARTIAL(*this,VA::med(ME_INT_DOM));
248  }
249 
250  {
251  ViewValues<VA> v0(x0);
253  GECODE_ME_CHECK(x1.inter_v(home,s0,false));
254  }
255 
256  {
257  ViewValues<VB> v1(x1);
259  GECODE_ME_CHECK(x0.inter_v(home,s1,false));
260  }
261 
262  return x0.assigned() ? home.ES_SUBSUMED(*this) : ES_FIX;
263  }
264 
265 
266  /*
267  * Domain consistent squaring
268  *
269  */
270 
271  template<class View>
273  SqrDom<View>::SqrDom(Home home, View x0, View x1)
274  : BinaryPropagator<View,PC_INT_DOM>(home,x0,x1) {}
275 
276  template<class View>
278  SqrDom<View>::post(Home home, View x0, View x1) {
279  GECODE_ME_CHECK(x1.gq(home,0));
280  if (same(x0,x1)) {
281  GECODE_ME_CHECK(x1.lq(home,1));
282  } else {
283  GECODE_ME_CHECK(x0.lq(home,floor(::sqrt(static_cast<double>
284  (Limits::max)))));
285  GECODE_ME_CHECK(x0.gq(home,-floor(::sqrt(static_cast<double>
286  (-Limits::min)))));
287  if (x0.min() >= 0)
288  return SqrPlusDom<IntView,IntView>::post(home,x0,x1);
289  if (x0.max() <= 0)
291  GECODE_ME_CHECK(x1.lq(home,
292  std::max(x0.min()*x0.min(),x0.max()*x0.max())));
293  (void) new (home) SqrDom<View>(home,x0,x1);
294  }
295  return ES_OK;
296  }
297 
298  template<class View>
300  SqrDom<View>::SqrDom(Space& home, bool share, SqrDom<View>& p)
301  : BinaryPropagator<View,PC_INT_DOM>(home,share,p) {}
302 
303  template<class View>
304  Actor*
305  SqrDom<View>::copy(Space& home, bool share) {
306  return new (home) SqrDom<View>(home,share,*this);
307  }
308 
309  template<class View>
310  PropCost
311  SqrDom<View>::cost(const Space&, const ModEventDelta& med) const {
312  if (View::me(med) == ME_INT_VAL)
314  else if (View::me(med) == ME_INT_DOM)
316  else
318  }
319 
320  template<class View>
321  ExecStatus
323  assert(x1.min() >= 0);
324  if (View::me(med) != ME_INT_DOM) {
325  if (x0.min() >= 0)
326  GECODE_REWRITE(*this,(SqrPlusDom<IntView,IntView>::post(home(*this),x0,x1)));
327  if (x0.max() <= 0)
329  MinusView(x0),x1)));
330 
331  GECODE_ME_CHECK(x1.lq(home,std::max(x0.min()*x0.min(),
332  x0.max()*x0.max())));
333 
334  int s = static_cast<int>(floor(::sqrt(static_cast<double>(x1.max()))));
335 
336  GECODE_ME_CHECK(x0.gq(home,-s));
337  GECODE_ME_CHECK(x0.lq(home,s));
338 
339  if (x0.assigned() && x1.assigned())
340  return (x0.val()*x0.val() == x1.val()) ?
341  home.ES_SUBSUMED(*this) : ES_FAILED;
342  return home.ES_NOFIX_PARTIAL(*this,View::med(ME_INT_DOM));
343 
344  }
345 
346  Region r(home);
347  {
348  ViewValues<View> i(x0), j(x0);
349  using namespace Iter::Values;
350  Positive<ViewValues<View> > p(i);
351  Negative<ViewValues<View> > n(j);
352  Minus m(r,n);
353 
354  Map<Positive<ViewValues<View> >,ValuesMapSqr,true> sp(p);
355  Map<Minus,ValuesMapSqr,true> sm(m);
357  Map<Minus,ValuesMapSqr,true> > u(sp,sm);
358  GECODE_ME_CHECK(x1.inter_v(home,u,false));
359  }
360 
361  {
362  ViewValues<View> i(x1), j(x1);
363  using namespace Iter::Values;
364  Map<ViewValues<View>,ValuesMapSqrt,true> si(i), sj(j);
365  Minus mi(r,si);
366  Union<Minus,
367  Map<ViewValues<View>,ValuesMapSqrt,true> > u(mi,sj);
368  GECODE_ME_CHECK(x0.inter_v(home,u,false));
369  }
370 
371  return x0.assigned() ? home.ES_SUBSUMED(*this) : ES_FIX;
372  }
373 
374 }}}
375 
376 // STATISTICS: int-prop
377