Add SparseVector::DeleteRange for efficiently removing ranges.

2 files changed, 143 insertions, 0 deletions

diff --git a/src/SparseVector.h b/src/SparseVector.h
index 3fa1ac95b..b0cfe2ded 100644
--- a/src/SparseVector.h
+++ b/src/SparseVector.h
@@ -154,6 +154,43 @@ public:
 		starts->InsertText(partition, -1);
 		Check();
 	}
+	void DeleteRange(Sci::Position position, Sci::Position deleteLength) {
+		// For now, delete elements in range - may want to leave value at start
+		// or combine onto position.
+		if (position > Length() || (deleteLength == 0)) {
+			return;
+		}
+		const Sci::Position positionEnd = position + deleteLength;
+		assert(positionEnd <= Length());
+		if (position == 0) {
+			// Remove all partitions in range, moving values to start
+			while ((Elements() > 1) && (starts->PositionFromPartition(1) <= deleteLength)) {
+				starts->RemovePartition(1);
+				values->Delete(0);
+			}
+			starts->InsertText(0, -deleteLength);
+			if (Length() == 0) {
+				ClearValue(0);
+			}
+		} else {
+			const Sci::Position partition = starts->PartitionFromPosition(position);
+			const bool atPartitionStart = position == starts->PositionFromPartition(partition);
+			const Sci::Position partitionDelete = partition + (atPartitionStart ? 0 : 1);
+			assert(partitionDelete > 0);
+			for (;;) {
+				const Sci::Position positionAtIndex = starts->PositionFromPartition(partitionDelete);
+				assert(position <= positionAtIndex);
+				if (positionAtIndex >= positionEnd) {
+					break;
+				}
+				assert(partitionDelete <= Elements());
+				starts->RemovePartition(partitionDelete);
+				values->Delete(partitionDelete);
+			}
+			starts->InsertText(partition - (atPartitionStart ? 1 : 0), -deleteLength);
+		}
+		Check();
+	}
 	Sci::Position IndexAfter(Sci::Position position) const noexcept {
 		assert(position < Length());
 		if (position < 0)
diff --git a/test/unit/testSparseVector.cxx b/test/unit/testSparseVector.cxx
index ae2e239cf..1a2868c88 100644
--- a/test/unit/testSparseVector.cxx
+++ b/test/unit/testSparseVector.cxx
@@ -218,6 +218,112 @@ TEST_CASE("SparseVector") {
 		REQUIRE("-" == Representation(st));
 	}
 
+	SECTION("DeleteRange") {
+		REQUIRE(1 == st.Elements());
+		st.InsertSpace(0, 10);
+		st.SetValueAt(9, UniqueStringCopy("9"));
+		st.SetValueAt(7, UniqueStringCopy("7"));
+		st.SetValueAt(4, UniqueStringCopy("4"));
+		st.SetValueAt(3, UniqueStringCopy("3"));
+		REQUIRE(5 == st.Elements());
+		REQUIRE(10 == st.Length());
+		REQUIRE("---34--7-9-" == Representation(st));
+		// Delete in space
+		st.DeleteRange(1, 1);
+		REQUIRE(5 == st.Elements());
+		REQUIRE(9 == st.Length());
+		REQUIRE("--34--7-9-" == Representation(st));
+		// Delete 2 values
+		st.DeleteRange(3, 4);
+		REQUIRE(3 == st.Elements());
+		REQUIRE(5 == st.Length());
+		REQUIRE("--3-9-" == Representation(st));
+		// Deletion at start
+		st.DeleteRange(0, 1);
+		REQUIRE(3 == st.Elements());
+		REQUIRE(4 == st.Length());
+		REQUIRE("-3-9-" == Representation(st));
+	}
+
+	SECTION("DeleteRangeAtEnds") {
+		// There are always elements at start and end although they can be nulled
+		REQUIRE(1 == st.Elements());
+		st.InsertSpace(0, 4);
+		REQUIRE(4 == st.Length());
+		st.SetValueAt(1, UniqueStringCopy("3"));
+		st.SetValueAt(4, UniqueStringCopy("9"));
+		REQUIRE("-3--9" == Representation(st));
+		REQUIRE(2 == st.Elements());
+		// Empty deletion at end -> no effect
+		st.DeleteRange(4, 0);
+		REQUIRE(2 == st.Elements());
+		REQUIRE(4 == st.Length());
+		REQUIRE("-3--9" == Representation(st));
+		// Delete value at start
+		st.InsertSpace(0, 1);
+		st.SetValueAt(0, UniqueStringCopy("0"));
+		REQUIRE(2 == st.Elements());
+		REQUIRE(5 == st.Length());
+		REQUIRE("0-3--9" == Representation(st));
+		st.DeleteRange(0, 1);
+		REQUIRE(2 == st.Elements());
+		REQUIRE(4 == st.Length());
+		REQUIRE("03--9" == Representation(st));
+		// Empty deletion at start -> no effect
+		st.InsertSpace(0, 1);
+		st.SetValueAt(0, UniqueStringCopy("1"));
+		REQUIRE(3 == st.Elements());
+		REQUIRE(5 == st.Length());
+		REQUIRE("103--9" == Representation(st));
+		st.DeleteRange(0, 0);
+		REQUIRE(3 == st.Elements());
+		REQUIRE(5 == st.Length());
+		REQUIRE("103--9" == Representation(st));
+	}
+
+	SECTION("DeleteStartingRange") {
+		REQUIRE(1 == st.Elements());
+		st.InsertSpace(0, 2);
+		st.SetValueAt(0, UniqueStringCopy("1"));
+		st.SetValueAt(1, UniqueStringCopy("2"));
+		REQUIRE(2 == st.Length());
+		REQUIRE("12-" == Representation(st));
+		st.DeleteRange(0,1);
+		REQUIRE(1 == st.Length());
+		REQUIRE("2-" == Representation(st));
+		st.DeleteRange(0,1);
+		REQUIRE(0 == st.Length());
+		REQUIRE("-" == Representation(st));
+		st.InsertSpace(0, 2);
+		st.SetValueAt(1, UniqueStringCopy("1"));
+		REQUIRE(2 == st.Length());
+		REQUIRE("-1-" == Representation(st));
+		st.DeleteRange(0, 2);
+		REQUIRE("-" == Representation(st));
+		st.InsertSpace(0, 4);
+		st.SetValueAt(1, UniqueStringCopy("1"));
+		st.SetValueAt(3, UniqueStringCopy("3"));
+		REQUIRE(4 == st.Length());
+		REQUIRE("-1-3-" == Representation(st));
+		st.DeleteRange(0, 3);
+		REQUIRE("3-" == Representation(st));
+		st.DeleteRange(0, 1);
+		REQUIRE("-" == Representation(st));
+		st.InsertSpace(0, 4);
+		st.SetValueAt(1, UniqueStringCopy("1"));
+		st.SetValueAt(4, UniqueStringCopy("4"));
+		st.SetValueAt(3, UniqueStringCopy("3"));
+		REQUIRE("-1-34" == Representation(st));
+		st.DeleteRange(1, 3);
+		REQUIRE("-4" == Representation(st));
+		st.InsertSpace(1, 3);
+		REQUIRE("----4" == Representation(st));
+		st.SetValueAt(4, UniqueStringCopy("4"));
+		st.SetValueAt(3, UniqueStringCopy("3"));
+		REQUIRE("---34" == Representation(st));
+		st.DeleteRange(1, 3);
+		REQUIRE("-4" == Representation(st));
+	}
 }
 
 TEST_CASE("SparseTextInt") {