Boost ICL map that replaces values in intervals?

Question

Boost.ICL's interval_map has two kinds of behaviors: += and insert. Both are useful in different context. The first adds up values in common intersections of two existing intervals. The second simply introduces the new value only in previously unassigned intervals (in previously assigned intervals the value is kept).

However I need a behavior that is subtly different, such that, in the example below instead of getting the undesired interval map (1.,2.)->1 , (2.5,3.)->3, (3.,5.)->2 I get instead the desired (1.,2.)->1 , (2.5,5.)->3.

That is, that new inserted values replace old values? How do I declare interval_map to get that replacing behavior?

#include<boost/icl/interval_map.hpp>
int main(){
    boost::icl::interval_map<double, int> joined_map;
    joined_map.insert( std::make_pair(
        boost::icl::interval<double>::open(1., 2.),
        1
    ));
    joined_map.insert( std::make_pair(
        boost::icl::interval<double>::open(3., 5.),
        2
    ));
    joined_map.insert( std::make_pair(
        boost::icl::interval<double>::open(2.5, 5.),
        3
    )); // this line doesn't replace the old value 2, it keeps it.
}

Bonus: Is that what boost::icl::map is supposed to do? How do I use it?

---

EDIT 1: This is a more explicit and simplified sample code using C++11

#include<boost/icl/interval_map.hpp>
#include<iostream>

namespace icl = boost::icl;
using interval = icl::interval<double>;

int main(){
    icl::interval_map<double, int> joined_map;

    joined_map.insert({interval::open(1., 2.), 1});
    joined_map.insert({interval::open(3., 5.), 2});
    joined_map.insert({interval::open(2.5, 5.), 3}); 
    // ^^^^ this line doesn't replace the old value 2! it keeps it.
    for(auto e: joined_map) std::cout << e.first <<' '<< e.second <<'\n';
    // prints: (1,2) 1 \\ (2.5,3] 3 \\ (3,5) 2
    // desired: (1,2) 1 \\ (2.5,5] 3  // value 2 gone
}

---

EDIT 2: Complete solution based on @JorgeBellon's answer:

#include<boost/icl/interval_map.hpp>
#include<iostream>

namespace icl = boost::icl;

template <class Type>
struct inplace_replace{// : icl::identity_based_inplace_combine<Type>{
    using first_argument_type = Type;
    void operator()(Type& object, Type const& operand) const{object = operand;}
};

using interval = icl::interval<double>;

int main(){

    icl::interval_map<
        double, int,
        icl::partial_enricher,   // Unmapped intervals have unkown value;
                                 // store identity values
        std::less             ,  // Comparator
        inplace_replace     //,  // Combination operator // IMPORTANT!!
    //  icl::inplace_erasure//,  // Extraction operator
    //  closed_interval<unsigned, std::less> // Interval type
    > joined_map;
    joined_map.add({interval::open(1. , 2.), 1}); // or joined_map+=std::make_pair(...)
    joined_map.add({interval::open(3. , 5.), 2}); // IMPORTANT: USE add, NOT insert!!
    joined_map.add({interval::open(2.5, 5.), 3}); 
    // ^^^^ this line now replaces the old value 2
    for(auto e: joined_map) std::cout << e.first <<' '<< e.second <<'\n';
    // prints: (1,2) 1 \\ (2.5,5] 3  // value 2 gone
}

Answer 1

One of the interval map's template parameters is the combination operator type. The typical example consists on map using std::set or similar as a value and then it uses the addition or the identity (keep the existing value) as operations.

Since the overwrite example is not there by default, you can create yours and pass it to the map yourself:

#include <boost/icl/interval_map.hpp>

using namespace boost::icl;

// interval_map combiner functor: assigns new value if key exists
template <class Type>
struct inplace_replace : identity_based_inplace_combine<Type> {
  void operator()(Type &object, const Type &operand) const {
    object = operand;
  }
};

template<>
inline std::string unary_template_to_string<inplace_replace>::apply() {
  return "=";
}

// When adding, if interval exists, replaces value.
// When subtracting, if interval exists, removes value.
using ival_map =
    interval_map<unsigned,         // Key
                 unsigned,         // Value
                 partial_enricher, // Unmapped intervals have unkown value; store identity values
                 std::less,        // Comparator
                 inplace_replace,  // Combination operator
                 inplace_erasure,  // Extraction operator
                 >;

See complete example: https://ideone.com/C49bDM

Edit: deriving from identity_based_inplace_combine<Type> (boost/icl/functors.hpp) does the following:

• Defines first_argument_type, second_argument_type and result_type.
• It is used to create the identity_element value for that type (a static function). For example the identity value for a set is an empty set, for an integer it is 0 (useful when you do a sum), etc.

It is not mandatory to use it if your map is partial_enricher or total_enricher, since in this case the map will contain entries for any values, including identity values. You will need it for the absorber types, since the map needs to know whether it can drop the interval or not in that case.

An alternative:

// interval_map combiner functor: assigns new value if key exists
template <class Type>
struct inplace_replace {
  typedef void result_type;
  typedef Type& first_argument_type;
  typedef const Type& second_argument_type;

  void operator()(Type &object, const Type &operand) const {
    object = operand;
  }
};

Note: older boost ICL implementations derive from std::binary_function instead of using these typedefs. Unfortunately this is deprecated in C++11 and removed in C++17, so I would try not to use it in your own code. The latest versions implement the functors like the snippet above.

Same example: https://ideone.com/lMLEDw

Answer 2

You can simply erase the contents of the section you'r intending to overwrite before insertion:

See it Live On Coliru:

#include <iostream>
#include <boost/icl/interval_map.hpp>

namespace icl = boost::icl;

int main()
{
    icl::interval_map<double, int> joined_map;
    using ival = icl::interval<double>;

    joined_map.add({ival::open(1., 2.), 1});
    joined_map.add({ival::open(3., 5.), 2});
    std::cout << "#1: "; for(auto el : joined_map) std::cout << el.first << ": " << el.second << ", "; std::cout << "\n";

    joined_map.erase(ival::open(3., 6.));
    joined_map.add({ival::open(3., 6.), 4});
    std::cout << "#2: "; for(auto el : joined_map) std::cout << el.first << ": " << el.second << ", "; std::cout << "\n";
}

This prints:

#1: (1,2): 1, (3,5): 2, 
#2: (1,2): 1, (3,6): 4, 

Which I believe is what you wanted.

---

^{old answer text for comic relief future reference}

I have a feeling the interval_map semantics aren't what you are expecting. I've played with this a little now, and can't say I do understand it, but I know enough to see that there's not a simple 1:1 mapping of things inserted and 'elements' stored in the container.

For this reason, many suprising deviations from std::map occur

• there's no operator[], but operator[] is overloaded (returning const)
• find() returns a const_iterator (presumably because it can return a 'virtual node' that's somehow derived from the actual data). So you can't just expect to map.erase(find(k)) - you have to explicitely erase by key or interval.
• there are add and subtract methods (aside from insert).

Demo code:

#include <iostream>
#include <boost/icl/interval_map.hpp>
#include <boost/icl/interval.hpp>

namespace icl = boost::icl;

int main()
{
    icl::interval_map<double, int,
       icl::partial_absorber,
       /*ICL_COMPARE Compare =*/ ICL_COMPARE_INSTANCE(ICL_COMPARE_DEFAULT, double), 
       /*ICL_COMBINE Combine =*/ ICL_COMBINE_INSTANCE(icl::inplace_plus, int), 
       /*ICL_SECTION Section =*/ ICL_SECTION_INSTANCE(icl::inter_section, int)
        > joined_map;
    using ival = icl::interval<double>;

    joined_map.add({ival::open(1., 2.), 1});
    joined_map.add({ival::open(3., 5.), 2});
    std::cout << "#1: "; for (auto el : joined_map) std::cout << el.first << ": " << el.second << ", "; std::cout << "\n";
    auto clone1 = joined_map;

    joined_map.add({3., 2});
    std::cout << "#2: "; for (auto el : joined_map) std::cout << el.first << ": " << el.second << ", "; std::cout << "\n";
    auto clone2 = joined_map;

    joined_map.add({3., 2});
    std::cout << "#3: "; for (auto el : joined_map) std::cout << el.first << ": " << el.second << ", "; std::cout << "\n";
    auto clone3 = joined_map;

    joined_map.add({ival::open(0., 6.), 10});
    std::cout << "#4: "; for (auto el : joined_map) std::cout << el.first << ": " << el.second << ", "; std::cout << "\n";
    auto clone4 = joined_map;

    for (double x = 0; x < 7; x += .5)
    {
        std::cout << x
            << "\t" << clone1(x)
            << "\t" << clone2(x)
            << "\t" << clone3(x)
            << "\t" << clone4(x) 
            << "\n";
    }
}

See it Live On Coliru, prints:

#1: (1,2): 1, (3,5): 2, 
#2: (1,2): 1, [3,5): 2, 
#3: (1,2): 1, [3,3]: 4, (3,5): 2, 
#4: (0,1]: 10, (1,2): 11, [2,3): 10, [3,3]: 14, (3,5): 12, [5,6): 10, 
0   0   0   0   0
0.5 0   0   0   10
1   0   0   0   10
1.5 1   1   1   11
2   0   0   0   10
2.5 0   0   0   10
3   0   2   4   14
3.5 2   2   2   12
4   2   2   2   12
4.5 2   2   2   12
5   0   0   0   10
5.5 0   0   0   10
6   0   0   0   0
6.5 0   0   0   0

Hope this helps