| 1 | using UnityEngine; |
| 2 | using System; |
| 3 | using System.Collections; |
| 4 | using System.Collections.Generic; |
| 5 | |
| 6 | public 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 | } |