< Summary

Class:Itinero.Network.DataStructures.SparseArrayExtensions
Assembly:Itinero
File(s):/home/runner/work/routing2/routing2/src/Itinero/Network/DataStructures/SparseArray.cs
Covered lines:6
Uncovered lines:0
Coverable lines:6
Total lines:198
Line coverage:100% (6 of 6)
Covered branches:2
Total branches:2
Branch coverage:100% (2 of 2)
Tag:224_14471318300

Metrics

MethodBranch coverage Cyclomatic complexity Line coverage
EnsureMinimumSize(...)100%2100%

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
 15    public SparseArray(long size, int blockSize = 1 << 16,
 16        T emptyDefault = default)
 17    {
 18        if (size < 0)
 19        {
 20            throw new ArgumentOutOfRangeException(nameof(size), "Size needs to be bigger than or equal to zero.");
 21        }
 22
 23        if (blockSize <= 0)
 24        {
 25            throw new ArgumentOutOfRangeException(nameof(blockSize),
 26                "Block size needs to be bigger than or equal to zero.");
 27        }
 28
 29        if ((blockSize & (blockSize - 1)) != 0)
 30        {
 31            throw new ArgumentOutOfRangeException(nameof(blockSize), "Block size needs to be a power of 2.");
 32        }
 33
 34        _default = emptyDefault;
 35        _blockSize = blockSize;
 36        _size = size;
 37        _arrayPow = ExpOf2(blockSize);
 38
 39        var blockCount = (long)Math.Ceiling((double)size / _blockSize);
 40        _blocks = new T[blockCount][];
 41    }
 42
 43    private SparseArray(T[][] blocks, long size, int blockSize, int arrayPow, T @default)
 44    {
 45        _blocks = blocks;
 46        _size = size;
 47        _blockSize = blockSize;
 48        _arrayPow = arrayPow;
 49        _default = @default;
 50    }
 51
 52    private static int ExpOf2(int powerOf2)
 53    {
 54        // this can probably be faster but it needs to run once in the constructor,
 55        // feel free to improve but not crucial.
 56        if (powerOf2 == 1)
 57        {
 58            return 0;
 59        }
 60
 61        return ExpOf2(powerOf2 / 2) + 1;
 62    }
 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
 71        {
 72            if (idx >= this.Length)
 73            {
 74                throw new ArgumentOutOfRangeException(nameof(idx));
 75            }
 76
 77            var blockId = idx >> _arrayPow;
 78            var block = _blocks[blockId];
 79            if (block == null)
 80            {
 81                return _default;
 82            }
 83
 84            var localIdx = idx - (blockId << _arrayPow);
 85            return block[localIdx];
 86        }
 87        set
 88        {
 89            if (idx >= this.Length)
 90            {
 91                throw new ArgumentOutOfRangeException(nameof(idx));
 92            }
 93
 94            var blockId = idx >> _arrayPow;
 95            var block = _blocks[blockId];
 96            if (block == null)
 97            {
 98                // don't create a new block for a default value.
 99                if (EqualityComparer<T>.Default.Equals(value, _default))
 100                {
 101                    return;
 102                }
 103
 104                block = new T[_blockSize];
 105                for (var i = 0; i < _blockSize; i++)
 106                {
 107                    block[i] = _default;
 108                }
 109
 110                _blocks[blockId] = block;
 111            }
 112
 113            var localIdx = idx % _blockSize;
 114            _blocks[blockId][localIdx] = value;
 115        }
 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)
 124    {
 125        if (size < 0)
 126        {
 127            throw new ArgumentOutOfRangeException(nameof(size),
 128                "Cannot resize an array to a size of zero or smaller.");
 129        }
 130
 131        _size = size;
 132
 133        var blockCount = (long)Math.Ceiling((double)size / _blockSize);
 134        if (blockCount != _blocks.Length)
 135        {
 136            Array.Resize(ref _blocks, (int)blockCount);
 137        }
 138    }
 139
 140    /// <summary>
 141    /// Gets the length of this array.
 142    /// </summary>
 143    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()
 150    {
 151        var blocks = new T[_blocks.Length][];
 152        for (var b = 0; b < blocks.Length; b++)
 153        {
 154            var block = _blocks[b];
 155            if (block == null)
 156            {
 157                continue;
 158            }
 159
 160            blocks[b] = (block.Clone() as T[])!;
 161        }
 162
 163        return new SparseArray<T>(blocks, _size, _blockSize, _arrayPow, _default);
 164    }
 165
 166    public IEnumerator<(long i, T value)> GetEnumerator()
 167    {
 168        for (var b = 0; b < _blocks.Length; b++)
 169        {
 170            var block = _blocks[b];
 171            if (block == null)
 172            {
 173                continue;
 174            }
 175
 176            for (var i = 0; i < block.Length; i++)
 177            {
 178                yield return ((_blockSize * b) + i, block[i]);
 179            }
 180        }
 181    }
 182
 183    IEnumerator IEnumerable.GetEnumerator()
 184    {
 185        return this.GetEnumerator();
 186    }
 187}
 188
 189internal static class SparseArrayExtensions
 190{
 191    internal static void EnsureMinimumSize<T>(this SparseArray<T> array, long i)
 1431192    {
 1431193        if (array.Length <= i)
 258194        {
 258195            array.Resize(i + 1);
 258196        }
 1431197    }
 198}
Generated by: ReportGenerator 4.8.2.0
04/15/2025 - 13:59:49
GitHub | www.palmmedia.de

Methods/Properties

EnsureMinimumSize(...)