AloneGame / Library / PackageCache / com.unity.inputsystem / InputSystem / Utilities / ArrayHelpers.cs

using System;
using System.Collections.Generic;
using System.Linq;
using Unity.Collections;
using Unity.Collections.LowLevel.Unsafe;

namespace UnityEngine.InputSystem.Utilities
{
    /// <summary>
    /// A collection of utility functions for working with arrays.
    /// </summary>
    /// <remarks>
    /// The goal of this collection is to make it easy to use arrays directly rather than resorting to
    /// <see cref="List{T}"/>.
    /// </remarks>
    internal static class ArrayHelpers
    {
        public static int LengthSafe<TValue>(this TValue[] array)
        {
            if (array == null)
                return 0;
            return array.Length;
        }

        public static void Clear<TValue>(this TValue[] array)
        {
            if (array == null)
                return;

            Array.Clear(array, 0, array.Length);
        }

        public static void Clear<TValue>(this TValue[] array, int count)
        {
            if (array == null)
                return;
            Array.Clear(array, 0, count);
        }

        public static void Clear<TValue>(this TValue[] array, ref int count)
        {
            if (array == null)
                return;

            Array.Clear(array, 0, count);
            count = 0;
        }

        public static void EnsureCapacity<TValue>(ref TValue[] array, int count, int capacity, int capacityIncrement = 10)
        {
            if (capacity == 0)
                return;

            if (array == null)
            {
                array = new TValue[Math.Max(capacity, capacityIncrement)];
                return;
            }

            var currentCapacity = array.Length - count;
            if (currentCapacity >= capacity)
                return;

            DuplicateWithCapacity(ref array, count, capacity, capacityIncrement);
        }

        public static void DuplicateWithCapacity<TValue>(ref TValue[] array, int count, int capacity, int capacityIncrement = 10)
        {
            if (array == null)
            {
                array = new TValue[Math.Max(capacity, capacityIncrement)];
                return;
            }

            var newSize = count + Math.Max(capacity, capacityIncrement);
            var newArray = new TValue[newSize];
            Array.Copy(array, newArray, count);
            array = newArray;
        }

        public static bool Contains<TValue>(TValue[] array, TValue value)
        {
            if (array == null)
                return false;

            var comparer = EqualityComparer<TValue>.Default;
            for (var i = 0; i < array.Length; ++i)
                if (comparer.Equals(array[i], value))
                    return true;

            return false;
        }

        public static bool ContainsReference<TValue>(this TValue[] array, TValue value)
            where TValue : class
        {
            if (array == null)
                return false;

            return ContainsReference(array, array.Length, value);
        }

        public static bool ContainsReference<TFirst, TSecond>(this TFirst[] array, int count, TSecond value)
            where TSecond : class
            where TFirst : TSecond
        {
            return IndexOfReference(array, value, count) != -1;
        }

        public static bool ContainsReference<TFirst, TSecond>(this TFirst[] array, int startIndex, int count, TSecond value)
            where TSecond : class
            where TFirst : TSecond
        {
            return IndexOfReference(array, value, startIndex, count) != -1;
        }

        [System.Diagnostics.CodeAnalysis.SuppressMessage("Microsoft.Usage", "CA1801:ReviewUnusedParameters", MessageId = "index", Justification = "Keep this for future implementation")]
        public static bool HaveDuplicateReferences<TFirst>(this TFirst[] first, int index, int count)
        {
            for (var i = 0; i < count; ++i)
            {
                var element = first[i];
                for (var n = i + 1; n < count - i; ++n)
                {
                    if (ReferenceEquals(element, first[n]))
                        return true;
                }
            }
            return false;
        }

        public static bool HaveEqualElements<TValue>(TValue[] first, TValue[] second, int count = int.MaxValue)
        {
            if (first == null || second == null)
                return second == first;

            var lengthFirst = Math.Min(count, first.Length);
            var lengthSecond = Math.Min(count, second.Length);

            if (lengthFirst != lengthSecond)
                return false;

            var comparer = EqualityComparer<TValue>.Default;
            for (var i = 0; i < lengthFirst; ++i)
                if (!comparer.Equals(first[i], second[i]))
                    return false;

            return true;
        }

        ////REVIEW: remove this to get rid of default equality comparer?
        public static int IndexOf<TValue>(TValue[] array, TValue value, int startIndex = 0, int count = -1)
        {
            if (array == null)
                return -1;

            if (count < 0)
                count = array.Length - startIndex;
            var comparer = EqualityComparer<TValue>.Default;
            for (var i = startIndex; i < startIndex + count; ++i)
                if (comparer.Equals(array[i], value))
                    return i;

            return -1;
        }

        public static int IndexOf<TValue>(this TValue[] array, Predicate<TValue> predicate)
        {
            if (array == null)
                return -1;

            var length = array.Length;
            for (var i = 0; i < length; ++i)
                if (predicate(array[i]))
                    return i;

            return -1;
        }

        public static int IndexOf<TValue>(this TValue[] array, Predicate<TValue> predicate, int startIndex = 0, int count = -1)
        {
            if (array == null)
                return -1;

            var end = startIndex + (count < 0 ? array.Length - startIndex : count);
            for (var i = startIndex; i < end; ++i)
            {
                if (predicate(array[i]))
                    return i;
            }

            return -1;
        }

        public static int IndexOfReference<TFirst, TSecond>(this TFirst[] array, TSecond value, int count = -1)
            where TSecond : class
            where TFirst : TSecond
        {
            return IndexOfReference(array, value, 0, count);
        }

        public static int IndexOfReference<TFirst, TSecond>(this TFirst[] array, TSecond value, int startIndex, int count)
            where TSecond : class
            where TFirst : TSecond
        {
            if (array == null)
                return -1;

            if (count < 0)
                count = array.Length - startIndex;
            for (var i = startIndex; i < startIndex + count; ++i)
                if (ReferenceEquals(array[i], value))
                    return i;

            return -1;
        }

        public static int IndexOfValue<TValue>(this TValue[] array, TValue value, int startIndex = 0, int count = -1)
            where TValue : struct, IEquatable<TValue>
        {
            if (array == null)
                return -1;

            if (count < 0)
                count = array.Length - startIndex;
            for (var i = startIndex; i < startIndex + count; ++i)
                if (value.Equals(array[i]))
                    return i;

            return -1;
        }

        public static unsafe void Resize<TValue>(ref NativeArray<TValue> array, int newSize, Allocator allocator)
            where TValue : struct
        {
            var oldSize = array.Length;
            if (oldSize == newSize)
                return;

            if (newSize == 0)
            {
                if (array.IsCreated)
                    array.Dispose();
                array = new NativeArray<TValue>();
                return;
            }

            var newArray = new NativeArray<TValue>(newSize, allocator);
            if (oldSize != 0)
            {
                // Copy contents from old array.
                UnsafeUtility.MemCpy(newArray.GetUnsafePtr(), array.GetUnsafeReadOnlyPtr(),
                    UnsafeUtility.SizeOf<TValue>() * (newSize < oldSize ? newSize : oldSize));
                array.Dispose();
            }
            array = newArray;
        }

        public static int Append<TValue>(ref TValue[] array, TValue value)
        {
            if (array == null)
            {
                array = new TValue[1];
                array[0] = value;
                return 0;
            }

            var length = array.Length;
            Array.Resize(ref array, length + 1);
            array[length] = value;
            return length;
        }

        public static int Append<TValue>(ref TValue[] array, IEnumerable<TValue> values)
        {
            if (array == null)
            {
                array = values.ToArray();
                return 0;
            }

            var oldLength = array.Length;
            var valueCount = values.Count();

            Array.Resize(ref array, oldLength + valueCount);

            var index = oldLength;
            foreach (var value in values)
                array[index++] = value;

            return oldLength;
        }

        // Append to an array that is considered immutable. This allows using 'values' as is
        // if 'array' is null.
        // Returns the index of the first newly added element in the resulting array.
        public static int AppendToImmutable<TValue>(ref TValue[] array, TValue[] values)
        {
            if (array == null)
            {
                array = values;
                return 0;
            }

            if (values != null && values.Length > 0)
            {
                var oldCount = array.Length;
                var valueCount = values.Length;
                Array.Resize(ref array, oldCount + valueCount);
                Array.Copy(values, 0, array, oldCount, valueCount);
                return oldCount;
            }

            return array.Length;
        }

        public static int AppendWithCapacity<TValue>(ref TValue[] array, ref int count, TValue value, int capacityIncrement = 10)
        {
            if (array == null)
            {
                array = new TValue[capacityIncrement];
                array[0] = value;
                ++count;
                return 0;
            }

            var capacity = array.Length;
            if (capacity == count)
            {
                capacity += capacityIncrement;
                Array.Resize(ref array, capacity);
            }

            var index = count;
            array[index] = value;
            ++count;

            return index;
        }

        public static int AppendListWithCapacity<TValue, TValues>(ref TValue[] array, ref int length, TValues values, int capacityIncrement = 10)
            where TValues : IReadOnlyList<TValue>
        {
            var numToAdd = values.Count;
            if (array == null)
            {
                var size = Math.Max(numToAdd, capacityIncrement);
                array = new TValue[size];
                for (var i = 0; i < numToAdd; ++i)
                    array[i] = values[i];
                length += numToAdd;
                return 0;
            }

            var capacity = array.Length;
            if (capacity < length + numToAdd)
            {
                capacity += Math.Max(length + numToAdd, capacityIncrement);
                Array.Resize(ref array, capacity);
            }

            var index = length;
            for (var i = 0; i < numToAdd; ++i)
                array[index + i] = values[i];
            length += numToAdd;

            return index;
        }

        public static int AppendWithCapacity<TValue>(ref NativeArray<TValue> array, ref int count, TValue value,
            int capacityIncrement = 10, Allocator allocator = Allocator.Persistent)
            where TValue : struct
        {
            var capacity = array.Length;
            if (capacity == count)
                GrowBy(ref array, capacityIncrement > 1 ? capacityIncrement : 1, allocator);

            var index = count;
            array[index] = value;
            ++count;

            return index;
        }

        public static void InsertAt<TValue>(ref TValue[] array, int index, TValue value)
        {
            if (array == null)
            {
                ////REVIEW: allow growing array to specific size by inserting at arbitrary index?
                if (index != 0)
                    throw new ArgumentOutOfRangeException(nameof(index));

                array = new TValue[1];
                array[0] = value;
                return;
            }

            // Reallocate.
            var oldLength = array.Length;
            Array.Resize(ref array, oldLength + 1);

            // Make room for element.
            if (index != oldLength)
                Array.Copy(array, index, array, index + 1, oldLength - index);

            array[index] = value;
        }

        public static void InsertAtWithCapacity<TValue>(ref TValue[] array, ref int count, int index, TValue value, int capacityIncrement = 10)
        {
            EnsureCapacity(ref array, count, count + 1, capacityIncrement);

            if (index != count)
                Array.Copy(array, index, array, index + 1, count - index);

            array[index] = value;
            ++count;
        }

        public static void PutAtIfNotSet<TValue>(ref TValue[] array, int index, Func<TValue> valueFn)
        {
            if (array.LengthSafe() < index + 1)
                Array.Resize(ref array, index + 1);

            if (EqualityComparer<TValue>.Default.Equals(array[index], default(TValue)))
                array[index] = valueFn();
        }

        // Adds 'count' entries to the array. Returns first index of newly added entries.
        public static int GrowBy<TValue>(ref TValue[] array, int count)
        {
            if (array == null)
            {
                array = new TValue[count];
                return 0;
            }

            var oldLength = array.Length;
            Array.Resize(ref array, oldLength + count);
            return oldLength;
        }

        public static unsafe int GrowBy<TValue>(ref NativeArray<TValue> array, int count, Allocator allocator = Allocator.Persistent)
            where TValue : struct
        {
            var length = array.Length;
            if (length == 0)
            {
                array = new NativeArray<TValue>(count, allocator);
                return 0;
            }

            var newArray = new NativeArray<TValue>(length + count, allocator);
            // CopyFrom() expects length to match. Copy manually.
            UnsafeUtility.MemCpy(newArray.GetUnsafePtr(), array.GetUnsafeReadOnlyPtr(), (long)length * UnsafeUtility.SizeOf<TValue>());
            array.Dispose();
            array = newArray;

            return length;
        }

        public static int GrowWithCapacity<TValue>(ref TValue[] array, ref int count, int growBy, int capacityIncrement = 10)
        {
            var length = array != null ? array.Length : 0;
            if (length < count + growBy)
            {
                if (capacityIncrement < growBy)
                    capacityIncrement = growBy;
                GrowBy(ref array, capacityIncrement);
            }

            var offset = count;
            count += growBy;
            return offset;
        }

        public static int GrowWithCapacity<TValue>(ref NativeArray<TValue> array, ref int count, int growBy,
            int capacityIncrement = 10, Allocator allocator = Allocator.Persistent)
            where TValue : struct
        {
            var length = array.Length;
            if (length < count + growBy)
            {
                if (capacityIncrement < growBy)
                    capacityIncrement = growBy;
                GrowBy(ref array, capacityIncrement, allocator);
            }

            var offset = count;
            count += growBy;
            return offset;
        }

        public static TValue[] Join<TValue>(TValue value, params TValue[] values)
        {
            // Determine length.
            var length = 0;
            if (value != null)
                ++length;
            if (values != null)
                length += values.Length;

            if (length == 0)
                return null;

            var array = new TValue[length];

            // Populate.
            var index = 0;
            if (value != null)
                array[index++] = value;

            if (values != null)
                Array.Copy(values, 0, array, index, values.Length);

            return array;
        }

        public static TValue[] Merge<TValue>(TValue[] first, TValue[] second)
            where TValue : IEquatable<TValue>
        {
            if (first == null)
                return second;
            if (second == null)
                return first;

            var merged = new List<TValue>();
            merged.AddRange(first);

            for (var i = 0; i < second.Length; ++i)
            {
                var secondValue = second[i];
                if (!merged.Exists(x => x.Equals(secondValue)))
                {
                    merged.Add(secondValue);
                }
            }

            return merged.ToArray();
        }

        public static TValue[] Merge<TValue>(TValue[] first, TValue[] second, IEqualityComparer<TValue> comparer)
        {
            if (first == null)
                return second;
            if (second == null)
                return null;

            var merged = new List<TValue>();
            merged.AddRange(first);

            for (var i = 0; i < second.Length; ++i)
            {
                var secondValue = second[i];
                if (!merged.Exists(x => comparer.Equals(secondValue)))
                {
                    merged.Add(secondValue);
                }
            }

            return merged.ToArray();
        }

        public static void EraseAt<TValue>(ref TValue[] array, int index)
        {
            Debug.Assert(array != null);
            Debug.Assert(index >= 0 && index < array.Length);

            var length = array.Length;
            if (index == 0 && length == 1)
            {
                array = null;
                return;
            }

            if (index < length - 1)
                Array.Copy(array, index + 1, array, index, length - index - 1);

            Array.Resize(ref array, length - 1);
        }

        public static void EraseAtWithCapacity<TValue>(this TValue[] array, ref int count, int index)
        {
            Debug.Assert(array != null);
            Debug.Assert(count <= array.Length);
            Debug.Assert(index >= 0 && index < count);

            // If we're erasing from the beginning or somewhere in the middle, move
            // the array contents down from after the index.
            if (index < count - 1)
            {
                Array.Copy(array, index + 1, array, index, count - index - 1);
            }

            array[count - 1] = default; // Tail has been moved down by one.
            --count;
        }

        public static unsafe void EraseAtWithCapacity<TValue>(NativeArray<TValue> array, ref int count, int index)
            where TValue : struct
        {
            Debug.Assert(array.IsCreated);
            Debug.Assert(count <= array.Length);
            Debug.Assert(index >= 0 && index < count);

            // If we're erasing from the beginning or somewhere in the middle, move
            // the array contents down from after the index.
            if (index < count - 1)
            {
                var elementSize = UnsafeUtility.SizeOf<TValue>();
                var arrayPtr = (byte*)array.GetUnsafePtr();

                UnsafeUtility.MemCpy(arrayPtr + elementSize * index, arrayPtr + elementSize * (index + 1),
                    (count - index - 1) * elementSize);
            }

            --count;
        }

        public static bool Erase<TValue>(ref TValue[] array, TValue value)
        {
            var index = IndexOf(array, value);
            if (index != -1)
            {
                EraseAt(ref array, index);
                return true;
            }
            return false;
        }

        /// <summary>
        /// Erase an element from the array by moving the tail element into its place.
        /// </summary>
        /// <param name="array">Array to modify. May be not <c>null</c>.</param>
        /// <param name="count">Current number of elements inside of array. May be less than <c>array.Length</c>.</param>
        /// <param name="index">Index of element to remove. Tail element will get moved into its place.</param>
        /// <typeparam name="TValue"></typeparam>
        /// <remarks>
        /// This method does not re-allocate the array. Instead <paramref name="count"/> is used
        /// to keep track of how many elements there actually are in the array.
        /// </remarks>
        public static void EraseAtByMovingTail<TValue>(TValue[] array, ref int count, int index)
        {
            Debug.Assert(array != null);
            Debug.Assert(index >= 0 && index < array.Length);
            Debug.Assert(count >= 0 && count <= array.Length);
            Debug.Assert(index < count);

            // Move tail, if necessary.
            if (index != count - 1)
                array[index] = array[count - 1];

            // Destroy current tail.
            if (count >= 1)
                array[count - 1] = default;
            --count;
        }

        public static TValue[] Copy<TValue>(TValue[] array)
        {
            if (array == null)
                return null;

            var length = array.Length;
            var result = new TValue[length];
            Array.Copy(array, result, length);
            return result;
        }

        public static TValue[] Clone<TValue>(TValue[] array)
            where TValue : ICloneable
        {
            if (array == null)
                return null;

            var count = array.Length;
            var result = new TValue[count];

            for (var i = 0; i < count; ++i)
                result[i] = (TValue)array[i].Clone();

            return result;
        }

        public static TNew[] Select<TOld, TNew>(TOld[] array, Func<TOld, TNew> converter)
        {
            if (array == null)
                return null;

            var length = array.Length;
            var result = new TNew[length];

            for (var i = 0; i < length; ++i)
                result[i] = converter(array[i]);

            return result;
        }

        private static void Swap<TValue>(ref TValue first, ref TValue second)
        {
            var temp = first;
            first = second;
            second = temp;
        }

        /// <summary>
        /// Move a slice in the array to a different place without allocating a temporary array.
        /// </summary>
        /// <param name="array"></param>
        /// <param name="sourceIndex"></param>
        /// <param name="destinationIndex"></param>
        /// <param name="count"></param>
        /// <typeparam name="TValue"></typeparam>
        /// <remarks>
        /// The slice is moved by repeatedly swapping slices until all the slices are where they
        /// are supposed to go. This is not super efficient but avoids having to allocate a temporary
        /// array on the heap.
        /// </remarks>
        public static void MoveSlice<TValue>(TValue[] array, int sourceIndex, int destinationIndex, int count)
        {
            if (count <= 0 || sourceIndex == destinationIndex)
                return;

            // Determine the number of elements in the window.
            int elementCount;
            if (destinationIndex > sourceIndex)
                elementCount = destinationIndex + count - sourceIndex;
            else
                elementCount = sourceIndex + count - destinationIndex;

            // If the source and target slice are right next to each other, just go
            // and swap out the elements in both slices.
            if (elementCount == count * 2)
            {
                for (var i = 0; i < count; ++i)
                    Swap(ref array[sourceIndex + i], ref array[destinationIndex + i]);
            }
            else
            {
                // There's elements in-between the two slices.
                //
                // The easiest way to picture this operation is as a rotation of the elements within
                // the window given by sourceIndex, destination, and count. Within that window, we are
                // simply treating it as a wrap-around buffer and then sliding the elements clockwise
                // or counter-clockwise (depending on whether we move up or down, respectively) through
                // the window.
                //
                // Unfortunately, we can't just memcopy the slices within that window as we have to
                // have a temporary copy in place in order to preserve element values. So instead, we
                // go and swap elements one by one, something that doesn't require anything other than
                // a single value temporary copy.

                // Determine the number of swaps we need to achieve the desired order. Swaps
                // operate in pairs so it's one less than the number of elements in the range.
                var swapCount = elementCount - 1;

                // We simply take sourceIndex as fixed and do all swaps from there until all
                // the elements in the window are in the right order. Each swap will put one
                // element in its final place.
                var dst = destinationIndex;
                for (var i = 0; i < swapCount; ++i)
                {
                    // Swap source into its destination place. This puts the current sourceIndex
                    // element in its final place.
                    Swap(ref array[dst], ref array[sourceIndex]);

                    // Find out where the element that we now swapped into sourceIndex should
                    // actually go.
                    if (destinationIndex > sourceIndex)
                    {
                        // Rotating clockwise.
                        dst -= count;
                        if (dst < sourceIndex)
                            dst = destinationIndex + count - Math.Abs(sourceIndex - dst); // Wrap around.
                    }
                    else
                    {
                        // Rotating counter-clockwise.
                        dst += count;
                        if (dst >= sourceIndex + count)
                            dst = destinationIndex + (dst - (sourceIndex + count)); // Wrap around.
                    }
                }
            }
        }

        public static void EraseSliceWithCapacity<TValue>(ref TValue[] array, ref int length, int index, int count)
        {
            // Move elements down.
            if (count < length)
                Array.Copy(array, index + count, array, index, length - index - count);

            // Erase now vacant slots.
            for (var i = 0; i < count; ++i)
                array[length - i - 1] = default;

            length -= count;
        }

        public static void SwapElements<TValue>(this TValue[] array, int index1, int index2)
        {
            MemoryHelpers.Swap(ref array[index1], ref array[index2]);
        }

        public static void SwapElements<TValue>(this NativeArray<TValue> array, int index1, int index2)
            where TValue : struct
        {
            var temp = array[index1];
            array[index1] = array[index2];
            array[index2] = temp;
        }
    }
}