< Summary

Class:Itinero.Routing.DataStructures.BinaryHeap`1
Assembly:Itinero
File(s):/home/runner/work/routing2/routing2/src/Itinero/Routing/DataStructures/BinaryHeap.cs
Covered lines:71
Uncovered lines:16
Coverable lines:87
Total lines:170
Line coverage:81.6% (71 of 87)
Covered branches:15
Total branches:18
Branch coverage:83.3% (15 of 18)
Tag:284_38118444584

Metrics

MethodBranch coverage Cyclomatic complexity Line coverage
.ctor()100%1100%
.ctor(...)100%1100%
get_Count()100%1100%
Push(...)83.33%683.33%
PeekWeight()100%10%
Peek()100%10%
Pop(...)83.33%1286.36%
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>
 8/// <remarks>
 9/// Priorities and items are separate arrays: sifting is almost all priority comparisons, and a
 10/// combined (T item, double priority)[] made each one stride over the item to read 8 bytes.
 11/// </remarks>
 12internal class BinaryHeap<T>
 13    where T : struct
 14{
 15    private T[] _items;
 16    private double[] _priorities;
 17    private int _count;
 18    private uint _latestIndex;
 19
 20    /// <summary>
 21    /// Creates a new binary heap.
 22    /// </summary>
 23    public BinaryHeap()
 107124        : this(1024) { }
 25
 26    /// <summary>
 27    /// Creates a new binary heap.
 28    /// </summary>
 35729    public BinaryHeap(uint initialSize)
 35730    {
 35731        _items = new T[initialSize];
 35732        _priorities = new double[initialSize];
 35733        _count = 0;
 35734        _latestIndex = 1;
 35735    }
 36
 37    /// <summary>
 38    /// Returns the number of items in this queue.
 39    /// </summary>
 42475540    public int Count => _count;
 41
 42    /// <summary>
 43    /// Enqueues a given item.
 44    /// </summary>
 45    public void Push(T item, double priority)
 42872146    {
 42872147        _count++;
 48
 42872149        if (_latestIndex == _items.Length - 1)
 050        {
 051            Array.Resize(ref _items, _items.Length * 2);
 052            Array.Resize(ref _priorities, _priorities.Length * 2);
 053        }
 54
 55        // ... and let it 'bubble' up using hole-sinking:
 56        // instead of swapping at each level, leave a hole and move it up.
 42872157        var bubbleIndex = _latestIndex;
 42872158        _latestIndex++;
 70927359        while (bubbleIndex != 1)
 63860460        {
 63860461            var parentIdx = bubbleIndex / 2;
 63860462            if (priority < _priorities[parentIdx])
 28055263            {
 28055264                _items[bubbleIndex] = _items[parentIdx];
 28055265                _priorities[bubbleIndex] = _priorities[parentIdx];
 28055266                bubbleIndex = parentIdx;
 28055267            }
 68            else
 35805269            {
 35805270                break;
 71            }
 28055272        }
 73
 42872174        _items[bubbleIndex] = item;
 42872175        _priorities[bubbleIndex] = priority;
 42872176    }
 77
 78    /// <summary>
 79    /// Returns the smallest weight in the queue.
 80    /// </summary>
 81    public double PeekWeight()
 082    {
 083        return _priorities[1];
 084    }
 85
 86    /// <summary>
 87    /// Returns the object with the smallest weight.
 88    /// </summary>
 89    public T Peek()
 090    {
 091        return _items[1];
 092    }
 93
 94    /// <summary>
 95    /// Returns the object with the smallest weight and removes it.
 96    /// </summary>
 97    public T Pop(out double priority)
 41210298    {
 41210299        priority = 0;
 412102100        if (_count <= 0)
 0101        {
 0102            return default;
 103        }
 104
 412102105        var result = _items[1];
 412102106        priority = _priorities[1];
 107
 412102108        _count--;
 412102109        _latestIndex--;
 110
 111        // take the last element and sift it down from the root.
 412102112        var lastItem = _items[_latestIndex];
 412102113        var lastPriority = _priorities[_latestIndex];
 114
 115        // sift down using hole-sinking: move the smaller child up,
 116        // place the last element at the final hole position.
 412102117        uint hole = 1;
 1298716118        while (true)
 1298716119        {
 1298716120            var child = hole * 2;
 1298716121            if (child + 1 <= _latestIndex)
 992006122            {
 123                // two children exist — pick the smaller one.
 992006124                if (_priorities[child + 1] < _priorities[child])
 457373125                {
 457373126                    child++;
 457373127                }
 128
 992006129                if (lastPriority <= _priorities[child])
 105392130                {
 105392131                    break;
 132                }
 133
 886614134                _items[hole] = _items[child];
 886614135                _priorities[hole] = _priorities[child];
 886614136                hole = child;
 886614137            }
 306710138            else if (child <= _latestIndex)
 99483139            {
 140                // only left child exists.
 99483141                if (lastPriority <= _priorities[child])
 99483142                {
 99483143                    break;
 144                }
 145
 0146                _items[hole] = _items[child];
 0147                _priorities[hole] = _priorities[child];
 0148                hole = child;
 0149            }
 150            else
 207227151            {
 207227152                break;
 153            }
 886614154        }
 155
 412102156        _items[hole] = lastItem;
 412102157        _priorities[hole] = lastPriority;
 158
 412102159        return result;
 412102160    }
 161
 162    /// <summary>
 163    /// Clears this priority queue.
 164    /// </summary>
 165    public void Clear()
 11588166    {
 11588167        _count = 0;
 11588168        _latestIndex = 1;
 11588169    }
 170}