< Summary

Class:Itinero.Routing.DataStructures.BinaryHeap`1
Assembly:Itinero
File(s):/home/runner/work/routing2/routing2/src/Itinero/Routing/DataStructures/BinaryHeap.cs
Covered lines:89
Uncovered lines:15
Coverable lines:104
Total lines:185
Line coverage:85.5% (89 of 104)
Covered branches:16
Total branches:20
Branch coverage:80% (16 of 20)
Tag:238_19435726042

Metrics

MethodBranch coverage Cyclomatic complexity Line coverage
.ctor()100%1100%
.ctor(...)100%1100%
get_Count()100%1100%
Push(...)100%6100%
PeekWeight()100%10%
Peek()100%10%
Pop(...)71.42%1484.21%
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[] _heap; // The objects per priority.
 12    private double[] _priorities; // Holds the priorities of this heap.
 13    private int _count; // The current count of elements.
 14    private uint _latestIndex; // The latest unused index
 15
 16    /// <summary>
 17    /// Creates a new binary heap.
 18    /// </summary>
 19    public BinaryHeap()
 25520        : this(2) { }
 21
 22    /// <summary>
 23    /// Creates a new binary heap.
 24    /// </summary>
 8525    public BinaryHeap(uint initialSize)
 8526    {
 8527        _heap = new T[initialSize];
 8528        _priorities = new double[initialSize];
 29
 8530        _count = 0;
 8531        _latestIndex = 1;
 8532    }
 33
 34    /// <summary>
 35    /// Returns the number of items in this queue.
 36    /// </summary>
 21037    public int Count => _count;
 38
 39    /// <summary>
 40    /// Enqueues a given item.
 41    /// </summary>
 42    public void Push(T item, double priority)
 21743    {
 21744        _count++; // another item was added!
 45
 46        // increase size if needed.
 21747        if (_latestIndex == _priorities.Length - 1)
 8548        {
 49            // time to increase size!
 8550            Array.Resize(ref _heap, _heap.Length + 100);
 8551            Array.Resize(ref _priorities, _priorities.Length + 100);
 8552        }
 53
 54        // add the item at the first free point
 21755        _priorities[_latestIndex] = priority;
 21756        _heap[_latestIndex] = item;
 57
 58        // ... and let it 'bubble' up.
 21759        var bubbleIndex = _latestIndex;
 21760        _latestIndex++;
 26161        while (bubbleIndex != 1)
 9162        {
 63            // bubble until the index is one.
 9164            var parentIdx = bubbleIndex / 2;
 9165            if (_priorities[bubbleIndex] < _priorities[parentIdx])
 4466            {
 67                // the parent priority is higher; do the swap.
 4468                var tempPriority = _priorities[parentIdx];
 4469                var tempItem = _heap[parentIdx];
 4470                _priorities[parentIdx] = _priorities[bubbleIndex];
 4471                _heap[parentIdx] = _heap[bubbleIndex];
 4472                _priorities[bubbleIndex] = tempPriority;
 4473                _heap[bubbleIndex] = tempItem;
 74
 4475                bubbleIndex = parentIdx;
 4476            }
 77            else
 4778            {
 79                // the parent priority is lower or equal; the item will not bubble up more.
 4780                break;
 81            }
 4482        }
 21783    }
 84
 85    /// <summary>
 86    /// Returns the smallest weight in the queue.
 87    /// </summary>
 88    public double PeekWeight()
 089    {
 090        return _priorities[1];
 091    }
 92
 93    /// <summary>
 94    /// Returns the object with the smallest weight.
 95    /// </summary>
 96    public T Peek()
 097    {
 098        return _heap[1];
 099    }
 100
 101    /// <summary>
 102    /// Returns the object with the smallest weight and removes it.
 103    /// </summary>
 104    public T Pop(out double priority)
 208105    {
 208106        priority = 0;
 208107        if (_count <= 0)
 8108        {
 8109            return default;
 110        }
 111
 200112        var item = _heap[1]; // get the first item.
 200113        priority = _priorities[1];
 114
 200115        _count--; // reduce the element count.
 200116        _latestIndex--; // reduce the latest index.
 117
 200118        var swapItem = 1;
 200119        var parentPriority = _priorities[_latestIndex];
 200120        var parentItem = _heap[_latestIndex];
 200121        _heap[1] = parentItem; // place the last element on top.
 200122        _priorities[1] = parentPriority; // place the last element on top.
 123        do
 289124        {
 289125            var parent = swapItem;
 289126            var swapItemPriority = 0d;
 289127            if ((2 * parent) + 1 <= _latestIndex)
 1128            {
 1129                swapItemPriority = _priorities[2 * parent];
 1130                var potentialSwapItem = _priorities[(2 * parent) + 1];
 1131                if (parentPriority >= swapItemPriority)
 1132                {
 1133                    swapItem = 2 * parent;
 1134                    if (_priorities[swapItem] >= potentialSwapItem)
 1135                    {
 1136                        swapItemPriority = potentialSwapItem;
 1137                        swapItem = (2 * parent) + 1;
 1138                    }
 1139                }
 0140                else if (parentPriority >= potentialSwapItem)
 0141                {
 0142                    swapItemPriority = potentialSwapItem;
 0143                    swapItem = (2 * parent) + 1;
 0144                }
 145                else
 0146                {
 0147                    break;
 148                }
 1149            }
 288150            else if (2 * parent <= _latestIndex)
 88151            {
 152                // Only one child exists
 88153                swapItemPriority = _priorities[2 * parent];
 88154                if (parentPriority >= swapItemPriority)
 88155                {
 88156                    swapItem = 2 * parent;
 88157                }
 158                else
 0159                {
 0160                    break;
 161                }
 88162            }
 163            else
 200164            {
 200165                break;
 166            }
 167
 89168            _priorities[parent] = swapItemPriority;
 89169            _priorities[swapItem] = parentPriority;
 89170            _heap[parent] = _heap[swapItem];
 89171            _heap[swapItem] = parentItem;
 178172        } while (true);
 173
 200174        return item;
 208175    }
 176
 177    /// <summary>
 178    /// Clears this priority queue.
 179    /// </summary>
 180    public void Clear()
 23181    {
 23182        _count = 0;
 23183        _latestIndex = 1;
 23184    }
 185}
Generated by: ReportGenerator 4.8.2.0
11/17/2025 - 15:54:34
GitHub | www.palmmedia.de

Methods/Properties

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