using System;
using System.Collections.Generic;
using System.Diagnostics;
using Unity.Burst;
using Unity.Collections.LowLevel.Unsafe;
using Unity.Jobs;
using Unity.Jobs.LowLevel.Unsafe;
using Unity.Mathematics;
namespace Unity.Collections
{
///
/// Extension methods for sorting collections.
///
[GenerateTestsForBurstCompatibility]
public static class NativeSortExtension
{
///
/// A comparer that uses IComparable.CompareTo(). For primitive types, this is an ascending sort.
///
/// Source type of elements
[GenerateTestsForBurstCompatibility(GenericTypeArguments = new[] { typeof(int) })]
public struct DefaultComparer : IComparer where T : IComparable
{
///
/// Compares two values.
///
/// First value to compare.
/// Second value to compare.
/// A signed integer that denotes the relative values of `x` and `y`:
/// 0 if they're equal, negative if `x < y`, and positive if `x > y`.
public int Compare(T x, T y) => x.CompareTo(y);
}
///
/// Sorts an array in ascending order.
///
/// The type of the elements.
/// The array to sort.
/// The number of elements to sort in the array.
/// Indexes greater than or equal to `length` won't be included in the sort.
[GenerateTestsForBurstCompatibility(GenericTypeArguments = new[] { typeof(int) })]
public unsafe static void Sort(T* array, int length)
where T : unmanaged, IComparable
{
IntroSort>(array, length, new DefaultComparer());
}
///
/// Sorts an array using a custom comparison.
///
/// The type of the elements.
/// The type of the comparer.
/// The array to sort.
/// The number of elements to sort in the array.
/// Indexes greater than or equal to `length` won't be included in the sort.
/// The comparison function used to determine the relative order of the elements.
[GenerateTestsForBurstCompatibility(GenericTypeArguments = new[] { typeof(int), typeof(DefaultComparer) })]
public unsafe static void Sort(T* array, int length, U comp)
where T : unmanaged
where U : IComparer
{
IntroSort(array, length, comp);
}
///
/// Returns a job which will sort an array in ascending order.
///
/// This method does not schedule the job. Scheduling the job is left to you.
/// The type of the elements.
/// The array to sort.
/// The number of elements to sort in the array.
/// Indexes greater than or equal to `length` won't be included in the sort.
/// A job for sorting the array.
[GenerateTestsForBurstCompatibility(GenericTypeArguments = new[] { typeof(int) }, RequiredUnityDefine = "UNITY_2020_2_OR_NEWER" /* Due to job scheduling on 2020.1 using statics */)]
public unsafe static SortJob> SortJob(T* array, int length)
where T : unmanaged, IComparable
{
return new SortJob> { Data = array, Length = length, Comp = new DefaultComparer() };
}
///
/// Returns a job which will sort an array using a custom comparison.
///
/// This method does not schedule the job. Scheduling the job is left to you.
/// The type of the elements.
/// The type of the comparer.
/// The array to sort.
/// The number of elements to sort in the array.
/// Indexes greater than or equal to `length` won't be included in the sort.
/// The comparison function used to determine the relative order of the elements.
/// A job for sorting the array.
[GenerateTestsForBurstCompatibility(GenericTypeArguments = new[] { typeof(int), typeof(DefaultComparer) }, RequiredUnityDefine = "UNITY_2020_2_OR_NEWER" /* Due to job scheduling on 2020.1 using statics */)]
public unsafe static SortJob SortJob(T* array, int length, U comp)
where T : unmanaged
where U : IComparer
{
CheckComparer(array, length, comp);
return new SortJob() { Data = array, Length = length, Comp = comp };
}
///
/// Finds a value in a sorted array by binary search.
///
/// If the array is not sorted, the value might not be found, even if it's present in the array.
/// The type of the elements.
/// The array to search.
/// The value to locate.
/// The number of elements to search. Indexes greater than or equal to `length` won't be searched.
/// If found, the index of the located value. If not found, the return value is negative.
[GenerateTestsForBurstCompatibility(GenericTypeArguments = new[] { typeof(int) })]
public unsafe static int BinarySearch(T* ptr, int length, T value)
where T : unmanaged, IComparable
{
return BinarySearch(ptr, length, value, new DefaultComparer());
}
///
/// Finds a value in a sorted array by binary search using a custom comparison.
///
/// If the array is not sorted, the value might not be found, even if it's present in the array.
/// The type of the elements.
/// The type of the comparer.
/// The array to search.
/// The value to locate.
/// The number of elements to search. Indexes greater than or equal to `length` won't be searched.
/// The comparison function used to determine the relative order of the elements.
/// If found, the index of the located value. If not found, the return value is negative.
[GenerateTestsForBurstCompatibility(GenericTypeArguments = new[] { typeof(int), typeof(DefaultComparer) })]
public unsafe static int BinarySearch(T* ptr, int length, T value, U comp)
where T : unmanaged
where U : IComparer
{
CheckComparer(ptr, length, comp);
var offset = 0;
for (var l = length; l != 0; l >>= 1)
{
var idx = offset + (l >> 1);
var curr = ptr[idx];
var r = comp.Compare(value, curr);
if (r == 0)
{
return idx;
}
if (r > 0)
{
offset = idx + 1;
--l;
}
}
return ~offset;
}
///
/// Sorts this array in ascending order.
///
/// The type of the elements.
/// The array to sort.
[GenerateTestsForBurstCompatibility(GenericTypeArguments = new[] { typeof(int) })]
public unsafe static void Sort(this NativeArray array)
where T : unmanaged, IComparable
{
IntroSortStruct>(array.GetUnsafePtr(), array.Length, new DefaultComparer());
}
///
/// Sorts this array using a custom comparison.
///
/// The type of the elements.
/// The type of the comparer.
/// The array to sort.
/// The comparison function used to determine the relative order of the elements.
[GenerateTestsForBurstCompatibility(GenericTypeArguments = new[] { typeof(int), typeof(DefaultComparer) })]
public unsafe static void Sort(this NativeArray array, U comp)
where T : unmanaged
where U : IComparer
{
var ptr = (T*)array.GetUnsafePtr();
var len = array.Length;
CheckComparer(ptr, len, comp);
IntroSortStruct(ptr, len, comp);
}
///
/// Returns a job which will sort this array in ascending order.
///
/// This method does not schedule the job. Scheduling the job is left to you.
/// The type of the elements.
/// The array to sort.
/// A job for sorting this array.
[GenerateTestsForBurstCompatibility(GenericTypeArguments = new[] { typeof(int) }, RequiredUnityDefine = "UNITY_2020_2_OR_NEWER" /* Due to job scheduling on 2020.1 using statics */)]
public unsafe static SortJob> SortJob(this NativeArray array)
where T : unmanaged, IComparable
{
return SortJob((T*)NativeArrayUnsafeUtility.GetUnsafeBufferPointerWithoutChecks(array), array.Length, new DefaultComparer());
}
///
/// Returns a job which will sort this array using a custom comparison.
///
/// This method does not schedule the job. Scheduling the job is left to you.
/// The type of the elements.
/// The type of the comparer.
/// The array to sort.
/// The comparison function used to determine the relative order of the elements.
/// A job for sorting the array.
[GenerateTestsForBurstCompatibility(GenericTypeArguments = new[] { typeof(int), typeof(DefaultComparer) }, RequiredUnityDefine = "UNITY_2020_2_OR_NEWER" /* Due to job scheduling on 2020.1 using statics */)]
public unsafe static SortJob SortJob(this NativeArray array, U comp)
where T : unmanaged
where U : IComparer
{
var ptr = (T*)NativeArrayUnsafeUtility.GetUnsafeBufferPointerWithoutChecks(array);
var len = array.Length;
CheckComparer(ptr, len, comp);
return new SortJob
{
Data = ptr,
Length = len,
Comp = comp
};
}
///
/// Finds a value in this sorted array by binary search.
///
/// If the array is not sorted, the value might not be found, even if it's present in this array.
/// The type of the elements.
/// The array to search.
/// The value to locate.
/// If found, the index of the located value. If not found, the return value is negative.
[GenerateTestsForBurstCompatibility(GenericTypeArguments = new[] { typeof(int) })]
public static int BinarySearch(this NativeArray array, T value)
where T : unmanaged, IComparable
{
return array.BinarySearch(value, new DefaultComparer());
}
///
/// Finds a value in this sorted array by binary search using a custom comparison.
///
/// If the array is not sorted, the value might not be found, even if it's present in this array.
///
/// The type of the elements.
/// The comparer type.
/// The array to search.
/// The value to locate.
/// The comparison function used to determine the relative order of the elements.
/// If found, the index of the located value. If not found, the return value is negative.
[GenerateTestsForBurstCompatibility(GenericTypeArguments = new[] { typeof(int), typeof(DefaultComparer) })]
public unsafe static int BinarySearch(this NativeArray array, T value, U comp)
where T : unmanaged
where U : IComparer
{
return BinarySearch((T*)NativeArrayUnsafeUtility.GetUnsafeReadOnlyPtr(array), array.Length, value, comp);
}
///
/// Finds a value in this sorted array by binary search.
///
/// If the array is not sorted, the value might not be found, even if it's present in this array.
/// The type of the elements.
/// The array to search.
/// The value to locate.
/// If found, the index of the located value. If not found, the return value is negative.
[GenerateTestsForBurstCompatibility(GenericTypeArguments = new[] { typeof(int) })]
public static int BinarySearch(this NativeArray.ReadOnly array, T value)
where T : unmanaged, IComparable
{
return array.BinarySearch(value, new DefaultComparer());
}
///
/// Finds a value in this sorted array by binary search using a custom comparison.
///
/// If the array is not sorted, the value might not be found, even if it's present in this array.
///
/// The type of the elements.
/// The comparer type.
/// The array to search.
/// The value to locate.
/// The comparison function used to determine the relative order of the elements.
/// If found, the index of the located value. If not found, the return value is negative.
[GenerateTestsForBurstCompatibility(GenericTypeArguments = new[] { typeof(int), typeof(DefaultComparer) })]
public unsafe static int BinarySearch(this NativeArray.ReadOnly array, T value, U comp)
where T : unmanaged
where U : IComparer
{
return BinarySearch((T*)NativeArrayUnsafeUtility.GetUnsafeReadOnlyPtr(array), array.Length, value, comp);
}
///
/// Sorts this list in ascending order.
///
/// The type of the elements.
/// The list to sort.
[GenerateTestsForBurstCompatibility(GenericTypeArguments = new[] { typeof(int) })]
public unsafe static void Sort(this NativeList list)
where T : unmanaged, IComparable
{
list.Sort(new DefaultComparer());
}
///
/// Sorts this list using a custom comparison.
///
/// The type of the elements.
/// The type of the comparer.
/// The list to sort.
/// The comparison function used to determine the relative order of the elements.
[GenerateTestsForBurstCompatibility(GenericTypeArguments = new[] { typeof(int), typeof(DefaultComparer) })]
public unsafe static void Sort(this NativeList list, U comp)
where T : unmanaged
where U : IComparer
{
IntroSort(list.GetUnsafePtr(), list.Length, comp);
}
///
/// Returns a job which will sort this list in ascending order.
///
/// When `NativeList.Length` is not known at scheduling time use `SortJobDefer` instead.
/// This method does not schedule the job. Scheduling the job is left to you.
/// The type of the elements.
/// The list to sort.
/// A job for sorting this list.
[GenerateTestsForBurstCompatibility(GenericTypeArguments = new[] { typeof(int) }, RequiredUnityDefine = "UNITY_2020_2_OR_NEWER" /* Due to job scheduling on 2020.1 using statics */)]
public unsafe static SortJob> SortJob(this NativeList list)
where T : unmanaged, IComparable
{
return SortJob(list, new DefaultComparer());
}
///
/// Returns a job which will sort this list using a custom comparison.
///
/// When `NativeList.Length` is not known at scheduling time use `SortJobDefer` instead.
/// This method does not schedule the job. Scheduling the job is left to you.
/// The type of the elements.
/// The type of the comparer.
/// The list to sort.
/// The comparison function used to determine the relative order of the elements.
/// A job for sorting this list.
[GenerateTestsForBurstCompatibility(GenericTypeArguments = new[] { typeof(int), typeof(DefaultComparer) }, RequiredUnityDefine = "UNITY_2020_2_OR_NEWER" /* Due to job scheduling on 2020.1 using statics */)]
public unsafe static SortJob SortJob(this NativeList list, U comp)
where T : unmanaged
where U : IComparer
{
return SortJob(list.GetUnsafePtr(), list.Length, comp);
}
///
/// Returns a job which will sort this list in ascending order.
///
/// `SortJobDefer` is intended for use when `NativeList.Length` is not known at scheduling time,
/// and it depends on completion of previosly scheduled job(s).
/// This method does not schedule the job. Scheduling the job is left to you.
/// The type of the elements.
/// The list to sort.
/// A job for sorting this list.
[GenerateTestsForBurstCompatibility(GenericTypeArguments = new[] { typeof(int) }, RequiredUnityDefine = "UNITY_2020_2_OR_NEWER" /* Due to job scheduling on 2020.1 using statics */)]
public unsafe static SortJobDefer> SortJobDefer(this NativeList list)
where T : unmanaged, IComparable
{
return SortJobDefer(list, new DefaultComparer());
}
///
/// Returns a job which will sort this list using a custom comparison.
///
/// `SortJobDefer` is intended for use when `NativeList.Length` is not known at scheduling time,
/// and it depends on completion of previosly scheduled job(s).
/// This method does not schedule the job. Scheduling the job is left to you.
/// The type of the elements.
/// The type of the comparer.
/// The list to sort.
/// The comparison function used to determine the relative order of the elements.
/// A job for sorting this list.
[GenerateTestsForBurstCompatibility(GenericTypeArguments = new[] { typeof(int), typeof(DefaultComparer) }, RequiredUnityDefine = "UNITY_2020_2_OR_NEWER" /* Due to job scheduling on 2020.1 using statics */)]
public unsafe static SortJobDefer SortJobDefer(this NativeList list, U comp)
where T : unmanaged
where U : IComparer
{
return new SortJobDefer { Data = list, Comp = comp };
}
///
/// Finds a value in this sorted list by binary search.
///
/// If this list is not sorted, the value might not be found, even if it's present in this list.
/// The type of the elements.
/// The list to search.
/// The value to locate.
/// If found, the index of the located value. If not found, the return value is negative.
[GenerateTestsForBurstCompatibility(GenericTypeArguments = new[] { typeof(int) })]
public static int BinarySearch(this NativeList list, T value)
where T : unmanaged, IComparable
{
return list.AsReadOnly().BinarySearch(value, new DefaultComparer());
}
///
/// Finds a value in this sorted list by binary search using a custom comparison.
///
/// If this list is not sorted, the value may not be found, even if it's present in this list.
/// The type of the elements.
/// The type of the comparer.
/// The list to search.
/// The value to locate.
/// The comparison function used to determine the relative order of the elements.
/// If found, the index of the located value. If not found, the return value is negative.
[GenerateTestsForBurstCompatibility(GenericTypeArguments = new[] { typeof(int), typeof(DefaultComparer) })]
public unsafe static int BinarySearch(this NativeList list, T value, U comp)
where T : unmanaged
where U : IComparer
{
return list.AsReadOnly().BinarySearch(value, comp);
}
///
/// Sorts this list in ascending order.
///
/// The type of the elements.
/// The list to sort.
[GenerateTestsForBurstCompatibility(GenericTypeArguments = new[] { typeof(int) })]
public unsafe static void Sort(this UnsafeList list) where T : unmanaged, IComparable
{
list.Sort(new DefaultComparer());
}
///
/// Sorts the list using a custom comparison.
///
/// The type of the elements.
/// The type of the comparer.
/// The list to sort.
/// The comparison function used to determine the relative order of the elements.
[GenerateTestsForBurstCompatibility(GenericTypeArguments = new[] { typeof(int), typeof(DefaultComparer) })]
public unsafe static void Sort(this UnsafeList list, U comp)
where T : unmanaged
where U : IComparer
{
IntroSort(list.Ptr, list.Length, comp);
}
///
/// Returns a job which will sort this list in ascending order.
///
/// This method does not schedule the job. Scheduling the job is left to you.
/// The type of the elements.
/// The list to sort.
/// A job for sorting this list.
[GenerateTestsForBurstCompatibility(GenericTypeArguments = new[] { typeof(int) }, RequiredUnityDefine = "UNITY_2020_2_OR_NEWER" /* Due to job scheduling on 2020.1 using statics */)]
public unsafe static SortJob> SortJob(this UnsafeList list)
where T : unmanaged, IComparable
{
return SortJob(list.Ptr, list.Length, new DefaultComparer());
}
///
/// Returns a job which will sort this list using a custom comparison.
///
/// This method does not schedule the job. Scheduling the job is left to you.
/// The type of the elements.
/// The type of the comparer.
/// The list to sort.
/// The comparison function used to determine the relative order of the elements.
/// A job for sorting this list.
[GenerateTestsForBurstCompatibility(GenericTypeArguments = new[] { typeof(int), typeof(DefaultComparer) }, RequiredUnityDefine = "UNITY_2020_2_OR_NEWER" /* Due to job scheduling on 2020.1 using statics */)]
public unsafe static SortJob SortJob(this UnsafeList list, U comp)
where T : unmanaged
where U : IComparer
{
return SortJob(list.Ptr, list.Length, comp);
}
///
/// Finds a value in this sorted list by binary search.
///
/// If this list is not sorted, the value might not be found, even if it's present in this list.
/// The type of the elements.
/// The list to search.
/// The value to locate.
/// If found, the index of the located value. If not found, the return value is negative.
[GenerateTestsForBurstCompatibility(GenericTypeArguments = new[] { typeof(int) })]
public static int BinarySearch(this UnsafeList list, T value)
where T : unmanaged, IComparable
{
return list.BinarySearch(value, new DefaultComparer());
}
///
/// Finds a value in this sorted list by binary search using a custom comparison.
///
/// If this list is not sorted, the value might not be found, even if it's present in this list.
/// The type of the elements.
/// The type of the comparer.
/// The list to search.
/// The value to locate.
/// The comparison function used to determine the relative order of the elements.
/// If found, the index of the located value. If not found, the return value is negative.
[GenerateTestsForBurstCompatibility(GenericTypeArguments = new[] { typeof(int), typeof(DefaultComparer) })]
public unsafe static int BinarySearch(this UnsafeList list, T value, U comp)
where T : unmanaged
where U : IComparer
{
return BinarySearch(list.Ptr, list.Length, value, comp);
}
///
/// Sorts this slice in ascending order.
///
/// The type of the elements.
/// The slice to sort.
[GenerateTestsForBurstCompatibility(GenericTypeArguments = new[] { typeof(int) })]
public unsafe static void Sort(this NativeSlice slice)
where T : unmanaged, IComparable
{
slice.Sort(new DefaultComparer());
}
///
/// Sorts this slice using a custom comparison.
///
/// The type of the elements.
/// The type of the comparer.
/// The slice to sort.
/// The comparison function used to determine the relative order of the elements.
[GenerateTestsForBurstCompatibility(GenericTypeArguments = new[] { typeof(int), typeof(DefaultComparer) })]
public unsafe static void Sort(this NativeSlice slice, U comp)
where T : unmanaged
where U : IComparer
{
var ptr = (T*)slice.GetUnsafePtr();
var len = slice.Length;
CheckComparer(ptr, len, comp);
CheckStrideMatchesSize(slice.Stride);
IntroSortStruct(ptr, len, comp);
}
///
/// Returns a job which will sort this slice in ascending order.
///
/// This method does not schedule the job. Scheduling the job is left to you.
/// The type of the elements.
/// The slice to sort.
/// A job for sorting this slice.
[GenerateTestsForBurstCompatibility(GenericTypeArguments = new[] { typeof(int) }, RequiredUnityDefine = "UNITY_2020_2_OR_NEWER" /* Due to job scheduling on 2020.1 using statics */)]
public unsafe static SortJob> SortJob(this NativeSlice slice)
where T : unmanaged, IComparable
{
CheckStrideMatchesSize(slice.Stride);
return SortJob((T*)slice.GetUnsafePtr(), slice.Length, new DefaultComparer());
}
///
/// Returns a job which will sort this slice using a custom comparison.
///
/// This method does not schedule the job. Scheduling the job is left to you.
/// The type of the elements.
/// The type of the comparer.
/// The slice to sort.
/// The comparison function used to determine the relative order of the elements.
/// A job for sorting this slice.
[GenerateTestsForBurstCompatibility(GenericTypeArguments = new[] { typeof(int), typeof(DefaultComparer) }, RequiredUnityDefine = "UNITY_2020_2_OR_NEWER" /* Due to job scheduling on 2020.1 using statics */)]
public unsafe static SortJob SortJob(this NativeSlice slice, U comp)
where T : unmanaged
where U : IComparer
{
CheckStrideMatchesSize(slice.Stride);
return SortJob((T*)slice.GetUnsafePtr(), slice.Length, comp);
}
///
/// Finds a value in this sorted slice by binary search.
///
/// If this slice is not sorted, the value might not be found, even if it's present in this slice.
/// The type of the elements.
/// The slice to search.
/// The value to locate.
/// If found, the index of the located value. If not found, the return value is negative.
[GenerateTestsForBurstCompatibility(GenericTypeArguments = new[] { typeof(int) })]
public static int BinarySearch(this NativeSlice slice, T value)
where T : unmanaged, IComparable
{
return slice.BinarySearch(value, new DefaultComparer());
}
///
/// Finds a value in this sorted slice by binary search using a custom comparison.
///
/// If this slice is not sorted, the value might not be found, even if it's present in this slice.
/// The type of the elements.
/// The type of the comparer.
/// The slice to search.
/// The value to locate.
/// The comparison function used to determine the relative order of the elements.
/// If found, the index of the located value. If not found, the return value is negative.
[GenerateTestsForBurstCompatibility(GenericTypeArguments = new[] { typeof(int), typeof(DefaultComparer) })]
public unsafe static int BinarySearch(this NativeSlice slice, T value, U comp)
where T : unmanaged
where U : IComparer
{
return BinarySearch((T*)slice.GetUnsafeReadOnlyPtr(), slice.Length, value, comp);
}
/// -- Internals
[GenerateTestsForBurstCompatibility(GenericTypeArguments = new[] { typeof(int), typeof(DefaultComparer) })]
unsafe internal static void IntroSort(void* array, int length, U comp)
where T : unmanaged
where U : IComparer
{
CheckComparer((T*)array, length, comp);
IntroSort_R(array, 0, length - 1, 2 * CollectionHelper.Log2Floor(length), comp);
}
const int k_IntrosortSizeThreshold = 16;
[GenerateTestsForBurstCompatibility(GenericTypeArguments = new[] { typeof(int), typeof(DefaultComparer) })]
unsafe internal static void IntroSort_R(void* array, int lo, int hi, int depth, U comp)
where T : unmanaged
where U : IComparer
{
while (hi > lo)
{
int partitionSize = hi - lo + 1;
if (partitionSize <= k_IntrosortSizeThreshold)
{
if (partitionSize == 1)
{
return;
}
if (partitionSize == 2)
{
SwapIfGreaterWithItems(array, lo, hi, comp);
return;
}
if (partitionSize == 3)
{
SwapIfGreaterWithItems(array, lo, hi - 1, comp);
SwapIfGreaterWithItems(array, lo, hi, comp);
SwapIfGreaterWithItems(array, hi - 1, hi, comp);
return;
}
InsertionSort(array, lo, hi, comp);
return;
}
if (depth == 0)
{
HeapSort(array, lo, hi, comp);
return;
}
depth--;
int p = Partition(array, lo, hi, comp);
IntroSort_R(array, p + 1, hi, depth, comp);
hi = p - 1;
}
}
unsafe static void InsertionSort(void* array, int lo, int hi, U comp)
where T : unmanaged
where U : IComparer
{
int i, j;
T t;
for (i = lo; i < hi; i++)
{
j = i;
t = UnsafeUtility.ReadArrayElement(array, i + 1);
while (j >= lo && comp.Compare(t, UnsafeUtility.ReadArrayElement(array, j)) < 0)
{
UnsafeUtility.WriteArrayElement(array, j + 1, UnsafeUtility.ReadArrayElement(array, j));
j--;
}
UnsafeUtility.WriteArrayElement(array, j + 1, t);
}
}
unsafe static int Partition(void* array, int lo, int hi, U comp)
where T : unmanaged
where U : IComparer
{
int mid = lo + ((hi - lo) / 2);
SwapIfGreaterWithItems(array, lo, mid, comp);
SwapIfGreaterWithItems(array, lo, hi, comp);
SwapIfGreaterWithItems(array, mid, hi, comp);
T pivot = UnsafeUtility.ReadArrayElement(array, mid);
Swap(array, mid, hi - 1);
int left = lo, right = hi - 1;
while (left < right)
{
while (left < hi && comp.Compare(pivot, UnsafeUtility.ReadArrayElement(array, ++left)) > 0)
{
}
while (right > left && comp.Compare(pivot, UnsafeUtility.ReadArrayElement(array, --right)) < 0)
{
}
if (left >= right)
break;
Swap(array, left, right);
}
Swap(array, left, (hi - 1));
return left;
}
unsafe static void HeapSort(void* array, int lo, int hi, U comp)
where T : unmanaged
where U : IComparer
{
int n = hi - lo + 1;
for (int i = n / 2; i >= 1; i--)
{
Heapify(array, i, n, lo, comp);
}
for (int i = n; i > 1; i--)
{
Swap(array, lo, lo + i - 1);
Heapify(array, 1, i - 1, lo, comp);
}
}
unsafe static void Heapify(void* array, int i, int n, int lo, U comp)
where T : unmanaged
where U : IComparer
{
T val = UnsafeUtility.ReadArrayElement(array, lo + i - 1);
int child;
while (i <= n / 2)
{
child = 2 * i;
if (child < n && (comp.Compare(UnsafeUtility.ReadArrayElement(array, lo + child - 1), UnsafeUtility.ReadArrayElement(array, (lo + child))) < 0))
{
child++;
}
if (comp.Compare(UnsafeUtility.ReadArrayElement(array, (lo + child - 1)), val) < 0)
{
break;
}
UnsafeUtility.WriteArrayElement(array, lo + i - 1, UnsafeUtility.ReadArrayElement(array, lo + child - 1));
i = child;
}
UnsafeUtility.WriteArrayElement(array, lo + i - 1, val);
}
unsafe static void Swap(void* array, int lhs, int rhs) where T : unmanaged
{
T val = UnsafeUtility.ReadArrayElement(array, lhs);
UnsafeUtility.WriteArrayElement(array, lhs, UnsafeUtility.ReadArrayElement(array, rhs));
UnsafeUtility.WriteArrayElement(array, rhs, val);
}
unsafe static void SwapIfGreaterWithItems(void* array, int lhs, int rhs, U comp)
where T : unmanaged
where U : IComparer
{
if (lhs != rhs)
{
if (comp.Compare(UnsafeUtility.ReadArrayElement(array, lhs), UnsafeUtility.ReadArrayElement(array, rhs)) > 0)
{
Swap(array, lhs, rhs);
}
}
}
unsafe static void IntroSortStruct(void* array, int length, U comp)
where T : unmanaged
where U : IComparer
{
IntroSortStruct_R(array, 0, length - 1, 2 * CollectionHelper.Log2Floor(length), comp);
}
unsafe static void IntroSortStruct_R(void* array, in int lo, in int _hi, int depth, U comp)
where T : unmanaged
where U : IComparer
{
var hi = _hi;
while (hi > lo)
{
int partitionSize = hi - lo + 1;
if (partitionSize <= k_IntrosortSizeThreshold)
{
if (partitionSize == 1)
{
return;
}
if (partitionSize == 2)
{
SwapIfGreaterWithItemsStruct(array, lo, hi, comp);
return;
}
if (partitionSize == 3)
{
SwapIfGreaterWithItemsStruct(array, lo, hi - 1, comp);
SwapIfGreaterWithItemsStruct(array, lo, hi, comp);
SwapIfGreaterWithItemsStruct(array, hi - 1, hi, comp);
return;
}
InsertionSortStruct(array, lo, hi, comp);
return;
}
if (depth == 0)
{
HeapSortStruct(array, lo, hi, comp);
return;
}
depth--;
int p = PartitionStruct(array, lo, hi, comp);
IntroSortStruct_R(array, p + 1, hi, depth, comp);
hi = p - 1;
}
}
unsafe static void InsertionSortStruct(void* array, in int lo, in int hi, U comp)
where T : unmanaged
where U : IComparer
{
int i, j;
T t;
for (i = lo; i < hi; i++)
{
j = i;
t = UnsafeUtility.ReadArrayElement(array, i + 1);
while (j >= lo && comp.Compare(t, UnsafeUtility.ReadArrayElement(array, j)) < 0)
{
UnsafeUtility.WriteArrayElement(array, j + 1, UnsafeUtility.ReadArrayElement(array, j));
j--;
}
UnsafeUtility.WriteArrayElement(array, j + 1, t);
}
}
unsafe static int PartitionStruct(void* array, in int lo, in int hi, U comp)
where T : unmanaged
where U : IComparer
{
int mid = lo + ((hi - lo) / 2);
SwapIfGreaterWithItemsStruct(array, lo, mid, comp);
SwapIfGreaterWithItemsStruct(array, lo, hi, comp);
SwapIfGreaterWithItemsStruct(array, mid, hi, comp);
T pivot = UnsafeUtility.ReadArrayElement(array, mid);
SwapStruct(array, mid, hi - 1);
int left = lo, right = hi - 1;
while (left < right)
{
while (left < hi && comp.Compare(pivot, UnsafeUtility.ReadArrayElement(array, ++left)) > 0)
{
}
while (right > left && comp.Compare(pivot, UnsafeUtility.ReadArrayElement(array, --right)) < 0)
{
}
if (left >= right)
break;
SwapStruct(array, left, right);
}
SwapStruct(array, left, (hi - 1));
return left;
}
unsafe static void HeapSortStruct(void* array, in int lo, in int hi, U comp)
where T : unmanaged
where U : IComparer
{
int n = hi - lo + 1;
for (int i = n / 2; i >= 1; i--)
{
HeapifyStruct(array, i, n, lo, comp);
}
for (int i = n; i > 1; i--)
{
SwapStruct(array, lo, lo + i - 1);
HeapifyStruct(array, 1, i - 1, lo, comp);
}
}
unsafe static void HeapifyStruct(void* array, int i, int n, in int lo, U comp)
where T : unmanaged
where U : IComparer
{
T val = UnsafeUtility.ReadArrayElement(array, lo + i - 1);
int child;
while (i <= n / 2)
{
child = 2 * i;
if (child < n && (comp.Compare(UnsafeUtility.ReadArrayElement(array, lo + child - 1), UnsafeUtility.ReadArrayElement(array, (lo + child))) < 0))
{
child++;
}
if (comp.Compare(UnsafeUtility.ReadArrayElement(array, (lo + child - 1)), val) < 0)
{
break;
}
UnsafeUtility.WriteArrayElement(array, lo + i - 1, UnsafeUtility.ReadArrayElement(array, lo + child - 1));
i = child;
}
UnsafeUtility.WriteArrayElement(array, lo + i - 1, val);
}
unsafe static void SwapStruct(void* array, int lhs, int rhs)
where T : unmanaged
{
T val = UnsafeUtility.ReadArrayElement(array, lhs);
UnsafeUtility.WriteArrayElement(array, lhs, UnsafeUtility.ReadArrayElement