IntervalSet.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_IntervalSet_H
#define Sawyer_IntervalSet_H
 
#include <Sawyer/IntervalMap.h>
#include <Sawyer/Optional.h>
#include <Sawyer/Sawyer.h>
 
#include <boost/integer_traits.hpp>
#include <boost/iterator/iterator_facade.hpp>
#include <boost/serialization/access.hpp>
#include <boost/serialization/nvp.hpp>
 
namespace Sawyer {
namespace Container {
 
template<class I>
class IntervalSet {
    // We use an IntervalMap to do all our work, always storing int(0) as the value.
    typedef IntervalMap<I, int> Map;
    Map map_;
 
private:
    friend class boost::serialization::access;
 
    template<class S>
    void serialize(S &s, const unsigned /*version*/) {
        s & BOOST_SERIALIZATION_NVP(map_);
    }
 
public:
    typedef I Interval;
    typedef typename I::Value Scalar;                   
    class ConstIntervalIterator: public boost::iterator_facade<ConstIntervalIterator, const Interval,
                                                               boost::bidirectional_traversal_tag> {
        typedef typename IntervalMap<Interval, int>::ConstNodeIterator MapNodeIterator;
        MapNodeIterator iter_;
    public:
        ConstIntervalIterator() {}
    private:
        friend class boost::iterator_core_access;
        friend class IntervalSet;
        explicit ConstIntervalIterator(MapNodeIterator iter): iter_(iter) {}
        const Interval& dereference() const { return iter_->key(); }
        bool equal(const ConstIntervalIterator &other) const { return iter_ == other.iter_; }
        void increment() { ++iter_; }
        void decrement() { --iter_; }
        MapNodeIterator base() const { return iter_; }
    };
 
    class ConstScalarIterator: public boost::iterator_facade<ConstScalarIterator, const typename Interval::Value,
                                                             boost::bidirectional_traversal_tag> {
        ConstIntervalIterator iter_;
        typename Interval::Value offset_;
        mutable typename Interval::Value value_;        // so dereference() can return a reference
    public:
        ConstScalarIterator(): offset_(0) {}
        ConstScalarIterator(ConstIntervalIterator iter): iter_(iter), offset_(0) {}
    private:
        friend class boost::iterator_core_access;
        friend class IntervalSet;
        const typename Interval::Value& dereference() const {
            ASSERT_require2(iter_->least() <= iter_->greatest(), "stored interval cannot be empty");
            ASSERT_require(iter_->least() + offset_ <= iter_->greatest());
            value_ = iter_->least() + offset_;
            return value_;                              // must return a reference
        }
        bool equal(const ConstScalarIterator &other) const {
            return iter_ == other.iter_ && offset_ == other.offset_;
        }
        void increment() {
            ASSERT_require2(iter_->least() <= iter_->greatest(), "stored interval cannot be empty");
            if (iter_->least() + offset_ == iter_->greatest()) {
                ++iter_;
                offset_ = 0;
            } else {
                ++offset_;
            }
        }
        void decrement() {
            ASSERT_require2(iter_->least() <= iter_->greatest(), "stored interval cannot be empty");
            if (0==offset_) {
                --iter_;
                offset_ = width(*iter_);
            } else {
                --offset_;
            }
        }
    };
 
    //                                  Constructors
 
    IntervalSet() {}
 
    template<class Interval2>
    IntervalSet(const IntervalSet<Interval2> &other) {
        typedef typename IntervalSet<Interval2>::ConstIntervalIterator OtherIntervalIterator;
        for (OtherIntervalIterator otherIter=other.intervals().begin(); otherIter!=other.intervals().end(); ++otherIter)
            insert(*otherIter);
    }
 
    template<class Interval2, class T, class Policy>
    explicit IntervalSet(const IntervalMap<Interval2, T, Policy> &other) {
        typedef typename IntervalMap<Interval2, T, Policy>::ConstNodeIterator OtherNodeIterator;
        for (OtherNodeIterator otherIter=other.nodes().begin(); otherIter!=other.nodes().end(); ++otherIter)
            insert(otherIter->key());
    }
 
    template<class Iterator>
    IntervalSet(const boost::iterator_range<Iterator> &intervals) {
        for (Iterator iter=intervals.begin(); iter!=intervals.end(); ++iter)
            insert(*iter);
    }
    
    template<class Interval2>
    IntervalSet& operator=(const IntervalSet<Interval2> &other) {
        clear();
        typedef typename IntervalSet<Interval2>::ConstIntervalIterator OtherIntervalIterator;
        for (OtherIntervalIterator otherIter=other.intervals().begin(); otherIter!=other.intervals().end(); ++otherIter)
            insert(*otherIter);
        return *this;
    }
 
    template<class Interval2, class T, class Policy>
    IntervalSet& operator=(const IntervalMap<Interval2, T, Policy> &other) {
        clear();
        typedef typename IntervalMap<Interval2, T, Policy>::ConstNodeIterator OtherNodeIterator;
        for (OtherNodeIterator otherIter=other.nodes().begin(); otherIter!=other.nodes().end(); ++otherIter)
            insert(otherIter->key());
        return *this;
    }
 
    template<class Iterator>
    IntervalSet& operator=(const boost::iterator_range<Iterator> &intervals) {
        clear();
        for (Iterator iter=intervals.begin(); iter!=intervals.end(); ++iter)
            insert(*iter);
        return *this;
    }
    
    //                                  Iteration
 
    boost::iterator_range<ConstIntervalIterator> intervals() const {
        return boost::iterator_range<ConstIntervalIterator>(ConstIntervalIterator(map_.nodes().begin()),
                                                            ConstIntervalIterator(map_.nodes().end()));
    }
 
    boost::iterator_range<ConstScalarIterator> scalars() const {
        return boost::iterator_range<ConstScalarIterator>(ConstScalarIterator(intervals().begin()),
                                                          ConstScalarIterator(intervals().end()));
    }
 
    ConstIntervalIterator lowerBound(const typename Interval::Value &scalar) const {
        return ConstIntervalIterator(map_.lowerBound(scalar));
    }
 
    ConstIntervalIterator upperBound(const typename Interval::Value &scalar) const {
        return ConstIntervalIterator(map_.upperBound(scalar));
    }
 
    ConstIntervalIterator findPrior(const typename Interval::Value &scalar) const {
        return ConstIntervalIterator(map_.findPrior(scalar));
    }
 
    ConstIntervalIterator find(const typename Interval::Value &scalar) const {
        return ConstIntervalIterator(map_.find(scalar));
    }
 
    boost::iterator_range<ConstIntervalIterator> findAll(const Interval &interval) const {
        boost::iterator_range<typename Map::ConstNodeIterator> range = map_.findAll(interval);
        return boost::iterator_range<ConstIntervalIterator>(ConstIntervalIterator(range.begin()),
                                                            ConstIntervalIterator(range.end()));
    }
 
    ConstIntervalIterator findFirstOverlap(const Interval &interval) const {
        return ConstIntervalIterator(map_.findFirstOverlap(interval));
    }
    std::pair<ConstIntervalIterator, ConstIntervalIterator>
    findFirstOverlap(ConstIntervalIterator thisIter, const IntervalSet &other, ConstIntervalIterator otherIter) const {
        std::pair<typename Map::ConstNodeIterator, typename Map::ConstNodeIterator> found =
            map_.findFirstOverlap(thisIter.base(), other.map_, otherIter.base());
        return std::make_pair(ConstIntervalIterator(found.first), ConstIntervalIterator(found.second));
    }
 
    //                                  Size
 
    bool isEmpty() const {
        return map_.isEmpty();
    }
 
    typename Interval::Value size() const {
        return map_.size();
    }
 
    size_t nIntervals() const {
        return map_.nIntervals();
    }
 
    Interval hull() const {
        return map_.hull();
    }
 
    //                                  Predicates
 
    template<class Interval2>
    bool isOverlapping(const Interval2 &interval) const {
        return map_.isOverlapping(interval);
    }
 
    template<class Interval2>
    bool isOverlapping(const IntervalSet<Interval2> &other) const {
        return map_.isOverlapping(other.map_);
    }
 
    template<class Interval2, class T2, class Policy2>
    bool isOverlapping(const IntervalMap<Interval2, T2, Policy2> &other) const {
        return map_.isOverlapping(other);
    }
    template<class Interval2>
    bool isDistinct(const Interval2 &interval) const {
        return !isOverlapping();
    }
 
    template<class Interval2>
    bool isDistinct(const IntervalSet<Interval2> &other) const {
        return !isOverlapping(other);
    }
 
    template<class Interval2, class T2, class Policy2>
    bool isDistinct(const IntervalMap<Interval2, T2, Policy2> &other) const {
        return !isOverlapping(other);
    }
    bool exists(const typename Interval::Value &scalar) const {
        return find(scalar)!=intervals().end();
    }
    
    bool contains(const typename Interval::Value &scalar) const {
        return exists(scalar);
    }
 
    template<class Interval2>
    bool contains(const Interval2 &interval) const {
        return map_.contains(interval);
    }
 
    template<class Interval2>
    bool contains(const IntervalSet<Interval2> &other) const {
        return map_.contains(other.map_);
    }
 
    template<class Interval2, class T2, class Policy2>
    bool contains(const IntervalMap<Interval2, T2, Policy2> &other) const {
        return map_.contains(other);
    }
    //                                  Searching
    
    Scalar least() const {
        ASSERT_forbid(isEmpty());
        return map_.least();
    }
 
    Scalar greatest() const {
        ASSERT_forbid(isEmpty());
        return map_.greatest();
    }
 
    Optional<Scalar> least(Scalar lowerLimit) const {
        return map_.least(lowerLimit);
    }
 
    Optional<Scalar> greatest(Scalar upperLimit) const {
        return map_.greatest(upperLimit);
    }
 
    Optional<Scalar> leastNonExistent(Scalar lowerLimit) const {
        return map_.leastUnmapped(lowerLimit);
    }
 
    Optional<Scalar> greatestNonExistent(Scalar upperLimit) const {
        return map_.greatestUnmapped(upperLimit);
    }
 
    ConstIntervalIterator firstFit(const typename Interval::Value &size, ConstIntervalIterator start) const {
        return ConstIntervalIterator(map_.firstFit(size, start.iter_));
    }
 
    ConstIntervalIterator bestFit(const typename Interval::Value &size, ConstIntervalIterator start) const {
        return ConstIntervalIterator(map_.bestFit(size, start.iter_));
    }
 
 
 
    //                                  Modifiers
 
    void clear() {
        map_.clear();
    }
 
    void invert() {
        invert(Interval::whole());
    }
 
    void invert(const Interval &restricted) {
        IntervalSet inverted;
        if (!restricted.isEmpty()) {
            typename Interval::Value pending = restricted.least();
            bool insertTop = true;
            for (typename Map::ConstIntervalIterator iter=map_.lowerBound(restricted.least());
                 iter!=map_.intervals().end(); ++iter) {
                if (iter->least() > restricted.greatest())
                    break;
                if (pending < iter->least())
                    inverted.insert(Interval::hull(pending, iter->least()-1));
                if (iter->greatest() < restricted.greatest()) {
                    pending = iter->greatest() + 1;
                } else {
                    insertTop = false;
                    break;
                }
            }
            if (insertTop)
                inverted.insert(Interval::hull(pending, restricted.greatest()));
        }
        std::swap(map_, inverted.map_);
    }
 
    template<class Interval2>
    void insert(const Interval2 &interval) {
        map_.insert(interval, 0);
    }
 
    template<class Interval2>
    void insertMultiple(const IntervalSet<Interval2> &other) {
        typedef typename IntervalSet<Interval2>::ConstIntervalIterator OtherIterator;
        for (OtherIterator otherIter=other.intervals().begin(); otherIter!=other.intervals().end(); ++otherIter)
            map_.insert(*otherIter, 0);
    }
 
    template<class Interval2, class T, class Policy>
    void insertMultiple(const IntervalMap<Interval2, T, Policy> &other) {
        typedef typename IntervalMap<Interval2, T, Policy>::ConstIntervalIterator OtherIterator;
        for (OtherIterator otherIter=other.intervals().begin(); otherIter!=other.intervals().end(); ++otherIter)
            map_.insert(*otherIter, 0);
    }
    template<class Interval2>
    void erase(const Interval2 &interval) {
        map_.erase(interval);
    }
 
    template<class Interval2>
    void eraseMultiple(const IntervalSet<Interval2> &other) {
        ASSERT_forbid2((void*)&other==(void*)this, "use IntervalSet::clear() instead");
        typedef typename IntervalSet<Interval2>::ConstIntervalIterator OtherIntervalIterator;
        for (OtherIntervalIterator otherIter=other.intervals().begin(); otherIter!=other.intervals().end(); ++otherIter)
            map_.erase(*otherIter);
    }
 
    template<class Interval2, class T, class Policy>
    void eraseMultiple(const IntervalMap<Interval2, T, Policy> &other) {
        typedef typename IntervalMap<Interval2, T, Policy>::ConstIntervalIterator OtherIntervalIterator;
        for (OtherIntervalIterator otherIter=other.intervals().begin(); otherIter!=other.intervals().end(); ++otherIter)
            map_.erase(otherIter->first);
    }
    template<class Interval2>
    void intersect(const Interval2 &interval) {
        if (isEmpty())
            return;
        if (interval.isEmpty()) {
            clear();
            return;
        }
        if (hull().least() < interval.least())
            map_.erase(Interval::hull(hull().least(), interval.least()-1));
        if (hull().greatest() > interval.greatest())
            map_.erase(Interval::hull(interval.greatest(), hull().greatest()));
    }
 
    template<class Interval2>
    void intersect(IntervalSet<Interval2> other) {
        other.invert(hull());
        map_.eraseMultiple(other.map_);
    }
 
    template<class Interval2, class T, class Policy>
    void intersect(const IntervalMap<Interval2, T, Policy> &other);// FIXME[Robb Matzke 2014-04-12]: not implemented yet
    //                                  Operators
 
    bool operator==(const IntervalSet &other) const {
        return !(*this!=other);
    }
 
    bool operator!=(const IntervalSet &other) const {
        if (map_.nIntervals()!=other.map_.nIntervals())
            return true;
        for (ConstIntervalIterator ai=intervals().begin(), bi=other.intervals().begin(); ai!=intervals().end(); ++ai, ++bi) {
            if (*ai!=*bi)
                return true;
        }
        return false;
    }
        
    IntervalSet operator~() const {
        IntervalSet tmp = *this;
        tmp.invert();
        return tmp;
    }
 
    IntervalSet& operator|=(const IntervalSet &other) {
        insertMultiple(other);
        return *this;
    }
    
    IntervalSet& operator|=(const Interval &interval) {
        insert(interval);
        return *this;
    }
 
    IntervalSet operator|(const IntervalSet &other) const {
        if (nIntervals() < other.nIntervals()) {
            IntervalSet tmp = other;
            tmp.insertMultiple(*this);
            return tmp;
        }
        IntervalSet tmp = *this;
        tmp.insertMultiple(other);
        return tmp;
    }
 
    IntervalSet operator|(const Interval &interval) const {
        IntervalSet retval = *this;
        retval.insert(interval);
        return retval;
    }
 
    IntervalSet& operator&=(const IntervalSet &other) {
        intersect(other);
        return *this;
    }
 
    IntervalSet& operator&=(const Interval &interval) {
        intersect(interval);
        return *this;
    }
 
    IntervalSet operator&(const IntervalSet &other) const {
        if (nIntervals() < other.nIntervals()) {
            IntervalSet tmp = other;
            tmp.intersect(*this);
            return tmp;
        }
        IntervalSet tmp = *this;
        tmp.intersect(other);
        return tmp;
    }
 
    IntervalSet operator&(const Interval &interval) const {
        IntervalSet retval = *this;
        retval.intersect(interval);
        return retval;
    }
 
    IntervalSet& operator-=(const IntervalSet &other) {
        eraseMultiple(other);
        return *this;
    }
 
    IntervalSet& operator-=(const Interval &interval) {
        erase(interval);
        return *this;
    }
    
    IntervalSet operator-(const IntervalSet &other) const {
        IntervalSet tmp = *this;
        tmp.eraseMultiple(other);
        return tmp;
    }
 
    IntervalSet operator-(const Interval &interval) const {
        IntervalSet tmp = *this;
        tmp.erase(interval);
        return tmp;
    }
};
 
} // namespace
} // namespace
 
#endif