LSST Applications
21.0.0-172-gfb10e10a+18fedfabac,22.0.0+297cba6710,22.0.0+80564b0ff1,22.0.0+8d77f4f51a,22.0.0+a28f4c53b1,22.0.0+dcf3732eb2,22.0.1-1-g7d6de66+2a20fdde0d,22.0.1-1-g8e32f31+297cba6710,22.0.1-1-geca5380+7fa3b7d9b6,22.0.1-12-g44dc1dc+2a20fdde0d,22.0.1-15-g6a90155+515f58c32b,22.0.1-16-g9282f48+790f5f2caa,22.0.1-2-g92698f7+dcf3732eb2,22.0.1-2-ga9b0f51+7fa3b7d9b6,22.0.1-2-gd1925c9+bf4f0e694f,22.0.1-24-g1ad7a390+a9625a72a8,22.0.1-25-g5bf6245+3ad8ecd50b,22.0.1-25-gb120d7b+8b5510f75f,22.0.1-27-g97737f7+2a20fdde0d,22.0.1-32-gf62ce7b1+aa4237961e,22.0.1-4-g0b3f228+2a20fdde0d,22.0.1-4-g243d05b+871c1b8305,22.0.1-4-g3a563be+32dcf1063f,22.0.1-4-g44f2e3d+9e4ab0f4fa,22.0.1-42-gca6935d93+ba5e5ca3eb,22.0.1-5-g15c806e+85460ae5f3,22.0.1-5-g58711c4+611d128589,22.0.1-5-g75bb458+99c117b92f,22.0.1-6-g1c63a23+7fa3b7d9b6,22.0.1-6-g50866e6+84ff5a128b,22.0.1-6-g8d3140d+720564cf76,22.0.1-6-gd805d02+cc5644f571,22.0.1-8-ge5750ce+85460ae5f3,master-g6e05de7fdc+babf819c66,master-g99da0e417a+8d77f4f51a,w.2021.48
LSST Data Management Base Package
|
A RangeSet
is a set of unsigned 64 bit integers.
More...
#include <RangeSet.h>
Classes | |
struct | Iterator |
A constant iterator over the ranges (represented as 2-tuples) in a RangeSet. More... | |
Public Types | |
using | difference_type = ptrdiff_t |
using | size_type = size_t |
using | value_type = std::tuple< uint64_t, uint64_t > |
using | const_iterator = Iterator |
Public Member Functions | |
RangeSet (RangeSet const &)=default | |
RangeSet (RangeSet &&)=default | |
RangeSet & | operator= (RangeSet const &)=default |
RangeSet & | operator= (RangeSet &&)=default |
RangeSet ()=default | |
The default constructor creates an empty set. More... | |
template<typename InputIterator , typename = typename std::enable_if< std::is_base_of< std::input_iterator_tag, typename std::iterator_traits<InputIterator>::iterator_category >::value >::type> | |
RangeSet (InputIterator a, InputIterator b) | |
This generic constructor creates a set containing the integers or ranges obtained by dereferencing the iterators in [a, b). More... | |
template<typename Container , typename = typename std::enable_if< std::is_base_of< std::input_iterator_tag, typename std::iterator_traits<decltype( std::begin(std::declval<typename std::add_const<Container>::type>()) )>::iterator_category, ::value &&std::is_base_of< std::input_iterator_tag, typename std::iterator_traits< decltype(std::end(std::declval< typename std::add_const< Container >::type >()))>::iterator_category , ::value , ::type > | |
RangeSet (Container const &c) | |
This generic constructor creates a set containing the integers or integer ranges in the given container. More... | |
RangeSet & | simplify (uint32_t n) |
simplify simplifies this range set by "coarsening" its ranges. More... | |
RangeSet | simplified (uint32_t n) const |
simplified returns a simplified copy of this set. More... | |
RangeSet & | scale (uint64_t i) |
scale multiplies the endpoints of each range in this set by the given integer. More... | |
RangeSet | scaled (uint64_t i) const |
scaled returns a scaled copy of this set. More... | |
void | clear () |
clear removes all integers from this set. More... | |
void | fill () |
fill adds all the unsigned 64 bit integers to this set. More... | |
bool | empty () const |
empty checks whether there are any integers in this set. More... | |
bool | full () const |
full checks whether all integers in the universe of range sets, [0, 2^64), are in this set. More... | |
Iterator | beginc () const |
beginc returns a constant iterator to the first range in the complement of this set. More... | |
Iterator | endc () const |
endc returns a constant iterator to to the range after the last one in the complement of this set. More... | |
size_t | max_size () const |
max_size returns the maximum number of ranges a set can hold. More... | |
size_t | size () const |
size returns the number of ranges in this set. More... | |
uint64_t | cardinality () const |
cardinality returns the number of integers in this set. More... | |
void | swap (RangeSet &s) |
bool | isValid () const |
isValid checks that this RangeSet is in a valid state. More... | |
RangeSet (uint64_t u) | |
RangeSet (uint64_t first, uint64_t last) | |
template<typename U , typename = typename std::enable_if< std::is_convertible<U, uint64_t>::value >::type> | |
RangeSet (std::tuple< U, U > const &range) | |
RangeSet (std::initializer_list< uint64_t >) | |
RangeSet (std::initializer_list< std::pair< uint64_t, uint64_t >>) | |
bool | operator== (RangeSet const &rs) const |
bool | operator!= (RangeSet const &rs) const |
void | insert (uint64_t u) |
template<typename U , typename = typename std::enable_if< std::is_convertible<U, uint64_t>::value >::type> | |
void | insert (std::tuple< U, U > const &range) |
void | insert (uint64_t first, uint64_t last) |
void | erase (uint64_t u) |
template<typename U , typename = typename std::enable_if< std::is_convertible<U, uint64_t>::value >::type> | |
void | erase (std::tuple< U, U > const &range) |
void | erase (uint64_t first, uint64_t last) |
Set operations | |
RangeSet & | complement () |
complement replaces this set S with U ∖ S, where U is the universe of range sets, [0, 2^64). More... | |
RangeSet | complemented () const |
complemented returns a complemented copy of this set. More... | |
RangeSet | intersection (RangeSet const &s) const |
intersection returns the intersection of this set and s. More... | |
RangeSet | join (RangeSet const &s) const |
join returns the union of this set and s. More... | |
RangeSet | difference (RangeSet const &s) const |
difference returns the difference between this set and s. More... | |
RangeSet | symmetricDifference (RangeSet const &s) const |
symmetricDifference returns the symmetric difference of this set and s. More... | |
RangeSet | operator~ () const |
The ~ operator returns the complement of this set. More... | |
RangeSet | operator& (RangeSet const &s) const |
The & operator returns the intersection of this set and s. More... | |
RangeSet | operator| (RangeSet const &s) const |
The | operator returns the union of this set and s. More... | |
RangeSet | operator- (RangeSet const &s) const |
The - operator returns the difference between this set and s. More... | |
RangeSet | operator^ (RangeSet const &s) const |
The ^ operator returns the symmetric difference between this set and s. More... | |
RangeSet & | operator&= (RangeSet const &s) |
The &= operator assigns the intersection of this set and s to this set. More... | |
RangeSet & | operator|= (RangeSet const &s) |
The |= operator assigns the union of this set and s to this set. More... | |
RangeSet & | operator-= (RangeSet const &s) |
The -= operator assigns the difference between this set and s to this set. More... | |
RangeSet & | operator^= (RangeSet const &s) |
The ^= operator assigns the symmetric difference between this set and s to this set. More... | |
bool | intersects (uint64_t u) const |
bool | intersects (uint64_t first, uint64_t last) const |
bool | intersects (RangeSet const &s) const |
bool | contains (uint64_t u) const |
bool | contains (uint64_t first, uint64_t last) const |
bool | contains (RangeSet const &s) const |
bool | isWithin (uint64_t u) const |
bool | isWithin (uint64_t first, uint64_t last) const |
bool | isWithin (RangeSet const &s) const |
bool | isDisjointFrom (uint64_t u) const |
bool | isDisjointFrom (uint64_t first, uint64_t last) const |
bool | isDisjointFrom (RangeSet const &s) const |
Iterator | begin () const |
Iterator | cbegin () const |
Iterator | end () const |
Iterator | cend () const |
A RangeSet
is a set of unsigned 64 bit integers.
Internally, elements in the set are tracked using a sorted vector of disjoint, non-empty, half-open ranges, which is memory efficient for sets containing many consecutive integers.
Given a hierarchical pixelization of the sphere and a simple spherical region, a RangeSet is a good way to store the indexes of pixels intersecting the region. For an in-depth discussion of this use case, see:
Efficient data structures for masks on 2D grids M. Reinecke and E. Hivon Astronomy & Astrophysics, Volume 580, id.A132, 9 pp.
http://www.aanda.org/articles/aa/abs/2015/08/aa26549-15/aa26549-15.html
The beginning and end points of the disjoint, non-empty, half-open integer ranges in the set are stored in a std::vector<uint64_t>, with monotonically increasing values, except for the last one. Each pair of consecutive elements [begin, end) in the vector is a non-empty half-open range, where the value of end is defined as the integer obtained by adding one to the largest element in the range.
Mathematically, a half-open range with largest element equal to 2^64 - 1 would have an end point of 2^64. But arithmetic for unsigned 64 bit integers is modular, and adding 1 to 2^64 - 1 "wraps around" to 0. So in practice, ranges containing the largest uint64_t value have an end point of 0. Note that overflow is undefined for signed integers, which motivates the use of unsigned 64 bit integers for this class.
The first and last values of the internal vector are are always 0, even if no range in the set has a beginning or end point of 0. To illustrate why, consider the contents of the vector for a set containing a single integer, 3:
[0, 3, 4, 0]
The range obtained by extracting pairs of elements from the vector starting at index 1 is [3, 4), which corresponds to the contents of the set. The ranges obtained by starting at index 0 are [0, 3) and [4, 0). They correspond to the unsigned 64 bit integers not in the set.
The use of bookended half open ranges means that simply toggling the index of the first range between 0 and 1 corresponds to complementing the set. This allows many simplifications in the implementation - for example, set union and difference can be implemented in terms of set intersection and complement, since A ∪ B = ¬(¬A ∩ ¬B) and A ∖ B = A ∩ ¬B.
Many of the RangeSet methods accept ranges of integers [first, last) as input, either directly or in the form of a tuple. The values in a range are generated by starting with a value equal to first, and incrementing it until last is reached. If first == last, the range is full (it contains all possible uint64_t values), and if first > last, it wraps around - that is, it contains all uint64_t values except for [last, first).
The ranges in a set can be iterated over. Set modification may invalidate all iterators.
Definition at line 99 of file RangeSet.h.
Definition at line 178 of file RangeSet.h.
using lsst::sphgeom::RangeSet::difference_type = ptrdiff_t |
Definition at line 175 of file RangeSet.h.
using lsst::sphgeom::RangeSet::size_type = size_t |
Definition at line 176 of file RangeSet.h.
using lsst::sphgeom::RangeSet::value_type = std::tuple<uint64_t, uint64_t> |
Definition at line 177 of file RangeSet.h.
|
default |
|
default |
|
default |
The default constructor creates an empty set.
|
inlineexplicit |
This constructor creates a set containing the given integer(s) or integer range(s).
Definition at line 191 of file RangeSet.h.
|
inline |
This constructor creates a set containing the given integer(s) or integer range(s).
Definition at line 195 of file RangeSet.h.
|
inlineexplicit |
This constructor creates a set containing the given integer(s) or integer range(s).
Definition at line 205 of file RangeSet.h.
lsst::sphgeom::RangeSet::RangeSet | ( | std::initializer_list< uint64_t > | list | ) |
This constructor creates a set containing the given integer(s) or integer range(s).
Definition at line 94 of file RangeSet.cc.
lsst::sphgeom::RangeSet::RangeSet | ( | std::initializer_list< std::pair< uint64_t, uint64_t >> | list | ) |
This constructor creates a set containing the given integer(s) or integer range(s).
Definition at line 98 of file RangeSet.cc.
|
inline |
This generic constructor creates a set containing the integers or ranges obtained by dereferencing the iterators in [a, b).
It is hidden via SFINAE if InputIterator is not a standard input iterator.
Definition at line 235 of file RangeSet.h.
|
inlineexplicit |
This generic constructor creates a set containing the integers or integer ranges in the given container.
It is hidden via SFINAE if Container does not provide constant input iterators over its elements.
Definition at line 264 of file RangeSet.h.
|
inline |
This function returns a constant iterator to the first range in this set.
Definition at line 516 of file RangeSet.h.
|
inline |
beginc
returns a constant iterator to the first range in the complement of this set.
Definition at line 529 of file RangeSet.h.
uint64_t lsst::sphgeom::RangeSet::cardinality | ( | ) | const |
cardinality
returns the number of integers in this set.
Note that 0 is returned both for full and empty sets (a full set contains 2^64 integers, which is 0 modulo 2^64).
Definition at line 300 of file RangeSet.cc.
|
inline |
This function returns a constant iterator to the first range in this set.
Definition at line 517 of file RangeSet.h.
|
inline |
This function returns a constant iterator to the range after the last one in this set.
Definition at line 524 of file RangeSet.h.
|
inline |
clear
removes all integers from this set.
Definition at line 501 of file RangeSet.h.
|
inline |
complement
replaces this set S with U ∖ S, where U is the universe of range sets, [0, 2^64).
It runs in constant time.
Definition at line 328 of file RangeSet.h.
|
inline |
complemented
returns a complemented copy of this set.
Definition at line 331 of file RangeSet.h.
bool lsst::sphgeom::RangeSet::contains | ( | RangeSet const & | s | ) | const |
contains
returns true iff every one of the given integers is in this set.
Definition at line 280 of file RangeSet.cc.
bool lsst::sphgeom::RangeSet::contains | ( | uint64_t | first, |
uint64_t | last | ||
) | const |
contains
returns true iff every one of the given integers is in this set.
Definition at line 264 of file RangeSet.cc.
|
inline |
contains
returns true iff every one of the given integers is in this set.
Definition at line 435 of file RangeSet.h.
difference
returns the difference between this set and s.
Definition at line 157 of file RangeSet.cc.
|
inline |
empty
checks whether there are any integers in this set.
Definition at line 507 of file RangeSet.h.
|
inline |
This function returns a constant iterator to the range after the last one in this set.
Definition at line 523 of file RangeSet.h.
|
inline |
endc
returns a constant iterator to to the range after the last one in the complement of this set.
Definition at line 533 of file RangeSet.h.
|
inline |
erase
removes the given integers from this set.
The strong exception safety guarantee is provided.
Definition at line 316 of file RangeSet.h.
void lsst::sphgeom::RangeSet::erase | ( | uint64_t | first, |
uint64_t | last | ||
) |
erase
removes the given integers from this set.
The strong exception safety guarantee is provided.
Definition at line 121 of file RangeSet.cc.
|
inline |
erase
removes the given integers from this set.
The strong exception safety guarantee is provided.
Definition at line 306 of file RangeSet.h.
|
inline |
fill
adds all the unsigned 64 bit integers to this set.
Definition at line 504 of file RangeSet.h.
|
inline |
full
checks whether all integers in the universe of range sets, [0, 2^64), are in this set.
Definition at line 511 of file RangeSet.h.
|
inline |
insert
adds the given integer(s) to this set.
It is strongly exception safe, and runs in amortized constant time if the given integers extend or follow the last (largest) range in this set. Otherwise, the worst case run time is O(N), where N is the number of ranges in the set.
Definition at line 295 of file RangeSet.h.
void lsst::sphgeom::RangeSet::insert | ( | uint64_t | first, |
uint64_t | last | ||
) |
insert
adds the given integer(s) to this set.
It is strongly exception safe, and runs in amortized constant time if the given integers extend or follow the last (largest) range in this set. Otherwise, the worst case run time is O(N), where N is the number of ranges in the set.
Definition at line 104 of file RangeSet.cc.
|
inline |
insert
adds the given integer(s) to this set.
It is strongly exception safe, and runs in amortized constant time if the given integers extend or follow the last (largest) range in this set. Otherwise, the worst case run time is O(N), where N is the number of ranges in the set.
Definition at line 285 of file RangeSet.h.
bool lsst::sphgeom::RangeSet::intersects | ( | RangeSet const & | s | ) | const |
intersects
returns true iff the intersection of this set and the given integers is non-empty.
Definition at line 257 of file RangeSet.cc.
bool lsst::sphgeom::RangeSet::intersects | ( | uint64_t | first, |
uint64_t | last | ||
) | const |
intersects
returns true iff the intersection of this set and the given integers is non-empty.
Definition at line 241 of file RangeSet.cc.
|
inline |
intersects
returns true iff the intersection of this set and the given integers is non-empty.
Definition at line 425 of file RangeSet.h.
|
inline |
isDisjointFrom
returns true iff the intersection of this set and the given integers is empty.
Definition at line 461 of file RangeSet.h.
|
inline |
isDisjointFrom
returns true iff the intersection of this set and the given integers is empty.
Definition at line 457 of file RangeSet.h.
|
inline |
isDisjointFrom
returns true iff the intersection of this set and the given integers is empty.
Definition at line 455 of file RangeSet.h.
bool lsst::sphgeom::RangeSet::isValid | ( | ) | const |
isValid
checks that this RangeSet is in a valid state.
It is intended for use by unit tests, but calling it in other contexts is harmless. A return value of false means the RangeSet implementation isn't preserving its invariants, i.e. has a bug.
Definition at line 377 of file RangeSet.cc.
|
inline |
isWithin
returns true iff every integer in this set is also one of the given integers.
Definition at line 449 of file RangeSet.h.
bool lsst::sphgeom::RangeSet::isWithin | ( | uint64_t | first, |
uint64_t | last | ||
) | const |
isWithin
returns true iff every integer in this set is also one of the given integers.
Definition at line 287 of file RangeSet.cc.
|
inline |
isWithin
returns true iff every integer in this set is also one of the given integers.
Definition at line 445 of file RangeSet.h.
join
returns the union of this set and s.
Definition at line 145 of file RangeSet.cc.
|
inline |
max_size
returns the maximum number of ranges a set can hold.
Definition at line 536 of file RangeSet.h.
|
inline |
Two RangeSet instances are equal iff they contain the same integers.
Definition at line 273 of file RangeSet.h.
The & operator returns the intersection of this set and s.
Definition at line 358 of file RangeSet.h.
The &= operator assigns the intersection of this set and s to this set.
It is strongly exception safe.
Definition at line 379 of file RangeSet.h.
The - operator returns the difference between this set and s.
Definition at line 368 of file RangeSet.h.
The -= operator assigns the difference between this set and s to this set.
It is strongly exception safe.
Definition at line 399 of file RangeSet.h.
|
inline |
Two RangeSet instances are equal iff they contain the same integers.
Definition at line 269 of file RangeSet.h.
The ^ operator returns the symmetric difference between this set and s.
Definition at line 373 of file RangeSet.h.
The ^= operator assigns the symmetric difference between this set and s to this set.
It is strongly exception safe.
Definition at line 411 of file RangeSet.h.
The | operator returns the union of this set and s.
Definition at line 363 of file RangeSet.h.
The |= operator assigns the union of this set and s to this set.
It is strongly exception safe.
Definition at line 389 of file RangeSet.h.
|
inline |
The ~ operator returns the complement of this set.
Definition at line 351 of file RangeSet.h.
RangeSet & lsst::sphgeom::RangeSet::scale | ( | uint64_t | i | ) |
scale
multiplies the endpoints of each range in this set by the given integer.
Given ranges that correspond to pixel indexes in a hierarchical pixelization of the sphere like HTM or Q3C, scaling by 4 corresponds to increasing the subdivision level of the pixelization by 1.
Definition at line 354 of file RangeSet.cc.
|
inline |
scaled
returns a scaled copy of this set.
Definition at line 494 of file RangeSet.h.
|
inline |
simplified
returns a simplified copy of this set.
Definition at line 479 of file RangeSet.h.
RangeSet & lsst::sphgeom::RangeSet::simplify | ( | uint32_t | n | ) |
simplify
simplifies this range set by "coarsening" its ranges.
The result is defined as the union of the ranges obtained by rounding existing range beginnings down to the nearest multiple of 2^n, and rounding the ends up. Therefore, simplifying a range set always results in a superset of the original set.
This function replaces many small ranges with fewer coarser ranges. If the ranges correspond to pixels in a hierarchical pixelization of the sphere that overlap a region R, then this operation can be thought of as computing a lower resolution representation of the coverage of R.
Definition at line 308 of file RangeSet.cc.
|
inline |
|
inline |
symmetricDifference
returns the symmetric difference of this set and s.
Definition at line 166 of file RangeSet.cc.