Untitled
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