< Summary

Information
Class: Trailblazer.Pathing.PersistentGridConfigurationMap<T>
Assembly: Trailblazer
File(s): /home/runner/work/Trailblazer/Trailblazer/src/Trailblazer/Pathing/Graph/PersistentGridConfigurationMap.cs
Line coverage
100%
Covered lines: 200
Uncovered lines: 0
Coverable lines: 200
Total lines: 355
Line coverage: 100%
Branch coverage
100%
Covered branches: 100
Total branches: 100
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%
TryGetValue(...)100%66100%
GetValueAt(...)100%11100%
Set(...)100%11100%
Set(...)100%11100%
Remove(...)100%11100%
Remove(...)100%22100%
Set(...)100%66100%
Set(...)100%66100%
Remove(...)100%1616100%
Remove(...)100%1616100%
Compare(...)100%2222100%
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%
GetNodeAt(...)100%66100%
.ctor(...)100%11100%

File(s)

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

#LineLine coverage
 1//=======================================================================
 2// PersistentGridConfigurationMap.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.Configuration;
 10
 11namespace Trailblazer.Pathing;
 12
 13/// <summary>Stores exact normalized grid-address values in an immutable balanced tree.</summary>
 14internal sealed class PersistentGridConfigurationMap<T>
 15{
 16    private readonly Node? _root;
 17
 18    internal static PersistentGridConfigurationMap<T> Empty { get; } = new(null);
 19
 689620    private PersistentGridConfigurationMap(Node? root) => _root = root;
 21
 26284322    internal int Count => CountOf(_root);
 23
 13009424    internal long RetainedBytes => checked(32L + ((long)Count * 144L));
 25
 26    internal bool TryGetValue(GridConfigurationKey key, out T value)
 27    {
 10066528        Node? node = _root;
 23522829        while (node != null)
 30        {
 23175431            int comparison = Compare(key, node.Key);
 23175432            if (comparison == 0)
 33            {
 9719134                value = node.Value;
 9719135                return true;
 36            }
 13456337            node = comparison < 0 ? node.Left : node.Right;
 38        }
 347439        value = default!;
 347440        return false;
 41    }
 42
 97343    internal T GetValueAt(int ordinal) => GetNodeAt(ordinal).Value;
 44
 45    internal PersistentGridConfigurationMap<T> Set(GridConfigurationKey key, T value) =>
 68946        new(Set(_root, key, value));
 47
 48    internal PersistentGridConfigurationMap<T> Set(
 49        GridConfigurationKey key,
 50        T value,
 51        out int copiedNodeCount)
 52    {
 271153        copiedNodeCount = 0;
 271154        return new PersistentGridConfigurationMap<T>(
 271155            Set(_root, key, value, ref copiedNodeCount));
 56    }
 57
 58    internal PersistentGridConfigurationMap<T> Remove(GridConfigurationKey key) =>
 759        new(Remove(_root, key, out _));
 60
 61    internal PersistentGridConfigurationMap<T> Remove(
 62        GridConfigurationKey key,
 63        out bool removed,
 64        out int copiedNodeCount)
 65    {
 4266        copiedNodeCount = 0;
 4267        Node? root = Remove(_root, key, out removed, ref copiedNodeCount);
 4268        return removed ? new PersistentGridConfigurationMap<T>(root) : this;
 69    }
 70
 71    private static Node Set(Node? node, GridConfigurationKey key, T value)
 72    {
 80273        if (node == null)
 68874            return new Node(key, value, null, null);
 11475        int comparison = Compare(key, node.Key);
 11476        if (comparison == 0)
 177            return new Node(key, value, node.Left, node.Right);
 11378        return comparison < 0
 11379            ? Balance(new Node(node.Key, node.Value, Set(node.Left, key, value), node.Right))
 11380            : Balance(new Node(node.Key, node.Value, node.Left, Set(node.Right, key, value)));
 81    }
 82
 83    private static Node Set(
 84        Node? node,
 85        GridConfigurationKey key,
 86        T value,
 87        ref int copiedNodeCount)
 88    {
 536189        if (node == null)
 243690            return NewNode(key, value, null, null, ref copiedNodeCount);
 292591        int comparison = Compare(key, node.Key);
 292592        if (comparison == 0)
 27593            return NewNode(key, value, node.Left, node.Right, ref copiedNodeCount);
 265094        return comparison < 0
 265095            ? Balance(
 265096                NewNode(
 265097                    node.Key,
 265098                    node.Value,
 265099                    Set(node.Left, key, value, ref copiedNodeCount),
 2650100                    node.Right,
 2650101                    ref copiedNodeCount),
 2650102                ref copiedNodeCount)
 2650103            : Balance(
 2650104                NewNode(
 2650105                    node.Key,
 2650106                    node.Value,
 2650107                    node.Left,
 2650108                    Set(node.Right, key, value, ref copiedNodeCount),
 2650109                    ref copiedNodeCount),
 2650110                ref copiedNodeCount);
 111    }
 112
 113    private static Node? Remove(Node? node, GridConfigurationKey key, out bool removed)
 114    {
 18115        if (node == null)
 116        {
 2117            removed = false;
 2118            return null;
 119        }
 16120        int comparison = Compare(key, node.Key);
 16121        if (comparison < 0)
 122        {
 4123            Node? left = Remove(node.Left, key, out removed);
 4124            return removed ? Balance(new Node(node.Key, node.Value, left, node.Right)) : node;
 125        }
 12126        if (comparison > 0)
 127        {
 6128            Node? right = Remove(node.Right, key, out removed);
 6129            return removed ? Balance(new Node(node.Key, node.Value, node.Left, right)) : node;
 130        }
 6131        removed = true;
 6132        if (node.Left == null)
 4133            return node.Right;
 2134        if (node.Right == null)
 1135            return node.Left;
 1136        Node successor = node.Right;
 2137        while (successor.Left != null)
 1138            successor = successor.Left;
 1139        Node? successorRight = Remove(node.Right, successor.Key, out _);
 1140        return Balance(new Node(successor.Key, successor.Value, node.Left, successorRight));
 141    }
 142
 143    private static Node? Remove(
 144        Node? node,
 145        GridConfigurationKey key,
 146        out bool removed,
 147        ref int copiedNodeCount)
 148    {
 62149        if (node == null)
 150        {
 2151            removed = false;
 2152            return null;
 153        }
 60154        int comparison = Compare(key, node.Key);
 60155        if (comparison < 0)
 156        {
 5157            Node? left = Remove(node.Left, key, out removed, ref copiedNodeCount);
 5158            return removed
 5159                ? Balance(
 5160                    NewNode(node.Key, node.Value, left, node.Right, ref copiedNodeCount),
 5161                    ref copiedNodeCount)
 5162                : node;
 163        }
 55164        if (comparison > 0)
 165        {
 14166            Node? right = Remove(node.Right, key, out removed, ref copiedNodeCount);
 14167            return removed
 14168                ? Balance(
 14169                    NewNode(node.Key, node.Value, node.Left, right, ref copiedNodeCount),
 14170                    ref copiedNodeCount)
 14171                : node;
 172        }
 41173        removed = true;
 41174        if (node.Left == null)
 39175            return node.Right;
 2176        if (node.Right == null)
 1177            return node.Left;
 1178        Node successor = node.Right;
 2179        while (successor.Left != null)
 1180            successor = successor.Left;
 1181        Node? successorRight = Remove(node.Right, successor.Key, out _, ref copiedNodeCount);
 1182        return Balance(
 1183            NewNode(successor.Key, successor.Value, node.Left, successorRight, ref copiedNodeCount),
 1184            ref copiedNodeCount);
 185    }
 186
 187    private static int Compare(GridConfigurationKey left, GridConfigurationKey right)
 188    {
 234869189        int value = left.BoundsMin.X.CompareTo(right.BoundsMin.X);
 369083190        if (value != 0) return value;
 100655191        value = left.BoundsMin.Y.CompareTo(right.BoundsMin.Y);
 102983192        if (value != 0) return value;
 98327193        value = left.BoundsMin.Z.CompareTo(right.BoundsMin.Z);
 98511194        if (value != 0) return value;
 98143195        value = left.BoundsMax.X.CompareTo(right.BoundsMax.X);
 98646196        if (value != 0) return value;
 97640197        value = left.BoundsMax.Y.CompareTo(right.BoundsMax.Y);
 97743198        if (value != 0) return value;
 97537199        value = left.BoundsMax.Z.CompareTo(right.BoundsMax.Z);
 97542200        if (value != 0) return value;
 97532201        value = ((int)left.TopologyKind).CompareTo((int)right.TopologyKind);
 97535202        if (value != 0) return value;
 97529203        value = left.TopologyMetrics.CellRadius.CompareTo(right.TopologyMetrics.CellRadius);
 97531204        if (value != 0) return value;
 97527205        value = left.TopologyMetrics.CellWidth.CompareTo(right.TopologyMetrics.CellWidth);
 97534206        if (value != 0) return value;
 97520207        value = left.TopologyMetrics.LayerHeight.CompareTo(right.TopologyMetrics.LayerHeight);
 97524208        if (value != 0) return value;
 97516209        value = left.TopologyMetrics.CellLength.CompareTo(right.TopologyMetrics.CellLength);
 97516210        return value != 0
 97516211            ? value
 97516212            : ((int)left.TopologyMetrics.HexOrientation).CompareTo(
 97516213                (int)right.TopologyMetrics.HexOrientation);
 214    }
 215
 216    private static Node Balance(Node node)
 217    {
 120218        int balance = HeightOf(node.Left) - HeightOf(node.Right);
 120219        if (balance > 1)
 220        {
 3221            if (HeightOf(node.Left!.Left) < HeightOf(node.Left.Right))
 1222                node = new Node(node.Key, node.Value, RotateLeft(node.Left), node.Right);
 3223            return RotateRight(node);
 224        }
 117225        if (balance < -1)
 226        {
 20227            if (HeightOf(node.Right!.Right) < HeightOf(node.Right.Left))
 5228                node = new Node(node.Key, node.Value, node.Left, RotateRight(node.Right));
 20229            return RotateLeft(node);
 230        }
 97231        return node;
 232    }
 233
 234    private static Node Balance(Node node, ref int copiedNodeCount)
 235    {
 2666236        int balance = HeightOf(node.Left) - HeightOf(node.Right);
 2666237        if (balance > 1)
 238        {
 47239            if (HeightOf(node.Left!.Left) < HeightOf(node.Left.Right))
 240            {
 5241                node = NewNode(
 5242                    node.Key,
 5243                    node.Value,
 5244                    RotateLeft(node.Left, ref copiedNodeCount),
 5245                    node.Right,
 5246                    ref copiedNodeCount);
 247            }
 47248            return RotateRight(node, ref copiedNodeCount);
 249        }
 2619250        if (balance < -1)
 251        {
 378252            if (HeightOf(node.Right!.Right) < HeightOf(node.Right.Left))
 253            {
 3254                node = NewNode(
 3255                    node.Key,
 3256                    node.Value,
 3257                    node.Left,
 3258                    RotateRight(node.Right, ref copiedNodeCount),
 3259                    ref copiedNodeCount);
 260            }
 378261            return RotateLeft(node, ref copiedNodeCount);
 262        }
 2241263        return node;
 264    }
 265
 266    private static Node RotateLeft(Node node)
 267    {
 21268        Node right = node.Right!;
 21269        return new Node(right.Key, right.Value, new Node(node.Key, node.Value, node.Left, right.Left), right.Right);
 270    }
 271
 272    private static Node RotateRight(Node node)
 273    {
 8274        Node left = node.Left!;
 8275        return new Node(left.Key, left.Value, left.Left, new Node(node.Key, node.Value, left.Right, node.Right));
 276    }
 277
 278    private static Node RotateLeft(Node node, ref int copiedNodeCount)
 279    {
 383280        Node right = node.Right!;
 383281        Node left = NewNode(
 383282            node.Key,
 383283            node.Value,
 383284            node.Left,
 383285            right.Left,
 383286            ref copiedNodeCount);
 383287        return NewNode(right.Key, right.Value, left, right.Right, ref copiedNodeCount);
 288    }
 289
 290    private static Node RotateRight(Node node, ref int copiedNodeCount)
 291    {
 50292        Node left = node.Left!;
 50293        Node right = NewNode(
 50294            node.Key,
 50295            node.Value,
 50296            left.Right,
 50297            node.Right,
 50298            ref copiedNodeCount);
 50299        return NewNode(left.Key, left.Value, left.Left, right, ref copiedNodeCount);
 300    }
 301
 302    private static Node NewNode(
 303        GridConfigurationKey key,
 304        T value,
 305        Node? left,
 306        Node? right,
 307        ref int copiedNodeCount)
 308    {
 6251309        copiedNodeCount = checked(copiedNodeCount + 1);
 6251310        return new Node(key, value, left, right);
 311    }
 312
 278102313    private static int CountOf(Node? node) => node?.Count ?? 0;
 20716314    private static int HeightOf(Node? node) => node?.Height ?? 0;
 315
 316    private Node GetNodeAt(int ordinal)
 317    {
 973318        if ((uint)ordinal >= (uint)Count)
 1319            throw new ArgumentOutOfRangeException(nameof(ordinal));
 972320        Node node = _root!;
 24321        while (true)
 322        {
 1011323            int leftCount = CountOf(node.Left);
 1011324            if (ordinal < leftCount)
 325            {
 15326                node = node.Left!;
 15327                continue;
 328            }
 996329            if (ordinal == leftCount)
 972330                return node;
 24331            ordinal -= leftCount + 1;
 24332            node = node.Right!;
 333        }
 334    }
 335
 336    private sealed class Node
 337    {
 7124338        internal Node(GridConfigurationKey key, T value, Node? left, Node? right)
 339        {
 7124340            Key = key;
 7124341            Value = value;
 7124342            Left = left;
 7124343            Right = right;
 7124344            Height = Math.Max(HeightOf(left), HeightOf(right)) + 1;
 7124345            Count = CountOf(left) + CountOf(right) + 1;
 7124346        }
 347
 348        internal GridConfigurationKey Key { get; }
 349        internal T Value { get; }
 350        internal Node? Left { get; }
 351        internal Node? Right { get; }
 352        internal int Height { get; }
 353        internal int Count { get; }
 354    }
 355}
Generated by: ReportGenerator 5.5.11.0
09/02/2026 - 04:28:06
GitHub | reportgenerator.io

Methods/Properties

.ctor(Trailblazer.Pathing.PersistentGridConfigurationMap`1/Node<T>)
get_Count()
get_RetainedBytes()
TryGetValue(GridForge.Configuration.GridConfigurationKey,T&)
GetValueAt(System.Int32)
Set(GridForge.Configuration.GridConfigurationKey,T)
Set(GridForge.Configuration.GridConfigurationKey,T,System.Int32&)
Remove(GridForge.Configuration.GridConfigurationKey)
Remove(GridForge.Configuration.GridConfigurationKey,System.Boolean&,System.Int32&)
Set(Trailblazer.Pathing.PersistentGridConfigurationMap`1/Node<T>,GridForge.Configuration.GridConfigurationKey,T)
Set(Trailblazer.Pathing.PersistentGridConfigurationMap`1/Node<T>,GridForge.Configuration.GridConfigurationKey,T,System.Int32&)
Remove(Trailblazer.Pathing.PersistentGridConfigurationMap`1/Node<T>,GridForge.Configuration.GridConfigurationKey,System.Boolean&)
Remove(Trailblazer.Pathing.PersistentGridConfigurationMap`1/Node<T>,GridForge.Configuration.GridConfigurationKey,System.Boolean&,System.Int32&)
Compare(GridForge.Configuration.GridConfigurationKey,GridForge.Configuration.GridConfigurationKey)
Balance(Trailblazer.Pathing.PersistentGridConfigurationMap`1/Node<T>)
Balance(Trailblazer.Pathing.PersistentGridConfigurationMap`1/Node<T>,System.Int32&)
RotateLeft(Trailblazer.Pathing.PersistentGridConfigurationMap`1/Node<T>)
RotateRight(Trailblazer.Pathing.PersistentGridConfigurationMap`1/Node<T>)
RotateLeft(Trailblazer.Pathing.PersistentGridConfigurationMap`1/Node<T>,System.Int32&)
RotateRight(Trailblazer.Pathing.PersistentGridConfigurationMap`1/Node<T>,System.Int32&)
NewNode(GridForge.Configuration.GridConfigurationKey,T,Trailblazer.Pathing.PersistentGridConfigurationMap`1/Node<T>,Trailblazer.Pathing.PersistentGridConfigurationMap`1/Node<T>,System.Int32&)
CountOf(Trailblazer.Pathing.PersistentGridConfigurationMap`1/Node<T>)
HeightOf(Trailblazer.Pathing.PersistentGridConfigurationMap`1/Node<T>)
GetNodeAt(System.Int32)
.ctor(GridForge.Configuration.GridConfigurationKey,T,Trailblazer.Pathing.PersistentGridConfigurationMap`1/Node<T>,Trailblazer.Pathing.PersistentGridConfigurationMap`1/Node<T>)