fork(25) download 
  1. #include <map>
  2. #include <limits>
  3. #include <cassert>
  4. #include <vector>
  5. #include <stdlib.h>
  6.  
  7. template<typename K, typename V>
  8. class interval_map {
  9. protected:
  10.     std::map<K, V> m_map;
  11.  
  12. public:
  13.     // constructor associates whole range of K with val by inserting (K_min, val)
  14.     // into the map
  15.     interval_map(V const& val) {
  16.         m_map.insert(m_map.end(), std::make_pair(std::numeric_limits<K>::lowest(), val));
  17.     }
  18.  
  19.     // Assign value val to interval [keyBegin, keyEnd).
  20.     // Overwrite previous values in this interval.
  21.     // Conforming to the C++ Standard Library conventions, the interval
  22.     // includes keyBegin, but excludes keyEnd.
  23.     // If !( keyBegin < keyEnd ), this designates an empty interval,
  24.     // and assign must do nothing.
  25.     void assign(K const& keyBegin, K const& keyEnd, V const& val) {
  26.         if (!(keyBegin < keyEnd))
  27.             return;
  28.         auto nextInterval = --m_map.upper_bound(keyEnd);
  29.         auto inserted1 = m_map.end();
  30.         auto inserted2 = m_map.end();
  31.         assert(nextInterval != m_map.end());
  32.         if (nextInterval->second == val)
  33.             ++nextInterval;
  34.         else if (nextInterval->first < keyEnd)
  35.         {
  36.             const V & nextValue = nextInterval->second;
  37.             ++nextInterval;
  38.             inserted1 = nextInterval = m_map.emplace_hint(nextInterval, keyEnd, nextValue);
  39.         }
  40.         try
  41.         {
  42.             auto prevInterval = nextInterval;
  43.             --prevInterval;
  44.             assert(prevInterval != m_map.end());
  45.             if (keyBegin < prevInterval->first)
  46.                 prevInterval = --m_map.upper_bound(keyBegin);
  47.             assert(prevInterval != m_map.end());
  48.             if (!(prevInterval->second == val))
  49.             {
  50.                 if (prevInterval->first < keyBegin)
  51.                 {
  52.                     ++prevInterval;
  53.                     inserted2 = prevInterval = m_map.emplace_hint(prevInterval, keyBegin, val);
  54.                 }
  55.                 else
  56.                 {
  57. 				    prevInterval->second = val;
  58. 				    if (prevInterval != m_map.begin() && !((--prevInterval)->second == val))
  59. 				    {
  60. 				        ++prevInterval;
  61. 				    }
  62.                 }
  63.             }
  64.             assert(prevInterval != m_map.end());
  65.             m_map.erase(++prevInterval, nextInterval);
  66.         }
  67.         catch (...)
  68.         {
  69.             if (inserted1 != m_map.end())
  70.                 m_map.erase(inserted1);
  71.             if (inserted2 != m_map.end())
  72.                 m_map.erase(inserted2);
  73.             throw;
  74.         }
  75.     }
  76.  
  77.     // look-up of the value associated with key
  78.     V const& operator[](K const& key) const {
  79.         return (--m_map.upper_bound(key))->second;
  80.     }
  81. };
  82.  
  83. class test_map : interval_map<unsigned char, unsigned char>
  84. {
  85. public:
  86.     std::vector<unsigned char> m_check;
  87.     test_map() : interval_map(16)
  88.     {
  89.         m_check.resize(256, 16);
  90.     }
  91.     void assign(unsigned char first, unsigned char last, unsigned char value)
  92.     {
  93.         test();
  94.         interval_map::assign(first, last, value);
  95.         for (int i = first; i < last; ++i)
  96.             m_check[i] = value;
  97.         test();
  98.     }
  99.     void test()
  100.     {
  101.         auto prev_it = m_map.begin();
  102.         assert(!m_map.empty());
  103.         assert(prev_it->first == 0);
  104.         for (auto it = ++m_map.begin(); it != m_map.end(); ++it)
  105.         {
  106.             assert(prev_it->second != it->second);
  107.             for (int i = prev_it->first; i < it->first; ++i)
  108.                 assert(m_check[i] == prev_it->second);
  109.             prev_it = it;
  110.         }
  111.         for (int i = prev_it->first; i < 256; ++i)
  112.             assert(m_check[i] == prev_it->second);
  113.     }
  114. };
  115.  
  116. // Many solutions we receive are incorrect. Consider using a randomized test
  117. // to discover the cases that your implementation does not handle correctly.
  118. // We recommend to implement a test function that tests the functionality of
  119. // the interval_map, for example using a map of unsigned int intervals to char.
  120.  
  121. int main()
  122. {
  123.     for (int t = 0; t < 300; ++t)
  124.     {
  125.         test_map tm;
  126.         for (int i = 0; i < 1000; ++i)
  127.         {
  128.             tm.assign(rand() % 256, rand() % 256, rand() % 16);
  129.         }
  130.         tm.test();
  131.     }
  132.     return 0;
  133. }
Success #stdin #stdout 0.27s 4392KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/DDitxZ
language:
C++14 (gcc 8.3)
created:
7 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!