贵港路建设路地下商业街网上演练
You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
 
 
 

667 lines
18 KiB

using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace AX.AudioSystem
{
/// <summary>
/// 表示一个双端队列数据结构。
/// </summary>
internal class Deque<T> : IList<T>, IEnumerable<T>
{
private const int defaultCapacity = 16;
private int capacityMinusOne;
private int startOffset;
private T[] buffer;
public Deque() : this(defaultCapacity) { }
public Deque(int capacity)
{
if (capacity < 0)
throw new ArgumentOutOfRangeException("capacity", "Capacity 不能小于 0.");
this.Capacity = capacity;
}
public Deque(IEnumerable<T> collection)
: this(LinqCount(collection))
{
InsertRange(0, collection);
}
public int Capacity
{
get
{
return buffer.Length;
}
set
{
if (value < 0)
throw new ArgumentOutOfRangeException("value", "Capacity 不能小于 0.");
else if (value < this.Count)
throw new InvalidOperationException("Capacity 不能设置为小于 Count 的值");
else if (null != buffer && value == buffer.Length)
return;
// 创建一个新数组,并复制旧数组中的数据
int powOfTwo = ClosestPowerOfTwoGreaterThan(value);
value = powOfTwo;
T[] newBuffer = new T[value];
CopyTo(newBuffer, 0);
buffer = newBuffer;
startOffset = 0;
capacityMinusOne = powOfTwo - 1;
}
}
public bool IsEmpty
{
get { return 0 == this.Count; }
}
private void EnsureCapacity(int count)
{
var computedCapacity = this.Count + count;
if (computedCapacity > this.Capacity)
this.Capacity = computedCapacity;
}
private int ToBufferIndex(int index)
{
int bufferIndex;
bufferIndex = (index + this.startOffset) & this.capacityMinusOne;
return bufferIndex;
}
private void CheckIndex(int index)
{
if (index >= this.Count)
throw new IndexOutOfRangeException("给定的索引值超过了 Count");
}
private static void CheckArguments(int length, int offset, int count)
{
if (offset < 0)
throw new ArgumentOutOfRangeException("offset", "无效的偏移量 " + offset);
if (count < 0)
throw new ArgumentOutOfRangeException("count", "无效的总数 " + count);
if (length - offset < count)
throw new ArgumentException(String.Format("无效的偏移量 ({0}) 或总数 + ({1}) " + ",因为原长度是 {2}", offset, count, length));
}
private int ShiftStartOffset(int value)
{
this.startOffset = ToBufferIndex(value);
return this.startOffset;
}
private int PreShiftStartOffset(int value)
{
int offset = this.startOffset;
this.ShiftStartOffset(value);
return offset;
}
private int PostShiftStartOffset(int value)
{
return ShiftStartOffset(value);
}
#region IEnumerable
public IEnumerator<T> GetEnumerator()
{
if (this.startOffset + this.Count > this.Capacity)
{
for (int i = this.startOffset; i < this.Capacity; i++)
yield return buffer[i];
int endIndex = ToBufferIndex(this.Count);
for (int i = 0; i < endIndex; i++)
yield return buffer[i];
}
else
{
int endIndex = this.startOffset + this.Count;
for (int i = this.startOffset; i < endIndex; i++)
yield return buffer[i];
}
}
IEnumerator IEnumerable.GetEnumerator()
{
return this.GetEnumerator();
}
#endregion
#region ICollection
bool ICollection<T>.IsReadOnly
{
get { return false; }
}
public int Count
{
get;
private set;
}
private void IncrementCount(int value)
{
this.Count = this.Count + value;
}
private void DecrementCount(int value)
{
this.Count = Math.Max(this.Count - value, 0);
}
public void Add(T item)
{
AddBack(item);
}
private void ClearBuffer(int logicalIndex, int length)
{
int offset = ToBufferIndex(logicalIndex);
if (offset + length > this.Capacity)
{
int len = this.Capacity - offset;
Array.Clear(this.buffer, offset, len);
len = ToBufferIndex(logicalIndex + length);
Array.Clear(this.buffer, 0, len);
}
else
{
Array.Clear(this.buffer, offset, length);
}
}
private void GetBuffer(int logicalIndex, int length, T[] data)
{
int offset = ToBufferIndex(logicalIndex);
if (offset + length > this.Capacity)
{
int len = this.Capacity - offset;
Array.Copy(this.buffer, offset, data, 0, len);
Array.Clear(this.buffer, offset, len);
int newlen = ToBufferIndex(logicalIndex + length);
Array.Copy(this.buffer, 0, data, len, newlen);
Array.Clear(this.buffer, 0, newlen);
}
else
{
Array.Copy(this.buffer, offset, data, 0, length);
Array.Clear(this.buffer, offset, length);
}
}
private void TakeBuffer(int logicalIndex, int length, T[] data)
{
int offset = ToBufferIndex(logicalIndex);
if (offset + length > this.Capacity)
{
int len = this.Capacity - offset;
Array.Copy(this.buffer, offset, data, 0, len);
int newlen = ToBufferIndex(logicalIndex + length);
Array.Copy(this.buffer, 0, data, len, newlen);
}
else
{
Array.Copy(this.buffer, offset, data, 0, length);
}
}
public void Clear()
{
if (this.Count > 0)
ClearBuffer(0, this.Count);
this.Count = 0;
this.startOffset = 0;
}
public bool Contains(T item)
{
return this.IndexOf(item) != -1;
}
public void CopyTo(T[] array, int arrayIndex)
{
if (null == array)
throw new ArgumentNullException("array", "数组不能为 null");
// Nothing to copy
if (null == this.buffer)
return;
CheckArguments(array.Length, arrayIndex, this.Count);
if (0 != this.startOffset && this.startOffset + this.Count >= this.Capacity)
{
int lengthFromStart = this.Capacity - this.startOffset;
int lengthFromEnd = this.Count - lengthFromStart;
Array.Copy(buffer, this.startOffset, array, 0, lengthFromStart);
Array.Copy(buffer, 0, array, lengthFromStart, lengthFromEnd);
}
else
{
Array.Copy(buffer, this.startOffset, array, 0, Count);
}
}
public bool Remove(T item)
{
bool result = true;
int index = IndexOf(item);
if (-1 == index)
result = false;
else
RemoveAt(index);
return result;
}
#endregion
#region List<T>
public T this[int index]
{
get { return this.Get(index); }
set { this.Set(index, value); }
}
public void Insert(int index, T item)
{
EnsureCapacity(1);
if (index == 0)
{
AddFront(item);
return;
}
else if (index == Count)
{
AddBack(item);
return;
}
InsertRange(index, new[] { item });
}
public int IndexOf(T item)
{
int index = 0;
foreach (var myItem in this)
{
if (myItem.Equals(item))
{
break;
}
++index;
}
if (index == this.Count)
{
index = -1;
}
return index;
}
public void RemoveAt(int index)
{
if (index == 0)
{
RemoveFront();
return;
}
else if (index == Count - 1)
{
RemoveBack();
return;
}
RemoveRange(index, 1);
}
#endregion
public void AddFront(T item)
{
EnsureCapacity(1);
buffer[PostShiftStartOffset(-1)] = item;
IncrementCount(1);
}
public void AddBack(T item)
{
EnsureCapacity(1);
buffer[ToBufferIndex(this.Count)] = item;
IncrementCount(1);
}
public T RemoveFront()
{
if (this.IsEmpty)
throw new InvalidOperationException("队列是空的");
T result = buffer[this.startOffset];
buffer[PreShiftStartOffset(1)] = default(T);
DecrementCount(1);
return result;
}
public T RemoveBack()
{
if (this.IsEmpty)
throw new InvalidOperationException("队列是空的");
DecrementCount(1);
int endIndex = ToBufferIndex(this.Count);
T result = buffer[endIndex];
buffer[endIndex] = default(T);
return result;
}
public void AddRange(IEnumerable<T> collection)
{
AddBackRange(collection);
}
public void AddFrontRange(IEnumerable<T> collection)
{
AddFrontRange(collection, 0, LinqCount(collection));
}
public void AddFrontRange(IEnumerable<T> collection, int fromIndex, int count)
{
InsertRange(0, collection, fromIndex, count);
}
public void AddBackRange(IEnumerable<T> collection)
{
AddBackRange(collection, 0, LinqCount(collection));
}
public void AddBackRange(IEnumerable<T> collection, int fromIndex, int count)
{
InsertRange(this.Count, collection, fromIndex, count);
}
public void InsertRange(int index, IEnumerable<T> collection)
{
int count = LinqCount(collection);
this.InsertRange(index, collection, 0, count);
}
public void InsertRange(int index, IEnumerable<T> collection, int fromIndex, int count)
{
CheckIndex(index - 1);
if (0 == count)
return;
EnsureCapacity(count);
if (index < this.Count / 2)
{
if (index > 0)
{
int copyCount = index;
int shiftIndex = this.Capacity - count;
for (int j = 0; j < copyCount; j++)
buffer[ToBufferIndex(shiftIndex + j)] = buffer[ToBufferIndex(j)];
}
this.ShiftStartOffset(-count);
}
else
{
if (index < this.Count)
{
int copyCount = this.Count - index;
int shiftIndex = index + count;
for (int j = 0; j < copyCount; j++)
buffer[ToBufferIndex(shiftIndex + j)] = buffer[ToBufferIndex(index + j)];
}
}
int i = index;
foreach (T item in collection)
{
buffer[ToBufferIndex(i)] = item;
++i;
}
IncrementCount(count);
}
public void RemoveRange(int index, int count)
{
if (this.IsEmpty)
throw new InvalidOperationException("队列是空的");
if (index > Count - count)
throw new IndexOutOfRangeException("给定的索引超过了 Count");
ClearBuffer(index, count);
if (index == 0)
{
this.ShiftStartOffset(count);
this.Count -= count;
return;
}
else if (index == Count - count)
{
this.Count -= count;
return;
}
if ((index + (count / 2)) < Count / 2)
{
int copyCount = index;
int writeIndex = count;
for (int j = 0; j < copyCount; j++)
buffer[ToBufferIndex(writeIndex + j)] = buffer[ToBufferIndex(j)];
this.ShiftStartOffset(count);
}
else
{
int copyCount = Count - count - index;
int readIndex = index + count;
for (int j = 0; j < copyCount; ++j)
buffer[ToBufferIndex(index + j)] = buffer[ToBufferIndex(readIndex + j)];
}
DecrementCount(count);
}
public void RemoveBackRange(int count)
{
RemoveRange(this.Count - count, count);
}
public void RemoveFrontRange(int count)
{
RemoveRange(0, count);
}
public void GetRange(int index, int count, T[] data)
{
if (this.IsEmpty)
throw new InvalidOperationException("队列是空的");
if (index > Count - count)
throw new IndexOutOfRangeException("给定的索引超过了 Count");
if (data == null)
throw new ArgumentNullException("data");
if (data.Length < count)
throw new ArgumentOutOfRangeException("data");
GetBuffer(index, count, data);
}
public void GetFrontRange(int count, T[] data)
{
GetRange(0, count, data);
}
public void GetBackRange(int count, T[] data)
{
GetRange(this.Count - count, count, data);
}
public void TakeRange(int index, int count, T[] data)
{
if (this.IsEmpty)
throw new InvalidOperationException("队列是空的");
if (index > Count - count)
throw new IndexOutOfRangeException("给定的索引超过了 Count");
if (data == null)
throw new ArgumentNullException("data");
if (data.Length < count)
throw new ArgumentOutOfRangeException("data");
TakeBuffer(index, count, data);
if (index == 0)
{
this.ShiftStartOffset(count);
this.Count -= count;
return;
}
else if (index == Count - count)
{
this.Count -= count;
return;
}
if ((index + (count / 2)) < Count / 2)
{
int copyCount = index;
int writeIndex = count;
for (int j = 0; j < copyCount; j++)
buffer[ToBufferIndex(writeIndex + j)] = buffer[ToBufferIndex(j)];
this.ShiftStartOffset(count);
}
else
{
int copyCount = Count - count - index;
int readIndex = index + count;
for (int j = 0; j < copyCount; ++j)
buffer[ToBufferIndex(index + j)] = buffer[ToBufferIndex(readIndex + j)];
}
DecrementCount(count);
}
public void TakeFrontRange(int count, T[] data)
{
TakeRange(0, count, data);
}
public void TakeBackRange(int count, T[] data)
{
TakeRange(this.Count - count, count, data);
}
public T Get(int index)
{
CheckIndex(index);
return buffer[ToBufferIndex(index)];
}
public void Set(int index, T item)
{
CheckIndex(index);
buffer[ToBufferIndex(index)] = item;
}
private static int ClosestPowerOfTwoGreaterThan(int x)
{
x--;
x |= (x >> 1);
x |= (x >> 2);
x |= (x >> 4);
x |= (x >> 8);
x |= (x >> 16);
return (x + 1);
}
/// <summary>
/// 重新实现 LINQ Count 扩展方法。
/// </summary>
private static int LinqCount<TSource>(IEnumerable<TSource> source)
{
if (source == null)
throw new ArgumentNullException("source");
ICollection<TSource> genericCollection = source as ICollection<TSource>;
if (genericCollection != null)
return genericCollection.Count;
ICollection nonGenericCollection = source as ICollection;
if (nonGenericCollection != null)
return nonGenericCollection.Count;
checked
{
int count = 0;
using (var iterator = source.GetEnumerator())
{
while (iterator.MoveNext())
count++;
}
return count;
}
}
}
}