using System;
using System.Collections.Generic;
using System.Diagnostics;
namespace UnityEngine.Rendering
{
/// <summary>
/// Generic growable array.
/// </summary>
/// <typeparam name="T">Type of the array.</typeparam>
[DebuggerDisplay("Size = {size} Capacity = {capacity}")]
public class DynamicArray<T> where T : new()
{
/// <summary>
/// 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.
/// </summary>
protected T[] m_Array = null;
/// <summary>
/// Number of elements in the array. There may be more elements allocated. Use `capacity` to query the number of allocated items.
/// </summary>
public int size { get; protected set; }
/// <summary>
/// Allocated size of the array.
/// </summary>
public int capacity { get { return m_Array.Length; } }
#if DEVELOPMENT_BUILD || UNITY_EDITOR
/// <summary>
/// This keeps track of structural modifications to this array and allows us to raise exceptions when modifying during enumeration
/// </summary>
protected internal int version { get; protected set; }
#endif
/// <summary>
/// Constructor.
/// Defaults to a capacity of 32 elements. The size will be 0.
/// </summary>
public DynamicArray()
{
m_Array = new T[32];
size = 0;
#if DEVELOPMENT_BUILD || UNITY_EDITOR
version = 0;
#endif
}
/// <summary>
/// Constructor. This constructor allocates memory and sets the size of the array to the specified number of elements.
/// </summary>
/// <param name="size">Number of elements. The elements are initialized to the default value of the element type, 0 for integers.</param>
public DynamicArray(int size)
{
m_Array = new T[size];
this.size = size;
#if DEVELOPMENT_BUILD || UNITY_EDITOR
version = 0;
#endif
}
/// <summary>
/// Constructor. This overload allows you to only allocate memory without setting the size.
/// </summary>
/// <param name="capacity">The number of elements to allocate.</param>
/// <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>
public DynamicArray(int capacity, bool resize)
{
m_Array = new T[capacity];
this.size = (resize) ? capacity : 0;
#if DEVELOPMENT_BUILD || UNITY_EDITOR
version = 0;
#endif
}
/// <summary>
/// Constructor. This constructor allocates memory and does a deep copy of the provided array.
/// </summary>
/// <param name="deepCopy">Array to be copied</param>
public DynamicArray(DynamicArray<T> deepCopy)
{
m_Array = new T[deepCopy.size];
size = deepCopy.size;
Array.Copy(deepCopy.m_Array, m_Array, size);
#if DEVELOPMENT_BUILD || UNITY_EDITOR
version = 0;
#endif
}
/// <summary>
/// Clear the array of all elements.
/// </summary>
public void Clear()
{
size = 0;
}
/// <summary>
/// Determines whether the DynamicArray contains a specific value.
/// </summary>
/// <param name="item">The object to locate in the DynamicArray.</param>
/// <returns>true if item is found in the DynamicArray; otherwise, false.</returns>
public bool Contains(T item)
{
return IndexOf(item) != -1;
}
/// <summary>
/// Add an element to the array.
/// </summary>
/// <param name="value">Element to add to the array.</param>
/// <returns>The index of the element.</returns>
public int Add(in T value)
{
int index = size;
// Grow array if needed;
if (index >= m_Array.Length)
{
var newArray = new T[Math.Max(m_Array.Length * 2,1)];
Array.Copy(m_Array, newArray, m_Array.Length);
m_Array = newArray;
}
m_Array[index] = value;
size++;
BumpVersion();
return index;
}
/// <summary>
/// Adds the elements of the specified collection to the end of the DynamicArray.
/// </summary>
/// <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>
public void AddRange(DynamicArray<T> array)
{
// Save the size before reserve. Otherwise things break when self-appending i.e. `a.AddRange(a)`
var addedSize = array.size;
Reserve(size + addedSize, true);
for (int i = 0; i < addedSize; ++i)
m_Array[size++] = array[i];
BumpVersion();
}
/// <summary>
/// Insert an item in the DynamicArray.
/// </summary>
/// <param name="index">Index where the item should be inserted.</param>
/// <param name="item">Item to be inserted in the DynamicArray.</param>
public void Insert(int index, T item)
{
#if DEVELOPMENT_BUILD || UNITY_EDITOR
if (index < 0 || index > size)
throw new IndexOutOfRangeException();
#endif
if (index == size)
Add(item);
else
{
Resize(size + 1, true);
Array.Copy(m_Array, index, m_Array, index + 1, size - index);
m_Array[index] = item;
}
}
/// <summary>
/// Removes the first occurrence of a specific object from the DynamicArray.
/// </summary>
/// <param name="item">The object to remove from the DynamicArray. The value can be null for reference types.</param>
/// <returns>true if item is successfully removed; otherwise, false. This method also returns false if item was not found in the DynamicArray.</returns>
public bool Remove(T item)
{
int index = IndexOf(item);
if (index != -1)
{
RemoveAt(index);
return true;
}
return false;
}
/// <summary>
/// Removes the element at the specified index of the DynamicArray.
/// </summary>
/// <param name="index">The zero-based index of the element to remove.</param>
public void RemoveAt(int index)
{
#if DEVELOPMENT_BUILD || UNITY_EDITOR
if (index < 0 || index >= size)
throw new IndexOutOfRangeException();
#endif
if (index != size - 1)
Array.Copy(m_Array, index + 1, m_Array, index, size - index - 1);
size--;
BumpVersion();
}
/// <summary>
/// Removes a range of elements from the DynamicArray.
/// </summary>
/// <param name="index">The zero-based starting index of the range of elements to remove.</param>
/// <param name="count">The number of elements to remove.</param>
public void RemoveRange(int index, int count)
{
if (count == 0)
return;
#if DEVELOPMENT_BUILD || UNITY_EDITOR
if (index < 0 || index >= size || count < 0 || index + count > size)
throw new ArgumentOutOfRangeException();
#endif
Array.Copy(m_Array, index + count, m_Array, index, size - index - count);
size -= count;
BumpVersion();
}
/// <summary>
/// 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.
/// </summary>
/// <param name="startIndex">The zero-based starting index of the search.</param>
/// <param name="count">The number of elements in the section to search.</param>
/// <param name="match">The Predicate delegate that defines the conditions of the element to search for.</param>
/// <returns>The zero-based index of the first occurrence of an element that matches the conditions defined by match, if found; otherwise, -1.</returns>
public int FindIndex(int startIndex, int count, Predicate<T> match)
{
for (int i = startIndex; i < size && count > 0; ++i, --count)
{
if (match(m_Array[i]))
{
return i;
}
}
return -1;
}
/// <summary>
/// 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.
/// </summary>
/// <param name="match">The Predicate delegate that defines the conditions of the element to search for.</param>
/// <returns>The zero-based index of the first occurrence of an element that matches the conditions defined by match, if found; otherwise, -1.</returns>
public int FindIndex(Predicate<T> match)
{
return FindIndex(0, size, match);
}
/// <summary>
/// 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.
/// </summary>
/// <param name="item">The object to locate in the DynamicArray. The value can be null for reference types.</param>
/// <param name="index">The zero-based starting index of the search. 0 (zero) is valid in an empty list.</param>
/// <param name="count">The number of elements in the section to search.</param>
/// <returns>The index of the first occurrence of the object within the range of elements, or -1 if not found.</returns>
public int IndexOf(T item, int index, int count)
{
for (int i = index; i < size && count > 0; ++i, --count)
{
if (m_Array[i].Equals(item))
{
return i;
}
}
return -1;
}
/// <summary>
/// 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.
/// </summary>
/// <param name="item">The object to locate in the DynamicArray. The value can be null for reference types.</param>
/// <param name="index">The zero-based starting index of the search. 0 (zero) is valid in an empty list.</param>
/// <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>
public int IndexOf(T item, int index)
{
for (int i = index; i < size; ++i)
{
if (m_Array[i].Equals(item))
{
return i;
}
}
return -1;
}
/// <summary>
/// Searches for the specified object and returns the zero-based index of the first occurrence within the entire DynamicArray.
/// </summary>
/// <param name="item">The object to locate in the DynamicArray. The value can be null for reference types.</param>
/// <returns>he zero-based index of the first occurrence of item within the entire DynamicArray, if found; otherwise, -1.</returns>
public int IndexOf(T item)
{
return IndexOf(item, 0);
}
/// <summary>
/// Resize the Dynamic Array.
/// This will reallocate memory if necessary and set the current size of the array to the provided size.
/// Note: The memory is not cleared so the elements may contain invalid data.
/// </summary>
/// <param name="newSize">New size for the array.</param>
/// <param name="keepContent">Set to true if you want the current content of the array to be kept.</param>
public void Resize(int newSize, bool keepContent = false)
{
Reserve(newSize, keepContent);
size = newSize;
BumpVersion();
}
/// <summary>
/// Resize the Dynamic Array.
/// This will reallocate memory if necessary and set the current size of the array to the provided size.
/// The elements are initialized to the default value of the element type, e.g. 0 for integers.
/// </summary>
/// <param name="newSize">New size for the array.</param>
public void ResizeAndClear(int newSize)
{
if (newSize > m_Array.Length)
{
// Reserve will allocate a whole new array that is cleared as part of the allocation
Reserve(newSize, false);
}
else
{
// We're not reallocating anything we need to clear the old values to the default.
Array.Clear(m_Array, 0, newSize);
}
size = newSize;
BumpVersion();
}
/// <summary>
/// Sets the total number of elements the internal data structure can hold without resizing.
/// </summary>
/// <param name="newCapacity">New capacity for the array.</param>
/// <param name="keepContent">Set to true if you want the current content of the array to be kept.</param>
public void Reserve(int newCapacity, bool keepContent = false)
{
if (newCapacity > m_Array.Length)
{
if (keepContent)
{
var newArray = new T[newCapacity];
Array.Copy(m_Array, newArray, m_Array.Length);
m_Array = newArray;
}
else
{
m_Array = new T[newCapacity];
}
}
}
/// <summary>
/// ref access to an element.
/// </summary>
/// <param name="index">Element index</param>
/// <value>The requested element.</value>
public ref T this[int index]
{
get
{
#if DEVELOPMENT_BUILD || UNITY_EDITOR
if (index < 0 || index >= size)
throw new IndexOutOfRangeException();
#endif
return ref m_Array[index];
}
}
/// <summary>
/// Implicit conversion to regular array.
/// </summary>
/// <param name="array">Input DynamicArray.</param>
/// <returns>The internal array.</returns>
[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. #from(2023.2)")]
public static implicit operator T[](DynamicArray<T> array) => array.m_Array;
/// <summary>
/// Implicit conversion to ReadOnlySpan.
/// </summary>
/// <param name="array">Input DynamicArray.</param>
/// <returns>The internal array.</returns>
public static implicit operator ReadOnlySpan<T>(DynamicArray<T> array) => new ReadOnlySpan<T>(array.m_Array, 0, array.size);
/// <summary>
/// Implicit conversion to Span.
/// </summary>
/// <param name="array">Input DynamicArray.</param>
/// <returns>The internal array.</returns>
public static implicit operator Span<T>(DynamicArray<T> array) => new Span<T>(array.m_Array, 0, array.size);
/// <summary>
/// IEnumerator-like struct used to loop over this entire array. See the IEnumerator docs for more info:
/// <a href="https://docs.microsoft.com/en-us/dotnet/api/system.collections.ienumerator">IEnumerator</a>
/// </summary>
/// <remarks>
/// This struct intentionally does not explicitly implement the IEnumarable/IEnumerator interfaces it just follows
/// the same function signatures. This means the duck typing used by <c>foreach</c> on the compiler level will
/// pick it up as IEnumerable but at the same time avoids generating Garbage.
/// For more info, see the C# language specification of the <c>foreach</c> statement.
/// </remarks>
/// <seealso cref="RangeIterator"/>
public struct Iterator
{
private readonly DynamicArray<T> owner;
private int index;
#if DEVELOPMENT_BUILD || UNITY_EDITOR
private int localVersion;
#endif
/// <summary>
/// Creates an iterator to iterate over an array.
/// </summary>
/// <param name="setOwner">The array to iterate over.</param>
/// <exception cref="ArgumentNullException">Thrown if the array is null.</exception>
public Iterator(DynamicArray<T> setOwner)
{
#if DEVELOPMENT_BUILD || UNITY_EDITOR
if (setOwner == null)
throw new ArgumentNullException();
#endif
owner = setOwner;
index = -1;
#if DEVELOPMENT_BUILD || UNITY_EDITOR
localVersion = owner.version;
#endif
}
/// <summary>
/// Gets the element in the DynamicArray at the current position of the iterator.
/// </summary>
public ref T Current
{
get
{
return ref owner[index];
}
}
/// <summary>
/// Advances the iterator to the next element of the DynamicArray.
/// </summary>
/// <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>
/// <exception cref="InvalidOperationException">An operation changed the DynamicArray after the creation of this iterator.</exception>
public bool MoveNext()
{
#if DEVELOPMENT_BUILD || UNITY_EDITOR
if (owner.version != localVersion)
{
throw new InvalidOperationException("DynamicArray was modified during enumeration");
}
#endif
index++;
return index < owner.size;
}
/// <summary>
/// Sets the iterator to its initial position, which is before the first element in the DynamicArray.
/// </summary>
public void Reset()
{
index = -1;
}
}
/// <summary>
/// Returns an enumerator that iterates through of this array.
/// See the IEnumerable docs for more info: <a href="https://docs.microsoft.com/en-us/dotnet/api/system.collections.ienumerable" >IEnumerable</a>
/// </summary>
/// <remarks>
/// The returned struct intentionally does not explicitly implement the IEnumarable/IEnumerator interfaces it just follows
/// the same function signatures. This means the duck typing used by <c>foreach</c> on the compiler level will
/// pick it up as IEnumerable but at the same time avoids generating Garbage.
/// For more info, see the C# language specification of the <c>foreach</c> statement.
/// </remarks>
/// <returns>Iterator pointing before the first element in the array.</returns>
public Iterator GetEnumerator()
{
return new Iterator(this);
}
/// <summary>
/// IEnumerable-like struct used to iterate through a subsection of this array.
/// See the IEnumerable docs for more info: <a href="https://docs.microsoft.com/en-us/dotnet/api/system.collections.ienumerable">IEnumerable</a>
/// </summary>
/// <remarks>
/// This struct intentionally does not explicitly implement the IEnumarable/IEnumerator interfaces it just follows
/// the same function signatures. This means the duck typing used by <c>foreach</c> on the compiler level will
/// pick it up as IEnumerable but at the same time avoids generating Garbage.
/// For more info, see the C# language specification of the <c>foreach</c> statement.
/// </remarks>
/// <seealso cref="SubRange"/>
public struct RangeEnumerable
{
/// <summary>
/// IEnumerator-like struct used to iterate through a subsection of this array.
/// See the IEnumerator docs for more info: <a href="https://docs.microsoft.com/en-us/dotnet/api/system.collections.ienumerator">IEnumerator</a>
/// </summary>
/// <remarks>
/// This struct intentionally does not explicitly implement the IEnumarable/IEnumerator interfaces it just follows
/// the same function signatures. This means the duck typing used by <c>foreach</c> on the compiler level will
/// pick it up as <c>IEnumarable</c> but at the same time avoids generating Garbage.
/// For more info, see the C# language specification of the <c>foreach</c> statement.
/// </remarks>
/// <seealso cref="SubRange"/>
public struct RangeIterator
{
private readonly DynamicArray<T> owner;
private int index;
private int first;
private int last;
#if DEVELOPMENT_BUILD || UNITY_EDITOR
private int localVersion;
#endif
/// <summary>
/// Create an iterator to iterate over the given range in the array.
/// </summary>
/// <param name="setOwner">The array to iterate over.</param>
/// <param name="first">The index of the first item in the array.</param>
/// <param name="numItems">The number of array members to iterate through.</param>
/// <exception cref="ArgumentNullException">Thrown if the array is null.</exception>
public RangeIterator(DynamicArray<T> setOwner, int first, int numItems)
{
#if DEVELOPMENT_BUILD || UNITY_EDITOR
if (setOwner == null)
throw new ArgumentNullException();
if (first < 0 || first > setOwner.size || (first + numItems) > setOwner.size)
throw new IndexOutOfRangeException();
#endif
owner = setOwner;
this.first = first;
index = first-1;
last = first + numItems;
#if DEVELOPMENT_BUILD || UNITY_EDITOR
localVersion = owner.version;
#endif
}
/// <summary>
/// Gets the element in the DynamicArray at the current position of the iterator.
/// </summary>
public ref T Current
{
get
{
return ref owner[index];
}
}
/// <summary>
/// Advances the iterator to the next element of the DynamicArray.
/// </summary>
/// <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>
/// <exception cref="InvalidOperationException">The DynamicArray was modified after the iterator was created.</exception>
public bool MoveNext()
{
#if DEVELOPMENT_BUILD || UNITY_EDITOR
if (owner.version != localVersion)
{
throw new InvalidOperationException("DynamicArray was modified during enumeration");
}
#endif
index++;
return index < last;
}
/// <summary>
/// Sets the iterator to its initial position, which is before the first element in the range.
/// </summary>
public void Reset()
{
index = first-1;
}
}
/// <summary>
/// The iterator associated with this Enumerable.
/// </summary>
public RangeIterator iterator;
/// <summary>
/// Returns an enumerator that iterates through this array.
/// </summary>
/// <remarks>
/// The returned struct intentionally does not explicitly implement the IEnumarable/IEnumerator interfaces it just follows
/// the same function signatures. This means the duck typing used by <c>foreach</c> on the compiler level will
/// pick it up as IEnumerable but at the same time avoids generating Garbage.
/// For more info, see the C# language specification of the <c>foreach</c> statement.
/// </remarks>
/// <returns>Iterator pointing before the first element in the range.</returns>
public RangeIterator GetEnumerator()
{
return iterator;
}
}
/// <summary>
/// Returns an IEnumeralbe-Like object that iterates through a subsection of this array.
/// </summary>
/// <remarks>
/// The returned struct intentionally does not explicitly implement the IEnumarable/IEnumerator interfaces it just follows
/// the same function signatures. This means the duck typing used by <c>foreach</c> on the compiler level will
/// pick it up as IEnumerable but at the same time avoids generating Garbage.
/// For more info, see the C# language specification of the <c>foreach</c> statement.
/// </remarks>
/// <param name="first">The index of the first item</param>
/// <param name="numItems">The number of items to iterate</param>
/// <returns><c>RangeEnumerable</c> that can be used to enumerate the given range.</returns>
/// <seealso cref="RangeIterator"/>
public RangeEnumerable SubRange(int first, int numItems)
{
RangeEnumerable r = new RangeEnumerable { iterator = new RangeEnumerable.RangeIterator(this, first, numItems) };
return r;
}
/// <summary>
/// Increments the internal version counter.
/// </summary>
protected internal void BumpVersion()
{
#if DEVELOPMENT_BUILD || UNITY_EDITOR
version++;
#endif
}
/// <summary>
/// Delegate for custom sorting comparison.
/// </summary>
/// <param name="x">First object.</param>
/// <param name="y">Second object.</param>
/// <returns>-1 if x smaller than y, 1 if x bigger than y and 0 otherwise.</returns>
public delegate int SortComparer(T x, T y);
}
/// <summary>
/// Extension class for DynamicArray
/// </summary>
public static class DynamicArrayExtensions
{
static int Partition<T>(Span<T> data, int left, int right) where T : IComparable<T>, new()
{
var pivot = data[left];
--left;
++right;
while (true)
{
var c = 0;
var lvalue = default(T);
do
{
++left;
lvalue = data[left];
c = lvalue.CompareTo(pivot);
}
while (c < 0);
var rvalue = default(T);
do
{
--right;
rvalue = data[right];
c = rvalue.CompareTo(pivot);
}
while (c > 0);
if (left < right)
{
data[right] = lvalue;
data[left] = rvalue;
}
else
{
return right;
}
}
}
static void QuickSort<T>(Span<T> data, int left, int right) where T : IComparable<T>, new()
{
if (left < right)
{
int pivot = Partition(data, left, right);
if (pivot >= 1)
QuickSort(data, left, pivot);
if (pivot + 1 < right)
QuickSort(data, pivot + 1, right);
}
}
// A copy/paste because it's apparently impossible to pass a sort delegate where T is Comparable<T>, otherwise some boxing happens and allocates...
// So two identical versions of the function, one with delegate but no Comparable and the other with just the comparable.
static int Partition<T>(Span<T> data, int left, int right, DynamicArray<T>.SortComparer comparer) where T : new()
{
var pivot = data[left];
--left;
++right;
while (true)
{
var c = 0;
var lvalue = default(T);
do
{
++left;
lvalue = data[left];
c = comparer(lvalue, pivot);
}
while (c < 0);
var rvalue = default(T);
do
{
--right;
rvalue = data[right];
c = comparer(rvalue, pivot);
}
while (c > 0);
if (left < right)
{
data[right] = lvalue;
data[left] = rvalue;
}
else
{
return right;
}
}
}
static void QuickSort<T>(Span<T> data, int left, int right, DynamicArray<T>.SortComparer comparer) where T : new()
{
if (left < right)
{
int pivot = Partition(data, left, right, comparer);
if (pivot >= 1)
QuickSort(data, left, pivot, comparer);
if (pivot + 1 < right)
QuickSort(data, pivot + 1, right, comparer);
}
}
/// <summary>
/// Perform a quick sort on the DynamicArray
/// </summary>
/// <typeparam name="T">Type of the array.</typeparam>
/// <param name="array">Array on which to perform the quick sort.</param>
public static void QuickSort<T>(this DynamicArray<T> array) where T : IComparable<T>, new()
{
QuickSort<T>(array, 0, array.size - 1);
array.BumpVersion();
}
/// <summary>
/// Perform a quick sort on the DynamicArray
/// </summary>
/// <typeparam name="T">Type of the array.</typeparam>
/// <param name="array">Array on which to perform the quick sort.</param>
/// <param name="comparer">Comparer used for sorting.</param>
public static void QuickSort<T>(this DynamicArray<T> array, DynamicArray<T>.SortComparer comparer) where T : new()
{
QuickSort<T>(array, 0, array.size - 1, comparer);
array.BumpVersion();
}
}
}