< Summary

Information
Class: Trailblazer.Pathing.PersistentStringMap<T>
Assembly: Trailblazer
File(s): /home/runner/work/Trailblazer/Trailblazer/src/Trailblazer/Pathing/Map/Operations/PersistentStringMap.cs
Line coverage
100%
Covered lines: 201
Uncovered lines: 0
Coverable lines: 201
Total lines: 361
Line coverage: 100%
Branch coverage
100%
Covered branches: 80
Total branches: 80
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_PersistentNodeCount()100%11100%
get_RetainedBytes()100%11100%
ContainsKey(...)100%11100%
TryGetValue(...)100%66100%
Set(...)100%11100%
Set(...)100%11100%
Remove(...)100%22100%
Remove(...)100%22100%
GetValueAt(...)100%11100%
GetKeyAt(...)100%11100%
GetNodeAt(...)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/Map/Operations/PersistentStringMap.cs

#LineLine coverage
 1//=======================================================================
 2// PersistentStringMap.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>Provides an ordinal string map whose updates copy only one balanced-tree path.</summary>
 13internal sealed class PersistentStringMap<T>
 14{
 15    private readonly Node? _root;
 16
 17    internal static PersistentStringMap<T> Empty { get; } = new(null);
 18
 17915519    private PersistentStringMap(Node? root)
 20    {
 17915521        _root = root;
 17915522    }
 23
 2160309924    internal int Count => CountOf(_root);
 25
 306423326    internal int PersistentNodeCount => Count;
 27
 293989728    internal long RetainedBytes => checked(32L + ((long)Count * 64L));
 29
 7963530    internal bool ContainsKey(string key) => TryGetValue(key, out _);
 31
 32    internal bool TryGetValue(string key, out T value)
 33    {
 1356651834        Node? node = _root;
 2184801535        while (node != null)
 36        {
 1925287737            int comparison = string.CompareOrdinal(key, node.Key);
 1925287738            if (comparison == 0)
 39            {
 1097138040                value = node.Value;
 1097138041                return true;
 42            }
 828149743            node = comparison < 0 ? node.Left : node.Right;
 44        }
 259513845        value = default!;
 259513846        return false;
 47    }
 48
 49    internal PersistentStringMap<T> Set(string key, T value) =>
 7550050        new(Set(_root, key, value));
 51
 52    internal PersistentStringMap<T> Set(string key, T value, out int copiedNodeCount)
 53    {
 10307254        copiedNodeCount = 0;
 10307255        return new PersistentStringMap<T>(Set(_root, key, value, ref copiedNodeCount));
 56    }
 57
 58    internal PersistentStringMap<T> Remove(string key, out bool removed)
 59    {
 7860        Node? root = Remove(_root, key, out removed);
 7861        return removed ? new PersistentStringMap<T>(root) : this;
 62    }
 63
 64    internal PersistentStringMap<T> Remove(
 65        string key,
 66        out bool removed,
 67        out int copiedNodeCount)
 68    {
 50569        copiedNodeCount = 0;
 50570        Node? root = Remove(_root, key, out removed, ref copiedNodeCount);
 50571        return removed ? new PersistentStringMap<T>(root) : this;
 72    }
 73
 74    internal T GetValueAt(int ordinal)
 654419075        => GetNodeAt(ordinal).Value;
 76
 77    internal string GetKeyAt(int ordinal)
 174602278        => GetNodeAt(ordinal).Key;
 79
 80    private Node GetNodeAt(int ordinal)
 81    {
 829021282        SwiftThrowHelper.ThrowIfArgumentOutOfRange(
 829021283            (uint)ordinal >= (uint)Count,
 829021284            ordinal,
 829021285            nameof(ordinal));
 829021286        Node node = _root!;
 617115087        while (true)
 88        {
 1717396389            int leftCount = CountOf(node.Left);
 1717396390            if (ordinal < leftCount)
 271260191                node = node.Left!;
 1446136292            else if (ordinal == leftCount)
 829021293                return node;
 94            else
 95            {
 617115096                ordinal -= leftCount + 1;
 617115097                node = node.Right!;
 98            }
 99        }
 100    }
 101
 102    private static Node Set(Node? node, string key, T value)
 103    {
 155296104        if (node == null)
 20862105            return new Node(key, value, null, null);
 134434106        int comparison = string.CompareOrdinal(key, node.Key);
 134434107        if (comparison == 0)
 54638108            return new Node(key, value, node.Left, node.Right);
 79796109        return comparison < 0
 79796110            ? Balance(new Node(node.Key, node.Value, Set(node.Left, key, value), node.Right))
 79796111            : Balance(new Node(node.Key, node.Value, node.Left, Set(node.Right, key, value)));
 112    }
 113
 114    private static Node Set(Node? node, string key, T value, ref int copiedNodeCount)
 115    {
 283335116        if (node == null)
 21112117            return NewNode(key, value, null, null, ref copiedNodeCount);
 262223118        int comparison = string.CompareOrdinal(key, node.Key);
 262223119        if (comparison == 0)
 81960120            return NewNode(key, value, node.Left, node.Right, ref copiedNodeCount);
 180263121        return comparison < 0
 180263122            ? Balance(
 180263123                NewNode(
 180263124                    node.Key,
 180263125                    node.Value,
 180263126                    Set(node.Left, key, value, ref copiedNodeCount),
 180263127                    node.Right,
 180263128                    ref copiedNodeCount),
 180263129                ref copiedNodeCount)
 180263130            : Balance(
 180263131                NewNode(
 180263132                    node.Key,
 180263133                    node.Value,
 180263134                    node.Left,
 180263135                    Set(node.Right, key, value, ref copiedNodeCount),
 180263136                    ref copiedNodeCount),
 180263137                ref copiedNodeCount);
 138    }
 139
 140    private static Node? Remove(Node? node, string key, out bool removed)
 141    {
 89142        if (node == null)
 143        {
 9144            removed = false;
 9145            return null;
 146        }
 80147        int comparison = string.CompareOrdinal(key, node.Key);
 80148        if (comparison < 0)
 149        {
 5150            Node? left = Remove(node.Left, key, out removed);
 5151            return removed ? Balance(new Node(node.Key, node.Value, left, node.Right)) : node;
 152        }
 75153        if (comparison > 0)
 154        {
 6155            Node? right = Remove(node.Right, key, out removed);
 6156            return removed ? Balance(new Node(node.Key, node.Value, node.Left, right)) : node;
 157        }
 158
 69159        removed = true;
 69160        if (node.Left == null)
 67161            return node.Right;
 2162        if (node.Right == null)
 1163            return node.Left;
 1164        Node successor = FindMinimum(node.Right);
 1165        Node? successorRight = RemoveMinimum(node.Right);
 1166        return Balance(new Node(successor.Key, successor.Value, node.Left, successorRight));
 167    }
 168
 169    private static Node? Remove(
 170        Node? node,
 171        string key,
 172        out bool removed,
 173        ref int copiedNodeCount)
 174    {
 657175        if (node == null)
 176        {
 9177            removed = false;
 9178            return null;
 179        }
 648180        int comparison = string.CompareOrdinal(key, node.Key);
 648181        if (comparison < 0)
 182        {
 91183            Node? left = Remove(node.Left, key, out removed, ref copiedNodeCount);
 91184            return removed
 91185                ? Balance(
 91186                    NewNode(node.Key, node.Value, left, node.Right, ref copiedNodeCount),
 91187                    ref copiedNodeCount)
 91188                : node;
 189        }
 557190        if (comparison > 0)
 191        {
 61192            Node? right = Remove(node.Right, key, out removed, ref copiedNodeCount);
 61193            return removed
 61194                ? Balance(
 61195                    NewNode(node.Key, node.Value, node.Left, right, ref copiedNodeCount),
 61196                    ref copiedNodeCount)
 61197                : node;
 198        }
 199
 496200        removed = true;
 496201        if (node.Left == null)
 454202            return node.Right;
 42203        if (node.Right == null)
 11204            return node.Left;
 31205        Node successor = FindMinimum(node.Right);
 31206        Node? successorRight = RemoveMinimum(node.Right, ref copiedNodeCount);
 31207        return Balance(
 31208            NewNode(successor.Key, successor.Value, node.Left, successorRight, ref copiedNodeCount),
 31209            ref copiedNodeCount);
 210    }
 211
 212    private static Node FindMinimum(Node node)
 213    {
 45214        while (node.Left != null)
 13215            node = node.Left;
 32216        return node;
 217    }
 218
 2219    private static Node? RemoveMinimum(Node node) => node.Left == null
 2220        ? node.Right
 2221        : Balance(new Node(node.Key, node.Value, RemoveMinimum(node.Left), node.Right));
 222
 43223    private static Node? RemoveMinimum(Node node, ref int copiedNodeCount) => node.Left == null
 43224        ? node.Right
 43225        : Balance(
 43226            NewNode(
 43227                node.Key,
 43228                node.Value,
 43229                RemoveMinimum(node.Left, ref copiedNodeCount),
 43230                node.Right,
 43231                ref copiedNodeCount),
 43232            ref copiedNodeCount);
 233
 234    private static Node Balance(Node node)
 235    {
 79803236        int balance = HeightOf(node.Left) - HeightOf(node.Right);
 79803237        if (balance > 1)
 238        {
 45239            if (HeightOf(node.Left!.Left) < HeightOf(node.Left.Right))
 19240                node = new Node(node.Key, node.Value, RotateLeft(node.Left), node.Right);
 45241            return RotateRight(node);
 242        }
 79758243        if (balance < -1)
 244        {
 8837245            if (HeightOf(node.Right!.Right) < HeightOf(node.Right.Left))
 38246                node = new Node(node.Key, node.Value, node.Left, RotateRight(node.Right));
 8837247            return RotateLeft(node);
 248        }
 70921249        return node;
 250    }
 251
 252    private static Node Balance(Node node, ref int copiedNodeCount)
 253    {
 180452254        int balance = HeightOf(node.Left) - HeightOf(node.Right);
 180452255        if (balance > 1)
 256        {
 122257            if (HeightOf(node.Left!.Left) < HeightOf(node.Left.Right))
 258            {
 68259                node = NewNode(
 68260                    node.Key,
 68261                    node.Value,
 68262                    RotateLeft(node.Left, ref copiedNodeCount),
 68263                    node.Right,
 68264                    ref copiedNodeCount);
 265            }
 122266            return RotateRight(node, ref copiedNodeCount);
 267        }
 180330268        if (balance < -1)
 269        {
 13284270            if (HeightOf(node.Right!.Right) < HeightOf(node.Right.Left))
 271            {
 18272                node = NewNode(
 18273                    node.Key,
 18274                    node.Value,
 18275                    node.Left,
 18276                    RotateRight(node.Right, ref copiedNodeCount),
 18277                    ref copiedNodeCount);
 278            }
 13284279            return RotateLeft(node, ref copiedNodeCount);
 280        }
 167046281        return node;
 282    }
 283
 284    private static Node RotateLeft(Node node)
 285    {
 8856286        Node right = node.Right!;
 8856287        return new Node(
 8856288            right.Key,
 8856289            right.Value,
 8856290            new Node(node.Key, node.Value, node.Left, right.Left),
 8856291            right.Right);
 292    }
 293
 294    private static Node RotateRight(Node node)
 295    {
 83296        Node left = node.Left!;
 83297        return new Node(
 83298            left.Key,
 83299            left.Value,
 83300            left.Left,
 83301            new Node(node.Key, node.Value, left.Right, node.Right));
 302    }
 303
 304    private static Node RotateLeft(Node node, ref int copiedNodeCount)
 305    {
 13352306        Node right = node.Right!;
 13352307        Node left = NewNode(
 13352308            node.Key,
 13352309            node.Value,
 13352310            node.Left,
 13352311            right.Left,
 13352312            ref copiedNodeCount);
 13352313        return NewNode(right.Key, right.Value, left, right.Right, ref copiedNodeCount);
 314    }
 315
 316    private static Node RotateRight(Node node, ref int copiedNodeCount)
 317    {
 140318        Node left = node.Left!;
 140319        Node right = NewNode(
 140320            node.Key,
 140321            node.Value,
 140322            left.Right,
 140323            node.Right,
 140324            ref copiedNodeCount);
 140325        return NewNode(left.Key, left.Value, left.Left, right, ref copiedNodeCount);
 326    }
 327
 328    private static Node NewNode(
 329        string key,
 330        T value,
 331        Node? left,
 332        Node? right,
 333        ref int copiedNodeCount)
 334    {
 310594335        copiedNodeCount = checked(copiedNodeCount + 1);
 310594336        return new Node(key, value, left, right);
 337    }
 338
 39744726339    private static int CountOf(Node? node) => node?.Count ?? 0;
 1532750340    private static int HeightOf(Node? node) => node?.Height ?? 0;
 341
 342    private sealed class Node
 343    {
 483832344        internal Node(string key, T value, Node? left, Node? right)
 345        {
 483832346            Key = key;
 483832347            Value = value;
 483832348            Left = left;
 483832349            Right = right;
 483832350            Height = Math.Max(HeightOf(left), HeightOf(right)) + 1;
 483832351            Count = CountOf(left) + CountOf(right) + 1;
 483832352        }
 353
 354        internal string Key { get; }
 355        internal T Value { get; }
 356        internal Node? Left { get; }
 357        internal Node? Right { get; }
 358        internal int Height { get; }
 359        internal int Count { get; }
 360    }
 361}
Generated by: ReportGenerator 5.5.11.0
09/02/2026 - 04:28:06
GitHub | reportgenerator.io

Methods/Properties

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