Boost `interval_map` — как настроить агрегацию на ощупь

Question

Boost `interval_map` — как настроить агрегацию на ощупь

Повышение ICL interval_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, функторы и т. Д.

1

boost-icl c++

Решение

Другие решения

Других решений пока нет …

Источник

Accepted Answer

Это более сложно для 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;
}
}

И они печатают Жить на Колиру

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

1