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