< Summary

Information
Class: Trailblazer.Pathing.PersistentVoxelIndexMap<T>
Assembly: Trailblazer
File(s): /home/runner/work/Trailblazer/Trailblazer/src/Trailblazer/Pathing/Graph/PersistentVoxelIndexMap.cs
Line coverage
100%
Covered lines: 209
Uncovered lines: 0
Coverable lines: 209
Total lines: 377
Line coverage: 100%
Branch coverage
100%
Covered branches: 84
Total branches: 84
Branch coverage: 100%
Method coverage

Feature is only available for sponsors

Upgrade to PRO version

Metrics

MethodBranch coverage Crap Score Cyclomatic complexity Line coverage
.ctor(...)100%11100%
get_Count()100%11100%
get_RetainedBytes()100%11100%
get_PersistentNodeCount()100%11100%
TryGetValue(...)100%66100%
Set(...)100%11100%
Set(...)100%11100%
Remove(...)100%22100%
Remove(...)100%22100%
GetValueAt(...)100%44100%
GetKeyAt(...)100%44100%
Set(...)100%66100%
Set(...)100%66100%
Remove(...)100%1414100%
Remove(...)100%1414100%
FindMinimum(...)100%22100%
RemoveMinimum(...)100%22100%
RemoveMinimum(...)100%22100%
Balance(...)100%88100%
Balance(...)100%88100%
RotateLeft(...)100%11100%
RotateRight(...)100%11100%
RotateLeft(...)100%11100%
RotateRight(...)100%11100%
NewNode(...)100%11100%
CountOf(...)100%22100%
HeightOf(...)100%22100%
.ctor(...)100%11100%

File(s)

/home/runner/work/Trailblazer/Trailblazer/src/Trailblazer/Pathing/Graph/PersistentVoxelIndexMap.cs

#LineLine coverage
 1//=======================================================================
 2// PersistentVoxelIndexMap.cs
 3//=======================================================================
 4// MIT License, Copyright (c) 2024-present David Oravsky (mrdav30)
 5// See LICENSE file in the project root for full license information.
 6//=======================================================================
 7
 8using System;
 9using GridForge.Spatial;
 10
 11namespace Trailblazer.Pathing;
 12
 13/// <summary>Stores topology-local address values in an immutable balanced tree.</summary>
 14internal sealed class PersistentVoxelIndexMap<T>
 15{
 16    private readonly Node? _root;
 17
 18    internal static PersistentVoxelIndexMap<T> Empty { get; } = new(null);
 19
 36095620    private PersistentVoxelIndexMap(Node? root) => _root = root;
 21
 1048513722    internal int Count => CountOf(_root);
 23
 30657024    internal long RetainedBytes => checked(32L + ((long)Count * 64L));
 25
 30794726    internal int PersistentNodeCount => Count;
 27
 28    internal bool TryGetValue(VoxelIndex key, out T value)
 29    {
 1058369630        Node? node = _root;
 6915959131        while (node != null)
 32        {
 6858133833            int comparison = key.CompareTo(node.Key);
 6858133834            if (comparison == 0)
 35            {
 1000544336                value = node.Value;
 1000544337                return true;
 38            }
 5857589539            node = comparison < 0 ? node.Left : node.Right;
 40        }
 57825341        value = default!;
 57825342        return false;
 43    }
 44
 45    internal PersistentVoxelIndexMap<T> Set(VoxelIndex key, T value) =>
 4821246        new(Set(_root, key, value));
 47
 48    internal PersistentVoxelIndexMap<T> Set(VoxelIndex key, T value, out int copiedNodeCount)
 49    {
 11485550        copiedNodeCount = 0;
 11485551        return new PersistentVoxelIndexMap<T>(Set(_root, key, value, ref copiedNodeCount));
 52    }
 53
 54    internal PersistentVoxelIndexMap<T> Remove(VoxelIndex key, out bool removed)
 55    {
 5756        Node? root = Remove(_root, key, out removed);
 5757        return removed ? new PersistentVoxelIndexMap<T>(root) : this;
 58    }
 59
 60    internal PersistentVoxelIndexMap<T> Remove(
 61        VoxelIndex key,
 62        out bool removed,
 63        out int copiedNodeCount)
 64    {
 1735065        copiedNodeCount = 0;
 1735066        Node? root = Remove(_root, key, out removed, ref copiedNodeCount);
 1735067        return removed ? new PersistentVoxelIndexMap<T>(root) : this;
 68    }
 69
 70    internal T GetValueAt(int ordinal)
 71    {
 255730772        SwiftThrowHelper.ThrowIfArgumentOutOfRange(
 255730773            (uint)ordinal >= (uint)Count,
 255730774            ordinal,
 255730775            nameof(ordinal));
 255730776        Node node = _root!;
 1235904177        while (true)
 78        {
 2726148679            int leftCount = CountOf(node.Left);
 2726148680            if (ordinal < leftCount)
 1234513881                node = node.Left!;
 1491634882            else if (ordinal == leftCount)
 255730783                return node.Value;
 84            else
 85            {
 1235904186                ordinal -= leftCount + 1;
 1235904187                node = node.Right!;
 88            }
 89        }
 90    }
 91
 92    internal VoxelIndex GetKeyAt(int ordinal)
 93    {
 226467094        SwiftThrowHelper.ThrowIfArgumentOutOfRange(
 226467095            (uint)ordinal >= (uint)Count,
 226467096            ordinal,
 226467097            nameof(ordinal));
 226467098        Node node = _root!;
 1118998099        while (true)
 100        {
 24640069101            int leftCount = CountOf(node.Left);
 24640069102            if (ordinal < leftCount)
 11185419103                node = node.Left!;
 13454650104            else if (ordinal == leftCount)
 2264670105                return node.Key;
 106            else
 107            {
 11189980108                ordinal -= leftCount + 1;
 11189980109                node = node.Right!;
 110            }
 111        }
 112    }
 113
 114    private static Node Set(Node? node, VoxelIndex key, T value)
 115    {
 402081116        if (node == null)
 48146117            return new Node(key, value, null, null);
 353935118        int comparison = key.CompareTo(node.Key);
 353935119        if (comparison == 0)
 66120            return new Node(key, value, node.Left, node.Right);
 353869121        return comparison < 0
 353869122            ? Balance(new Node(node.Key, node.Value, Set(node.Left, key, value), node.Right))
 353869123            : Balance(new Node(node.Key, node.Value, node.Left, Set(node.Right, key, value)));
 124    }
 125
 126    private static Node Set(
 127        Node? node,
 128        VoxelIndex key,
 129        T value,
 130        ref int copiedNodeCount)
 131    {
 1191308132        if (node == null)
 114624133            return NewNode(key, value, null, null, ref copiedNodeCount);
 1076684134        int comparison = key.CompareTo(node.Key);
 1076684135        if (comparison == 0)
 231136            return NewNode(key, value, node.Left, node.Right, ref copiedNodeCount);
 1076453137        return comparison < 0
 1076453138            ? Balance(
 1076453139                NewNode(
 1076453140                    node.Key,
 1076453141                    node.Value,
 1076453142                    Set(node.Left, key, value, ref copiedNodeCount),
 1076453143                    node.Right,
 1076453144                    ref copiedNodeCount),
 1076453145                ref copiedNodeCount)
 1076453146            : Balance(
 1076453147                NewNode(
 1076453148                    node.Key,
 1076453149                    node.Value,
 1076453150                    node.Left,
 1076453151                    Set(node.Right, key, value, ref copiedNodeCount),
 1076453152                    ref copiedNodeCount),
 1076453153                ref copiedNodeCount);
 154    }
 155
 156    private static Node? Remove(Node? node, VoxelIndex key, out bool removed)
 157    {
 106158        if (node == null)
 159        {
 2160            removed = false;
 2161            return null;
 162        }
 104163        int comparison = key.CompareTo(node.Key);
 104164        if (comparison < 0)
 165        {
 43166            Node? left = Remove(node.Left, key, out removed);
 43167            return removed ? Balance(new Node(node.Key, node.Value, left, node.Right)) : node;
 168        }
 61169        if (comparison > 0)
 170        {
 6171            Node? right = Remove(node.Right, key, out removed);
 6172            return removed ? Balance(new Node(node.Key, node.Value, node.Left, right)) : node;
 173        }
 174
 55175        removed = true;
 55176        if (node.Left == null)
 51177            return node.Right;
 4178        if (node.Right == null)
 2179            return node.Left;
 2180        Node successor = FindMinimum(node.Right);
 2181        Node? successorRight = RemoveMinimum(node.Right);
 2182        return Balance(new Node(successor.Key, successor.Value, node.Left, successorRight));
 183    }
 184
 185    private static Node? Remove(
 186        Node? node,
 187        VoxelIndex key,
 188        out bool removed,
 189        ref int copiedNodeCount)
 190    {
 141458191        if (node == null)
 192        {
 2193            removed = false;
 2194            return null;
 195        }
 141456196        int comparison = key.CompareTo(node.Key);
 141456197        if (comparison < 0)
 198        {
 124002199            Node? left = Remove(node.Left, key, out removed, ref copiedNodeCount);
 124002200            return removed
 124002201                ? Balance(
 124002202                    NewNode(node.Key, node.Value, left, node.Right, ref copiedNodeCount),
 124002203                    ref copiedNodeCount)
 124002204                : node;
 205        }
 17454206        if (comparison > 0)
 207        {
 106208            Node? right = Remove(node.Right, key, out removed, ref copiedNodeCount);
 106209            return removed
 106210                ? Balance(
 106211                    NewNode(node.Key, node.Value, node.Left, right, ref copiedNodeCount),
 106212                    ref copiedNodeCount)
 106213                : node;
 214        }
 215
 17348216        removed = true;
 17348217        if (node.Left == null)
 17331218            return node.Right;
 17219        if (node.Right == null)
 15220            return node.Left;
 2221        Node successor = FindMinimum(node.Right);
 2222        Node? successorRight = RemoveMinimum(node.Right, ref copiedNodeCount);
 2223        return Balance(
 2224            NewNode(successor.Key, successor.Value, node.Left, successorRight, ref copiedNodeCount),
 2225            ref copiedNodeCount);
 226    }
 227
 228    private static Node FindMinimum(Node node)
 229    {
 6230        while (node.Left != null)
 2231            node = node.Left;
 4232        return node;
 233    }
 234
 3235    private static Node? RemoveMinimum(Node node) => node.Left == null
 3236        ? node.Right
 3237        : Balance(new Node(node.Key, node.Value, RemoveMinimum(node.Left), node.Right));
 238
 3239    private static Node? RemoveMinimum(Node node, ref int copiedNodeCount) => node.Left == null
 3240        ? node.Right
 3241        : Balance(
 3242            NewNode(
 3243                node.Key,
 3244                node.Value,
 3245                RemoveMinimum(node.Left, ref copiedNodeCount),
 3246                node.Right,
 3247                ref copiedNodeCount),
 3248            ref copiedNodeCount);
 249
 250    private static Node Balance(Node node)
 251    {
 353917252        int balance = HeightOf(node.Left) - HeightOf(node.Right);
 353917253        if (balance > 1)
 254        {
 362255            if (HeightOf(node.Left!.Left) < HeightOf(node.Left.Right))
 361256                node = new Node(node.Key, node.Value, RotateLeft(node.Left), node.Right);
 362257            return RotateRight(node);
 258        }
 353555259        if (balance < -1)
 260        {
 41252261            if (HeightOf(node.Right!.Right) < HeightOf(node.Right.Left))
 10262                node = new Node(node.Key, node.Value, node.Left, RotateRight(node.Right));
 41252263            return RotateLeft(node);
 264        }
 312303265        return node;
 266    }
 267
 268    private static Node Balance(Node node, ref int copiedNodeCount)
 269    {
 1200560270        int balance = HeightOf(node.Left) - HeightOf(node.Right);
 1200560271        if (balance > 1)
 272        {
 62273            if (HeightOf(node.Left!.Left) < HeightOf(node.Left.Right))
 274            {
 61275                node = NewNode(
 61276                    node.Key,
 61277                    node.Value,
 61278                    RotateLeft(node.Left, ref copiedNodeCount),
 61279                    node.Right,
 61280                    ref copiedNodeCount);
 281            }
 62282            return RotateRight(node, ref copiedNodeCount);
 283        }
 1200498284        if (balance < -1)
 285        {
 114703286            if (HeightOf(node.Right!.Right) < HeightOf(node.Right.Left))
 287            {
 185288                node = NewNode(
 185289                    node.Key,
 185290                    node.Value,
 185291                    node.Left,
 185292                    RotateRight(node.Right, ref copiedNodeCount),
 185293                    ref copiedNodeCount);
 294            }
 114703295            return RotateLeft(node, ref copiedNodeCount);
 296        }
 1085795297        return node;
 298    }
 299
 300    private static Node RotateLeft(Node node)
 301    {
 41613302        Node right = node.Right!;
 41613303        return new Node(
 41613304            right.Key,
 41613305            right.Value,
 41613306            new Node(node.Key, node.Value, node.Left, right.Left),
 41613307            right.Right);
 308    }
 309
 310    private static Node RotateRight(Node node)
 311    {
 372312        Node left = node.Left!;
 372313        return new Node(
 372314            left.Key,
 372315            left.Value,
 372316            left.Left,
 372317            new Node(node.Key, node.Value, left.Right, node.Right));
 318    }
 319
 320    private static Node RotateLeft(Node node, ref int copiedNodeCount)
 321    {
 114764322        Node right = node.Right!;
 114764323        Node left = NewNode(
 114764324            node.Key,
 114764325            node.Value,
 114764326            node.Left,
 114764327            right.Left,
 114764328            ref copiedNodeCount);
 114764329        return NewNode(right.Key, right.Value, left, right.Right, ref copiedNodeCount);
 330    }
 331
 332    private static Node RotateRight(Node node, ref int copiedNodeCount)
 333    {
 247334        Node left = node.Left!;
 247335        Node right = NewNode(
 247336            node.Key,
 247337            node.Value,
 247338            left.Right,
 247339            node.Right,
 247340            ref copiedNodeCount);
 247341        return NewNode(left.Key, left.Value, left.Left, right, ref copiedNodeCount);
 342    }
 343
 344    private static Node NewNode(
 345        VoxelIndex key,
 346        T value,
 347        Node? left,
 348        Node? right,
 349        ref int copiedNodeCount)
 350    {
 1545683351        copiedNodeCount = checked(copiedNodeCount + 1);
 1545683352        return new Node(key, value, left, right);
 353    }
 354
 66450998355    private static int CountOf(Node? node) => node?.Count ?? 0;
 7486018356    private static int HeightOf(Node? node) => node?.Height ?? 0;
 357
 358    private sealed class Node
 359    {
 2032153360        internal Node(VoxelIndex key, T value, Node? left, Node? right)
 361        {
 2032153362            Key = key;
 2032153363            Value = value;
 2032153364            Left = left;
 2032153365            Right = right;
 2032153366            Height = Math.Max(HeightOf(left), HeightOf(right)) + 1;
 2032153367            Count = CountOf(left) + CountOf(right) + 1;
 2032153368        }
 369
 370        internal VoxelIndex Key { get; }
 371        internal T Value { get; }
 372        internal Node? Left { get; }
 373        internal Node? Right { get; }
 374        internal int Height { get; }
 375        internal int Count { get; }
 376    }
 377}
Generated by: ReportGenerator 5.5.11.0
09/02/2026 - 04:28:06
GitHub | reportgenerator.io

Methods/Properties

.ctor(Trailblazer.Pathing.PersistentVoxelIndexMap`1/Node<T>)
get_Count()
get_RetainedBytes()
get_PersistentNodeCount()
TryGetValue(GridForge.Spatial.VoxelIndex,T&)
Set(GridForge.Spatial.VoxelIndex,T)
Set(GridForge.Spatial.VoxelIndex,T,System.Int32&)
Remove(GridForge.Spatial.VoxelIndex,System.Boolean&)
Remove(GridForge.Spatial.VoxelIndex,System.Boolean&,System.Int32&)
GetValueAt(System.Int32)
GetKeyAt(System.Int32)
Set(Trailblazer.Pathing.PersistentVoxelIndexMap`1/Node<T>,GridForge.Spatial.VoxelIndex,T)
Set(Trailblazer.Pathing.PersistentVoxelIndexMap`1/Node<T>,GridForge.Spatial.VoxelIndex,T,System.Int32&)
Remove(Trailblazer.Pathing.PersistentVoxelIndexMap`1/Node<T>,GridForge.Spatial.VoxelIndex,System.Boolean&)
Remove(Trailblazer.Pathing.PersistentVoxelIndexMap`1/Node<T>,GridForge.Spatial.VoxelIndex,System.Boolean&,System.Int32&)
FindMinimum(Trailblazer.Pathing.PersistentVoxelIndexMap`1/Node<T>)
RemoveMinimum(Trailblazer.Pathing.PersistentVoxelIndexMap`1/Node<T>)
RemoveMinimum(Trailblazer.Pathing.PersistentVoxelIndexMap`1/Node<T>,System.Int32&)
Balance(Trailblazer.Pathing.PersistentVoxelIndexMap`1/Node<T>)
Balance(Trailblazer.Pathing.PersistentVoxelIndexMap`1/Node<T>,System.Int32&)
RotateLeft(Trailblazer.Pathing.PersistentVoxelIndexMap`1/Node<T>)
RotateRight(Trailblazer.Pathing.PersistentVoxelIndexMap`1/Node<T>)
RotateLeft(Trailblazer.Pathing.PersistentVoxelIndexMap`1/Node<T>,System.Int32&)
RotateRight(Trailblazer.Pathing.PersistentVoxelIndexMap`1/Node<T>,System.Int32&)
NewNode(GridForge.Spatial.VoxelIndex,T,Trailblazer.Pathing.PersistentVoxelIndexMap`1/Node<T>,Trailblazer.Pathing.PersistentVoxelIndexMap`1/Node<T>,System.Int32&)
CountOf(Trailblazer.Pathing.PersistentVoxelIndexMap`1/Node<T>)
HeightOf(Trailblazer.Pathing.PersistentVoxelIndexMap`1/Node<T>)
.ctor(GridForge.Spatial.VoxelIndex,T,Trailblazer.Pathing.PersistentVoxelIndexMap`1/Node<T>,Trailblazer.Pathing.PersistentVoxelIndexMap`1/Node<T>)