Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Interval map that overwrites values instead of accumulating
#include <boost/icl/interval_map.hpp>
#include <boost/optional.hpp>
#include <iostream>
using namespace boost::icl;
template <class Type>
struct inplace_overwrite : identity_based_inplace_combine<Type> {
void operator()(Type &object, const Type &operand) const { object = operand; }
};
using ival_map =
interval_map<unsigned, // Interval type
unsigned, // Value type
partial_absorber, // Combine when overlap on insertion
std::less, // Comparator
inplace_overwrite, // Combine operator
inplace_erasure, // Subtract operator
closed_interval<unsigned int, std::less>, // Interval type
std::allocator>;
using ival = ival_map::interval_type;
bool insert(ival_map &map, unsigned index, unsigned value) {
auto current = ival(index, index);
auto previous = ival(index - 1, index - 1);
// Look for interval left-touching or greater
auto pos = map.lower_bound(previous);
if (pos != map.end()) {
// Case 1: interval is just before
unsigned next_value = pos->second + length(pos->first);
if (touches(pos->first, current) && next_value == value) {
// Index and value are consecutive, merge in existing interval
current = ival(pos->first.lower(), index);
value = pos->second;
// Look next interval too
pos++;
}
// Case 2: interval already contains index
if (contains(pos->first, index)) {
return false;
}
// Case 3: interval is just after
unsigned prev_value = pos->second - 1;
if (touches(current, pos->first) && prev_value == value) {
// Include index in next interval if consecutive
current = ival(current.lower(), pos->first.upper());
}
}
map.insert(std::make_pair(current, value));
return true;
}
boost::optional<unsigned> find(const ival_map &map, unsigned index) {
auto pos = map.find(index);
if (pos != map.end()) {
return pos->second + index - pos->first.lower();
}
return boost::none;
}
int main() {
ival_map m;
// std::cout << insert(m, 1, 1)
// << insert(m, 2, 2)
// << insert(m, 3, 3)
// << insert(m, 4, 4)
// << insert(m, 5, 5)
// << insert(m, 2, 5);
m.add(std::make_pair(ival(0, 9), 1));
m.add(std::make_pair(ival(3, 6), 3));
m.add(std::make_pair(ival(10, 19), 1));
m.subtract(std::make_pair(ival(3, 6), 3));
// m.add(std::make_pair(ival(9, 11), 4));
// m.add(std::make_pair(ival(10, 11), 5));
// m.add(std::make_pair(ival(3, 11), 1));
for (auto &entry : m) {
std::printf("[%u, %u) : %u\n", entry.first.lower(), entry.first.upper(),
entry.second);
}
std::printf("Find %u returns %u\n", 3, *find(m, 3));
std::printf("Find %u returns %u\n", 2, *find(m, 2));
std::printf("Find %u returns %u\n", 5, *find(m, 5));
std::printf("Find %u returns %u\n", 1, *find(m, 1));
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.