main page
modules
namespaces
classes
files
Gecode home
Generated on Sat May 25 2013 18:00:33 for Gecode by
doxygen
1.8.3.1
gecode
int
branch
val-sel.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-05 20:51:24 +0100 (Tue, 05 Mar 2013) $ by $Author: schulte $
11
* $Revision: 13438 $
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
namespace
Gecode {
namespace
Int {
namespace
Branch {
39
40
template
<
class
View>
41
forceinline
42
ValSelMin<View>::ValSelMin
(
Space
& home,
const
ValBranch
& vb)
43
:
ValSel
<
View
,int>(home,vb) {}
44
template
<
class
View>
45
forceinline
46
ValSelMin<View>::ValSelMin
(
Space
& home,
bool
shared
,
ValSelMin
& vs)
47
:
ValSel
<
View
,int>(home,shared,vs) {}
48
template
<
class
View>
49
forceinline
int
50
ValSelMin<View>::val
(
const
Space
&,
View
x
,
int
) {
51
return
x.min();
52
}
53
54
template
<
class
View>
55
forceinline
56
ValSelMax<View>::ValSelMax
(
Space
& home,
const
ValBranch
& vb)
57
:
ValSel
<
View
,int>(home,vb) {}
58
template
<
class
View>
59
forceinline
60
ValSelMax<View>::ValSelMax
(
Space
& home,
bool
shared
,
ValSelMax
& vs)
61
:
ValSel
<
View
,int>(home,shared,vs) {}
62
template
<
class
View>
63
forceinline
int
64
ValSelMax<View>::val
(
const
Space
&,
View
x
,
int
) {
65
return
x.max();
66
}
67
68
template
<
class
View>
69
forceinline
70
ValSelMed<View>::ValSelMed
(
Space
& home,
const
ValBranch
& vb)
71
:
ValSel
<
View
,int>(home,vb) {}
72
template
<
class
View>
73
forceinline
74
ValSelMed<View>::ValSelMed
(
Space
& home,
bool
shared
,
ValSelMed
& vs)
75
:
ValSel
<
View
,int>(home,shared,vs) {}
76
template
<
class
View>
77
forceinline
int
78
ValSelMed<View>::val
(
const
Space
&,
View
x
,
int
) {
79
return
x.med();
80
}
81
82
template
<
class
View>
83
forceinline
84
ValSelAvg<View>::ValSelAvg
(
Space
& home,
const
ValBranch
& vb)
85
:
ValSel
<
View
,int>(home,vb) {}
86
template
<
class
View>
87
forceinline
88
ValSelAvg<View>::ValSelAvg
(
Space
& home,
bool
shared
,
ValSelAvg
& vs)
89
:
ValSel
<
View
,int>(home,shared,vs) {}
90
template
<
class
View>
91
forceinline
int
92
ValSelAvg<View>::val
(
const
Space
&,
View
x
,
int
) {
93
return
(x.width() == 2U) ? x.min() : ((x.min()+x.max()) / 2);
94
}
95
96
template
<
class
View>
97
forceinline
98
ValSelRnd<View>::ValSelRnd
(
Space
& home,
const
ValBranch
& vb)
99
:
ValSel
<
View
,int>(home,vb),
r
(vb.rnd()) {}
100
template
<
class
View>
101
forceinline
102
ValSelRnd<View>::ValSelRnd
(
Space
& home,
bool
shared
,
ValSelRnd
& vs)
103
:
ValSel
<
View
,int>(home,shared,vs) {
104
r
.
update
(home,shared,vs.
r
);
105
}
106
template
<
class
View>
107
forceinline
int
108
ValSelRnd<View>::val
(
const
Space
&,
View
x
,
int
) {
109
unsigned
int
p
=
r
(x.size());
110
for
(
ViewRanges<View>
i
(x);
i
(); ++
i
) {
111
if
(
i
.width() >
p
)
112
return
i
.min() +
static_cast<
int
>
(
p
);
113
p -=
i
.width();
114
}
115
GECODE_NEVER
;
116
return
0;
117
}
118
template
<
class
View>
119
forceinline
bool
120
ValSelRnd<View>::notice
(
void
)
const
{
121
return
true
;
122
}
123
template
<
class
View>
124
forceinline
void
125
ValSelRnd<View>::dispose
(
Space
&) {
126
r
.~Rnd();
127
}
128
129
forceinline
130
ValSelRangeMin::ValSelRangeMin
(
Space
& home,
const
ValBranch
& vb)
131
:
ValSel
<
IntView
,int>(home,vb) {}
132
forceinline
133
ValSelRangeMin::ValSelRangeMin
(
Space
& home,
bool
shared
,
ValSelRangeMin
& vs)
134
:
ValSel
<
IntView
,int>(home,shared,vs) {}
135
forceinline
int
136
ValSelRangeMin::val
(
const
Space
&,
IntView
x
,
int
) {
137
if
(x.
range
()) {
138
return
(x.
width
() == 2) ? x.
min
() : (x.
min
() + (x.
max
()-x.
min
())/2);
139
}
else
{
140
ViewRanges<View>
r
(x);
141
return
r.
max
();
142
}
143
}
144
145
forceinline
146
ValSelRangeMax::ValSelRangeMax
(
Space
& home,
const
ValBranch
& vb)
147
:
ValSel
<
IntView
,int>(home,vb) {}
148
forceinline
149
ValSelRangeMax::ValSelRangeMax
(
Space
& home,
bool
shared
,
ValSelRangeMax
& vs)
150
:
ValSel
<
IntView
,int>(home,shared,vs) {}
151
forceinline
int
152
ValSelRangeMax::val
(
const
Space
&,
IntView
x
,
int
) {
153
if
(x.
range
()) {
154
return
(x.
width
() == 2) ? x.
max
() : (x.
max
() - (x.
max
()-x.
min
())/2);
155
}
else
{
156
int
min
;
157
ViewRanges<IntView>
r
(x);
158
do
{
159
min = r.
min
(); ++
r
;
160
}
while
(
r
());
161
return
min
;
162
}
163
}
164
165
template
<
class
View,
bool
min>
166
forceinline
167
ValSelNearMinMax<View,min>::ValSelNearMinMax
(
Space
& home,
168
const
ValBranch
& vb)
169
:
ValSel
<
View
,int>(home,vb),
170
c
(static_cast<const
IntValBranch
&>(vb).
values
()) {}
171
template
<
class
View,
bool
min>
172
forceinline
173
ValSelNearMinMax<View,min>::ValSelNearMinMax
(
Space
& home,
bool
shared
,
174
ValSelNearMinMax
& vs)
175
:
ValSel
<
View
,int>(home,shared,vs) {
176
c
.
update
(home,shared,vs.
c
);
177
}
178
template
<
class
View,
bool
min>
179
forceinline
int
180
ValSelNearMinMax<View,min>::val
(
const
Space
&,
View
x
,
int
i
) {
181
int
n
=
c
[
i
];
182
if
(x.max() <=
n
)
return
x.
max
();
183
if
(x.min() >=
n
)
return
x.
min
();
184
if
(x.range())
return
n;
185
ViewRanges<View>
r
(x);
186
int
pmax;
187
do
{
188
pmax=r.
max
(); ++
r
;
189
}
while
(r.
max
() <
n
);
190
assert(
r
());
191
if
((pmax >= n) || (r.
min
() <=
n
))
192
return
n
;
193
assert((pmax < n) && (n < r.
min
()));
194
unsigned
int
dmin =
static_cast<
unsigned
int
>
(n - pmax);
195
unsigned
int
dmax =
static_cast<
unsigned
int
>
(r.
min
() -
n
);
196
if
(dmin == dmax)
197
return
min
? pmax : r.
min
();
198
else
if
(dmin < dmax)
199
return
pmax;
200
else
201
return
r.
min
();
202
}
203
template
<
class
View,
bool
min>
204
forceinline
bool
205
ValSelNearMinMax<View,min>::notice
(
void
)
const
{
206
return
true
;
207
}
208
template
<
class
View,
bool
min>
209
forceinline
void
210
ValSelNearMinMax<View,min>::dispose
(
Space
&) {
211
c
.~IntSharedArray();
212
}
213
214
template
<
class
View,
bool
inc>
215
forceinline
216
ValSelNearIncDec<View,inc>::ValSelNearIncDec
(
Space
& home,
217
const
ValBranch
& vb)
218
:
ValSel
<
View
,int>(home,vb),
219
c
(static_cast<const
IntValBranch
&>(vb).
values
()) {}
220
template
<
class
View,
bool
inc>
221
forceinline
222
ValSelNearIncDec<View,inc>::ValSelNearIncDec
(
Space
& home,
bool
shared
,
223
ValSelNearIncDec
& vs)
224
:
ValSel
<
View
,int>(home,shared,vs) {
225
c
.
update
(home,shared,vs.
c
);
226
}
227
template
<
class
View,
bool
inc>
228
forceinline
int
229
ValSelNearIncDec<View,inc>::val
(
const
Space
&,
View
x
,
int
i
) {
230
int
n
=
c
[
i
];
231
if
(x.max() <=
n
)
return
x.
max
();
232
if
(x.min() >=
n
)
return
x.
min
();
233
if
(x.range())
return
n;
234
if
(inc) {
235
ViewRanges<View>
r
(x);
236
while
(r.
max
() <
n
)
237
++r;
238
assert(
r
());
239
return
(r.
min
() <=
n
) ? n : r.
min
();
240
}
else
{
241
ViewRanges<View>
r
(x);
242
int
pmax;
243
do
{
244
pmax=r.
max
(); ++
r
;
245
}
while
(r.
max
() <
n
);
246
assert(
r
());
247
return
(r.
min
() <=
n
) ? n : pmax;
248
}
249
}
250
template
<
class
View,
bool
inc>
251
forceinline
bool
252
ValSelNearIncDec<View,inc>::notice
(
void
)
const
{
253
return
true
;
254
}
255
template
<
class
View,
bool
inc>
256
forceinline
void
257
ValSelNearIncDec<View,inc>::dispose
(
Space
&) {
258
c
.~IntSharedArray();
259
}
260
261
}}}
262
263
// STATISTICS: int-branch
264