LSSTApplications  17.0+124,17.0+14,17.0+73,18.0.0+37,18.0.0+80,18.0.0-4-g68ffd23+4,18.1.0-1-g0001055+12,18.1.0-1-g03d53ef+5,18.1.0-1-g1349e88+55,18.1.0-1-g2505f39+44,18.1.0-1-g5315e5e+4,18.1.0-1-g5e4b7ea+14,18.1.0-1-g7e8fceb+4,18.1.0-1-g85f8cd4+48,18.1.0-1-g8ff0b9f+4,18.1.0-1-ga2c679d+1,18.1.0-1-gd55f500+35,18.1.0-10-gb58edde+2,18.1.0-11-g0997b02+4,18.1.0-13-gfe4edf0b+12,18.1.0-14-g259bd21+21,18.1.0-19-gdb69f3f+2,18.1.0-2-g5f9922c+24,18.1.0-2-gd3b74e5+11,18.1.0-2-gfbf3545+32,18.1.0-26-g728bddb4+5,18.1.0-27-g6ff7ca9+2,18.1.0-3-g52aa583+25,18.1.0-3-g8ea57af+9,18.1.0-3-gb69f684+42,18.1.0-3-gfcaddf3+6,18.1.0-32-gd8786685a,18.1.0-4-gf3f9b77+6,18.1.0-5-g1dd662b+2,18.1.0-5-g6dbcb01+41,18.1.0-6-gae77429+3,18.1.0-7-g9d75d83+9,18.1.0-7-gae09a6d+30,18.1.0-9-gc381ef5+4,w.2019.45
LSSTDataManagementBasePackage
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<
250  std::input_iterator_tag,
251  typename std::iterator_traits<decltype(
254  >::value
255  &&
257  std::input_iterator_tag,
258  typename std::iterator_traits<decltype(
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 
613 
614 }} // namespace lsst::sphgeom
615 
616 #endif // LSST_SPHGEOM_RANGESET_H_
RangeSet operator-(RangeSet const &s) const
The - operator returns the difference between this set and s.
Definition: RangeSet.h:368
bool operator!=(Iterator const &i) const
Definition: RangeSet.h:158
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
bool operator!=(RangeSet const &rs) const
Definition: RangeSet.h:273
bool operator>(Iterator const &i) const
Definition: RangeSet.h:160
bool operator>=(Iterator const &i) const
Definition: RangeSet.h:162
void clear()
clear removes all integers from this set.
Definition: RangeSet.h:501
void insert(std::tuple< U, U > const &range)
Definition: RangeSet.h:295
bool operator<(Iterator const &i) const
Definition: RangeSet.h:159
bool operator==(Iterator const &i) const
Definition: RangeSet.h:157
bool operator==(RangeSet const &rs) const
Definition: RangeSet.h:269
bool contains(uint64_t u) const
Definition: RangeSet.h:435
RangeSet & operator^=(RangeSet const &s)
The ^= operator assigns the symmetric difference between this set and s to this set.
Definition: RangeSet.h:411
T swap(T... args)
Iterator cbegin() const
Definition: RangeSet.h:517
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
ptrdiff_t operator-(Iterator const &i) const
Definition: RangeSet.h:154
RangeSet & operator &=(RangeSet const &s)
The &= operator assigns the intersection of this set and s to this set.
Definition: RangeSet.h:379
bool isDisjointFrom(RangeSet const &s) const
Definition: RangeSet.h:461
RangeSet complemented() const
complemented returns a complemented copy of this set.
Definition: RangeSet.h:331
RangeSet & operator=(RangeSet const &)=default
bool operator<=(Iterator const &i) const
Definition: RangeSet.h:161
RangeSet()=default
The default constructor creates an empty set.
table::Key< int > a
RangeSet(uint64_t u)
Definition: RangeSet.h:191
STL namespace.
std::ostream & operator<<(std::ostream &, Angle const &)
Definition: Angle.cc:34
friend Iterator operator+(ptrdiff_t n, Iterator const &i)
Definition: RangeSet.h:150
Iterator begin() const
Definition: RangeSet.h:516
T make_tuple(T... args)
std::tuple< uint64_t, uint64_t > operator*()
Definition: RangeSet.h:164
bool isDisjointFrom(uint64_t first, uint64_t last) const
Definition: RangeSet.h:457
T end(T... args)
bool isDisjointFrom(uint64_t u) const
Definition: RangeSet.h:455
Iterator & operator-=(ptrdiff_t n)
Definition: RangeSet.h:148
Iterator operator-(ptrdiff_t n) const
Definition: RangeSet.h:145
Iterator beginc() const
beginc returns a constant iterator to the first range in the complement of this set.
Definition: RangeSet.h:529
RangeSet & simplify(uint32_t n)
simplify simplifies this range set by "coarsening" its ranges.
Definition: RangeSet.cc:308
RangeSet simplified(uint32_t n) const
simplified returns a simplified copy of this set.
Definition: RangeSet.h:479
Iterator end() const
Definition: RangeSet.h:523
void erase(std::tuple< U, U > const &range)
Definition: RangeSet.h:316
std::tuple< uint64_t, uint64_t > operator[](ptrdiff_t n) const
Definition: RangeSet.h:168
Iterator cend() const
Definition: RangeSet.h:524
RangeSet(std::tuple< U, U > const &range)
Definition: RangeSet.h:205
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
bool isWithin(RangeSet const &s) const
Definition: RangeSet.h:449
void erase(uint64_t u)
Definition: RangeSet.h:306
RangeSet & scale(uint64_t i)
scale multiplies the endpoints of each range in this set by the given integer.
Definition: RangeSet.cc:354
RangeSet & operator-=(RangeSet const &s)
The -= operator assigns the difference between this set and s to this set.
Definition: RangeSet.h:399
Iterator operator+(ptrdiff_t n) const
Definition: RangeSet.h:144
T data(T... args)
A base class for image defects.
RangeSet(uint64_t first, uint64_t last)
Definition: RangeSet.h:195
table::Key< int > type
Definition: Detector.cc:163
size_t max_size() const
max_size returns the maximum number of ranges a set can hold.
Definition: RangeSet.h:536
void swap(RangeSet &s)
Definition: RangeSet.h:547
T declval(T... args)
RangeSet scaled(uint64_t i) const
scaled returns a scaled copy of this set.
Definition: RangeSet.h:494
RangeSet operator &(RangeSet const &s) const
The & operator returns the intersection of this set and s.
Definition: RangeSet.h:358
RangeSet operator|(RangeSet const &s) const
The | operator returns the union of this set and s.
Definition: RangeSet.h:363
Iterator & operator+=(ptrdiff_t n)
Definition: RangeSet.h:147
RangeSet operator^(RangeSet const &s) const
The ^ operator returns the symmetric difference between this set and s.
Definition: RangeSet.h:373
T size(T... args)
bool intersects(uint64_t u) const
Definition: RangeSet.h:425
Iterator(uint64_t const *ptr)
Definition: RangeSet.h:131
bool isValid() const
isValid checks that this RangeSet is in a valid state.
Definition: RangeSet.cc:377
T begin(T... args)
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~() const
The ~ operator returns the complement of this set.
Definition: RangeSet.h:351
RangeSet & operator|=(RangeSet const &s)
The |= operator assigns the union of this set and s to this set.
Definition: RangeSet.h:389
A RangeSet is a set of unsigned 64 bit integers.
Definition: RangeSet.h:99
void fill()
fill adds all the unsigned 64 bit integers to this set.
Definition: RangeSet.h:504
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
void insert(uint64_t u)
Definition: RangeSet.h:285
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.
std::input_iterator_tag iterator_category
Definition: RangeSet.h:128
ptrdiff_t difference_type
Definition: RangeSet.h:175
RangeSet(InputIterator a, InputIterator b)
This generic constructor creates a set containing the integers or ranges obtained by dereferencing th...
Definition: RangeSet.h:235
size_t size() const
size returns the number of ranges in this set.
Definition: RangeSet.h:539
RangeSet(Container const &c)
This generic constructor creates a set containing the integers or integer ranges in the given contain...
Definition: RangeSet.h:264
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