< Summary

Class:Itinero.IO.Osm.Collections.UnsignedNodeIndex
Assembly:Itinero.IO.Osm
File(s):/home/runner/work/routing2/routing2/src/Itinero.IO.Osm/Collections/UnsignedNodeIndex.cs
Covered lines:0
Uncovered lines:294
Coverable lines:294
Total lines:472
Line coverage:0% (0 of 294)
Covered branches:0
Total branches:94
Branch coverage:0% (0 of 94)
Tag:263_26948838820

Metrics

MethodBranch coverage Cyclomatic complexity Line coverage
.ctor()100%10%
AddId(...)100%10%
long2doubleInt(...)100%10%
doubleInt2long(...)100%10%
SortAndConvertIndex()0%40%
get_Item(...)100%10%
Set(...)100%10%
SetIndex(...)0%20%
TryGetCoreNode(...)0%40%
IsCoreNode(...)0%100%
HasId(...)0%40%
TryGetValue(...)0%40%
TryGetValue(...)0%80%
TryGetValue(...)0%20%
IsCoreNodeAtIndex(...)0%80%
TryGetIndex(...)0%340%
GetId(...)0%60%
GetLatLon(...)0%40%
get_Count()100%10%
EnsureMinimumSize(...)0%40%

File(s)

/home/runner/work/routing2/routing2/src/Itinero.IO.Osm/Collections/UnsignedNodeIndex.cs

#LineLine coverage
 1using System;
 2using System.Collections.Generic;
 3
 4namespace Itinero.IO.Osm.Collections;
 5
 6/// <summary>
 7/// A cache for node coordinates.
 8/// </summary>
 9internal sealed class UnsignedNodeIndex
 10{
 11    // keeps all coordinates in a form [id, lat * 10.000.000, lon * 10.000.000]
 12    // assumes coordinates are added from a sorted source: TODO: make sure that the source read by the routerdb is sorte
 13    private int[] _data;
 14    private int[] _index;
 15
 16    /// <summary>
 17    /// Creates a new node coordinates cache.
 18    /// </summary>
 019    public UnsignedNodeIndex()
 020    {
 021        _index = new int[1024 * 1024];
 022        _data = new int[0];
 023    }
 24
 025    private List<long>? _overflows = null; // overflows is null before sorting.
 026    private long _idx = 0;
 27
 28    /// <summary>
 29    /// Adds a node id to the index.
 30    /// </summary>
 31    public void AddId(long id)
 032    {
 33        int int1, int2;
 034        long2doubleInt(id, out int1, out int2);
 35
 036        EnsureMinimumSize(ref _index, _idx + 2);
 037        _index[(int)(_idx + 0)] = int1;
 038        _index[(int)(_idx + 1)] = int2;
 039        _idx += 2;
 040    }
 41
 42    private static void long2doubleInt(long a, out int a1, out int a2)
 043    {
 44        unchecked
 045        {
 046            a1 = (int)(a & uint.MaxValue);
 047            a2 = (int)(a >> 32);
 048        }
 049    }
 50
 51    private static long doubleInt2long(int a1, int a2)
 052    {
 53        unchecked
 054        {
 055            long b = a2;
 056            b = b << 32;
 057            b = b | (uint)a1;
 058            return b;
 59        }
 060    }
 61
 62    /// <summary>
 63    /// Sorts and converts the index.
 64    /// </summary>
 65    public void SortAndConvertIndex()
 066    {
 067        _overflows = new List<long>();
 068        Array.Resize(ref _index, (int)_idx);
 69
 070        Logging.Logger.Log("NodeIndex", Logging.TraceEventType.Information, "Sorting node id's...");
 071        QuickSort.Sort((i) =>
 072        {
 073            var int1 = _index[(int)(i * 2 + 0)];
 074            var int2 = _index[(int)(i * 2 + 1)];
 075            return doubleInt2long(int1, int2);
 076        },
 077            (i, j) =>
 078            {
 079                var int1 = _index[(int)(i * 2 + 0)];
 080                var int2 = _index[(int)(i * 2 + 1)];
 081                _index[(int)(i * 2 + 0)] = _index[(int)(j * 2 + 0)];
 082                _index[(int)(i * 2 + 1)] = _index[(int)(j * 2 + 1)];
 083                _index[(int)(j * 2 + 0)] = int1;
 084                _index[(int)(j * 2 + 1)] = int2;
 085            }, 0, _index.Length / 2 - 1);
 86
 087        for (long i = 0; i < _index.Length / 2; i++)
 088        {
 089            var int1 = _index[(int)(i * 2 + 0)];
 090            var int2 = _index[(int)(i * 2 + 1)];
 091            var id = doubleInt2long(int1, int2);
 92
 093            while (id >= (long)int.MaxValue * (long)(_overflows.Count + 1))
 094            { // nodes are overflowing again.
 095                _overflows.Add(i);
 096            }
 97
 098            _index[(int)i] = (int)(id - (long)int.MaxValue * (long)_overflows.Count);
 099        }
 100
 0101        Array.Resize(ref _index, _index.Length / 2);
 0102        _idx = _index.Length;
 0103    }
 104
 105    /// <summary>
 106    /// Gets the node id at the given index.
 107    /// </summary>
 108    public long this[long idx]
 109    {
 110        get
 0111        {
 0112            var int1 = _index[(int)(idx * 2 + 0)];
 0113            var int2 = _index[(int)(idx * 2 + 1)];
 0114            return doubleInt2long(int1, int2);
 0115        }
 116    }
 117
 118    /// <summary>
 119    /// Sets a vertex id for the given vertex.
 120    /// </summary>
 121    public void Set(long id, uint vertex)
 0122    {
 0123        var idx = this.TryGetIndex(id);
 124
 0125        EnsureMinimumSize(ref _data, idx * 2 + 2, int.MaxValue);
 0126        _data[(int)(idx * 2 + 0)] = unchecked((int)vertex);
 0127        _data[(int)(idx * 2 + 1)] = int.MinValue;
 0128    }
 129
 130    /// <summary>
 131    /// Sets the coordinate for the given index.
 132    /// </summary>
 133    public void SetIndex(long idx, float latitude, float longitude)
 0134    {
 0135        var lat = (int)(latitude * 10000000);
 0136        var lon = (int)(longitude * 10000000);
 137
 0138        EnsureMinimumSize(ref _data, idx * 2 + 2, int.MaxValue);
 139
 0140        if (_data[(int)(idx * 2 + 1)] == int.MinValue)
 0141        {
 142            // this is already a core vertex, no need to overwrite this more valuable data.
 0143            return;
 144        }
 145
 0146        _data[(int)(idx * 2 + 0)] = lat;
 0147        _data[(int)(idx * 2 + 1)] = lon;
 0148    }
 149
 150    /// <summary>
 151    /// Tries to get a core node and it's matching vertex.
 152    /// </summary>
 153    public bool TryGetCoreNode(long id, out uint vertex)
 0154    {
 0155        var idx = this.TryGetIndex(id);
 0156        if (idx == long.MaxValue)
 0157        {
 0158            vertex = uint.MaxValue;
 0159            return false;
 160        }
 161
 0162        if (_data.Length <= idx * 2 + 0)
 0163        {
 0164            vertex = uint.MaxValue;
 0165            return false;
 166        }
 167
 0168        vertex = unchecked((uint)_data[(int)(idx * 2 + 0)]);
 0169        return _data[(int)(idx * 2 + 1)] == int.MinValue;
 0170    }
 171
 172    /// <summary>
 173    /// Returns true if the given id is a core node.
 174    /// </summary>
 175    public bool IsCoreNode(long id)
 0176    {
 0177        if (_previousIndex != long.MaxValue)
 0178        {
 0179            var tempId = this.GetId(_previousIndex + 1);
 0180            if (tempId == id)
 0181            {
 0182                if (this.IsCoreNodeAtIndex(_previousIndex + 1, id))
 0183                {
 0184                    return true;
 185                }
 186
 0187                return false;
 188            }
 0189        }
 190
 0191        var idx = this.TryGetIndex(id);
 0192        if (idx != long.MaxValue)
 0193        {
 0194            _previousIndex = idx;
 0195            if (this.IsCoreNodeAtIndex(idx, id))
 0196            {
 0197                return true;
 198            }
 199
 0200            return false;
 201        }
 202
 0203        return false;
 0204    }
 205
 206
 207    /// <summary>
 208    /// Returns true if the given id is in this index.
 209    /// </summary>
 210    public bool HasId(long id)
 0211    {
 0212        if (_previousIndex != long.MaxValue)
 0213        {
 0214            var tempId = this.GetId(_previousIndex + 1);
 0215            if (tempId == id)
 0216            {
 0217                return true;
 218            }
 0219        }
 220
 0221        var idx = this.TryGetIndex(id);
 0222        _previousIndex = idx;
 0223        return idx != long.MaxValue;
 0224    }
 225
 226    /// <summary>
 227    /// Gets the coordinate for the given node.
 228    /// </summary>
 229    public bool TryGetValue(long id, out float latitude, out float longitude, out bool isCore)
 0230    {
 0231        var idx = this.TryGetIndex(id);
 0232        if (idx == long.MaxValue)
 0233        {
 0234            latitude = float.MaxValue;
 0235            longitude = float.MaxValue;
 0236            isCore = false;
 0237            return false;
 238        }
 239
 0240        if (!this.GetLatLon(idx, out latitude, out longitude))
 0241        {
 0242            latitude = float.MaxValue;
 0243            longitude = float.MaxValue;
 0244            isCore = false;
 0245            return false;
 246        }
 247
 0248        isCore = this.IsCoreNodeAtIndex(idx, id);
 0249        return true;
 0250    }
 251
 252    /// <summary>
 253    /// Gets all relevant info on the given node.
 254    /// </summary>
 255    public bool TryGetValue(long id, out float latitude, out float longitude, out bool isCore, out uint vertex,
 256        out long idx)
 0257    {
 0258        idx = this.TryGetIndex(id);
 0259        if (idx == long.MaxValue)
 0260        { // no relevant data here.
 0261            latitude = float.MaxValue;
 0262            longitude = float.MaxValue;
 0263            isCore = false;
 0264            vertex = uint.MaxValue;
 0265            return false;
 266        }
 0267        else if (_data.Length > idx * 2 + 1 &&
 0268                 _data[(int)(idx * 2 + 1)] == int.MinValue)
 0269        { // this is a core-vertex, no coordinates here anymore.
 0270            latitude = float.MaxValue;
 0271            longitude = float.MaxValue;
 0272            isCore = this.IsCoreNodeAtIndex(idx, id);
 0273            vertex = unchecked((uint)_data[(int)(idx * 2 + 0)]);
 0274            return true;
 275        }
 276
 0277        if (this.GetLatLon(idx, out latitude, out longitude))
 0278        { // no relevant data.
 0279            isCore = this.IsCoreNodeAtIndex(idx, id);
 0280            vertex = uint.MaxValue;
 0281            return true;
 282        }
 283
 0284        latitude = float.MaxValue;
 0285        longitude = float.MaxValue;
 0286        isCore = false;
 0287        vertex = uint.MaxValue;
 0288        return false;
 0289    }
 290
 291    /// <summary>
 292    /// Gets the coordinate for the given node.
 293    /// </summary>
 294    public bool TryGetValue(long id, out (double longitude, double latitude, float? e) coordinate,
 295        out bool isCore)
 0296    {
 0297        if (this.TryGetValue(id, out var latitude, out var longitude, out isCore))
 0298        {
 0299            coordinate = (longitude, latitude, null);
 0300            return true;
 301        }
 302
 0303        coordinate = (default, default, null);
 0304        return false;
 0305    }
 306
 307    /// <summary>
 308    /// Returns true if a the given index there is an id that represents a core node.
 309    /// </summary>
 310    private bool IsCoreNodeAtIndex(long idx, long id)
 0311    {
 0312        if (idx > 0 &&
 0313            this.GetId(idx - 1) == id)
 0314        {
 0315            return true;
 316        }
 317
 0318        if (idx < _index.Length - 1 &&
 0319            this.GetId(idx + 1) == id)
 0320        {
 0321            return true;
 322        }
 323
 0324        return false;
 0325    }
 326
 0327    private long _previousIndex = long.MaxValue;
 328
 329    /// <summary>
 330    /// Gets the coordinate for the given node.
 331    /// </summary>
 332    public long TryGetIndex(long id)
 0333    {
 0334        if (_previousIndex != long.MaxValue &&
 0335            _previousIndex + 1 < _idx)
 0336        {
 0337            var previousId = this.GetId(_previousIndex);
 0338            var offset = 1;
 0339            var nextId = this.GetId(_previousIndex + offset);
 0340            while (nextId == previousId &&
 0341                   _previousIndex + offset + 1 < _idx)
 0342            {
 0343                offset++;
 0344                nextId = this.GetId(_previousIndex + offset);
 0345            }
 346
 0347            if (previousId < id && id < nextId)
 0348            {
 0349                return long.MaxValue;
 350            }
 351
 0352            if (previousId == id)
 0353            {
 0354                return _previousIndex;
 355            }
 356
 0357            if (nextId == id)
 0358            {
 0359                _previousIndex += offset;
 0360                return _previousIndex;
 361            }
 0362        }
 363
 364        // do a binary search.
 0365        long bottom = 0;
 0366        var top = _idx - 1;
 0367        var bottomId = this.GetId(bottom);
 0368        if (id == bottomId)
 0369        {
 0370            _previousIndex = bottom;
 0371            return bottom;
 372        }
 373
 0374        var topId = this.GetId(top);
 0375        if (id == topId)
 0376        {
 0377            while (top - 1 > 0 &&
 0378                   this.GetId(top - 1) == id)
 0379            {
 0380                top--;
 0381            }
 382
 0383            _previousIndex = top;
 0384            return top;
 385        }
 386
 0387        while (top - bottom > 1)
 0388        {
 0389            var middle = (top - bottom) / 2 + bottom;
 0390            var middleId = this.GetId(middle);
 0391            if (middleId == id)
 0392            {
 0393                while (middle - 1 > 0 &&
 0394                       this.GetId(middle - 1) == id)
 0395                {
 0396                    middle--;
 0397                }
 398
 0399                _previousIndex = middle;
 0400                return middle;
 401            }
 402
 0403            if (middleId > id)
 0404            {
 0405                topId = middleId;
 0406                top = middle;
 0407            }
 408            else
 0409            {
 0410                bottomId = middleId;
 0411                bottom = middle;
 0412            }
 0413        }
 414
 0415        return long.MaxValue;
 0416    }
 417
 418    private long GetId(long index)
 0419    {
 0420        if (_index.Length == 0)
 0421        {
 0422            return long.MaxValue;
 423        }
 424
 0425        var overflow = 0;
 0426        for (var i = 0; i < _overflows.Count; i++)
 0427        {
 0428            if (index >= _overflows[i])
 0429            {
 0430                overflow = i + 1;
 0431            }
 432            else
 0433            {
 0434                break;
 435            }
 0436        }
 437
 0438        return (long)_index[(int)index] + (long)(int.MaxValue * (long)overflow);
 0439    }
 440
 441    private bool GetLatLon(long index, out float latitude, out float longitude)
 0442    {
 0443        index = index * 2;
 444
 0445        var lat = _data[(int)(index + 0)];
 0446        var lon = _data[(int)(index + 1)];
 447
 0448        if (lat == int.MaxValue && lon == int.MaxValue)
 0449        {
 0450            latitude = float.MaxValue;
 0451            longitude = float.MaxValue;
 0452            return false;
 453        }
 454
 0455        latitude = (float)(lat / 10000000.0);
 0456        longitude = (float)(lon / 10000000.0);
 0457        return true;
 0458    }
 459
 460    /// <summary>
 461    /// Returns the number of elements.
 462    /// </summary>
 0463    public long Count => _index.Length;
 464
 465    private static void EnsureMinimumSize(ref int[] array, long position, long step = 16)
 0466    {
 0467        if (array.Length > position) return;
 0468        var newSize = array.Length + step;
 0469        while (newSize <= position) newSize += step;
 0470        Array.Resize(ref array, (int)newSize);
 0471    }
 472}
Generated by: ReportGenerator 4.8.2.0
06/04/2026 - 11:29:09
GitHub | www.palmmedia.de

Methods/Properties

.ctor()
AddId(...)
long2doubleInt(...)
doubleInt2long(...)
SortAndConvertIndex()
get_Item(...)
Set(...)
SetIndex(...)
TryGetCoreNode(...)
IsCoreNode(...)
HasId(...)
TryGetValue(...)
TryGetValue(...)
TryGetValue(...)
IsCoreNodeAtIndex(...)
TryGetIndex(...)
GetId(...)
GetLatLon(...)
get_Count()
EnsureMinimumSize(...)