Untitled

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


using namespace std;

template<typename K, typename V>
class interval_map {
	friend void IntervalMapTest();
	V m_valBegin;
	std::map<K,V> m_map;
	std::map<K,V> validation_map;
public:
	// constructor associates whole range of K with val
	template<typename V_forward>
	interval_map(V_forward&& val)
	: m_valBegin(std::forward<V_forward>(val))
	{
	    for (K key = -1000; key < 1000; key++) {
	        validation_map[key] = 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.
	// 1 operation Log(n) - Rest O(1) - use forward
	template<typename V_forward>
	void assign( K const& keyBegin, K const& keyEnd, V_forward&& val )
		requires (std::is_same<std::remove_cvref_t<V_forward>, V>::value)
	{
	    for (K key = keyBegin; key < keyEnd; key++) {
	        validation_map[key] = val;
	    }
	    
        if (!(keyBegin < keyEnd)) return;

        auto itBegin = m_map.lower_bound(keyBegin); //log(n)
        V valCurr = itBegin->second;
        
        if (keyBegin < itBegin->first) {
            if (itBegin == m_map.begin()) {
                valCurr = m_valBegin;
            } else {
                valCurr = (--itBegin)->second;
            }
        }
        
        auto itDelBegin = m_map.insert_or_assign(itBegin, keyBegin, val);
        if (itDelBegin == m_map.begin()) {
            if (!(val == m_valBegin)) {
                ++itDelBegin;
            }
        } else {
            if (!((--itDelBegin)->second == val)) {
                ++itDelBegin;
            }
            ++itDelBegin;
        }
        
        auto itCurr = itDelBegin;
        while (itCurr != m_map.end()) {
            if (keyEnd < itCurr->first) {
                break;
            }
            valCurr = itCurr->second;
            itCurr = m_map.erase(itCurr);
        }
        auto itEnd = m_map.insert(itCurr, std::pair<K,V>(keyEnd, valCurr));
        auto itEndTmp = itEnd;
        if ((itEnd != m_map.end()) && ((++itEnd)->second == valCurr)) {
            m_map.erase(itEnd);
        }
        if ((--itEndTmp)->second == valCurr) {
            m_map.erase(++itEndTmp);
        }
	}

	// 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;
		}
	}
	
	void print() {	    
	    for (auto p : m_map) {
            cout << "{" << p.first << ", " << p.second << "}, ";
        }
        cout << endl;
        auto prev = m_map.begin();
        if (m_map.begin() != m_map.end()) {
            for (auto it = (++m_map.begin()); it != m_map.end(); ++it) {
                if (it->second == prev->second) cout << "wrong ..." << endl;
                ++prev;
            }
        }
	}
};


// lower_bound: Returns an iterator pointing to the first element in the container whose key is not considered to go before k (i.e., either it is equivalent or goes after).
// An iterator to the the first element in the container whose key is not considered to go before k, or map::end if all keys are considered to go before k.


// upper_bound : Returns an iterator pointing to the first element in the container whose key is considered to go after k.
// An iterator to the the first element in the container whose key is considered to go after k, or map::end if no keys are considered to go after k.

// 

// 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.

void IntervalMapTest() {
    interval_map<int, char> internalMap('a');
    internalMap.print();
    std::random_device rd;
    std::mt19937 gen(rd());
    std::uniform_int_distribution<int> intDist(1, 100);  // Range for a and b
    std::uniform_int_distribution<char> charDist('a', 'z'); // Range for c

    for (int i = 0; i < 1000; ++i) {
        int a = 0, b = 0;
        char c;
        while(a >= b) {
            a = intDist(gen);
            b = intDist(gen);
            c = charDist(gen);
        }

        std::cout << "Set " << i + 1 << ": (" << a << ", " << b << ", " << c << ")\n";
        
        internalMap.assign(a, b, c);
        internalMap.print();
        for(int i =-100; i< 100; ++i)
            if (!(internalMap[i] == internalMap.validation_map[i])) {
                cout << i << " Wrong ....." << internalMap[i] << " " << internalMap.validation_map[i]<< endl;
            }
    }
}

int main()
{
    IntervalMapTest();
    return 0;
}