提升"interval_map" - 如何自定义触摸聚合

Question

Boost ICLinterval_set可以在将右开间隔添加到集合期间相互接触。例如，间隔[0,4)和[4,8)将联接起来成为间隔[0,8)。

这对于interval_map来说更复杂 - 间隔(相互接触并具有不同的关联值(将不会联接：

#include <iostream>
#include <utility>
#include <boost/icl/interval_map.hpp>
namespace icl = boost::icl;
using IMap = icl::interval_map<int, int>;
int main()
{
IMap m;
m += std::make_pair(IMap::interval_type::right_open(0, 4), 1);
m += std::make_pair(IMap::interval_type::right_open(4, 8), 2);
std::cout << m << std::endl;
}

该测试程序的输出如下：

{([0,4)->1)([4,8)->2)}

我知道如何自定义重叠聚合的过程，但是我需要自定义另一种情况 -触摸聚合。例如，如果区间相互接触，并且左区间的值等于右区间的值减去 1，则必须联接区间，并且生成的区间必须具有左区间的值。因此，上面的程序应该打印：

{([0,8)->1)}

是否可以使用当前可用的 Boost ICL 来做到这一点？

我可以使用interval_map的奇怪操作来做我想做的事，但我认为这会很麻烦且效率低下。我宁愿被指出正确的方向来使用当前可用的 ICL 自定义、函子等。

Answer 1

这对于interval_map来说更复杂 - 相互接触并具有不同关联值的间隔不会连接：

真的没有区别。

我知道如何自定义重叠聚合的过程，但是我需要自定义另一种情况 - 触摸聚合。

你似乎暗示

m += std::make_pair(IMap::interval_type::right_open(4, 8), 2);

将插入[4, 8) -> 2.

事实并非如此。这是一个共域组合操作，结果取决于映射的先前状态。

当然，你可以这样写：

m.set({Ival::right_open(4, 8), 2});

如果需要，可以查询前面的槽，因此操作可能如下所示：

// returns true if joined with preceding slot
bool fill_slot(IMap& m, int from, int till, int value) {
bool joined = false;
auto slot = Ival::right_open(from, till);
if (within(slot, m)) {
// There is overlap, I don't know how  you want to handle this.
// You can add some logic here.
} else {
auto preceding = m(from - 1);
if (preceding && value == preceding + 1) {
joined = true;
value = preceding;
}
}
m.set({slot, value});
return joined;
}

现在您可以编写如下测试用例：

int main() {
{
IMap m;
fill_slot(m,  0,  4,  1);
fill_slot(m,  4,  8,  2);
std::cout << m << std::endl;
}
{
IMap m;
fill_slot(m,  0,  4,  1);
fill_slot(m,  4,  8,  3);
std::cout << m << std::endl;
}
{
IMap m;
fill_slot(m,  0,  4,  1);
fill_slot(m,  5,  8,  2);
std::cout << m << std::endl;
}
}

他们打印了Live On Coliru

{([0,8)->1)}
{([0,4)->1)([4,8)->3)}
{([0,4)->1)([5,8)->2)}