A game about forced loneliness, made by TACStudios
tacstudios.tngl.sh
1using System;
2using System.Collections.Generic;
3using System.Diagnostics;
4
5namespace UnityEngine.Rendering
6{
7 /// <summary>
8 /// Generic growable array.
9 /// </summary>
10 /// <typeparam name="T">Type of the array.</typeparam>
11 [DebuggerDisplay("Size = {size} Capacity = {capacity}")]
12 public class DynamicArray<T> where T : new()
13 {
14 /// <summary>
15 /// The C# array memory used to store the DynamicArray values in. This array's Length may be longer than the DynamicArrayLength. Objects beyond the length should not be referenced.
16 /// </summary>
17 protected T[] m_Array = null;
18
19 /// <summary>
20 /// Number of elements in the array. There may be more elements allocated. Use `capacity` to query the number of allocated items.
21 /// </summary>
22 public int size { get; protected set; }
23
24 /// <summary>
25 /// Allocated size of the array.
26 /// </summary>
27 public int capacity { get { return m_Array.Length; } }
28
29#if DEVELOPMENT_BUILD || UNITY_EDITOR
30 /// <summary>
31 /// This keeps track of structural modifications to this array and allows us to raise exceptions when modifying during enumeration
32 /// </summary>
33 protected internal int version { get; protected set; }
34#endif
35
36 /// <summary>
37 /// Constructor.
38 /// Defaults to a capacity of 32 elements. The size will be 0.
39 /// </summary>
40 public DynamicArray()
41 {
42 m_Array = new T[32];
43 size = 0;
44#if DEVELOPMENT_BUILD || UNITY_EDITOR
45 version = 0;
46#endif
47 }
48
49 /// <summary>
50 /// Constructor. This constructor allocates memory and sets the size of the array to the specified number of elements.
51 /// </summary>
52 /// <param name="size">Number of elements. The elements are initialized to the default value of the element type, 0 for integers.</param>
53 public DynamicArray(int size)
54 {
55 m_Array = new T[size];
56 this.size = size;
57#if DEVELOPMENT_BUILD || UNITY_EDITOR
58 version = 0;
59#endif
60 }
61
62 /// <summary>
63 /// Constructor. This overload allows you to only allocate memory without setting the size.
64 /// </summary>
65 /// <param name="capacity">The number of elements to allocate.</param>
66 /// <param name="resize">If true, also set the size of the array to the passed in capacity. If false, only allocate data but keep the size at 0.</param>
67 public DynamicArray(int capacity, bool resize)
68 {
69 m_Array = new T[capacity];
70 this.size = (resize) ? capacity : 0;
71#if DEVELOPMENT_BUILD || UNITY_EDITOR
72 version = 0;
73#endif
74 }
75
76 /// <summary>
77 /// Constructor. This constructor allocates memory and does a deep copy of the provided array.
78 /// </summary>
79 /// <param name="deepCopy">Array to be copied</param>
80 public DynamicArray(DynamicArray<T> deepCopy)
81 {
82 m_Array = new T[deepCopy.size];
83 size = deepCopy.size;
84 Array.Copy(deepCopy.m_Array, m_Array, size);
85#if DEVELOPMENT_BUILD || UNITY_EDITOR
86 version = 0;
87#endif
88 }
89
90 /// <summary>
91 /// Clear the array of all elements.
92 /// </summary>
93 public void Clear()
94 {
95 size = 0;
96 }
97
98 /// <summary>
99 /// Determines whether the DynamicArray contains a specific value.
100 /// </summary>
101 /// <param name="item">The object to locate in the DynamicArray.</param>
102 /// <returns>true if item is found in the DynamicArray; otherwise, false.</returns>
103 public bool Contains(T item)
104 {
105 return IndexOf(item) != -1;
106 }
107
108 /// <summary>
109 /// Add an element to the array.
110 /// </summary>
111 /// <param name="value">Element to add to the array.</param>
112 /// <returns>The index of the element.</returns>
113 public int Add(in T value)
114 {
115 int index = size;
116
117 // Grow array if needed;
118 if (index >= m_Array.Length)
119 {
120 var newArray = new T[Math.Max(m_Array.Length * 2,1)];
121 Array.Copy(m_Array, newArray, m_Array.Length);
122 m_Array = newArray;
123 }
124
125 m_Array[index] = value;
126 size++;
127 BumpVersion();
128 return index;
129 }
130
131 /// <summary>
132 /// Adds the elements of the specified collection to the end of the DynamicArray.
133 /// </summary>
134 /// <param name="array">The array whose elements should be added to the end of the DynamicArray. The array itself cannot be null, but it can contain elements that are null, if type T is a reference type.</param>
135 public void AddRange(DynamicArray<T> array)
136 {
137 // Save the size before reserve. Otherwise things break when self-appending i.e. `a.AddRange(a)`
138 var addedSize = array.size;
139
140 Reserve(size + addedSize, true);
141 for (int i = 0; i < addedSize; ++i)
142 m_Array[size++] = array[i];
143 BumpVersion();
144 }
145
146 /// <summary>
147 /// Insert an item in the DynamicArray.
148 /// </summary>
149 /// <param name="index">Index where the item should be inserted.</param>
150 /// <param name="item">Item to be inserted in the DynamicArray.</param>
151 public void Insert(int index, T item)
152 {
153#if DEVELOPMENT_BUILD || UNITY_EDITOR
154 if (index < 0 || index > size)
155 throw new IndexOutOfRangeException();
156#endif
157 if (index == size)
158 Add(item);
159 else
160 {
161 Resize(size + 1, true);
162 Array.Copy(m_Array, index, m_Array, index + 1, size - index);
163 m_Array[index] = item;
164 }
165 }
166
167 /// <summary>
168 /// Removes the first occurrence of a specific object from the DynamicArray.
169 /// </summary>
170 /// <param name="item">The object to remove from the DynamicArray. The value can be null for reference types.</param>
171 /// <returns>true if item is successfully removed; otherwise, false. This method also returns false if item was not found in the DynamicArray.</returns>
172 public bool Remove(T item)
173 {
174 int index = IndexOf(item);
175 if (index != -1)
176 {
177 RemoveAt(index);
178 return true;
179 }
180
181 return false;
182 }
183
184 /// <summary>
185 /// Removes the element at the specified index of the DynamicArray.
186 /// </summary>
187 /// <param name="index">The zero-based index of the element to remove.</param>
188 public void RemoveAt(int index)
189 {
190#if DEVELOPMENT_BUILD || UNITY_EDITOR
191 if (index < 0 || index >= size)
192 throw new IndexOutOfRangeException();
193#endif
194
195 if (index != size - 1)
196 Array.Copy(m_Array, index + 1, m_Array, index, size - index - 1);
197
198 size--;
199 BumpVersion();
200 }
201
202 /// <summary>
203 /// Removes a range of elements from the DynamicArray.
204 /// </summary>
205 /// <param name="index">The zero-based starting index of the range of elements to remove.</param>
206 /// <param name="count">The number of elements to remove.</param>
207 public void RemoveRange(int index, int count)
208 {
209 if (count == 0)
210 return;
211
212#if DEVELOPMENT_BUILD || UNITY_EDITOR
213 if (index < 0 || index >= size || count < 0 || index + count > size)
214 throw new ArgumentOutOfRangeException();
215#endif
216
217 Array.Copy(m_Array, index + count, m_Array, index, size - index - count);
218 size -= count;
219 BumpVersion();
220 }
221
222 /// <summary>
223 /// Searches for an element that matches the conditions defined by the specified predicate, and returns the zero-based index of the first occurrence within the range of elements in the DynamicArray that starts at the specified index and contains the specified number of elements.
224 /// </summary>
225 /// <param name="startIndex">The zero-based starting index of the search.</param>
226 /// <param name="count">The number of elements in the section to search.</param>
227 /// <param name="match">The Predicate delegate that defines the conditions of the element to search for.</param>
228 /// <returns>The zero-based index of the first occurrence of an element that matches the conditions defined by match, if found; otherwise, -1.</returns>
229 public int FindIndex(int startIndex, int count, Predicate<T> match)
230 {
231 for (int i = startIndex; i < size; ++i)
232 {
233 if (match(m_Array[i]))
234 {
235 return i;
236 }
237 }
238 return -1;
239 }
240
241 /// <summary>
242 /// Searches for the specified object and returns the zero-based index of the first occurrence within the range of elements in the DynamicArray that starts at the specified index and contains the specified number of elements.
243 /// </summary>
244 /// <param name="item">The object to locate in the DynamicArray. The value can be null for reference types.</param>
245 /// <param name="index">The zero-based starting index of the search. 0 (zero) is valid in an empty list.</param>
246 /// <param name="count">The number of elements in the section to search.</param>
247 /// <returns>The index of the first occurrence of the object within the range of elements, or -1 if not found.</returns>
248 public int IndexOf(T item, int index, int count)
249 {
250 for (int i = index; i < size && count > 0; ++i, --count)
251 {
252 if (m_Array[i].Equals(item))
253 {
254 return i;
255 }
256 }
257 return -1;
258 }
259
260 /// <summary>
261 /// Searches for the specified object and returns the zero-based index of the first occurrence within the range of elements in the DynamicArray that extends from the specified index to the last element.
262 /// </summary>
263 /// <param name="item">The object to locate in the DynamicArray. The value can be null for reference types.</param>
264 /// <param name="index">The zero-based starting index of the search. 0 (zero) is valid in an empty list.</param>
265 /// <returns>The zero-based index of the first occurrence of item within the range of elements in the DynamicArray that extends from index to the last element, if found; otherwise, -1.</returns>
266 public int IndexOf(T item, int index)
267 {
268 for (int i = index; i < size; ++i)
269 {
270 if (m_Array[i].Equals(item))
271 {
272 return i;
273 }
274 }
275 return -1;
276 }
277
278 /// <summary>
279 /// Searches for the specified object and returns the zero-based index of the first occurrence within the entire DynamicArray.
280 /// </summary>
281 /// <param name="item">The object to locate in the DynamicArray. The value can be null for reference types.</param>
282 /// <returns>he zero-based index of the first occurrence of item within the entire DynamicArray, if found; otherwise, -1.</returns>
283 public int IndexOf(T item)
284 {
285 return IndexOf(item, 0);
286 }
287
288 /// <summary>
289 /// Resize the Dynamic Array.
290 /// This will reallocate memory if necessary and set the current size of the array to the provided size.
291 /// Note: The memory is not cleared so the elements may contain invalid data.
292 /// </summary>
293 /// <param name="newSize">New size for the array.</param>
294 /// <param name="keepContent">Set to true if you want the current content of the array to be kept.</param>
295 public void Resize(int newSize, bool keepContent = false)
296 {
297 Reserve(newSize, keepContent);
298 size = newSize;
299 BumpVersion();
300 }
301
302 /// <summary>
303 /// Resize the Dynamic Array.
304 /// This will reallocate memory if necessary and set the current size of the array to the provided size.
305 /// The elements are initialized to the default value of the element type, e.g. 0 for integers.
306 /// </summary>
307 /// <param name="newSize">New size for the array.</param>
308 public void ResizeAndClear(int newSize)
309 {
310 if (newSize > m_Array.Length)
311 {
312 // Reserve will allocate a whole new array that is cleared as part of the allocation
313 Reserve(newSize, false);
314 }
315 else
316 {
317 // We're not reallocating anything we need to clear the old values to the default.
318 Array.Clear(m_Array, 0, newSize);
319 }
320 size = newSize;
321 BumpVersion();
322 }
323
324 /// <summary>
325 /// Sets the total number of elements the internal data structure can hold without resizing.
326 /// </summary>
327 /// <param name="newCapacity">New capacity for the array.</param>
328 /// <param name="keepContent">Set to true if you want the current content of the array to be kept.</param>
329 public void Reserve(int newCapacity, bool keepContent = false)
330 {
331 if (newCapacity > m_Array.Length)
332 {
333 if (keepContent)
334 {
335 var newArray = new T[newCapacity];
336 Array.Copy(m_Array, newArray, m_Array.Length);
337 m_Array = newArray;
338 }
339 else
340 {
341 m_Array = new T[newCapacity];
342 }
343 }
344 }
345
346 /// <summary>
347 /// ref access to an element.
348 /// </summary>
349 /// <param name="index">Element index</param>
350 /// <value>The requested element.</value>
351 public ref T this[int index]
352 {
353 get
354 {
355#if DEVELOPMENT_BUILD || UNITY_EDITOR
356 if (index < 0 || index >= size)
357 throw new IndexOutOfRangeException();
358#endif
359 return ref m_Array[index];
360 }
361 }
362
363 /// <summary>
364 /// Implicit conversion to regular array.
365 /// </summary>
366 /// <param name="array">Input DynamicArray.</param>
367 /// <returns>The internal array.</returns>
368 [Obsolete("This is deprecated because it returns an incorrect value. It may returns an array with elements beyond the size. Please use Span/ReadOnly if you want safe raw access to the DynamicArray memory.",false)]
369 public static implicit operator T[](DynamicArray<T> array) => array.m_Array;
370
371 /// <summary>
372 /// Implicit conversion to ReadOnlySpan.
373 /// </summary>
374 /// <param name="array">Input DynamicArray.</param>
375 /// <returns>The internal array.</returns>
376 public static implicit operator ReadOnlySpan<T>(DynamicArray<T> array) => new ReadOnlySpan<T>(array.m_Array, 0, array.size);
377
378 /// <summary>
379 /// Implicit conversion to Span.
380 /// </summary>
381 /// <param name="array">Input DynamicArray.</param>
382 /// <returns>The internal array.</returns>
383 public static implicit operator Span<T>(DynamicArray<T> array) => new Span<T>(array.m_Array, 0, array.size);
384
385 /// <summary>
386 /// IEnumerator-like struct used to loop over this entire array. See the IEnumerator docs for more info:
387 /// <a href="https://docs.microsoft.com/en-us/dotnet/api/system.collections.ienumerator">IEnumerator</a>
388 /// </summary>
389 /// <remarks>
390 /// This struct intentionally does not explicitly implement the IEnumarable/IEnumerator interfaces it just follows
391 /// the same function signatures. This means the duck typing used by <c>foreach</c> on the compiler level will
392 /// pick it up as IEnumerable but at the same time avoids generating Garbage.
393 /// For more info, see the C# language specification of the <c>foreach</c> statement.
394 /// </remarks>
395 /// <seealso cref="RangeIterator"/>
396 public struct Iterator
397 {
398 private readonly DynamicArray<T> owner;
399 private int index;
400#if DEVELOPMENT_BUILD || UNITY_EDITOR
401 private int localVersion;
402#endif
403
404 /// <summary>
405 /// Creates an iterator to iterate over an array.
406 /// </summary>
407 /// <param name="setOwner">The array to iterate over.</param>
408 /// <exception cref="ArgumentNullException">Thrown if the array is null.</exception>
409 public Iterator(DynamicArray<T> setOwner)
410 {
411#if DEVELOPMENT_BUILD || UNITY_EDITOR
412 if (setOwner == null)
413 throw new ArgumentNullException();
414#endif
415 owner = setOwner;
416 index = -1;
417#if DEVELOPMENT_BUILD || UNITY_EDITOR
418 localVersion = owner.version;
419#endif
420 }
421
422 /// <summary>
423 /// Gets the element in the DynamicArray at the current position of the iterator.
424 /// </summary>
425 public ref T Current
426 {
427 get
428 {
429 return ref owner[index];
430 }
431 }
432
433 /// <summary>
434 /// Advances the iterator to the next element of the DynamicArray.
435 /// </summary>
436 /// <returns>Returns <c>true</c> if the iterator has successfully advanced to the next element; <c>false</c> if the iterator has passed the end of the DynamicArray.</returns>
437 /// <exception cref="InvalidOperationException">An operation changed the DynamicArray after the creation of this iterator.</exception>
438 public bool MoveNext()
439 {
440#if DEVELOPMENT_BUILD || UNITY_EDITOR
441 if (owner.version != localVersion)
442 {
443 throw new InvalidOperationException("DynamicArray was modified during enumeration");
444 }
445#endif
446 index++;
447 return index < owner.size;
448 }
449
450 /// <summary>
451 /// Sets the iterator to its initial position, which is before the first element in the DynamicArray.
452 /// </summary>
453 public void Reset()
454 {
455 index = -1;
456 }
457 }
458
459 /// <summary>
460 /// Returns an enumerator that iterates through of this array.
461 /// See the IEnumerable docs for more info: <a href="https://docs.microsoft.com/en-us/dotnet/api/system.collections.ienumerable" >IEnumerable</a>
462 /// </summary>
463 /// <remarks>
464 /// The returned struct intentionally does not explicitly implement the IEnumarable/IEnumerator interfaces it just follows
465 /// the same function signatures. This means the duck typing used by <c>foreach</c> on the compiler level will
466 /// pick it up as IEnumerable but at the same time avoids generating Garbage.
467 /// For more info, see the C# language specification of the <c>foreach</c> statement.
468 /// </remarks>
469 /// <returns>Iterator pointing before the first element in the array.</returns>
470 public Iterator GetEnumerator()
471 {
472 return new Iterator(this);
473 }
474
475 /// <summary>
476 /// IEnumerable-like struct used to iterate through a subsection of this array.
477 /// See the IEnumerable docs for more info: <a href="https://docs.microsoft.com/en-us/dotnet/api/system.collections.ienumerable">IEnumerable</a>
478 /// </summary>
479 /// <remarks>
480 /// This struct intentionally does not explicitly implement the IEnumarable/IEnumerator interfaces it just follows
481 /// the same function signatures. This means the duck typing used by <c>foreach</c> on the compiler level will
482 /// pick it up as IEnumerable but at the same time avoids generating Garbage.
483 /// For more info, see the C# language specification of the <c>foreach</c> statement.
484 /// </remarks>
485 /// <seealso cref="SubRange"/>
486 public struct RangeEnumerable
487 {
488 /// <summary>
489 /// IEnumerator-like struct used to iterate through a subsection of this array.
490 /// See the IEnumerator docs for more info: <a href="https://docs.microsoft.com/en-us/dotnet/api/system.collections.ienumerator">IEnumerator</a>
491 /// </summary>
492 /// <remarks>
493 /// This struct intentionally does not explicitly implement the IEnumarable/IEnumerator interfaces it just follows
494 /// the same function signatures. This means the duck typing used by <c>foreach</c> on the compiler level will
495 /// pick it up as <c>IEnumarable</c> but at the same time avoids generating Garbage.
496 /// For more info, see the C# language specification of the <c>foreach</c> statement.
497 /// </remarks>
498 /// <seealso cref="SubRange"/>
499 public struct RangeIterator
500 {
501 private readonly DynamicArray<T> owner;
502 private int index;
503 private int first;
504 private int last;
505#if DEVELOPMENT_BUILD || UNITY_EDITOR
506 private int localVersion;
507#endif
508
509
510 /// <summary>
511 /// Create an iterator to iterate over the given range in the array.
512 /// </summary>
513 /// <param name="setOwner">The array to iterate over.</param>
514 /// <param name="first">The index of the first item in the array.</param>
515 /// <param name="numItems">The number of array members to iterate through.</param>
516 /// <exception cref="ArgumentNullException">Thrown if the array is null.</exception>
517 public RangeIterator(DynamicArray<T> setOwner, int first, int numItems)
518 {
519#if DEVELOPMENT_BUILD || UNITY_EDITOR
520 if (setOwner == null)
521 throw new ArgumentNullException();
522 if (first < 0 || first > setOwner.size || (first + numItems) > setOwner.size)
523 throw new IndexOutOfRangeException();
524#endif
525 owner = setOwner;
526 this.first = first;
527 index = first-1;
528 last = first + numItems;
529#if DEVELOPMENT_BUILD || UNITY_EDITOR
530 localVersion = owner.version;
531#endif
532 }
533
534 /// <summary>
535 /// Gets the element in the DynamicArray at the current position of the iterator.
536 /// </summary>
537 public ref T Current
538 {
539 get
540 {
541 return ref owner[index];
542 }
543 }
544
545 /// <summary>
546 /// Advances the iterator to the next element of the DynamicArray.
547 /// </summary>
548 /// <returns>Returs <c>true</c> if the iterator successfully advanced to the next element; returns <c>false</c> if the iterator has passed the end of the range.</returns>
549 /// <exception cref="InvalidOperationException">The DynamicArray was modified after the iterator was created.</exception>
550 public bool MoveNext()
551 {
552#if DEVELOPMENT_BUILD || UNITY_EDITOR
553 if (owner.version != localVersion)
554 {
555 throw new InvalidOperationException("DynamicArray was modified during enumeration");
556 }
557#endif
558 index++;
559 return index < last;
560 }
561
562 /// <summary>
563 /// Sets the iterator to its initial position, which is before the first element in the range.
564 /// </summary>
565 public void Reset()
566 {
567 index = first-1;
568 }
569 }
570
571 /// <summary>
572 /// The iterator associated with this Enumerable.
573 /// </summary>
574 public RangeIterator iterator;
575
576 /// <summary>
577 /// Returns an enumerator that iterates through this array.
578 /// </summary>
579 /// <remarks>
580 /// The returned struct intentionally does not explicitly implement the IEnumarable/IEnumerator interfaces it just follows
581 /// the same function signatures. This means the duck typing used by <c>foreach</c> on the compiler level will
582 /// pick it up as IEnumerable but at the same time avoids generating Garbage.
583 /// For more info, see the C# language specification of the <c>foreach</c> statement.
584 /// </remarks>
585 /// <returns>Iterator pointing before the first element in the range.</returns>
586 public RangeIterator GetEnumerator()
587 {
588 return iterator;
589 }
590 }
591
592 /// <summary>
593 /// Returns an IEnumeralbe-Like object that iterates through a subsection of this array.
594 /// </summary>
595 /// <remarks>
596 /// The returned struct intentionally does not explicitly implement the IEnumarable/IEnumerator interfaces it just follows
597 /// the same function signatures. This means the duck typing used by <c>foreach</c> on the compiler level will
598 /// pick it up as IEnumerable but at the same time avoids generating Garbage.
599 /// For more info, see the C# language specification of the <c>foreach</c> statement.
600 /// </remarks>
601 /// <param name="first">The index of the first item</param>
602 /// <param name="numItems">The number of items to iterate</param>
603 /// <returns><c>RangeEnumerable</c> that can be used to enumerate the given range.</returns>
604 /// <seealso cref="RangeIterator"/>
605 public RangeEnumerable SubRange(int first, int numItems)
606 {
607 RangeEnumerable r = new RangeEnumerable { iterator = new RangeEnumerable.RangeIterator(this, first, numItems) };
608 return r;
609 }
610
611 /// <summary>
612 /// Increments the internal version counter.
613 /// </summary>
614 protected internal void BumpVersion()
615 {
616#if DEVELOPMENT_BUILD || UNITY_EDITOR
617 version++;
618#endif
619 }
620
621 /// <summary>
622 /// Delegate for custom sorting comparison.
623 /// </summary>
624 /// <param name="x">First object.</param>
625 /// <param name="y">Second object.</param>
626 /// <returns>-1 if x smaller than y, 1 if x bigger than y and 0 otherwise.</returns>
627 public delegate int SortComparer(T x, T y);
628 }
629
630 /// <summary>
631 /// Extension class for DynamicArray
632 /// </summary>
633 public static class DynamicArrayExtensions
634 {
635 static int Partition<T>(Span<T> data, int left, int right) where T : IComparable<T>, new()
636 {
637 var pivot = data[left];
638
639 --left;
640 ++right;
641 while (true)
642 {
643 var c = 0;
644 var lvalue = default(T);
645 do
646 {
647 ++left;
648 lvalue = data[left];
649 c = lvalue.CompareTo(pivot);
650 }
651 while (c < 0);
652
653 var rvalue = default(T);
654 do
655 {
656 --right;
657 rvalue = data[right];
658 c = rvalue.CompareTo(pivot);
659 }
660 while (c > 0);
661
662 if (left < right)
663 {
664 data[right] = lvalue;
665 data[left] = rvalue;
666 }
667 else
668 {
669 return right;
670 }
671 }
672 }
673
674 static void QuickSort<T>(Span<T> data, int left, int right) where T : IComparable<T>, new()
675 {
676 if (left < right)
677 {
678 int pivot = Partition(data, left, right);
679
680 if (pivot >= 1)
681 QuickSort(data, left, pivot);
682
683 if (pivot + 1 < right)
684 QuickSort(data, pivot + 1, right);
685 }
686 }
687
688 // C# SUCKS
689 // Had to copy paste because it's apparently impossible to pass a sort delegate where T is Comparable<T>, otherwise some boxing happens and allocates...
690 // So two identical versions of the function, one with delegate but no Comparable and the other with just the comparable.
691 static int Partition<T>(Span<T> data, int left, int right, DynamicArray<T>.SortComparer comparer) where T : new()
692 {
693 var pivot = data[left];
694
695 --left;
696 ++right;
697 while (true)
698 {
699 var c = 0;
700 var lvalue = default(T);
701 do
702 {
703 ++left;
704 lvalue = data[left];
705 c = comparer(lvalue, pivot);
706 }
707 while (c < 0);
708
709 var rvalue = default(T);
710 do
711 {
712 --right;
713 rvalue = data[right];
714 c = comparer(rvalue, pivot);
715 }
716 while (c > 0);
717
718 if (left < right)
719 {
720 data[right] = lvalue;
721 data[left] = rvalue;
722 }
723 else
724 {
725 return right;
726 }
727 }
728 }
729
730 static void QuickSort<T>(Span<T> data, int left, int right, DynamicArray<T>.SortComparer comparer) where T : new()
731 {
732 if (left < right)
733 {
734 int pivot = Partition(data, left, right, comparer);
735
736 if (pivot >= 1)
737 QuickSort(data, left, pivot, comparer);
738
739 if (pivot + 1 < right)
740 QuickSort(data, pivot + 1, right, comparer);
741 }
742 }
743
744 /// <summary>
745 /// Perform a quick sort on the DynamicArray
746 /// </summary>
747 /// <typeparam name="T">Type of the array.</typeparam>
748 /// <param name="array">Array on which to perform the quick sort.</param>
749 public static void QuickSort<T>(this DynamicArray<T> array) where T : IComparable<T>, new()
750 {
751 QuickSort<T>(array, 0, array.size - 1);
752 array.BumpVersion();
753 }
754
755 /// <summary>
756 /// Perform a quick sort on the DynamicArray
757 /// </summary>
758 /// <typeparam name="T">Type of the array.</typeparam>
759 /// <param name="array">Array on which to perform the quick sort.</param>
760 /// <param name="comparer">Comparer used for sorting.</param>
761 public static void QuickSort<T>(this DynamicArray<T> array, DynamicArray<T>.SortComparer comparer) where T : new()
762 {
763 QuickSort<T>(array, 0, array.size - 1, comparer);
764 array.BumpVersion();
765 }
766 }
767}