< Summary

Information
Class: Trailblazer.Pathing.PathHeap<T>
Assembly: Trailblazer
File(s): /home/runner/work/Trailblazer/Trailblazer/src/Trailblazer/Pathing/Search/OpenSet/PathHeap.cs
Line coverage
99%
Covered lines: 117
Uncovered lines: 1
Coverable lines: 118
Total lines: 261
Line coverage: 99.1%
Branch coverage
89%
Covered branches: 41
Total branches: 46
Branch coverage: 89.1%
Method coverage

Feature is only available for sponsors

Upgrade to PRO version

Metrics

MethodBranch coverage Crap Score Cyclomatic complexity Line coverage
get_TrackedCount()100%11100%
get_Capacity()100%11100%
.ctor()100%11100%
Add(...)100%44100%
TryGetPathCost(...)100%22100%
UpdatePathCost(...)50%22100%
PeekAt(...)100%11100%
RemoveFirst(...)87.5%8895%
Contains(...)100%22100%
SetClosed(...)50%22100%
IsClosed(...)100%22100%
SortUp(...)100%66100%
SortDown(...)100%1010100%
EnumerateClosed()100%11100%
FastClear()100%11100%
Reset()100%11100%
Resize(...)50%44100%
HasHigherPriority(...)100%44100%
Swap(...)100%11100%

File(s)

/home/runner/work/Trailblazer/Trailblazer/src/Trailblazer/Pathing/Search/OpenSet/PathHeap.cs

#LineLine coverage
 1using System;
 2using System.Diagnostics.CodeAnalysis;
 3using System.Runtime.CompilerServices;
 4
 5namespace Trailblazer.Pathing;
 6
 7internal struct PathHeapMeta
 8{
 9    public uint HeapIndex;
 10
 11    public uint HeapVersion;
 12
 13    public uint ClosedHeapVersion;
 14
 15    public int PathCost;
 16
 17    public int TieBreakCost;
 18}
 19
 20/// <summary>
 21/// Shared binary heap used by the pathing surveyors to track open and closed nodes.
 22/// Heap ordering cost is owned by the heap metadata instead of the node types themselves.
 23/// </summary>
 24internal sealed class PathHeap<TNode> where TNode : class
 25{
 26    public const int DefaultCapacity = 128;
 27
 28    private TNode[] _items;
 29
 30    private readonly PathHeapMetadata<TNode> _meta;
 31
 32    public uint CurrentHeapVersion { get; private set; } = 1;
 33
 34    public uint HeapCount { get; private set; }
 35
 12336    public int TrackedCount => _meta.Count;
 37
 238    public int Capacity => _items.Length;
 39
 290840    public PathHeap()
 41    {
 290842        _items = new TNode[DefaultCapacity];
 290843        _meta = new(DefaultCapacity);
 290844    }
 45
 46    public void Add(TNode item, int pathCost, int tieBreakCost = 0)
 47    {
 1250048        if (Contains(item))
 149            return;
 50
 1249951        if (HeapCount + 1 > _items.Length)
 652            Resize(_items.Length * 2);
 53
 1249954        PathHeapMeta meta = new()
 1249955        {
 1249956            HeapIndex = HeapCount,
 1249957            HeapVersion = CurrentHeapVersion,
 1249958            PathCost = pathCost,
 1249959            TieBreakCost = tieBreakCost
 1249960        };
 61
 1249962        _meta[item] = meta;
 1249963        _items[HeapCount++] = item;
 1249964        SortUp(item);
 1249965    }
 66
 67    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 68    public bool TryGetPathCost(TNode item, out int pathCost)
 69    {
 1525970        if (!_meta.TryGetValue(item, out PathHeapMeta meta))
 71        {
 272            pathCost = int.MaxValue;
 273            return false;
 74        }
 75
 1525776        pathCost = meta.PathCost;
 1525777        return true;
 78    }
 79
 80    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 81    public void UpdatePathCost(TNode item, int pathCost, int tieBreakCost = 0)
 82    {
 583        if (_meta.TryGetValue(item, out PathHeapMeta meta))
 84        {
 585            meta.PathCost = pathCost;
 586            meta.TieBreakCost = tieBreakCost;
 587            _meta[item] = meta;
 88        }
 589    }
 90
 91    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 192    public TNode PeekAt(int index) => _items[index];
 93
 94    public bool RemoveFirst([MaybeNullWhen(false)] out TNode result)
 95    {
 403296        if (HeapCount == 0)
 97        {
 56498            result = null!;
 56499            return false;
 100        }
 101
 3468102        result = _items[0];
 3468103        if (!_meta.TryGetValue(result, out PathHeapMeta meta))
 0104            return false;
 105
 3468106        HeapCount--;
 107
 3468108        if (HeapCount == 0)
 109        {
 1711110            _items[0] = null!;
 111        }
 112        else
 113        {
 1757114            TNode temp = _items[HeapCount];
 1757115            PathHeapMeta tempMeta = _meta[temp];
 1757116            _items[0] = temp;
 1757117            tempMeta.HeapIndex = 0;
 1757118            _meta[temp] = tempMeta;
 1757119            _items[HeapCount] = null!;
 120
 1757121            if (HeapCount > 1)
 1561122                SortDown(temp);
 123        }
 124
 3468125        meta.HeapVersion--;
 3468126        _meta[result] = meta;
 3468127        return true;
 128    }
 129
 130    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 131    public bool Contains(TNode item)
 132    {
 17307133        return _meta.TryGetValue(item, out PathHeapMeta meta)
 17307134            && meta.HeapVersion == CurrentHeapVersion;
 135    }
 136
 137    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 138    public void SetClosed(TNode item)
 139    {
 3179140        if (_meta.TryGetValue(item, out PathHeapMeta meta))
 141        {
 3179142            meta.ClosedHeapVersion = CurrentHeapVersion;
 3179143            _meta[item] = meta;
 144        }
 3179145    }
 146
 147    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 148    public bool IsClosed(TNode item)
 149    {
 44425150        return _meta.TryGetValue(item, out PathHeapMeta meta)
 44425151            && meta.ClosedHeapVersion == CurrentHeapVersion;
 152    }
 153
 154    public void SortUp(TNode item)
 155    {
 12504156        PathHeapMeta meta = _meta[item];
 12504157        uint index = meta.HeapIndex;
 158
 13652159        while (index > 0 && index < HeapCount)
 160        {
 11599161            uint parentIndex = (index - 1) / 2;
 11599162            TNode parent = _items[parentIndex];
 163
 11599164            if (!HasHigherPriority(meta, _meta[parent]))
 165                break;
 166
 1148167            Swap(item, parent);
 1148168            meta = _meta[item];
 1148169            index = meta.HeapIndex;
 170        }
 12504171    }
 172
 173    public void SortDown(TNode item)
 174    {
 1561175        PathHeapMeta meta = _meta[item];
 1561176        uint index = meta.HeapIndex;
 177
 1744178        while (true)
 179        {
 3305180            uint left = (index * 2) + 1;
 3305181            uint right = left + 1;
 3305182            uint lowest = index;
 183
 3305184            if (left < HeapCount
 3305185                && HasHigherPriority(_meta[_items[left]], _meta[_items[lowest]]))
 186            {
 1126187                lowest = left;
 188            }
 189
 3305190            if (right < HeapCount
 3305191                && HasHigherPriority(_meta[_items[right]], _meta[_items[lowest]]))
 192            {
 677193                lowest = right;
 194            }
 195
 3305196            if (lowest == index)
 197                break;
 198
 1744199            Swap(item, _items[lowest]);
 1744200            meta = _meta[item];
 1744201            index = meta.HeapIndex;
 202        }
 1561203    }
 204
 205    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 206    public PathHeapMetadata<TNode>.ClosedEnumerable EnumerateClosed()
 245207        => _meta.EnumerateClosed(CurrentHeapVersion);
 208
 209    public void FastClear()
 210    {
 1712211        HeapCount = 0;
 1712212        CurrentHeapVersion++;
 1712213        _meta.Clear();
 1712214    }
 215
 216    public void Reset()
 217    {
 1218        HeapCount = 0;
 1219        CurrentHeapVersion = 1;
 1220        _meta.Clear();
 1221        _meta.TrimExcess();
 1222    }
 223
 224    private void Resize(int newSize)
 225    {
 6226        int newCapacity = newSize <= DefaultCapacity ? DefaultCapacity : newSize;
 227
 6228        TNode[] newArray = new TNode[newCapacity];
 6229        if (HeapCount > 0)
 6230            Array.Copy(_items, 0, newArray, 0, HeapCount);
 231
 6232        _items = newArray;
 6233        _meta.EnsureCapacity(newCapacity);
 6234    }
 235
 236    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 237    private static bool HasHigherPriority(PathHeapMeta candidate, PathHeapMeta current)
 238    {
 16805239        return candidate.PathCost < current.PathCost
 16805240            || (candidate.PathCost == current.PathCost
 16805241                && candidate.TieBreakCost < current.TieBreakCost);
 242    }
 243
 244    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 245    private void Swap(TNode itemA, TNode itemB)
 246    {
 2892247        PathHeapMeta metaA = _meta[itemA];
 2892248        PathHeapMeta metaB = _meta[itemB];
 249
 2892250        uint indexA = metaA.HeapIndex;
 2892251        uint indexB = metaB.HeapIndex;
 252
 2892253        _items[indexA] = itemB;
 2892254        _items[indexB] = itemA;
 255
 2892256        metaA.HeapIndex = indexB;
 2892257        metaB.HeapIndex = indexA;
 2892258        _meta[itemA] = metaA;
 2892259        _meta[itemB] = metaB;
 2892260    }
 261}
Generated by: ReportGenerator 5.5.10.0
05/19/2026 - 21:06:43
GitHub | reportgenerator.io

Methods/Properties

get_TrackedCount()
get_Capacity()
.ctor()
Add(TNode,System.Int32,System.Int32)
TryGetPathCost(TNode,System.Int32&)
UpdatePathCost(TNode,System.Int32,System.Int32)
PeekAt(System.Int32)
RemoveFirst(TNode&)
Contains(TNode)
SetClosed(TNode)
IsClosed(TNode)
SortUp(TNode)
SortDown(TNode)
EnumerateClosed()
FastClear()
Reset()
Resize(System.Int32)
HasHigherPriority(Trailblazer.Pathing.PathHeapMeta,Trailblazer.Pathing.PathHeapMeta)
Swap(TNode,TNode)