Interval map that overwrites values instead of accumulating

ival_overwrite.cpp

#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));
}