Generated on Sat Feb 7 2015 02:01:26 for Gecode by doxygen 1.8.9.1
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  * Last modified:
10  * $Date: 2013-07-11 19:23:04 +0200 (Thu, 11 Jul 2013) $ by $Author: schulte $
11  * $Revision: 13866 $
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 #include <algorithm>
39 
40 namespace Gecode { namespace Iter { namespace Ranges {
41 
47  template<class I, class J>
48  class Union : public MinMax {
49  protected:
51  I i;
53  J j;
54  public:
56 
57  Union(void);
60  Union(I& i, J& j);
62  void init(I& i, J& j);
64 
66 
67  void operator ++(void);
70  };
71 
72 
78  class NaryUnion : public RangeListIter {
79  protected:
83  template<class I, class J>
84  RangeList* two(I& i, J& j);
86  template<class I>
87  void insert(I& i, RangeList*& u);
88  public:
90 
91  NaryUnion(void);
94  template<class I>
95  NaryUnion(Region& r, I& i);
97  template<class I, class J>
98  NaryUnion(Region& r, I& i, J& j);
100  template<class I>
101  NaryUnion(Region& r, I* i, int n);
103  template<class I>
104  void init(Region& r, I& i);
106  template<class I, class J>
107  void init(Region& r, I& i, J& j);
109  template<class I>
110  void init(Region& r, I* i, int n);
112  template<class I>
113  void operator |=(I& i);
115  NaryUnion& operator =(const NaryUnion& m);
117  };
118 
119 
120 
121  /*
122  * Binary union
123  *
124  */
125 
126  template<class I, class J>
127  inline void
129  if (!i() && !j()) {
130  finish(); return;
131  }
132 
133  if (!i() || (j() && (j.max()+1 < i.min()))) {
134  mi = j.min(); ma = j.max(); ++j; return;
135  }
136  if (!j() || (i() && (i.max()+1 < j.min()))) {
137  mi = i.min(); ma = i.max(); ++i; return;
138  }
139 
140  mi = std::min(i.min(),j.min());
141  ma = std::max(i.max(),j.max());
142 
143  ++i; ++j;
144 
145  next:
146  if (i() && (i.min() <= ma+1)) {
147  ma = std::max(ma,i.max()); ++i;
148  goto next;
149  }
150  if (j() && (j.min() <= ma+1)) {
151  ma = std::max(ma,j.max()); ++j;
152  goto next;
153  }
154  }
155 
156 
157  template<class I, class J>
160 
161  template<class I, class J>
163  Union<I,J>::Union(I& i0, J& j0)
164  : i(i0), j(j0) {
165  operator ++();
166  }
167 
168  template<class I, class J>
169  forceinline void
170  Union<I,J>::init(I& i0, J& j0) {
171  i = i0; j = j0;
172  operator ++();
173  }
174 
175 
176 
177  /*
178  * Nary union
179  *
180  */
181 
182  template<class I, class J>
184  NaryUnion::two(I& i, J& j) {
185  RangeList* h;
186  RangeList** c = &h;
187 
188  while (i() && j())
189  if (i.max()+1 < j.min()) {
190  RangeList* t = range(i); ++i;
191  *c = t; c = &t->next;
192  } else if (j.max()+1 < i.min()) {
193  RangeList* t = range(j); ++j;
194  *c = t; c = &t->next;
195  } else {
196  int min = std::min(i.min(),j.min());
197  int max = std::max(i.max(),j.max());
198  ++i; ++j;
199 
200  nexta:
201  if (i() && (i.min() <= max+1)) {
202  max = std::max(max,i.max()); ++i;
203  goto nexta;
204  }
205  if (j() && (j.min() <= max+1)) {
206  max = std::max(max,j.max()); ++j;
207  goto nexta;
208  }
209 
210  RangeList* t = range(min,max);
211  *c = t; c = &t->next;
212  }
213  for ( ; i(); ++i) {
214  RangeList* t = range(i);
215  *c = t; c = &t->next;
216  }
217  for ( ; j(); ++j) {
218  RangeList* t = range(j);
219  *c = t; c = &t->next;
220  }
221  *c = NULL;
222  return h;
223  }
224 
225  template<class I>
226  void
228  // The current rangelist
229  RangeList** c = &u;
230 
231  while ((*c != NULL) && i())
232  if ((*c)->max+1 < i.min()) {
233  // Keep range from union
234  c = &(*c)->next;
235  } else if (i.max()+1 < (*c)->min) {
236  // Copy range from iterator
237  RangeList* t = range(i,f); ++i;
238  // Insert
239  t->next = *c; *c = t; c = &t->next;
240  } else {
241  // Ranges overlap
242  // Compute new minimum
243  (*c)->min = std::min((*c)->min,i.min());
244  // Compute new maximum
245  int max = std::max((*c)->max,i.max());
246 
247  // Scan from the next range in the union
248  RangeList* s = (*c)->next;
249  ++i;
250 
251  nextb:
252  if ((s != NULL) && (s->min <= max+1)) {
253  max = std::max(max,s->max);
254  RangeList* t = s;
255  s = s->next;
256  // Put deleted element into freelist
257  t->next = f; f = t;
258  goto nextb;
259  }
260  if (i() && (i.min() <= max+1)) {
261  max = std::max(max,i.max()); ++i;
262  goto nextb;
263  }
264  // Store computed max and shunt skipped ranges from union
265  (*c)->max = max; (*c)->next = s;
266  }
267  if (*c == NULL) {
268  // Copy remaining ranges from iterator
269  for ( ; i(); ++i) {
270  RangeList* t = range(i,f);
271  *c = t; c = &t->next;
272  }
273  *c = NULL;
274  }
275  }
276 
277 
280  : f(NULL) {}
281 
282  template<class I>
283  forceinline void
286  f = NULL;
287  set(copy(i));
288  }
289 
290  template<class I, class J>
291  forceinline void
292  NaryUnion::init(Region& r, I& i, J& j) {
294  f = NULL;
295  set(two(i,j));
296  }
297 
298  template<class I>
299  forceinline void
300  NaryUnion::init(Region& r, I* i, int n) {
301  f = NULL;
303 
304  int m = 0;
305  while ((m < n) && !i[m]())
306  m++;
307 
308  // Union is empty
309  if (m >= n)
310  return;
311 
312  n--;
313  while (!i[n]())
314  n--;
315 
316  if (m == n) {
317  // Union is just a single iterator
318  set(copy(i[m]));
319  } else {
320  // At least two iterators
321  RangeList* u = two(i[m++],i[n--]);
322  // Insert the remaining iterators
323  for ( ; m<=n; m++)
324  insert(i[m], u);
325  set(u);
326  }
327  }
328 
329  template<class I>
332  init(r, i);
333  }
334  template<class I, class J>
337  init(r, i, j);
338  }
339  template<class I>
342  init(r, i, n);
343  }
344 
345  template<class I>
346  forceinline void
348  RangeList* u = get();
349  insert(i, u);
350  set(u);
351  }
352 
355  f = NULL;
356  return static_cast<NaryUnion&>(RangeListIter::operator =(m));
357  }
358 
359 }}}
360 
361 // STATISTICS: iter-any
362 
NodeType t
Type of node.
Definition: bool-expr.cpp:234
RangeList * range(int min, int max, RangeList *&f)
Create new range possibly from freelist f and init.
const FloatNum max
Largest allowed float value.
Definition: float.hh:831
int min(void) const
Return smallest value of range.
void operator|=(I &i)
Add iterator i.
void init(Region &r, I &i)
Initialize with single iterator i.
Base for range iterators with explicit min and max.
RangeListIter & operator=(const RangeListIter &i)
Assignment operator.
Handle to region.
Definition: region.hpp:61
NaryUnion(void)
Default constructor.
void init(I &i, J &j)
Initialize with iterator i and j.
const FloatNum min
Smallest allowed float value.
Definition: float.hh:833
Gecode::IntArgs i(4, 1, 2, 3, 4)
int n
Number of negative literals for node type.
Definition: bool-expr.cpp:238
NNF * r
Right subtree.
Definition: bool-expr.cpp:246
NaryUnion & operator=(const NaryUnion &m)
Assignment operator (both iterators must be allocated from the same region)
Range iterator for union of iterators.
RangeList * copy(I &i)
Copy the iterator i to a range list.
int min
Minimum and maximum of a range.
Definition: ranges-list.hpp:51
Range iterator for computing union (binary)
union Gecode::@518::NNF::@57 u
Union depending on nodetype t.
void set(RangeList *l)
Set range lists.
void init(Region &r)
Initialize.
#define forceinline
Definition: config.hpp:132
void operator++(void)
Move iterator to next range (if possible)
RangeList * two(I &i, J &j)
Return range list for union of two iterators.
int max(void) const
Return largest value of range.
void insert(I &i, RangeList *&u)
Insert ranges from i into u.
Gecode toplevel namespace
Union(void)
Default constructor.
RangeList * h
Head of range list.
Definition: ranges-list.hpp:66
Iterator over range lists.
Definition: ranges-list.hpp:45
RangeList * c
Current list element.
Definition: ranges-list.hpp:68
RangeList * f
Freelist used for allocation.