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