Skip to main content

Think-Cell - interval_map

Received a message that this code failed ..... Not sure where the problem is ....
#define _AMD64_
#include <Windows.h>
#include <map>


template <typename K, typename V>
class interval_map {
    friend void IntervalMapTest();
    V m_valBegin; // default constructor, whtever it is
    std::map<K, V> m_map;

public:
    // 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 ) {
        // ATTENTION: *** Not sure if should be a return or a throw. It is not clear how error should be treated.
        // This code can be much better

        // Key type K. besides being copyable and assignable, is less - than comparable via operator<, and does not implement any other operations, in particular no equality comparison or arithmetic operators.
        if ( !( keyBegin < keyEnd ) ) {
            return;
        }
        // An empty map...just add it
        if ( m_map.empty() ) {
            // if V is the same as initial, do not add anything. Depending on V type, this can lead to extra execution time
            // Value type V. besides being copyable and assignable, is equality - comparable via operator==, and does not implement any other operations.
            if ( !( val == m_valBegin ) ) {
                m_map.insert( std::make_pair( keyBegin, val ) );
            }
        } else { // there is at least one entry
            // Remove all entries between Begin and End (exlcusive)
            auto it = m_map.lower_bound( keyBegin ); // Returns an iterator pointing to the first element that is not less than (i.e. greater or equal to) key
            while ( ( it != m_map.end() ) && ( it->first < keyEnd ) ) {
                it = m_map.erase( it );
            }
            // Insert new K
            m_map.insert( std::make_pair( keyBegin, val ) ); // the new pair..Maybe add a test for success?
            it = m_map.lower_bound( keyBegin ); // iterator to new element. Assuming the insert worked ;)
            auto it_next = it; // previous item (it is the current item. it has to exist, assuming the insert worked ;) )
            it_next++;
            if ( ( it_next != m_map.end() ) && ( it->second == it_next->second ) ) { // if next entry has same V, exclude it
                m_map.erase( it_next ); // remove next key, preserving this new entry
            } else if ( it != m_map.begin() ) {
                auto it_prev = it; // next item (it is the current item. it has to exist, assuming the insert worked ;) )
                it_prev--;
                if ( it_prev->second == it->second ) { // if previous entry has same V, exclude it
                    m_map.erase( it ); // remove this entry, preserving previous key....this can be an issue with ctor/dtor....
                }
            }
            if ( !m_map.empty() ) { // it should not be empty, but....
                // If first entry has same default value, remove first entry
                if ( m_map.begin()->second == m_valBegin ) {
                    m_map.erase( m_map.begin() ); // this can result on an empty map
                }
            }
        }
    }

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


void IntervalMapTest() {
    interval_map<int, char> M( 'A' );

}

main() {

}

Comments

Popular posts from this blog

Movies - Deadpool & Wolverine (2024)

 

TV Mini-serie - Lady in the Lake (2024)

 

Movie - The Gorge (2025)

  My views For 80 years everything was ok ... until they sent a woman For sure is DTV ... really bad Inside the gorge is clearly designed and written by a gamer Plot Two elite  snipers  receive identical missions: travel to an undisclosed location and guard the West and East sides of a deep gorge for one year without any contact with the outside world nor their counterpart on the opposite side. Levi Kane, a former  U.S. Marine  and current  private contractor  accepts the offer to guard the West tower. Drasa, a  Lithuanian  covert operative frequently employed by the  Kremlin , agrees to guard the East side. Upon arriving, Levi relieves his predecessor, J.D., a  British   Royal Marine  of duty and asks for specifics about the mission. J.D. explains that in addition to the towers on the East and West, there are automated turret defenses to the North and South, a powerful signal ‘ cloak ,’ and  explosives on the walls ...