interval_map.cpp

#include <map>
#include <limits>
#include <random>
#include <iostream>
#include <cstdlib>

template<typename K, typename V>
class interval_map {
	std::map<K,V> m_map;

public:
    // constructor associates whole range of K with val by inserting (K_min, val)
    // into the map
    interval_map( V const& val) {
        m_map.insert(m_map.end(),std::make_pair(std::numeric_limits<K>::lowest(),val));
    }

    // Assign value val to interval [keyBegin, keyEnd).
    // Overwrite previous values in this interval.
    // Conforming to the C++ Standard Library conventions, the interval
    // includes keyBegin, but excludes keyEnd.
    // If !( keyBegin < keyEnd ), this designates an empty interval,
    // and assign must do nothing.
    void assign( K const& keyBegin, K const& keyEnd, V const& val ) {
       	using namespace std;

        if ( !( keyBegin < keyEnd ) )
            return;

        auto oldVal = m_map.rbegin()->second;
        auto intervalBegin = m_map.insert_or_assign( keyBegin, val ).first;
        auto intervalEnd = m_map.lower_bound( keyEnd );

        if ( intervalEnd != m_map.end() ) {
            if ( keyEnd < intervalEnd->first ) {
                --intervalEnd;
                if ( intervalEnd != m_map.begin() && intervalEnd->second == val )
                    --intervalEnd;
            }
            intervalEnd = m_map.insert( intervalEnd, make_pair( keyEnd, intervalEnd->second ) );
        } else {
            intervalEnd = m_map.insert( intervalEnd, make_pair( keyEnd, oldVal ) );
        }

        m_map.erase( ++intervalBegin, intervalEnd );
    }

    // look-up of the value associated with key
    V const& operator[]( K const& key ) const {
        return ( --m_map.upper_bound(key) )->second;
    }

    void print_map() const {
        using namespace std;
        for (auto kv: m_map) {
            cout << kv.first << "=" << int(kv.second) << " ";
        }
        cout << endl;
    }
};

// Many solutions we receive are incorrect. Consider using a randomized test
// to discover the cases that your implementation does not handle correctly.
// We recommend to implement a test function that tests the functionality of
// the interval_map, for example using a map of unsigned int intervals to char.

template<typename K, typename V>
void verify(const K &b, const K &e, const K &i, const V &ret, const V &v, int line) {
    using namespace std;
    if (ret != v) {
        cerr << "error(" << line << ") (" << b << ", " << e << "] " << "for key=" << i << " " << int(ret) << "!=" << int(v) << endl;
        exit(EXIT_FAILURE);
    }
}

#define VERIFY(b, e, i, ret, v) do { \
    verify((b), (e), (i), (ret), (v), __LINE__); \
} while (false)

int main() {
    using namespace std;

    using key_type = unsigned int;
    using val_type = unsigned char;

    interval_map<key_type, val_type> im( 'A' );

    default_random_engine generator;
    uniform_int_distribution<key_type> kdist(numeric_limits<key_type>::lowest(), 100);
    uniform_int_distribution<val_type> vdist(numeric_limits<val_type>::lowest(), numeric_limits<val_type>::max());

    auto pk = make_pair(numeric_limits<key_type>::lowest(), key_type(2U));
    auto pv = val_type('A');
    im.print_map();

    for (;;)  {
        auto k = make_pair(kdist(generator), kdist(generator));
        auto v = vdist(generator);

        if ( k.second < k.first )
            swap(k.first, k.second);

        im.assign(k.first, k.second, v);
        cout << "Testing k=(" << k.first << ", " << k.second << "] pk=(" << pk.first << ", " << pk.second << "] v=" << int(v) << " pv=" << int(pv) << endl;
        im.print_map();

        VERIFY(k.first, k.second, 101U, im[101], val_type('A'));

        for (auto i = k.first; i < k.second; ++i)
            VERIFY(k.first, k.second, i, im[i], v);

        // out of the interval
        if (pk.first > k.second || pk.second < k.first)
            for (auto i = pk.first; i < pk.second; ++i)
                VERIFY(pk.first, pk.second, i, im[i], pv);

        // outside
        if (pk.first >= k.first && pk.second <= k.second)
            for (auto i = pk.first; i < pk.second; ++i)
                VERIFY(pk.first, pk.second, i, im[i], v);

        // inside
        if (k.first > pk.first && k.second < pk.second) {
            for (auto i = pk.first; i < k.first; ++i)
                VERIFY(pk.first, k.first, i, im[i], pv);

            for (auto i = k.second; i < pk.second; ++i)
                VERIFY(k.second, pk.second, i, im[i], pv);
        }

        if (k.first < pk.first && pk.second > k.first && pk.second < k.second)
            for (auto i = k.second; i < pk.second; ++i)
                VERIFY(k.second, pk.second, i, im[i], pv);

        if (k.first > pk.first && k.first < pk.second && k.second > pk.second)
            for (auto i = pk.second; i < k.second; ++i)
                VERIFY(pk.second, k.second, i, im[i], v);

        pk = k;
        pv = v;
    }

    return 0;
}