this repo has no description
dekker.one
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 * This file is part of Gecode, the generic constraint
10 * development environment:
11 * http://www.gecode.org
12 *
13 * Permission is hereby granted, free of charge, to any person obtaining
14 * a copy of this software and associated documentation files (the
15 * "Software"), to deal in the Software without restriction, including
16 * without limitation the rights to use, copy, modify, merge, publish,
17 * distribute, sublicense, and/or sell copies of the Software, and to
18 * permit persons to whom the Software is furnished to do so, subject to
19 * the following conditions:
20 *
21 * The above copyright notice and this permission notice shall be
22 * included in all copies or substantial portions of the Software.
23 *
24 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
25 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
26 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
27 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
28 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
29 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
30 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
31 *
32 */
33
34#include <gecode/int/rel.hh>
35
36#include <climits>
37#include <algorithm>
38
39namespace Gecode { namespace Int { namespace Arithmetic {
40
41 /*
42 * Positive bounds consistent nth root
43 *
44 */
45
46 template<class Ops, bool minus>
47 forceinline ExecStatus
48 prop_nroot_plus_bnd(Space& home, IntView x0, IntView x1, const Ops& ops) {
49 if (minus) {
50 bool mod;
51 do {
52 mod = false;
53 {
54 ModEvent me = x1.gq(home,-ops.cnroot(-x0.min()));
55 if (me_failed(me)) return ES_FAILED;
56 mod |= me_modified(me);
57 }
58 {
59 ModEvent me = x1.lq(home,-ops.cnroot(-x0.max()));
60 if (me_failed(me)) return ES_FAILED;
61 mod |= me_modified(me);
62 }
63 {
64 ModEvent me = x0.gq(home,-ops.tpow(-x1.min()));
65 if (me_failed(me)) return ES_FAILED;
66 mod |= me_modified(me);
67 }
68 {
69 ModEvent me = x0.lq(home,-(ops.tpow(-x1.max()-1)+1));
70 if (me_failed(me)) return ES_FAILED;
71 mod |= me_modified(me);
72 }
73 } while (mod);
74 } else {
75 bool mod;
76 do {
77 mod = false;
78 {
79 ModEvent me = x1.lq(home,ops.fnroot(x0.max()));
80 if (me_failed(me)) return ES_FAILED;
81 mod |= me_modified(me);
82 }
83 {
84 ModEvent me = x1.gq(home,ops.fnroot(x0.min()));
85 if (me_failed(me)) return ES_FAILED;
86 mod |= me_modified(me);
87 }
88 {
89 ModEvent me = x0.le(home,ops.tpow(x1.max()+1));
90 if (me_failed(me)) return ES_FAILED;
91 mod |= me_modified(me);
92 }
93 {
94 ModEvent me = x0.gq(home,ops.tpow(x1.min()));
95 if (me_failed(me)) return ES_FAILED;
96 mod |= me_modified(me);
97 }
98 } while (mod);
99 }
100 return ES_OK;
101 }
102
103 template<class Ops, bool minus>
104 forceinline
105 NrootPlusBnd<Ops,minus>::NrootPlusBnd(Home home, IntView x0, IntView x1,
106 const Ops& o)
107 : BinaryPropagator<IntView,PC_INT_BND>(home,x0,x1),
108 ops(o) {}
109
110 template<class Ops, bool minus>
111 forceinline ExecStatus
112 NrootPlusBnd<Ops,minus>::post(Home home, IntView x0, IntView x1, Ops ops) {
113 if (minus) {
114 GECODE_ME_CHECK(x0.lq(home,0));
115 GECODE_ME_CHECK(x1.lq(home,0));
116 } else {
117 GECODE_ME_CHECK(x0.gq(home,0));
118 GECODE_ME_CHECK(x1.gq(home,0));
119 }
120 (void) new (home) NrootPlusBnd<Ops,minus>(home,x0,x1,ops);
121 return ES_OK;
122 }
123
124 template<class Ops, bool minus>
125 forceinline
126 NrootPlusBnd<Ops,minus>::NrootPlusBnd(Space& home,
127 NrootPlusBnd<Ops,minus>& p)
128 : BinaryPropagator<IntView,PC_INT_BND>(home,p),
129 ops(p.ops) {}
130
131 template<class Ops, bool minus>
132 Actor*
133 NrootPlusBnd<Ops,minus>::copy(Space& home) {
134 return new (home) NrootPlusBnd<Ops,minus>(home,*this);
135 }
136
137 template<class Ops, bool minus>
138 ExecStatus
139 NrootPlusBnd<Ops,minus>::propagate(Space& home, const ModEventDelta&) {
140 GECODE_ES_CHECK((prop_nroot_plus_bnd<Ops,minus>(home,x0,x1,ops)));
141 return x1.assigned() ? home.ES_SUBSUMED(*this) : ES_FIX;
142 }
143
144
145 /*
146 * Bounds consistent nth root
147 *
148 */
149
150 template<class Ops>
151 forceinline ExecStatus
152 prop_nroot_bnd(Space& home, IntView x0, IntView x1, const Ops& ops) {
153 assert((x0.min() < 0) && (x0.max() > 0));
154 assert((x1.min() < 0) && (x1.max() > 0));
155
156 GECODE_ME_CHECK(x1.lq(home,ops.fnroot(x0.max())));
157 GECODE_ME_CHECK(x1.gq(home,-ops.cnroot(-x0.min())));
158 GECODE_ME_CHECK(x0.le(home,ops.tpow(x1.max()+1)));
159 GECODE_ME_CHECK(x0.gq(home,ops.tpow(x1.min()-1)+1));
160
161 return ES_OK;
162 }
163
164 template<class Ops>
165 forceinline
166 NrootBnd<Ops>::NrootBnd(Home home, IntView x0, IntView x1, const Ops& o)
167 : BinaryPropagator<IntView,PC_INT_BND>(home,x0,x1),
168 ops(o) {}
169
170 template<class Ops>
171 forceinline ExecStatus
172 NrootBnd<Ops>::post(Home home, IntView x0, IntView x1, Ops ops) {
173 if (static_cast<unsigned int>(ops.exp()) >= sizeof(int) * CHAR_BIT) {
174 // The integer limits allow only -2, -1, 0, 1 for x1
175 GECODE_ME_CHECK(x1.lq(home,1));
176 GECODE_ME_CHECK(x1.gq(home,-2));
177 // Just rewrite to values that can be handeled without overflow
178 ops.exp(ops.even() ? 30 : 31);
179 }
180
181 if (ops.exp() == 0) {
182 GECODE_ME_CHECK(x1.eq(home,1));
183 return ES_OK;
184 } else if (ops.exp() == 1) {
185 return Rel::EqBnd<IntView,IntView>::post(home,x0,x1);
186 }
187
188 if (x0 == x1) {
189 assert(ops.exp() > 1);
190 GECODE_ME_CHECK(x0.lq(home,1));
191 GECODE_ME_CHECK(x0.gq(home,ops.even() ? 0 : -2));
192 return ES_OK;
193 }
194
195 // Limits values such that no overflow can occur
196 GECODE_ME_CHECK(x1.lq(home,ops.fnroot(Limits::max)));
197 GECODE_ME_CHECK(x1.gq(home,-ops.cnroot(-Limits::min)));
198
199 if (ops.even()) {
200 GECODE_ME_CHECK(x0.gq(home,0));
201 GECODE_ME_CHECK(x1.gq(home,0));
202 }
203
204 if ((x0.min() >= 0) || (x1.min() >= 0))
205 return NrootPlusBnd<Ops,false>::post(home,x0,x1,ops);
206
207 if ((x0.max() <= 0) || (x1.max() <= 0))
208 return NrootPlusBnd<Ops,true>::post(home,x0,x1,ops);
209
210 assert((x0.min() < 0) && (x0.max() > 0));
211 assert((x1.min() < 0) && (x1.max() > 0));
212 GECODE_ES_CHECK(prop_nroot_bnd<Ops>(home,x0,x1,ops));
213 (void) new (home) NrootBnd(home,x0,x1,ops);
214 return ES_OK;
215 }
216
217 template<class Ops>
218 forceinline
219 NrootBnd<Ops>::NrootBnd(Space& home, NrootBnd<Ops>& p)
220 : BinaryPropagator<IntView,PC_INT_BND>(home,p),
221 ops(p.ops) {}
222
223 template<class Ops>
224 Actor*
225 NrootBnd<Ops>::copy(Space& home) {
226 return new (home) NrootBnd<Ops>(home,*this);
227 }
228
229 template<class Ops>
230 ExecStatus
231 NrootBnd<Ops>::propagate(Space& home, const ModEventDelta&) {
232 assert(!ops.even());
233 if ((x0.min() >= 0) || (x1.min() >= 0))
234 GECODE_REWRITE(*this,(NrootPlusBnd<Ops,false>::post(home(*this),x0,x1,ops)));
235
236 if ((x0.max() <= 0) || (x1.max() <= 0))
237 GECODE_REWRITE(*this,(NrootPlusBnd<Ops,true>::post(home(*this),x0,x1,ops)));
238
239 GECODE_ES_CHECK(prop_nroot_bnd(home,x0,x1,ops));
240
241 return x0.assigned() && x1.assigned() ? home.ES_SUBSUMED(*this) : ES_NOFIX;
242 }
243
244
245 /*
246 * Domain consistent nth root
247 *
248 */
249 /// Mapping ranges to powers
250 template<class Ops>
251 class RangesMapPow {
252 protected:
253 /// Power operations
254 Ops ops;
255 public:
256 /// Initialize with operations \a o
257 forceinline RangesMapPow(const Ops& o) : ops(o) {}
258 /// Perform mapping of minimum
259 forceinline int min(int x) const {
260 return ops.tpow(x);
261 }
262 /// Perform mapping of maximum
263 forceinline int max(int x) const {
264 return ops.tpow(x+1)-1;
265 }
266 };
267
268 /// Mapping integer to n-th root
269 template<class Ops>
270 class RangesMapNroot {
271 protected:
272 /// Power operations
273 Ops ops;
274 public:
275 /// Initialize with operations \a o
276 forceinline RangesMapNroot(const Ops& o) : ops(o) {}
277 /// Perform mapping of minimum
278 forceinline int min(int x) const {
279 return (x < 0) ? -ops.cnroot(-x) : ops.fnroot(x);
280 }
281 /// Perform mapping of maximum
282 forceinline int max(int x) const {
283 return (x < 0) ? -ops.cnroot(-x) : ops.fnroot(x);
284 }
285 };
286
287 template<class Ops, bool minus>
288 forceinline
289 NrootPlusDom<Ops,minus>::NrootPlusDom(Home home, IntView x0, IntView x1,
290 const Ops& o)
291 : BinaryPropagator<IntView,PC_INT_DOM>(home,x0,x1),
292 ops(o) {}
293
294 template<class Ops, bool minus>
295 forceinline ExecStatus
296 NrootPlusDom<Ops,minus>::post(Home home, IntView x0, IntView x1, Ops ops) {
297 if (minus) {
298 GECODE_ME_CHECK(x0.lq(home,0));
299 GECODE_ME_CHECK(x1.lq(home,0));
300 } else {
301 GECODE_ME_CHECK(x0.gq(home,0));
302 GECODE_ME_CHECK(x1.gq(home,0));
303 }
304 GECODE_ES_CHECK((prop_nroot_plus_bnd<Ops,minus>(home,x0,x1,ops)));
305 (void) new (home) NrootPlusDom<Ops,minus>(home,x0,x1,ops);
306 return ES_OK;
307 }
308
309 template<class Ops, bool minus>
310 forceinline
311 NrootPlusDom<Ops,minus>::NrootPlusDom(Space& home,
312 NrootPlusDom<Ops,minus>& p)
313 : BinaryPropagator<IntView,PC_INT_DOM>(home,p),
314 ops(p.ops) {}
315
316 template<class Ops, bool minus>
317 Actor*
318 NrootPlusDom<Ops,minus>::copy(Space& home) {
319 return new (home) NrootPlusDom<Ops,minus>(home,*this);
320 }
321
322 template<class Ops, bool minus>
323 PropCost
324 NrootPlusDom<Ops,minus>::cost(const Space&, const ModEventDelta& med) const {
325 if (IntView::me(med) == ME_INT_VAL)
326 return PropCost::unary(PropCost::LO);
327 else if (IntView::me(med) == ME_INT_DOM)
328 return PropCost::binary(PropCost::HI);
329 else
330 return PropCost::binary(PropCost::LO);
331 }
332
333 template<class Ops, bool minus>
334 ExecStatus
335 NrootPlusDom<Ops,minus>::propagate(Space& home, const ModEventDelta& med) {
336 if (IntView::me(med) != ME_INT_DOM) {
337 GECODE_ES_CHECK((prop_nroot_plus_bnd<Ops,minus>(home,x0,x1,ops)));
338 return x1.assigned() ? home.ES_SUBSUMED(*this)
339 : home.ES_NOFIX_PARTIAL(*this,IntView::med(ME_INT_DOM));
340 }
341
342 {
343 ViewRanges<IntView> r(x0);
344 RangesMapNroot<Ops> rmn(ops);
345 Iter::Ranges::Map<ViewRanges<IntView>,RangesMapNroot<Ops>,false>
346 m(r,rmn);
347 GECODE_ME_CHECK(x1.inter_r(home,m,false));
348 }
349
350 {
351 ViewRanges<IntView> r(x1);
352 RangesMapPow<Ops> rmp(ops);
353 Iter::Ranges::Map<ViewRanges<IntView>,RangesMapPow<Ops>,true>
354 m(r,rmp);
355 GECODE_ME_CHECK(x0.inter_r(home,m,false));
356 }
357
358 return x1.assigned() ? home.ES_SUBSUMED(*this) : ES_FIX;
359 }
360
361
362
363 template<class Ops>
364 forceinline
365 NrootDom<Ops>::NrootDom(Home home, IntView x0, IntView x1, const Ops& o)
366 : BinaryPropagator<IntView,PC_INT_DOM>(home,x0,x1),
367 ops(o) {}
368
369 template<class Ops>
370 forceinline ExecStatus
371 NrootDom<Ops>::post(Home home, IntView x0, IntView x1, Ops ops) {
372 if (static_cast<unsigned int>(ops.exp()) >= sizeof(int) * CHAR_BIT) {
373 // The integer limits allow only -2, -1, 0, 1 for x1
374 GECODE_ME_CHECK(x1.lq(home,1));
375 GECODE_ME_CHECK(x1.gq(home,-2));
376 // Just rewrite to values that can be handeled without overflow
377 ops.exp(ops.even() ? 30 : 31);
378 }
379
380 if (ops.exp() == 0) {
381 GECODE_ME_CHECK(x1.eq(home,1));
382 return ES_OK;
383 } else if (ops.exp() == 1) {
384 return Rel::EqDom<IntView,IntView>::post(home,x0,x1);
385 }
386
387 if (x0 == x1) {
388 assert(ops.exp() > 1);
389 GECODE_ME_CHECK(x0.lq(home,1));
390 GECODE_ME_CHECK(x0.gq(home,ops.even() ? 0 : -2));
391 return ES_OK;
392 }
393
394 // Limits values such that no overflow can occur
395 GECODE_ME_CHECK(x1.lq(home,ops.fnroot(Limits::max)));
396 GECODE_ME_CHECK(x1.gq(home,-ops.cnroot(-Limits::min)));
397
398 if (ops.even()) {
399 GECODE_ME_CHECK(x0.gq(home,0));
400 GECODE_ME_CHECK(x1.gq(home,0));
401 }
402
403 if ((x0.min() >= 0) || (x1.min() >= 0))
404 return NrootPlusDom<Ops,false>::post(home,x0,x1,ops);
405
406 if ((x0.max() <= 0) || (x1.max() <= 0))
407 return NrootPlusDom<Ops,true>::post(home,x0,x1,ops);
408
409 assert((x0.min() < 0) && (x0.max() > 0));
410 assert((x1.min() < 0) && (x1.max() > 0));
411 GECODE_ES_CHECK(prop_nroot_bnd<Ops>(home,x0,x1,ops));
412 (void) new (home) NrootDom(home,x0,x1,ops);
413 return ES_OK;
414 }
415
416 template<class Ops>
417 forceinline
418 NrootDom<Ops>::NrootDom(Space& home, NrootDom<Ops>& p)
419 : BinaryPropagator<IntView,PC_INT_DOM>(home,p),
420 ops(p.ops) {}
421
422 template<class Ops>
423 Actor*
424 NrootDom<Ops>::copy(Space& home) {
425 return new (home) NrootDom<Ops>(home,*this);
426 }
427
428 template<class Ops>
429 PropCost
430 NrootDom<Ops>::cost(const Space&, const ModEventDelta& med) const {
431 if (IntView::me(med) == ME_INT_VAL)
432 return PropCost::unary(PropCost::LO);
433 else if (IntView::me(med) == ME_INT_DOM)
434 return PropCost::binary(PropCost::HI);
435 else
436 return PropCost::binary(PropCost::LO);
437 }
438
439 template<class Ops>
440 ExecStatus
441 NrootDom<Ops>::propagate(Space& home, const ModEventDelta& med) {
442 assert(!ops.even());
443 if ((x0.min() >= 0) || (x1.min() >= 0))
444 GECODE_REWRITE(*this,(NrootPlusDom<Ops,false>::post(home(*this),x0,x1,ops)));
445
446 if ((x0.max() <= 0) || (x1.max() <= 0))
447 GECODE_REWRITE(*this,(NrootPlusDom<Ops,true>::post(home(*this),x0,x1,ops)));
448
449 if (IntView::me(med) != ME_INT_DOM) {
450 GECODE_ES_CHECK(prop_nroot_bnd<Ops>(home,x0,x1,ops));
451 return x0.assigned() && x1.assigned() ? home.ES_SUBSUMED(*this)
452 : home.ES_NOFIX_PARTIAL(*this,IntView::med(ME_INT_DOM));
453 }
454
455 {
456 ViewRanges<IntView> r(x0);
457 RangesMapNroot<Ops> rmn(ops);
458 Iter::Ranges::Map<ViewRanges<IntView>,RangesMapNroot<Ops>,false>
459 m(r,rmn);
460 GECODE_ME_CHECK(x1.inter_r(home,m,false));
461 }
462
463 {
464 ViewRanges<IntView> r(x1);
465 RangesMapPow<Ops> rmp(ops);
466 Iter::Ranges::Map<ViewRanges<IntView>,RangesMapPow<Ops>,true>
467 m(r,rmp);
468 GECODE_ME_CHECK(x0.inter_r(home,m,false));
469 }
470
471 return x0.assigned() && x1.assigned() ? home.ES_SUBSUMED(*this) : ES_FIX;
472 }
473
474
475}}}
476
477// STATISTICS: int-prop
478