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