Generated on Sat Apr 10 2021 00:00:00 for Gecode by doxygen 1.9.1
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 
38 namespace Gecode {
39 
49  class RangeList : public FreeList {
50  protected:
52  int _min;
54  int _max;
55  public:
57 
58  RangeList(void);
61  RangeList(int min, int max);
63  RangeList(int min, int max, RangeList* n);
65 
67 
68  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  void min(int n);
86  void max(int n);
88  void next(RangeList* n);
90 
92 
93  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  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 
134  : FreeList(n), _min(min), _max(max) {}
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
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
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
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(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
NNF * l
Left subtree.
Definition: bool-expr.cpp:240
int p
Number of positive literals for node type.
Definition: bool-expr.cpp:232
int n
Number of negative literals for node type.
Definition: bool-expr.cpp:234
NNF * r
Right subtree.
Definition: bool-expr.cpp:242
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
Base-class for freelist-managed objects.
Definition: manager.hpp:98
FreeList ** nextRef(void)
Return pointer to next link in freelist object.
Definition: manager.hpp:253
FreeList * next(void) const
Return next freelist object.
Definition: manager.hpp:248
Lists of ranges (intervals)
Definition: range-list.hpp:49
int max(void) const
Return maximum.
Definition: range-list.hpp:168
int min(void) const
Return minimum.
Definition: range-list.hpp:164
void dispose(Space &home, RangeList *l)
Free memory for all elements between this and l (inclusive)
Definition: range-list.hpp:201
int _min
Minimum of range.
Definition: range-list.hpp:52
RangeList * next(void) const
Return next element.
Definition: range-list.hpp:141
unsigned int width(void) const
Return width (distance between maximum and minimum)
Definition: range-list.hpp:172
static void overwrite(Space &home, RangeList *&r, Iter &i)
Overwrite rangelist r with ranges from range iterator i.
Definition: range-list.hpp:228
RangeList ** nextRef(void)
Return pointer to next element.
Definition: range-list.hpp:146
RangeList(void)
Default constructor (noop)
Definition: range-list.hpp:130
static void insert(Space &home, RangeList *&r, I &i)
Insert (as union) ranges from iterator i into r.
Definition: range-list.hpp:257
static void copy(Space &home, RangeList *&r, Iter &i)
Create rangelist r from range iterator i.
Definition: range-list.hpp:215
int _max
Maximum of range.
Definition: range-list.hpp:54
Computation spaces.
Definition: core.hpp:1742
void fl_dispose(FreeList *f, FreeList *l)
Return freelist-managed memory to freelist.
Definition: core.hpp:2827
Base * next(void) const
Return next test.
Definition: test.hpp:58
const FloatNum max
Largest allowed float value.
Definition: float.hh:844
const FloatNum min
Smallest allowed float value.
Definition: float.hh:846
Gecode::FloatVal c(-8, 8)
Gecode::IntArgs i({1, 2, 3, 4})
Min _min("Int::Min")
Max _max("Int::Max")
#define forceinline
Definition: config.hpp:192
#define GECODE_NEVER
Assert that this command is never executed.
Definition: macros.hpp:56