Scribd
Upload
1K views2 pages

C++ Interval Map Implementation

This document defines an interval_map class template that associates values with key intervals. The class contains a default value and a map to store key-value pairs. The assign method inserts or updates the value for a given key interval, handling overlapping entries. The operator[] looks up the value associated with a given key. Unit tests are recommended to validate the interval mapping functionality.

Uploaded by

perez0z0
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as TXT, PDF, TXT or read online on Scribd
1K views2 pages

C++ Interval Map Implementation

This document defines an interval_map class template that associates values with key intervals. The class contains a default value and a map to store key-value pairs. The assign method inserts or updates the value for a given key interval, handling overlapping entries. The operator[] looks up the value associated with a given key. Unit tests are recommended to validate the interval mapping functionality.

Uploaded by

perez0z0
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as TXT, PDF, TXT or read online on Scribd
You are on page 1/ 2

#include <map>

template<typename K, typename V>


class interval_map {
friend void IntervalMapTest();
V m_valBegin;
std::map<K,V> m_map;
public:
// constructor associates whole range of K with val
interval_map(V const& val)
: m_valBegin(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.

void assign(K const& keyBegin, K const& keyEnd, V const& val) {


if (!(keyBegin < keyEnd)) return; // Empty interval, do nothing

auto it = m_map.lower_bound(keyBegin);
if (it != m_map.begin() && (--it)->second == val) {
++it; // Skip overlapping entries with the same value
}

while (it != m_map.end() && it->first < keyEnd) {


if (it->second == val) {
++it; // Skip overlapping entries with the same value
} else {
it = m_map.erase(it); // Remove overlapping entries with
different values
}
}

if (it != m_map.begin() && (--it)->second == val) {


++it; // Skip overlapping entries with the same value
}

if (it != m_map.end() && it->first == keyBegin) {


if (it->second == val) {
++it; // Skip overlapping entries with the same value
} else {
it = m_map.erase(it); // Remove overlapping entries with
different values
}
}

if (it != m_map.end() && it->first == keyEnd) {


if (it->second == val) {
++it; // Skip overlapping entries with the same value
} else {
it = m_map.erase(it); // Remove overlapping entries with
different values
}
}
if (it != m_map.end() && it->first > keyEnd) {
m_map.emplace_hint(it, keyEnd, it->second); // Insert new entry
for keyEnd
}

if (it != m_map.begin() && (--it)->first < keyBegin) {


m_map.emplace_hint(it, keyBegin, val); // Insert new entry for
keyBegin
}

if (it == m_map.begin() || (--it)->first < keyBegin) {


m_map.emplace_hint(it, keyBegin, val); // Insert new entry for
keyBegin
}
}

// 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;
}
}
};

// 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.

You might also like