this repo has no description
dekker.one
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
38 /**
39 * \brief Range iterator for computing union (binary)
40 *
41 * \ingroup FuncIterRanges
42 */
43 template<class I, class J>
44 class Union : public MinMax {
45 protected:
46 /// First iterator
47 I i;
48 /// Second iterator
49 J j;
50 public:
51 /// \name Constructors and initialization
52 //@{
53 /// Default constructor
54 Union(void);
55 /// Initialize with iterator \a i and \a j
56 Union(I& i, J& j);
57 /// Initialize with iterator \a i and \a j
58 void init(I& i, J& j);
59 //@}
60
61 /// \name Iteration control
62 //@{
63 /// Move iterator to next range (if possible)
64 void operator ++(void);
65 //@}
66 };
67
68
69 /**
70 * \brief Range iterator for union of iterators
71 *
72 * \ingroup FuncIterRanges
73 */
74 class NaryUnion : public RangeListIter {
75 protected:
76 /// Freelist used for allocation
77 RangeList* f;
78 /// Return range list for union of two iterators
79 template<class I, class J>
80 RangeList* two(I& i, J& j);
81 /// Insert ranges from \a i into \a u
82 template<class I>
83 void insert(I& i, RangeList*& u);
84 public:
85 /// \name Constructors and initialization
86 //@{
87 /// Default constructor
88 NaryUnion(void);
89 /// Initialize with single iterator \a i
90 template<class I>
91 NaryUnion(Region& r, I& i);
92 /// Initialize with iterators \a i and \a j
93 template<class I, class J>
94 NaryUnion(Region& r, I& i, J& j);
95 /// Initialize with \a n iterators in \a i
96 template<class I>
97 NaryUnion(Region& r, I* i, int n);
98 /// Initialize with single iterator \a i
99 template<class I>
100 void init(Region& r, I& i);
101 /// Initialize with iterators \a i and \a j
102 template<class I, class J>
103 void init(Region& r, I& i, J& j);
104 /// Initialize with \a n iterators in \a i
105 template<class I>
106 void init(Region& r, I* i, int n);
107 /// Add iterator \a i
108 template<class I>
109 void operator |=(I& i);
110 /// Assignment operator (both iterators must be allocated from the same region)
111 NaryUnion& operator =(const NaryUnion& m);
112 //@}
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 = nullptr;
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 != nullptr) && 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 != nullptr) && (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 == nullptr) {
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 = nullptr;
270 }
271 }
272
273
274 forceinline
275 NaryUnion::NaryUnion(void)
276 : f(nullptr) {}
277
278 template<class I>
279 forceinline void
280 NaryUnion::init(Region& r, I& i) {
281 RangeListIter::init(r);
282 f = nullptr;
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 = nullptr;
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 = nullptr;
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 = nullptr;
352 return static_cast<NaryUnion&>(RangeListIter::operator =(m));
353 }
354
355}}}
356
357// STATISTICS: iter-any
358