LSST Applications 27.0.0,g0265f82a02+469cd937ee,g02d81e74bb+21ad69e7e1,g1470d8bcf6+cbe83ee85a,g2079a07aa2+e67c6346a6,g212a7c68fe+04a9158687,g2305ad1205+94392ce272,g295015adf3+81dd352a9d,g2bbee38e9b+469cd937ee,g337abbeb29+469cd937ee,g3939d97d7f+72a9f7b576,g487adcacf7+71499e7cba,g50ff169b8f+5929b3527e,g52b1c1532d+a6fc98d2e7,g591dd9f2cf+df404f777f,g5a732f18d5+be83d3ecdb,g64a986408d+21ad69e7e1,g858d7b2824+21ad69e7e1,g8a8a8dda67+a6fc98d2e7,g99cad8db69+f62e5b0af5,g9ddcbc5298+d4bad12328,ga1e77700b3+9c366c4306,ga8c6da7877+71e4819109,gb0e22166c9+25ba2f69a1,gb6a65358fc+469cd937ee,gbb8dafda3b+69d3c0e320,gc07e1c2157+a98bf949bb,gc120e1dc64+615ec43309,gc28159a63d+469cd937ee,gcf0d15dbbd+72a9f7b576,gdaeeff99f8+a38ce5ea23,ge6526c86ff+3a7c1ac5f1,ge79ae78c31+469cd937ee,gee10cc3b42+a6fc98d2e7,gf1cff7945b+21ad69e7e1,gfbcc870c63+9a11dc8c8f
LSST Data Management Base Package
Loading...
Searching...
No Matches
RangeSet.h
Go to the documentation of this file.
1/*
2 * This file is part of sphgeom.
3 *
4 * Developed for the LSST Data Management System.
5 * This product includes software developed by the LSST Project
6 * (http://www.lsst.org).
7 * See the COPYRIGHT file at the top-level directory of this distribution
8 * for details of code ownership.
9 *
10 * This software is dual licensed under the GNU General Public License and also
11 * under a 3-clause BSD license. Recipients may choose which of these licenses
12 * to use; please see the files gpl-3.0.txt and/or bsd_license.txt,
13 * respectively. If you choose the GPL option then the following text applies
14 * (but note that there is still no warranty even if you opt for BSD instead):
15 *
16 * This program is free software: you can redistribute it and/or modify
17 * it under the terms of the GNU General Public License as published by
18 * the Free Software Foundation, either version 3 of the License, or
19 * (at your option) any later version.
20 *
21 * This program is distributed in the hope that it will be useful,
22 * but WITHOUT ANY WARRANTY; without even the implied warranty of
23 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
24 * GNU General Public License for more details.
25 *
26 * You should have received a copy of the GNU General Public License
27 * along with this program. If not, see <http://www.gnu.org/licenses/>.
28 */
29
30#ifndef LSST_SPHGEOM_RANGESET_H_
31#define LSST_SPHGEOM_RANGESET_H_
32
35
36#include <cstddef>
37#include <cstdint>
38#include <initializer_list>
39#include <iosfwd>
40#include <iterator>
41#include <tuple>
42#include <type_traits>
43#include <vector>
44
45
46namespace lsst {
47namespace sphgeom {
48
106class RangeSet {
107public:
108
129 struct Iterator {
130 // For std::iterator_traits
131 using difference_type = ptrdiff_t;
133 using pointer = void;
136
137 Iterator() = default;
138 explicit Iterator(uint64_t const * ptr) : p{ptr} {}
139
140 friend void swap(Iterator & a, Iterator & b) {
141 std::swap(a.p, b.p);
142 }
143
144 // Arithmetic
145 Iterator & operator++() { p += 2; return *this; }
146 Iterator & operator--() { p -= 2; return *this; }
147
148 Iterator operator++(int) { Iterator i(*this); p += 2; return i; }
149 Iterator operator--(int) { Iterator i(*this); p -= 2; return i; }
150
151 Iterator operator+(ptrdiff_t n) const { return Iterator(p + 2 * n); }
152 Iterator operator-(ptrdiff_t n) const { return Iterator(p + 2 * n); }
153
154 Iterator & operator+=(ptrdiff_t n) { p += 2 * n; return *this; }
155 Iterator & operator-=(ptrdiff_t n) { p -= 2 * n; return *this; }
156
157 friend Iterator operator+(ptrdiff_t n, Iterator const & i) {
158 return i + n;
159 }
160
161 ptrdiff_t operator-(Iterator const & i) const { return (p - i.p) / 2; }
162
163 // Comparison
164 bool operator==(Iterator const & i) const { return p == i.p; }
165 bool operator!=(Iterator const & i) const { return p != i.p; }
166 bool operator<(Iterator const & i) const { return p < i.p; }
167 bool operator>(Iterator const & i) const { return p > i.p; }
168 bool operator<=(Iterator const & i) const { return p <= i.p; }
169 bool operator>=(Iterator const & i) const { return p >= i.p; }
170
174
176 return std::make_tuple(p[2 * n], p[2 * n + 1]);
177 }
178
179 uint64_t const * p = nullptr;
180 };
181
182 using difference_type = ptrdiff_t;
183 using size_type = size_t;
186
187 RangeSet(RangeSet const &) = default;
188 RangeSet(RangeSet &&) = default;
189 RangeSet & operator=(RangeSet const &) = default;
190 RangeSet & operator=(RangeSet &&) = default;
191
193 RangeSet() = default;
194
198 explicit RangeSet(uint64_t u) {
199 insert(u);
200 }
201
202 RangeSet(uint64_t first, uint64_t last) {
203 insert(first, last);
204 }
205
206 template <
207 typename U,
208 typename = typename std::enable_if<
210 >::type
211 >
212 explicit RangeSet(std::tuple<U, U> const & range) {
213 insert(static_cast<uint64_t>(std::get<0>(range)),
214 static_cast<uint64_t>(std::get<1>(range)));
215 }
216
218
219 // Note: the standard library for GCC unfortunately declares explicit conversion
220 // constructors for tuples - the use of std::pair is required for code like:
221 //
222 // RangeSet s = {{0, 1}, {2, 3}};
223 //
224 // to compile.
227
233 template <
234 typename InputIterator,
235 typename = typename std::enable_if<
239 >::value
240 >::type
241 >
242 RangeSet(InputIterator a, InputIterator b) {
243 for (; a != b; ++a) {
244 insert(*a);
245 }
246 }
247
253 template <
254 typename Container,
255 typename = typename std::enable_if<
258 typename std::iterator_traits<decltype(
260 )>::iterator_category
261 >::value
262 &&
265 typename std::iterator_traits<decltype(
267 )>::iterator_category
268 >::value
269 >::type
270 >
271 explicit RangeSet(Container const & c) :
272 RangeSet(std::begin(c), std::end(c)) {}
273
276 bool operator==(RangeSet const & rs) const {
277 return _offset == rs._offset && _ranges == rs._ranges;
278 }
279
280 bool operator!=(RangeSet const & rs) const {
281 return _offset != rs._offset || _ranges != rs._ranges;
282 }
284
292 void insert(uint64_t u) {
293 insert(u, u + 1);
294 }
295
296 template <
297 typename U,
298 typename = typename std::enable_if<
300 >::type
301 >
302 void insert(std::tuple<U, U> const & range) {
303 insert(std::get<0>(range), std::get<1>(range));
304 }
305
306 void insert(uint64_t first, uint64_t last);
308
313 void erase(uint64_t u) {
314 erase(u, u + 1);
315 }
316
317 template <
318 typename U,
319 typename = typename std::enable_if<
321 >::type
322 >
323 void erase(std::tuple<U, U> const & range) {
324 erase(std::get<0>(range), std::get<1>(range));
325 }
326
327 void erase(uint64_t first, uint64_t last);
329
332
335 RangeSet & complement() { _offset = !_offset; return *this; }
336
339 RangeSet s(*this);
340 s.complement();
341 return s;
342 }
343
345 RangeSet intersection(RangeSet const & s) const;
346
348 RangeSet join(RangeSet const & s) const;
349
351 RangeSet difference(RangeSet const & s) const;
352
355 RangeSet symmetricDifference(RangeSet const & s) const;
356
359 RangeSet s(*this);
360 s.complement();
361 return s;
362 }
363
365 RangeSet operator&(RangeSet const & s) const {
366 return intersection(s);
367 }
368
370 RangeSet operator|(RangeSet const & s) const {
371 return join(s);
372 }
373
375 RangeSet operator-(RangeSet const & s) const {
376 return difference(s);
377 }
378
380 RangeSet operator^(RangeSet const & s) const {
381 return symmetricDifference(s);
382 }
383
387 if (this != &s) {
388 RangeSet r = intersection(s);
389 swap(r);
390 }
391 return *this;
392 }
393
397 if (this != &s) {
398 RangeSet r = join(s);
399 swap(r);
400 }
401 return *this;
402 }
403
407 if (this != &s) {
408 RangeSet r = difference(s);
409 swap(r);
410 } else {
411 clear();
412 }
413 return *this;
414 }
415
419 if (this != &s) {
421 swap(r);
422 } else {
423 clear();
424 }
425 return *this;
426 }
428
432 bool intersects(uint64_t u) const { return intersects(u, u + 1); }
433
434 bool intersects(uint64_t first, uint64_t last) const;
435
436 bool intersects(RangeSet const & s) const;
438
442 bool contains(uint64_t u) const { return contains(u, u + 1); }
443
444 bool contains(uint64_t first, uint64_t last) const;
445
446 bool contains(RangeSet const & s) const;
448
452 bool isWithin(uint64_t u) const { return isWithin(u, u + 1); }
453
454 bool isWithin(uint64_t first, uint64_t last) const;
455
456 bool isWithin(RangeSet const & s) const { return s.contains(*this); }
458
462 bool isDisjointFrom(uint64_t u) const { return !intersects(u); }
463
464 bool isDisjointFrom(uint64_t first, uint64_t last) const {
465 return !intersects(first, last);
466 }
467
468 bool isDisjointFrom(RangeSet const & s) const { return !intersects(s); }
470
483 RangeSet & simplify(uint32_t n);
484
486 RangeSet simplified(uint32_t n) const {
487 RangeSet rs(*this);
488 rs.simplify(n);
489 return rs;
490 }
491
498 RangeSet & scale(uint64_t i);
499
501 RangeSet scaled(uint64_t i) const {
502 RangeSet rs(*this);
503 rs.scale(i);
504 return rs;
505 }
506
508 void clear() { _ranges = {0, 0}; _offset = true; }
509
511 void fill() { _ranges = {0, 0}; _offset = false; }
512
514 bool empty() const { return _begin() == _end(); }
515
518 bool full() const { return _beginc() == _endc(); }
519
523 Iterator begin() const { return Iterator(_begin()); }
524 Iterator cbegin() const { return begin(); }
526
530 Iterator end() const { return Iterator(_end()); }
531 Iterator cend() const { return end(); }
533
536 Iterator beginc() const { return Iterator(_beginc()); }
537
540 Iterator endc() const { return Iterator(_endc()); }
541
543 size_t max_size() const { return _ranges.max_size() / 2; }
544
546 size_t size() const { return (_ranges.size() - _offset) / 2; }
547
552 uint64_t cardinality() const;
553
554 void swap(RangeSet & s) {
555 using std::swap;
556 swap(_ranges, s._ranges);
557 swap(_offset, s._offset);
558 }
559
565 bool isValid() const;
566
567private:
568 std::vector<uint64_t> _ranges = {0, 0};
569
570 // The offset of the first range in _ranges. It is 0 (false) if the
571 // first integer in the set is 0, and 1 (true) otherwise.
572 bool _offset = true;
573
574 // `_begin` returns a pointer to the first range in this set.
575 uint64_t const * _begin() const { return _ranges.data() + _offset; }
576
577 // `_end` returns a pointer to the range after the last one in this set.
578 uint64_t const * _end() const {
579 size_t s = _ranges.size();
580 return _ranges.data() + (s - ((s & 1) ^ _offset));
581 }
582
583 // `_beginc` returns a pointer to the first range in
584 // the complement of this set.
585 uint64_t const * _beginc() const { return _ranges.data() + !_offset; }
586
587 // `_endc` returns a pointer to the range after the last one in
588 // the complement of this set.
589 uint64_t const * _endc() const {
590 size_t s = _ranges.size();
591 return _ranges.data() + (s - ((s & 1) ^ !_offset));
592 }
593
594 void _insert(uint64_t first, uint64_t last);
595
596 static void _intersectOne(std::vector<uint64_t> &,
597 uint64_t const *,
598 uint64_t const *, uint64_t const *);
599
600 static void _intersect(std::vector<uint64_t> &,
601 uint64_t const *, uint64_t const *,
602 uint64_t const *, uint64_t const *);
603
604 void _intersect(uint64_t const *, uint64_t const *,
605 uint64_t const *, uint64_t const *);
606
607 static bool _intersectsOne(uint64_t const *,
608 uint64_t const *, uint64_t const *);
609
610 static bool _intersects(uint64_t const *, uint64_t const *,
611 uint64_t const *, uint64_t const *);
612};
613
614
615inline void swap(RangeSet & a, RangeSet & b) {
616 a.swap(b);
617}
618
619std::ostream & operator<<(std::ostream &, RangeSet const &);
620
621}} // namespace lsst::sphgeom
622
623#endif // LSST_SPHGEOM_RANGESET_H_
uint64_t * ptr
Definition RangeSet.cc:95
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:106
RangeSet intersection(RangeSet const &s) const
intersection returns the intersection of this set and s.
Definition RangeSet.cc:142
void erase(std::tuple< U, U > const &range)
Definition RangeSet.h:323
bool intersects(uint64_t u) const
Definition RangeSet.h:432
RangeSet operator-(RangeSet const &s) const
The - operator returns the difference between this set and s.
Definition RangeSet.h:375
RangeSet & operator=(RangeSet const &)=default
RangeSet operator~() const
The ~ operator returns the complement of this set.
Definition RangeSet.h:358
void clear()
clear removes all integers from this set.
Definition RangeSet.h:508
Iterator beginc() const
beginc returns a constant iterator to the first range in the complement of this set.
Definition RangeSet.h:536
bool isValid() const
isValid checks that this RangeSet is in a valid state.
Definition RangeSet.cc:384
bool operator!=(RangeSet const &rs) const
Definition RangeSet.h:280
ptrdiff_t difference_type
Definition RangeSet.h:182
size_t max_size() const
max_size returns the maximum number of ranges a set can hold.
Definition RangeSet.h:543
Iterator end() const
Definition RangeSet.h:530
RangeSet(RangeSet &&)=default
RangeSet & operator|=(RangeSet const &s)
The |= operator assigns the union of this set and s to this set.
Definition RangeSet.h:396
bool isWithin(uint64_t u) const
Definition RangeSet.h:452
void insert(uint64_t u)
Definition RangeSet.h:292
bool full() const
full checks whether all integers in the universe of range sets, [0, 2^64), are in this set.
Definition RangeSet.h:518
Iterator cend() const
Definition RangeSet.h:531
RangeSet(InputIterator a, InputIterator b)
This generic constructor creates a set containing the integers or ranges obtained by dereferencing th...
Definition RangeSet.h:242
RangeSet & operator-=(RangeSet const &s)
The -= operator assigns the difference between this set and s to this set.
Definition RangeSet.h:406
bool contains(uint64_t u) const
Definition RangeSet.h:442
RangeSet join(RangeSet const &s) const
join returns the union of this set and s.
Definition RangeSet.cc:152
bool isWithin(RangeSet const &s) const
Definition RangeSet.h:456
RangeSet & scale(uint64_t i)
scale multiplies the endpoints of each range in this set by the given integer.
Definition RangeSet.cc:361
bool isDisjointFrom(uint64_t u) const
Definition RangeSet.h:462
RangeSet simplified(uint32_t n) const
simplified returns a simplified copy of this set.
Definition RangeSet.h:486
bool empty() const
empty checks whether there are any integers in this set.
Definition RangeSet.h:514
RangeSet scaled(uint64_t i) const
scaled returns a scaled copy of this set.
Definition RangeSet.h:501
void insert(std::tuple< U, U > const &range)
Definition RangeSet.h:302
RangeSet & operator^=(RangeSet const &s)
The ^= operator assigns the symmetric difference between this set and s to this set.
Definition RangeSet.h:418
RangeSet & complement()
complement replaces this set S with U ∖ S, where U is the universe of range sets, [0,...
Definition RangeSet.h:335
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:540
RangeSet operator|(RangeSet const &s) const
The | operator returns the union of this set and s.
Definition RangeSet.h:370
Iterator begin() const
Definition RangeSet.h:523
RangeSet operator&(RangeSet const &s) const
The & operator returns the intersection of this set and s.
Definition RangeSet.h:365
size_t size() const
size returns the number of ranges in this set.
Definition RangeSet.h:546
RangeSet & operator&=(RangeSet const &s)
The &= operator assigns the intersection of this set and s to this set.
Definition RangeSet.h:386
void swap(RangeSet &s)
Definition RangeSet.h:554
RangeSet(Container const &c)
This generic constructor creates a set containing the integers or integer ranges in the given contain...
Definition RangeSet.h:271
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:511
Iterator cbegin() const
Definition RangeSet.h:524
bool isDisjointFrom(uint64_t first, uint64_t last) const
Definition RangeSet.h:464
bool isDisjointFrom(RangeSet const &s) const
Definition RangeSet.h:468
void erase(uint64_t u)
Definition RangeSet.h:313
RangeSet operator^(RangeSet const &s) const
The ^ operator returns the symmetric difference between this set and s.
Definition RangeSet.h:380
RangeSet(uint64_t first, uint64_t last)
Definition RangeSet.h:202
RangeSet(RangeSet const &)=default
RangeSet complemented() const
complemented returns a complemented copy of this set.
Definition RangeSet.h:338
bool operator==(RangeSet const &rs) const
Definition RangeSet.h:276
RangeSet difference(RangeSet const &s) const
difference returns the difference between this set and s.
Definition RangeSet.cc:164
RangeSet & simplify(uint32_t n)
simplify simplifies this range set by "coarsening" its ranges.
Definition RangeSet.cc:315
RangeSet(std::tuple< U, U > const &range)
Definition RangeSet.h:212
RangeSet & operator=(RangeSet &&)=default
uint64_t cardinality() const
cardinality returns the number of integers in this set.
Definition RangeSet.cc:307
RangeSet symmetricDifference(RangeSet const &s) const
symmetricDifference returns the symmetric difference of this set and s.
Definition RangeSet.cc:173
T data(T... args)
T declval(T... args)
T end(T... args)
T make_tuple(T... args)
T max_size(T... args)
void swap(RangeSet &a, RangeSet &b)
Definition RangeSet.h:615
std::ostream & operator<<(std::ostream &, Angle const &)
Definition Angle.cc:41
T size(T... args)
A constant iterator over the ranges (represented as 2-tuples) in a RangeSet.
Definition RangeSet.h:129
friend void swap(Iterator &a, Iterator &b)
Definition RangeSet.h:140
bool operator<=(Iterator const &i) const
Definition RangeSet.h:168
Iterator & operator+=(ptrdiff_t n)
Definition RangeSet.h:154
ptrdiff_t operator-(Iterator const &i) const
Definition RangeSet.h:161
Iterator operator-(ptrdiff_t n) const
Definition RangeSet.h:152
std::tuple< uint64_t, uint64_t > operator[](ptrdiff_t n) const
Definition RangeSet.h:175
std::tuple< uint64_t, uint64_t > operator*()
Definition RangeSet.h:171
Iterator(uint64_t const *ptr)
Definition RangeSet.h:138
Iterator operator+(ptrdiff_t n) const
Definition RangeSet.h:151
friend Iterator operator+(ptrdiff_t n, Iterator const &i)
Definition RangeSet.h:157
bool operator>=(Iterator const &i) const
Definition RangeSet.h:169
bool operator==(Iterator const &i) const
Definition RangeSet.h:164
bool operator!=(Iterator const &i) const
Definition RangeSet.h:165
Iterator & operator-=(ptrdiff_t n)
Definition RangeSet.h:155
bool operator>(Iterator const &i) const
Definition RangeSet.h:167
bool operator<(Iterator const &i) const
Definition RangeSet.h:166
T swap(T... args)