< Summary

Information
Class: SwiftCollections.SwiftSparseMap<T>
Assembly: SwiftCollections
File(s): File 1: /home/runner/work/SwiftCollections/SwiftCollections/src/SwiftCollections/Collection/SwiftSparseMap.cs
File 2: /home/runner/work/SwiftCollections/SwiftCollections/src/SwiftCollections/Collection/SwiftSparseMap.SwiftSparseMapEnumerator.cs
Line coverage
100%
Covered lines: 224
Uncovered lines: 0
Coverable lines: 224
Total lines: 784
Line coverage: 100%
Branch coverage
100%
Covered branches: 84
Total branches: 84
Branch coverage: 100%
Method coverage

Feature is only available for sponsors

Upgrade to PRO version

Metrics

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

File(s)

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

#LineLine coverage
 1//=======================================================================
 2// SwiftSparseMap.cs
 3//=======================================================================
 4// MIT License, Copyright (c) 2024-present David Oravsky (mrdav30)
 5// See LICENSE file in the project root for full license information.
 6//=======================================================================
 7
 8using System;
 9using System.Collections;
 10using System.Collections.Generic;
 11using System.Runtime.CompilerServices;
 12using System.Text.Json.Serialization;
 13using Chronicler;
 14using Chronicler.Diagnostics;
 15using Chronicler.Serialization;
 16using MemoryPack;
 17using SwiftCollections.Utility;
 18
 19namespace SwiftCollections;
 20
 21/// <summary>
 22/// Represents a high-performance sparse map that stores values indexed by externally supplied integer keys.
 23/// Provides O(1) Add, Remove, Contains, and lookup operations while maintaining densely packed storage
 24/// for cache-friendly iteration.
 25/// </summary>
 26/// <remarks>
 27/// Unlike <see cref="SwiftSlotMap{T}"/>, which internally assigns and manages item indices,
 28/// <see cref="SwiftSparseMap{T}"/> is externally keyed. The caller supplies the integer key
 29/// (for example, an entity ID or handle) used to index the value.
 30///
 31/// Internally, the container maintains:
 32/// <list type="bullet">
 33///     <item>
 34///         <description>A sparse lookup table mapping keys to dense indices.</description>
 35///     </item>
 36///     <item>
 37///         <description>A dense array of keys.</description>
 38///     </item>
 39///     <item>
 40///         <description>A dense array of values.</description>
 41///     </item>
 42/// </list>
 43///
 44/// Removal uses a swap-back strategy to keep dense storage contiguous. As a result,
 45/// iteration order is not guaranteed to remain stable.
 46///
 47/// Keys are used as direct indices into the sparse lookup table, so memory usage scales
 48/// with the highest stored key rather than the number of stored values. This container is
 49/// intended for compact, non-negative IDs such as entity handles or slot indices. It is
 50/// not a good fit for arbitrary hashes or widely spaced keys; for those workloads prefer
 51/// <c>SwiftDictionary&lt;TKey, TValue&gt;</c>.
 52/// </remarks>
 53/// <typeparam name="T">Value type stored by key.</typeparam>
 54[Serializable]
 55[JsonConverter(typeof(StateJsonConverterFactory))]
 56[MemoryPackable]
 57public sealed partial class SwiftSparseMap<T> : IStateBacked<SwiftSparseMapState<T>>, ISwiftCloneable<T>, IEnumerable<Ke
 58{
 59    #region Constants
 60
 61    /// <summary>
 62    /// Represents the default initial capacity for dense collections.
 63    /// </summary>
 64    public const int DefaultDenseCapacity = 8;
 65
 66    /// <summary>
 67    /// Represents the default initial capacity for sparse collections.
 68    /// </summary>
 69    public const int DefaultSparseCapacity = 8;
 70
 71    /// <summary>
 72    /// Represents the value used to indicate that a key is not present in the sparse array.
 73    /// </summary>
 74    /// <remarks>
 75    /// A value of 0 signifies that the key is absent.
 76    /// When a key is present, the stored value is the dense index plus one.
 77    /// </remarks>
 78    private const int NotPresent = 0;
 79
 80    #endregion
 81
 82    #region Fields
 83
 84    private int[] _sparse;       // key -> denseIndex+1
 85    private int[] _denseKeys;    // denseIndex -> key
 86    private T[] _denseValues;    // denseIndex -> value
 87    private int _count;
 88
 89    [NonSerialized]
 90    private uint _version;
 91
 92    [NonSerialized]
 93    private object? _syncRoot;
 94
 95    #endregion
 96
 97    #region Constructors
 98
 99    /// <summary>
 100    /// Initializes a new instance of the SwiftSparseMap class with default sparse and dense capacities.
 101    /// </summary>
 118102    public SwiftSparseMap() : this(DefaultSparseCapacity, DefaultDenseCapacity) { }
 103
 104    /// <summary>
 105    /// Initializes a new sparse map with the specified sparse and dense capacities.
 106    /// </summary>
 107    /// <param name="sparseCapacity">
 108    /// Initial sparse lookup capacity. This should track the highest expected key plus one,
 109    /// not the number of stored values.
 110    /// </param>
 111    /// <param name="denseCapacity">Initial dense storage capacity for values.</param>
 65112    public SwiftSparseMap(int sparseCapacity, int denseCapacity)
 113    {
 65114        ChronicleGuard.ThrowIfNegative(sparseCapacity, nameof(sparseCapacity));
 65115        ChronicleGuard.ThrowIfNegative(denseCapacity, nameof(denseCapacity));
 116
 65117        int sparseSize = sparseCapacity == 0 ? 0 : SwiftHashTools.NextPowerOfTwo(sparseCapacity);
 65118        _sparse = sparseCapacity == 0
 65119            ? Array.Empty<int>()
 65120            : new int[sparseSize];
 65121        int denseSize = denseCapacity < DefaultDenseCapacity
 65122            ? DefaultDenseCapacity
 65123            : SwiftHashTools.NextPowerOfTwo(denseCapacity);
 65124        _denseKeys = denseCapacity == 0
 65125            ? Array.Empty<int>()
 65126            : new int[denseSize];
 65127        _denseValues = _denseKeys.Length == 0 ? Array.Empty<T>() : new T[_denseKeys.Length];
 128
 65129        _count = 0;
 65130    }
 131
 132    /// <summary>
 133    /// Initializes a new instance of the SwiftSparseMap class using the specified state.
 134    /// </summary>
 135    /// <param name="state">The state object that provides the initial configuration and data for the map. Cannot be nul
 136    [MemoryPackConstructor]
 7137    public SwiftSparseMap(SwiftSparseMapState<T> state)
 138    {
 7139        _sparse = Array.Empty<int>();
 7140        _denseKeys = Array.Empty<int>();
 7141        _denseValues = Array.Empty<T>();
 142
 7143        State = state;
 5144    }
 145
 146    #endregion
 147
 148    #region Properties
 149
 150    /// <summary>
 151    /// Gets the number of elements contained in the collection.
 152    /// </summary>
 153    [JsonIgnore]
 154    [MemoryPackIgnore]
 15155    public int Count => _count;
 156
 157    /// <summary>
 158    /// Capacity of the dense arrays (Keys/Values storage).
 159    /// </summary>
 160    [JsonIgnore]
 161    [MemoryPackIgnore]
 7162    public int DenseCapacity => _denseKeys.Length;
 163
 164    /// <summary>
 165    /// Capacity of the sparse array (max key+1 that can be mapped without resizing).
 166    /// Memory usage grows with this capacity.
 167    /// </summary>
 168    [JsonIgnore]
 169    [MemoryPackIgnore]
 8170    public int SparseCapacity => _sparse.Length;
 171
 172    /// <summary>
 173    /// Gets a value indicating whether access to the collection is synchronized (thread safe).
 174    /// </summary>
 175    [JsonIgnore]
 176    [MemoryPackIgnore]
 1177    public bool IsSynchronized => false;
 178
 179    /// <summary>
 180    /// Gets an object that can be used to synchronize access to the collection.
 181    /// </summary>
 182    /// <remarks>
 183    /// Use this object to lock the collection during multithreaded operations to ensure thread safety.
 184    /// The returned object is unique to this collection instance.
 185    /// </remarks>
 186    [JsonIgnore]
 187    [MemoryPackIgnore]
 3188    public object SyncRoot => _syncRoot ??= new object();
 189
 190    /// <summary>
 191    /// Returns the dense keys array (valid range: [0..Count)).
 192    /// </summary>
 193    /// <remarks>
 194    /// Prefer collection APIs. Direct key mutation must preserve the dense/sparse lookup invariants; invalid edits may 
 195    /// </remarks>
 196    [JsonIgnore]
 197    [MemoryPackIgnore]
 6198    public int[] DenseKeys => _denseKeys;
 199
 200    /// <summary>
 201    /// Gets a span containing the keys currently stored in the collection.
 202    /// </summary>
 203    /// <remarks>
 204    /// The returned span provides a view of the underlying key data and reflects the current state of the collection.
 205    /// Prefer collection APIs. Direct key mutation must preserve the dense/sparse lookup invariants; invalid edits may 
 206    /// The span is only valid as long as the underlying collection is not modified.
 207    /// </remarks>
 208    [JsonIgnore]
 209    [MemoryPackIgnore]
 1210    public Span<int> Keys => _denseKeys.AsSpan(0, _count);
 211
 212    /// <summary>
 213    /// Returns the dense values array (valid range: [0..Count)).
 214    /// </summary>
 215    [JsonIgnore]
 216    [MemoryPackIgnore]
 7217    public T[] DenseValues => _denseValues;
 218
 219    /// <summary>
 220    /// Gets a span containing the current values in the collection.
 221    /// </summary>
 222    /// <remarks>
 223    /// The returned span reflects the live contents of the collection up to the current count.
 224    /// Modifying the span will update the underlying collection data.
 225    /// The span length is equal to the number of elements currently stored.
 226    /// </remarks>
 227    [JsonIgnore]
 228    [MemoryPackIgnore]
 1229    public Span<T> Values => _denseValues.AsSpan(0, _count);
 230
 231    /// <summary>
 232    /// Gets/sets the value for a key. Setting:
 233    /// - overwrites if present
 234    /// - inserts if not present
 235    /// </summary>
 236    [JsonIgnore]
 237    [MemoryPackIgnore]
 238    public T this[int key]
 239    {
 240        get
 241        {
 26242            int denseIndex = GetDenseIndexOrThrow(key);
 23243            return _denseValues[denseIndex];
 244        }
 245        set
 246        {
 217247            EnsureSparseCapacity(GetRequiredSparseCapacity(key));
 248
 215249            int slot = _sparse[key];
 215250            if (slot != NotPresent)
 251            {
 252                // present -> overwrite
 1253                int denseIndex = slot - 1;
 1254                _denseValues[denseIndex] = value;
 1255                _version++;
 1256                return;
 257            }
 258
 259            // not present -> insert
 214260            EnsureDenseCapacity(_count + 1);
 261
 214262            int newIndex = _count++;
 214263            _denseKeys[newIndex] = key;
 214264            _denseValues[newIndex] = value;
 214265            _sparse[key] = newIndex + 1;
 266
 214267            _version++;
 214268        }
 269    }
 270
 271    /// <summary>
 272    /// Gets or sets the current state of the sparse map, including the used dense keys and values.
 273    /// </summary>
 274    /// <remarks>
 275    /// The state includes only the active elements in the map.
 276    /// Setting this property replaces the current contents with the provided state.
 277    /// The setter is intended for internal use, such as serialization or deserialization scenarios.
 278    /// </remarks>
 279    [JsonInclude]
 280    [MemoryPackInclude]
 281    public SwiftSparseMapState<T> State
 282    {
 283        get
 284        {
 285            // Serialize only the used portions of dense arrays
 4286            var denseKeys = new int[_count];
 4287            Array.Copy(_denseKeys, denseKeys, _count);
 288
 4289            var denseValues = new T[_count];
 4290            Array.Copy(_denseValues, denseValues, _count);
 291
 4292            return new SwiftSparseMapState<T>(denseKeys, denseValues);
 293        }
 294        internal set
 295        {
 7296            ChronicleGuard.ThrowIfNull(value.DenseKeys);
 7297            ChronicleGuard.ThrowIfNull(value.DenseValues);
 298
 7299            int n = value.DenseKeys.Length;
 300
 7301            ChronicleGuard.ThrowIfArgument(n != value.DenseValues.Length, nameof(value), "DenseKeys and DenseValues leng
 302
 303            // Allocate dense storage
 6304            _denseKeys = n == 0 ? Array.Empty<int>() : new int[Math.Max(DefaultDenseCapacity, n)];
 6305            _denseValues = n == 0 ? Array.Empty<T>() : new T[_denseKeys.Length];
 306
 6307            if (n > 0)
 308            {
 5309                Array.Copy(value.DenseKeys, _denseKeys, n);
 5310                Array.Copy(value.DenseValues, _denseValues, n);
 311            }
 312
 6313            _count = n;
 314
 315            // Compute maxKey from dense keys
 6316            int maxKey = -1;
 30317            for (int i = 0; i < n; i++)
 318            {
 9319                int key = _denseKeys[i];
 9320                ChronicleGuard.ThrowIfArgument(key < 0, nameof(value), "Key cannot be negative.");
 321
 9322                if (key > maxKey)
 8323                    maxKey = key;
 324            }
 325
 326            // Allocate sparse map
 6327            int sparseSize = maxKey < 0
 6328                ? DefaultSparseCapacity
 6329                : Math.Max(DefaultSparseCapacity, GetRequiredSparseCapacity(maxKey));
 6330            _sparse = new int[sparseSize];
 331
 332            // Rebuild sparse lookup
 28333            for (int i = 0; i < n; i++)
 334            {
 9335                int key = _denseKeys[i];
 336
 9337                ChronicleGuard.ThrowIfArgument(_sparse[key] != NotPresent, nameof(value), "Duplicate key in DenseKeys.")
 338
 8339                _sparse[key] = i + 1;
 340            }
 341
 5342            _version++;
 5343        }
 344    }
 345
 346    #endregion
 347
 348    #region Core Operations
 349
 350    /// <summary>
 351    /// Determines whether the collection contains the specified key.
 352    /// </summary>
 353    /// <param name="key">The key to locate in the collection.</param>
 354    /// <returns>true if the collection contains an element with the specified key; otherwise, false.</returns>
 355    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 356    public bool ContainsKey(int key)
 357    {
 14358        if ((uint)key >= (uint)_sparse.Length) return false;
 12359        return _sparse[key] != NotPresent;
 360    }
 361
 362    /// <summary>
 363    /// Adds a key/value only if the key is not present.
 364    /// Returns false if already present.
 365    /// </summary>
 366    public bool TryAdd(int key, T value)
 367    {
 2368        EnsureSparseCapacity(GetRequiredSparseCapacity(key));
 2369        if (_sparse[key] != NotPresent)
 1370            return false;
 371
 1372        EnsureDenseCapacity(_count + 1);
 373
 1374        int newIndex = _count++;
 1375        _denseKeys[newIndex] = key;
 1376        _denseValues[newIndex] = value;
 1377        _sparse[key] = newIndex + 1;
 378
 1379        _version++;
 1380        return true;
 381    }
 382
 383    /// <summary>
 384    /// Adds or overwrites (same behavior as indexer set).
 385    /// </summary>
 216386    public void Add(int key, T value) => this[key] = value;
 387
 388    /// <summary>
 389    /// Attempts to retrieve the value associated with the specified key.
 390    /// </summary>
 391    /// <param name="key">The key whose associated value is to be retrieved.</param>
 392    /// <param name="value">
 393    /// When this method returns, contains the value associated with the specified key, if the key is found;
 394    /// otherwise, the default value for the type parameter <typeparamref name="T"/>.
 395    /// This parameter is passed uninitialized.
 396    /// </param>
 397    /// <returns>true if the key was found and its value was retrieved; otherwise, false.</returns>
 398    public bool TryGetValue(int key, out T value)
 399    {
 3400        if ((uint)key < (uint)_sparse.Length)
 401        {
 2402            int slot = _sparse[key];
 2403            if (slot != NotPresent)
 404            {
 1405                value = _denseValues[slot - 1];
 1406                return true;
 407            }
 408        }
 409
 2410        value = default!;
 2411        return false;
 412    }
 413
 414    /// <summary>
 415    /// Removes the element with the specified key from the collection, if it exists.
 416    /// </summary>
 417    /// <param name="key">The key of the element to remove. Must be a non-negative integer within the valid range of key
 418    /// <returns>true if the element is successfully found and removed; otherwise, false.</returns>
 419    public bool Remove(int key)
 420    {
 8421        if ((uint)key >= (uint)_sparse.Length) return false;
 422
 6423        int slot = _sparse[key];
 7424        if (slot == NotPresent) return false;
 425
 5426        int index = slot - 1;
 5427        int last = --_count;
 428
 5429        _sparse[key] = NotPresent;
 430
 5431        if (index != last)
 432        {
 3433            int movedKey = _denseKeys[last];
 434
 3435            _denseKeys[index] = movedKey;
 3436            _denseValues[index] = _denseValues[last];
 437
 3438            _sparse[movedKey] = index + 1;
 439        }
 440
 5441        _denseKeys[last] = default;
 5442        _denseValues[last] = default!;
 443
 5444        _version++;
 5445        return true;
 446    }
 447
 448    /// <summary>
 449    /// Removes all keys and values from the collection.
 450    /// </summary>
 451    /// <remarks>
 452    /// After calling this method, the collection will be empty and its Count property will be zero.
 453    /// This method does not reduce the capacity of the underlying storage.
 454    /// </remarks>
 455    public void Clear()
 456    {
 147457        if (_count == 0) return;
 458
 459        // reset sparse for keys that were present
 542460        for (int i = 0; i < _count; i++)
 461        {
 136462            int key = _denseKeys[i];
 136463            _sparse[key] = NotPresent;
 464        }
 465
 135466        Array.Clear(_denseKeys, 0, _count);
 135467        Array.Clear(_denseValues, 0, _count);
 468
 135469        _count = 0;
 135470        _version++;
 135471    }
 472
 473    /// <summary>
 474    /// Removes all elements, optionally releasing references throughout retained backing storage.
 475    /// </summary>
 476    /// <param name="clearRetainedReferences">If true, also releases references outside the live range; otherwise uses o
 477    /// <remarks>Capacity is preserved. Full reference cleanup can take time proportional to retained capacity.</remarks
 478    public void Clear(bool clearRetainedReferences)
 479    {
 136480        if (clearRetainedReferences && RuntimeHelpers.IsReferenceOrContainsReferences<T>())
 131481            Array.Clear(_denseValues, _count, _denseValues.Length - _count);
 136482        Clear();
 136483    }
 484
 485    #endregion
 486
 487    #region Capacity Management
 488
 489    /// <summary>
 490    /// Ensures that the internal dense storage has at least the specified capacity, expanding it if necessary.
 491    /// </summary>
 492    /// <remarks>
 493    /// If the current capacity is less than the specified value, the internal storage is resized to accommodate at leas
 494    /// Existing elements are preserved.
 495    /// The capacity is increased to the next power of two greater than or equal to the requested capacity for performan
 496    /// </remarks>
 497    /// <param name="capacity">The minimum number of elements that the dense storage must be able to hold. Must be non-n
 498    public void EnsureDenseCapacity(int capacity)
 499    {
 433500        if (capacity <= _denseKeys.Length) return;
 501
 3502        int newCap = _denseKeys.Length == 0 ? DefaultDenseCapacity : _denseKeys.Length * 2;
 5503        if (newCap < capacity) newCap = capacity;
 504
 3505        newCap = SwiftHashTools.NextPowerOfTwo(newCap);
 506
 3507        var newKeys = new int[newCap];
 3508        var newVals = new T[newCap];
 509
 3510        if (_count > 0)
 511        {
 1512            Array.Copy(_denseKeys, newKeys, _count);
 1513            Array.Copy(_denseValues, newVals, _count);
 514        }
 515
 3516        _denseKeys = newKeys;
 3517        _denseValues = newVals;
 518
 3519        _version++;
 3520    }
 521
 522    /// <summary>
 523    /// Ensures that the internal sparse array has a capacity at least as large as the specified value.
 524    /// </summary>
 525    /// <remarks>
 526    /// If the current capacity is less than the specified value, the internal storage is resized to accommodate at leas
 527    /// Existing elements are preserved.
 528    /// The capacity is increased to the next power of two greater than or equal to the requested capacity for performan
 529    /// </remarks>
 530    /// <param name="capacity">The minimum required capacity for the internal sparse array. Must be non-negative.</param
 531    public void EnsureSparseCapacity(int capacity)
 532    {
 421533        if (capacity <= _sparse.Length) return;
 534
 17535        int newCap = _sparse.Length == 0
 17536            ? DefaultSparseCapacity
 17537            : _sparse.Length * 2;
 23538        if (newCap < capacity) newCap = capacity;
 539
 17540        newCap = SwiftHashTools.NextPowerOfTwo(newCap);
 541
 17542        var newSparse = new int[newCap];
 17543        if (_sparse.Length > 0)
 16544            Array.Copy(_sparse, newSparse, _sparse.Length);
 545
 17546        _sparse = newSparse;
 17547        _version++;
 17548    }
 549
 550    /// <summary>
 551    /// Reduces the memory usage of the collection by resizing internal storage to fit the current number of elements as
 552    /// </summary>
 553    /// <remarks>
 554    /// Call this method to minimize the collection's memory footprint after removing a significant number of elements.
 555    /// This operation may improve memory efficiency but can be an expensive operation if the collection is large.
 556    /// The method does not affect the logical contents of the collection.
 557    /// </remarks>
 558    public void TrimExcess()
 559    {
 560        // Dense: shrink to Count (with a minimum)
 4561        int newDense = Math.Max(DefaultDenseCapacity, _count);
 4562        if (newDense < _denseKeys.Length)
 563        {
 3564            var newKeys = new int[newDense];
 3565            var newVals = new T[newDense];
 3566            if (_count > 0)
 567            {
 2568                Array.Copy(_denseKeys, newKeys, _count);
 2569                Array.Copy(_denseValues, newVals, _count);
 570            }
 3571            _denseKeys = newKeys;
 3572            _denseValues = newVals;
 573        }
 574
 575        // Sparse: shrink to (maxKey+1) based on dense keys
 4576        int maxKey = -1;
 18577        for (int i = 0; i < _count; i++)
 8578            if (_denseKeys[i] > maxKey) maxKey = _denseKeys[i];
 579
 4580        int newSparse = maxKey < 0
 4581            ? DefaultSparseCapacity
 4582            : Math.Max(DefaultSparseCapacity, GetRequiredSparseCapacity(maxKey));
 4583        if (newSparse < _sparse.Length)
 584        {
 3585            var newMap = new int[newSparse];
 586            // rebuild from dense
 12587            for (int i = 0; i < _count; i++)
 3588                newMap[_denseKeys[i]] = i + 1;
 3589            _sparse = newMap;
 590        }
 591
 4592        _version++;
 4593    }
 594
 595    #endregion
 596
 597    #region Enumeration
 598
 599    /// <inheritdoc cref="IEnumerable.GetEnumerator()"/>
 50600    public SwiftSparseMapEnumerator GetEnumerator() => new(this);
 29601    IEnumerator<KeyValuePair<int, T>> IEnumerable<KeyValuePair<int, T>>.GetEnumerator() => GetEnumerator();
 19602    IEnumerator IEnumerable.GetEnumerator() => GetEnumerator();
 603
 604
 605
 606    #endregion
 607
 608    #region Helpers
 609
 610    /// <summary>
 611    /// Retrieves the dense representation of the collection as parallel arrays of keys and values, along with the numbe
 612    /// </summary>
 613    /// <remarks>
 614    /// The arrays returned may be larger than the actual number of elements.
 615    /// Only the first <paramref name="count"/> entries in each array are valid and should be used.
 616    /// </remarks>
 617    /// <param name="keys">
 618    /// When this method returns, contains an array of keys representing the dense mapping.
 619    /// The array length is at least as large as the number of elements returned in <paramref name="count"/>.
 620    /// </param>
 621    /// <param name="values">
 622    /// When this method returns, contains an array of values corresponding to the keys in <paramref name="keys"/>.
 623    /// The array length is at least as large as the number of elements returned in <paramref name="count"/>.
 624    /// </param>
 625    /// <param name="count">When this method returns, contains the number of valid key-value pairs in the dense arrays.<
 626    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 627    public void GetDense(out int[] keys, out T[] values, out int count)
 628    {
 1629        keys = _denseKeys;
 1630        values = _denseValues;
 1631        count = _count;
 1632    }
 633
 634    /// <summary>
 635    /// Replaces the destination list contents with this map's keys in dense iteration order.
 636    /// </summary>
 637    /// <remarks>
 638    /// The destination list is reused and only grows when its current capacity is smaller than
 639    /// <see cref="Count"/>. Use <see cref="CopySortedKeysTo(SwiftList{int})"/> when stable ascending
 640    /// key order is required.
 641    /// </remarks>
 642    /// <param name="destination">The caller-owned list that receives the keys.</param>
 643    public void CopyKeysTo(SwiftList<int> destination)
 644    {
 4645        ChronicleGuard.ThrowIfNull(destination, nameof(destination));
 646
 4647        destination.FastClear();
 4648        destination.AddRange(_denseKeys.AsSpan(0, _count));
 4649    }
 650
 651    /// <summary>
 652    /// Replaces the destination list contents with this map's keys sorted in ascending order.
 653    /// </summary>
 654    /// <remarks>
 655    /// This method is intended for reusable hot-path scratch buffers that need deterministic key order
 656    /// without constructing a persistent sorted collection.
 657    /// </remarks>
 658    /// <param name="destination">The caller-owned list that receives the sorted keys.</param>
 659    public void CopySortedKeysTo(SwiftList<int> destination)
 660    {
 3661        CopyKeysTo(destination);
 3662        destination.SortInPlace(default(SwiftIntAscendingComparer));
 3663    }
 664
 665    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 666    private static int GetRequiredSparseCapacity(int key)
 667    {
 227668        ChronicleGuard.ThrowIfNegative(key, nameof(key));
 226669        ChronicleGuard.ThrowIfArgumentOutOfRange(key == int.MaxValue, key, nameof(key), "Key is too large for direct spa
 670
 225671        return key + 1;
 672    }
 673
 674    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 675    private int GetDenseIndexOrThrow(int key)
 676    {
 26677        ChronicleGuard.ThrowIfKeyNotFound((uint)key >= (uint)_sparse.Length, key);
 678
 24679        int slot = _sparse[key];
 680
 24681        ChronicleGuard.ThrowIfKeyNotFound(slot == NotPresent, key);
 682
 23683        return slot - 1;
 684    }
 685
 686    /// <inheritdoc/>
 687    public void CloneTo(ICollection<T> output)
 688    {
 1689        ChronicleGuard.ThrowIfNull(output, nameof(output));
 690
 1691        output.Clear();
 692
 6693        for (int i = 0; i < _count; i++)
 2694            output.Add(_denseValues[i]);
 1695    }
 696
 697    #endregion
 698}

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

#LineLine coverage
 1//=======================================================================
 2// SwiftSparseMap.SwiftSparseMapEnumerator.cs
 3//=======================================================================
 4// MIT License, Copyright (c) 2024-present David Oravsky (mrdav30)
 5// See LICENSE file in the project root for full license information.
 6//=======================================================================
 7
 8
 9using System.Collections;
 10using System.Collections.Generic;
 11using Chronicler.Diagnostics;
 12
 13namespace SwiftCollections;
 14
 15public sealed partial class SwiftSparseMap<T>
 16{
 17    /// <summary>
 18    /// Supports iteration over the key/value pairs in a <see cref="SwiftSparseMap{T}"/> collection.
 19    /// </summary>
 20    /// <remarks>
 21    /// The enumerator provides a forward-only, read-only traversal of the collection.
 22    /// It is invalidated if the underlying collection is modified during enumeration, and any such modification will ca
 23    /// subsequent operations to throw an InvalidOperationException.
 24    /// </remarks>
 25    public struct SwiftSparseMapEnumerator : IEnumerator<KeyValuePair<int, T>>
 26    {
 27        private readonly SwiftSparseMap<T> _map;
 28        private readonly int[] _keys;
 29        private readonly T[] _values;
 30        private readonly int _count;
 31        private readonly uint _version;
 32        private int _index;
 33
 34        internal SwiftSparseMapEnumerator(SwiftSparseMap<T> map)
 35        {
 5036            _map = map;
 5037            _keys = map._denseKeys;
 5038            _values = map._denseValues;
 5039            _count = map._count;
 5040            _version = map._version;
 5041            _index = -1;
 5042            Current = default;
 5043        }
 44
 45        /// <inheritdoc/>
 46        public KeyValuePair<int, T> Current { get; private set; }
 47        object IEnumerator.Current
 48        {
 49            get
 50            {
 3151                ChronicleGuard.ThrowIfTrue((uint)_index >= (uint)_count, message: "Enumerator is before the first elemen
 1352                return Current;
 53            }
 54        }
 55
 56        /// <inheritdoc/>
 57        public bool MoveNext()
 58        {
 9959            ChronicleGuard.ThrowIfTrue(_version != _map._version, message: "Collection was modified during enumeration."
 60
 9561            int next = _index + 1;
 9562            if (next >= _count)
 63            {
 4564                _index = _count;
 4565                Current = default;
 4566                return false;
 67            }
 68
 5069            _index = next;
 5070            Current = new KeyValuePair<int, T>(_keys[_index], _values[_index]);
 5071            return true;
 72        }
 73
 74        /// <inheritdoc/>
 75        public void Reset()
 76        {
 1077            ChronicleGuard.ThrowIfTrue(_version != _map._version, message: "Collection was modified during enumeration."
 78
 779            _index = -1;
 780            Current = default;
 781        }
 82
 83        /// <inheritdoc/>
 3284        public void Dispose() => _index = -1;
 85    }
 86}
Generated by: ReportGenerator 5.5.12.0
11/05/2026 - 04:17:34
GitHub | reportgenerator.io

Methods/Properties

.ctor()
.ctor(System.Int32,System.Int32)
.ctor(SwiftCollections.SwiftSparseMapState`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.SwiftSparseMapState`1<T>)
ContainsKey(System.Int32)
TryAdd(System.Int32,T)
Add(System.Int32,T)
TryGetValue(System.Int32,T&)
Remove(System.Int32)
Clear()
Clear(System.Boolean)
EnsureDenseCapacity(System.Int32)
EnsureSparseCapacity(System.Int32)
TrimExcess()
GetEnumerator()
System.Collections.Generic.IEnumerable<System.Collections.Generic.KeyValuePair<System.Int32,T>>.GetEnumerator()
System.Collections.IEnumerable.GetEnumerator()
GetDense(System.Int32[]&,T[]&,System.Int32&)
CopyKeysTo(SwiftCollections.SwiftList`1<System.Int32>)
CopySortedKeysTo(SwiftCollections.SwiftList`1<System.Int32>)
GetRequiredSparseCapacity(System.Int32)
GetDenseIndexOrThrow(System.Int32)
CloneTo(System.Collections.Generic.ICollection`1<T>)
.ctor(SwiftCollections.SwiftSparseMap`1<T>)
System.Collections.IEnumerator.get_Current()
MoveNext()
Reset()
Dispose()