RangeSet.h

Go to the documentation of this file.

/*
 * LSST Data Management System
 * Copyright 2016 AURA/LSST.
 *
 * This product includes software developed by the
 * LSST Project (http://www.lsst.org/).
 *
 * 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 LSST License Statement and
 * the GNU General Public License along with this program.  If not,
 * see <https://www.lsstcorp.org/LegalNotices/>.
 */

#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<uint64_t, uint64_t>;
        using pointer = void;
        using reference = std::tuple<uint64_t, uint64_t>;
        using iterator_category = std::input_iterator_tag;

        Iterator() = default;
        explicit Iterator(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<uint64_t, uint64_t> operator*() {
            return std::make_tuple(p[0], p[1]);
        }

        std::tuple<uint64_t, uint64_t> operator[](ptrdiff_t n) const {
            return std::make_tuple(p[2 * n], p[2 * n + 1]);
        }

        uint64_t const * p = nullptr;
    };

    using difference_type = ptrdiff_t;
    using size_type = size_t;
    using value_type = std::tuple<uint64_t, 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(uint64_t u) {
        insert(u);
    }

    RangeSet(uint64_t first, uint64_t last) {
        insert(first, last);
    }

    template <
        typename U,
        typename = typename std::enable_if<
            std::is_convertible<U, uint64_t>::value
        >::type
    >
    explicit RangeSet(std::tuple<U, U> const & range) {
        insert(static_cast<uint64_t>(std::get<0>(range)),
               static_cast<uint64_t>(std::get<1>(range)));
    }

    RangeSet(std::initializer_list<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<uint64_t, 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(uint64_t u) {
        insert(u, u + 1);
    }

    template <
        typename U,
        typename = typename std::enable_if<
            std::is_convertible<U, uint64_t>::value
        >::type
    >
    void insert(std::tuple<U, U> const & range) {
        insert(std::get<0>(range), std::get<1>(range));
    }

    void insert(uint64_t first, uint64_t last);

    void erase(uint64_t u) {
        erase(u, u + 1);
    }

    template <
        typename U,
        typename = typename std::enable_if<
            std::is_convertible<U, uint64_t>::value
        >::type
    >
    void erase(std::tuple<U, U> const & range) {
        erase(std::get<0>(range), std::get<1>(range));
    }

    void erase(uint64_t first, 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(uint64_t u) const { return intersects(u, u + 1); }

    bool intersects(uint64_t first, uint64_t last) const;

    bool intersects(RangeSet const & s) const;

    bool contains(uint64_t u) const { return contains(u, u + 1); }

    bool contains(uint64_t first, uint64_t last) const;

    bool contains(RangeSet const & s) const;

    bool isWithin(uint64_t u) const { return isWithin(u, u + 1); }

    bool isWithin(uint64_t first, uint64_t last) const;

    bool isWithin(RangeSet const & s) const { return s.contains(*this); }

    bool isDisjointFrom(uint64_t u) const { return !intersects(u); }

    bool isDisjointFrom(uint64_t first, uint64_t last) const {
        return !intersects(first, last);
    }

    bool isDisjointFrom(RangeSet const & s) const { return !intersects(s); }

    RangeSet & simplify(uint32_t n);

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

    RangeSet & scale(uint64_t i);

    RangeSet scaled(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; }

    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<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.
    uint64_t const * _begin() const { return _ranges.data() + _offset; }

    // `_end` returns a pointer to the range after the last one in this set.
    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.
    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.
    uint64_t const * _endc() const {
        size_t s = _ranges.size();
        return _ranges.data() + (s - ((s & 1) ^ !_offset));
    }

    void _insert(uint64_t first, uint64_t last);

    static void _intersectOne(std::vector<uint64_t> &,
                              uint64_t const *,
                              uint64_t const *, uint64_t const *);

    static void _intersect(std::vector<uint64_t> &,
                           uint64_t const *, uint64_t const *,
                           uint64_t const *, uint64_t const *);

    void _intersect(uint64_t const *, uint64_t const *,
                    uint64_t const *, uint64_t const *);

    static bool _intersectsOne(uint64_t const *,
                               uint64_t const *, uint64_t const *);

    static bool _intersects(uint64_t const *, uint64_t const *,
                            uint64_t const *, 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_