| | | 1 | | //======================================================================= |
| | | 2 | | // Physics2DHitSorter.cs |
| | | 3 | | //======================================================================= |
| | | 4 | | // MIT License, Copyright (c) 2026–present David Oravsky (mrdav30) |
| | | 5 | | // See LICENSE file in the project root for full license information. |
| | | 6 | | //======================================================================= |
| | | 7 | | |
| | | 8 | | using SwiftCollections; |
| | | 9 | | using System.Runtime.CompilerServices; |
| | | 10 | | |
| | | 11 | | namespace Gravitas.Queries; |
| | | 12 | | |
| | | 13 | | internal static class Physics2DHitSorter |
| | | 14 | | { |
| | | 15 | | public static void SortByDistance(SwiftList<Physics2DHit> hits) |
| | | 16 | | { |
| | 7575 | 17 | | SortByDistance(hits, 0, hits.Count); |
| | 7575 | 18 | | } |
| | | 19 | | |
| | | 20 | | public static void SortByDistance(SwiftList<Physics2DHit> hits, int start, int count) |
| | | 21 | | { |
| | 7575 | 22 | | if (count < 2) |
| | 6180 | 23 | | return; |
| | | 24 | | |
| | 27708 | 25 | | for (int root = (count / 2) - 1; root >= 0; root--) |
| | 12459 | 26 | | SiftDown(hits, start, root, count); |
| | | 27 | | |
| | 51528 | 28 | | for (int end = count - 1; end > 0; end--) |
| | | 29 | | { |
| | 24369 | 30 | | Swap(hits, start, start + end); |
| | 24369 | 31 | | SiftDown(hits, start, 0, end); |
| | | 32 | | } |
| | 1395 | 33 | | } |
| | | 34 | | |
| | 174541 | 35 | | public static bool ComesBefore(Physics2DHit left, Physics2DHit right) => Compare(left, right) < 0; |
| | | 36 | | |
| | | 37 | | private static void SiftDown(SwiftList<Physics2DHit> hits, int start, int root, int count) |
| | | 38 | | { |
| | 77149 | 39 | | while (true) |
| | | 40 | | { |
| | 113977 | 41 | | int child = (root * 2) + 1; |
| | 113977 | 42 | | if (child >= count) |
| | 32044 | 43 | | return; |
| | | 44 | | |
| | 81933 | 45 | | int swapIndex = root; |
| | 81933 | 46 | | if (ComesBefore(hits[start + swapIndex], hits[start + child])) |
| | 74425 | 47 | | swapIndex = child; |
| | | 48 | | |
| | 81933 | 49 | | int right = child + 1; |
| | 81933 | 50 | | if (right < count && ComesBefore(hits[start + swapIndex], hits[start + right])) |
| | 35834 | 51 | | swapIndex = right; |
| | | 52 | | |
| | 81933 | 53 | | if (swapIndex == root) |
| | 4784 | 54 | | return; |
| | | 55 | | |
| | 77149 | 56 | | Swap(hits, start + root, start + swapIndex); |
| | 77149 | 57 | | root = swapIndex; |
| | | 58 | | } |
| | | 59 | | } |
| | | 60 | | |
| | | 61 | | [MethodImpl(MethodImplOptions.AggressiveInlining)] |
| | | 62 | | private static int Compare(Physics2DHit left, Physics2DHit right) |
| | | 63 | | { |
| | 174541 | 64 | | int distance = left.Distance.CompareTo(right.Distance); |
| | 174541 | 65 | | if (distance != 0) |
| | 166779 | 66 | | return distance; |
| | | 67 | | |
| | 7762 | 68 | | return left.Collider.Id.CompareTo(right.Collider.Id); |
| | | 69 | | } |
| | | 70 | | |
| | | 71 | | [MethodImpl(MethodImplOptions.AggressiveInlining)] |
| | | 72 | | private static void Swap(SwiftList<Physics2DHit> hits, int left, int right) |
| | | 73 | | { |
| | 101518 | 74 | | Physics2DHit temp = hits[left]; |
| | 101518 | 75 | | hits[left] = hits[right]; |
| | 101518 | 76 | | hits[right] = temp; |
| | 101518 | 77 | | } |
| | | 78 | | } |