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
Classes | Public Types | Public Member Functions | List of all members
lsst::sphgeom::RangeSet Class Reference

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
 
RangeSetoperator= (RangeSet const &)=default
 
RangeSetoperator= (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...
 
RangeSetsimplify (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...
 
RangeSetscale (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
RangeSetcomplement ()
 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...
 
RangeSetoperator&= (RangeSet const &s)
 The &= operator assigns the intersection of this set and s to this set. More...
 
RangeSetoperator|= (RangeSet const &s)
 The |= operator assigns the union of this set and s to this set. More...
 
RangeSetoperator-= (RangeSet const &s)
 The -= operator assigns the difference between this set and s to this set. More...
 
RangeSetoperator^= (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
 

Detailed Description

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.

Member Typedef Documentation

◆ const_iterator

Definition at line 178 of file RangeSet.h.

◆ difference_type

Definition at line 175 of file RangeSet.h.

◆ size_type

Definition at line 176 of file RangeSet.h.

◆ value_type

using lsst::sphgeom::RangeSet::value_type = std::tuple<uint64_t, uint64_t>

Definition at line 177 of file RangeSet.h.

Constructor & Destructor Documentation

◆ RangeSet() [1/10]

lsst::sphgeom::RangeSet::RangeSet ( RangeSet const &  )
default

◆ RangeSet() [2/10]

lsst::sphgeom::RangeSet::RangeSet ( RangeSet &&  )
default

◆ RangeSet() [3/10]

lsst::sphgeom::RangeSet::RangeSet ( )
default

The default constructor creates an empty set.

◆ RangeSet() [4/10]

lsst::sphgeom::RangeSet::RangeSet ( uint64_t  u)
inlineexplicit

This constructor creates a set containing the given integer(s) or integer range(s).

Definition at line 191 of file RangeSet.h.

191  {
192  insert(u);
193  }
void insert(uint64_t u)
Definition: RangeSet.h:285

◆ RangeSet() [5/10]

lsst::sphgeom::RangeSet::RangeSet ( uint64_t  first,
uint64_t  last 
)
inline

This constructor creates a set containing the given integer(s) or integer range(s).

Definition at line 195 of file RangeSet.h.

195  {
196  insert(first, last);
197  }

◆ RangeSet() [6/10]

template<typename U , typename = typename std::enable_if< std::is_convertible<U, uint64_t>::value >::type>
lsst::sphgeom::RangeSet::RangeSet ( std::tuple< U, U > const &  range)
inlineexplicit

This constructor creates a set containing the given integer(s) or integer range(s).

Definition at line 205 of file RangeSet.h.

205  {
206  insert(static_cast<uint64_t>(std::get<0>(range)),
207  static_cast<uint64_t>(std::get<1>(range)));
208  }

◆ RangeSet() [7/10]

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.

94  :
95  RangeSet(list.begin(), list.end())
96 {}
RangeSet()=default
The default constructor creates an empty set.
daf::base::PropertyList * list
Definition: fits.cc:913

◆ RangeSet() [8/10]

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.

98  {
99  for (auto t: list) {
100  insert(std::get<0>(t), std::get<1>(t));
101  }
102 }

◆ RangeSet() [9/10]

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>
lsst::sphgeom::RangeSet::RangeSet ( InputIterator  a,
InputIterator  b 
)
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.

235  {
236  for (; a != b; ++a) {
237  insert(*a);
238  }
239  }
table::Key< int > b
table::Key< int > a

◆ RangeSet() [10/10]

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 >
lsst::sphgeom::RangeSet::RangeSet ( Container const &  c)
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.

264  :
265  RangeSet(std::begin(c), std::end(c)) {}
T begin(T... args)
T end(T... args)

Member Function Documentation

◆ begin()

Iterator lsst::sphgeom::RangeSet::begin ( ) const
inline

This function returns a constant iterator to the first range in this set.

Definition at line 516 of file RangeSet.h.

516 { return Iterator(_begin()); }
FastFinder::Iterator Iterator
Definition: FastFinder.cc:178

◆ beginc()

Iterator lsst::sphgeom::RangeSet::beginc ( ) const
inline

beginc returns a constant iterator to the first range in the complement of this set.

Definition at line 529 of file RangeSet.h.

529 { return Iterator(_beginc()); }

◆ cardinality()

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.

300  {
301  uint64_t sz = 0;
302  for (auto r = _begin(), e = _end(); r != e; r += 2) {
303  sz += r[1] - r[0];
304  }
305  return sz;
306 }

◆ cbegin()

Iterator lsst::sphgeom::RangeSet::cbegin ( ) const
inline

This function returns a constant iterator to the first range in this set.

Definition at line 517 of file RangeSet.h.

517 { return begin(); }
Iterator begin() const
Definition: RangeSet.h:516

◆ cend()

Iterator lsst::sphgeom::RangeSet::cend ( ) const
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.

524 { return end(); }
Iterator end() const
Definition: RangeSet.h:523

◆ clear()

void lsst::sphgeom::RangeSet::clear ( )
inline

clear removes all integers from this set.

Definition at line 501 of file RangeSet.h.

501 { _ranges = {0, 0}; _offset = true; }

◆ complement()

RangeSet& lsst::sphgeom::RangeSet::complement ( )
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.

328 { _offset = !_offset; return *this; }

◆ complemented()

RangeSet lsst::sphgeom::RangeSet::complemented ( ) const
inline

complemented returns a complemented copy of this set.

Definition at line 331 of file RangeSet.h.

331  {
332  RangeSet s(*this);
333  s.complement();
334  return s;
335  }

◆ contains() [1/3]

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.

280  {
281  if (s.empty() || full()) {
282  return true;
283  }
284  return !_intersects(_beginc(), _endc(), s._begin(), s._end());
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

◆ contains() [2/3]

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.

264  {
265  if (full()) {
266  return true;
267  }
268  if (first == last) {
269  return false;
270  }
271  if (first <= last - 1) {
272  uint64_t r[2] = {first, last};
273  return !_intersectsOne(r, _beginc(), _endc());
274  }
275  uint64_t r[4] = {0, last, first, 0};
276  return !_intersectsOne(r, _beginc(), _endc()) &&
277  !_intersectsOne(r + 2, _beginc(), _endc());
278 }

◆ contains() [3/3]

bool lsst::sphgeom::RangeSet::contains ( uint64_t  u) const
inline

contains returns true iff every one of the given integers is in this set.

Definition at line 435 of file RangeSet.h.

435 { return contains(u, u + 1); }
bool contains(uint64_t u) const
Definition: RangeSet.h:435

◆ difference()

RangeSet lsst::sphgeom::RangeSet::difference ( RangeSet const &  s) const

difference returns the difference between this set and s.

Definition at line 157 of file RangeSet.cc.

157  {
159  if (this != &s) {
160  // A ∖ B = A ∩ ¬B
161  result._intersect(_begin(), _end(), s._beginc(), s._endc());
162  }
163  return result;
164 }
py::object result
Definition: _schema.cc:429

◆ empty()

bool lsst::sphgeom::RangeSet::empty ( ) const
inline

empty checks whether there are any integers in this set.

Definition at line 507 of file RangeSet.h.

507 { return _begin() == _end(); }

◆ end()

Iterator lsst::sphgeom::RangeSet::end ( ) const
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.

523 { return Iterator(_end()); }

◆ endc()

Iterator lsst::sphgeom::RangeSet::endc ( ) const
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.

533 { return Iterator(_endc()); }

◆ erase() [1/3]

template<typename U , typename = typename std::enable_if< std::is_convertible<U, uint64_t>::value >::type>
void lsst::sphgeom::RangeSet::erase ( std::tuple< U, U > const &  range)
inline

erase removes the given integers from this set.

The strong exception safety guarantee is provided.

Definition at line 316 of file RangeSet.h.

316  {
317  erase(std::get<0>(range), std::get<1>(range));
318  }
void erase(uint64_t u)
Definition: RangeSet.h:306

◆ erase() [2/3]

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.

121  {
122  // To erase [first, last), insert it into the complement of this set,
123  // then complement the result. The complements are performed in the
124  // constructor and destructor of a local object, so that the second
125  // complement is executed even if insert throws.
126  struct Complementor {
127  RangeSet & set;
128  Complementor(RangeSet & s) : set(s) { set.complement(); }
129  ~Complementor() { set.complement(); }
130  };
131  Complementor c(*this);
132  insert(first, last);
133 }
daf::base::PropertySet * set
Definition: fits.cc:912

◆ erase() [3/3]

void lsst::sphgeom::RangeSet::erase ( uint64_t  u)
inline

erase removes the given integers from this set.

The strong exception safety guarantee is provided.

Definition at line 306 of file RangeSet.h.

306  {
307  erase(u, u + 1);
308  }

◆ fill()

void lsst::sphgeom::RangeSet::fill ( )
inline

fill adds all the unsigned 64 bit integers to this set.

Definition at line 504 of file RangeSet.h.

504 { _ranges = {0, 0}; _offset = false; }

◆ full()

bool lsst::sphgeom::RangeSet::full ( ) const
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.

511 { return _beginc() == _endc(); }

◆ insert() [1/3]

template<typename U , typename = typename std::enable_if< std::is_convertible<U, uint64_t>::value >::type>
void lsst::sphgeom::RangeSet::insert ( std::tuple< U, U > const &  range)
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.

295  {
296  insert(std::get<0>(range), std::get<1>(range));
297  }

◆ insert() [2/3]

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.

104  {
105  if (first == last) {
106  fill();
107  } else {
108  // Ensure that there is enough space for 2 new values in _ranges.
109  // Afterwards, none of the possible modifications of _ranges will throw,
110  // so the strong exception safety guarantee is provided.
111  _ranges.reserve(_ranges.size() + 2);
112  if (first <= last - 1) {
113  _insert(first, last);
114  } else {
115  _insert(0, last);
116  _insert(first, 0);
117  }
118  }
119 }
void fill()
fill adds all the unsigned 64 bit integers to this set.
Definition: RangeSet.h:504
T reserve(T... args)
T size(T... args)

◆ insert() [3/3]

void lsst::sphgeom::RangeSet::insert ( uint64_t  u)
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.

285  {
286  insert(u, u + 1);
287  }

◆ intersection()

RangeSet lsst::sphgeom::RangeSet::intersection ( RangeSet const &  s) const

intersection returns the intersection of this set and s.

Definition at line 135 of file RangeSet.cc.

135  {
137  if (this == &s) {
138  result = s;
139  } else {
140  result._intersect(_begin(), _end(), s._begin(), s._end());
141  }
142  return result;
143 }

◆ intersects() [1/3]

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.

257  {
258  if (empty() || s.empty()) {
259  return false;
260  }
261  return _intersects(_begin(), _end(), s._begin(), s._end());
262 }
bool empty() const
empty checks whether there are any integers in this set.
Definition: RangeSet.h:507

◆ intersects() [2/3]

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.

241  {
242  if (empty()) {
243  return false;
244  }
245  if (first == last) {
246  return true;
247  }
248  if (first <= last - 1) {
249  uint64_t r[2] = {first, last};
250  return _intersectsOne(r, _begin(), _end());
251  }
252  uint64_t r[4] = {0, last, first, 0};
253  return _intersectsOne(r, _begin(), _end()) ||
254  _intersectsOne(r + 2, _begin(), _end());
255 }

◆ intersects() [3/3]

bool lsst::sphgeom::RangeSet::intersects ( uint64_t  u) const
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.

425 { return intersects(u, u + 1); }
bool intersects(uint64_t u) const
Definition: RangeSet.h:425

◆ isDisjointFrom() [1/3]

bool lsst::sphgeom::RangeSet::isDisjointFrom ( RangeSet const &  s) const
inline

isDisjointFrom returns true iff the intersection of this set and the given integers is empty.

Definition at line 461 of file RangeSet.h.

461 { return !intersects(s); }

◆ isDisjointFrom() [2/3]

bool lsst::sphgeom::RangeSet::isDisjointFrom ( uint64_t  first,
uint64_t  last 
) const
inline

isDisjointFrom returns true iff the intersection of this set and the given integers is empty.

Definition at line 457 of file RangeSet.h.

457  {
458  return !intersects(first, last);
459  }

◆ isDisjointFrom() [3/3]

bool lsst::sphgeom::RangeSet::isDisjointFrom ( uint64_t  u) const
inline

isDisjointFrom returns true iff the intersection of this set and the given integers is empty.

Definition at line 455 of file RangeSet.h.

455 { return !intersects(u); }

◆ isValid()

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.

377  {
378  // Bookends are mandatory.
379  if (_ranges.size() < 2) {
380  return false;
381  }
382  if (_ranges.front() != 0 || _ranges.back() != 0) {
383  return false;
384  }
385  // Values except the last one must be monotonically increasing.
386  for (auto i = _ranges.begin() + 1, e = _ranges.end() - 1; i != e; ++i) {
387  if (i[0] <= i[-1]) {
388  return false;
389  }
390  }
391  return true;
392 }
T back(T... args)
T front(T... args)

◆ isWithin() [1/3]

bool lsst::sphgeom::RangeSet::isWithin ( RangeSet const &  s) const
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.

449 { return s.contains(*this); }

◆ isWithin() [2/3]

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.

287  {
288  if (empty() || first == last) {
289  return true;
290  }
291  if (last <= first - 1) {
292  uint64_t r[2] = {last, first};
293  return !_intersectsOne(r, _begin(), _end());
294  }
295  uint64_t r[4] = {0, first, last, 0};
296  return !_intersectsOne(r, _begin(), _end()) &&
297  !_intersectsOne(r + 2, _begin(), _end());
298 }

◆ isWithin() [3/3]

bool lsst::sphgeom::RangeSet::isWithin ( uint64_t  u) const
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.

445 { return isWithin(u, u + 1); }
bool isWithin(uint64_t u) const
Definition: RangeSet.h:445

◆ join()

RangeSet lsst::sphgeom::RangeSet::join ( RangeSet const &  s) const

join returns the union of this set and s.

Definition at line 145 of file RangeSet.cc.

145  {
147  if (this == &s) {
148  result = s;
149  } else {
150  // A ∪ B = ¬(¬A ∩ ¬B)
151  result._intersect(_beginc(), _endc(), s._beginc(), s._endc());
152  result.complement();
153  }
154  return result;
155 }

◆ max_size()

size_t lsst::sphgeom::RangeSet::max_size ( ) const
inline

max_size returns the maximum number of ranges a set can hold.

Definition at line 536 of file RangeSet.h.

536 { return _ranges.max_size() / 2; }
T max_size(T... args)

◆ operator!=()

bool lsst::sphgeom::RangeSet::operator!= ( RangeSet const &  rs) const
inline

Two RangeSet instances are equal iff they contain the same integers.

Definition at line 273 of file RangeSet.h.

273  {
274  return _offset != rs._offset || _ranges != rs._ranges;
275  }

◆ operator&()

RangeSet lsst::sphgeom::RangeSet::operator& ( RangeSet const &  s) const
inline

The & operator returns the intersection of this set and s.

Definition at line 358 of file RangeSet.h.

358  {
359  return intersection(s);
360  }
RangeSet intersection(RangeSet const &s) const
intersection returns the intersection of this set and s.
Definition: RangeSet.cc:135

◆ operator&=()

RangeSet& lsst::sphgeom::RangeSet::operator&= ( RangeSet const &  s)
inline

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.

379  {
380  if (this != &s) {
381  RangeSet r = intersection(s);
382  swap(r);
383  }
384  return *this;
385  }
void swap(RangeSet &s)
Definition: RangeSet.h:547

◆ operator-()

RangeSet lsst::sphgeom::RangeSet::operator- ( RangeSet const &  s) const
inline

The - operator returns the difference between this set and s.

Definition at line 368 of file RangeSet.h.

368  {
369  return difference(s);
370  }
RangeSet difference(RangeSet const &s) const
difference returns the difference between this set and s.
Definition: RangeSet.cc:157

◆ operator-=()

RangeSet& lsst::sphgeom::RangeSet::operator-= ( RangeSet const &  s)
inline

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.

399  {
400  if (this != &s) {
401  RangeSet r = difference(s);
402  swap(r);
403  } else {
404  clear();
405  }
406  return *this;
407  }
void clear()
clear removes all integers from this set.
Definition: RangeSet.h:501

◆ operator=() [1/2]

RangeSet& lsst::sphgeom::RangeSet::operator= ( RangeSet &&  )
default

◆ operator=() [2/2]

RangeSet& lsst::sphgeom::RangeSet::operator= ( RangeSet const &  )
default

◆ operator==()

bool lsst::sphgeom::RangeSet::operator== ( RangeSet const &  rs) const
inline

Two RangeSet instances are equal iff they contain the same integers.

Definition at line 269 of file RangeSet.h.

269  {
270  return _offset == rs._offset && _ranges == rs._ranges;
271  }

◆ operator^()

RangeSet lsst::sphgeom::RangeSet::operator^ ( RangeSet const &  s) const
inline

The ^ operator returns the symmetric difference between this set and s.

Definition at line 373 of file RangeSet.h.

373  {
374  return symmetricDifference(s);
375  }
RangeSet symmetricDifference(RangeSet const &s) const
symmetricDifference returns the symmetric difference of this set and s.
Definition: RangeSet.cc:166

◆ operator^=()

RangeSet& lsst::sphgeom::RangeSet::operator^= ( RangeSet const &  s)
inline

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.

411  {
412  if (this != &s) {
414  swap(r);
415  } else {
416  clear();
417  }
418  return *this;
419  }

◆ operator|()

RangeSet lsst::sphgeom::RangeSet::operator| ( RangeSet const &  s) const
inline

The | operator returns the union of this set and s.

Definition at line 363 of file RangeSet.h.

363  {
364  return join(s);
365  }
RangeSet join(RangeSet const &s) const
join returns the union of this set and s.
Definition: RangeSet.cc:145

◆ operator|=()

RangeSet& lsst::sphgeom::RangeSet::operator|= ( RangeSet const &  s)
inline

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.

389  {
390  if (this != &s) {
391  RangeSet r = join(s);
392  swap(r);
393  }
394  return *this;
395  }

◆ operator~()

RangeSet lsst::sphgeom::RangeSet::operator~ ( ) const
inline

The ~ operator returns the complement of this set.

Definition at line 351 of file RangeSet.h.

351  {
352  RangeSet s(*this);
353  s.complement();
354  return s;
355  }

◆ scale()

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.

354  {
355  if (empty() || i == 1) {
356  return *this;
357  } else if (i == 0) {
358  clear();
359  return *this;
360  }
361  uint64_t overflowThreshold = static_cast<uint64_t>(-1) / i;
362  auto r = _ranges.begin();
363  auto rend = _ranges.end();
364  for (; r < rend; ++r) {
365  uint64_t value = *r;
366  if (value > overflowThreshold) {
367  *r = 0;
368  ++r;
369  break;
370  }
371  *r = value * i;
372  }
373  _ranges.erase(r, rend);
374  return *this;
375 }
T erase(T... args)

◆ scaled()

RangeSet lsst::sphgeom::RangeSet::scaled ( uint64_t  i) const
inline

scaled returns a scaled copy of this set.

Definition at line 494 of file RangeSet.h.

494  {
495  RangeSet rs(*this);
496  rs.scale(i);
497  return rs;
498  }

◆ simplified()

RangeSet lsst::sphgeom::RangeSet::simplified ( uint32_t  n) const
inline

simplified returns a simplified copy of this set.

Definition at line 479 of file RangeSet.h.

479  {
480  RangeSet rs(*this);
481  rs.simplify(n);
482  return rs;
483  }

◆ simplify()

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.

308  {
309  if (empty() || n == 0) {
310  return *this;
311  } else if (n >= 64) {
312  fill();
313  return *this;
314  }
315  // Compute m, the integer with n LSBs set to 1. Then, (x & ~m) is x
316  // rounded down to the nearest multiple of 2^n, and (x + m) & ~m is
317  // x rounded up to the nearest multiple of 2^n.
318  uint64_t const m = (static_cast<uint64_t>(1) << n) - 1;
319  uint64_t * r = const_cast<uint64_t *>(_begin());
320  uint64_t * rend = const_cast<uint64_t *>(_end());
321  uint64_t * out = r;
322  // Expand the first range.
323  uint64_t first = r[0] & ~m;
324  uint64_t last = (r[1] + m) & ~m;
325  if (r[0] != 0 && first == 0) {
326  // The expanded first range now contains the leading bookend.
327  _offset = false;
328  --out;
329  }
330  out[0] = first;
331  out[1] = last;
332  // Expand the remaining ranges.
333  for (r += 2; last != 0 && r != rend; r += 2) {
334  uint64_t u = r[0] & ~m;
335  uint64_t v = (r[1] + m) & ~m;
336  if (u > last) {
337  out += 2;
338  out[0] = u;
339  }
340  out[1] = v;
341  last = v;
342  }
343  out += 2;
344  if (last != 0) {
345  // Append a trailing bookend if necessary.
346  *out = 0;
347  ++out;
348  }
349  // Erase everything after the location of the new trailing bookend.
350  _ranges.erase(_ranges.begin() + (out - _ranges.data()), _ranges.end());
351  return *this;
352 }
int m
Definition: SpanSet.cc:48
T data(T... args)

◆ size()

size_t lsst::sphgeom::RangeSet::size ( ) const
inline

size returns the number of ranges in this set.

Definition at line 539 of file RangeSet.h.

539 { return (_ranges.size() - _offset) / 2; }

◆ swap()

void lsst::sphgeom::RangeSet::swap ( RangeSet s)
inline

Definition at line 547 of file RangeSet.h.

547  {
548  using std::swap;
549  swap(_ranges, s._ranges);
550  swap(_offset, s._offset);
551  }
T swap(T... args)

◆ symmetricDifference()

RangeSet lsst::sphgeom::RangeSet::symmetricDifference ( RangeSet const &  s) const

symmetricDifference returns the symmetric difference of this set and s.

Definition at line 166 of file RangeSet.cc.

166  {
168  if (this != &s) {
169  if (empty()) {
170  result = s;
171  } else if (s.empty()) {
172  result = *this;
173  } else {
174  // Sweep through the beginning and end points of the ranges from
175  // sets A and B in ascending order.
176  //
177  // Passing through the beginning of a range toggles the
178  // corresponding state (astate or bstate) from 0 to 1, and passing
179  // through the end toggles it from 1 to 0. The XOR of astate and
180  // bstate determines whether or not the current position of the
181  // sweep is inside the symmetric set difference of A and B.
182  //
183  // Merging the sorted lists of ranges from each set is complicated
184  // by trailing zero bookends. These compare less than or equal to
185  // all other values, even though logically they are greater than
186  // them all.
187  //
188  // To handle this, leading zero bookends are dealt with outside of
189  // the main loop. Then, 1 is subtracted from all other values prior
190  // to comparison, yielding the proper ordering (since subtracting
191  // 1 from a trailing zero bookend results in 2^64 - 1).
192  uint64_t const * a = _begin();
193  uint64_t const * aend = _end();
194  uint64_t const * b = s._begin();
195  uint64_t const * bend = s._end();
196  int astate = (*a == 0);
197  int bstate = (*b == 0);
198  a += astate;
199  b += bstate;
200  // state is 0 if the next value to output is the beginning
201  // of a range, and 1 otherwise.
202  int state = astate ^ bstate;
203  // Start with a vector containing just the leading bookend.
204  result._ranges = {0};
205  // If 0 is contained in exactly one of the two sets, it is
206  // in their symmetric difference.
207  result._offset = (state == 0);
208  // Merge lists until one or both are exhausted.
209  while (a != aend && b != bend) {
210  uint64_t av = *a - 1;
211  uint64_t bv = *b - 1;
212  // The pointer(s) yielding the minimal value will be
213  // incremented.
214  bool ainc = (av <= bv);
215  bool binc = (bv <= av);
216  uint64_t minval = ainc ? av : bv;
217  astate ^= ainc;
218  bstate ^= binc;
219  // Output the minimum value if the output state changes.
220  if (state != (astate ^ bstate)) {
221  result._ranges.push_back(minval + 1);
222  state ^= 1;
223  }
224  a += ainc;
225  b += binc;
226  }
227  // The sweep has exhausted at least one list. Each remaining
228  // beginning and end point in the other list will toggle the
229  // output state, so they can simply be appended to the result.
230  result._ranges.insert(result._ranges.end(), a, aend);
231  result._ranges.insert(result._ranges.end(), b, bend);
232  // Append a trailing bookend if necessary.
233  if ((aend[-1] == 0) == (bend[-1] == 0)) {
234  result._ranges.push_back(0);
235  }
236  }
237  }
238  return result;
239 }

The documentation for this class was generated from the following files: