| | | 1 | | using System; |
| | | 2 | | using System.Collections.Generic; |
| | | 3 | | using System.IO; |
| | | 4 | | using Itinero.IO; |
| | | 5 | | using Itinero.Network.Storage; |
| | | 6 | | using Itinero.Network.Tiles.Standalone.Global; |
| | | 7 | | using Itinero.Network.TurnCosts; |
| | | 8 | | |
| | | 9 | | namespace Itinero.Network.Tiles; |
| | | 10 | | |
| | | 11 | | internal partial class NetworkTile |
| | | 12 | | { |
| | | 13 | | private const int DefaultSizeIncrease = 16; |
| | | 14 | | |
| | | 15 | | /// <summary> |
| | | 16 | | /// Makes sure a buffer can hold <paramref name="required"/> elements, growing it geometrically. |
| | | 17 | | /// </summary> |
| | | 18 | | /// <remarks> |
| | | 19 | | /// Fixed-increment growth made appending to a large tile quadratic, and a cached tile is sized to |
| | | 20 | | /// its content so the first boundary edge resizes it. Capacity is invisible to the file format. |
| | | 21 | | /// </remarks> |
| | | 22 | | private static void EnsureCapacity<T>(ref T[] array, long required, int minimumIncrease) |
| | 950104 | 23 | | { |
| | 1869532 | 24 | | if (array.Length >= required) return; |
| | | 25 | | |
| | 30676 | 26 | | var grown = array.Length + Math.Max(minimumIncrease, array.Length >> 3); |
| | 30676 | 27 | | Array.Resize(ref array, (int)Math.Max(required, grown)); |
| | 950104 | 28 | | } |
| | | 29 | | |
| | | 30 | | private readonly uint _tileId; |
| | | 31 | | private readonly int _zoom; // the zoom level. |
| | | 32 | | private readonly Guid _edgeTypeMapId; // the edge type index id. |
| | | 33 | | |
| | 2767 | 34 | | private uint _nextVertexId = 0; // the next vertex id. |
| | | 35 | | |
| | | 36 | | // the pointers, per vertex, to their first edge. |
| | | 37 | | // TODO: investigate if it's worth storing these with less precision, one tile will never contain this much data. |
| | | 38 | | // TODO: investigate if we can not use one-increasing vertex ids but also use their pointers like with the edges. |
| | | 39 | | private uint[] _pointers; |
| | | 40 | | private uint _nextCrossTileId; // the next id for an edge that crosses tile boundaries. |
| | | 41 | | private uint[] _crossEdgePointers; // points to the cross tile boundary edges. |
| | | 42 | | |
| | | 43 | | // the next edge id. |
| | 2767 | 44 | | private uint _nextEdgeId = 0; |
| | | 45 | | |
| | | 46 | | // the edges. |
| | | 47 | | private byte[] _edges; |
| | | 48 | | |
| | | 49 | | /// <summary> |
| | | 50 | | /// Creates a new tile. |
| | | 51 | | /// </summary> |
| | | 52 | | /// <param name="zoom">The zoom level.</param> |
| | | 53 | | /// <param name="tileId">The tile id.</param> |
| | | 54 | | /// <param name="edgeTypeMapId">The edge type index id.</param> |
| | 2747 | 55 | | public NetworkTile(int zoom, uint tileId, Guid? edgeTypeMapId = null) |
| | 2747 | 56 | | { |
| | 2747 | 57 | | _zoom = zoom; |
| | 2747 | 58 | | _tileId = tileId; |
| | 2747 | 59 | | (_boxLeft, _boxTop, _boxLonStep, _boxLatStep) = this.ComputeBox(); |
| | 2747 | 60 | | _edgeTypeMapId = edgeTypeMapId ?? Guid.Empty; |
| | 2747 | 61 | | _nextCrossTileId = 0; |
| | | 62 | | |
| | 2747 | 63 | | _pointers = new uint[0]; |
| | 2747 | 64 | | _edges = new byte[0]; |
| | 2747 | 65 | | _crossEdgePointers = new uint[0]; |
| | | 66 | | |
| | 2747 | 67 | | _coordinates = new byte[0]; |
| | 2747 | 68 | | _shapes = new byte[0]; |
| | 2747 | 69 | | _attributes = new byte[0]; |
| | 2747 | 70 | | _strings = new string[0]; |
| | 2747 | 71 | | } |
| | | 72 | | |
| | 20 | 73 | | private NetworkTile(int zoom, uint tileId, Guid edgeTypeMapId, uint nextCrossTileId, uint[] pointers, |
| | 20 | 74 | | byte[] edges, |
| | 20 | 75 | | uint[] crossEdgePointers, byte[] coordinates, byte[] shapes, |
| | 20 | 76 | | byte[] attributes, |
| | 20 | 77 | | string[] strings, byte[] turnCosts, uint nextVertexId, uint nextEdgeId, |
| | 20 | 78 | | uint nextAttributePointer, |
| | 20 | 79 | | uint nextShapePointer, uint nextStringId) |
| | 20 | 80 | | { |
| | 20 | 81 | | _zoom = zoom; |
| | 20 | 82 | | _tileId = tileId; |
| | 20 | 83 | | (_boxLeft, _boxTop, _boxLonStep, _boxLatStep) = this.ComputeBox(); |
| | 20 | 84 | | _edgeTypeMapId = edgeTypeMapId; |
| | 20 | 85 | | _nextCrossTileId = nextCrossTileId; |
| | 20 | 86 | | _pointers = pointers; |
| | 20 | 87 | | _edges = edges; |
| | 20 | 88 | | _crossEdgePointers = crossEdgePointers; |
| | | 89 | | |
| | 20 | 90 | | _coordinates = coordinates; |
| | 20 | 91 | | _shapes = shapes; |
| | 20 | 92 | | _attributes = attributes; |
| | 20 | 93 | | _strings = strings; |
| | 20 | 94 | | _turnCosts = turnCosts; |
| | | 95 | | |
| | 20 | 96 | | _nextVertexId = nextVertexId; |
| | 20 | 97 | | _nextEdgeId = nextEdgeId; |
| | 20 | 98 | | _nextAttributePointer = nextAttributePointer; |
| | 20 | 99 | | _nextShapePointer = nextShapePointer; |
| | 20 | 100 | | _nextStringId = nextStringId; |
| | 20 | 101 | | } |
| | | 102 | | |
| | | 103 | | /// <summary> |
| | | 104 | | /// Clones this graph tile. |
| | | 105 | | /// </summary> |
| | | 106 | | /// <returns>The copy of this tile.</returns> |
| | | 107 | | public NetworkTile Clone() |
| | 14 | 108 | | { |
| | 14 | 109 | | return new(_zoom, _tileId, _edgeTypeMapId, _nextCrossTileId, (uint[])_pointers.Clone(), (byte[])_edges.Clone(), |
| | 14 | 110 | | (uint[])_crossEdgePointers.Clone(), |
| | 14 | 111 | | (byte[])_coordinates.Clone(), (byte[])_shapes.Clone(), (byte[])_attributes.Clone(), (string[])_strings.Clone |
| | 14 | 112 | | _nextVertexId, |
| | 14 | 113 | | _nextEdgeId, _nextAttributePointer, _nextShapePointer, _nextStringId); |
| | 14 | 114 | | } |
| | | 115 | | |
| | | 116 | | /// <summary> |
| | | 117 | | /// Gets the tile id. |
| | | 118 | | /// </summary> |
| | 16369913 | 119 | | public uint TileId => _tileId; |
| | | 120 | | |
| | | 121 | | /// <summary> |
| | | 122 | | /// Gets the number of vertices. |
| | | 123 | | /// </summary> |
| | 3832812 | 124 | | public uint VertexCount => _nextVertexId; |
| | | 125 | | |
| | | 126 | | /// <summary> |
| | | 127 | | /// Gets the edge type map id. |
| | | 128 | | /// </summary> |
| | 4278565 | 129 | | public Guid EdgeTypeMapId => _edgeTypeMapId; |
| | | 130 | | |
| | | 131 | | /// <summary> |
| | | 132 | | /// Adds a new vertex and returns its id. |
| | | 133 | | /// </summary> |
| | | 134 | | /// <param name="longitude">The longitude.</param> |
| | | 135 | | /// <param name="latitude">The latitude.</param> |
| | | 136 | | /// <param name="e">The elevation in meters.</param> |
| | | 137 | | /// <returns>The ID of the new vertex.</returns> |
| | | 138 | | public VertexId AddVertex(double longitude, double latitude, float? e = null) |
| | 46556 | 139 | | { |
| | | 140 | | // set coordinate. |
| | 46556 | 141 | | this.SetCoordinate(_nextVertexId, longitude, latitude, e); |
| | | 142 | | |
| | | 143 | | // create id. |
| | 46556 | 144 | | var vertexId = new VertexId(_tileId, _nextVertexId); |
| | 46556 | 145 | | _nextVertexId++; |
| | | 146 | | |
| | | 147 | | // make room. |
| | 46556 | 148 | | ArrayBaseExtensions.EnsureMinimumSize(ref _pointers, vertexId.LocalId, DefaultSizeIncrease); |
| | | 149 | | |
| | 46556 | 150 | | return vertexId; |
| | 46556 | 151 | | } |
| | | 152 | | |
| | | 153 | | /// <summary> |
| | | 154 | | /// Returns true if the vertex exists. |
| | | 155 | | /// </summary> |
| | | 156 | | /// <param name="vertex"></param> |
| | | 157 | | /// <returns></returns> |
| | | 158 | | public bool HasVertex(VertexId vertex) |
| | 7234 | 159 | | { |
| | 7234 | 160 | | if (vertex.LocalId >= _nextVertexId) |
| | 1842 | 161 | | { |
| | 1842 | 162 | | return false; |
| | | 163 | | } |
| | | 164 | | |
| | 5392 | 165 | | return true; |
| | 7234 | 166 | | } |
| | | 167 | | |
| | | 168 | | /// <summary> |
| | | 169 | | /// Gets the vertex with the given id. |
| | | 170 | | /// </summary> |
| | | 171 | | /// <param name="vertex">The vertex.</param> |
| | | 172 | | /// <param name="longitude">The longitude.</param> |
| | | 173 | | /// <param name="latitude">The latitude.</param> |
| | | 174 | | /// <param name="elevation">The elevation.</param> |
| | | 175 | | /// <returns>True if the vertex exists.</returns> |
| | | 176 | | public bool TryGetVertex(VertexId vertex, out double longitude, out double latitude, out float? elevation) |
| | 5662444 | 177 | | { |
| | 5662444 | 178 | | longitude = default; |
| | 5662444 | 179 | | latitude = default; |
| | 5662444 | 180 | | elevation = null; |
| | 5662444 | 181 | | if (vertex.LocalId >= _nextVertexId) |
| | 5 | 182 | | { |
| | 5 | 183 | | return false; |
| | | 184 | | } |
| | | 185 | | |
| | 5662439 | 186 | | this.GetCoordinate(vertex.LocalId, out longitude, out latitude, out elevation); |
| | 5662439 | 187 | | return true; |
| | 5662444 | 188 | | } |
| | | 189 | | |
| | | 190 | | /// <summary> |
| | | 191 | | /// Adds a new edge and returns its id. |
| | | 192 | | /// </summary> |
| | | 193 | | /// <param name="vertex1">The first vertex.</param> |
| | | 194 | | /// <param name="vertex2">The second vertex.</param> |
| | | 195 | | /// <param name="shape">The shape."</param> |
| | | 196 | | /// <param name="attributes">The attributes."</param> |
| | | 197 | | /// <param name="edgeId">The edge id if this edge is a part of another tile.</param> |
| | | 198 | | /// <param name="edgeTypeId">The edge type id, if any.</param> |
| | | 199 | | /// <param name="length">The length in centimeters.</param> |
| | | 200 | | /// <param name="globalEdgeId">The global edge id, if any.</param> |
| | | 201 | | /// <returns>The new edge id.</returns> |
| | | 202 | | public EdgeId AddEdge(VertexId vertex1, VertexId vertex2, |
| | | 203 | | IEnumerable<(double longitude, double latitude, float? e)>? shape = null, |
| | | 204 | | IEnumerable<(string key, string value)>? attributes = null, EdgeId? edgeId = null, uint? edgeTypeId = null, |
| | | 205 | | uint? length = null, GlobalEdgeId? globalEdgeId = null) |
| | 65349 | 206 | | { |
| | | 207 | | // Edge set changed → cached MaxLonDiff/MaxLatDiff are now stale. |
| | 65349 | 208 | | this.InvalidateDiffs(); |
| | | 209 | | |
| | 65349 | 210 | | if (vertex2.TileId != _tileId) |
| | 4526 | 211 | | { |
| | | 212 | | // this edge crosses tiles boundaries, it need special treatment and a stable id. |
| | | 213 | | // because the edge originates in this tile, this tile is responsible for generating the id. |
| | 4526 | 214 | | if (edgeId != null) throw new ArgumentException( |
| | 0 | 215 | | "The edge id shouldn't be a given, it should be generated by the originating tile.", |
| | 0 | 216 | | nameof(edgeId)); |
| | 4526 | 217 | | if (vertex1.TileId != _tileId) throw new ArgumentException("None of the two vertices in this edge are in thi |
| | 0 | 218 | | nameof(vertex1)); |
| | | 219 | | |
| | | 220 | | // generate a new cross tile id and store pointer to edge. |
| | 4526 | 221 | | edgeId = EdgeId.CrossEdgeId(_tileId, _nextCrossTileId); |
| | 4526 | 222 | | ArrayBaseExtensions.EnsureMinimumSize(ref _crossEdgePointers, _nextCrossTileId + 1); |
| | 4526 | 223 | | _crossEdgePointers[_nextCrossTileId] = _nextEdgeId; |
| | 4526 | 224 | | _nextCrossTileId++; |
| | 4526 | 225 | | } |
| | 60823 | 226 | | else if (vertex1.TileId != _tileId) |
| | 4525 | 227 | | { |
| | | 228 | | // this edge crosses tiles boundaries, it need special treatment and a stable id. |
| | | 229 | | // because the edge originates in another tile it should already have an id. |
| | 4525 | 230 | | if (edgeId == null) throw new ArgumentException( |
| | 0 | 231 | | "Cannot add an edge that doesn't start in this tile without a proper edge id.", |
| | 0 | 232 | | nameof(edgeId)); |
| | 4525 | 233 | | if (edgeId.Value.TileId != vertex1.TileId) throw new ArgumentException("The edge id doesn't match the tile i |
| | 0 | 234 | | nameof(edgeId)); |
| | 4525 | 235 | | } |
| | | 236 | | else |
| | 56298 | 237 | | { |
| | | 238 | | // this edge starts in this tile, it get an id from this tile. |
| | 56298 | 239 | | edgeId = new EdgeId(_tileId, _nextEdgeId); |
| | 56298 | 240 | | } |
| | | 241 | | |
| | | 242 | | // write the edge data. |
| | 65349 | 243 | | var newEdgePointer = _nextEdgeId; |
| | 65349 | 244 | | var size = EncodeVertex(ref _edges, _tileId, _nextEdgeId, vertex1); |
| | 65349 | 245 | | _nextEdgeId += size; |
| | 65349 | 246 | | size = EncodeVertex(ref _edges, _tileId, _nextEdgeId, vertex2); |
| | 65349 | 247 | | _nextEdgeId += size; |
| | | 248 | | |
| | | 249 | | // get previous pointers if vertex already has edges |
| | | 250 | | // set the new pointers. |
| | 65349 | 251 | | uint? v1p = null; |
| | 65349 | 252 | | if (vertex1.TileId == _tileId) |
| | 60824 | 253 | | { |
| | 60824 | 254 | | v1p = _pointers[vertex1.LocalId].DecodeNullableData(); |
| | 60824 | 255 | | _pointers[vertex1.LocalId] = newEdgePointer.EncodeToNullableData(); |
| | 60824 | 256 | | } |
| | | 257 | | |
| | 65349 | 258 | | uint? v2p = null; |
| | 65349 | 259 | | if (vertex2.TileId == _tileId) |
| | 60823 | 260 | | { |
| | 60823 | 261 | | v2p = _pointers[vertex2.LocalId].DecodeNullableData(); |
| | 60823 | 262 | | _pointers[vertex2.LocalId] = newEdgePointer.EncodeToNullableData(); |
| | 60823 | 263 | | } |
| | | 264 | | |
| | | 265 | | // set next pointers. |
| | 65349 | 266 | | size = EncodePointer(ref _edges, _nextEdgeId, v1p); |
| | 65349 | 267 | | _nextEdgeId += size; |
| | 65349 | 268 | | size = EncodePointer(ref _edges, _nextEdgeId, v2p); |
| | 65349 | 269 | | _nextEdgeId += size; |
| | | 270 | | |
| | | 271 | | // write edge id explicitly if not in this edge. |
| | 65349 | 272 | | if (vertex1.TileId != vertex2.TileId) |
| | 9051 | 273 | | { |
| | | 274 | | // this data will only be there for edges crossing tile boundaries. |
| | 9051 | 275 | | _nextEdgeId += (uint)_edges.SetDynamicUInt32(_nextEdgeId, |
| | 9051 | 276 | | edgeId.Value.LocalId - EdgeId.MinCrossId); |
| | 9051 | 277 | | } |
| | | 278 | | |
| | | 279 | | // write edge profile id. |
| | 65349 | 280 | | _nextEdgeId += SetDynamicUIn32Nullable(ref _edges, _nextEdgeId, edgeTypeId); |
| | | 281 | | |
| | | 282 | | // write length. |
| | 65349 | 283 | | _nextEdgeId += SetDynamicUIn32Nullable(ref _edges, _nextEdgeId, length); |
| | | 284 | | |
| | | 285 | | // set tail and head order. |
| | 65349 | 286 | | _edges.SetTailHeadOrder(_nextEdgeId, null, null); |
| | 65349 | 287 | | _nextEdgeId++; |
| | | 288 | | |
| | | 289 | | // take care of shape if any. |
| | 65349 | 290 | | uint? shapePointer = null; |
| | 65349 | 291 | | if (shape != null) |
| | 56264 | 292 | | { |
| | 56264 | 293 | | shapePointer = this.SetShape(shape); |
| | 56264 | 294 | | } |
| | | 295 | | |
| | 65349 | 296 | | size = EncodePointer(ref _edges, _nextEdgeId, shapePointer); |
| | 65349 | 297 | | _nextEdgeId += size; |
| | | 298 | | |
| | | 299 | | // take care of attributes if any. |
| | 65349 | 300 | | uint? attributesPointer = null; |
| | 65349 | 301 | | if (attributes != null || globalEdgeId != null) |
| | 59925 | 302 | | { |
| | 59925 | 303 | | attributesPointer = this.SetAttributes(attributes ?? [], globalEdgeId); |
| | 59925 | 304 | | } |
| | | 305 | | |
| | 65349 | 306 | | size = EncodePointer(ref _edges, _nextEdgeId, attributesPointer); |
| | 65349 | 307 | | _nextEdgeId += size; |
| | | 308 | | |
| | 65349 | 309 | | return edgeId.Value; |
| | 65349 | 310 | | } |
| | | 311 | | |
| | | 312 | | private HashSet<EdgeId>? _deletedEdges; |
| | | 313 | | |
| | | 314 | | /// <summary> |
| | | 315 | | /// Marks the given edge as deleted. |
| | | 316 | | /// </summary> |
| | | 317 | | /// <param name="edge">The edge to delete.</param> |
| | | 318 | | internal void DeleteEdge(EdgeId edge) |
| | 10 | 319 | | { |
| | 10 | 320 | | _deletedEdges ??= []; |
| | 10 | 321 | | _deletedEdges.Add(edge); |
| | 10 | 322 | | this.InvalidateDiffs(); |
| | 10 | 323 | | } |
| | | 324 | | |
| | | 325 | | /// <summary> |
| | | 326 | | /// Returns true if the edge is deleted. |
| | | 327 | | /// </summary> |
| | | 328 | | /// <param name="edge">The edge.</param> |
| | | 329 | | /// <returns>True if the edge was deleted.</returns> |
| | | 330 | | internal bool IsEdgeDeleted(EdgeId edge) |
| | 6568177 | 331 | | { |
| | 13136348 | 332 | | if (_deletedEdges == null) return false; |
| | | 333 | | |
| | 6 | 334 | | return _deletedEdges.Contains(edge); |
| | 6568177 | 335 | | } |
| | | 336 | | |
| | | 337 | | /// <summary> |
| | | 338 | | /// Returns true if there are deleted edges. |
| | | 339 | | /// </summary> |
| | 738 | 340 | | internal bool HasDeletedEdges => _deletedEdges != null; |
| | | 341 | | |
| | | 342 | | /// <summary> |
| | | 343 | | /// Removes all the deleted edges. |
| | | 344 | | /// </summary> |
| | | 345 | | /// <remarks>This changes all the edges if all edges written after a deleted edge.</remarks> |
| | | 346 | | internal void RemoveDeletedEdges() |
| | 10 | 347 | | { |
| | 10 | 348 | | if (_deletedEdges == null) return; |
| | 10 | 349 | | this.InvalidateDiffs(); |
| | | 350 | | |
| | | 351 | | // reset vertex pointers. |
| | 340 | 352 | | for (var i = 0; i < _pointers.Length; i++) |
| | 160 | 353 | | { |
| | 160 | 354 | | _pointers[i] = 0; |
| | 160 | 355 | | } |
| | | 356 | | |
| | | 357 | | // redo edges, skipping deleted edges. |
| | 10 | 358 | | var nextEdgeId = _nextEdgeId; |
| | 10 | 359 | | var p = 0U; |
| | 10 | 360 | | var newP = 0U; |
| | 24 | 361 | | while (p < nextEdgeId) |
| | 14 | 362 | | { |
| | | 363 | | // read edge data. |
| | 14 | 364 | | var currentEdgeId = p; |
| | 14 | 365 | | p += this.DecodeVertex(p, out var local1Id, out var tile1Id); |
| | 14 | 366 | | var vertex1 = new VertexId(tile1Id, local1Id); |
| | 14 | 367 | | p += this.DecodeVertex(p, out var local2Id, out var tile2Id); |
| | 14 | 368 | | var vertex2 = new VertexId(tile2Id, local2Id); |
| | 14 | 369 | | p += this.DecodePointer(p, out _); |
| | 14 | 370 | | p += this.DecodePointer(p, out _); |
| | 14 | 371 | | uint? crossEdgeId = null; |
| | 14 | 372 | | if (tile1Id != tile2Id) |
| | 4 | 373 | | { |
| | 4 | 374 | | p += _edges.GetDynamicUInt32(p, out var c); |
| | 4 | 375 | | crossEdgeId = c; |
| | 4 | 376 | | } |
| | | 377 | | |
| | 14 | 378 | | p += _edges.GetDynamicUInt32Nullable(p, out var edgeTypeId); |
| | 14 | 379 | | p += _edges.GetDynamicUInt32Nullable(p, out var length); |
| | 14 | 380 | | var tailHeadOrder = _edges[p]; |
| | 14 | 381 | | p++; |
| | 14 | 382 | | p += this.DecodePointer(p, out var shapePointer); |
| | 14 | 383 | | p += this.DecodePointer(p, out var attributePointer); |
| | | 384 | | |
| | | 385 | | // check if edge was deleted. |
| | 20 | 386 | | if (_deletedEdges.Contains(new EdgeId(_tileId, currentEdgeId))) continue; |
| | 8 | 387 | | if (crossEdgeId.HasValue) |
| | 4 | 388 | | { |
| | 8 | 389 | | if (_deletedEdges.Contains(EdgeId.CrossEdgeId(vertex1.TileId, crossEdgeId.Value))) continue; |
| | 0 | 390 | | } |
| | | 391 | | |
| | | 392 | | // no need to overwrite identical data. |
| | 4 | 393 | | if (p == newP) continue; |
| | | 394 | | |
| | | 395 | | // write edge data again. |
| | 4 | 396 | | var newEdgePointer = newP; |
| | 4 | 397 | | newP += EncodeVertex(ref _edges, _tileId, newP, vertex1); |
| | 4 | 398 | | newP += EncodeVertex(ref _edges, _tileId, newP, vertex2); |
| | 4 | 399 | | uint? v1p = null; |
| | 4 | 400 | | if (vertex1.TileId == _tileId) |
| | 4 | 401 | | { |
| | 4 | 402 | | v1p = _pointers[vertex1.LocalId].DecodeNullableData(); |
| | 4 | 403 | | _pointers[vertex1.LocalId] = newEdgePointer.EncodeToNullableData(); |
| | 4 | 404 | | } |
| | | 405 | | |
| | 4 | 406 | | uint? v2P = null; |
| | 4 | 407 | | if (vertex2.TileId == _tileId) |
| | 4 | 408 | | { |
| | 4 | 409 | | v2P = _pointers[vertex2.LocalId].DecodeNullableData(); |
| | 4 | 410 | | _pointers[vertex2.LocalId] = newEdgePointer.EncodeToNullableData(); |
| | 4 | 411 | | } |
| | | 412 | | |
| | 4 | 413 | | newP += EncodePointer(ref _edges, newP, v1p); |
| | 4 | 414 | | newP += EncodePointer(ref _edges, newP, v2P); |
| | 4 | 415 | | if (crossEdgeId != null) |
| | 0 | 416 | | { |
| | 0 | 417 | | newP += (uint)_edges.SetDynamicUInt32(newP, crossEdgeId.Value); |
| | 0 | 418 | | if (vertex1.TileId == _tileId) |
| | 0 | 419 | | { |
| | 0 | 420 | | _crossEdgePointers[crossEdgeId.Value] = newEdgePointer; |
| | 0 | 421 | | } |
| | 0 | 422 | | } |
| | | 423 | | |
| | 4 | 424 | | newP += _edges.SetDynamicUInt32Nullable(newP, edgeTypeId); |
| | 4 | 425 | | newP += _edges.SetDynamicUInt32Nullable(newP, length); |
| | 4 | 426 | | _edges[newP] = tailHeadOrder; |
| | 4 | 427 | | newP++; |
| | 4 | 428 | | newP += EncodePointer(ref _edges, newP, shapePointer); |
| | 4 | 429 | | newP += EncodePointer(ref _edges, newP, attributePointer); |
| | 4 | 430 | | } |
| | | 431 | | |
| | 10 | 432 | | _nextEdgeId = newP; |
| | 10 | 433 | | _deletedEdges = null; |
| | 10 | 434 | | } |
| | | 435 | | |
| | | 436 | | internal NetworkTile CloneForEdgeTypeMap( |
| | | 437 | | (Guid id, Func<IEnumerable<(string key, string value)>, uint> func) edgeTypeMap) |
| | 6 | 438 | | { |
| | 6 | 439 | | var edges = new byte[_edges.Length]; |
| | 6 | 440 | | var pointers = new uint[_pointers.Length]; |
| | 6 | 441 | | var crossEdgePointers = new uint[_crossEdgePointers.Length]; |
| | 6 | 442 | | var nextEdgeId = _nextEdgeId; |
| | 6 | 443 | | var p = 0U; |
| | 6 | 444 | | var newP = 0U; |
| | 16 | 445 | | while (p < nextEdgeId) |
| | 10 | 446 | | { |
| | | 447 | | // read edge data. |
| | 10 | 448 | | p += this.DecodeVertex(p, out var local1Id, out var tile1Id); |
| | 10 | 449 | | var vertex1 = new VertexId(tile1Id, local1Id); |
| | 10 | 450 | | p += this.DecodeVertex(p, out var local2Id, out var tile2Id); |
| | 10 | 451 | | var vertex2 = new VertexId(tile2Id, local2Id); |
| | 10 | 452 | | p += this.DecodePointer(p, out _); |
| | 10 | 453 | | p += this.DecodePointer(p, out _); |
| | 10 | 454 | | uint? crossEdgeId = null; |
| | 10 | 455 | | if (tile1Id != tile2Id) |
| | 0 | 456 | | { |
| | 0 | 457 | | p += (uint)_edges.GetDynamicUInt32(p, out var c); |
| | 0 | 458 | | crossEdgeId = c; |
| | 0 | 459 | | } |
| | | 460 | | |
| | 10 | 461 | | p += _edges.GetDynamicUInt32Nullable(p, out var _); |
| | 10 | 462 | | p += _edges.GetDynamicUInt32Nullable(p, out var length); |
| | 10 | 463 | | var tailHeadOrder = _edges[p]; |
| | 10 | 464 | | p++; |
| | 10 | 465 | | p += this.DecodePointer(p, out var shapePointer); |
| | 10 | 466 | | p += this.DecodePointer(p, out var attributePointer); |
| | | 467 | | |
| | | 468 | | // generate new edge type id. |
| | 10 | 469 | | var newEdgeTypeId = edgeTypeMap.func(this.GetAttributes(attributePointer)); |
| | | 470 | | |
| | | 471 | | // write edge data again. |
| | 10 | 472 | | var newEdgePointer = newP; |
| | 10 | 473 | | newP += EncodeVertex(ref edges, _tileId, newP, vertex1); |
| | 10 | 474 | | newP += EncodeVertex(ref edges, _tileId, newP, vertex2); |
| | 10 | 475 | | uint? v1p = null; |
| | 10 | 476 | | if (vertex1.TileId == _tileId) |
| | 10 | 477 | | { |
| | 10 | 478 | | v1p = pointers[vertex1.LocalId].DecodeNullableData(); |
| | 10 | 479 | | pointers[vertex1.LocalId] = newEdgePointer.EncodeToNullableData(); |
| | 10 | 480 | | } |
| | | 481 | | |
| | 10 | 482 | | uint? v2p = null; |
| | 10 | 483 | | if (vertex2.TileId == _tileId) |
| | 10 | 484 | | { |
| | 10 | 485 | | v2p = pointers[vertex2.LocalId].DecodeNullableData(); |
| | 10 | 486 | | pointers[vertex2.LocalId] = newEdgePointer.EncodeToNullableData(); |
| | 10 | 487 | | } |
| | | 488 | | |
| | 10 | 489 | | newP += EncodePointer(ref edges, newP, v1p); |
| | 10 | 490 | | newP += EncodePointer(ref edges, newP, v2p); |
| | 10 | 491 | | if (crossEdgeId != null) |
| | 0 | 492 | | { |
| | 0 | 493 | | newP += edges.SetDynamicUInt32(newP, crossEdgeId.Value); |
| | 0 | 494 | | if (vertex1.TileId == _tileId) |
| | 0 | 495 | | { |
| | 0 | 496 | | crossEdgePointers[crossEdgeId.Value] = newEdgePointer; |
| | 0 | 497 | | } |
| | 0 | 498 | | } |
| | | 499 | | |
| | 10 | 500 | | newP += edges.SetDynamicUInt32Nullable(newP, newEdgeTypeId); |
| | 10 | 501 | | newP += edges.SetDynamicUInt32Nullable(newP, length); |
| | 10 | 502 | | edges[newP] = tailHeadOrder; |
| | 10 | 503 | | newP++; |
| | 10 | 504 | | newP += EncodePointer(ref edges, newP, shapePointer); |
| | 10 | 505 | | newP += EncodePointer(ref edges, newP, attributePointer); |
| | 10 | 506 | | } |
| | | 507 | | |
| | 6 | 508 | | return new NetworkTile(_zoom, _tileId, edgeTypeMap.id, _nextCrossTileId, pointers, edges, crossEdgePointers, |
| | 6 | 509 | | _coordinates, |
| | 6 | 510 | | _shapes, _attributes, _strings, _turnCosts, _nextVertexId, _nextEdgeId, |
| | 6 | 511 | | _nextAttributePointer, _nextShapePointer, _nextStringId); |
| | 6 | 512 | | } |
| | | 513 | | |
| | | 514 | | /// <summary> |
| | | 515 | | /// Shrinks every appendable buffer to what it actually holds. |
| | | 516 | | /// </summary> |
| | | 517 | | /// <remarks> |
| | | 518 | | /// Growing by an eighth leaves slack in arrays resident for the process's life; hot measured −2.4% |
| | | 519 | | /// without this. Caller must hold this tile's write lock: it replaces the arrays. |
| | | 520 | | /// </remarks> |
| | | 521 | | internal void Trim() |
| | 1928 | 522 | | { |
| | 3856 | 523 | | if (_pointers.Length > _nextVertexId) Array.Resize(ref _pointers, (int)_nextVertexId); |
| | 3829 | 524 | | if (_edges.Length > _nextEdgeId) Array.Resize(ref _edges, (int)_nextEdgeId); |
| | 1928 | 525 | | if (_crossEdgePointers.Length > _nextCrossTileId) |
| | 629 | 526 | | { |
| | 629 | 527 | | Array.Resize(ref _crossEdgePointers, (int)_nextCrossTileId); |
| | 629 | 528 | | } |
| | | 529 | | |
| | 1928 | 530 | | this.TrimAttributes(); |
| | 1928 | 531 | | this.TrimShapes(); |
| | 1928 | 532 | | this.TrimTurnCosts(); |
| | 1928 | 533 | | } |
| | | 534 | | |
| | | 535 | | internal uint VertexEdgePointer(uint vertex) |
| | 1141968 | 536 | | { |
| | 1141968 | 537 | | return _pointers[vertex]; |
| | 1141968 | 538 | | } |
| | | 539 | | |
| | | 540 | | internal static byte EncodeVertex(ref byte[] edges, uint localTileId, uint location, VertexId vertexId) |
| | 130726 | 541 | | { |
| | 130726 | 542 | | if (vertexId.TileId == localTileId) |
| | 121675 | 543 | | { |
| | | 544 | | // same tile, only store local id. |
| | 121675 | 545 | | EnsureCapacity(ref edges, location + 6L, DefaultSizeIncrease); |
| | | 546 | | |
| | 121675 | 547 | | return edges.SetDynamicUInt32(location, vertexId.LocalId); |
| | | 548 | | } |
| | | 549 | | |
| | | 550 | | // other tile, store full id. |
| | 9051 | 551 | | EnsureCapacity(ref edges, location + 11L, DefaultSizeIncrease); |
| | | 552 | | |
| | 9051 | 553 | | var encodedId = vertexId.Encode(); |
| | 9051 | 554 | | return edges.SetDynamicUInt64(location, encodedId); |
| | 130726 | 555 | | } |
| | | 556 | | |
| | | 557 | | internal byte DecodeVertex(uint location, out uint localId, out uint tileId) |
| | 13156584 | 558 | | { |
| | 13156584 | 559 | | var size = _edges.GetDynamicUInt64(location, out var encodedId); |
| | 13156584 | 560 | | if (encodedId < uint.MaxValue) |
| | 13029299 | 561 | | { |
| | 13029299 | 562 | | localId = (uint)encodedId; |
| | 13029299 | 563 | | tileId = _tileId; |
| | 13029299 | 564 | | return size; |
| | | 565 | | } |
| | | 566 | | |
| | 127285 | 567 | | VertexId.Decode(encodedId, out tileId, out localId); |
| | 127285 | 568 | | return size; |
| | 13156584 | 569 | | } |
| | | 570 | | |
| | | 571 | | internal byte DecodeEdgeCrossId(uint location, out uint edgeCrossId) |
| | 125802 | 572 | | { |
| | 125802 | 573 | | var s = _edges.GetDynamicUInt32(location, out var c); |
| | 125802 | 574 | | edgeCrossId = EdgeId.MinCrossId + c; |
| | 125802 | 575 | | return s; |
| | 125802 | 576 | | } |
| | | 577 | | |
| | | 578 | | internal uint GetEdgeCrossPointer(uint edgeCrossId) |
| | 52605 | 579 | | { |
| | 52605 | 580 | | return _crossEdgePointers[edgeCrossId]; |
| | 52605 | 581 | | } |
| | | 582 | | |
| | | 583 | | internal static byte EncodePointer(ref byte[] edges, uint location, uint? pointer) |
| | 261452 | 584 | | { |
| | | 585 | | // TODO: save the diff instead of the full pointer. |
| | 261452 | 586 | | EnsureCapacity(ref edges, location + 6L, DefaultSizeIncrease); |
| | | 587 | | |
| | 261452 | 588 | | return edges.SetDynamicUInt32(location, |
| | 261452 | 589 | | pointer.EncodeAsNullableData()); |
| | 261452 | 590 | | } |
| | | 591 | | |
| | | 592 | | internal byte DecodePointer(uint location, out uint? pointer) |
| | 14512006 | 593 | | { |
| | 14512006 | 594 | | var size = _edges.GetDynamicUInt32(location, out var data); |
| | 14512006 | 595 | | pointer = data.DecodeNullableData(); |
| | 14512006 | 596 | | return size; |
| | 14512006 | 597 | | } |
| | | 598 | | |
| | | 599 | | internal static byte SetDynamicUIn32Nullable(ref byte[] edges, uint pointer, uint? data) |
| | 130698 | 600 | | { |
| | 130698 | 601 | | EnsureCapacity(ref edges, pointer + 6L, DefaultSizeIncrease); |
| | | 602 | | |
| | 130698 | 603 | | return edges.SetDynamicUInt32Nullable(pointer, data); |
| | 130698 | 604 | | } |
| | | 605 | | |
| | | 606 | | internal void GetTailHeadOrder(uint location, ref byte? tail, ref byte? head) |
| | 6578267 | 607 | | { |
| | 6578267 | 608 | | _edges.GetTailHeadOrder(location, ref tail, ref head); |
| | 6578267 | 609 | | } |
| | | 610 | | |
| | | 611 | | internal byte DecodeEdgePointerId(uint location, out uint? edgeProfileId) |
| | 13156534 | 612 | | { |
| | 13156534 | 613 | | return _edges.GetDynamicUInt32Nullable(location, out edgeProfileId); |
| | 13156534 | 614 | | } |
| | | 615 | | |
| | | 616 | | private void WriteEdgesAndVerticesTo(Stream stream) |
| | 8 | 617 | | { |
| | | 618 | | // write vertex pointers. |
| | 8 | 619 | | stream.WriteVarUInt32(_nextVertexId); |
| | 42 | 620 | | for (var i = 0; i < _nextVertexId; i++) |
| | 13 | 621 | | { |
| | 13 | 622 | | stream.WriteVarUInt32(_pointers[i]); |
| | 13 | 623 | | } |
| | | 624 | | |
| | | 625 | | // write edges. |
| | 8 | 626 | | stream.WriteVarUInt32(_nextEdgeId); |
| | 106 | 627 | | for (var i = 0; i < _nextEdgeId; i++) |
| | 45 | 628 | | { |
| | 45 | 629 | | stream.WriteByte(_edges[i]); |
| | 45 | 630 | | } |
| | | 631 | | |
| | | 632 | | // write cross edge pointers. |
| | 8 | 633 | | stream.WriteVarUInt32(_nextCrossTileId); |
| | 16 | 634 | | for (var i = 0; i < _nextCrossTileId; i++) |
| | 0 | 635 | | { |
| | 0 | 636 | | stream.WriteVarUInt32(_crossEdgePointers[i]); |
| | 0 | 637 | | } |
| | 8 | 638 | | } |
| | | 639 | | |
| | | 640 | | private void ReadEdgesAndVerticesFrom(Stream stream) |
| | 8 | 641 | | { |
| | | 642 | | // read vertex pointers. |
| | 8 | 643 | | _nextVertexId = stream.ReadVarUInt32(); |
| | 8 | 644 | | Array.Resize(ref _pointers, (int)_nextVertexId); |
| | 42 | 645 | | for (var i = 0; i < _nextVertexId; i++) |
| | 13 | 646 | | { |
| | 13 | 647 | | _pointers[i] = stream.ReadVarUInt32(); |
| | 13 | 648 | | } |
| | | 649 | | |
| | | 650 | | // read edges. |
| | 8 | 651 | | _nextEdgeId = stream.ReadVarUInt32(); |
| | 8 | 652 | | Array.Resize(ref _edges, (int)_nextEdgeId); |
| | 106 | 653 | | for (var i = 0; i < _nextEdgeId; i++) |
| | 45 | 654 | | { |
| | 45 | 655 | | _edges[i] = (byte)stream.ReadByte(); |
| | 45 | 656 | | } |
| | | 657 | | |
| | | 658 | | // read cross tile edge pointers. |
| | 8 | 659 | | _nextCrossTileId = stream.ReadVarUInt32(); |
| | 8 | 660 | | Array.Resize(ref _crossEdgePointers, (int)_nextCrossTileId); |
| | 16 | 661 | | for (var i = 0; i < _nextCrossTileId; i++) |
| | 0 | 662 | | { |
| | 0 | 663 | | _crossEdgePointers[i] = stream.ReadVarUInt32(); |
| | 0 | 664 | | } |
| | 8 | 665 | | } |
| | | 666 | | |
| | | 667 | | private void ReadEdgesAndVerticesFrom(byte[] data, ref int offset) |
| | 0 | 668 | | { |
| | 0 | 669 | | _nextVertexId = BitCoderBuffer.GetVarUInt32(data, ref offset); |
| | 0 | 670 | | Array.Resize(ref _pointers, (int)_nextVertexId); |
| | 0 | 671 | | for (var i = 0; i < _nextVertexId; i++) |
| | 0 | 672 | | { |
| | 0 | 673 | | _pointers[i] = BitCoderBuffer.GetVarUInt32(data, ref offset); |
| | 0 | 674 | | } |
| | | 675 | | |
| | 0 | 676 | | _nextEdgeId = BitCoderBuffer.GetVarUInt32(data, ref offset); |
| | 0 | 677 | | Array.Resize(ref _edges, (int)_nextEdgeId); |
| | 0 | 678 | | Buffer.BlockCopy(data, offset, _edges, 0, (int)_nextEdgeId); |
| | 0 | 679 | | offset += (int)_nextEdgeId; |
| | | 680 | | |
| | 0 | 681 | | _nextCrossTileId = BitCoderBuffer.GetVarUInt32(data, ref offset); |
| | 0 | 682 | | Array.Resize(ref _crossEdgePointers, (int)_nextCrossTileId); |
| | 0 | 683 | | for (var i = 0; i < _nextCrossTileId; i++) |
| | 0 | 684 | | { |
| | 0 | 685 | | _crossEdgePointers[i] = BitCoderBuffer.GetVarUInt32(data, ref offset); |
| | 0 | 686 | | } |
| | 0 | 687 | | } |
| | | 688 | | |
| | | 689 | | private void WriteEdgesAndVerticesTo(byte[] data, ref int offset) |
| | 0 | 690 | | { |
| | 0 | 691 | | BitCoderBuffer.SetVarUInt32(data, ref offset, _nextVertexId); |
| | 0 | 692 | | for (var i = 0; i < _nextVertexId; i++) |
| | 0 | 693 | | { |
| | 0 | 694 | | BitCoderBuffer.SetVarUInt32(data, ref offset, _pointers[i]); |
| | 0 | 695 | | } |
| | | 696 | | |
| | 0 | 697 | | BitCoderBuffer.SetVarUInt32(data, ref offset, _nextEdgeId); |
| | 0 | 698 | | Buffer.BlockCopy(_edges, 0, data, offset, (int)_nextEdgeId); |
| | 0 | 699 | | offset += (int)_nextEdgeId; |
| | | 700 | | |
| | 0 | 701 | | BitCoderBuffer.SetVarUInt32(data, ref offset, _nextCrossTileId); |
| | 0 | 702 | | for (var i = 0; i < _nextCrossTileId; i++) |
| | 0 | 703 | | { |
| | 0 | 704 | | BitCoderBuffer.SetVarUInt32(data, ref offset, _crossEdgePointers[i]); |
| | 0 | 705 | | } |
| | 0 | 706 | | } |
| | | 707 | | } |