< Summary

Class:Itinero.Routing.DataStructures.BinaryHeap`1
Assembly:Itinero
File(s):/home/runner/work/routing2/routing2/src/Itinero/Routing/DataStructures/BinaryHeap.cs
Covered lines:87
Uncovered lines:17
Coverable lines:104
Total lines:185
Line coverage:83.6% (87 of 104)
Covered branches:15
Total branches:20
Branch coverage:75% (15 of 20)
Tag:232_15462506344

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(...)64.28%1480.7%
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()
 22520        : this(2) { }
 21
 22    /// <summary>
 23    /// Creates a new binary heap.
 24    /// </summary>
 7525    public BinaryHeap(uint initialSize)
 7526    {
 7527        _heap = new T[initialSize];
 7528        _priorities = new double[initialSize];
 29
 7530        _count = 0;
 7531        _latestIndex = 1;
 7532    }
 33
 34    /// <summary>
 35    /// Returns the number of items in this queue.
 36    /// </summary>
 18237    public int Count => _count;
 38
 39    /// <summary>
 40    /// Enqueues a given item.
 41    /// </summary>
 42    public void Push(T item, double priority)
 18143    {
 18144        _count++; // another item was added!
 45
 46        // increase size if needed.
 18147        if (_latestIndex == _priorities.Length - 1)
 7548        {
 49            // time to increase size!
 7550            Array.Resize(ref _heap, _heap.Length + 100);
 7551            Array.Resize(ref _priorities, _priorities.Length + 100);
 7552        }
 53
 54        // add the item at the first free point
 18155        _priorities[_latestIndex] = priority;
 18156        _heap[_latestIndex] = item;
 57
 58        // ... and let it 'bubble' up.
 18159        var bubbleIndex = _latestIndex;
 18160        _latestIndex++;
 21961        while (bubbleIndex != 1)
 8062        {
 63            // bubble until the index is one.
 8064            var parentIdx = bubbleIndex / 2;
 8065            if (_priorities[bubbleIndex] < _priorities[parentIdx])
 3866            {
 67                // the parent priority is higher; do the swap.
 3868                var tempPriority = _priorities[parentIdx];
 3869                var tempItem = _heap[parentIdx];
 3870                _priorities[parentIdx] = _priorities[bubbleIndex];
 3871                _heap[parentIdx] = _heap[bubbleIndex];
 3872                _priorities[bubbleIndex] = tempPriority;
 3873                _heap[bubbleIndex] = tempItem;
 74
 3875                bubbleIndex = parentIdx;
 3876            }
 77            else
 4278            {
 79                // the parent priority is lower or equal; the item will not bubble up more.
 4280                break;
 81            }
 3882        }
 18183    }
 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)
 163105    {
 163106        priority = 0;
 163107        if (_count <= 0)
 0108        {
 0109            return default;
 110        }
 111
 163112        var item = _heap[1]; // get the first item.
 163113        priority = _priorities[1];
 114
 163115        _count--; // reduce the element count.
 163116        _latestIndex--; // reduce the latest index.
 117
 163118        var swapItem = 1;
 163119        var parentPriority = _priorities[_latestIndex];
 163120        var parentItem = _heap[_latestIndex];
 163121        _heap[1] = parentItem; // place the last element on top.
 163122        _priorities[1] = parentPriority; // place the last element on top.
 123        do
 241124        {
 241125            var parent = swapItem;
 241126            var swapItemPriority = 0d;
 241127            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            }
 240150            else if (2 * parent <= _latestIndex)
 77151            {
 152                // Only one child exists
 77153                swapItemPriority = _priorities[2 * parent];
 77154                if (parentPriority >= swapItemPriority)
 77155                {
 77156                    swapItem = 2 * parent;
 77157                }
 158                else
 0159                {
 0160                    break;
 161                }
 77162            }
 163            else
 163164            {
 163165                break;
 166            }
 167
 78168            _priorities[parent] = swapItemPriority;
 78169            _priorities[swapItem] = parentPriority;
 78170            _heap[parent] = _heap[swapItem];
 78171            _heap[swapItem] = parentItem;
 156172        } while (true);
 173
 163174        return item;
 163175    }
 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
06/05/2025 - 08:42:07
GitHub | www.palmmedia.de

Methods/Properties

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