C
Simple Variante für halboffene Intervalle.
#include <iostream>
#include <iterator>
#include <set>
#include <type_traits>
#include <utility>
struct interval {
// Invariant: lbound < rbound
int lbound;
int rbound;
};
bool operator<(const interval& lhs, const interval& rhs) {
return lhs.rbound < rhs.lbound; // induces total ordering if intervals not connected
}
std::ostream& operator<<(std::ostream& s, const interval& i) {
return s << '[' << i.lbound << ',' << i.rbound << ')';
}
void merge(std::set<interval>& s, interval i) {
auto [first, last] = s.equal_range(i);
if (first == last) {
s.insert(last, i);
return;
}
i.lbound = std::min(i.lbound, first->lbound);
i.rbound = std::max(i.rbound, prev(last)->rbound);
s.insert(s.erase(first, last), i);
}
template <typename Iter, std::enable_if_t<std::is_same_v<typename std::iterator_traits<Iter>::value_type, interval>, int> = 0>
std::set<interval> merge(Iter first, Iter last) {
std::set<interval> result;
for (;first != last; ++first)
merge(result, *first);
return result;
}
std::set<interval> intersect(const std::set<interval>& s, interval i) {
std::set<interval> result;
auto [first, last] = s.equal_range(i);
if (first == last)
return result;
auto lbound = std::max(i.lbound, first->lbound);
auto rbound = std::min(i.rbound, first->rbound);
if (lbound != rbound)
result.insert({ lbound, rbound });
if (++first == last--)
return result;
result.insert(first, last);
lbound = last->lbound;
rbound = std::min(i.rbound, last->rbound);
if (lbound != rbound)
result.insert(result.end(), { lbound, rbound });
return result;
}
#include <vector>
int main() {
std::vector<interval> sets{ { 0, 30 }, { 40, 70 }, { 20, 60 }, { 80, 100 } };
for (auto& x : sets)
std::cout << x << ',';
interval reference{ 10, 90 };
std::cout << '\n' << reference << '\n';
for (auto& x : intersect(merge(sets.begin(), sets.end()), reference))
std::cout << x << ',';
std::cout << '\n';
}
