<#/*THIS IS A T4 FILE - see t4_text_templating.md for what it is and how to run codegen*/#>
<#@ template debug="True" #>
<#@ output extension=".gen.cs" #>
<#@ assembly name="System.Core" #>
using NUnit.Framework;
using System;
using System.Collections;
using System.Collections.Generic;
using Unity.Burst;
using Unity.Collections;
using Unity.Collections.Tests;
using Unity.Collections.LowLevel.Unsafe;
using Unity.Jobs;
using Unity.Mathematics;
//------------------------------------------------------------------------------
// <auto-generated>
// This code was generated by a tool.
//
// TextTransform Packages/com.unity.collections/Unity.Collections.Tests/NativeSortTests.tt
//
// Changes to this file may cause incorrect behavior and will be lost if
// the code is regenerated.
// </auto-generated>
//------------------------------------------------------------------------------
[assembly: RegisterGenericJobType(typeof(SortJob<int, NativeSortExtension.DefaultComparer<int>>))]
[assembly: RegisterGenericJobType(typeof(SortJob<int, NativeSortExtension.DefaultComparer<int>>.SegmentSort))]
[assembly: RegisterGenericJobType(typeof(SortJob<int, NativeSortExtension.DefaultComparer<int>>.SegmentSortMerge))]
[assembly: RegisterGenericJobType(typeof(SortJob<int, NativeSortTests.DescendingComparer<int>>))]
[assembly: RegisterGenericJobType(typeof(SortJob<int, NativeSortTests.DescendingComparer<int>>.SegmentSort))]
[assembly: RegisterGenericJobType(typeof(SortJob<int, NativeSortTests.DescendingComparer<int>>.SegmentSortMerge))]
[assembly: RegisterGenericJobType(typeof(SortJob<int, NativeSortTests.BrokenComparer0<int>>))]
[assembly: RegisterGenericJobType(typeof(SortJob<int, NativeSortTests.BrokenComparer0<int>>.SegmentSort))]
[assembly: RegisterGenericJobType(typeof(SortJob<int, NativeSortTests.BrokenComparer0<int>>.SegmentSortMerge))]
[assembly: RegisterGenericJobType(typeof(SortJob<int, NativeSortTests.BrokenComparer1<int>>))]
[assembly: RegisterGenericJobType(typeof(SortJob<int, NativeSortTests.BrokenComparer1<int>>.SegmentSort))]
[assembly: RegisterGenericJobType(typeof(SortJob<int, NativeSortTests.BrokenComparer1<int>>.SegmentSortMerge))]
[assembly: RegisterGenericJobType(typeof(SortJob<int, NativeSortTests.BrokenComparer2<int>>))]
[assembly: RegisterGenericJobType(typeof(SortJob<int, NativeSortTests.BrokenComparer2<int>>.SegmentSort))]
[assembly: RegisterGenericJobType(typeof(SortJob<int, NativeSortTests.BrokenComparer2<int>>.SegmentSortMerge))]
[assembly: RegisterGenericJobType(typeof(SortJob<int, NativeSortTests.BrokenComparer3<int>>))]
[assembly: RegisterGenericJobType(typeof(SortJob<int, NativeSortTests.BrokenComparer3<int>>.SegmentSort))]
[assembly: RegisterGenericJobType(typeof(SortJob<int, NativeSortTests.BrokenComparer3<int>>.SegmentSortMerge))]
internal class NativeSortTests : CollectionsTestCommonBase
{
internal struct DescendingComparer<T> : IComparer<T> where T : IComparable<T>
{
public int Compare(T x, T y) => y.CompareTo(x);
}
internal struct BrokenComparer0<T> : IComparer<T> where T : IComparable<T>
{
public int Compare(T x, T y)
{
int result = y.CompareTo(x);
return result < 0 ? -1 : 1;
}
}
internal struct BrokenComparer1<T> : IComparer<T> where T : IComparable<T>
{
public int Compare(T x, T y)
{
int result = y.CompareTo(x);
return result > 0 ? 1 : -1;
}
}
internal struct BrokenComparer2<T> : IComparer<T> where T : IComparable<T>
{
public int Compare(T x, T y)
{
int result = y.CompareTo(x);
return math.max(0, result);
}
}
internal struct BrokenComparer3<T> : IComparer<T> where T : IComparable<T>
{
public int Compare(T x, T y)
{
int result = y.CompareTo(x);
return math.min(0, result);
}
}
[Test]
public void NativeArraySlice_BinarySearch()
{
var init = new int[] { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53 };
var container = new NativeArray<int>(16, Allocator.Persistent);
var slice = new NativeSlice<int>(container, 0, container.Length);
var arrayRo = container.AsReadOnly();
container.CopyFrom(init);
for (int i = 0, num = container.Length; i < num; ++i)
{
Assert.AreEqual(i, container.BinarySearch(container[i]));
Assert.AreEqual(i, slice.BinarySearch(container[i]));
Assert.AreEqual(i, arrayRo.BinarySearch(container[i]));
}
container.Dispose();
}
struct BinarySearch_Job : IJob
{
[ReadOnly]
public NativeArray<int> array;
[ReadOnly]
public NativeSlice<int> slice;
[ReadOnly]
public NativeArray<int>.ReadOnly arrayRo;
[ReadOnly]
public NativeList<int> nativeList;
public void Execute()
{
for (int i = 0, num = array.Length; i < num; ++i)
{
Assert.AreEqual(i, array.BinarySearch(array[i]));
Assert.AreEqual(i, slice.BinarySearch(array[i]));
Assert.AreEqual(i, arrayRo.BinarySearch(array[i]));
Assert.AreEqual(i, nativeList.BinarySearch(array[i]));
}
}
}
[Test]
public void BinarySearch_From_Job()
{
var init = new int[] { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53 };
var container = new NativeArray<int>(16, Allocator.Persistent);
var slice = new NativeSlice<int>(container, 0, container.Length);
var arrayRo = container.AsReadOnly();
container.CopyFrom(init);
var nativeList = new NativeList<int>(16, Allocator.Persistent);
nativeList.CopyFrom(container);
new BinarySearch_Job
{
array = container,
slice = slice,
arrayRo = arrayRo,
nativeList = nativeList,
}.Run();
container.Dispose();
nativeList.Dispose();
}
[Test]
public void NativeArraySlice_BinarySearch_NotFound()
{
{
var container = new NativeArray<int>(1, Allocator.Temp);
var slice = new NativeSlice<int>(container, 0, container.Length);
var arrayRo = container.AsReadOnly();
Assert.AreEqual(container.Length, 1);
Assert.AreEqual(-2, ~container.Length);
Assert.AreEqual(-2, ~slice.Length);
Assert.AreEqual(-2, ~arrayRo.Length);
Assert.AreEqual(-2, container.BinarySearch(1));
Assert.AreEqual(-2, slice.BinarySearch(1));
Assert.AreEqual(-2, arrayRo.BinarySearch(1));
slice[0] = 1;
Assert.AreEqual(0, container.BinarySearch(1));
Assert.AreEqual(0, slice.BinarySearch(1));
Assert.AreEqual(0, arrayRo.BinarySearch(1));
Assert.AreEqual(-1, container.BinarySearch(-2));
var sliceBinarySearchResult = slice.BinarySearch(-2);
Assert.AreEqual(-1, sliceBinarySearchResult);
Assert.AreEqual(-1, arrayRo.BinarySearch(-2));
Assert.AreEqual(0, ~sliceBinarySearchResult);
Assert.AreEqual(-2, container.BinarySearch(2));
Assert.AreEqual(-2, slice.BinarySearch(2));
Assert.AreEqual(-2, arrayRo.BinarySearch(2));
container.Dispose();
}
{
var init = new int[] { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15 };
var container = new NativeArray<int>(16, Allocator.Temp);
var slice = new NativeSlice<int>(container, 0, container.Length);
var arrayRo = container.AsReadOnly();
container.CopyFrom(init);
for (int i = 0, num = container.Length; i < num; ++i)
{
Assert.AreEqual(~container.Length, container.BinarySearch(i + 16));
Assert.AreEqual(~slice.Length, slice.BinarySearch(i + 16));
Assert.AreEqual(~arrayRo.Length, arrayRo.BinarySearch(i + 16));
}
container.Dispose();
}
{
var init = new int[] { 0, 2, 4, 6, 8, 10, 12, 14 };
var container = new NativeArray<int>(8, Allocator.Temp);
var slice = new NativeSlice<int>(container, 0, container.Length);
var arrayRo = container.AsReadOnly();
container.CopyFrom(init);
for (int i = 0, num = container.Length; i < num; ++i)
{
Assert.AreEqual(~(i + 1) /* ~index of first greatest value searched */, container.BinarySearch(i * 2 + 1));
Assert.AreEqual(~(i + 1) /* ~index of first greatest value searched */, slice.BinarySearch(i * 2 + 1));
Assert.AreEqual(~(i + 1) /* ~index of first greatest value searched */, arrayRo.BinarySearch(i * 2 + 1));
}
container.Dispose();
}
}
[Test]
public void NativeArraySlice_BinarySearch_NotFound_Reference_ArrayList()
{
{
var reference = new ArrayList();
reference.Add(0);
var container = new NativeArray<int>(1, Allocator.Temp);
var slice = new NativeSlice<int>(container, 0, container.Length);
var arrayRo = container.AsReadOnly();
Assert.AreEqual(container.Length, 1);
Assert.AreEqual(-2, ~reference.Count);
Assert.AreEqual(-2, ~container.Length);
Assert.AreEqual(-2, ~slice.Length);
Assert.AreEqual(-2, reference.BinarySearch(1));
Assert.AreEqual(-2, container.BinarySearch(1));
Assert.AreEqual(-2, slice.BinarySearch(1));
Assert.AreEqual(-2, arrayRo.BinarySearch(1));
reference[0] = 1;
slice[0] = 1;
Assert.AreEqual(0, reference.BinarySearch(1));
Assert.AreEqual(0, container.BinarySearch(1));
Assert.AreEqual(0, slice.BinarySearch(1));
Assert.AreEqual(0, arrayRo.BinarySearch(1));
Assert.AreEqual(-1, reference.BinarySearch(-2));
Assert.AreEqual(0, ~reference.BinarySearch(-2));
Assert.AreEqual(-1, container.BinarySearch(-2));
Assert.AreEqual(-1, slice.BinarySearch(-2));
Assert.AreEqual(-1, arrayRo.BinarySearch(-2));
Assert.AreEqual(-2, reference.BinarySearch(2));
Assert.AreEqual(-2, container.BinarySearch(2));
Assert.AreEqual(-2, slice.BinarySearch(2));
Assert.AreEqual(-2, arrayRo.BinarySearch(2));
}
{
var init = new int[] { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15 };
var container = new NativeArray<int>(16, Allocator.Temp);
var slice = new NativeSlice<int>(container, 0, container.Length);
var arrayRo = container.AsReadOnly();
container.CopyFrom(init);
var reference = new ArrayList(init);
for (int i = 0, num = container.Length; i < num; ++i)
{
Assert.AreEqual(~reference.Count, reference.BinarySearch(i + 16));
Assert.AreEqual(~container.Length, container.BinarySearch(i + 16));
Assert.AreEqual(~slice.Length, slice.BinarySearch(i + 16));
Assert.AreEqual(~arrayRo.Length, arrayRo.BinarySearch(i + 16));
}
}
{
var init = new int[] { 0, 2, 4, 6, 8, 10, 12, 14 };
var container = new NativeArray<int>(8, Allocator.Temp);
var slice = new NativeSlice<int>(container, 0, container.Length);
var arrayRo = container.AsReadOnly();
container.CopyFrom(init);
var reference = new ArrayList(init);
for (int i = 0, num = container.Length; i < num; ++i)
{
Assert.AreEqual(~(i + 1) /* ~index of first greatest value searched */, reference.BinarySearch(i * 2 + 1));
Assert.AreEqual(~(i + 1) /* ~index of first greatest value searched */, container.BinarySearch(i * 2 + 1));
Assert.AreEqual(~(i + 1) /* ~index of first greatest value searched */, slice.BinarySearch(i * 2 + 1));
Assert.AreEqual(~(i + 1) /* ~index of first greatest value searched */, arrayRo.BinarySearch(i * 2 + 1));
}
}
}
<#
{
foreach (var ContainerType in new[] {
( "NativeList" ),
( "UnsafeList" ),
}) {
#>
[Test]
public void <#=ContainerType#>_BinarySearch()
{
using (var container = new <#=ContainerType#><int>(16, Allocator.Persistent) { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53 })
{
for (int i = 0, num = container.Length; i < num; ++i)
{
Assert.AreEqual(i, container.BinarySearch(container[i]));
}
}
}
[Test]
public void <#=ContainerType#>_BinarySearch_NotFound()
{
{
var container = new <#=ContainerType#><int>(1, Allocator.Temp);
Assert.AreEqual(-1, ~container.Length);
Assert.AreEqual(-1, container.BinarySearch(1));
container.Add(1);
Assert.AreEqual(-2, ~container.Length);
Assert.AreEqual(0, container.BinarySearch(1));
Assert.AreEqual(-1, container.BinarySearch(-2));
Assert.AreEqual(0, ~container.BinarySearch(-2));
Assert.AreEqual(-2, container.BinarySearch(2));
}
using (var container = new <#=ContainerType#><int>(16, Allocator.Temp) { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15 })
{
for (int i = 0, num = container.Length; i < num; ++i)
{
Assert.AreEqual(~container.Length, container.BinarySearch(i + 16));
}
}
using (var container = new <#=ContainerType#><int>(8, Allocator.Temp) { 0, 2, 4, 6, 8, 10, 12, 14 })
{
for (int i = 0, num = container.Length; i < num; ++i)
{
Assert.AreEqual(~(i + 1) /* ~index of first greatest value searched */, container.BinarySearch(i * 2 + 1));
}
}
}
[Test]
public void <#=ContainerType#>_BinarySearch_NotFound_Reference_ArrayList()
{
{
var reference = new ArrayList();
var container = new <#=ContainerType#><int>(1, Allocator.Temp);
Assert.AreEqual(-1, ~reference.Count);
Assert.AreEqual(-1, reference.BinarySearch(1));
Assert.AreEqual(-1, container.BinarySearch(1));
reference.Add(1);
container.Add(1);
Assert.AreEqual(-2, ~reference.Count);
Assert.AreEqual(0, reference.BinarySearch(1));
Assert.AreEqual(0, container.BinarySearch(1));
Assert.AreEqual(-1, reference.BinarySearch(-2));
Assert.AreEqual(0, ~reference.BinarySearch(-2));
Assert.AreEqual(-1, container.BinarySearch(-2));
Assert.AreEqual(-2, reference.BinarySearch(2));
Assert.AreEqual(-2, container.BinarySearch(2));
}
using (var container = new <#=ContainerType#><int>(16, Allocator.Temp) { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15 })
{
var reference = new ArrayList() { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15 };
for (int i = 0, num = container.Length; i < num; ++i)
{
Assert.AreEqual(~reference.Count, reference.BinarySearch(i + 16));
Assert.AreEqual(~container.Length, container.BinarySearch(i + 16));
}
}
using (var container = new <#=ContainerType#><int>(8, Allocator.Temp) { 0, 2, 4, 6, 8, 10, 12, 14 })
{
var reference = new ArrayList() { 0, 2, 4, 6, 8, 10, 12, 14 };
for (int i = 0, num = container.Length; i < num; ++i)
{
Assert.AreEqual(~(i + 1) /* ~index of first greatest value searched */, reference.BinarySearch(i * 2 + 1));
Assert.AreEqual(~(i + 1) /* ~index of first greatest value searched */, container.BinarySearch(i * 2 + 1));
}
}
}
[Test]
public void <#=ContainerType#>_GenericSortJob_NoBurst()
{
<#=ContainerType#>_GenericSortJob();
}
[BurstCompile]
public static void Bursted_<#=ContainerType#>_GenericSortJob()
{
<#=ContainerType#>_GenericSortJob();
}
[Test]
public void <#=ContainerType#>_GenericSortJob_Burst()
{
Bursted_<#=ContainerType#>_GenericSortJob();
}
public static void <#=ContainerType#>_GenericSortJob()
{
using (var container = new <#=ContainerType#><int>(5, Allocator.Persistent))
{
for (var i = 0; i < 5; ++i)
{
container.Add(4 - i);
}
container.Sort();
for (var i = 0; i < 5; ++i)
{
Assert.AreEqual(i, container[i]);
}
}
using (var container = new <#=ContainerType#><int>(5, Allocator.Persistent))
{
for (var i = 0; i < 5; ++i)
{
container.Add(4 - i);
}
container.SortJob().Schedule().Complete();
for (var i = 0; i < 5; ++i)
{
Assert.AreEqual(i, container[i]);
}
}
}
[Test]
[TestRequiresDotsDebugOrCollectionChecks]
public void <#=ContainerType#>_GenericSortJobCustomComparer_NoBurst()
{
<#=ContainerType#>_GenericSortJobCustomComparer();
}
[BurstCompile]
public static void Bursted_<#=ContainerType#>_GenericSortJobCustomComparer()
{
<#=ContainerType#>_GenericSortJobCustomComparer();
}
[Test]
[TestRequiresDotsDebugOrCollectionChecks]
public void <#=ContainerType#>_GenericSortJobCustomComparer_Burst()
{
Bursted_<#=ContainerType#>_GenericSortJobCustomComparer();
}
public static void <#=ContainerType#>_GenericSortJobCustomComparer()
{
var num = 35;
using (var container = new <#=ContainerType#><int>(num, Allocator.Persistent))
{
for (var i = 0; i < num; ++i)
{
container.Add(i);
}
Assert.Throws<InvalidOperationException>(() => container.Sort(new BrokenComparer0<int>()));
Assert.Throws<InvalidOperationException>(() => container.Sort(new BrokenComparer1<int>()));
Assert.Throws<InvalidOperationException>(() => container.Sort(new BrokenComparer2<int>()));
Assert.Throws<InvalidOperationException>(() => container.Sort(new BrokenComparer3<int>()));
container.Sort(new DescendingComparer<int>());
for (var i = 0; i < num; ++i)
{
Assert.AreEqual(num - 1 - i, container[i]);
}
}
using (var container = new <#=ContainerType#><int>(num, Allocator.Persistent))
{
for (var i = 0; i < num; ++i)
{
container.Add(i);
}
Assert.Throws<InvalidOperationException>(() => container.SortJob(new BrokenComparer0<int>()).Schedule().Complete());
Assert.Throws<InvalidOperationException>(() => container.SortJob(new BrokenComparer1<int>()).Schedule().Complete());
Assert.Throws<InvalidOperationException>(() => container.SortJob(new BrokenComparer2<int>()).Schedule().Complete());
Assert.Throws<InvalidOperationException>(() => container.SortJob(new BrokenComparer3<int>()).Schedule().Complete());
container.SortJob(new DescendingComparer<int>()).Schedule().Complete();
for (var i = 0; i < num; ++i)
{
Assert.AreEqual(num - 1 - i, container[i]);
}
}
}
<#}}#>
<#
{
foreach (var ContainerType in new[] {
( "FixedList32Bytes" ),
( "FixedList64Bytes" ),
( "FixedList128Bytes" ),
( "FixedList512Bytes" ),
( "FixedList4096Bytes" ),
}) {
#>
[Test]
public void <#=ContainerType#>_GenericSort()
{
var container = new <#=ContainerType#><int>();
for (var i = 0; i < 5; ++i)
{
container.Add(i);
}
container.Sort(new DescendingComparer<int>());
for (var i = 0; i < 5; ++i)
{
Assert.AreEqual(4 - i, container[i]);
}
}
<#}}#>
unsafe static void IntroSortNoComparerCheck<T, U>(T* array, int length, U comp)
where T : unmanaged
where U : IComparer<T>
{
NativeSortExtension.IntroSort_R<T, U>(array, 0, length - 1, 2 * CollectionHelper.Log2Floor(length), comp);
}
[Test]
[TestRequiresDotsDebugOrCollectionChecks]
public unsafe void NativeList_BrokenCustomComparerDoesNotCrash()
{
var rng = new Unity.Mathematics.Random(1);
var num = 10000;
using (var container = new NativeList<int>(num, Allocator.Persistent))
{
for (var i = 0; i < num; ++i)
{
container.Add(rng.NextInt());
}
Assert.DoesNotThrow(() => IntroSortNoComparerCheck(container.GetUnsafePtr(), container.Length, new BrokenComparer0<int>()));
}
using (var container = new NativeList<int>(num, Allocator.Persistent))
{
for (var i = 0; i < num; ++i)
{
container.Add(rng.NextInt());
}
Assert.DoesNotThrow(() => IntroSortNoComparerCheck(container.GetUnsafePtr(), container.Length, new BrokenComparer1<int>()));
}
using (var container = new NativeList<int>(num, Allocator.Persistent))
{
for (var i = 0; i < num; ++i)
{
container.Add(rng.NextInt());
}
Assert.DoesNotThrow(() => IntroSortNoComparerCheck(container.GetUnsafePtr(), container.Length, new BrokenComparer2<int>()));
}
using (var container = new NativeList<int>(num, Allocator.Persistent))
{
for (var i = 0; i < num; ++i)
{
container.Add(rng.NextInt());
}
Assert.DoesNotThrow(() => IntroSortNoComparerCheck(container.GetUnsafePtr(), container.Length, new BrokenComparer3<int>()));
}
}
}