Generated on Sat Feb 7 2015 02:01:26 for Gecode by doxygen 1.8.9.1
ranges-inter.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: 2012-09-07 17:42:21 +0200 (Fri, 07 Sep 2012) $ by $Author: schulte $
11  * $Revision: 13069 $
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 Inter : public MinMax {
49  protected:
51  I i;
53  J j;
54  public:
56 
57  Inter(void);
60  Inter(I& i, J& j);
62  void init(I& i, J& j);
64 
66 
67  void operator ++(void);
70  };
71 
72 
78  class NaryInter : public RangeListIter {
79  protected:
82  public:
84 
85  NaryInter(void);
88  template<class I>
89  NaryInter(Region& r, I& i);
91  template<class I, class J>
92  NaryInter(Region& r, I& i, J& j);
94  template<class I>
95  NaryInter(Region& r, I* i, int n);
97  template<class I>
98  void init(Region& r, I& i);
100  template<class I, class J>
101  void init(Region& r, I& i, J& j);
103  template<class I>
104  void init(Region& r, I* i, int n);
106  template<class I>
107  void operator &=(I& i);
109  NaryInter& operator =(const NaryInter& m);
111  };
112 
113 
114 
115  /*
116  * Binary intersection
117  *
118  */
119 
120  template<class I, class J>
121  inline void
123  if (!i() || !j()) goto done;
124  do {
125  while (i() && (i.max() < j.min())) ++i;
126  if (!i()) goto done;
127  while (j() && (j.max() < i.min())) ++j;
128  if (!j()) goto done;
129  } while (i.max() < j.min());
130  // Now the intervals overlap: consume the smaller interval
131  ma = std::min(i.max(),j.max());
132  mi = std::max(i.min(),j.min());
133  if (i.max() < j.max()) ++i; else ++j;
134  return;
135  done:
136  finish();
137  }
138 
139  template<class I, class J>
142 
143  template<class I, class J>
145  Inter<I,J>::Inter(I& i0, J& j0)
146  : i(i0), j(j0) {
147  operator ++();
148  }
149 
150  template<class I, class J>
151  forceinline void
152  Inter<I,J>::init(I& i0, J& j0) {
153  i = i0; j = j0;
154  operator ++();
155  }
156 
157 
158  /*
159  * Nary intersection
160  *
161  */
162 
165 
166  template<class I>
167  forceinline void
170  f = NULL;
171  set(copy(i));
172  }
173 
174  template<class I, class J>
175  forceinline void
176  NaryInter::init(Region& r, I& i, J& j) {
178  f = NULL;
179  RangeList* h;
180  RangeList** c = &h;
181  while (i() && j()) {
182  do {
183  while (i() && (i.max() < j.min())) ++i;
184  if (!i()) goto done;
185  while (j() && (j.max() < i.min())) ++j;
186  if (!j()) goto done;
187  } while (i.max() < j.min());
188  // Now the intervals overlap: consume the smaller interval
189  RangeList* t = range(std::max(i.min(),j.min()),
190  std::min(i.max(),j.max()));
191  *c = t; c = &t->next;
192  if (i.max() < j.max()) ++i; else ++j;
193  }
194  done:
195  *c = NULL;
196  set(h);
197  }
198 
199  template<class I>
200  forceinline void
201  NaryInter::init(Region& r, I* i, int n) {
203  f = NULL;
204  if ((n > 0) && i[0]()) {
205  RangeList* h;
206  RangeList** c = &h;
207 
208  int min = i[0].min();
209  while (i[0]()) {
210  // Initialize with last interval
211  int max = i[0].max();
212  // Intersect with all other intervals
213  restart:
214  for (int j=n; j--;) {
215  // Skip intervals that are too small
216  while (i[j]() && (i[j].max() < min))
217  ++i[j];
218  if (!i[j]())
219  goto done;
220  if (i[j].min() > max) {
221  min=i[j].min();
222  max=i[j].max();
223  goto restart;
224  }
225  // Now the intervals overlap
226  if (min < i[j].min())
227  min = i[j].min();
228  if (max > i[j].max())
229  max = i[j].max();
230  }
231  RangeList* t = range(min,max);
232  *c = t; c = &t->next;
233  // The next interval must be at least two elements away
234  min = max + 2;
235  }
236  done:
237  *c = NULL;
238  set(h);
239  }
240  }
241 
242  template<class I>
245  init(r, i);
246  }
247  template<class I, class J>
250  init(r, i, j);
251  }
252  template<class I>
255  init(r, i, n);
256  }
257 
258  template<class I>
259  forceinline void
261  RangeList* j = get();
262  // The new rangelist
263  RangeList* h;
264  RangeList** c = &h;
265  while (i() && (j != NULL)) {
266  do {
267  while (i() && (i.max() < j->min))
268  ++i;
269  if (!i()) goto done;
270  while ((j != NULL) && (j->max < i.min())) {
271  RangeList* t = j->next;
272  j->next = f; f = j;
273  j = t;
274  }
275  if (j == NULL) goto done;
276  } while (i.max() < j->min);
277  // Now the intervals overlap: consume the smaller interval
278  RangeList* t = range(std::max(i.min(),j->min),
279  std::min(i.max(),j->max),f);
280  *c = t; c = &t->next;
281  if (i.max() < j->max) {
282  ++i;
283  } else {
284  RangeList* t = j->next;
285  j->next = f; f = j;
286  j = t;
287  }
288  }
289  done:
290  // Put remaining elements into freelist
291  while (j != NULL) {
292  RangeList* t = j->next;
293  j->next = f; f = j;
294  j = t;
295  }
296  *c = NULL;
297  set(h);
298  }
299 
302  f = NULL;
303  return static_cast<NaryInter&>(RangeListIter::operator =(m));
304  }
305 
306 }}}
307 
308 // STATISTICS: iter-any
309 
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.
Base for range iterators with explicit min and max.
RangeListIter & operator=(const RangeListIter &i)
Assignment operator.
Handle to region.
Definition: region.hpp:61
Inter(void)
Default constructor.
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
Range iterator for computing intersection (binary)
NNF * r
Right subtree.
Definition: bool-expr.cpp:246
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
void init(Region &r, I &i)
Initialize with single iterator i.
NaryInter & operator=(const NaryInter &m)
Assignment operator (both iterators must be allocated from the same region)
NaryInter(void)
Default constructor.
Range iterator for intersection of iterators.
void set(RangeList *l)
Set range lists.
void init(Region &r)
Initialize.
#define forceinline
Definition: config.hpp:132
void init(I &i, J &j)
Initialize with iterator i and j.
int max(void) const
Return largest value of range.
Gecode toplevel namespace
void operator++(void)
Move iterator to next range (if possible)
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
void operator&=(I &i)
Add iterator i.