BlueGit

blue-star ggj-2020

Files

ggj-2020 / Assets / Oculus / AudioManager / Scripts / Utils / FastList.cs

FastList.cs

Project Import
timfa Tim Falken · pushed by timfa · 6 years ago
b77834a1 History
FastList.cs 6.9 KiB Download Raw
1using UnityEngine;
2using System;
3using System.Collections;
4using System.Collections.Generic;
5
6public class FastList<T> {
7
8 /// <summary>
9 /// Comparison function should return -1 if left is less than right, 1 if left is greater than right, and 0 if they match.
10 /// </summary>
11 public delegate int CompareFunc(T left, T right);
12
13
14 public T[] array = null;
15 public int size = 0;
16
17 public FastList () {
18 }
19
20 public FastList(int size) {
21 if (size > 0) {
22 this.size = 0;
23 array = new T[size];
24 }
25 else {
26 this.size = 0;
27 }
28 }
29
30 public int Count {
31 get { return size;}
32 set { }
33 }
34
35 public T this[int i] {
36 get { return array[i];}
37 set { array[i] = value;}
38 }
39
40 //Add item to end of list.
41 public void Add(T item) {
42 if (array == null || size == array.Length) {
43 Allocate();
44 }
45 array[size] = item;
46 size++;
47 }
48
49 //Add item to end of list if it is unique.
50 public void AddUnique( T item ) {
51 if ( array == null || size == array.Length ) {
52 Allocate();
53 }
54 if ( !Contains( item ) ) {
55 array[size] = item;
56 size++;
57 }
58 }
59
60 //Add items to the end of the list
61 public void AddRange( IEnumerable<T> items ) {
62 foreach ( T item in items ) {
63 Add( item );
64 }
65 }
66
67 //Insert item at specified index
68 public void Insert(int index, T item) {
69 if (array == null || size == array.Length) {
70 Allocate();
71 }
72 if (index < size) {
73 //move things back 1
74 for (int i = size; i > index; i--) {
75 array[i] = array[i-1];
76 }
77 array[index] = item;
78 size++;
79 }
80 else Add(item);
81 }
82
83 //Removes specified item and keeps everything else in order
84 public bool Remove(T item) {
85 if (array != null) {
86 for (int i = 0; i < size; i++) {
87 if (item.Equals(array[i])) { //found it, push everything up
88 size--;
89 for (int j = i; j < size; j++) {
90 array[j] = array[j+1];
91 }
92 array[size] = default(T);
93 return true;
94 }
95 }
96 }
97 return false;
98 }
99
100 //Removes item at specified index while keeping everything else in order
101 //O(n)
102 public void RemoveAt(int index) {
103 if (array != null && size > 0 && index < size) {
104 size--;
105 for (int i = index; i < size; i++) {
106 array[i] = array[i+1];
107 }
108 array[size] = default(T);
109 }
110 }
111
112 //Removes the specified item from the list and replaces with last item. Return true if removed, false if not found.
113 public bool RemoveFast(T item) {
114 if (array != null) {
115 for (int i = 0; i < size; i++) {
116 if ( item.Equals( array[i] )) { //found
117 //Move last item here
118 if (i < (size - 1)) {
119 T lastItem = array[size-1];
120 array[size-1] = default(T);
121 array[i] = lastItem;
122 } else {
123 array[i] = default(T);
124 }
125 size--;
126 return true;
127 }
128 }
129 }
130 return false;
131 }
132
133 //Removes item at specified index and replace with last item.
134 public void RemoveAtFast(int index) {
135 if (array != null && index < size && index >= 0) {
136 //last element
137 if (index == size - 1) {
138 array[index] = default(T);
139 }
140 else {
141 T lastItem = array[size - 1];
142 array[index] = lastItem;
143 array[size - 1] = default(T);
144 }
145 size--;
146
147 }
148 }
149
150 //Return whether an item is contained within the list
151 //O(n)
152 public bool Contains(T item) {
153 if (array == null || size <= 0 ) return false;
154 for (int i = 0; i < size; i++) {
155 if (array[i].Equals(item)) { return true;}
156 }
157 return false;
158 }
159
160 //Returns index of specified item, or -1 if not found.
161 //O(n)
162 public int IndexOf(T item) {
163 if (size <= 0 || array == null) { return -1;}
164 for (int i = 0; i < size; i++) {
165 if (item.Equals(array[i])) { return i;}
166 }
167 return -1;
168 }
169
170 public T Pop() {
171 if (array != null && size > 0) {
172 T lastItem = array[size-1];
173 array[size-1] = default(T);
174 size--;
175 return lastItem;
176 }
177
178 return default(T);
179 }
180
181 public T[] ToArray() {
182 Trim();
183 return array;
184 }
185
186 public void Sort (CompareFunc comparer) {
187 int start = 0;
188 int end = size - 1;
189 bool changed = true;
190
191 while (changed) {
192 changed = false;
193
194 for (int i = start; i < end; i++) {
195
196 if (comparer(array[i], array[i + 1]) > 0) {
197 T temp = array[i];
198 array[i] = array[i+1];
199 array[i+1] = temp;
200 changed = true;
201 }
202 else if (!changed) {
203 start = (i==0) ? 0 : i-1;
204 }
205 }
206 }
207 }
208
209 public void InsertionSort(CompareFunc comparer) {
210 for (int i = 1; i < size; i++) {
211 T curr = array[i];
212 int j = i;
213 while (j > 0 && comparer(array[j - 1], curr) > 0) {
214 array[j] = array[j-1];
215 j--;
216 }
217 array[j] = curr;
218 }
219 }
220
221 public IEnumerator<T> GetEnumerator() {
222 if (array != null) {
223 for (int i = 0; i < size; i++) {
224 yield return array[i];
225 }
226 }
227 }
228
229 public T Find(Predicate<T> match) {
230 if (match != null) {
231 if (array != null) {
232 for (int i = 0; i < size; i++) {
233 if (match(array[i])) { return array[i];}
234 }
235 }
236 }
237 return default(T);
238 }
239
240 //Allocate more space to internal array.
241 void Allocate() {
242 T[] newArray;
243 if (array == null) {
244 newArray = new T[32];
245 }
246 else {
247 newArray = new T[Mathf.Max(array.Length << 1, 32)];
248 }
249 if (array != null && size > 0) {
250 array.CopyTo(newArray, 0);
251 }
252
253 array = newArray;
254 }
255
256
257 void Trim() {
258 if (size > 0) {
259 T[] newArray = new T[size];
260 for (int i = 0; i < size; i++) {
261 newArray[i] = array[i];
262 }
263 array = newArray;
264 }
265 else {
266 array = null;
267 }
268 }
269
270 //Set size to 0, does not delete array from memory
271 public void Clear() {
272 size = 0;
273 }
274
275 //Delete array from memory
276 public void Release() {
277 Clear();
278 array = null;
279 }
280
281
282
283}