< 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:293
Coverable lines:293
Total lines:475
Line coverage:0% (0 of 293)
Covered branches:0
Total branches:90
Branch coverage:0% (0 of 90)
Tag:224_14471318300

Metrics

MethodBranch coverage Cyclomatic complexity Line coverage
.ctor()100%10%
.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%

File(s)

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

#LineLine coverage
 1using System.Collections.Generic;
 2using Reminiscence;
 3using Reminiscence.Arrays;
 4using Reminiscence.IO;
 5
 6namespace Itinero.IO.Osm.Collections;
 7
 8/// <summary>
 9/// A cache for node coordinates.
 10/// </summary>
 11internal sealed class UnsignedNodeIndex
 12{
 13    // keeps all coordinates in a form [id, lat * 10.000.000, lon * 10.000.000]
 14    // assumes coordinates are added from a sorted source: TODO: make sure that the source read by the routerdb is sorte
 15    private readonly ArrayBase<int> _data;
 16    private readonly ArrayBase<int> _index;
 17
 18    /// <summary>
 19    /// Creates a new node coordinates cache.
 20    /// </summary>
 021    public UnsignedNodeIndex()
 022    {
 023        _index = new MemoryArray<int>(1024 * 1024);
 024        _data = new MemoryArray<int>(0);
 025    }
 26
 27    /// <summary>
 28    /// Creates a new node coordinates cache.
 29    /// </summary>
 030    public UnsignedNodeIndex(MemoryMap map)
 031    {
 032        _index = new Array<int>(map, 1024 * 1024);
 033        _data = new Array<int>(map, 0);
 034    }
 35
 036    private List<long>? _overflows = null; // overflows is null before sorting.
 037    private long _idx = 0;
 38
 39    /// <summary>
 40    /// Adds a node id to the index.
 41    /// </summary>
 42    public void AddId(long id)
 043    {
 44        int int1, int2;
 045        long2doubleInt(id, out int1, out int2);
 46
 047        _index.EnsureMinimumSize(_idx + 2);
 048        _index[_idx + 0] = int1;
 049        _index[_idx + 1] = int2;
 050        _idx += 2;
 051    }
 52
 53    private static void long2doubleInt(long a, out int a1, out int a2)
 054    {
 55        unchecked
 056        {
 057            a1 = (int)(a & uint.MaxValue);
 058            a2 = (int)(a >> 32);
 059        }
 060    }
 61
 62    private static long doubleInt2long(int a1, int a2)
 063    {
 64        unchecked
 065        {
 066            long b = a2;
 067            b = b << 32;
 068            b = b | (uint)a1;
 069            return b;
 70        }
 071    }
 72
 73    /// <summary>
 74    /// Sorts and converts the index.
 75    /// </summary>
 76    public void SortAndConvertIndex()
 077    {
 078        _overflows = new List<long>();
 079        _index.Resize(_idx);
 80
 081        Logging.Logger.Log("NodeIndex", Logging.TraceEventType.Information, "Sorting node id's...");
 082        QuickSort.Sort((i) =>
 083        {
 084            var int1 = _index[i * 2 + 0];
 085            var int2 = _index[i * 2 + 1];
 086            return doubleInt2long(int1, int2);
 087        },
 088            (i, j) =>
 089            {
 090                var int1 = _index[i * 2 + 0];
 091                var int2 = _index[i * 2 + 1];
 092                _index[i * 2 + 0] = _index[j * 2 + 0];
 093                _index[i * 2 + 1] = _index[j * 2 + 1];
 094                _index[j * 2 + 0] = int1;
 095                _index[j * 2 + 1] = int2;
 096            }, 0, _index.Length / 2 - 1);
 97
 098        for (long i = 0; i < _index.Length / 2; i++)
 099        {
 0100            var int1 = _index[i * 2 + 0];
 0101            var int2 = _index[i * 2 + 1];
 0102            var id = doubleInt2long(int1, int2);
 103
 0104            while (id >= (long)int.MaxValue * (long)(_overflows.Count + 1))
 0105            { // nodes are overflowing again.
 0106                _overflows.Add(i);
 0107            }
 108
 0109            _index[i] = (int)(id - (long)int.MaxValue * (long)_overflows.Count);
 0110        }
 111
 0112        _index.Resize(_index.Length / 2);
 0113        _idx = _index.Length;
 0114    }
 115
 116    /// <summary>
 117    /// Gets the node id at the given index.
 118    /// </summary>
 119    public long this[long idx]
 120    {
 121        get
 0122        {
 0123            var int1 = _index[idx * 2 + 0];
 0124            var int2 = _index[idx * 2 + 1];
 0125            return doubleInt2long(int1, int2);
 0126        }
 127    }
 128
 129    /// <summary>
 130    /// Sets a vertex id for the given vertex.
 131    /// </summary>
 132    public void Set(long id, uint vertex)
 0133    {
 0134        var idx = this.TryGetIndex(id);
 135
 0136        _data.EnsureMinimumSize(idx * 2 + 2, int.MaxValue);
 0137        _data[idx * 2 + 0] = unchecked((int)vertex);
 0138        _data[idx * 2 + 1] = int.MinValue;
 0139    }
 140
 141    /// <summary>
 142    /// Sets the coordinate for the given index.
 143    /// </summary>
 144    public void SetIndex(long idx, float latitude, float longitude)
 0145    {
 0146        var lat = (int)(latitude * 10000000);
 0147        var lon = (int)(longitude * 10000000);
 148
 0149        _data.EnsureMinimumSize(idx * 2 + 2, int.MaxValue);
 150
 0151        if (_data[idx * 2 + 1] == int.MinValue)
 0152        {
 153            // this is already a core vertex, no need to overwrite this more valuable data.
 0154            return;
 155        }
 156
 0157        _data[idx * 2 + 0] = lat;
 0158        _data[idx * 2 + 1] = lon;
 0159    }
 160
 161    /// <summary>
 162    /// Tries to get a core node and it's matching vertex.
 163    /// </summary>
 164    public bool TryGetCoreNode(long id, out uint vertex)
 0165    {
 0166        var idx = this.TryGetIndex(id);
 0167        if (idx == long.MaxValue)
 0168        {
 0169            vertex = uint.MaxValue;
 0170            return false;
 171        }
 172
 0173        if (_data.Length <= idx * 2 + 0)
 0174        {
 0175            vertex = uint.MaxValue;
 0176            return false;
 177        }
 178
 0179        vertex = unchecked((uint)_data[idx * 2 + 0]);
 0180        return _data[idx * 2 + 1] == int.MinValue;
 0181    }
 182
 183    /// <summary>
 184    /// Returns true if the given id is a core node.
 185    /// </summary>
 186    public bool IsCoreNode(long id)
 0187    {
 0188        if (_previousIndex != long.MaxValue)
 0189        {
 0190            var tempId = this.GetId(_previousIndex + 1);
 0191            if (tempId == id)
 0192            {
 0193                if (this.IsCoreNodeAtIndex(_previousIndex + 1, id))
 0194                {
 0195                    return true;
 196                }
 197
 0198                return false;
 199            }
 0200        }
 201
 0202        var idx = this.TryGetIndex(id);
 0203        if (idx != long.MaxValue)
 0204        {
 0205            _previousIndex = idx;
 0206            if (this.IsCoreNodeAtIndex(idx, id))
 0207            {
 0208                return true;
 209            }
 210
 0211            return false;
 212        }
 213
 0214        return false;
 0215    }
 216
 217
 218    /// <summary>
 219    /// Returns true if the given id is in this index.
 220    /// </summary>
 221    public bool HasId(long id)
 0222    {
 0223        if (_previousIndex != long.MaxValue)
 0224        {
 0225            var tempId = this.GetId(_previousIndex + 1);
 0226            if (tempId == id)
 0227            {
 0228                return true;
 229            }
 0230        }
 231
 0232        var idx = this.TryGetIndex(id);
 0233        _previousIndex = idx;
 0234        return idx != long.MaxValue;
 0235    }
 236
 237    /// <summary>
 238    /// Gets the coordinate for the given node.
 239    /// </summary>
 240    public bool TryGetValue(long id, out float latitude, out float longitude, out bool isCore)
 0241    {
 0242        var idx = this.TryGetIndex(id);
 0243        if (idx == long.MaxValue)
 0244        {
 0245            latitude = float.MaxValue;
 0246            longitude = float.MaxValue;
 0247            isCore = false;
 0248            return false;
 249        }
 250
 0251        if (!this.GetLatLon(idx, out latitude, out longitude))
 0252        {
 0253            latitude = float.MaxValue;
 0254            longitude = float.MaxValue;
 0255            isCore = false;
 0256            return false;
 257        }
 258
 0259        isCore = this.IsCoreNodeAtIndex(idx, id);
 0260        return true;
 0261    }
 262
 263    /// <summary>
 264    /// Gets all relevant info on the given node.
 265    /// </summary>
 266    public bool TryGetValue(long id, out float latitude, out float longitude, out bool isCore, out uint vertex,
 267        out long idx)
 0268    {
 0269        idx = this.TryGetIndex(id);
 0270        if (idx == long.MaxValue)
 0271        { // no relevant data here.
 0272            latitude = float.MaxValue;
 0273            longitude = float.MaxValue;
 0274            isCore = false;
 0275            vertex = uint.MaxValue;
 0276            return false;
 277        }
 0278        else if (_data.Length > idx * 2 + 1 &&
 0279                 _data[idx * 2 + 1] == int.MinValue)
 0280        { // this is a core-vertex, no coordinates here anymore.
 0281            latitude = float.MaxValue;
 0282            longitude = float.MaxValue;
 0283            isCore = this.IsCoreNodeAtIndex(idx, id);
 0284            vertex = unchecked((uint)_data[idx * 2 + 0]);
 0285            return true;
 286        }
 287
 0288        if (this.GetLatLon(idx, out latitude, out longitude))
 0289        { // no relevant data.
 0290            isCore = this.IsCoreNodeAtIndex(idx, id);
 0291            vertex = uint.MaxValue;
 0292            return true;
 293        }
 294
 0295        latitude = float.MaxValue;
 0296        longitude = float.MaxValue;
 0297        isCore = false;
 0298        vertex = uint.MaxValue;
 0299        return false;
 0300    }
 301
 302    /// <summary>
 303    /// Gets the coordinate for the given node.
 304    /// </summary>
 305    public bool TryGetValue(long id, out (double longitude, double latitude, float? e) coordinate,
 306        out bool isCore)
 0307    {
 0308        if (this.TryGetValue(id, out var latitude, out var longitude, out isCore))
 0309        {
 0310            coordinate = (longitude, latitude, null);
 0311            return true;
 312        }
 313
 0314        coordinate = (default, default, null);
 0315        return false;
 0316    }
 317
 318    /// <summary>
 319    /// Returns true if a the given index there is an id that represents a core node.
 320    /// </summary>
 321    private bool IsCoreNodeAtIndex(long idx, long id)
 0322    {
 0323        if (idx > 0 &&
 0324            this.GetId(idx - 1) == id)
 0325        {
 0326            return true;
 327        }
 328
 0329        if (idx < _index.Length - 1 &&
 0330            this.GetId(idx + 1) == id)
 0331        {
 0332            return true;
 333        }
 334
 0335        return false;
 0336    }
 337
 0338    private long _previousIndex = long.MaxValue;
 339
 340    /// <summary>
 341    /// Gets the coordinate for the given node.
 342    /// </summary>
 343    public long TryGetIndex(long id)
 0344    {
 0345        if (_previousIndex != long.MaxValue &&
 0346            _previousIndex + 1 < _idx)
 0347        {
 0348            var previousId = this.GetId(_previousIndex);
 0349            var offset = 1;
 0350            var nextId = this.GetId(_previousIndex + offset);
 0351            while (nextId == previousId &&
 0352                   _previousIndex + offset + 1 < _idx)
 0353            {
 0354                offset++;
 0355                nextId = this.GetId(_previousIndex + offset);
 0356            }
 357
 0358            if (previousId < id && id < nextId)
 0359            {
 0360                return long.MaxValue;
 361            }
 362
 0363            if (previousId == id)
 0364            {
 0365                return _previousIndex;
 366            }
 367
 0368            if (nextId == id)
 0369            {
 0370                _previousIndex += offset;
 0371                return _previousIndex;
 372            }
 0373        }
 374
 375        // do a binary search.
 0376        long bottom = 0;
 0377        var top = _idx - 1;
 0378        var bottomId = this.GetId(bottom);
 0379        if (id == bottomId)
 0380        {
 0381            _previousIndex = bottom;
 0382            return bottom;
 383        }
 384
 0385        var topId = this.GetId(top);
 0386        if (id == topId)
 0387        {
 0388            while (top - 1 > 0 &&
 0389                   this.GetId(top - 1) == id)
 0390            {
 0391                top--;
 0392            }
 393
 0394            _previousIndex = top;
 0395            return top;
 396        }
 397
 0398        while (top - bottom > 1)
 0399        {
 0400            var middle = (top - bottom) / 2 + bottom;
 0401            var middleId = this.GetId(middle);
 0402            if (middleId == id)
 0403            {
 0404                while (middle - 1 > 0 &&
 0405                       this.GetId(middle - 1) == id)
 0406                {
 0407                    middle--;
 0408                }
 409
 0410                _previousIndex = middle;
 0411                return middle;
 412            }
 413
 0414            if (middleId > id)
 0415            {
 0416                topId = middleId;
 0417                top = middle;
 0418            }
 419            else
 0420            {
 0421                bottomId = middleId;
 0422                bottom = middle;
 0423            }
 0424        }
 425
 0426        return long.MaxValue;
 0427    }
 428
 429    private long GetId(long index)
 0430    {
 0431        if (_index.Length == 0)
 0432        {
 0433            return long.MaxValue;
 434        }
 435
 0436        var overflow = 0;
 0437        for (var i = 0; i < _overflows.Count; i++)
 0438        {
 0439            if (index >= _overflows[i])
 0440            {
 0441                overflow = i + 1;
 0442            }
 443            else
 0444            {
 0445                break;
 446            }
 0447        }
 448
 0449        return (long)_index[index] + (long)(int.MaxValue * (long)overflow);
 0450    }
 451
 452    private bool GetLatLon(long index, out float latitude, out float longitude)
 0453    {
 0454        index = index * 2;
 455
 0456        var lat = _data[index + 0];
 0457        var lon = _data[index + 1];
 458
 0459        if (lat == int.MaxValue && lon == int.MaxValue)
 0460        {
 0461            latitude = float.MaxValue;
 0462            longitude = float.MaxValue;
 0463            return false;
 464        }
 465
 0466        latitude = (float)(lat / 10000000.0);
 0467        longitude = (float)(lon / 10000000.0);
 0468        return true;
 0469    }
 470
 471    /// <summary>
 472    /// Returns the number of elements.
 473    /// </summary>
 0474    public long Count => _index.Length;
 475}
Generated by: ReportGenerator 4.8.2.0
04/15/2025 - 13:59:49
GitHub | www.palmmedia.de

Methods/Properties

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