main page
modules
namespaces
classes
files
Gecode home
Generated on Mon Feb 8 2021 00:00:00 for Gecode by
doxygen
1.8.20
gecode
iter
ranges-union.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, 2004
8
*
9
* This file is part of Gecode, the generic constraint
10
* development environment:
11
* http://www.gecode.org
12
*
13
* Permission is hereby granted, free of charge, to any person obtaining
14
* a copy of this software and associated documentation files (the
15
* "Software"), to deal in the Software without restriction, including
16
* without limitation the rights to use, copy, modify, merge, publish,
17
* distribute, sublicense, and/or sell copies of the Software, and to
18
* permit persons to whom the Software is furnished to do so, subject to
19
* the following conditions:
20
*
21
* The above copyright notice and this permission notice shall be
22
* included in all copies or substantial portions of the Software.
23
*
24
* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
25
* EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
26
* MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
27
* NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
28
* LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
29
* OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
30
* WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
31
*
32
*/
33
34
#include <algorithm>
35
36
namespace
Gecode
{
namespace
Iter {
namespace
Ranges {
37
43
template
<
class
I,
class
J>
44
class
Union
:
public
MinMax
{
45
protected
:
47
I
i
;
49
J
j
;
50
public
:
52
53
Union
(
void
);
56
Union
(I&
i
, J&
j
);
58
void
init
(I&
i
, J&
j
);
60
62
63
void
operator ++
(
void
);
66
};
67
68
74
class
NaryUnion
:
public
RangeListIter
{
75
protected
:
77
RangeList
*
f
;
79
template
<
class
I,
class
J>
80
RangeList
*
two
(I&
i
, J& j);
82
template
<
class
I>
83
void
insert
(I&
i
,
RangeList
*&
u
);
84
public
:
86
87
NaryUnion
(
void
);
90
template
<
class
I>
91
NaryUnion
(
Region
&
r
, I&
i
);
93
template
<
class
I,
class
J>
94
NaryUnion
(
Region
&
r
, I&
i
, J& j);
96
template
<
class
I>
97
NaryUnion
(
Region
&
r
, I*
i
,
int
n
);
99
template
<
class
I>
100
void
init
(
Region
&
r
, I&
i
);
102
template
<
class
I,
class
J>
103
void
init
(
Region
&
r
, I&
i
, J& j);
105
template
<
class
I>
106
void
init
(
Region
&
r
, I*
i
,
int
n
);
108
template
<
class
I>
109
void
operator |=
(I&
i
);
111
NaryUnion
&
operator =
(
const
NaryUnion
& m);
113
};
114
115
116
117
/*
118
* Binary union
119
*
120
*/
121
122
template
<
class
I,
class
J>
123
inline
void
124
Union<I,J>::operator ++
(
void
) {
125
if
(!
i
() && !j()) {
126
finish();
return
;
127
}
128
129
if
(!
i
() || (j() && (j.max()+1 <
i
.min()))) {
130
mi = j.min(); ma = j.max(); ++j;
return
;
131
}
132
if
(!j() || (
i
() && (
i
.max()+1 < j.min()))) {
133
mi =
i
.min(); ma =
i
.max(); ++
i
;
return
;
134
}
135
136
mi =
std::min
(
i
.min(),j.min());
137
ma =
std::max
(
i
.max(),j.max());
138
139
++
i
; ++j;
140
141
next:
142
if
(
i
() && (
i
.min() <= ma+1)) {
143
ma =
std::max
(ma,
i
.max()); ++
i
;
144
goto
next;
145
}
146
if
(j() && (j.min() <= ma+1)) {
147
ma =
std::max
(ma,j.max()); ++j;
148
goto
next;
149
}
150
}
151
152
153
template
<
class
I,
class
J>
154
forceinline
155
Union<I,J>::Union
(
void
) {}
156
157
template
<
class
I,
class
J>
158
forceinline
159
Union<I,J>::Union
(I& i0, J& j0)
160
:
i
(i0), j(j0) {
161
operator ++
();
162
}
163
164
template
<
class
I,
class
J>
165
forceinline
void
166
Union<I,J>::init
(I& i0, J& j0) {
167
i
= i0; j = j0;
168
operator ++();
169
}
170
171
172
173
/*
174
* Nary union
175
*
176
*/
177
178
template
<
class
I,
class
J>
179
RangeListIter::RangeList
*
180
NaryUnion::two
(I&
i
, J& j) {
181
RangeList
*
h
;
182
RangeList
**
c
= &
h
;
183
184
while
(
i
() && j())
185
if
(
i
.max()+1 < j.min()) {
186
RangeList
*
t
=
range
(
i
); ++
i
;
187
*
c
=
t
;
c
= &
t
->next;
188
}
else
if
(j.max()+1 <
i
.min()) {
189
RangeList
*
t
=
range
(j); ++j;
190
*
c
=
t
;
c
= &
t
->next;
191
}
else
{
192
int
min
=
std::min
(
i
.min(),j.min());
193
int
max
=
std::max
(
i
.max(),j.max());
194
++
i
; ++j;
195
196
nexta:
197
if
(
i
() && (
i
.min() <=
max
+1)) {
198
max
=
std::max
(
max
,
i
.max()); ++
i
;
199
goto
nexta;
200
}
201
if
(j() && (j.min() <=
max
+1)) {
202
max
=
std::max
(
max
,j.max()); ++j;
203
goto
nexta;
204
}
205
206
RangeList
*
t
=
range
(
min
,
max
);
207
*
c
=
t
;
c
= &
t
->next;
208
}
209
for
( ;
i
(); ++
i
) {
210
RangeList
*
t
=
range
(
i
);
211
*
c
=
t
;
c
= &
t
->next;
212
}
213
for
( ; j(); ++j) {
214
RangeList
*
t
=
range
(j);
215
*
c
=
t
;
c
= &
t
->next;
216
}
217
*
c
= NULL;
218
return
h
;
219
}
220
221
template
<
class
I>
222
void
223
NaryUnion::insert
(I&
i
,
RangeList
*&
u
) {
224
// The current rangelist
225
RangeList
**
c
= &
u
;
226
227
while
((*
c
!= NULL) &&
i
())
228
if
((*c)->max+1 <
i
.min()) {
229
// Keep range from union
230
c
= &(*c)->
next
;
231
}
else
if
(
i
.max()+1 < (*c)->min) {
232
// Copy range from iterator
233
RangeList
*
t
=
range
(
i
,
f
); ++
i
;
234
// Insert
235
t
->next = *
c
; *
c
=
t
;
c
= &
t
->next;
236
}
else
{
237
// Ranges overlap
238
// Compute new minimum
239
(*c)->min =
std::min
((*c)->min,
i
.min());
240
// Compute new maximum
241
int
max
=
std::max
((*c)->max,
i
.max());
242
243
// Scan from the next range in the union
244
RangeList
* s = (*c)->
next
;
245
++
i
;
246
247
nextb:
248
if
((s != NULL) && (s->
min
<=
max
+1)) {
249
max
=
std::max
(
max
,s->
max
);
250
RangeList
*
t
= s;
251
s = s->
next
;
252
// Put deleted element into freelist
253
t
->next =
f
;
f
=
t
;
254
goto
nextb;
255
}
256
if
(
i
() && (
i
.min() <=
max
+1)) {
257
max
=
std::max
(
max
,
i
.max()); ++
i
;
258
goto
nextb;
259
}
260
// Store computed max and shunt skipped ranges from union
261
(*c)->max =
max
; (*c)->next = s;
262
}
263
if
(*
c
== NULL) {
264
// Copy remaining ranges from iterator
265
for
( ;
i
(); ++
i
) {
266
RangeList
*
t
=
range
(
i
,
f
);
267
*
c
=
t
;
c
= &
t
->next;
268
}
269
*
c
= NULL;
270
}
271
}
272
273
274
forceinline
275
NaryUnion::NaryUnion
(
void
)
276
:
f
(NULL) {}
277
278
template
<
class
I>
279
forceinline
void
280
NaryUnion::init
(
Region
&
r
, I&
i
) {
281
RangeListIter::init
(
r
);
282
f
= NULL;
283
set
(
copy
(
i
));
284
}
285
286
template
<
class
I,
class
J>
287
forceinline
void
288
NaryUnion::init
(
Region
&
r
, I&
i
, J& j) {
289
RangeListIter::init
(
r
);
290
f
= NULL;
291
set
(
two
(
i
,j));
292
}
293
294
template
<
class
I>
295
forceinline
void
296
NaryUnion::init
(
Region
&
r
, I*
i
,
int
n
) {
297
f
= NULL;
298
RangeListIter::init
(
r
);
299
300
int
m = 0;
301
while
((m <
n
) && !
i
[m]())
302
m++;
303
304
// Union is empty
305
if
(m >=
n
)
306
return
;
307
308
n
--;
309
while
(!
i
[
n
]())
310
n
--;
311
312
if
(m ==
n
) {
313
// Union is just a single iterator
314
set
(
copy
(
i
[m]));
315
}
else
{
316
// At least two iterators
317
RangeList
*
u
=
two
(
i
[m++],
i
[
n
--]);
318
// Insert the remaining iterators
319
for
( ; m<=
n
; m++)
320
insert
(
i
[m],
u
);
321
set
(
u
);
322
}
323
}
324
325
template
<
class
I>
326
forceinline
327
NaryUnion::NaryUnion
(
Region
&
r
, I&
i
) {
328
init
(
r
,
i
);
329
}
330
template
<
class
I,
class
J>
331
forceinline
332
NaryUnion::NaryUnion
(
Region
&
r
, I&
i
, J& j) {
333
init
(
r
,
i
, j);
334
}
335
template
<
class
I>
336
forceinline
337
NaryUnion::NaryUnion
(
Region
&
r
, I*
i
,
int
n
) {
338
init
(
r
,
i
,
n
);
339
}
340
341
template
<
class
I>
342
forceinline
void
343
NaryUnion::operator |=
(I&
i
) {
344
RangeList
*
u
=
get
();
345
insert
(
i
,
u
);
346
set
(
u
);
347
}
348
349
forceinline
NaryUnion
&
350
NaryUnion::operator =
(
const
NaryUnion
& m) {
351
f
= NULL;
352
return
static_cast<
NaryUnion
&
>
(
RangeListIter::operator =
(m));
353
}
354
355
}}}
356
357
// STATISTICS: iter-any
358
Gecode::Iter::Ranges::NaryUnion::operator=
NaryUnion & operator=(const NaryUnion &m)
Assignment operator (both iterators must be allocated from the same region)
Definition:
ranges-union.hpp:350
Gecode::Iter::Ranges::NaryUnion::insert
void insert(I &i, RangeList *&u)
Insert ranges from i into u.
Definition:
ranges-union.hpp:223
Gecode::Iter::Ranges::RangeListIter::range
RangeList * range(int min, int max, RangeList *&f)
Create new range possibly from freelist f and init.
Definition:
ranges-list.hpp:185
Gecode::Iter::Ranges::Union::init
void init(I &i, J &j)
Initialize with iterator i and j.
Definition:
ranges-union.hpp:166
t
NodeType t
Type of node.
Definition:
bool-expr.cpp:230
Gecode::Float::Limits::min
const FloatNum min
Smallest allowed float value.
Definition:
float.hh:846
Gecode::Iter::Ranges::RangeListIter::operator=
RangeListIter & operator=(const RangeListIter &i)
Assignment operator.
Definition:
ranges-list.hpp:149
Gecode::Iter::Ranges::NaryUnion::two
RangeList * two(I &i, J &j)
Return range list for union of two iterators.
Gecode
Gecode toplevel namespace
u
union Gecode::@602::NNF::@65 u
Union depending on nodetype t.
Gecode::Iter::Ranges::MinMax
Base for range iterators with explicit min and max.
Definition:
ranges-minmax.hpp:47
Gecode::Iter::Ranges::RangeListIter::max
int max(void) const
Return largest value of range.
Definition:
ranges-list.hpp:249
Gecode::Iter::Ranges::RangeListIter::RangeList
Range list class.
Definition:
ranges-list.hpp:44
Gecode::Iter::Ranges::NaryUnion::operator|=
void operator|=(I &i)
Add iterator i.
Definition:
ranges-union.hpp:343
Gecode::Iter::Ranges::RangeListIter::copy
RangeList * copy(I &i)
Copy the iterator i to a range list.
Definition:
ranges-list.hpp:218
Gecode::Region
Handle to region.
Definition:
region.hpp:55
Gecode::Iter::Ranges::RangeListIter::RangeList::max
int max
Definition:
ranges-list.hpp:47
Gecode::r
Post propagator for SetVar SetOpType SetVar SetRelType r
Definition:
set.hh:767
Gecode::Iter::Ranges::Union::operator++
void operator++(void)
Move iterator to next range (if possible)
Definition:
ranges-union.hpp:124
Gecode::Iter::Ranges::NaryUnion
Range iterator for union of iterators.
Definition:
ranges-union.hpp:74
Gecode::Iter::Ranges::RangeListIter
Iterator over range lists.
Definition:
ranges-list.hpp:41
Gecode::Iter::Ranges::Union::i
I i
First iterator.
Definition:
ranges-union.hpp:47
Gecode::Iter::Ranges::NaryUnion::init
void init(Region &r, I &i)
Initialize with single iterator i.
Definition:
ranges-union.hpp:280
Gecode::Iter::Ranges::Union::j
J j
Second iterator.
Definition:
ranges-union.hpp:49
Gecode::Iter::Ranges::RangeListIter::min
int min(void) const
Return smallest value of range.
Definition:
ranges-list.hpp:245
Gecode::Iter::Ranges::RangeListIter::set
void set(RangeList *l)
Set range lists.
Definition:
ranges-list.hpp:175
Gecode::Iter::Ranges::NaryUnion::f
RangeList * f
Freelist used for allocation.
Definition:
ranges-union.hpp:77
Gecode::Iter::Ranges::Union
Range iterator for computing union (binary)
Definition:
ranges-union.hpp:44
Gecode::Iter::Ranges::RangeListIter::RangeList::min
int min
Minimum and maximum of a range.
Definition:
ranges-list.hpp:47
Gecode::Iter::Ranges::RangeListIter::RangeList::next
RangeList * next
Next element.
Definition:
ranges-list.hpp:49
Gecode::Iter::Ranges::Union::Union
Union(void)
Default constructor.
Definition:
ranges-union.hpp:155
Gecode::Iter::Ranges::NaryUnion::NaryUnion
NaryUnion(void)
Default constructor.
Definition:
ranges-union.hpp:275
Gecode::Iter::Ranges::RangeListIter::init
void init(Region &r)
Initialize.
Definition:
ranges-list.hpp:136
forceinline
#define forceinline
Definition:
config.hpp:192
Gecode::Iter::Ranges::RangeListIter::get
RangeList * get(void) const
Get head of current range list.
Definition:
ranges-list.hpp:180
Gecode::Iter::Ranges::RangeListIter::h
RangeList * h
Head of range list.
Definition:
ranges-list.hpp:62
Gecode::f
Post propagator for f(x \diamond_{\mathit{op}} y) \sim_r z \f$ void rel(Home home
n
int n
Number of negative literals for node type.
Definition:
bool-expr.cpp:234
Test::Int::Basic::i
Gecode::IntArgs i({1, 2, 3, 4})
Gecode::Float::Limits::max
const FloatNum max
Largest allowed float value.
Definition:
float.hh:844
Gecode::Iter::Ranges::RangeListIter::c
RangeList * c
Current list element.
Definition:
ranges-list.hpp:64