LSST Applications  21.0.0-147-g0e635eb1+1acddb5be5,22.0.0+052faf71bd,22.0.0+1ea9a8b2b2,22.0.0+6312710a6c,22.0.0+729191ecac,22.0.0+7589c3a021,22.0.0+9f079a9461,22.0.1-1-g7d6de66+b8044ec9de,22.0.1-1-g87000a6+536b1ee016,22.0.1-1-g8e32f31+6312710a6c,22.0.1-10-gd060f87+016f7cdc03,22.0.1-12-g9c3108e+df145f6f68,22.0.1-16-g314fa6d+c825727ab8,22.0.1-19-g93a5c75+d23f2fb6d8,22.0.1-19-gb93eaa13+aab3ef7709,22.0.1-2-g8ef0a89+b8044ec9de,22.0.1-2-g92698f7+9f079a9461,22.0.1-2-ga9b0f51+052faf71bd,22.0.1-2-gac51dbf+052faf71bd,22.0.1-2-gb66926d+6312710a6c,22.0.1-2-gcb770ba+09e3807989,22.0.1-20-g32debb5+b8044ec9de,22.0.1-23-gc2439a9a+fb0756638e,22.0.1-3-g496fd5d+09117f784f,22.0.1-3-g59f966b+1e6ba2c031,22.0.1-3-g849a1b8+f8b568069f,22.0.1-3-gaaec9c0+c5c846a8b1,22.0.1-32-g5ddfab5d3+60ce4897b0,22.0.1-4-g037fbe1+64e601228d,22.0.1-4-g8623105+b8044ec9de,22.0.1-5-g096abc9+d18c45d440,22.0.1-5-g15c806e+57f5c03693,22.0.1-7-gba73697+57f5c03693,master-g6e05de7fdc+c1283a92b8,master-g72cdda8301+729191ecac,w.2021.39
LSST Data Management Base Package
RangeSet.h
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 
23 #ifndef LSST_SPHGEOM_RANGESET_H_
24 #define LSST_SPHGEOM_RANGESET_H_
25 
28 
29 #include <cstddef>
30 #include <cstdint>
31 #include <initializer_list>
32 #include <iosfwd>
33 #include <iterator>
34 #include <tuple>
35 #include <type_traits>
36 #include <vector>
37 
38 
39 namespace lsst {
40 namespace sphgeom {
41 
99 class RangeSet {
100 public:
101 
122  struct Iterator {
123  // For std::iterator_traits
124  using difference_type = ptrdiff_t;
126  using pointer = void;
129 
130  Iterator() = default;
131  explicit Iterator(uint64_t const * ptr) : p{ptr} {}
132 
133  friend void swap(Iterator & a, Iterator & b) {
134  std::swap(a.p, b.p);
135  }
136 
137  // Arithmetic
138  Iterator & operator++() { p += 2; return *this; }
139  Iterator & operator--() { p -= 2; return *this; }
140 
141  Iterator operator++(int) { Iterator i(*this); p += 2; return i; }
142  Iterator operator--(int) { Iterator i(*this); p -= 2; return i; }
143 
144  Iterator operator+(ptrdiff_t n) const { return Iterator(p + 2 * n); }
145  Iterator operator-(ptrdiff_t n) const { return Iterator(p + 2 * n); }
146 
147  Iterator & operator+=(ptrdiff_t n) { p += 2 * n; return *this; }
148  Iterator & operator-=(ptrdiff_t n) { p -= 2 * n; return *this; }
149 
150  friend Iterator operator+(ptrdiff_t n, Iterator const & i) {
151  return i + n;
152  }
153 
154  ptrdiff_t operator-(Iterator const & i) const { return (p - i.p) / 2; }
155 
156  // Comparison
157  bool operator==(Iterator const & i) const { return p == i.p; }
158  bool operator!=(Iterator const & i) const { return p != i.p; }
159  bool operator<(Iterator const & i) const { return p < i.p; }
160  bool operator>(Iterator const & i) const { return p > i.p; }
161  bool operator<=(Iterator const & i) const { return p <= i.p; }
162  bool operator>=(Iterator const & i) const { return p >= i.p; }
163 
165  return std::make_tuple(p[0], p[1]);
166  }
167 
169  return std::make_tuple(p[2 * n], p[2 * n + 1]);
170  }
171 
172  uint64_t const * p = nullptr;
173  };
174 
175  using difference_type = ptrdiff_t;
176  using size_type = size_t;
179 
180  RangeSet(RangeSet const &) = default;
181  RangeSet(RangeSet &&) = default;
182  RangeSet & operator=(RangeSet const &) = default;
183  RangeSet & operator=(RangeSet &&) = default;
184 
186  RangeSet() = default;
187 
191  explicit RangeSet(uint64_t u) {
192  insert(u);
193  }
194 
195  RangeSet(uint64_t first, uint64_t last) {
196  insert(first, last);
197  }
198 
199  template <
200  typename U,
201  typename = typename std::enable_if<
203  >::type
204  >
205  explicit RangeSet(std::tuple<U, U> const & range) {
206  insert(static_cast<uint64_t>(std::get<0>(range)),
207  static_cast<uint64_t>(std::get<1>(range)));
208  }
209 
211 
212  // Note: the standard library for GCC unfortunately declares explicit conversion
213  // constructors for tuples - the use of std::pair is required for code like:
214  //
215  // RangeSet s = {{0, 1}, {2, 3}};
216  //
217  // to compile.
220 
226  template <
227  typename InputIterator,
228  typename = typename std::enable_if<
232  >::value
233  >::type
234  >
235  RangeSet(InputIterator a, InputIterator b) {
236  for (; a != b; ++a) {
237  insert(*a);
238  }
239  }
240 
246  template <
247  typename Container,
248  typename = typename std::enable_if<
251  typename std::iterator_traits<decltype(
253  )>::iterator_category
254  >::value
255  &&
258  typename std::iterator_traits<decltype(
260  )>::iterator_category
261  >::value
262  >::type
263  >
264  explicit RangeSet(Container const & c) :
265  RangeSet(std::begin(c), std::end(c)) {}
266 
269  bool operator==(RangeSet const & rs) const {
270  return _offset == rs._offset && _ranges == rs._ranges;
271  }
272 
273  bool operator!=(RangeSet const & rs) const {
274  return _offset != rs._offset || _ranges != rs._ranges;
275  }
277 
285  void insert(uint64_t u) {
286  insert(u, u + 1);
287  }
288 
289  template <
290  typename U,
291  typename = typename std::enable_if<
293  >::type
294  >
295  void insert(std::tuple<U, U> const & range) {
296  insert(std::get<0>(range), std::get<1>(range));
297  }
298 
299  void insert(uint64_t first, uint64_t last);
301 
306  void erase(uint64_t u) {
307  erase(u, u + 1);
308  }
309 
310  template <
311  typename U,
312  typename = typename std::enable_if<
314  >::type
315  >
316  void erase(std::tuple<U, U> const & range) {
317  erase(std::get<0>(range), std::get<1>(range));
318  }
319 
320  void erase(uint64_t first, uint64_t last);
322 
325 
328  RangeSet & complement() { _offset = !_offset; return *this; }
329 
332  RangeSet s(*this);
333  s.complement();
334  return s;
335  }
336 
338  RangeSet intersection(RangeSet const & s) const;
339 
341  RangeSet join(RangeSet const & s) const;
342 
344  RangeSet difference(RangeSet const & s) const;
345 
348  RangeSet symmetricDifference(RangeSet const & s) const;
349 
351  RangeSet operator~() const {
352  RangeSet s(*this);
353  s.complement();
354  return s;
355  }
356 
358  RangeSet operator&(RangeSet const & s) const {
359  return intersection(s);
360  }
361 
363  RangeSet operator|(RangeSet const & s) const {
364  return join(s);
365  }
366 
368  RangeSet operator-(RangeSet const & s) const {
369  return difference(s);
370  }
371 
373  RangeSet operator^(RangeSet const & s) const {
374  return symmetricDifference(s);
375  }
376 
379  RangeSet & operator&=(RangeSet const & s) {
380  if (this != &s) {
381  RangeSet r = intersection(s);
382  swap(r);
383  }
384  return *this;
385  }
386 
389  RangeSet & operator|=(RangeSet const & s) {
390  if (this != &s) {
391  RangeSet r = join(s);
392  swap(r);
393  }
394  return *this;
395  }
396 
399  RangeSet & operator-=(RangeSet const & s) {
400  if (this != &s) {
401  RangeSet r = difference(s);
402  swap(r);
403  } else {
404  clear();
405  }
406  return *this;
407  }
408 
411  RangeSet & operator^=(RangeSet const & s) {
412  if (this != &s) {
414  swap(r);
415  } else {
416  clear();
417  }
418  return *this;
419  }
421 
425  bool intersects(uint64_t u) const { return intersects(u, u + 1); }
426 
427  bool intersects(uint64_t first, uint64_t last) const;
428 
429  bool intersects(RangeSet const & s) const;
431 
435  bool contains(uint64_t u) const { return contains(u, u + 1); }
436 
437  bool contains(uint64_t first, uint64_t last) const;
438 
439  bool contains(RangeSet const & s) const;
441 
445  bool isWithin(uint64_t u) const { return isWithin(u, u + 1); }
446 
447  bool isWithin(uint64_t first, uint64_t last) const;
448 
449  bool isWithin(RangeSet const & s) const { return s.contains(*this); }
451 
455  bool isDisjointFrom(uint64_t u) const { return !intersects(u); }
456 
457  bool isDisjointFrom(uint64_t first, uint64_t last) const {
458  return !intersects(first, last);
459  }
460 
461  bool isDisjointFrom(RangeSet const & s) const { return !intersects(s); }
463 
476  RangeSet & simplify(uint32_t n);
477 
479  RangeSet simplified(uint32_t n) const {
480  RangeSet rs(*this);
481  rs.simplify(n);
482  return rs;
483  }
484 
491  RangeSet & scale(uint64_t i);
492 
494  RangeSet scaled(uint64_t i) const {
495  RangeSet rs(*this);
496  rs.scale(i);
497  return rs;
498  }
499 
501  void clear() { _ranges = {0, 0}; _offset = true; }
502 
504  void fill() { _ranges = {0, 0}; _offset = false; }
505 
507  bool empty() const { return _begin() == _end(); }
508 
511  bool full() const { return _beginc() == _endc(); }
512 
516  Iterator begin() const { return Iterator(_begin()); }
517  Iterator cbegin() const { return begin(); }
519 
523  Iterator end() const { return Iterator(_end()); }
524  Iterator cend() const { return end(); }
526 
529  Iterator beginc() const { return Iterator(_beginc()); }
530 
533  Iterator endc() const { return Iterator(_endc()); }
534 
536  size_t max_size() const { return _ranges.max_size() / 2; }
537 
539  size_t size() const { return (_ranges.size() - _offset) / 2; }
540 
545  uint64_t cardinality() const;
546 
547  void swap(RangeSet & s) {
548  using std::swap;
549  swap(_ranges, s._ranges);
550  swap(_offset, s._offset);
551  }
552 
558  bool isValid() const;
559 
560 private:
561  std::vector<uint64_t> _ranges = {0, 0};
562 
563  // The offset of the first range in _ranges. It is 0 (false) if the
564  // first integer in the set is 0, and 1 (true) otherwise.
565  bool _offset = true;
566 
567  // `_begin` returns a pointer to the first range in this set.
568  uint64_t const * _begin() const { return _ranges.data() + _offset; }
569 
570  // `_end` returns a pointer to the range after the last one in this set.
571  uint64_t const * _end() const {
572  size_t s = _ranges.size();
573  return _ranges.data() + (s - ((s & 1) ^ _offset));
574  }
575 
576  // `_beginc` returns a pointer to the first range in
577  // the complement of this set.
578  uint64_t const * _beginc() const { return _ranges.data() + !_offset; }
579 
580  // `_endc` returns a pointer to the range after the last one in
581  // the complement of this set.
582  uint64_t const * _endc() const {
583  size_t s = _ranges.size();
584  return _ranges.data() + (s - ((s & 1) ^ !_offset));
585  }
586 
587  void _insert(uint64_t first, uint64_t last);
588 
589  static void _intersectOne(std::vector<uint64_t> &,
590  uint64_t const *,
591  uint64_t const *, uint64_t const *);
592 
593  static void _intersect(std::vector<uint64_t> &,
594  uint64_t const *, uint64_t const *,
595  uint64_t const *, uint64_t const *);
596 
597  void _intersect(uint64_t const *, uint64_t const *,
598  uint64_t const *, uint64_t const *);
599 
600  static bool _intersectsOne(uint64_t const *,
601  uint64_t const *, uint64_t const *);
602 
603  static bool _intersects(uint64_t const *, uint64_t const *,
604  uint64_t const *, uint64_t const *);
605 };
606 
607 
608 inline void swap(RangeSet & a, RangeSet & b) {
609  a.swap(b);
610 }
611 
612 std::ostream & operator<<(std::ostream &, RangeSet const &);
613 
614 }} // namespace lsst::sphgeom
615 
616 #endif // LSST_SPHGEOM_RANGESET_H_
table::Key< int > type
Definition: Detector.cc:163
uint64_t * ptr
Definition: RangeSet.cc:88
table::Key< int > b
table::Key< int > a
T begin(T... args)
A RangeSet is a set of unsigned 64 bit integers.
Definition: RangeSet.h:99
RangeSet intersection(RangeSet const &s) const
intersection returns the intersection of this set and s.
Definition: RangeSet.cc:135
void erase(std::tuple< U, U > const &range)
Definition: RangeSet.h:316
RangeSet & operator=(RangeSet &&)=default
bool intersects(uint64_t u) const
Definition: RangeSet.h:425
RangeSet operator-(RangeSet const &s) const
The - operator returns the difference between this set and s.
Definition: RangeSet.h:368
RangeSet & operator|=(RangeSet const &s)
The |= operator assigns the union of this set and s to this set.
Definition: RangeSet.h:389
RangeSet & operator&=(RangeSet const &s)
The &= operator assigns the intersection of this set and s to this set.
Definition: RangeSet.h:379
RangeSet operator~() const
The ~ operator returns the complement of this set.
Definition: RangeSet.h:351
void clear()
clear removes all integers from this set.
Definition: RangeSet.h:501
Iterator beginc() const
beginc returns a constant iterator to the first range in the complement of this set.
Definition: RangeSet.h:529
bool isValid() const
isValid checks that this RangeSet is in a valid state.
Definition: RangeSet.cc:377
bool operator!=(RangeSet const &rs) const
Definition: RangeSet.h:273
ptrdiff_t difference_type
Definition: RangeSet.h:175
size_t max_size() const
max_size returns the maximum number of ranges a set can hold.
Definition: RangeSet.h:536
Iterator end() const
Definition: RangeSet.h:523
RangeSet(RangeSet &&)=default
bool isWithin(uint64_t u) const
Definition: RangeSet.h:445
void insert(uint64_t u)
Definition: RangeSet.h:285
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
Iterator cend() const
Definition: RangeSet.h:524
RangeSet(InputIterator a, InputIterator b)
This generic constructor creates a set containing the integers or ranges obtained by dereferencing th...
Definition: RangeSet.h:235
bool contains(uint64_t u) const
Definition: RangeSet.h:435
RangeSet join(RangeSet const &s) const
join returns the union of this set and s.
Definition: RangeSet.cc:145
bool isWithin(RangeSet const &s) const
Definition: RangeSet.h:449
RangeSet & scale(uint64_t i)
scale multiplies the endpoints of each range in this set by the given integer.
Definition: RangeSet.cc:354
bool isDisjointFrom(uint64_t u) const
Definition: RangeSet.h:455
RangeSet & operator=(RangeSet const &)=default
RangeSet simplified(uint32_t n) const
simplified returns a simplified copy of this set.
Definition: RangeSet.h:479
bool empty() const
empty checks whether there are any integers in this set.
Definition: RangeSet.h:507
RangeSet scaled(uint64_t i) const
scaled returns a scaled copy of this set.
Definition: RangeSet.h:494
void insert(std::tuple< U, U > const &range)
Definition: RangeSet.h:295
RangeSet & operator^=(RangeSet const &s)
The ^= operator assigns the symmetric difference between this set and s to this set.
Definition: RangeSet.h:411
RangeSet & complement()
complement replaces this set S with U ∖ S, where U is the universe of range sets, [0,...
Definition: RangeSet.h:328
Iterator endc() const
endc returns a constant iterator to to the range after the last one in the complement of this set.
Definition: RangeSet.h:533
RangeSet operator|(RangeSet const &s) const
The | operator returns the union of this set and s.
Definition: RangeSet.h:363
Iterator begin() const
Definition: RangeSet.h:516
RangeSet operator&(RangeSet const &s) const
The & operator returns the intersection of this set and s.
Definition: RangeSet.h:358
size_t size() const
size returns the number of ranges in this set.
Definition: RangeSet.h:539
void swap(RangeSet &s)
Definition: RangeSet.h:547
RangeSet(Container const &c)
This generic constructor creates a set containing the integers or integer ranges in the given contain...
Definition: RangeSet.h:264
RangeSet()=default
The default constructor creates an empty set.
void fill()
fill adds all the unsigned 64 bit integers to this set.
Definition: RangeSet.h:504
Iterator cbegin() const
Definition: RangeSet.h:517
RangeSet(uint64_t u)
Definition: RangeSet.h:191
bool isDisjointFrom(uint64_t first, uint64_t last) const
Definition: RangeSet.h:457
bool isDisjointFrom(RangeSet const &s) const
Definition: RangeSet.h:461
void erase(uint64_t u)
Definition: RangeSet.h:306
RangeSet operator^(RangeSet const &s) const
The ^ operator returns the symmetric difference between this set and s.
Definition: RangeSet.h:373
RangeSet(uint64_t first, uint64_t last)
Definition: RangeSet.h:195
RangeSet(RangeSet const &)=default
RangeSet complemented() const
complemented returns a complemented copy of this set.
Definition: RangeSet.h:331
bool operator==(RangeSet const &rs) const
Definition: RangeSet.h:269
RangeSet difference(RangeSet const &s) const
difference returns the difference between this set and s.
Definition: RangeSet.cc:157
RangeSet & simplify(uint32_t n)
simplify simplifies this range set by "coarsening" its ranges.
Definition: RangeSet.cc:308
RangeSet(std::tuple< U, U > const &range)
Definition: RangeSet.h:205
RangeSet & operator-=(RangeSet const &s)
The -= operator assigns the difference between this set and s to this set.
Definition: RangeSet.h:399
uint64_t cardinality() const
cardinality returns the number of integers in this set.
Definition: RangeSet.cc:300
RangeSet symmetricDifference(RangeSet const &s) const
symmetricDifference returns the symmetric difference of this set and s.
Definition: RangeSet.cc:166
T data(T... args)
T declval(T... args)
T end(T... args)
T make_tuple(T... args)
T max_size(T... args)
FastFinder::Iterator Iterator
Definition: FastFinder.cc:178
void swap(RangeSet &a, RangeSet &b)
Definition: RangeSet.h:608
std::ostream & operator<<(std::ostream &, Angle const &)
Definition: Angle.cc:34
A base class for image defects.
STL namespace.
T size(T... args)
A constant iterator over the ranges (represented as 2-tuples) in a RangeSet.
Definition: RangeSet.h:122
friend void swap(Iterator &a, Iterator &b)
Definition: RangeSet.h:133
Iterator & operator+=(ptrdiff_t n)
Definition: RangeSet.h:147
bool operator<=(Iterator const &i) const
Definition: RangeSet.h:161
std::tuple< uint64_t, uint64_t > operator*()
Definition: RangeSet.h:164
ptrdiff_t operator-(Iterator const &i) const
Definition: RangeSet.h:154
Iterator operator-(ptrdiff_t n) const
Definition: RangeSet.h:145
Iterator & operator-=(ptrdiff_t n)
Definition: RangeSet.h:148
std::tuple< uint64_t, uint64_t > operator[](ptrdiff_t n) const
Definition: RangeSet.h:168
Iterator(uint64_t const *ptr)
Definition: RangeSet.h:131
Iterator operator+(ptrdiff_t n) const
Definition: RangeSet.h:144
friend Iterator operator+(ptrdiff_t n, Iterator const &i)
Definition: RangeSet.h:150
bool operator>=(Iterator const &i) const
Definition: RangeSet.h:162
bool operator==(Iterator const &i) const
Definition: RangeSet.h:157
bool operator!=(Iterator const &i) const
Definition: RangeSet.h:158
bool operator>(Iterator const &i) const
Definition: RangeSet.h:160
bool operator<(Iterator const &i) const
Definition: RangeSet.h:159
T swap(T... args)