Generated on Thu Jan 31 2019 20:56:39 for Gecode by doxygen 1.8.15
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  * Last modified:
14  * $Date: 2016-05-23 22:18:23 +0200 (Mon, 23 May 2016) $ by $Author: schulte $
15  * $Revision: 15073 $
16  *
17  * This file is part of Gecode, the generic constraint
18  * development environment:
19  * http://www.gecode.org
20  *
21  * Permission is hereby granted, free of charge, to any person obtaining
22  * a copy of this software and associated documentation files (the
23  * "Software"), to deal in the Software without restriction, including
24  * without limitation the rights to use, copy, modify, merge, publish,
25  * distribute, sublicense, and/or sell copies of the Software, and to
26  * permit persons to whom the Software is furnished to do so, subject to
27  * the following conditions:
28  *
29  * The above copyright notice and this permission notice shall be
30  * included in all copies or substantial portions of the Software.
31  *
32  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
33  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
34  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
35  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
36  * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
37  * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
38  * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
39  *
40  */
41 
42 namespace Gecode {
43 
53  class RangeList : public FreeList {
54  protected:
56  int _min;
58  int _max;
59  public:
61 
62  RangeList(void);
65  RangeList(int min, int max);
67  RangeList(int min, int max, RangeList* n);
69 
71 
72  int min(void) const;
75  int max(void) const;
77  unsigned int width(void) const;
78 
80  RangeList* next(void) const;
82  RangeList** nextRef(void);
84 
86 
87  void min(int n);
90  void max(int n);
92  void next(RangeList* n);
94 
96 
97  template<class Iter>
99  static void copy(Space& home, RangeList*& r, Iter& i);
101  template<class Iter>
102  static void overwrite(Space& home, RangeList*& r, Iter& i);
104  template<class I>
105  static void insert(Space& home, RangeList*& r, I& i);
107 
109 
110  void dispose(Space& home, RangeList* l);
113  void dispose(Space& home);
114 
116  static void* operator new(size_t s, Space& home);
118  static void* operator new(size_t s, void* p);
120  static void operator delete(void*);
122  static void operator delete(void*, Space& home);
124  static void operator delete(void*, void*);
126  };
127 
128  /*
129  * Range lists
130  *
131  */
132 
135 
138  : FreeList(n), _min(min), _max(max) {}
139 
142  : _min(min), _max(max) {}
143 
145  RangeList::next(void) const {
146  return static_cast<RangeList*>(FreeList::next());
147  }
148 
151  return reinterpret_cast<RangeList**>(FreeList::nextRef());
152  }
153 
154  forceinline void
156  _min = n;
157  }
158  forceinline void
160  _max = n;
161  }
162  forceinline void
164  FreeList::next(n);
165  }
166 
167  forceinline int
168  RangeList::min(void) const {
169  return _min;
170  }
171  forceinline int
172  RangeList::max(void) const {
173  return _max;
174  }
175  forceinline unsigned int
176  RangeList::width(void) const {
177  return static_cast<unsigned int>(_max - _min + 1);
178  }
179 
180 
181  forceinline void
182  RangeList::operator delete(void*) {}
183 
184  forceinline void
185  RangeList::operator delete(void*, Space&) {
186  GECODE_NEVER;
187  }
188 
189  forceinline void
190  RangeList::operator delete(void*, void*) {
191  GECODE_NEVER;
192  }
193 
194  forceinline void*
195  RangeList::operator new(size_t, Space& home) {
196  return home.fl_alloc<sizeof(RangeList)>();
197  }
198 
199  forceinline void*
200  RangeList::operator new(size_t, void* p) {
201  return p;
202  }
203 
204  forceinline void
206  home.fl_dispose<sizeof(RangeList)>(this,l);
207  }
208 
209  forceinline void
211  RangeList* l = this;
212  while (l->next() != NULL)
213  l=l->next();
214  dispose(home,l);
215  }
216 
217  template<class Iter>
218  forceinline void
219  RangeList::copy(Space& home, RangeList*& r, Iter& i) {
220  RangeList sentinel; sentinel.next(r);
221  RangeList* p = &sentinel;
222  while (i()) {
223  RangeList* n = new (home) RangeList(i.min(),i.max());
224  p->next(n); p=n; ++i;
225  }
226  p->next(NULL);
227  r = sentinel.next();
228  }
229 
230  template<class Iter>
231  forceinline void
233  RangeList sentinel; sentinel.next(r);
234  RangeList* p = &sentinel;
235  RangeList* c = p->next();
236  while ((c != NULL) && i()) {
237  c->min(i.min()); c->max(i.max());
238  p=c; c=c->next(); ++i;
239  }
240  if ((c == NULL) && !i())
241  return;
242  if (c == NULL) {
243  assert(i());
244  // New elements needed
245  do {
246  RangeList* n = new (home) RangeList(i.min(),i.max());
247  p->next(n); p=n; ++i;
248  } while (i());
249  } else {
250  // Dispose excess elements
251  while (c->next() != NULL)
252  c=c->next();
253  p->next()->dispose(home,c);
254  }
255  p->next(NULL);
256  r = sentinel.next();
257  }
258 
259  template<class I>
260  forceinline void
262  RangeList sentinel;
263  sentinel.next(r);
264  RangeList* p = &sentinel;
265  RangeList* c = p->next();
266  while ((c != NULL) && i()) {
267  if ((c->max()+1 < i.min())) {
268  p=c; c=c->next();
269  } else if (i.max()+1 < c->min()) {
270  RangeList* n = new (home) RangeList(i.min(),i.max(),c);
271  p->next(n); p=n; ++i;
272  } else {
273  int min = std::min(c->min(),i.min());
274  int max = std::max(c->max(),i.max());
275  RangeList* f=c;
276  p=c; c=c->next(); ++i;
277  next:
278  if ((c != NULL) && (c->min() <= max+1)) {
279  max = std::max(max,c->max());
280  p=c; c=c->next();
281  goto next;
282  }
283  if (i() && (i.min() <= max+1)) {
284  max = std::max(max,i.max());
285  ++i;
286  goto next;
287  }
288  // Dispose now unused elements
289  if (f->next() != p)
290  f->next()->dispose(home,p);
291  f->min(min); f->max(max); f->next(c);
292  }
293  }
294  if (c == NULL) {
295  while (i()) {
296  RangeList* n = new (home) RangeList(i.min(),i.max());
297  p->next(n); p=n;
298  ++i;
299  }
300  p->next(NULL);
301  }
302  r = sentinel.next();
303  }
304 
305 }
306 // STATISTICS: kernel-other
NNF * l
Left subtree.
Definition: bool-expr.cpp:244
const FloatNum max
Largest allowed float value.
Definition: float.hh:848
FreeList * next(void) const
Return next freelist object.
RangeList * next(void) const
Return next element.
Definition: range-list.hpp:145
void max(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Definition: arithmetic.cpp:53
int min(void) const
Return minimum.
Definition: range-list.hpp:168
Computation spaces.
Definition: core.hpp:1748
Min _min("Int::Min")
Gecode::FloatVal c(-8, 8)
int p
Number of positive literals for node type.
Definition: bool-expr.cpp:236
const FloatNum min
Smallest allowed float value.
Definition: float.hh:850
Gecode::IntArgs i(4, 1, 2, 3, 4)
int n
Number of negative literals for node type.
Definition: bool-expr.cpp:238
Max _max("Int::Max")
int max(void) const
Return maximum.
Definition: range-list.hpp:172
FreeList ** nextRef(void)
Return pointer to next link in freelist object.
int _max
Maximum of range.
Definition: range-list.hpp:58
Post propagator for SetVar SetOpType SetVar SetRelType r
Definition: set.hh:784
void min(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Definition: arithmetic.cpp:71
static void copy(Space &home, RangeList *&r, Iter &i)
Create rangelist r from range iterator i.
Definition: range-list.hpp:219
Post propagator for f(x \diamond_{\mathit{op}} y) \sim_r z \f$ void rel(Home home
#define forceinline
Definition: config.hpp:173
Base-class for freelist-managed objects.
void fl_dispose(FreeList *f, FreeList *l)
Return freelist-managed memory to freelist.
Definition: core.hpp:2858
void dispose(Space &home, RangeList *l)
Free memory for all elements between this and l (inclusive)
Definition: range-list.hpp:205
Lists of ranges (intervals)
Definition: range-list.hpp:53
static void overwrite(Space &home, RangeList *&r, Iter &i)
Overwrite rangelist r with ranges from range iterator i.
Definition: range-list.hpp:232
static void insert(Space &home, RangeList *&r, I &i)
Insert (as union) ranges from iterator i into r.
Definition: range-list.hpp:261
Gecode toplevel namespace
int _min
Minimum of range.
Definition: range-list.hpp:56
friend FloatVal max(const FloatVal &x, const FloatVal &y)
Definition: val.hpp:390
RangeList ** nextRef(void)
Return pointer to next element.
Definition: range-list.hpp:150
friend FloatVal min(const FloatVal &x, const FloatVal &y)
Definition: val.hpp:402
#define GECODE_NEVER
Assert that this command is never executed.
Definition: macros.hpp:60
unsigned int width(void) const
Return width (distance between maximum and minimum)
Definition: range-list.hpp:176
RangeList(void)
Default constructor (noop)
Definition: range-list.hpp:134