Generated on for Gecode by doxygen 1.17.0
divides.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
34#include <algorithm>
35
36namespace Gecode { namespace Int { namespace Arithmetic {
37
38 forceinline bool
39 divides_value(int divisor, int dividend) {
40 return (divisor == 0) ? (dividend == 0) : (dividend % divisor == 0);
41 }
42
44 inline ExecStatus
45 divides_bnd(Space& home, IntView divisor, IntView dividend) {
46 if (divisor == dividend)
47 return ES_OK;
48 if (dividend.assigned() && (dividend.val() == 0))
49 return ES_OK;
50 if (divisor.assigned()) {
51 const int d=divisor.val();
52 if (d == 0) {
53 GECODE_ME_CHECK(dividend.eq(home,0));
54 return ES_OK;
55 }
56 if ((d == 1) || (d == -1))
57 return ES_OK;
58 GECODE_ES_CHECK(multiple_bounds(home,dividend,(d < 0) ? -d : d));
59 }
60
61 // Every divisor of a nonzero dividend has no greater magnitude.
62 if (!dividend.in(0)) {
63 const int a=gcd_max_abs(dividend);
64 GECODE_ME_CHECK(divisor.gq(home,-a));
65 GECODE_ME_CHECK(divisor.lq(home,a));
66 GECODE_ME_CHECK(divisor.nq(home,0));
67 }
68
69 if (divisor.assigned() && dividend.assigned())
70 return divides_value(divisor.val(),dividend.val()) ? ES_OK : ES_FAILED;
71 return ES_FIX;
72 }
73
74 inline RelTest
75 divides_status(const IntView& x0, const IntView& x1) {
76 if (x0 == x1)
77 return RT_TRUE;
78 if (x1.assigned() && (x1.val() == 0))
79 return RT_TRUE;
80 if (x0.assigned() && ((x0.val() == 1) || (x0.val() == -1)))
81 return RT_TRUE;
82 if (x0.assigned() && (x0.val() == 0) && !x1.in(0))
83 return RT_FALSE;
84 if (x0.assigned() && (x0.val() != 0)) {
85 const int a=(x0.val() < 0) ? -x0.val() : x0.val();
86 const long long int l =
87 ceil_div_xx(static_cast<long long int>(x1.min()),
88 static_cast<long long int>(a)) * a;
89 const long long int u =
90 floor_div_xx(static_cast<long long int>(x1.max()),
91 static_cast<long long int>(a)) * a;
92 if (l > u)
93 return RT_FALSE;
94 }
95 if (!x1.in(0)) {
96 const int a=gcd_max_abs(x1);
97 if ((x0.min() > a) || (x0.max() < -a))
98 return RT_FALSE;
99 }
100 if (x0.assigned() && x1.assigned())
101 return divides_value(x0.val(),x1.val()) ? RT_TRUE : RT_FALSE;
102 return RT_MAYBE;
103 }
104
105 template<ReifyMode rm>
109 home.notice(*this,AP_WEAKLY);
110 }
111
112 template<ReifyMode rm>
113 inline ExecStatus
115 if (b.one() && (rm == RM_PMI))
116 return ES_OK;
117 if (b.zero() && (rm == RM_IMP))
118 return ES_OK;
120 if (rt == RT_TRUE) {
121 if (rm != RM_IMP)
122 GECODE_ME_CHECK(b.one(home));
123 return ES_OK;
124 }
125 if (rt == RT_FALSE) {
126 if (rm != RM_PMI)
127 GECODE_ME_CHECK(b.zero(home));
128 return ES_OK;
129 }
130 (void) new (home) ReDivides<rm>(home,x0,x1,b);
131 return ES_OK;
132 }
133
134 template<ReifyMode rm>
138
139 template<ReifyMode rm>
142 return new (home) ReDivides<rm>(home,*this);
143 }
144
145 template<ReifyMode rm>
149 }
150
151 template<ReifyMode rm>
152 inline ExecStatus
154 if (b.one()) {
155 if (rm == RM_PMI)
156 return home.ES_SUBSUMED(*this);
157 const unsigned int s0=x0.size();
158 const unsigned int s1=x1.size();
160 const RelTest rt=divides_status(x0,x1);
161 if (rt == RT_FALSE)
162 return ES_FAILED;
163 if (rt == RT_TRUE)
164 return home.ES_SUBSUMED(*this);
165 // Revisit sparse endpoints and divisors assigned by this call.
166 return ((s0 != x0.size()) || (s1 != x1.size())) ? ES_NOFIX : ES_FIX;
167 }
168 if (b.zero()) {
169 if (rm == RM_IMP)
170 return home.ES_SUBSUMED(*this);
171 if (x0.assigned() && (x0.val() == 0)) {
172 GECODE_ME_CHECK(x1.nq(home,0));
173 return home.ES_SUBSUMED(*this);
174 }
175 const RelTest rt=divides_status(x0,x1);
176 if (rt == RT_TRUE) return ES_FAILED;
177 if (rt == RT_FALSE)
178 return home.ES_SUBSUMED(*this);
179 return ES_FIX;
180 }
181
182 switch (divides_status(x0,x1)) {
183 case RT_TRUE:
184 if (rm != RM_IMP)
185 GECODE_ME_CHECK(b.one_none(home));
186 break;
187 case RT_FALSE:
188 if (rm != RM_PMI)
189 GECODE_ME_CHECK(b.zero_none(home));
190 break;
191 case RT_MAYBE:
192 return ES_FIX;
193 default: GECODE_NEVER;
194 }
195 return home.ES_SUBSUMED(*this);
196 }
197
198 template<ReifyMode rm>
199 forceinline size_t
201 home.ignore(*this,AP_WEAKLY);
203 return sizeof(*this);
204 }
205
206}}}
207
208// STATISTICS: int-prop
Base-class for both propagators and branchers.
Definition core.hpp:635
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
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Definition divides.hpp:153
static ExecStatus post(Home home, IntView x0, IntView x1, BoolView b)
Post propagator.
Definition divides.hpp:114
virtual PropCost cost(const Space &home, const ModEventDelta &med) const
Cost function.
Definition divides.hpp:147
ReDivides(Home home, IntView x0, IntView x1, BoolView b)
Constructor for posting.
Definition divides.hpp:107
virtual Actor * copy(Space &home)
Copy propagator during cloning.
Definition divides.hpp:141
virtual size_t dispose(Space &home)
Delete propagator and return its size.
Definition divides.hpp:200
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 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 nq(Space &home, int n)
Restrict domain values to be different from n.
Definition int.hpp:157
ModEvent eq(Space &home, int n)
Restrict domain values to be equal to n.
Definition int.hpp:166
virtual size_t dispose(Space &home)
Delete propagator and return its size.
Propagation cost.
Definition core.hpp:493
static PropCost binary(PropCost::Mod m)
Two variables for modifier pcm.
Definition core.hpp:5093
friend class Space
Definition core.hpp:1075
Computation spaces.
Definition core.hpp:1787
bool assigned(void) const
Test whether view is assigned.
Definition view.hpp:516
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_ES_CHECK(es)
Check whether execution status es is failed or subsumed, and forward failure or subsumption.
Definition macros.hpp:91
@ 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.
ExecStatus divides_bnd(Space &home, IntView divisor, IntView dividend)
Enforce divisibility with bounds reasoning only.
Definition divides.hpp:45
bool divides_value(int divisor, int dividend)
Definition divides.hpp:39
RelTest divides_status(const IntView &x0, const IntView &x1)
Definition divides.hpp:75
ExecStatus multiple_bounds(Home home, IntView x, int d)
Tighten a view to the extreme multiples of a positive divisor.
Definition gcd.hpp:73
int gcd_max_abs(const IntView &x)
Definition gcd.hpp:50
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
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
Gecode toplevel namespace
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
#define forceinline
Definition config.hpp:144
#define GECODE_NEVER
Assert that this command is never executed.
Definition macros.hpp:56