< Summary

Information
Class: Trailblazer.Pathing.PersistentIntMap<T>
Assembly: Trailblazer
File(s): /home/runner/work/Trailblazer/Trailblazer/src/Trailblazer/Pathing/Graph/PersistentIntMap.cs
Line coverage
100%
Covered lines: 203
Uncovered lines: 0
Coverable lines: 203
Total lines: 347
Line coverage: 100%
Branch coverage
100%
Covered branches: 86
Total branches: 86
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%
Set(...)100%88100%
Set(...)100%88100%
Remove(...)100%1616100%
Remove(...)100%1616100%
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/PersistentIntMap.cs

#LineLine coverage
 1//=======================================================================
 2// PersistentIntMap.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;
 9
 10namespace Trailblazer.Pathing;
 11
 12/// <summary>Stores integer-addressed persistent pages with logarithmic path copying.</summary>
 13internal sealed class PersistentIntMap<T>
 14{
 15    private readonly Node? _root;
 16
 17    internal static PersistentIntMap<T> Empty { get; } = new(null);
 18
 7279019    private PersistentIntMap(Node? root) => _root = root;
 20
 8264321    internal int Count => CountOf(_root);
 22
 2981923    internal long RetainedBytes => checked(32L + ((long)Count * 72L));
 24
 3165825    internal int PersistentNodeCount => Count;
 26
 27    internal bool TryGetValue(int key, out T value)
 28    {
 1575607329        Node? node = _root;
 7947147830        while (node != null)
 31        {
 7557213732            if (key == node.Key)
 33            {
 1185673234                value = node.Value;
 1185673235                return true;
 36            }
 6371540537            node = key < node.Key ? node.Left : node.Right;
 38        }
 389934139        value = default!;
 389934140        return false;
 41    }
 42
 297643    internal PersistentIntMap<T> Set(int key, T value) => new(Set(_root, key, value));
 44
 45    internal PersistentIntMap<T> Set(int key, T value, out int copiedNodeCount)
 46    {
 3334647        copiedNodeCount = 0;
 3334648        return new PersistentIntMap<T>(Set(_root, key, value, ref copiedNodeCount));
 49    }
 50
 51    internal PersistentIntMap<T> Remove(int key)
 52    {
 853        Node? root = Remove(_root, key, out bool removed);
 854        return removed ? new PersistentIntMap<T>(root) : this;
 55    }
 56
 57    internal PersistentIntMap<T> Remove(int key, out int copiedNodeCount)
 58    {
 6259        copiedNodeCount = 0;
 6260        Node? root = Remove(_root, key, out bool removed, ref copiedNodeCount);
 6261        return removed ? new PersistentIntMap<T>(root) : this;
 62    }
 63
 64    internal T GetValueAt(int ordinal)
 65    {
 111366        SwiftThrowHelper.ThrowIfArgumentOutOfRange(
 111367            (uint)ordinal >= (uint)Count,
 111368            ordinal,
 111369            nameof(ordinal));
 111370        Node node = _root!;
 40371        while (true)
 72        {
 181973            int leftCount = CountOf(node.Left);
 181974            if (ordinal < leftCount)
 30375                node = node.Left!;
 151676            else if (ordinal == leftCount)
 111377                return node.Value;
 78            else
 79            {
 40380                ordinal -= leftCount + 1;
 40381                node = node.Right!;
 82            }
 83        }
 84    }
 85
 86    private static Node Set(Node? node, int key, T value)
 87    {
 440588        if (node == null)
 268889            return new Node(key, value, null, null);
 171790        if (key == node.Key)
 28891            return ReferenceEquals(value, node.Value)
 28892                ? node
 28893                : new Node(key, value, node.Left, node.Right);
 142994        return key < node.Key
 142995            ? Balance(new Node(node.Key, node.Value, Set(node.Left, key, value), node.Right))
 142996            : Balance(new Node(node.Key, node.Value, node.Left, Set(node.Right, key, value)));
 97    }
 98
 99    private static Node Set(Node? node, int key, T value, ref int copiedNodeCount)
 100    {
 282084101        if (node == null)
 17122102            return NewNode(key, value, null, null, ref copiedNodeCount);
 264962103        if (key == node.Key)
 16224104            return ReferenceEquals(value, node.Value)
 16224105                ? node
 16224106                : NewNode(key, value, node.Left, node.Right, ref copiedNodeCount);
 248738107        return key < node.Key
 248738108            ? Balance(
 248738109                NewNode(
 248738110                    node.Key,
 248738111                    node.Value,
 248738112                    Set(node.Left, key, value, ref copiedNodeCount),
 248738113                    node.Right,
 248738114                    ref copiedNodeCount),
 248738115                ref copiedNodeCount)
 248738116            : Balance(
 248738117                NewNode(
 248738118                    node.Key,
 248738119                    node.Value,
 248738120                    node.Left,
 248738121                    Set(node.Right, key, value, ref copiedNodeCount),
 248738122                    ref copiedNodeCount),
 248738123                ref copiedNodeCount);
 124    }
 125
 126    private static Node? Remove(Node? node, int key, out bool removed)
 127    {
 16128        if (node == null)
 129        {
 2130            removed = false;
 2131            return null;
 132        }
 14133        if (key < node.Key)
 134        {
 3135            Node? left = Remove(node.Left, key, out removed);
 3136            return removed ? Balance(new Node(node.Key, node.Value, left, node.Right)) : node;
 137        }
 11138        if (key > node.Key)
 139        {
 5140            Node? right = Remove(node.Right, key, out removed);
 5141            return removed ? Balance(new Node(node.Key, node.Value, node.Left, right)) : node;
 142        }
 6143        removed = true;
 6144        if (node.Left == null)
 4145            return node.Right;
 2146        if (node.Right == null)
 1147            return node.Left;
 1148        Node successor = node.Right;
 2149        while (successor.Left != null)
 1150            successor = successor.Left;
 1151        return Balance(new Node(
 1152            successor.Key,
 1153            successor.Value,
 1154            node.Left,
 1155            RemoveMinimum(node.Right)));
 156    }
 157
 158    private static Node? Remove(
 159        Node? node,
 160        int key,
 161        out bool removed,
 162        ref int copiedNodeCount)
 163    {
 74164        if (node == null)
 165        {
 3166            removed = false;
 3167            return null;
 168        }
 71169        if (key < node.Key)
 170        {
 4171            Node? left = Remove(node.Left, key, out removed, ref copiedNodeCount);
 4172            return removed
 4173                ? Balance(
 4174                    NewNode(node.Key, node.Value, left, node.Right, ref copiedNodeCount),
 4175                    ref copiedNodeCount)
 4176                : node;
 177        }
 67178        if (key > node.Key)
 179        {
 8180            Node? right = Remove(node.Right, key, out removed, ref copiedNodeCount);
 8181            return removed
 8182                ? Balance(
 8183                    NewNode(node.Key, node.Value, node.Left, right, ref copiedNodeCount),
 8184                    ref copiedNodeCount)
 8185                : node;
 186        }
 59187        removed = true;
 59188        if (node.Left == null)
 57189            return node.Right;
 2190        if (node.Right == null)
 1191            return node.Left;
 1192        Node successor = node.Right;
 2193        while (successor.Left != null)
 1194            successor = successor.Left;
 1195        return Balance(
 1196            NewNode(
 1197                successor.Key,
 1198                successor.Value,
 1199                node.Left,
 1200                RemoveMinimum(node.Right, ref copiedNodeCount),
 1201                ref copiedNodeCount),
 1202            ref copiedNodeCount);
 203    }
 204
 2205    private static Node? RemoveMinimum(Node node) => node.Left == null
 2206        ? node.Right
 2207        : Balance(new Node(node.Key, node.Value, RemoveMinimum(node.Left), node.Right));
 208
 2209    private static Node? RemoveMinimum(Node node, ref int copiedNodeCount) => node.Left == null
 2210        ? node.Right
 2211        : Balance(
 2212            NewNode(
 2213                node.Key,
 2214                node.Value,
 2215                RemoveMinimum(node.Left, ref copiedNodeCount),
 2216                node.Right,
 2217                ref copiedNodeCount),
 2218            ref copiedNodeCount);
 219
 220    private static Node Balance(Node node)
 221    {
 1437222        int balance = HeightOf(node.Left) - HeightOf(node.Right);
 1437223        if (balance > 1)
 224        {
 2225            if (HeightOf(node.Left!.Left) < HeightOf(node.Left.Right))
 1226                node = new Node(node.Key, node.Value, RotateLeft(node.Left), node.Right);
 2227            return RotateRight(node);
 228        }
 1435229        if (balance < -1)
 230        {
 298231            if (HeightOf(node.Right!.Right) < HeightOf(node.Right.Left))
 3232                node = new Node(node.Key, node.Value, node.Left, RotateRight(node.Right));
 298233            return RotateLeft(node);
 234        }
 1137235        return node;
 236    }
 237
 238    private static Node Balance(Node node, ref int copiedNodeCount)
 239    {
 248747240        int balance = HeightOf(node.Left) - HeightOf(node.Right);
 248747241        if (balance > 1)
 242        {
 2243            if (HeightOf(node.Left!.Left) < HeightOf(node.Left.Right))
 244            {
 1245                node = NewNode(
 1246                    node.Key,
 1247                    node.Value,
 1248                    RotateLeft(node.Left, ref copiedNodeCount),
 1249                    node.Right,
 1250                    ref copiedNodeCount);
 251            }
 2252            return RotateRight(node, ref copiedNodeCount);
 253        }
 248745254        if (balance < -1)
 255        {
 16696256            if (HeightOf(node.Right!.Right) < HeightOf(node.Right.Left))
 257            {
 1258                node = NewNode(
 1259                    node.Key,
 1260                    node.Value,
 1261                    node.Left,
 1262                    RotateRight(node.Right, ref copiedNodeCount),
 1263                    ref copiedNodeCount);
 264            }
 16696265            return RotateLeft(node, ref copiedNodeCount);
 266        }
 232049267        return node;
 268    }
 269
 270    private static Node RotateLeft(Node node)
 271    {
 299272        Node right = node.Right!;
 299273        return new Node(
 299274            right.Key,
 299275            right.Value,
 299276            new Node(node.Key, node.Value, node.Left, right.Left),
 299277            right.Right);
 278    }
 279
 280    private static Node RotateRight(Node node)
 281    {
 5282        Node left = node.Left!;
 5283        return new Node(
 5284            left.Key,
 5285            left.Value,
 5286            left.Left,
 5287            new Node(node.Key, node.Value, left.Right, node.Right));
 288    }
 289
 290    private static Node RotateLeft(Node node, ref int copiedNodeCount)
 291    {
 16697292        Node right = node.Right!;
 16697293        Node left = NewNode(
 16697294            node.Key,
 16697295            node.Value,
 16697296            node.Left,
 16697297            right.Left,
 16697298            ref copiedNodeCount);
 16697299        return NewNode(right.Key, right.Value, left, right.Right, ref copiedNodeCount);
 300    }
 301
 302    private static Node RotateRight(Node node, ref int copiedNodeCount)
 303    {
 3304        Node left = node.Left!;
 3305        Node right = NewNode(
 3306            node.Key,
 3307            node.Value,
 3308            left.Right,
 3309            node.Right,
 3310            ref copiedNodeCount);
 3311        return NewNode(left.Key, left.Value, left.Left, right, ref copiedNodeCount);
 312    }
 313
 314    private static Node NewNode(
 315        int key,
 316        T value,
 317        Node? left,
 318        Node? right,
 319        ref int copiedNodeCount)
 320    {
 315494321        copiedNodeCount = checked(copiedNodeCount + 1);
 315494322        return new Node(key, value, left, right);
 323    }
 324
 725498325    private static int CountOf(Node? node) => node?.Count ?? 0;
 1175400326    private static int HeightOf(Node? node) => node?.Height ?? 0;
 327
 328    private sealed class Node
 329    {
 320518330        internal Node(int key, T value, Node? left, Node? right)
 331        {
 320518332            Key = key;
 320518333            Value = value;
 320518334            Left = left;
 320518335            Right = right;
 320518336            Height = Math.Max(HeightOf(left), HeightOf(right)) + 1;
 320518337            Count = CountOf(left) + CountOf(right) + 1;
 320518338        }
 339
 340        internal int Key { get; }
 341        internal T Value { get; }
 342        internal Node? Left { get; }
 343        internal Node? Right { get; }
 344        internal int Height { get; }
 345        internal int Count { get; }
 346    }
 347}
Generated by: ReportGenerator 5.5.11.0
09/02/2026 - 04:28:06
GitHub | reportgenerator.io

Methods/Properties

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