/*
* Copyright (C) 2013 FooProject
* * This program is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by
* the Free Software Foundation; either version 3 of the License, or (at your option) any later version.
* This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.
You should have received a copy of the GNU General Public License along with this program. If not, see .
*/
#region Using Directives
using System;
using System.Collections.Generic;
using System.Collections;
using System.Text;
using System.Threading;
using System.Globalization;
using System.Diagnostics;
#endregion Using Directives
namespace Slusser.Collections.Generic
{
///
/// 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.
///
/// The type of elements in the buffer.
[DebuggerDisplay("Count = {Count}")]
[DebuggerTypeProxy(typeof(CollectionDebugView<>))]
sealed 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;
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", "");
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", "");
// 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", "");
// 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.
/// The count of collction.count is -1 when this method is slowly
/// is a null reference.
public void AddRange(IEnumerable collection,int count = -1)
{
InsertRange(Count, collection,count);
}
///
/// 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", "");
if (array.Rank != 1)
throw new ArgumentException("", "array");
if (arrayIndex >= array.Length || arrayIndex + Count > array.Length)
throw new ArgumentException("", "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("", "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, E.
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", "");
// 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, ICollection col)
{
if (col == null)
throw new ArgumentNullException("collection");
if (index < 0 || index > Count)
throw new ArgumentOutOfRangeException("index", "");
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;
}
}
this._version++;
}
///
/// 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.
/// The count of collction.count is -1 when this method is slowly
/// is a null reference.
///
/// is less than 0.
/// -or-
/// is greater than .
///
public void InsertRange(int index, IEnumerable collection, int preallocatCount = -1)
{
if (collection == null)
throw new ArgumentNullException("collection");
if (index < 0 || index > Count)
throw new ArgumentOutOfRangeException("index", "");
if (preallocatCount == -1)
{
// Add the items to the buffer one-at-a-time :(
using (IEnumerator enumerator = collection.GetEnumerator())
{
while (enumerator.MoveNext())
{
Insert(index, enumerator.Current);
index++;
}
}
}
else if(preallocatCount > 0)
{
PlaceGapStart(index);
EnsureGapCapacity(preallocatCount);
int collectionLength = 0;
using (IEnumerator enumerator = collection.GetEnumerator())
{
while (enumerator.MoveNext())
{
this._buffer[index] = enumerator.Current;
index++;
collectionLength++;
}
}
this._gapStart += collectionLength;
}
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", "");
// 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 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", "");
if (count < 0 || size - index < count)
throw new ArgumentOutOfRangeException("count", "");
// 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) || value is ValueType))
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))
{
throw new ArgumentException("", "value");
}
}
#endregion Methods
}
}