Generated on Tue Feb 11 2025 17:33:26 for Gecode by doxygen 1.12.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
union Gecode::@603::NNF::@65 u
Union depending on nodetype t.
NodeType t
Type of node.
int n
Number of negative literals for node type.
Base for range iterators with explicit min and max.
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.
Iterator over range lists.
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 & 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.
Range iterator for computing union (binary)
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
Gecode toplevel namespace
Post propagator for SetVar SetOpType SetVar SetRelType r
Definition set.hh:767
#define forceinline
Definition config.hpp:187