1 files changed, 45 insertions, 11 deletions

diff --git a/gfx/gl/instanceVertices.h b/gfx/gl/instanceVertices.h
index a89aa78..28e11ee 100644
--- a/gfx/gl/instanceVertices.h
+++ b/gfx/gl/instanceVertices.h
@@ -1,7 +1,6 @@
 #pragma once
 
 #include "glContainer.h"
-#include "pack.h"
 #include <cassert>
 #include <special_members.h>
 #include <utility>
@@ -14,7 +13,8 @@ public:
 	public:
 		InstanceProxy(InstanceVertices * iv, std::size_t idx) : instances {iv}, index {idx} { }
 
-		InstanceProxy(InstanceProxy && other) : instances {std::exchange(other.instances, nullptr)}, index {other.index}
+		InstanceProxy(InstanceProxy && other) noexcept :
+			instances {std::exchange(other.instances, nullptr)}, index {other.index}
 		{
 		}
 
@@ -28,7 +28,7 @@ public:
 		}
 
 		InstanceProxy &
-		operator=(InstanceProxy && other)
+		operator=(InstanceProxy && other) noexcept
 		{
 			if (instances) {
 				instances->release(index);
@@ -39,17 +39,20 @@ public:
 		}
 
 		template<typename U>
-		T &
+		InstanceProxy &
 		operator=(U && v)
 		{
-			return instances->lookup(index) = std::forward<U>(v);
+			instances->lookup(index) = std::forward<U>(v);
+			return *this;
 		}
 
+		// NOLINTNEXTLINE)hicpp-explicit-conversions
 		[[nodiscard]] operator T &()
 		{
 			return instances->lookup(index);
 		}
 
+		// NOLINTNEXTLINE)hicpp-explicit-conversions
 		[[nodiscard]] operator const T &() const
 		{
 			return instances->lookup(index);
@@ -104,10 +107,12 @@ public:
 			auto idx = unused.back();
 			unused.pop_back();
 			index[idx] = base::size();
+			reverseIndex.emplace_back(idx);
 			base::emplace_back(std::forward<Params>(params)...);
 			return InstanceProxy {this, idx};
 		}
 		index.emplace_back(base::size());
+		reverseIndex.push_back(base::size());
 		base::emplace_back(std::forward<Params>(params)...);
 		return InstanceProxy {this, index.size() - 1};
 	}
@@ -121,25 +126,35 @@ public:
 		return base::size();
 	}
 
+	template<typename Pred>
+	glContainer<T>::iterator
+	partition(Pred pred)
+	{
+		return partition(base::begin(), base::end(), pred);
+	}
+
 protected:
+	static constexpr auto npos = static_cast<size_t>(-1);
 	friend InstanceProxy;
 
 	void
 	release(const size_t pidx)
 	{
-		if (base::size() - 1 != index[pidx]) {
+		if (const size_t last = base::size() - 1; last != index[pidx]) {
 			lookup(pidx) = std::move(base::back());
-			*std::find_if(index.begin(), index.end(), [this, old = base::size() - 1](const auto & i) {
-				return i == old && !std::binary_search(unused.begin(), unused.end(), &i - index.data());
-			}) = index[pidx];
+			const auto movedKey = reverseIndex[last];
+			index[movedKey] = std::exchange(index[pidx], npos);
+			reverseIndex[index[movedKey]] = movedKey;
 		}
 		base::pop_back();
+		reverseIndex.pop_back();
 		if (pidx == index.size() - 1) {
 			index.pop_back();
 		}
 		else {
-			// Remember p.index is free index now, keeping it sorted
-			unused.insert(std::upper_bound(unused.begin(), unused.end(), pidx), pidx);
+			index[pidx] = npos;
+			// Remember p.index is free index now
+			unused.emplace_back(pidx);
 		}
 	}
 
@@ -149,8 +164,27 @@ 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);
+				const auto fidx = static_cast<size_t>(first - base::begin()),
+						   lidx = static_cast<size_t>(last - base::begin());
+				std::swap(index[reverseIndex[fidx]], index[reverseIndex[lidx]]);
+				std::swap(reverseIndex[fidx], reverseIndex[lidx]);
+			}
+		}
+		return first;
+	}
+
 	//  Index into buffer given to nth proxy
 	std::vector<size_t> index;
+	std::vector<size_t> reverseIndex;
 	//  List of free spaces in index
 	std::vector<size_t> unused;
 };