Untitled
unknown
plain_text
a month ago
5.0 kB
1
Indexable
#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; }
Editor is loading...
Leave a Comment