fork download 
  1. #include <assert.h>
  2. #include <map>
  3. #include <limits>
  4.  
  5.  
  6. template<class K, class V>
  7. class interval_map {
  8.     friend void IntervalMapTest();
  9.  
  10. private:
  11.     std::map<K,V> m_map;
  12.  
  13. public:
  14.     // constructor associates whole range of K with val by inserting (K_min, val)
  15.     // into the map
  16.     interval_map( V const& val) {
  17.         m_map.insert(m_map.begin(),make_pair(numeric_limits<K>::lowest(),val));
  18.     };
  19.  
  20.  
  21. 	void eraseUntillEnd(std::map <K, V>::iterator beginIter , std::map <K, V>::iterator endIter)
  22. 	{
  23. 		if ( beginIter + 1 != endIter && beginIter +1 != m_map.end() )
  24. 			{
  25. 				for (it = beginIter + 1; it != m_map.end(); it++)
  26. 					m_map.erase(it);
  27. 			}
  28. 	}
  29.  
  30. 	void mergeHead(std::map <K, V>::iterator beginIter, const V& val )
  31. 	{
  32. 		*beginIter = val;
  33. 			if (beginIter != m_map.begin())
  34. 			{
  35. 				auto& preBeginIter = beginIter - 1; 
  36. 				if (*beginIter == *preBeginIter)
  37. 				{
  38. 					m_map.erase(beginIter);
  39. 				}
  40. 			}
  41. 	}
  42.  
  43. 	void mergeTail(std::map <K, V>::iterator endIter)
  44. 	{
  45. 		if(endIter + 1 != m_map.end())
  46. 			{
  47. 				auto& nextEndIter = endIter + 1;
  48. 				if(*endIter == *nextEndIter)
  49. 					m_map.erase(endIter);
  50. 			}
  51. 	}
  52.  
  53.     // Assign value val to interval [keyBegin, keyEnd). 
  54.     // Overwrite previous values in this interval. 
  55.     // Do not change values outside this interval.
  56.     // Conforming to the C++ Standard Library conventions, the interval 
  57.     // includes keyBegin, but excludes keyEnd.
  58.     // If !( keyBegin < keyEnd ), this designates an empty interval, 
  59.     // and assign must do nothing.
  60.     void assign( K const& keyBegin, K const& keyEnd, const V& val ) 
  61. 	{
  62. 		map <K, V>::iterator beginIter = m_map.find(keyBegin);
  63. 		map <K, V>::iterator endIter = m_map.find(keyEnd);
  64. 		map <K, V>::iterator it = ;
  65.  
  66. 		if (beginIter != m_map.end() && endIter != m_map.end())
  67. 		{
  68.  
  69. 			// erase untill end
  70.  
  71. 			eraseUntillEnd(beginIter, endIter);
  72.  
  73. 			// merge head
  74.  
  75. 			mergeHead(beginIter, val);
  76.  
  77. 			//merge tail
  78.  
  79. 			mergeTail(endIter);
  80.  
  81. 		}
  82.  
  83. 		// No begin, Yes End
  84. 		else if(beginIter == m_map.end() && endIter != m_map.end())
  85. 		{
  86. 			beginIter = m_map.insert(m_map.begin(),make_pair(keyBegin,val));
  87.  
  88. 			// erase untill end
  89.  
  90. 			eraseUntillEnd(beginIter, endIter);
  91.  
  92. 			// merge head
  93.  
  94. 			mergeHead(beginIter, val);
  95.  
  96. 			//merge tail
  97.  
  98. 			mergeTail(endIter);
  99. 		}
  100.  
  101. 		//Yes begin, No End
  102. 		else if(beginIter != m_map.end() && endIter == m_map.end())
  103. 		{
  104. 			endIter = m_map.insert(m_map.begin(),make_pair(keyEnd,val));
  105. 			*endIter = *endIter - 1;
  106.  
  107. 			// erase untill end
  108.  
  109. 			eraseUntillEnd(beginIter, endIter);
  110.  
  111. 			// merge head
  112.  
  113. 			mergeHead(beginIter, val);
  114.  
  115. 			//merge tail
  116.  
  117. 			mergeTail(endIter);
  118. 		}
  119.  
  120. 		//No , No
  121. 		else if(beginIter == m_map.end() && endIter == m_map.end())
  122. 		{
  123. 			beginIter = m_map.insert(m_map.begin(),make_pair(keyBegin,val));
  124. 			endIter = m_map.insert(m_map.begin(),make_pair(keyEnd,val));
  125. 			*endIter = *endIter - 1;
  126.  
  127. 			// erase untill end
  128.  
  129. 			eraseUntillEnd(beginIter, endIter);
  130.  
  131. 			// merge head
  132.  
  133. 			mergeHead(beginIter);
  134.  
  135. 			//merge tail
  136.  
  137. 			mergeTail(endIter);
  138. 		}
  139.  
  140. 		else
  141. 			cout << "RIDI" << endl;
  142. 	}
  143.  
  144.  
  145.     // look-up of the value associated with key
  146.     V const& operator[]( K const& key ) const {
  147.         return ( --m_map.upper_bound(key) )->second;
  148.     }
  149. };
  150.  
  151. // Many solutions we receive are incorrect. Consider using a randomized test
  152. // to discover the cases that your implementation does not handle correctly.
  153. // We recommend to implement a function IntervalMapTest() here that tests the
  154. // functionality of the interval_map, for example using a map of unsigned int
  155. // intervals to char.
  156.  
  157. int main(int argc, char* argv[]) {
  158.     //IntervalMapTest();
  159.     return 0;
  160. }
Compilation error #stdin compilation error #stdout 0s 0KB
comments (?)
stdin 
Standard input is empty
compilation info 
prog.cpp:21:39: error: 'std::map<K, V, std::less<_Key>, std::allocator<std::pair<const _Key, _Tp> > >::iterator' is not a type
  void eraseUntillEnd(std::map <K, V>::iterator beginIter , std::map <K, V>::iterator endIter)
                                       ^
prog.cpp:21:77: error: 'std::map<K, V, std::less<_Key>, std::allocator<std::pair<const _Key, _Tp> > >::iterator' is not a type
  void eraseUntillEnd(std::map <K, V>::iterator beginIter , std::map <K, V>::iterator endIter)
                                                                             ^
prog.cpp:30:34: error: 'std::map<K, V, std::less<_Key>, std::allocator<std::pair<const _Key, _Tp> > >::iterator' is not a type
  void mergeHead(std::map <K, V>::iterator beginIter, const V& val )
                                  ^
prog.cpp:43:34: error: 'std::map<K, V, std::less<_Key>, std::allocator<std::pair<const _Key, _Tp> > >::iterator' is not a type
  void mergeTail(std::map <K, V>::iterator endIter)
                                  ^
prog.cpp: In constructor 'interval_map<K, V>::interval_map(const V&)':
prog.cpp:17:46: error: 'numeric_limits' was not declared in this scope
         m_map.insert(m_map.begin(),make_pair(numeric_limits<K>::lowest(),val));
                                              ^
prog.cpp:17:46: note: suggested alternative:
In file included from prog.cpp:3:0:
/usr/include/c++/5/limits:315:12: note:   'std::numeric_limits'
     struct numeric_limits : public __numeric_limits_base
            ^
prog.cpp:17:62: error: expected primary-expression before '>' token
         m_map.insert(m_map.begin(),make_pair(numeric_limits<K>::lowest(),val));
                                                              ^
prog.cpp:17:63: error: '::lowest' has not been declared
         m_map.insert(m_map.begin(),make_pair(numeric_limits<K>::lowest(),val));
                                                               ^
prog.cpp: In member function 'void interval_map<K, V>::eraseUntillEnd(int, int)':
prog.cpp:25:10: error: 'it' was not declared in this scope
     for (it = beginIter + 1; it != m_map.end(); it++)
          ^
prog.cpp: In member function 'void interval_map<K, V>::mergeHead(int, const V&)':
prog.cpp:32:4: error: invalid type argument of unary '*' (have 'int')
   *beginIter = val;
    ^
prog.cpp:35:11: error: ISO C++ forbids declaration of 'preBeginIter' with no type [-fpermissive]
     auto& preBeginIter = beginIter - 1; 
           ^
prog.cpp:36:10: error: invalid type argument of unary '*' (have 'int')
     if (*beginIter == *preBeginIter)
          ^
prog.cpp:36:24: error: invalid type argument of unary '*' (have 'int')
     if (*beginIter == *preBeginIter)
                        ^
prog.cpp: In member function 'void interval_map<K, V>::mergeTail(int)':
prog.cpp:47:11: error: ISO C++ forbids declaration of 'nextEndIter' with no type [-fpermissive]
     auto& nextEndIter = endIter + 1;
           ^
prog.cpp:48:9: error: invalid type argument of unary '*' (have 'int')
     if(*endIter == *nextEndIter)
         ^
prog.cpp:48:21: error: invalid type argument of unary '*' (have 'int')
     if(*endIter == *nextEndIter)
                     ^
prog.cpp: In member function 'void interval_map<K, V>::assign(const K&, const K&, const V&)':
prog.cpp:62:3: error: 'map' was not declared in this scope
   map <K, V>::iterator beginIter = m_map.find(keyBegin);
   ^
prog.cpp:62:3: note: suggested alternative:
In file included from /usr/include/c++/5/map:61:0,
                 from prog.cpp:2:
/usr/include/c++/5/bits/stl_map.h:96:11: note:   'std::map'
     class map
           ^
prog.cpp:62:9: error: expected primary-expression before ',' token
   map <K, V>::iterator beginIter = m_map.find(keyBegin);
         ^
prog.cpp:62:12: error: expected primary-expression before '>' token
   map <K, V>::iterator beginIter = m_map.find(keyBegin);
            ^
prog.cpp:62:13: error: '::iterator' has not been declared
   map <K, V>::iterator beginIter = m_map.find(keyBegin);
             ^
prog.cpp:62:13: note: suggested alternatives:
In file included from /usr/include/c++/5/bits/stl_algobase.h:65:0,
                 from /usr/include/c++/5/bits/stl_tree.h:63,
                 from /usr/include/c++/5/map:60,
                 from prog.cpp:2:
/usr/include/c++/5/bits/stl_iterator_base_types.h:118:12: note:   'std::iterator'
     struct iterator
            ^
/usr/include/c++/5/bits/stl_iterator_base_types.h:118:12: note:   'std::iterator'
prog.cpp:63:9: error: expected primary-expression before ',' token
   map <K, V>::iterator endIter = m_map.find(keyEnd);
         ^
prog.cpp:63:12: error: expected primary-expression before '>' token
   map <K, V>::iterator endIter = m_map.find(keyEnd);
            ^
prog.cpp:63:13: error: '::iterator' has not been declared
   map <K, V>::iterator endIter = m_map.find(keyEnd);
             ^
prog.cpp:63:13: note: suggested alternatives:
In file included from /usr/include/c++/5/bits/stl_algobase.h:65:0,
                 from /usr/include/c++/5/bits/stl_tree.h:63,
                 from /usr/include/c++/5/map:60,
                 from prog.cpp:2:
/usr/include/c++/5/bits/stl_iterator_base_types.h:118:12: note:   'std::iterator'
     struct iterator
            ^
/usr/include/c++/5/bits/stl_iterator_base_types.h:118:12: note:   'std::iterator'
prog.cpp:64:9: error: expected primary-expression before ',' token
   map <K, V>::iterator it = ;
         ^
prog.cpp:64:12: error: expected primary-expression before '>' token
   map <K, V>::iterator it = ;
            ^
prog.cpp:64:13: error: '::iterator' has not been declared
   map <K, V>::iterator it = ;
             ^
prog.cpp:64:13: note: suggested alternatives:
In file included from /usr/include/c++/5/bits/stl_algobase.h:65:0,
                 from /usr/include/c++/5/bits/stl_tree.h:63,
                 from /usr/include/c++/5/map:60,
                 from prog.cpp:2:
/usr/include/c++/5/bits/stl_iterator_base_types.h:118:12: note:   'std::iterator'
     struct iterator
            ^
/usr/include/c++/5/bits/stl_iterator_base_types.h:118:12: note:   'std::iterator'
prog.cpp:66:7: error: 'beginIter' was not declared in this scope
   if (beginIter != m_map.end() && endIter != m_map.end())
       ^
prog.cpp:66:35: error: 'endIter' was not declared in this scope
   if (beginIter != m_map.end() && endIter != m_map.end())
                                   ^
prog.cpp:141:4: error: 'cout' was not declared in this scope
    cout << "RIDI" << endl;
    ^
prog.cpp:141:22: error: 'endl' was not declared in this scope
    cout << "RIDI" << endl;
                      ^
stdout 
Standard output is empty
https://ideone.com/kTPGSc
language:
C++ (gcc 8.3)
created:
9 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!