Last active
May 30, 2024 10:24
-
-
Save serg06/769a1dc4180b00d47a00cee6a6f55e28 to your computer and use it in GitHub Desktop.
[C++] Short IntervalMap data structure implementation
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/* | |
* NOTE 1: This works on VC++ but might need a little extra syntax to work on GCC. | |
* NOTE 2: It breaks when calling set_interval on the minimum key (std::numeric_limits<K>::lowest()) and maybe on the maximum key too. | |
* | |
* OPERATIONS: | |
* | |
* N = number of unique intervals. (Neighboring intervals with the same value are joined.) | |
* Iterators run in key-sorted order. (Or reverse, if you like - they're bidirectional.) | |
* | |
* get_min(): O(1) | |
* get_max(): O(1) | |
* iter.next(): O(1) amortized | |
* iterating entire tree: O(N) amortized | |
* map an interval to a value: O(log N) | |
* get value for interval containing key: O(log N) | |
* get iter to interval containing key: O(log N) | |
* | |
*/ | |
// Backstory, as with any shitty recipe blog: | |
// I discovered interval maps when I was asked to implement an interval map function during a coding challenge. | |
// Bombed the challenge, but learned about IntervalMaps and how cool they are. | |
// Came up with a really beautiful, simple implementation. | |
// Could be slightly improved with `const`, `&`, and `private:` in the right places, but otherwise it works great. | |
// Variable names are changed for the sake of the company that gives this test out. | |
#include <iterator> // std::prev, std::next | |
#include <limits> // std::numeric_limits | |
#include <map> // std::map | |
template <typename K, typename V> | |
class IntervalMap | |
{ | |
private: | |
std::map<K, V> my_map; | |
public: | |
inline IntervalMap() : IntervalMap(0) {} | |
// create interval map with default v | |
inline IntervalMap(const V& v) { | |
clear(v); | |
} | |
// map [begin, end) -> v | |
// O(log N) | |
void set_interval(const K& begin, const K& end, const V& v) { | |
if (begin >= end) return; | |
// get end intersector (inclusive) | |
auto end_intersect = --my_map.upper_bound(end); | |
// if required, insert at end | |
auto inserted_end = my_map.end(); | |
if (end_intersect->second != v) { | |
inserted_end = my_map.insert_or_assign(end_intersect, end, end_intersect->second); | |
} | |
// get begin intersector (inclusive) | |
auto begin_intersect = --my_map.upper_bound(begin); | |
// if required, insert at start | |
auto inserted_start = my_map.end(); | |
if (begin_intersect->second != v) { | |
inserted_start = my_map.insert_or_assign(begin_intersect, begin, v); | |
} | |
// delete everyone inside | |
auto del_start = inserted_start != my_map.end() ? inserted_start : begin_intersect; | |
if (del_start->first < begin || (del_start->first == begin && std::prev(del_start)->second != v)) { | |
del_start++; | |
} | |
auto del_end = inserted_end != my_map.end() ? inserted_end : end_intersect; | |
if (del_end != my_map.end() && del_end->first == end && std::next(del_end) != my_map.end() && del_end->second == v) { | |
del_end++; | |
} | |
if (del_start != my_map.end() && (del_end == my_map.end() || del_start->first < del_end->first)) { | |
my_map.erase(del_start, del_end); | |
} | |
} | |
// iterator which traverses elements in sorted order (smallest to largest) | |
// O(1) | |
inline auto begin() { | |
return my_map.begin(); | |
} | |
// end of elements | |
// O(1) | |
inline auto end() { | |
return my_map.end(); | |
} | |
// get iterator containing key `k` | |
// O(log N) | |
inline auto get_interval(K const& k) { | |
return --my_map.upper_bound(k); | |
} | |
// get value at key `k` | |
// O(log N) | |
const inline V& operator[](K const& k) const { | |
return (--my_map.upper_bound(k))->second; | |
} | |
// clear | |
inline void clear(V const& v) { | |
my_map.clear(); | |
my_map.insert(my_map.end(), { std::numeric_limits<K>::lowest(), v }); | |
} | |
// get num intervals overall | |
// always at least 1 | |
inline auto num_intervals() { | |
return my_map.size(); | |
} | |
// get number of intervals in a range | |
// UNTESTED | |
inline auto num_intervals(const K& start, const K& end) { | |
return get_interval(end) - get_interval(start); | |
} | |
}; |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Hi, how would one add a first element into this interval_map? Lets say you don't have any elements, so you add key: 1, 6 and value W....how would this be represented internaly in the class? That is, with std::map?
(1, W) , (6, ?) ---> I mean we need to somehow know that W is mapped on interval from 1 to 6, 6 excluded...