< Summary

Class:Itinero.MapMatching.Model.BinaryHeap`1
Assembly:Itinero.MapMatching
File(s):/home/runner/work/routing2/routing2/src/Itinero.MapMatching/Model/BinaryHeap.cs
Covered lines:92
Uncovered lines:12
Coverable lines:104
Total lines:186
Line coverage:88.4% (92 of 104)
Covered branches:18
Total branches:20
Branch coverage:90% (18 of 20)
Tag:251_23667616543

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(...)85.71%1496.36%
Clear()100%10%

File(s)

/home/runner/work/routing2/routing2/src/Itinero.MapMatching/Model/BinaryHeap.cs

#LineLine coverage
 1using System;
 2
 3namespace Itinero.MapMatching.Model;
 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()
 2920        : this(2)
 2921    {
 22
 2923    }
 24
 25    /// <summary>
 26    /// Creates a new binary heap.
 27    /// </summary>
 2928    public BinaryHeap(uint initialSize)
 2929    {
 2930        _heap = new T[initialSize];
 2931        _priorities = new double[initialSize];
 32
 2933        _count = 0;
 2934        _latestIndex = 1;
 2935    }
 36
 37    /// <summary>
 38    /// Returns the number of items in this queue.
 39    /// </summary>
 9550840    public int Count => _count;
 41
 42    /// <summary>
 43    /// Enqueues a given item.
 44    /// </summary>
 45    public void Push(T item, double priority)
 11449146    {
 11449147        _count++; // another item was added!
 48
 49        // increase size if needed.
 11449150        if (_latestIndex == _priorities.Length - 1)
 28551        {
 52            // time to increase size!
 28553            Array.Resize(ref _heap, _heap.Length + 100);
 28554            Array.Resize(ref _priorities, _priorities.Length + 100);
 28555        }
 56
 57        // add the item at the first free point
 11449158        _priorities[_latestIndex] = priority;
 11449159        _heap[_latestIndex] = item;
 60
 61        // ... and let it 'bubble' up.
 11449162        var bubbleIndex = _latestIndex;
 11449163        _latestIndex++;
 18998264        while (bubbleIndex != 1)
 18928865        {
 66            // bubble until the index is one.
 18928867            var parentIdx = bubbleIndex / 2;
 18928868            if (_priorities[bubbleIndex] < _priorities[parentIdx])
 7549169            {
 70                // the parent priority is higher; do the swap.
 7549171                var tempPriority = _priorities[parentIdx];
 7549172                var tempItem = _heap[parentIdx];
 7549173                _priorities[parentIdx] = _priorities[bubbleIndex];
 7549174                _heap[parentIdx] = _heap[bubbleIndex];
 7549175                _priorities[bubbleIndex] = tempPriority;
 7549176                _heap[bubbleIndex] = tempItem;
 77
 7549178                bubbleIndex = parentIdx;
 7549179            }
 80            else
 11379781            {
 82                // the parent priority is lower or equal; the item will not bubble up more.
 11379783                break;
 84            }
 7549185        }
 11449186    }
 87
 88    /// <summary>
 89    /// Returns the smallest weight in the queue.
 90    /// </summary>
 91    public double PeekWeight()
 092    {
 093        return _priorities[1];
 094    }
 95
 96    /// <summary>
 97    /// Returns the object with the smallest weight.
 98    /// </summary>
 99    public T Peek()
 0100    {
 0101        return _heap[1];
 0102    }
 103
 104    /// <summary>
 105    /// Returns the object with the smallest weight and removes it.
 106    /// </summary>
 107    public T Pop(out double priority)
 95508108    {
 95508109        priority = 0;
 95508110        if (_count <= 0) return default(T);
 111
 95508112        var item = _heap[1]; // get the first item.
 95508113        priority = _priorities[1];
 114
 95508115        _count--; // reduce the element count.
 95508116        _latestIndex--; // reduce the latest index.
 117
 95508118        var swapItem = 1;
 95508119        var parentPriority = _priorities[_latestIndex];
 95508120        var parentItem = _heap[_latestIndex];
 95508121        _heap[1] = parentItem; // place the last element on top.
 95508122        _priorities[1] = parentPriority; // place the last element on top.
 123        do
 1126803124        {
 1126803125            var parent = swapItem;
 1126803126            var swapItemPriority = 0d;
 1126803127            if ((2 * parent + 1) <= _latestIndex)
 1054435128            {
 1054435129                swapItemPriority = _priorities[2 * parent];
 1054435130                var potentialSwapItem = _priorities[2 * parent + 1];
 1054435131                if (parentPriority >= swapItemPriority)
 1006863132                {
 1006863133                    swapItem = 2 * parent;
 1006863134                    if (_priorities[swapItem] >= potentialSwapItem)
 481590135                    {
 481590136                        swapItemPriority = potentialSwapItem;
 481590137                        swapItem = 2 * parent + 1;
 481590138                    }
 1006863139                }
 47572140                else if (parentPriority >= potentialSwapItem)
 23715141                {
 23715142                    swapItemPriority = potentialSwapItem;
 23715143                    swapItem = 2 * parent + 1;
 23715144                }
 145                else
 23857146                {
 23857147                    break;
 148                }
 1030578149            }
 72368150            else if ((2 * parent) <= _latestIndex)
 717151            {
 152                // Only one child exists
 717153                swapItemPriority = _priorities[2 * parent];
 717154                if (parentPriority >= swapItemPriority)
 717155                {
 717156                    swapItem = 2 * parent;
 717157                }
 158                else
 0159                {
 0160                    break;
 161                }
 717162            }
 163            else
 71651164            {
 71651165                break;
 166            }
 167
 1031295168            _priorities[parent] = swapItemPriority;
 1031295169            _priorities[swapItem] = parentPriority;
 1031295170            _heap[parent] = _heap[swapItem];
 1031295171            _heap[swapItem] = parentItem;
 172
 2062590173        } while (true);
 174
 95508175        return item;
 95508176    }
 177
 178    /// <summary>
 179    /// Clears this priority queue.
 180    /// </summary>
 181    public void Clear()
 0182    {
 0183        _count = 0;
 0184        _latestIndex = 1;
 0185    }
 186}
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()