Changed ContractionState data structure to be more efficient by not only

modifying data near an insertion or deletion when there is good locality of
modification.

1 files changed, 151 insertions, 195 deletions

diff --git a/src/ContractionState.cxx b/src/ContractionState.cxx
index b44b4e742..4e289a155 100644
--- a/src/ContractionState.cxx
+++ b/src/ContractionState.cxx
@@ -1,293 +1,249 @@
 // Scintilla source code edit control
 /** @file ContractionState.cxx
- ** Manages visibility of lines for folding.
+ ** Manages visibility of lines for folding and wrapping.
  **/
-// Copyright 1998-2001 by Neil Hodgson <neilh@scintilla.org>
+// Copyright 1998-2007 by Neil Hodgson <neilh@scintilla.org>
 // The License.txt file describes the conditions under which this software may be distributed.
 
+#include <string.h>
+
 #include "Platform.h"
 
+#include "SplitVector.h"
+#include "Partitioning.h"
+#include "RunStyles.h"
 #include "ContractionState.h"
 
 #ifdef SCI_NAMESPACE
 using namespace Scintilla;
 #endif
 
-OneLine::OneLine() {
-	displayLine = 0;
-	//docLine = 0;
-	visible = true;
-	height = 1;
-	expanded = true;
-}
-
-ContractionState::ContractionState() {
-	lines = 0;
-	size = 0;
-	linesInDoc = 1;
-	linesInDisplay = 1;
-	valid = false;
-	docLines = 0;
-	sizeDocLines = 0;
+ContractionState::ContractionState() : visible(0), expanded(0), heights(0), displayLines(0), linesInDocument(1) {
+	//InsertLine(0);
 }
 
 ContractionState::~ContractionState() {
 	Clear();
 }
 
-void ContractionState::MakeValid() const {
-	if (!valid) {
-		// Could be cleverer by keeping the index of the last still valid entry
-		// rather than invalidating all.
-		linesInDisplay = 0;
-		for (int lineInDoc=0; lineInDoc<linesInDoc; lineInDoc++) {
-			lines[lineInDoc].displayLine = linesInDisplay;
-			if (lines[lineInDoc].visible) {
-				linesInDisplay += lines[lineInDoc].height;
-			}
-		}
-		if (sizeDocLines < linesInDisplay) {
-			delete []docLines;
-			int *docLinesNew = new int[linesInDisplay + growSize];
-			if (!docLinesNew) {
-				docLines = 0;
-				sizeDocLines = 0;
-				return;
-			}
-			docLines = docLinesNew;
-			sizeDocLines = linesInDisplay + growSize;
-		}
-
-		int lineInDisplay=0;
-		for (int line=0; line<linesInDoc; line++) {
-			if (lines[line].visible) {
-				for (int linePiece=0; linePiece<lines[line].height; linePiece++) {
-					docLines[lineInDisplay] = line;
-					lineInDisplay++;
-				}
-			}
-		}
-		valid = true;
+void ContractionState::EnsureData() {
+	if (OneToOne()) {
+		visible = new RunStyles();
+		expanded = new RunStyles();
+		heights = new RunStyles();
+		displayLines = new Partitioning(4);
+		InsertLines(0, linesInDocument);
 	}
 }
 
 void ContractionState::Clear() {
-	delete []lines;
-	lines = 0;
-	size = 0;
-	linesInDoc = 1;
-	linesInDisplay = 1;
-	delete []docLines;
-	docLines = 0;
-	sizeDocLines = 0;
+	delete visible;
+	visible = 0;
+	delete expanded;
+	expanded = 0;
+	delete heights;
+	heights = 0;
+	delete displayLines;
+	displayLines = 0;
+	linesInDocument = 1;
 }
 
 int ContractionState::LinesInDoc() const {
-	return linesInDoc;
+	if (OneToOne()) {
+		return linesInDocument;
+	} else {
+		return displayLines->Partitions() - 1;
+	}
 }
 
 int ContractionState::LinesDisplayed() const {
-	if (size != 0) {
-		MakeValid();
+	if (OneToOne()) {
+		return linesInDocument;
+	} else {
+		return displayLines->PositionFromPartition(LinesInDoc());
 	}
-	return linesInDisplay;
 }
 
 int ContractionState::DisplayFromDoc(int lineDoc) const {
-	if (size == 0) {
+	if (OneToOne()) {
 		return lineDoc;
+	} else {
+		if (lineDoc > displayLines->Partitions())
+			lineDoc = displayLines->Partitions();
+		return displayLines->PositionFromPartition(lineDoc);
 	}
-	MakeValid();
-	if ((lineDoc >= 0) && (lineDoc < linesInDoc)) {
-		return lines[lineDoc].displayLine;
-	}
-	return -1;
 }
 
 int ContractionState::DocFromDisplay(int lineDisplay) const {
-	if (lineDisplay <= 0)
-		return 0;
-	if (lineDisplay >= linesInDisplay)
-		return linesInDoc;
-	if (size == 0)
+	if (OneToOne()) {
 		return lineDisplay;
-	MakeValid();
-	if (docLines) {	// Valid allocation
-		return docLines[lineDisplay];
 	} else {
-		return 0;
+		if (lineDisplay <= 0) {
+			return 0;
+		}
+		if (lineDisplay > LinesDisplayed()) {
+			return displayLines->PartitionFromPosition(LinesDisplayed());
+		}
+		int lineDoc = displayLines->PartitionFromPosition(lineDisplay);
+		PLATFORM_ASSERT(GetVisible(lineDoc));
+		return lineDoc;
 	}
 }
 
-void ContractionState::Grow(int sizeNew) {
-	OneLine *linesNew = new OneLine[sizeNew];
-	if (linesNew) {
-		int i = 0;
-		for (; i < size; i++) {
-			linesNew[i] = lines[i];
-		}
-		for (; i < sizeNew; i++) {
-			linesNew[i].displayLine = i;
-		}
-		delete []lines;
-		lines = linesNew;
-		size = sizeNew;
-		valid = false;
+void ContractionState::InsertLine(int lineDoc) {
+	if (OneToOne()) {
+		linesInDocument++;
 	} else {
-		Platform::DebugPrintf("No memory available\n");
-		// TODO: Blow up
+		visible->InsertSpace(lineDoc, 1);
+		visible->SetValueAt(lineDoc, 1);
+		expanded->InsertSpace(lineDoc, 1);
+		expanded->SetValueAt(lineDoc, 1);
+		heights->InsertSpace(lineDoc, 1);
+		heights->SetValueAt(lineDoc, 1);
+		int lineDisplay = DisplayFromDoc(lineDoc);
+		displayLines->InsertPartition(lineDoc, lineDisplay);
+		displayLines->InsertText(lineDoc, 1);
 	}
 }
 
 void ContractionState::InsertLines(int lineDoc, int lineCount) {
-	if (size == 0) {
-		linesInDoc += lineCount;
-		linesInDisplay += lineCount;
-		return;
+	for (int l = 0; l < lineCount; l++) {
+		InsertLine(lineDoc + l);
 	}
-	//Platform::DebugPrintf("InsertLine[%d] = %d\n", lineDoc);
-	if ((linesInDoc + lineCount + 2) >= size) {
-		Grow(linesInDoc + lineCount + growSize);
-	}
-	linesInDoc += lineCount;
-	for (int i = linesInDoc; i >= lineDoc + lineCount; i--) {
-		lines[i].visible = lines[i - lineCount].visible;
-		lines[i].height = lines[i - lineCount].height;
-		linesInDisplay += lines[i].height;
-		lines[i].expanded = lines[i - lineCount].expanded;
-	}
-	for (int d=0;d<lineCount;d++) {
-		lines[lineDoc+d].visible = true;	// Should inherit visibility from context ?
-		lines[lineDoc+d].height = 1;
-		lines[lineDoc+d].expanded = true;
+	Check();
+}
+
+void ContractionState::DeleteLine(int lineDoc) {
+	if (OneToOne()) {
+		linesInDocument--;
+	} else {
+		if (GetVisible(lineDoc)) {
+			displayLines->InsertText(lineDoc, -heights->ValueAt(lineDoc));
+		}
+		displayLines->RemovePartition(lineDoc);
+		visible->DeleteRange(lineDoc, 1);
+		expanded->DeleteRange(lineDoc, 1);
+		heights->DeleteRange(lineDoc, 1);
 	}
-	valid = false;
 }
 
 void ContractionState::DeleteLines(int lineDoc, int lineCount) {
-	if (size == 0) {
-		linesInDoc -= lineCount;
-		linesInDisplay -= lineCount;
-		return;
-	}
-	int deltaDisplayed = 0;
-	for (int d=0;d<lineCount;d++) {
-		if (lines[lineDoc+d].visible)
-			deltaDisplayed -= lines[lineDoc+d].height;
+	for (int l = 0; l < lineCount; l++) {
+		DeleteLine(lineDoc);
 	}
-	for (int i = lineDoc; i < linesInDoc-lineCount; i++) {
-		if (i != 0) // Line zero is always visible
-			lines[i].visible = lines[i + lineCount].visible;
-		lines[i].expanded = lines[i + lineCount].expanded;
-		lines[i].height = lines[i + lineCount].height;
-	}
-	linesInDoc -= lineCount;
-	linesInDisplay += deltaDisplayed;
-	valid = false;
+	Check();
 }
 
 bool ContractionState::GetVisible(int lineDoc) const {
-	if (size == 0)
+	if (OneToOne()) {
 		return true;
-	if ((lineDoc >= 0) && (lineDoc < linesInDoc)) {
-		return lines[lineDoc].visible;
 	} else {
-		return false;
+		if (lineDoc >= visible->Length())
+			return true;
+		return visible->ValueAt(lineDoc) == 1;
 	}
 }
 
-bool ContractionState::SetVisible(int lineDocStart, int lineDocEnd, bool visible) {
-	if (lineDocStart == 0)
-		lineDocStart++;
-	if (lineDocStart > lineDocEnd)
+bool ContractionState::SetVisible(int lineDocStart, int lineDocEnd, bool visible_) {
+	if (OneToOne() && visible_) {
 		return false;
-	if (size == 0) {
-		Grow(linesInDoc + growSize);
-	}
-	// TODO: modify docLine members to mirror displayLine
-	int delta = 0;
-	// Change lineDocs
-	if ((lineDocStart <= lineDocEnd) && (lineDocStart >= 0) && (lineDocEnd < linesInDoc)) {
-		for (int line=lineDocStart; line <= lineDocEnd; line++) {
-			if (lines[line].visible != visible) {
-				delta += visible ? lines[line].height : -lines[line].height;
-				lines[line].visible = visible;
-				valid = false;
+	} else {
+		EnsureData();
+		int delta = 0;
+		Check();
+		if ((lineDocStart <= lineDocEnd) && (lineDocStart >= 0) && (lineDocEnd < LinesInDoc())) {
+			for (int line = lineDocStart; line <= lineDocEnd; line++) {
+				if (GetVisible(line) != visible_) {
+					int difference = visible_ ? heights->ValueAt(line) : -heights->ValueAt(line);
+					visible->SetValueAt(line, visible_ ? 1 : 0);
+					displayLines->InsertText(line, difference);
+					delta += difference;
+				}
 			}
+		} else {
+			return false;
 		}
+		Check();
+		return delta != 0;
 	}
-	linesInDisplay += delta;
-	return delta != 0;
 }
 
 bool ContractionState::GetExpanded(int lineDoc) const {
-	if (size == 0)
+	if (OneToOne()) {
 		return true;
-	if ((lineDoc >= 0) && (lineDoc < linesInDoc)) {
-		return lines[lineDoc].expanded;
 	} else {
-		return false;
+		Check();
+		return expanded->ValueAt(lineDoc) == 1;
 	}
 }
 
-bool ContractionState::SetExpanded(int lineDoc, bool expanded) {
-	if (size == 0) {
-		if (expanded) {
-			// If in completely expanded state then setting
-			// one line to expanded has no effect.
-			return false;
-		}
-		Grow(linesInDoc + growSize);
-	}
-	if ((lineDoc >= 0) && (lineDoc < linesInDoc)) {
-		if (lines[lineDoc].expanded != expanded) {
-			lines[lineDoc].expanded = expanded;
+bool ContractionState::SetExpanded(int lineDoc, bool expanded_) {
+	if (OneToOne() && expanded_) {
+		return false;
+	} else {
+		EnsureData();
+		if (expanded_ != (expanded->ValueAt(lineDoc) == 1)) {
+			expanded->SetValueAt(lineDoc, expanded_ ? 1 : 0);
+			Check();
 			return true;
+		} else {
+			Check();
+			return false;
 		}
 	}
-	return false;
 }
 
 int ContractionState::GetHeight(int lineDoc) const {
-	if (size == 0)
+	if (OneToOne()) {
 		return 1;
-	if ((lineDoc >= 0) && (lineDoc < linesInDoc)) {
-		return lines[lineDoc].height;
 	} else {
-		return 1;
+		return heights->ValueAt(lineDoc);
 	}
 }
 
 // Set the number of display lines needed for this line.
 // Return true if this is a change.
 bool ContractionState::SetHeight(int lineDoc, int height) {
-	if (lineDoc > linesInDoc)
+	if (OneToOne() && (height == 1)) {
 		return false;
-	if (size == 0) {
-		if (height == 1) {
-			// If in completely expanded state then all lines
-			// assumed to have height of one so no effect here.
+	} else {
+		EnsureData();
+		if (GetHeight(lineDoc) != height) {
+			if (GetVisible(lineDoc)) {
+				displayLines->InsertText(lineDoc, height - GetHeight(lineDoc));
+			}
+			heights->SetValueAt(lineDoc, height);
+			Check();
+			return true;
+		} else {
+			Check();
 			return false;
 		}
-		Grow(linesInDoc + growSize);
-	}
-	if (lines[lineDoc].height != height) {
-		lines[lineDoc].height = height;
-		valid = false;
-		return true;
-	} else {
-		return false;
 	}
 }
 
 void ContractionState::ShowAll() {
-	delete []lines;
-	lines = 0;
-	size = 0;
+	Clear();
+}
 
-	delete []docLines;
-	docLines = 0;
-	sizeDocLines = 0;
+// Debugging checks
 
-	linesInDisplay = linesInDoc;
+void ContractionState::Check() const {
+#ifdef CHECK_CORRECTNESS
+	for (int vline = 0;vline < LinesDisplayed(); vline++) {
+		const int lineDoc = DocFromDisplay(vline);
+		PLATFORM_ASSERT(GetVisible(lineDoc));
+	}
+	for (int lineDoc = 0;lineDoc < LinesInDoc(); lineDoc++) {
+		const int displayThis = DisplayFromDoc(lineDoc);
+		const int displayNext = DisplayFromDoc(lineDoc + 1);
+		const int height = displayNext - displayThis;
+		PLATFORM_ASSERT(height >= 0);
+		if (GetVisible(lineDoc)) {
+			PLATFORM_ASSERT(GetHeight(lineDoc) == height);
+		} else {
+			PLATFORM_ASSERT(0 == height);
+		}
+	}
+#endif
 }