diff options
Diffstat (limited to 'lib')
| -rw-r--r-- | lib/collections.h | 38 |
1 files changed, 38 insertions, 0 deletions
diff --git a/lib/collections.h b/lib/collections.h index ea5d5dc..6f26eae 100644 --- a/lib/collections.h +++ b/lib/collections.h @@ -3,6 +3,7 @@ #include <algorithm> #include <array> #include <cstdint> +#include <ranges> #include <span> #include <tuple> #include <utility> @@ -224,3 +225,40 @@ strip_end(IterableCollection auto & cont) { return stripiter {cont.end()}; } + +template<typename T, typename Dist, typename Merger> +void +mergeClose(std::vector<T> & range, const Dist & dist, const Merger & merger, + decltype(dist(range.front(), range.front())) tolerance) +{ + using DistanceType = decltype(tolerance); + std::vector<DistanceType> distances; + distances.reserve(range.size() - 1); + std::ranges::transform(range | std::views::pairwise, std::back_inserter(distances), [&dist](const auto & pair) { + return (std::apply(dist, pair)); + }); + while (distances.size() > 1) { + const auto closestPair = std::ranges::min_element(distances); + if (*closestPair > tolerance) { + return; + } + const auto offset = std::distance(distances.begin(), closestPair); + const auto idx = static_cast<std::size_t>(offset); + if (closestPair == distances.begin()) { + // Remove second element + range.erase(range.begin() + 1); + distances.erase(distances.begin()); + } + else if (closestPair == --distances.end()) { + // Remove second from last element + range.erase(range.end() - 2); + distances.erase(distances.end() - 1); + } + else { + range[idx] = merger(range[idx], range[idx + 1]); + range.erase(range.begin() + offset + 1); + distances.erase(distances.begin() + offset); + } + distances[idx] = dist(range[idx], range[idx + 1]); + } +} |