Комбинации N Boost interval_set

Как Я догадался, здесь есть подход «высокого уровня».

Контейнеры Boost ICL — это больше, чем просто контейнеры «прославленных пар интервалов начальной / конечной точек». Они предназначены для реализации только то бизнес объединения, поиска, в общем оптимизированном виде.

Так вы не надо

Если вы позволите библиотеке делать то, что она должна делать:

using TimePoint = unsigned;
using DownTimes = boost::icl::interval_set<TimePoint>;
using Interval  = DownTimes::interval_type;
using Records   = std::vector<DownTimes>;

Использование функциональных доменных typedefs предлагает подход более высокого уровня. Теперь давайте зададим гипотетический «деловой вопрос»:

Что мы на самом деле хотим сделать с нашими записями простоев по месту службы?

Ну, по сути, мы хотим

1. подсчитать их для всех заметных временных интервалов и
2. отфильтруйте те, где подсчеты не менее 2
3. наконец, мы хотели бы показать «объединенные» временные интервалы, которые остались.

Хорошо, инженер: внедри это!

1. Хм. Тальманские. Как трудно это может быть?

   To Ключом к элегантным решениям является выбор правильной структуры данных

   using Tally     = unsigned; // or: bit mask representing affected locations?
   using DownMap   = boost::icl::interval_map<TimePoint, Tally>;
   

   Теперь это просто массовая вставка:

   // We will do a tally of affected locations per time slot
   DownMap tallied;
   for (auto& location : records)
   for (auto& incident : location)
   tallied.add({incident, 1u});
   

2. Хорошо, давайте отфильтруем. Нам просто нужен предикат, который работает на нашем DownMap, верно

   // define threshold where at least 2 locations have an outage
   auto exceeds_threshold = [](DownMap::value_type const& slot) {
   return slot.second >= 2;
   };
   

3. Объедините временные интервалы!

   На самом деле. Мы просто создаем еще один набор DownTimes, верно. Просто не в этот раз.

   Выбор структуры данных снова побеждает:

   // just printing the union of any criticals:
   DownTimes merged;
   for (auto&& slot : tallied | filtered(exceeds_threshold) | map_keys)
   merged.insert(slot);
   

Доклад!

std::cout << "Criticals: " << merged << "\n";

Обратите внимание, что нигде мы не приблизились к манипулированию индексами массива, перекрывающимся или непересекающимся интервалам, закрытым или открытым границам. Или [eeeeek!] Перестановки элементов грубой силы.

Мы только что сформулировали наши цели, и пусть библиотека сделает всю работу.

Полная демонстрация

Жить на Колиру

#include <boost/icl/interval_set.hpp>
#include <boost/icl/interval_map.hpp>
#include <boost/range.hpp>
#include <boost/range/algorithm.hpp>
#include <boost/range/adaptors.hpp>
#include <boost/range/numeric.hpp>
#include <boost/range/irange.hpp>
#include <algorithm>
#include <iostream>
#include <vector>

using TimePoint = unsigned;
using DownTimes = boost::icl::interval_set<TimePoint>;
using Interval  = DownTimes::interval_type;
using Records   = std::vector<DownTimes>;

using Tally     = unsigned; // or: bit mask representing affected locations?
using DownMap   = boost::icl::interval_map<TimePoint, Tally>;

// Just for fun, removed the explicit loops from the generation too. Obviously,
// this is bit gratuitous :)
static DownTimes generate_downtime(int j) {
return boost::accumulate(
boost::irange(0, 5),
DownTimes{},
[j](DownTimes accum, int i) { return accum + Interval::closed((i*10), ((i*10) + 5 - j)); }
);
}

int main() {
// Initializing data for test
using namespace boost::adaptors;
auto const records = boost::copy_range<Records>(boost::irange(0,4) | transformed(generate_downtime));

for (auto location : records | indexed()) {
std::cout << "Location " << (location.index()+1) << " " << location.value() << std::endl;
}

// We will do a tally of affected locations per time slot
DownMap tallied;
for (auto& location : records)
for (auto& incident : location)
tallied.add({incident, 1u});

// We will combine them so we get an interval_set defined for those periods
// where at least 2 locations have an outage
auto exceeds_threshold = [](DownMap::value_type const& slot) {
return slot.second >= 2;
};

// just printing the union of any criticals:
DownTimes merged;
for (auto&& slot : tallied | filtered(exceeds_threshold) | map_keys)
merged.insert(slot);

std::cout << "Criticals: " << merged << "\n";
}

Какие отпечатки

Location 1 {[0,5][10,15][20,25][30,35][40,45]}
Location 2 {[0,4][10,14][20,24][30,34][40,44]}
Location 3 {[0,3][10,13][20,23][30,33][40,43]}
Location 4 {[0,2][10,12][20,22][30,32][40,42]}
Criticals: {[0,4][10,14][20,24][30,34][40,44]}