Generated on for Gecode by doxygen 1.17.0
product.hpp
Go to the documentation of this file.
1/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2/*
3 * Main authors:
4 * Mikael Zayenz Lagerkvist <lagerkvist@gecode.dev>
5 *
6 * Copyright:
7 * Mikael Zayenz Lagerkvist, 2026
8 *
9 * This file is part of Gecode, the generic constraint
10 * development environment:
11 * http://www.gecode.dev
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#include <algorithm>
34
35namespace Gecode { namespace Int { namespace Arithmetic {
36
39 int min;
40 int max;
41 };
42
45 product_interval_mul(ProductInterval a, int bmin, int bmax) {
46 long long int p[4] = {
47 static_cast<long long int>(a.min) * bmin,
48 static_cast<long long int>(a.min) * bmax,
49 static_cast<long long int>(a.max) * bmin,
50 static_cast<long long int>(a.max) * bmax
51 };
52 long long int l = *std::min_element(p,p+4);
53 long long int u = *std::max_element(p,p+4);
54 l = std::max(static_cast<long long int>(Limits::min),
55 std::min(l,static_cast<long long int>(Limits::max)));
56 u = std::max(static_cast<long long int>(Limits::min),
57 std::min(u,static_cast<long long int>(Limits::max)));
58 ProductInterval r = {static_cast<int>(l),static_cast<int>(u)};
59 return r;
60 }
61
63 forceinline ProductInterval
67
69 forceinline int
70 product_power_abs(int x, int n) {
71 const long long int a = x < 0 ? -static_cast<long long int>(x) : x;
72 long long int p=1;
73 for (int i=0; i<n; i++) {
74 if ((a != 0) && (p > static_cast<long long int>(Limits::max)/a))
75 return Limits::max;
76 p *= a;
77 }
78 return static_cast<int>(p);
79 }
80
82 forceinline ProductInterval
84 const int l=product_power_abs(x.min(),n);
85 const int u=product_power_abs(x.max(),n);
86 if ((n & 1) != 0) {
87 ProductInterval p = {x.min() < 0 ? -l : l,
88 x.max() < 0 ? -u : u};
89 return p;
90 }
91 ProductInterval p = {
92 ((x.min() <= 0) && (x.max() >= 0)) ? 0 : std::min(l,u),
93 std::max(l,u)
94 };
95 return p;
96 }
97
98 forceinline bool
99 product_power_le(int x, int n, int limit) {
100 long long int p=1;
101 for (int i=0; i<n; i++) {
102 if ((x != 0) && (p > static_cast<long long int>(limit)/x))
103 return false;
104 p *= x;
105 }
106 return true;
107 }
108
110 inline int
111 product_floor_root(int x, int n) {
112 int l=0;
113 int u=x;
114 while (l < u) {
115 const int m=l+(u-l+1)/2;
116 if (product_power_le(m,n,x)) l=m; else u=m-1;
117 }
118 return l;
119 }
120
121 forceinline int
122 product_ceil_root(int x, int n) {
123 if (x <= 0) return 0;
124 return product_floor_root(x-1,n)+1;
125 }
126
129 long long int min;
130 long long int max;
131 };
132
135 product_quotient_bounds(long long int ymin, long long int ymax,
136 int qmin, int qmax) {
137 long long int c[4] = {
138 ceil_div_xx(ymin,static_cast<long long int>(qmin)),
139 ceil_div_xx(ymin,static_cast<long long int>(qmax)),
140 ceil_div_xx(ymax,static_cast<long long int>(qmin)),
141 ceil_div_xx(ymax,static_cast<long long int>(qmax))
142 };
143 long long int f[4] = {
144 floor_div_xx(ymin,static_cast<long long int>(qmin)),
145 floor_div_xx(ymin,static_cast<long long int>(qmax)),
146 floor_div_xx(ymax,static_cast<long long int>(qmin)),
147 floor_div_xx(ymax,static_cast<long long int>(qmax))
148 };
150 *std::min_element(c,c+4), *std::max_element(f,f+4)
151 };
152 return r;
153 }
154
156 forceinline ProductInterval
157 product_quotient_interval(int ymin, int ymax, int qmin, int qmax) {
158 const ProductWideInterval q=product_quotient_bounds(ymin,ymax,qmin,qmax);
159 const long long int l = std::max
160 (static_cast<long long int>(Limits::min),std::min
161 (q.min,static_cast<long long int>(Limits::max)));
162 const long long int u = std::max
163 (static_cast<long long int>(Limits::min),std::min
164 (q.max,static_cast<long long int>(Limits::max)));
165 ProductInterval r = {static_cast<int>(l),static_cast<int>(u)};
166 return r;
167 }
168
170 forceinline ProductInterval
172 ProductInterval d = {1,0};
173 if (q.min < 0)
174 d=product_quotient_interval(y.min,y.max,q.min,std::min(q.max,-1));
175 if (q.max > 0) {
177 (y.min,y.max,std::max(q.min,1),q.max);
178 if (q.min < 0) {
179 d.min=std::min(d.min,p.min); d.max=std::max(d.max,p.max);
180 } else {
181 d=p;
182 }
183 }
184 return d;
185 }
186
188 inline ProductInterval
190 if (n == 1)
191 return d;
192 if ((n & 1) != 0) {
193 ProductInterval r = {
194 d.min < 0 ? -product_floor_root(-d.min,n) :
196 d.max < 0 ? -product_ceil_root(-d.max,n) :
198 };
199 return r;
200 }
201 if (d.max < 0)
202 return ProductInterval{1,0};
203 const int lo=product_ceil_root(std::max(d.min,0),n);
204 const int hi=product_floor_root(d.max,n);
205 if (lo > hi)
206 return ProductInterval{1,0};
207 const ProductInterval negative = {
208 std::max(x.min,-hi), std::min(x.max,-lo)
209 };
210 const ProductInterval positive = {
211 std::max(x.min,lo), std::min(x.max,hi)
212 };
213 if (negative.min > negative.max)
214 return positive;
215 if (positive.min > positive.max)
216 return negative;
217 return ProductInterval{negative.min,positive.max};
218 }
219
221 inline ProductInterval
222 product_interval(const ViewArray<IntView>& x, int omit=-1) {
223 ProductInterval r = {1,1};
224 // Equal views are adjacent after posting and remain adjacent in clones.
225 for (int i=0; i<x.size();) {
226 int j=i+1;
227 while ((j < x.size()) && (x[j] == x[i])) j++;
228 const int n=j-i-((omit >= i) && (omit < j) ? 1 : 0);
229 if (n > 0)
231 i=j;
232 }
233 return r;
234 }
235
237 inline bool
238 product_value(const int* v, int n, int& p) {
239 for (int i=0; i<n; i++)
240 if (v[i] == 0) {
241 p = 0;
242 return true;
243 }
244 long long int q = 1;
245 for (int i=0; i<n; i++) {
246 if (Limits::overflow_mul(q,static_cast<long long int>(v[i])))
247 return false;
248 q *= static_cast<long long int>(v[i]);
249 }
250 if (!Limits::valid(q))
251 return false;
252 p = static_cast<int>(q);
253 return true;
254 }
255
257 inline RelTest
259 if ((x.size() == 1) && (x[0] == y))
260 return RT_TRUE;
261 for (int i=0; i<x.size(); i++)
262 if (x[i].assigned() && (x[i].val() == 0)) {
263 if (!y.in(0)) return RT_FALSE;
264 return y.assigned() ? RT_TRUE : RT_MAYBE;
265 }
267 if ((p.max < y.min()) || (p.min > y.max()))
268 return RT_FALSE;
269 bool assigned = true;
270 for (int i=0; assigned && (i<x.size()); i++)
271 assigned = x[i].assigned();
272 if (!assigned)
273 return RT_MAYBE;
274 Region r;
275 int* v = r.alloc<int>(x.size());
276 for (int i=0; i<x.size(); i++) v[i] = x[i].val();
277 int q;
278 if (!product_value(v,x.size(),q) || !y.in(q))
279 return RT_FALSE;
280 return y.assigned() ? RT_TRUE : RT_MAYBE;
281 }
282
285 : NaryOnePropagator<IntView,PC_INT_BND>(home,z,w), neg(n) {
286 home.notice(*this,AP_WEAKLY);
287 }
288
289 inline ExecStatus
291 for (int i=x.size(); i--;) {
292 if (!x[i].assigned())
293 continue;
294 if (x[i].val() == 0) {
295 GECODE_ME_CHECK(y.eq(home,0));
296 return ES_OK;
297 }
298 if ((x[i].val() == 1) || (x[i].val() == -1)) {
299 neg ^= x[i].val() == -1;
300 x.move_lst(i);
301 }
302 }
303 if (x.size() == 0) {
304 GECODE_ME_CHECK(y.eq(home,neg ? -1 : 1));
305 return ES_OK;
306 }
307 if (x.size() == 1) {
308 if (neg)
310 return Rel::EqBnd<IntView,IntView>::post(home,x[0],y);
311 }
312 // Keep zero-aware inverse bounds when both intervals contain zero;
313 // binary multiplication does less pruning in that case.
314 if ((x.size() == 2) && !neg &&
315 ((x[0] == x[1]) || (x[0].min() > 0) || (x[0].max() < 0) ||
316 (x[1].min() > 0) || (x[1].max() < 0)))
317 return MultBnd::post(home,x[0],x[1],y);
318 Support::quicksort(&x[0],x.size());
319 (void) new (home) Product(home,x,y,neg);
320 return ES_OK;
321 }
322
326
329 return new (home) Product(home,*this);
330 }
331
333 Product::cost(const Space&, const ModEventDelta&) const {
334 return PropCost::linear(PropCost::HI,x.size()+1);
335 }
336
337 forceinline size_t
339 home.ignore(*this,AP_WEAKLY);
341 return sizeof(*this);
342 }
343
344 inline ExecStatus
346 // Preserve adjacent equal views while removing assigned units in place.
347 int n=0;
348 bool zero=false;
349 for (int i=0; i<x.size(); i++) {
350 if (x[i].assigned()) {
351 if (x[i].val() == 0) {
352 zero=true;
353 continue;
354 }
355 if ((x[i].val() == 1) || (x[i].val() == -1)) {
356 neg ^= x[i].val() == -1;
357 continue;
358 }
359 }
360 x[n++]=x[i];
361 }
362 if (n < x.size()) {
363 x.size(n);
364 if (zero) {
365 GECODE_ME_CHECK(y.eq(home,0));
366 return home.ES_SUBSUMED(*this);
367 }
368 if (n <= 2)
369 GECODE_REWRITE(*this,Product::post(home(*this),x,y,neg));
370 }
371
372 // Cancel one result occurrence when it is nonzero. If cancellation is
373 // not yet possible, a remaining product that cannot be the required unit
374 // makes zero the only solution for the result.
375 int alias=-1;
376 for (int i=0; i<x.size(); i++)
377 if (x[i] == y) { alias=i; break; }
378 if (alias >= 0) {
379 if (y.assigned() && (y.val() == 0))
380 return home.ES_SUBSUMED(*this);
381 const int unit=neg ? -1 : 1;
382 if (!y.in(0)) {
383 ViewArray<IntView> z(home,x.size()-1);
384 int j=0;
385 for (int i=0; i<x.size(); i++)
386 if (i != alias) z[j++]=x[i];
387 IntVar u(home,unit,unit);
388 GECODE_REWRITE(*this,Product::post(home(*this),z,IntView(u)));
389 }
391 if ((unit < q.min) || (unit > q.max)) {
392 GECODE_ME_CHECK(y.eq(home,0));
393 return home.ES_SUBSUMED(*this);
394 }
395 }
396
397 // A nonzero result excludes a bounds-visible zero endpoint.
398 if (!y.in(0))
399 for (int i=0; i<x.size(); i++) {
400 if ((x[i].min() == 0) && (x[i].max() > 0))
401 GECODE_ME_CHECK(x[i].gq(home,1));
402 else if ((x[i].max() == 0) && (x[i].min() < 0))
403 GECODE_ME_CHECK(x[i].lq(home,-1));
404 }
405
406 // Zero can only arise from a zero factor.
407 if (y.assigned() && (y.val() == 0)) {
408 int zero=-1;
409 for (int i=0; i<x.size(); i++)
410 if (x[i].in(0)) {
411 if (zero >= 0) { zero=-2; break; }
412 zero=i;
413 }
414 if (zero == -1)
415 return ES_FAILED;
416 if (zero >= 0) {
417 GECODE_ME_CHECK(x[zero].eq(home,0));
418 return home.ES_SUBSUMED(*this);
419 }
420 }
421
422 // Stable one-sided signs determine aggregate parity and zero possibility.
423 bool stable=true;
424 bool strict=true;
425 bool negative=neg;
426 for (int i=0; i<x.size(); i++) {
427 if (x[i].max() <= 0) {
428 negative=!negative;
429 strict &= x[i].max() < 0;
430 } else if (x[i].min() >= 0) {
431 strict &= x[i].min() > 0;
432 } else {
433 stable=false; strict=false; break;
434 }
435 }
436 if (stable) {
437 if (negative)
438 GECODE_ME_CHECK(y.lq(home,strict ? -1 : 0));
439 else
440 GECODE_ME_CHECK(y.gq(home,strict ? 1 : 0));
441 }
442
443 // View identities do not change during propagation. Group once, then
444 // reuse the powers for forward and inverse bounds in each iteration.
445 Region r;
446 int* representative=r.alloc<int>(x.size());
447 int* exponent=r.alloc<int>(x.size());
448 int groups=0;
449 for (int i=0; i<x.size(); i++) {
450 if ((i == 0) || (x[i-1] != x[i])) {
451 representative[groups]=i; exponent[groups]=1; groups++;
452 } else {
453 exponent[groups-1]++;
454 }
455 }
456 ProductInterval* power=r.alloc<ProductInterval>(groups);
457 ProductInterval* prefix=r.alloc<ProductInterval>(groups+1);
458 ProductInterval* suffix=r.alloc<ProductInterval>(groups+1);
459 bool modified;
460 do {
461 modified = false;
462 prefix[0] = ProductInterval{1,1};
463 for (int g=0; g<groups; g++) {
464 power[g]=product_power_interval(x[representative[g]],exponent[g]);
465 prefix[g+1]=product_interval_mul(prefix[g],power[g]);
466 }
467 const ProductInterval p=prefix[groups];
468 {
469 ModEvent me = neg ? y.lq(home,-p.min) : y.gq(home,p.min);
470 if (me_failed(me)) return ES_FAILED;
471 modified |= me_modified(me);
472 }
473 {
474 ModEvent me = neg ? y.gq(home,-p.max) : y.lq(home,p.max);
475 if (me_failed(me)) return ES_FAILED;
476 modified |= me_modified(me);
477 }
478 suffix[groups] = ProductInterval{1,1};
479 for (int g=groups; g--;)
480 suffix[g]=product_interval_mul(suffix[g+1],power[g]);
481
482 for (int g=0; g<groups; g++) {
483 IntView xi=x[representative[g]];
484 ProductInterval q=product_interval_mul(prefix[g],suffix[g+1]);
485 if ((q.min <= 0) && (q.max >= 0) && y.in(0))
486 continue;
487 if ((q.min == 0) && (q.max == 0))
488 return ES_FAILED;
489
490 const ProductInterval result = {
491 neg ? -y.max() : y.min(), neg ? -y.min() : y.max()
492 };
493 const ProductInterval d=product_quotient_hull(result,q);
494 if (d.min > d.max)
495 return ES_FAILED;
496 const ProductInterval bounds={xi.min(),xi.max()};
497 const ProductInterval roots=product_root_interval(bounds,exponent[g],d);
498 if (roots.min > roots.max)
499 return ES_FAILED;
500 ModEvent me=xi.gq(home,roots.min);
501 if (me_failed(me)) return ES_FAILED;
502 modified |= me_modified(me);
503 me=xi.lq(home,roots.max);
504 if (me_failed(me)) return ES_FAILED;
505 modified |= me_modified(me);
506 }
507 } while (modified);
508
509 // Result propagation above can have excluded zero during this call.
510 bool endpoint_modified=false;
511 if (!y.in(0))
512 for (int i=0; i<x.size(); i++) {
514 if ((x[i].min() == 0) && (x[i].max() > 0))
515 me=x[i].gq(home,1);
516 else if ((x[i].max() == 0) && (x[i].min() < 0))
517 me=x[i].lq(home,-1);
518 if (me_failed(me)) return ES_FAILED;
519 endpoint_modified |= me_modified(me);
520 }
521 if (endpoint_modified)
522 return ES_NOFIX;
523
524 bool factors_assigned = true;
525 for (int i=0; factors_assigned && (i<x.size()); i++)
526 factors_assigned = x[i].assigned();
527 if (factors_assigned) {
528 Region r;
529 int* v = r.alloc<int>(x.size());
530 for (int i=0; i<x.size(); i++) v[i] = x[i].val();
531 int p;
532 if (!product_value(v,x.size(),p))
533 return ES_FAILED;
534 GECODE_ME_CHECK(y.eq(home,neg ? -p : p));
535 return home.ES_SUBSUMED(*this);
536 }
537 return ES_FIX;
538 }
539
540 template<ReifyMode rm>
543 BoolView c)
544 : Propagator(home), x(z), y(w), b(c) {
545 home.notice(*this,AP_WEAKLY);
546 x.subscribe(home,*this,PC_INT_BND);
547 y.subscribe(home,*this,PC_INT_BND);
548 b.subscribe(home,*this,PC_BOOL_VAL);
549 }
550
551 template<ReifyMode rm>
552 inline ExecStatus
554 if (b.one() && (rm == RM_PMI)) return ES_OK;
555 if (b.zero() && (rm == RM_IMP)) return ES_OK;
556 if (x.size() == 0)
558 if (x.size() == 1)
560 Support::quicksort(&x[0],x.size());
561 (void) new (home) ReProduct<rm>(home,x,y,b);
562 return ES_OK;
563 }
564
565 template<ReifyMode rm>
568 : Propagator(home,p) {
569 x.update(home,p.x); y.update(home,p.y); b.update(home,p.b);
570 }
571
572 template<ReifyMode rm>
575 return new (home) ReProduct<rm>(home,*this);
576 }
577
578 template<ReifyMode rm>
581 return PropCost::linear(PropCost::HI,x.size()+2);
582 }
583
584 template<ReifyMode rm>
585 forceinline void
587 x.reschedule(home,*this,PC_INT_BND);
588 y.reschedule(home,*this,PC_INT_BND);
589 b.reschedule(home,*this,PC_BOOL_VAL);
590 }
591
592 template<ReifyMode rm>
593 inline ExecStatus
595 if (b.one()) {
596 if (rm == RM_PMI) return home.ES_SUBSUMED(*this);
597 GECODE_REWRITE(*this,Product::post(home(*this),x,y));
598 }
599 if (b.zero()) {
600 if (rm == RM_IMP) return home.ES_SUBSUMED(*this);
601 switch (product_status(x,y)) {
602 case RT_TRUE: return ES_FAILED;
603 case RT_FALSE: return home.ES_SUBSUMED(*this);
604 case RT_MAYBE: return ES_FIX;
605 default: GECODE_NEVER;
606 }
607 }
608 switch (product_status(x,y)) {
609 case RT_TRUE:
610 if (rm != RM_IMP) GECODE_ME_CHECK(b.one_none(home));
611 return home.ES_SUBSUMED(*this);
612 case RT_FALSE:
613 if (rm != RM_PMI) GECODE_ME_CHECK(b.zero_none(home));
614 return home.ES_SUBSUMED(*this);
615 case RT_MAYBE:
616 return ES_FIX;
617 default: GECODE_NEVER;
618 }
619 }
620
621 template<ReifyMode rm>
622 forceinline size_t
624 x.cancel(home,*this,PC_INT_BND);
625 y.cancel(home,*this,PC_INT_BND);
626 b.cancel(home,*this,PC_BOOL_VAL);
627 home.ignore(*this,AP_WEAKLY);
628 (void) Propagator::dispose(home);
629 return sizeof(*this);
630 }
631
632}}}
633
634// STATISTICS: int-prop
Base-class for both propagators and branchers.
Definition core.hpp:635
virtual size_t dispose(Space &home)
Delete actor and return its size.
Definition core.hpp:3430
friend FloatVal max(const FloatVal &x, const FloatVal &y)
Definition val.hpp:387
friend FloatVal min(const FloatVal &x, const FloatVal &y)
Definition val.hpp:399
Home class for posting propagators
Definition core.hpp:863
void notice(Actor &a, ActorProperty p, bool duplicate=false)
Notice actor property.
Definition core.hpp:3373
int min(int i) const
Return minimum of range at position i.
int max(int i) const
Return maximum of range at position i.
Integer variables.
Definition int.hh:390
static ExecStatus post(Home home, IntView x0, IntView x1, IntView x2)
Post propagator .
Definition mult.cpp:144
bool neg
Whether the remaining product is negated.
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Definition product.hpp:345
virtual Actor * copy(Space &home)
Copy propagator during cloning.
Definition product.hpp:328
Product(Home home, ViewArray< IntView > &x, IntView y, bool neg)
Constructor for posting.
Definition product.hpp:284
virtual PropCost cost(const Space &home, const ModEventDelta &med) const
Cost function.
Definition product.hpp:333
virtual size_t dispose(Space &home)
Delete propagator and return its size.
Definition product.hpp:338
static ExecStatus post(Home home, ViewArray< IntView > &x, IntView y, bool neg=false)
Post propagator.
Definition product.hpp:290
virtual Actor * copy(Space &home)
Copy propagator during cloning.
Definition product.hpp:574
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Definition product.hpp:594
virtual size_t dispose(Space &home)
Delete propagator and return its size.
Definition product.hpp:623
BoolView b
Reification control.
virtual void reschedule(Space &home)
Reschedule propagator.
Definition product.hpp:586
virtual PropCost cost(const Space &home, const ModEventDelta &med) const
Cost function.
Definition product.hpp:580
static ExecStatus post(Home home, ViewArray< IntView > &x, IntView y, BoolView b)
Post propagator.
Definition product.hpp:553
ReProduct(Home home, ViewArray< IntView > &x, IntView y, BoolView b)
Constructor for posting.
Definition product.hpp:542
ViewArray< IntView > x
Factors.
Boolean view for Boolean variables.
Definition view.hpp:1378
Integer view for integer variables.
Definition view.hpp:129
int min(void) const
Return minimum of domain.
Definition int.hpp:58
bool in(int n) const
Test whether n is contained in domain.
Definition int.hpp:107
ModEvent lq(Space &home, int n)
Restrict domain values to be less or equal than n.
Definition int.hpp:121
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, View x0, View x1, CtrlView b)
Post bounds consistent propagator .
Definition eq.hpp:568
static ExecStatus post(Home home, View x, int c, CtrlView b)
Post domain consistent propagator .
Definition eq.hpp:644
NaryOnePropagator(Space &home, NaryOnePropagator &p)
virtual size_t dispose(Space &home)
Delete propagator and return its size.
Definition pattern.hpp:570
Propagation cost.
Definition core.hpp:493
static PropCost linear(PropCost::Mod m, unsigned int n)
Linear complexity for modifier pcm and size measure n.
Definition core.hpp:5080
@ HI
Expensive.
Definition core.hpp:521
friend class Space
Definition core.hpp:1075
Propagator(Home home)
Constructor for posting.
Definition core.hpp:3707
Handle to region.
Definition region.hpp:55
bool assigned(void) const
Test whether view is assigned.
Definition view.hpp:516
View arrays.
Definition array.hpp:255
int size(void) const
Return size of array (number of elements).
Definition array.hpp:1165
ExecStatus ES_SUBSUMED(Propagator &p)
Propagator p is subsumed
Definition core.hpp:3780
void ignore(Actor &a, ActorProperty p, bool duplicate=false)
Ignore actor property.
Definition core.hpp:4321
int ModEventDelta
Modification event deltas.
Definition core.hpp:94
#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
bool me_modified(ModEvent me)
Check whether modification event me describes variable modification.
Definition modevent.hpp:59
@ AP_WEAKLY
Definition core.hpp:575
@ RM_IMP
Implication for reification.
Definition int.hh:1162
@ RM_PMI
Inverse implication for reification.
Definition int.hh:1169
Numerical (arithmetic) propagators.
bool product_power_le(int x, int n, int limit)
Definition product.hpp:99
int product_ceil_root(int x, int n)
Definition product.hpp:122
RelTest product_status(const ViewArray< IntView > &x, const IntView &y)
Determine the relation when bounds or assignments prove it.
Definition product.hpp:258
ProductInterval product_root_interval(ProductInterval x, int n, ProductInterval d)
Invert integer power bounds; min greater than max denotes no support.
Definition product.hpp:189
ProductInterval product_interval_mul(ProductInterval a, int bmin, int bmax)
Multiply two representable intervals, clipping out-of-range endpoints.
Definition product.hpp:45
int product_floor_root(int x, int n)
Floor and ceiling of a nonnegative integer root.
Definition product.hpp:111
ProductInterval product_interval(const ViewArray< IntView > &x, int omit=-1)
Compute product bounds, optionally omitting one factor.
Definition product.hpp:222
ProductInterval product_quotient_hull(ProductInterval y, ProductInterval q)
Hull of quotients by the nonzero parts of a cofactor interval.
Definition product.hpp:171
int product_power_abs(int x, int n)
Compute a nonnegative power, saturating at the integer limit.
Definition product.hpp:70
ProductWideInterval product_quotient_bounds(long long int ymin, long long int ymax, int qmin, int qmax)
Quotient bounds for a zero-free divisor, before clipping the endpoints.
Definition product.hpp:135
ProductInterval product_quotient_interval(int ymin, int ymax, int qmin, int qmax)
Compute a saturated hull of quotients by a zero-free interval.
Definition product.hpp:157
ProductInterval product_power_interval(IntView x, int n)
Bounds for a repeated occurrence viewed as an integer power.
Definition product.hpp:83
bool product_value(const int *v, int n, int &p)
Evaluate a tuple without overflowing internal arithmetic.
Definition product.hpp:238
bool overflow_mul(int n, int m)
Check whether multiplying n and m would overflow.
Definition limits.hpp:107
const int min
Smallest allowed integer value.
Definition int.hh:123
bool valid(int n)
Return whether n is in range.
Definition limits.hpp:37
const int max
Largest allowed integer value.
Definition int.hh:121
Finite domain integers.
Definition lastval.hh:52
const Gecode::PropCond PC_INT_BND
Propagate when minimum or maximum of a view changes.
Definition var-type.hpp:99
const Gecode::PropCond PC_BOOL_VAL
Propagate when a view becomes assigned (single value).
Definition var-type.hpp:134
IntType floor_div_xx(IntType x, IntType y)
Compute .
Definition div.hpp:87
IntType ceil_div_xx(IntType x, IntType y)
Compute .
Definition div.hpp:82
RelTest
Result of testing relation.
Definition view.hpp:1732
@ RT_TRUE
Relation does hold.
Definition view.hpp:1735
@ RT_MAYBE
Relation may hold or not.
Definition view.hpp:1734
@ RT_FALSE
Relation does not hold.
Definition view.hpp:1733
const Gecode::ModEvent ME_INT_NONE
Domain operation has not changed domain.
Definition var-type.hpp:62
void quicksort(Type *l, Type *r, Less &less)
Standard quick sort.
Definition sort.hpp:130
Gecode toplevel namespace
void min(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
void roots(Home home, const IntVarArgs &x, SetVar y, SetVar z)
Post constraint .
Definition aliases.hpp:163
ExecStatus
Definition core.hpp:479
@ ES_OK
Execution is okay.
Definition core.hpp:483
@ ES_FIX
Propagation has computed fixpoint.
Definition core.hpp:484
@ ES_FAILED
Execution has resulted in failure.
Definition core.hpp:481
@ ES_NOFIX
Propagation has not computed fixpoint.
Definition core.hpp:482
void max(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
int ModEvent
Type for modification events.
Definition core.hpp:67
A representable, conservative interval for an exact product.
Definition product.hpp:38
An interval whose endpoints have not been restricted to integer limits.
Definition product.hpp:128
#define forceinline
Definition config.hpp:144
#define GECODE_NEVER
Assert that this command is never executed.
Definition macros.hpp:56