Why wouldn't boost::icl::interval_map add up the value?

Question

Consider the following program:

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

struct Value
{
    explicit Value(int v) : v(v), is_empty(false) {}
    Value() : v(0), is_empty(true) {}

    Value& operator+=(const Value& other)
    {
        v += other.v;
        return *this;
    }

    bool operator==(const Value& other) const { return is_empty == other.is_empty; }
    bool operator!=(const Value& other) const { return is_empty != other.is_empty; }

    int v;
    bool is_empty;
};

int main()
{
    boost::icl::interval_map<int, Value> m;
    m.add(std::make_pair(boost::icl::interval<int>::right_open(10, 20), Value(2)));
    m.add(std::make_pair(boost::icl::interval<int>::right_open(15, 30), Value(3)));
    std::cout << m.iterative_size() << '\n';
    std::cout << m.begin()->first.lower() << '\n';
    std::cout << m.begin()->first.upper() << '\n';
    std::cout << m.begin()->second.v << '\n';
}

The output is

1
10
30
2

Questons:

• Why is the last line 2?
• Isn't the interval map expected to add up the value, so that it is 5?
• How to achieve the behavior that intervals are added and the value from += is preserved?

---

I want the following results:

{([10,20)->(2))+
      ([15,30)->(3))+ 
                       ([40,50)->(11))}
=
{([10,30)->(5))([40,50)->(11))}

That is, when intervals are added, they are merged, and the combined value is stored for entire merged interval.

There's may be no math sense in this operation, but this is what I need in my program. (Also, I don't to subtract intervals).

Answer 1

The problem is that

bool operator==(const Value& other) const { return is_empty == other.is_empty; }
bool operator!=(const Value& other) const { return is_empty != other.is_empty; }

make it so that ANY value is "identical". That makes the behaviour unspecified, and likely ends up merging any touching intervals and keeping the previous value (because it was "equal" according to your own operator==).

Let's have C++ generate a more correct comparison:

struct Value {
    explicit Value(int v) : value(v) {}
    Value() : is_empty(true) {}

    Value& operator+=(const Value& other) { value += other.value; return *this; }

    auto operator<=>(Value const&) const = default;

    bool is_empty = false;
    int  value    = 0;
};

Now you can Live On Compiler Explorer

#include <iostream>
#include <boost/icl/interval_map.hpp>
int main()
{
    namespace icl = boost::icl;
    using I = icl::interval<int>;
    using Value = int;

    auto const a = std::make_pair(I::right_open(10, 20), Value(2));
    auto const b = std::make_pair(I::right_open(15, 30), Value(3));
    auto const c = std::make_pair(I::right_open(40, 50), Value(11));

    icl::interval_map<int, Value> m;
    m.add(a);
    m.add(b);
    m.add(c);

    std::cout << m << "\n";

    m.subtract(a);

    std::cout << m << "\n";
}

Printing

{([10,15)->(2))([15,20)->(5))([20,30)->(3))([40,50)->(11))}

However, I'm struggling to understand what Value adds over optional<int> which, in fact is already the behaviour of the interval_map anyways:

int main()
{
    namespace icl = boost::icl;
    using I = icl::interval<int>;

    auto const a = std::make_pair(I::right_open(10, 20), 2);
    auto const b = std::make_pair(I::right_open(15, 30), 3);
    auto const c = std::make_pair(I::right_open(40, 50), 11);

    icl::interval_map<int, int> m;
    m.add(a);
    m.add(b);
    m.add(c);

    std::cout << m << "\n";

    m.subtract(a);

    std::cout << m << "\n";
}

Prints:

{([10,15)->2)([15,20)->5)([20,30)->3)([40,50)->11)}
{([15,30)->3)([40,50)->11)}

In fact, in some respects, your custom Value take seems "wrong" to me, evem with the fixed comparison:

Live On Compiler Explorer

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

struct Value {
    explicit Value(int v) : value(v) {}
    Value() : is_empty(true) {}

    Value& operator+=(const Value& other) { value += other.value; return *this; }
    Value& operator-=(const Value& other) { value -= other.value; return *this; }

    auto operator<=>(Value const&) const = default;

    bool is_empty = false;
    int  value    = 0;

    friend std::ostream& operator<<(std::ostream& os, Value const& v) {
        return v.is_empty ? os << "#EMPTY" : os << v.value;
    }
};

int main()
{
    namespace icl = boost::icl;
    using I = icl::interval<int>;

    auto const a = std::make_pair(I::right_open(10, 20), Value(2));
    auto const b = std::make_pair(I::right_open(15, 30), Value(3));
    auto const c = std::make_pair(I::right_open(40, 50), Value(11));

    icl::interval_map<int, Value> m;
    m.add(a);
    m.add(b);
    m.add(c);

    std::cout << m << "\n";

    m.subtract(a);

    std::cout << m << "\n";
}

Printing

{([10,15)->2)([15,20)->5)([20,30)->3)([40,50)->11)}
{([10,15)->0)([15,30)->3)([40,50)->11)}

Is [10,15)->0 really intended, desired?