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

Question

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

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)}