Generated on Sat Feb 7 2015 02:01:19 for Gecode by doxygen 1.8.9.1
nroot.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-08-29 16:05:54 +0200 (Thu, 29 Aug 2013) $ by $Author: schulte $
11  * $Revision: 13993 $
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 nth root
47  *
48  */
49 
50  template<class Ops, bool minus>
52  prop_nroot_plus_bnd(Space& home, IntView x0, IntView x1, const Ops& ops) {
53  if (minus) {
54  bool mod;
55  do {
56  mod = false;
57  {
58  ModEvent me = x1.gq(home,-ops.cnroot(-x0.min()));
59  if (me_failed(me)) return ES_FAILED;
60  mod |= me_modified(me);
61  }
62  {
63  ModEvent me = x1.lq(home,-ops.cnroot(-x0.max()));
64  if (me_failed(me)) return ES_FAILED;
65  mod |= me_modified(me);
66  }
67  {
68  ModEvent me = x0.gq(home,-ops.tpow(-x1.min()));
69  if (me_failed(me)) return ES_FAILED;
70  mod |= me_modified(me);
71  }
72  {
73  ModEvent me = x0.lq(home,-(ops.tpow(-x1.max()-1)+1));
74  if (me_failed(me)) return ES_FAILED;
75  mod |= me_modified(me);
76  }
77  } while (mod);
78  } else {
79  bool mod;
80  do {
81  mod = false;
82  {
83  ModEvent me = x1.lq(home,ops.fnroot(x0.max()));
84  if (me_failed(me)) return ES_FAILED;
85  mod |= me_modified(me);
86  }
87  {
88  ModEvent me = x1.gq(home,ops.fnroot(x0.min()));
89  if (me_failed(me)) return ES_FAILED;
90  mod |= me_modified(me);
91  }
92  {
93  ModEvent me = x0.le(home,ops.tpow(x1.max()+1));
94  if (me_failed(me)) return ES_FAILED;
95  mod |= me_modified(me);
96  }
97  {
98  ModEvent me = x0.gq(home,ops.tpow(x1.min()));
99  if (me_failed(me)) return ES_FAILED;
100  mod |= me_modified(me);
101  }
102  } while (mod);
103  }
104  return ES_OK;
105  }
106 
107  template<class Ops, bool minus>
110  const Ops& o)
111  : BinaryPropagator<IntView,PC_INT_BND>(home,x0,x1),
112  ops(o) {}
113 
114  template<class Ops, bool minus>
117  if (minus) {
118  GECODE_ME_CHECK(x0.lq(home,0));
119  GECODE_ME_CHECK(x1.lq(home,0));
120  } else {
121  GECODE_ME_CHECK(x0.gq(home,0));
122  GECODE_ME_CHECK(x1.gq(home,0));
123  }
124  (void) new (home) NrootPlusBnd<Ops,minus>(home,x0,x1,ops);
125  return ES_OK;
126  }
127 
128  template<class Ops, bool minus>
132  : BinaryPropagator<IntView,PC_INT_BND>(home,share,p),
133  ops(p.ops) {}
134 
135  template<class Ops, bool minus>
136  Actor*
138  return new (home) NrootPlusBnd<Ops,minus>(home,share,*this);
139  }
140 
141  template<class Ops, bool minus>
142  ExecStatus
144  GECODE_ES_CHECK((prop_nroot_plus_bnd<Ops,minus>(home,x0,x1,ops)));
145  return x1.assigned() ? home.ES_SUBSUMED(*this) : ES_FIX;
146  }
147 
148 
149  /*
150  * Bounds consistent nth root
151  *
152  */
153 
154  template<class Ops>
156  prop_nroot_bnd(Space& home, IntView x0, IntView x1, const Ops& ops) {
157  assert((x0.min() < 0) && (x0.max() > 0));
158  assert((x1.min() < 0) && (x1.max() > 0));
159 
160  GECODE_ME_CHECK(x1.lq(home,ops.fnroot(x0.max())));
161  GECODE_ME_CHECK(x1.gq(home,-ops.cnroot(-x0.min())));
162  GECODE_ME_CHECK(x0.le(home,ops.tpow(x1.max()+1)));
163  GECODE_ME_CHECK(x0.gq(home,ops.tpow(x1.min()-1)+1));
164 
165  return ES_OK;
166  }
167 
168  template<class Ops>
170  NrootBnd<Ops>::NrootBnd(Home home, IntView x0, IntView x1, const Ops& o)
171  : BinaryPropagator<IntView,PC_INT_BND>(home,x0,x1),
172  ops(o) {}
173 
174  template<class Ops>
176  NrootBnd<Ops>::post(Home home, IntView x0, IntView x1, Ops ops) {
177  if (static_cast<unsigned int>(ops.exp()) >= sizeof(int) * CHAR_BIT) {
178  // The integer limits allow only -2, -1, 0, 1 for x1
179  GECODE_ME_CHECK(x1.lq(home,1));
180  GECODE_ME_CHECK(x1.gq(home,-2));
181  // Just rewrite to values that can be handeled without overflow
182  ops.exp(ops.even() ? 30 : 31);
183  }
184 
185  if (ops.exp() == 0) {
186  GECODE_ME_CHECK(x1.eq(home,1));
187  return ES_OK;
188  } else if (ops.exp() == 1) {
189  return Rel::EqBnd<IntView,IntView>::post(home,x0,x1);
190  }
191 
192  if (same(x0,x1)) {
193  assert(ops.exp() > 1);
194  GECODE_ME_CHECK(x0.lq(home,1));
195  GECODE_ME_CHECK(x0.gq(home,ops.even() ? 0 : -2));
196  return ES_OK;
197  }
198 
199  // Limits values such that no overflow can occur
200  GECODE_ME_CHECK(x1.lq(home,ops.fnroot(Limits::max)));
201  GECODE_ME_CHECK(x1.gq(home,-ops.cnroot(-Limits::min)));
202 
203  if (ops.even()) {
204  GECODE_ME_CHECK(x0.gq(home,0));
205  GECODE_ME_CHECK(x1.gq(home,0));
206  }
207 
208  if ((x0.min() >= 0) || (x1.min() >= 0))
209  return NrootPlusBnd<Ops,false>::post(home,x0,x1,ops);
210 
211  if ((x0.max() <= 0) || (x1.max() <= 0))
212  return NrootPlusBnd<Ops,true>::post(home,x0,x1,ops);
213 
214  assert((x0.min() < 0) && (x0.max() > 0));
215  assert((x1.min() < 0) && (x1.max() > 0));
216  GECODE_ES_CHECK(prop_nroot_bnd<Ops>(home,x0,x1,ops));
217  (void) new (home) NrootBnd(home,x0,x1,ops);
218  return ES_OK;
219  }
220 
221  template<class Ops>
224  : BinaryPropagator<IntView,PC_INT_BND>(home,share,p),
225  ops(p.ops) {}
226 
227  template<class Ops>
228  Actor*
229  NrootBnd<Ops>::copy(Space& home, bool share) {
230  return new (home) NrootBnd<Ops>(home,share,*this);
231  }
232 
233  template<class Ops>
234  ExecStatus
236  assert(!ops.even());
237  if ((x0.min() >= 0) || (x1.min() >= 0))
238  GECODE_REWRITE(*this,(NrootPlusBnd<Ops,false>::post(home,x0,x1,ops)));
239 
240  if ((x0.max() <= 0) || (x1.max() <= 0))
241  GECODE_REWRITE(*this,(NrootPlusBnd<Ops,true>::post(home,x0,x1,ops)));
242 
243  GECODE_ES_CHECK(prop_nroot_bnd(home,x0,x1,ops));
244 
245  return x0.assigned() && x1.assigned() ? home.ES_SUBSUMED(*this) : ES_NOFIX;
246  }
247 
248 
249  /*
250  * Domain consistent nth root
251  *
252  */
254  template<class Ops>
255  class RangesMapPow {
256  protected:
258  Ops ops;
259  public:
261  forceinline RangesMapPow(const Ops& o) : ops(o) {}
263  forceinline int min(int x) const {
264  return ops.tpow(x);
265  }
267  forceinline int max(int x) const {
268  return ops.tpow(x+1)-1;
269  }
270  };
271 
273  template<class Ops>
275  protected:
277  Ops ops;
278  public:
280  forceinline RangesMapNroot(const Ops& o) : ops(o) {}
282  forceinline int min(int x) const {
283  return (x < 0) ? -ops.cnroot(-x) : ops.fnroot(x);
284  }
286  forceinline int max(int x) const {
287  return (x < 0) ? -ops.cnroot(-x) : ops.fnroot(x);
288  }
289  };
290 
291  template<class Ops, bool minus>
294  const Ops& o)
295  : BinaryPropagator<IntView,PC_INT_DOM>(home,x0,x1),
296  ops(o) {}
297 
298  template<class Ops, bool minus>
301  if (minus) {
302  GECODE_ME_CHECK(x0.lq(home,0));
303  GECODE_ME_CHECK(x1.lq(home,0));
304  } else {
305  GECODE_ME_CHECK(x0.gq(home,0));
306  GECODE_ME_CHECK(x1.gq(home,0));
307  }
308  GECODE_ES_CHECK((prop_nroot_plus_bnd<Ops,minus>(home,x0,x1,ops)));
309  (void) new (home) NrootPlusDom<Ops,minus>(home,x0,x1,ops);
310  return ES_OK;
311  }
312 
313  template<class Ops, bool minus>
317  : BinaryPropagator<IntView,PC_INT_DOM>(home,share,p),
318  ops(p.ops) {}
319 
320  template<class Ops, bool minus>
321  Actor*
323  return new (home) NrootPlusDom<Ops,minus>(home,share,*this);
324  }
325 
326  template<class Ops, bool minus>
327  PropCost
329  if (IntView::me(med) == ME_INT_VAL)
331  else if (IntView::me(med) == ME_INT_DOM)
333  else
335  }
336 
337  template<class Ops, bool minus>
338  ExecStatus
340  if (IntView::me(med) != ME_INT_DOM) {
341  GECODE_ES_CHECK((prop_nroot_plus_bnd<Ops,minus>(home,x0,x1,ops)));
342  return x1.assigned() ? home.ES_SUBSUMED(*this)
344  }
345 
346  {
348  RangesMapNroot<Ops> rmn(ops);
350  m(r,rmn);
351  GECODE_ME_CHECK(x1.inter_r(home,m,false));
352  }
353 
354  {
356  RangesMapPow<Ops> rmp(ops);
358  m(r,rmp);
359  GECODE_ME_CHECK(x0.inter_r(home,m,false));
360  }
361 
362  return x1.assigned() ? home.ES_SUBSUMED(*this) : ES_FIX;
363  }
364 
365 
366 
367  template<class Ops>
369  NrootDom<Ops>::NrootDom(Home home, IntView x0, IntView x1, const Ops& o)
370  : BinaryPropagator<IntView,PC_INT_DOM>(home,x0,x1),
371  ops(o) {}
372 
373  template<class Ops>
375  NrootDom<Ops>::post(Home home, IntView x0, IntView x1, Ops ops) {
376  if (static_cast<unsigned int>(ops.exp()) >= sizeof(int) * CHAR_BIT) {
377  // The integer limits allow only -2, -1, 0, 1 for x1
378  GECODE_ME_CHECK(x1.lq(home,1));
379  GECODE_ME_CHECK(x1.gq(home,-2));
380  // Just rewrite to values that can be handeled without overflow
381  ops.exp(ops.even() ? 30 : 31);
382  }
383 
384  if (ops.exp() == 0) {
385  GECODE_ME_CHECK(x1.eq(home,1));
386  return ES_OK;
387  } else if (ops.exp() == 1) {
388  return Rel::EqDom<IntView,IntView>::post(home,x0,x1);
389  }
390 
391  if (same(x0,x1)) {
392  assert(ops.exp() > 1);
393  GECODE_ME_CHECK(x0.lq(home,1));
394  GECODE_ME_CHECK(x0.gq(home,ops.even() ? 0 : -2));
395  return ES_OK;
396  }
397 
398  // Limits values such that no overflow can occur
399  GECODE_ME_CHECK(x1.lq(home,ops.fnroot(Limits::max)));
400  GECODE_ME_CHECK(x1.gq(home,-ops.cnroot(-Limits::min)));
401 
402  if (ops.even()) {
403  GECODE_ME_CHECK(x0.gq(home,0));
404  GECODE_ME_CHECK(x1.gq(home,0));
405  }
406 
407  if ((x0.min() >= 0) || (x1.min() >= 0))
408  return NrootPlusDom<Ops,false>::post(home,x0,x1,ops);
409 
410  if ((x0.max() <= 0) || (x1.max() <= 0))
411  return NrootPlusDom<Ops,true>::post(home,x0,x1,ops);
412 
413  assert((x0.min() < 0) && (x0.max() > 0));
414  assert((x1.min() < 0) && (x1.max() > 0));
415  GECODE_ES_CHECK(prop_nroot_bnd<Ops>(home,x0,x1,ops));
416  (void) new (home) NrootDom(home,x0,x1,ops);
417  return ES_OK;
418  }
419 
420  template<class Ops>
423  : BinaryPropagator<IntView,PC_INT_DOM>(home,share,p),
424  ops(p.ops) {}
425 
426  template<class Ops>
427  Actor*
428  NrootDom<Ops>::copy(Space& home, bool share) {
429  return new (home) NrootDom<Ops>(home,share,*this);
430  }
431 
432  template<class Ops>
433  PropCost
434  NrootDom<Ops>::cost(const Space&, const ModEventDelta& med) const {
435  if (IntView::me(med) == ME_INT_VAL)
437  else if (IntView::me(med) == ME_INT_DOM)
439  else
441  }
442 
443  template<class Ops>
444  ExecStatus
446  assert(!ops.even());
447  if ((x0.min() >= 0) || (x1.min() >= 0))
448  GECODE_REWRITE(*this,(NrootPlusDom<Ops,false>::post(home,x0,x1,ops)));
449 
450  if ((x0.max() <= 0) || (x1.max() <= 0))
451  GECODE_REWRITE(*this,(NrootPlusDom<Ops,true>::post(home,x0,x1,ops)));
452 
453  if (IntView::me(med) != ME_INT_DOM) {
454  GECODE_ES_CHECK(prop_nroot_bnd<Ops>(home,x0,x1,ops));
455  return x0.assigned() && x1.assigned() ? home.ES_SUBSUMED(*this)
457  }
458 
459  {
461  RangesMapNroot<Ops> rmn(ops);
463  m(r,rmn);
464  GECODE_ME_CHECK(x1.inter_r(home,m,false));
465  }
466 
467  {
469  RangesMapPow<Ops> rmp(ops);
471  m(r,rmp);
472  GECODE_ME_CHECK(x0.inter_r(home,m,false));
473  }
474 
475  return x0.assigned() && x1.assigned() ? home.ES_SUBSUMED(*this) : ES_FIX;
476  }
477 
478 
479 }}}
480 
481 // STATISTICS: int-prop
482 
int min(int x) const
Perform mapping of minimum.
Definition: nroot.hpp:263
#define GECODE_REWRITE(prop, post)
Rewrite propagator by executing post function.
Definition: macros.hpp:109
void mod(Home home, IntVar x0, IntVar x1, IntVar x2, IntConLevel icl)
Post propagator for .
Definition: arithmetic.cpp:213
int max(int x) const
Perform mapping of maximum.
Definition: nroot.hpp:286
ExecStatus ES_SUBSUMED(Propagator &p)
Definition: core.hpp:2973
Domain consistent n-th root propagator.
Definition: arithmetic.hh:582
ModEvent eq(Space &home, int n)
Restrict domain values to be equal to n.
Definition: int.hpp:160
Positive bounds consistent n-th root propagator.
Definition: arithmetic.hh:496
ExecStatus ES_NOFIX_PARTIAL(Propagator &p, const ModEventDelta &med)
Propagator p has not computed partial fixpoint
Definition: core.hpp:2986
NrootDom(Space &home, bool share, NrootDom< Ops > &p)
Constructor for cloning p.
Definition: nroot.hpp:422
static ExecStatus post(Home home, View0 x0, View1 x1)
Post domain consistent propagator .
Definition: eq.hpp:120
int ModEvent
Type for modification events.
Definition: core.hpp:146
Expensive.
Definition: core.hpp:564
static ExecStatus post(Home home, IntView x0, IntView x1, Ops ops)
Post propagator.
Definition: nroot.hpp:375
RangesMapNroot(const Ops &o)
Initialize with operations o.
Definition: nroot.hpp:280
Ops ops
Power operations.
Definition: nroot.hpp:258
Range iterator for integer variable views
Definition: int.hpp:236
static ExecStatus post(Home home, IntView x0, IntView x1, Ops ops)
Post propagator.
Definition: nroot.hpp:176
static ExecStatus post(Home home, IntView x0, IntView x1, Ops ops)
Post propagator.
Definition: nroot.hpp:116
Propagation has computed fixpoint.
Definition: core.hpp:528
static PropCost unary(PropCost::Mod m)
Single variable for modifier pcm.
Definition: core.hpp:4058
const int max
Largest allowed integer value.
Definition: int.hh:113
Computation spaces.
Definition: core.hpp:1362
virtual Actor * copy(Space &home, bool share)
Copy propagator during cloning.
Definition: nroot.hpp:428
const int min
Smallest allowed integer value.
Definition: int.hh:115
Base-class for both propagators and branchers.
Definition: core.hpp:666
static ExecStatus post(Home home, View0 x0, View1 x1)
Post bounds consistent propagator .
Definition: eq.hpp:52
int max(void) const
Return maximum of domain.
Definition: int.hpp:62
#define GECODE_ES_CHECK(es)
Check whether execution status es is failed or subsumed, and forward failure or subsumption.
Definition: macros.hpp:84
bool same(const CachedView< View > &x, const CachedView< View > &y)
Definition: cached.hpp:389
virtual Actor * copy(Space &home, bool share)
Copy propagator during cloning.
Definition: nroot.hpp:229
ExecStatus prop_nroot_plus_bnd(Space &home, IntView x0, IntView x1, const Ops &ops)
Definition: nroot.hpp:52
ModEvent le(Space &home, int n)
Restrict domain values to be less than n.
Definition: int.hpp:124
int p
Number of positive literals for node type.
Definition: bool-expr.cpp:236
NrootBnd(Space &home, bool share, NrootBnd< Ops > &p)
Constructor for cloning p.
Definition: nroot.hpp:223
Domain consistent n-th root propagator.
Definition: arithmetic.hh:548
Execution has resulted in failure.
Definition: core.hpp:525
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Definition: nroot.hpp:143
ModEvent lq(Space &home, int n)
Restrict domain values to be less or equal than n.
Definition: int.hpp:115
NNF * r
Right subtree.
Definition: bool-expr.cpp:246
Binary propagator.
Definition: propagator.hpp:87
const Gecode::PropCond PC_INT_BND
Propagate when minimum or maximum of a view changes.
Definition: var-type.hpp:91
const Gecode::ModEvent ME_INT_VAL
Domain operation has resulted in a value (assigned variable)
Definition: var-type.hpp:56
virtual PropCost cost(const Space &home, const ModEventDelta &med) const
Cost function.
Definition: nroot.hpp:328
const Gecode::PropCond PC_INT_DOM
Propagate when domain changes.
Definition: var-type.hpp:100
int min(void) const
Return minimum of domain.
Definition: int.hpp:58
int max(int x) const
Perform mapping of maximum.
Definition: nroot.hpp:267
virtual Actor * copy(Space &home, bool share)
Copy propagator during cloning.
Definition: nroot.hpp:322
ExecStatus prop_nroot_bnd(Space &home, IntView x0, IntView x1, const Ops &ops)
Definition: nroot.hpp:156
Mapping ranges to powers.
Definition: nroot.hpp:255
virtual Actor * copy(Space &home, bool share)
Copy propagator during cloning.
Definition: nroot.hpp:137
#define GECODE_ME_CHECK(me)
Check whether modification event me is failed, and forward failure.
Definition: macros.hpp:45
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Definition: nroot.hpp:445
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Definition: nroot.hpp:339
Integer view for integer variables.
Definition: view.hpp:129
Node * x
Pointer to corresponding Boolean expression node.
Definition: bool-expr.cpp:253
Propagation cost.
Definition: core.hpp:537
const Gecode::ModEvent ME_INT_DOM
Domain operation has changed the domain.
Definition: var-type.hpp:72
ExecStatus
Definition: core.hpp:523
static ModEvent me(const ModEventDelta &med)
Return modification event for view type in med.
NrootPlusDom(Space &home, bool share, NrootPlusDom< Ops, minus > &p)
Constructor for cloning p.
Definition: nroot.hpp:315
Range iterator for mapping ranges.
Definition: ranges-map.hpp:49
#define forceinline
Definition: config.hpp:132
bool me_modified(ModEvent me)
Check whether modification event me describes variable modification.
Definition: modevent.hpp:63
static ExecStatus post(Home home, IntView x0, IntView x1, Ops ops)
Post propagator.
Definition: nroot.hpp:300
virtual PropCost cost(const Space &home, const ModEventDelta &med) const
Cost function.
Definition: nroot.hpp:434
int min(int x) const
Perform mapping of minimum.
Definition: nroot.hpp:282
ModEvent gq(Space &home, int n)
Restrict domain values to be greater or equal than n.
Definition: int.hpp:133
int med(void) const
Return median of domain (greatest element not greater than the median)
Definition: int.hpp:66
Execution is okay.
Definition: core.hpp:527
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Definition: nroot.hpp:235
Propagation has not computed fixpoint.
Definition: core.hpp:526
RangesMapPow(const Ops &o)
Initialize with operations o.
Definition: nroot.hpp:261
Gecode toplevel namespace
Mapping integer to n-th root.
Definition: nroot.hpp:274
int ModEventDelta
Modification event deltas.
Definition: core.hpp:173
Home class for posting propagators
Definition: core.hpp:717
static PropCost binary(PropCost::Mod m)
Two variables for modifier pcm.
Definition: core.hpp:4054
Bounds consistent n-th root propagator.
Definition: arithmetic.hh:522
bool me_failed(ModEvent me)
Check whether modification event me is failed.
Definition: modevent.hpp:58
NrootPlusBnd(Space &home, bool share, NrootPlusBnd< Ops, minus > &p)
Constructor for cloning p.
Definition: nroot.hpp:130