main page
modules
namespaces
classes
files
Gecode home
Generated on Tue Jan 28 2020 00:00:00 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
* Last modified:
14
* $Date: 2016-05-23 22:18:23 +0200 (Mon, 23 May 2016) $ by $Author: schulte $
15
* $Revision: 15073 $
16
*
17
* This file is part of Gecode, the generic constraint
18
* development environment:
19
* http://www.gecode.org
20
*
21
* Permission is hereby granted, free of charge, to any person obtaining
22
* a copy of this software and associated documentation files (the
23
* "Software"), to deal in the Software without restriction, including
24
* without limitation the rights to use, copy, modify, merge, publish,
25
* distribute, sublicense, and/or sell copies of the Software, and to
26
* permit persons to whom the Software is furnished to do so, subject to
27
* the following conditions:
28
*
29
* The above copyright notice and this permission notice shall be
30
* included in all copies or substantial portions of the Software.
31
*
32
* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
33
* EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
34
* MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
35
* NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
36
* LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
37
* OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
38
* WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
39
*
40
*/
41
42
namespace
Gecode
{
43
53
class
RangeList
:
public
FreeList
{
54
protected
:
56
int
_min
;
58
int
_max
;
59
public
:
61
62
RangeList
(
void
);
65
RangeList
(
int
min
,
int
max
);
67
RangeList
(
int
min
,
int
max
,
RangeList
*
n
);
69
71
72
int
min
(
void
)
const
;
75
int
max
(
void
)
const
;
77
unsigned
int
width
(
void
)
const
;
78
80
RangeList
*
next
(
void
)
const
;
82
RangeList
**
nextRef
(
void
);
84
86
87
void
min
(
int
n
);
90
void
max
(
int
n
);
92
void
next
(
RangeList
*
n
);
94
96
97
template
<
class
Iter>
99
static
void
copy
(
Space
& home,
RangeList
*&
r
, Iter&
i
);
101
template
<
class
Iter>
102
static
void
overwrite
(
Space
& home,
RangeList
*&
r
, Iter&
i
);
104
template
<
class
I>
105
static
void
insert
(
Space
& home,
RangeList
*&
r
, I&
i
);
107
109
110
void
dispose
(
Space
& home,
RangeList
*
l
);
113
void
dispose
(
Space
& home);
114
116
static
void
*
operator
new
(
size_t
s,
Space
& home);
118
static
void
*
operator
new
(
size_t
s,
void
*
p
);
120
static
void
operator
delete
(
void
*);
122
static
void
operator
delete
(
void
*,
Space
& home);
124
static
void
operator
delete
(
void
*,
void
*);
126
};
127
128
/*
129
* Range lists
130
*
131
*/
132
133
forceinline
134
RangeList::RangeList
(
void
) {}
135
136
forceinline
137
RangeList::RangeList
(
int
min
,
int
max
,
RangeList
*
n
)
138
:
FreeList
(
n
),
_min
(
min
),
_max
(
max
) {}
139
140
forceinline
141
RangeList::RangeList
(
int
min
,
int
max
)
142
:
_min
(
min
),
_max
(
max
) {}
143
144
forceinline
RangeList
*
145
RangeList::next
(
void
)
const
{
146
return
static_cast<
RangeList
*
>
(
FreeList::next
());
147
}
148
149
forceinline
RangeList
**
150
RangeList::nextRef
(
void
) {
151
return
reinterpret_cast<
RangeList
**
>
(
FreeList::nextRef
());
152
}
153
154
forceinline
void
155
RangeList::min
(
int
n
) {
156
_min
=
n
;
157
}
158
forceinline
void
159
RangeList::max
(
int
n
) {
160
_max
=
n
;
161
}
162
forceinline
void
163
RangeList::next
(
RangeList
*
n
) {
164
FreeList::next
(
n
);
165
}
166
167
forceinline
int
168
RangeList::min
(
void
)
const
{
169
return
_min
;
170
}
171
forceinline
int
172
RangeList::max
(
void
)
const
{
173
return
_max
;
174
}
175
forceinline
unsigned
int
176
RangeList::width
(
void
)
const
{
177
return
static_cast<
unsigned
int
>
(
_max
-
_min
+ 1);
178
}
179
180
181
forceinline
void
182
RangeList::operator
delete
(
void
*) {}
183
184
forceinline
void
185
RangeList::operator
delete
(
void
*,
Space
&) {
186
GECODE_NEVER
;
187
}
188
189
forceinline
void
190
RangeList::operator
delete
(
void
*,
void
*) {
191
GECODE_NEVER
;
192
}
193
194
forceinline
void
*
195
RangeList::operator
new
(size_t,
Space
& home) {
196
return
home.fl_alloc<
sizeof
(
RangeList
)>();
197
}
198
199
forceinline
void
*
200
RangeList::operator
new
(size_t,
void
*
p
) {
201
return
p
;
202
}
203
204
forceinline
void
205
RangeList::dispose
(
Space
& home,
RangeList
*
l
) {
206
home.
fl_dispose
<
sizeof
(
RangeList
)>(
this
,
l
);
207
}
208
209
forceinline
void
210
RangeList::dispose
(
Space
& home) {
211
RangeList
*
l
=
this
;
212
while
(
l
->next() != NULL)
213
l
=
l
->next();
214
dispose
(home,
l
);
215
}
216
217
template
<
class
Iter>
218
forceinline
void
219
RangeList::copy
(
Space
& home,
RangeList
*&
r
, Iter&
i
) {
220
RangeList
sentinel; sentinel.
next
(
r
);
221
RangeList
*
p
= &sentinel;
222
while
(
i
()) {
223
RangeList
*
n
=
new
(home)
RangeList
(
i
.min(),
i
.max());
224
p
->next(
n
);
p
=
n
; ++
i
;
225
}
226
p
->next(NULL);
227
r
= sentinel.
next
();
228
}
229
230
template
<
class
Iter>
231
forceinline
void
232
RangeList::overwrite
(
Space
& home,
RangeList
*&
r
, Iter&
i
) {
233
RangeList
sentinel; sentinel.
next
(
r
);
234
RangeList
*
p
= &sentinel;
235
RangeList
*
c
=
p
->next();
236
while
((
c
!= NULL) &&
i
()) {
237
c
->
min
(
i
.min());
c
->
max
(
i
.max());
238
p
=
c
;
c
=
c
->next(); ++
i
;
239
}
240
if
((
c
== NULL) && !
i
())
241
return
;
242
if
(
c
== NULL) {
243
assert(
i
());
244
// New elements needed
245
do
{
246
RangeList
*
n
=
new
(home)
RangeList
(
i
.min(),
i
.max());
247
p
->next(
n
);
p
=
n
; ++
i
;
248
}
while
(
i
());
249
}
else
{
250
// Dispose excess elements
251
while
(
c
->next() != NULL)
252
c
=
c
->next();
253
p
->next()->dispose(home,
c
);
254
}
255
p
->next(NULL);
256
r
= sentinel.
next
();
257
}
258
259
template
<
class
I>
260
forceinline
void
261
RangeList::insert
(
Space
& home,
RangeList
*&
r
, I&
i
) {
262
RangeList
sentinel;
263
sentinel.
next
(
r
);
264
RangeList
*
p
= &sentinel;
265
RangeList
*
c
=
p
->next();
266
while
((
c
!= NULL) &&
i
()) {
267
if
((
c
->
max
()+1 <
i
.min())) {
268
p
=
c
;
c
=
c
->next();
269
}
else
if
(
i
.max()+1 <
c
->
min
()) {
270
RangeList
*
n
=
new
(home)
RangeList
(
i
.min(),
i
.max(),
c
);
271
p
->next(
n
);
p
=
n
; ++
i
;
272
}
else
{
273
int
min
=
std::min
(
c
->
min
(),
i
.min());
274
int
max
=
std::max
(
c
->
max
(),
i
.max());
275
RangeList
*
f
=
c
;
276
p
=
c
;
c
=
c
->next(); ++
i
;
277
next
:
278
if
((
c
!= NULL) && (
c
->
min
() <=
max
+1)) {
279
max
=
std::max
(
max
,
c
->
max
());
280
p
=
c
;
c
=
c
->next();
281
goto
next
;
282
}
283
if
(
i
() && (
i
.min() <=
max
+1)) {
284
max
=
std::max
(
max
,
i
.max());
285
++
i
;
286
goto
next
;
287
}
288
// Dispose now unused elements
289
if
(
f
->next() !=
p
)
290
f
->next()->dispose(home,
p
);
291
f
->min(
min
);
f
->max(
max
);
f
->next(
c
);
292
}
293
}
294
if
(
c
== NULL) {
295
while
(
i
()) {
296
RangeList
*
n
=
new
(home)
RangeList
(
i
.min(),
i
.max());
297
p
->next(
n
);
p
=
n
;
298
++
i
;
299
}
300
p
->next(NULL);
301
}
302
r
= sentinel.
next
();
303
}
304
305
}
306
// STATISTICS: kernel-other
Gecode::RangeList::width
unsigned int width(void) const
Return width (distance between maximum and minimum)
Definition:
range-list.hpp:176
Gecode::FreeList::nextRef
FreeList ** nextRef(void)
Return pointer to next link in freelist object.
Definition:
memory-manager.hpp:300
forceinline
#define forceinline
Definition:
config.hpp:173
Gecode::FloatVal::max
friend FloatVal max(const FloatVal &x, const FloatVal &y)
Definition:
val.hpp:390
Gecode::RangeList::min
int min(void) const
Return minimum.
Definition:
range-list.hpp:168
Gecode::max
void max(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Definition:
arithmetic.cpp:53
Gecode::FloatVal::min
friend FloatVal min(const FloatVal &x, const FloatVal &y)
Definition:
val.hpp:402
Test::Int::Basic::i
Gecode::IntArgs i(4, 1, 2, 3, 4)
Gecode::Float::Limits::min
const FloatNum min
Smallest allowed float value.
Definition:
float.hh:850
Gecode::Space
Computation spaces.
Definition:
core.hpp:1748
Gecode::Space::fl_dispose
void fl_dispose(FreeList *f, FreeList *l)
Return freelist-managed memory to freelist.
Definition:
core.hpp:2858
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:232
Gecode
Gecode toplevel namespace
Gecode::FreeList::next
FreeList * next(void) const
Return next freelist object.
Definition:
memory-manager.hpp:295
Gecode::r
Post propagator for SetVar SetOpType SetVar SetRelType r
Definition:
set.hh:784
Gecode::RangeList::copy
static void copy(Space &home, RangeList *&r, Iter &i)
Create rangelist r from range iterator i.
Definition:
range-list.hpp:219
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:261
Gecode::RangeList::max
int max(void) const
Return maximum.
Definition:
range-list.hpp:172
GECODE_NEVER
#define GECODE_NEVER
Assert that this command is never executed.
Definition:
macros.hpp:60
Gecode::FreeList
Base-class for freelist-managed objects.
Definition:
memory-manager.hpp:123
l
NNF * l
Left subtree.
Definition:
bool-expr.cpp:244
Gecode::RangeList::_max
int _max
Maximum of range.
Definition:
range-list.hpp:58
Gecode::RangeList::dispose
void dispose(Space &home, RangeList *l)
Free memory for all elements between this and l (inclusive)
Definition:
range-list.hpp:205
Gecode::RangeList::nextRef
RangeList ** nextRef(void)
Return pointer to next element.
Definition:
range-list.hpp:150
Gecode::min
void min(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Definition:
arithmetic.cpp:71
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:145
n
int n
Number of negative literals for node type.
Definition:
bool-expr.cpp:238
Gecode::RangeList
Lists of ranges (intervals)
Definition:
range-list.hpp:53
Gecode::RangeList::RangeList
RangeList(void)
Default constructor (noop)
Definition:
range-list.hpp:134
Test::Set::Int::_max
Max _max("Int::Max")
Gecode::RangeList::_min
int _min
Minimum of range.
Definition:
range-list.hpp:56
p
int p
Number of positive literals for node type.
Definition:
bool-expr.cpp:236
Gecode::Float::Limits::max
const FloatNum max
Largest allowed float value.
Definition:
float.hh:848