< Summary

Information
Class: Trailblazer.Pathing.NavigationDependencySortWork
Assembly: Trailblazer
File(s): /home/runner/work/Trailblazer/Trailblazer/src/Trailblazer/Pathing/Search/AStar/NavigationDependencySortWork.cs
Line coverage
100%
Covered lines: 116
Uncovered lines: 0
Coverable lines: 116
Total lines: 231
Line coverage: 100%
Branch coverage
100%
Covered branches: 48
Total branches: 48
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_IsComplete()100%11100%
GetMaximumComparisonCount(...)100%11100%
Advance(...)100%2626100%
InitializeCollection()100%44100%
BeginSift(...)100%11100%
Compare(...)100%44100%
Swap(...)100%22100%
TryConsumeComparison(...)100%44100%
GetCollectionMaximumComparisonCount(...)100%44100%
GetSiftMaximumComparisonCount(...)100%44100%

File(s)

/home/runner/work/Trailblazer/Trailblazer/src/Trailblazer/Pathing/Search/AStar/NavigationDependencySortWork.cs

#LineLine coverage
 1//=======================================================================
 2// NavigationDependencySortWork.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>Canonically sorts unique graph dependencies with bounded comparisons.</summary>
 13internal struct NavigationDependencySortWork
 14{
 15    private enum Collection : byte
 16    {
 17        Components = 0,
 18        Pages = 1,
 19        Complete = 2
 20    }
 21
 22    private enum SiftStage : byte
 23    {
 24        None = 0,
 25        ChooseChild = 1,
 26        CompareRoot = 2
 27    }
 28
 29    private readonly NavigationSurfaceComponentKey[] _components;
 30    private readonly int _componentCount;
 31    private readonly GraphPageDependencyAddress[] _pages;
 32    private readonly int _pageCount;
 33    private Collection _collection;
 34    private SiftStage _siftStage;
 35    private int _heapSize;
 36    private int _buildIndex;
 37    private int _sortEnd;
 38    private int _siftRoot;
 39    private int _siftCandidate;
 40    private bool _building;
 41
 42    internal NavigationDependencySortWork(NavigationAStarWorkspace workspace)
 21543        : this(
 21544            workspace.EndpointComponents,
 21545            workspace.EndpointComponentCount,
 21546            workspace.EndpointPages,
 21547            workspace.EndpointPageCount)
 48    {
 21549    }
 50
 51    internal NavigationDependencySortWork(
 52        NavigationSurfaceComponentKey[] components,
 53        int componentCount,
 54        GraphPageDependencyAddress[] pages,
 55        int pageCount)
 56    {
 92057        _components = components;
 92058        _componentCount = componentCount;
 92059        _pages = pages;
 92060        _pageCount = pageCount;
 92061        _collection = Collection.Components;
 92062        _siftStage = SiftStage.None;
 92063        _heapSize = 0;
 92064        _buildIndex = 0;
 92065        _sortEnd = 0;
 92066        _siftRoot = 0;
 92067        _siftCandidate = 0;
 92068        _building = false;
 92069        InitializeCollection();
 92070    }
 71
 814372    internal bool IsComplete => _collection == Collection.Complete;
 73
 74    internal static int GetMaximumComparisonCount(
 75        int componentCount,
 76        int pageCount)
 77    {
 11978        SwiftThrowHelper.ThrowIfNegative(componentCount, nameof(componentCount));
 11979        SwiftThrowHelper.ThrowIfNegative(pageCount, nameof(pageCount));
 11980        return checked(
 11981            GetCollectionMaximumComparisonCount(componentCount)
 11982            + GetCollectionMaximumComparisonCount(pageCount));
 83    }
 84
 85    internal bool Advance(NavigationWorkMeter meter, int lookupStepLimit)
 86    {
 94187        SwiftThrowHelper.ThrowIfNegative(lookupStepLimit, nameof(lookupStepLimit));
 94188        int remaining = Math.Min(lookupStepLimit, meter.RemainingLookupProbes);
 538689        while (!IsComplete)
 90        {
 446891            if (_siftStage == SiftStage.None)
 92            {
 391693                if (_building)
 94                {
 195095                    if (_buildIndex < 0)
 96                    {
 183797                        _building = false;
 183798                        continue;
 99                    }
 113100                    BeginSift(_buildIndex--);
 113101                    continue;
 102                }
 1966103                if (_sortEnd <= 0)
 104                {
 1837105                    _collection = _collection == Collection.Components
 1837106                        ? Collection.Pages
 1837107                        : Collection.Complete;
 1837108                    InitializeCollection();
 1837109                    continue;
 110                }
 129111                Swap(0, _sortEnd);
 129112                _heapSize = _sortEnd--;
 129113                BeginSift(0);
 129114                continue;
 115            }
 116
 552117            if (_siftStage == SiftStage.ChooseChild)
 118            {
 383119                int left = checked((_siftRoot * 2) + 1);
 383120                if (left >= _heapSize)
 121                {
 212122                    _siftStage = SiftStage.None;
 212123                    continue;
 124                }
 171125                _siftCandidate = left;
 171126                int right = left + 1;
 171127                if (right < _heapSize)
 128                {
 58129                    if (!TryConsumeComparison(meter, ref remaining))
 12130                        return false;
 46131                    if (Compare(left, right) < 0)
 20132                        _siftCandidate = right;
 133                }
 159134                _siftStage = SiftStage.CompareRoot;
 159135                continue;
 136            }
 137
 169138            if (!TryConsumeComparison(meter, ref remaining))
 11139                return false;
 158140            if (Compare(_siftRoot, _siftCandidate) >= 0)
 141            {
 29142                _siftStage = SiftStage.None;
 29143                continue;
 144            }
 129145            Swap(_siftRoot, _siftCandidate);
 129146            _siftRoot = _siftCandidate;
 129147            _siftStage = SiftStage.ChooseChild;
 148        }
 918149        return true;
 150    }
 151
 152    private void InitializeCollection()
 153    {
 2757154        if (IsComplete)
 918155            return;
 1839156        int count = _collection == Collection.Components
 1839157            ? _componentCount
 1839158            : _pageCount;
 1839159        _heapSize = count;
 1839160        _buildIndex = (count / 2) - 1;
 1839161        _sortEnd = count - 1;
 1839162        _building = true;
 1839163        _siftStage = SiftStage.None;
 1839164    }
 165
 166    private void BeginSift(int root)
 167    {
 242168        _siftRoot = root;
 242169        _siftStage = SiftStage.ChooseChild;
 242170    }
 171
 172    private int Compare(int left, int right)
 173    {
 204174        if (_collection == Collection.Components)
 175        {
 72176            return _components[left].CompareTo(_components[right]);
 177        }
 132178        GraphPageDependencyAddress leftPage = _pages[left];
 132179        GraphPageDependencyAddress rightPage = _pages[right];
 132180        int mapComparison = string.CompareOrdinal(leftPage.MapId, rightPage.MapId);
 132181        return mapComparison != 0
 132182            ? mapComparison
 132183            : leftPage.PageIndex.CompareTo(rightPage.PageIndex);
 184    }
 185
 186    private void Swap(int left, int right)
 187    {
 258188        if (_collection == Collection.Components)
 189        {
 134190            (_components[left], _components[right]) =
 134191                (_components[right], _components[left]);
 134192            return;
 193        }
 124194        (_pages[left], _pages[right]) = (_pages[right], _pages[left]);
 124195    }
 196
 197    private static bool TryConsumeComparison(
 198        NavigationWorkMeter meter,
 199        ref int remaining)
 200    {
 227201        if (remaining == 0 || !meter.TryConsumeLookupProbes(1))
 23202            return false;
 204203        remaining--;
 204204        return true;
 205    }
 206
 207    private static int GetCollectionMaximumComparisonCount(int count)
 208    {
 236209        int comparisons = 0;
 580210        for (int root = (count / 2) - 1; root >= 0; root--)
 57211            comparisons = checked(comparisons + GetSiftMaximumComparisonCount(root, count));
 584212        for (int heapSize = count - 1; heapSize > 0; heapSize--)
 59213            comparisons = checked(comparisons + GetSiftMaximumComparisonCount(0, heapSize));
 233214        return comparisons;
 215    }
 216
 217    private static int GetSiftMaximumComparisonCount(int root, int heapSize)
 218    {
 116219        int comparisons = 0;
 62220        while (true)
 221        {
 178222            int left = checked((root * 2) + 1);
 175223            if (left >= heapSize)
 113224                return comparisons;
 62225            comparisons = checked(comparisons + 1);
 62226            if (left + 1 < heapSize)
 8227                comparisons = checked(comparisons + 1);
 62228            root = left;
 229        }
 230    }
 231}
Generated by: ReportGenerator 5.5.11.0
09/02/2026 - 04:28:06
GitHub | reportgenerator.io

Methods/Properties

.ctor(Trailblazer.Pathing.NavigationAStarWorkspace)
.ctor(Trailblazer.Pathing.NavigationSurfaceComponentKey[],System.Int32,Trailblazer.Pathing.GraphPageDependencyAddress[],System.Int32)
get_IsComplete()
GetMaximumComparisonCount(System.Int32,System.Int32)
Advance(Trailblazer.Pathing.NavigationWorkMeter,System.Int32)
InitializeCollection()
BeginSift(System.Int32)
Compare(System.Int32,System.Int32)
Swap(System.Int32,System.Int32)
TryConsumeComparison(Trailblazer.Pathing.NavigationWorkMeter,System.Int32&)
GetCollectionMaximumComparisonCount(System.Int32)
GetSiftMaximumComparisonCount(System.Int32,System.Int32)