main page
modules
namespaces
classes
files
Gecode home
Generated on Tue Mar 24 2020 14:04:04 for Gecode by
doxygen
1.8.17
gecode
kernel
range-list.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
* Contributing authors:
7
* Guido Tack <tack@gecode.org>
8
*
9
* Copyright:
10
* Christian Schulte, 2004
11
* Guido Tack, 2004
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
{
39
49
class
RangeList
:
public
FreeList
{
50
protected
:
52
int
_min
;
54
int
_max
;
55
public
:
57
58
RangeList
(
void
);
61
RangeList
(
int
min
,
int
max
);
63
RangeList
(
int
min
,
int
max
,
RangeList
*
n
);
65
67
68
int
min
(
void
)
const
;
71
int
max
(
void
)
const
;
73
unsigned
int
width
(
void
)
const
;
74
76
RangeList
*
next
(
void
)
const
;
78
RangeList
**
nextRef
(
void
);
80
82
83
void
min
(
int
n
);
86
void
max
(
int
n
);
88
void
next
(
RangeList
*
n
);
90
92
93
template
<
class
Iter>
95
static
void
copy
(
Space
& home,
RangeList
*&
r
, Iter&
i
);
97
template
<
class
Iter>
98
static
void
overwrite
(
Space
& home,
RangeList
*&
r
, Iter&
i
);
100
template
<
class
I>
101
static
void
insert
(
Space
& home,
RangeList
*&
r
, I&
i
);
103
105
106
void
dispose
(
Space
& home,
RangeList
*
l
);
109
void
dispose
(
Space
& home);
110
112
static
void
*
operator
new
(
size_t
s,
Space
& home);
114
static
void
*
operator
new
(
size_t
s,
void
*
p
);
116
static
void
operator
delete
(
void
*);
118
static
void
operator
delete
(
void
*,
Space
& home);
120
static
void
operator
delete
(
void
*,
void
*);
122
};
123
124
/*
125
* Range lists
126
*
127
*/
128
129
forceinline
130
RangeList::RangeList
(
void
) {}
131
132
forceinline
133
RangeList::RangeList
(
int
min
,
int
max
,
RangeList
*
n
)
134
:
FreeList
(
n
),
_min
(
min
),
_max
(
max
) {}
135
136
forceinline
137
RangeList::RangeList
(
int
min
,
int
max
)
138
:
_min
(
min
),
_max
(
max
) {}
139
140
forceinline
RangeList
*
141
RangeList::next
(
void
)
const
{
142
return
static_cast<
RangeList
*
>
(
FreeList::next
());
143
}
144
145
forceinline
RangeList
**
146
RangeList::nextRef
(
void
) {
147
return
reinterpret_cast<
RangeList
**
>
(
FreeList::nextRef
());
148
}
149
150
forceinline
void
151
RangeList::min
(
int
n
) {
152
_min
=
n
;
153
}
154
forceinline
void
155
RangeList::max
(
int
n
) {
156
_max
=
n
;
157
}
158
forceinline
void
159
RangeList::next
(
RangeList
*
n
) {
160
FreeList::next
(
n
);
161
}
162
163
forceinline
int
164
RangeList::min
(
void
)
const
{
165
return
_min
;
166
}
167
forceinline
int
168
RangeList::max
(
void
)
const
{
169
return
_max
;
170
}
171
forceinline
unsigned
int
172
RangeList::width
(
void
)
const
{
173
return
static_cast<
unsigned
int
>
(
_max
-
_min
+ 1);
174
}
175
176
177
forceinline
void
178
RangeList::operator
delete
(
void
*) {}
179
180
forceinline
void
181
RangeList::operator
delete
(
void
*,
Space
&) {
182
GECODE_NEVER
;
183
}
184
185
forceinline
void
186
RangeList::operator
delete
(
void
*,
void
*) {
187
GECODE_NEVER
;
188
}
189
190
forceinline
void
*
191
RangeList::operator
new
(size_t,
Space
& home) {
192
return
home.fl_alloc<
sizeof
(
RangeList
)>();
193
}
194
195
forceinline
void
*
196
RangeList::operator
new
(size_t,
void
*
p
) {
197
return
p
;
198
}
199
200
forceinline
void
201
RangeList::dispose
(
Space
& home,
RangeList
*
l
) {
202
home.
fl_dispose
<
sizeof
(
RangeList
)>(
this
,
l
);
203
}
204
205
forceinline
void
206
RangeList::dispose
(
Space
& home) {
207
RangeList
*
l
=
this
;
208
while
(
l
->next() != NULL)
209
l
=
l
->next();
210
dispose
(home,
l
);
211
}
212
213
template
<
class
Iter>
214
forceinline
void
215
RangeList::copy
(
Space
& home,
RangeList
*&
r
, Iter&
i
) {
216
RangeList
sentinel; sentinel.
next
(
r
);
217
RangeList
*
p
= &sentinel;
218
while
(
i
()) {
219
RangeList
*
n
=
new
(home)
RangeList
(
i
.min(),
i
.max());
220
p
->next(
n
);
p
=
n
; ++
i
;
221
}
222
p
->next(NULL);
223
r
= sentinel.
next
();
224
}
225
226
template
<
class
Iter>
227
forceinline
void
228
RangeList::overwrite
(
Space
& home,
RangeList
*&
r
, Iter&
i
) {
229
RangeList
sentinel; sentinel.
next
(
r
);
230
RangeList
*
p
= &sentinel;
231
RangeList
*
c
=
p
->next();
232
while
((
c
!= NULL) &&
i
()) {
233
c
->
min
(
i
.min());
c
->
max
(
i
.max());
234
p
=
c
;
c
=
c
->next(); ++
i
;
235
}
236
if
((
c
== NULL) && !
i
())
237
return
;
238
if
(
c
== NULL) {
239
assert(
i
());
240
// New elements needed
241
do
{
242
RangeList
*
n
=
new
(home)
RangeList
(
i
.min(),
i
.max());
243
p
->next(
n
);
p
=
n
; ++
i
;
244
}
while
(
i
());
245
}
else
{
246
// Dispose excess elements
247
while
(
c
->next() != NULL)
248
c
=
c
->next();
249
p
->next()->dispose(home,
c
);
250
}
251
p
->next(NULL);
252
r
= sentinel.
next
();
253
}
254
255
template
<
class
I>
256
forceinline
void
257
RangeList::insert
(
Space
& home,
RangeList
*&
r
, I&
i
) {
258
RangeList
sentinel;
259
sentinel.
next
(
r
);
260
RangeList
*
p
= &sentinel;
261
RangeList
*
c
=
p
->next();
262
while
((
c
!= NULL) &&
i
()) {
263
if
((
c
->
max
()+1 <
i
.min())) {
264
p
=
c
;
c
=
c
->next();
265
}
else
if
(
i
.max()+1 <
c
->
min
()) {
266
RangeList
*
n
=
new
(home)
RangeList
(
i
.min(),
i
.max(),
c
);
267
p
->next(
n
);
p
=
n
; ++
i
;
268
}
else
{
269
int
min
=
std::min
(
c
->
min
(),
i
.min());
270
int
max
=
std::max
(
c
->
max
(),
i
.max());
271
RangeList
*
f
=
c
;
272
p
=
c
;
c
=
c
->next(); ++
i
;
273
next
:
274
if
((
c
!= NULL) && (
c
->
min
() <=
max
+1)) {
275
max
=
std::max
(
max
,
c
->
max
());
276
p
=
c
;
c
=
c
->next();
277
goto
next
;
278
}
279
if
(
i
() && (
i
.min() <=
max
+1)) {
280
max
=
std::max
(
max
,
i
.max());
281
++
i
;
282
goto
next
;
283
}
284
// Dispose now unused elements
285
if
(
f
->next() !=
p
)
286
f
->next()->dispose(home,
p
);
287
f
->min(
min
);
f
->max(
max
);
f
->next(
c
);
288
}
289
}
290
if
(
c
== NULL) {
291
while
(
i
()) {
292
RangeList
*
n
=
new
(home)
RangeList
(
i
.min(),
i
.max());
293
p
->next(
n
);
p
=
n
;
294
++
i
;
295
}
296
p
->next(NULL);
297
}
298
r
= sentinel.
next
();
299
}
300
301
}
302
// STATISTICS: kernel-other
Gecode::RangeList::width
unsigned int width(void) const
Return width (distance between maximum and minimum)
Definition:
range-list.hpp:172
Gecode::FreeList::nextRef
FreeList ** nextRef(void)
Return pointer to next link in freelist object.
Definition:
manager.hpp:253
Gecode::FloatVal::max
friend FloatVal max(const FloatVal &x, const FloatVal &y)
Definition:
val.hpp:386
Gecode::RangeList::min
int min(void) const
Return minimum.
Definition:
range-list.hpp:164
Gecode::max
void max(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Definition:
arithmetic.cpp:49
Gecode::FloatVal::min
friend FloatVal min(const FloatVal &x, const FloatVal &y)
Definition:
val.hpp:398
Gecode::Float::Limits::min
const FloatNum min
Smallest allowed float value.
Definition:
float.hh:846
Gecode::Space
Computation spaces.
Definition:
core.hpp:1742
Gecode::Space::fl_dispose
void fl_dispose(FreeList *f, FreeList *l)
Return freelist-managed memory to freelist.
Definition:
core.hpp:2827
Gecode::RangeList::overwrite
static void overwrite(Space &home, RangeList *&r, Iter &i)
Overwrite rangelist r with ranges from range iterator i.
Definition:
range-list.hpp:228
Gecode
Gecode toplevel namespace
Gecode::FreeList::next
FreeList * next(void) const
Return next freelist object.
Definition:
manager.hpp:248
Gecode::r
Post propagator for SetVar SetOpType SetVar SetRelType r
Definition:
set.hh:767
Gecode::RangeList::copy
static void copy(Space &home, RangeList *&r, Iter &i)
Create rangelist r from range iterator i.
Definition:
range-list.hpp:215
Gecode::RangeList::insert
static void insert(Space &home, RangeList *&r, I &i)
Insert (as union) ranges from iterator i into r.
Definition:
range-list.hpp:257
Gecode::RangeList::max
int max(void) const
Return maximum.
Definition:
range-list.hpp:168
GECODE_NEVER
#define GECODE_NEVER
Assert that this command is never executed.
Definition:
macros.hpp:56
Gecode::FreeList
Base-class for freelist-managed objects.
Definition:
manager.hpp:98
l
NNF * l
Left subtree.
Definition:
bool-expr.cpp:240
Gecode::RangeList::_max
int _max
Maximum of range.
Definition:
range-list.hpp:54
Gecode::RangeList::dispose
void dispose(Space &home, RangeList *l)
Free memory for all elements between this and l (inclusive)
Definition:
range-list.hpp:201
forceinline
#define forceinline
Definition:
config.hpp:185
Gecode::RangeList::nextRef
RangeList ** nextRef(void)
Return pointer to next element.
Definition:
range-list.hpp:146
Gecode::min
void min(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Definition:
arithmetic.cpp:67
Gecode::f
Post propagator for f(x \diamond_{\mathit{op}} y) \sim_r z \f$ void rel(Home home
Test::Set::Int::_min
Min _min("Int::Min")
Test::Float::Arithmetic::c
Gecode::FloatVal c(-8, 8)
Gecode::RangeList::next
RangeList * next(void) const
Return next element.
Definition:
range-list.hpp:141
n
int n
Number of negative literals for node type.
Definition:
bool-expr.cpp:234
Gecode::RangeList
Lists of ranges (intervals)
Definition:
range-list.hpp:49
Gecode::RangeList::RangeList
RangeList(void)
Default constructor (noop)
Definition:
range-list.hpp:130
Test::Int::Basic::i
Gecode::IntArgs i({1, 2, 3, 4})
Test::Set::Int::_max
Max _max("Int::Max")
Gecode::RangeList::_min
int _min
Minimum of range.
Definition:
range-list.hpp:52
p
int p
Number of positive literals for node type.
Definition:
bool-expr.cpp:232
Gecode::Float::Limits::max
const FloatNum max
Largest allowed float value.
Definition:
float.hh:844