Generated on Thu Jan 16 2025 00:00:00 for Gecode by doxygen 1.14.0
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
36namespace 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
54 Union(void);
56 Union(I& i, J& j);
58 void init(I& i, J& j);
60
62
63
64 void operator ++(void);
66 };
67
68
74 class NaryUnion : public RangeListIter {
75 protected:
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
88 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
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>
156
157 template<class I, class J>
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>
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
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
276 : f(NULL) {}
277
278 template<class I>
279 forceinline void
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) {
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;
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>
328 init(r, i);
329 }
330 template<class I, class J>
333 init(r, i, j);
334 }
335 template<class I>
338 init(r, i, n);
339 }
340
341 template<class I>
342 forceinline void
344 RangeList* u = get();
345 insert(i, u);
346 set(u);
347 }
348
351 f = NULL;
352 return static_cast<NaryUnion&>(RangeListIter::operator =(m));
353 }
354
355}}}
356
357// STATISTICS: iter-any
358
int ma
Maximum of current range.
int mi
Minimum of current range.
MinMax(void)
Default constructor.
void finish(void)
Set range such that iteration stops
Range iterator for union of iterators.
RangeList * f
Freelist used for allocation.
NaryUnion & operator=(const NaryUnion &m)
Assignment operator (both iterators must be allocated from the same region)
void insert(I &i, RangeList *&u)
Insert ranges from i into u.
RangeList * two(I &i, J &j)
Return range list for union of two iterators.
NaryUnion(void)
Default constructor.
void operator|=(I &i)
Add iterator i.
void init(Region &r, I &i)
Initialize with single iterator i.
int min
Minimum and maximum of a range.
RangeList * copy(I &i)
Copy the iterator i to a range list.
int max(void) const
Return largest value of range.
RangeList * get(void) const
Get head of current range list.
void init(Region &r)
Initialize.
RangeListIter(void)
Default constructor.
RangeListIter & operator=(const RangeListIter &i)
Assignment operator.
RangeList * range(int min, int max, RangeList *&f)
Create new range possibly from freelist f and init.
void set(RangeList *l)
Set range lists.
RangeList * c
Current list element.
RangeList * h
Head of range list.
int min(void) const
Return smallest value of range.
Union(void)
Default constructor.
void operator++(void)
Move iterator to next range (if possible)
void init(I &i, J &j)
Initialize with iterator i and j.
Handle to region.
Definition region.hpp:55
Range iterators.
Definition iter.hh:43
Range and value iterators.
Definition iter.hh:41
Gecode toplevel namespace
Post propagator for SetVar SetOpType SetVar SetRelType r
Definition set.hh:773
#define forceinline
Definition config.hpp:194