16 private uint _front, _count;
17 private uint _indexMask;
19 public Deque(
int minCapacity = 8) {
20 if (minCapacity <= 0) {
21 throw new ArgumentException(
"Capacity must be positive and nonzero.");
25 int capacity = Mathf.ClosestPowerOfTwo(minCapacity);
26 if (capacity < minCapacity) {
30 _array =
new T[capacity];
31 recalculateIndexMask();
44 Array.Clear(_array, 0, _array.Length);
51 doubleCapacityIfFull();
53 _array[getBackIndex()] = t;
57 doubleCapacityIfFull();
59 _front = (_front - 1) & _indexMask;
64 checkForEmpty(
"pop back");
66 _array[getBackIndex()] =
default(T);
71 checkForEmpty(
"pop front");
73 _array[_front] =
default(T);
75 _front = (_front + 1) & _indexMask;
79 checkForEmpty(
"pop back");
81 uint backIndex = getBackIndex();
82 back = _array[backIndex];
83 _array[backIndex] =
default(T);
88 checkForEmpty(
"pop front");
90 front = _array[_front];
91 _array[_front] =
default(T);
92 _front = (_front + 1) & _indexMask;
98 checkForEmpty(
"get front");
99 return _array[_front];
102 checkForEmpty(
"set front");
103 _array[_front] = value;
109 checkForEmpty(
"get back");
110 return _array[getBackIndex()];
113 checkForEmpty(
"set back");
114 _array[getBackIndex()] = value;
118 public T
this[
int index] {
120 uint uindex = (uint)index;
121 checkForValidIndex(uindex);
122 return _array[getIndex(uindex)];
125 uint uindex = (uint)index;
126 checkForValidIndex(uindex);
127 _array[getIndex(uindex)] = value;
133 uint back = getBackIndex();
134 for (uint i = 0; i < _array.Length; i++) {
138 }
else if (_count == 1) {
139 isEmpty = i != _front;
140 }
else if (_front < back) {
141 isEmpty = (i < _front) || (i > back);
143 isEmpty = (i < _front) && (i > back);
156 element += _array[i].ToString();
171 private uint getBackIndex() {
172 return (_front + _count - 1) & _indexMask;
175 private uint getIndex(uint index) {
176 return (_front + index) & _indexMask;
179 private void doubleCapacityIfFull() {
180 if (_count >= _array.Length) {
181 T[] newArray =
new T[_array.Length * 2];
183 uint front = getBackIndex();
184 if (_front <= front) {
186 Array.Copy(_array, _front, newArray, 0, _count);
189 uint backOffset = (uint)_array.Length - _front;
190 Array.Copy(_array, _front, newArray, 0, backOffset);
191 Array.Copy(_array, 0, newArray, backOffset, _count - backOffset);
196 recalculateIndexMask();
200 private void recalculateIndexMask() {
204 _indexMask = (uint)_array.Length - 1;
207 private void checkForValidIndex(uint index) {
208 if (index >= _count) {
209 throw new IndexOutOfRangeException(
"The index " + index +
" was out of range for the RingBuffer with size " + _count +
".");
213 private void checkForEmpty(
string actionName) {
215 throw new InvalidOperationException(
"Cannot " + actionName +
" because the RingBuffer is empty.");
void PopFront(out T front)