< 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:224_14471318300

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()
 19220        : this(2) { }
 21
 22    /// <summary>
 23    /// Creates a new binary heap.
 24    /// </summary>
 6425    public BinaryHeap(uint initialSize)
 6426    {
 6427        _heap = new T[initialSize];
 6428        _priorities = new double[initialSize];
 29
 6430        _count = 0;
 6431        _latestIndex = 1;
 6432    }
 33
 34    /// <summary>
 35    /// Returns the number of items in this queue.
 36    /// </summary>
 20437    public int Count => _count;
 38
 39    /// <summary>
 40    /// Enqueues a given item.
 41    /// </summary>
 42    public void Push(T item, double priority)
 15643    {
 15644        _count++; // another item was added!
 45
 46        // increase size if needed.
 15647        if (_latestIndex == _priorities.Length - 1)
 6448        {
 49            // time to increase size!
 6450            Array.Resize(ref _heap, _heap.Length + 100);
 6451            Array.Resize(ref _priorities, _priorities.Length + 100);
 6452        }
 53
 54        // add the item at the first free point
 15655        _priorities[_latestIndex] = priority;
 15656        _heap[_latestIndex] = item;
 57
 58        // ... and let it 'bubble' up.
 15659        var bubbleIndex = _latestIndex;
 15660        _latestIndex++;
 18961        while (bubbleIndex != 1)
 6962        {
 63            // bubble until the index is one.
 6964            var parentIdx = bubbleIndex / 2;
 6965            if (_priorities[bubbleIndex] < _priorities[parentIdx])
 3366            {
 67                // the parent priority is higher; do the swap.
 3368                var tempPriority = _priorities[parentIdx];
 3369                var tempItem = _heap[parentIdx];
 3370                _priorities[parentIdx] = _priorities[bubbleIndex];
 3371                _heap[parentIdx] = _heap[bubbleIndex];
 3372                _priorities[bubbleIndex] = tempPriority;
 3373                _heap[bubbleIndex] = tempItem;
 74
 3375                bubbleIndex = parentIdx;
 3376            }
 77            else
 3678            {
 79                // the parent priority is lower or equal; the item will not bubble up more.
 3680                break;
 81            }
 3382        }
 15683    }
 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)
 138105    {
 138106        priority = 0;
 138107        if (_count <= 0)
 0108        {
 0109            return default;
 110        }
 111
 138112        var item = _heap[1]; // get the first item.
 138113        priority = _priorities[1];
 114
 138115        _count--; // reduce the element count.
 138116        _latestIndex--; // reduce the latest index.
 117
 138118        var swapItem = 1;
 138119        var parentPriority = _priorities[_latestIndex];
 138120        var parentItem = _heap[_latestIndex];
 138121        _heap[1] = parentItem; // place the last element on top.
 138122        _priorities[1] = parentPriority; // place the last element on top.
 123        do
 205124        {
 205125            var parent = swapItem;
 205126            var swapItemPriority = 0d;
 205127            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            }
 204150            else if (2 * parent <= _latestIndex)
 66151            {
 152                // Only one child exists
 66153                swapItemPriority = _priorities[2 * parent];
 66154                if (parentPriority >= swapItemPriority)
 66155                {
 66156                    swapItem = 2 * parent;
 66157                }
 158                else
 0159                {
 0160                    break;
 161                }
 66162            }
 163            else
 138164            {
 138165                break;
 166            }
 167
 67168            _priorities[parent] = swapItemPriority;
 67169            _priorities[swapItem] = parentPriority;
 67170            _heap[parent] = _heap[swapItem];
 67171            _heap[swapItem] = parentItem;
 134172        } while (true);
 173
 138174        return item;
 138175    }
 176
 177    /// <summary>
 178    /// Clears this priority queue.
 179    /// </summary>
 180    public void Clear()
 30181    {
 30182        _count = 0;
 30183        _latestIndex = 1;
 30184    }
 185}
Generated by: ReportGenerator 4.8.2.0
04/15/2025 - 13:59:49
GitHub | www.palmmedia.de

Methods/Properties

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