Range consolidation: Difference between revisions
Content added Content deleted
m (Show ranges before and after consolidation) |
(Added C++ solution) |
||
Line 198: | Line 198: | ||
(-1, 2), (3, 10) |
(-1, 2), (3, 10) |
||
(-6, -1), (1, 8)</pre> |
(-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}}== |
=={{header|Dyalect}}== |