Generated on Sat May 25 2013 18:00:35 for Gecode by doxygen 1.8.3.1
pow.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, 2012
8  *
9  * Last modified:
10  * $Date: 2013-03-12 20:08:33 +0100 (Tue, 12 Mar 2013) $ by $Author: schulte $
11  * $Revision: 13510 $
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 <gecode/int/rel.hh>
39 
40 #include <climits>
41 #include <algorithm>
42 
43 namespace Gecode { namespace Int { namespace Arithmetic {
44 
45  /*
46  * Positive bounds consistent power
47  *
48  */
49  template<class VA, class VB, class Ops>
50  inline ExecStatus
51  prop_pow_plus_bnd(Space& home, VA x0, VB x1, const Ops& ops) {
52  bool mod;
53  do {
54  mod = false;
55  {
56  ModEvent me = x0.lq(home,ops.fnroot(x1.max()));
57  if (me_failed(me)) return ES_FAILED;
58  mod |= me_modified(me);
59  }
60  {
61  ModEvent me = x0.gq(home,ops.cnroot(x1.min()));
62  if (me_failed(me)) return ES_FAILED;
63  mod |= me_modified(me);
64  }
65  {
66  ModEvent me = x1.lq(home,ops.pow(x0.max()));
67  if (me_failed(me)) return ES_FAILED;
68  mod |= me_modified(me);
69  }
70  {
71  ModEvent me = x1.gq(home,ops.pow(x0.min()));
72  if (me_failed(me)) return ES_FAILED;
73  mod |= me_modified(me);
74  }
75  } while (mod);
76  return ES_OK;
77  }
78 
79  template<class VA, class VB, class Ops>
81  PowPlusBnd<VA,VB,Ops>::PowPlusBnd(Home home, VA x0, VB x1, const Ops& o)
82  : MixBinaryPropagator<VA,PC_INT_BND,VB,PC_INT_BND>(home,x0,x1),
83  ops(o) {}
84 
85  template<class VA, class VB, class Ops>
87  PowPlusBnd<VA,VB,Ops>::post(Home home, VA x0, VB x1, Ops ops) {
88  GECODE_ME_CHECK(x0.gq(home,0));
89  GECODE_ME_CHECK(x1.gq(home,0));
90  GECODE_ES_CHECK(prop_pow_plus_bnd(home,x0,x1,ops));
91  if (!x0.assigned()) {
92  assert(!x1.assigned());
93  (void) new (home) PowPlusBnd<VA,VB,Ops>(home,x0,x1,ops);
94  }
95  return ES_OK;
96  }
97 
98  template<class VA, class VB, class Ops>
102  : MixBinaryPropagator<VA,PC_INT_BND,VB,PC_INT_BND>(home,share,p),
103  ops(p.ops) {}
104 
105  template<class VA, class VB, class Ops>
106  Actor*
107  PowPlusBnd<VA,VB,Ops>::copy(Space& home, bool share) {
108  return new (home) PowPlusBnd<VA,VB,Ops>(home,share,*this);
109  }
110 
111  template<class VA, class VB, class Ops>
112  ExecStatus
114  GECODE_ES_CHECK(prop_pow_plus_bnd(home,x0,x1,ops));
115  return x0.assigned() ? home.ES_SUBSUMED(*this) : ES_FIX;
116  }
117 
118 
119 
120  /*
121  * Bounds consistent power
122  *
123  */
124 
125  template<class Ops>
126  inline ExecStatus
127  prop_pow_bnd(Space& home, IntView x0, IntView x1, const Ops& ops) {
128  assert((x0.min() < 0) && (0 < x0.max()));
129  if (ops.even()) {
130  assert(x1.min() >= 0);
131  int u = ops.fnroot(x1.max());
132  GECODE_ME_CHECK(x0.lq(home,u));
133  GECODE_ME_CHECK(x0.gq(home,-u));
134  GECODE_ME_CHECK(x1.lq(home,std::max(ops.pow(x0.max()),
135  ops.pow(-x0.min()))));
136  } else {
137  assert((x1.min() < 0) && (0 < x1.max()));
138  GECODE_ME_CHECK(x0.lq(home,ops.fnroot(x1.max())));
139  GECODE_ME_CHECK(x0.gq(home,-ops.fnroot(-x1.min())));
140  GECODE_ME_CHECK(x1.lq(home,ops.pow(x0.max())));
141  GECODE_ME_CHECK(x1.gq(home,ops.pow(x0.min())));
142  }
143  return ES_OK;
144  }
145 
146  template<class Ops>
148  PowBnd<Ops>::PowBnd(Home home, IntView x0, IntView x1, const Ops& o)
149  : BinaryPropagator<IntView,PC_INT_BND>(home,x0,x1),
150  ops(o) {}
151 
152  template<class Ops>
153  inline ExecStatus
154  PowBnd<Ops>::post(Home home, IntView x0, IntView x1, Ops ops) {
155  if (static_cast<unsigned int>(ops.exp()) >= sizeof(int) * CHAR_BIT) {
156  // The integer limits allow only -1, 0, 1 for x0
157  GECODE_ME_CHECK(x0.lq(home,1));
158  GECODE_ME_CHECK(x0.gq(home,-1));
159  // Just rewrite to values that can be handeled without overflow
160  ops.exp(ops.even() ? 2 : 1);
161  }
162 
163  if (ops.exp() == 0) {
164  GECODE_ME_CHECK(x1.eq(home,1));
165  return ES_OK;
166  } else if (ops.exp() == 1) {
167  return Rel::EqBnd<IntView,IntView>::post(home,x0,x1);
168  }
169 
170  if (same(x0,x1)) {
171  assert(ops.exp() != 0);
172  GECODE_ME_CHECK(x0.lq(home,1));
173  GECODE_ME_CHECK(x0.gq(home,ops.even() ? 0 : -1));
174  return ES_OK;
175  }
176 
177  // Limits values such that no overflow can occur
178  assert(Limits::max == -Limits::min);
179  {
180  int l = ops.fnroot(Limits::max);
181  GECODE_ME_CHECK(x0.lq(home,l));
182  GECODE_ME_CHECK(x0.gq(home,-l));
183  }
184 
185  if ((x0.min() >= 0) || ((x1.min() >= 0) && !ops.even()))
186  return PowPlusBnd<IntView,IntView,Ops>::post(home,x0,x1,ops);
187 
188  if (ops.even() && (x0.max() <= 0))
190  ::post(home,MinusView(x0),x1,ops);
191 
192  if (!ops.even() && ((x0.max() <= 0) || (x1.max() <= 0)))
194  ::post(home,MinusView(x0),MinusView(x1),ops);
195 
196  if (ops.even())
197  GECODE_ME_CHECK(x1.gq(home,0));
198 
199  assert((x0.min() < 0) && (x0.max() > 0));
200 
201  if (ops.even()) {
202  GECODE_ME_CHECK(x1.lq(home,std::max(ops.pow(x0.min()),
203  ops.pow(x0.max()))));
204  } else {
205  GECODE_ME_CHECK(x1.lq(home,ops.pow(x0.max())));
206  GECODE_ME_CHECK(x1.gq(home,ops.pow(x0.min())));
207  }
208 
209  (void) new (home) PowBnd<Ops>(home,x0,x1,ops);
210  return ES_OK;
211  }
212 
213  template<class Ops>
215  PowBnd<Ops>::PowBnd(Space& home, bool share, PowBnd<Ops>& p)
216  : BinaryPropagator<IntView,PC_INT_BND>(home,share,p),
217  ops(p.ops) {}
218 
219  template<class Ops>
220  Actor*
221  PowBnd<Ops>::copy(Space& home, bool share) {
222  return new (home) PowBnd<Ops>(home,share,*this);
223  }
224 
225  template<class Ops>
226  ExecStatus
228  if ((x0.min() >= 0) || ((x1.min() >= 0) && !ops.even()))
230  ::post(home(*this),x0,x1,ops)));
231 
232  if (ops.even() && (x0.max() <= 0))
234  ::post(home(*this),MinusView(x0),x1,ops)));
235 
236  if (!ops.even() && ((x0.max() <= 0) || (x1.max() <= 0)))
238  ::post(home(*this),MinusView(x0),
239  MinusView(x1),ops)));
240 
241  GECODE_ES_CHECK(prop_pow_bnd<Ops>(home,x0,x1,ops));
242 
243  if (x0.assigned() && x1.assigned())
244  return (ops.pow(x0.val()) == x1.val()) ?
245  home.ES_SUBSUMED(*this) : ES_FAILED;
246 
247  return ES_NOFIX;
248  }
249 
250 
251  /*
252  * Value mappings for power and nroot
253  *
254  */
255 
257  template<class Ops>
258  class ValuesMapPow {
259  protected:
261  Ops ops;
262  public:
264  forceinline ValuesMapPow(const Ops& o) : ops(o) {}
266  forceinline int val(int x) const {
267  return ops.pow(x);
268  }
269  };
270 
272  template<class Ops>
274  protected:
276  Ops ops;
277  public:
279  forceinline ValuesMapNroot(const Ops& o) : ops(o) {}
281  forceinline int val(int x) const {
282  return ops.fnroot(x);
283  }
284  };
285 
287  template<class Ops>
289  protected:
291  Ops ops;
292  public:
294  forceinline ValuesMapNrootSigned(const Ops& o) : ops(o) {}
296  forceinline int val(int x) const {
297  if (x < 0)
298  return -ops.fnroot(-x);
299  else
300  return ops.fnroot(x);
301  }
302  };
303 
304 
305  /*
306  * Positive domain consistent power
307  *
308  */
309  template<class VA, class VB, class Ops>
311  PowPlusDom<VA,VB,Ops>::PowPlusDom(Home home, VA x0, VB x1, const Ops& o)
312  : MixBinaryPropagator<VA,PC_INT_DOM,VB,PC_INT_DOM>(home,x0,x1),
313  ops(o) {}
314 
315  template<class VA, class VB, class Ops>
317  PowPlusDom<VA,VB,Ops>::post(Home home, VA x0, VB x1, Ops ops) {
318  GECODE_ME_CHECK(x0.gq(home,0));
319  GECODE_ME_CHECK(x1.gq(home,0));
320  GECODE_ES_CHECK(prop_pow_plus_bnd(home,x0,x1,ops));
321  if (!x0.assigned()) {
322  assert(!x1.assigned());
323  (void) new (home) PowPlusDom<VA,VB,Ops>(home,x0,x1,ops);
324  }
325  return ES_OK;
326  }
327 
328  template<class VA, class VB, class Ops>
332  : MixBinaryPropagator<VA,PC_INT_DOM,VB,PC_INT_DOM>(home,share,p),
333  ops(p.ops) {}
334 
335  template<class VA, class VB, class Ops>
336  Actor*
337  PowPlusDom<VA,VB,Ops>::copy(Space& home, bool share) {
338  return new (home) PowPlusDom<VA,VB,Ops>(home,share,*this);
339  }
340 
341  template<class VA, class VB, class Ops>
342  PropCost
343  PowPlusDom<VA,VB,Ops>::cost(const Space&, const ModEventDelta& med) const {
344  if (VA::me(med) == ME_INT_VAL)
346  else if (VA::me(med) == ME_INT_DOM)
348  else
350  }
351 
352  template<class VA, class VB, class Ops>
353  ExecStatus
355  if (VA::me(med) != ME_INT_DOM) {
356  GECODE_ES_CHECK(prop_pow_plus_bnd(home,x0,x1,ops));
357  return x0.assigned() ?
358  home.ES_SUBSUMED(*this)
359  : home.ES_NOFIX_PARTIAL(*this,VA::med(ME_INT_DOM));
360  }
361 
362  {
363  ViewValues<VA> v0(x0);
364  ValuesMapPow<Ops> vmp(ops);
366  GECODE_ME_CHECK(x1.inter_v(home,s0,false));
367  }
368 
369  {
370  ViewValues<VB> v1(x1);
371  ValuesMapNroot<Ops> vmn(ops);
373  GECODE_ME_CHECK(x0.inter_v(home,s1,false));
374  }
375 
376  return x0.assigned() ? home.ES_SUBSUMED(*this) : ES_FIX;
377  }
378 
379 
380  /*
381  * Domain consistent power
382  *
383  */
384 
385  template<class Ops>
387  PowDom<Ops>::PowDom(Home home, IntView x0, IntView x1, const Ops& o)
388  : BinaryPropagator<IntView,PC_INT_DOM>(home,x0,x1), ops(o) {}
389 
390  template<class Ops>
391  inline ExecStatus
392  PowDom<Ops>::post(Home home, IntView x0, IntView x1, Ops ops) {
393  if (static_cast<unsigned int>(ops.exp()) >= sizeof(int) * CHAR_BIT) {
394  // The integer limits allow only -1, 0, 1 for x0
395  GECODE_ME_CHECK(x0.lq(home,1));
396  GECODE_ME_CHECK(x0.gq(home,-1));
397  // Just rewrite to values that can be handeled without overflow
398  ops.exp(ops.even() ? 2 : 1);
399  }
400 
401  if (ops.exp() == 0) {
402  GECODE_ME_CHECK(x1.eq(home,1));
403  return ES_OK;
404  } else if (ops.exp() == 1) {
405  return Rel::EqDom<IntView,IntView>::post(home,x0,x1);
406  }
407 
408  if (same(x0,x1)) {
409  assert(ops.exp() != 0);
410  GECODE_ME_CHECK(x0.lq(home,1));
411  GECODE_ME_CHECK(x0.gq(home,ops.even() ? 0 : -1));
412  return ES_OK;
413  }
414 
415  // Limits values such that no overflow can occur
416  assert(Limits::max == -Limits::min);
417  {
418  int l = ops.fnroot(Limits::max);
419  GECODE_ME_CHECK(x0.lq(home,l));
420  GECODE_ME_CHECK(x0.gq(home,-l));
421  }
422 
423  if ((x0.min() >= 0) || ((x1.min() >= 0) && !ops.even()))
424  return PowPlusDom<IntView,IntView,Ops>::post(home,x0,x1,ops);
425 
426  if (ops.even() && (x0.max() <= 0))
428  ::post(home,MinusView(x0),x1,ops);
429 
430  if (!ops.even() && ((x0.max() <= 0) || (x1.max() <= 0)))
432  ::post(home,MinusView(x0),MinusView(x1),ops);
433 
434  if (ops.even())
435  GECODE_ME_CHECK(x1.gq(home,0));
436 
437  assert((x0.min() < 0) && (x0.max() > 0));
438 
439  if (ops.even()) {
440  GECODE_ME_CHECK(x1.lq(home,std::max(ops.pow(x0.min()),
441  ops.pow(x0.max()))));
442  } else {
443  GECODE_ME_CHECK(x1.lq(home,ops.pow(x0.max())));
444  GECODE_ME_CHECK(x1.gq(home,ops.pow(x0.min())));
445  }
446 
447  (void) new (home) PowDom<Ops>(home,x0,x1,ops);
448  return ES_OK;
449  }
450 
451  template<class Ops>
453  PowDom<Ops>::PowDom(Space& home, bool share, PowDom<Ops>& p)
454  : BinaryPropagator<IntView,PC_INT_DOM>(home,share,p),
455  ops(p.ops) {}
456 
457  template<class Ops>
458  Actor*
459  PowDom<Ops>::copy(Space& home, bool share) {
460  return new (home) PowDom<Ops>(home,share,*this);
461  }
462 
463  template<class Ops>
464  PropCost
465  PowDom<Ops>::cost(const Space&, const ModEventDelta& med) const {
466  if (IntView::me(med) == ME_INT_VAL)
468  else if (IntView::me(med) == ME_INT_DOM)
470  else
472  }
473 
474  template<class Ops>
475  ExecStatus
477  if ((x0.min() >= 0) || ((x1.min() >= 0) && !ops.even()))
479  ::post(home(*this),x0,x1,ops)));
480 
481  if (ops.even() && (x0.max() <= 0))
483  ::post(home(*this),MinusView(x0),x1,ops)));
484 
485  if (!ops.even() && ((x0.max() <= 0) || (x1.max() <= 0)))
487  ::post(home(*this),MinusView(x0),
488  MinusView(x1),ops)));
489 
490  if (IntView::me(med) != ME_INT_DOM) {
491  GECODE_ES_CHECK(prop_pow_bnd<Ops>(home,x0,x1,ops));
492  if (x0.assigned() && x1.assigned())
493  return (ops.pow(x0.val()) == x1.val()) ?
494  home.ES_SUBSUMED(*this) : ES_FAILED;
495 
496  return home.ES_NOFIX_PARTIAL(*this,IntView::med(ME_INT_DOM));
497  }
498 
499  Region r(home);
500  if (ops.even()) {
501  ViewValues<IntView> i(x0), j(x0);
502  using namespace Iter::Values;
503  Positive<ViewValues<IntView> > pos(i);
504  Negative<ViewValues<IntView> > neg(j);
505  Minus m(r,neg);
506 
507  ValuesMapPow<Ops> vmp(ops);
508  Map<Positive<ViewValues<IntView> >,ValuesMapPow<Ops>,true> sp(pos,vmp);
509  Map<Minus,ValuesMapPow<Ops>,true> sm(m,vmp);
511  Map<Minus,ValuesMapPow<Ops>,true> > u(sp,sm);
512  GECODE_ME_CHECK(x1.inter_v(home,u,false));
513  } else {
514  ViewValues<IntView> v0(x0);
515  ValuesMapPow<Ops> vmp(ops);
517  GECODE_ME_CHECK(x1.inter_v(home,s0,false));
518  }
519 
520  if (ops.even()) {
521  ViewValues<IntView> i(x1), j(x1);
522  using namespace Iter::Values;
523  ValuesMapNroot<Ops> vmn(ops);
524  Map<ViewValues<IntView>,ValuesMapNroot<Ops>,true> si(i,vmn), sj(j,vmn);
525  Minus mi(r,si);
526  Union<Minus,
527  Map<ViewValues<IntView>,ValuesMapNroot<Ops>,true> > u(mi,sj);
528  GECODE_ME_CHECK(x0.inter_v(home,u,false));
529  } else {
531  ValuesMapNrootSigned<Ops> vmn(ops);
533  s1(v1,vmn);
534  GECODE_ME_CHECK(x0.inter_v(home,s1,false));
535  }
536 
537  return x0.assigned() ? home.ES_SUBSUMED(*this) : ES_FIX;
538  }
539 
540 }}}
541 
542 // STATISTICS: int-prop
543