Untitled

 avatar
unknown
plain_text
a year ago
3.9 kB
31
Indexable
#include <map>
#include <iostream>
using namespace std;
template<typename K, typename V>
class interval_map {
    friend void IntervalMapTest();
    V m_valBegin;
    std::map<K,V> m_map;
public:
    void printmap() {
        std::cout << " begin = ";
        m_valBegin.print();
        std::cout << "\n";
        // m_valBegin.print();
        for (auto it = m_map.begin(); it != m_map.end(); it++) {
            K key = it->first;
            V val = it->second;
            key.print();
            val.print();
            std::cout << "\n";
        }
    }
    // constructor associates whole range of K with val
    interval_map(V const& val)
    : m_valBegin(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 ){
    if(!(keyBegin < keyEnd))
        return;

    if( m_map.empty() ){
        if( val == m_valBegin )
            return;
        m_map.insert({keyBegin, val});
        m_map.insert({keyEnd, m_valBegin});
        return;
    }


    K end_interval = m_map.rbegin()->first;
    auto iter = m_map.end();
    if( end_interval < keyEnd ){
        m_map.insert( m_map.end(), pair<K,V>( keyEnd, m_valBegin) );
        iter--;iter--;
    } else {
        iter = m_map.lower_bound(keyEnd);
        V nextIntervalValue = iter->second;
        if( !(nextIntervalValue == val) ){
            iter = m_map.insert_or_assign( iter, keyEnd, prev(iter)->second );
            iter--;
        }
    }


    while( keyBegin < iter->first  ){
        if(iter == m_map.begin()){
            m_map.erase(iter);
            break;
        }
        m_map.erase(iter--);
    }

    K begin_interval = m_map.begin()->first;
    if(keyBegin < begin_interval) {
        if( !(val == m_valBegin) )
            m_map.insert_or_assign(  m_map.begin(),keyBegin, val );
    } else {
        V previousIntervalValue = (--iter)->second;
        if( !(val == previousIntervalValue ) )
        m_map.insert_or_assign(  iter, keyBegin, val );
    }
    
}


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

// 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 int intervals to char.

#include <iostream>
struct K
{
    int c;
    bool operator< (const K& x) const {
        return c < x.c;
    }
    K* operator=(const K& x) {
        c = x.c;
        return this;
    }
    void print() {
        std::cout << " key = " << c;
    }

};
struct V {
    char c;
    bool operator< (const V& x) const {
        return c < x.c;
    }
    V* operator=(const V& x) {
        c = x.c;
        return this;
    }
    bool operator== (const V& x) const {
        return c == x.c;
    }
    void print() {
        std::cout << " value = " << c;
    }
};


int main () {   
    int x, y;
    char c;
    V v;
    v.c = 'A';
    interval_map <K, V> mp(v);
    while (std::cin >> x >> y >> c) {
        v.c = c;
        K k1, k2;
        k1.c = x;
        k2.c = y;
        mp.assign(k1, k2, v);
        mp.printmap();
    }
    return 0;
}
Editor is loading...
Leave a Comment