main page
modules
namespaces
classes
files
Gecode home
Generated on Sat Nov 9 2013 19:18:27 for Gecode by
doxygen
1.8.4
gecode
int
arithmetic
mult.cpp
Go to the documentation of this file.
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
* Last modified:
10
* $Date: 2013-02-14 16:29:11 +0100 (Thu, 14 Feb 2013) $ by $Author: schulte $
11
* $Revision: 13292 $
12
*
13
* This file is part of Gecode, the generic constraint
14
* development environment:
15
* http://www.gecode.org
16
*
17
* Permission is hereby granted, free of charge, to any person obtaining
18
* a copy of this software and associated documentation files (the
19
* "Software"), to deal in the Software without restriction, including
20
* without limitation the rights to use, copy, modify, merge, publish,
21
* distribute, sublicense, and/or sell copies of the Software, and to
22
* permit persons to whom the Software is furnished to do so, subject to
23
* the following conditions:
24
*
25
* The above copyright notice and this permission notice shall be
26
* included in all copies or substantial portions of the Software.
27
*
28
* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
29
* EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
30
* MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
31
* NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
32
* LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
33
* OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
34
* WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
35
*
36
*/
37
38
#include <
gecode/int/arithmetic.hh
>
39
40
namespace
Gecode {
namespace
Int {
namespace
Arithmetic {
41
42
/*
43
* Bounds consistent multiplication
44
*
45
*/
46
Actor*
47
MultBnd::copy
(
Space
& home,
bool
share) {
48
return
new
(home)
MultBnd
(home,share,*
this
);
49
}
50
51
ExecStatus
52
MultBnd::propagate
(
Space
& home,
const
ModEventDelta
&) {
53
if
(
pos
(
x0
)) {
54
if
(
pos
(
x1
) ||
pos
(
x2
))
goto
rewrite_ppp;
55
if
(
neg
(
x1
) ||
neg
(
x2
))
goto
rewrite_pnn;
56
goto
prop_pxx;
57
}
58
if
(
neg
(
x0
)) {
59
if
(
neg
(
x1
) ||
pos
(
x2
))
goto
rewrite_nnp;
60
if
(
pos
(
x1
) ||
neg
(
x2
))
goto
rewrite_npn;
61
goto
prop_nxx;
62
}
63
if
(
pos
(
x1
)) {
64
if
(
pos
(
x2
))
goto
rewrite_ppp;
65
if
(
neg
(
x2
))
goto
rewrite_npn;
66
goto
prop_xpx;
67
}
68
if
(
neg
(
x1
)) {
69
if
(
pos
(
x2
))
goto
rewrite_nnp;
70
if
(
neg
(
x2
))
goto
rewrite_pnn;
71
goto
prop_xnx;
72
}
73
74
assert(
any
(
x0
) &&
any
(
x1
));
75
GECODE_ME_CHECK
(
x2
.
lq
(home,
std::max
(
mll
(
x0
.
max
(),
x1
.
max
()),
76
mll
(
x0
.
min
(),
x1
.
min
()))));
77
GECODE_ME_CHECK
(
x2
.
gq
(home,
std::min
(
mll
(
x0
.
min
(),
x1
.
max
()),
78
mll
(
x0
.
max
(),
x1
.
min
()))));
79
80
if
(
x0
.
assigned
()) {
81
assert((
x0
.
val
() == 0) && (
x2
.
val
() == 0));
82
return
home.
ES_SUBSUMED
(*
this
);
83
}
84
85
if
(
x1
.
assigned
()) {
86
assert((
x1
.
val
() == 0) && (
x2
.
val
() == 0));
87
return
home.
ES_SUBSUMED
(*
this
);
88
}
89
90
return
ES_NOFIX
;
91
92
prop_xpx:
93
std::swap(
x0
,
x1
);
94
prop_pxx:
95
assert(
pos
(
x0
) &&
any
(
x1
) &&
any
(
x2
));
96
97
GECODE_ME_CHECK
(
x2
.
lq
(home,
mll
(
x0
.
max
(),
x1
.
max
())));
98
GECODE_ME_CHECK
(
x2
.
gq
(home,
mll
(
x0
.
max
(),
x1
.
min
())));
99
100
if
(
pos
(
x2
))
goto
rewrite_ppp;
101
if
(
neg
(
x2
))
goto
rewrite_pnn;
102
103
GECODE_ME_CHECK
(
x1
.
lq
(home,
floor_div_xp
(
x2
.
max
(),
x0
.
min
())));
104
GECODE_ME_CHECK
(
x1
.
gq
(home,
ceil_div_xp
(
x2
.
min
(),
x0
.
min
())));
105
106
if
(
x0
.
assigned
() &&
x1
.
assigned
()) {
107
GECODE_ME_CHECK
(
x2
.
eq
(home,
mll
(
x0
.
val
(),
x1
.
val
())));
108
return
home.
ES_SUBSUMED
(*
this
);
109
}
110
111
return
ES_NOFIX
;
112
113
prop_xnx:
114
std::swap(
x0
,
x1
);
115
prop_nxx:
116
assert(
neg
(
x0
) &&
any
(
x1
) &&
any
(
x2
));
117
118
GECODE_ME_CHECK
(
x2
.
lq
(home,
mll
(
x0
.
min
(),
x1
.
min
())));
119
GECODE_ME_CHECK
(
x2
.
gq
(home,
mll
(
x0
.
min
(),
x1
.
max
())));
120
121
if
(
pos
(
x2
))
goto
rewrite_nnp;
122
if
(
neg
(
x2
))
goto
rewrite_npn;
123
124
GECODE_ME_CHECK
(
x1
.
lq
(home,
floor_div_xx
(
x2
.
min
(),
x0
.
max
())));
125
GECODE_ME_CHECK
(
x1
.
gq
(home,
ceil_div_xx
(
x2
.
max
(),
x0
.
max
())));
126
127
if
(
x0
.
assigned
() &&
x1
.
assigned
()) {
128
GECODE_ME_CHECK
(
x2
.
eq
(home,
mll
(
x0
.
val
(),
x1
.
val
())));
129
return
home.
ES_SUBSUMED
(*
this
);
130
}
131
132
return
ES_NOFIX
;
133
134
rewrite_ppp:
135
GECODE_REWRITE
(*
this
,(
MultPlusBnd<IntView,IntView,IntView>
136
::
post
(home(*
this
),
x0
,
x1
,
x2
)));
137
rewrite_nnp:
138
GECODE_REWRITE
(*
this
,(
MultPlusBnd<MinusView,MinusView,IntView>
139
::
post
(home(*
this
),
MinusView
(
x0
),
MinusView
(
x1
),
x2
)));
140
rewrite_pnn:
141
std::swap(
x0
,
x1
);
142
rewrite_npn:
143
GECODE_REWRITE
(*
this
,(
MultPlusBnd<MinusView,IntView,MinusView>
144
::
post
(home(*
this
),
MinusView
(
x0
),
x1
,
MinusView
(
x2
))));
145
}
146
147
ExecStatus
148
MultBnd::post
(
Home
home,
IntView
x0,
IntView
x1,
IntView
x2) {
149
if
(
same
(x0,x1)) {
150
SqrOps
ops;
151
return
PowBnd<SqrOps>::post
(home,x0,x2,ops);
152
}
153
if
(
same
(x0,x2))
154
return
MultZeroOne<IntView,PC_INT_BND>::post
(home,x0,x1);
155
if
(
same
(x1,x2))
156
return
MultZeroOne<IntView,PC_INT_BND>::post
(home,x1,x0);
157
if
(
pos
(x0)) {
158
if
(
pos
(x1) ||
pos
(x2))
goto
post_ppp;
159
if
(
neg
(x1) ||
neg
(x2))
goto
post_pnn;
160
}
else
if
(
neg
(x0)) {
161
if
(
neg
(x1) ||
pos
(x2))
goto
post_nnp;
162
if
(
pos
(x1) ||
neg
(x2))
goto
post_npn;
163
}
else
if
(
pos
(x1)) {
164
if
(
pos
(x2))
goto
post_ppp;
165
if
(
neg
(x2))
goto
post_npn;
166
}
else
if
(
neg
(x1)) {
167
if
(
pos
(x2))
goto
post_nnp;
168
if
(
neg
(x2))
goto
post_pnn;
169
}
170
{
171
long
long
int
a
=
mll
(x0.
min
(),x1.
min
());
172
long
long
int
b
=
mll
(x0.
min
(),x1.
max
());
173
long
long
int
c
=
mll
(x0.
max
(),x1.
min
());
174
long
long
int
d
=
mll
(x0.
max
(),x1.
max
());
175
GECODE_ME_CHECK
(x2.
gq
(home,
std::min
(
std::min
(a,b),
std::min
(c,d))));
176
GECODE_ME_CHECK
(x2.
lq
(home,
std::max
(
std::max
(a,b),
std::max
(c,d))));
177
(void)
new
(home)
MultBnd
(home,x0,x1,x2);
178
}
179
return
ES_OK
;
180
181
post_ppp:
182
return
MultPlusBnd<IntView,IntView,IntView>
183
::post
(home,x0,x1,x2);
184
post_nnp:
185
return
MultPlusBnd<MinusView,MinusView,IntView>
186
::post
(home,
MinusView
(x0),
MinusView
(x1),x2);
187
post_pnn:
188
std::swap(x0,x1);
189
post_npn:
190
return
MultPlusBnd<MinusView,IntView,MinusView>
191
::post
(home,
MinusView
(x0),x1,
MinusView
(x2));
192
}
193
194
195
196
/*
197
* Domain consistent multiplication
198
*
199
*/
200
Actor
*
201
MultDom::copy
(
Space
& home,
bool
share) {
202
return
new
(home)
MultDom
(home,share,*
this
);
203
}
204
205
PropCost
206
MultDom::cost
(
const
Space
&,
const
ModEventDelta
& med)
const
{
207
if
(
IntView::me
(med) ==
ME_INT_DOM
)
208
return
PropCost::ternary
(
PropCost::HI
);
209
else
210
return
PropCost::ternary
(
PropCost::LO
);
211
}
212
213
ExecStatus
214
MultDom::propagate
(
Space
& home,
const
ModEventDelta
& med) {
215
if
(
IntView::me
(med) !=
ME_INT_DOM
) {
216
if
(
pos
(
x0
)) {
217
if
(
pos
(
x1
) ||
pos
(
x2
))
goto
rewrite_ppp;
218
if
(
neg
(
x1
) ||
neg
(
x2
))
goto
rewrite_pnn;
219
goto
prop_pxx;
220
}
221
if
(
neg
(
x0
)) {
222
if
(
neg
(
x1
) ||
pos
(
x2
))
goto
rewrite_nnp;
223
if
(
pos
(
x1
) ||
neg
(
x2
))
goto
rewrite_npn;
224
goto
prop_nxx;
225
}
226
if
(
pos
(
x1
)) {
227
if
(
pos
(
x2
))
goto
rewrite_ppp;
228
if
(
neg
(
x2
))
goto
rewrite_npn;
229
goto
prop_xpx;
230
}
231
if
(
neg
(
x1
)) {
232
if
(
pos
(
x2
))
goto
rewrite_nnp;
233
if
(
neg
(
x2
))
goto
rewrite_pnn;
234
goto
prop_xnx;
235
}
236
237
assert(
any
(
x0
) &&
any
(
x1
));
238
GECODE_ME_CHECK
(
x2
.
lq
(home,
std::max
(
mll
(
x0
.
max
(),
x1
.
max
()),
239
mll
(
x0
.
min
(),
x1
.
min
()))));
240
GECODE_ME_CHECK
(
x2
.
gq
(home,
std::min
(
mll
(
x0
.
min
(),
x1
.
max
()),
241
mll
(
x0
.
max
(),
x1
.
min
()))));
242
243
if
(
x0
.
assigned
()) {
244
assert((
x0
.
val
() == 0) && (
x2
.
val
() == 0));
245
return
home.
ES_SUBSUMED
(*
this
);
246
}
247
248
if
(
x1
.
assigned
()) {
249
assert((
x1
.
val
() == 0) && (
x2
.
val
() == 0));
250
return
home.
ES_SUBSUMED
(*
this
);
251
}
252
253
return
home.
ES_NOFIX_PARTIAL
(*
this
,
IntView::med
(
ME_INT_DOM
));
254
255
prop_xpx:
256
std::swap(
x0
,
x1
);
257
prop_pxx:
258
assert(
pos
(
x0
) &&
any
(
x1
) &&
any
(
x2
));
259
260
GECODE_ME_CHECK
(
x2
.
lq
(home,
mll
(
x0
.
max
(),
x1
.
max
())));
261
GECODE_ME_CHECK
(
x2
.
gq
(home,
mll
(
x0
.
max
(),
x1
.
min
())));
262
263
if
(
pos
(
x2
))
goto
rewrite_ppp;
264
if
(
neg
(
x2
))
goto
rewrite_pnn;
265
266
GECODE_ME_CHECK
(
x1
.
lq
(home,
floor_div_xp
(
x2
.
max
(),
x0
.
min
())));
267
GECODE_ME_CHECK
(
x1
.
gq
(home,
ceil_div_xp
(
x2
.
min
(),
x0
.
min
())));
268
269
if
(
x0
.
assigned
() &&
x1
.
assigned
()) {
270
GECODE_ME_CHECK
(
x2
.
eq
(home,
mll
(
x0
.
val
(),
x1
.
val
())));
271
return
home.
ES_SUBSUMED
(*
this
);
272
}
273
274
return
home.
ES_NOFIX_PARTIAL
(*
this
,
IntView::med
(
ME_INT_DOM
));
275
276
prop_xnx:
277
std::swap(
x0
,
x1
);
278
prop_nxx:
279
assert(
neg
(
x0
) &&
any
(
x1
) &&
any
(
x2
));
280
281
GECODE_ME_CHECK
(
x2
.
lq
(home,
mll
(
x0
.
min
(),
x1
.
min
())));
282
GECODE_ME_CHECK
(
x2
.
gq
(home,
mll
(
x0
.
min
(),
x1
.
max
())));
283
284
if
(
pos
(
x2
))
goto
rewrite_nnp;
285
if
(
neg
(
x2
))
goto
rewrite_npn;
286
287
GECODE_ME_CHECK
(
x1
.
lq
(home,
floor_div_xx
(
x2
.
min
(),
x0
.
max
())));
288
GECODE_ME_CHECK
(
x1
.
gq
(home,
ceil_div_xx
(
x2
.
max
(),
x0
.
max
())));
289
290
if
(
x0
.
assigned
() &&
x1
.
assigned
()) {
291
GECODE_ME_CHECK
(
x2
.
eq
(home,
mll
(
x0
.
val
(),
x1
.
val
())));
292
return
home.
ES_SUBSUMED
(*
this
);
293
}
294
295
return
home.
ES_NOFIX_PARTIAL
(*
this
,
IntView::med
(
ME_INT_DOM
));
296
297
rewrite_ppp:
298
GECODE_REWRITE
(*
this
,(
MultPlusDom<IntView,IntView,IntView>
299
::
post
(home(*
this
),
x0
,
x1
,
x2
)));
300
rewrite_nnp:
301
GECODE_REWRITE
(*
this
,(
MultPlusDom<MinusView,MinusView,IntView>
302
::
post
(home(*
this
),
303
MinusView
(
x0
),
MinusView
(
x1
),
x2
)));
304
rewrite_pnn:
305
std::swap(
x0
,
x1
);
306
rewrite_npn:
307
GECODE_REWRITE
(*
this
,(
MultPlusDom<MinusView,IntView,MinusView>
308
::
post
(home(*
this
),
309
MinusView
(
x0
),
x1
,
MinusView
(
x2
))));
310
}
311
return
prop_mult_dom<IntView>(home,*
this
,
x0
,
x1
,
x2
);
312
}
313
314
ExecStatus
315
MultDom::post
(
Home
home,
IntView
x0,
IntView
x1,
IntView
x2) {
316
if
(
same
(x0,x1)) {
317
SqrOps
ops;
318
return
PowDom<SqrOps>::post
(home,x0,x2,ops);
319
}
320
if
(
same
(x0,x2))
321
return
MultZeroOne<IntView,PC_INT_DOM>::post
(home,x0,x1);
322
if
(
same
(x1,x2))
323
return
MultZeroOne<IntView,PC_INT_DOM>::post
(home,x1,x0);
324
if
(
pos
(x0)) {
325
if
(
pos
(x1) ||
pos
(x2))
goto
post_ppp;
326
if
(
neg
(x1) ||
neg
(x2))
goto
post_pnn;
327
}
else
if
(
neg
(x0)) {
328
if
(
neg
(x1) ||
pos
(x2))
goto
post_nnp;
329
if
(
pos
(x1) ||
neg
(x2))
goto
post_npn;
330
}
else
if
(
pos
(x1)) {
331
if
(
pos
(x2))
goto
post_ppp;
332
if
(
neg
(x2))
goto
post_npn;
333
}
else
if
(
neg
(x1)) {
334
if
(
pos
(x2))
goto
post_nnp;
335
if
(
neg
(x2))
goto
post_pnn;
336
}
337
{
338
long
long
int
a
=
mll
(x0.
min
(),x1.
min
());
339
long
long
int
b
=
mll
(x0.
min
(),x1.
max
());
340
long
long
int
c
=
mll
(x0.
max
(),x1.
min
());
341
long
long
int
d
=
mll
(x0.
max
(),x1.
max
());
342
GECODE_ME_CHECK
(x2.
gq
(home,
std::min
(
std::min
(a,b),
std::min
(c,d))));
343
GECODE_ME_CHECK
(x2.
lq
(home,
std::max
(
std::max
(a,b),
std::max
(c,d))));
344
(void)
new
(home)
MultDom
(home,x0,x1,x2);
345
}
346
return
ES_OK
;
347
348
post_ppp:
349
return
MultPlusDom<IntView,IntView,IntView>
350
::post
(home,x0,x1,x2);
351
post_nnp:
352
return
MultPlusDom<MinusView,MinusView,IntView>
353
::post
(home,
MinusView
(x0),
MinusView
(x1),x2);
354
post_pnn:
355
std::swap(x0,x1);
356
post_npn:
357
return
MultPlusDom<MinusView,IntView,MinusView>
358
::post
(home,
MinusView
(x0),x1,
MinusView
(x2));
359
}
360
361
}}}
362
363
// STATISTICS: int-prop
364