Maintain a reverse index in instance vertices

Removes need to search unused and/or index when moving/adding things

3 files changed, 80 insertions, 16 deletions

diff --git a/gfx/gl/instanceVertices.h b/gfx/gl/instanceVertices.h
index ad1716d..28e11ee 100644
--- a/gfx/gl/instanceVertices.h
+++ b/gfx/gl/instanceVertices.h
@@ -107,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};
 	}
@@ -132,24 +134,27 @@ public:
 	}
 
 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);
 		}
 	}
 
@@ -168,8 +173,10 @@ protected:
 			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()));
+				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;
@@ -177,6 +184,7 @@ protected:
 
 	//  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;
 };
diff --git a/test/test-instancing.cpp b/test/test-instancing.cpp
index 37f32c8..77467d8 100644
--- a/test/test-instancing.cpp
+++ b/test/test-instancing.cpp
@@ -13,12 +13,33 @@
 BOOST_GLOBAL_FIXTURE(ApplicationBase);
 BOOST_GLOBAL_FIXTURE(TestMainWindow);
 
-BOOST_FIXTURE_TEST_SUITE(i, InstanceVertices<int>)
+struct TestInstanceVertices : public InstanceVertices<int> {
+	void
+	checkReverseIndex(std::source_location ctx = std::source_location::current())
+	{
+		BOOST_TEST_CONTEXT(ctx.function_name() << ":" << ctx.line()) {
+			std::vector<size_t> genIndexIndex(size(), npos);
+			for (size_t i {}; i < index.size(); i++) {
+				if (index[i] != npos) {
+					BOOST_REQUIRE_EQUAL(genIndexIndex.at(index[i]), npos);
+					genIndexIndex.at(index[i]) = i;
+				}
+			}
+
+			BOOST_TEST_CONTEXT(reverseIndex << genIndexIndex) {
+				BOOST_CHECK_EQUAL_COLCOL(reverseIndex, genIndexIndex);
+			}
+		}
+	}
+};
+
+BOOST_FIXTURE_TEST_SUITE(i, TestInstanceVertices)
 
 BOOST_AUTO_TEST_CASE(createDestroy)
 {
 	BOOST_CHECK(unused.empty());
 	BOOST_CHECK(index.empty());
+	BOOST_CHECK(reverseIndex.empty());
 }
 
 BOOST_AUTO_TEST_CASE(acquireRelease)
@@ -29,11 +50,14 @@ BOOST_AUTO_TEST_CASE(acquireRelease)
 		BOOST_CHECK_EQUAL(1, size());
 		BOOST_REQUIRE_EQUAL(1, index.size());
 		BOOST_CHECK_EQUAL(0, index.front());
+		BOOST_REQUIRE_EQUAL(1, reverseIndex.size());
+		BOOST_CHECK_EQUAL(0, reverseIndex.front());
 		BOOST_CHECK(unused.empty());
 	}
 	BOOST_CHECK_EQUAL(0, size());
 	BOOST_CHECK(unused.empty());
 	BOOST_CHECK(index.empty());
+	BOOST_CHECK(reverseIndex.empty());
 }
 
 BOOST_AUTO_TEST_CASE(acquireReleaseMove)
@@ -50,6 +74,7 @@ BOOST_AUTO_TEST_CASE(acquireReleaseMove)
 	BOOST_CHECK_EQUAL(0, size());
 	BOOST_CHECK(unused.empty());
 	BOOST_CHECK(index.empty());
+	BOOST_CHECK(reverseIndex.empty());
 }
 
 BOOST_AUTO_TEST_CASE(autoMapUnmap)
@@ -100,15 +125,13 @@ BOOST_AUTO_TEST_CASE(shuffle)
 	BOOST_CHECK_EQUAL(at(2), *proxies[2].get());
 	BOOST_CHECK_EQUAL(at(3), *proxies[3].get());
 	BOOST_CHECK(unused.empty());
-	BOOST_REQUIRE_EQUAL(4, index.size());
-	BOOST_CHECK_EQUAL(0, index[0]);
-	BOOST_CHECK_EQUAL(1, index[1]);
-	BOOST_CHECK_EQUAL(2, index[2]);
-	BOOST_CHECK_EQUAL(3, index[3]);
+	BOOST_CHECK_EQUAL_COLVALS(index, 0, 1, 2, 3);
+	checkReverseIndex();
 	// Remove 1, 3 moves to [1]
 	proxies.erase(proxies.begin() + 1);
 	BOOST_REQUIRE_EQUAL(3, proxies.size());
-	BOOST_REQUIRE_EQUAL(4, index.size());
+	BOOST_CHECK_EQUAL_COLVALS(index, 0, npos, 2, 1);
+	BOOST_CHECK_EQUAL_COLVALS(reverseIndex, 0, 3, 2);
 	BOOST_REQUIRE_EQUAL(1, unused.size());
 	BOOST_CHECK_EQUAL(1, unused[0]);
 	BOOST_CHECK_EQUAL(at(0), *proxies[0].get());
@@ -117,6 +140,8 @@ BOOST_AUTO_TEST_CASE(shuffle)
 	//  Remove 1, 2 moves to [1]
 	proxies.erase(proxies.begin() + 1);
 	BOOST_REQUIRE_EQUAL(4, index.size());
+	BOOST_CHECK_EQUAL_COLVALS(index, 0, npos, npos, 1);
+	checkReverseIndex();
 	BOOST_REQUIRE_EQUAL(2, unused.size());
 	BOOST_CHECK_EQUAL(1, unused[0]);
 	BOOST_CHECK_EQUAL(2, unused[1]);
@@ -124,12 +149,33 @@ BOOST_AUTO_TEST_CASE(shuffle)
 	BOOST_CHECK_EQUAL(at(1), *proxies[1].get());
 	// Add new, takes 2 at [2]
 	BOOST_CHECK_EQUAL(4, proxies.emplace_back(acquire(4)));
-	BOOST_REQUIRE_EQUAL(4, index.size());
+	BOOST_CHECK_EQUAL_COLVALS(index, 0, npos, 2, 1);
+	checkReverseIndex();
 	BOOST_REQUIRE_EQUAL(1, unused.size());
 	BOOST_CHECK_EQUAL(1, unused[0]);
 	BOOST_CHECK_EQUAL(at(0), *proxies[0].get());
 	BOOST_CHECK_EQUAL(at(1), *proxies[1].get());
 	BOOST_CHECK_EQUAL(at(2), *proxies[2].get());
+	// Add new, takes 1 at [3]
+	BOOST_CHECK_EQUAL(5, proxies.emplace_back(acquire(5)));
+	BOOST_REQUIRE_EQUAL(proxies.size(), reverseIndex.size());
+	BOOST_CHECK_EQUAL_COLVALS(index, 0, 3, 2, 1);
+	checkReverseIndex();
+	// Add new, takes 4 at [4]
+	BOOST_CHECK_EQUAL(6, proxies.emplace_back(acquire(6)));
+	BOOST_REQUIRE_EQUAL(proxies.size(), reverseIndex.size());
+	BOOST_CHECK_EQUAL_COLVALS(index, 0, 3, 2, 1, 4);
+	checkReverseIndex();
+	// Remove [0]
+	proxies.erase(proxies.begin());
+	BOOST_REQUIRE_EQUAL(proxies.size(), reverseIndex.size());
+	BOOST_CHECK_EQUAL_COLVALS(index, npos, 3, 2, 1, 0);
+	checkReverseIndex();
+	// Remove [3]
+	proxies.erase(proxies.begin());
+	BOOST_REQUIRE_EQUAL(proxies.size(), reverseIndex.size());
+	BOOST_CHECK_EQUAL_COLVALS(index, npos, 1, 2, npos, 0);
+	checkReverseIndex();
 }
 
 BOOST_DATA_TEST_CASE(shuffle_random, boost::unit_test::data::xrange(0, 10), x)
@@ -163,6 +209,7 @@ BOOST_DATA_TEST_CASE(shuffle_random, boost::unit_test::data::xrange(0, 10), x)
 				iused.emplace(index[i]);
 			}
 		}
+		checkReverseIndex();
 
 		BOOST_TEST_CONTEXT(index) {
 			BOOST_REQUIRE_EQUAL(iused.size(), size());
@@ -202,6 +249,7 @@ BOOST_AUTO_TEST_CASE(partition_by, *boost::unit_test::timeout(1))
 	// The partition point is right...
 	BOOST_CHECK(!pred(*matchedEnd));
 	BOOST_CHECK(pred(*--matchedEnd));
+	checkReverseIndex();
 }
 
 BOOST_AUTO_TEST_SUITE_END()
diff --git a/test/testHelpers.h b/test/testHelpers.h
index c9fd6dc..a261b3d 100644
--- a/test/testHelpers.h
+++ b/test/testHelpers.h
@@ -51,3 +51,11 @@ loadFixtureJson(const std::filesystem::path & path)
 		BOOST_CHECK(VAR); \
 	} \
 	else
+
+#define BOOST_CHECK_EQUAL_COLCOL(cola_, colb_) \
+	BOOST_CHECK_EQUAL_COLLECTIONS(cola_.begin(), cola_.end(), colb_.begin(), colb_.end())
+#define BOOST_CHECK_EQUAL_COLVALS(col_, ...) \
+	{ \
+		const std::initializer_list<decltype(col_)::value_type> vals {__VA_ARGS__}; \
+		BOOST_CHECK_EQUAL_COLLECTIONS(col_.begin(), col_.end(), vals.begin(), vals.end()); \
+	}