A game about forced loneliness, made by TACStudios
tacstudios.tngl.sh
1<#/*THIS IS A T4 FILE - see t4_text_templating.md for what it is and how to run codegen*/#>
2<#@ template debug="True" #>
3<#@ output extension=".gen.cs" #>
4<#@ assembly name="System.Core" #>
5using NUnit.Framework;
6using System;
7using System.Collections;
8using System.Collections.Generic;
9using Unity.Burst;
10using Unity.Collections;
11using Unity.Collections.Tests;
12using Unity.Collections.LowLevel.Unsafe;
13using Unity.Jobs;
14using Unity.Mathematics;
15
16//------------------------------------------------------------------------------
17// <auto-generated>
18// This code was generated by a tool.
19//
20// TextTransform Packages/com.unity.collections/Unity.Collections.Tests/NativeSortTests.tt
21//
22// Changes to this file may cause incorrect behavior and will be lost if
23// the code is regenerated.
24// </auto-generated>
25//------------------------------------------------------------------------------
26
27[assembly: RegisterGenericJobType(typeof(SortJob<int, NativeSortExtension.DefaultComparer<int>>))]
28[assembly: RegisterGenericJobType(typeof(SortJob<int, NativeSortExtension.DefaultComparer<int>>.SegmentSort))]
29[assembly: RegisterGenericJobType(typeof(SortJob<int, NativeSortExtension.DefaultComparer<int>>.SegmentSortMerge))]
30[assembly: RegisterGenericJobType(typeof(SortJob<int, NativeSortTests.DescendingComparer<int>>))]
31[assembly: RegisterGenericJobType(typeof(SortJob<int, NativeSortTests.DescendingComparer<int>>.SegmentSort))]
32[assembly: RegisterGenericJobType(typeof(SortJob<int, NativeSortTests.DescendingComparer<int>>.SegmentSortMerge))]
33
34[assembly: RegisterGenericJobType(typeof(SortJob<int, NativeSortTests.BrokenComparer0<int>>))]
35[assembly: RegisterGenericJobType(typeof(SortJob<int, NativeSortTests.BrokenComparer0<int>>.SegmentSort))]
36[assembly: RegisterGenericJobType(typeof(SortJob<int, NativeSortTests.BrokenComparer0<int>>.SegmentSortMerge))]
37[assembly: RegisterGenericJobType(typeof(SortJob<int, NativeSortTests.BrokenComparer1<int>>))]
38[assembly: RegisterGenericJobType(typeof(SortJob<int, NativeSortTests.BrokenComparer1<int>>.SegmentSort))]
39[assembly: RegisterGenericJobType(typeof(SortJob<int, NativeSortTests.BrokenComparer1<int>>.SegmentSortMerge))]
40[assembly: RegisterGenericJobType(typeof(SortJob<int, NativeSortTests.BrokenComparer2<int>>))]
41[assembly: RegisterGenericJobType(typeof(SortJob<int, NativeSortTests.BrokenComparer2<int>>.SegmentSort))]
42[assembly: RegisterGenericJobType(typeof(SortJob<int, NativeSortTests.BrokenComparer2<int>>.SegmentSortMerge))]
43[assembly: RegisterGenericJobType(typeof(SortJob<int, NativeSortTests.BrokenComparer3<int>>))]
44[assembly: RegisterGenericJobType(typeof(SortJob<int, NativeSortTests.BrokenComparer3<int>>.SegmentSort))]
45[assembly: RegisterGenericJobType(typeof(SortJob<int, NativeSortTests.BrokenComparer3<int>>.SegmentSortMerge))]
46
47internal class NativeSortTests : CollectionsTestCommonBase
48{
49 internal struct DescendingComparer<T> : IComparer<T> where T : IComparable<T>
50 {
51 public int Compare(T x, T y) => y.CompareTo(x);
52 }
53
54 internal struct BrokenComparer0<T> : IComparer<T> where T : IComparable<T>
55 {
56 public int Compare(T x, T y)
57 {
58 int result = y.CompareTo(x);
59 return result < 0 ? -1 : 1;
60 }
61 }
62
63 internal struct BrokenComparer1<T> : IComparer<T> where T : IComparable<T>
64 {
65 public int Compare(T x, T y)
66 {
67 int result = y.CompareTo(x);
68 return result > 0 ? 1 : -1;
69 }
70 }
71
72 internal struct BrokenComparer2<T> : IComparer<T> where T : IComparable<T>
73 {
74 public int Compare(T x, T y)
75 {
76 int result = y.CompareTo(x);
77 return math.max(0, result);
78 }
79 }
80
81 internal struct BrokenComparer3<T> : IComparer<T> where T : IComparable<T>
82 {
83 public int Compare(T x, T y)
84 {
85 int result = y.CompareTo(x);
86 return math.min(0, result);
87 }
88 }
89
90 [Test]
91 public void NativeArraySlice_BinarySearch()
92 {
93 var init = new int[] { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53 };
94 var container = new NativeArray<int>(16, Allocator.Persistent);
95 var slice = new NativeSlice<int>(container, 0, container.Length);
96 var arrayRo = container.AsReadOnly();
97 container.CopyFrom(init);
98
99 for (int i = 0, num = container.Length; i < num; ++i)
100 {
101 Assert.AreEqual(i, container.BinarySearch(container[i]));
102 Assert.AreEqual(i, slice.BinarySearch(container[i]));
103 Assert.AreEqual(i, arrayRo.BinarySearch(container[i]));
104 }
105
106 container.Dispose();
107 }
108
109 struct BinarySearch_Job : IJob
110 {
111 [ReadOnly]
112 public NativeArray<int> array;
113
114 [ReadOnly]
115 public NativeSlice<int> slice;
116
117 [ReadOnly]
118 public NativeArray<int>.ReadOnly arrayRo;
119
120 [ReadOnly]
121 public NativeList<int> nativeList;
122
123 public void Execute()
124 {
125 for (int i = 0, num = array.Length; i < num; ++i)
126 {
127 Assert.AreEqual(i, array.BinarySearch(array[i]));
128 Assert.AreEqual(i, slice.BinarySearch(array[i]));
129 Assert.AreEqual(i, arrayRo.BinarySearch(array[i]));
130 Assert.AreEqual(i, nativeList.BinarySearch(array[i]));
131 }
132 }
133 }
134
135 [Test]
136 public void BinarySearch_From_Job()
137 {
138 var init = new int[] { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53 };
139 var container = new NativeArray<int>(16, Allocator.Persistent);
140 var slice = new NativeSlice<int>(container, 0, container.Length);
141 var arrayRo = container.AsReadOnly();
142 container.CopyFrom(init);
143
144 var nativeList = new NativeList<int>(16, Allocator.Persistent);
145 nativeList.CopyFrom(container);
146
147 new BinarySearch_Job
148 {
149 array = container,
150 slice = slice,
151 arrayRo = arrayRo,
152 nativeList = nativeList,
153
154 }.Run();
155
156 container.Dispose();
157 nativeList.Dispose();
158 }
159
160 [Test]
161 public void NativeArraySlice_BinarySearch_NotFound()
162 {
163 {
164 var container = new NativeArray<int>(1, Allocator.Temp);
165 var slice = new NativeSlice<int>(container, 0, container.Length);
166 var arrayRo = container.AsReadOnly();
167
168 Assert.AreEqual(container.Length, 1);
169 Assert.AreEqual(-2, container.BinarySearch(1));
170 Assert.AreEqual(-2, slice.BinarySearch(1));
171 Assert.AreEqual(-2, arrayRo.BinarySearch(1));
172
173 slice[0] = 1;
174
175 Assert.AreEqual(0, container.BinarySearch(1));
176 Assert.AreEqual(0, slice.BinarySearch(1));
177 Assert.AreEqual(0, arrayRo.BinarySearch(1));
178
179 Assert.AreEqual(-1, container.BinarySearch(-2));
180 Assert.AreEqual(-1, slice.BinarySearch(-2));
181 Assert.AreEqual(-1, arrayRo.BinarySearch(-2));
182
183 Assert.AreEqual(-2, container.BinarySearch(2));
184 Assert.AreEqual(-2, slice.BinarySearch(2));
185 Assert.AreEqual(-2, arrayRo.BinarySearch(2));
186
187 container.Dispose();
188 }
189
190 {
191 var init = new int[] { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15 };
192 var container = new NativeArray<int>(16, Allocator.Temp);
193 var slice = new NativeSlice<int>(container, 0, container.Length);
194 var arrayRo = container.AsReadOnly();
195
196 container.CopyFrom(init);
197
198 for (int i = 0, num = container.Length; i < num; ++i)
199 {
200 Assert.AreEqual(~container.Length, container.BinarySearch(i + 16));
201 Assert.AreEqual(~slice.Length, slice.BinarySearch(i + 16));
202 Assert.AreEqual(~arrayRo.Length, arrayRo.BinarySearch(i + 16));
203 }
204
205 container.Dispose();
206 }
207
208 {
209 var init = new int[] { 0, 2, 4, 6, 8, 10, 12, 14 };
210 var container = new NativeArray<int>(8, Allocator.Temp);
211 var slice = new NativeSlice<int>(container, 0, container.Length);
212 var arrayRo = container.AsReadOnly();
213
214 container.CopyFrom(init);
215
216 for (int i = 0, num = container.Length; i < num; ++i)
217 {
218 Assert.AreEqual(~(i + 1) /* ~index of first greatest value searched */, container.BinarySearch(i * 2 + 1));
219 Assert.AreEqual(~(i + 1) /* ~index of first greatest value searched */, slice.BinarySearch(i * 2 + 1));
220 Assert.AreEqual(~(i + 1) /* ~index of first greatest value searched */, arrayRo.BinarySearch(i * 2 + 1));
221 }
222
223 container.Dispose();
224 }
225 }
226
227 [Test]
228 public void NativeArraySlice_BinarySearch_NotFound_Reference_ArrayList()
229 {
230 {
231 var reference = new ArrayList();
232 reference.Add(0);
233 var container = new NativeArray<int>(1, Allocator.Temp);
234 var slice = new NativeSlice<int>(container, 0, container.Length);
235 var arrayRo = container.AsReadOnly();
236
237 Assert.AreEqual(container.Length, 1);
238 Assert.AreEqual(-2, reference.BinarySearch(1));
239 Assert.AreEqual(-2, container.BinarySearch(1));
240 Assert.AreEqual(-2, slice.BinarySearch(1));
241 Assert.AreEqual(-2, arrayRo.BinarySearch(1));
242
243 reference[0] = 1;
244 slice[0] = 1;
245
246 Assert.AreEqual(0, reference.BinarySearch(1));
247 Assert.AreEqual(0, container.BinarySearch(1));
248 Assert.AreEqual(0, slice.BinarySearch(1));
249 Assert.AreEqual(0, arrayRo.BinarySearch(1));
250
251 Assert.AreEqual(-1, reference.BinarySearch(-2));
252 Assert.AreEqual(-1, container.BinarySearch(-2));
253 Assert.AreEqual(-1, slice.BinarySearch(-2));
254 Assert.AreEqual(-1, arrayRo.BinarySearch(-2));
255
256 Assert.AreEqual(-2, reference.BinarySearch(2));
257 Assert.AreEqual(-2, container.BinarySearch(2));
258 Assert.AreEqual(-2, slice.BinarySearch(2));
259 Assert.AreEqual(-2, arrayRo.BinarySearch(2));
260 }
261
262 {
263 var init = new int[] { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15 };
264 var container = new NativeArray<int>(16, Allocator.Temp);
265 var slice = new NativeSlice<int>(container, 0, container.Length);
266 var arrayRo = container.AsReadOnly();
267
268 container.CopyFrom(init);
269 var reference = new ArrayList(init);
270
271 for (int i = 0, num = container.Length; i < num; ++i)
272 {
273 Assert.AreEqual(~reference.Count, reference.BinarySearch(i + 16));
274 Assert.AreEqual(~container.Length, container.BinarySearch(i + 16));
275 Assert.AreEqual(~slice.Length, slice.BinarySearch(i + 16));
276 Assert.AreEqual(~arrayRo.Length, arrayRo.BinarySearch(i + 16));
277 }
278 }
279
280 {
281 var init = new int[] { 0, 2, 4, 6, 8, 10, 12, 14 };
282 var container = new NativeArray<int>(8, Allocator.Temp);
283 var slice = new NativeSlice<int>(container, 0, container.Length);
284 var arrayRo = container.AsReadOnly();
285
286 container.CopyFrom(init);
287 var reference = new ArrayList(init);
288
289 for (int i = 0, num = container.Length; i < num; ++i)
290 {
291 Assert.AreEqual(~(i + 1) /* ~index of first greatest value searched */, reference.BinarySearch(i * 2 + 1));
292 Assert.AreEqual(~(i + 1) /* ~index of first greatest value searched */, container.BinarySearch(i * 2 + 1));
293 Assert.AreEqual(~(i + 1) /* ~index of first greatest value searched */, slice.BinarySearch(i * 2 + 1));
294 Assert.AreEqual(~(i + 1) /* ~index of first greatest value searched */, arrayRo.BinarySearch(i * 2 + 1));
295 }
296 }
297 }
298
299
300<#
301{
302 foreach (var ContainerType in new[] {
303 ( "NativeList" ),
304 ( "UnsafeList" ),
305 }) {
306#>
307
308 [Test]
309 public void <#=ContainerType#>_BinarySearch()
310 {
311 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 })
312 {
313 for (int i = 0, num = container.Length; i < num; ++i)
314 {
315 Assert.AreEqual(i, container.BinarySearch(container[i]));
316 }
317 }
318 }
319
320 [Test]
321 public void <#=ContainerType#>_BinarySearch_NotFound()
322 {
323 {
324 var container = new <#=ContainerType#><int>(1, Allocator.Temp);
325 Assert.AreEqual(-1, container.BinarySearch(1));
326
327 container.Add(1);
328
329 Assert.AreEqual(0, container.BinarySearch(1));
330 Assert.AreEqual(-1, container.BinarySearch(-2));
331 Assert.AreEqual(-2, container.BinarySearch(2));
332 }
333
334 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 })
335 {
336 for (int i = 0, num = container.Length; i < num; ++i)
337 {
338 Assert.AreEqual(~container.Length, container.BinarySearch(i + 16));
339 }
340 }
341
342 using (var container = new <#=ContainerType#><int>(8, Allocator.Temp) { 0, 2, 4, 6, 8, 10, 12, 14 })
343 {
344 for (int i = 0, num = container.Length; i < num; ++i)
345 {
346 Assert.AreEqual(~(i + 1) /* ~index of first greatest value searched */, container.BinarySearch(i * 2 + 1));
347 }
348 }
349 }
350
351 [Test]
352 public void <#=ContainerType#>_BinarySearch_NotFound_Reference_ArrayList()
353 {
354 {
355 var reference = new ArrayList();
356 var container = new <#=ContainerType#><int>(1, Allocator.Temp);
357 Assert.AreEqual(-1, reference.BinarySearch(1));
358 Assert.AreEqual(-1, container.BinarySearch(1));
359
360 reference.Add(1);
361 container.Add(1);
362
363 Assert.AreEqual(0, reference.BinarySearch(1));
364 Assert.AreEqual(0, container.BinarySearch(1));
365
366 Assert.AreEqual(-1, reference.BinarySearch(-2));
367 Assert.AreEqual(-1, container.BinarySearch(-2));
368
369 Assert.AreEqual(-2, reference.BinarySearch(2));
370 Assert.AreEqual(-2, container.BinarySearch(2));
371 }
372
373 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 })
374 {
375 var reference = new ArrayList() { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15 };
376
377 for (int i = 0, num = container.Length; i < num; ++i)
378 {
379 Assert.AreEqual(~reference.Count, reference.BinarySearch(i + 16));
380 Assert.AreEqual(~container.Length, container.BinarySearch(i + 16));
381 }
382 }
383
384 using (var container = new <#=ContainerType#><int>(8, Allocator.Temp) { 0, 2, 4, 6, 8, 10, 12, 14 })
385 {
386 var reference = new ArrayList() { 0, 2, 4, 6, 8, 10, 12, 14 };
387
388 for (int i = 0, num = container.Length; i < num; ++i)
389 {
390 Assert.AreEqual(~(i + 1) /* ~index of first greatest value searched */, reference.BinarySearch(i * 2 + 1));
391 Assert.AreEqual(~(i + 1) /* ~index of first greatest value searched */, container.BinarySearch(i * 2 + 1));
392 }
393 }
394 }
395
396 [Test]
397 public void <#=ContainerType#>_GenericSortJob_NoBurst()
398 {
399 <#=ContainerType#>_GenericSortJob();
400 }
401
402 [BurstCompile]
403 public static void Bursted_<#=ContainerType#>_GenericSortJob()
404 {
405 <#=ContainerType#>_GenericSortJob();
406 }
407
408 [Test]
409 public void <#=ContainerType#>_GenericSortJob_Burst()
410 {
411 Bursted_<#=ContainerType#>_GenericSortJob();
412 }
413
414 public static void <#=ContainerType#>_GenericSortJob()
415 {
416 using (var container = new <#=ContainerType#><int>(5, Allocator.Persistent))
417 {
418 for (var i = 0; i < 5; ++i)
419 {
420 container.Add(4 - i);
421 }
422
423 container.Sort();
424
425 for (var i = 0; i < 5; ++i)
426 {
427 Assert.AreEqual(i, container[i]);
428 }
429 }
430
431 using (var container = new <#=ContainerType#><int>(5, Allocator.Persistent))
432 {
433 for (var i = 0; i < 5; ++i)
434 {
435 container.Add(4 - i);
436 }
437
438 container.SortJob().Schedule().Complete();
439
440 for (var i = 0; i < 5; ++i)
441 {
442 Assert.AreEqual(i, container[i]);
443 }
444 }
445 }
446
447 [Test]
448 [TestRequiresDotsDebugOrCollectionChecks]
449 public void <#=ContainerType#>_GenericSortJobCustomComparer_NoBurst()
450 {
451 <#=ContainerType#>_GenericSortJobCustomComparer();
452 }
453
454 [BurstCompile]
455 public static void Bursted_<#=ContainerType#>_GenericSortJobCustomComparer()
456 {
457 <#=ContainerType#>_GenericSortJobCustomComparer();
458 }
459
460 [Test]
461 [TestRequiresDotsDebugOrCollectionChecks]
462 public void <#=ContainerType#>_GenericSortJobCustomComparer_Burst()
463 {
464 Bursted_<#=ContainerType#>_GenericSortJobCustomComparer();
465 }
466
467 public static void <#=ContainerType#>_GenericSortJobCustomComparer()
468 {
469 var num = 35;
470 using (var container = new <#=ContainerType#><int>(num, Allocator.Persistent))
471 {
472 for (var i = 0; i < num; ++i)
473 {
474 container.Add(i);
475 }
476
477 Assert.Throws<InvalidOperationException>(() => container.Sort(new BrokenComparer0<int>()));
478 Assert.Throws<InvalidOperationException>(() => container.Sort(new BrokenComparer1<int>()));
479 Assert.Throws<InvalidOperationException>(() => container.Sort(new BrokenComparer2<int>()));
480 Assert.Throws<InvalidOperationException>(() => container.Sort(new BrokenComparer3<int>()));
481
482 container.Sort(new DescendingComparer<int>());
483
484 for (var i = 0; i < num; ++i)
485 {
486 Assert.AreEqual(num - 1 - i, container[i]);
487 }
488 }
489
490 using (var container = new <#=ContainerType#><int>(num, Allocator.Persistent))
491 {
492 for (var i = 0; i < num; ++i)
493 {
494 container.Add(i);
495 }
496
497 Assert.Throws<InvalidOperationException>(() => container.SortJob(new BrokenComparer0<int>()).Schedule().Complete());
498 Assert.Throws<InvalidOperationException>(() => container.SortJob(new BrokenComparer1<int>()).Schedule().Complete());
499 Assert.Throws<InvalidOperationException>(() => container.SortJob(new BrokenComparer2<int>()).Schedule().Complete());
500 Assert.Throws<InvalidOperationException>(() => container.SortJob(new BrokenComparer3<int>()).Schedule().Complete());
501
502 container.SortJob(new DescendingComparer<int>()).Schedule().Complete();
503
504 for (var i = 0; i < num; ++i)
505 {
506 Assert.AreEqual(num - 1 - i, container[i]);
507 }
508 }
509 }
510<#}}#>
511
512<#
513{
514 foreach (var ContainerType in new[] {
515 ( "FixedList32Bytes" ),
516 ( "FixedList64Bytes" ),
517 ( "FixedList128Bytes" ),
518 ( "FixedList512Bytes" ),
519 ( "FixedList4096Bytes" ),
520 }) {
521#>
522
523 [Test]
524 public void <#=ContainerType#>_GenericSort()
525 {
526 var container = new <#=ContainerType#><int>();
527
528 for (var i = 0; i < 5; ++i)
529 {
530 container.Add(i);
531 }
532
533 container.Sort(new DescendingComparer<int>());
534
535 for (var i = 0; i < 5; ++i)
536 {
537 Assert.AreEqual(4 - i, container[i]);
538 }
539 }
540
541<#}}#>
542 unsafe static void IntroSortNoComparerCheck<T, U>(T* array, int length, U comp)
543 where T : unmanaged
544 where U : IComparer<T>
545 {
546 NativeSortExtension.IntroSort_R<T, U>(array, 0, length - 1, 2 * CollectionHelper.Log2Floor(length), comp);
547 }
548
549 [Test]
550 [TestRequiresDotsDebugOrCollectionChecks]
551 public unsafe void NativeList_BrokenCustomComparerDoesNotCrash()
552 {
553 var rng = new Unity.Mathematics.Random(1);
554
555 var num = 10000;
556 using (var container = new NativeList<int>(num, Allocator.Persistent))
557 {
558 for (var i = 0; i < num; ++i)
559 {
560 container.Add(rng.NextInt());
561 }
562
563 Assert.DoesNotThrow(() => IntroSortNoComparerCheck(container.GetUnsafePtr(), container.Length, new BrokenComparer0<int>()));
564 }
565
566 using (var container = new NativeList<int>(num, Allocator.Persistent))
567 {
568 for (var i = 0; i < num; ++i)
569 {
570 container.Add(rng.NextInt());
571 }
572
573 Assert.DoesNotThrow(() => IntroSortNoComparerCheck(container.GetUnsafePtr(), container.Length, new BrokenComparer1<int>()));
574 }
575
576 using (var container = new NativeList<int>(num, Allocator.Persistent))
577 {
578 for (var i = 0; i < num; ++i)
579 {
580 container.Add(rng.NextInt());
581 }
582
583 Assert.DoesNotThrow(() => IntroSortNoComparerCheck(container.GetUnsafePtr(), container.Length, new BrokenComparer2<int>()));
584 }
585
586 using (var container = new NativeList<int>(num, Allocator.Persistent))
587 {
588 for (var i = 0; i < num; ++i)
589 {
590 container.Add(rng.NextInt());
591 }
592
593 Assert.DoesNotThrow(() => IntroSortNoComparerCheck(container.GetUnsafePtr(), container.Length, new BrokenComparer3<int>()));
594 }
595 }
596}