Generated on for Gecode by doxygen 1.18.0
product-mod.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
38 inline bool
40 ProductInterval& p) {
41 long long int q[4] = {
42 static_cast<long long int>(a.min)*b.min,
43 static_cast<long long int>(a.min)*b.max,
44 static_cast<long long int>(a.max)*b.min,
45 static_cast<long long int>(a.max)*b.max
46 };
47 const long long int l=*std::min_element(q,q+4);
48 const long long int u=*std::max_element(q,q+4);
49 if (!Limits::valid(l) || !Limits::valid(u))
50 return false;
51 p.min=static_cast<int>(l); p.max=static_cast<int>(u);
52 return true;
53 }
54
56 inline bool
58 int a=1) {
59 p.min=a; p.max=a;
60 for (int i=0; i<x.size(); i++) {
61 ProductInterval q={x[i].min(),x[i].max()};
62 if (!product_mod_interval_mul(p,q,p))
63 return false;
64 }
65 return true;
66 }
67
69 inline bool
71 ProductInterval* prefix, ProductInterval* suffix,
72 int a=1) {
73 prefix[0]=ProductInterval{a,a};
74 suffix[x.size()]=ProductInterval{1,1};
75 for (int i=0; i<x.size(); i++) {
76 ProductInterval q={x[i].min(),x[i].max()};
77 if (!product_mod_interval_mul(prefix[i],q,prefix[i+1]))
78 return false;
79 }
80 for (int i=x.size(); i--;) {
81 ProductInterval q={x[i].min(),x[i].max()};
82 if (!product_mod_interval_mul(q,suffix[i+1],suffix[i]))
83 return false;
84 }
85 return true;
86 }
87
89 inline int
91 int& free_count) {
92 long long int p=1 % m;
93 free_count=0;
94 for (int i=0; i<x.size(); i++) {
95 if (!x[i].assigned()) {
96 free_count++;
97 } else {
98 long long int q=static_cast<long long int>(x[i].val()) % m;
99 if (q < 0) q+=m;
100 p=(p*q) % m;
101 }
102 }
103 return static_cast<int>(p);
104 }
105
107 inline void
108 product_mod_fold(ViewArray<IntView>& x, int m, int& c, int& a) {
109 for (int i=x.size(); i--;)
110 if (x[i].assigned()) {
111 const int v=x[i].val();
112 c=static_cast<int>((static_cast<long long int>(c)*v) % m);
113 if (c < 0) c+=m;
114 const long long int p=static_cast<long long int>(a)*v;
115 // Zero marks an unavailable exact coefficient; c remains exact modulo m.
116 a=Limits::valid(p) ? static_cast<int>(p) : 0;
117 x.move_lst(i);
118 }
119 }
120
122 inline void
124 for (int i=x.size(); i--;)
125 if (x[i].assigned() && (x[i].val() == 1))
126 x.move_lst(i);
127 }
128
130 inline ExecStatus
131 product_mod_nonzero(Space& home, ViewArray<IntView>& x, bool& modified) {
132 for (int i=0; i<x.size(); i++) {
134 if (x[i].min() == 0)
135 me=x[i].gq(home,1);
136 else if (x[i].max() == 0)
137 me=x[i].lq(home,-1);
138 if (me_failed(me)) return ES_FAILED;
139 modified |= me_modified(me);
140 }
141 return ES_OK;
142 }
143
145 inline RelTest
146 product_mod_status(const ViewArray<IntView>& x, const IntView& y, int m) {
147 if ((y.max() < 0) || (y.min() >= m))
148 return RT_FALSE;
149 int free_count;
150 const int c=product_mod_coefficient(x,m,free_count);
151 if ((c == 0) || (free_count == 0)) {
152 if (!y.in(c)) return RT_FALSE;
153 return y.assigned() ? RT_TRUE : RT_MAYBE;
154 }
155 const int g=gcd_value(c,m);
156 const long long int l=ceil_div_xx
157 (static_cast<long long int>(std::max(0,y.min())),
158 static_cast<long long int>(g))*g;
159 if (l > std::min(m-1,y.max()))
160 return RT_FALSE;
162 if (product_mod_interval(x,p)) {
163 const long long int kl = floor_div_xx
164 (static_cast<long long int>(p.min),static_cast<long long int>(m));
165 const long long int ku = floor_div_xx
166 (static_cast<long long int>(p.max),static_cast<long long int>(m));
167 if (kl == ku) {
168 const long long int shift=kl*m;
169 if ((static_cast<long long int>(p.max)-shift < y.min()) ||
170 (static_cast<long long int>(p.min)-shift > y.max()))
171 return RT_FALSE;
172 }
173 }
174 return RT_MAYBE;
175 }
176
178 inline long long int
179 product_mod_inverse(long long int a, long long int m) {
180 long long int old_r=a;
181 long long int r=m;
182 long long int old_s=1;
183 long long int s=0;
184 while (r != 0) {
185 const long long int q=old_r/r;
186 const long long int nr=old_r-q*r; old_r=r; r=nr;
187 const long long int ns=old_s-q*s; old_s=s; s=ns;
188 }
189 old_s %= m;
190 return old_s < 0 ? old_s+m : old_s;
191 }
192
194 inline ProductInterval
195 product_mod_congruence(ProductInterval x, int c, int m, int y) {
196 const int g=gcd_value(c,m);
197 if ((y % g) != 0)
198 return ProductInterval{1,0};
199 const long long int step=m/g;
200 long long int r=0;
201 if (step > 1) {
202 const long long int a=c/g;
203 const long long int b=y/g;
204 r=(product_mod_inverse(a % step,step)*b) % step;
205 if (r < 0) r+=step;
206 }
207 const long long int l=r + ceil_div_xx
208 (static_cast<long long int>(x.min)-r,step)*step;
209 const long long int u=r + floor_div_xx
210 (static_cast<long long int>(x.max)-r,step)*step;
211 if (l > u)
212 return ProductInterval{1,0};
213 // Nonempty bounds lie inside x, so narrowing to int is safe.
214 return ProductInterval{static_cast<int>(l),static_cast<int>(u)};
215 }
216
217 forceinline
219 IntView w, int c0, int a0)
221 m(modulus), c(c0), a(a0) {}
222
223 inline ExecStatus
225 GECODE_ME_CHECK(y.gq(home,0));
226 GECODE_ME_CHECK(y.lq(home,m-1));
227 if (m == 1) {
228 GECODE_ME_CHECK(y.eq(home,0));
229 return ES_OK;
230 }
231 if (x.size() == 0) {
232 GECODE_ME_CHECK(y.eq(home,1 % m));
233 return ES_OK;
234 }
235 int c=1;
236 int a=1;
238 if ((c == 0) || (x.size() == 0)) {
239 GECODE_ME_CHECK(y.eq(home,c));
240 return ES_OK;
241 }
242 (void) new (home) ProductMod(home,x,m,y,c,a);
243 return ES_OK;
244 }
245
246 forceinline
249 m(p.m), c(p.c), a(p.a) {}
250
251 forceinline Actor*
253 return new (home) ProductMod(home,*this);
254 }
255
256 forceinline PropCost
257 ProductMod::cost(const Space&, const ModEventDelta&) const {
259 }
260
261 forceinline size_t
264 return sizeof(*this);
265 }
266
267 inline ExecStatus
269 GECODE_ME_CHECK(y.gq(home,0));
270 GECODE_ME_CHECK(y.lq(home,m-1));
271
272 Region region;
273 ProductInterval* prefix=NULL;
274 ProductInterval* suffix=NULL;
275 bool modified;
276 do {
277 modified=false;
279 if ((c == 0) || (x.size() == 0)) {
280 GECODE_ME_CHECK(y.eq(home,c));
281 return home.ES_SUBSUMED(*this);
282 }
283 const unsigned int old_size=y.size();
285 modified |= old_size != y.size();
286 if (y.min() > 0)
287 GECODE_ES_CHECK(product_mod_nonzero(home,x,modified));
288
289 // One remaining occurrence gives a linear congruence.
290 if ((x.size() == 1) && y.assigned()) {
291 const ProductInterval bounds={x[0].min(),x[0].max()};
292 const ProductInterval solutions=
293 product_mod_congruence(bounds,c,m,y.val());
294 if (solutions.min > solutions.max)
295 return ES_FAILED;
296 ModEvent me=x[0].gq(home,solutions.min);
297 if (me_failed(me)) return ES_FAILED;
298 modified |= me_modified(me);
299 me=x[0].lq(home,solutions.max);
300 if (me_failed(me)) return ES_FAILED;
301 modified |= me_modified(me);
302 }
304 if ((a != 0) && product_mod_interval(x,p,a)) {
305 const long long int kl = floor_div_xx
306 (static_cast<long long int>(p.min),static_cast<long long int>(m));
307 const long long int ku = floor_div_xx
308 (static_cast<long long int>(p.max),static_cast<long long int>(m));
309 if (kl == ku) {
310 const long long int shift=kl*m;
311 {
312 const long long int l=static_cast<long long int>(p.min)-shift;
313 ModEvent me=y.gq(home,static_cast<int>(l));
314 if (me_failed(me)) return ES_FAILED;
315 modified |= me_modified(me);
316 }
317 {
318 const long long int u=static_cast<long long int>(p.max)-shift;
319 ModEvent me=y.lq(home,static_cast<int>(u));
320 if (me_failed(me)) return ES_FAILED;
321 modified |= me_modified(me);
322 }
323
324 // Allocate cofactors only when interval inversion can contribute.
325 if (prefix == NULL) {
326 prefix=region.alloc<ProductInterval>(x.size()+1);
327 suffix=region.alloc<ProductInterval>(x.size()+1);
328 }
329 if (!product_mod_intervals(x,prefix,suffix,a))
330 continue;
331
332 // Within one quotient band, invert the exact-product interval.
333 const long long int tmin=static_cast<long long int>(y.min())+shift;
334 const long long int tmax=static_cast<long long int>(y.max())+shift;
335 for (int i=0; i<x.size(); i++) {
337 if (product_mod_interval_mul(prefix[i],suffix[i+1],q) &&
338 ((q.min > 0) || (q.max < 0))) {
339 const ProductWideInterval d=
340 product_quotient_bounds(tmin,tmax,q.min,q.max);
341 const long long int l=std::max
342 (d.min,static_cast<long long int>(Limits::min));
343 const long long int u=std::min
344 (d.max,static_cast<long long int>(Limits::max));
345 if (l > u) return ES_FAILED;
346 {
347 ModEvent me=x[i].gq(home,static_cast<int>(l));
348 if (me_failed(me)) return ES_FAILED;
349 modified |= me_modified(me);
350 }
351 {
352 ModEvent me=x[i].lq(home,static_cast<int>(u));
353 if (me_failed(me)) return ES_FAILED;
354 modified |= me_modified(me);
355 }
356 }
357 }
358 }
359 }
360 } while (modified);
361
362 return ES_FIX;
363 }
364
366 inline bool
368 for (int i=0; i<x.size(); i++)
369 if (x[i] == m)
370 return true;
371 return false;
372 }
373
375 inline bool
376 product_mod_var_exact(const ViewArray<IntView>& x, long long int& p) {
377 long long int q=1;
378 for (int i=0; i<x.size(); i++) {
379 if (!x[i].assigned())
380 return false;
381 const long long int v=x[i].val();
382 if (Limits::overflow_mul(q,v))
383 return false;
384 q *= v;
385 }
386 p=q;
387 return true;
388 }
389
391 inline bool
392 product_mod_var_divisor_bounds(int lower, int upper, long long int d,
393 int& least, int& greatest) {
394 const unsigned long long int ad = d < 0
395 ? static_cast<unsigned long long int>(-(d+1))+1ULL
396 : static_cast<unsigned long long int>(d);
397 assert(ad > 0);
398
399 least=lower;
400 greatest=upper;
401
402 // A positive divisor cannot exceed the absolute difference.
403 if (ad <= static_cast<unsigned long long int>(Limits::max))
404 greatest=std::min(greatest,static_cast<int>(ad));
405 if (least > greatest)
406 return false;
407
408 // If floor(ad/m) is fixed throughout the remaining interval, there is
409 // at most one possible divisor. This is constant-time quotient reasoning;
410 // it does not inspect the values in the modulus domain.
411 const unsigned long long int q0 =
412 ad / static_cast<unsigned long long int>(greatest);
413 const unsigned long long int q1 =
414 ad / static_cast<unsigned long long int>(least);
415 if (q0 == q1) {
416 if ((q0 == 0) || ((ad % q0) != 0))
417 return false;
418 const unsigned long long int candidate=ad/q0;
419 if ((candidate < static_cast<unsigned long long int>(least)) ||
420 (candidate > static_cast<unsigned long long int>(greatest)) ||
421 (candidate > static_cast<unsigned long long int>(Limits::max)))
422 return false;
423 least=greatest=static_cast<int>(candidate);
424 }
425 return true;
426 }
427
429 inline ExecStatus
431 IntView y) {
432 Region region;
433 ProductInterval* prefix=NULL;
434 ProductInterval* suffix=NULL;
435 bool modified;
436 do {
437 modified=false;
438 if (y.min() > 0)
439 GECODE_ES_CHECK(product_mod_nonzero(home,x,modified));
440 for (int i=0; i<x.size(); i++)
441 if (x[i].min() < 0)
442 return ES_OK;
444 if (!product_mod_interval(x,p))
445 return ES_OK;
446
447 {
448 ModEvent me=y.lq(home,std::min(p.max,m.max()-1));
449 if (me_failed(me)) return ES_FAILED;
450 modified |= me_modified(me);
451 }
452
453 const long long int kmin =
454 static_cast<long long int>(p.min) / m.max();
455 const long long int kmax =
456 static_cast<long long int>(p.max) / m.min();
457 if (kmin != kmax)
458 continue;
459
460 const long long int k=kmin;
461 const long long int rmin =
462 static_cast<long long int>(p.min)-k*m.max();
463 const long long int rmax =
464 static_cast<long long int>(p.max)-k*m.min();
465 {
466 ModEvent me=y.gq(home,static_cast<int>(rmin));
467 if (me_failed(me)) return ES_FAILED;
468 modified |= me_modified(me);
469 }
470 {
471 ModEvent me=y.lq(home,static_cast<int>(rmax));
472 if (me_failed(me)) return ES_FAILED;
473 modified |= me_modified(me);
474 }
475 {
476 ModEvent me=m.gq(home,y.min()+1);
477 if (me_failed(me)) return ES_FAILED;
478 modified |= me_modified(me);
479 }
480
481 if (prefix == NULL) {
482 prefix=region.alloc<ProductInterval>(x.size()+1);
483 suffix=region.alloc<ProductInterval>(x.size()+1);
484 }
485 if (!product_mod_intervals(x,prefix,suffix))
486 continue;
487
488 const long long int tmin=k*m.min()+y.min();
489 const long long int tmax=k*m.max()+y.max();
490 for (int i=0; i<x.size(); i++) {
492 if (!product_mod_interval_mul(prefix[i],suffix[i+1],q))
493 continue;
494 if (q.max == 0) {
495 if (tmin > 0)
496 return ES_FAILED;
497 continue;
498 }
499 const long long int candidate_min=ceil_div_xx(tmin,
500 static_cast<long long int>(q.max));
501 const long long int candidate_max=(q.min == 0) ? x[i].max() :
502 floor_div_xx(tmax,static_cast<long long int>(q.min));
503 const long long int l=std::max(
504 candidate_min,static_cast<long long int>(x[i].min()));
505 const long long int u=std::min(
506 candidate_max,static_cast<long long int>(x[i].max()));
507 if (l > u)
508 return ES_FAILED;
509 {
510 ModEvent me=x[i].gq(home,static_cast<int>(l));
511 if (me_failed(me)) return ES_FAILED;
512 modified |= me_modified(me);
513 }
514 {
515 ModEvent me=x[i].lq(home,static_cast<int>(u));
516 if (me_failed(me)) return ES_FAILED;
517 modified |= me_modified(me);
518 }
519 }
520 } while (modified);
521 return ES_OK;
522 }
523
525 inline RelTest
527 const IntView& y) {
528 if ((m == y) || (m.max() <= 0) || (y.max() < 0) ||
529 (y.min() >= m.max()))
530 return RT_FALSE;
531 if (m.assigned())
532 return product_mod_status(x,y,m.val());
533 bool zero=product_mod_var_mod_factor(x,m);
534 for (int i=0; !zero && (i<x.size()); i++)
535 zero=x[i].assigned() && (x[i].val() == 0);
536 if (zero) {
537 if (!y.in(0)) return RT_FALSE;
538 if ((m.min() > 0) && y.assigned()) return RT_TRUE;
539 return RT_MAYBE;
540 }
541 if (x.size() == 0) {
542 const bool zero=m.in(1) && y.in(0);
543 const bool one=(m.max() >= 2) && y.in(1);
544 if (!zero && !one) return RT_FALSE;
545 if ((m.min() >= 2) && y.assigned() && (y.val() == 1))
546 return RT_TRUE;
547 return RT_MAYBE;
548 }
549 if (y.assigned()) {
550 long long int p;
551 if (product_mod_var_exact(x,p) &&
552 !Limits::overflow_sub(p,static_cast<long long int>(y.val()))) {
553 const long long int d=p-y.val();
554 if (d == 0)
555 return (y.val() >= 0) && (m.min() > y.val())
556 ? RT_TRUE : RT_MAYBE;
557 int least;
558 int greatest;
560 (std::max(m.min(),y.val()+1),m.max(),d,least,greatest))
561 return RT_FALSE;
562 if ((least == greatest) && !m.in(least))
563 return RT_FALSE;
564 }
565 }
566 return RT_MAYBE;
567 }
568
569 forceinline
571 IntView modulus, IntView w)
572 : Propagator(home), x(z), m(modulus), y(w) {
573 home.notice(*this,AP_WEAKLY);
574 x.subscribe(home,*this,PC_INT_BND);
575 m.subscribe(home,*this,PC_INT_BND);
576 y.subscribe(home,*this,PC_INT_BND);
577 }
578
579 inline ExecStatus
581 if (m == y)
582 return ES_FAILED;
583 GECODE_ME_CHECK(m.gq(home,1));
584 GECODE_ME_CHECK(y.gq(home,0));
585 GECODE_ME_CHECK(y.lq(home,m.max()-1));
586 GECODE_ME_CHECK(m.gq(home,y.min()+1));
589 GECODE_ME_CHECK(y.eq(home,0));
590 return ES_OK;
591 }
592 if (x.size() == 0) {
593 GECODE_ME_CHECK(y.lq(home,1));
594 if (!y.in(0)) {
595 GECODE_ME_CHECK(m.gq(home,2));
596 GECODE_ME_CHECK(y.eq(home,1));
597 } else if (!y.in(1)) {
598 GECODE_ME_CHECK(m.eq(home,1));
599 GECODE_ME_CHECK(y.eq(home,0));
600 }
601 }
602 if (m.assigned())
603 return ProductMod::post(home,x,m.val(),y);
604 (void) new (home) ProductModVar(home,x,m,y);
605 return ES_OK;
606 }
607
608 forceinline
610 : Propagator(home,p) {
611 x.update(home,p.x); m.update(home,p.m); y.update(home,p.y);
612 }
613
614 forceinline Actor*
616 return new (home) ProductModVar(home,*this);
617 }
618
619 forceinline PropCost
622 }
623
624 forceinline void
626 x.reschedule(home,*this,PC_INT_BND);
627 m.reschedule(home,*this,PC_INT_BND);
628 y.reschedule(home,*this,PC_INT_BND);
629 }
630
631 inline ExecStatus
633 GECODE_ME_CHECK(m.gq(home,1));
634 GECODE_ME_CHECK(y.gq(home,0));
635 GECODE_ME_CHECK(y.lq(home,m.max()-1));
636 GECODE_ME_CHECK(m.gq(home,y.min()+1));
639 GECODE_ME_CHECK(y.eq(home,0));
640 return home.ES_SUBSUMED(*this);
641 }
642 for (int i=0; i<x.size(); i++)
643 if (x[i].assigned() && (x[i].val() == 0)) {
644 GECODE_ME_CHECK(y.eq(home,0));
645 return home.ES_SUBSUMED(*this);
646 }
647 if (x.size() == 0) {
648 GECODE_ME_CHECK(y.lq(home,1));
649 if (!y.in(0)) {
650 GECODE_ME_CHECK(m.gq(home,2));
651 GECODE_ME_CHECK(y.eq(home,1));
652 return home.ES_SUBSUMED(*this);
653 }
654 if (!y.in(1)) {
655 GECODE_ME_CHECK(m.eq(home,1));
656 GECODE_ME_CHECK(y.eq(home,0));
657 return home.ES_SUBSUMED(*this);
658 }
659 if (m.min() >= 2) {
660 GECODE_ME_CHECK(y.eq(home,1));
661 return home.ES_SUBSUMED(*this);
662 }
663 if (!m.in(1)) {
664 GECODE_ME_CHECK(y.eq(home,1));
665 return home.ES_SUBSUMED(*this);
666 }
667 }
668 if (m.assigned())
669 GECODE_REWRITE(*this,ProductMod::post(home(*this),x,m.val(),y));
670
672 if (m.assigned())
673 GECODE_REWRITE(*this,ProductMod::post(home(*this),x,m.val(),y));
674
675 // With an assigned product and result, m must divide product-result.
676 const unsigned int modulus_size=m.size();
677 long long int p;
678 if (y.assigned() && product_mod_var_exact(x,p)) {
679 if (!Limits::overflow_sub(p,static_cast<long long int>(y.val()))) {
680 const long long int d=p-y.val();
681 if (d == 0)
682 return home.ES_SUBSUMED(*this);
683 int least;
684 int greatest;
686 (m.min(),m.max(),d,least,greatest))
687 return ES_FAILED;
688 GECODE_ME_CHECK(m.gq(home,least));
689 GECODE_ME_CHECK(m.lq(home,greatest));
690 }
691 }
692 if (m.assigned())
693 GECODE_REWRITE(*this,ProductMod::post(home(*this),x,m.val(),y));
694 // A sparse-domain update can expose a new fixed quotient band.
695 return (modulus_size != m.size()) ? ES_NOFIX : ES_FIX;
696 }
697
698 forceinline size_t
700 x.cancel(home,*this,PC_INT_BND);
701 m.cancel(home,*this,PC_INT_BND);
702 y.cancel(home,*this,PC_INT_BND);
703 home.ignore(*this,AP_WEAKLY);
704 (void) Propagator::dispose(home);
705 return sizeof(*this);
706 }
707
708 template<ReifyMode rm>
709 forceinline
711 IntView modulus, IntView w, BoolView c)
712 : Propagator(home), x(z), m(modulus), y(w), b(c) {
713 home.notice(*this,AP_WEAKLY);
714 x.subscribe(home,*this,PC_INT_BND);
715 m.subscribe(home,*this,PC_INT_BND);
716 y.subscribe(home,*this,PC_INT_BND);
717 b.subscribe(home,*this,PC_BOOL_VAL);
718 }
719
720 template<ReifyMode rm>
721 inline ExecStatus
723 IntView y, BoolView b) {
724 if (b.one()) {
725 if (rm == RM_PMI) return ES_OK;
726 return ProductModVar::post(home,x,m,y);
727 }
728 if (b.zero() && (rm == RM_IMP))
729 return ES_OK;
730 (void) new (home) ReProductModVar<rm>(home,x,m,y,b);
731 return ES_OK;
732 }
733
734 template<ReifyMode rm>
735 forceinline
738 : Propagator(home,p) {
739 x.update(home,p.x); m.update(home,p.m); y.update(home,p.y);
740 b.update(home,p.b);
741 }
742
743 template<ReifyMode rm>
744 forceinline Actor*
746 return new (home) ReProductModVar<rm>(home,*this);
747 }
748
749 template<ReifyMode rm>
750 forceinline PropCost
752 return PropCost::linear(PropCost::HI,x.size()+3);
753 }
754
755 template<ReifyMode rm>
756 forceinline void
758 x.reschedule(home,*this,PC_INT_BND);
759 m.reschedule(home,*this,PC_INT_BND);
760 y.reschedule(home,*this,PC_INT_BND);
761 b.reschedule(home,*this,PC_BOOL_VAL);
762 }
763
764 template<ReifyMode rm>
765 inline ExecStatus
767 if (b.one()) {
768 if (rm == RM_PMI)
769 return home.ES_SUBSUMED(*this);
770 GECODE_REWRITE(*this,ProductModVar::post(home(*this),x,m,y));
771 }
772 if (b.zero()) {
773 if (rm == RM_IMP)
774 return home.ES_SUBSUMED(*this);
776 if (rt == RT_TRUE)
777 return ES_FAILED;
778 if (rt == RT_FALSE)
779 return home.ES_SUBSUMED(*this);
780 return ES_FIX;
781 }
782
784 switch (rt) {
785 case RT_TRUE:
786 if (rm != RM_IMP) GECODE_ME_CHECK(b.one_none(home));
787 return home.ES_SUBSUMED(*this);
788 case RT_FALSE:
789 if (rm != RM_PMI) GECODE_ME_CHECK(b.zero_none(home));
790 return home.ES_SUBSUMED(*this);
791 case RT_MAYBE:
792 return ES_FIX;
793 default: GECODE_NEVER;
794 }
795 }
796
797 template<ReifyMode rm>
798 forceinline size_t
800 x.cancel(home,*this,PC_INT_BND);
801 m.cancel(home,*this,PC_INT_BND);
802 y.cancel(home,*this,PC_INT_BND);
803 b.cancel(home,*this,PC_BOOL_VAL);
804 home.ignore(*this,AP_WEAKLY);
805 (void) Propagator::dispose(home);
806 return sizeof(*this);
807 }
808
809 template<ReifyMode rm>
810 forceinline
812 int modulus, IntView w, BoolView c)
813 : Propagator(home), x(z), y(w), b(c), m(modulus) {
814 home.notice(*this,AP_WEAKLY);
815 x.subscribe(home,*this,PC_INT_BND);
816 y.subscribe(home,*this,PC_INT_BND);
817 b.subscribe(home,*this,PC_BOOL_VAL);
818 }
819
820 template<ReifyMode rm>
821 inline ExecStatus
823 BoolView b) {
824 if (b.one() && (rm == RM_PMI))
825 return ES_OK;
826 if (b.zero() && (rm == RM_IMP))
827 return ES_OK;
828 if (x.size() == 0)
830 switch (product_mod_status(x,y,m)) {
831 case RT_TRUE:
832 if (rm != RM_IMP) GECODE_ME_CHECK(b.one(home));
833 return ES_OK;
834 case RT_FALSE:
835 if (rm != RM_PMI) GECODE_ME_CHECK(b.zero(home));
836 return ES_OK;
837 case RT_MAYBE:
838 break;
839 default: GECODE_NEVER;
840 }
841 (void) new (home) ReProductMod<rm>(home,x,m,y,b);
842 return ES_OK;
843 }
844
845 template<ReifyMode rm>
846 forceinline
848 : Propagator(home,p), m(p.m) {
849 x.update(home,p.x); y.update(home,p.y); b.update(home,p.b);
850 }
851
852 template<ReifyMode rm>
853 forceinline Actor*
855 return new (home) ReProductMod<rm>(home,*this);
856 }
857
858 template<ReifyMode rm>
859 forceinline PropCost
861 return PropCost::linear(PropCost::HI,x.size()+2);
862 }
863
864 template<ReifyMode rm>
865 forceinline void
867 x.reschedule(home,*this,PC_INT_BND);
868 y.reschedule(home,*this,PC_INT_BND);
869 b.reschedule(home,*this,PC_BOOL_VAL);
870 }
871
872 template<ReifyMode rm>
873 inline ExecStatus
875 if (b.one()) {
876 if (rm == RM_PMI)
877 return home.ES_SUBSUMED(*this);
878 GECODE_REWRITE(*this,ProductMod::post(home(*this),x,m,y));
879 }
880 if (b.zero()) {
881 if (rm == RM_IMP)
882 return home.ES_SUBSUMED(*this);
883 switch (product_mod_status(x,y,m)) {
884 case RT_TRUE: return ES_FAILED;
885 case RT_FALSE: return home.ES_SUBSUMED(*this);
886 case RT_MAYBE: return ES_FIX;
887 default: GECODE_NEVER;
888 }
889 }
890 switch (product_mod_status(x,y,m)) {
891 case RT_TRUE:
892 if (rm != RM_IMP) GECODE_ME_CHECK(b.one_none(home));
893 return home.ES_SUBSUMED(*this);
894 case RT_FALSE:
895 if (rm != RM_PMI) GECODE_ME_CHECK(b.zero_none(home));
896 return home.ES_SUBSUMED(*this);
897 case RT_MAYBE:
898 return ES_FIX;
899 default: GECODE_NEVER;
900 }
901 }
902
903 template<ReifyMode rm>
904 forceinline size_t
906 x.cancel(home,*this,PC_INT_BND);
907 y.cancel(home,*this,PC_INT_BND);
908 b.cancel(home,*this,PC_BOOL_VAL);
909 home.ignore(*this,AP_WEAKLY);
910 (void) Propagator::dispose(home);
911 return sizeof(*this);
912 }
913
914}}}
915
916// 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
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
ViewArray< IntView > x
Factors.
static ExecStatus post(Home home, ViewArray< IntView > &x, IntView m, IntView y)
Post propagator.
virtual PropCost cost(const Space &home, const ModEventDelta &med) const
Cost function.
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
virtual Actor * copy(Space &home)
Copy propagator during cloning.
ProductModVar(Home home, ViewArray< IntView > &x, IntView m, IntView y)
Constructor for posting.
virtual void reschedule(Space &home)
Reschedule propagator.
virtual size_t dispose(Space &home)
Delete propagator and return its size.
virtual Actor * copy(Space &home)
Copy propagator during cloning.
int a
Exact product of removed factors, or zero when not representable.
ProductMod(Home home, ViewArray< IntView > &x, int m, IntView y, int c, int a)
Constructor for posting.
static ExecStatus post(Home home, ViewArray< IntView > &x, int m, IntView y)
Post propagator.
int c
Canonical residue of removed factors.
virtual size_t dispose(Space &home)
Delete propagator and return its size.
virtual PropCost cost(const Space &home, const ModEventDelta &med) const
Cost function.
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
virtual void reschedule(Space &home)
Reschedule propagator.
BoolView b
Reification control.
ViewArray< IntView > x
Factors.
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
virtual size_t dispose(Space &home)
Delete propagator and return its size.
virtual Actor * copy(Space &home)
Copy propagator during cloning.
IntView m
Modulus (positivity is part of the reified proposition).
static ExecStatus post(Home home, ViewArray< IntView > &x, IntView m, IntView y, BoolView b)
Post propagator.
virtual PropCost cost(const Space &home, const ModEventDelta &med) const
Cost function.
ReProductModVar(Home home, ViewArray< IntView > &x, IntView m, IntView y, BoolView b)
Constructor for posting.
ViewArray< IntView > x
Factors.
virtual Actor * copy(Space &home)
Copy propagator during cloning.
static ExecStatus post(Home home, ViewArray< IntView > &x, int m, IntView y, BoolView b)
Post propagator.
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
virtual size_t dispose(Space &home)
Delete propagator and return its size.
ReProductMod(Home home, ViewArray< IntView > &x, int m, IntView y, BoolView b)
Constructor for posting.
virtual void reschedule(Space &home)
Reschedule propagator.
BoolView b
Reification control.
virtual PropCost cost(const Space &home, const ModEventDelta &med) const
Cost function.
Boolean view for Boolean variables.
Definition view.hpp:1378
bool zero(void) const
Test whether view is assigned to be zero.
Definition bool.hpp:220
bool one(void) const
Test whether view is assigned to be one.
Definition bool.hpp:224
Integer view for integer variables.
Definition view.hpp:129
unsigned int size(void) const
Return size (cardinality) of domain.
Definition int.hpp:81
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 val(void) const
Return assigned value (only if assigned).
Definition int.hpp:70
int max(void) const
Return maximum of domain.
Definition int.hpp:62
ModEvent eq(Space &home, int n)
Restrict domain values to be equal to n.
Definition int.hpp:166
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
T * alloc(long unsigned int n)
Allocate block of n objects of type T from region.
Definition region.hpp:386
Computation spaces.
Definition core.hpp:1787
void update(Space &home, VarImpView< Var > &y)
Update this view to be a clone of view y.
Definition view.hpp:567
void cancel(Space &home, Propagator &p, PropCond pc)
Cancel subscription of propagator p with propagation condition pc to view.
Definition view.hpp:527
void reschedule(Space &home, Propagator &p, PropCond pc)
Re-schedule propagator p with propagation condition pc.
Definition view.hpp:532
bool assigned(void) const
Test whether view is assigned.
Definition view.hpp:516
void subscribe(Space &home, Propagator &p, PropCond pc, bool schedule=true)
Subscribe propagator p with propagation condition pc to view.
Definition view.hpp:521
View arrays.
Definition array.hpp:255
void update(Space &home, ViewArray< View > &a)
Update array to be a clone of array a.
Definition array.hpp:1337
void reschedule(Space &home, Propagator &p, PropCond pc)
Re-schedule propagator p with propagation condition pc.
Definition array.hpp:1379
void cancel(Space &home, Propagator &p, PropCond pc)
Cancel subscription of propagator p with propagation condition pc to all views.
Definition array.hpp:1358
void move_lst(int i)
Move view from position size()-1 to position i (truncate array by one).
Definition array.hpp:1245
void subscribe(Space &home, Propagator &p, PropCond pc, bool schedule=true)
Subscribe propagator p with propagation condition pc to variable.
Definition array.hpp:1350
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
#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
@ 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.
long long int product_mod_inverse(long long int a, long long int m)
Extended Euclid for a modular inverse (arguments are coprime).
ProductInterval product_mod_congruence(ProductInterval x, int c, int m, int y)
Extreme solutions to c*x = y modulo m, or an empty interval.
RelTest product_mod_var_status(const ViewArray< IntView > &x, const IntView &m, const IntView &y)
Determine algebraic status; evaluate the residue only when fully assigned.
int product_mod_coefficient(const ViewArray< IntView > &x, int m, int &free_count)
Reduce assigned factors and count the remaining factor occurrences.
bool product_mod_interval(const ViewArray< IntView > &x, ProductInterval &p, int a=1)
Return exact representable product bounds, or false on overflow.
void product_mod_fold(ViewArray< IntView > &x, int m, int &c, int &a)
Fold assigned occurrences into modular and representable exact coefficients.
bool product_mod_intervals(const ViewArray< IntView > &x, ProductInterval *prefix, ProductInterval *suffix, int a=1)
Build all cofactor bounds in linear time, without modular saturation.
ExecStatus product_mod_var_ranges(Home home, ViewArray< IntView > &x, IntView m, IntView y)
Propagate a nonnegative representable product with a variable modulus.
ExecStatus multiple_bounds(Home home, IntView x, int d)
Tighten a view to the extreme multiples of a positive divisor.
Definition gcd.hpp:73
bool product_mod_var_exact(const ViewArray< IntView > &x, long long int &p)
Compute the exact assigned product when it fits in a signed 64-bit value.
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
bool product_mod_var_mod_factor(const ViewArray< IntView > &x, const IntView &m)
Whether the modulus occurs among the factors.
int gcd_value(int a, int b)
Definition gcd.hpp:39
bool product_mod_interval_mul(ProductInterval a, ProductInterval b, ProductInterval &p)
Multiply intervals exactly; saturation would make modular deductions unsound.
ExecStatus product_mod_nonzero(Space &home, ViewArray< IntView > &x, bool &modified)
A nonzero residue excludes bounds-visible zero factors.
void product_mod_units(ViewArray< IntView > &x)
Drop assigned units without changing a product with an unknown modulus.
RelTest product_mod_status(const ViewArray< IntView > &x, const IntView &y, int m)
Determine the fixed-modulus relation algebraically.
bool product_mod_var_divisor_bounds(int lower, int upper, long long int d, int &least, int &greatest)
Tighten divisor bounds for a nonzero difference without enumeration.
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
bool overflow_sub(int n, int m)
Check whether subtracting m from n would overflow.
Definition limits.hpp:93
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
Gecode toplevel namespace
void min(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
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 GECODE_NEVER
Assert that this command is never executed.
Definition macros.hpp:56