< 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:232_15462506344

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
 32515    public SparseArray(long size, int blockSize = 1 << 16,
 32516        T emptyDefault = default)
 32517    {
 32518        if (size < 0)
 019        {
 020            throw new ArgumentOutOfRangeException(nameof(size), "Size needs to be bigger than or equal to zero.");
 21        }
 22
 32523        if (blockSize <= 0)
 024        {
 025            throw new ArgumentOutOfRangeException(nameof(blockSize),
 026                "Block size needs to be bigger than or equal to zero.");
 27        }
 28
 32529        if ((blockSize & (blockSize - 1)) != 0)
 030        {
 031            throw new ArgumentOutOfRangeException(nameof(blockSize), "Block size needs to be a power of 2.");
 32        }
 33
 32534        _default = emptyDefault;
 32535        _blockSize = blockSize;
 32536        _size = size;
 32537        _arrayPow = ExpOf2(blockSize);
 38
 32539        var blockCount = (long)Math.Ceiling((double)size / _blockSize);
 32540        _blocks = new T[blockCount][];
 32541    }
 42
 13543    private SparseArray(T[][] blocks, long size, int blockSize, int arrayPow, T @default)
 13544    {
 13545        _blocks = blocks;
 13546        _size = size;
 13547        _blockSize = blockSize;
 13548        _arrayPow = arrayPow;
 13549        _default = @default;
 13550    }
 51
 52    private static int ExpOf2(int powerOf2)
 552553    {
 54        // this can probably be faster but it needs to run once in the constructor,
 55        // feel free to improve but not crucial.
 552556        if (powerOf2 == 1)
 32557        {
 32558            return 0;
 59        }
 60
 520061        return ExpOf2(powerOf2 / 2) + 1;
 552562    }
 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
 34838271        {
 34838272            if (idx >= this.Length)
 073            {
 074                throw new ArgumentOutOfRangeException(nameof(idx));
 75            }
 76
 34838277            var blockId = idx >> _arrayPow;
 34838278            var block = _blocks[blockId];
 34838279            if (block == null)
 16080            {
 16081                return _default;
 82            }
 83
 34822284            var localIdx = idx - (blockId << _arrayPow);
 34822285            return block[localIdx];
 34838286        }
 87        set
 30788        {
 30789            if (idx >= this.Length)
 090            {
 091                throw new ArgumentOutOfRangeException(nameof(idx));
 92            }
 93
 30794            var blockId = idx >> _arrayPow;
 30795            var block = _blocks[blockId];
 30796            if (block == null)
 28697            {
 98                // don't create a new block for a default value.
 28699                if (EqualityComparer<T>.Default.Equals(value, _default))
 0100                {
 0101                    return;
 102                }
 103
 286104                block = new T[_blockSize];
 37487164105                for (var i = 0; i < _blockSize; i++)
 18743296106                {
 18743296107                    block[i] = _default;
 18743296108                }
 109
 286110                _blocks[blockId] = block;
 286111            }
 112
 307113            var localIdx = idx % _blockSize;
 307114            _blocks[blockId][localIdx] = value;
 307115        }
 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)
 284124    {
 284125        if (size < 0)
 0126        {
 0127            throw new ArgumentOutOfRangeException(nameof(size),
 0128                "Cannot resize an array to a size of zero or smaller.");
 129        }
 130
 284131        _size = size;
 132
 284133        var blockCount = (long)Math.Ceiling((double)size / _blockSize);
 284134        if (blockCount != _blocks.Length)
 276135        {
 276136            Array.Resize(ref _blocks, (int)blockCount);
 276137        }
 284138    }
 139
 140    /// <summary>
 141    /// Gets the length of this array.
 142    /// </summary>
 1080774143    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()
 135150    {
 135151        var blocks = new T[_blocks.Length][];
 27610152        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
 135163        return new SparseArray<T>(blocks, _size, _blockSize, _arrayPow, _default);
 135164    }
 165
 166    public IEnumerator<(long i, T value)> GetEnumerator()
 155167    {
 402196168        for (var b = 0; b < _blocks.Length; b++)
 200946169        {
 200946170            var block = _blocks[b];
 200946171            if (block == null)
 200797172            {
 200797173                continue;
 174            }
 175
 19285664176            for (var i = 0; i < block.Length; i++)
 9642686177            {
 9642686178                yield return ((_blockSize * b) + i, block[i]);
 9642683179            }
 146180        }
 152181    }
 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/05/2025 - 08:42:07
GitHub | www.palmmedia.de

Methods/Properties

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