< 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:263_26948838820

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
 59215    public SparseArray(long size, int blockSize = 1 << 16,
 59216        T emptyDefault = default)
 59217    {
 59218        if (size < 0)
 019        {
 020            throw new ArgumentOutOfRangeException(nameof(size), "Size needs to be bigger than or equal to zero.");
 21        }
 22
 59223        if (blockSize <= 0)
 024        {
 025            throw new ArgumentOutOfRangeException(nameof(blockSize),
 026                "Block size needs to be bigger than or equal to zero.");
 27        }
 28
 59229        if ((blockSize & (blockSize - 1)) != 0)
 030        {
 031            throw new ArgumentOutOfRangeException(nameof(blockSize), "Block size needs to be a power of 2.");
 32        }
 33
 59234        _default = emptyDefault;
 59235        _blockSize = blockSize;
 59236        _size = size;
 59237        _arrayPow = ExpOf2(blockSize);
 38
 59239        var blockCount = (long)Math.Ceiling((double)size / _blockSize);
 59240        _blocks = new T[blockCount][];
 59241    }
 42
 24943    private SparseArray(T[][] blocks, long size, int blockSize, int arrayPow, T @default)
 24944    {
 24945        _blocks = blocks;
 24946        _size = size;
 24947        _blockSize = blockSize;
 24948        _arrayPow = arrayPow;
 24949        _default = @default;
 24950    }
 51
 52    private static int ExpOf2(int powerOf2)
 1006453    {
 54        // this can probably be faster but it needs to run once in the constructor,
 55        // feel free to improve but not crucial.
 1006456        if (powerOf2 == 1)
 59257        {
 59258            return 0;
 59        }
 60
 947261        return ExpOf2(powerOf2 / 2) + 1;
 1006462    }
 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
 533271271        {
 533271272            if (idx >= this.Length)
 073            {
 074                throw new ArgumentOutOfRangeException(nameof(idx));
 75            }
 76
 533271277            var blockId = idx >> _arrayPow;
 533271278            var block = _blocks[blockId];
 533271279            if (block == null)
 30980            {
 30981                return _default;
 82            }
 83
 533240384            var localIdx = idx - (blockId << _arrayPow);
 533240385            return block[localIdx];
 533271286        }
 87        set
 107188        {
 107189            if (idx >= this.Length)
 090            {
 091                throw new ArgumentOutOfRangeException(nameof(idx));
 92            }
 93
 107194            var blockId = idx >> _arrayPow;
 107195            var block = _blocks[blockId];
 107196            if (block == null)
 55397            {
 98                // don't create a new block for a default value.
 55399                if (EqualityComparer<T>.Default.Equals(value, _default))
 0100                {
 0101                    return;
 102                }
 103
 553104                block = new T[_blockSize];
 72483922105                for (var i = 0; i < _blockSize; i++)
 36241408106                {
 36241408107                    block[i] = _default;
 36241408108                }
 109
 553110                _blocks[blockId] = block;
 553111            }
 112
 1071113            var localIdx = idx % _blockSize;
 1071114            _blocks[blockId][localIdx] = value;
 1071115        }
 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)
 610124    {
 610125        if (size < 0)
 0126        {
 0127            throw new ArgumentOutOfRangeException(nameof(size),
 0128                "Cannot resize an array to a size of zero or smaller.");
 129        }
 130
 610131        var blockCount = (long)Math.Ceiling((double)size / _blockSize);
 610132        if (blockCount != _blocks.Length)
 537133        {
 537134            Array.Resize(ref _blocks, (int)blockCount);
 537135        }
 136
 610137        _size = size;
 610138    }
 139
 140    /// <summary>
 141    /// Gets the length of this array.
 142    /// </summary>
 11270471143    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()
 249150    {
 249151        var blocks = new T[_blocks.Length][];
 27838152        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
 249163        return new SparseArray<T>(blocks, _size, _blockSize, _arrayPow, _default);
 249164    }
 165
 166    public IEnumerator<(long i, T value)> GetEnumerator()
 296167    {
 789516168        for (var b = 0; b < _blocks.Length; b++)
 394490169        {
 394490170            var block = _blocks[b];
 394490171            if (block == null)
 394194172            {
 394194173                continue;
 174            }
 175
 36516706176            for (var i = 0; i < block.Length; i++)
 18258085177            {
 18258085178                yield return ((_blockSize * b) + i, block[i]);
 18258057179            }
 268180        }
 268181    }
 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
06/04/2026 - 11:29:09
GitHub | www.palmmedia.de

Methods/Properties

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