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
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
* Last modified:
10
* $Date: 2016-04-19 17:19:45 +0200 (Tue, 19 Apr 2016) $ by $Author: schulte $
11
* $Revision: 14967 $
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 <algorithm>
39
40
namespace
Gecode
{
namespace
Iter {
namespace
Ranges {
41
47
template
<
class
I,
class
J>
48
class
Union
:
public
MinMax
{
49
protected
:
51
I
i
;
53
J
j
;
54
public
:
56
57
Union
(
void
);
60
Union
(I&
i
, J&
j
);
62
void
init
(I&
i
, J&
j
);
64
66
67
void
operator ++
(
void
);
70
};
71
72
78
class
NaryUnion
:
public
RangeListIter
{
79
protected
:
81
RangeList
*
f
;
83
template
<
class
I,
class
J>
84
RangeList
*
two
(I&
i
, J& j);
86
template
<
class
I>
87
void
insert
(I&
i
,
RangeList
*&
u
);
88
public
:
90
91
NaryUnion
(
void
);
94
template
<
class
I>
95
NaryUnion
(
Region
&
r
, I&
i
);
97
template
<
class
I,
class
J>
98
NaryUnion
(
Region
&
r
, I&
i
, J& j);
100
template
<
class
I>
101
NaryUnion
(
Region
&
r
, I*
i
,
int
n
);
103
template
<
class
I>
104
void
init
(
Region
&
r
, I&
i
);
106
template
<
class
I,
class
J>
107
void
init
(
Region
&
r
, I&
i
, J& j);
109
template
<
class
I>
110
void
init
(
Region
&
r
, I*
i
,
int
n
);
112
template
<
class
I>
113
void
operator |=
(I&
i
);
115
NaryUnion
&
operator =
(
const
NaryUnion
& m);
117
};
118
119
120
121
/*
122
* Binary union
123
*
124
*/
125
126
template
<
class
I,
class
J>
127
inline
void
128
Union<I,J>::operator ++
(
void
) {
129
if
(!
i
() && !j()) {
130
finish();
return
;
131
}
132
133
if
(!
i
() || (j() && (j.max()+1 <
i
.min()))) {
134
mi = j.min(); ma = j.max(); ++j;
return
;
135
}
136
if
(!j() || (
i
() && (
i
.max()+1 < j.min()))) {
137
mi =
i
.min(); ma =
i
.max(); ++
i
;
return
;
138
}
139
140
mi =
std::min
(
i
.min(),j.min());
141
ma =
std::max
(
i
.max(),j.max());
142
143
++
i
; ++j;
144
145
next:
146
if
(
i
() && (
i
.min() <= ma+1)) {
147
ma =
std::max
(ma,
i
.max()); ++
i
;
148
goto
next;
149
}
150
if
(j() && (j.min() <= ma+1)) {
151
ma =
std::max
(ma,j.max()); ++j;
152
goto
next;
153
}
154
}
155
156
157
template
<
class
I,
class
J>
158
forceinline
159
Union<I,J>::Union
(
void
) {}
160
161
template
<
class
I,
class
J>
162
forceinline
163
Union<I,J>::Union
(I& i0, J& j0)
164
:
i
(i0), j(j0) {
165
operator ++
();
166
}
167
168
template
<
class
I,
class
J>
169
forceinline
void
170
Union<I,J>::init
(I& i0, J& j0) {
171
i
= i0; j = j0;
172
operator ++();
173
}
174
175
176
177
/*
178
* Nary union
179
*
180
*/
181
182
template
<
class
I,
class
J>
183
RangeListIter::RangeList
*
184
NaryUnion::two
(I&
i
, J& j) {
185
RangeList
*
h
;
186
RangeList
**
c
= &
h
;
187
188
while
(
i
() && j())
189
if
(
i
.max()+1 < j.min()) {
190
RangeList
*
t
=
range
(
i
); ++
i
;
191
*
c
=
t
;
c
= &
t
->next;
192
}
else
if
(j.max()+1 <
i
.min()) {
193
RangeList
*
t
=
range
(j); ++j;
194
*
c
=
t
;
c
= &
t
->next;
195
}
else
{
196
int
min
=
std::min
(
i
.min(),j.min());
197
int
max
=
std::max
(
i
.max(),j.max());
198
++
i
; ++j;
199
200
nexta:
201
if
(
i
() && (
i
.min() <=
max
+1)) {
202
max
=
std::max
(
max
,
i
.max()); ++
i
;
203
goto
nexta;
204
}
205
if
(j() && (j.min() <=
max
+1)) {
206
max
=
std::max
(
max
,j.max()); ++j;
207
goto
nexta;
208
}
209
210
RangeList
*
t
=
range
(
min
,
max
);
211
*
c
=
t
;
c
= &
t
->next;
212
}
213
for
( ;
i
(); ++
i
) {
214
RangeList
*
t
=
range
(
i
);
215
*
c
=
t
;
c
= &
t
->next;
216
}
217
for
( ; j(); ++j) {
218
RangeList
*
t
=
range
(j);
219
*
c
=
t
;
c
= &
t
->next;
220
}
221
*
c
= NULL;
222
return
h
;
223
}
224
225
template
<
class
I>
226
void
227
NaryUnion::insert
(I&
i
,
RangeList
*&
u
) {
228
// The current rangelist
229
RangeList
**
c
= &
u
;
230
231
while
((*
c
!= NULL) &&
i
())
232
if
((*c)->max+1 <
i
.min()) {
233
// Keep range from union
234
c
= &(*c)->
next
;
235
}
else
if
(
i
.max()+1 < (*c)->min) {
236
// Copy range from iterator
237
RangeList
*
t
=
range
(
i
,
f
); ++
i
;
238
// Insert
239
t
->next = *
c
; *
c
=
t
;
c
= &
t
->next;
240
}
else
{
241
// Ranges overlap
242
// Compute new minimum
243
(*c)->min =
std::min
((*c)->min,
i
.min());
244
// Compute new maximum
245
int
max
=
std::max
((*c)->max,
i
.max());
246
247
// Scan from the next range in the union
248
RangeList
* s = (*c)->
next
;
249
++
i
;
250
251
nextb:
252
if
((s != NULL) && (s->
min
<=
max
+1)) {
253
max
=
std::max
(
max
,s->
max
);
254
RangeList
*
t
= s;
255
s = s->
next
;
256
// Put deleted element into freelist
257
t
->next =
f
;
f
=
t
;
258
goto
nextb;
259
}
260
if
(
i
() && (
i
.min() <=
max
+1)) {
261
max
=
std::max
(
max
,
i
.max()); ++
i
;
262
goto
nextb;
263
}
264
// Store computed max and shunt skipped ranges from union
265
(*c)->max =
max
; (*c)->next = s;
266
}
267
if
(*
c
== NULL) {
268
// Copy remaining ranges from iterator
269
for
( ;
i
(); ++
i
) {
270
RangeList
*
t
=
range
(
i
,
f
);
271
*
c
=
t
;
c
= &
t
->next;
272
}
273
*
c
= NULL;
274
}
275
}
276
277
278
forceinline
279
NaryUnion::NaryUnion
(
void
)
280
:
f
(NULL) {}
281
282
template
<
class
I>
283
forceinline
void
284
NaryUnion::init
(
Region
&
r
, I&
i
) {
285
RangeListIter::init
(
r
);
286
f
= NULL;
287
set
(
copy
(
i
));
288
}
289
290
template
<
class
I,
class
J>
291
forceinline
void
292
NaryUnion::init
(
Region
&
r
, I&
i
, J& j) {
293
RangeListIter::init
(
r
);
294
f
= NULL;
295
set
(
two
(
i
,j));
296
}
297
298
template
<
class
I>
299
forceinline
void
300
NaryUnion::init
(
Region
&
r
, I*
i
,
int
n
) {
301
f
= NULL;
302
RangeListIter::init
(
r
);
303
304
int
m = 0;
305
while
((m <
n
) && !
i
[m]())
306
m++;
307
308
// Union is empty
309
if
(m >=
n
)
310
return
;
311
312
n
--;
313
while
(!
i
[
n
]())
314
n
--;
315
316
if
(m ==
n
) {
317
// Union is just a single iterator
318
set
(
copy
(
i
[m]));
319
}
else
{
320
// At least two iterators
321
RangeList
*
u
=
two
(
i
[m++],
i
[
n
--]);
322
// Insert the remaining iterators
323
for
( ; m<=
n
; m++)
324
insert
(
i
[m],
u
);
325
set
(
u
);
326
}
327
}
328
329
template
<
class
I>
330
forceinline
331
NaryUnion::NaryUnion
(
Region
&
r
, I&
i
) {
332
init
(
r
,
i
);
333
}
334
template
<
class
I,
class
J>
335
forceinline
336
NaryUnion::NaryUnion
(
Region
&
r
, I&
i
, J& j) {
337
init
(
r
,
i
, j);
338
}
339
template
<
class
I>
340
forceinline
341
NaryUnion::NaryUnion
(
Region
&
r
, I*
i
,
int
n
) {
342
init
(
r
,
i
,
n
);
343
}
344
345
template
<
class
I>
346
forceinline
void
347
NaryUnion::operator |=
(I&
i
) {
348
RangeList
*
u
=
get
();
349
insert
(
i
,
u
);
350
set
(
u
);
351
}
352
353
forceinline
NaryUnion
&
354
NaryUnion::operator =
(
const
NaryUnion
& m) {
355
f
= NULL;
356
return
static_cast<
NaryUnion
&
>
(
RangeListIter::operator =
(m));
357
}
358
359
}}}
360
361
// STATISTICS: iter-any
362
forceinline
#define forceinline
Definition:
config.hpp:173
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:354
Gecode::Iter::Ranges::NaryUnion::insert
void insert(I &i, RangeList *&u)
Insert ranges from i into u.
Definition:
ranges-union.hpp:227
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:189
Gecode::Iter::Ranges::Union::init
void init(I &i, J &j)
Initialize with iterator i and j.
Definition:
ranges-union.hpp:170
Test::Int::Basic::i
Gecode::IntArgs i(4, 1, 2, 3, 4)
t
NodeType t
Type of node.
Definition:
bool-expr.cpp:234
Gecode::Float::Limits::min
const FloatNum min
Smallest allowed float value.
Definition:
float.hh:850
Gecode::Iter::Ranges::RangeListIter::operator=
RangeListIter & operator=(const RangeListIter &i)
Assignment operator.
Definition:
ranges-list.hpp:153
Gecode::Iter::Ranges::NaryUnion::two
RangeList * two(I &i, J &j)
Return range list for union of two iterators.
u
union Gecode::@579::NNF::@61 u
Union depending on nodetype t.
Gecode
Gecode toplevel namespace
Gecode::Iter::Ranges::MinMax
Base for range iterators with explicit min and max.
Definition:
ranges-minmax.hpp:51
Gecode::Iter::Ranges::RangeListIter::max
int max(void) const
Return largest value of range.
Definition:
ranges-list.hpp:253
Gecode::Iter::Ranges::RangeListIter::RangeList
Range list class.
Definition:
ranges-list.hpp:48
Gecode::Iter::Ranges::NaryUnion::operator|=
void operator|=(I &i)
Add iterator i.
Definition:
ranges-union.hpp:347
Gecode::Iter::Ranges::RangeListIter::copy
RangeList * copy(I &i)
Copy the iterator i to a range list.
Definition:
ranges-list.hpp:222
Gecode::Region
Handle to region.
Definition:
region.hpp:61
Gecode::Iter::Ranges::RangeListIter::RangeList::max
int max
Definition:
ranges-list.hpp:51
Gecode::r
Post propagator for SetVar SetOpType SetVar SetRelType r
Definition:
set.hh:784
Gecode::Iter::Ranges::Union::operator++
void operator++(void)
Move iterator to next range (if possible)
Definition:
ranges-union.hpp:128
Gecode::Iter::Ranges::NaryUnion
Range iterator for union of iterators.
Definition:
ranges-union.hpp:78
Gecode::Iter::Ranges::RangeListIter
Iterator over range lists.
Definition:
ranges-list.hpp:45
Gecode::Iter::Ranges::Union::i
I i
First iterator.
Definition:
ranges-union.hpp:51
Gecode::Iter::Ranges::NaryUnion::init
void init(Region &r, I &i)
Initialize with single iterator i.
Definition:
ranges-union.hpp:284
Gecode::Iter::Ranges::Union::j
J j
Second iterator.
Definition:
ranges-union.hpp:53
Gecode::Iter::Ranges::RangeListIter::min
int min(void) const
Return smallest value of range.
Definition:
ranges-list.hpp:249
Gecode::Iter::Ranges::RangeListIter::set
void set(RangeList *l)
Set range lists.
Definition:
ranges-list.hpp:179
Gecode::Iter::Ranges::NaryUnion::f
RangeList * f
Freelist used for allocation.
Definition:
ranges-union.hpp:81
Gecode::Iter::Ranges::Union
Range iterator for computing union (binary)
Definition:
ranges-union.hpp:48
Gecode::Iter::Ranges::RangeListIter::RangeList::min
int min
Minimum and maximum of a range.
Definition:
ranges-list.hpp:51
Gecode::Iter::Ranges::RangeListIter::RangeList::next
RangeList * next
Next element.
Definition:
ranges-list.hpp:53
Gecode::Iter::Ranges::Union::Union
Union(void)
Default constructor.
Definition:
ranges-union.hpp:159
Gecode::Iter::Ranges::NaryUnion::NaryUnion
NaryUnion(void)
Default constructor.
Definition:
ranges-union.hpp:279
Gecode::Iter::Ranges::RangeListIter::init
void init(Region &r)
Initialize.
Definition:
ranges-list.hpp:140
Gecode::Iter::Ranges::RangeListIter::get
RangeList * get(void) const
Get head of current range list.
Definition:
ranges-list.hpp:184
Gecode::Iter::Ranges::RangeListIter::h
RangeList * h
Head of range list.
Definition:
ranges-list.hpp:66
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:238
Gecode::Float::Limits::max
const FloatNum max
Largest allowed float value.
Definition:
float.hh:848
Gecode::Iter::Ranges::RangeListIter::c
RangeList * c
Current list element.
Definition:
ranges-list.hpp:68