< Summary

Class:Itinero.Routing.DataStructures.BinaryHeap`1
Assembly:Itinero
File(s):/home/runner/work/routing2/routing2/src/Itinero/Routing/DataStructures/BinaryHeap.cs
Covered lines:69
Uncovered lines:12
Coverable lines:81
Total lines:161
Line coverage:85.1% (69 of 81)
Covered branches:16
Total branches:18
Branch coverage:88.8% (16 of 18)
Tag:251_23667616543

Metrics

MethodBranch coverage Cyclomatic complexity Line coverage
.ctor()100%1100%
.ctor(...)100%1100%
get_Count()100%1100%
Push(...)83.33%686.36%
PeekWeight()100%10%
Peek()100%10%
Pop(...)91.66%1292.68%
Clear()100%1100%

File(s)

/home/runner/work/routing2/routing2/src/Itinero/Routing/DataStructures/BinaryHeap.cs

#LineLine coverage
 1using System;
 2
 3namespace Itinero.Routing.DataStructures;
 4
 5/// <summary>
 6/// Implements a priority queue in the form of a binary heap.
 7/// </summary>
 8internal class BinaryHeap<T>
 9    where T : struct
 10{
 11    private (T item, double priority)[] _data;
 12    private int _count;
 13    private uint _latestIndex;
 14
 15    /// <summary>
 16    /// Creates a new binary heap.
 17    /// </summary>
 18    public BinaryHeap()
 22819        : this(1024) { }
 20
 21    /// <summary>
 22    /// Creates a new binary heap.
 23    /// </summary>
 7624    public BinaryHeap(uint initialSize)
 7625    {
 7626        _data = new (T, double)[initialSize];
 7627        _count = 0;
 7628        _latestIndex = 1;
 7629    }
 30
 31    /// <summary>
 32    /// Returns the number of items in this queue.
 33    /// </summary>
 40077834    public int Count => _count;
 35
 36    /// <summary>
 37    /// Enqueues a given item.
 38    /// </summary>
 39    public void Push(T item, double priority)
 40867940    {
 40867941        _count++;
 42
 40867943        if (_latestIndex == _data.Length - 1)
 044        {
 045            Array.Resize(ref _data, _data.Length * 2);
 046        }
 47
 48        // add the item at the first free point.
 40867949        _data[_latestIndex] = (item, priority);
 50
 51        // ... and let it 'bubble' up using hole-sinking:
 52        // instead of swapping at each level, leave a hole and move it up.
 40867953        var bubbleIndex = _latestIndex;
 40867954        _latestIndex++;
 68528355        while (bubbleIndex != 1)
 61675556        {
 61675557            var parentIdx = bubbleIndex / 2;
 61675558            if (priority < _data[parentIdx].priority)
 27660459            {
 27660460                _data[bubbleIndex] = _data[parentIdx];
 27660461                bubbleIndex = parentIdx;
 27660462            }
 63            else
 34015164            {
 34015165                break;
 66            }
 27660467        }
 68
 40867969        _data[bubbleIndex] = (item, priority);
 40867970    }
 71
 72    /// <summary>
 73    /// Returns the smallest weight in the queue.
 74    /// </summary>
 75    public double PeekWeight()
 076    {
 077        return _data[1].priority;
 078    }
 79
 80    /// <summary>
 81    /// Returns the object with the smallest weight.
 82    /// </summary>
 83    public T Peek()
 084    {
 085        return _data[1].item;
 086    }
 87
 88    /// <summary>
 89    /// Returns the object with the smallest weight and removes it.
 90    /// </summary>
 91    public T Pop(out double priority)
 39257192    {
 39257193        priority = 0;
 39257194        if (_count <= 0)
 1195        {
 1196            return default;
 97        }
 98
 39256099        var result = _data[1];
 392560100        priority = result.priority;
 101
 392560102        _count--;
 392560103        _latestIndex--;
 104
 105        // take the last element and sift it down from the root.
 392560106        var last = _data[_latestIndex];
 392560107        var lastPriority = last.priority;
 108
 109        // sift down using hole-sinking: move the smaller child up,
 110        // place the last element at the final hole position.
 392560111        uint hole = 1;
 1184452112        while (true)
 1184452113        {
 1184452114            var child = hole * 2;
 1184452115            if (child + 1 <= _latestIndex)
 894566116            {
 117                // two children exist — pick the smaller one.
 894566118                if (_data[child + 1].priority < _data[child].priority)
 412589119                {
 412589120                    child++;
 412589121                }
 122
 894566123                if (lastPriority <= _data[child].priority)
 102674124                {
 102674125                    break;
 126                }
 127
 791892128                _data[hole] = _data[child];
 791892129                hole = child;
 791892130            }
 289886131            else if (child <= _latestIndex)
 97561132            {
 133                // only left child exists.
 97561134                if (lastPriority <= _data[child].priority)
 97561135                {
 97561136                    break;
 137                }
 138
 0139                _data[hole] = _data[child];
 0140                hole = child;
 0141            }
 142            else
 192325143            {
 192325144                break;
 145            }
 791892146        }
 147
 392560148        _data[hole] = last;
 149
 392560150        return result.item;
 392571151    }
 152
 153    /// <summary>
 154    /// Clears this priority queue.
 155    /// </summary>
 156    public void Clear()
 11438157    {
 11438158        _count = 0;
 11438159        _latestIndex = 1;
 11438160    }
 161}
Generated by: ReportGenerator 4.8.2.0
03/27/2026 - 21:11:43
GitHub | www.palmmedia.de

Methods/Properties

.ctor()
.ctor(...)
get_Count()
Push(...)
PeekWeight()
Peek()
Pop(...)
Clear()