Алгоритм — Необходим: класс C ++ для поддержки одномерного списка экстентов

Я ищу класс C ++, который может поддерживать одномерный список экстентов.

Каждый экстент определяется как (start,len) пара.

Я хочу иметь возможность добавлять дополнительные экстенты в список и автоматически объединять их. То есть, если у нас есть (0,5) а также (10,5) в списке, и (5,5) добавлен, новый список должен содержать только (0,15),

Экстенты никогда не удаляются из списка.

Существует ли что-нибудь подобное?

Благодарю.

5

Решение

Вы ищете Boost.Icl. Это именно то, что вы описали.

http://www.boost.org/doc/libs/1_52_0/libs/icl/doc/html/index.html

5

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

Вот пример реализации простого интервального контейнера:

#include <iostream>
#include <vector>
#include <memory>
#include <algorithm>

using std::vector;
using std::pair;
using std::make_pair;

typedef pair<int, int> interval;

struct interval_container
{
void add(int start, int len)
{
_data.emplace_back( make_pair(start, len) );
}

void consolidate()
{
// sort intervals first by start then by length
std::sort(_data.begin(), _data.end());

// create temp data
vector<interval> consolidated;

// iterate over all sorted intervals
for(const interval& i : _data)
{
int start = i.first;
int len = i.second;

// special case: first interval
if (consolidated.empty())
{
consolidated.emplace_back(i);
}
// all other cases
else
{
// get last interval in the consolidated array
interval& last = consolidated.back();
int& last_start = last.first;
int& last_len = last.second;// if the current interval can be merged with the last one
if ((start >= last_start) and (start < (last_start + last_len)))
{
// merge the interval with the last one
last_len = std::max(last_len, (start + len - last_start));
}
// if the current interval can't be merged with the last one
else
{
consolidated.emplace_back(i);
}
}
}

// copy consolidated data
_data = consolidated;
}vector<interval>& data() { return _data; }

private:
vector<interval> _data;
};int main()
{
interval_container intervals;

intervals.add(0, 2);
intervals.add(1, 3);
intervals.add(5, 3);

intervals.consolidate();

int c(0);
for(interval i : intervals.data())
{
std::cout << (c++) << ": from " << i.first << " to " << (i.first + i.second) << std::endl;
}
}
2

По вопросам рекламы [email protected]