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 * 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
40 /**
41 * \brief Lists of ranges (intervals)
42 *
43 * This class implements a simple datastructure for storing sets of
44 * integers as lists of ranges (intervals). Memory is managed as
45 * space-allocated free lists.
46 *
47 * \ingroup FuncMemSpace
48 */
49 class RangeList : public FreeList {
50 protected:
51 /// Minimum of range
52 int _min;
53 /// Maximum of range
54 int _max;
55 public:
56 /// \name Constructors
57 //@{
58 /// Default constructor (noop)
59 RangeList(void);
60 /// Initialize with minimum \a min and maximum \a max
61 RangeList(int min, int max);
62 /// Initialize with minimum \a min and maximum \a max and successor \a n
63 RangeList(int min, int max, RangeList* n);
64 //@}
65
66 /// \name Access
67 //@{
68 /// Return minimum
69 int min(void) const;
70 /// Return maximum
71 int max(void) const;
72 /// Return width (distance between maximum and minimum)
73 unsigned int width(void) const;
74
75 /// Return next element
76 RangeList* next(void) const;
77 /// Return pointer to next element
78 RangeList** nextRef(void);
79 //@}
80
81 /// \name Update
82 //@{
83 /// Set minimum to \a n
84 void min(int n);
85 /// Set maximum to \a n
86 void max(int n);
87 /// Set next range to \a n
88 void next(RangeList* n);
89 //@}
90
91 /// \name Iterator operations
92 //@{
93 /// Create rangelist \a r from range iterator \a i
94 template<class Iter>
95 static void copy(Space& home, RangeList*& r, Iter& i);
96 /// Overwrite rangelist \a r with ranges from range iterator \a i
97 template<class Iter>
98 static void overwrite(Space& home, RangeList*& r, Iter& i);
99 /// Insert (as union) ranges from iterator \a i into \a r
100 template<class I>
101 static void insert(Space& home, RangeList*& r, I& i);
102 //@}
103
104 /// \name Memory management
105 //@{
106 /// Free memory for all elements between this and \a l (inclusive)
107 void dispose(Space& home, RangeList* l);
108 /// Free memory for all elements reachable from this
109 void dispose(Space& home);
110
111 /// Allocate memory from space
112 static void* operator new(size_t s, Space& home);
113 /// Placement-new operator (noop)
114 static void* operator new(size_t s, void* p);
115 /// No-op (for exceptions)
116 static void operator delete(void*);
117 /// No-op (use dispose instead)
118 static void operator delete(void*, Space& home);
119 /// No-op (use dispose instead)
120 static void operator delete(void*, void*);
121 //@}
122 };
123
124 /*
125 * Range lists
126 *
127 */
128
129 forceinline
130 RangeList::RangeList(void) {}
131
132 forceinline
133 RangeList::RangeList(int min, int max, RangeList* n)
134 : FreeList(n), _min(min), _max(max) {}
135
136 forceinline
137 RangeList::RangeList(int min, int max)
138 : _min(min), _max(max) {}
139
140 forceinline RangeList*
141 RangeList::next(void) const {
142 return static_cast<RangeList*>(FreeList::next());
143 }
144
145 forceinline RangeList**
146 RangeList::nextRef(void) {
147 return reinterpret_cast<RangeList**>(FreeList::nextRef());
148 }
149
150 forceinline void
151 RangeList::min(int n) {
152 _min = n;
153 }
154 forceinline void
155 RangeList::max(int n) {
156 _max = n;
157 }
158 forceinline void
159 RangeList::next(RangeList* n) {
160 FreeList::next(n);
161 }
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&) {
182 GECODE_NEVER;
183 }
184
185 forceinline void
186 RangeList::operator delete(void*, void*) {
187 GECODE_NEVER;
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
201 RangeList::dispose(Space& home, RangeList* l) {
202 home.fl_dispose<sizeof(RangeList)>(this,l);
203 }
204
205 forceinline void
206 RangeList::dispose(Space& home) {
207 RangeList* l = this;
208 while (l->next() != nullptr)
209 l=l->next();
210 dispose(home,l);
211 }
212
213 template<class Iter>
214 forceinline void
215 RangeList::copy(Space& home, RangeList*& r, Iter& i) {
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(nullptr);
223 r = sentinel.next();
224 }
225
226 template<class Iter>
227 forceinline void
228 RangeList::overwrite(Space& home, RangeList*& r, Iter& i) {
229 RangeList sentinel; sentinel.next(r);
230 RangeList* p = &sentinel;
231 RangeList* c = p->next();
232 while ((c != nullptr) && i()) {
233 c->min(i.min()); c->max(i.max());
234 p=c; c=c->next(); ++i;
235 }
236 if ((c == nullptr) && !i())
237 return;
238 if (c == nullptr) {
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() != nullptr)
248 c=c->next();
249 p->next()->dispose(home,c);
250 }
251 p->next(nullptr);
252 r = sentinel.next();
253 }
254
255 template<class I>
256 forceinline void
257 RangeList::insert(Space& home, RangeList*& r, I& i) {
258 RangeList sentinel;
259 sentinel.next(r);
260 RangeList* p = &sentinel;
261 RangeList* c = p->next();
262 while ((c != nullptr) && 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 != nullptr) && (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 == nullptr) {
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(nullptr);
297 }
298 r = sentinel.next();
299 }
300
301}
302// STATISTICS: kernel-other