3
* Christian Schulte <schulte@gecode.org>
6
* Christian Schulte, 2004
9
* $Date: 2005-11-23 21:29:36 +0100 (Wed, 23 Nov 2005) $ by $Author: schulte $
12
* This file is part of Gecode, the generic constraint
13
* development environment:
14
* http://www.gecode.org
16
* See the file "LICENSE" for information on usage and
17
* redistribution of this file, and for a
18
* DISCLAIMER OF ALL WARRANTIES.
24
namespace Gecode { namespace Int { namespace Arithmetic {
27
* Arithmetic help functions
31
/// Multiply \a a and \a b as double
34
return static_cast<double>(a)*static_cast<double>(b);
37
/// Compute \f$\lfloor x/y\rfloor\f$
40
return static_cast<int>(floor(static_cast<double>(x) /
41
static_cast<double>(y)));
44
/// Compute \f$\lceil x/y\rceil\f$
47
return static_cast<int>(ceil(static_cast<double>(x) /
48
static_cast<double>(y)));
51
/// Test whether \a x is postive
57
/// Test whether \a x is negative
63
/// Test whether \a x is neither positive nor negative
67
return (x.min() <= 0) && (x.max() >= 0);
71
/// Performs \a TELL operation and sets \a mod, if modified
72
#define GECODE_CM(TELL) \
74
ModEvent me = (TELL); \
75
if (me_failed(me)) return ES_FAILED; \
76
if (me_modified(me)) mod = true; \
81
* Positive bounds-consistent squaring
84
template <class VA, class VB>
86
SquarePlus<VA,VB>::SquarePlus(Space* home, VA y0, VB y1)
87
: Propagator(home), x0(y0), x1(y1) {
88
x0.subscribe(home,this,PC_INT_BND);
89
x1.subscribe(home,this,PC_INT_BND);
92
template <class VA, class VB>
93
forceinline ExecStatus
94
SquarePlus<VA,VB>::post(Space* home, VA x0, VB x1) {
95
(void) new (home) SquarePlus<VA,VB>(home,x0,x1);
99
template <class VA, class VB>
101
SquarePlus<VA,VB>::SquarePlus(Space* home, bool share, SquarePlus<VA,VB>& p)
102
: Propagator(home,share,p) {
103
x0.update(home,share,p.x0);
104
x1.update(home,share,p.x1);
107
template <class VA, class VB>
109
SquarePlus<VA,VB>::copy(Space* home, bool share) {
110
return new (home) SquarePlus<VA,VB>(home,share,*this);
113
template <class VA, class VB>
115
SquarePlus<VA,VB>::cost(void) const {
116
return PC_TERNARY_HI;
119
template <class VA, class VB>
121
SquarePlus<VA,VB>::propagate(Space* home) {
125
GECODE_CM(x0.lq(home,floor(sqrt(static_cast<double>(x1.max())))));
126
GECODE_CM(x0.gq(home,ceil(sqrt(static_cast<double>(x1.min())))));
127
GECODE_CM(x1.lq(home,x0.max()*x0.max()));
128
GECODE_CM(x1.gq(home,x0.min()*x0.min()));
130
return x0.assigned() ? ES_SUBSUMED : ES_FIX;
133
template <class VA, class VB>
134
SquarePlus<VA,VB>::~SquarePlus(void) {
135
x0.cancel(this,PC_INT_BND);
136
x1.cancel(this,PC_INT_BND);
141
* Bounds-consistent Square
145
template <class View>
147
Square<View>::Square(Space* home, View x0, View x1)
148
: BinaryPropagator<View,PC_INT_BND>(home,x0,x1) {}
150
template <class View>
151
forceinline ExecStatus
152
Square<View>::post(Space* home, View x0, View x1) {
153
GECODE_ME_CHECK(x1.gq(home,0));
154
GECODE_ME_CHECK(x0.lq(home,floor(sqrt(static_cast<double>(Limits::Int::int_max)))));
156
return SquarePlus<IntView,IntView>::post(home,x0,x1);
158
return SquarePlus<MinusView,IntView>::post(home,x0,x1);
159
(void) new (home) Square<View>(home,x0,x1);
163
template <class View>
165
Square<View>::Square(Space* home, bool share, Square<View>& p)
166
: BinaryPropagator<View,PC_INT_BND>(home,share,p) {}
168
template <class View>
170
Square<View>::copy(Space* home, bool share) {
171
return new (home) Square<View>(home,share,*this);
174
template <class View>
176
Square<View>::cost(void) const {
180
template <class View>
182
Square<View>::propagate(Space* home) {
184
assert(x1.min() >= 0);
186
return (SquarePlus<IntView,IntView>::post(home,x0,x1)
187
== ES_FAILED) ? ES_FAILED : ES_SUBSUMED;
189
return (SquarePlus<MinusView,IntView>::post(home,x0,x1)
190
== ES_FAILED) ? ES_FAILED : ES_SUBSUMED;
195
GECODE_CM(x1.lq(home,std::max(x0.min()*x0.min(),x0.max()*x0.max())));
196
int s = static_cast<int>(floor(sqrt(static_cast<double>(x1.max()))));
197
GECODE_CM(x0.gq(home,-s));
198
GECODE_CM(x0.lq(home,s));
200
return x0.assigned() && x1.assigned() ? ES_SUBSUMED : ES_FIX;
205
* Positive bounds-consistent multiplication
208
template <class VA, class VB, class VC>
210
MultPlus<VA,VB,VC>::MultPlus(Space* home, VA y0, VB y1, VC y2)
211
: Propagator(home), x0(y0), x1(y1), x2(y2) {
212
x0.subscribe(home,this,PC_INT_BND);
213
x1.subscribe(home,this,PC_INT_BND);
214
x2.subscribe(home,this,PC_INT_BND);
217
template <class VA, class VB, class VC>
219
MultPlus<VA,VB,VC>::post(Space* home, VA x0, VB x1, VC x2) {
220
GECODE_ME_CHECK(x0.gr(home,0));
221
GECODE_ME_CHECK(x1.gr(home,0));
222
GECODE_ME_CHECK(x2.gr(home,0));
223
(void) new (home) MultPlus<VA,VB,VC>(home,x0,x1,x2);
227
template <class VA, class VB, class VC>
229
MultPlus<VA,VB,VC>::MultPlus(Space* home, bool share, MultPlus<VA,VB,VC>& p)
230
: Propagator(home,share,p) {
231
x0.update(home,share,p.x0);
232
x1.update(home,share,p.x1);
233
x2.update(home,share,p.x2);
236
template <class VA, class VB, class VC>
238
MultPlus<VA,VB,VC>::copy(Space* home, bool share) {
239
return new (home) MultPlus<VA,VB,VC>(home,share,*this);
242
template <class VA, class VB, class VC>
244
MultPlus<VA,VB,VC>::cost(void) const {
245
return PC_TERNARY_HI;
248
template <class VA, class VB, class VC>
250
MultPlus<VA,VB,VC>::propagate(Space* home) {
251
assert(p(x0) && p(x1) && p(x2));
255
GECODE_CM(x2.lq(home,m(x0.max(),x1.max())));
256
GECODE_CM(x2.gq(home,m(x0.min(),x1.min())));
257
GECODE_CM(x0.lq(home,f_d(x2.max(),x1.min())));
258
GECODE_CM(x0.gq(home,c_d(x2.min(),x1.max())));
259
GECODE_CM(x1.lq(home,f_d(x2.max(),x0.min())));
260
GECODE_CM(x1.gq(home,c_d(x2.min(),x0.max())));
262
return x0.assigned() && x1.assigned() ? ES_SUBSUMED : ES_FIX;
265
template <class VA, class VB, class VC>
266
MultPlus<VA,VB,VC>::~MultPlus(void) {
267
x0.cancel(this,PC_INT_BND);
268
x1.cancel(this,PC_INT_BND);
269
x2.cancel(this,PC_INT_BND);
274
* Bounds-consistent multiplication
278
template <class View>
280
Mult<View>::Mult(Space* home, View x0, View x1, View x2)
281
: TernaryPropagator<View,PC_INT_BND>(home,x0,x1,x2) {}
283
template <class View>
285
Mult<View>::Mult(Space* home, bool share, Mult<View>& p)
286
: TernaryPropagator<View,PC_INT_BND>(home,share,p) {}
288
template <class View>
290
Mult<View>::copy(Space* home, bool share) {
291
return new (home) Mult<View>(home,share,*this);
294
template <class View>
296
Mult<View>::cost(void) const {
297
return PC_TERNARY_HI;
300
template <class View>
302
Mult<View>::propagate(Space* home) {
304
if (p(x1) || p(x2)) goto rewrite_ppp;
305
if (n(x1) || n(x2)) goto rewrite_pnn;
309
if (n(x1) || p(x2)) goto rewrite_nnp;
310
if (p(x1) || n(x2)) goto rewrite_npn;
314
if (p(x2)) goto rewrite_ppp;
315
if (n(x2)) goto rewrite_npn;
319
if (p(x2)) goto rewrite_nnp;
320
if (n(x2)) goto rewrite_pnn;
324
assert(x(x0) && x(x1));
325
GECODE_ME_CHECK(x2.lq(home,std::max(m(x0.max(),x1.max()),
326
m(x0.min(),x1.min()))));
327
GECODE_ME_CHECK(x2.gq(home,std::min(m(x0.min(),x1.max()),
328
m(x0.max(),x1.min()))));
331
assert((x0.val() == 0) && (x2.val() == 0));
336
assert((x1.val() == 0) && (x2.val() == 0));
345
assert(p(x0) && x(x1) && x(x2));
347
GECODE_ME_CHECK(x2.lq(home,m(x0.max(),x1.max())));
348
GECODE_ME_CHECK(x2.gq(home,m(x0.max(),x1.min())));
350
if (p(x2)) goto rewrite_ppp;
351
if (n(x2)) goto rewrite_pnn;
353
GECODE_ME_CHECK(x1.lq(home,f_d(x2.max(),x0.min())));
354
GECODE_ME_CHECK(x1.gq(home,c_d(x2.min(),x0.min())));
356
if (x0.assigned() && x1.assigned()) {
357
GECODE_ME_CHECK(x2.eq(home,m(x0.val(),x1.val())));
366
assert(n(x0) && x(x1) && x(x2));
368
GECODE_ME_CHECK(x2.lq(home,m(x0.min(),x1.min())));
369
GECODE_ME_CHECK(x2.gq(home,m(x0.min(),x1.max())));
371
if (p(x2)) goto rewrite_nnp;
372
if (n(x2)) goto rewrite_npn;
374
GECODE_ME_CHECK(x1.lq(home,f_d(x2.min(),x0.max())));
375
GECODE_ME_CHECK(x1.gq(home,c_d(x2.max(),x0.max())));
377
if (x0.assigned() && x1.assigned()) {
378
GECODE_ME_CHECK(x2.eq(home,m(x0.val(),x1.val())));
385
return (MultPlus<IntView,IntView,IntView>::post(home,x0,x1,x2)
386
== ES_FAILED) ? ES_FAILED : ES_SUBSUMED;
389
return (MultPlus<MinusView,MinusView,IntView>::post(home,x0,x1,x2)
390
== ES_FAILED) ? ES_FAILED : ES_SUBSUMED;
395
return (MultPlus<MinusView,IntView,MinusView>::post(home,x0,x1,x2)
396
== ES_FAILED) ? ES_FAILED : ES_SUBSUMED;
400
template <class View>
402
Mult<View>::post(Space* home, View x0, View x1, View x2) {
404
return Square<View>::post(home,x0,x2);
406
if (p(x1) || p(x2)) goto post_ppp;
407
if (n(x1) || n(x2)) goto post_pnn;
409
if (n(x1) || p(x2)) goto post_nnp;
410
if (p(x1) || n(x2)) goto post_npn;
412
if (p(x2)) goto post_ppp;
413
if (n(x2)) goto post_npn;
415
if (p(x2)) goto post_nnp;
416
if (n(x2)) goto post_pnn;
418
(void) new (home) Mult<View>(home,x0,x1,x2);
422
return MultPlus<IntView,IntView,IntView>::post(home,x0,x1,x2);
424
return MultPlus<MinusView,MinusView,IntView>::post(home,x0,x1,x2);
428
return MultPlus<MinusView,IntView,MinusView>::post(home,x0,x1,x2);
436
// STATISTICS: int-prop