RangeSet.h

Go to the documentation of this file.

/*
 * This file is part of sphgeom.
 *
 * Developed for the LSST Data Management System.
 * This product includes software developed by the LSST Project
 * (http://www.lsst.org).
 * See the COPYRIGHT file at the top-level directory of this distribution
 * for details of code ownership.
 *
 * This software is dual licensed under the GNU General Public License and also
 * under a 3-clause BSD license. Recipients may choose which of these licenses
 * to use; please see the files gpl-3.0.txt and/or bsd_license.txt,
 * respectively.  If you choose the GPL option then the following text applies
 * (but note that there is still no warranty even if you opt for BSD instead):
 *
 * This program is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program.  If not, see <http://www.gnu.org/licenses/>.
 */
 
#ifndef LSST_SPHGEOM_RANGESET_H_
#define LSST_SPHGEOM_RANGESET_H_

 
#include <cstddef>
#include <cstdint>
#include <initializer_list>
#include <iosfwd>
#include <iterator>
#include <tuple>
#include <type_traits>
#include <vector>
 
 
namespace lsst {
namespace sphgeom {

class RangeSet {
public:

    struct Iterator {
        // For std::iterator_traits
        using difference_type = ptrdiff_t;
        using value_type = std::tuple<std::uint64_t, std::uint64_t>;
        using pointer = void;
        using reference = std::tuple<std::uint64_t, std::uint64_t>;
        using iterator_category = std::input_iterator_tag;
 
        Iterator() = default;
        explicit Iterator(std::uint64_t const * ptr) : p{ptr} {}
 
        friend void swap(Iterator & a, Iterator & b) {
            std::swap(a.p, b.p);
        }
 
        // Arithmetic
        Iterator & operator++() { p += 2; return *this; }
        Iterator & operator--() { p -= 2; return *this; }
 
        Iterator operator++(int) { Iterator i(*this); p += 2; return i; }
        Iterator operator--(int) { Iterator i(*this); p -= 2; return i; }
 
        Iterator operator+(ptrdiff_t n) const { return Iterator(p + 2 * n); }
        Iterator operator-(ptrdiff_t n) const { return Iterator(p + 2 * n); }
 
        Iterator & operator+=(ptrdiff_t n) { p += 2 * n; return *this; }
        Iterator & operator-=(ptrdiff_t n) { p -= 2 * n; return *this; }
 
        friend Iterator operator+(ptrdiff_t n, Iterator const & i) {
            return i + n;
        }
 
        ptrdiff_t operator-(Iterator const & i) const { return (p - i.p) / 2; }
 
        // Comparison
        bool operator==(Iterator const & i) const { return p == i.p; }
        bool operator!=(Iterator const & i) const { return p != i.p; }
        bool operator<(Iterator const & i) const { return p < i.p; }
        bool operator>(Iterator const & i) const { return p > i.p; }
        bool operator<=(Iterator const & i) const { return p <= i.p; }
        bool operator>=(Iterator const & i) const { return p >= i.p; }
 
        std::tuple<std::uint64_t, std::uint64_t> operator*() {
            return std::make_tuple(p[0], p[1]);
        }
 
        std::tuple<std::uint64_t, std::uint64_t> operator[](ptrdiff_t n) const {
            return std::make_tuple(p[2 * n], p[2 * n + 1]);
        }
 
        std::uint64_t const * p = nullptr;
    };
 
    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;
 
    RangeSet(RangeSet const &) = default;
    RangeSet(RangeSet &&) = default;
    RangeSet & operator=(RangeSet const &) = default;
    RangeSet & operator=(RangeSet &&) = default;

    RangeSet() = default;

    explicit RangeSet(std::uint64_t u) {
        insert(u);
    }
 
    RangeSet(std::uint64_t first, std::uint64_t last) {
        insert(first, last);
    }
 
    template <
        typename U,
        typename = typename std::enable_if<
            std::is_convertible<U, std::uint64_t>::value
        >::type
    >
    explicit RangeSet(std::tuple<U, U> const & range) {
        insert(static_cast<std::uint64_t>(std::get<0>(range)),
               static_cast<std::uint64_t>(std::get<1>(range)));
    }
 
    RangeSet(std::initializer_list<std::uint64_t>);
 
    // Note: the standard library for GCC unfortunately declares explicit conversion
    // constructors for tuples - the use of std::pair is required for code like:
    //
    //      RangeSet s = {{0, 1}, {2, 3}};
    //
    // to compile.
    RangeSet(std::initializer_list<std::pair<std::uint64_t, std::uint64_t>>);

    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) {
        for (; a != b; ++a) {
            insert(*a);
        }
    }

    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
    >
    explicit RangeSet(Container const & c) :
        RangeSet(std::begin(c), std::end(c)) {}

    bool operator==(RangeSet const & rs) const {
        return _offset == rs._offset && _ranges == rs._ranges;
    }
 
    bool operator!=(RangeSet const & rs) const {
        return _offset != rs._offset || _ranges != rs._ranges;
    }

    void insert(std::uint64_t u) {
        insert(u, u + 1);
    }
 
    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) {
        insert(std::get<0>(range), std::get<1>(range));
    }
 
    void insert(std::uint64_t first, std::uint64_t last);

    void erase(std::uint64_t u) {
        erase(u, u + 1);
    }
 
    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) {
        erase(std::get<0>(range), std::get<1>(range));
    }
 
    void erase(std::uint64_t first, std::uint64_t last);


    RangeSet & complement() { _offset = !_offset; return *this; }

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

    RangeSet intersection(RangeSet const & s) const;

    RangeSet join(RangeSet const & s) const;

    RangeSet difference(RangeSet const & s) const;

    RangeSet symmetricDifference(RangeSet const & s) const;

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

    RangeSet operator&(RangeSet const & s) const {
        return intersection(s);
    }

    RangeSet operator|(RangeSet const & s) const {
        return join(s);
    }

    RangeSet operator-(RangeSet const & s) const {
        return difference(s);
    }

    RangeSet operator^(RangeSet const & s) const {
        return symmetricDifference(s);
    }

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

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

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

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


    bool intersects(std::uint64_t u) const { return intersects(u, u + 1); }
 
    bool intersects(std::uint64_t first, std::uint64_t last) const;
 
    bool intersects(RangeSet const & s) const;

    bool contains(std::uint64_t u) const { return contains(u, u + 1); }
 
    bool contains(std::uint64_t first, std::uint64_t last) const;
 
    bool contains(RangeSet const & s) const;

    bool isWithin(std::uint64_t u) const { return isWithin(u, u + 1); }
 
    bool isWithin(std::uint64_t first, std::uint64_t last) const;
 
    bool isWithin(RangeSet const & s) const { return s.contains(*this); }

    bool isDisjointFrom(std::uint64_t u) const { return !intersects(u); }
 
    bool isDisjointFrom(std::uint64_t first, std::uint64_t last) const {
        return !intersects(first, last);
    }
 
    bool isDisjointFrom(RangeSet const & s) const { return !intersects(s); }

    RangeSet & simplify(std::uint32_t n);

    RangeSet simplified(std::uint32_t n) const {
        RangeSet rs(*this);
        rs.simplify(n);
        return rs;
    }

    RangeSet & scale(std::uint64_t i);

    RangeSet scaled(std::uint64_t i) const {
        RangeSet rs(*this);
        rs.scale(i);
        return rs;
    }

    void clear() { _ranges = {0, 0}; _offset = true; }

    void fill() { _ranges = {0, 0}; _offset = false; }

    bool empty() const { return _begin() == _end(); }

    bool full() const { return _beginc() == _endc(); }

    Iterator begin() const { return Iterator(_begin()); }
    Iterator cbegin() const { return begin(); }

    Iterator end() const { return Iterator(_end()); }
    Iterator cend() const { return end(); }

    Iterator beginc() const { return Iterator(_beginc()); }

    Iterator endc() const { return Iterator(_endc()); }

    size_t max_size() const { return _ranges.max_size() / 2; }

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

    std::uint64_t cardinality() const;
 
    void swap(RangeSet & s) {
        using std::swap;
        swap(_ranges, s._ranges);
        swap(_offset, s._offset);
    }

    bool isValid() const;
 
private:
    std::vector<std::uint64_t> _ranges = {0, 0};
 
    // The offset of the first range in _ranges. It is 0 (false) if the
    // first integer in the set is 0, and 1 (true) otherwise.
    bool _offset = true;
 
    // `_begin` returns a pointer to the first range in this set.
    std::uint64_t const * _begin() const { return _ranges.data() + _offset; }
 
    // `_end` returns a pointer to the range after the last one in this set.
    std::uint64_t const * _end() const {
        size_t s = _ranges.size();
        return _ranges.data() + (s - ((s & 1) ^ _offset));
    }
 
    // `_beginc` returns a pointer to the first range in
    // the complement of this set.
    std::uint64_t const * _beginc() const { return _ranges.data() + !_offset; }
 
    // `_endc` returns a pointer to the range after the last one in
    // the complement of this set.
    std::uint64_t const * _endc() const {
        size_t s = _ranges.size();
        return _ranges.data() + (s - ((s & 1) ^ !_offset));
    }
 
    void _insert(std::uint64_t first, std::uint64_t last);
 
    static void _intersectOne(std::vector<std::uint64_t> &,
                              std::uint64_t const *,
                              std::uint64_t const *, std::uint64_t const *);
 
    static void _intersect(std::vector<std::uint64_t> &,
                           std::uint64_t const *, std::uint64_t const *,
                           std::uint64_t const *, std::uint64_t const *);
 
    void _intersect(std::uint64_t const *, std::uint64_t const *,
                    std::uint64_t const *, std::uint64_t const *);
 
    static bool _intersectsOne(std::uint64_t const *,
                               std::uint64_t const *, std::uint64_t const *);
 
    static bool _intersects(std::uint64_t const *, std::uint64_t const *,
                            std::uint64_t const *, std::uint64_t const *);
};
 
 
inline void swap(RangeSet & a, RangeSet & b) {
    a.swap(b);
}
 
std::ostream & operator<<(std::ostream &, RangeSet const &);
 
}} // namespace lsst::sphgeom
 
#endif // LSST_SPHGEOM_RANGESET_H_