rangemap.h

Go to the documentation of this file.

#ifndef ROSE_RANGEMAP_H
#define ROSE_RANGEMAP_H

/* This file defines four main template classes:
 *    - RangeMap:      Time and space efficient storage of non-overlapping Range objects each associated with an arbitrary value.
 *    - Range:         Contiguous set of integers defined by the starting value and size.
 *    - RangeMapVoid:  Void value for RangeMap classes that don't store any useful value (just the ranges themselves).
 *    - RangeMapValue: Class for storing simple values in a RangeMap.
 */


/* There is no need to include "sage3basic.h"; this file defines all it needs. */

#ifndef __STDC_FORMAT_MACROS
#define __STDC_FORMAT_MACROS
#endif
#include <inttypes.h>

#include <cassert>
#include <cmath>
#include <cstdlib>
#include <iostream>
#include <map>
#include <sstream>
#include <string>
#include <vector>

/* Define this if you want the class to do fairly extensive testing of the consistency of the map after every operation.  Note
 * that this substantially increases execution time.  The NDEBUG preprocessor symbol must not be defined, or else the check()
 * method won't really do anything. */
//#define RANGEMAP_CHECK

/******************************************************************************************************************************
 *                                      Range<>
 ******************************************************************************************************************************/

template<class T>
class Range {
public:
    typedef T Value;
    typedef std::pair<Range, Range> Pair;               
protected:
    Value r_first;                                      
    Value r_last;                                       
public:
    Range()
        : r_first(1), r_last(0) {} // see clear()

    explicit Range(const Value &first)
        : r_first(first), r_last(first) {}

    Range(const Value &first, const Value &size)
        : r_first(first), r_last(first+size-1) {
        if (0==size) {
            r_last = first; // or else clear() is a no-op leaving invalid values
            clear();
        } else {
            assert(!empty()); // checks for overflow
        }
    }

    template<class Other>
    explicit Range(const Other &other)
        : r_first(other.relaxed_first()), r_last(other.relaxed_last()) {}

    static Range inin(const Value &v1, const Value &v2) {
        assert(v1<=v2);
        Range retval;
        retval.first(v1);
        retval.last(v2);
        return retval;
    }

    void first(const Value &first) {
        r_first = first;
    }
    const Value first() const {
        assert(!empty());
        return r_first;
    }
    const Value relaxed_first() const {
        if (!empty())
            return first();
        if (1==r_first-r_last)
            return r_first-1;
        return r_first;
    }
    void last(const Value &last) {
        r_last = last;
    }
    const Value last() const {
        assert(!empty());
        return r_last;
    }
    const Value relaxed_last() const {
        return empty() ? relaxed_first() : last();
    }
    Value size() const {
        if (empty())
            return 0;
        return r_last + 1 - r_first;
    }

    void resize(const Value &new_size) {
        assert(!empty());
        if (0==new_size) {
            clear();
        } else {
            r_last = r_first + new_size - 1;
            assert(!empty()); // this one is to check for overflow of r_last
        }
    }
    void relaxed_resize(const Value &new_size) {
        if (0==new_size) {
            clear();
        } else {
            r_first = relaxed_first();
            r_last = r_first + new_size - 1;
            assert(!empty()); // this one is to check for overflow of r_last
        }
    }
    Pair split_range_at(const Value &at) const {
        assert(!empty());
        assert(at>first() && at<=last()); // neither half can be empty
        Range left(first(), at-first());
        Range right(at, last()+1-at);
        return std::make_pair(left, right);
    }

    Range join(const Range &right) const {
        if (empty())
            return right;
        if (right.empty())
            return *this;
        assert(abuts_lt(right));
        return Range::inin(first(), right.last());
    }

    std::vector<Range> erase(const Range &to_erase) const {
        std::vector<Range> retval;
        if (to_erase.empty() || distinct(to_erase)) {
            retval.push_back(*this);
        } else if (contained_in(to_erase)) {
            // void
        } else {
            if (begins_before(to_erase))
                retval.push_back(Range::inin(first(), to_erase.first()-1));
            if (ends_after(to_erase))
                retval.push_back(Range::inin(to_erase.last()+1, last()));
        }
        return retval;
    }

    Range intersect(const Range &other) const {
        if (empty() || contains(other))
            return other;
        if (other.empty() || other.contains(*this))
            return *this;
        if (!overlaps(other))
            return Range();
        return Range::inin(
        std::max(first(), other.first()),
        std::min(last(), other.last()));
    }
    
    bool empty() const {
        return r_last<r_first; // can't use first() or last() here because they're not valid for empty ranges.
    }

    void clear() {
        if (!empty()) {
            if (r_first<maximum()) {
                r_first = r_first + 1;
                r_last = r_first - 1;
            } else {
                r_last = r_first - 2;
            }
            assert(empty());
        }
    }

    bool begins_with(const Range &x) const {
        if (empty() || x.empty())
            return false;
        return first() == x.first();
    }

    bool ends_with(const Range &x) const {
        if (empty() || x.empty())
            return false;
        return last() == x.last();
    }

    bool begins_after(const Range &x, bool strict=true) const {
        if (empty() || x.empty())
            return false;
        return strict ? first() > x.first() : first() >= x.first();
    }

    bool begins_before(const Range &x, bool strict=true) const {
        if (empty() || x.empty())
            return false;
        return strict ? first() < x.first() : first() <= x.first();
    }

    bool ends_after(const Range &x, bool strict=true) const {
        if (empty() || x.empty())
            return false;
        return strict ? last() > x.last() : last() >= x.last();
    }

    bool ends_before(const Range &x, bool strict=true) const {
        if (empty() || x.empty())
            return false;
        return strict ? last() < x.last() : last() <= x.last();
    }

    bool contains(const Range &x, bool strict=false) const {
        if (empty() || x.empty())
            return false;
        return strict ? x.first()>first() && x.last()<last() : x.first()>=first() && x.last()<=last();
    }

    bool contained_in(const Range &x, bool strict=false) const {
        if (empty() || x.empty())
            return false;
        return strict ? first()>x.first() && last()<x.last() : first()>=x.first() && last()<=x.last();
    }

    bool congruent(const Range &x) const {
        if (empty() || x.empty())
            return empty() && x.empty();
        return first()==x.first() && last()==x.last();
    }

    bool left_of(const Range &x) const {
        if (empty() || x.empty())
            return false;
        return last() < x.first();
    }

    bool right_of(const Range &x) const {
        if (empty() || x.empty())
            return false;
        return first() > x.last();
    }

    bool overlaps(const Range &x) const {
        if (empty() || x.empty())
            return false;
        return !left_of(x) && !right_of(x);
    }

    bool distinct(const Range &x) const {
        if (empty() || x.empty())
            return true;
        return !overlaps(x);
    }

    bool abuts_lt(const Range &x) const {
        if (empty() || x.empty())
            return false;
        return last()+1 == x.first();
    }

    bool abuts_gt(const Range &x) const {
        if (empty() || x.empty())
            return false;
        return first() == x.last()+1;
    }

    static Value minimum() {
        return 0; // FIXME
    }

    static Value maximum() {
        return (Value)(-1); // FIXME
    }

    static Range all() {
        return Range::inin(minimum(), maximum());
    }

    bool operator==(const Range &x) const {
        return congruent(x);
    }
    bool operator!=(const Range &x) const {
        return !congruent(x);
    }
    
    void print(std::ostream &o) const {
        if (empty()) {
            o <<"<empty>";
        } else if (first()==last()) {
            o <<first();
        } else {
            o <<first() <<".." <<last();
        }
    }

    friend std::ostream& operator<<(std::ostream &o, const Range &x) {
        x.print(o);
        return o;
    }
};

/******************************************************************************************************************************
 *                                      Specializations for Range<double>
 ******************************************************************************************************************************/

template<>
Range<double>::Range();

template<>
bool
Range<double>::empty() const;

template<>
void
Range<double>::clear();

template<>
const double
Range<double>::relaxed_first() const;

template<>
double
Range<double>::size() const;

template<>
void
Range<double>::resize(const double &new_size);

template<>
void
Range<double>::relaxed_resize(const double &new_size);

template<>
Range<double>::Pair
Range<double>::split_range_at(const double &at) const;

template<>
double
Range<double>::minimum();

template<>
double
Range<double>::maximum();

/******************************************************************************************************************************
 *                                      Specializations for Range<float>
 ******************************************************************************************************************************/

template<>
Range<float>::Range();

template<>
bool
Range<float>::empty() const;

template<>
void
Range<float>::clear();

template<>
const float
Range<float>::relaxed_first() const;

template<>
float
Range<float>::size() const;

template<>
void
Range<float>::resize(const float &new_size);

template<>
void
Range<float>::relaxed_resize(const float &new_size);

template<>
Range<float>::Pair
Range<float>::split_range_at(const float &at) const;

template<>
float
Range<float>::minimum();

template<>
float
Range<float>::maximum();

/******************************************************************************************************************************
 *                                      RangeMap void values
 ******************************************************************************************************************************/

template<class R>
class RangeMapVoid {
public:
    typedef R Range;

    RangeMapVoid() {}

    template<class Other>
    explicit RangeMapVoid(const Other&) {}

    void removing(const Range &my_range) {
        assert(!my_range.empty());
    }

    void truncate(const Range &my_range, const typename Range::Value &new_end) {
        assert(new_end>my_range.first() && new_end<=my_range.last());
    }

    bool merge(const Range &my_range, const Range &other_range, const RangeMapVoid &other_value) {
        assert(!my_range.empty() && !other_range.empty());
        return true;
    }

    RangeMapVoid split(const Range &my_range, const typename Range::Value &new_end) {
        assert(my_range.contains(Range(new_end)));
        return RangeMapVoid();
    }

    void print(std::ostream &o) const {}
    friend std::ostream& operator<<(std::ostream &o, const RangeMapVoid &x) {
        x.print(o);
        return o;
    }
};

/******************************************************************************************************************************
 *                                      RangeMap numeric values
 ******************************************************************************************************************************/

template<class R, class T>
class RangeMapNumeric /*final*/ {
public:
    typedef R Range;
    typedef T Value;

    RangeMapNumeric(): value(0) {}

    RangeMapNumeric(Value v): value(v) {} // implicit
    
    void set(Value v) /*final*/ {
        value = v;
    }
    virtual Value get() const /*final*/ {
        return value;
    }
    void removing(const Range &my_range) /*final*/ {
        assert(!my_range.empty());
    }

    void truncate(const Range &my_range, const typename Range::Value &new_end) /*final*/ {
        assert(new_end>my_range.first() && new_end<=my_range.last());
    }

    bool merge(const Range &my_range, const Range &other_range, RangeMapNumeric other_value) /*final*/ {
        assert(!my_range.empty() && !other_range.empty());
        return get()==other_value.get();
    }

    RangeMapNumeric split(const Range &my_range, typename Range::Value new_end) /*final*/ {
        assert(my_range.contains(Range(new_end)));
        return *this;
    }

    void print(std::ostream &o) const /*final*/ {
        o <<value;
    }
    friend std::ostream& operator<<(std::ostream &o, const RangeMapNumeric &x) {
        x.print(o);
        return o;
    }
private:
    Value value;
};

/******************************************************************************************************************************
 *                                      RangeMap simple values
 ******************************************************************************************************************************/

template<class R, class T>
class RangeMapValue {
public:
    typedef R Range;
    typedef T Value;

    RangeMapValue() {}

    RangeMapValue(const Value &v) { // implicit
        value = v;
    }

    /* This class often serves as a base class, so we have some virtual methods. */
    virtual ~RangeMapValue() {}
    

    virtual void set(const Value &v) {
        value = v;
    }
    virtual Value get() const {
        return value;
    }
    virtual void removing(const Range &my_range) {
        assert(!my_range.empty());
    }

    virtual void truncate(const Range &my_range, const typename Range::Value &new_end) {
        assert(new_end>my_range.first() && new_end<=my_range.last());
    }

    bool merge(const Range &my_range, const Range &other_range, const RangeMapValue &other_value) {
        assert(!my_range.empty() && !other_range.empty());
        return get()==other_value.get();
    }

#if 0 /* Must be implemented in the subclass due to return type. */

    RangeMapValue split(const Range &my_range, const typename Range::Value &new_end) {
        assert(my_range.contains(Range(new_end)));
        return *this;
    }
#endif

    virtual void print(std::ostream &o) const {
        o <<value;
    }
    friend std::ostream& operator<<(std::ostream &o, const RangeMapValue &x) {
        x.print(o);
        return o;
    }
protected:
    Value value;
};

/******************************************************************************************************************************
 *                                      RangeMap<>
 ******************************************************************************************************************************/

template<class R, class T=RangeMapVoid<R> >
class RangeMap {
public:
    typedef R Range;                    
    typedef T Value;                    
protected:
    /* The keys of the underlying map are sorted by their last value rather than beginning value.  This allows us to use the
     * map's lower_bound() method to find the range to which an address might belong.  Since the ranges in the map are
     * non-overlapping, sorting by ending address has the same effect as sorting by starting address. */
    struct RangeCompare {
        bool operator()(const Range &a, const Range &b) const {
            return a.last() < b.last();
        }
    };

    typedef std::pair<Range, Range> RangePair;
    typedef std::pair<Range, Value> MapPair;
    typedef std::map<Range, Value, RangeCompare> Map;
    Map ranges;

public:
    typedef typename Map::iterator iterator;
    typedef typename Map::const_iterator const_iterator;
    typedef typename Map::reverse_iterator reverse_iterator;
    typedef typename Map::const_reverse_iterator const_reverse_iterator;

    /**************************************************************************************************************************
     *                                  Constructors
     **************************************************************************************************************************/
public:

    RangeMap() {}

    template<class Other>
    explicit RangeMap(const Other &other) {
        for (typename Other::const_iterator ri=other.begin(); ri!=other.end(); ++ri) {
            Range new_range(ri->first);
            Value new_value(ri->second);
            insert(new_range, new_value);
        }
    }

    /**************************************************************************************************************************
     *                                  Iterators and searching
     **************************************************************************************************************************/
public:

    iterator begin() {
        return ranges.begin();
    }
    const_iterator begin() const {
        return ranges.begin();
    }
    iterator end() {
        return ranges.end();
    }
    const_iterator end() const {
        return ranges.end();
    }
    reverse_iterator rbegin() {
        return ranges.rbegin();
    }
    const_reverse_iterator rbegin() const {
        return ranges.rbegin();
    }
    reverse_iterator rend() {
        return ranges.rend();
    }
    const_reverse_iterator rend() const {
        return ranges.rend();
    }
    iterator find(const typename Range::Value &addr) {
        iterator ei = lower_bound(addr);
        if (ei==end() || Range(addr).left_of(ei->first))
            return end();
        return ei;
    }
    const_iterator find(const typename Range::Value &addr) const {
        const_iterator ei = lower_bound(addr);
        if (ei==end() || Range(addr).left_of(ei->first))
            return end();
        return ei;
    }
    iterator lower_bound(const typename Range::Value &addr) {
        return ranges.lower_bound(Range(addr));
    }
    const_iterator lower_bound(const typename Range::Value &addr) const {
        return ranges.lower_bound(Range(addr));
    }
    iterator find_prior(const typename Range::Value &addr) {
        if (empty())
            return end();
        iterator lb = lower_bound(addr);
        if (lb!=end() && lb->first.begins_before(Range(addr), false/*non-strict*/))
            return lb;
        if (lb==begin())
            return end();
        return --lb;
    }
    const_iterator find_prior(const typename Range::Value &addr) const {
        if (empty())
            return end();
        const_iterator lb = lower_bound(addr);
        if (lb!=end() && lb->first.begins_before(Range(addr), false/*non-strict*/))
            return lb;
        if (lb==begin())
            return end();
        return --lb;
    }
    iterator best_fit(const typename Range::Value &size, iterator start) {
        iterator best = end();
        for (iterator ri=start; ri!=end(); ++ri) {
            if (ri->first.size()==size)
                return ri;
            if (ri->first.size()>size && (best==end() || ri->first.size()<best->first.size()))
                best = ri;
        }
        return best;
    }
    const_iterator best_fit(const typename Range::Value &size, const_iterator start) const {
        const_iterator best = end();
        for (const_iterator ri=start; ri!=end(); ++ri) {
            if (ri->first.size()==size)
                return ri;
            if (ri->first.size()>size && (best==end() || ri->first.size()<best->first.size()))
                best = ri;
        }
        return best;
    }
    iterator first_fit(const typename Range::Value &size, iterator start) {
        for (iterator ri=start; ri!=end(); ++ri) {
            if (ri->first.size()>=size)
                return ri;
        }
        return end();
    }
    const_iterator first_fit(const typename Range::Value &size, const_iterator start) {
        for (const_iterator ri=start; ri!=end(); ++ri) {
            if (ri->first.size()>=size)
                return ri;
        }
        return end();
    }
    /**************************************************************************************************************************
     *                                  Capacity
     **************************************************************************************************************************/
public:

    bool empty() const {
        return ranges.empty();
    }

    size_t nranges() const {
        return ranges.size();
    }

    typename Range::Value size() const {
        typename Range::Value retval = 0;
        for (const_iterator ei=begin(); ei!=end(); ++ei)
            retval += ei->first.size();
        return retval;
    }

    typename Range::Value min() const {
        assert(!empty());
        return ranges.begin()->first.first();
    }

    typename Range::Value max() const {
        assert(!empty());
        return ranges.rbegin()->first.last();
    }

    Range minmax() const {
        typename Range::Value lt=min(), rt=max();
        return Range::inin(lt, rt);
    }

    /**************************************************************************************************************************
     *                                  Low-level support functions
     **************************************************************************************************************************/
protected:

    /**************************************************************************************************************************
     *                                  Modifiers
     **************************************************************************************************************************/
public:

    void clear(bool notify=true) {
        if (notify) {
            for (iterator ei=begin(); ei!=end(); ++ei)
                ei->second.removing(ei->first);
        }
        ranges.clear();
    }

    void erase(const Range &erase_range) {
        /* This loop figures out what needs to be removed and calls the elements' removing(), truncate(), etc. methods but does
         * not actually erase them from the underlying map yet.  We must not erase them yet because the std::map::erase()
         * method doesn't return any iterator.  Instead, we create a list (via an iterator range) of elements that will need to
         * be erased from the underlying map.
         *
         * This loop also creates a list of items that need to be inserted into the underlying map.  Even though the
         * std::map::insert() can return an iterator, we can't call it inside the loop because then our erasure iterators will
         * become invalid. */
        if (erase_range.empty())
            return;
        Map insertions;
        iterator erase_begin=end();
        iterator ei;
        for (ei=lower_bound(erase_range.first()); ei!=end() && !erase_range.left_of(ei->first); ++ei) {
            Range found_range = ei->first;
            Value &v = ei->second;
            if (erase_range.contains(found_range)) {
                /* Erase entire found range. */
                if (erase_begin==end())
                    erase_begin = ei;
                v.removing(found_range);
            } else if (erase_range.contained_in(found_range, true/*strict*/)) {
                /* Erase middle of found range. */
                assert(erase_begin==end());
                erase_begin = ei;
                RangePair rt = found_range.split_range_at(erase_range.last()+1);
                insertions[rt.second] = v.split(found_range, rt.second.first());
                RangePair lt = rt.first.split_range_at(erase_range.first());
                v.truncate(rt.first, erase_range.first());
                insertions[lt.first] = v;
            } else if (erase_range.begins_after(found_range, true/*strict*/)) {
                /* Erase right part of found range. */
                assert(erase_begin==end());
                erase_begin = ei;
                RangePair halves = found_range.split_range_at(erase_range.first());
                v.truncate(found_range, erase_range.first());
                insertions[halves.first] = v;
            } else if (erase_range.ends_before(found_range, true/*strict*/)) {
                /* Erase left part of found range. */
                if (erase_begin==end())
                    erase_begin = ei;
                RangePair halves = found_range.split_range_at(erase_range.last()+1);
                insertions[halves.second] = v.split(found_range, halves.second.first());
                v.removing(halves.first);
            }
        }

        /* Inserting is easy here because we already know that no merging is necessary. */
        if (erase_begin!=end())
            ranges.erase(erase_begin, ei);
        ranges.insert(insertions.begin(), insertions.end());
#ifdef RANGEMAP_CHECK
        check();
#endif
    }

    template<class OtherMap>
    void erase_ranges(const OtherMap &other) {
        assert((const void*)&other!=(const void*)this);
        for (typename OtherMap::const_iterator ri=other.begin(); ri!=other.end(); ++ri)
            erase(Range::inin(ri->first.first(), ri->first.last()));
    }

    iterator insert(Range new_range, Value new_value=Value(), bool make_hole=true) {
        if (new_range.empty())
            return end();

        if (make_hole) {
            erase(new_range);
        } else {
            iterator found = lower_bound(new_range.first());
            if (found!=end() && new_range.overlaps(found->first))
                return end();
        }

        /* Attempt to merge with a left and/or right value. */
        iterator left = new_range.first()>Range::minimum() ? find(new_range.first()-1) : end();
        if (left!=end() && new_range.abuts_gt(left->first) && new_value.merge(new_range, left->first, left->second)) {
            new_range = left->first.join(new_range);
            ranges.erase(left);
        }
        iterator right = new_range.last()<new_range.maximum() ? find(new_range.last()+1) : end();
        if (right!=end() && new_range.abuts_lt(right->first) && new_value.merge(new_range, right->first, right->second)) {
            new_range = new_range.join(right->first);
            ranges.erase(right);
        }

        iterator retval = ranges.insert(end(), std::make_pair(new_range, new_value));
#ifdef RANGEMAP_CHECK
        check();
#endif
        return retval;
    }

    void insert_ranges(const RangeMap &x, bool make_hole=true) {
        assert(&x!=this);
        insert_ranges(x.begin(), x.end(), make_hole);
    }

    void insert_ranges(const_iterator start, const_iterator stop, bool make_hole=true) {
        for (const_iterator ri=start; ri!=stop; ri++)
            insert(ri->first, ri->second, make_hole);
    }

    /**************************************************************************************************************************
     *                                  Predicates
     **************************************************************************************************************************/
public:

    bool overlaps(const RangeMap &x) const {
        return first_overlap(x)!=end();
    }

    bool overlaps(const Range &r) const {
        if (r.empty())
            return false;
        const_iterator found = lower_bound(r.first());
        return found!=end() && r.overlaps(found->first);
    }

    bool distinct(const Range &r) const {
        return !overlaps(r);
    }

    bool distinct(const RangeMap &x) const {
        return first_overlap(x)==end();
    }

    bool contains(Range need) const {
        if (need.empty())
            return true;
        const_iterator found=find(need.first());
        while (1) {
            if (found==end())
                return false;
            if (need.begins_before(found->first))
                return false;
            assert(need.overlaps(found->first));
            if (need.ends_before(found->first, false/*non-strict*/))
                return true;
            need = need.split_range_at(found->first.last()+1).second;
            ++found;
        }
        assert(!"should not be reached");
        return true;
    }

    bool contains(const RangeMap &x) const {
        if (x.empty())
            return true;
        for (const_iterator xi=x.begin(); xi!=x.end(); ++xi) {
            if (!contains(xi->first))
                return false;
        }
        return true;
    }

    /**************************************************************************************************************************
     *                                  Comparisons
     **************************************************************************************************************************/
public:

    iterator find_overlap(const RangeMap &x) {
        return find_overlap(begin(), end(), x);
    }
    const_iterator first_overlap(const RangeMap &x) const {
        return find_overlap(begin(), end(), x);
    }
    iterator find_overlap(iterator start, iterator stop, const RangeMap &x) {
        if (start==stop)
            return end();

        iterator ia = start;
        const_iterator ib = x.lower_bound(start->first.first());
        while (ia!=stop && ib!=x.end() && ia->first.distinct(ib->first)) {
            while (ia!=stop && ia->first.left_of(ib->first))
                ++ia;
            while (ib!=x.end() && ib->first.left_of(ia->first))
                ++ib;
        }

        return ia!=stop && ib!=x.end() && ia->first.overlaps(ib->first);
    }
    const_iterator find_overlap(const_iterator start, const_iterator stop, const RangeMap &x) const {
        if (start==stop)
            return end();

        const_iterator ia = start;
        const_iterator ib = x.lower_bound(start->first.first());
        while (ia!=stop && ib!=x.end() && ia->first.distinct(ib->first)) {
            while (ia!=stop && ia->first.left_of(ib->first))
                ++ia;
            while (ib!=x.end() && ib->first.left_of(ia->first))
                ++ib;
        }

        return ia!=stop && ib!=x.end() && ia->first.overlaps(ib->first) ? ia : end();
    }
    /**************************************************************************************************************************
     *                                  Operators
     **************************************************************************************************************************/
public:

    template<class ResultMap>
    ResultMap invert() const {
        return invert_within<ResultMap>(Range::all());
    }

    template<class ResultMap>
    ResultMap invert_within(const Range &limits) const {
        ResultMap retval;
        if (limits.empty())
            return retval;
        typename Range::Value pending = limits.first();
        for (const_iterator ri=lower_bound(limits.first()); ri!=end() && !limits.left_of(ri->first); ++ri) {
            if (pending < ri->first.first())
                retval.insert(Range::inin(pending, ri->first.first()-1));
            pending = ri->first.last()+1;
        }
        if (pending <= limits.last())
            retval.insert(Range::inin(pending, limits.last()));
        if (!retval.empty())
            assert(retval.minmax().contained_in(limits, false));
        return retval;
    }

    RangeMap select_overlapping_ranges(const Range &selector) const {
        RangeMap retval;
        if (!selector.empty()) {
            for (const_iterator ri=lower_bound(selector.start()); ri!=end() && !selector.left_of(ri->first); ++ri) {
                if (selector.overlaps(ri->first))
                    retval.insert(ri->first, ri->second);
            }
        }
        return retval;
    }

    /**************************************************************************************************************************
     *                                  Debugging
     **************************************************************************************************************************/
public:

    void check() const {
// DQ (11/8/2011): Commented out as part of ROSE compiling this ROSE source code (EDG frontend complains about errors).
#ifndef USE_ROSE
#ifndef NDEBUG
#define RANGEMAP_CHECK(EXPR) if (!(EXPR)) {                                                                                    \
            std::cerr <<"RangeMap::check() failed at r1=" <<r1 <<" r2=" <<r2 <<": " #EXPR "\n";                                \
            std::cerr <<"Entire range map at point of failure:\n";                                                             \
            print(std::cerr, "    ");                                                                                          \
            assert(EXPR);                                                                                                      \
        }
            
        for (const_iterator i1=begin(); i1!=end(); ++i1) {
            const Range &r1 = i1->first;
            const_iterator i2 = i1; ++i2;
            if (i2!=end()) {
                const Range &r2 = i2->first;

                RANGEMAP_CHECK(!r2.empty());

                RANGEMAP_CHECK(!r1.begins_with(r2));
                RANGEMAP_CHECK(!r2.begins_with(r1));

                RANGEMAP_CHECK(!r1.ends_with(r2));
                RANGEMAP_CHECK(!r2.ends_with(r1));

                RANGEMAP_CHECK(!r1.begins_after(r2, false));
                RANGEMAP_CHECK(!r1.begins_after(r2, true));
                RANGEMAP_CHECK(r2.begins_after(r1, false));
                RANGEMAP_CHECK(r2.begins_after(r1, true));

                RANGEMAP_CHECK(r1.begins_before(r2, false));
                RANGEMAP_CHECK(r1.begins_before(r2, true));
                RANGEMAP_CHECK(!r2.begins_before(r1, false));
                RANGEMAP_CHECK(!r2.begins_before(r1, true));

                RANGEMAP_CHECK(!r1.ends_after(r2, false));
                RANGEMAP_CHECK(!r1.ends_after(r2, true));
                RANGEMAP_CHECK(r2.ends_after(r1, false));
                RANGEMAP_CHECK(r2.ends_after(r1, true));

                RANGEMAP_CHECK(r1.ends_before(r2, false));
                RANGEMAP_CHECK(r1.ends_before(r2, true));
                RANGEMAP_CHECK(!r2.ends_before(r1, false));
                RANGEMAP_CHECK(!r2.ends_before(r1, true));

                RANGEMAP_CHECK(!r1.contains(r2, false));
                RANGEMAP_CHECK(!r1.contains(r2, true));
                RANGEMAP_CHECK(!r2.contains(r1, false));
                RANGEMAP_CHECK(!r2.contains(r1, true));

                RANGEMAP_CHECK(!r1.contained_in(r2, false));
                RANGEMAP_CHECK(!r1.contained_in(r2, true));
                RANGEMAP_CHECK(!r2.contained_in(r1, false));
                RANGEMAP_CHECK(!r2.contained_in(r1, true));

                RANGEMAP_CHECK(!r1.congruent(r2));
                RANGEMAP_CHECK(!r2.congruent(r1));

                RANGEMAP_CHECK(r1.left_of(r2));
                RANGEMAP_CHECK(!r2.left_of(r1));

                RANGEMAP_CHECK(!r1.right_of(r2));
                RANGEMAP_CHECK(r2.right_of(r1));

                RANGEMAP_CHECK(!r1.overlaps(r2));
                RANGEMAP_CHECK(!r2.overlaps(r1));

                RANGEMAP_CHECK(r1.distinct(r2));
                RANGEMAP_CHECK(r2.distinct(r1));

                RANGEMAP_CHECK(!r1.abuts_gt(r2)); // r1.abuts_lt(r2) is possible
                RANGEMAP_CHECK(!r2.abuts_lt(r1)); // r2.abuts_gt(r1) is possible
            }
        }
#undef RANGEMAP_CHECK
#endif
#endif
    }

    void print(std::ostream &o) const {
        for (const_iterator ri=begin(); ri!=end(); ++ri) {
            std::ostringstream s;
            s <<ri->second;
            o <<(ri==begin()?"":", ") <<ri->first;
            if (!s.str().empty())
                o <<" {" <<s.str() <<"}";
        }
    }

    friend std::ostream& operator<<(std::ostream &o, const RangeMap &rmap) {
        rmap.print(o);
        return o;
    }

};

#endif