IntervalSetMap.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_Container_IntervalSetMap_H
#define Sawyer_Container_IntervalSetMap_H

#include <boost/foreach.hpp>
#include <Sawyer/IntervalMap.h>
#include <Sawyer/Sawyer.h>

namespace Sawyer {
namespace Container {

template<typename I, typename S>
class IntervalSetMap: public IntervalMap<I, S> {
    typedef IntervalMap<I, S> Super;
public:
    typedef I Interval;                                 
    typedef S Set;                                      
    //                                  Iterators
public:
    Set getUnion(const Interval &interval) const {
        Set retval;
        BOOST_FOREACH (const typename Super::Node &node, this->findAll(interval)) {
            BOOST_FOREACH (const typename Set::Value &member, node.value().values()) {
                retval.insert(member);
            }
        }
        return retval;
    }

    Set getIntersection(const Interval &interval) const {
        Set retval;
        size_t nNodes = 0;
        BOOST_FOREACH (const typename Super::Node &node, this->findAll(interval)) {
            const Set &set = this->get(node.key().least());
            if (1 == ++nNodes) {
                retval = set;
            } else {
                retval &= set;
            }
        }
        return retval;
    }
    
    //                                  Predicates and queries
public:
    bool exists(const Interval &interval) const {
        return Super::contains(interval);
    }

    bool existsAnywhere(const Interval &interval, const typename Set::Value &value) const {
        BOOST_FOREACH (const typename Super::Node &node, this->findAll(interval)) {
            if (node.value().exists(value))
                return true;
        }
        return false;
    }

    bool existsEverywhere(const Interval &interval, const typename Set::Value &value) const {
        if (interval.isEmpty())
            return false;
        BOOST_FOREACH (const typename Super::Node &node, this->findAll(interval)) {
            if (!node.value().exists(value))
                return false;
        }
        return true;
    }
    
    //                                  Mutators
public:

    void erase(const Interval &interval) {
        Super::erase(interval);
    }

    bool erase(const Interval &interval, const typename Set::Value &value) {
        Set set;
        set.insert(value);
        return erase(interval, set);
    }

    bool erase(const Interval &interval, const Set &values) {
        bool isErased = false;
        Interval worklist = interval;
        while (!worklist.isEmpty()) {
            typename Super::ConstNodeIterator iter = this->findFirstOverlap(worklist);
            if (iter == this->nodes().end()) {
                break;
            } else if (worklist.least() < iter->key().least()) {
                worklist = Interval::hull(iter->key().least(), worklist.greatest());
            } else {
                Interval work = worklist.intersection(iter->key());
                Set set = this->get(work.least());
                if (set.erase(values)) {
                    replace(work, set);
                    isErased = true;
                }
                if (work == worklist)
                    break;
                worklist = Interval::hull(work.greatest()+1, worklist.greatest());
            }
        }
        return isErased;
    }

    bool insert(const Interval &interval, const typename Set::Value &value) {
        Set set;
        set.insert(value);
        return insert(interval, set);
    }

    bool insert(const Interval &interval, const Set &values) {
        bool isInserted = false;
        Interval worklist = interval;
        while (!worklist.isEmpty()) {
            typename Super::ConstNodeIterator iter = this->findFirstOverlap(worklist);
            Set set;
            Interval work;
            if (iter == this->nodes().end()) {
                work = worklist;
            } else if (worklist.least() < iter->key().least()) {
                work = Interval::hull(worklist.least(), iter->key().least() - 1);
            } else {
                work = worklist.intersection(iter->key());
                set = this->get(work.least());
            }
            if (set.insert(values)) {
                Super::insert(work, set);
                isInserted = true;
            }
            if (work == worklist)
                break;
            worklist = Interval::hull(work.greatest()+1, worklist.greatest());
        }
        return isInserted;
    }
    
    void replace(const Interval &interval, const Set &set) {
        if (set.isEmpty()) {
            Super::erase(interval);
        } else {
            Super::insert(interval, set);
        }
    }
};

} // namespace
} // namespace

#endif