Generated on Thu Jan 16 2025 00:00:00 for Gecode by doxygen 1.14.0
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 * 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>
77 PowPlusBnd<VA,VB,Ops>::PowPlusBnd(Home home, VA x0, VB x1, const Ops& o)
79 ops(o) {}
80
81 template<class VA, class VB, class Ops>
84 GECODE_ME_CHECK(x0.gq(home,0));
85 GECODE_ME_CHECK(x1.gq(home,0));
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>
99
100 template<class VA, class VB, class Ops>
101 Actor*
103 return new (home) PowPlusBnd<VA,VB,Ops>(home,*this);
104 }
105
106 template<class VA, class VB, class 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>
145 ops(o) {}
146
147 template<class Ops>
148 inline ExecStatus
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) {
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()))
182
183 if (ops.even() && (x0.max() <= 0))
185 ::post(home,MinusView(x0),x1,ops);
186
187 if (!ops.even() && ((x0.max() <= 0) || (x1.max() <= 0)))
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>
213
214 template<class Ops>
215 Actor*
217 return new (home) PowBnd<Ops>(home,*this);
218 }
219
220 template<class Ops>
223 if ((x0.min() >= 0) || ((x1.min() >= 0) && !ops.even()))
225 ::post(home(*this),x0,x1,ops)));
226
227 if (ops.even() && (x0.max() <= 0))
229 ::post(home(*this),MinusView(x0),x1,ops)));
230
231 if (!ops.even() && ((x0.max() <= 0) || (x1.max() <= 0)))
233 ::post(home(*this),MinusView(x0),
234 MinusView(x1),ops)));
235
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
252 template<class Ops>
254 protected:
256 Ops ops;
257 public:
259 forceinline ValuesMapPow(const Ops& o) : ops(o) {}
261 forceinline int val(int x) const {
262 return ops.pow(x);
263 }
264 };
265
267 template<class Ops>
269 protected:
271 Ops ops;
272 public:
274 forceinline ValuesMapNroot(const Ops& o) : ops(o) {}
276 forceinline int val(int x) const {
277 return ops.fnroot(x);
278 }
279 };
280
282 template<class Ops>
284 protected:
286 Ops ops;
287 public:
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>
306 PowPlusDom<VA,VB,Ops>::PowPlusDom(Home home, VA x0, VB x1, const Ops& o)
308 ops(o) {}
309
310 template<class VA, class VB, class Ops>
313 GECODE_ME_CHECK(x0.gq(home,0));
314 GECODE_ME_CHECK(x1.gq(home,0));
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>
328
329 template<class VA, class VB, class Ops>
330 Actor*
332 return new (home) PowPlusDom<VA,VB,Ops>(home,*this);
333 }
334
335 template<class VA, class VB, class Ops>
338 if (VA::me(med) == ME_INT_VAL)
340 else if (VA::me(med) == ME_INT_DOM)
342 else
344 }
345
346 template<class VA, class VB, class Ops>
349 if (VA::me(med) != ME_INT_DOM) {
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);
360 GECODE_ME_CHECK(x1.inter_v(home,s0,false));
361 }
362
363 {
364 ViewValues<VB> v1(x1);
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>
383
384 template<class Ops>
385 inline ExecStatus
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) {
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()))
419
420 if (ops.even() && (x0.max() <= 0))
422 ::post(home,MinusView(x0),x1,ops);
423
424 if (!ops.even() && ((x0.max() <= 0) || (x1.max() <= 0)))
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>
450
451 template<class Ops>
452 Actor*
454 return new (home) PowDom<Ops>(home,*this);
455 }
456
457 template<class Ops>
459 PowDom<Ops>::cost(const Space&, const ModEventDelta& med) const {
460 if (IntView::me(med) == ME_INT_VAL)
462 else if (IntView::me(med) == ME_INT_DOM)
464 else
466 }
467
468 template<class Ops>
471 if ((x0.min() >= 0) || ((x1.min() >= 0) && !ops.even()))
473 ::post(home(*this),x0,x1,ops)));
474
475 if (ops.even() && (x0.max() <= 0))
477 ::post(home(*this),MinusView(x0),x1,ops)));
478
479 if (!ops.even() && ((x0.max() <= 0) || (x1.max() <= 0)))
481 ::post(home(*this),MinusView(x0),
482 MinusView(x1),ops)));
483
484 if (IntView::me(med) != ME_INT_DOM) {
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()) {
496 using namespace Iter::Values;
497 Positive<ViewValues<IntView> > pos(i);
498 Negative<ViewValues<IntView> > neg(j);
499 Minus m(r,neg);
500
502 Map<Positive<ViewValues<IntView> >,ValuesMapPow<Ops>,true> sp(pos,vmp);
503 Map<Minus,ValuesMapPow<Ops>,true> sm(m,vmp);
505 Map<Minus,ValuesMapPow<Ops>,true> > u(sp,sm);
506 GECODE_ME_CHECK(x1.inter_v(home,u,false));
507 } else {
511 GECODE_ME_CHECK(x1.inter_v(home,s0,false));
512 }
513
514 if (ops.even()) {
516 using namespace Iter::Values;
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 {
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
Base-class for both propagators and branchers.
Definition core.hpp:628
BinaryPropagator(Space &home, BinaryPropagator &p)
Home class for posting propagators
Definition core.hpp:856
virtual Actor * copy(Space &home)
Copy propagator during cloning.
Definition pow.hpp:216
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Definition pow.hpp:222
static ExecStatus post(Home home, IntView x0, IntView x1, Ops ops)
Post propagator.
Definition pow.hpp:149
PowBnd(Space &home, PowBnd &p)
Constructor for cloning p.
Definition pow.hpp:210
static ExecStatus post(Home home, IntView x0, IntView x1, Ops ops)
Post propagator.
Definition pow.hpp:386
virtual Actor * copy(Space &home)
Copy propagator during cloning.
Definition pow.hpp:453
PowDom(Space &home, PowDom< Ops > &p)
Constructor for cloning p.
Definition pow.hpp:447
virtual PropCost cost(const Space &home, const ModEventDelta &med) const
Cost function.
Definition pow.hpp:459
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Definition pow.hpp:470
Bounds consistent positive power propagator.
static ExecStatus post(Home home, VA x0, VB x1, Ops ops)
Post propagator.
Definition pow.hpp:83
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Definition pow.hpp:108
virtual Actor * copy(Space &home)
Copy propagator during cloning.
Definition pow.hpp:102
PowPlusBnd(Home home, VA x0, VB x1, const Ops &ops)
Constructor for posting.
Definition pow.hpp:77
Domain consistent positive power propagator.
virtual PropCost cost(const Space &home, const ModEventDelta &med) const
Cost function.
Definition pow.hpp:337
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Definition pow.hpp:348
static ExecStatus post(Home home, VA x0, VB x1, Ops ops)
Post propagator.
Definition pow.hpp:312
PowPlusDom(Home home, VA x0, VB x1, const Ops &ops)
Constructor for posting.
Definition pow.hpp:306
virtual Actor * copy(Space &home)
Copy propagator during cloning.
Definition pow.hpp:331
Mapping integer (must be an n-th power) to n-th root (signed)
Definition pow.hpp:283
ValuesMapNrootSigned(const Ops &o)
Initialize with operations o.
Definition pow.hpp:289
int val(int x) const
Perform mapping.
Definition pow.hpp:291
Mapping integer (must be an n-th power) to n-th root.
Definition pow.hpp:268
int val(int x) const
Perform mapping.
Definition pow.hpp:276
ValuesMapNroot(const Ops &o)
Initialize with operations o.
Definition pow.hpp:274
Mapping integer to power.
Definition pow.hpp:253
ValuesMapPow(const Ops &o)
Initialize with operations o.
Definition pow.hpp:259
int val(int x) const
Perform mapping.
Definition pow.hpp:261
Integer view for integer variables.
Definition view.hpp:129
int min(void) const
Return minimum of domain.
Definition int.hpp:58
ModEvent lq(Space &home, int n)
Restrict domain values to be less or equal than n.
Definition int.hpp:121
int med(void) const
Return median of domain (greatest element not greater than the median)
Definition int.hpp:66
ModEvent gq(Space &home, int n)
Restrict domain values to be greater or equal than n.
Definition int.hpp:139
int max(void) const
Return maximum of domain.
Definition int.hpp:62
Minus integer view.
Definition view.hpp:282
static ExecStatus post(Home home, View0 x0, View1 x1)
Post bounds consistent propagator .
Definition eq.hpp:108
static ExecStatus post(Home home, View0 x0, View1 x1)
Post domain consistent propagator .
Definition eq.hpp:176
Value iterator for integer views.
Definition view.hpp:94
Value iterator for mapping values of a value iterator.
MixBinaryPropagator(Space &home, MixBinaryPropagator &p)
Definition pattern.hpp:597
Propagation cost.
Definition core.hpp:486
static PropCost unary(PropCost::Mod m)
Single variable for modifier pcm.
Definition core.hpp:4820
static PropCost binary(PropCost::Mod m)
Two variables for modifier pcm.
Definition core.hpp:4816
@ HI
Expensive.
Definition core.hpp:514
friend class Space
Definition core.hpp:1068
ModEventDelta med
A set of modification events (used during propagation)
Definition core.hpp:1077
Handle to region.
Definition region.hpp:55
Propagator for ternary union
Definition rel-op.hh:154
Computation spaces.
Definition core.hpp:1744
static ModEvent me(const ModEventDelta &med)
Definition view.hpp:552
ExecStatus ES_NOFIX_PARTIAL(Propagator &p, const ModEventDelta &med)
Propagator p has not computed partial fixpoint
Definition core.hpp:3583
ExecStatus ES_SUBSUMED(Propagator &p)
Propagator p is subsumed
Definition core.hpp:3570
int ModEventDelta
Modification event deltas.
Definition core.hpp:89
#define GECODE_ME_CHECK(me)
Check whether modification event me is failed, and forward failure.
Definition macros.hpp:52
#define GECODE_REWRITE(prop, post)
Rewrite propagator by executing post function.
Definition macros.hpp:116
bool me_failed(ModEvent me)
Check whether modification event me is failed.
Definition modevent.hpp:54
#define GECODE_ES_CHECK(es)
Check whether execution status es is failed or subsumed, and forward failure or subsumption.
Definition macros.hpp:91
bool me_modified(ModEvent me)
Check whether modification event me describes variable modification.
Definition modevent.hpp:59
Numerical (arithmetic) propagators.
bool pos(const View &x)
Test whether x is postive.
Definition mult.hpp:70
ExecStatus prop_pow_plus_bnd(Space &home, VA x0, VB x1, const Ops &ops)
Definition pow.hpp:47
ExecStatus prop_pow_bnd(Space &home, IntView x0, IntView x1, const Ops &ops)
Definition pow.hpp:122
bool neg(const View &x)
Test whether x is negative.
Definition mult.hpp:76
const int min
Smallest allowed integer value.
Definition int.hh:118
const int max
Largest allowed integer value.
Definition int.hh:116
Finite domain integers.
const Gecode::PropCond PC_INT_BND
Propagate when minimum or maximum of a view changes.
Definition var-type.hpp:91
const Gecode::PropCond PC_INT_DOM
Propagate when domain changes.
Definition var-type.hpp:100
const Gecode::ModEvent ME_INT_VAL
Domain operation has resulted in a value (assigned variable)
Definition var-type.hpp:56
const Gecode::ModEvent ME_INT_DOM
Domain operation has changed the domain.
Definition var-type.hpp:72
Value iterators.
Definition iter.hh:45
Gecode toplevel namespace
Post propagator for SetVar SetOpType SetVar SetRelType r
Definition set.hh:773
void mod(Home home, IntVar x0, IntVar x1, IntVar x2, IntPropLevel ipl=IPL_DEF)
Post propagator for .
ExecStatus
Definition core.hpp:472
@ ES_OK
Execution is okay.
Definition core.hpp:476
@ ES_FIX
Propagation has computed fixpoint.
Definition core.hpp:477
@ ES_FAILED
Execution has resulted in failure.
Definition core.hpp:474
@ ES_NOFIX
Propagation has not computed fixpoint.
Definition core.hpp:475
Post propagator for SetVar x
Definition set.hh:773
int ModEvent
Type for modification events.
Definition core.hpp:62
#define forceinline
Definition config.hpp:194