< Summary

Class:Itinero.Routing.Flavours.Dijkstra.PreviousEdgeEnumerable
Assembly:Itinero
File(s):/home/runner/work/routing2/routing2/src/Itinero/Routing/Flavours/Dijkstra/PreviousEdgeEnumerable.cs
Covered lines:37
Uncovered lines:3
Coverable lines:40
Total lines:131
Line coverage:92.5% (37 of 40)
Covered branches:13
Total branches:14
Branch coverage:92.8% (13 of 14)
Tag:284_38118444584

Metrics

MethodBranch coverage Cyclomatic complexity Line coverage
.ctor(...)100%1100%
.ctor(...)100%1100%
ForEdge(...)100%1100%
get_IsEmpty()75%4100%
GetEnumerator()100%1100%
get_First()100%2100%
System.Collections.Generic.IEnumerable<System.ValueTuple<Itinero.Network.EdgeId,System.Byte?>>.GetEnumerator()100%1100%
System.Collections.IEnumerable.GetEnumerator()100%10%
.ctor(...)100%2100%
get_Current()100%1100%
System.Collections.IEnumerator.get_Current()100%10%
MoveNext()100%6100%
Reset()100%10%
Dispose()100%1100%

File(s)

/home/runner/work/routing2/routing2/src/Itinero/Routing/Flavours/Dijkstra/PreviousEdgeEnumerable.cs

#LineLine coverage
 1using System.Collections;
 2using System.Collections.Generic;
 3using Itinero.Network;
 4using Itinero.Routing.DataStructures;
 5
 6namespace Itinero.Routing.Flavours.Dijkstra;
 7
 8/// <summary>
 9/// A lazy, struct-based enumerable over previous edges in a path tree.
 10/// </summary>
 11/// <remarks>
 12/// Creating this is allocation-free and <c>foreach</c> on the concrete type uses the struct
 13/// enumerator. Reaching it through <see cref="IEnumerable{T}"/> is not free, and that was the
 14/// trap: <c>ICostFunction.Get</c> declared the parameter as the interface, so every call boxed
 15/// the struct, and every enumeration boxed the enumerator too. In the allocation profile those
 16/// were 10.4% and 12.9% — **23% of everything the service allocated**, for a sequence whose
 17/// first element is all anyone reads.
 18///
 19/// So the cost function takes this concrete type now. Public for that reason, with an internal
 20/// constructor: implementations outside Itinero receive one and pass it on, but only the search
 21/// can create one.
 22/// </remarks>
 23public readonly struct PreviousEdgeEnumerable : IEnumerable<(EdgeId edge, byte? turn)>
 24{
 25    private readonly PathTree? _tree;
 26    private readonly uint _pointer;
 27    private readonly EdgeId _singleEdge;
 28    private readonly byte? _singleTurn;
 29    private readonly bool _hasSingle;
 30
 31    internal PreviousEdgeEnumerable(PathTree tree, uint pointer)
 56186832    {
 56186833        _tree = tree;
 56186834        _pointer = pointer;
 56186835    }
 36
 37    private PreviousEdgeEnumerable(EdgeId edge, byte? turn)
 2838    {
 2839        _pointer = uint.MaxValue;
 2840        _singleEdge = edge;
 2841        _singleTurn = turn;
 2842        _hasSingle = true;
 2843    }
 44
 45    /// <summary>
 46    /// A sequence of exactly one previous edge.
 47    /// </summary>
 48    /// <remarks>
 49    /// The callers that need this were writing <c>new[] { (edge, order) }</c> — an array
 50    /// allocated per call to carry a single element through an interface that then boxed it.
 51    /// Held inline here instead, so the whole thing stays on the stack.
 52    /// </remarks>
 2853    public static PreviousEdgeEnumerable ForEdge(EdgeId edge, byte? turn) => new(edge, turn);
 54
 55    /// <summary>
 56    /// Returns true if there are no previous edges.
 57    /// </summary>
 96422258    public bool IsEmpty => !_hasSingle && (_tree == null || _pointer == uint.MaxValue);
 59
 60    /// <summary>
 61    /// Returns a struct enumerator (no allocation when used via foreach on the concrete type).
 62    /// </summary>
 111222763    public Enumerator GetEnumerator() => new(_tree, _pointer, _singleEdge, _singleTurn, _hasSingle);
 64
 65    /// <summary>
 66    /// The most recent previous edge, or null when there is none.
 67    /// </summary>
 68    /// <remarks>
 69    /// Every cost function today wants exactly this and used to get it with
 70    /// <c>previousEdges.FirstOrDefault()</c> — a LINQ call through the interface, which is what
 71    /// boxed the enumerator. The full sequence stays available for the prefix comparison the
 72    /// turn-cost code has a TODO for; this is just the part anyone actually reads.
 73    /// </remarks>
 74    public (EdgeId edge, byte? turn)? First
 75    {
 76        get
 111222777        {
 111222778            var enumerator = this.GetEnumerator();
 79
 111222780            return enumerator.MoveNext() ? enumerator.Current : null;
 111222781        }
 82    }
 83
 84    IEnumerator<(EdgeId edge, byte? turn)> IEnumerable<(EdgeId edge, byte? turn)>.GetEnumerator() =>
 2185        new Enumerator(_tree, _pointer, _singleEdge, _singleTurn, _hasSingle);
 86
 87    IEnumerator IEnumerable.GetEnumerator() =>
 088        new Enumerator(_tree, _pointer, _singleEdge, _singleTurn, _hasSingle);
 89
 90    public struct Enumerator : IEnumerator<(EdgeId edge, byte? turn)>
 91    {
 92        private readonly PathTree? _tree;
 93        private uint _pointer;
 94        private (EdgeId edge, byte? turn) _current;
 95        private bool _single;
 96
 97        internal Enumerator(PathTree? tree, uint pointer, EdgeId singleEdge, byte? singleTurn,
 98            bool hasSingle)
 111224899        {
 1112248100            _tree = tree;
 1112248101            _pointer = pointer;
 1112248102            _current = hasSingle ? (singleEdge, singleTurn) : default;
 1112248103            _single = hasSingle;
 1112248104        }
 105
 561749106        public (EdgeId edge, byte? turn) Current => _current;
 107
 0108        object IEnumerator.Current => _current;
 109
 110        public bool MoveNext()
 1112248111        {
 1112248112            if (_single)
 28113            {
 114                // _current already holds it; yield once and stop.
 28115                _single = false;
 28116                return true;
 117            }
 118
 1662719119            if (_tree == null || _pointer == uint.MaxValue) return false;
 120
 561721121            var (_, edge, _, head, next) = PathTreeExtensions.GetVisit(_tree, _pointer);
 561721122            _current = (edge, head);
 561721123            _pointer = next;
 561721124            return true;
 1112248125        }
 126
 0127        public void Reset() { }
 128
 42129        public void Dispose() { }
 130    }
 131}