IntervalMap.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_IntervalMap_H
#define Sawyer_IntervalMap_H

#include <boost/cstdint.hpp>
#include <Sawyer/Assert.h>
#include <Sawyer/Map.h>
#include <Sawyer/Optional.h>
#include <Sawyer/Sawyer.h>

#include <boost/serialization/access.hpp>
#include <boost/serialization/nvp.hpp>

namespace Sawyer {
namespace Container {

template<class IntervalMap>
struct IntervalMapTraits {
    typedef typename IntervalMap::NodeIterator NodeIterator;    
    typedef typename IntervalMap::ValueIterator ValueIterator;  
    typedef typename IntervalMap::Value &ValueReference;        
};

template<class IntervalMap>
struct IntervalMapTraits<const IntervalMap> {
    typedef typename IntervalMap::ConstNodeIterator NodeIterator;
    typedef typename IntervalMap::ConstValueIterator ValueIterator;
    typedef typename IntervalMap::Value const &ValueReference;
};

template<typename I, typename T>
class MergePolicy {
public:
    typedef I Interval;
    typedef T Value;

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

    template<class S>
    void serialize(S&, const unsigned /*version*/) {
        // nothing to serialize in this class
    }

public:
    bool merge(const Interval &leftInterval, Value &leftValue, const Interval &rightInterval, Value &rightValue) {
        SAWYER_ARGUSED(leftInterval);
        SAWYER_ARGUSED(rightInterval);
        return leftValue == rightValue;
    }

    Value split(const Interval &interval, Value &value, const typename Interval::Value &splitPoint) {
        SAWYER_ARGUSED(interval);
        SAWYER_ARGUSED(splitPoint);
        return value;
    }

    void truncate(const Interval &interval, Value &value, const typename Interval::Value &splitPoint) {
        SAWYER_ARGUSED(interval);
        SAWYER_ARGUSED(value);
        SAWYER_ARGUSED(splitPoint);
    }
};

template<typename I, typename T, class Policy = MergePolicy<I, T> >
class IntervalMap {
public:
    typedef I Interval;                                 
    typedef T Value;                                    
private:
    // Nodes of the underlying map are sorted by their last value so that we can use that map's lowerBound method to find the
    // range to which a scalar key might belong.  Since the intervals in the map are non-overlapping, sorting by greatest values
    // has the same effect as sorting by least values.
    struct IntervalCompare {
        bool operator()(const Interval &a, const Interval &b) const {
            return a.greatest() < b.greatest();
        }
    };

    typedef std::pair<Interval, Interval> IntervalPair;

public:
    typedef Container::Map<Interval, Value, IntervalCompare> Map;

    typedef typename Map::Node Node;

    typedef typename Map::ConstKeyIterator ConstIntervalIterator;

    typedef typename Map::ValueIterator ValueIterator;
    typedef typename Map::ConstValueIterator ConstValueIterator;
    typedef typename Map::NodeIterator NodeIterator;
    typedef typename Map::ConstNodeIterator ConstNodeIterator;
private:
    Map map_;
    Policy policy_;
    typename Interval::Value size_;                     // number of values (map_.size is number of intervals)

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

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

    //                                  Constructors
public:
    IntervalMap(): size_(0) {}

    template<class Interval2, class T2, class Policy2>
    IntervalMap(const IntervalMap<Interval2, T2, Policy2> &other) {
        typedef typename IntervalMap<Interval2, T2, Policy2>::ConstNodeIterator OtherIterator;
        for (OtherIterator otherIter=other.nodes().begin(); other!=other.nodes().end(); ++other)
            insert(Interval(otherIter->key()), Value(otherIter->value()));
    }

    template<class Interval2, class T2, class Policy2>
    IntervalMap& operator=(const IntervalMap<Interval2, T2, Policy2> &other) {
        clear();
        typedef typename IntervalMap<Interval2, T2, Policy2>::ConstNodeIterator OtherIterator;
        for (OtherIterator otherIter=other.nodes().begin(); other!=other.nodes().end(); ++other)
            insert(Interval(otherIter->key()), Value(otherIter->value()));
        return *this;
    }

    //                                  Searching
public:

    boost::iterator_range<NodeIterator> nodes() { return map_.nodes(); }
    boost::iterator_range<ConstNodeIterator> nodes() const { return map_.nodes(); }
    boost::iterator_range<ConstIntervalIterator> intervals() const { return map_.keys(); }

    boost::iterator_range<ValueIterator> values() { return map_.values(); }
    boost::iterator_range<ConstValueIterator> values() const { return map_.values(); }
    NodeIterator lowerBound(const typename Interval::Value &scalar) {
        return map_.lowerBound(Interval(scalar));
    }
    ConstNodeIterator lowerBound(const typename Interval::Value &scalar) const {
        return map_.lowerBound(Interval(scalar));
    }
    NodeIterator upperBound(const typename Interval::Value &scalar) {
        NodeIterator ub = map_.upperBound(Interval(scalar)); // first node that ENDS after scalar
        while (ub!=map_.nodes().end() && ub->key().least() <= scalar)
            ++ub;
        return ub;
    }
    ConstNodeIterator upperBound(const typename Interval::Value &scalar) const {
        ConstNodeIterator ub = map_.upperBound(Interval(scalar)); // first node that ENDS after scalar
        while (ub!=map_.nodes().end() && ub->key().least() <= scalar)
            ++ub;
        return ub;
    }
    NodeIterator findPrior(const typename Interval::Value &scalar) {
        return findPriorImpl(*this, scalar);
    }
    ConstNodeIterator findPrior(const typename Interval::Value &scalar) const {
        return findPriorImpl(*this, scalar);
    }

    template<class IMap>
    static typename IntervalMapTraits<IMap>::NodeIterator
    findPriorImpl(IMap &imap, const typename Interval::Value &scalar) {
        typedef typename IntervalMapTraits<IMap>::NodeIterator Iter;
        if (imap.isEmpty())
            return imap.nodes().end();
        Iter lb = imap.lowerBound(scalar);
        if (lb!=imap.nodes().end() && lb->key().least() <= scalar)
            return lb;
        if (lb==imap.nodes().begin())
            return imap.nodes().end();
        return --lb;
    }
    NodeIterator find(const typename Interval::Value &scalar) {
        return findImpl(*this, scalar);
    }
    ConstNodeIterator find(const typename Interval::Value &scalar) const {
        return findImpl(*this, scalar);
    }

    template<class IMap>
    static typename IntervalMapTraits<IMap>::NodeIterator
    findImpl(IMap &imap, const typename Interval::Value &scalar) {
        typedef typename IntervalMapTraits<IMap>::NodeIterator Iter;
        Iter found = imap.lowerBound(scalar);
        if (found==imap.nodes().end() || scalar < found->key().least())
            return imap.nodes().end();
        return found;
    }
    boost::iterator_range<NodeIterator> findAll(const Interval &interval) {
        return findAllImpl(*this, interval);
    }
    boost::iterator_range<ConstNodeIterator> findAll(const Interval &interval) const {
        return findAllImpl(*this, interval);
    }

    template<class IMap>
    static boost::iterator_range<typename IntervalMapTraits<IMap>::NodeIterator>
    findAllImpl(IMap &imap, const Interval &interval) {
        typedef typename IntervalMapTraits<IMap>::NodeIterator Iter;
        if (interval.isEmpty())
            return boost::iterator_range<Iter>(imap.nodes().end(), imap.nodes().end());
        Iter begin = imap.lowerBound(interval.least());
        if (begin==imap.nodes().end() || begin->key().least() > interval.greatest())
            return boost::iterator_range<Iter>(imap.nodes().end(), imap.nodes().end());
        return boost::iterator_range<Iter>(begin, imap.upperBound(interval.greatest()));
    }
    NodeIterator findFirstOverlap(const Interval &interval) {
        return findFirstOverlapImpl(*this, interval);
    }
    ConstNodeIterator findFirstOverlap(const Interval &interval) const {
        return findFirstOverlapImpl(*this, interval);
    }

    template<class IMap>
    static typename IntervalMapTraits<IMap>::NodeIterator
    findFirstOverlapImpl(IMap &imap, const Interval &interval) {
        typedef typename IntervalMapTraits<IMap>::NodeIterator Iter;
        if (interval.isEmpty())
            return imap.nodes().end();
        Iter lb = imap.lowerBound(interval.least());
        return lb!=imap.nodes().end() && interval.overlaps(lb->key()) ? lb : imap.nodes().end();
    }
    template<typename T2, class Policy2>
    std::pair<NodeIterator, typename IntervalMap<Interval, T2, Policy2>::ConstNodeIterator>
    findFirstOverlap(typename IntervalMap::NodeIterator thisIter, const IntervalMap<Interval, T2, Policy2> &other,
                     typename IntervalMap<Interval, T2, Policy2>::ConstNodeIterator otherIter) {
        return findFirstOverlapImpl(*this, thisIter, other, otherIter);
    }
    template<typename T2, class Policy2>
    std::pair<ConstNodeIterator, typename IntervalMap<Interval, T2, Policy2>::ConstNodeIterator>
    findFirstOverlap(typename IntervalMap::ConstNodeIterator thisIter, const IntervalMap<Interval, T2, Policy2> &other,
                     typename IntervalMap<Interval, T2, Policy2>::ConstNodeIterator otherIter) const {
        return findFirstOverlapImpl(*this, thisIter, other, otherIter);
    }

    template<class IMap, typename T2, class Policy2>
    static std::pair<typename IntervalMapTraits<IMap>::NodeIterator,
                     typename IntervalMap<Interval, T2, Policy2>::ConstNodeIterator>
    findFirstOverlapImpl(IMap &imap,
                         typename IntervalMapTraits<IMap>::NodeIterator thisIter,
                         const IntervalMap<Interval, T2, Policy2> &other,
                         typename IntervalMap<Interval, T2, Policy2>::ConstNodeIterator otherIter) {
        while (thisIter!=imap.nodes().end() && otherIter!=other.nodes().end()) {
            if (thisIter->key().overlaps(otherIter->key()))
                return std::make_pair(thisIter, otherIter);
            if (thisIter->key().greatest() < otherIter->key().greatest()) {
                ++thisIter;
            } else {
                ++otherIter;
            }
        }
        return std::make_pair(imap.nodes().end(), other.nodes().end());
    }
    NodeIterator firstFit(const typename Interval::Value &size, NodeIterator start) {
        return firstFitImpl(*this, size, start);
    }
    ConstNodeIterator firstFit(const typename Interval::Value &size, ConstNodeIterator start) const {
        return firstFitImpl(*this, size, start);
    }

    template<class IMap>
    static typename IntervalMapTraits<IMap>::NodeIterator
    firstFitImpl(IMap &imap, const typename Interval::Value &size, typename IntervalMapTraits<IMap>::NodeIterator start) {
        typedef typename IntervalMapTraits<IMap>::NodeIterator Iter;
        for (Iter iter=start; iter!=imap.nodes().end(); ++iter) {
            if (isLarge(iter->key(), size))
                return iter;
        }
        return imap.nodes().end();
    }
        
    NodeIterator bestFit(const typename Interval::Value &size, NodeIterator start) {
        return bestFitImpl(*this, size, start);
    }
    ConstNodeIterator bestFit(const typename Interval::Value &size, ConstNodeIterator start) const {
        return bestFitImpl(*this, size, start);
    }

    template<class IMap>
    static typename IntervalMapTraits<IMap>::NodeIterator
    bestFitImpl(IMap &imap, const typename Interval::Value &size, typename IntervalMapTraits<IMap>::NodeIterator start) {
        typedef typename IntervalMapTraits<IMap>::NodeIterator Iter;
        Iter best = imap.nodes().end();
        for (Iter iter=start; iter!=imap.nodes().end(); ++iter) {
            if (iter->key().size()==size && size!=0)
                return iter;
            if (iter->key().size() > size && (best==imap.nodes().end() || iter->key().size() < best->key().size()))
                best = iter;
        }
        return best;
    }
    Interval firstUnmapped(typename Interval::Value minAddr) const {
        Interval all = Interval::whole();
        for (ConstNodeIterator iter=lowerBound(minAddr); iter!=nodes().end(); ++iter) {
            if (minAddr < iter->key().least())          // minAddr is not mapped
                return Interval::hull(minAddr, iter->key().least()-1);
            if (iter->key().greatest() == all.greatest())
                return Interval();                      // no unmapped addresses, prevent potential overflow in next statement
            minAddr = iter->key().greatest() + 1;
        }
        return Interval::hull(minAddr, all.greatest());
    }

    Interval lastUnmapped(typename Interval::Value maxAddr) const {
        Interval all = Interval::whole();
        for (ConstNodeIterator iter=findPrior(maxAddr); iter!=nodes().begin(); --iter) {
            if (maxAddr > iter->key().greatest())        // maxAddr is not mapped
                return Interval::hull(iter->key().greatest()+1, maxAddr);
            if (iter->key().least() == all.least())
                return Interval();                      // no unmapped address, prevent potential overflow in next statement
            maxAddr = iter->key().least() - 1;
        }
        return Interval::hull(all.least(), maxAddr);
    }

    bool exists(const typename Interval::Value &size) const {
        return find(size)!=nodes().end();
    }
    
    //                                  Accessors
public:
    const Value& operator[](const typename Interval::Value &scalar) const {
        ConstNodeIterator found = find(scalar);
        if (found==nodes().end())
            throw std::domain_error("key lookup failure; key is not in map domain");
        return found->value();
    }

    const Value& get(const typename Interval::Value &scalar) const {
        ConstNodeIterator found = find(scalar);
        if (found==nodes().end())
            throw std::domain_error("key lookup failure; key is not in map domain");
        return found->value();
    }
    Optional<Value> getOptional(const typename Interval::Value &scalar) const {
        ConstNodeIterator found = find(scalar);
        return found == nodes().end() ? Optional<Value>() : Optional<Value>(found->value());
    }
    
    Value& getOrElse(const typename Interval::Value &scalar, Value &dflt) {
        NodeIterator found = find(scalar);
        return found == nodes().end() ? dflt : found->value();
    }
    const Value& getOrElse(const typename Interval::Value &scalar, const Value &dflt) const {
        ConstNodeIterator found = find(scalar);
        return found == nodes().end() ? dflt : found->value();
    }
    const Value& getOrDefault(const typename Interval::Value &scalar) const {
        static const Value dflt;
        ConstNodeIterator found = find(scalar);
        return found==nodes().end() ? dflt : found->value();
    }
    
    //                                  Capacity
public:

    bool isEmpty() const {
        return map_.isEmpty();
    }

    size_t nIntervals() const {
        return map_.size();
    }

    typename Interval::Value size() const {
        return size_;
    }

    typename Interval::Value least() const {
        ASSERT_forbid(isEmpty());
        return map_.keys().begin()->least();
    }

    typename Interval::Value greatest() const {
        ASSERT_forbid(isEmpty());
        ConstIntervalIterator last = map_.keys().end(); --last;
        return last->greatest();
    }

    Optional<typename Interval::Value> least(typename Interval::Value lowerLimit) const {
        ConstNodeIterator found = lowerBound(lowerLimit); // first node ending at or after lowerLimit
        if (found==nodes().end())
            return Nothing();
        return std::max(lowerLimit, found->key().least());
    }

    Optional<typename Interval::Value> greatest(typename Interval::Value upperLimit) const {
        ConstNodeIterator found = findPrior(upperLimit); // last node beginning at or before upperLimit
        if (found==nodes().end())
            return Nothing();
        return std::min(upperLimit, found->key().greatest());
    }

    Optional<typename Interval::Value> leastUnmapped(typename Interval::Value lowerLimit) const {
        for (ConstNodeIterator iter = lowerBound(lowerLimit); iter!=nodes().end(); ++iter) {
            if (lowerLimit < iter->key().least())
                return lowerLimit;
            lowerLimit = iter->key().greatest() + 1;
            if (lowerLimit <= iter->key().least())      // sensitive to GCC optimization
                return Nothing();                       // overflow
        }
        return lowerLimit;
    }

    Optional<typename Interval::Value> greatestUnmapped(typename Interval::Value upperLimit) const {
        for (ConstNodeIterator iter = findPrior(upperLimit); iter!=nodes().end(); --iter) {
            if (upperLimit > iter->key().greatest())
                return upperLimit;
            upperLimit = iter->key().least() - 1;
            if (upperLimit >= iter->key().greatest())   // sensitive to GCC optimization
                return Nothing();                       // overflow
            if (iter==nodes().begin())
                break;
        }
        return upperLimit;
    }
    
    Interval hull() const {
        return isEmpty() ? Interval() : Interval::hull(least(), greatest());
    }


    //                                  Mutators
public:

    void clear() {
        map_.clear();
        size_ = 0;
    }

    void erase(const Interval &erasure) {
        if (erasure.isEmpty())
            return;

        // Find what needs to be removed, and create a list of things to insert, but delay actual removing until after
        // the loop since Map::erase doesn't return a next iterator.
        Map insertions;                                 // what needs to be inserted back in
        NodeIterator eraseBegin = nodes().end();
        NodeIterator iter;
        for (iter=lowerBound(erasure.least()); iter!=nodes().end() && !erasure.isLeftOf(iter->key()); ++iter) {
            Interval foundInterval = iter->key();
            Value &v = iter->value();
            if (erasure.contains(foundInterval)) {
                // erase entire found interval
                if (eraseBegin==nodes().end())
                    eraseBegin = iter;
                size_ -= foundInterval.size();
            } else if (erasure.least()>foundInterval.least() && erasure.greatest()<foundInterval.greatest()) {
                // erase the middle of the node, leaving a left and a right portion
                ASSERT_require(eraseBegin==nodes().end());
                eraseBegin = iter;
                IntervalPair rt = splitInterval(foundInterval, erasure.greatest()+1);
                Value rightValue = policy_.split(foundInterval, v /*in,out*/, rt.second.least());
                insertions.insert(rt.second, rightValue);
                IntervalPair lt = splitInterval(rt.first, erasure.least());
                policy_.truncate(rt.first, v /*in,out*/, erasure.least());
                insertions.insert(lt.first, v);
                size_ -= erasure.size();
            } else if (erasure.least() > foundInterval.least()) {
                // erase the right part of the node
                ASSERT_require(eraseBegin==nodes().end());
                eraseBegin = iter;
                IntervalPair halves = splitInterval(foundInterval, erasure.least());
                policy_.truncate(foundInterval, v /*in,out*/, erasure.least());
                insertions.insert(halves.first, v);
                size_ -= halves.second.size();
            } else if (erasure.greatest() < foundInterval.greatest()) {
                // erase the left part of the node
                if (eraseBegin==nodes().end())
                    eraseBegin = iter;
                IntervalPair halves = splitInterval(foundInterval, erasure.greatest()+1);
                Value rightValue = policy_.split(foundInterval, v /*in,out*/, halves.second.least());
                insertions.insert(halves.second, rightValue);
                size_ -= halves.first.size();
            }
        }

        // Do the actual erasing and insert the new stuff, which is easy now because we know it doesn't overlap with anything.
        if (eraseBegin!=nodes().end())
            map_.eraseAtMultiple(eraseBegin, iter);
        map_.insertMultiple(insertions.nodes());
    }

    template<typename T2, class Policy2>
    void eraseMultiple(const IntervalMap<Interval, T2, Policy2> &other) {
        ASSERT_forbid2((const void*)&other == (const void*)this, "use clear() instead");
        typedef typename IntervalMap<Interval, T2, Policy2>::ConstNodeIterator OtherIter;
        for (OtherIter oi=other.nodes().begin(); oi!=other.nodes().end(); ++oi)
            erase(oi->key());
    }

    void insert(Interval key, Value value, bool makeHole=true) {
        if (key.isEmpty())
            return;
        if (makeHole) {
            erase(key);
        } else {
            NodeIterator found = lowerBound(key.least());
            if (found!=nodes().end() && key.overlaps(found->key()))
                return;
        }

        // Attempt to merge with a left-adjoining node
        if (key.least() - 1 < key.least()) {
            NodeIterator left = find(key.least() - 1);
            if (left!=nodes().end() &&
                left->key().greatest()+1==key.least() &&
                policy_.merge(left->key(), left->value(), key, value)) {
                key = Interval::hull(left->key().least(), key.greatest());
                std::swap(value, left->value());
                size_ -= left->key().size();
                map_.eraseAt(left);
            }
        }

        // Attempt to merge with a right-adjoining node
        if (key.greatest() + 1 > key.greatest()) {
            NodeIterator right = find(key.greatest() + 1);
            if (right!=nodes().end() &&
                key.greatest()+1==right->key().least() &&
                policy_.merge(key, value, right->key(), right->value())) {
                key = Interval::hull(key.least(), right->key().greatest());
                size_ -= right->key().size();
                map_.eraseAt(right);
            }
        }

        map_.insert(key, value);
        size_ += key.size();
    }

    template<typename T2, class Policy2>
    void insertMultiple(const IntervalMap<Interval, T2, Policy2> &other, bool makeHole=true) {
        ASSERT_forbid2((const void*)&other == (const void*)this, "cannot insert a container into itself");
        typedef typename IntervalMap<Interval, T2, Policy>::ConstNodeIterator OtherIter;
        for (OtherIter oi=other.nodes().begin(); oi!=other.nodes().end(); ++oi)
            insert(oi->key(), Value(oi->value()), makeHole);
    }

// FIXME[Robb Matzke 2014-04-13]
//    // Intersection
//    void intersect(const Interval&);



    //                                  Predicates
public:
    bool overlaps(const Interval &interval) const {
        return findFirstOverlap(interval) != nodes().end();
    }
    bool isOverlapping(const Interval &interval) const {
        return overlaps(interval);
    }

    template<typename T2, class Policy2>
    bool overlaps(const IntervalMap<Interval, T2, Policy2> &other) const {
        return findFirstOverlap(nodes().begin(), other, other.nodes().begin()).first != nodes().end();
    }
    template<typename T2, class Policy2>
    bool isOverlapping(const IntervalMap<Interval, T2, Policy2> &other) const {
        return overlaps(other);
    }

    bool isDistinct(const Interval &interval) const {
        return !overlaps(interval);
    }

    template<typename T2, class Policy2>
    bool isDistinct(const IntervalMap<Interval, T2, Policy2> &other) const {
        return !overlaps(other);
    }

    bool contains(Interval key) const {
        if (key.isEmpty())
            return true;
        ConstNodeIterator found = find(key.least());
        while (1) {
            if (found==nodes().end())
                return false;
            if (key.least() < found->key().least())
                return false;
            ASSERT_require(key.overlaps(found->key()));
            if (key.greatest() <= found->key().greatest())
                return true;
            key = splitInterval(key, found->key().greatest()+1).second;
            ++found;
        }
    }

    template<typename T2, class Policy2>
    bool contains(const IntervalMap<Interval, T2, Policy2> &other) const {
        for (ConstNodeIterator iter=other.nodes().begin(); iter!=other.nodes().end(); ++iter) {
            if (!contains(iter->key()))
                return false;
        }
        return true;
    }


    //                                  Private support methods
private:
    static IntervalPair splitInterval(const Interval &interval, const typename Interval::Value &splitPoint) {
        ASSERT_forbid(interval.isEmpty());
        ASSERT_require(splitPoint > interval.least() && splitPoint <= interval.greatest());

        Interval left = Interval::hull(interval.least(), splitPoint-1);
        Interval right = Interval::hull(splitPoint, interval.greatest());
        return IntervalPair(left, right);
    }

    // a more convenient way to check whether interval contains at least size items and still handle overflow
    static bool isLarge(const Interval &interval, boost::uint64_t size) {
        return !interval.isEmpty() && (interval.size()==0 || interval.size() >= size);
    }
};

} // namespace
} // namespace

#endif