292 lines
7.2 KiB
C++
292 lines
7.2 KiB
C++
// 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
|
|
|
|
#ifdef SCI_NAMESPACE
|
|
namespace Scintilla {
|
|
#endif
|
|
|
|
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) {
|
|
while (growSize < size / 6)
|
|
growSize *= 2;
|
|
ReAllocate(size + insertionLength + growSize);
|
|
}
|
|
}
|
|
|
|
void Init() {
|
|
body = NULL;
|
|
growSize = 8;
|
|
size = 0;
|
|
lengthBody = 0;
|
|
part1Length = 0;
|
|
gapLength = 0;
|
|
}
|
|
|
|
public:
|
|
/// Construct a split buffer.
|
|
SplitVector() {
|
|
Init();
|
|
}
|
|
|
|
~SplitVector() {
|
|
delete []body;
|
|
body = 0;
|
|
}
|
|
|
|
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 != 0)) {
|
|
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.
|
|
/// The assertions here are disabled since calling code can be
|
|
/// simpler if out of range access works and 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) {
|
|
PLATFORM_ASSERT((position >= 0) && (position <= lengthBody));
|
|
if (insertLength > 0) {
|
|
if ((position < 0) || (position > lengthBody)) {
|
|
return;
|
|
}
|
|
RoomFor(insertLength);
|
|
GapTo(position);
|
|
std::fill(&body[part1Length], &body[part1Length + insertLength], v);
|
|
lengthBody += insertLength;
|
|
part1Length += insertLength;
|
|
gapLength -= insertLength;
|
|
}
|
|
}
|
|
|
|
/// Ensure at least length elements allocated,
|
|
/// appending zero valued elements if needed.
|
|
void EnsureLength(int wantedLength) {
|
|
if (Length() < wantedLength) {
|
|
InsertValue(Length(), wantedLength - Length(), 0);
|
|
}
|
|
}
|
|
|
|
/// Insert text into the buffer from an array.
|
|
void InsertFromArray(int positionToInsert, const T s[], int positionFrom, int insertLength) {
|
|
PLATFORM_ASSERT((positionToInsert >= 0) && (positionToInsert <= lengthBody));
|
|
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) {
|
|
PLATFORM_ASSERT((position >= 0) && (position < lengthBody));
|
|
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 ((position == 0) && (deleteLength == lengthBody)) {
|
|
// Full deallocation returns storage and is faster
|
|
delete []body;
|
|
Init();
|
|
} else if (deleteLength > 0) {
|
|
GapTo(position);
|
|
lengthBody -= deleteLength;
|
|
gapLength += deleteLength;
|
|
}
|
|
}
|
|
|
|
/// Delete all the buffer contents.
|
|
void DeleteAll() {
|
|
DeleteRange(0, lengthBody);
|
|
}
|
|
|
|
// Retrieve a range of elements into an array
|
|
void GetRange(T *buffer, int position, int retrieveLength) const {
|
|
// Split into up to 2 ranges, before and after the split then use memcpy on each.
|
|
int range1Length = 0;
|
|
if (position < part1Length) {
|
|
int part1AfterPosition = part1Length - position;
|
|
range1Length = retrieveLength;
|
|
if (range1Length > part1AfterPosition)
|
|
range1Length = part1AfterPosition;
|
|
}
|
|
memcpy(buffer, body + position, range1Length * sizeof(T));
|
|
buffer += range1Length;
|
|
position = position + range1Length + gapLength;
|
|
int range2Length = retrieveLength - range1Length;
|
|
memcpy(buffer, body + position, range2Length * sizeof(T));
|
|
}
|
|
|
|
T *BufferPointer() {
|
|
RoomFor(1);
|
|
GapTo(lengthBody);
|
|
body[lengthBody] = 0;
|
|
return body;
|
|
}
|
|
|
|
T *RangePointer(int position, int rangeLength) {
|
|
if (position < part1Length) {
|
|
if ((position + rangeLength) > part1Length) {
|
|
// Range overlaps gap, so move gap to start of range.
|
|
GapTo(position);
|
|
return body + position + gapLength;
|
|
} else {
|
|
return body + position ;
|
|
}
|
|
} else {
|
|
return body + position + gapLength;
|
|
}
|
|
}
|
|
|
|
int GapPosition() const {
|
|
return part1Length;
|
|
}
|
|
};
|
|
|
|
#ifdef SCI_NAMESPACE
|
|
}
|
|
#endif
|
|
|
|
#endif
|