Terraria v1.4.4.9
Terraria source code documentation
Loading...
Searching...
No Matches
GenericArraySortHelper.cs
Go to the documentation of this file.
1using System.Numerics;
2using System.Runtime.CompilerServices;
3using System.Runtime.InteropServices;
4using Internal.Runtime.CompilerServices;
5
6namespace System.Collections.Generic;
7
8internal sealed class GenericArraySortHelper<T> : IArraySortHelper<T> where T : IComparable<T>
9{
10 public void Sort(Span<T> keys, IComparer<T> comparer)
11 {
12 try
13 {
14 if (comparer == null || comparer == Comparer<T>.Default)
15 {
16 if (keys.Length <= 1)
17 {
18 return;
19 }
20 if (typeof(T) == typeof(double) || typeof(T) == typeof(float) || typeof(T) == typeof(Half))
21 {
22 int num = SortUtils.MoveNansToFront(keys, default(Span<byte>));
23 if (num == keys.Length)
24 {
25 return;
26 }
27 keys = keys.Slice(num);
28 }
29 IntroSort(keys, 2 * (BitOperations.Log2((uint)keys.Length) + 1));
30 }
31 else
32 {
33 ArraySortHelper<T>.IntrospectiveSort(keys, comparer.Compare);
34 }
35 }
36 catch (IndexOutOfRangeException)
37 {
38 ThrowHelper.ThrowArgumentException_BadComparer(comparer);
39 }
40 catch (Exception e)
41 {
42 ThrowHelper.ThrowInvalidOperationException(ExceptionResource.InvalidOperation_IComparerFailed, e);
43 }
44 }
45
46 public int BinarySearch(T[] array, int index, int length, T value, IComparer<T> comparer)
47 {
48 try
49 {
50 if (comparer == null || comparer == Comparer<T>.Default)
51 {
52 return BinarySearch(array, index, length, value);
53 }
54 return ArraySortHelper<T>.InternalBinarySearch(array, index, length, value, comparer);
55 }
56 catch (Exception e)
57 {
58 ThrowHelper.ThrowInvalidOperationException(ExceptionResource.InvalidOperation_IComparerFailed, e);
59 return 0;
60 }
61 }
62
63 private static int BinarySearch(T[] array, int index, int length, T value)
64 {
65 int num = index;
66 int num2 = index + length - 1;
67 while (num <= num2)
68 {
69 int num3 = num + (num2 - num >> 1);
70 int num4 = ((array[num3] != null) ? array[num3].CompareTo(value) : ((value != null) ? (-1) : 0));
71 if (num4 == 0)
72 {
73 return num3;
74 }
75 if (num4 < 0)
76 {
77 num = num3 + 1;
78 }
79 else
80 {
81 num2 = num3 - 1;
82 }
83 }
84 return ~num;
85 }
86
87 [MethodImpl(MethodImplOptions.AggressiveInlining)]
88 private static void SwapIfGreater(ref T i, ref T j)
89 {
90 if (i != null && GreaterThan(ref i, ref j))
91 {
92 Swap(ref i, ref j);
93 }
94 }
95
96 [MethodImpl(MethodImplOptions.AggressiveInlining)]
97 private static void Swap(ref T i, ref T j)
98 {
99 T val = i;
100 i = j;
101 j = val;
102 }
103
104 private static void IntroSort(Span<T> keys, int depthLimit)
105 {
106 int num = keys.Length;
107 while (num > 1)
108 {
109 if (num <= 16)
110 {
111 switch (num)
112 {
113 case 2:
114 SwapIfGreater(ref keys[0], ref keys[1]);
115 break;
116 case 3:
117 {
118 ref T j = ref keys[2];
119 ref T reference = ref keys[1];
120 ref T i = ref keys[0];
121 SwapIfGreater(ref i, ref reference);
122 SwapIfGreater(ref i, ref j);
123 SwapIfGreater(ref reference, ref j);
124 break;
125 }
126 default:
127 InsertionSort(keys.Slice(0, num));
128 break;
129 }
130 break;
131 }
132 if (depthLimit == 0)
133 {
134 HeapSort(keys.Slice(0, num));
135 break;
136 }
137 depthLimit--;
138 int num2 = PickPivotAndPartition(keys.Slice(0, num));
139 Span<T> span = keys;
140 IntroSort(span[(num2 + 1)..num], depthLimit);
141 num = num2;
142 }
143 }
144
145 private static int PickPivotAndPartition(Span<T> keys)
146 {
147 ref T reference = ref MemoryMarshal.GetReference(keys);
148 ref T j = ref Unsafe.Add(ref reference, keys.Length - 1);
149 ref T reference2 = ref Unsafe.Add(ref reference, keys.Length - 1 >> 1);
150 SwapIfGreater(ref reference, ref reference2);
151 SwapIfGreater(ref reference, ref j);
152 SwapIfGreater(ref reference2, ref j);
153 ref T reference3 = ref Unsafe.Add(ref reference, keys.Length - 2);
154 T left = reference2;
155 Swap(ref reference2, ref reference3);
156 ref T reference4 = ref reference;
157 ref T reference5 = ref reference3;
158 while (Unsafe.IsAddressLessThan(ref reference4, ref reference5))
159 {
160 if (left == null)
161 {
162 while (Unsafe.IsAddressLessThan(ref reference4, ref reference3))
163 {
164 ref T reference6 = ref Unsafe.Add(ref reference4, 1);
165 reference4 = ref reference6;
166 if (reference6 != null)
167 {
168 break;
169 }
170 }
171 while (Unsafe.IsAddressGreaterThan(ref reference5, ref reference))
172 {
173 ref T reference7 = ref Unsafe.Add(ref reference5, -1);
174 reference5 = ref reference7;
175 if (reference7 == null)
176 {
177 break;
178 }
179 }
180 }
181 else
182 {
183 while (Unsafe.IsAddressLessThan(ref reference4, ref reference3))
184 {
185 ref T reference8 = ref Unsafe.Add(ref reference4, 1);
186 reference4 = ref reference8;
187 if (!GreaterThan(ref left, ref reference8))
188 {
189 break;
190 }
191 }
192 while (Unsafe.IsAddressGreaterThan(ref reference5, ref reference))
193 {
194 ref T reference9 = ref Unsafe.Add(ref reference5, -1);
195 reference5 = ref reference9;
196 if (!LessThan(ref left, ref reference9))
197 {
198 break;
199 }
200 }
201 }
202 if (!Unsafe.IsAddressLessThan(ref reference4, ref reference5))
203 {
204 break;
205 }
206 Swap(ref reference4, ref reference5);
207 }
208 if (!Unsafe.AreSame(ref reference4, ref reference3))
209 {
210 Swap(ref reference4, ref reference3);
211 }
212 return (int)((nint)Unsafe.ByteOffset(ref reference, ref reference4) / Unsafe.SizeOf<T>());
213 }
214
215 private static void HeapSort(Span<T> keys)
216 {
217 int length = keys.Length;
218 for (int num = length >> 1; num >= 1; num--)
219 {
220 DownHeap(keys, num, length);
221 }
222 for (int num2 = length; num2 > 1; num2--)
223 {
224 Swap(ref keys[0], ref keys[num2 - 1]);
225 DownHeap(keys, 1, num2 - 1);
226 }
227 }
228
229 private static void DownHeap(Span<T> keys, int i, int n)
230 {
231 T left = keys[i - 1];
232 while (i <= n >> 1)
233 {
234 int num = 2 * i;
235 if (num < n && (keys[num - 1] == null || LessThan(ref keys[num - 1], ref keys[num])))
236 {
237 num++;
238 }
239 if (keys[num - 1] == null || !LessThan(ref left, ref keys[num - 1]))
240 {
241 break;
242 }
243 keys[i - 1] = keys[num - 1];
244 i = num;
245 }
246 keys[i - 1] = left;
247 }
248
249 private static void InsertionSort(Span<T> keys)
250 {
251 for (int i = 0; i < keys.Length - 1; i++)
252 {
253 T left = Unsafe.Add(ref MemoryMarshal.GetReference(keys), i + 1);
254 int num = i;
255 while (num >= 0 && (left == null || LessThan(ref left, ref Unsafe.Add(ref MemoryMarshal.GetReference(keys), num))))
256 {
257 Unsafe.Add(ref MemoryMarshal.GetReference(keys), num + 1) = Unsafe.Add(ref MemoryMarshal.GetReference(keys), num);
258 num--;
259 }
260 Unsafe.Add(ref MemoryMarshal.GetReference(keys), num + 1) = left;
261 }
262 }
263
264 [MethodImpl(MethodImplOptions.AggressiveInlining)]
265 private static bool LessThan(ref T left, ref T right)
266 {
267 if (typeof(T) == typeof(byte))
268 {
269 if ((byte)(object)left >= (byte)(object)right)
270 {
271 return false;
272 }
273 return true;
274 }
275 if (typeof(T) == typeof(sbyte))
276 {
277 if ((sbyte)(object)left >= (sbyte)(object)right)
278 {
279 return false;
280 }
281 return true;
282 }
283 if (typeof(T) == typeof(ushort))
284 {
285 if ((ushort)(object)left >= (ushort)(object)right)
286 {
287 return false;
288 }
289 return true;
290 }
291 if (typeof(T) == typeof(short))
292 {
293 if ((short)(object)left >= (short)(object)right)
294 {
295 return false;
296 }
297 return true;
298 }
299 if (typeof(T) == typeof(uint))
300 {
301 if ((uint)(object)left >= (uint)(object)right)
302 {
303 return false;
304 }
305 return true;
306 }
307 if (typeof(T) == typeof(int))
308 {
309 if ((int)(object)left >= (int)(object)right)
310 {
311 return false;
312 }
313 return true;
314 }
315 if (typeof(T) == typeof(ulong))
316 {
317 if ((ulong)(object)left >= (ulong)(object)right)
318 {
319 return false;
320 }
321 return true;
322 }
323 if (typeof(T) == typeof(long))
324 {
325 if ((long)(object)left >= (long)(object)right)
326 {
327 return false;
328 }
329 return true;
330 }
331 if (typeof(T) == typeof(UIntPtr))
332 {
333 if ((nuint)(UIntPtr)(object)left >= (nuint)(UIntPtr)(object)right)
334 {
335 return false;
336 }
337 return true;
338 }
339 if (typeof(T) == typeof(IntPtr))
340 {
341 if ((nint)(IntPtr)(object)left >= (nint)(IntPtr)(object)right)
342 {
343 return false;
344 }
345 return true;
346 }
347 if (typeof(T) == typeof(float))
348 {
349 if (!((float)(object)left < (float)(object)right))
350 {
351 return false;
352 }
353 return true;
354 }
355 if (typeof(T) == typeof(double))
356 {
357 if (!((double)(object)left < (double)(object)right))
358 {
359 return false;
360 }
361 return true;
362 }
363 if (typeof(T) == typeof(Half))
364 {
365 if (!((Half)(object)left < (Half)(object)right))
366 {
367 return false;
368 }
369 return true;
370 }
371 if (left.CompareTo(right) >= 0)
372 {
373 return false;
374 }
375 return true;
376 }
377
378 [MethodImpl(MethodImplOptions.AggressiveInlining)]
379 private static bool GreaterThan(ref T left, ref T right)
380 {
381 if (typeof(T) == typeof(byte))
382 {
383 if ((byte)(object)left <= (byte)(object)right)
384 {
385 return false;
386 }
387 return true;
388 }
389 if (typeof(T) == typeof(sbyte))
390 {
391 if ((sbyte)(object)left <= (sbyte)(object)right)
392 {
393 return false;
394 }
395 return true;
396 }
397 if (typeof(T) == typeof(ushort))
398 {
399 if ((ushort)(object)left <= (ushort)(object)right)
400 {
401 return false;
402 }
403 return true;
404 }
405 if (typeof(T) == typeof(short))
406 {
407 if ((short)(object)left <= (short)(object)right)
408 {
409 return false;
410 }
411 return true;
412 }
413 if (typeof(T) == typeof(uint))
414 {
415 if ((uint)(object)left <= (uint)(object)right)
416 {
417 return false;
418 }
419 return true;
420 }
421 if (typeof(T) == typeof(int))
422 {
423 if ((int)(object)left <= (int)(object)right)
424 {
425 return false;
426 }
427 return true;
428 }
429 if (typeof(T) == typeof(ulong))
430 {
431 if ((ulong)(object)left <= (ulong)(object)right)
432 {
433 return false;
434 }
435 return true;
436 }
437 if (typeof(T) == typeof(long))
438 {
439 if ((long)(object)left <= (long)(object)right)
440 {
441 return false;
442 }
443 return true;
444 }
445 if (typeof(T) == typeof(UIntPtr))
446 {
447 if ((nuint)(UIntPtr)(object)left <= (nuint)(UIntPtr)(object)right)
448 {
449 return false;
450 }
451 return true;
452 }
453 if (typeof(T) == typeof(IntPtr))
454 {
455 if ((nint)(IntPtr)(object)left <= (nint)(IntPtr)(object)right)
456 {
457 return false;
458 }
459 return true;
460 }
461 if (typeof(T) == typeof(float))
462 {
463 if (!((float)(object)left > (float)(object)right))
464 {
465 return false;
466 }
467 return true;
468 }
469 if (typeof(T) == typeof(double))
470 {
471 if (!((double)(object)left > (double)(object)right))
472 {
473 return false;
474 }
475 return true;
476 }
477 if (typeof(T) == typeof(Half))
478 {
479 if (!((Half)(object)left > (Half)(object)right))
480 {
481 return false;
482 }
483 return true;
484 }
485 if (left.CompareTo(right) <= 0)
486 {
487 return false;
488 }
489 return true;
490 }
491}
492internal sealed class GenericArraySortHelper<TKey, TValue> : IArraySortHelper<TKey, TValue> where TKey : IComparable<TKey>
493{
494 public void Sort(Span<TKey> keys, Span<TValue> values, IComparer<TKey> comparer)
495 {
496 try
497 {
498 if (comparer == null || comparer == Comparer<TKey>.Default)
499 {
500 if (keys.Length <= 1)
501 {
502 return;
503 }
504 if (typeof(TKey) == typeof(double) || typeof(TKey) == typeof(float) || typeof(TKey) == typeof(Half))
505 {
506 int num = SortUtils.MoveNansToFront(keys, values);
507 if (num == keys.Length)
508 {
509 return;
510 }
511 keys = keys.Slice(num);
512 values = values.Slice(num);
513 }
514 IntroSort(keys, values, 2 * (BitOperations.Log2((uint)keys.Length) + 1));
515 }
516 else
517 {
518 ArraySortHelper<TKey, TValue>.IntrospectiveSort(keys, values, comparer);
519 }
520 }
521 catch (IndexOutOfRangeException)
522 {
523 ThrowHelper.ThrowArgumentException_BadComparer(comparer);
524 }
525 catch (Exception e)
526 {
527 ThrowHelper.ThrowInvalidOperationException(ExceptionResource.InvalidOperation_IComparerFailed, e);
528 }
529 }
530
531 private static void SwapIfGreaterWithValues(Span<TKey> keys, Span<TValue> values, int i, int j)
532 {
533 ref TKey reference = ref keys[i];
534 if (reference != null && GreaterThan(ref reference, ref keys[j]))
535 {
536 TKey val = reference;
537 keys[i] = keys[j];
538 keys[j] = val;
539 TValue val2 = values[i];
540 values[i] = values[j];
541 values[j] = val2;
542 }
543 }
544
545 [MethodImpl(MethodImplOptions.AggressiveInlining)]
546 private static void Swap(Span<TKey> keys, Span<TValue> values, int i, int j)
547 {
548 TKey val = keys[i];
549 keys[i] = keys[j];
550 keys[j] = val;
551 TValue val2 = values[i];
552 values[i] = values[j];
553 values[j] = val2;
554 }
555
556 private static void IntroSort(Span<TKey> keys, Span<TValue> values, int depthLimit)
557 {
558 int num = keys.Length;
559 while (num > 1)
560 {
561 if (num <= 16)
562 {
563 switch (num)
564 {
565 case 2:
566 SwapIfGreaterWithValues(keys, values, 0, 1);
567 break;
568 case 3:
569 SwapIfGreaterWithValues(keys, values, 0, 1);
570 SwapIfGreaterWithValues(keys, values, 0, 2);
571 SwapIfGreaterWithValues(keys, values, 1, 2);
572 break;
573 default:
574 InsertionSort(keys.Slice(0, num), values.Slice(0, num));
575 break;
576 }
577 break;
578 }
579 if (depthLimit == 0)
580 {
581 HeapSort(keys.Slice(0, num), values.Slice(0, num));
582 break;
583 }
584 depthLimit--;
585 int num2 = PickPivotAndPartition(keys.Slice(0, num), values.Slice(0, num));
586 Span<TKey> span = keys;
587 Span<TKey> keys2 = span[(num2 + 1)..num];
588 Span<TValue> span2 = values;
589 IntroSort(keys2, span2[(num2 + 1)..num], depthLimit);
590 num = num2;
591 }
592 }
593
594 private static int PickPivotAndPartition(Span<TKey> keys, Span<TValue> values)
595 {
596 int num = keys.Length - 1;
597 int num2 = num >> 1;
598 SwapIfGreaterWithValues(keys, values, 0, num2);
599 SwapIfGreaterWithValues(keys, values, 0, num);
600 SwapIfGreaterWithValues(keys, values, num2, num);
601 TKey left = keys[num2];
602 Swap(keys, values, num2, num - 1);
603 int num3 = 0;
604 int num4 = num - 1;
605 while (num3 < num4)
606 {
607 if (left == null)
608 {
609 while (num3 < num - 1 && keys[++num3] == null)
610 {
611 }
612 while (num4 > 0 && keys[--num4] != null)
613 {
614 }
615 }
616 else
617 {
618 while (GreaterThan(ref left, ref keys[++num3]))
619 {
620 }
621 while (LessThan(ref left, ref keys[--num4]))
622 {
623 }
624 }
625 if (num3 >= num4)
626 {
627 break;
628 }
629 Swap(keys, values, num3, num4);
630 }
631 if (num3 != num - 1)
632 {
633 Swap(keys, values, num3, num - 1);
634 }
635 return num3;
636 }
637
638 private static void HeapSort(Span<TKey> keys, Span<TValue> values)
639 {
640 int length = keys.Length;
641 for (int num = length >> 1; num >= 1; num--)
642 {
643 DownHeap(keys, values, num, length);
644 }
645 for (int num2 = length; num2 > 1; num2--)
646 {
647 Swap(keys, values, 0, num2 - 1);
648 DownHeap(keys, values, 1, num2 - 1);
649 }
650 }
651
652 private static void DownHeap(Span<TKey> keys, Span<TValue> values, int i, int n)
653 {
654 TKey left = keys[i - 1];
655 TValue val = values[i - 1];
656 while (i <= n >> 1)
657 {
658 int num = 2 * i;
659 if (num < n && (keys[num - 1] == null || LessThan(ref keys[num - 1], ref keys[num])))
660 {
661 num++;
662 }
663 if (keys[num - 1] == null || !LessThan(ref left, ref keys[num - 1]))
664 {
665 break;
666 }
667 keys[i - 1] = keys[num - 1];
668 values[i - 1] = values[num - 1];
669 i = num;
670 }
671 keys[i - 1] = left;
672 values[i - 1] = val;
673 }
674
675 private static void InsertionSort(Span<TKey> keys, Span<TValue> values)
676 {
677 for (int i = 0; i < keys.Length - 1; i++)
678 {
679 TKey left = keys[i + 1];
680 TValue val = values[i + 1];
681 int num = i;
682 while (num >= 0 && (left == null || LessThan(ref left, ref keys[num])))
683 {
684 keys[num + 1] = keys[num];
685 values[num + 1] = values[num];
686 num--;
687 }
688 keys[num + 1] = left;
689 values[num + 1] = val;
690 }
691 }
692
693 [MethodImpl(MethodImplOptions.AggressiveInlining)]
694 private static bool LessThan(ref TKey left, ref TKey right)
695 {
696 if (typeof(TKey) == typeof(byte))
697 {
698 if ((byte)(object)left >= (byte)(object)right)
699 {
700 return false;
701 }
702 return true;
703 }
704 if (typeof(TKey) == typeof(sbyte))
705 {
706 if ((sbyte)(object)left >= (sbyte)(object)right)
707 {
708 return false;
709 }
710 return true;
711 }
712 if (typeof(TKey) == typeof(ushort))
713 {
714 if ((ushort)(object)left >= (ushort)(object)right)
715 {
716 return false;
717 }
718 return true;
719 }
720 if (typeof(TKey) == typeof(short))
721 {
722 if ((short)(object)left >= (short)(object)right)
723 {
724 return false;
725 }
726 return true;
727 }
728 if (typeof(TKey) == typeof(uint))
729 {
730 if ((uint)(object)left >= (uint)(object)right)
731 {
732 return false;
733 }
734 return true;
735 }
736 if (typeof(TKey) == typeof(int))
737 {
738 if ((int)(object)left >= (int)(object)right)
739 {
740 return false;
741 }
742 return true;
743 }
744 if (typeof(TKey) == typeof(ulong))
745 {
746 if ((ulong)(object)left >= (ulong)(object)right)
747 {
748 return false;
749 }
750 return true;
751 }
752 if (typeof(TKey) == typeof(long))
753 {
754 if ((long)(object)left >= (long)(object)right)
755 {
756 return false;
757 }
758 return true;
759 }
760 if (typeof(TKey) == typeof(UIntPtr))
761 {
762 if ((nuint)(UIntPtr)(object)left >= (nuint)(UIntPtr)(object)right)
763 {
764 return false;
765 }
766 return true;
767 }
768 if (typeof(TKey) == typeof(IntPtr))
769 {
770 if ((nint)(IntPtr)(object)left >= (nint)(IntPtr)(object)right)
771 {
772 return false;
773 }
774 return true;
775 }
776 if (typeof(TKey) == typeof(float))
777 {
778 if (!((float)(object)left < (float)(object)right))
779 {
780 return false;
781 }
782 return true;
783 }
784 if (typeof(TKey) == typeof(double))
785 {
786 if (!((double)(object)left < (double)(object)right))
787 {
788 return false;
789 }
790 return true;
791 }
792 if (typeof(TKey) == typeof(Half))
793 {
794 if (!((Half)(object)left < (Half)(object)right))
795 {
796 return false;
797 }
798 return true;
799 }
800 if (left.CompareTo(right) >= 0)
801 {
802 return false;
803 }
804 return true;
805 }
806
807 [MethodImpl(MethodImplOptions.AggressiveInlining)]
808 private static bool GreaterThan(ref TKey left, ref TKey right)
809 {
810 if (typeof(TKey) == typeof(byte))
811 {
812 if ((byte)(object)left <= (byte)(object)right)
813 {
814 return false;
815 }
816 return true;
817 }
818 if (typeof(TKey) == typeof(sbyte))
819 {
820 if ((sbyte)(object)left <= (sbyte)(object)right)
821 {
822 return false;
823 }
824 return true;
825 }
826 if (typeof(TKey) == typeof(ushort))
827 {
828 if ((ushort)(object)left <= (ushort)(object)right)
829 {
830 return false;
831 }
832 return true;
833 }
834 if (typeof(TKey) == typeof(short))
835 {
836 if ((short)(object)left <= (short)(object)right)
837 {
838 return false;
839 }
840 return true;
841 }
842 if (typeof(TKey) == typeof(uint))
843 {
844 if ((uint)(object)left <= (uint)(object)right)
845 {
846 return false;
847 }
848 return true;
849 }
850 if (typeof(TKey) == typeof(int))
851 {
852 if ((int)(object)left <= (int)(object)right)
853 {
854 return false;
855 }
856 return true;
857 }
858 if (typeof(TKey) == typeof(ulong))
859 {
860 if ((ulong)(object)left <= (ulong)(object)right)
861 {
862 return false;
863 }
864 return true;
865 }
866 if (typeof(TKey) == typeof(long))
867 {
868 if ((long)(object)left <= (long)(object)right)
869 {
870 return false;
871 }
872 return true;
873 }
874 if (typeof(TKey) == typeof(UIntPtr))
875 {
876 if ((nuint)(UIntPtr)(object)left <= (nuint)(UIntPtr)(object)right)
877 {
878 return false;
879 }
880 return true;
881 }
882 if (typeof(TKey) == typeof(IntPtr))
883 {
884 if ((nint)(IntPtr)(object)left <= (nint)(IntPtr)(object)right)
885 {
886 return false;
887 }
888 return true;
889 }
890 if (typeof(TKey) == typeof(float))
891 {
892 if (!((float)(object)left > (float)(object)right))
893 {
894 return false;
895 }
896 return true;
897 }
898 if (typeof(TKey) == typeof(double))
899 {
900 if (!((double)(object)left > (double)(object)right))
901 {
902 return false;
903 }
904 return true;
905 }
906 if (typeof(TKey) == typeof(Half))
907 {
908 if (!((Half)(object)left > (Half)(object)right))
909 {
910 return false;
911 }
912 return true;
913 }
914 if (left.CompareTo(right) <= 0)
915 {
916 return false;
917 }
918 return true;
919 }
920}
System.Collections.Generic.GenericArraySortHelper.HeapSort
static void HeapSort(Span< TKey > keys, Span< TValue > values)
Definition GenericArraySortHelper.cs:638
System.Collections.Generic.GenericArraySortHelper.IntroSort
static void IntroSort(Span< T > keys, int depthLimit)
Definition GenericArraySortHelper.cs:104
System.Collections.Generic.GenericArraySortHelper.PickPivotAndPartition
static int PickPivotAndPartition(Span< TKey > keys, Span< TValue > values)
Definition GenericArraySortHelper.cs:594
System.Collections.Generic.GenericArraySortHelper.DownHeap
static void DownHeap(Span< T > keys, int i, int n)
Definition GenericArraySortHelper.cs:229
System.Collections.Generic.GenericArraySortHelper.BinarySearch
int BinarySearch(T[] array, int index, int length, T value, IComparer< T > comparer)
Definition GenericArraySortHelper.cs:46
System.Collections.Generic.GenericArraySortHelper.InsertionSort
static void InsertionSort(Span< TKey > keys, Span< TValue > values)
Definition GenericArraySortHelper.cs:675
System.Collections.Generic.GenericArraySortHelper.DownHeap
static void DownHeap(Span< TKey > keys, Span< TValue > values, int i, int n)
Definition GenericArraySortHelper.cs:652
System.Collections.Generic.GenericArraySortHelper.Sort
void Sort(Span< T > keys, IComparer< T > comparer)
Definition GenericArraySortHelper.cs:10
System.Collections.Generic.GenericArraySortHelper.SwapIfGreaterWithValues
static void SwapIfGreaterWithValues(Span< TKey > keys, Span< TValue > values, int i, int j)
Definition GenericArraySortHelper.cs:531
System.Collections.Generic.GenericArraySortHelper.LessThan
static bool LessThan(ref TKey left, ref TKey right)
Definition GenericArraySortHelper.cs:694
System.Collections.Generic.GenericArraySortHelper.Sort
void Sort(Span< TKey > keys, Span< TValue > values, IComparer< TKey > comparer)
Definition GenericArraySortHelper.cs:494
System.Collections.Generic.GenericArraySortHelper.Swap
static void Swap(Span< TKey > keys, Span< TValue > values, int i, int j)
Definition GenericArraySortHelper.cs:546
System.Collections.Generic.GenericArraySortHelper.BinarySearch
static int BinarySearch(T[] array, int index, int length, T value)
Definition GenericArraySortHelper.cs:63
System.Collections.Generic.GenericArraySortHelper.GreaterThan
static bool GreaterThan(ref TKey left, ref TKey right)
Definition GenericArraySortHelper.cs:808
System.Collections.Generic.GenericArraySortHelper.IntroSort
static void IntroSort(Span< TKey > keys, Span< TValue > values, int depthLimit)
Definition GenericArraySortHelper.cs:556
System.Numerics.BitOperations.Log2
static int Log2(uint value)
Definition BitOperations.cs:180
System.ThrowHelper.ThrowArgumentException_BadComparer
static void ThrowArgumentException_BadComparer(object comparer)
Definition ThrowHelper.cs:68
System.ThrowHelper.ThrowInvalidOperationException
static void ThrowInvalidOperationException()
Definition ThrowHelper.cs:34