< Summary

Information
Class: Gravitas.IslandGraphUtility
Assembly: Gravitas
File(s): /home/runner/work/Gravitas/Gravitas/src/Gravitas/Core/Islands/IslandGraphUtility.cs
Line coverage
100%
Covered lines: 78
Uncovered lines: 0
Coverable lines: 78
Total lines: 160
Line coverage: 100%
Branch coverage
100%
Covered branches: 44
Total branches: 44
Branch coverage: 100%
Method coverage

Feature is only available for sponsors

Upgrade to PRO version

Metrics

MethodBranch coverage Crap Score Cyclomatic complexity Line coverage
SortAndDeduplicate(...)100%1010100%
Find(...)100%66100%
Union(...)100%66100%
FindRoot(...)100%44100%
CompressRoots(...)100%22100%
ResolveConstraintRootKey(...)100%44100%
WakeBodies(...)100%1212100%

File(s)

/home/runner/work/Gravitas/Gravitas/src/Gravitas/Core/Islands/IslandGraphUtility.cs

#LineLine coverage
 1//=======================================================================
 2// IslandGraphUtility.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
 8using System.Collections.Generic;
 9using SwiftCollections;
 10
 11namespace Gravitas;
 12
 13/// <summary>
 14/// Builds and resolves collision island membership in deterministic body-key order.
 15/// </summary>
 16internal static class IslandGraphUtility
 17{
 18    public static void SortAndDeduplicate<TNode>(SwiftList<TNode> nodes, IComparer<TNode> comparer)
 19        where TNode : struct, IIslandNodeState
 20    {
 489721        if (nodes.Count == 0)
 322            return;
 23
 489424        if (nodes.Count == 1)
 25        {
 13426            TNode singleNode = nodes[0];
 13427            singleNode.ParentIndex = 0;
 13428            singleNode.RootKey = singleNode.BodyKey;
 13429            nodes[0] = singleNode;
 13430            return;
 31        }
 32
 476033        nodes.SortInPlace(comparer);
 34
 476035        int writeIndex = 0;
 476036        int previousKey = -1;
 8031237        for (int readIndex = 0; readIndex < nodes.Count; readIndex++)
 38        {
 3539639            TNode node = nodes[readIndex];
 3539640            if (node.BodyKey == previousKey)
 41                continue;
 42
 1720943            node.ParentIndex = writeIndex;
 1720944            node.RootKey = node.BodyKey;
 1720945            nodes[writeIndex++] = node;
 1720946            previousKey = node.BodyKey;
 47        }
 48
 2294749        while (nodes.Count > writeIndex)
 1818750            nodes.RemoveAt(nodes.Count - 1);
 476051    }
 52
 53    public static int Find<TNode>(SwiftList<TNode> nodes, int key)
 54        where TNode : struct, IIslandNodeState
 55    {
 7105656        int low = 0;
 7105657        int high = nodes.Count - 1;
 15488858        while (low <= high)
 59        {
 15488760            int mid = low + ((high - low) >> 1);
 15488761            int midKey = nodes[mid].BodyKey;
 15488762            if (midKey == key)
 7105563                return mid;
 64
 8383265            if (midKey < key)
 4883566                low = mid + 1;
 67            else
 3499768                high = mid - 1;
 69        }
 70
 171        return -1;
 72    }
 73
 74    public static void Union<TNode>(SwiftList<TNode> nodes, int nodeA, int nodeB)
 75        where TNode : struct, IIslandNodeState
 76    {
 1213777        int rootA = FindRoot(nodes, nodeA);
 1213778        int rootB = FindRoot(nodes, nodeB);
 1213779        if (rootA == rootB)
 24980            return;
 81
 1188882        int keyA = nodes[rootA].BodyKey;
 1188883        int keyB = nodes[rootB].BodyKey;
 1188884        int parent = keyA <= keyB ? rootA : rootB;
 1188885        int child = parent == rootA ? rootB : rootA;
 86
 1188887        TNode childNode = nodes[child];
 1188888        childNode.ParentIndex = parent;
 1188889        childNode.RootKey = nodes[parent].BodyKey;
 1188890        nodes[child] = childNode;
 1188891    }
 92
 93    public static int FindRoot<TNode>(SwiftList<TNode> nodes, int index)
 94        where TNode : struct, IIslandNodeState
 95    {
 4161796        int root = index;
 5954897        while (nodes[root].ParentIndex != root)
 1793198            root = nodes[root].ParentIndex;
 99
 59548100        while (index != root)
 101        {
 17931102            TNode node = nodes[index];
 17931103            int parent = node.ParentIndex;
 17931104            node.ParentIndex = root;
 17931105            node.RootKey = nodes[root].BodyKey;
 17931106            nodes[index] = node;
 17931107            index = parent;
 108        }
 109
 41617110        return root;
 111    }
 112
 113    public static void CompressRoots<TNode>(SwiftList<TNode> nodes)
 114        where TNode : struct, IIslandNodeState
 115    {
 44474116        for (int i = 0; i < nodes.Count; i++)
 117        {
 17343118            int root = FindRoot(nodes, i);
 17343119            TNode node = nodes[i];
 17343120            node.RootKey = nodes[root].BodyKey;
 17343121            nodes[i] = node;
 122        }
 4894123    }
 124
 125    public static int ResolveConstraintRootKey<TNode>(SwiftList<TNode> nodes, int nodeA, int nodeB)
 126        where TNode : struct, IIslandNodeState
 127    {
 23377128        if (nodeA >= 0)
 15142129            return nodes[nodeA].RootKey;
 130
 8235131        return nodeB >= 0 ? nodes[nodeB].RootKey : -1;
 132    }
 133
 134    public static bool WakeBodies<TNode>(SwiftList<TNode> nodes, int rootKey)
 135        where TNode : struct, IIslandNodeState
 136    {
 5439137        bool hasAwakeBody = false;
 29828138        for (int i = 0; i < nodes.Count; i++)
 139        {
 14881140            TNode node = nodes[i];
 14881141            if (node.RootKey == rootKey && node.IsAwakeForCollision)
 142            {
 5406143                hasAwakeBody = true;
 5406144                break;
 145            }
 146        }
 147
 5439148        if (!hasAwakeBody)
 33149            return false;
 150
 83052151        for (int i = 0; i < nodes.Count; i++)
 152        {
 36120153            TNode node = nodes[i];
 36120154            if (node.RootKey == rootKey)
 17292155                node.WakeFromCollision();
 156        }
 157
 5406158        return true;
 159    }
 160}