aboutsummaryrefslogtreecommitdiffhomepage
path: root/src/ContractionState.cxx
diff options
context:
space:
mode:
authornyamatongwe <unknown>2007-07-25 09:58:17 +0000
committernyamatongwe <unknown>2007-07-25 09:58:17 +0000
commitcc88e2af38e51d286b712a3ebef4dd46222be1dd (patch)
tree33ce9d88f5bddd18fa01537a9ec0c45f12701357 /src/ContractionState.cxx
parent8b609f7f8901b3ae3b8171a21858f35ae9703d15 (diff)
downloadscintilla-mirror-cc88e2af38e51d286b712a3ebef4dd46222be1dd.tar.gz
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.
Diffstat (limited to 'src/ContractionState.cxx')
-rw-r--r--src/ContractionState.cxx346
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
}