think-cell

interval_map.cpp

/*

Task Description
interval_map<K,V> is a data structure that efficiently associates intervals of keys of type K with values of type V. Your task is to implement the assign member function of this data structure, which is outlined below.

interval_map<K, V> is implemented on top of std::map. In case you are not entirely sure which functions std::map provides, what they do and which guarantees they provide, we provide an excerpt of the C++ standard here: 

Each key-value-pair (k,v) in the std::map means that the value v is associated with the interval from k (including) to the next key (excluding) in the std::map.

Example: the std::map (0,'A'), (3,'B'), (5,'A') represents the mapping

0 -> 'A'
1 -> 'A'
2 -> 'A'
3 -> 'B'
4 -> 'B'
5 -> 'A'
6 -> 'A'
7 -> 'A'
... all the way to numeric_limits<int>::max()
The representation in the std::map must be canonical, that is, consecutive map entries must not have the same value: ..., (0,'A'), (3,'A'), ... is not allowed. Initially, the whole range of K is associated with a given initial value, passed to the constructor of the interval_map<K,V> data structure.

Key type K

besides being copyable and assignable, is less-than comparable via operator<
is bounded below, with the lowest value being std::numeric_limits<K>::lowest()
does not implement any other operations, in particular no equality comparison or arithmetic operators
Value type V

besides being copyable and assignable, is equality-comparable via operator==
does not implement any other operations
*/

#include <map>
#include <limits>
#include <ctime>

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 ) {

			if (!(keyBegin < keyEnd)) return;

			std::pair<K,V> beginExtra;
			std::pair<K,V> endExtra;
			bool beginHasExtra = false;
			bool endHasExtra = false;

			typename std::map<K,V>::const_iterator itBegin;
			itBegin = m_map.lower_bound(keyBegin);
			if ( itBegin!=m_map.end() && keyBegin < itBegin->first ) {
				if (itBegin != m_map.begin()) {
					beginHasExtra = true;
					--itBegin;
					beginExtra = std::make_pair(itBegin->first, itBegin->second);
				}
				// openRange for erase is prevIterator
				// insert (prevIterator->first, prevIterator->second) as well!
			}

			typename std::map<K,V>::const_iterator itEnd;
			itEnd = m_map.lower_bound(keyEnd);
			if ( itEnd!=m_map.end() && keyEnd < itEnd->first ) {
				endHasExtra = true;
				typename std::map<K,V>::const_iterator extraIt = itEnd;
				--extraIt;
				endExtra = std::make_pair(keyEnd, extraIt->second);
				// closeRange for erase is this iterator
				// insert (keyEnd, prevIterator->second) as well!
			}

			// 4 canonical conflicts:
			//	 beginExtra w/ mid
			//	 before-mid w/ mid (beginHasExtra==false)
			//	 mid w/ endExtra
			//	 mid w/ after-mid (endHasExtra==false)

			bool insertMid = true;
			if (beginHasExtra) {
				if (beginExtra.second == val)
					insertMid = false;
			} else {
				if (itBegin != m_map.begin()) {
					typename std::map<K,V>::const_iterator beforeMid = itBegin;
					--beforeMid;
					if (beforeMid->second == val)
						insertMid = false;
				}
			}


			if (endHasExtra) {
				if ( (insertMid && endExtra.second == val) || (!insertMid && endExtra.second == beginExtra.second) )
					endHasExtra = false;
			} else {
				if ( (insertMid && itEnd!=m_map.end() && itEnd->second == val) || (!insertMid && itEnd!=m_map.end() && itEnd->second == beginExtra.second) )
					itEnd = m_map.erase(itEnd);
			}

			itBegin = m_map.erase(itBegin, itEnd);
			if (beginHasExtra)
				itBegin = m_map.insert(itBegin, beginExtra);
			if (insertMid)
				itBegin = m_map.insert(itBegin, std::make_pair(keyBegin, val));
			if (endHasExtra)
									m_map.insert(itBegin, endExtra);

// INSERT YOUR SOLUTION HERE
    }

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

Here is one take without using upper/lower bound checks. I shortly checked against a normal array and if it is canonical, but didn't check the boundaries. One concern I had was whether the eraseEnd iterator will be invalidated if the lower bound is inserted but according to the standard it should not be the case for std::map. It is not a submitted code, so use the idea at your own risk.

PS: Really, we shouldn't use even insert() Then why are we using a map?

void assign( K const& keyBegin, K const& keyEnd, V const& val ) {
    // incorrect key
    if ( keyEnd <= keyBegin )
        return;

    const auto &[ upperBoundItr, upperBoundSuccess ] = m_map.insert( { keyEnd, val } );
    auto eraseEnd = upperBoundItr;

    // upper boundary should be the continuation of the previous range. if it is a new insertion
    // it should have the previous range value. if the insertion was not successful, the value should not change.
    if ( upperBoundSuccess ) {
        upperBoundItr->second = std::prev( upperBoundItr )->second;

        // if it is a new insertion, we need to check if the next boundary has the same value.
        if ( auto n = std::next( eraseEnd ); n != m_map.cend() && n->second == eraseEnd->second )
            m_map.erase( n );
    }

    const auto &[ lowerBoundItr, lowerBoundSuccess ] = m_map.insert_or_assign( keyBegin, val );
    auto eraseStart = std::next( lowerBoundItr );

    // if the end of the range has the same value, the end boundary should be removed.
    if ( lowerBoundItr->second == eraseEnd->second )
        eraseEnd = std::next( eraseEnd );

    // if the previous start boundary has the same value, remove the new duplicate.
    if ( lowerBoundItr != m_map.cbegin() && std::prev( lowerBoundItr )->second == val )
        eraseStart = lowerBoundItr;

    m_map.erase( eraseStart, eraseEnd );
}