Generated on Thu Mar 13 2014 04:39:34 for Gecode by doxygen 1.8.1.2
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: 2011-08-09 02:04:53 +1000 (Tue, 09 Aug 2011) $ by $Author: schulte $
11  * $Revision: 12253 $
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 
58  Union(void);
60  Union(I& i, J& j);
62  void init(I& i, J& j);
64 
66 
67 
68  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 
92  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 
281  template<class I>
282  forceinline void
285  f = NULL;
286  set(copy(i));
287  }
288 
289  template<class I, class J>
290  forceinline void
291  NaryUnion::init(Region& r, I& i, J& j) {
293  f = NULL;
294  set(two(i,j));
295  }
296 
297  template<class I>
298  forceinline void
299  NaryUnion::init(Region& r, I* i, int n) {
300  f = NULL;
302 
303  int m = 0;
304  while ((m < n) && !i[m]())
305  m++;
306 
307  // Union is empty
308  if (m >= n)
309  return;
310 
311  n--;
312  while (!i[n]())
313  n--;
314 
315  if (m == n) {
316  // Union is just a single iterator
317  set(copy(i[m]));
318  } else {
319  // At least two iterators
320  RangeList* u = two(i[m++],i[n--]);
321  // Insert the remaining iterators
322  for ( ; m<=n; m++)
323  insert(i[m], u);
324  set(u);
325  }
326  }
327 
328  template<class I>
331  init(r, i);
332  }
333  template<class I, class J>
336  init(r, i, j);
337  }
338  template<class I>
341  init(r, i, n);
342  }
343 
344  template<class I>
345  forceinline void
347  RangeList* u = get();
348  insert(i, u);
349  set(u);
350  }
351 
354  f = NULL;
355  return static_cast<NaryUnion&>(RangeListIter::operator =(m));
356  }
357 
358 }}}
359 
360 // STATISTICS: iter-any
361