Выделение в кодомене interval_map
В моем текущем проекте процессы, различимые интервалы, должны быть объединены, если они являются смежными.
Для этого я хотел использовать фантастический boost::icl библиотека. Каждый процесс может быть уникально идентифицирован по его идентификатору.
Сначала я добавляю несколько интервалов в мой interval_map, Теперь я хотел сделать две вещи:
- Итерация по всем встречающимся типам процессов (Здесь id = 1,4,7)
- Во-вторых, переберите все процессы, относящиеся к определенному подмножеству видов, таким образом, чтобы слияние перекрывающихся интервалов выполнялось автоматически.
Это то, что я получил так далеко:
#include <iostream>
#include <set>
#include <boost/icl/interval_map.hpp>
#include "boost/icl/closed_interval.hpp"
struct Process {
int id;
};
bool operator==(const Process& p, const Process& q) {
return p.id == q.id;
}
bool operator<(const Process& p, const Process& q) {
return p.id < q.id;
}
std::ostream& operator<<(std::ostream& str, const Process& p) {
str << "Process{" << p.id << "}";
return str;
}
int main(int, char**) {
using namespace boost::icl;
interval_map<double, std::set<Process>> imap;
imap.add({ interval<double>::closed(0., 4.),{ Process{ 4 } } });
imap.add({ interval<double>::closed(2., 6.),{ Process{ 1 } } });
imap.add({ interval<double>::closed(4., 9.),{ Process{ 4 } } });
imap.add({ interval<double>::closed(8., 8.),{ Process{ 7 } } });
for (auto&& iter : imap) {
std::cout << iter.first << " - " << iter.second<< std::endl;
}
for (auto iter : find(imap, { Process{4} })) { // How to implement find on codomain
// Should print:
// [0.,4.] - { Process{4}}
// [4.,9.] - { Process{4}}
std::cout << iter.first << " - " << iter.second << std::endl;
}
}
Решение
Во-первых, наблюдение, так как интервалы закрыты, [0,4] а также [4,6] на самом деле не примыкающий, но перекрывая Ты имел ввиду right_open?
Во-вторых, интервальная карта моделирует функцию, отображение не гарантируется инъективны.
В ограниченном объеме вашего примера кажется, что вы бы предпочли инвертировать структуру данных, чтобы получить:
#include "boost/icl/closed_interval.hpp"#include <boost/icl/interval_map.hpp>
#include <iostream>
#include <set>
#include <map>
struct Process {
int id;
friend bool operator==(const Process& p, const Process& q) { return p.id == q.id; }
friend bool operator<(const Process& p, const Process& q) { return p.id < q.id; }
friend std::ostream& operator<<(std::ostream& str, const Process& p) {
return str << "Process{" << p.id << "}";
}
};
int main(int, char**) {
using namespace boost::icl;
using Map = std::map<Process, boost::icl::interval_set<double> >; // instead of boost::icl::interval_map<double, std::set<Process> >;
using IVal = Map::mapped_type::interval_type;
Map imap;
imap[{4}] += IVal::right_open(0, 4);
imap[{1}] += IVal::right_open(2, 6);
imap[{4}] += IVal::right_open(4, 9);
imap[{7}] += IVal::closed(8, 8);
//for (auto&& el : imap) { std::cout << el.first << " - " << el.second << std::endl; }
Process key{4};
std::cout << key << " - " << imap[key];
}
Это приводит к:
Process{4} - {[0,9)}
Именно это, как я думаю, вы имели в виду «таким образом, что объединение перекрывающихся интервалов выполняется автоматически».
Имея оба
Конечно, вы можете получить обратные отображения из исходной структуры данных:
template <typename IMap>
auto inverted(IMap const& imap) {
std::map<typename IMap::codomain_type::value_type, boost::icl::interval_set<typename IMap::domain_type> > output;
for (auto& el : imap)
for (auto& key: el.second)
output[key] += el.first;
return output;
}
Видеть это Жить на Колиру
#include "boost/icl/closed_interval.hpp"#include <boost/icl/interval_map.hpp>
#include <iostream>
#include <set>
struct Process {
int id;
friend bool operator==(const Process& p, const Process& q) { return p.id == q.id; }
friend bool operator<(const Process& p, const Process& q) { return p.id < q.id; }
};
std::ostream& operator<<(std::ostream& str, const Process& p) {
str << "Process{" << p.id << "}";
return str;
}
template <typename IMap>
auto inverted(IMap const& imap) {
std::map<typename IMap::codomain_type::value_type, boost::icl::interval_set<typename IMap::domain_type> > output;
for (auto& el : imap)
for (auto& key: el.second)
output[key] += el.first;
return output;
}
int main(int, char**) {
using namespace boost::icl;
using IMap = boost::icl::interval_map<double, std::set<Process> >;
using IVal = IMap::interval_type;
IMap imap;
imap.add({ IVal::right_open(0, 4), {Process{ 4 }} });
imap.add({ IVal::right_open(2, 6), {Process{ 1 }} });
imap.add({ IVal::right_open(4, 9), {Process{ 4 }} });
imap.add({ IVal::closed(8, 8), {Process{ 7 }} });
std::cout << imap << "\n\n";
for (auto&& iter : imap) {
std::cout << iter.first << " - " << iter.second << std::endl;
}
Process key{4};
std::cout << key << " - " << inverted(imap)[key] << "\n";
}
Больше заметок
Запрос нескольких ключей в домен непосредственно поддерживается, см. хороший набор указателей здесь:
- использование split_interval_map, эффективный поиск всех интервалов, пересекающих точку
- увеличить поиск multi_index_container для записей, которые попадают в интервалы, определенные двумя полями
Вы всегда можете создать свою собственную структуру данных, которая обеспечивает двунаправленные индексы, такие как показано, например.
Другие решения
Других решений пока нет …