Generated on Thu Jan 16 2025 00:00:00 for Gecode by doxygen 1.14.0
ranges-inter.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 Inter : public MinMax {
45 protected:
47 I i;
49 J j;
50 public:
52
53
54 Inter(void);
56 Inter(I& i, J& j);
58 void init(I& i, J& j);
60
62
63
64 void operator ++(void);
66 };
67
68
74 class NaryInter : public RangeListIter {
75 protected:
78 public:
80
81
82 NaryInter(void);
84 template<class I>
85 NaryInter(Region& r, I& i);
87 template<class I, class J>
88 NaryInter(Region& r, I& i, J& j);
90 template<class I>
91 NaryInter(Region& r, I* i, int n);
93 template<class I>
94 void init(Region& r, I& i);
96 template<class I, class J>
97 void init(Region& r, I& i, J& j);
99 template<class I>
100 void init(Region& r, I* i, int n);
102 template<class I>
103 void operator &=(I& i);
105 NaryInter& operator =(const NaryInter& m);
107 };
108
109
110
111 /*
112 * Binary intersection
113 *
114 */
115
116 template<class I, class J>
117 inline void
119 if (!i() || !j()) goto done;
120 do {
121 while (i() && (i.max() < j.min())) ++i;
122 if (!i()) goto done;
123 while (j() && (j.max() < i.min())) ++j;
124 if (!j()) goto done;
125 } while (i.max() < j.min());
126 // Now the intervals overlap: consume the smaller interval
127 ma = std::min(i.max(),j.max());
128 mi = std::max(i.min(),j.min());
129 if (i.max() < j.max()) ++i; else ++j;
130 return;
131 done:
132 finish();
133 }
134
135 template<class I, class J>
138
139 template<class I, class J>
141 Inter<I,J>::Inter(I& i0, J& j0)
142 : i(i0), j(j0) {
143 operator ++();
144 }
145
146 template<class I, class J>
147 forceinline void
148 Inter<I,J>::init(I& i0, J& j0) {
149 i = i0; j = j0;
150 operator ++();
151 }
152
153
154 /*
155 * Nary intersection
156 *
157 */
158
161
162 template<class I>
163 forceinline void
166 f = NULL;
167 set(copy(i));
168 }
169
170 template<class I, class J>
171 forceinline void
172 NaryInter::init(Region& r, I& i, J& j) {
174 f = NULL;
175 RangeList* h;
176 RangeList** c = &h;
177 while (i() && j()) {
178 do {
179 while (i() && (i.max() < j.min())) ++i;
180 if (!i()) goto done;
181 while (j() && (j.max() < i.min())) ++j;
182 if (!j()) goto done;
183 } while (i.max() < j.min());
184 // Now the intervals overlap: consume the smaller interval
185 RangeList* t = range(std::max(i.min(),j.min()),
186 std::min(i.max(),j.max()));
187 *c = t; c = &t->next;
188 if (i.max() < j.max()) ++i; else ++j;
189 }
190 done:
191 *c = NULL;
192 set(h);
193 }
194
195 template<class I>
196 forceinline void
197 NaryInter::init(Region& r, I* i, int n) {
199 f = NULL;
200 if ((n > 0) && i[0]()) {
201 RangeList* h;
202 RangeList** c = &h;
203
204 int min = i[0].min();
205 while (i[0]()) {
206 // Initialize with last interval
207 int max = i[0].max();
208 // Intersect with all other intervals
209 restart:
210 for (int j=n; j--;) {
211 // Skip intervals that are too small
212 while (i[j]() && (i[j].max() < min))
213 ++i[j];
214 if (!i[j]())
215 goto done;
216 if (i[j].min() > max) {
217 min=i[j].min();
218 max=i[j].max();
219 goto restart;
220 }
221 // Now the intervals overlap
222 if (min < i[j].min())
223 min = i[j].min();
224 if (max > i[j].max())
225 max = i[j].max();
226 }
227 RangeList* t = range(min,max);
228 *c = t; c = &t->next;
229 // The next interval must be at least two elements away
230 min = max + 2;
231 }
232 done:
233 *c = NULL;
234 set(h);
235 }
236 }
237
238 template<class I>
241 init(r, i);
242 }
243 template<class I, class J>
246 init(r, i, j);
247 }
248 template<class I>
251 init(r, i, n);
252 }
253
254 template<class I>
255 forceinline void
257 RangeList* j = get();
258 // The new rangelist
259 RangeList* h;
260 RangeList** c = &h;
261 while (i() && (j != NULL)) {
262 do {
263 while (i() && (i.max() < j->min))
264 ++i;
265 if (!i()) goto done;
266 while ((j != NULL) && (j->max < i.min())) {
267 RangeList* t = j->next;
268 j->next = f; f = j;
269 j = t;
270 }
271 if (j == NULL) goto done;
272 } while (i.max() < j->min);
273 // Now the intervals overlap: consume the smaller interval
274 RangeList* t = range(std::max(i.min(),j->min),
275 std::min(i.max(),j->max),f);
276 *c = t; c = &t->next;
277 if (i.max() < j->max) {
278 ++i;
279 } else {
280 RangeList* tn = j->next;
281 j->next = f; f = j;
282 j = tn;
283 }
284 }
285 done:
286 // Put remaining elements into freelist
287 while (j != NULL) {
288 RangeList* t = j->next;
289 j->next = f; f = j;
290 j = t;
291 }
292 *c = NULL;
293 set(h);
294 }
295
298 f = NULL;
299 return static_cast<NaryInter&>(RangeListIter::operator =(m));
300 }
301
302}}}
303
304// STATISTICS: iter-any
305
void operator++(void)
Move iterator to next range (if possible)
void init(I &i, J &j)
Initialize with iterator i and j.
Inter(void)
Default constructor.
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 intersection of iterators.
NaryInter & operator=(const NaryInter &m)
Assignment operator (both iterators must be allocated from the same region)
NaryInter(void)
Default constructor.
void init(Region &r, I &i)
Initialize with single iterator i.
void operator&=(I &i)
Add 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.
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