From e9f310d4043e58739c9e661159a35847a7ba5df5 Mon Sep 17 00:00:00 2001
From: Neil <nyamatongwe@gmail.com>
Date: Mon, 2 Dec 2019 08:34:47 +1100
Subject: Backport: Add SparseVector::IndexAfter for efficiently finding
 elements in a range.

Backport of changeset 7779:67b7e8f152a9.
---
 src/SparseVector.h             |  7 +++++++
 test/unit/testSparseVector.cxx | 17 +++++++++++++++++
 2 files changed, 24 insertions(+)

diff --git a/src/SparseVector.h b/src/SparseVector.h
index 6dd02ba8b..86d631c3f 100644
--- a/src/SparseVector.h
+++ b/src/SparseVector.h
@@ -154,6 +154,13 @@ public:
 		starts->InsertText(partition, -1);
 		Check();
 	}
+	Sci::Position IndexAfter(Sci::Position position) const noexcept {
+		assert(position < Length());
+		if (position < 0)
+			return 0;
+		const Sci::Position partition = starts->PartitionFromPosition(position);
+		return partition + 1;
+	}
 	void Check() const {
 #ifdef CHECK_CORRECTNESS
 		starts->Check();
diff --git a/test/unit/testSparseVector.cxx b/test/unit/testSparseVector.cxx
index 4d3b872e1..c9fc58bf1 100644
--- a/test/unit/testSparseVector.cxx
+++ b/test/unit/testSparseVector.cxx
@@ -248,6 +248,23 @@ TEST_CASE("SparseTextInt") {
 		REQUIRE(0 == st.ValueAt(4));
 		st.Check();
 	}
+
+	SECTION("IndexAfter") {
+		st.InsertSpace(0, 5);
+		REQUIRE(1 == st.Elements());
+		REQUIRE(0 == st.IndexAfter(-1));
+		REQUIRE(0 == st.PositionOfElement(0));
+		REQUIRE(1 == st.IndexAfter(0));
+		REQUIRE(5 == st.PositionOfElement(1));
+		st.SetValueAt(3, 3);
+		REQUIRE(2 == st.Elements());
+		REQUIRE(0 == st.IndexAfter(-1));
+		REQUIRE(0 == st.PositionOfElement(0));
+		REQUIRE(1 == st.IndexAfter(0));
+		REQUIRE(3 == st.PositionOfElement(1));
+		REQUIRE(2 == st.IndexAfter(3));
+		REQUIRE(5 == st.PositionOfElement(2));
+	}
 }
 
 TEST_CASE("SparseTextString") {
-- 
cgit v1.2.3