1 files changed, 221 insertions, 0 deletions
diff --git a/src/SplitVector.h b/src/SplitVector.h
new file mode 100644
index 000000000..2847108fa
--- /dev/null
+++ b/src/SplitVector.h
@@ -0,0 +1,221 @@
+// Scintilla source code edit control
+/** @file SplitVector.h
+ ** Main data structure for holding arrays that handle insertions 
+ ** and deletions efficiently.
+ **/
+// Copyright 1998-2007 by Neil Hodgson <neilh@scintilla.org>
+// The License.txt file describes the conditions under which this software may be distributed.
+
+#ifndef SPLITVECTOR_H
+#define SPLITVECTOR_H
+
+template <typename T>
+class SplitVector {
+protected:
+	T *body;
+	int size;
+	int lengthBody;
+	int part1Length;
+	int gapLength;	/// invariant: gapLength == size - lengthBody
+	int growSize;
+
+	/// Move the gap to a particular position so that insertion and
+	/// deletion at that point will not require much copying and
+	/// hence be fast.
+	void GapTo(int position) {
+		if (position != part1Length) {
+			if (position < part1Length) {
+				memmove(
+					body + position + gapLength,
+					body + position,
+					sizeof(T) * (part1Length - position));
+			} else {	// position > part1Length
+				memmove(
+					body + part1Length,
+					body + part1Length + gapLength,
+					sizeof(T) * (position - part1Length));
+			}
+			part1Length = position;
+		}
+	}
+
+	/// Check that there is room in the buffer for an insertion,
+	/// reallocating if more space needed.
+	void RoomFor(int insertionLength) {
+		if (gapLength <= insertionLength) {
+			if (growSize * 6 < size)
+				growSize *= 2;
+			ReAllocate(size + insertionLength + growSize);
+		}
+	}
+
+public:
+	/// Construct a split buffer.
+	SplitVector() {
+		body = NULL;
+		growSize = 8;
+		size = 0;
+		lengthBody = 0;
+		part1Length = 0;
+		gapLength = 0;
+	}
+
+	~SplitVector() {
+		delete []body;
+		body = NULL;
+	}
+
+	void Create(int initialLength_, int growSize_);
+
+	int GetGrowSize() const {
+		return growSize;
+	}
+
+	void SetGrowSize(int growSize_) {
+		growSize = growSize_;
+	}
+
+	/// Reallocate the storage for the buffer to be newSize and
+	/// copy exisiting contents to the new buffer.
+	/// Must not be used to decrease the size of the buffer.
+	void ReAllocate(int newSize) {
+		if (newSize > size) {
+			// Move the gap to the end
+			GapTo(lengthBody);
+			T *newBody = new T[newSize];
+			if ((size != 0) && (body != NULL)) {
+				memmove(newBody, body, sizeof(T) * lengthBody);
+				delete []body;
+			}
+			body = newBody;
+			gapLength += newSize - size;
+			size = newSize;
+		}
+	}
+
+	/// Retrieve the character at a particular position.
+	/// Retrieving positions outside the range of the buffer returns 0.
+	T ValueAt(int position) const {
+		if (position < part1Length) {
+			//PLATFORM_ASSERT(position >= 0);
+			if (position < 0) {
+				return 0;
+			} else {
+				return body[position];
+			}
+		} else {
+			//PLATFORM_ASSERT(position < lengthBody);
+			if (position >= lengthBody) {
+				return 0;
+			} else {
+				return body[gapLength + position];
+			}
+		}
+	}
+
+	void SetValueAt(int position, T v) {
+		if (position < part1Length) {
+			PLATFORM_ASSERT(position >= 0);
+			if (position < 0) {
+				;
+			} else {
+				body[position] = v;
+			}
+		} else {
+			PLATFORM_ASSERT(position < lengthBody);
+			if (position >= lengthBody) {
+				;
+			} else {
+				body[gapLength + position] = v;
+			}
+		}
+	}
+
+	T& operator[](int position) const {
+		PLATFORM_ASSERT(position >= 0 && position < lengthBody);
+		if (position < part1Length) {
+			return body[position];
+		} else {
+			return body[gapLength + position];
+		}
+	}
+
+	/// Retrieve the length of the buffer.
+	int Length() const {
+		return lengthBody;
+	}
+
+	/// Insert a single value into the buffer.
+	/// Inserting at positions outside the current range fails.
+	void Insert(int position, T v) {
+		PLATFORM_ASSERT((position >= 0) && (position <= lengthBody));
+		if ((position < 0) || (position > lengthBody)) {
+			return;
+		}
+		RoomFor(1);
+		GapTo(position);
+		body[part1Length] = v;
+		lengthBody++;
+		part1Length++;
+		gapLength--;
+	}
+
+	/// Insert a number of elements into the buffer setting their value.
+	/// Inserting at positions outside the current range fails.
+	void InsertValue(int position, int insertLength, T v) {
+		if (insertLength > 0) {
+			RoomFor(insertLength);
+			GapTo(position);
+			for (int i = 0; i < insertLength; i++)
+				body[part1Length + i] = v;
+			lengthBody += insertLength;
+			part1Length += insertLength;
+			gapLength -= insertLength;
+		}
+	}
+	
+	/// Insert text into the buffer from an array.
+	void InsertFromArray(int positionToInsert, T s[], int positionFrom, int insertLength) {
+		if (insertLength > 0) {
+			if ((positionToInsert < 0) || (positionToInsert > lengthBody)) {
+				return;
+			}
+			RoomFor(insertLength);
+			GapTo(positionToInsert);
+			memmove(body + part1Length, s + positionFrom, sizeof(T) * insertLength);
+			lengthBody += insertLength;
+			part1Length += insertLength;
+			gapLength -= insertLength;
+		}
+	}
+
+	/// Delete one element from the buffer.
+	void Delete(int position) {
+		if ((position < 0) || (position >= lengthBody)) {
+			return;
+		}
+		DeleteRange(position, 1);
+	}
+
+	/// Delete a range from the buffer.
+	/// Deleting positions outside the current range fails.
+	void DeleteRange(int position, int deleteLength) {
+		PLATFORM_ASSERT((position >= 0) && (position + deleteLength <= lengthBody));
+		if ((position < 0) || ((position + deleteLength) > lengthBody)) {
+			return;
+		}
+		if (deleteLength > 0) {
+			GapTo(position);
+			lengthBody -= deleteLength;
+			gapLength += deleteLength;
+		}
+	}
+
+	/// Delete all the buffer contents.
+	void DeleteAll() {
+		DeleteRange(0, lengthBody);
+	}
+
+};
+
+#endif