A game about forced loneliness, made by TACStudios
tacstudios.tngl.sh
1using System;
2using System.Collections;
3using System.Collections.Generic;
4using System.Linq;
5
6////REVIEW: what about ignoring 'firstValue' entirely in case length > 1 and putting everything into an array in that case
7
8namespace UnityEngine.InputSystem.Utilities
9{
10 /// <summary>
11 /// Helper to avoid array allocations if there's only a single value in the array.
12 /// </summary>
13 /// <remarks>
14 /// Also, once more than one entry is necessary, allows treating the extra array as having capacity.
15 /// This means that, for example, 5 or 10 entries can be allocated in batch rather than growing an
16 /// array one by one.
17 /// </remarks>
18 /// <typeparam name="TValue">Element type for the array.</typeparam>
19 internal struct InlinedArray<TValue> : IEnumerable<TValue>
20 {
21 // We inline the first value so if there's only one, there's
22 // no additional allocation. If more are added, we allocate an array.
23 public int length;
24 public TValue firstValue;
25 public TValue[] additionalValues;
26
27 public int Capacity => additionalValues?.Length + 1 ?? 1;
28
29 public InlinedArray(TValue value)
30 {
31 length = 1;
32 firstValue = value;
33 additionalValues = null;
34 }
35
36 public InlinedArray(TValue firstValue, params TValue[] additionalValues)
37 {
38 length = 1 + additionalValues.Length;
39 this.firstValue = firstValue;
40 this.additionalValues = additionalValues;
41 }
42
43 public InlinedArray(IEnumerable<TValue> values)
44 : this()
45 {
46 length = values.Count();
47 if (length > 1)
48 additionalValues = new TValue[length - 1];
49 else
50 additionalValues = null;
51
52 var index = 0;
53 foreach (var value in values)
54 {
55 if (index == 0)
56 firstValue = value;
57 else
58 additionalValues[index - 1] = value;
59 ++index;
60 }
61 }
62
63 public TValue this[int index]
64 {
65 get
66 {
67 if (index < 0 || index >= length)
68 throw new ArgumentOutOfRangeException(nameof(index));
69
70 if (index == 0)
71 return firstValue;
72
73 return additionalValues[index - 1];
74 }
75 set
76 {
77 if (index < 0 || index >= length)
78 throw new ArgumentOutOfRangeException(nameof(index));
79
80 if (index == 0)
81 firstValue = value;
82 else
83 additionalValues[index - 1] = value;
84 }
85 }
86
87 public void Clear()
88 {
89 length = 0;
90 firstValue = default;
91 additionalValues = null;
92 }
93
94 public void ClearWithCapacity()
95 {
96 firstValue = default;
97 for (var i = 0; i < length - 1; ++i)
98 additionalValues[i] = default;
99 length = 0;
100 }
101
102 ////REVIEW: This is inconsistent with ArrayHelpers.Clone() which also clones elements
103 public InlinedArray<TValue> Clone()
104 {
105 return new InlinedArray<TValue>
106 {
107 length = length,
108 firstValue = firstValue,
109 additionalValues = additionalValues != null ? ArrayHelpers.Copy(additionalValues) : null
110 };
111 }
112
113 public void SetLength(int size)
114 {
115 // Null out everything we're cutting off.
116 if (size < length)
117 {
118 for (var i = size; i < length; ++i)
119 this[i] = default;
120 }
121
122 length = size;
123
124 if (size > 1 && (additionalValues == null || additionalValues.Length < size - 1))
125 Array.Resize(ref additionalValues, size - 1);
126 }
127
128 public TValue[] ToArray()
129 {
130 return ArrayHelpers.Join(firstValue, additionalValues);
131 }
132
133 public TOther[] ToArray<TOther>(Func<TValue, TOther> mapFunction)
134 {
135 if (length == 0)
136 return null;
137
138 var result = new TOther[length];
139 for (var i = 0; i < length; ++i)
140 result[i] = mapFunction(this[i]);
141
142 return result;
143 }
144
145 public int IndexOf(TValue value)
146 {
147 var comparer = EqualityComparer<TValue>.Default;
148 if (length > 0)
149 {
150 if (comparer.Equals(firstValue, value))
151 return 0;
152 if (additionalValues != null)
153 {
154 for (var i = 0; i < length - 1; ++i)
155 if (comparer.Equals(additionalValues[i], value))
156 return i + 1;
157 }
158 }
159
160 return -1;
161 }
162
163 public int Append(TValue value)
164 {
165 if (length == 0)
166 {
167 firstValue = value;
168 }
169 else if (additionalValues == null)
170 {
171 additionalValues = new TValue[1];
172 additionalValues[0] = value;
173 }
174 else
175 {
176 Array.Resize(ref additionalValues, length);
177 additionalValues[length - 1] = value;
178 }
179
180 var index = length;
181 ++length;
182 return index;
183 }
184
185 public int AppendWithCapacity(TValue value, int capacityIncrement = 10)
186 {
187 if (length == 0)
188 {
189 firstValue = value;
190 }
191 else
192 {
193 var numAdditionalValues = length - 1;
194 ArrayHelpers.AppendWithCapacity(ref additionalValues, ref numAdditionalValues, value, capacityIncrement: capacityIncrement);
195 }
196
197 var index = length;
198 ++length;
199 return index;
200 }
201
202 public void AssignWithCapacity(InlinedArray<TValue> values)
203 {
204 if (Capacity < values.length && values.length > 1)
205 additionalValues = new TValue[values.length - 1];
206
207 length = values.length;
208 if (length > 0)
209 firstValue = values.firstValue;
210 if (length > 1)
211 Array.Copy(values.additionalValues, additionalValues, length - 1);
212 }
213
214 public void Append(IEnumerable<TValue> values)
215 {
216 foreach (var value in values)
217 Append(value);
218 }
219
220 public void Remove(TValue value)
221 {
222 if (length < 1)
223 return;
224
225 if (EqualityComparer<TValue>.Default.Equals(firstValue, value))
226 {
227 RemoveAt(0);
228 }
229 else if (additionalValues != null)
230 {
231 for (var i = 0; i < length - 1; ++i)
232 {
233 if (EqualityComparer<TValue>.Default.Equals(additionalValues[i], value))
234 {
235 RemoveAt(i + 1);
236 break;
237 }
238 }
239 }
240 }
241
242 public void RemoveAtWithCapacity(int index)
243 {
244 if (index < 0 || index >= length)
245 throw new ArgumentOutOfRangeException(nameof(index));
246
247 if (index == 0)
248 {
249 if (length == 1)
250 {
251 firstValue = default;
252 }
253 else if (length == 2)
254 {
255 firstValue = additionalValues[0];
256 additionalValues[0] = default;
257 }
258 else
259 {
260 Debug.Assert(length > 2);
261 firstValue = additionalValues[0];
262 var numAdditional = length - 1;
263 ArrayHelpers.EraseAtWithCapacity(additionalValues, ref numAdditional, 0);
264 }
265 }
266 else
267 {
268 var numAdditional = length - 1;
269 ArrayHelpers.EraseAtWithCapacity(additionalValues, ref numAdditional, index - 1);
270 }
271
272 --length;
273 }
274
275 public void RemoveAt(int index)
276 {
277 if (index < 0 || index >= length)
278 throw new ArgumentOutOfRangeException(nameof(index));
279
280 if (index == 0)
281 {
282 if (additionalValues != null)
283 {
284 firstValue = additionalValues[0];
285 if (additionalValues.Length == 1)
286 additionalValues = null;
287 else
288 {
289 Array.Copy(additionalValues, 1, additionalValues, 0, additionalValues.Length - 1);
290 Array.Resize(ref additionalValues, additionalValues.Length - 1);
291 }
292 }
293 else
294 {
295 firstValue = default;
296 }
297 }
298 else
299 {
300 Debug.Assert(additionalValues != null);
301
302 var numAdditionalValues = length - 1;
303 if (numAdditionalValues == 1)
304 {
305 // Remove only entry in array.
306 additionalValues = null;
307 }
308 else if (index == length - 1)
309 {
310 // Remove entry at end.
311 Array.Resize(ref additionalValues, numAdditionalValues - 1);
312 }
313 else
314 {
315 // Remove entry at beginning or in middle by pasting together
316 // into a new array.
317 var newAdditionalValues = new TValue[numAdditionalValues - 1];
318 if (index >= 2)
319 {
320 // Copy elements before entry.
321 Array.Copy(additionalValues, 0, newAdditionalValues, 0, index - 1);
322 }
323
324 // Copy elements after entry. We already know that we're not removing
325 // the last entry so there have to be entries.
326 Array.Copy(additionalValues, index + 1 - 1, newAdditionalValues, index - 1,
327 length - index - 1);
328
329 additionalValues = newAdditionalValues;
330 }
331 }
332
333 --length;
334 }
335
336 public void RemoveAtByMovingTailWithCapacity(int index)
337 {
338 if (index < 0 || index >= length)
339 throw new ArgumentOutOfRangeException(nameof(index));
340
341 var numAdditionalValues = length - 1;
342 if (index == 0)
343 {
344 if (length > 1)
345 {
346 firstValue = additionalValues[numAdditionalValues - 1];
347 additionalValues[numAdditionalValues - 1] = default;
348 }
349 else
350 {
351 firstValue = default;
352 }
353 }
354 else
355 {
356 Debug.Assert(additionalValues != null);
357
358 ArrayHelpers.EraseAtByMovingTail(additionalValues, ref numAdditionalValues, index - 1);
359 }
360
361 --length;
362 }
363
364 public bool RemoveByMovingTailWithCapacity(TValue value)
365 {
366 var index = IndexOf(value);
367 if (index == -1)
368 return false;
369
370 RemoveAtByMovingTailWithCapacity(index);
371 return true;
372 }
373
374 public bool Contains(TValue value, IEqualityComparer<TValue> comparer)
375 {
376 for (var n = 0; n < length; ++n)
377 if (comparer.Equals(this[n], value))
378 return true;
379 return false;
380 }
381
382 public void Merge(InlinedArray<TValue> other)
383 {
384 var comparer = EqualityComparer<TValue>.Default;
385 for (var i = 0; i < other.length; ++i)
386 {
387 var value = other[i];
388 if (Contains(value, comparer))
389 continue;
390
391 ////FIXME: this is ugly as it repeatedly copies
392 Append(value);
393 }
394 }
395
396 public IEnumerator<TValue> GetEnumerator()
397 {
398 return new Enumerator { array = this, index = -1 };
399 }
400
401 IEnumerator IEnumerable.GetEnumerator()
402 {
403 return GetEnumerator();
404 }
405
406 private struct Enumerator : IEnumerator<TValue>
407 {
408 public InlinedArray<TValue> array;
409 public int index;
410
411 public bool MoveNext()
412 {
413 if (index >= array.length)
414 return false;
415 ++index;
416 return index < array.length;
417 }
418
419 public void Reset()
420 {
421 index = -1;
422 }
423
424 public TValue Current => array[index];
425 object IEnumerator.Current => Current;
426
427 public void Dispose()
428 {
429 }
430 }
431 }
432
433 internal static class InputArrayExtensions
434 {
435 public static int IndexOfReference<TValue>(this InlinedArray<TValue> array, TValue value)
436 where TValue : class
437 {
438 for (var i = 0; i < array.length; ++i)
439 if (ReferenceEquals(array[i], value))
440 return i;
441
442 return -1;
443 }
444
445 public static bool Contains<TValue>(this InlinedArray<TValue> array, TValue value)
446 {
447 for (var i = 0; i < array.length; ++i)
448 if (array[i].Equals(value))
449 return true;
450 return false;
451 }
452
453 public static bool ContainsReference<TValue>(this InlinedArray<TValue> array, TValue value)
454 where TValue : class
455 {
456 return IndexOfReference(array, value) != -1;
457 }
458 }
459}