| | | 1 | | using System; |
| | | 2 | | using System.Collections.Generic; |
| | | 3 | | using System.Threading; |
| | | 4 | | using System.Threading.Tasks; |
| | | 5 | | using Itinero.Network; |
| | | 6 | | using Itinero.Network.Enumerators.Edges; |
| | | 7 | | using Itinero.Network.Search.Reachability; |
| | | 8 | | using Itinero.Routing.Costs; |
| | | 9 | | using Itinero.Routing.DataStructures; |
| | | 10 | | using Itinero.Snapping; |
| | | 11 | | |
| | | 12 | | namespace Itinero.Routing.Flavours.Dijkstra.Bidirectional; |
| | | 13 | | |
| | | 14 | | /// <summary> |
| | | 15 | | /// One side of a bidirectional search: everything reached so far from one endpoint, and |
| | | 16 | | /// everywhere it could go next. |
| | | 17 | | /// </summary> |
| | | 18 | | /// <remarks> |
| | | 19 | | /// A type of its own because a half outlives the call that created it: the half the snapper |
| | | 20 | | /// expands to check reachability IS the half the search continues with. |
| | | 21 | | /// </remarks> |
| | | 22 | | internal sealed class SearchHalf |
| | | 23 | | { |
| | | 24 | | /// <summary> |
| | | 25 | | /// Whether this half grows forward from an origin or backward from a destination; it decides |
| | | 26 | | /// which way edge costs are read, so it belongs to the half rather than to each step. |
| | | 27 | | /// </summary> |
| | | 28 | | public bool IsForwardHalf { get; } |
| | | 29 | | |
| | | 30 | | |
| | | 31 | | /// <summary> |
| | | 32 | | /// The edge at the other end of the route. Set so this half can notice when it gets there. |
| | | 33 | | /// </summary> |
| | | 34 | | public EdgeId? OtherEndpointEdge { get; set; } |
| | | 35 | | |
| | | 36 | | /// <summary> |
| | | 37 | | /// Whether this half has settled a state on <see cref="OtherEndpointEdge"/>. |
| | | 38 | | /// </summary> |
| | | 39 | | /// <remarks> |
| | | 40 | | /// With an empty heap this separates "nowhere left to go" from "already there": no path |
| | | 41 | | /// exists, so the other half need not walk to the tile budget to find that out. |
| | | 42 | | /// </remarks> |
| | | 43 | | public bool ReachedOtherEndpoint { get; private set; } |
| | | 44 | | |
| | | 45 | | public SearchHalf(bool isForwardHalf) |
| | | 46 | | { |
| | | 47 | | this.IsForwardHalf = isForwardHalf; |
| | | 48 | | } |
| | | 49 | | |
| | | 50 | | /// <summary> |
| | | 51 | | /// Whether this half has traversed a local-access edge. A closed component out in ordinary |
| | | 52 | | /// road network is an island and there is nothing more to learn about it; among |
| | | 53 | | /// access=destination edges it is worth a second opinion before rejecting a snap. |
| | | 54 | | /// </summary> |
| | | 55 | | public bool SawLocalAccess { get; private set; } |
| | | 56 | | |
| | | 57 | | /// <summary> |
| | | 58 | | /// Local-access states pushed but not yet settled. Zero means the frontier has left the |
| | | 59 | | /// enclave rather than merely touched its edge. |
| | | 60 | | /// </summary> |
| | | 61 | | /// <remarks> |
| | | 62 | | /// Counted rather than scanned: asked after every step, so walking the heap would make |
| | | 63 | | /// escaping a pocket quadratic in its size. |
| | | 64 | | /// </remarks> |
| | | 65 | | public int LocalOnHeap { get; private set; } |
| | | 66 | | |
| | | 67 | | public readonly PathTree Tree = new(); |
| | | 68 | | |
| | | 69 | | // Carries g because the heap is ordered by g + p; only the stopping rule uses the key. |
| | | 70 | | public readonly BinaryHeap<(uint pointer, EdgeId edge, VertexId vertex, double g)> Heap = new(); |
| | | 71 | | public readonly HashSet<(EdgeId edge, VertexId vertex)> Settled = new(); |
| | | 72 | | |
| | | 73 | | // Per-vertex list of settled arrivals. Each entry records the incoming edge plus the head |
| | | 74 | | // order at this vertex for that edge — both are needed to query turn costs against this |
| | | 75 | | // label when the other half asks "can I meet you here?". |
| | | 76 | | public readonly Dictionary<VertexId, List<SettledEntry>> SettledByVertex = new(); |
| | | 77 | | |
| | | 78 | | public void Clear() |
| | | 79 | | { |
| | | 80 | | Tree.Clear(); |
| | | 81 | | Heap.Clear(); |
| | | 82 | | Settled.Clear(); |
| | | 83 | | SettledByVertex.Clear(); |
| | | 84 | | this.SawLocalAccess = false; |
| | | 85 | | this.LocalOnHeap = 0; |
| | | 86 | | this.ReachedOtherEndpoint = false; |
| | | 87 | | } |
| | | 88 | | |
| | | 89 | | /// Pops one state, keeping the local-frontier count in step. |
| | | 90 | | private (uint pointer, EdgeId edge, VertexId vertex, double g) PopCounted(out double key) |
| | | 91 | | { |
| | | 92 | | var entry = Heap.Pop(out key); |
| | | 93 | | var (_, _, _, _, localAccess, _, _) = Tree.GetVisitWithState(entry.pointer); |
| | | 94 | | if (localAccess) this.LocalOnHeap--; |
| | | 95 | | return entry; |
| | | 96 | | } |
| | | 97 | | |
| | | 98 | | /// Pushes one state, keeping the local-frontier count in step. |
| | | 99 | | private void PushCounted((uint pointer, EdgeId edge, VertexId vertex, double g) entry, |
| | | 100 | | double key, bool localAccess) |
| | | 101 | | { |
| | | 102 | | if (localAccess) this.LocalOnHeap++; |
| | | 103 | | Heap.Push(entry, key); |
| | | 104 | | } |
| | | 105 | | |
| | | 106 | | /// <summary> |
| | | 107 | | /// Seeds this half from a snapped point: the states you can be in having just started on |
| | | 108 | | /// that edge, at that offset. |
| | | 109 | | /// </summary> |
| | | 110 | | public void PushTerminal( |
| | | 111 | | RoutingNetworkEdgeEnumerator enumerator, |
| | | 112 | | SnapPoint snap, |
| | | 113 | | ICostFunction costFunction, |
| | | 114 | | HeuristicFunc? potential) |
| | | 115 | | { |
| | | 116 | | // Forward half computes cost in the edge's natural direction, backward half against it, |
| | | 117 | | // so the backward half reaches "back toward the origin" with the right weights. |
| | | 118 | | foreach (var forward in new[] { true, false }) |
| | | 119 | | { |
| | | 120 | | if (!enumerator.MoveTo(snap.EdgeId, forward)) continue; |
| | | 121 | | var (canAccess, _, localAccess, cost, _) = costFunction.Get(enumerator, tailToHead: this.IsForwardHalf); |
| | | 122 | | if (!canAccess || cost <= 0) continue; |
| | | 123 | | var offsetCost = forward |
| | | 124 | | ? cost * (1 - snap.OffsetFactor()) |
| | | 125 | | : cost * snap.OffsetFactor(); |
| | | 126 | | this.SawLocalAccess |= localAccess; |
| | | 127 | | var p = Tree.AddVisit(enumerator, leftMain: false, localAccess: localAccess, uint.MaxValue); |
| | | 128 | | this.PushCounted((p, enumerator.EdgeId, enumerator.Head, offsetCost), |
| | | 129 | | offsetCost + Potential(potential, enumerator), localAccess); |
| | | 130 | | |
| | | 131 | | } |
| | | 132 | | } |
| | | 133 | | |
| | | 134 | | /// <summary> |
| | | 135 | | /// Rebuilds the frontier's ordering against a goal-direction potential. |
| | | 136 | | /// </summary> |
| | | 137 | | /// <remarks> |
| | | 138 | | /// An expansion with no goal keyed its frontier with p = 0; mixing that with potential-keyed |
| | | 139 | | /// states settles them out of order, which in a Dijkstra is a wrong answer, not a slow one. |
| | | 140 | | /// </remarks> |
| | | 141 | | public void ReKey(RoutingNetwork network, HeuristicFunc? potential) |
| | | 142 | | { |
| | | 143 | | if (potential == null || Heap.Count == 0) return; |
| | | 144 | | |
| | | 145 | | var entries = new List<(uint pointer, EdgeId edge, VertexId vertex, double g)>(Heap.Count); |
| | | 146 | | while (Heap.Count > 0) entries.Add(Heap.Pop(out _)); |
| | | 147 | | |
| | | 148 | | var enumerator = network.GetEdgeEnumerator(); |
| | | 149 | | foreach (var entry in entries) |
| | | 150 | | { |
| | | 151 | | // Position on the arrival so the potential is taken at the state's own location, |
| | | 152 | | // matching how the key was formed when the search pushes normally. |
| | | 153 | | var p = 0d; |
| | | 154 | | if (enumerator.MoveTo(entry.edge, true)) |
| | | 155 | | { |
| | | 156 | | p = enumerator.Head == entry.vertex |
| | | 157 | | ? Potential(potential, enumerator) |
| | | 158 | | : enumerator.MoveTo(entry.edge, false) ? Potential(potential, enumerator) : 0d; |
| | | 159 | | } |
| | | 160 | | |
| | | 161 | | Heap.Push(entry, entry.g + p); |
| | | 162 | | } |
| | | 163 | | } |
| | | 164 | | |
| | | 165 | | /// <summary> |
| | | 166 | | /// Expands out of a local-access enclave, stopping once it is properly clear of it. |
| | | 167 | | /// </summary> |
| | | 168 | | /// <param name="threshold"> |
| | | 169 | | /// How much must be explored before clearing the enclave counts; without it, stepping onto |
| | | 170 | | /// the first ordinary road would stop the search having proven nothing. |
| | | 171 | | /// </param> |
| | | 172 | | /// <param name="ceiling"> |
| | | 173 | | /// Work limit. Reaching it means the area is too big to treat as an enclave at all. |
| | | 174 | | /// </param> |
| | | 175 | | /// <remarks> |
| | | 176 | | /// Both halves of the stopping condition are load-bearing: the threshold alone can stop deep |
| | | 177 | | /// inside the enclave, the non-local frontier alone one edge out of a driveway. |
| | | 178 | | /// </remarks> |
| | | 179 | | public async Task<ReachabilityVerdict> EscapeLocalAsync( |
| | | 180 | | RoutingNetwork network, |
| | | 181 | | ICostFunction costFunction, |
| | | 182 | | int threshold, |
| | | 183 | | int ceiling, |
| | | 184 | | CancellationToken cancellationToken = default) |
| | | 185 | | { |
| | | 186 | | var expanded = 0; |
| | | 187 | | while (Heap.Count > 0) |
| | | 188 | | { |
| | | 189 | | cancellationToken.ThrowIfCancellationRequested(); |
| | | 190 | | |
| | | 191 | | await this.StepAsync(network, costFunction, isMainN: null, localAccessRule: true, |
| | | 192 | | bestCost: double.MaxValue, settledCb: LoadTileFor, potential: null, |
| | | 193 | | onReached: null, cancellationToken); |
| | | 194 | | |
| | | 195 | | expanded++; |
| | | 196 | | |
| | | 197 | | // Too big to be an enclave. Not a statement that the search got out of anything — |
| | | 198 | | // a statement that there is nothing here to get out of. |
| | | 199 | | if (expanded >= ceiling) return ReachabilityVerdict.BeyondBound; |
| | | 200 | | |
| | | 201 | | if (expanded >= threshold && this.LocalOnHeap == 0) return ReachabilityVerdict.BeyondBound; |
| | | 202 | | } |
| | | 203 | | |
| | | 204 | | // Ran out of network. Everything reachable from the enclave has been seen and it does |
| | | 205 | | // not lead anywhere, whether or not it ever got onto ordinary roads. |
| | | 206 | | return ReachabilityVerdict.Island; |
| | | 207 | | |
| | | 208 | | async Task<bool> LoadTileFor(VertexId v) |
| | | 209 | | { |
| | | 210 | | if (!network.UsageNotifier.IsVertexDataReady(network, v)) |
| | | 211 | | { |
| | | 212 | | await network.UsageNotifier.NotifyVertex(network, v, cancellationToken); |
| | | 213 | | } |
| | | 214 | | |
| | | 215 | | return false; |
| | | 216 | | } |
| | | 217 | | } |
| | | 218 | | |
| | | 219 | | /// <summary> |
| | | 220 | | /// Expands until this half either runs out of network or has gone far enough to be believed — |
| | | 221 | | /// the reachability check a snap needs, done by the search that will continue from here. |
| | | 222 | | /// </summary> |
| | | 223 | | /// <param name="ceiling"> |
| | | 224 | | /// States to expand before concluding the network is real. Running out first means the |
| | | 225 | | /// component is closed, which is an island whatever its size. |
| | | 226 | | /// </param> |
| | | 227 | | /// <remarks> |
| | | 228 | | /// No access rule here, deliberately: the question is what can be reached, not what route is |
| | | 229 | | /// legal, so a non-local road buried in an estate is crossed rather than refused. |
| | | 230 | | /// </remarks> |
| | | 231 | | public async Task<ReachabilityVerdict> ExpandAsync( |
| | | 232 | | RoutingNetwork network, |
| | | 233 | | ICostFunction costFunction, |
| | | 234 | | int ceiling, |
| | | 235 | | CancellationToken cancellationToken = default) |
| | | 236 | | { |
| | | 237 | | var expanded = 0; |
| | | 238 | | while (Heap.Count > 0) |
| | | 239 | | { |
| | | 240 | | cancellationToken.ThrowIfCancellationRequested(); |
| | | 241 | | |
| | | 242 | | // The same access rule the search itself applies, and it has to be: these states |
| | | 243 | | // become the search's frontier, so anything allowed here the finished route may do. |
| | | 244 | | await this.StepAsync(network, costFunction, isMainN: null, localAccessRule: true, |
| | | 245 | | bestCost: double.MaxValue, settledCb: LoadTileFor, potential: null, |
| | | 246 | | onReached: null, cancellationToken); |
| | | 247 | | |
| | | 248 | | expanded++; |
| | | 249 | | if (expanded >= ceiling) return ReachabilityVerdict.BeyondBound; |
| | | 250 | | } |
| | | 251 | | |
| | | 252 | | // Ran out of network: everything reachable has been seen and none of it leaves. |
| | | 253 | | return ReachabilityVerdict.Island; |
| | | 254 | | |
| | | 255 | | // Pulls in a vertex's tile before expanding from it. Without this the walk stops at the |
| | | 256 | | // edge of whatever happens to be loaded and reports an island wherever the data ran out. |
| | | 257 | | async Task<bool> LoadTileFor(VertexId v) |
| | | 258 | | { |
| | | 259 | | if (!network.UsageNotifier.IsVertexDataReady(network, v)) |
| | | 260 | | { |
| | | 261 | | await network.UsageNotifier.NotifyVertex(network, v, cancellationToken); |
| | | 262 | | } |
| | | 263 | | |
| | | 264 | | return false; |
| | | 265 | | } |
| | | 266 | | } |
| | | 267 | | |
| | | 268 | | private RoutingNetwork? _probeNetwork; |
| | | 269 | | |
| | | 270 | | private RoutingNetworkEdgeEnumerator? _probe; |
| | | 271 | | |
| | | 272 | | /// <summary> |
| | | 273 | | /// The edge enumerator this half expands with, created once and reused. |
| | | 274 | | /// </summary> |
| | | 275 | | /// <remarks> |
| | | 276 | | /// A fresh one per step was three allocations per settled state and the top two entries in |
| | | 277 | | /// the allocation profile. Safe because a half is never stepped concurrently with itself. |
| | | 278 | | /// </remarks> |
| | | 279 | | private RoutingNetworkEdgeEnumerator Probe(RoutingNetwork network) |
| | | 280 | | { |
| | | 281 | | if (_probe != null && ReferenceEquals(_probeNetwork, network)) return _probe; |
| | | 282 | | |
| | | 283 | | _probe = network.GetEdgeEnumerator(); |
| | | 284 | | _probeNetwork = network; |
| | | 285 | | |
| | | 286 | | return _probe; |
| | | 287 | | } |
| | | 288 | | |
| | | 289 | | /// <summary> |
| | | 290 | | /// Settles the cheapest state on the frontier and relaxes its neighbours. |
| | | 291 | | /// </summary> |
| | | 292 | | /// <param name="onReached"> |
| | | 293 | | /// Invoked for every state settled or queued; null when a half expands alone for a snapping |
| | | 294 | | /// check, because there is no other half yet. |
| | | 295 | | /// </param> |
| | | 296 | | /// <param name="bestCost"> |
| | | 297 | | /// Cost of the best complete path so far, used to prune. No bound yet means MaxValue. |
| | | 298 | | /// </param> |
| | | 299 | | /// <returns>The key of the state settled, or of the last one popped if already settled.</returns> |
| | | 300 | | public async ValueTask<double?> StepAsync( |
| | | 301 | | RoutingNetwork network, |
| | | 302 | | ICostFunction costFunction, |
| | | 303 | | IsMainNFunc? isMainN, |
| | | 304 | | bool localAccessRule, |
| | | 305 | | double bestCost, |
| | | 306 | | Func<VertexId, Task<bool>>? settledCb, |
| | | 307 | | HeuristicFunc? potential, |
| | | 308 | | ReachedCallback? onReached, |
| | | 309 | | CancellationToken cancellationToken, |
| | | 310 | | RelaxedCallback? onRelaxed = null) |
| | | 311 | | { |
| | | 312 | | // Dequeue, skipping already-settled labels. `key` is g + p, `cost` is g. |
| | | 313 | | // PopCounted keeps LocalOnHeap in step: every pushed state is popped exactly once, |
| | | 314 | | // including the ones skipped here as already settled, so the count balances. |
| | | 315 | | var entry = this.PopCounted(out var key); |
| | | 316 | | while (Settled.Contains((entry.edge, entry.vertex))) |
| | | 317 | | { |
| | | 318 | | if (Heap.Count == 0) return key; |
| | | 319 | | entry = this.PopCounted(out key); |
| | | 320 | | } |
| | | 321 | | if (!Settled.Add((entry.edge, entry.vertex))) return key; |
| | | 322 | | |
| | | 323 | | var cost = entry.g; |
| | | 324 | | |
| | | 325 | | var (vertex, edge, forward, _, localAccess, headOrder, _) = Tree.GetVisitWithState(entry.pointer); |
| | | 326 | | this.SawLocalAccess |= localAccess; |
| | | 327 | | |
| | | 328 | | if (this.OtherEndpointEdge.HasValue && edge == this.OtherEndpointEdge.Value) |
| | | 329 | | { |
| | | 330 | | this.ReachedOtherEndpoint = true; |
| | | 331 | | } |
| | | 332 | | |
| | | 333 | | // Record in per-vertex settled multimap for meeting checks initiated by the other half. |
| | | 334 | | if (!SettledByVertex.TryGetValue(vertex, out var list)) |
| | | 335 | | { |
| | | 336 | | list = new List<SettledEntry>(2); |
| | | 337 | | SettledByVertex[vertex] = list; |
| | | 338 | | } |
| | | 339 | | list.Add(new SettledEntry(edge, forward, headOrder, entry.pointer, cost)); |
| | | 340 | | |
| | | 341 | | // Settled callback semantics match the unidirectional edge-based: returning true |
| | | 342 | | // means "stop expanding from this vertex" (e.g. outside the max-distance box). |
| | | 343 | | if (settledCb != null && await settledCb(vertex)) return key; |
| | | 344 | | if (cancellationToken.IsCancellationRequested) return key; |
| | | 345 | | |
| | | 346 | | onReached?.Invoke(edge, forward, headOrder, entry.pointer, cost, vertex); |
| | | 347 | | |
| | | 348 | | // Expand neighbours. |
| | | 349 | | var probe = this.Probe(network); |
| | | 350 | | if (!probe.MoveTo(vertex)) return key; |
| | | 351 | | while (probe.MoveNext()) |
| | | 352 | | { |
| | | 353 | | var neighbourEdge = probe.EdgeId; |
| | | 354 | | if (neighbourEdge == edge) continue; // no U-turn |
| | | 355 | | |
| | | 356 | | // Cost in this half's direction. Forward uses tailToHead=true, backward uses false. |
| | | 357 | | // PreviousEdgeEnumerable provides turn-cost context from the path so far. |
| | | 358 | | var prev = new PreviousEdgeEnumerable(Tree, entry.pointer); |
| | | 359 | | var (canAccess, _, neighbourLocalAccess, neighbourCost, turnCost) = |
| | | 360 | | costFunction.Get(probe, tailToHead: this.IsForwardHalf, prev); |
| | | 361 | | if (!canAccess || neighbourCost is >= double.MaxValue or <= 0) continue; |
| | | 362 | | if (turnCost is >= double.MaxValue or < 0) continue; |
| | | 363 | | this.SawLocalAccess |= neighbourLocalAccess; |
| | | 364 | | |
| | | 365 | | // A local-access edge may only be reached from another, so each half stays inside its |
| | | 366 | | // own pocket and cannot use access=destination streets as a shortcut between roads. |
| | | 367 | | if (localAccessRule) |
| | | 368 | | { |
| | | 369 | | // L to L, L to N, N to N. Never N to L: a half leaves its pocket once and never |
| | | 370 | | // enters another, so the composed path is pocket, network, pocket. |
| | | 371 | | if (neighbourLocalAccess && !localAccess) continue; |
| | | 372 | | } |
| | | 373 | | // Per-half access-aware rule: reject prev_main && !curr_main in this half's direction. |
| | | 374 | | else if (isMainN != null) |
| | | 375 | | { |
| | | 376 | | var prevMain = IsMain(edge, localAccess, isMainN); |
| | | 377 | | var currMain = IsMain(neighbourEdge, neighbourLocalAccess, isMainN); |
| | | 378 | | if (prevMain && !currMain) continue; |
| | | 379 | | } |
| | | 380 | | |
| | | 381 | | var totalCost = cost + neighbourCost + turnCost; |
| | | 382 | | if (totalCost >= bestCost) continue; |
| | | 383 | | |
| | | 384 | | var neighbourPointer = Tree.AddVisit(probe, leftMain: false, localAccess: neighbourLocalAccess, entry.pointe |
| | | 385 | | |
| | | 386 | | // Meeting check against the other half's settled set BEFORE pushing — mirrors the |
| | | 387 | | // existing vertex-based pattern's OnQueued hook. |
| | | 388 | | onReached?.Invoke(neighbourEdge, probe.Forward, probe.HeadOrder, neighbourPointer, |
| | | 389 | | totalCost, probe.Head); |
| | | 390 | | onRelaxed?.Invoke(edge, vertex, neighbourEdge); |
| | | 391 | | |
| | | 392 | | this.PushCounted((neighbourPointer, neighbourEdge, probe.Head, totalCost), |
| | | 393 | | totalCost + Potential(potential, probe), neighbourLocalAccess); |
| | | 394 | | } |
| | | 395 | | |
| | | 396 | | return key; |
| | | 397 | | } |
| | | 398 | | |
| | | 399 | | /// The half's potential at the edge's head; 0 without one. HeadLocation is memoised. |
| | | 400 | | private static double Potential(HeuristicFunc? potential, RoutingNetworkEdgeEnumerator enumerator) |
| | | 401 | | { |
| | | 402 | | if (potential == null) return 0d; |
| | | 403 | | |
| | | 404 | | var (longitude, latitude, _) = enumerator.HeadLocation; |
| | | 405 | | return potential(longitude, latitude); |
| | | 406 | | } |
| | | 407 | | |
| | | 408 | | /// <summary> |
| | | 409 | | /// The turn where one half's arrival continues into the other's. Neither half charged it: the |
| | | 410 | | /// turn only exists once the two are composed, which also inverts pathOutgoing's direction. |
| | | 411 | | /// </summary> |
| | | 412 | | /// <returns><see cref="double.MaxValue"/> when the turn is forbidden or the edge is gone.</returns> |
| | | 413 | | internal static double TurnCostBetween( |
| | | 414 | | RoutingNetworkEdgeEnumerator enumerator, |
| | | 415 | | ICostFunction costFunction, |
| | | 416 | | EdgeId pathIncoming, |
| | | 417 | | byte? pathIncomingHeadOrder, |
| | | 418 | | EdgeId pathOutgoing, |
| | | 419 | | bool pathOutgoingForwardFromOther) |
| | | 420 | | { |
| | | 421 | | // Position at the outgoing edge in path-outgoing direction (the shared vertex is tail). |
| | | 422 | | if (!enumerator.MoveTo(pathOutgoing, !pathOutgoingForwardFromOther)) return double.MaxValue; |
| | | 423 | | |
| | | 424 | | var previous = pathIncomingHeadOrder.HasValue |
| | | 425 | | ? PreviousEdgeEnumerable.ForEdge(pathIncoming, pathIncomingHeadOrder) |
| | | 426 | | : default; |
| | | 427 | | var (_, _, _, _, turnCost) = costFunction.Get(enumerator, tailToHead: true, previous); |
| | | 428 | | return turnCost; |
| | | 429 | | } |
| | | 430 | | |
| | | 431 | | private static bool IsMain(EdgeId edgeId, bool localAccess, IsMainNFunc isMainN) |
| | | 432 | | { |
| | | 433 | | var verdict = isMainN(edgeId, localAccess); |
| | | 434 | | // Without a leftMain state-bit the bidirectional defaults unknown to "main": the per-half |
| | | 435 | | // rule then doesn't spuriously reject across edges we know nothing about. |
| | | 436 | | return verdict ?? true; |
| | | 437 | | } |
| | | 438 | | } |
| | | 439 | | |
| | | 440 | | /// <summary> |
| | | 441 | | /// Notifies that a half has reached a state — settled it, or queued it. |
| | | 442 | | /// </summary> |
| | | 443 | | internal delegate void ReachedCallback( |
| | | 444 | | EdgeId edge, bool forward, byte? headOrder, uint pointer, double cost, VertexId vertex); |
| | | 445 | | |
| | | 446 | | /// <summary> |
| | | 447 | | /// Invoked for every relaxation, improving or not: filtering to improvements would describe a |
| | | 448 | | /// tree rather than a graph. By value, since a path-tree pointer means nothing to an outside |
| | | 449 | | /// caller, and without costs, which the two halves measure in opposite directions. |
| | | 450 | | /// </summary> |
| | | 451 | | /// <param name="turnVertex">Where the two edges meet, in this half's direction of travel.</param> |
| | | 452 | | internal delegate void RelaxedCallback(EdgeId fromEdge, VertexId turnVertex, EdgeId toEdge); |
| | | 453 | | |
| | | 454 | | /// <summary> |
| | | 455 | | /// One arrival at a vertex, recorded so the other half can ask whether it may meet here. |
| | | 456 | | /// </summary> |
| | | 457 | | internal readonly record struct SettledEntry( |
| | 2055 | 458 | | EdgeId Edge, bool Forward, byte? HeadOrder, uint Pointer, double Cost); |