#include #include #include #include #define DTRACE // Assign value val to interval [keyBegin, keyEnd). // Overwrite previous values in this interval. // The interval includes keyBegin, but excludes keyEnd. // If !( keyBegin < keyEnd ), this designates an empty interval, // and assign must do nothing. template class interval_map { std::map m_map; public: interval_map(V const& val) { m_map.insert( m_map.end(), std::make_pair( std::numeric_limits::lowest(), val ) ); } //debug print intervals void print(){ typedef typename std::map ::iterator map_it; std::cout << "print" << std::endl; for (map_it it = m_map.begin(); it != m_map.end(); it++) std::cout << it->first << ":\"" << it->second << "\"" << ", "; std::cout << std::endl << "." << std::endl; } void assign( K const& keyBegin, K const& keyEnd, V const& val) { if (!(keyBegin < keyEnd)) return; V rV,pV; auto uIt = m_map.lower_bound(keyBegin); auto dIt = m_map.lower_bound(keyEnd); if (uIt != m_map.end()) { if ( uIt == dIt ){ if(dIt == m_map.begin()){ //case A m_map[keyBegin] = val; } else { if (dIt->first == keyEnd) { //case B1 if(uIt != m_map.begin() ){ uIt--; pV = uIt->second; uIt++; if(pV != val) m_map[keyBegin] = val; } else { m_map[keyBegin] = val; } } else { //case B2 dIt--; rV = dIt->second; if(uIt != m_map.begin() ){ uIt--; pV = uIt->second; uIt++; if (pV != val) { m_map[keyBegin] = val; m_map[keyEnd] = rV; } else { if (pV != dIt->second) m_map[keyEnd] = rV; }; } else { m_map[keyBegin] = val; m_map[keyEnd] = rV; } }; }; } else { if (dIt != m_map.end()) { if (dIt->first == keyEnd) { //case C1 if(uIt != m_map.begin() ){ uIt--; pV = uIt->second; uIt++; if (pV != val) { m_map.erase(uIt, dIt); m_map[keyBegin] = val; } else { if (pV == dIt->second) dIt++; m_map.erase(uIt, dIt); } } else { m_map.erase(uIt, dIt); m_map[keyBegin] = val; } } else { //case C2 dIt--; rV = dIt->second; dIt++; if(uIt != m_map.begin() ){ uIt--; pV = uIt->second; uIt++; if (pV != val) { m_map.erase(uIt, dIt); m_map[keyBegin] = val; } else { if (pV == dIt->second) dIt++; m_map.erase(uIt, dIt); } } else { m_map.erase(uIt, dIt); m_map[keyBegin] = val; } if(val != rV) m_map[keyEnd] = rV; }; } else { //case D dIt--; rV = dIt->second; dIt++; if(uIt != m_map.begin() ){ uIt--; pV = uIt->second; uIt++; if (pV != val) { m_map.erase(uIt, dIt); m_map[keyBegin] = val; } else { if (pV == dIt->second) dIt++; m_map.erase(uIt, dIt); } } else { m_map.erase(uIt, dIt); m_map[keyBegin] = val; } if(val != rV) m_map[keyEnd] = rV; }; }; }else{ if (m_map.size() == 0) { //case Z m_map[keyBegin] = val; } else { //case E dIt = m_map.end(); dIt--; rV = dIt->second; if (rV != val) { m_map[keyBegin] = val; m_map[keyEnd] = rV; }; }; } } }; typedef unsigned int KeyType; typedef interval_map IC_map; int main() { IC_map vIC_map( "A" ); vIC_map.print(); /* //Case serie 1 vIC_map.assign( (KeyType)1, (KeyType)4, "B"); vIC_map.print(); vIC_map.assign( (KeyType)4, (KeyType)8, "C"); vIC_map.print(); vIC_map.assign( (KeyType)2, (KeyType)4, "G"); vIC_map.print(); vIC_map.assign( (KeyType)11, (KeyType)12, "A"); vIC_map.print(); vIC_map.assign( (KeyType)5, (KeyType)7, "D"); vIC_map.print(); vIC_map.assign( (KeyType)3, (KeyType)6, "F"); vIC_map.print(); vIC_map.assign( (KeyType)2, (KeyType)7, "I"); vIC_map.print(); vIC_map.assign( (KeyType)4, (KeyType)12, "R"); vIC_map.print(); vIC_map.assign( (KeyType)1, (KeyType)6, "A"); vIC_map.print(); */ vIC_map.assign( (KeyType)100, (KeyType)200, "B"); vIC_map.print(); vIC_map.assign( (KeyType)50, (KeyType)150, "C"); vIC_map.print(); vIC_map.assign( (KeyType)50, (KeyType)200, "A"); vIC_map.print(); vIC_map.assign( (KeyType)0, (KeyType)10000, "C"); vIC_map.print(); vIC_map.assign( (KeyType)20000, (KeyType)30000, "W"); vIC_map.print(); vIC_map.assign( (KeyType)10, (KeyType)40, "B"); vIC_map.print(); vIC_map.assign( (KeyType)40, (KeyType)80, "C"); vIC_map.print(); vIC_map.assign( (KeyType)20, (KeyType)40, "G"); vIC_map.print(); vIC_map.assign( (KeyType)110, (KeyType)120, "A"); vIC_map.print(); vIC_map.assign( (KeyType)50, (KeyType)70, "D"); vIC_map.print(); vIC_map.assign( (KeyType)30, (KeyType)60, "F"); vIC_map.print(); vIC_map.assign( (KeyType)27, (KeyType)29, "G"); vIC_map.print(); return 0; };

Example interval map - my solution