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, 2004
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/arithmetic.hh>
35
36namespace Gecode { namespace Int { namespace Arithmetic {
37
38 /*
39 * Bounds consistent multiplication
40 *
41 */
42 Actor*
43 MultBnd::copy(Space& home) {
44 return new (home) MultBnd(home,*this);
45 }
46
47 ExecStatus
48 MultBnd::propagate(Space& home, const ModEventDelta&) {
49 if (pos(x0)) {
50 if (pos(x1) || pos(x2)) goto rewrite_ppp;
51 if (neg(x1) || neg(x2)) goto rewrite_pnn;
52 goto prop_pxx;
53 }
54 if (neg(x0)) {
55 if (neg(x1) || pos(x2)) goto rewrite_nnp;
56 if (pos(x1) || neg(x2)) goto rewrite_npn;
57 goto prop_nxx;
58 }
59 if (pos(x1)) {
60 if (pos(x2)) goto rewrite_ppp;
61 if (neg(x2)) goto rewrite_npn;
62 goto prop_xpx;
63 }
64 if (neg(x1)) {
65 if (pos(x2)) goto rewrite_nnp;
66 if (neg(x2)) goto rewrite_pnn;
67 goto prop_xnx;
68 }
69
70 assert(any(x0) && any(x1));
71 GECODE_ME_CHECK(x2.lq(home,std::max(mll(x0.max(),x1.max()),
72 mll(x0.min(),x1.min()))));
73 GECODE_ME_CHECK(x2.gq(home,std::min(mll(x0.min(),x1.max()),
74 mll(x0.max(),x1.min()))));
75
76 if (x0.assigned()) {
77 assert((x0.val() == 0) && (x2.val() == 0));
78 return home.ES_SUBSUMED(*this);
79 }
80
81 if (x1.assigned()) {
82 assert((x1.val() == 0) && (x2.val() == 0));
83 return home.ES_SUBSUMED(*this);
84 }
85
86 return ES_NOFIX;
87
88 prop_xpx:
89 std::swap(x0,x1);
90 prop_pxx:
91 assert(pos(x0) && any(x1) && any(x2));
92
93 GECODE_ME_CHECK(x2.lq(home,mll(x0.max(),x1.max())));
94 GECODE_ME_CHECK(x2.gq(home,mll(x0.max(),x1.min())));
95
96 if (pos(x2)) goto rewrite_ppp;
97 if (neg(x2)) goto rewrite_pnn;
98
99 GECODE_ME_CHECK(x1.lq(home,floor_div_xp(x2.max(),x0.min())));
100 GECODE_ME_CHECK(x1.gq(home,ceil_div_xp(x2.min(),x0.min())));
101
102 if (x0.assigned() && x1.assigned()) {
103 GECODE_ME_CHECK(x2.eq(home,mll(x0.val(),x1.val())));
104 return home.ES_SUBSUMED(*this);
105 }
106
107 return ES_NOFIX;
108
109 prop_xnx:
110 std::swap(x0,x1);
111 prop_nxx:
112 assert(neg(x0) && any(x1) && any(x2));
113
114 GECODE_ME_CHECK(x2.lq(home,mll(x0.min(),x1.min())));
115 GECODE_ME_CHECK(x2.gq(home,mll(x0.min(),x1.max())));
116
117 if (pos(x2)) goto rewrite_nnp;
118 if (neg(x2)) goto rewrite_npn;
119
120 GECODE_ME_CHECK(x1.lq(home,floor_div_xx(x2.min(),x0.max())));
121 GECODE_ME_CHECK(x1.gq(home,ceil_div_xx(x2.max(),x0.max())));
122
123 if (x0.assigned() && x1.assigned()) {
124 GECODE_ME_CHECK(x2.eq(home,mll(x0.val(),x1.val())));
125 return home.ES_SUBSUMED(*this);
126 }
127
128 return ES_NOFIX;
129
130 rewrite_ppp:
131 GECODE_REWRITE(*this,(MultPlusBnd<IntView,IntView,IntView>
132 ::post(home(*this),x0,x1,x2)));
133 rewrite_nnp:
134 GECODE_REWRITE(*this,(MultPlusBnd<MinusView,MinusView,IntView>
135 ::post(home(*this),MinusView(x0),MinusView(x1),x2)));
136 rewrite_pnn:
137 std::swap(x0,x1);
138 rewrite_npn:
139 GECODE_REWRITE(*this,(MultPlusBnd<MinusView,IntView,MinusView>
140 ::post(home(*this),MinusView(x0),x1,MinusView(x2))));
141 }
142
143 ExecStatus
144 MultBnd::post(Home home, IntView x0, IntView x1, IntView x2) {
145 if (x0 == x1) {
146 SqrOps ops;
147 return PowBnd<SqrOps>::post(home,x0,x2,ops);
148 }
149 if (x0 == x2)
150 return MultZeroOne<IntView,PC_INT_BND>::post(home,x0,x1);
151 if (x1 == x2)
152 return MultZeroOne<IntView,PC_INT_BND>::post(home,x1,x0);
153 if (pos(x0)) {
154 if (pos(x1) || pos(x2)) goto post_ppp;
155 if (neg(x1) || neg(x2)) goto post_pnn;
156 } else if (neg(x0)) {
157 if (neg(x1) || pos(x2)) goto post_nnp;
158 if (pos(x1) || neg(x2)) goto post_npn;
159 } else if (pos(x1)) {
160 if (pos(x2)) goto post_ppp;
161 if (neg(x2)) goto post_npn;
162 } else if (neg(x1)) {
163 if (pos(x2)) goto post_nnp;
164 if (neg(x2)) goto post_pnn;
165 }
166 {
167 long long int a = mll(x0.min(),x1.min());
168 long long int b = mll(x0.min(),x1.max());
169 long long int c = mll(x0.max(),x1.min());
170 long long int d = mll(x0.max(),x1.max());
171 GECODE_ME_CHECK(x2.gq(home,std::min(std::min(a,b),std::min(c,d))));
172 GECODE_ME_CHECK(x2.lq(home,std::max(std::max(a,b),std::max(c,d))));
173 (void) new (home) MultBnd(home,x0,x1,x2);
174 }
175 return ES_OK;
176
177 post_ppp:
178 return MultPlusBnd<IntView,IntView,IntView>
179 ::post(home,x0,x1,x2);
180 post_nnp:
181 return MultPlusBnd<MinusView,MinusView,IntView>
182 ::post(home,MinusView(x0),MinusView(x1),x2);
183 post_pnn:
184 std::swap(x0,x1);
185 post_npn:
186 return MultPlusBnd<MinusView,IntView,MinusView>
187 ::post(home,MinusView(x0),x1,MinusView(x2));
188 }
189
190
191
192 /*
193 * Domain consistent multiplication
194 *
195 */
196 Actor*
197 MultDom::copy(Space& home) {
198 return new (home) MultDom(home,*this);
199 }
200
201 PropCost
202 MultDom::cost(const Space&, const ModEventDelta& med) const {
203 if (IntView::me(med) == ME_INT_DOM)
204 return PropCost::ternary(PropCost::HI);
205 else
206 return PropCost::ternary(PropCost::LO);
207 }
208
209 ExecStatus
210 MultDom::propagate(Space& home, const ModEventDelta& med) {
211 if (IntView::me(med) != ME_INT_DOM) {
212 if (pos(x0)) {
213 if (pos(x1) || pos(x2)) goto rewrite_ppp;
214 if (neg(x1) || neg(x2)) goto rewrite_pnn;
215 goto prop_pxx;
216 }
217 if (neg(x0)) {
218 if (neg(x1) || pos(x2)) goto rewrite_nnp;
219 if (pos(x1) || neg(x2)) goto rewrite_npn;
220 goto prop_nxx;
221 }
222 if (pos(x1)) {
223 if (pos(x2)) goto rewrite_ppp;
224 if (neg(x2)) goto rewrite_npn;
225 goto prop_xpx;
226 }
227 if (neg(x1)) {
228 if (pos(x2)) goto rewrite_nnp;
229 if (neg(x2)) goto rewrite_pnn;
230 goto prop_xnx;
231 }
232
233 assert(any(x0) && any(x1));
234 GECODE_ME_CHECK(x2.lq(home,std::max(mll(x0.max(),x1.max()),
235 mll(x0.min(),x1.min()))));
236 GECODE_ME_CHECK(x2.gq(home,std::min(mll(x0.min(),x1.max()),
237 mll(x0.max(),x1.min()))));
238
239 if (x0.assigned()) {
240 assert((x0.val() == 0) && (x2.val() == 0));
241 return home.ES_SUBSUMED(*this);
242 }
243
244 if (x1.assigned()) {
245 assert((x1.val() == 0) && (x2.val() == 0));
246 return home.ES_SUBSUMED(*this);
247 }
248
249 return home.ES_NOFIX_PARTIAL(*this,IntView::med(ME_INT_DOM));
250
251 prop_xpx:
252 std::swap(x0,x1);
253 prop_pxx:
254 assert(pos(x0) && any(x1) && any(x2));
255
256 GECODE_ME_CHECK(x2.lq(home,mll(x0.max(),x1.max())));
257 GECODE_ME_CHECK(x2.gq(home,mll(x0.max(),x1.min())));
258
259 if (pos(x2)) goto rewrite_ppp;
260 if (neg(x2)) goto rewrite_pnn;
261
262 GECODE_ME_CHECK(x1.lq(home,floor_div_xp(x2.max(),x0.min())));
263 GECODE_ME_CHECK(x1.gq(home,ceil_div_xp(x2.min(),x0.min())));
264
265 if (x0.assigned() && x1.assigned()) {
266 GECODE_ME_CHECK(x2.eq(home,mll(x0.val(),x1.val())));
267 return home.ES_SUBSUMED(*this);
268 }
269
270 return home.ES_NOFIX_PARTIAL(*this,IntView::med(ME_INT_DOM));
271
272 prop_xnx:
273 std::swap(x0,x1);
274 prop_nxx:
275 assert(neg(x0) && any(x1) && any(x2));
276
277 GECODE_ME_CHECK(x2.lq(home,mll(x0.min(),x1.min())));
278 GECODE_ME_CHECK(x2.gq(home,mll(x0.min(),x1.max())));
279
280 if (pos(x2)) goto rewrite_nnp;
281 if (neg(x2)) goto rewrite_npn;
282
283 GECODE_ME_CHECK(x1.lq(home,floor_div_xx(x2.min(),x0.max())));
284 GECODE_ME_CHECK(x1.gq(home,ceil_div_xx(x2.max(),x0.max())));
285
286 if (x0.assigned() && x1.assigned()) {
287 GECODE_ME_CHECK(x2.eq(home,mll(x0.val(),x1.val())));
288 return home.ES_SUBSUMED(*this);
289 }
290
291 return home.ES_NOFIX_PARTIAL(*this,IntView::med(ME_INT_DOM));
292
293 rewrite_ppp:
294 GECODE_REWRITE(*this,(MultPlusDom<IntView,IntView,IntView>
295 ::post(home(*this),x0,x1,x2)));
296 rewrite_nnp:
297 GECODE_REWRITE(*this,(MultPlusDom<MinusView,MinusView,IntView>
298 ::post(home(*this),
299 MinusView(x0),MinusView(x1),x2)));
300 rewrite_pnn:
301 std::swap(x0,x1);
302 rewrite_npn:
303 GECODE_REWRITE(*this,(MultPlusDom<MinusView,IntView,MinusView>
304 ::post(home(*this),
305 MinusView(x0),x1,MinusView(x2))));
306 }
307 return prop_mult_dom<IntView>(home,*this,x0,x1,x2);
308 }
309
310 ExecStatus
311 MultDom::post(Home home, IntView x0, IntView x1, IntView x2) {
312 if (x0 == x1) {
313 SqrOps ops;
314 return PowDom<SqrOps>::post(home,x0,x2,ops);
315 }
316 if (x0 == x2)
317 return MultZeroOne<IntView,PC_INT_DOM>::post(home,x0,x1);
318 if (x1 == x2)
319 return MultZeroOne<IntView,PC_INT_DOM>::post(home,x1,x0);
320 if (pos(x0)) {
321 if (pos(x1) || pos(x2)) goto post_ppp;
322 if (neg(x1) || neg(x2)) goto post_pnn;
323 } else if (neg(x0)) {
324 if (neg(x1) || pos(x2)) goto post_nnp;
325 if (pos(x1) || neg(x2)) goto post_npn;
326 } else if (pos(x1)) {
327 if (pos(x2)) goto post_ppp;
328 if (neg(x2)) goto post_npn;
329 } else if (neg(x1)) {
330 if (pos(x2)) goto post_nnp;
331 if (neg(x2)) goto post_pnn;
332 }
333 {
334 long long int a = mll(x0.min(),x1.min());
335 long long int b = mll(x0.min(),x1.max());
336 long long int c = mll(x0.max(),x1.min());
337 long long int d = mll(x0.max(),x1.max());
338 GECODE_ME_CHECK(x2.gq(home,std::min(std::min(a,b),std::min(c,d))));
339 GECODE_ME_CHECK(x2.lq(home,std::max(std::max(a,b),std::max(c,d))));
340 (void) new (home) MultDom(home,x0,x1,x2);
341 }
342 return ES_OK;
343
344 post_ppp:
345 return MultPlusDom<IntView,IntView,IntView>
346 ::post(home,x0,x1,x2);
347 post_nnp:
348 return MultPlusDom<MinusView,MinusView,IntView>
349 ::post(home,MinusView(x0),MinusView(x1),x2);
350 post_pnn:
351 std::swap(x0,x1);
352 post_npn:
353 return MultPlusDom<MinusView,IntView,MinusView>
354 ::post(home,MinusView(x0),x1,MinusView(x2));
355 }
356
357}}}
358
359// STATISTICS: int-prop
360