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
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; |
|
} |
|
} |
|
} |
|
} |