< Summary

Class:Itinero.Network.DataStructures.SparseArray`1
Assembly:Itinero
File(s):/home/runner/work/routing2/routing2/src/Itinero/Network/DataStructures/SparseArray.cs
Covered lines:89
Uncovered lines:19
Coverable lines:108
Total lines:198
Line coverage:82.4% (89 of 108)
Covered branches:27
Total branches:34
Branch coverage:79.4% (27 of 34)
Tag:251_23667616543

Metrics

MethodBranch coverage Cyclomatic complexity Line coverage
.ctor(...)50%665%
.ctor(...)100%1100%
ExpOf2(...)100%2100%
get_Item(...)75%483.33%
set_Item(...)75%880.95%
Resize(...)75%475%
get_Length()100%1100%
Clone()100%4100%
GetEnumerator()100%6100%
System.Collections.IEnumerable.GetEnumerator()100%10%

File(s)

/home/runner/work/routing2/routing2/src/Itinero/Network/DataStructures/SparseArray.cs

#LineLine coverage
 1using System;
 2using System.Collections;
 3using System.Collections.Generic;
 4
 5namespace Itinero.Network.DataStructures;
 6
 7internal sealed class SparseArray<T> : IEnumerable<(long i, T value)>
 8{
 9    private T[][] _blocks;
 10    private readonly int _blockSize; // Holds the maximum array size, always needs to be a power of 2.
 11    private readonly int _arrayPow;
 12    private long _size; // the total size of this array.
 13    private readonly T _default;
 14
 40815    public SparseArray(long size, int blockSize = 1 << 16,
 40816        T emptyDefault = default)
 40817    {
 40818        if (size < 0)
 019        {
 020            throw new ArgumentOutOfRangeException(nameof(size), "Size needs to be bigger than or equal to zero.");
 21        }
 22
 40823        if (blockSize <= 0)
 024        {
 025            throw new ArgumentOutOfRangeException(nameof(blockSize),
 026                "Block size needs to be bigger than or equal to zero.");
 27        }
 28
 40829        if ((blockSize & (blockSize - 1)) != 0)
 030        {
 031            throw new ArgumentOutOfRangeException(nameof(blockSize), "Block size needs to be a power of 2.");
 32        }
 33
 40834        _default = emptyDefault;
 40835        _blockSize = blockSize;
 40836        _size = size;
 40837        _arrayPow = ExpOf2(blockSize);
 38
 40839        var blockCount = (long)Math.Ceiling((double)size / _blockSize);
 40840        _blocks = new T[blockCount][];
 40841    }
 42
 17243    private SparseArray(T[][] blocks, long size, int blockSize, int arrayPow, T @default)
 17244    {
 17245        _blocks = blocks;
 17246        _size = size;
 17247        _blockSize = blockSize;
 17248        _arrayPow = arrayPow;
 17249        _default = @default;
 17250    }
 51
 52    private static int ExpOf2(int powerOf2)
 693653    {
 54        // this can probably be faster but it needs to run once in the constructor,
 55        // feel free to improve but not crucial.
 693656        if (powerOf2 == 1)
 40857        {
 40858            return 0;
 59        }
 60
 652861        return ExpOf2(powerOf2 / 2) + 1;
 693662    }
 63
 64    /// <summary>
 65    /// Gets or sets the item at the given index.
 66    /// </summary>
 67    /// <param name="idx">The index.</param>
 68    public T this[long idx]
 69    {
 70        get
 478660071        {
 478660072            if (idx >= this.Length)
 073            {
 074                throw new ArgumentOutOfRangeException(nameof(idx));
 75            }
 76
 478660077            var blockId = idx >> _arrayPow;
 478660078            var block = _blocks[blockId];
 478660079            if (block == null)
 21480            {
 21481                return _default;
 82            }
 83
 478638684            var localIdx = idx - (blockId << _arrayPow);
 478638685            return block[localIdx];
 478660086        }
 87        set
 85888        {
 85889            if (idx >= this.Length)
 090            {
 091                throw new ArgumentOutOfRangeException(nameof(idx));
 92            }
 93
 85894            var blockId = idx >> _arrayPow;
 85895            var block = _blocks[blockId];
 85896            if (block == null)
 38297            {
 98                // don't create a new block for a default value.
 38299                if (EqualityComparer<T>.Default.Equals(value, _default))
 0100                {
 0101                    return;
 102                }
 103
 382104                block = new T[_blockSize];
 50070268105                for (var i = 0; i < _blockSize; i++)
 25034752106                {
 25034752107                    block[i] = _default;
 25034752108                }
 109
 382110                _blocks[blockId] = block;
 382111            }
 112
 858113            var localIdx = idx % _blockSize;
 858114            _blocks[blockId][localIdx] = value;
 858115        }
 116    }
 117
 118    /// <summary>
 119    /// Resizes this array to the given size.
 120    /// </summary>
 121    /// <param name="size">The size.</param>
 122    /// <exception cref="ArgumentOutOfRangeException"></exception>
 123    public void Resize(long size)
 411124    {
 411125        if (size < 0)
 0126        {
 0127            throw new ArgumentOutOfRangeException(nameof(size),
 0128                "Cannot resize an array to a size of zero or smaller.");
 129        }
 130
 411131        var blockCount = (long)Math.Ceiling((double)size / _blockSize);
 411132        if (blockCount != _blocks.Length)
 366133        {
 366134            Array.Resize(ref _blocks, (int)blockCount);
 366135        }
 136
 411137        _size = size;
 411138    }
 139
 140    /// <summary>
 141    /// Gets the length of this array.
 142    /// </summary>
 10175164143    public long Length => _size;
 144
 145    /// <summary>
 146    /// Creates a clone.
 147    /// </summary>
 148    /// <returns>A copy of this array.</returns>
 149    public SparseArray<T> Clone()
 172150    {
 172151        var blocks = new T[_blocks.Length][];
 27684152        for (var b = 0; b < blocks.Length; b++)
 13670153        {
 13670154            var block = _blocks[b];
 13670155            if (block == null)
 13660156            {
 13660157                continue;
 158            }
 159
 10160            blocks[b] = (block.Clone() as T[])!;
 10161        }
 162
 172163        return new SparseArray<T>(blocks, _size, _blockSize, _arrayPow, _default);
 172164    }
 165
 166    public IEnumerator<(long i, T value)> GetEnumerator()
 194167    {
 510158168        for (var b = 0; b < _blocks.Length; b++)
 254888169        {
 254888170            var block = _blocks[b];
 254888171            if (block == null)
 254695172            {
 254695173                continue;
 174            }
 175
 25052920176            for (var i = 0; i < block.Length; i++)
 12526270177            {
 12526270178                yield return ((_blockSize * b) + i, block[i]);
 12526267179            }
 190180        }
 191181    }
 182
 183    IEnumerator IEnumerable.GetEnumerator()
 0184    {
 0185        return this.GetEnumerator();
 0186    }
 187}
 188
 189internal static class SparseArrayExtensions
 190{
 191    internal static void EnsureMinimumSize<T>(this SparseArray<T> array, long i)
 192    {
 193        if (array.Length <= i)
 194        {
 195            array.Resize(i + 1);
 196        }
 197    }
 198}
Generated by: ReportGenerator 4.8.2.0
03/27/2026 - 21:11:43
GitHub | www.palmmedia.de

Methods/Properties

.ctor(...)
.ctor(...)
ExpOf2(...)
get_Item(...)
set_Item(...)
Resize(...)
get_Length()
Clone()
GetEnumerator()
System.Collections.IEnumerable.GetEnumerator()