CoreUnsafeUtils.cs

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

namespace UnityEngine.Rendering
{
    /// <summary>
    /// Static class with unsafe utility functions.
    /// </summary>
    public static unsafe class CoreUnsafeUtils
    {
        /// <summary>
        /// Fixed Buffer String Queue class.
        /// </summary>
        public struct FixedBufferStringQueue
        {
            byte* m_ReadCursor;
            byte* m_WriteCursor;

            readonly byte* m_BufferEnd;
            readonly byte* m_BufferStart;
            readonly int m_BufferLength;

            /// <summary>
            /// Number of element in the queue.
            /// </summary>
            public int Count { get; private set; }

            /// <summary>
            /// Constructor.
            /// </summary>
            /// <param name="ptr">Buffer pointer.</param>
            /// <param name="length">Length of the provided allocated buffer in byte.</param>
            public FixedBufferStringQueue(byte* ptr, int length)
            {
                m_BufferStart = ptr;
                m_BufferLength = length;

                m_BufferEnd = m_BufferStart + m_BufferLength;
                m_ReadCursor = m_BufferStart;
                m_WriteCursor = m_BufferStart;
                Count = 0;
                Clear();
            }

            /// <summary>
            /// Try to push a new element in the queue.
            /// </summary>
            /// <param name="v">Element to push in the queue.</param>
            /// <returns>True if the new element could be pushed in the queue. False if reserved memory was not enough.</returns>
            public bool TryPush(string v)
            {
                var size = v.Length * sizeof(char) + sizeof(int);
                if (m_WriteCursor + size >= m_BufferEnd)
                    return false;

                *(int*)m_WriteCursor = v.Length;
                m_WriteCursor += sizeof(int);

                var charPtr = (char*)m_WriteCursor;
                for (int i = 0; i < v.Length; ++i, ++charPtr)
                    *charPtr = v[i];

                m_WriteCursor += sizeof(char) * v.Length;
                ++Count;

                return true;
            }

            /// <summary>
            /// Try to pop an element of the queue.
            /// </summary>
            /// <param name="v">Output result string.</param>
            /// <returns>True if an element was successfully popped.</returns>
            public bool TryPop(out string v)
            {
                if (m_ReadCursor + sizeof(int) >= m_BufferEnd)
                {
                    v = null;
                    return false;
                }

                var size = *(int*)m_ReadCursor;
                if (size != 0)
                {
                    m_ReadCursor += sizeof(int);
                    v = new string((char*)m_ReadCursor, 0, size);
                    m_ReadCursor += size * sizeof(char);
                    return true;
                }

                v = null;
                return false;
            }

            /// <summary>
            /// Clear the queue.
            /// </summary>
            public void Clear()
            {
                m_WriteCursor = m_BufferStart;
                m_ReadCursor = m_BufferStart;
                Count = 0;
                UnsafeUtility.MemClear(m_BufferStart, m_BufferLength);
            }
        }

        /// <summary>
        /// Key Getter interface.
        /// </summary>
        /// <typeparam name="TValue">Value</typeparam>
        /// <typeparam name="TKey">Key</typeparam>
        public interface IKeyGetter<TValue, TKey>
        {
            /// <summary>Getter</summary>
            /// <param name="v">The value</param>
            /// <returns>The key</returns>
            TKey Get(ref TValue v);
        }

        internal struct DefaultKeyGetter<T> : IKeyGetter<T, T>
        { public T Get(ref T v) { return v; } }

        // Note: this is a workaround needed to circumvent some AOT issues when building for xbox
        internal struct UintKeyGetter : IKeyGetter<uint, uint>
        { public uint Get(ref uint v) { return v; } }
        internal struct UlongKeyGetter : IKeyGetter<ulong, ulong>
        { public ulong Get(ref ulong v) { return v; } }


        /// <summary>
        /// Extension method to copy elements of a list into a buffer.
        /// </summary>
        /// <typeparam name="T">Type of the provided List.</typeparam>
        /// <param name="list">Input List.</param>
        /// <param name="dest">Destination buffer.</param>
        /// <param name="count">Number of elements to copy.</param>
        public static void CopyTo<T>(this List<T> list, void* dest, int count)
            where T : struct
        {
            var c = Mathf.Min(count, list.Count);
            for (int i = 0; i < c; ++i)
                UnsafeUtility.WriteArrayElement<T>(dest, i, list[i]);
        }

        /// <summary>
        /// Extension method to copy elements of an array into a buffer.
        /// </summary>
        /// <typeparam name="T">Type of the provided array.</typeparam>
        /// <param name="list">Input List.</param>
        /// <param name="dest">Destination buffer.</param>
        /// <param name="count">Number of elements to copy.</param>
        public static void CopyTo<T>(this T[] list, void* dest, int count)
            where T : struct
        {
            var c = Mathf.Min(count, list.Length);
            for (int i = 0; i < c; ++i)
                UnsafeUtility.WriteArrayElement<T>(dest, i, list[i]);
        }

        private static void CalculateRadixParams(int radixBits, out int bitStates)
        {
#if DEVELOPMENT_BUILD || UNITY_EDITOR
            if (radixBits != 2 && radixBits != 4 && radixBits != 8)
                throw new Exception("Radix bits must be 2, 4 or 8 for uint radix sort.");
#endif
            bitStates = 1 << radixBits;
        }

        private static int CalculateRadixSupportSize(int bitStates, int arrayLength)
        {
            return bitStates * 3 + arrayLength;
        }

        private static unsafe void CalculateRadixSortSupportArrays(
            int bitStates, int arrayLength, uint* supportArray,
            out uint* bucketIndices, out uint* bucketSizes, out uint* bucketPrefix, out uint* arrayOutput)
        {
            bucketIndices = supportArray;
            bucketSizes = bucketIndices + bitStates;
            bucketPrefix = bucketSizes + bitStates;
            arrayOutput = bucketPrefix + bitStates;
        }

        private static unsafe void MergeSort(uint* array, uint* support, int length)
        {
            for (int k = 1; k < length; k *= 2)
            {
                for (int left = 0; left + k < length; left += k * 2)
                {
                    int right = left + k;
                    int rightend = right + k;
                    if (rightend > length)
                        rightend = length;
                    int m = left;
                    int i = left;
                    int j = right;
                    while (i < right && j < rightend)
                    {
                        if (array[i] <= array[j])
                        {
                            support[m] = array[i++];
                        }
                        else
                        {
                            support[m] = array[j++];
                        }
                        m++;
                    }
                    while (i < right)
                    {
                        support[m] = array[i++];
                        m++;
                    }
                    while (j < rightend)
                    {
                        support[m] = array[j++];
                        m++;
                    }
                    for (m = left; m < rightend; m++)
                    {
                        array[m] = support[m];
                    }
                }
            }
        }

        /// <summary>
        /// Merge sort - non recursive
        /// </summary>
        /// <param name="arr">Array to sort.</param>
        /// <param name="sortSize">Size of the array to sort. If greater than array capacity, it will get clamped.</param>
        /// <param name="supportArray">Secondary array reference, used to store intermediate merge results.</param>
        public static unsafe void MergeSort(uint[] arr, int sortSize, ref uint[] supportArray)
        {
            sortSize = Math.Min(sortSize, arr.Length);
            if (arr == null || sortSize == 0)
                return;

            if (supportArray == null || supportArray.Length < sortSize)
                supportArray = new uint[sortSize];

            fixed (uint* arrPtr = arr)
            fixed (uint* supportPtr = supportArray)
                CoreUnsafeUtils.MergeSort(arrPtr, supportPtr, sortSize);
        }

        /// <summary>
        /// Merge sort - non recursive
        /// </summary>
        /// <param name="arr">Array to sort.</param>
        /// <param name="sortSize">Size of the array to sort. If greater than array capacity, it will get clamped.</param>
        /// <param name="supportArray">Secondary array reference, used to store intermediate merge results.</param>
        public static unsafe void MergeSort(NativeArray<uint> arr, int sortSize, ref NativeArray<uint> supportArray)
        {
            sortSize = Math.Min(sortSize, arr.Length);
            if (!arr.IsCreated || sortSize == 0)
                return;

            if (!supportArray.IsCreated || supportArray.Length < sortSize)
                supportArray.ResizeArray(arr.Length);

            CoreUnsafeUtils.MergeSort((uint*)arr.GetUnsafePtr(), (uint*)supportArray.GetUnsafePtr(), sortSize);
        }

        private static unsafe void InsertionSort(uint* arr, int length)
        {
            for (int i = 0; i < length; ++i)
            {
                for (int j = i; j >= 1; --j)
                {
                    if (arr[j] >= arr[j - 1])
                        break;

                    var tmp = arr[j];
                    arr[j] = arr[j - 1];
                    arr[j - 1] = tmp;
                }
            }
        }

        /// <summary>
        /// Insertion sort
        /// </summary>
        /// <param name="arr">Array to sort.</param>
        /// <param name="sortSize">Size of the array to sort. If greater than array capacity, it will get clamped.</param>
        public static unsafe void InsertionSort(uint[] arr, int sortSize)
        {
            sortSize = Math.Min(arr.Length, sortSize);
            if (arr == null || sortSize == 0)
                return;

            fixed (uint* ptr = arr)
                CoreUnsafeUtils.InsertionSort(ptr, sortSize);
        }

        /// <summary>
        /// Insertion sort
        /// </summary>
        /// <param name="arr">Array to sort.</param>
        /// <param name="sortSize">Size of the array to sort. If greater than array capacity, it will get clamped.</param>
        public static unsafe void InsertionSort(NativeArray<uint> arr, int sortSize)
        {
            sortSize = Math.Min(arr.Length, sortSize);
            if (!arr.IsCreated || sortSize == 0)
                return;

            CoreUnsafeUtils.InsertionSort((uint*)arr.GetUnsafePtr(), sortSize);
        }

        private static unsafe void RadixSort(uint* array, uint* support, int radixBits, int bitStates, int length)
        {
            uint mask = (uint)(bitStates - 1);
            CalculateRadixSortSupportArrays(bitStates, length, support, out uint* bucketIndices, out uint* bucketSizes, out uint* bucketPrefix, out uint* arrayOutput);

            int buckets = (sizeof(uint) * 8) / radixBits;
            uint* targetBuffer = arrayOutput;
            uint* inputBuffer = array;
            for (int b = 0; b < buckets; ++b)
            {
                int shift = b * radixBits;
                for (int s = 0; s < 3 * bitStates; ++s)
                    bucketIndices[s] = 0;//bucketSizes and bucketPrefix get zeroed, since we walk 3x the bit states

                for (int i = 0; i < length; ++i)
                    bucketSizes[((inputBuffer[i] >> shift) & mask)]++;

                for (int s = 1; s < bitStates; ++s)
                    bucketPrefix[s] = bucketPrefix[s - 1] + bucketSizes[s - 1];

                for (int i = 0; i < length; ++i)
                {
                    uint val = inputBuffer[i];
                    uint bucket = (val >> shift) & mask;
                    targetBuffer[bucketPrefix[bucket] + bucketIndices[bucket]++] = val;
                }

                uint* tmp = inputBuffer;
                inputBuffer = targetBuffer;
                targetBuffer = tmp;
            }
        }

        /// <summary>
        /// Radix sort or bucket sort, stable and non in place.
        /// </summary>
        /// <param name="arr">Array to sort.</param>
        /// <param name="sortSize">Size of the array to sort. If greater than array capacity, it will get clamped.</param>
        /// <param name="supportArray">Array of uints that is used for support data. The algorithm will automatically allocate it if necessary.</param>
        /// <param name="radixBits">Number of bits to use for each bucket. Can only be 8, 4 or 2.</param>
        public static unsafe void RadixSort(uint[] arr, int sortSize, ref uint[] supportArray, int radixBits = 8)
        {
            sortSize = Math.Min(sortSize, arr.Length);
            CalculateRadixParams(radixBits, out int bitStates);
            if (arr == null || sortSize == 0)
                return;

            int supportSize = CalculateRadixSupportSize(bitStates, sortSize);
            if (supportArray == null || supportArray.Length < supportSize)
                supportArray = new uint[supportSize];

            fixed (uint* ptr = arr)
            fixed (uint* supportArrayPtr = supportArray)
                CoreUnsafeUtils.RadixSort(ptr, supportArrayPtr, radixBits, bitStates, sortSize);
        }

        /// <summary>
        /// Radix sort or bucket sort, stable and non in place.
        /// </summary>
        /// <param name="array">Array to sort.</param>
        /// <param name="sortSize">Size of the array to sort. If greater than array capacity, it will get clamped.</param>
        /// <param name="supportArray">Array of uints that is used for support data. The algorithm will automatically allocate it if necessary.</param>
        /// <param name="radixBits">Number of bits to use for each bucket. Can only be 8, 4 or 2.</param>
        public static unsafe void RadixSort(NativeArray<uint> array, int sortSize, ref NativeArray<uint> supportArray, int radixBits = 8)
        {
            sortSize = Math.Min(sortSize, array.Length);
            CalculateRadixParams(radixBits, out int bitStates);
            if (!array.IsCreated || sortSize == 0)
                return;

            int supportSize = CalculateRadixSupportSize(bitStates, sortSize);
            if (!supportArray.IsCreated || supportArray.Length < supportSize)
                supportArray.ResizeArray((int)supportSize);

            CoreUnsafeUtils.RadixSort((uint*)array.GetUnsafePtr(), (uint*)supportArray.GetUnsafePtr(), radixBits, bitStates, sortSize);
        }

        /// <summary>
        /// Quick Sort
        /// </summary>
        /// <param name="arr">uint array.</param>
        /// <param name="left">Left boundary.</param>
        /// <param name="right">Left boundary.</param>
        public static unsafe void QuickSort(uint[] arr, int left, int right)
        {
            fixed (uint* ptr = arr)
                CoreUnsafeUtils.QuickSort<uint, uint, UintKeyGetter>(ptr, left, right);
        }

        /// <summary>
        /// Quick Sort
        /// </summary>
        /// <param name="arr">ulong array.</param>
        /// <param name="left">Left boundary.</param>
        /// <param name="right">Left boundary.</param>
        public static unsafe void QuickSort(ulong[] arr, int left, int right)
        {
            fixed (ulong* ptr = arr)
                CoreUnsafeUtils.QuickSort<ulong, ulong, UlongKeyGetter>(ptr, left, right);
        }

        /// <summary>
        /// Quick sort.
        /// </summary>
        /// <typeparam name="T">Type to compare.</typeparam>
        /// <param name="count">Number of element.</param>
        /// <param name="data">Buffer to sort.</param>
        public static void QuickSort<T>(int count, void* data)
            where T : struct, IComparable<T>
        {
            QuickSort<T, T, DefaultKeyGetter<T>>(data, 0, count - 1);
        }

        /// <summary>
        /// Quick sort.
        /// </summary>
        /// <typeparam name="TValue">Value type.</typeparam>
        /// <typeparam name="TKey">Key Type.</typeparam>
        /// <typeparam name="TGetter">Getter type.</typeparam>
        /// <param name="count">Number of element.</param>
        /// <param name="data">Data to sort.</param>
        public static void QuickSort<TValue, TKey, TGetter>(int count, void* data)
            where TKey : struct, IComparable<TKey>
            where TValue : struct
            where TGetter : struct, IKeyGetter<TValue, TKey>
        {
            QuickSort<TValue, TKey, TGetter>(data, 0, count - 1);
        }

        /// <summary>
        /// Quick sort.
        /// </summary>
        /// <typeparam name="TValue">Value type.</typeparam>
        /// <typeparam name="TKey">Key Type.</typeparam>
        /// <typeparam name="TGetter">Getter type.</typeparam>
        /// <param name="data">Data to sort.</param>
        /// <param name="left">Left boundary.</param>
        /// <param name="right">Right boundary.</param>
        public static void QuickSort<TValue, TKey, TGetter>(void* data, int left, int right)
            where TKey : struct, IComparable<TKey>
            where TValue : struct
            where TGetter : struct, IKeyGetter<TValue, TKey>
        {
            // For Recursion
            if (left < right)
            {
                int pivot = Partition<TValue, TKey, TGetter>(data, left, right);

                if (pivot >= 1)
                    QuickSort<TValue, TKey, TGetter>(data, left, pivot);

                if (pivot + 1 < right)
                    QuickSort<TValue, TKey, TGetter>(data, pivot + 1, right);
            }
        }

        /// <summary>
        /// Index of an element in a buffer.
        /// </summary>
        /// <typeparam name="T">Data type.</typeparam>
        /// <param name="data">Data buffer.</param>
        /// <param name="count">Number of elements.</param>
        /// <param name="v">Element to test against.</param>
        /// <returns>The first index of the provided element.</returns>
        public static int IndexOf<T>(void* data, int count, T v)
            where T : struct, IEquatable<T>
        {
            for (int i = 0; i < count; ++i)
            {
                if (UnsafeUtility.ReadArrayElement<T>(data, i).Equals(v))
                    return i;
            }
            return -1;
        }

        /// <summary>
        /// Compare hashes of two collections and provide
        /// a list of indices <paramref name="removeIndices"/> to remove in <paramref name="oldHashes"/>
        /// and a list of indices <paramref name="addIndices"/> to add in <paramref name="newHashes"/>.
        ///
        /// Assumes that <paramref name="newHashes"/> and <paramref name="oldHashes"/> are sorted.
        /// </summary>
        /// <typeparam name="TOldValue">Old value type.</typeparam>
        /// <typeparam name="TOldGetter">Old getter type.</typeparam>
        /// <typeparam name="TNewValue">New value type.</typeparam>
        /// <typeparam name="TNewGetter">New getter type.</typeparam>
        /// <param name="oldHashCount">Number of hashes in <paramref name="oldHashes"/>.</param>
        /// <param name="oldHashes">Previous hashes to compare.</param>
        /// <param name="newHashCount">Number of hashes in <paramref name="newHashes"/>.</param>
        /// <param name="newHashes">New hashes to compare.</param>
        /// <param name="addIndices">Indices of element to add in <paramref name="newHashes"/> will be written here.</param>
        /// <param name="removeIndices">Indices of element to remove in <paramref name="oldHashes"/> will be written here.</param>
        /// <param name="addCount">Number of elements to add will be written here.</param>
        /// <param name="remCount">Number of elements to remove will be written here.</param>
        /// <returns>The number of operations to perform (<paramref name="addCount"/><c> + </c><paramref name="remCount"/>)</returns>

        public static int CompareHashes<TOldValue, TOldGetter, TNewValue, TNewGetter>(
            int oldHashCount, void* oldHashes,
            int newHashCount, void* newHashes,
            // assume that the capacity of indices is >= max(oldHashCount, newHashCount)
            int* addIndices, int* removeIndices,
            out int addCount, out int remCount
        )
            where TOldValue : struct
            where TNewValue : struct
            where TOldGetter : struct, IKeyGetter<TOldValue, Hash128>
            where TNewGetter : struct, IKeyGetter<TNewValue, Hash128>
        {
            var oldGetter = new TOldGetter();
            var newGetter = new TNewGetter();

            addCount = 0;
            remCount = 0;
            // Check combined hashes
            if (oldHashCount == newHashCount)
            {
                var oldHash = new Hash128();
                var newHash = new Hash128();
                CombineHashes<TOldValue, TOldGetter>(oldHashCount, oldHashes, &oldHash);
                CombineHashes<TNewValue, TNewGetter>(newHashCount, newHashes, &newHash);
                if (oldHash == newHash)
                    return 0;
            }

            var numOperations = 0;

            var oldI = 0;
            var newI = 0;

            while (oldI < oldHashCount || newI < newHashCount)
            {
                // At the end of old array.
                if (oldI == oldHashCount)
                {
                    // No more hashes in old array. Add remaining entries from new array.
                    for (; newI < newHashCount; ++newI)
                    {
                        addIndices[addCount++] = newI;
                        ++numOperations;
                    }
                    continue;
                }

                // At end of new array.
                if (newI == newHashCount)
                {
                    // No more hashes in old array. Remove remaining entries from old array.
                    for (; oldI < oldHashCount; ++oldI)
                    {
                        removeIndices[remCount++] = oldI;
                        ++numOperations;
                    }
                    continue;
                }

                // Both arrays have data.
                var newVal = UnsafeUtility.ReadArrayElement<TNewValue>(newHashes, newI);
                var oldVal = UnsafeUtility.ReadArrayElement<TOldValue>(oldHashes, oldI);
                var newKey = newGetter.Get(ref newVal);
                var oldKey = oldGetter.Get(ref oldVal);
                if (newKey == oldKey)
                {
                    // Matching hash, skip.
                    ++newI;
                    ++oldI;
                    continue;
                }

                // Both arrays have data, but hashes do not match.
                if (newKey < oldKey)
                {
                    // oldIter is the greater hash. Push "add" jobs from the new array until reaching the oldIter hash.
                    while (newI < newHashCount && newKey < oldKey)
                    {
                        addIndices[addCount++] = newI;
                        ++newI;
                        ++numOperations;
                        newVal = UnsafeUtility.ReadArrayElement<TNewValue>(newHashes, newI);
                        newKey = newGetter.Get(ref newVal);
                    }
                }
                else
                {
                    // newIter is the greater hash. Push "remove" jobs from the old array until reaching the newIter hash.
                    while (oldI < oldHashCount && oldKey < newKey)
                    {
                        removeIndices[remCount++] = oldI;
                        ++numOperations;
                        ++oldI;
                    }
                }
            }

            return numOperations;
        }

        /// <summary>
        /// Compare hashes.
        /// </summary>
        /// <param name="oldHashCount">Number of hashes in <paramref name="oldHashes"/>.</param>
        /// <param name="oldHashes">Previous hashes to compare.</param>
        /// <param name="newHashCount">Number of hashes in <paramref name="newHashes"/>.</param>
        /// <param name="newHashes">New hashes to compare.</param>
        /// <param name="addIndices">Indices of element to add in <paramref name="newHashes"/> will be written here.</param>
        /// <param name="removeIndices">Indices of element to remove in <paramref name="oldHashes"/> will be written here.</param>
        /// <param name="addCount">Number of elements to add will be written here.</param>
        /// <param name="remCount">Number of elements to remove will be written here.</param>
        /// <returns>The number of operations to perform (<paramref name="addCount"/><c> + </c><paramref name="remCount"/>)</returns>
        public static int CompareHashes(
            int oldHashCount, Hash128* oldHashes,
            int newHashCount, Hash128* newHashes,
            // assume that the capacity of indices is >= max(oldHashCount, newHashCount)
            int* addIndices, int* removeIndices,
            out int addCount, out int remCount
        )
        {
            return CompareHashes<Hash128, DefaultKeyGetter<Hash128>, Hash128, DefaultKeyGetter<Hash128>>(
                oldHashCount, oldHashes,
                newHashCount, newHashes,
                addIndices, removeIndices,
                out addCount, out remCount
            );
        }

        /// <summary>Combine all of the hashes of a collection of hashes.</summary>
        /// <typeparam name="TValue">Value type.</typeparam>
        /// <typeparam name="TGetter">Getter type.</typeparam>
        /// <param name="count">Number of hash to combine.</param>
        /// <param name="hashes">Hashes to combine.</param>
        /// <param name="outHash">Hash to update.</param>
        public static void CombineHashes<TValue, TGetter>(int count, void* hashes, Hash128* outHash)
            where TValue : struct
            where TGetter : struct, IKeyGetter<TValue, Hash128>
        {
            var getter = new TGetter();
            for (int i = 0; i < count; ++i)
            {
                var v = UnsafeUtility.ReadArrayElement<TValue>(hashes, i);
                var h = getter.Get(ref v);
                HashUtilities.AppendHash(ref h, ref *outHash);
            }
        }

        /// <summary>
        /// Combine hashes.
        /// </summary>
        /// <param name="count">Number of hash to combine.</param>
        /// <param name="hashes">Hashes to combine.</param>
        /// <param name="outHash">Hash to update.</param>
        public static void CombineHashes(int count, Hash128* hashes, Hash128* outHash)
        {
            CombineHashes<Hash128, DefaultKeyGetter<Hash128>>(count, hashes, outHash);
        }

        // Just a sort function that doesn't allocate memory
        // Note: Should be replace by a radix sort for positive integer
        static int Partition<TValue, TKey, TGetter>(void* data, int left, int right)
            where TKey : struct, IComparable<TKey>
            where TValue : struct
            where TGetter : struct, IKeyGetter<TValue, TKey>
        {
            var getter = default(TGetter);
            var pivotvalue = UnsafeUtility.ReadArrayElement<TValue>(data, left);
            var pivot = getter.Get(ref pivotvalue);

            --left;
            ++right;
            while (true)
            {
                var c = 0;
                var lvalue = default(TValue);
                var lkey = default(TKey);
                do
                {
                    ++left;
                    lvalue = UnsafeUtility.ReadArrayElement<TValue>(data, left);
                    lkey = getter.Get(ref lvalue);
                    c = lkey.CompareTo(pivot);
                }
                while (c < 0);

                var rvalue = default(TValue);
                var rkey = default(TKey);
                do
                {
                    --right;
                    rvalue = UnsafeUtility.ReadArrayElement<TValue>(data, right);
                    rkey = getter.Get(ref rvalue);
                    c = rkey.CompareTo(pivot);
                }
                while (c > 0);

                if (left < right)
                {
                    UnsafeUtility.WriteArrayElement(data, right, lvalue);
                    UnsafeUtility.WriteArrayElement(data, left, rvalue);
                }
                else
                {
                    return right;
                }
            }
        }

        /// <summary>
        /// Checks for duplicates in an array.
        /// </summary>
        /// <param name="arr">Input array.</param>
        /// <returns>True if there is any duplicate in the input array.</returns>
        public static unsafe bool HaveDuplicates(int[] arr)
        {
            int* copy = stackalloc int[arr.Length];
            arr.CopyTo<int>(copy, arr.Length);
            QuickSort<int>(arr.Length, copy);
            for (int i = arr.Length - 1; i > 0; --i)
            {
                if (UnsafeUtility.ReadArrayElement<int>(copy, i).CompareTo(UnsafeUtility.ReadArrayElement<int>(copy, i - 1)) == 0)
                {
                    return true;
                }
            }
            return false;
        }
    }
}