Tanoda
Deque.cs
Go to the documentation of this file.
1/******************************************************************************
2 * Copyright (C) Ultraleap, Inc. 2011-2020. *
3 * *
4 * Use subject to the terms of the Apache License 2.0 available at *
5 * http://www.apache.org/licenses/LICENSE-2.0, or another agreement *
6 * between Ultraleap and you, your company or other organization. *
7 ******************************************************************************/
8
9using System;
10using UnityEngine;
11
12namespace Leap.Unity {
13
14 public class Deque<T> {
15 private T[] _array;
16 private uint _front, _count;
17 private uint _indexMask;
18
19 public Deque(int minCapacity = 8) {
20 if (minCapacity <= 0) {
21 throw new ArgumentException("Capacity must be positive and nonzero.");
22 }
23
24 //Find next highest power of two
25 int capacity = Mathf.ClosestPowerOfTwo(minCapacity);
26 if (capacity < minCapacity) {
27 capacity *= 2;
28 }
29
30 _array = new T[capacity];
31 recalculateIndexMask();
32 _front = 0;
33 _count = 0;
34 }
35
36 public int Count {
37 get {
38 return (int)_count;
39 }
40 }
41
42 public void Clear() {
43 if (_count != 0) {
44 Array.Clear(_array, 0, _array.Length);
45 _front = 0;
46 _count = 0;
47 }
48 }
49
50 public void PushBack(T t) {
51 doubleCapacityIfFull();
52 ++_count;
53 _array[getBackIndex()] = t;
54 }
55
56 public void PushFront(T t) {
57 doubleCapacityIfFull();
58 ++_count;
59 _front = (_front - 1) & _indexMask;
60 _array[_front] = t;
61 }
62
63 public void PopBack() {
64 checkForEmpty("pop back");
65
66 _array[getBackIndex()] = default(T);
67 --_count;
68 }
69
70 public void PopFront() {
71 checkForEmpty("pop front");
72
73 _array[_front] = default(T);
74 --_count;
75 _front = (_front + 1) & _indexMask;
76 }
77
78 public void PopBack(out T back) {
79 checkForEmpty("pop back");
80
81 uint backIndex = getBackIndex();
82 back = _array[backIndex];
83 _array[backIndex] = default(T);
84 --_count;
85 }
86
87 public void PopFront(out T front) {
88 checkForEmpty("pop front");
89
90 front = _array[_front];
91 _array[_front] = default(T);
92 _front = (_front + 1) & _indexMask;
93 --_count;
94 }
95
96 public T Front {
97 get {
98 checkForEmpty("get front");
99 return _array[_front];
100 }
101 set {
102 checkForEmpty("set front");
103 _array[_front] = value;
104 }
105 }
106
107 public T Back {
108 get {
109 checkForEmpty("get back");
110 return _array[getBackIndex()];
111 }
112 set {
113 checkForEmpty("set back");
114 _array[getBackIndex()] = value;
115 }
116 }
117
118 public T this[int index] {
119 get {
120 uint uindex = (uint)index;
121 checkForValidIndex(uindex);
122 return _array[getIndex(uindex)];
123 }
124 set {
125 uint uindex = (uint)index;
126 checkForValidIndex(uindex);
127 _array[getIndex(uindex)] = value;
128 }
129 }
130
131 public string ToDebugString() {
132 string debug = "[";
133 uint back = getBackIndex();
134 for (uint i = 0; i < _array.Length; i++) {
135 bool isEmpty;
136 if (_count == 0) {
137 isEmpty = true;
138 } else if (_count == 1) {
139 isEmpty = i != _front;
140 } else if (_front < back) {
141 isEmpty = (i < _front) || (i > back);
142 } else {
143 isEmpty = (i < _front) && (i > back);
144 }
145
146 string element = "";
147 if (i == _front) {
148 element = "{";
149 } else {
150 element = " ";
151 }
152
153 if (isEmpty) {
154 element += ".";
155 } else {
156 element += _array[i].ToString();
157 }
158
159 if (i == back) {
160 element += "}";
161 } else {
162 element += " ";
163 }
164
165 debug += element;
166 }
167 debug += "]";
168 return debug;
169 }
170
171 private uint getBackIndex() {
172 return (_front + _count - 1) & _indexMask;
173 }
174
175 private uint getIndex(uint index) {
176 return (_front + index) & _indexMask;
177 }
178
179 private void doubleCapacityIfFull() {
180 if (_count >= _array.Length) {
181 T[] newArray = new T[_array.Length * 2];
182
183 uint front = getBackIndex();
184 if (_front <= front) {
185 //values do not wrap around, we can use a simple copy
186 Array.Copy(_array, _front, newArray, 0, _count);
187 } else {
188 //values do wrap around, we need to use 2 copies
189 uint backOffset = (uint)_array.Length - _front;
190 Array.Copy(_array, _front, newArray, 0, backOffset);
191 Array.Copy(_array, 0, newArray, backOffset, _count - backOffset);
192 }
193
194 _front = 0;
195 _array = newArray;
196 recalculateIndexMask();
197 }
198 }
199
200 private void recalculateIndexMask() {
201 //array length is always power of 2, so length-1 is the bitmask we need
202 //8 = 1000
203 //7 = 0111 = mask for values 0-7
204 _indexMask = (uint)_array.Length - 1;
205 }
206
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 + ".");
210 }
211 }
212
213 private void checkForEmpty(string actionName) {
214 if (_count == 0) {
215 throw new InvalidOperationException("Cannot " + actionName + " because the RingBuffer is empty.");
216 }
217 }
218 }
219}
string ToDebugString()
Definition: Deque.cs:131
void PopFront()
Definition: Deque.cs:70
void PushBack(T t)
Definition: Deque.cs:50
void PopFront(out T front)
Definition: Deque.cs:87
void PopBack()
Definition: Deque.cs:63
void Clear()
Definition: Deque.cs:42
void PopBack(out T back)
Definition: Deque.cs:78
void PushFront(T t)
Definition: Deque.cs:56
Deque(int minCapacity=8)
Definition: Deque.cs:19