Range consolidation: Difference between revisions
Added C++ solution
m (Show ranges before and after consolidation) |
(Added C++ solution) |
||
Line 198:
(-1, 2), (3, 10)
(-6, -1), (1, 8)</pre>
=={{header|C++}}==
<lang cpp>#include <algorithm>
#include <iostream>
#include <utility>
#include <vector>
// A range is represented as std::pair<from, to>
template <typename iterator>
void normalize_ranges(iterator begin, iterator end) {
for (iterator i = begin; i != end; ++i) {
if (i->second < i->first)
std::swap(i->first, i->second);
}
std::sort(begin, end);
}
template <typename iterator>
iterator merge_ranges(iterator begin, iterator end) {
for (iterator i = begin; i != end; ++i) {
iterator j = i;
int count = 0;
while (++j != end && j->first <= i->second) {
i->second = std::max(i->second, j->second);
++count;
}
if (count > 0) {
iterator k = i;
std::move(j, end, ++k);
std::advance(end, -count);
}
}
return end;
}
template <typename iterator>
iterator consolidate_ranges(iterator begin, iterator end) {
normalize_ranges(begin, end);
return merge_ranges(begin, end);
}
template <typename pair>
void print_range(std::ostream& out, const pair& range) {
out << '[' << range.first << ", " << range.second << ']';
}
template <typename iterator>
void print_ranges(std::ostream& out, iterator begin, iterator end) {
if (begin != end) {
print_range(out, *begin++);
for (; begin != end; ++begin) {
out << ", ";
print_range(out, *begin);
}
}
}
int main() {
std::vector<std::pair<double, double>> test_cases[] = {
{ {1.1, 2.2} },
{ {6.1, 7.2}, {7.2, 8.3} },
{ {4, 3}, {2, 1} },
{ {4, 3}, {2, 1}, {-1, -2}, {3.9, 10} },
{ {1, 3}, {-6, -1}, {-4, -5}, {8, 2}, {-6, -6} }
};
for (auto&& ranges : test_cases) {
print_ranges(std::cout, std::begin(ranges), std::end(ranges));
std::cout << " -> ";
auto i = consolidate_ranges(std::begin(ranges), std::end(ranges));
print_ranges(std::cout, std::begin(ranges), i);
std::cout << '\n';
}
return 0;
}</lang>
{{out}}
<pre>
[1.1, 2.2] -> [1.1, 2.2]
[6.1, 7.2], [7.2, 8.3] -> [6.1, 8.3]
[4, 3], [2, 1] -> [1, 2], [3, 4]
[4, 3], [2, 1], [-1, -2], [3.9, 10] -> [-2, -1], [1, 2], [3, 10]
[1, 3], [-6, -1], [-4, -5], [8, 2], [-6, -6] -> [-6, -1], [1, 8]
</pre>
=={{header|Dyalect}}==
| |||