LSSTApplications  19.0.0+10,19.0.0+80,19.0.0-1-g20d9b18+31,19.0.0-1-g49a97f9+4,19.0.0-1-g8c57eb9+31,19.0.0-1-g9a028c0+13,19.0.0-1-ga72da6b+3,19.0.0-1-gb77924a+15,19.0.0-1-gbfe0924+66,19.0.0-1-gc3516c3,19.0.0-1-gefe1d0d+49,19.0.0-1-gf8cb8b4+3,19.0.0-14-g7511ce4+6,19.0.0-16-g3dc1a33c+6,19.0.0-17-g59f0e8a+4,19.0.0-17-g9c22e3c+9,19.0.0-18-g35bb99870+2,19.0.0-19-g2772d4a+9,19.0.0-2-g260436e+53,19.0.0-2-g31cdcee,19.0.0-2-g9675b69+3,19.0.0-2-gaa2795f,19.0.0-2-gbcc4de1,19.0.0-2-gd6f004e+6,19.0.0-2-gde8e5e3+5,19.0.0-2-gff6972b+15,19.0.0-21-ge306cd8,19.0.0-21-gf122e69+2,19.0.0-3-g2d43a51+2,19.0.0-3-gf3b1435+6,19.0.0-4-g56feb96,19.0.0-4-gac56cce+17,19.0.0-49-gce872c1+1,19.0.0-5-g66946eb+6,19.0.0-5-gd8897ba+6,19.0.0-51-gfc4a647e,19.0.0-7-g686a884+5,19.0.0-7-g886f805+5,19.0.0-8-g305ff64,w.2020.17
LSSTDataManagementBasePackage
RangeSet.cc
Go to the documentation of this file.
1 /*
2  * LSST Data Management System
3  * Copyright 2016 AURA/LSST.
4  *
5  * This product includes software developed by the
6  * LSST Project (http://www.lsst.org/).
7  *
8  * This program is free software: you can redistribute it and/or modify
9  * it under the terms of the GNU General Public License as published by
10  * the Free Software Foundation, either version 3 of the License, or
11  * (at your option) any later version.
12  *
13  * This program is distributed in the hope that it will be useful,
14  * but WITHOUT ANY WARRANTY; without even the implied warranty of
15  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16  * GNU General Public License for more details.
17  *
18  * You should have received a copy of the LSST License Statement and
19  * the GNU General Public License along with this program. If not,
20  * see <https://www.lsstcorp.org/LegalNotices/>.
21  */
22 
25 
26 #include "lsst/sphgeom/RangeSet.h"
27 
28 #include <algorithm>
29 #include <ostream>
30 
31 
32 namespace lsst {
33 namespace sphgeom {
34 
35 namespace {
36 
37 // `roundUpToEven` returns the smallest multiple of 2
38 // greater than or equal to i.
39 inline ptrdiff_t roundUpToEven(ptrdiff_t i) { return i + (i & 1); }
40 
41 
42 // `RangeIter` is a stride-2 iterator over uint64_t values
43 // in an underlying array.
44 struct RangeIter {
45 
46  // For std::iterator_traits
47  using difference_type = ptrdiff_t;
48  using value_type = uint64_t;
49  using pointer = uint64_t *;
50  using reference = uint64_t &;
51  using iterator_category = std::random_access_iterator_tag;
52 
53  RangeIter() = default;
54  explicit RangeIter(uint64_t * p) : ptr{p} {}
55 
56  friend void swap(RangeIter & a, RangeIter & b) { std::swap(a.ptr, b.ptr); }
57 
58  // Arithmetic
59  RangeIter & operator++() { ptr += 2; return *this; }
60  RangeIter & operator--() { ptr -= 2; return *this; }
61 
62  RangeIter operator++(int) { RangeIter i(*this); ptr += 2; return i; }
63  RangeIter operator--(int) { RangeIter i(*this); ptr -= 2; return i; }
64 
65  RangeIter operator+(ptrdiff_t n) const { return RangeIter(ptr + 2 * n); }
66  RangeIter operator-(ptrdiff_t n) const { return RangeIter(ptr + 2 * n); }
67 
68  RangeIter & operator+=(ptrdiff_t n) { ptr += 2 * n; return *this; }
69  RangeIter & operator-=(ptrdiff_t n) { ptr -= 2 * n; return *this; }
70 
71  friend RangeIter operator+(ptrdiff_t n, RangeIter const & i) { return i + n; }
72 
73  ptrdiff_t operator-(RangeIter const & i) const { return (ptr - i.ptr) / 2; }
74 
75  // Comparison
76  bool operator==(RangeIter const & i) const { return ptr == i.ptr; }
77  bool operator!=(RangeIter const & i) const { return ptr != i.ptr; }
78  bool operator<(RangeIter const & i) const { return ptr < i.ptr; }
79  bool operator>(RangeIter const & i) const { return ptr > i.ptr; }
80  bool operator<=(RangeIter const & i) const { return ptr <= i.ptr; }
81  bool operator>=(RangeIter const & i) const { return ptr >= i.ptr; }
82 
83  // Dereferencing
84  uint64_t & operator*() const { return *ptr; }
85  uint64_t * operator->() const { return ptr; }
86  uint64_t & operator[](ptrdiff_t n) const { return ptr[2 * n]; }
87 
88  uint64_t * ptr = nullptr;
89 };
90 
91 } // unnamed namespace
92 
93 
95  RangeSet(list.begin(), list.end())
96 {}
97 
99  for (auto t: list) {
100  insert(std::get<0>(t), std::get<1>(t));
101  }
102 }
103 
104 void RangeSet::insert(uint64_t first, uint64_t last) {
105  if (first == last) {
106  fill();
107  } else {
108  // Ensure that there is enough space for 2 new values in _ranges.
109  // Afterwards, none of the possible modifications of _ranges will throw,
110  // so the strong exception safety guarantee is provided.
111  _ranges.reserve(_ranges.size() + 2);
112  if (first <= last - 1) {
113  _insert(first, last);
114  } else {
115  _insert(0, last);
116  _insert(first, 0);
117  }
118  }
119 }
120 
121 void RangeSet::erase(uint64_t first, uint64_t last) {
122  // To erase [first, last), insert it into the complement of this set,
123  // then complement the result. The complements are performed in the
124  // constructor and destructor of a local object, so that the second
125  // complement is executed even if insert throws.
126  struct Complementor {
127  RangeSet & set;
128  Complementor(RangeSet & s) : set(s) { set.complement(); }
129  ~Complementor() { set.complement(); }
130  };
131  Complementor c(*this);
132  insert(first, last);
133 }
134 
137  if (this == &s) {
138  result = s;
139  } else {
140  result._intersect(_begin(), _end(), s._begin(), s._end());
141  }
142  return result;
143 }
144 
145 RangeSet RangeSet::join(RangeSet const & s) const {
147  if (this == &s) {
148  result = s;
149  } else {
150  // A ∪ B = ¬(¬A ∩ ¬B)
151  result._intersect(_beginc(), _endc(), s._beginc(), s._endc());
152  result.complement();
153  }
154  return result;
155 }
156 
159  if (this != &s) {
160  // A ∖ B = A ∩ ¬B
161  result._intersect(_begin(), _end(), s._beginc(), s._endc());
162  }
163  return result;
164 }
165 
168  if (this != &s) {
169  if (empty()) {
170  result = s;
171  } else if (s.empty()) {
172  result = *this;
173  } else {
174  // Sweep through the beginning and end points of the ranges from
175  // sets A and B in ascending order.
176  //
177  // Passing through the beginning of a range toggles the
178  // corresponding state (astate or bstate) from 0 to 1, and passing
179  // through the end toggles it from 1 to 0. The XOR of astate and
180  // bstate determines whether or not the current position of the
181  // sweep is inside the symmetric set difference of A and B.
182  //
183  // Merging the sorted lists of ranges from each set is complicated
184  // by trailing zero bookends. These compare less than or equal to
185  // all other values, even though logically they are greater than
186  // them all.
187  //
188  // To handle this, leading zero bookends are dealt with outside of
189  // the main loop. Then, 1 is subtracted from all other values prior
190  // to comparison, yielding the proper ordering (since subtracting
191  // 1 from a trailing zero bookend results in 2^64 - 1).
192  uint64_t const * a = _begin();
193  uint64_t const * aend = _end();
194  uint64_t const * b = s._begin();
195  uint64_t const * bend = s._end();
196  int astate = (*a == 0);
197  int bstate = (*b == 0);
198  a += astate;
199  b += bstate;
200  // state is 0 if the next value to output is the beginning
201  // of a range, and 1 otherwise.
202  int state = astate ^ bstate;
203  // Start with a vector containing just the leading bookend.
204  result._ranges = {0};
205  // If 0 is contained in exactly one of the two sets, it is
206  // in their symmetric difference.
207  result._offset = (state == 0);
208  // Merge lists until one or both are exhausted.
209  while (a != aend && b != bend) {
210  uint64_t av = *a - 1;
211  uint64_t bv = *b - 1;
212  // The pointer(s) yielding the minimal value will be
213  // incremented.
214  bool ainc = (av <= bv);
215  bool binc = (bv <= av);
216  uint64_t minval = ainc ? av : bv;
217  astate ^= ainc;
218  bstate ^= binc;
219  // Output the minimum value if the output state changes.
220  if (state != (astate ^ bstate)) {
221  result._ranges.push_back(minval + 1);
222  state ^= 1;
223  }
224  a += ainc;
225  b += binc;
226  }
227  // The sweep has exhausted at least one list. Each remaining
228  // beginning and end point in the other list will toggle the
229  // output state, so they can simply be appended to the result.
230  result._ranges.insert(result._ranges.end(), a, aend);
231  result._ranges.insert(result._ranges.end(), b, bend);
232  // Append a trailing bookend if necessary.
233  if ((aend[-1] == 0) == (bend[-1] == 0)) {
234  result._ranges.push_back(0);
235  }
236  }
237  }
238  return result;
239 }
240 
241 bool RangeSet::intersects(uint64_t first, uint64_t last) const {
242  if (empty()) {
243  return false;
244  }
245  if (first == last) {
246  return true;
247  }
248  if (first <= last - 1) {
249  uint64_t r[2] = {first, last};
250  return _intersectsOne(r, _begin(), _end());
251  }
252  uint64_t r[4] = {0, last, first, 0};
253  return _intersectsOne(r, _begin(), _end()) ||
254  _intersectsOne(r + 2, _begin(), _end());
255 }
256 
257 bool RangeSet::intersects(RangeSet const & s) const {
258  if (empty() || s.empty()) {
259  return false;
260  }
261  return _intersects(_begin(), _end(), s._begin(), s._end());
262 }
263 
264 bool RangeSet::contains(uint64_t first, uint64_t last) const {
265  if (full()) {
266  return true;
267  }
268  if (first == last) {
269  return false;
270  }
271  if (first <= last - 1) {
272  uint64_t r[2] = {first, last};
273  return !_intersectsOne(r, _beginc(), _endc());
274  }
275  uint64_t r[4] = {0, last, first, 0};
276  return !_intersectsOne(r, _beginc(), _endc()) &&
277  !_intersectsOne(r + 2, _beginc(), _endc());
278 }
279 
280 bool RangeSet::contains(RangeSet const & s) const {
281  if (s.empty() || full()) {
282  return true;
283  }
284  return !_intersects(_beginc(), _endc(), s._begin(), s._end());
285 }
286 
287 bool RangeSet::isWithin(uint64_t first, uint64_t last) const {
288  if (empty() || first == last) {
289  return true;
290  }
291  if (last <= first - 1) {
292  uint64_t r[2] = {last, first};
293  return !_intersectsOne(r, _begin(), _end());
294  }
295  uint64_t r[4] = {0, first, last, 0};
296  return !_intersectsOne(r, _begin(), _end()) &&
297  !_intersectsOne(r + 2, _begin(), _end());
298 }
299 
300 uint64_t RangeSet::cardinality() const {
301  uint64_t sz = 0;
302  for (auto r = _begin(), e = _end(); r != e; r += 2) {
303  sz += r[1] - r[0];
304  }
305  return sz;
306 }
307 
309  if (empty() || n == 0) {
310  return *this;
311  } else if (n >= 64) {
312  fill();
313  return *this;
314  }
315  // Compute m, the integer with n LSBs set to 1. Then, (x & ~m) is x
316  // rounded down to the nearest multiple of 2^n, and (x + m) & ~m is
317  // x rounded up to the nearest multiple of 2^n.
318  uint64_t const m = (static_cast<uint64_t>(1) << n) - 1;
319  uint64_t * r = const_cast<uint64_t *>(_begin());
320  uint64_t * rend = const_cast<uint64_t *>(_end());
321  uint64_t * out = r;
322  // Expand the first range.
323  uint64_t first = r[0] & ~m;
324  uint64_t last = (r[1] + m) & ~m;
325  if (r[0] != 0 && first == 0) {
326  // The expanded first range now contains the leading bookend.
327  _offset = false;
328  --out;
329  }
330  out[0] = first;
331  out[1] = last;
332  // Expand the remaining ranges.
333  for (r += 2; last != 0 && r != rend; r += 2) {
334  uint64_t u = r[0] & ~m;
335  uint64_t v = (r[1] + m) & ~m;
336  if (u > last) {
337  out += 2;
338  out[0] = u;
339  }
340  out[1] = v;
341  last = v;
342  }
343  out += 2;
344  if (last != 0) {
345  // Append a trailing bookend if necessary.
346  *out = 0;
347  ++out;
348  }
349  // Erase everything after the location of the new trailing bookend.
350  _ranges.erase(_ranges.begin() + (out - _ranges.data()), _ranges.end());
351  return *this;
352 }
353 
354 RangeSet & RangeSet::scale(uint64_t i) {
355  if (empty() || i == 1) {
356  return *this;
357  } else if (i == 0) {
358  clear();
359  return *this;
360  }
361  uint64_t overflowThreshold = static_cast<uint64_t>(-1) / i;
362  auto r = _ranges.begin();
363  auto rend = _ranges.end();
364  for (; r < rend; ++r) {
365  uint64_t value = *r;
366  if (value > overflowThreshold) {
367  *r = 0;
368  ++r;
369  break;
370  }
371  *r = value * i;
372  }
373  _ranges.erase(r, rend);
374  return *this;
375 }
376 
377 bool RangeSet::isValid() const {
378  // Bookends are mandatory.
379  if (_ranges.size() < 2) {
380  return false;
381  }
382  if (_ranges.front() != 0 || _ranges.back() != 0) {
383  return false;
384  }
385  // Values except the last one must be monotonically increasing.
386  for (auto i = _ranges.begin() + 1, e = _ranges.end() - 1; i != e; ++i) {
387  if (i[0] <= i[-1]) {
388  return false;
389  }
390  }
391  return true;
392 }
393 
394 void RangeSet::_insert(uint64_t first, uint64_t last) {
395  // First, check if this set is empty, or if [first, last) extends
396  // or comes after the last range in this set.
397  //
398  // It is assumed that first <= last - 1; that is, first and last
399  // do not correspond to a full range, or one that wraps.
400  uint64_t * r = const_cast<uint64_t *>(_begin());
401  uint64_t * rend = const_cast<uint64_t *>(_end());
402  if (r == rend) {
403  // This set is empty.
404  uint64_t array[4] = {0, first, last, 0};
405  _ranges.assign(array + (first == 0), array + (4 - (last == 0)));
406  _offset = (first != 0);
407  } else if (first >= rend[-2]) {
408  if (rend[-1] != 0) {
409  if (first <= rend[-1]) {
410  // [first, last) extends the last range in this set.
411  rend[-1] = std::max(last - 1, rend[-1] - 1) + 1;
412  if (last == 0) {
413  _ranges.pop_back();
414  }
415  } else {
416  // [first, last) follows the last range in this set.
417  rend[0] = first;
418  _ranges.push_back(last);
419  if (last != 0) {
420  _ranges.push_back(0);
421  }
422  }
423  }
424  } else {
425  // Find a, the first range with end point a[1] >= first, and b,
426  // the first range with beginning point b[0] > last.
427  uint64_t * a;
428  uint64_t * b;
429  if (first == 0) {
430  a = r;
431  } else {
432  // Subtract one from values before comparisons so that the
433  // trailing zero bookend is ordered properly.
434  a = std::lower_bound(RangeIter(r + 1), RangeIter(rend + 1), first,
435  [](uint64_t u, uint64_t v) {
436  return u - 1 < v - 1;
437  }).ptr - 1;
438  }
439  if (last == 0) {
440  b = rend;
441  } else {
442  b = std::upper_bound(RangeIter(a), RangeIter(rend), last).ptr;
443  }
444  // Perform the insert. Inserts involving a leading or trailing bookend
445  // are special cased.
446  if (first == 0) {
447  _offset = false;
448  if (b == r) {
449  _ranges.insert(_ranges.begin() + (r - _ranges.data()), last);
450  } else {
451  --b;
452  *b = std::max(last - 1, *b - 1) + 1;
453  _ranges.erase(_ranges.begin() + 1,
454  _ranges.begin() + (b - _ranges.data()));
455  }
456  } else if (last == 0) {
457  *a = std::min(first, *a);
458  ++a;
459  _ranges.erase(_ranges.begin() + (a - _ranges.data()),
460  _ranges.end() - 1);
461  } else {
462  if (a == b) {
463  _ranges.insert(_ranges.begin() + (a - _ranges.data()),
464  {first, last});
465  } else {
466  --b;
467  *b = std::max(last - 1, *b - 1) + 1;
468  *a = std::min(first, *a);
469  ++a;
470  _ranges.erase(_ranges.begin() + (a - _ranges.data()),
471  _ranges.begin() + (b - _ranges.data()));
472  }
473  }
474  }
475 }
476 
479 void RangeSet::_intersectOne(std::vector<uint64_t> & v,
480  uint64_t const * a,
481  uint64_t const * b,
482  uint64_t const * bend)
483 {
484  // The range B = [b[0], bend[-1]) contains all the ranges
485  // [b[0], b[1]), ... , [bend[-2], bend[-1]). If [a[0], a[1])
486  // does not intersect B, it does not intersect any of them.
487  //
488  // Note that one is subtracted from range end-points prior to
489  // comparison - otherwise, trailing zero bookends would not be
490  // ordered properly with respect to other values.
491  if (a[0] > bend[-1] - 1 || a[1] - 1 < b[0]) {
492  return;
493  }
494  if (b + 2 == bend) {
495  // Output the intersection of the ranges pointed to by a and b.
496  uint64_t u = std::max(a[0], b[0]);
497  if (u != 0) {
498  v.push_back(u);
499  }
500  v.push_back(std::min(a[1] - 1, b[1] - 1) + 1);
501  } else if (a[0] <= b[0] && a[1] - 1 >= bend[-1] - 1) {
502  // [a[0], a[1]) contains [b[0], bend[-1]), so it contains
503  // [b[0], b[1]), [b[2], b[3]), ... , [bend[-2], bend[-1]).
504  v.insert(v.end(), b + (b[0] == 0), bend);
505  } else {
506  // Divide and conquer - split the list of ranges pointed
507  // to by b in half and recurse.
508  uint64_t const * bmid = b + roundUpToEven((bend - b) >> 1);
509  _intersectOne(v, a, b, bmid);
510  _intersectOne(v, a, bmid, bend);
511  }
512 }
513 
516 void RangeSet::_intersect(std::vector<uint64_t> & v,
517  uint64_t const * a,
518  uint64_t const * aend,
519  uint64_t const * b,
520  uint64_t const * bend)
521 {
522  // The range A = [a[0], aend[-1]) contains all the ranges
523  // [a[0], a[1]), ... , [aend[-2], aend[-1]), and similarly,
524  // B = [b[0], bend[-1]) contains all the ranges pointed to by b.
525  // A and B must intersect if any of the ranges pointed to by
526  // a and b do, so if A and B are disjoint there is nothing to do.
527  //
528  // Note that one is subtracted from range end-points prior to
529  // comparison - otherwise, trailing zero bookends would not be
530  // ordered properly with respect to other values.
531  if (a + 2 == aend) {
532  _intersectOne(v, a, b, bend);
533  } else if (b + 2 == bend) {
534  _intersectOne(v, b, a, aend);
535  } else if (a[0] <= bend[-1] - 1 && aend[-1] - 1 >= b[0]) {
536  // Divide and conquer - split the lists of ranges pointed to by a and b
537  // in half and recurse. This is a depth first dual-tree traversal of
538  // implicit balanced binary trees, where a sorted list of ranges forms
539  // the bottom level of a tree, and level N - 1 is obtained from level N
540  // by joining adjacent ranges.
541  //
542  // Note that the order of the recursive calls matters -
543  // output must be generated in sorted order.
544  uint64_t const * amid = a + roundUpToEven((aend - a) >> 1);
545  uint64_t const * bmid = b + roundUpToEven((bend - b) >> 1);
546  _intersect(v, a, amid, b, bmid);
547  _intersect(v, a, amid, bmid, bend);
548  _intersect(v, amid, aend, b, bmid);
549  _intersect(v, amid, aend, bmid, bend);
550  }
551 }
552 
553 void RangeSet::_intersect(uint64_t const * a,
554  uint64_t const * aend,
555  uint64_t const * b,
556  uint64_t const * bend)
557 {
558  if (a == aend || b == bend) {
559  clear();
560  } else {
561  // Start with a vector containing just the leading bookend.
562  _ranges = {0};
563  // If both a and b contain 0, their intersection contains 0,
564  // and _offset must be 0 (false).
565  _offset = ((*a != 0) || (*b != 0));
566  // Compute the intersection and append a trailing bookend if necessary.
567  _intersect(_ranges, a, aend, b, bend);
568  if ((aend[-1] != 0) || (bend[-1] != 0)) {
569  _ranges.push_back(0);
570  }
571  }
572 }
573 
576 bool RangeSet::_intersectsOne(uint64_t const * a,
577  uint64_t const * b,
578  uint64_t const * bend)
579 {
580  // See the comments in _intersectOne for an explanation.
581  if (a[0] > bend[-1] - 1 || a[1] - 1 < b[0]) {
582  return false;
583  }
584  if (b + 2 == bend || a[0] <= b[0] || a[1] - 1 >= bend[-1] - 1) {
585  return true;
586  }
587  uint64_t const * bmid = b + roundUpToEven((bend - b) >> 1);
588  return _intersectsOne(a, b, bmid) || _intersectsOne(a, bmid, bend);
589 }
590 
593 bool RangeSet::_intersects(uint64_t const * a,
594  uint64_t const * aend,
595  uint64_t const * b,
596  uint64_t const * bend)
597 {
598  // See the comments in _intersect for an explanation.
599  if (a + 2 == aend) {
600  return _intersectsOne(a, b, bend);
601  }
602  if (b + 2 == bend) {
603  return _intersectsOne(b, a, aend);
604  }
605  if (a[0] > bend[-1] - 1 || aend[-1] - 1 < b[0]) {
606  return false;
607  }
608  uint64_t const * amid = a + roundUpToEven((aend - a) >> 1);
609  uint64_t const * bmid = b + roundUpToEven((bend - b) >> 1);
610  return _intersects(a, amid, b, bmid) ||
611  _intersects(a, amid, bmid, bend) ||
612  _intersects(amid, aend, b, bmid) ||
613  _intersects(amid, aend, bmid, bend);
614 }
615 
617  os << "{\"RangeSet\": [";
618  bool first = true;
619  for (auto const & t: s) {
620  if (!first) {
621  os << ", ";
622  }
623  first = false;
624  os << '[' << std::get<0>(t) << ", " << std::get<1>(t) << ']';
625  }
626  os << "]}";
627  return os;
628 }
629 
630 }} // namespace lsst::sphgeom
RangeSet symmetricDifference(RangeSet const &s) const
symmetricDifference returns the symmetric difference of this set and s.
Definition: RangeSet.cc:166
uint64_t * ptr
Definition: RangeSet.cc:88
void clear()
clear removes all integers from this set.
Definition: RangeSet.h:501
Image< LhsPixelT > & operator+=(Image< LhsPixelT > &lhs, Image< RhsPixelT > const &rhs)
Add lhs to Image rhs (i.e. pixel-by-pixel addition) where types are different.
Definition: Image.cc:671
bool contains(uint64_t u) const
Definition: RangeSet.h:435
T swap(T... args)
T operator!=(T... args)
RangeSet difference(RangeSet const &s) const
difference returns the difference between this set and s.
Definition: RangeSet.cc:157
bool empty() const
empty checks whether there are any integers in this set.
Definition: RangeSet.h:507
table::Key< int > b
Angle operator*(double a, Angle const &b)
Definition: Angle.h:98
T upper_bound(T... args)
std::shared_ptr< Image< PixelT > > operator+(Image< PixelT > const &img, ImageSlice< PixelT > const &slc)
Overload operator+()
Definition: ImageSlice.cc:69
RangeSet()=default
The default constructor creates an empty set.
table::Key< int > a
std::ostream & operator<<(std::ostream &, Angle const &)
Definition: Angle.cc:34
T end(T... args)
T lower_bound(T... args)
RangeSet & simplify(uint32_t n)
simplify simplifies this range set by "coarsening" its ranges.
Definition: RangeSet.cc:308
RangeSet & complement()
complement replaces this set S with U ∖ S, where U is the universe of range sets, [0, 2^64).
Definition: RangeSet.h:328
T min(T... args)
void erase(uint64_t u)
Definition: RangeSet.h:306
T push_back(T... args)
RangeSet & scale(uint64_t i)
scale multiplies the endpoints of each range in this set by the given integer.
Definition: RangeSet.cc:354
A base class for image defects.
This file provides a type for representing integer sets.
T max(T... args)
std::shared_ptr< Image< PixelT > > operator-(Image< PixelT > const &img, ImageSlice< PixelT > const &slc)
Overload operator-()
Definition: ImageSlice.cc:89
T insert(T... args)
T size(T... args)
bool intersects(uint64_t u) const
Definition: RangeSet.h:425
bool isValid() const
isValid checks that this RangeSet is in a valid state.
Definition: RangeSet.cc:377
Image< LhsPixelT > & operator-=(Image< LhsPixelT > &lhs, Image< RhsPixelT > const &rhs)
Subtract lhs from Image rhs (i.e. pixel-by-pixel subtraction) where types are different.
Definition: Image.cc:677
A RangeSet is a set of unsigned 64 bit integers.
Definition: RangeSet.h:99
int m
Definition: SpanSet.cc:49
void swap(RangeSet &a, RangeSet &b)
Definition: RangeSet.h:608
void fill()
fill adds all the unsigned 64 bit integers to this set.
Definition: RangeSet.h:504
void insert(uint64_t u)
Definition: RangeSet.h:285
std::ostream * os
Definition: Schema.cc:746
bool isWithin(uint64_t u) const
Definition: RangeSet.h:445
bool full() const
full checks whether all integers in the universe of range sets, [0, 2^64), are in this set...
Definition: RangeSet.h:511
STL class.
daf::base::PropertyList * list
Definition: fits.cc:913
py::object result
Definition: _schema.cc:429
int end
T reserve(T... args)
uint64_t cardinality() const
cardinality returns the number of integers in this set.
Definition: RangeSet.cc:300
RangeSet join(RangeSet const &s) const
join returns the union of this set and s.
Definition: RangeSet.cc:145
RangeSet intersection(RangeSet const &s) const
intersection returns the intersection of this set and s.
Definition: RangeSet.cc:135