Generated on Thu Jan 16 2025 00:00:00 for Gecode by doxygen 1.14.0
range-list.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 * Contributing authors:
7 * Guido Tack <tack@gecode.org>
8 *
9 * Copyright:
10 * Christian Schulte, 2004
11 * Guido Tack, 2004
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
38namespace Gecode {
39
49 class RangeList : public FreeList {
50 protected:
52 int _min;
54 int _max;
55 public:
57
58
59 RangeList(void);
61 RangeList(int min, int max);
63 RangeList(int min, int max, RangeList* n);
65
67
68
69 int min(void) const;
71 int max(void) const;
73 unsigned int width(void) const;
74
76 RangeList* next(void) const;
78 RangeList** nextRef(void);
80
82
83
84 void min(int n);
86 void max(int n);
88 void next(RangeList* n);
90
92
93
94 template<class Iter>
95 static void copy(Space& home, RangeList*& r, Iter& i);
97 template<class Iter>
98 static void overwrite(Space& home, RangeList*& r, Iter& i);
100 template<class I>
101 static void insert(Space& home, RangeList*& r, I& i);
103
105
106
107 void dispose(Space& home, RangeList* l);
109 void dispose(Space& home);
110
112 static void* operator new(size_t s, Space& home);
114 static void* operator new(size_t s, void* p);
116 static void operator delete(void*);
118 static void operator delete(void*, Space& home);
120 static void operator delete(void*, void*);
122 };
123
124 /*
125 * Range lists
126 *
127 */
128
131
135
138 : _min(min), _max(max) {}
139
141 RangeList::next(void) const {
142 return static_cast<RangeList*>(FreeList::next());
143 }
144
147 return reinterpret_cast<RangeList**>(FreeList::nextRef());
148 }
149
150 forceinline void
152 _min = n;
153 }
154 forceinline void
156 _max = n;
157 }
158 forceinline void
162
163 forceinline int
164 RangeList::min(void) const {
165 return _min;
166 }
167 forceinline int
168 RangeList::max(void) const {
169 return _max;
170 }
171 forceinline unsigned int
172 RangeList::width(void) const {
173 return static_cast<unsigned int>(_max - _min + 1);
174 }
175
176
177 forceinline void
178 RangeList::operator delete(void*) {}
179
180 forceinline void
181 RangeList::operator delete(void*, Space&) {
183 }
184
185 forceinline void
186 RangeList::operator delete(void*, void*) {
188 }
189
190 forceinline void*
191 RangeList::operator new(size_t, Space& home) {
192 return home.fl_alloc<sizeof(RangeList)>();
193 }
194
195 forceinline void*
196 RangeList::operator new(size_t, void* p) {
197 return p;
198 }
199
200 forceinline void
202 home.fl_dispose<sizeof(RangeList)>(this,l);
203 }
204
205 forceinline void
207 RangeList* l = this;
208 while (l->next() != NULL)
209 l=l->next();
210 dispose(home,l);
211 }
212
213 template<class Iter>
214 forceinline void
216 RangeList sentinel; sentinel.next(r);
217 RangeList* p = &sentinel;
218 while (i()) {
219 RangeList* n = new (home) RangeList(i.min(),i.max());
220 p->next(n); p=n; ++i;
221 }
222 p->next(NULL);
223 r = sentinel.next();
224 }
225
226 template<class Iter>
227 forceinline void
229 RangeList sentinel; sentinel.next(r);
230 RangeList* p = &sentinel;
231 RangeList* c = p->next();
232 while ((c != NULL) && i()) {
233 c->min(i.min()); c->max(i.max());
234 p=c; c=c->next(); ++i;
235 }
236 if ((c == NULL) && !i())
237 return;
238 if (c == NULL) {
239 assert(i());
240 // New elements needed
241 do {
242 RangeList* n = new (home) RangeList(i.min(),i.max());
243 p->next(n); p=n; ++i;
244 } while (i());
245 } else {
246 // Dispose excess elements
247 while (c->next() != NULL)
248 c=c->next();
249 p->next()->dispose(home,c);
250 }
251 p->next(NULL);
252 r = sentinel.next();
253 }
254
255 template<class I>
256 forceinline void
258 RangeList sentinel;
259 sentinel.next(r);
260 RangeList* p = &sentinel;
261 RangeList* c = p->next();
262 while ((c != NULL) && i()) {
263 if ((c->max()+1 < i.min())) {
264 p=c; c=c->next();
265 } else if (i.max()+1 < c->min()) {
266 RangeList* n = new (home) RangeList(i.min(),i.max(),c);
267 p->next(n); p=n; ++i;
268 } else {
269 int min = std::min(c->min(),i.min());
270 int max = std::max(c->max(),i.max());
271 RangeList* f=c;
272 p=c; c=c->next(); ++i;
273 next:
274 if ((c != NULL) && (c->min() <= max+1)) {
275 max = std::max(max,c->max());
276 p=c; c=c->next();
277 goto next;
278 }
279 if (i() && (i.min() <= max+1)) {
280 max = std::max(max,i.max());
281 ++i;
282 goto next;
283 }
284 // Dispose now unused elements
285 if (f->next() != p)
286 f->next()->dispose(home,p);
287 f->min(min); f->max(max); f->next(c);
288 }
289 }
290 if (c == NULL) {
291 while (i()) {
292 RangeList* n = new (home) RangeList(i.min(),i.max());
293 p->next(n); p=n;
294 ++i;
295 }
296 p->next(NULL);
297 }
298 r = sentinel.next();
299 }
300
301}
302// STATISTICS: kernel-other
friend FloatVal max(const FloatVal &x, const FloatVal &y)
Definition val.hpp:386
friend FloatVal min(const FloatVal &x, const FloatVal &y)
Definition val.hpp:398
FreeList ** nextRef(void)
Return pointer to next link in freelist object.
Definition manager.hpp:253
FreeList(void)
Use uninitialized.
Definition manager.hpp:241
FreeList * next(void) const
Return next freelist object.
Definition manager.hpp:248
Lists of ranges (intervals)
int max(void) const
Return maximum.
int min(void) const
Return minimum.
void dispose(Space &home, RangeList *l)
Free memory for all elements between this and l (inclusive)
int _min
Minimum of range.
RangeList * next(void) const
Return next element.
unsigned int width(void) const
Return width (distance between maximum and minimum)
static void overwrite(Space &home, RangeList *&r, Iter &i)
Overwrite rangelist r with ranges from range iterator i.
RangeList ** nextRef(void)
Return pointer to next element.
RangeList(void)
Default constructor (noop)
static void insert(Space &home, RangeList *&r, I &i)
Insert (as union) ranges from iterator i into r.
static void copy(Space &home, RangeList *&r, Iter &i)
Create rangelist r from range iterator i.
int _max
Maximum of range.
Computation spaces.
Definition core.hpp:1744
void fl_dispose(FreeList *f, FreeList *l)
Return freelist-managed memory to freelist.
Definition core.hpp:2831
Base * next(void) const
Return next test.
Definition test.hpp:58
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
#define GECODE_NEVER
Assert that this command is never executed.
Definition macros.hpp:56