< Summary

Information
Class: SwiftCollections.SwiftSparseMap<T>
Assembly: SwiftCollections
File(s): /home/runner/work/SwiftCollections/SwiftCollections/src/SwiftCollections/Collection/SwiftSparseMap.cs
Line coverage
97%
Covered lines: 263
Uncovered lines: 7
Coverable lines: 270
Total lines: 563
Line coverage: 97.4%
Branch coverage
87%
Covered branches: 91
Total branches: 104
Branch coverage: 87.5%
Method coverage

Feature is only available for sponsors

Upgrade to PRO version

Metrics

MethodBranch coverage Crap Score Cyclomatic complexity Line coverage
.ctor()100%11100%
.ctor(...)100%1010100%
.ctor(...)100%11100%
get_Count()100%11100%
get_DenseCapacity()100%11100%
get_SparseCapacity()100%11100%
get_IsSynchronized()100%11100%
get_SyncRoot()100%22100%
get_DenseKeys()100%11100%
get_Keys()100%11100%
get_DenseValues()100%11100%
get_Values()100%11100%
get_Item(...)100%11100%
set_Item(...)100%22100%
get_State()100%11100%
set_State(...)75%242497.05%
ContainsKey(...)100%22100%
TryAdd(...)100%22100%
Add(...)100%11100%
TryGetValue(...)75%4491.66%
Remove(...)83.33%66100%
Clear()100%66100%
EnsureDenseCapacity(...)75%9875%
EnsureSparseCapacity(...)87.5%88100%
TrimExcess()92.85%1414100%
GetEnumerator()100%11100%
System.Collections.Generic.IEnumerable<System.Collections.Generic.KeyValuePair<System.Int32,T>>.GetEnumerator()100%11100%
System.Collections.IEnumerable.GetEnumerator()100%11100%
.ctor(...)100%11100%
get_Current()100%11100%
System.Collections.IEnumerator.get_Current()100%11100%
MoveNext()100%44100%
Reset()50%2283.33%
Dispose()100%11100%
GetDense(...)100%11100%
GetRequiredSparseCapacity(...)100%44100%
GetDenseIndexOrThrow(...)100%44100%
CloneTo(...)100%22100%

File(s)

/home/runner/work/SwiftCollections/SwiftCollections/src/SwiftCollections/Collection/SwiftSparseMap.cs

#LineLine coverage
 1using MemoryPack;
 2using System;
 3using System.Collections;
 4using System.Collections.Generic;
 5using System.Runtime.CompilerServices;
 6using System.Text.Json.Serialization;
 7
 8namespace SwiftCollections;
 9
 10/// <summary>
 11/// Represents a high-performance sparse map that stores values indexed by externally supplied integer keys.
 12/// Provides O(1) Add, Remove, Contains, and lookup operations while maintaining densely packed storage
 13/// for cache-friendly iteration.
 14/// </summary>
 15/// <remarks>
 16/// Unlike <see cref="SwiftBucket{T}"/>, which internally assigns and manages item indices,
 17/// <see cref="SwiftSparseMap{T}"/> is externally keyed. The caller supplies the integer key
 18/// (for example, an entity ID or handle) used to index the value.
 19///
 20/// Internally, the container maintains:
 21/// <list type="bullet">
 22///     <item>
 23///         <description>A sparse lookup table mapping keys to dense indices.</description>
 24///     </item>
 25///     <item>
 26///         <description>A dense array of keys.</description>
 27///     </item>
 28///     <item>
 29///         <description>A dense array of values.</description>
 30///     </item>
 31/// </list>
 32///
 33/// Removal uses a swap-back strategy to keep dense storage contiguous. As a result,
 34/// iteration order is not guaranteed to remain stable.
 35///
 36/// Keys are used as direct indices into the sparse lookup table, so memory usage scales
 37/// with the highest stored key rather than the number of stored values. This container is
 38/// intended for compact, non-negative IDs such as entity handles or slot indices. It is
 39/// not a good fit for arbitrary hashes or widely spaced keys; for those workloads prefer
 40/// <c>SwiftDictionary&lt;TKey, TValue&gt;</c>.
 41/// </remarks>
 42/// <typeparam name="T">Value type stored by key.</typeparam>
 43[Serializable]
 44[JsonConverter(typeof(SwiftStateJsonConverterFactory))]
 45[MemoryPackable]
 46public sealed partial class SwiftSparseMap<T> : ISwiftCloneable<T>, IEnumerable<KeyValuePair<int, T>>, IEnumerable
 47{
 48    #region Constants
 49
 50    public const int DefaultDenseCapacity = 8;
 51    public const int DefaultSparseCapacity = 8;
 52
 53    // sparse[key] stores (denseIndex + 1). 0 means "not present".
 54    private const int NotPresent = 0;
 55
 56    #endregion
 57
 58    #region Fields
 59
 60    private int[] _sparse;       // key -> denseIndex+1
 61    private int[] _denseKeys;    // denseIndex -> key
 62    private T[] _denseValues;    // denseIndex -> value
 63    private int _count;
 64
 65    [NonSerialized]
 66    private uint _version;
 67
 68    [NonSerialized]
 69    private object _syncRoot;
 70
 71    #endregion
 72
 73    #region Constructors
 74
 9375    public SwiftSparseMap() : this(DefaultSparseCapacity, DefaultDenseCapacity) { }
 76
 77    /// <summary>
 78    /// Initializes a new sparse map with the specified sparse and dense capacities.
 79    /// </summary>
 80    /// <param name="sparseCapacity">
 81    /// Initial sparse lookup capacity. This should track the highest expected key plus one,
 82    /// not the number of stored values.
 83    /// </param>
 84    /// <param name="denseCapacity">Initial dense storage capacity for values.</param>
 3285    public SwiftSparseMap(int sparseCapacity, int denseCapacity)
 3286    {
 3287        SwiftThrowHelper.ThrowIfNegative(sparseCapacity, nameof(sparseCapacity));
 3288        SwiftThrowHelper.ThrowIfNegative(denseCapacity, nameof(denseCapacity));
 89
 3290        int sparseSize = sparseCapacity == 0 ? 0 : SwiftHashTools.NextPowerOfTwo(sparseCapacity);
 3291        _sparse = sparseCapacity == 0
 3292            ? Array.Empty<int>()
 3293            : new int[sparseSize];
 3294        int denseSize = denseCapacity < DefaultDenseCapacity
 3295            ? DefaultDenseCapacity
 3296            : SwiftHashTools.NextPowerOfTwo(denseCapacity);
 3297        _denseKeys = denseCapacity == 0
 3298            ? Array.Empty<int>()
 3299            : new int[denseSize];
 32100        _denseValues = _denseKeys.Length == 0 ? Array.Empty<T>() : new T[_denseKeys.Length];
 101
 32102        _count = 0;
 32103    }
 104
 105    [MemoryPackConstructor]
 6106    public SwiftSparseMap(SwiftSparseSetState<T> state)
 6107    {
 6108        State = state;
 4109    }
 110
 111    #endregion
 112
 113    #region Properties
 114
 115    [JsonIgnore]
 116    [MemoryPackIgnore]
 14117    public int Count => _count;
 118
 119    /// <summary>
 120    /// Capacity of the dense arrays (Keys/Values storage).
 121    /// </summary>
 122    [JsonIgnore]
 123    [MemoryPackIgnore]
 2124    public int DenseCapacity => _denseKeys.Length;
 125
 126    /// <summary>
 127    /// Capacity of the sparse array (max key+1 that can be mapped without resizing).
 128    /// Memory usage grows with this capacity.
 129    /// </summary>
 130    [JsonIgnore]
 131    [MemoryPackIgnore]
 3132    public int SparseCapacity => _sparse.Length;
 133
 134    [JsonIgnore]
 135    [MemoryPackIgnore]
 1136    public bool IsSynchronized => false;
 137
 138    [JsonIgnore]
 139    [MemoryPackIgnore]
 1140    public object SyncRoot => _syncRoot ??= new object();
 141
 142    /// <summary>
 143    /// Returns the dense keys array (valid range: [0..Count)).
 144    /// </summary>
 145    [JsonIgnore]
 146    [MemoryPackIgnore]
 5147    public int[] DenseKeys => _denseKeys;
 148
 149    [JsonIgnore]
 150    [MemoryPackIgnore]
 1151    public Span<int> Keys => _denseKeys.AsSpan(0, _count);
 152
 153    /// <summary>
 154    /// Returns the dense values array (valid range: [0..Count)).
 155    /// </summary>
 156    [JsonIgnore]
 157    [MemoryPackIgnore]
 4158    public T[] DenseValues => _denseValues;
 159
 160    [JsonIgnore]
 161    [MemoryPackIgnore]
 1162    public Span<T> Values => _denseValues.AsSpan(0, _count);
 163
 164    /// <summary>
 165    /// Gets/sets the value for a key. Setting:
 166    /// - overwrites if present
 167    /// - inserts if not present
 168    /// </summary>
 169    [JsonIgnore]
 170    [MemoryPackIgnore]
 171    public T this[int key]
 172    {
 173        get
 19174        {
 19175            int denseIndex = GetDenseIndexOrThrow(key);
 17176            return _denseValues[denseIndex];
 17177        }
 178        set
 40179        {
 40180            EnsureSparseCapacity(GetRequiredSparseCapacity(key));
 181
 38182            int slot = _sparse[key];
 38183            if (slot != NotPresent)
 1184            {
 185                // present -> overwrite
 1186                int denseIndex = slot - 1;
 1187                _denseValues[denseIndex] = value;
 1188                _version++;
 1189                return;
 190            }
 191
 192            // not present -> insert
 37193            EnsureDenseCapacity(_count + 1);
 194
 37195            int newIndex = _count++;
 37196            _denseKeys[newIndex] = key;
 37197            _denseValues[newIndex] = value;
 37198            _sparse[key] = newIndex + 1;
 199
 37200            _version++;
 38201        }
 202    }
 203
 204    [JsonInclude]
 205    [MemoryPackInclude]
 206    public SwiftSparseSetState<T> State
 207    {
 208        get
 4209        {
 210            // Serialize only the used portions of dense arrays
 4211            var denseKeys = new int[_count];
 4212            Array.Copy(_denseKeys, denseKeys, _count);
 213
 4214            var denseValues = new T[_count];
 4215            Array.Copy(_denseValues, denseValues, _count);
 216
 4217            return new SwiftSparseSetState<T>(denseKeys, denseValues);
 4218        }
 219        internal set
 6220        {
 6221            int n = value.DenseKeys?.Length ?? 0;
 222
 6223            if (n != (value.DenseValues?.Length ?? 0))
 1224                throw new ArgumentException("DenseKeys and DenseValues length mismatch.");
 225
 226            // Allocate dense storage
 5227            _denseKeys = n == 0 ? Array.Empty<int>() : new int[Math.Max(DefaultDenseCapacity, n)];
 5228            _denseValues = n == 0 ? Array.Empty<T>() : new T[_denseKeys.Length];
 229
 5230            if (n > 0)
 5231            {
 5232                Array.Copy(value.DenseKeys, _denseKeys, n);
 5233                Array.Copy(value.DenseValues, _denseValues, n);
 5234            }
 235
 5236            _count = n;
 237
 238            // Compute maxKey from dense keys
 5239            int maxKey = -1;
 28240            for (int i = 0; i < n; i++)
 9241            {
 9242                int key = _denseKeys[i];
 9243                if (key < 0)
 0244                    throw new ArgumentException("Key cannot be negative.");
 245
 9246                if (key > maxKey)
 8247                    maxKey = key;
 9248            }
 249
 250            // Allocate sparse map
 5251            int sparseSize = maxKey < 0
 5252                ? DefaultSparseCapacity
 5253                : Math.Max(DefaultSparseCapacity, GetRequiredSparseCapacity(maxKey));
 5254            _sparse = new int[sparseSize];
 255
 256            // Rebuild sparse lookup
 26257            for (int i = 0; i < n; i++)
 9258            {
 9259                int key = _denseKeys[i];
 260
 9261                if (_sparse[key] != NotPresent)
 1262                    throw new ArgumentException("Duplicate key in DenseKeys.");
 263
 8264                _sparse[key] = i + 1;
 8265            }
 266
 4267            _version++;
 4268        }
 269    }
 270
 271    #endregion
 272
 273    #region Core Operations
 274
 275    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 276    public bool ContainsKey(int key)
 11277    {
 12278        if ((uint)key >= (uint)_sparse.Length) return false;
 10279        return _sparse[key] != NotPresent;
 11280    }
 281
 282    /// <summary>
 283    /// Adds a key/value only if the key is not present.
 284    /// Returns false if already present.
 285    /// </summary>
 286    public bool TryAdd(int key, T value)
 2287    {
 2288        EnsureSparseCapacity(GetRequiredSparseCapacity(key));
 2289        if (_sparse[key] != NotPresent)
 1290            return false;
 291
 1292        EnsureDenseCapacity(_count + 1);
 293
 1294        int newIndex = _count++;
 1295        _denseKeys[newIndex] = key;
 1296        _denseValues[newIndex] = value;
 1297        _sparse[key] = newIndex + 1;
 298
 1299        _version++;
 1300        return true;
 2301    }
 302
 303    /// <summary>
 304    /// Adds or overwrites (same behavior as indexer set).
 305    /// </summary>
 39306    public void Add(int key, T value) => this[key] = value;
 307
 308    public bool TryGetValue(int key, out T value)
 2309    {
 2310        if ((uint)key < (uint)_sparse.Length)
 1311        {
 1312            int slot = _sparse[key];
 1313            if (slot != NotPresent)
 1314            {
 1315                value = _denseValues[slot - 1];
 1316                return true;
 317            }
 0318        }
 319
 1320        value = default;
 1321        return false;
 2322    }
 323
 324    public bool Remove(int key)
 4325    {
 5326        if ((uint)key >= (uint)_sparse.Length) return false;
 327
 3328        int slot = _sparse[key];
 3329        if (slot == NotPresent) return false;
 330
 3331        int index = slot - 1;
 3332        int last = --_count;
 333
 3334        _sparse[key] = NotPresent;
 335
 3336        if (index != last)
 1337        {
 1338            int movedKey = _denseKeys[last];
 339
 1340            _denseKeys[index] = movedKey;
 1341            _denseValues[index] = _denseValues[last];
 342
 1343            _sparse[movedKey] = index + 1;
 1344        }
 345
 3346        _denseKeys[last] = default;
 3347        _denseValues[last] = default;
 348
 3349        _version++;
 3350        return true;
 4351    }
 352
 353    public void Clear()
 5354    {
 7355        if (_count == 0) return;
 356
 357        // reset sparse for keys that were present
 14358        for (int i = 0; i < _count; i++)
 4359        {
 4360            int key = _denseKeys[i];
 4361            if ((uint)key < (uint)_sparse.Length)
 4362                _sparse[key] = NotPresent;
 4363        }
 364
 3365        Array.Clear(_denseKeys, 0, _count);
 3366        Array.Clear(_denseValues, 0, _count);
 367
 3368        _count = 0;
 3369        _version++;
 5370    }
 371
 372    #endregion
 373
 374    #region Capacity Management
 375
 376    public void EnsureDenseCapacity(int capacity)
 39377    {
 77378        if (capacity <= _denseKeys.Length) return;
 379
 1380        int newCap = _denseKeys.Length == 0 ? DefaultDenseCapacity : _denseKeys.Length * 2;
 2381        if (newCap < capacity) newCap = capacity;
 382
 1383        newCap = SwiftHashTools.NextPowerOfTwo(newCap);
 384
 1385        var newKeys = new int[newCap];
 1386        var newVals = new T[newCap];
 387
 1388        if (_count > 0)
 0389        {
 0390            Array.Copy(_denseKeys, newKeys, _count);
 0391            Array.Copy(_denseValues, newVals, _count);
 0392        }
 393
 1394        _denseKeys = newKeys;
 1395        _denseValues = newVals;
 396
 1397        _version++;
 39398    }
 399
 400    public void EnsureSparseCapacity(int capacity)
 41401    {
 78402        if (capacity <= _sparse.Length) return;
 403
 4404        int newCap = _sparse.Length == 0
 4405            ? DefaultSparseCapacity
 4406            : _sparse.Length * 2;
 7407        if (newCap < capacity) newCap = capacity;
 408
 4409        newCap = SwiftHashTools.NextPowerOfTwo(newCap);
 410
 4411        var newSparse = new int[newCap];
 4412        if (_sparse.Length > 0)
 4413            Array.Copy(_sparse, newSparse, _sparse.Length);
 414
 4415        _sparse = newSparse;
 4416        _version++;
 41417    }
 418
 419    public void TrimExcess()
 1420    {
 421        // Dense: shrink to Count (with a minimum)
 1422        int newDense = Math.Max(DefaultDenseCapacity, _count);
 1423        if (newDense < _denseKeys.Length)
 1424        {
 1425            var newKeys = new int[newDense];
 1426            var newVals = new T[newDense];
 1427            if (_count > 0)
 1428            {
 1429                Array.Copy(_denseKeys, newKeys, _count);
 1430                Array.Copy(_denseValues, newVals, _count);
 1431            }
 1432            _denseKeys = newKeys;
 1433            _denseValues = newVals;
 1434        }
 435
 436        // Sparse: shrink to (maxKey+1) based on dense keys
 1437        int maxKey = -1;
 4438        for (int i = 0; i < _count; i++)
 2439            if (_denseKeys[i] > maxKey) maxKey = _denseKeys[i];
 440
 1441        int newSparse = maxKey < 0
 1442            ? DefaultSparseCapacity
 1443            : Math.Max(DefaultSparseCapacity, GetRequiredSparseCapacity(maxKey));
 1444        if (newSparse < _sparse.Length)
 1445        {
 1446            var newMap = new int[newSparse];
 447            // rebuild from dense
 4448            for (int i = 0; i < _count; i++)
 1449                newMap[_denseKeys[i]] = i + 1;
 1450            _sparse = newMap;
 1451        }
 452
 1453        _version++;
 1454    }
 455
 456    #endregion
 457
 458    #region Enumeration
 459
 8460    public Enumerator GetEnumerator() => new Enumerator(this);
 5461    IEnumerator<KeyValuePair<int, T>> IEnumerable<KeyValuePair<int, T>>.GetEnumerator() => GetEnumerator();
 1462    IEnumerator IEnumerable.GetEnumerator() => GetEnumerator();
 463
 464    public struct Enumerator : IEnumerator<KeyValuePair<int, T>>
 465    {
 466        private readonly SwiftSparseMap<T> _set;
 467        private readonly int[] _keys;
 468        private readonly T[] _values;
 469        private readonly int _count;
 470        private readonly uint _version;
 471        private int _index;
 472
 473        internal Enumerator(SwiftSparseMap<T> set)
 8474        {
 8475            _set = set;
 8476            _keys = set._denseKeys;
 8477            _values = set._denseValues;
 8478            _count = set._count;
 8479            _version = set._version;
 8480            _index = -1;
 8481            Current = default;
 8482        }
 483
 24484        public KeyValuePair<int, T> Current { get; private set; }
 1485        object IEnumerator.Current => Current;
 486
 487        public bool MoveNext()
 11488        {
 11489            if (_version != _set._version)
 1490                throw new InvalidOperationException("Collection was modified during enumeration.");
 491
 10492            int next = _index + 1;
 10493            if (next >= _count)
 5494            {
 5495                Current = default;
 5496                return false;
 497            }
 498
 5499            _index = next;
 5500            Current = new KeyValuePair<int, T>(_keys[_index], _values[_index]);
 5501            return true;
 10502        }
 503
 504        public void Reset()
 1505        {
 1506            if (_version != _set._version)
 0507                throw new InvalidOperationException("Collection was modified during enumeration.");
 1508            _index = -1;
 1509            Current = default;
 1510        }
 511
 10512        public void Dispose() { }
 513    }
 514
 515    #endregion
 516
 517    #region Helpers
 518
 519    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 520    public void GetDense(out int[] keys, out T[] values, out int count)
 1521    {
 1522        keys = _denseKeys;
 1523        values = _denseValues;
 1524        count = _count;
 1525    }
 526
 527    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 528    private static int GetRequiredSparseCapacity(int key)
 48529    {
 48530        if (key < 0)
 1531            throw new ArgumentOutOfRangeException(nameof(key), "Key must be non-negative.");
 532
 47533        if (key == int.MaxValue)
 1534            throw new ArgumentOutOfRangeException(nameof(key), "Key is too large for direct sparse indexing.");
 535
 46536        return key + 1;
 46537    }
 538
 539    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 540    private int GetDenseIndexOrThrow(int key)
 19541    {
 19542        if ((uint)key >= (uint)_sparse.Length)
 1543           throw new KeyNotFoundException($"Key not found: {key}");
 544
 18545        int slot = _sparse[key];
 18546        if (slot == NotPresent)
 1547            throw new KeyNotFoundException($"Key not found: {key}");
 548
 17549        return slot - 1;
 17550    }
 551
 552    public void CloneTo(ICollection<T> output)
 1553    {
 1554        SwiftThrowHelper.ThrowIfNull(output, nameof(output));
 555
 1556        output.Clear();
 557
 6558        for (int i = 0; i < _count; i++)
 2559            output.Add(_denseValues[i]);
 1560    }
 561
 562    #endregion
 563}
Generated by: ReportGenerator 5.5.4.0
04/03/2026 - 18:03:54
GitHub | reportgenerator.io

Methods/Properties

.ctor()
.ctor(System.Int32,System.Int32)
.ctor(SwiftCollections.SwiftSparseSetState`1<T>)
get_Count()
get_DenseCapacity()
get_SparseCapacity()
get_IsSynchronized()
get_SyncRoot()
get_DenseKeys()
get_Keys()
get_DenseValues()
get_Values()
get_Item(System.Int32)
set_Item(System.Int32,T)
get_State()
set_State(SwiftCollections.SwiftSparseSetState`1<T>)
ContainsKey(System.Int32)
TryAdd(System.Int32,T)
Add(System.Int32,T)
TryGetValue(System.Int32,T&)
Remove(System.Int32)
Clear()
EnsureDenseCapacity(System.Int32)
EnsureSparseCapacity(System.Int32)
TrimExcess()
GetEnumerator()
System.Collections.Generic.IEnumerable<System.Collections.Generic.KeyValuePair<System.Int32,T>>.GetEnumerator()
System.Collections.IEnumerable.GetEnumerator()
.ctor(SwiftCollections.SwiftSparseMap`1<T>)
get_Current()
System.Collections.IEnumerator.get_Current()
MoveNext()
Reset()
Dispose()
GetDense(System.Int32[]&,T[]&,System.Int32&)
GetRequiredSparseCapacity(System.Int32)
GetDenseIndexOrThrow(System.Int32)
CloneTo(System.Collections.Generic.ICollection`1<T>)