Interval.h

// WARNING: Changes to this file must be contributed back to Sawyer or else they will
//          be clobbered by the next update from Sawyer.  The Sawyer repository is at
//          https://github.com/matzke1/sawyer.




#ifndef Sawyer_Interval_H
#define Sawyer_Interval_H

#include <Sawyer/Assert.h>
#include <Sawyer/Sawyer.h>
#include <boost/integer_traits.hpp>
#include <boost/iterator/iterator_facade.hpp>
#include <boost/range/iterator_range.hpp>
#include <boost/serialization/access.hpp>
#include <boost/serialization/nvp.hpp>

namespace Sawyer {
namespace Container {

template<class T>
class Interval {
public:
    typedef T Value;
private:
    T lo_, hi_;

private:
    friend class boost::serialization::access;

    template<class S>
    void serialize(S &s, const unsigned /*version*/) {
        s & BOOST_SERIALIZATION_NVP(lo_);
        s & BOOST_SERIALIZATION_NVP(hi_);
    }

public:
    class ConstIterator: public boost::iterator_facade<ConstIterator, const Value, boost::bidirectional_traversal_tag,
                                                       Value> {
        friend class Interval;
        friend class boost::iterator_core_access;

        T first_, cur_, last_;
        bool atEnd_;

        ConstIterator(T first, T last, T cur): first_(first), cur_(cur), last_(last), atEnd_(false) {}
    public:
        ConstIterator(): first_(0), cur_(0), last_(0), atEnd_(true) {}

        bool atEnd() const {
            return atEnd_;
        }

    private:
        Value dereference() const {
            ASSERT_forbid(atEnd());
            return cur_;
        }

        bool equal(const ConstIterator &other) const {
            if (atEnd() || other.atEnd())
                return atEnd() && other.atEnd();
            return cur_ == other.cur_;
        }

        // Incrementing an iterator associated with an empty interval is a no-op, and such an interval's @ref atEnd always
        // returns true. Otherwise, incrementing an iterator positioned one past the interval's greatest end is a
        // no-op. Otherwise, incrementing an iterator positioned one prior to the interval's least end returns the iterator to
        // the interval's least value. Otherwise the iterator derefences to a value one greater than before this call.
        void increment() {
            if (cur_ == last_) {                        // avoid overflow
                atEnd_ = true;
            } else if (atEnd_) {
                ASSERT_require(cur_ == first_);
                atEnd_ = false;
            } else {
                ++cur_;
            }
        }

        void decrement() {
            if (cur_ == first_) {                       // avoid overflow
                atEnd_ = true;
            } else if (atEnd_) {
                ASSERT_require(cur_ == last_);
                atEnd_ = false;
            } else {
                --cur_;
            }
        }
    };
    
public:
    Interval(): lo_(1), hi_(0) {}

    Interval(const Interval &other): lo_(other.lo_), hi_(other.hi_) {}

    Interval(T value): lo_(value), hi_(value) {}

#if 0 // [Robb Matzke 2014-05-14]: too much confusion with "hi" vs. "size". Use either baseSize or hull instead.

    Interval(T lo, T hi): lo_(lo), hi_(hi) {
        ASSERT_require(lo <= hi);
    }
#endif

    static Interval hull(T v1, T v2) {
        Interval retval;
        retval.lo_ = std::min(v1, v2);
        retval.hi_ = std::max(v1, v2);
        return retval;
    }

    static Interval baseSize(T lo, T size) {
        ASSERT_forbid(baseSizeOverflows(lo, size));
        return 0==size ? Interval() : Interval::hull(lo, lo+size-1);
    }

    static Interval baseSizeSat(T lo, T size) {
        if (baseSizeOverflows(lo, size)) {
            return hull(lo, boost::integer_traits<T>::const_max);
        } else {
            return baseSize(lo, size);
        }
    }

    static Interval whole() {
        return hull(boost::integer_traits<T>::const_min, boost::integer_traits<T>::const_max);
    }

    Interval& operator=(const Interval &other) {
        lo_ = other.lo_;
        hi_ = other.hi_;
        return *this;
    }

    Interval& operator=(T value) {
        lo_ = hi_ = value;
        return *this;
    }

    static bool baseSizeOverflows(T base, T size) {
        // Warning: This only works when T is unsigned since signed integer overflow is undefined behavior in C++.
        return base + size < base;
    }

    T least() const {
        ASSERT_forbid(isEmpty());
        return lo_;
    }

    T greatest() const {
        ASSERT_forbid(isEmpty());
        return hi_;
    }

    bool isEmpty() const { return 1==lo_ && 0==hi_; }

    bool isSingleton() const { return lo_ == hi_; }

    bool isWhole() const { return lo_==boost::integer_traits<T>::const_min && hi_==boost::integer_traits<T>::const_max; }

    bool overlaps(const Interval &other) const {
        return !intersection(other).isEmpty();
    }
    bool isOverlapping(const Interval &other) const {
        return overlaps(other);
    }
    bool contains(const Interval &other) const {
        return (other.isEmpty() ||
                (!isEmpty() && least()<=other.least() && greatest()>=other.greatest()));
    }
    bool isContaining(const Interval &other) const {
        return contains(other);
    }
    bool isLeftAdjacent(const Interval &right) const {
        return isEmpty() || right.isEmpty() || (!isWhole() && greatest()+1 == right.least());
    }
    bool isRightAdjacent(const Interval &left) const {
        return isEmpty() || left.isEmpty() || (!left.isWhole() && left.greatest()+1 == least());
    }
    bool isAdjacent(const Interval &other) const {
        return (isEmpty() || other.isEmpty() ||
                (!isWhole() && greatest()+1 == other.least()) ||
                (!other.isWhole() && other.greatest()+1 == least()));
    }
    bool isLeftOf(const Interval &right) const {
        return isEmpty() || right.isEmpty() || greatest() < right.least();
    }
    bool isRightOf(const Interval &left) const {
        return isEmpty() || left.isEmpty() || left.greatest() < least();
    }
    Value size() const {
        return isEmpty() ? 0 : hi_ - lo_ + 1;
    }

    bool operator==(const Interval &other) const {
        return lo_==other.lo_ && hi_==other.hi_;
    }
    bool operator!=(const Interval &other) const {
        return lo_!=other.lo_ || hi_!=other.hi_;
    }
    Interval intersection(const Interval &other) const {
        if (isEmpty() || other.isEmpty() || greatest()<other.least() || least()>other.greatest())
            return Interval();
        return Interval::hull(std::max(least(), other.least()), std::min(greatest(), other.greatest()));
    }
    Interval operator&(const Interval &other) const {
        return intersection(other);
    }
    Interval hull(const Interval &other) const {
        if (isEmpty()) {
            return other;
        } else if (other.isEmpty()) {
            return *this;
        } else {
            return Interval::hull(std::min(least(), other.least()), std::max(greatest(), other.greatest()));
        }
    }

    Interval hull(T value) const {
        if (isEmpty()) {
            return Interval(value);
        } else {
            return Interval::hull(std::min(least(), value), std::max(greatest(), value));
        }
    }

    std::pair<Interval, Interval> split(T splitPoint) const {
        if (isEmpty()) {
            return std::make_pair(Interval(), Interval());
        } else if (splitPoint < least()) {
            return std::make_pair(Interval(), *this);
        } else if (splitPoint < greatest()) {
            return std::make_pair(Interval::hull(least(), splitPoint), Interval::hull(splitPoint+1, greatest()));
        } else {
            return std::make_pair(*this, Interval());
        }
    }

    Interval join(const Interval &right) const {
        if (isEmpty()) {
            return right;
        } else if (right.isEmpty()) {
            return *this;
        } else {
            ASSERT_require(greatest()+1 == right.least() && right.least() > greatest());
            return hull(right);
        }
    }

    Interval shiftRightSat(Value n) const {
        if (isEmpty() || baseSizeOverflows(least(), n)) {
            return Interval();
        } else if (baseSizeOverflows(greatest(), n)) {
            return hull(least() + n, boost::integer_traits<T>::const_max);
        } else {
            return hull(least() + n, greatest() + n);
        }
    }

    // These types are needed for BOOST_FOREACH but are not advertised as part of this interface.
    typedef ConstIterator const_iterator;
    typedef ConstIterator iterator;

    ConstIterator begin() const {
        return isEmpty() ? ConstIterator() : ConstIterator(least(), greatest(), least());
    }

    ConstIterator end() const {
        return isEmpty() ? ConstIterator() : ++ConstIterator(least(), greatest(), greatest());
    }
    
    boost::iterator_range<ConstIterator> values() const {
        return boost::iterator_range<ConstIterator>(begin(), end());
    }
    
    // The following trickery is to allow things like "if (x)" to work but without having an implicit
    // conversion to bool which would cause no end of other problems.  This is fixed in C++11
private:
    typedef void(Interval::*unspecified_bool)() const;
    void this_type_does_not_support_comparisons() const {}
public:
    operator unspecified_bool() const {
        return isEmpty() ? 0 : &Interval::this_type_does_not_support_comparisons;
    }
};

} // namespace
} // namespace

#endif