| | | 1 | | /* |
| | | 2 | | * Licensed to SharpSoftware under one or more contributor |
| | | 3 | | * license agreements. See the NOTICE file distributed with this work for |
| | | 4 | | * additional information regarding copyright ownership. |
| | | 5 | | * |
| | | 6 | | * SharpSoftware licenses this file to you under the Apache License, |
| | | 7 | | * Version 2.0 (the "License"); you may not use this file except in |
| | | 8 | | * compliance with the License. You may obtain a copy of the License at |
| | | 9 | | * |
| | | 10 | | * http://www.apache.org/licenses/LICENSE-2.0 |
| | | 11 | | * |
| | | 12 | | * Unless required by applicable law or agreed to in writing, software |
| | | 13 | | * distributed under the License is distributed on an "AS IS" BASIS, |
| | | 14 | | * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
| | | 15 | | * See the License for the specific language governing permissions and |
| | | 16 | | * limitations under the License. |
| | | 17 | | */ |
| | | 18 | | |
| | | 19 | | using System.Collections.Generic; |
| | | 20 | | |
| | | 21 | | namespace Itinero.IO.Osm.Collections; |
| | | 22 | | |
| | | 23 | | /// <summary> |
| | | 24 | | /// A unique id map, only vertex per id. |
| | | 25 | | /// </summary> |
| | | 26 | | public class UniqueIdMap<T> |
| | | 27 | | where T : struct |
| | | 28 | | { |
| | | 29 | | private readonly Dictionary<long, Block> _blocks; |
| | | 30 | | private readonly int _blockSize; |
| | | 31 | | private static T _defaultValue; |
| | | 32 | | |
| | | 33 | | /// <summary> |
| | | 34 | | /// Creates a new id map. |
| | | 35 | | /// </summary> |
| | 0 | 36 | | public UniqueIdMap(T defaultValue, int blockSize = 32) |
| | 0 | 37 | | { |
| | 0 | 38 | | _blocks = new Dictionary<long, Block>(); |
| | 0 | 39 | | _blockSize = blockSize; |
| | 0 | 40 | | _defaultValue = defaultValue; |
| | 0 | 41 | | } |
| | | 42 | | |
| | | 43 | | /// <summary> |
| | | 44 | | /// Sets a tile id. |
| | | 45 | | /// </summary> |
| | | 46 | | public void Set(long id, T vertex) |
| | 0 | 47 | | { |
| | 0 | 48 | | var blockIdx = id / _blockSize; |
| | 0 | 49 | | var offset = id - blockIdx * _blockSize; |
| | | 50 | | |
| | 0 | 51 | | if (!_blocks.TryGetValue(blockIdx, out var block)) |
| | 0 | 52 | | { |
| | 0 | 53 | | block = new Block |
| | 0 | 54 | | { |
| | 0 | 55 | | Start = (uint)offset, |
| | 0 | 56 | | End = (uint)offset, |
| | 0 | 57 | | Data = new T[] { vertex } |
| | 0 | 58 | | }; |
| | 0 | 59 | | _blocks[blockIdx] = block; |
| | 0 | 60 | | } |
| | | 61 | | else |
| | 0 | 62 | | { |
| | 0 | 63 | | block.Set(offset, vertex); |
| | 0 | 64 | | _blocks[blockIdx] = block; |
| | 0 | 65 | | } |
| | 0 | 66 | | } |
| | | 67 | | |
| | | 68 | | /// <summary> |
| | | 69 | | /// Gets or sets the tile id for the given id. |
| | | 70 | | /// </summary> |
| | | 71 | | public T this[long id] |
| | | 72 | | { |
| | 0 | 73 | | get => this.Get(id); |
| | 0 | 74 | | set => this.Set(id, value); |
| | | 75 | | } |
| | | 76 | | |
| | | 77 | | /// <summary> |
| | | 78 | | /// Gets a tile id. |
| | | 79 | | /// </summary> |
| | | 80 | | public T Get(long id) |
| | 0 | 81 | | { |
| | 0 | 82 | | var blockIdx = id / _blockSize; |
| | 0 | 83 | | var offset = id - blockIdx * _blockSize; |
| | | 84 | | |
| | 0 | 85 | | if (!_blocks.TryGetValue(blockIdx, out var block)) |
| | 0 | 86 | | { |
| | 0 | 87 | | return _defaultValue; |
| | | 88 | | } |
| | | 89 | | |
| | 0 | 90 | | return block.Get(offset); |
| | 0 | 91 | | } |
| | | 92 | | |
| | | 93 | | /// <summary> |
| | | 94 | | /// An enumerable with the non-default indices in this map. |
| | | 95 | | /// </summary> |
| | 0 | 96 | | public IEnumerable<long> NonDefaultIndices => throw new System.NotImplementedException(); |
| | | 97 | | |
| | | 98 | | private struct Block |
| | | 99 | | { |
| | 0 | 100 | | public uint Start { get; set; } |
| | | 101 | | |
| | 0 | 102 | | public uint End { get; set; } |
| | | 103 | | |
| | 0 | 104 | | public T[] Data { get; set; } |
| | | 105 | | |
| | | 106 | | public T Get(long offset) |
| | 0 | 107 | | { |
| | 0 | 108 | | if (this.Start > offset) |
| | 0 | 109 | | { |
| | 0 | 110 | | return _defaultValue; |
| | | 111 | | } |
| | 0 | 112 | | else if (offset > this.End) |
| | 0 | 113 | | { |
| | 0 | 114 | | return _defaultValue; |
| | | 115 | | } |
| | | 116 | | |
| | 0 | 117 | | return this.Data[offset - this.Start]; |
| | 0 | 118 | | } |
| | | 119 | | |
| | | 120 | | public void Set(long offset, T value) |
| | 0 | 121 | | { |
| | 0 | 122 | | if (this.Start > offset) |
| | 0 | 123 | | { // expand at the beginning. |
| | 0 | 124 | | var newData = new T[this.End - offset + 1]; |
| | 0 | 125 | | this.Data.CopyTo(newData, (int)(this.Start - offset)); |
| | 0 | 126 | | for (var i = 1; i < this.Start - offset; i++) |
| | 0 | 127 | | { |
| | 0 | 128 | | newData[i] = _defaultValue; |
| | 0 | 129 | | } |
| | | 130 | | |
| | 0 | 131 | | this.Data = newData; |
| | 0 | 132 | | this.Start = (uint)offset; |
| | 0 | 133 | | this.Data[0] = value; |
| | 0 | 134 | | } |
| | 0 | 135 | | else if (this.End < offset) |
| | 0 | 136 | | { // expand at the end. |
| | 0 | 137 | | var newData = new T[offset - this.Start + 1]; |
| | 0 | 138 | | this.Data.CopyTo(newData, 0); |
| | 0 | 139 | | for (var i = this.End + 1 - this.Start; i < newData.Length - 1; i++) |
| | 0 | 140 | | { |
| | 0 | 141 | | newData[i] = _defaultValue; |
| | 0 | 142 | | } |
| | | 143 | | |
| | 0 | 144 | | this.Data = newData; |
| | 0 | 145 | | this.End = (uint)offset; |
| | 0 | 146 | | this.Data[offset - this.Start] = value; |
| | 0 | 147 | | } |
| | | 148 | | else |
| | 0 | 149 | | { |
| | 0 | 150 | | this.Data[offset - this.Start] = value; |
| | 0 | 151 | | } |
| | 0 | 152 | | } |
| | | 153 | | } |
| | | 154 | | } |