LSST Applications g063fba187b+fee0456c91,g0f08755f38+ea96e5a5a3,g1653933729+a8ce1bb630,g168dd56ebc+a8ce1bb630,g1a2382251a+90257ff92a,g20f6ffc8e0+ea96e5a5a3,g217e2c1bcf+937a289c59,g28da252d5a+daa7da44eb,g2bbee38e9b+253935c60e,g2bc492864f+253935c60e,g3156d2b45e+6e55a43351,g32e5bea42b+31359a2a7a,g347aa1857d+253935c60e,g35bb328faa+a8ce1bb630,g3a166c0a6a+253935c60e,g3b1af351f3+a8ce1bb630,g3e281a1b8c+c5dd892a6c,g414038480c+416496e02f,g41af890bb2+afe91b1188,g599934f4f4+0db33f7991,g7af13505b9+e36de7bce6,g80478fca09+da231ba887,g82479be7b0+a4516e59e3,g858d7b2824+ea96e5a5a3,g89c8672015+f4add4ffd5,g9125e01d80+a8ce1bb630,ga5288a1d22+bc6ab8dfbd,gb58c049af0+d64f4d3760,gc28159a63d+253935c60e,gcab2d0539d+3f2b72788c,gcf0d15dbbd+4ea9c45075,gda6a2b7d83+4ea9c45075,gdaeeff99f8+1711a396fd,ge79ae78c31+253935c60e,gef2f8181fd+3031e3cf99,gf0baf85859+c1f95f4921,gfa517265be+ea96e5a5a3,gfa999e8aa5+17cd334064,w.2024.50
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(std::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 std::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
199 insert(u);
200 }
201
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<std::uint64_t>(std::get<0>(range)),
214 static_cast<std::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
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(std::uint64_t first, std::uint64_t last);
308
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(std::uint64_t first, std::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(std::uint64_t u) const { return intersects(u, u + 1); }
433
434 bool intersects(std::uint64_t first, std::uint64_t last) const;
435
436 bool intersects(RangeSet const & s) const;
438
442 bool contains(std::uint64_t u) const { return contains(u, u + 1); }
443
444 bool contains(std::uint64_t first, std::uint64_t last) const;
445
446 bool contains(RangeSet const & s) const;
448
452 bool isWithin(std::uint64_t u) const { return isWithin(u, u + 1); }
453
454 bool isWithin(std::uint64_t first, std::uint64_t last) const;
455
456 bool isWithin(RangeSet const & s) const { return s.contains(*this); }
458
462 bool isDisjointFrom(std::uint64_t u) const { return !intersects(u); }
463
465 return !intersects(first, last);
466 }
467
468 bool isDisjointFrom(RangeSet const & s) const { return !intersects(s); }
470
484
487 RangeSet rs(*this);
488 rs.simplify(n);
489 return rs;
490 }
491
499
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
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<std::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 std::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 std::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 std::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 std::uint64_t const * _endc() const {
590 size_t s = _ranges.size();
591 return _ranges.data() + (s - ((s & 1) ^ !_offset));
592 }
593
594 void _insert(std::uint64_t first, std::uint64_t last);
595
596 static void _intersectOne(std::vector<std::uint64_t> &,
597 std::uint64_t const *,
598 std::uint64_t const *, std::uint64_t const *);
599
600 static void _intersect(std::vector<std::uint64_t> &,
601 std::uint64_t const *, std::uint64_t const *,
602 std::uint64_t const *, std::uint64_t const *);
603
604 void _intersect(std::uint64_t const *, std::uint64_t const *,
605 std::uint64_t const *, std::uint64_t const *);
606
607 static bool _intersectsOne(std::uint64_t const *,
608 std::uint64_t const *, std::uint64_t const *);
609
610 static bool _intersects(std::uint64_t const *, std::uint64_t const *,
611 std::uint64_t const *, std::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_
std::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
std::uint64_t cardinality() const
cardinality returns the number of integers in this set.
Definition RangeSet.cc:307
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
RangeSet(std::uint64_t u)
Definition RangeSet.h:198
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 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 & scale(std::uint64_t i)
scale multiplies the endpoints of each range in this set by the given integer.
Definition RangeSet.cc:361
bool intersects(std::uint64_t u) const
Definition RangeSet.h:432
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
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
bool empty() const
empty checks whether there are any integers in this set.
Definition RangeSet.h:514
void insert(std::tuple< U, U > const &range)
Definition RangeSet.h:302
RangeSet(std::uint64_t first, std::uint64_t last)
Definition RangeSet.h:202
RangeSet & operator^=(RangeSet const &s)
The ^= operator assigns the symmetric difference between this set and s to this set.
Definition RangeSet.h:418
void erase(std::uint64_t u)
Definition RangeSet.h:313
bool contains(std::uint64_t u) const
Definition RangeSet.h:442
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
bool isDisjointFrom(std::uint64_t first, std::uint64_t last) const
Definition RangeSet.h:464
bool isWithin(std::uint64_t u) const
Definition RangeSet.h:452
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 simplified(std::uint32_t n) const
simplified returns a simplified copy of this set.
Definition RangeSet.h:486
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
bool isDisjointFrom(std::uint64_t u) const
Definition RangeSet.h:462
RangeSet()=default
The default constructor creates an empty set.
RangeSet & simplify(std::uint32_t n)
simplify simplifies this range set by "coarsening" its ranges.
Definition RangeSet.cc:315
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(RangeSet const &s) const
Definition RangeSet.h:468
RangeSet operator^(RangeSet const &s) const
The ^ operator returns the symmetric difference between this set and s.
Definition RangeSet.h:380
RangeSet scaled(std::uint64_t i) const
scaled returns a scaled copy of this set.
Definition RangeSet.h:501
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(std::tuple< U, U > const &range)
Definition RangeSet.h:212
RangeSet & operator=(RangeSet &&)=default
RangeSet symmetricDifference(RangeSet const &s) const
symmetricDifference returns the symmetric difference of this set and s.
Definition RangeSet.cc:173
void insert(std::uint64_t u)
Definition RangeSet.h:292
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::uint64_t const * p
Definition RangeSet.h:179
std::tuple< std::uint64_t, std::uint64_t > operator[](ptrdiff_t n) const
Definition RangeSet.h:175
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
Iterator(std::uint64_t const *ptr)
Definition RangeSet.h:138
bool operator>(Iterator const &i) const
Definition RangeSet.h:167
bool operator<(Iterator const &i) const
Definition RangeSet.h:166
std::tuple< std::uint64_t, std::uint64_t > operator*()
Definition RangeSet.h:171
T swap(T... args)