Backport: Fix a bug with deleting the first element in SparseVector that left an extra

empty partition.
Add extra checking to Partitioning and turn on checking for UnitTester.

Backport of changeset 7777:12fb0335514e.

4 files changed, 64 insertions, 10 deletions

diff --git a/src/Partitioning.h b/src/Partitioning.h
index a92e55b53..e742952ab 100644
--- a/src/Partitioning.h
+++ b/src/Partitioning.h
@@ -110,6 +110,10 @@ public:
 		return static_cast<T>(body->Length())-1;
 	}
 
+	T Length() const noexcept {
+		return PositionFromPartition(Partitions());
+	}
+
 	void InsertPartition(T partition, T pos) {
 		if (stepPartition < partition) {
 			ApplyStep(partition);
@@ -196,6 +200,34 @@ public:
 	void DeleteAll() {
 		Allocate(body->GetGrowSize());
 	}
+
+	void Check() const {
+#ifdef CHECK_CORRECTNESS
+		if (Length() < 0) {
+			throw std::runtime_error("Partitioning: Length can not be negative.");
+		}
+		if (Partitions() < 1) {
+			throw std::runtime_error("Partitioning: Must always have 1 or more partitions.");
+		}
+		if (Length() == 0) {
+			if ((PositionFromPartition(0) != 0) || (PositionFromPartition(1) != 0)) {
+				throw std::runtime_error("Partitioning: Invalid empty partitioning.");
+			}
+		} else {
+			// Positions should be a strictly ascending sequence
+			for (T i = 0; i < Partitions(); i++) {
+				const T pos = PositionFromPartition(i);
+				const T posNext = PositionFromPartition(i+1);
+				if (pos > posNext) {
+					throw std::runtime_error("Partitioning: Negative partition.");
+				} else if (pos == posNext) {
+					throw std::runtime_error("Partitioning: Empty partition.");
+				}
+			}
+		}
+#endif
+	}
+
 };
 
 
diff --git a/src/SparseVector.h b/src/SparseVector.h
index 3b1b7d299..67ad1e1e3 100644
--- a/src/SparseVector.h
+++ b/src/SparseVector.h
@@ -120,6 +120,14 @@ public:
 		if (startPartition == position) {
 			if (partition == 0) {
 				ClearValue(0);
+				if (starts->PositionFromPartition(1) == 1) {
+					// Removing all space of first partition, so remove next partition
+					// and move value if not last
+					if (Elements() > 1) {
+						starts->RemovePartition(partition + 1);
+						values->Delete(partition);
+					}
+				}
 			} else if (partition == starts->Partitions()) {
 				// This should not be possible
 				ClearValue(partition);
@@ -133,14 +141,11 @@ public:
 			}
 		}
 		starts->InsertText(partition, -1);
+		Check();
 	}
 	void Check() const {
-		if (Length() < 0) {
-			throw std::runtime_error("SparseVector: Length can not be negative.");
-		}
-		if (starts->Partitions() < 1) {
-			throw std::runtime_error("SparseVector: Must always have 1 or more partitions.");
-		}
+#ifdef CHECK_CORRECTNESS
+		starts->Check();
 		if (starts->Partitions() != values->Length() - 1) {
 			throw std::runtime_error("SparseVector: Partitions and values different lengths.");
 		}
@@ -148,6 +153,7 @@ public:
 		if (values->ValueAt(values->Length() - 1) != T()) {
 			throw std::runtime_error("SparseVector: Unused style at end changed.");
 		}
+#endif
 	}
 };
 
diff --git a/test/unit/UnitTester.vcxproj b/test/unit/UnitTester.vcxproj
index 0f62f90a5..c80270618 100644
--- a/test/unit/UnitTester.vcxproj
+++ b/test/unit/UnitTester.vcxproj
@@ -87,7 +87,7 @@
       </PrecompiledHeader>

       <WarningLevel>Level3</WarningLevel>

       <Optimization>Disabled</Optimization>

-      <PreprocessorDefinitions>_CRT_SECURE_NO_WARNINGS=1;_SCL_SECURE_NO_WARNINGS=1;WIN32;_DEBUG;_CONSOLE;%(PreprocessorDefinitions)</PreprocessorDefinitions>

+      <PreprocessorDefinitions>_CRT_SECURE_NO_WARNINGS=1;_HAS_AUTO_PTR_ETC=1;_SCL_SECURE_NO_WARNINGS=1;CHECK_CORRECTNESS;WIN32;_DEBUG;_CONSOLE;%(PreprocessorDefinitions)</PreprocessorDefinitions>

       <AdditionalIncludeDirectories>..\..\include\;..\..\src\;..\..\lexlib\</AdditionalIncludeDirectories>

     </ClCompile>

     <Link>

@@ -101,7 +101,7 @@
       </PrecompiledHeader>

       <WarningLevel>Level3</WarningLevel>

       <Optimization>Disabled</Optimization>

-      <PreprocessorDefinitions>_CRT_SECURE_NO_WARNINGS=1;_SCL_SECURE_NO_WARNINGS=1;_DEBUG;_CONSOLE;%(PreprocessorDefinitions)</PreprocessorDefinitions>

+      <PreprocessorDefinitions>_CRT_SECURE_NO_WARNINGS=1;_HAS_AUTO_PTR_ETC=1;_SCL_SECURE_NO_WARNINGS=1;CHECK_CORRECTNESS;_DEBUG;_CONSOLE;%(PreprocessorDefinitions)</PreprocessorDefinitions>

       <AdditionalIncludeDirectories>..\..\include\;..\..\src\;..\..\lexlib\</AdditionalIncludeDirectories>

     </ClCompile>

     <Link>

@@ -117,7 +117,7 @@
       <Optimization>MaxSpeed</Optimization>

       <FunctionLevelLinking>true</FunctionLevelLinking>

       <IntrinsicFunctions>true</IntrinsicFunctions>

-      <PreprocessorDefinitions>_CRT_SECURE_NO_WARNINGS=1;_SCL_SECURE_NO_WARNINGS=1;WIN32;NDEBUG;_CONSOLE;%(PreprocessorDefinitions)</PreprocessorDefinitions>

+      <PreprocessorDefinitions>_CRT_SECURE_NO_WARNINGS=1;_HAS_AUTO_PTR_ETC=1;_SCL_SECURE_NO_WARNINGS=1;CHECK_CORRECTNESS;WIN32;NDEBUG;_CONSOLE;%(PreprocessorDefinitions)</PreprocessorDefinitions>

       <AdditionalIncludeDirectories>..\..\include\;..\..\src\;..\..\lexlib\</AdditionalIncludeDirectories>

     </ClCompile>

     <Link>

@@ -135,7 +135,7 @@
       <Optimization>MaxSpeed</Optimization>

       <FunctionLevelLinking>true</FunctionLevelLinking>

       <IntrinsicFunctions>true</IntrinsicFunctions>

-      <PreprocessorDefinitions>_CRT_SECURE_NO_WARNINGS=1;_SCL_SECURE_NO_WARNINGS=1;NDEBUG;_CONSOLE;%(PreprocessorDefinitions)</PreprocessorDefinitions>

+      <PreprocessorDefinitions>_CRT_SECURE_NO_WARNINGS=1;_HAS_AUTO_PTR_ETC=1;_SCL_SECURE_NO_WARNINGS=1;CHECK_CORRECTNESS;NDEBUG;_CONSOLE;%(PreprocessorDefinitions)</PreprocessorDefinitions>

       <AdditionalIncludeDirectories>..\..\include\;..\..\src\;..\..\lexlib\</AdditionalIncludeDirectories>

     </ClCompile>

     <Link>

diff --git a/test/unit/testSparseVector.cxx b/test/unit/testSparseVector.cxx
index ce3b9706b..df7b412ce 100644
--- a/test/unit/testSparseVector.cxx
+++ b/test/unit/testSparseVector.cxx
@@ -164,6 +164,22 @@ TEST_CASE("SparseVector") {
 		st.Check();
 	}
 
+	SECTION("CheckDeletionLeavesOrdered") {
+		REQUIRE(1 == st.Elements());
+		st.InsertSpace(0, 1);
+		st.SetValueAt(0, UniqueStringCopy("1"));
+		REQUIRE("1" == Representation(st));
+		REQUIRE(1 == st.Elements());
+		st.InsertSpace(1, 1);
+		st.SetValueAt(1, UniqueStringCopy("2"));
+		REQUIRE("12" == Representation(st));
+		st.DeletePosition(0);
+		REQUIRE("2" == Representation(st));
+		REQUIRE(1 == st.Elements());
+		st.DeletePosition(0);
+		REQUIRE("" == Representation(st));
+	}
+
 	SECTION("DeleteAll") {
 		REQUIRE(1 == st.Elements());
 		st.InsertSpace(0, 10);