Add helper for merging close elements in a vector

2 files changed, 71 insertions, 1 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]);
+	}
+}
diff --git a/test/test-lib.cpp b/test/test-lib.cpp
index 5f0b5e5..7672acc 100644
--- a/test/test-lib.cpp
+++ b/test/test-lib.cpp
@@ -1,8 +1,8 @@
 #define BOOST_TEST_MODULE test_lib
 
-#include "testHelpers.h"
 #include <boost/test/data/test_case.hpp>
 #include <boost/test/unit_test.hpp>
+#include <stream_support.h>
 
 #include <collections.h>
 #include <glArrays.h>
@@ -69,3 +69,35 @@ BOOST_AUTO_TEST_CASE(triangle_strip_iter)
 	BOOST_CHECK_EQUAL_COLLECTIONS(
 			out.begin(), out.end(), TRIANGLE_STRIP_EXPECTED.begin(), TRIANGLE_STRIP_EXPECTED.end());
 }
+
+using MergeCloseData = std::tuple<std::vector<int>, int, std::vector<int>>;
+
+BOOST_DATA_TEST_CASE(mergeCloseInts,
+		boost::unit_test::data::make<MergeCloseData>({
+				{{0}, 0, {0}},
+				{{0, 1}, 0, {0, 1}},
+				{{0, 1}, 2, {0, 1}},
+				{{0, 1, 2}, 2, {0, 2}},
+				{{0, 1, 4}, 2, {0, 4}},
+				{{0, 1, 2}, 4, {0, 2}},
+				{{0, 4, 8}, 4, {0, 8}},
+				{{0, 4, 10, 14}, 4, {0, 14}},
+				{{0, 3, 6}, 2, {0, 3, 6}},
+				{{0, 3, 4}, 2, {0, 4}},
+				{{0, 5, 7, 12}, 4, {0, 6, 12}},
+				{{0, 3, 4, 5, 10, 17, 18, 19}, 2, {0, 4, 10, 19}},
+		}),
+		collection, tolerance, expected)
+{
+	auto mutableCollection {collection};
+	BOOST_REQUIRE_NO_THROW((mergeClose(
+			mutableCollection,
+			[](int left, int right) {
+				return std::abs(left - right);
+			},
+			[](int left, int right) {
+				return (left + right) / 2;
+			},
+			tolerance)));
+	BOOST_CHECK_EQUAL_COLLECTIONS(mutableCollection.begin(), mutableCollection.end(), expected.begin(), expected.end());
+}