main page
modules
namespaces
classes
files
Gecode home
Generated on Tue Oct 22 2013 00:49:02 for Gecode by
doxygen
1.8.4
gecode
int
arithmetic
nroot.hpp
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, 2012
8
*
9
* Last modified:
10
* $Date: 2013-03-12 20:08:33 +0100 (Tue, 12 Mar 2013) $ by $Author: schulte $
11
* $Revision: 13510 $
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/rel.hh
>
39
40
#include <climits>
41
#include <algorithm>
42
43
namespace
Gecode {
namespace
Int {
namespace
Arithmetic {
44
45
/*
46
* Bounds consistent nth root
47
*
48
*/
49
50
template
<
class
Ops>
51
forceinline
ExecStatus
52
prop_nroot_bnd
(
Space
& home,
IntView
x0,
IntView
x1,
const
Ops& ops) {
53
bool
mod
;
54
do
{
55
mod =
false
;
56
{
57
ModEvent
me = x1.
lq
(home,ops.fnroot(x0.
max
()));
58
if
(
me_failed
(me))
return
ES_FAILED
;
59
mod |=
me_modified
(me);
60
}
61
{
62
ModEvent
me = x1.
gq
(home,ops.fnroot(x0.
min
()));
63
if
(
me_failed
(me))
return
ES_FAILED
;
64
mod |=
me_modified
(me);
65
}
66
{
67
ModEvent
me = x0.
le
(home,ops.tpow(x1.
max
()+1));
68
if
(
me_failed
(me))
return
ES_FAILED
;
69
mod |=
me_modified
(me);
70
}
71
{
72
ModEvent
me = x0.
gq
(home,ops.pow(x1.
min
()));
73
if
(
me_failed
(me))
return
ES_FAILED
;
74
mod |=
me_modified
(me);
75
}
76
}
while
(mod);
77
return
ES_OK
;
78
}
79
80
template
<
class
Ops>
81
forceinline
82
NrootBnd<Ops>::NrootBnd
(
Home
home,
IntView
x0,
IntView
x1,
const
Ops& o)
83
:
BinaryPropagator
<
IntView
,
PC_INT_BND
>(home,x0,x1),
84
ops(o) {
85
}
86
87
template
<
class
Ops>
88
forceinline
ExecStatus
89
NrootBnd<Ops>::post
(
Home
home,
IntView
x0,
IntView
x1, Ops ops) {
90
GECODE_ME_CHECK
(x0.
gq
(home,0));
91
GECODE_ME_CHECK
(x1.
gq
(home,0));
92
93
if
(static_cast<unsigned int>(ops.exp()) >=
sizeof
(
int
) * CHAR_BIT) {
94
// The integer limits allow only 0 and 1 for x1
95
GECODE_ME_CHECK
(x1.
lq
(home,1));
96
}
97
98
if
(ops.exp() == 0) {
99
GECODE_ME_CHECK
(x1.
eq
(home,1));
100
return
ES_OK
;
101
}
else
if
(ops.exp() == 1) {
102
return
Rel::EqBnd<IntView,IntView>::post
(home,x0,x1);
103
}
104
105
if
(
same
(x0,x1)) {
106
assert(ops.exp() > 1);
107
GECODE_ME_CHECK
(x1.
lq
(home,1));
108
return
ES_OK
;
109
}
110
111
// Limits values such that no overflow can occur
112
GECODE_ME_CHECK
(x1.
lq
(home,ops.fnroot(
Limits::max
)));
113
114
GECODE_ES_CHECK
(prop_nroot_bnd<Ops>(home,x0,x1,ops));
115
(void)
new
(home)
NrootBnd
(home,x0,x1,ops);
116
117
return
ES_OK
;
118
}
119
120
template
<
class
Ops>
121
forceinline
122
NrootBnd<Ops>::NrootBnd
(
Space
& home,
bool
share,
NrootBnd<Ops>
&
p
)
123
:
BinaryPropagator
<
IntView
,
PC_INT_BND
>(home,share,p),
124
ops(p.ops) {}
125
126
template
<
class
Ops>
127
Actor
*
128
NrootBnd<Ops>::copy
(
Space
& home,
bool
share) {
129
return
new
(home)
NrootBnd<Ops>
(home,share,*
this
);
130
}
131
132
template
<
class
Ops>
133
ExecStatus
134
NrootBnd<Ops>::propagate
(
Space
& home,
const
ModEventDelta
&) {
135
GECODE_ES_CHECK
(
prop_nroot_bnd
(home,x0,x1,ops));
136
return
x1.assigned() ? home.
ES_SUBSUMED
(*
this
) :
ES_FIX
;
137
}
138
139
140
/*
141
* Domain consistent nth root
142
*
143
*/
145
template
<
class
Ops>
146
class
RangesMapPow
{
147
protected
:
149
Ops
ops
;
150
public
:
152
forceinline
RangesMapPow
(
const
Ops& o) :
ops
(o) {}
154
forceinline
int
min
(
int
x
)
const
{
155
return
ops
.pow(x);
156
}
158
forceinline
int
max
(
int
x
)
const
{
159
return
ops
.tpow(x+1)-1;
160
}
161
};
162
164
template
<
class
Ops>
165
class
RangesMapNroot
{
166
protected
:
168
Ops
ops
;
169
public
:
171
forceinline
RangesMapNroot
(
const
Ops& o) :
ops
(o) {}
173
forceinline
int
min
(
int
x
)
const
{
174
return
ops
.fnroot(x);
175
}
177
forceinline
int
max
(
int
x
)
const
{
178
return
ops
.fnroot(x);
179
}
180
};
181
182
template
<
class
Ops>
183
forceinline
184
NrootDom<Ops>::NrootDom
(
Home
home,
IntView
x0,
IntView
x1,
const
Ops& o)
185
:
BinaryPropagator
<
IntView
,
PC_INT_DOM
>(home,x0,x1),
186
ops(o) {}
187
188
template
<
class
Ops>
189
forceinline
ExecStatus
190
NrootDom<Ops>::post
(
Home
home,
IntView
x0,
IntView
x1, Ops ops) {
191
GECODE_ME_CHECK
(x0.
gq
(home,0));
192
GECODE_ME_CHECK
(x1.
gq
(home,0));
193
194
if
(static_cast<unsigned int>(ops.exp()) >=
sizeof
(
int
) * CHAR_BIT) {
195
// The integer limits allow only 0 and 1 for x1
196
GECODE_ME_CHECK
(x1.
lq
(home,1));
197
}
198
199
if
(ops.exp() == 0) {
200
GECODE_ME_CHECK
(x1.
eq
(home,1));
201
return
ES_OK
;
202
}
else
if
(ops.exp() == 1) {
203
return
Rel::EqDom<IntView,IntView>::post
(home,x0,x1);
204
}
205
206
if
(
same
(x0,x1)) {
207
assert(ops.exp() > 1);
208
GECODE_ME_CHECK
(x1.
lq
(home,1));
209
return
ES_OK
;
210
}
211
212
// Limits values such that no overflow can occur
213
GECODE_ME_CHECK
(x1.
lq
(home,ops.fnroot(
Limits::max
)));
214
215
GECODE_ES_CHECK
(
prop_nroot_bnd
(home,x0,x1,ops));
216
(void)
new
(home)
NrootDom<Ops>
(home,x0,x1,ops);
217
218
return
ES_OK
;
219
}
220
221
template
<
class
Ops>
222
forceinline
223
NrootDom<Ops>::NrootDom
(
Space
& home,
bool
share,
NrootDom<Ops>
&
p
)
224
:
BinaryPropagator
<
IntView
,
PC_INT_DOM
>(home,share,p),
225
ops(p.ops) {}
226
227
template
<
class
Ops>
228
Actor
*
229
NrootDom<Ops>::copy
(
Space
& home,
bool
share) {
230
return
new
(home)
NrootDom<Ops>
(home,share,*
this
);
231
}
232
233
template
<
class
Ops>
234
PropCost
235
NrootDom<Ops>::cost
(
const
Space
&,
const
ModEventDelta
& med)
const
{
236
if
(
IntView::me
(med) ==
ME_INT_VAL
)
237
return
PropCost::unary
(
PropCost::LO
);
238
else
if
(
IntView::me
(med) ==
ME_INT_DOM
)
239
return
PropCost::binary
(
PropCost::HI
);
240
else
241
return
PropCost::binary
(
PropCost::LO
);
242
}
243
244
template
<
class
Ops>
245
ExecStatus
246
NrootDom<Ops>::propagate
(
Space
& home,
const
ModEventDelta
& med) {
247
if
(
IntView::me
(med) !=
ME_INT_DOM
) {
248
GECODE_ES_CHECK
(
prop_nroot_bnd
(home,x0,x1,ops));
249
return
x1.assigned() ? home.
ES_SUBSUMED
(*
this
)
250
: home.
ES_NOFIX_PARTIAL
(*
this
,
IntView::med
(
ME_INT_DOM
));
251
}
252
253
{
254
ViewRanges<IntView>
r
(x0);
255
RangesMapNroot<Ops>
rmn(ops);
256
Iter::Ranges::Map<ViewRanges<IntView>
,
RangesMapNroot<Ops>
,
false
>
257
m(r,rmn);
258
GECODE_ME_CHECK
(x1.inter_r(home,m,
false
));
259
}
260
261
{
262
ViewRanges<IntView>
r
(x1);
263
RangesMapPow<Ops>
rmp(ops);
264
Iter::Ranges::Map<ViewRanges<IntView>
,
RangesMapPow<Ops>
,
true
>
265
m(r,rmp);
266
GECODE_ME_CHECK
(x0.inter_r(home,m,
false
));
267
}
268
269
return
x1.assigned() ? home.
ES_SUBSUMED
(*
this
) :
ES_FIX
;
270
}
271
272
273
}}}
274
275
// STATISTICS: int-prop
276