увеличить непересекающиеся наборы интервалов
Я пытаюсь использовать boost: disjoint_sets для непересекающихся интервалов (в моем случае интервалы в наборе не должны пересекаться между его членами), которые представлены следующей структурой:
struct dataum {
int x,y;
bool operator< (const dataum& o) const { return y < o.x ; }
bool operator==(const dataum& o) const {
if(x <= o.x && o.x <= y && y <= o.y )
return true;
if(x <= o.x && o.y <= y)
return true;
if(o.x <= x && y <= o.y)
return true;
if(o.x <= x && x <= o.y && o.y <= y )
return true;
return false;
}
bool operator!=(const dataum& o) const {
return !operator==(o);
}
};
Допустим, у меня есть список интервалов, например ([1,3], [4,5], [6,10], [8,9]). Я инициализирую несвязанный набор, как показано ниже:
boost::disjoint_sets<
associative_property_map<std::map<dataum,int>>,
associative_property_map<std::map<dataum,dataum>> > ds(
make_assoc_property_map(rank),
make_assoc_property_map(parent));
Затем я выполняю make_set во всех элементах моего списка, что приведет к 4 непересекающимся наборам, верно? После этого я выполняю следующие операции:
std::cout << ds.count_sets(S.begin(), S.end()) << std::endl;
ds.union_set(S[0],S[1]);
ds.union_set(S[1],S[2]);
std::cout << ds.count_sets(S.begin(), S.end()) << std::endl;
Что я не понимаю, так это то, почему последний кут говорит, что у меня есть только один набор, который в моем понимании должен сказать, что у меня есть 2 набора {[1,3], [4,5], [6,10]} и {[8,9]}.
Может ли кто-нибудь помочь мне понять, что происходит?
Решение
Я не совсем уверен, что понимаю, что вы пытаетесь сделать, но посмотрите на Boost ICL:
#include <boost/icl/split_interval_set.hpp>
#include <iostream>
using dset = boost::icl::split_interval_set<int>;
using dataum = dset::interval_type;int main() {
dset data;
for (auto i : {
dataum::closed (1,3),
dataum::closed (4,5),
dataum::closed (6,10),
dataum::closed (8,9),
})
{
data.insert(i);
std::cout << data << "\n";
}
}
Выход
{[1,3]}
{[1,3][4,5]}
{[1,3][4,5][6,10]}
{[1,3][4,5][6,8)[8,9](9,10]}
Другие решения