< Summary

Information
Class: Trailblazer.Pathing.NavigationSeamEditTree<T1, T2>
Assembly: Trailblazer
File(s): /home/runner/work/Trailblazer/Trailblazer/src/Trailblazer/Pathing/Graph/NavigationSeamEditTree.cs
Line coverage
100%
Covered lines: 223
Uncovered lines: 0
Coverable lines: 223
Total lines: 434
Line coverage: 100%
Branch coverage
100%
Covered branches: 72
Total branches: 72
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%
.ctor(...)100%11100%
get_RetainedBytes()100%11100%
get_PersistentPageCount()100%11100%
TryGetValue(...)100%66100%
Edit(...)100%11100%
CreateCursor(...)100%11100%
.ctor(...)100%11100%
get_RetainedBytes()100%11100%
get_PersistentPageCount()100%11100%
TryGetValue(...)100%66100%
Set(...)100%66100%
Remove(...)100%22100%
Seal()100%22100%
Set(...)100%66100%
Remove(...)100%1010100%
RemoveMinimum(...)100%22100%
Balance(...)100%88100%
RotateLeft(...)100%11100%
RotateRight(...)100%11100%
Own(...)100%22100%
NewNode(...)100%11100%
ReleaseIfOwned(...)100%22100%
EnsureWritable()100%11100%
.ctor(...)100%11100%
get_RetainedBytes()100%11100%
get_PersistentPageCount()100%11100%
get_HasNext()100%11100%
Begin(...)100%11100%
BeginAll(...)100%11100%
BeginAtLeast(...)100%11100%
MoveNext()100%66100%
PushLowerBound(...)100%44100%
PushLeft(...)100%22100%
Push(...)100%11100%
ClearStack()100%22100%
FindMinimum(...)100%22100%
Update(...)100%11100%
HeightOf(...)100%22100%
CountOf(...)100%22100%
.ctor(...)100%11100%

File(s)

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

#LineLine coverage
 1//=======================================================================
 2// NavigationSeamEditTree.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 a seam-local immutable AVL with exact token-owned edit accounting.</summary>
 13internal sealed class NavigationSeamEditTree<TKey, TValue>
 14    where TKey : struct, IComparable<TKey>
 15    where TValue : class
 16{
 17    private readonly Node? _root;
 18    private readonly int _nodeBytes;
 19
 20    internal NavigationSeamEditTree(int nodeBytes)
 1921        : this(null, 0, nodeBytes)
 22    {
 1923    }
 24
 119525    private NavigationSeamEditTree(Node? root, int count, int nodeBytes)
 26    {
 119527        _root = root;
 119528        Count = count;
 119529        _nodeBytes = nodeBytes;
 119530    }
 31
 32    internal int Count { get; }
 33
 22645734    internal long RetainedBytes => checked(32L + ((long)Count * _nodeBytes));
 35
 22645336    internal int PersistentPageCount => checked(1 + Count);
 37
 38    internal bool TryGetValue(TKey key, out TValue value)
 39    {
 61022940        Node? node = _root;
 85697041        while (node != null)
 42        {
 39047543            int comparison = key.CompareTo(node.Key);
 39047544            if (comparison == 0)
 45            {
 14373446                value = node.Value;
 14373447                return true;
 48            }
 24674149            node = comparison < 0 ? node.Left : node.Right;
 50        }
 46649551        value = null!;
 46649552        return false;
 53    }
 54
 129855    internal Editor Edit(NavigationSeamEditToken ownershipToken) => new(this, ownershipToken);
 56
 57    internal Cursor CreateCursor(int maximumHeight, int shellBytes) =>
 63158        new(maximumHeight, shellBytes);
 59
 60    internal sealed class Editor
 61    {
 62        private readonly int _nodeBytes;
 63        private readonly long _token;
 64        private readonly NavigationSeamEditTree<TKey, TValue> _source;
 65        private Node? _root;
 66        private bool _sealed;
 67
 129868        internal Editor(
 129869            NavigationSeamEditTree<TKey, TValue> source,
 129870            NavigationSeamEditToken ownershipToken)
 71        {
 129872            _root = source._root;
 129873            _source = source;
 129874            _nodeBytes = source._nodeBytes;
 129875            _token = ownershipToken.Value;
 129876            Count = source.Count;
 129877        }
 78
 79        internal int Count { get; private set; }
 80
 81        internal int OwnedNodeCount { get; private set; }
 82
 83        internal bool IsChanged { get; private set; }
 84
 68414985        internal long RetainedBytes => checked(56L + ((long)OwnedNodeCount * _nodeBytes));
 86
 68413387        internal int PersistentPageCount => checked(1 + OwnedNodeCount);
 88
 89        internal bool TryGetValue(TKey key, out TValue value)
 90        {
 10102491            Node? node = _root;
 94154892            while (node != null)
 93            {
 87667794                int comparison = key.CompareTo(node.Key);
 87667795                if (comparison == 0)
 96                {
 3615397                    value = node.Value;
 3615398                    return true;
 99                }
 840524100                node = comparison < 0 ? node.Left : node.Right;
 101            }
 64871102            value = null!;
 64871103            return false;
 104        }
 105
 106        internal void Set(TKey key, TValue value)
 107        {
 16489108            EnsureWritable();
 16488109            if (TryGetValue(key, out TValue prior) && ReferenceEquals(prior, value))
 1110                return;
 16487111            bool added = false;
 16487112            _root = Set(_root, key, value, ref added);
 16487113            if (added)
 16389114                Count = checked(Count + 1);
 16487115            IsChanged = true;
 16487116        }
 117
 118        internal bool Remove(TKey key)
 119        {
 223120            EnsureWritable();
 222121            if (!TryGetValue(key, out _))
 1122                return false;
 221123            _root = Remove(_root!, key);
 221124            Count--;
 221125            IsChanged = true;
 221126            return true;
 127        }
 128
 129        internal NavigationSeamEditTree<TKey, TValue> Seal()
 130        {
 1249131            EnsureWritable();
 1249132            _sealed = true;
 1249133            return IsChanged
 1249134                ? new NavigationSeamEditTree<TKey, TValue>(_root, Count, _nodeBytes)
 1249135                : _source;
 136        }
 137
 138        private Node Set(Node? node, TKey key, TValue value, ref bool added)
 139        {
 150303140            if (node == null)
 141            {
 16389142                added = true;
 16389143                return NewNode(key, value, null, null);
 144            }
 133914145            node = Own(node);
 133914146            int comparison = key.CompareTo(node.Key);
 133914147            if (comparison == 0)
 148            {
 98149                node.Value = value;
 98150                return node;
 151            }
 133816152            if (comparison < 0)
 12275153                node.Left = Set(node.Left, key, value, ref added);
 154            else
 121541155                node.Right = Set(node.Right, key, value, ref added);
 133816156            Update(node);
 133816157            return Balance(node);
 158        }
 159
 160        private Node? Remove(Node node, TKey key)
 161        {
 455162            int comparison = key.CompareTo(node.Key);
 455163            if (comparison == 0)
 164            {
 221165                if (node.Left == null || node.Right == null)
 166                {
 220167                    Node? replacement = node.Left ?? node.Right;
 220168                    ReleaseIfOwned(node);
 220169                    return replacement;
 170                }
 1171                node = Own(node);
 1172                Node successor = FindMinimum(node.Right!);
 1173                node.Key = successor.Key;
 1174                node.Value = successor.Value;
 1175                node.Right = RemoveMinimum(node.Right!);
 1176                Update(node);
 1177                return Balance(node);
 178            }
 234179            node = Own(node);
 234180            if (comparison < 0)
 212181                node.Left = Remove(node.Left!, key);
 182            else
 22183                node.Right = Remove(node.Right!, key);
 234184            Update(node);
 234185            return Balance(node);
 186        }
 187
 188        private Node? RemoveMinimum(Node node)
 189        {
 2190            if (node.Left == null)
 191            {
 1192                Node? replacement = node.Right;
 1193                ReleaseIfOwned(node);
 1194                return replacement;
 195            }
 1196            node = Own(node);
 1197            node.Left = RemoveMinimum(node.Left!);
 1198            Update(node);
 1199            return Balance(node);
 200        }
 201
 202        private Node Balance(Node node)
 203        {
 134052204            int balance = HeightOf(node.Left) - HeightOf(node.Right);
 134052205            if (balance > 1)
 206            {
 996207                node.Left = Own(node.Left!);
 996208                if (HeightOf(node.Left.Left) < HeightOf(node.Left.Right))
 928209                node.Left = RotateLeft(node.Left!);
 996210                return RotateRight(node);
 211            }
 133056212            if (balance < -1)
 213            {
 12218214                node.Right = Own(node.Right!);
 12218215                if (HeightOf(node.Right.Right) < HeightOf(node.Right.Left))
 187216                node.Right = RotateRight(node.Right!);
 12218217                return RotateLeft(node);
 218            }
 120838219            return node;
 220        }
 221
 222        private Node RotateLeft(Node node)
 223        {
 13146224            Node right = Own(node.Right!);
 13146225            node.Right = right.Left;
 13146226            Update(node);
 13146227            right.Left = node;
 13146228            Update(right);
 13146229            return right;
 230        }
 231
 232        private Node RotateRight(Node node)
 233        {
 1183234            Node left = Own(node.Left!);
 1183235            node.Left = left.Right;
 1183236            Update(node);
 1183237            left.Right = node;
 1183238            Update(left);
 1183239            return left;
 240        }
 241
 242        private Node Own(Node node)
 243        {
 161693244            if (node.OwnerToken == _token)
 161495245                return node;
 198246            return NewNode(node.Key, node.Value, node.Left, node.Right);
 247        }
 248
 249        private Node NewNode(TKey key, TValue value, Node? left, Node? right)
 250        {
 16587251            OwnedNodeCount = checked(OwnedNodeCount + 1);
 16587252            return new Node(key, value, left, right, _token);
 253        }
 254
 255        private void ReleaseIfOwned(Node node)
 256        {
 221257            if (node.OwnerToken == _token)
 57258                OwnedNodeCount--;
 221259        }
 260
 261        private void EnsureWritable()
 262        {
 17961263            SwiftThrowHelper.ThrowIfTrue(
 17961264                _sealed,
 17961265                message: "The seam edit session is already sealed.");
 17959266        }
 267    }
 268
 269    internal sealed class Cursor
 270    {
 271        private readonly Node?[] _stack;
 272        private readonly int _shellBytes;
 273        private int _count;
 274        private TKey _maximum;
 275        private bool _hasMaximum;
 276
 631277        internal Cursor(int maximumHeight, int shellBytes)
 278        {
 631279            SwiftThrowHelper.ThrowIfArgumentOutOfRange(
 631280                maximumHeight <= 0,
 631281                maximumHeight,
 631282                nameof(maximumHeight));
 631283            _stack = new Node?[maximumHeight];
 631284            _shellBytes = shellBytes;
 631285        }
 286
 168781287        internal long RetainedBytes => checked(
 168781288            _shellBytes + 24L + ((long)_stack.Length * 8L));
 289
 168772290        internal int PersistentPageCount => 2;
 291
 292        internal TValue Current { get; private set; } = null!;
 293
 294        internal TKey CurrentKey { get; private set; }
 295
 9010296        internal bool HasNext => _count != 0;
 297
 298        internal void Begin(
 299            NavigationSeamEditTree<TKey, TValue> tree,
 300            TKey minimum,
 301            TKey maximum)
 302        {
 1303            ClearStack();
 1304            _maximum = maximum;
 1305            _hasMaximum = true;
 1306            PushLowerBound(tree._root, minimum);
 1307            Current = null!;
 1308            CurrentKey = default;
 1309        }
 310
 311        internal void BeginAll(NavigationSeamEditTree<TKey, TValue> tree)
 312        {
 519313            ClearStack();
 519314            _hasMaximum = false;
 519315            PushLeft(tree._root);
 518316            Current = null!;
 518317            CurrentKey = default;
 518318        }
 319
 320        internal void BeginAtLeast(
 321            NavigationSeamEditTree<TKey, TValue> tree,
 322            TKey minimum)
 323        {
 113324            ClearStack();
 113325            _hasMaximum = false;
 113326            PushLowerBound(tree._root, minimum);
 113327            Current = null!;
 113328            CurrentKey = default;
 113329        }
 330
 331        internal bool MoveNext()
 332        {
 8278333            if (_count == 0)
 334            {
 5335                Current = null!;
 5336                CurrentKey = default;
 5337                return false;
 338            }
 8273339            Node node = _stack[--_count]!;
 8273340            _stack[_count] = null;
 8273341            if (_hasMaximum && node.Key.CompareTo(_maximum) >= 0)
 342            {
 1343                ClearStack();
 1344                Current = null!;
 1345                CurrentKey = default;
 1346                return false;
 347            }
 8272348            PushLeft(node.Right);
 8272349            CurrentKey = node.Key;
 8272350            Current = node.Value;
 8272351            return true;
 352        }
 353
 354        private void PushLowerBound(Node? node, TKey minimum)
 355        {
 198356            while (node != null)
 357            {
 84358                if (node.Key.CompareTo(minimum) < 0)
 359                {
 30360                    node = node.Right;
 30361                    continue;
 362                }
 54363                Push(node);
 54364                node = node.Left;
 365            }
 114366        }
 367
 368        private void PushLeft(Node? node)
 369        {
 17024370            while (node != null)
 371            {
 8234372                Push(node);
 8233373                node = node.Left;
 374            }
 8790375        }
 376
 377        private void Push(Node node)
 378        {
 8288379            SwiftThrowHelper.ThrowIfTrue(
 8288380                _count == _stack.Length,
 8288381                message: "The configured seam tree height was exceeded.");
 8287382            _stack[_count++] = node;
 8287383        }
 384
 385        private void ClearStack()
 386        {
 637387            while (_count != 0)
 3388                _stack[--_count] = null;
 634389        }
 390    }
 391
 392    private static Node FindMinimum(Node node)
 393    {
 2394        while (node.Left != null)
 1395            node = node.Left;
 1396        return node;
 397    }
 398
 399    private static void Update(Node node)
 400    {
 179297401        node.Height = Math.Max(HeightOf(node.Left), HeightOf(node.Right)) + 1;
 179297402        node.Count = CountOf(node.Left) + CountOf(node.Right) + 1;
 179297403    }
 404
 653126405    private static int HeightOf(Node? node) => node?.Height ?? 0;
 406
 358594407    private static int CountOf(Node? node) => node?.Count ?? 0;
 408
 409    private sealed class Node
 410    {
 16587411        internal Node(
 16587412            TKey key,
 16587413            TValue value,
 16587414            Node? left,
 16587415            Node? right,
 16587416            long ownerToken)
 417        {
 16587418            Key = key;
 16587419            Value = value;
 16587420            Left = left;
 16587421            Right = right;
 16587422            OwnerToken = ownerToken;
 16587423            Update(this);
 16587424        }
 425
 426        internal TKey Key;
 427        internal TValue Value;
 428        internal Node? Left;
 429        internal Node? Right;
 430        internal long OwnerToken;
 431        internal int Height;
 432        internal int Count;
 433    }
 434}
Generated by: ReportGenerator 5.5.11.0
09/02/2026 - 04:28:06
GitHub | reportgenerator.io

Methods/Properties

.ctor(System.Int32)
.ctor(Trailblazer.Pathing.NavigationSeamEditTree`2/Node<TKey,TValue>,System.Int32,System.Int32)
get_RetainedBytes()
get_PersistentPageCount()
TryGetValue(TKey,TValue&)
Edit(Trailblazer.Pathing.NavigationSeamEditToken)
CreateCursor(System.Int32,System.Int32)
.ctor(Trailblazer.Pathing.NavigationSeamEditTree`2<TKey,TValue>,Trailblazer.Pathing.NavigationSeamEditToken)
get_RetainedBytes()
get_PersistentPageCount()
TryGetValue(TKey,TValue&)
Set(TKey,TValue)
Remove(TKey)
Seal()
Set(Trailblazer.Pathing.NavigationSeamEditTree`2/Node<TKey,TValue>,TKey,TValue,System.Boolean&)
Remove(Trailblazer.Pathing.NavigationSeamEditTree`2/Node<TKey,TValue>,TKey)
RemoveMinimum(Trailblazer.Pathing.NavigationSeamEditTree`2/Node<TKey,TValue>)
Balance(Trailblazer.Pathing.NavigationSeamEditTree`2/Node<TKey,TValue>)
RotateLeft(Trailblazer.Pathing.NavigationSeamEditTree`2/Node<TKey,TValue>)
RotateRight(Trailblazer.Pathing.NavigationSeamEditTree`2/Node<TKey,TValue>)
Own(Trailblazer.Pathing.NavigationSeamEditTree`2/Node<TKey,TValue>)
NewNode(TKey,TValue,Trailblazer.Pathing.NavigationSeamEditTree`2/Node<TKey,TValue>,Trailblazer.Pathing.NavigationSeamEditTree`2/Node<TKey,TValue>)
ReleaseIfOwned(Trailblazer.Pathing.NavigationSeamEditTree`2/Node<TKey,TValue>)
EnsureWritable()
.ctor(System.Int32,System.Int32)
get_RetainedBytes()
get_PersistentPageCount()
get_HasNext()
Begin(Trailblazer.Pathing.NavigationSeamEditTree`2<TKey,TValue>,TKey,TKey)
BeginAll(Trailblazer.Pathing.NavigationSeamEditTree`2<TKey,TValue>)
BeginAtLeast(Trailblazer.Pathing.NavigationSeamEditTree`2<TKey,TValue>,TKey)
MoveNext()
PushLowerBound(Trailblazer.Pathing.NavigationSeamEditTree`2/Node<TKey,TValue>,TKey)
PushLeft(Trailblazer.Pathing.NavigationSeamEditTree`2/Node<TKey,TValue>)
Push(Trailblazer.Pathing.NavigationSeamEditTree`2/Node<TKey,TValue>)
ClearStack()
FindMinimum(Trailblazer.Pathing.NavigationSeamEditTree`2/Node<TKey,TValue>)
Update(Trailblazer.Pathing.NavigationSeamEditTree`2/Node<TKey,TValue>)
HeightOf(Trailblazer.Pathing.NavigationSeamEditTree`2/Node<TKey,TValue>)
CountOf(Trailblazer.Pathing.NavigationSeamEditTree`2/Node<TKey,TValue>)
.ctor(TKey,TValue,Trailblazer.Pathing.NavigationSeamEditTree`2/Node<TKey,TValue>,Trailblazer.Pathing.NavigationSeamEditTree`2/Node<TKey,TValue>,System.Int64)