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<std::uint64_t, std::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.
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).
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.
RangeSet &	simplify (std::uint32_t n)
	simplify simplifies this range set by "coarsening" its ranges.
RangeSet	simplified (std::uint32_t n) const
	simplified returns a simplified copy of this set.
RangeSet &	scale (std::uint64_t i)
	scale multiplies the endpoints of each range in this set by the given integer.
RangeSet	scaled (std::uint64_t i) const
	scaled returns a scaled copy of this set.
void	clear ()
	clear removes all integers from this set.
void	fill ()
	fill adds all the unsigned 64 bit integers to this set.
bool	empty () const
	empty checks whether there are any integers in this set.
bool	full () const
	full checks whether all integers in the universe of range sets, [0, 2^64), are in this set.
Iterator	beginc () const
	beginc returns a constant iterator to the first range in the complement of this set.
Iterator	endc () const
	endc returns a constant iterator to to the range after the last one in the complement of this set.
size_t	max_size () const
	max_size returns the maximum number of ranges a set can hold.
size_t	size () const
	size returns the number of ranges in this set.
std::uint64_t	cardinality () const
	cardinality returns the number of integers in this set.
void	swap (RangeSet &s)
bool	isValid () const
	isValid checks that this RangeSet is in a valid state.
	RangeSet (std::uint64_t u)
	RangeSet (std::uint64_t first, std::uint64_t last)
template<typename U , typename = typename std::enable_if< std::is_convertible<U, std::uint64_t>::value >::type>
	RangeSet (std::tuple< U, U > const &range)
	RangeSet (std::initializer_list< std::uint64_t >)
	RangeSet (std::initializer_list< std::pair< std::uint64_t, std::uint64_t > >)
bool	operator== (RangeSet const &rs) const
bool	operator!= (RangeSet const &rs) const
void	insert (std::uint64_t u)
template<typename U , typename = typename std::enable_if< std::is_convertible<U, std::uint64_t>::value >::type>
void	insert (std::tuple< U, U > const &range)
void	insert (std::uint64_t first, std::uint64_t last)
void	erase (std::uint64_t u)
template<typename U , typename = typename std::enable_if< std::is_convertible<U, std::uint64_t>::value >::type>
void	erase (std::tuple< U, U > const &range)
void	erase (std::uint64_t first, std::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).
RangeSet	complemented () const
	complemented returns a complemented copy of this set.
RangeSet	intersection (RangeSet const &s) const
	intersection returns the intersection of this set and s.
RangeSet	join (RangeSet const &s) const
	join returns the union of this set and s.
RangeSet	difference (RangeSet const &s) const
	difference returns the difference between this set and s.
RangeSet	symmetricDifference (RangeSet const &s) const
	symmetricDifference returns the symmetric difference of this set and s.
RangeSet	operator~ () const
	The ~ operator returns the complement of this set.
RangeSet	operator& (RangeSet const &s) const
	The & operator returns the intersection of this set and s.
RangeSet	operator| (RangeSet const &s) const
	The | operator returns the union of this set and s.
RangeSet	operator- (RangeSet const &s) const
	The - operator returns the difference between this set and s.
RangeSet	operator^ (RangeSet const &s) const
	The ^ operator returns the symmetric difference between this set and s.
RangeSet &	operator&= (RangeSet const &s)
	The &= operator assigns the intersection of this set and s to this set.
RangeSet &	operator|= (RangeSet const &s)
	The |= operator assigns the union of this set and s to this set.
RangeSet &	operator-= (RangeSet const &s)
	The -= operator assigns the difference between this set and s to this set.
RangeSet &	operator^= (RangeSet const &s)
	The ^= operator assigns the symmetric difference between this set and s to this set.
bool	intersects (std::uint64_t u) const
bool	intersects (std::uint64_t first, std::uint64_t last) const
bool	intersects (RangeSet const &s) const
bool	contains (std::uint64_t u) const
bool	contains (std::uint64_t first, std::uint64_t last) const
bool	contains (RangeSet const &s) const
bool	isWithin (std::uint64_t u) const
bool	isWithin (std::uint64_t first, std::uint64_t last) const
bool	isWithin (RangeSet const &s) const
bool	isDisjointFrom (std::uint64_t u) const
bool	isDisjointFrom (std::uint64_t first, std::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<std::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 std::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 std::uint64_t values), and if first > last, it wraps around - that is, it contains all std::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 106 of file RangeSet.h.

Member Typedef Documentation

const_iterator

using lsst::sphgeom::RangeSet::const_iterator = Iterator

Definition at line 185 of file RangeSet.h.

difference_type

using lsst::sphgeom::RangeSet::difference_type = ptrdiff_t

Definition at line 182 of file RangeSet.h.

size_type

using lsst::sphgeom::RangeSet::size_type = size_t

Definition at line 183 of file RangeSet.h.

value_type

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

Definition at line 184 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 ( std::uint64_t u )

inlineexplicit

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

Definition at line 198 of file RangeSet.h.

                                     {
        insert(u);
    }

RangeSet() [5/10]

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

inline

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

Definition at line 202 of file RangeSet.h.

                                                  {
        insert(first, last);
    }

RangeSet() [6/10]

template<typename U , typename = typename std::enable_if< std::is_convertible<U, std::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 212 of file RangeSet.h.

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

RangeSet() [7/10]

lsst::sphgeom::RangeSet::RangeSet

(

std::initializer_list< std::uint64_t >

list

)

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

Definition at line 101 of file RangeSet.cc.

                                                        :
    RangeSet(list.begin(), list.end())
{}

RangeSet() [8/10]

lsst::sphgeom::RangeSet::RangeSet

(

std::initializer_list< std::pair< std::uint64_t, std::uint64_t > >

list

)

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

Definition at line 105 of file RangeSet.cc.

                                                                              {
    for (auto t: list) {
        insert(std::get<0>(t), std::get<1>(t));
    }
}

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 242 of file RangeSet.h.

                                               {
        for (; a != b; ++a) {
            insert(*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 271 of file RangeSet.h.

                                           :
        RangeSet(std::begin(c), std::end(c)) {}

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 523 of file RangeSet.h.

{ return Iterator(_begin()); }

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 536 of file RangeSet.h.

{ return Iterator(_beginc()); }

cardinality()

std::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 307 of file RangeSet.cc.

                                        {
    std::uint64_t sz = 0;
    for (auto r = _begin(), e = _end(); r != e; r += 2) {
        sz += r[1] - r[0];
    }
    return sz;
}

cbegin()

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

inline

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

Definition at line 524 of file RangeSet.h.

{ return begin(); }

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 531 of file RangeSet.h.

{ return end(); }

clear()

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

inline

clear removes all integers from this set.

Definition at line 508 of file RangeSet.h.

{ _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 335 of file RangeSet.h.

{ _offset = !_offset; return *this; }

complemented()

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

inline

complemented returns a complemented copy of this set.

Definition at line 338 of file RangeSet.h.

                                  {
        RangeSet s(*this);
        s.complement();
        return s;
    }

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 287 of file RangeSet.cc.

                                                {
    if (s.empty() || full()) {
        return true;
    }
    return !_intersects(_beginc(), _endc(), s._begin(), s._end());
}

contains() [2/3]

bool lsst::sphgeom::RangeSet::contains	(	std::uint64_t	first,
		std::uint64_t	last ) const

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

Definition at line 271 of file RangeSet.cc.

                                                                 {
    if (full()) {
        return true;
    }
    if (first == last) {
        return false;
    }
    if (first <= last - 1) {
        std::uint64_t r[2] = {first, last};
        return !_intersectsOne(r, _beginc(), _endc());
    }
    std::uint64_t r[4] = {0, last, first, 0};
    return !_intersectsOne(r, _beginc(), _endc()) &&
           !_intersectsOne(r + 2, _beginc(), _endc());
}

contains() [3/3]

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

inline

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

Definition at line 442 of file RangeSet.h.

{ return contains(u, u + 1); }

difference()

RangeSet lsst::sphgeom::RangeSet::difference

(

RangeSet const &

s

)

const

difference returns the difference between this set and s.

Definition at line 164 of file RangeSet.cc.

                                                      {
    RangeSet result;
    if (this != &s) {
        // A ∖ B = A ∩ ¬B
        result._intersect(_begin(), _end(), s._beginc(), s._endc());
    }
    return result;
}

empty()

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

inline

empty checks whether there are any integers in this set.

Definition at line 514 of file RangeSet.h.

{ 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 530 of file RangeSet.h.

{ 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 540 of file RangeSet.h.

{ return Iterator(_endc()); }

erase() [1/3]

template<typename U , typename = typename std::enable_if< std::is_convertible<U, std::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 323 of file RangeSet.h.

                                             {
        erase(std::get<0>(range), std::get<1>(range));
    }

erase() [2/3]

void lsst::sphgeom::RangeSet::erase	(	std::uint64_t	first,
		std::uint64_t	last )

erase removes the given integers from this set.

The strong exception safety guarantee is provided.

Definition at line 128 of file RangeSet.cc.

                                                        {
    // To erase [first, last), insert it into the complement of this set,
    // then complement the result. The complements are performed in the
    // constructor and destructor of a local object, so that the second
    // complement is executed even if insert throws.
    struct Complementor {
        RangeSet & set;
        Complementor(RangeSet & s) : set(s) { set.complement(); }
        ~Complementor() { set.complement(); }
    };
    Complementor c(*this);
    insert(first, last);
}

erase() [3/3]

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

inline

erase removes the given integers from this set.

The strong exception safety guarantee is provided.

Definition at line 313 of file RangeSet.h.

                              {
        erase(u, u + 1);
    }

fill()

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

inline

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

Definition at line 511 of file RangeSet.h.

{ _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 518 of file RangeSet.h.

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

insert() [1/3]

template<typename U , typename = typename std::enable_if< std::is_convertible<U, std::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 302 of file RangeSet.h.

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

insert() [2/3]

void lsst::sphgeom::RangeSet::insert	(	std::uint64_t	first,
		std::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 111 of file RangeSet.cc.

                                                         {
    if (first == last) {
        fill();
    } else {
        // Ensure that there is enough space for 2 new values in _ranges.
        // Afterwards, none of the possible modifications of _ranges will throw,
        // so the strong exception safety guarantee is provided.
        _ranges.reserve(_ranges.size() + 2);
        if (first <= last - 1) {
            _insert(first, last);
        } else {
            _insert(0, last);
            _insert(first, 0);
        }
    }
}

insert() [3/3]

void lsst::sphgeom::RangeSet::insert ( std::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 292 of file RangeSet.h.

                               {
        insert(u, u + 1);
    }

intersection()

RangeSet lsst::sphgeom::RangeSet::intersection

(

RangeSet const &

s

)

const

intersection returns the intersection of this set and s.

Definition at line 142 of file RangeSet.cc.

                                                        {
    RangeSet result;
    if (this == &s) {
        result = s;
    } else {
        result._intersect(_begin(), _end(), s._begin(), s._end());
    }
    return result;
}

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 264 of file RangeSet.cc.

                                                  {
    if (empty() || s.empty()) {
        return false;
    }
    return _intersects(_begin(), _end(), s._begin(), s._end());
}

intersects() [2/3]

bool lsst::sphgeom::RangeSet::intersects	(	std::uint64_t	first,
		std::uint64_t	last ) const

intersects returns true iff the intersection of this set and the given integers is non-empty.

Definition at line 248 of file RangeSet.cc.

                                                                   {
    if (empty()) {
        return false;
    }
    if (first == last) {
        return true;
    }
    if (first <= last - 1) {
        std::uint64_t r[2] = {first, last};
        return _intersectsOne(r, _begin(), _end());
    }
    std::uint64_t r[4] = {0, last, first, 0};
    return _intersectsOne(r, _begin(), _end()) ||
           _intersectsOne(r + 2, _begin(), _end());
}

intersects() [3/3]

bool lsst::sphgeom::RangeSet::intersects ( std::uint64_t u ) const

inline

intersects returns true iff the intersection of this set and the given integers is non-empty.

Definition at line 432 of file RangeSet.h.

{ return intersects(u, u + 1); }

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 468 of file RangeSet.h.

{ return !intersects(s); }

isDisjointFrom() [2/3]

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

inline

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

Definition at line 464 of file RangeSet.h.

                                                                   {
        return !intersects(first, last);
    }

isDisjointFrom() [3/3]

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

inline

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

Definition at line 462 of file RangeSet.h.

{ 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 384 of file RangeSet.cc.

                             {
    // Bookends are mandatory.
    if (_ranges.size() < 2) {
        return false;
    }
    if (_ranges.front() != 0 || _ranges.back() != 0) {
        return false;
    }
    // Values except the last one must be monotonically increasing.
    for (auto i = _ranges.begin() + 1, e = _ranges.end() - 1; i != e; ++i) {
        if (i[0] <= i[-1]) {
            return false;
        }
    }
    return true;
}

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 456 of file RangeSet.h.

{ return s.contains(*this); }

isWithin() [2/3]

bool lsst::sphgeom::RangeSet::isWithin	(	std::uint64_t	first,
		std::uint64_t	last ) const

isWithin returns true iff every integer in this set is also one of the given integers.

Definition at line 294 of file RangeSet.cc.

                                                                 {
    if (empty() || first == last) {
        return true;
    }
    if (last <= first - 1) {
        std::uint64_t r[2] = {last, first};
        return !_intersectsOne(r, _begin(), _end());
    }
    std::uint64_t r[4] = {0, first, last, 0};
    return !_intersectsOne(r, _begin(), _end()) &&
           !_intersectsOne(r + 2, _begin(), _end());
}

isWithin() [3/3]

bool lsst::sphgeom::RangeSet::isWithin ( std::uint64_t u ) const

inline

isWithin returns true iff every integer in this set is also one of the given integers.

Definition at line 452 of file RangeSet.h.

{ return isWithin(u, u + 1); }

join()

RangeSet lsst::sphgeom::RangeSet::join

(

RangeSet const &

s

)

const

join returns the union of this set and s.

Definition at line 152 of file RangeSet.cc.

                                                {
    RangeSet result;
    if (this == &s) {
        result = s;
    } else {
        // A ∪ B = ¬(¬A ∩ ¬B)
        result._intersect(_beginc(), _endc(), s._beginc(), s._endc());
        result.complement();
    }
    return result;
}

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 543 of file RangeSet.h.

{ return _ranges.max_size() / 2; }

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 280 of file RangeSet.h.

                                               {
        return _offset != rs._offset || _ranges != rs._ranges;
    }

operator&()

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

inline

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

Definition at line 365 of file RangeSet.h.

                                                 {
        return intersection(s);
    }

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 386 of file RangeSet.h.

                                              {
        if (this != &s) {
            RangeSet r = intersection(s);
            swap(r);
        }
        return *this;
    }

operator-()

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

inline

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

Definition at line 375 of file RangeSet.h.

                                                 {
        return difference(s);
    }

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 406 of file RangeSet.h.

                                              {
        if (this != &s) {
            RangeSet r = difference(s);
            swap(r);
        } else {
            clear();
        }
        return *this;
    }

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 276 of file RangeSet.h.

                                               {
        return _offset == rs._offset && _ranges == rs._ranges;
    }

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 380 of file RangeSet.h.

                                                 {
        return symmetricDifference(s);
    }

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 418 of file RangeSet.h.

                                              {
        if (this != &s) {
            RangeSet r = symmetricDifference(s);
            swap(r);
        } else {
            clear();
        }
        return *this;
    }

operator|()

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

inline

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

Definition at line 370 of file RangeSet.h.

                                                 {
        return join(s);
    }

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 396 of file RangeSet.h.

                                              {
        if (this != &s) {
            RangeSet r = join(s);
            swap(r);
        }
        return *this;
    }

operator~()

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

inline

The ~ operator returns the complement of this set.

Definition at line 358 of file RangeSet.h.

                               {
        RangeSet s(*this);
        s.complement();
        return s;
    }

scale()

RangeSet & lsst::sphgeom::RangeSet::scale

(

std::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 361 of file RangeSet.cc.

                                        {
    if (empty() || i == 1) {
        return *this;
    } else if (i == 0) {
        clear();
        return *this;
    }
    std::uint64_t overflowThreshold = static_cast<std::uint64_t>(-1) / i;
    auto r = _ranges.begin();
    auto rend = _ranges.end();
    for (; r < rend; ++r) {
        std::uint64_t value = *r;
        if (value > overflowThreshold) {
            *r = 0;
            ++r;
            break;
        }
        *r = value * i;
    }
    _ranges.erase(r, rend);
    return *this;
}

scaled()

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

inline

scaled returns a scaled copy of this set.

Definition at line 501 of file RangeSet.h.

                                         {
        RangeSet rs(*this);
        rs.scale(i);
        return rs;
    }

simplified()

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

inline

simplified returns a simplified copy of this set.

Definition at line 486 of file RangeSet.h.

                                             {
        RangeSet rs(*this);
        rs.simplify(n);
        return rs;
    }

simplify()

RangeSet & lsst::sphgeom::RangeSet::simplify

(

std::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 315 of file RangeSet.cc.

                                           {
    if (empty() || n == 0) {
        return *this;
    } else if (n >= 64) {
        fill();
        return *this;
    }
    // Compute m, the integer with n LSBs set to 1. Then, (x & ~m) is x
    // rounded down to the nearest multiple of 2^n, and (x + m) & ~m is
    // x rounded up to the nearest multiple of 2^n.
    std::uint64_t const m = (static_cast<std::uint64_t>(1) << n) - 1;
    std::uint64_t * r = const_cast<std::uint64_t *>(_begin());
    std::uint64_t * rend = const_cast<std::uint64_t *>(_end());
    std::uint64_t * out = r;
    // Expand the first range.
    std::uint64_t first = r[0] & ~m;
    std::uint64_t last = (r[1] + m) & ~m;
    if (r[0] != 0 && first == 0) {
        // The expanded first range now contains the leading bookend.
        _offset = false;
        --out;
    }
    out[0] = first;
    out[1] = last;
    // Expand the remaining ranges.
    for (r += 2; last != 0 && r != rend; r += 2) {
        std::uint64_t u = r[0] & ~m;
        std::uint64_t v = (r[1] + m) & ~m;
        if (u > last) {
            out += 2;
            out[0] = u;
        }
        out[1] = v;
        last = v;
    }
    out += 2;
    if (last != 0) {
        // Append a trailing bookend if necessary.
        *out = 0;
        ++out;
    }
    // Erase everything after the location of the new trailing bookend.
    _ranges.erase(_ranges.begin() + (out  - _ranges.data()), _ranges.end());
    return *this;
}

size()

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

inline

size returns the number of ranges in this set.

Definition at line 546 of file RangeSet.h.

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

swap()

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

inline

Definition at line 554 of file RangeSet.h.

                            {
        using std::swap;
        swap(_ranges, s._ranges);
        swap(_offset, s._offset);
    }

symmetricDifference()

RangeSet lsst::sphgeom::RangeSet::symmetricDifference

(

RangeSet const &

s

)

const

symmetricDifference returns the symmetric difference of this set and s.

Definition at line 173 of file RangeSet.cc.

                                                               {
    RangeSet result;
    if (this != &s) {
        if (empty()) {
            result = s;
        } else if (s.empty()) {
            result = *this;
        } else {
            // Sweep through the beginning and end points of the ranges from
            // sets A and B in ascending order.
            //
            // Passing through the beginning of a range toggles the
            // corresponding state (astate or bstate) from 0 to 1, and passing
            // through the end toggles it from 1 to 0. The XOR of astate and
            // bstate determines whether or not the current position of the
            // sweep is inside the symmetric set difference of A and B.
            //
            // Merging the sorted lists of ranges from each set is complicated
            // by trailing zero bookends. These compare less than or equal to
            // all other values, even though logically they are greater than
            // them all.
            //
            // To handle this, leading zero bookends are dealt with outside of
            // the main loop. Then, 1 is subtracted from all other values prior
            // to comparison, yielding the proper ordering (since subtracting
            // 1 from a trailing zero bookend results in 2^64 - 1).
            std::uint64_t const * a = _begin();
            std::uint64_t const * aend = _end();
            std::uint64_t const * b = s._begin();
            std::uint64_t const * bend = s._end();
            int astate = (*a == 0);
            int bstate = (*b == 0);
            a += astate;
            b += bstate;
            // state is 0 if the next value to output is the beginning
            // of a range, and 1 otherwise.
            int state = astate ^ bstate;
            // Start with a vector containing just the leading bookend.
            result._ranges = {0};
            // If 0 is contained in exactly one of the two sets, it is
            // in their symmetric difference.
            result._offset = (state == 0);
            // Merge lists until one or both are exhausted.
            while (a != aend && b != bend) {
                std::uint64_t av = *a - 1;
                std::uint64_t bv = *b - 1;
                // The pointer(s) yielding the minimal value will be
                // incremented.
                bool ainc = (av <= bv);
                bool binc = (bv <= av);
                std::uint64_t minval = ainc ? av : bv;
                astate ^= ainc;
                bstate ^= binc;
                // Output the minimum value if the output state changes.
                if (state != (astate ^ bstate)) {
                    result._ranges.push_back(minval + 1);
                    state ^= 1;
                }
                a += ainc;
                b += binc;
            }
            // The sweep has exhausted at least one list. Each remaining
            // beginning and end point in the other list will toggle the
            // output state, so they can simply be appended to the result.
            result._ranges.insert(result._ranges.end(), a, aend);
            result._ranges.insert(result._ranges.end(), b, bend);
            // Append a trailing bookend if necessary.
            if ((aend[-1] == 0) == (bend[-1] == 0)) {
                result._ranges.push_back(0);
            }
        }
    }
    return result;
}

---

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

• /j/snowflake/release/lsstsw/stack/lsst-scipipe-9.0.0/Linux64/sphgeom/g781aacb6e4+a8ce1bb630/include/lsst/sphgeom/RangeSet.h
• /j/snowflake/release/lsstsw/stack/lsst-scipipe-9.0.0/Linux64/sphgeom/g781aacb6e4+a8ce1bb630/src/RangeSet.cc