Generated on Mon Jul 27 2020 00:00:00 for Gecode by doxygen 1.8.18
ranges-union.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 
36 namespace Gecode { namespace Iter { namespace Ranges {
37 
43  template<class I, class J>
44  class Union : public MinMax {
45  protected:
47  I i;
49  J j;
50  public:
52 
53  Union(void);
56  Union(I& i, J& j);
58  void init(I& i, J& j);
60 
62 
63  void operator ++(void);
66  };
67 
68 
74  class NaryUnion : public RangeListIter {
75  protected:
79  template<class I, class J>
80  RangeList* two(I& i, J& j);
82  template<class I>
83  void insert(I& i, RangeList*& u);
84  public:
86 
87  NaryUnion(void);
90  template<class I>
91  NaryUnion(Region& r, I& i);
93  template<class I, class J>
94  NaryUnion(Region& r, I& i, J& j);
96  template<class I>
97  NaryUnion(Region& r, I* i, int n);
99  template<class I>
100  void init(Region& r, I& i);
102  template<class I, class J>
103  void init(Region& r, I& i, J& j);
105  template<class I>
106  void init(Region& r, I* i, int n);
108  template<class I>
109  void operator |=(I& i);
111  NaryUnion& operator =(const NaryUnion& m);
113  };
114 
115 
116 
117  /*
118  * Binary union
119  *
120  */
121 
122  template<class I, class J>
123  inline void
125  if (!i() && !j()) {
126  finish(); return;
127  }
128 
129  if (!i() || (j() && (j.max()+1 < i.min()))) {
130  mi = j.min(); ma = j.max(); ++j; return;
131  }
132  if (!j() || (i() && (i.max()+1 < j.min()))) {
133  mi = i.min(); ma = i.max(); ++i; return;
134  }
135 
136  mi = std::min(i.min(),j.min());
137  ma = std::max(i.max(),j.max());
138 
139  ++i; ++j;
140 
141  next:
142  if (i() && (i.min() <= ma+1)) {
143  ma = std::max(ma,i.max()); ++i;
144  goto next;
145  }
146  if (j() && (j.min() <= ma+1)) {
147  ma = std::max(ma,j.max()); ++j;
148  goto next;
149  }
150  }
151 
152 
153  template<class I, class J>
156 
157  template<class I, class J>
159  Union<I,J>::Union(I& i0, J& j0)
160  : i(i0), j(j0) {
161  operator ++();
162  }
163 
164  template<class I, class J>
165  forceinline void
166  Union<I,J>::init(I& i0, J& j0) {
167  i = i0; j = j0;
168  operator ++();
169  }
170 
171 
172 
173  /*
174  * Nary union
175  *
176  */
177 
178  template<class I, class J>
180  NaryUnion::two(I& i, J& j) {
181  RangeList* h;
182  RangeList** c = &h;
183 
184  while (i() && j())
185  if (i.max()+1 < j.min()) {
186  RangeList* t = range(i); ++i;
187  *c = t; c = &t->next;
188  } else if (j.max()+1 < i.min()) {
189  RangeList* t = range(j); ++j;
190  *c = t; c = &t->next;
191  } else {
192  int min = std::min(i.min(),j.min());
193  int max = std::max(i.max(),j.max());
194  ++i; ++j;
195 
196  nexta:
197  if (i() && (i.min() <= max+1)) {
198  max = std::max(max,i.max()); ++i;
199  goto nexta;
200  }
201  if (j() && (j.min() <= max+1)) {
202  max = std::max(max,j.max()); ++j;
203  goto nexta;
204  }
205 
206  RangeList* t = range(min,max);
207  *c = t; c = &t->next;
208  }
209  for ( ; i(); ++i) {
210  RangeList* t = range(i);
211  *c = t; c = &t->next;
212  }
213  for ( ; j(); ++j) {
214  RangeList* t = range(j);
215  *c = t; c = &t->next;
216  }
217  *c = NULL;
218  return h;
219  }
220 
221  template<class I>
222  void
224  // The current rangelist
225  RangeList** c = &u;
226 
227  while ((*c != NULL) && i())
228  if ((*c)->max+1 < i.min()) {
229  // Keep range from union
230  c = &(*c)->next;
231  } else if (i.max()+1 < (*c)->min) {
232  // Copy range from iterator
233  RangeList* t = range(i,f); ++i;
234  // Insert
235  t->next = *c; *c = t; c = &t->next;
236  } else {
237  // Ranges overlap
238  // Compute new minimum
239  (*c)->min = std::min((*c)->min,i.min());
240  // Compute new maximum
241  int max = std::max((*c)->max,i.max());
242 
243  // Scan from the next range in the union
244  RangeList* s = (*c)->next;
245  ++i;
246 
247  nextb:
248  if ((s != NULL) && (s->min <= max+1)) {
249  max = std::max(max,s->max);
250  RangeList* t = s;
251  s = s->next;
252  // Put deleted element into freelist
253  t->next = f; f = t;
254  goto nextb;
255  }
256  if (i() && (i.min() <= max+1)) {
257  max = std::max(max,i.max()); ++i;
258  goto nextb;
259  }
260  // Store computed max and shunt skipped ranges from union
261  (*c)->max = max; (*c)->next = s;
262  }
263  if (*c == NULL) {
264  // Copy remaining ranges from iterator
265  for ( ; i(); ++i) {
266  RangeList* t = range(i,f);
267  *c = t; c = &t->next;
268  }
269  *c = NULL;
270  }
271  }
272 
273 
276  : f(NULL) {}
277 
278  template<class I>
279  forceinline void
282  f = NULL;
283  set(copy(i));
284  }
285 
286  template<class I, class J>
287  forceinline void
288  NaryUnion::init(Region& r, I& i, J& j) {
290  f = NULL;
291  set(two(i,j));
292  }
293 
294  template<class I>
295  forceinline void
296  NaryUnion::init(Region& r, I* i, int n) {
297  f = NULL;
299 
300  int m = 0;
301  while ((m < n) && !i[m]())
302  m++;
303 
304  // Union is empty
305  if (m >= n)
306  return;
307 
308  n--;
309  while (!i[n]())
310  n--;
311 
312  if (m == n) {
313  // Union is just a single iterator
314  set(copy(i[m]));
315  } else {
316  // At least two iterators
317  RangeList* u = two(i[m++],i[n--]);
318  // Insert the remaining iterators
319  for ( ; m<=n; m++)
320  insert(i[m], u);
321  set(u);
322  }
323  }
324 
325  template<class I>
328  init(r, i);
329  }
330  template<class I, class J>
333  init(r, i, j);
334  }
335  template<class I>
338  init(r, i, n);
339  }
340 
341  template<class I>
342  forceinline void
344  RangeList* u = get();
345  insert(i, u);
346  set(u);
347  }
348 
351  f = NULL;
352  return static_cast<NaryUnion&>(RangeListIter::operator =(m));
353  }
354 
355 }}}
356 
357 // STATISTICS: iter-any
358 
NaryUnion & operator=(const NaryUnion &m)
Assignment operator (both iterators must be allocated from the same region)
void insert(I &i, RangeList *&u)
Insert ranges from i into u.
RangeList * range(int min, int max, RangeList *&f)
Create new range possibly from freelist f and init.
void init(I &i, J &j)
Initialize with iterator i and j.
NodeType t
Type of node.
Definition: bool-expr.cpp:230
const FloatNum min
Smallest allowed float value.
Definition: float.hh:846
RangeListIter & operator=(const RangeListIter &i)
Assignment operator.
RangeList * two(I &i, J &j)
Return range list for union of two iterators.
Gecode toplevel namespace
union Gecode::@602::NNF::@65 u
Union depending on nodetype t.
Base for range iterators with explicit min and max.
int max(void) const
Return largest value of range.
Range list class.
Definition: ranges-list.hpp:44
void operator|=(I &i)
Add iterator i.
RangeList * copy(I &i)
Copy the iterator i to a range list.
Handle to region.
Definition: region.hpp:55
int max
Definition: ranges-list.hpp:47
Post propagator for SetVar SetOpType SetVar SetRelType r
Definition: set.hh:767
void operator++(void)
Move iterator to next range (if possible)
Range iterator for union of iterators.
Iterator over range lists.
Definition: ranges-list.hpp:41
I i
First iterator.
void init(Region &r, I &i)
Initialize with single iterator i.
J j
Second iterator.
int min(void) const
Return smallest value of range.
void set(RangeList *l)
Set range lists.
RangeList * f
Freelist used for allocation.
Range iterator for computing union (binary)
int min
Minimum and maximum of a range.
Definition: ranges-list.hpp:47
RangeList * next
Next element.
Definition: ranges-list.hpp:49
Union(void)
Default constructor.
NaryUnion(void)
Default constructor.
void init(Region &r)
Initialize.
#define forceinline
Definition: config.hpp:185
RangeList * get(void) const
Get head of current range list.
RangeList * h
Head of range list.
Definition: ranges-list.hpp:62
Post propagator for f(x \diamond_{\mathit{op}} y) \sim_r z \f$ void rel(Home home
int n
Number of negative literals for node type.
Definition: bool-expr.cpp:234
Gecode::IntArgs i({1, 2, 3, 4})
const FloatNum max
Largest allowed float value.
Definition: float.hh:844
RangeList * c
Current list element.
Definition: ranges-list.hpp:64