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, функторы и т. Д.
Решение
Это более сложно для 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)}
Другие решения
Других решений пока нет …