From 38547fe8ef1595726706ee3ecc7d33aaf352fbf7 Mon Sep 17 00:00:00 2001
From: Dan Goodliffe <dan@randomdan.homeip.net>
Date: Sat, 29 Jun 2024 17:55:32 +0100
Subject: Implement partition on InstanceVertices

---
 gfx/gl/instanceVertices.h | 23 +++++++++++++++++++++++
 1 file changed, 23 insertions(+)

(limited to 'gfx/gl/instanceVertices.h')

diff --git a/gfx/gl/instanceVertices.h b/gfx/gl/instanceVertices.h
index d9d9123..ad1716d 100644
--- a/gfx/gl/instanceVertices.h
+++ b/gfx/gl/instanceVertices.h
@@ -124,6 +124,13 @@ public:
 		return base::size();
 	}
 
+	template<typename Pred>
+	glContainer<T>::iterator
+	partition(Pred pred)
+	{
+		return partition(base::begin(), base::end(), pred);
+	}
+
 protected:
 	friend InstanceProxy;
 
@@ -152,6 +159,22 @@ protected:
 		return base::data()[index[pindex]];
 	}
 
+	template<typename Pred>
+	glContainer<T>::iterator
+	partition(glContainer<T>::iterator first, glContainer<T>::iterator last, Pred pred)
+	{
+		while (first < last) {
+			first = std::find_if_not(first, last, pred);
+			last = --std::find_if(std::make_reverse_iterator(last), std::make_reverse_iterator(first), pred).base();
+			if (first < last) {
+				std::iter_swap(first, last);
+				std::iter_swap(std::find(index.begin(), index.end(), first - base::begin()),
+						std::find(index.begin(), index.end(), last - base::begin()));
+			}
+		}
+		return first;
+	}
+
 	//  Index into buffer given to nth proxy
 	std::vector<size_t> index;
 	//  List of free spaces in index
-- 
cgit v1.2.3