< 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:224_14471318300

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
 29915    public SparseArray(long size, int blockSize = 1 << 16,
 29916        T emptyDefault = default)
 29917    {
 29918        if (size < 0)
 019        {
 020            throw new ArgumentOutOfRangeException(nameof(size), "Size needs to be bigger than or equal to zero.");
 21        }
 22
 29923        if (blockSize <= 0)
 024        {
 025            throw new ArgumentOutOfRangeException(nameof(blockSize),
 026                "Block size needs to be bigger than or equal to zero.");
 27        }
 28
 29929        if ((blockSize & (blockSize - 1)) != 0)
 030        {
 031            throw new ArgumentOutOfRangeException(nameof(blockSize), "Block size needs to be a power of 2.");
 32        }
 33
 29934        _default = emptyDefault;
 29935        _blockSize = blockSize;
 29936        _size = size;
 29937        _arrayPow = ExpOf2(blockSize);
 38
 29939        var blockCount = (long)Math.Ceiling((double)size / _blockSize);
 29940        _blocks = new T[blockCount][];
 29941    }
 42
 12243    private SparseArray(T[][] blocks, long size, int blockSize, int arrayPow, T @default)
 12244    {
 12245        _blocks = blocks;
 12246        _size = size;
 12247        _blockSize = blockSize;
 12248        _arrayPow = arrayPow;
 12249        _default = @default;
 12250    }
 51
 52    private static int ExpOf2(int powerOf2)
 508353    {
 54        // this can probably be faster but it needs to run once in the constructor,
 55        // feel free to improve but not crucial.
 508356        if (powerOf2 == 1)
 29957        {
 29958            return 0;
 59        }
 60
 478461        return ExpOf2(powerOf2 / 2) + 1;
 508362    }
 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
 34823871        {
 34823872            if (idx >= this.Length)
 073            {
 074                throw new ArgumentOutOfRangeException(nameof(idx));
 75            }
 76
 34823877            var blockId = idx >> _arrayPow;
 34823878            var block = _blocks[blockId];
 34823879            if (block == null)
 14780            {
 14781                return _default;
 82            }
 83
 34809184            var localIdx = idx - (blockId << _arrayPow);
 34809185            return block[localIdx];
 34823886        }
 87        set
 28188        {
 28189            if (idx >= this.Length)
 090            {
 091                throw new ArgumentOutOfRangeException(nameof(idx));
 92            }
 93
 28194            var blockId = idx >> _arrayPow;
 28195            var block = _blocks[blockId];
 28196            if (block == null)
 26097            {
 98                // don't create a new block for a default value.
 26099                if (EqualityComparer<T>.Default.Equals(value, _default))
 0100                {
 0101                    return;
 102                }
 103
 260104                block = new T[_blockSize];
 34079240105                for (var i = 0; i < _blockSize; i++)
 17039360106                {
 17039360107                    block[i] = _default;
 17039360108                }
 109
 260110                _blocks[blockId] = block;
 260111            }
 112
 281113            var localIdx = idx % _blockSize;
 281114            _blocks[blockId][localIdx] = value;
 281115        }
 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)
 258124    {
 258125        if (size < 0)
 0126        {
 0127            throw new ArgumentOutOfRangeException(nameof(size),
 0128                "Cannot resize an array to a size of zero or smaller.");
 129        }
 130
 258131        _size = size;
 132
 258133        var blockCount = (long)Math.Ceiling((double)size / _blockSize);
 258134        if (blockCount != _blocks.Length)
 250135        {
 250136            Array.Resize(ref _blocks, (int)blockCount);
 250137        }
 258138    }
 139
 140    /// <summary>
 141    /// Gets the length of this array.
 142    /// </summary>
 1080404143    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()
 122150    {
 122151        var blocks = new T[_blocks.Length][];
 27584152        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
 122163        return new SparseArray<T>(blocks, _size, _blockSize, _arrayPow, _default);
 122164    }
 165
 166    public IEnumerator<(long i, T value)> GetEnumerator()
 142167    {
 366640168        for (var b = 0; b < _blocks.Length; b++)
 183181169        {
 183181170            var block = _blocks[b];
 183181171            if (block == null)
 183045172            {
 183045173                continue;
 174            }
 175
 17581702176            for (var i = 0; i < block.Length; i++)
 8790718177            {
 8790718178                yield return ((_blockSize * b) + i, block[i]);
 8790715179            }
 133180        }
 139181    }
 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
04/15/2025 - 13:59:49
GitHub | www.palmmedia.de

Methods/Properties

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