Я ищу класс C ++, который может поддерживать одномерный список экстентов.
Каждый экстент определяется как (start,len)
пара.
Я хочу иметь возможность добавлять дополнительные экстенты в список и автоматически объединять их. То есть, если у нас есть (0,5)
а также (10,5)
в списке, и (5,5)
добавлен, новый список должен содержать только (0,15)
,
Экстенты никогда не удаляются из списка.
Существует ли что-нибудь подобное?
Благодарю.
Вы ищете Boost.Icl. Это именно то, что вы описали.
http://www.boost.org/doc/libs/1_52_0/libs/icl/doc/html/index.html
Вот пример реализации простого интервального контейнера:
#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;
}
}