Add support for partitioning by 2 unary predicates

Second predicate creates a single block of truthy values in the middle,
and two falsy blocks at each end.

3 files changed, 91 insertions, 2 deletions

diff --git a/gfx/gl/instanceVertices.h b/gfx/gl/instanceVertices.h
index 629c664..de20871 100644
--- a/gfx/gl/instanceVertices.h
+++ b/gfx/gl/instanceVertices.h
@@ -2,6 +2,7 @@
 
 #include "glContainer.h"
 #include <cassert>
+#include <functional>
 #include <special_members.h>
 #include <utility>
 
@@ -133,6 +134,19 @@ public:
 		return indexOf(partition(base::begin(), base::end(), pred));
 	}
 
+	using PartitionResult
+			= std::pair<typename base::size_type, std::pair<typename base::size_type, typename base::size_type>>;
+
+	template<typename Pred1, typename Pred2>
+	PartitionResult
+	partition(Pred1 pred1, Pred2 pred2)
+	{
+		auto boundary1 = partition(base::begin(), base::end(), pred1);
+		auto begin2 = partition(base::begin(), boundary1, std::not_fn(pred2));
+		auto end2 = partition(boundary1, base::end(), pred2);
+		return {indexOf(boundary1), {indexOf(begin2), indexOf(end2)}};
+	}
+
 protected:
 	static constexpr auto npos = static_cast<size_t>(-1);
 	friend InstanceProxy;
diff --git a/test/perf-instancing.cpp b/test/perf-instancing.cpp
index a56d60e..f3d16a8 100644
--- a/test/perf-instancing.cpp
+++ b/test/perf-instancing.cpp
@@ -26,7 +26,7 @@ namespace {
 	};
 
 	void
-	partition(benchmark::State & state)
+	partition1(benchmark::State & state)
 	{
 		TestMainWindowAppBase window;
 		Data data(static_cast<size_t>(state.range()));
@@ -39,8 +39,28 @@ namespace {
 			pos %= 1000000;
 		}
 	}
+
+	void
+	partition2(benchmark::State & state)
+	{
+		TestMainWindowAppBase window;
+		Data data(static_cast<size_t>(state.range()));
+		GlobalPosition2D pos {};
+		for (auto loop : state) {
+			data.instances.partition(
+					[&pos](const auto & instance) {
+						return std::abs(instance.pos.x - pos.x) < 5;
+					},
+					[&pos](const auto & instance) {
+						return std::abs(instance.pos.y - pos.y) < 5;
+					});
+			pos += GlobalPosition2D {33, 17};
+			pos %= 1000000;
+		}
+	}
 }
 
-BENCHMARK(partition)->Range(0, 1 << 20);
+BENCHMARK(partition1)->Range(0, 1 << 20);
+BENCHMARK(partition2)->Range(0, 1 << 20);
 
 BENCHMARK_MAIN();
diff --git a/test/test-instancing.cpp b/test/test-instancing.cpp
index f303a15..4748f93 100644
--- a/test/test-instancing.cpp
+++ b/test/test-instancing.cpp
@@ -255,4 +255,59 @@ BOOST_AUTO_TEST_CASE(PartitionBy, *boost::unit_test::timeout(1))
 	checkReverseIndex();
 }
 
+BOOST_AUTO_TEST_CASE(PartitionBy2, *boost::unit_test::timeout(1))
+{
+	std::mt19937 gen(std::random_device {}());
+	std::uniform_int_distribution<int> dist(0, 100000);
+	static constexpr auto COUNT = 20;
+	reserve(COUNT);
+	std::vector<decltype(acquire(0))> instances;
+	instances.reserve(COUNT);
+	// At least one of each
+	instances.push_back(acquire(1));
+	instances.push_back(acquire(3));
+	while (instances.size() < COUNT) {
+		instances.push_back(acquire(dist(gen)));
+	}
+	const std::vector<int> values(instances.begin(), instances.end());
+	BOOST_REQUIRE_EQUAL(size(), COUNT);
+
+	const auto pred3 = [](auto value) {
+		return (value % 3) == 0;
+	};
+	const auto pred5 = [](auto value) {
+		return (value % 5) == 0;
+	};
+	auto matchedBoundaries = partition(pred3, pred5);
+	// As PartitionBy... primary partition is normal layout
+	// The underlying data is partitioned...
+	BOOST_REQUIRE(std::is_partitioned(mkcspan().cbegin(), mkcspan().cend(), pred3));
+	// The external view of the data is unchanged...
+	BOOST_CHECK_EQUAL_COLLECTIONS(values.cbegin(), values.cend(), instances.cbegin(), instances.cend());
+	// The partition point is right...
+	BOOST_CHECK(!pred3(at(matchedBoundaries.first)));
+	BOOST_CHECK(pred3(at(matchedBoundaries.first - 1)));
+
+	// Secondary partition lives contiguous in the middle somewhere, with two falsy blocks at each end
+	const auto p2bndry = matchedBoundaries.second;
+
+	BOOST_TEST_CONTEXT(mkcspan()) {
+		BOOST_TEST_CONTEXT(matchedBoundaries.first) {
+			BOOST_CHECK(std::all_of(
+					mkcspan().cbegin(), mkcspan().cbegin() + static_cast<int>(matchedBoundaries.first), pred3));
+			BOOST_CHECK(std::none_of(
+					mkcspan().cbegin() + static_cast<int>(matchedBoundaries.first), mkcspan().cend(), pred3));
+		}
+
+		BOOST_TEST_CONTEXT(p2bndry) {
+			BOOST_CHECK(std::all_of(mkcspan().cbegin() + static_cast<int>(p2bndry.first),
+					mkcspan().begin() + static_cast<int>(p2bndry.second), pred5));
+			BOOST_CHECK(std::none_of(mkcspan().cbegin(), mkcspan().cbegin() + static_cast<int>(p2bndry.first), pred5));
+			BOOST_CHECK(std::none_of(mkcspan().cbegin() + static_cast<int>(p2bndry.second), mkcspan().cend(), pred5));
+		}
+	}
+
+	checkReverseIndex();
+}
+
 BOOST_AUTO_TEST_SUITE_END()