pastebin

Paste Search Dynamic
Recent pastes
interval map
  1. #include <assert.h>
  2. #include <map>
  3. #include <limits>
  4. #include <iostream>
  5.  
  6. using namespace std;
  7. template<class K, class V>
  8. class interval_map {
  9.     friend void IntervalMapTest();
  10.  
  11. public:
  12.     std::map<K,V> m_map;
  13.  
  14. public:
  15.     // constructor associates whole range of K with val by inserting (K_min, val)
  16.     // into the map
  17.     interval_map( V const& val) {
  18.         m_map.insert(m_map.begin(),std::make_pair(std::numeric_limits<K>::lowest(),val));
  19.     };
  20.  
  21.     // Assign value val to interval [keyBegin, keyEnd).
  22.     // Overwrite previous values in this interval.
  23.     // Do not change values outside this interval.
  24.     // Conforming to the C++ Standard Library conventions, the interval
  25.     // includes keyBegin, but excludes keyEnd.
  26.     // If !( keyBegin < keyEnd ), this designates an empty interval,
  27.     // and assign must do nothing.
  28.     void assign( K const& keyBegin, K const& keyEnd, const V& val ) {
  29.            //Check if assign need to do anything
  30.        if( (keyBegin < keyEnd) && (std::numeric_limits<K>::lowest() < keyEnd ) )
  31.         {
  32.             typename std::map<K,V>::iterator iter = m_map.lower_bound(keyBegin);
  33.             //Check for consecutive same value. Insert only if different value
  34.             if (iter==m_map.end() && !((--iter)->second == val))
  35.             {
  36.                 m_map.insert(m_map.end(),std::make_pair(keyBegin, val));
  37.             }
  38.             else if(iter!=m_map.end())
  39.             {
  40.                 if(!(keyBegin < iter->first))
  41.                 {
  42.                     iter->second= val;
  43.                 }
  44.                 else if((keyBegin < iter->first) && !(iter->second == val))
  45.                 {
  46.                     m_map.insert(--iter,std::make_pair(keyBegin, val));
  47.                 }
  48.                
  49.             }
  50.  
  51.         }
  52.     }
  53.  
  54.     // look-up of the value associated with key
  55.     V const& operator[]( K const& key ) const {
  56.         return ( --m_map.upper_bound(key) )->second;
  57.     }
  58. };
  59.  
  60. // Many solutions we receive are incorrect. Consider using a randomized test
  61. // to discover the cases that your implementation does not handle correctly.
  62. // We recommend to implement a function IntervalMapTest() here that tests the
  63. // functionality of the interval_map, for example using a map of unsigned int
  64. // intervals to char.
  65. void IntervalMapTest()
  66. {
  67.     interval_map<unsigned int,char> test('m');
  68.     cout<<"Elements are<<test[0]<<test[1]<<test[2]<<test[3]<<test[4]<<test[5]<<test[6]<<test[7]";
  69.     test.assign(2,4,'k');
  70.     test.assign(4,5,'s');
  71.     test.assign(5,6,'t');
  72.     cout<<"Elements are::::"<<endl<<test[0]<<endl<<test[1]<<endl<<test[2]<<endl<<test[3]<<endl<<test[4]<<endl<<test[5]<<endl<<test[6]<<endl<<test[7];
  73.     //for(auto &iter : test.m_map){cout<<"first"<<iter->first<<"second"<<iter->second;}
  74. }
  75. int main(int argc, char* argv[]) {
  76.     cout<<"hello";
  77.     IntervalMapTest();
  78.     return 0;
  79. }
  80.  
Parsed in 0.013 seconds