using System;
using System.Collections.Generic;
using System.Collections;
using System.Threading;
using System.Globalization;
using System.Diagnostics;
namespace TextEditorTest
{
///
/// Represents a strongly typed collection of objects that can be accessed by index. Insertions and
/// deletions to the collection near the same relative index are optimized.
///
/// From: https://www.codeproject.com/Articles/20910/Generic-Gap-Buffer
/// The type of elements in the buffer.
[Serializable]
[DebuggerDisplay("Count = {Count}")]
[DebuggerTypeProxy(typeof(CollectionDebugView<>))]
public partial class GapBuffer : IList, IList
{
#region Fields
private const int MIN_CAPACITY = 4;
private T[] _buffer;
private int _gapStart;
private int _gapEnd;
private int _version;
[NonSerialized]
private object _syncRoot;
#endregion Fields
#region Constructors
///
/// Initializes a new instance of the class.
///
public GapBuffer()
{
this._buffer = new T[MIN_CAPACITY];
this._gapEnd = this._buffer.Length;
}
#endregion Constructors
#region Properties
///
/// Gets or sets the total number of elements the internal data structure can hold
/// without resizing.
///
/// The number of elements that the can contain before
/// resizing is required.
///
/// is set to a value that is less than .
///
public int Capacity
{
get
{
return this._buffer.Length;
}
set
{
// Is there any work to do?
if (value == this._buffer.Length)
return;
// Look for naughty boys and girls
if (value < Count)
throw new ArgumentOutOfRangeException("value", "Capacity was too small for this value!");
if (value > 0)
{
// Allocate a new buffer
T[] newBuffer = new T[value];
int newGapEnd = newBuffer.Length - (this._buffer.Length - this._gapEnd);
// Copy the spans into the front and back of the new buffer
Array.Copy(this._buffer, 0, newBuffer, 0, this._gapStart);
Array.Copy(this._buffer, this._gapEnd, newBuffer, newGapEnd, newBuffer.Length - newGapEnd);
this._buffer = newBuffer;
this._gapEnd = newGapEnd;
}
else
{
// Reset everything
this._buffer = new T[MIN_CAPACITY];
this._gapStart = 0;
this._gapEnd = this._buffer.Length;
}
}
}
///
/// Gets the number of elements actually contained in the .
///
///
/// The number of elements actually contained in the .
///
public int Count
{
get
{
return this._buffer.Length - (this._gapEnd - this._gapStart);
}
}
// Explicit IList implementation
bool IList.IsFixedSize
{
get { return false; }
}
// Explicit IList implementation
bool IList.IsReadOnly
{
get { return false; }
}
// Explicit ICollection implementation
bool ICollection.IsReadOnly
{
get { return false; }
}
// Explicit ICollection implementation
bool ICollection.IsSynchronized
{
get { return false; }
}
// Explicit ICollection implementation
object ICollection.SyncRoot
{
get
{
if (this._syncRoot == null)
Interlocked.CompareExchange(ref this._syncRoot, new object(), null);
return this._syncRoot;
}
}
///
/// Gets or sets the element at the specified index.
///
/// The zero-based index of the element to get or set.
/// The element at the specified index.
///
/// is less than 0.
/// -or-
/// is equal to or greater than .
///
public T this[int index]
{
get
{
if (index < 0 || index >= Count)
throw new ArgumentOutOfRangeException("index", "Index was out of range!");
// Find the correct span and get the item
if (index >= this._gapStart)
index += (this._gapEnd - this._gapStart);
return this._buffer[index];
}
set
{
if (index < 0 || index >= Count)
throw new ArgumentOutOfRangeException("index", "Index was out of range!");
// Find the correct span and set the item
if (index >= this._gapStart)
index += (this._gapEnd - this._gapStart);
this._buffer[index] = value;
this._version++;
}
}
// Explicit IList implementation
object IList.this[int index]
{
get { return this[index]; }
set
{
VerifyValueType(value);
this[index] = (T)value;
}
}
#endregion Properties
#region Methods
///
/// Adds an object to the end of the .
///
/// The object to be added to the end of the .
/// The value can be null for reference types.
public void Add(T item)
{
Insert(Count, item);
}
// Explicit IList implementation
int IList.Add(object value)
{
VerifyValueType(value);
Add((T)value);
return (Count - 1);
}
///
/// Adds the elements of the specified collection to the end of the .
///
/// The collection whose elements should be inserted into the .
/// The collection itself cannot be null, but it can contain elements that are null, if
/// type is a reference type.
/// is a null reference.
public void AddRange(IEnumerable collection)
{
InsertRange(Count, collection);
}
///
/// Removes all elements from the .
///
public void Clear()
{
// Clearing the buffer means simply enlarging the gap to the
// entire buffer size
Array.Clear(this._buffer, 0, this._buffer.Length);
this._gapStart = 0;
this._gapEnd = this._buffer.Length;
this._version++;
}
///
/// Determines whether an element is in the .
///
/// The object to locate in the . The value
/// can be null for reference types.
/// true if item is found in the ;
/// otherwise, false.
public bool Contains(T item)
{
// Search on both sides of the gap for the item
EqualityComparer comparer = EqualityComparer.Default;
for (int i = 0; i < this._gapStart; i++)
{
if (comparer.Equals(this._buffer[i], item))
return true;
}
for (int i = this._gapEnd; i < this._buffer.Length; i++)
{
if (comparer.Equals(this._buffer[i], item))
return true;
}
return false;
}
// Explicit IList implementation
bool IList.Contains(object value)
{
if (IsCompatibleObject(value))
return Contains((T)value);
return false;
}
///
/// Copies the to a compatible one-dimensional array,
/// starting at the specified index of the target array.
///
/// The one-dimensional that is the destination of the elements
/// copied from . The must have zero-based indexing.
/// The zero-based index in at which copying begins.
/// is a null reference.
/// is less than 0.
///
/// is multidimensional.
/// -or-
/// is equal to or greater than the length of .
/// -or-
/// The number of elements in the source is greater than the available space
/// from to the end of the destination .
///
public void CopyTo(T[] array, int arrayIndex)
{
if (array == null)
throw new ArgumentNullException("array");
if (arrayIndex < 0)
throw new ArgumentOutOfRangeException("arrayIndex", "Offset and length were out of bounds for the array or count is greater than the number of elements from index to the end of the source collection.");
if (array.Rank != 1)
throw new ArgumentException("Only single dimensional arrays are supported for the requested action.", "array");
if (arrayIndex >= array.Length || arrayIndex + Count > array.Length)
throw new ArgumentException("Offset and length were out of bounds for the array or count is greater than the number of elements from index to the end of the source collection.", "arrayIndex");
// Copy the spans into the destination array at the offset
Array.Copy(this._buffer, 0, array, arrayIndex, this._gapStart);
Array.Copy(this._buffer, this._gapEnd, array, arrayIndex + this._gapStart, this._buffer.Length - this._gapEnd);
}
// Explicit ICollection implementation
void ICollection.CopyTo(Array array, int arrayIndex)
{
try
{
CopyTo((T[])array, arrayIndex);
}
catch (InvalidCastException)
{
throw new ArgumentException("Target array type is not compatible with the type of items in the collection.", "array");
}
catch
{
throw;
}
}
///
/// Returns an enumerator that iterates through the .
///
/// A for the .
public GapBuffer.Enumerator GetEnumerator()
{
return new GapBuffer.Enumerator(this);
}
// Explicit IEnumerable implementation
IEnumerator IEnumerable.GetEnumerator()
{
return new GapBuffer.Enumerator(this);
}
// Explicit IEnumerable implementation
IEnumerator IEnumerable.GetEnumerator()
{
return new GapBuffer.Enumerator(this);
}
///
/// Searches for the specified object and returns the zero-based index of the first
/// occurrence within the .
///
/// The object to locate in the . The value
/// can be null for reference types.
/// The zero-based index of the first occurrence of within
/// the , if found; otherwise, –1.
public int IndexOf(T item)
{
// Search within the buffer spans
int index = Array.IndexOf(this._buffer, item, 0, this._gapStart);
if (index < 0)
{
index = Array.IndexOf(this._buffer, item, this._gapEnd, this._buffer.Length - this._gapEnd);
// Translate the internal index to the index in the collection
if (index != -1)
return index - (this._gapEnd - this._gapStart);
}
return index;
}
// Explicit IList implementation
int IList.IndexOf(object item)
{
if (IsCompatibleObject(item))
return IndexOf((T)item);
return -1;
}
///
/// Inserts an element into the at the specified index. Consecutive operations
/// at or near previous inserts are optimized.
///
/// The object to insert. The value can be null for reference types.
/// The zero-based index at which should be inserted.
///
/// is less than 0.
/// -or-
/// is greater than .
///
public void Insert(int index, T item)
{
if (index < 0 || index > Count)
throw new ArgumentOutOfRangeException("index", "Index must be non-negative and less than the size of the collection.");
// Prepare the buffer
PlaceGapStart(index);
EnsureGapCapacity(1);
this._buffer[index] = item;
this._gapStart++;
this._version++;
}
// Explicit IList implementation
void IList.Insert(int index, object item)
{
VerifyValueType(item);
Insert(index, (T)item);
}
///
/// Inserts the elements of a collection into the at the specified index.
/// Consecutive operations at or near previous inserts are optimized.
///
/// The zero-based index at which the new elements should be inserted.
/// The collection whose elements should be inserted into the .
/// The collection itself cannot be null, but it can contain elements that are null, if
/// type is a reference type.
/// is a null reference.
///
/// is less than 0.
/// -or-
/// is greater than .
///
public void InsertRange(int index, IEnumerable collection)
{
if (collection == null)
throw new ArgumentNullException("collection");
if (index < 0 || index > Count)
throw new ArgumentOutOfRangeException("index", "Index must be non-negative and less than the size of the collection.");
ICollection col = collection as ICollection;
if (col != null)
{
int count = col.Count;
if (count > 0)
{
PlaceGapStart(index);
EnsureGapCapacity(count);
// Copy the collection directly into the buffer
col.CopyTo(this._buffer, this._gapStart);
this._gapStart += count;
}
}
else
{
// Add the items to the buffer one-at-a-time :(
using (IEnumerator enumerator = collection.GetEnumerator())
{
while (enumerator.MoveNext())
{
Insert(index, enumerator.Current);
index++;
}
}
}
this._version++;
}
///
/// Removes the first occurrence of a specific object from the .
///
/// The object to remove from the . The
/// value can be null for reference types.
/// true if is successfully removed; otherwise,
/// false. This method also returns false if was not
/// found in the .
public bool Remove(T item)
{
// Get the index of the item
int index = IndexOf(item);
if (index < 0)
return false;
// Remove the item
RemoveAt(index);
return true;
}
// Explicit IList implementation
void IList.Remove(object item)
{
if (IsCompatibleObject(item))
Remove((T)item);
}
///
/// Removes the element at the specified index of the .
///
/// The zero-based index of the element to remove.
///
/// is less than 0.
/// -or-
/// is equal to or greater than .
///
public void RemoveAt(int index)
{
if (index < 0 || index >= Count)
throw new ArgumentOutOfRangeException("index", "Index must be non-negative and less than the size of the collection.");
// Place the gap at the index and increase the gap size by 1
PlaceGapStart(index);
this._buffer[this._gapEnd] = default(T);
this._gapEnd++;
this._version++;
}
///
/// Removes the last element from this GapBuffer instance.
///
public void RemoveLast()
{
RemoveAt(Count - 1);
}
///
/// Removes a range of elements from the .
///
/// The zero-based starting index of the range of elements to remove.
/// The number of elements to remove.
///
/// is less than 0 or is equal to or greater than .
/// -or-
/// is less than 0.
/// -or-
/// and do not denote a valid range of elements in
/// the .
///
public void RemoveRange(int index, int count)
{
int size = Count;
if (index < 0 || index >= size)
throw new ArgumentOutOfRangeException("index", "Index must be non-negative and less than the size of the collection.");
if (count < 0 || size - index < count)
throw new ArgumentOutOfRangeException("count", "Count must be positive and count must refer to a location within the string/array/collection.");
// Move the gap over the index and increase the gap size
// by the number of elements removed. Easy as pie!
if (count > 0)
{
PlaceGapStart(index);
Array.Clear(this._buffer, this._gapEnd, count);
this._gapEnd += count;
this._version++;
}
}
///
/// Sets the to the actual number of elements in the ,
/// if that number is less than a threshold value.
///
public void TrimExcess()
{
int size = Count;
int threshold = (int)(_buffer.Length * 0.9);
if (size < threshold)
{
Capacity = size;
}
}
// Moves the gap start to the given index
private void PlaceGapStart(int index)
{
// Are we already there?
if (index == this._gapStart)
return;
// Is there even a gap?
if ((this._gapEnd - this._gapStart) == 0)
{
this._gapStart = index;
this._gapEnd = index;
return;
}
// Which direction do we move the gap?
if (index < this._gapStart)
{
// Move the gap near (by copying the items at the beginning
// of the gap to the end)
int count = this._gapStart - index;
int deltaCount = (this._gapEnd - this._gapStart < count ? this._gapEnd - this._gapStart : count);
Array.Copy(this._buffer, index, this._buffer, this._gapEnd - count, count);
this._gapStart -= count;
this._gapEnd -= count;
// Clear the contents of the gap
Array.Clear(this._buffer, index, deltaCount);
}
else
{
// Move the gap far (by copying the items at the end
// of the gap to the beginning)
int count = index - this._gapStart;
int deltaIndex = (index > this._gapEnd ? index : this._gapEnd);
Array.Copy(this._buffer, this._gapEnd, this._buffer, this._gapStart, count);
this._gapStart += count;
this._gapEnd += count;
// Clear the contents of the gap
Array.Clear(this._buffer, deltaIndex, this._gapEnd - deltaIndex);
}
}
// Expands the interal array if the required size isn't available
private void EnsureGapCapacity(int required)
{
// Is the available space in the gap?
if (required > (this._gapEnd - this._gapStart))
{
// Calculate a new size (double the size necessary)
int newCapacity = (Count + required) * 2;
if (newCapacity < MIN_CAPACITY)
newCapacity = MIN_CAPACITY;
Capacity = newCapacity;
}
}
private static bool IsCompatibleObject(object value)
{
// Ensure the object is compatible with the generic type
if (!(value is T) && ((value != null) || typeof(T).IsValueType))
return false;
return true;
}
private static void VerifyValueType(object value)
{
// Throw an exception if the object is not compatible with
// the generic type
if (!IsCompatibleObject(value))
{
string message = String.Format(CultureInfo.CurrentCulture, "The value { 0}" +
" is not of type { 1}" +
" and cannot be used in this generic collection", value, typeof(T));
throw new ArgumentException(message, "value");
}
}
#endregion Methods
}
}