Generated on Tue Oct 22 2013 00:49:02 for Gecode by doxygen 1.8.4
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-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  * Bounds consistent nth root
47  *
48  */
49 
50  template<class Ops>
52  prop_nroot_bnd(Space& home, IntView x0, IntView x1, const Ops& ops) {
53  bool mod;
54  do {
55  mod = false;
56  {
57  ModEvent me = x1.lq(home,ops.fnroot(x0.max()));
58  if (me_failed(me)) return ES_FAILED;
59  mod |= me_modified(me);
60  }
61  {
62  ModEvent me = x1.gq(home,ops.fnroot(x0.min()));
63  if (me_failed(me)) return ES_FAILED;
64  mod |= me_modified(me);
65  }
66  {
67  ModEvent me = x0.le(home,ops.tpow(x1.max()+1));
68  if (me_failed(me)) return ES_FAILED;
69  mod |= me_modified(me);
70  }
71  {
72  ModEvent me = x0.gq(home,ops.pow(x1.min()));
73  if (me_failed(me)) return ES_FAILED;
74  mod |= me_modified(me);
75  }
76  } while (mod);
77  return ES_OK;
78  }
79 
80  template<class Ops>
82  NrootBnd<Ops>::NrootBnd(Home home, IntView x0, IntView x1, const Ops& o)
83  : BinaryPropagator<IntView,PC_INT_BND>(home,x0,x1),
84  ops(o) {
85  }
86 
87  template<class Ops>
89  NrootBnd<Ops>::post(Home home, IntView x0, IntView x1, Ops ops) {
90  GECODE_ME_CHECK(x0.gq(home,0));
91  GECODE_ME_CHECK(x1.gq(home,0));
92 
93  if (static_cast<unsigned int>(ops.exp()) >= sizeof(int) * CHAR_BIT) {
94  // The integer limits allow only 0 and 1 for x1
95  GECODE_ME_CHECK(x1.lq(home,1));
96  }
97 
98  if (ops.exp() == 0) {
99  GECODE_ME_CHECK(x1.eq(home,1));
100  return ES_OK;
101  } else if (ops.exp() == 1) {
102  return Rel::EqBnd<IntView,IntView>::post(home,x0,x1);
103  }
104 
105  if (same(x0,x1)) {
106  assert(ops.exp() > 1);
107  GECODE_ME_CHECK(x1.lq(home,1));
108  return ES_OK;
109  }
110 
111  // Limits values such that no overflow can occur
112  GECODE_ME_CHECK(x1.lq(home,ops.fnroot(Limits::max)));
113 
114  GECODE_ES_CHECK(prop_nroot_bnd<Ops>(home,x0,x1,ops));
115  (void) new (home) NrootBnd(home,x0,x1,ops);
116 
117  return ES_OK;
118  }
119 
120  template<class Ops>
123  : BinaryPropagator<IntView,PC_INT_BND>(home,share,p),
124  ops(p.ops) {}
125 
126  template<class Ops>
127  Actor*
128  NrootBnd<Ops>::copy(Space& home, bool share) {
129  return new (home) NrootBnd<Ops>(home,share,*this);
130  }
131 
132  template<class Ops>
133  ExecStatus
135  GECODE_ES_CHECK(prop_nroot_bnd(home,x0,x1,ops));
136  return x1.assigned() ? home.ES_SUBSUMED(*this) : ES_FIX;
137  }
138 
139 
140  /*
141  * Domain consistent nth root
142  *
143  */
145  template<class Ops>
146  class RangesMapPow {
147  protected:
149  Ops ops;
150  public:
152  forceinline RangesMapPow(const Ops& o) : ops(o) {}
154  forceinline int min(int x) const {
155  return ops.pow(x);
156  }
158  forceinline int max(int x) const {
159  return ops.tpow(x+1)-1;
160  }
161  };
162 
164  template<class Ops>
166  protected:
168  Ops ops;
169  public:
171  forceinline RangesMapNroot(const Ops& o) : ops(o) {}
173  forceinline int min(int x) const {
174  return ops.fnroot(x);
175  }
177  forceinline int max(int x) const {
178  return ops.fnroot(x);
179  }
180  };
181 
182  template<class Ops>
184  NrootDom<Ops>::NrootDom(Home home, IntView x0, IntView x1, const Ops& o)
185  : BinaryPropagator<IntView,PC_INT_DOM>(home,x0,x1),
186  ops(o) {}
187 
188  template<class Ops>
190  NrootDom<Ops>::post(Home home, IntView x0, IntView x1, Ops ops) {
191  GECODE_ME_CHECK(x0.gq(home,0));
192  GECODE_ME_CHECK(x1.gq(home,0));
193 
194  if (static_cast<unsigned int>(ops.exp()) >= sizeof(int) * CHAR_BIT) {
195  // The integer limits allow only 0 and 1 for x1
196  GECODE_ME_CHECK(x1.lq(home,1));
197  }
198 
199  if (ops.exp() == 0) {
200  GECODE_ME_CHECK(x1.eq(home,1));
201  return ES_OK;
202  } else if (ops.exp() == 1) {
203  return Rel::EqDom<IntView,IntView>::post(home,x0,x1);
204  }
205 
206  if (same(x0,x1)) {
207  assert(ops.exp() > 1);
208  GECODE_ME_CHECK(x1.lq(home,1));
209  return ES_OK;
210  }
211 
212  // Limits values such that no overflow can occur
213  GECODE_ME_CHECK(x1.lq(home,ops.fnroot(Limits::max)));
214 
215  GECODE_ES_CHECK(prop_nroot_bnd(home,x0,x1,ops));
216  (void) new (home) NrootDom<Ops>(home,x0,x1,ops);
217 
218  return ES_OK;
219  }
220 
221  template<class Ops>
224  : BinaryPropagator<IntView,PC_INT_DOM>(home,share,p),
225  ops(p.ops) {}
226 
227  template<class Ops>
228  Actor*
229  NrootDom<Ops>::copy(Space& home, bool share) {
230  return new (home) NrootDom<Ops>(home,share,*this);
231  }
232 
233  template<class Ops>
234  PropCost
235  NrootDom<Ops>::cost(const Space&, const ModEventDelta& med) const {
236  if (IntView::me(med) == ME_INT_VAL)
238  else if (IntView::me(med) == ME_INT_DOM)
240  else
242  }
243 
244  template<class Ops>
245  ExecStatus
247  if (IntView::me(med) != ME_INT_DOM) {
248  GECODE_ES_CHECK(prop_nroot_bnd(home,x0,x1,ops));
249  return x1.assigned() ? home.ES_SUBSUMED(*this)
251  }
252 
253  {
255  RangesMapNroot<Ops> rmn(ops);
257  m(r,rmn);
258  GECODE_ME_CHECK(x1.inter_r(home,m,false));
259  }
260 
261  {
263  RangesMapPow<Ops> rmp(ops);
265  m(r,rmp);
266  GECODE_ME_CHECK(x0.inter_r(home,m,false));
267  }
268 
269  return x1.assigned() ? home.ES_SUBSUMED(*this) : ES_FIX;
270  }
271 
272 
273 }}}
274 
275 // STATISTICS: int-prop
276