< Summary

Information
Class: SwiftCollections.SwiftSparseSet
Assembly: SwiftCollections
File(s): File 1: /home/runner/work/SwiftCollections/SwiftCollections/src/SwiftCollections/Collection/SwiftSparseSet.cs
File 2: /home/runner/work/SwiftCollections/SwiftCollections/src/SwiftCollections/Collection/SwiftSparseSet.SwiftSparseSetEnumerator.cs
Line coverage
100%
Covered lines: 314
Uncovered lines: 0
Coverable lines: 314
Total lines: 881
Line coverage: 100%
Branch coverage
100%
Covered branches: 172
Total branches: 172
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%11100%
File 1: .ctor(...)100%88100%
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_IsReadOnly()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_State()100%11100%
File 1: set_State(...)100%11100%
File 1: RestoreDenseKeys(...)100%44100%
File 1: ValidateDenseKeys(...)100%44100%
File 1: RestoreSparseLookup(...)100%44100%
File 1: Contains(...)100%22100%
File 1: ContainsKey(...)100%11100%
File 1: Add(...)100%22100%
File 1: TryAdd(...)100%11100%
File 1: System.Collections.Generic.ICollection<System.Int32>.Add(...)100%11100%
File 1: Remove(...)100%66100%
File 1: Clear()100%44100%
File 1: Clear(...)100%11100%
File 1: ExceptWith(...)100%66100%
File 1: IntersectWith(...)100%88100%
File 1: IsProperSubsetOf(...)100%1010100%
File 1: IsProperSupersetOf(...)100%1010100%
File 1: IsSubsetOf(...)100%88100%
File 1: IsSupersetOf(...)100%66100%
File 1: Overlaps(...)100%44100%
File 1: SetEquals(...)100%66100%
File 1: SymmetricExceptWith(...)100%66100%
File 1: UnionWith(...)100%22100%
File 1: RemoveWhereMissingFrom(...)100%44100%
File 1: RemoveWhereMissingFrom(...)100%44100%
File 1: AllKeysIn(...)100%44100%
File 1: AllKeysIn(...)100%44100%
File 1: IsSubsetOfSparseSet(...)100%22100%
File 1: IsSubsetOfSet(...)100%22100%
File 1: SetEqualsSparseSet(...)100%22100%
File 1: SetEqualsSet(...)100%22100%
File 1: SymmetricExceptWithSet(...)100%44100%
File 1: EnsureDenseCapacity(...)100%88100%
File 1: EnsureSparseCapacity(...)100%88100%
File 1: TrimExcess()100%11100%
File 1: TrimDenseStorage()100%44100%
File 1: TrimSparseLookup()100%1010100%
File 1: AsReadOnlySpan()100%11100%
File 1: GetDense(...)100%11100%
File 1: CopyKeysTo(...)100%11100%
File 1: CopySortedKeysTo(...)100%11100%
File 1: CopyTo(...)100%11100%
File 1: System.Collections.ICollection.CopyTo(...)100%88100%
File 1: CloneTo(...)100%22100%
File 1: GetEnumerator()100%11100%
File 1: System.Collections.Generic.IEnumerable<System.Int32>.GetEnumerator()100%11100%
File 1: System.Collections.IEnumerable.GetEnumerator()100%11100%
File 1: GetRequiredSparseCapacity(...)100%11100%
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/SwiftSparseSet.cs

#LineLine coverage
 1//=======================================================================
 2// SwiftSparseSet.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 set for externally supplied non-negative integer IDs.
 23/// Provides O(1) Add, Remove, Contains, and densely packed iteration.
 24/// </summary>
 25/// <remarks>
 26/// <para>
 27/// <see cref="SwiftSparseSet"/> is intended for membership workloads where the caller already owns
 28/// compact integer IDs, such as entity handles, body IDs, or slot indices.
 29/// </para>
 30/// <para>
 31/// Internally, IDs are stored in a dense array for cache-friendly iteration while a sparse lookup
 32/// table maps each ID directly to its dense position. Removal uses swap-back, so iteration order is
 33/// not stable.
 34/// </para>
 35/// <para>
 36/// Memory usage scales with the highest stored ID rather than only the number of IDs. For arbitrary,
 37/// huge, or widely spaced keys, prefer <see cref="SwiftHashSet{T}"/> with <c>int</c> keys.
 38/// </para>
 39/// </remarks>
 40[Serializable]
 41[JsonConverter(typeof(StateJsonConverterFactory))]
 42[MemoryPackable]
 43public sealed partial class SwiftSparseSet : IStateBacked<SwiftArrayState<int>>, ISwiftCloneable<int>, ISet<int>, IReadO
 44{
 45    #region Constants
 46
 47    /// <summary>
 48    /// Represents the default initial capacity for dense ID storage.
 49    /// </summary>
 50    public const int DefaultDenseCapacity = 8;
 51
 52    /// <summary>
 53    /// Represents the default initial capacity for sparse ID lookup.
 54    /// </summary>
 55    public const int DefaultSparseCapacity = 8;
 56
 57    private const int NotPresent = 0;
 58
 59    #endregion
 60
 61    #region Fields
 62
 63    private int[] _sparse;       // id -> denseIndex+1
 64    private int[] _denseKeys;    // denseIndex -> id
 65    private int _count;
 66
 67    [NonSerialized]
 68    private uint _version;
 69
 70    [NonSerialized]
 71    private object? _syncRoot;
 72
 73    #endregion
 74
 75    #region Constructors
 76
 77    /// <summary>
 78    /// Initializes a new instance of the <see cref="SwiftSparseSet"/> class with default sparse and dense capacities.
 79    /// </summary>
 11880    public SwiftSparseSet() : this(DefaultSparseCapacity, DefaultDenseCapacity) { }
 81
 82    /// <summary>
 83    /// Initializes a new instance of the <see cref="SwiftSparseSet"/> class with matching sparse and dense capacities.
 84    /// </summary>
 85    /// <param name="capacity">The initial sparse and dense capacity.</param>
 286    public SwiftSparseSet(int capacity) : this(capacity, capacity) { }
 87
 88    /// <summary>
 89    /// Initializes a new instance of the <see cref="SwiftSparseSet"/> class with explicit sparse and dense capacities.
 90    /// </summary>
 91    /// <param name="sparseCapacity">
 92    /// Initial sparse lookup capacity. This should track the highest expected ID plus one,
 93    /// not just the number of stored IDs.
 94    /// </param>
 95    /// <param name="denseCapacity">Initial dense storage capacity for IDs.</param>
 6696    public SwiftSparseSet(int sparseCapacity, int denseCapacity)
 97    {
 6698        ChronicleGuard.ThrowIfNegative(sparseCapacity, nameof(sparseCapacity));
 6699        ChronicleGuard.ThrowIfNegative(denseCapacity, nameof(denseCapacity));
 100
 66101        int sparseSize = sparseCapacity == 0 ? 0 : SwiftHashTools.NextPowerOfTwo(sparseCapacity);
 66102        _sparse = sparseCapacity == 0
 66103            ? Array.Empty<int>()
 66104            : new int[sparseSize];
 105
 66106        int denseSize = denseCapacity < DefaultDenseCapacity
 66107            ? DefaultDenseCapacity
 66108            : SwiftHashTools.NextPowerOfTwo(denseCapacity);
 66109        _denseKeys = denseCapacity == 0
 66110            ? Array.Empty<int>()
 66111            : new int[denseSize];
 66112    }
 113
 114    /// <summary>
 115    /// Initializes a new instance of the <see cref="SwiftSparseSet"/> class using the specified state.
 116    /// </summary>
 117    /// <param name="state">The state object that provides the initial IDs. Cannot be null.</param>
 118    [MemoryPackConstructor]
 5119    public SwiftSparseSet(SwiftArrayState<int> state)
 120    {
 5121        _sparse = Array.Empty<int>();
 5122        _denseKeys = Array.Empty<int>();
 123
 5124        State = state;
 3125    }
 126
 127    #endregion
 128
 129    #region Properties
 130
 131    /// <summary>
 132    /// Gets the number of IDs contained in the set.
 133    /// </summary>
 134    [JsonIgnore]
 135    [MemoryPackIgnore]
 4136    public int Count => _count;
 137
 138    /// <summary>
 139    /// Capacity of the dense ID storage.
 140    /// </summary>
 141    [JsonIgnore]
 142    [MemoryPackIgnore]
 9143    public int DenseCapacity => _denseKeys.Length;
 144
 145    /// <summary>
 146    /// Capacity of the sparse lookup table.
 147    /// </summary>
 148    [JsonIgnore]
 149    [MemoryPackIgnore]
 9150    public int SparseCapacity => _sparse.Length;
 151
 152    /// <inheritdoc/>
 153    [JsonIgnore]
 154    [MemoryPackIgnore]
 1155    public bool IsReadOnly => false;
 156
 157    /// <summary>
 158    /// Gets a value indicating whether access to the collection is synchronized.
 159    /// </summary>
 160    [JsonIgnore]
 161    [MemoryPackIgnore]
 1162    public bool IsSynchronized => false;
 163
 164    /// <summary>
 165    /// Gets an object that can be used to synchronize access to the collection.
 166    /// </summary>
 167    [JsonIgnore]
 168    [MemoryPackIgnore]
 3169    public object SyncRoot => _syncRoot ??= new object();
 170
 171    /// <summary>
 172    /// Returns the dense ID array. Only the range [0..Count) is populated.
 173    /// </summary>
 174    /// <remarks>
 175    /// Prefer collection APIs. Direct key mutation must preserve the dense/sparse lookup invariants; invalid edits may 
 176    /// </remarks>
 177    [JsonIgnore]
 178    [MemoryPackIgnore]
 4179    public int[] DenseKeys => _denseKeys;
 180
 181    /// <summary>
 182    /// Gets a span containing the current IDs in dense iteration order.
 183    /// </summary>
 184    /// <remarks>
 185    /// Prefer collection APIs. Direct key mutation must preserve the dense/sparse lookup invariants; invalid edits may 
 186    /// </remarks>
 187    [JsonIgnore]
 188    [MemoryPackIgnore]
 3189    public Span<int> Keys => _denseKeys.AsSpan(0, _count);
 190
 191    /// <summary>
 192    /// Gets or sets the current state of the sparse set.
 193    /// </summary>
 194    [JsonInclude]
 195    [MemoryPackInclude]
 196    public SwiftArrayState<int> State
 197    {
 198        get
 199        {
 2200            var items = new int[_count];
 2201            Array.Copy(_denseKeys, items, _count);
 2202            return new SwiftArrayState<int>(items);
 203        }
 204        internal set
 205        {
 5206            ChronicleGuard.ThrowIfNull(value.Items, nameof(value.Items));
 207
 5208            RestoreDenseKeys(value.Items);
 5209            int maxKey = ValidateDenseKeys(nameof(value.Items));
 4210            RestoreSparseLookup(maxKey, nameof(value));
 211
 3212            _version++;
 3213        }
 214    }
 215
 216    private void RestoreDenseKeys(int[] items)
 217    {
 5218        int count = items.Length;
 5219        _denseKeys = count == 0
 5220            ? Array.Empty<int>()
 5221            : new int[Math.Max(DefaultDenseCapacity, SwiftHashTools.NextPowerOfTwo(count))];
 222
 5223        if (count > 0)
 4224            Array.Copy(items, _denseKeys, count);
 225
 5226        _count = count;
 5227    }
 228
 229    private int ValidateDenseKeys(string paramName)
 230    {
 5231        int maxKey = -1;
 20232        for (int i = 0; i < _count; i++)
 233        {
 6234            int key = _denseKeys[i];
 6235            ChronicleGuard.ThrowIfNegative(key, paramName);
 5236            ChronicleGuard.ThrowIfArgumentOutOfRange(key == int.MaxValue, key, paramName, "ID is too large for direct sp
 237
 5238            if (key > maxKey)
 4239                maxKey = key;
 240        }
 241
 4242        return maxKey;
 243    }
 244
 245    private void RestoreSparseLookup(int maxKey, string paramName)
 246    {
 4247        int sparseSize = maxKey < 0
 4248            ? DefaultSparseCapacity
 4249            : Math.Max(DefaultSparseCapacity, GetRequiredSparseCapacity(maxKey));
 4250        _sparse = new int[sparseSize];
 251
 16252        for (int i = 0; i < _count; i++)
 253        {
 5254            int key = _denseKeys[i];
 5255            ChronicleGuard.ThrowIfArgument(_sparse[key] != NotPresent, paramName, "Duplicate ID in sparse set state.");
 4256            _sparse[key] = i + 1;
 257        }
 3258    }
 259
 260    #endregion
 261
 262    #region Core Operations
 263
 264    /// <summary>
 265    /// Determines whether the set contains the specified ID.
 266    /// </summary>
 267    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 268    public bool Contains(int item)
 269    {
 52270        if ((uint)item >= (uint)_sparse.Length) return false;
 42271        return _sparse[item] != NotPresent;
 272    }
 273
 274    /// <summary>
 275    /// Determines whether the set contains the specified key. Alias for <see cref="Contains(int)"/>.
 276    /// </summary>
 277    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 5278    public bool ContainsKey(int key) => Contains(key);
 279
 280    /// <summary>
 281    /// Adds the specified ID if it is not already present.
 282    /// </summary>
 283    /// <returns>true if the ID was added; false if it was already present.</returns>
 284    public bool Add(int item)
 285    {
 251286        EnsureSparseCapacity(GetRequiredSparseCapacity(item));
 249287        if (_sparse[item] != NotPresent)
 1288            return false;
 289
 248290        EnsureDenseCapacity(_count + 1);
 291
 248292        int newIndex = _count++;
 248293        _denseKeys[newIndex] = item;
 248294        _sparse[item] = newIndex + 1;
 295
 248296        _version++;
 248297        return true;
 298    }
 299
 300    /// <summary>
 301    /// Adds the specified ID if it is not already present.
 302    /// </summary>
 1303    public bool TryAdd(int item) => Add(item);
 304
 1305    void ICollection<int>.Add(int item) => Add(item);
 306
 307    /// <summary>
 308    /// Removes the specified ID from the set.
 309    /// </summary>
 310    /// <returns>true if the ID was found and removed; otherwise, false.</returns>
 311    public bool Remove(int item)
 312    {
 24313        if ((uint)item >= (uint)_sparse.Length) return false;
 314
 18315        int slot = _sparse[item];
 22316        if (slot == NotPresent) return false;
 317
 14318        int index = slot - 1;
 14319        int last = --_count;
 320
 14321        _sparse[item] = NotPresent;
 322
 14323        if (index != last)
 324        {
 12325            int movedKey = _denseKeys[last];
 12326            _denseKeys[index] = movedKey;
 12327            _sparse[movedKey] = index + 1;
 328        }
 329
 14330        _denseKeys[last] = default;
 14331        _version++;
 14332        return true;
 333    }
 334
 335    /// <summary>
 336    /// Removes all IDs from the set without reducing capacity.
 337    /// </summary>
 338    public void Clear()
 339    {
 139340        if (_count == 0) return;
 341
 538342        for (int i = 0; i < _count; i++)
 343        {
 136344            int key = _denseKeys[i];
 136345            _sparse[key] = NotPresent;
 136346            _denseKeys[i] = default;
 347        }
 348
 133349        _count = 0;
 133350        _version++;
 133351    }
 352
 353    /// <summary>
 354    /// Removes all elements, optionally releasing references throughout retained backing storage.
 355    /// </summary>
 356    /// <param name="clearRetainedReferences">If true, also releases references outside the live range; otherwise uses o
 357    /// <remarks>This collection stores only integer IDs, so the option adds no reference cleanup or capacity scan.</rem
 358    public void Clear(bool clearRetainedReferences)
 359    {
 132360        Clear();
 132361    }
 362
 363    #endregion
 364
 365    #region Set Operations
 366
 367    /// <inheritdoc/>
 368    public void ExceptWith(IEnumerable<int> other)
 369    {
 3370        ChronicleGuard.ThrowIfNull(other, nameof(other));
 371
 4372        if (_count == 0) return;
 2373        if (ReferenceEquals(other, this))
 374        {
 1375            Clear();
 1376            return;
 377        }
 378
 6379        foreach (int item in other)
 2380            Remove(item);
 1381    }
 382
 383    /// <inheritdoc/>
 384    public void IntersectWith(IEnumerable<int> other)
 385    {
 5386        ChronicleGuard.ThrowIfNull(other, nameof(other));
 387
 7388        if (_count == 0 || ReferenceEquals(other, this)) return;
 389
 3390        if (other is SwiftSparseSet sparseSet)
 391        {
 1392            RemoveWhereMissingFrom(sparseSet);
 1393            return;
 394        }
 395
 2396        if (other is ISet<int> set)
 397        {
 1398            RemoveWhereMissingFrom(set);
 1399            return;
 400        }
 401
 1402        RemoveWhereMissingFrom(new HashSet<int>(other));
 1403    }
 404
 405    /// <inheritdoc/>
 406    public bool IsProperSubsetOf(IEnumerable<int> other)
 407    {
 6408        ChronicleGuard.ThrowIfNull(other, nameof(other));
 409
 6410        if (other is SwiftSparseSet sparseSet)
 2411            return _count < sparseSet._count && IsSubsetOf(sparseSet);
 412
 4413        if (other is ISet<int> set)
 2414            return _count < set.Count && IsSubsetOf(set);
 415
 2416        var lookup = new HashSet<int>(other);
 2417        return _count < lookup.Count && IsSubsetOf(lookup);
 418    }
 419
 420    /// <inheritdoc/>
 421    public bool IsProperSupersetOf(IEnumerable<int> other)
 422    {
 6423        ChronicleGuard.ThrowIfNull(other, nameof(other));
 424
 6425        if (other is SwiftSparseSet sparseSet)
 2426            return _count > sparseSet._count && IsSupersetOf(sparseSet);
 427
 4428        if (other is ISet<int> set)
 2429            return _count > set.Count && IsSupersetOf(set);
 430
 2431        var lookup = new HashSet<int>(other);
 2432        return _count > lookup.Count && IsSupersetOf(lookup);
 433    }
 434
 435    /// <inheritdoc/>
 436    public bool IsSubsetOf(IEnumerable<int> other)
 437    {
 10438        ChronicleGuard.ThrowIfNull(other, nameof(other));
 439
 12440        if (_count == 0 || ReferenceEquals(other, this)) return true;
 441
 8442        if (other is SwiftSparseSet sparseSet)
 3443            return IsSubsetOfSparseSet(sparseSet);
 444
 5445        if (other is ISet<int> set)
 4446            return IsSubsetOfSet(set);
 447
 1448        return IsSubsetOfSet(new HashSet<int>(other));
 449    }
 450
 451    /// <inheritdoc/>
 452    public bool IsSupersetOf(IEnumerable<int> other)
 453    {
 6454        ChronicleGuard.ThrowIfNull(other, nameof(other));
 455
 7456        if (ReferenceEquals(other, this)) return true;
 457
 29458        foreach (int item in other)
 459        {
 10460            if (!Contains(item))
 1461                return false;
 462        }
 463
 4464        return true;
 1465    }
 466
 467    /// <inheritdoc/>
 468    public bool Overlaps(IEnumerable<int> other)
 469    {
 2470        ChronicleGuard.ThrowIfNull(other, nameof(other));
 471
 9472        foreach (int item in other)
 473        {
 3474            if (Contains(item))
 1475                return true;
 476        }
 477
 1478        return false;
 1479    }
 480
 481    /// <inheritdoc/>
 482    public bool SetEquals(IEnumerable<int> other)
 483    {
 16484        ChronicleGuard.ThrowIfNull(other, nameof(other));
 485
 17486        if (ReferenceEquals(other, this)) return true;
 487
 15488        if (other is SwiftSparseSet sparseSet)
 4489            return SetEqualsSparseSet(sparseSet);
 490
 11491        if (other is ISet<int> set)
 4492            return SetEqualsSet(set);
 493
 7494        return SetEqualsSet(new HashSet<int>(other));
 495    }
 496
 497    /// <inheritdoc/>
 498    public void SymmetricExceptWith(IEnumerable<int> other)
 499    {
 5500        ChronicleGuard.ThrowIfNull(other, nameof(other));
 501
 5502        if (ReferenceEquals(other, this))
 503        {
 1504            Clear();
 1505            return;
 506        }
 507
 4508        if (other is SwiftSparseSet sparseSet)
 509        {
 1510            SymmetricExceptWithSet(sparseSet);
 1511            return;
 512        }
 513
 3514        if (other is ISet<int> set)
 515        {
 1516            SymmetricExceptWithSet(set);
 1517            return;
 518        }
 519
 2520        SymmetricExceptWithSet(new HashSet<int>(other));
 2521    }
 522
 523    /// <inheritdoc/>
 524    public void UnionWith(IEnumerable<int> other)
 525    {
 1526        ChronicleGuard.ThrowIfNull(other, nameof(other));
 527
 6528        foreach (int item in other)
 2529            Add(item);
 1530    }
 531
 532    private void RemoveWhereMissingFrom(SwiftSparseSet other)
 533    {
 1534        int index = 0;
 4535        while (index < _count)
 536        {
 3537            int key = _denseKeys[index];
 3538            if (other.Contains(key))
 2539                index++;
 540            else
 1541                Remove(key);
 542        }
 1543    }
 544
 545    private void RemoveWhereMissingFrom(ISet<int> other)
 546    {
 2547        int index = 0;
 9548        while (index < _count)
 549        {
 7550            int key = _denseKeys[index];
 7551            if (other.Contains(key))
 4552                index++;
 553            else
 3554                Remove(key);
 555        }
 2556    }
 557
 558    private bool AllKeysIn(SwiftSparseSet other)
 559    {
 28560        for (int i = 0; i < _count; i++)
 561        {
 10562            if (!other.Contains(_denseKeys[i]))
 1563                return false;
 564        }
 565
 4566        return true;
 567    }
 568
 569    private bool AllKeysIn(ISet<int> other)
 570    {
 82571        for (int i = 0; i < _count; i++)
 572        {
 30573            if (!other.Contains(_denseKeys[i]))
 3574                return false;
 575        }
 576
 11577        return true;
 578    }
 579
 580    private bool IsSubsetOfSparseSet(SwiftSparseSet other) =>
 3581        _count <= other._count && AllKeysIn(other);
 582
 583    private bool IsSubsetOfSet(ISet<int> other) =>
 5584        _count <= other.Count && AllKeysIn(other);
 585
 586    private bool SetEqualsSparseSet(SwiftSparseSet other) =>
 4587        _count == other._count && AllKeysIn(other);
 588
 589    private bool SetEqualsSet(ISet<int> other) =>
 11590        _count == other.Count && AllKeysIn(other);
 591
 592    private void SymmetricExceptWithSet(IEnumerable<int> other)
 593    {
 26594        foreach (int item in other)
 595        {
 9596            if (!Remove(item))
 4597                Add(item);
 598        }
 4599    }
 600
 601    #endregion
 602
 603    #region Capacity Management
 604
 605    /// <summary>
 606    /// Ensures that dense storage can hold at least the specified number of IDs.
 607    /// </summary>
 608    public void EnsureDenseCapacity(int capacity)
 609    {
 497610        if (capacity <= _denseKeys.Length) return;
 611
 3612        int newCap = _denseKeys.Length == 0 ? DefaultDenseCapacity : _denseKeys.Length * 2;
 5613        if (newCap < capacity) newCap = capacity;
 614
 3615        newCap = SwiftHashTools.NextPowerOfTwo(newCap);
 616
 3617        var newKeys = new int[newCap];
 3618        if (_count > 0)
 1619            Array.Copy(_denseKeys, newKeys, _count);
 620
 3621        _denseKeys = newKeys;
 3622        _version++;
 3623    }
 624
 625    /// <summary>
 626    /// Ensures that the sparse lookup table has at least the specified capacity.
 627    /// </summary>
 628    public void EnsureSparseCapacity(int capacity)
 629    {
 483630        if (capacity <= _sparse.Length) return;
 631
 17632        int newCap = _sparse.Length == 0
 17633            ? DefaultSparseCapacity
 17634            : _sparse.Length * 2;
 22635        if (newCap < capacity) newCap = capacity;
 636
 17637        newCap = SwiftHashTools.NextPowerOfTwo(newCap);
 638
 17639        var newSparse = new int[newCap];
 17640        if (_sparse.Length > 0)
 16641            Array.Copy(_sparse, newSparse, _sparse.Length);
 642
 17643        _sparse = newSparse;
 17644        _version++;
 17645    }
 646
 647    /// <summary>
 648    /// Reduces unused dense and sparse capacity while preserving all IDs.
 649    /// </summary>
 650    public void TrimExcess()
 651    {
 5652        TrimDenseStorage();
 5653        TrimSparseLookup();
 5654        _version++;
 5655    }
 656
 657    private void TrimDenseStorage()
 658    {
 5659        int newDense = Math.Max(DefaultDenseCapacity, _count);
 7660        if (newDense >= _denseKeys.Length) return;
 661
 3662        var newKeys = new int[newDense];
 3663        if (_count > 0)
 2664            Array.Copy(_denseKeys, newKeys, _count);
 3665        _denseKeys = newKeys;
 3666    }
 667
 668    private void TrimSparseLookup()
 669    {
 5670        int maxKey = -1;
 20671        for (int i = 0; i < _count; i++)
 8672            if (_denseKeys[i] > maxKey) maxKey = _denseKeys[i];
 673
 5674        int newSparse = maxKey < 0
 5675            ? DefaultSparseCapacity
 5676            : Math.Max(DefaultSparseCapacity, GetRequiredSparseCapacity(maxKey));
 7677        if (newSparse >= _sparse.Length) return;
 678
 3679        var newMap = new int[newSparse];
 12680        for (int i = 0; i < _count; i++)
 3681            newMap[_denseKeys[i]] = i + 1;
 3682        _sparse = newMap;
 3683    }
 684
 685    #endregion
 686
 687    #region Copy and Enumeration
 688
 689    /// <summary>
 690    /// Returns a read-only span over the populated dense ID range.
 691    /// </summary>
 1692    public ReadOnlySpan<int> AsReadOnlySpan() => _denseKeys.AsSpan(0, _count);
 693
 694    /// <summary>
 695    /// Retrieves the backing dense ID array and current count.
 696    /// </summary>
 697    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 698    public void GetDense(out int[] keys, out int count)
 699    {
 1700        keys = _denseKeys;
 1701        count = _count;
 1702    }
 703
 704    /// <summary>
 705    /// Replaces the destination list contents with this set's keys in dense iteration order.
 706    /// </summary>
 707    /// <remarks>
 708    /// The destination list is reused and only grows when its current capacity is smaller than
 709    /// <see cref="Count"/>. Use <see cref="CopySortedKeysTo(SwiftList{int})"/> when stable ascending
 710    /// key order is required.
 711    /// </remarks>
 712    /// <param name="destination">The caller-owned list that receives the keys.</param>
 713    public void CopyKeysTo(SwiftList<int> destination)
 714    {
 4715        ChronicleGuard.ThrowIfNull(destination, nameof(destination));
 716
 4717        destination.FastClear();
 4718        destination.AddRange(_denseKeys.AsSpan(0, _count));
 4719    }
 720
 721    /// <summary>
 722    /// Replaces the destination list contents with this set's keys sorted in ascending order.
 723    /// </summary>
 724    /// <remarks>
 725    /// This method is intended for reusable hot-path scratch buffers that need deterministic key order
 726    /// without constructing a persistent sorted collection.
 727    /// </remarks>
 728    /// <param name="destination">The caller-owned list that receives the sorted keys.</param>
 729    public void CopySortedKeysTo(SwiftList<int> destination)
 730    {
 3731        CopyKeysTo(destination);
 3732        destination.SortInPlace(default(SwiftIntAscendingComparer));
 3733    }
 734
 735    /// <inheritdoc/>
 736    public void CopyTo(int[] array, int arrayIndex)
 737    {
 3738        ChronicleGuard.ThrowIfNull(array, nameof(array));
 3739        ChronicleGuard.ThrowIfArrayIndexInvalid(arrayIndex, array.Length);
 3740        ChronicleGuard.ThrowIfArgument(array.Length - arrayIndex < _count, nameof(array), "The array is not large enough
 741
 3742        Array.Copy(_denseKeys, 0, array, arrayIndex, _count);
 3743    }
 744
 745    /// <inheritdoc/>
 746    void ICollection.CopyTo(Array array, int index)
 747    {
 8748        ChronicleGuard.ThrowIfNull(array, nameof(array));
 8749        ChronicleGuard.ThrowIfArgument(array.Rank != 1, nameof(array), "Only single dimensional arrays are supported.");
 7750        ChronicleGuard.ThrowIfArgument(array.GetLowerBound(0) != 0, nameof(array), "Non-zero lower bound arrays are not 
 6751        ChronicleGuard.ThrowIfArrayIndexInvalid(index, array.Length, nameof(index));
 5752        ChronicleGuard.ThrowIfArgument(array.Length - index < _count, nameof(array), "The array is not large enough to h
 753
 4754        if (array is int[] intArray)
 755        {
 1756            CopyTo(intArray, index);
 1757            return;
 758        }
 759
 3760        Type elementType = array.GetType().GetElementType()!;
 3761        if (array is object[] objects && elementType.IsAssignableFrom(typeof(int)))
 762        {
 6763            for (int i = 0; i < _count; i++)
 2764                objects[index + i] = _denseKeys[i];
 1765            return;
 766        }
 767
 2768        throw new ArgumentException("Invalid array type.", nameof(array));
 769    }
 770
 771    /// <inheritdoc/>
 772    public void CloneTo(ICollection<int> output)
 773    {
 1774        ChronicleGuard.ThrowIfNull(output, nameof(output));
 775
 1776        output.Clear();
 777
 6778        for (int i = 0; i < _count; i++)
 2779            output.Add(_denseKeys[i]);
 1780    }
 781
 782    /// <inheritdoc cref="IEnumerable.GetEnumerator()"/>
 56783    public SwiftSparseSetEnumerator GetEnumerator() => new(this);
 35784    IEnumerator<int> IEnumerable<int>.GetEnumerator() => GetEnumerator();
 19785    IEnumerator IEnumerable.GetEnumerator() => GetEnumerator();
 786
 787
 788
 789    #endregion
 790
 791    #region Helpers
 792
 793    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 794    private static int GetRequiredSparseCapacity(int key)
 795    {
 257796        ChronicleGuard.ThrowIfNegative(key, nameof(key));
 256797        ChronicleGuard.ThrowIfArgumentOutOfRange(key == int.MaxValue, key, nameof(key), "ID is too large for direct spar
 798
 255799        return key + 1;
 800    }
 801
 802    #endregion
 803}

/home/runner/work/SwiftCollections/SwiftCollections/src/SwiftCollections/Collection/SwiftSparseSet.SwiftSparseSetEnumerator.cs

#LineLine coverage
 1//=======================================================================
 2// SwiftSparseSet.SwiftSparseSetEnumerator.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.Collections;
 9using System.Collections.Generic;
 10using Chronicler.Diagnostics;
 11
 12namespace SwiftCollections;
 13
 14public sealed partial class SwiftSparseSet
 15{
 16    /// <summary>
 17    /// Supports iteration over IDs in a <see cref="SwiftSparseSet"/>.
 18    /// </summary>
 19    public struct SwiftSparseSetEnumerator : IEnumerator<int>
 20    {
 21        private readonly SwiftSparseSet _set;
 22        private readonly int[] _keys;
 23        private readonly int _count;
 24        private readonly uint _version;
 25        private int _index;
 26
 27        internal SwiftSparseSetEnumerator(SwiftSparseSet set)
 28        {
 5629            _set = set;
 5630            _keys = set._denseKeys;
 5631            _count = set._count;
 5632            _version = set._version;
 5633            _index = -1;
 5634            Current = default;
 5635        }
 36
 37        /// <inheritdoc/>
 38        public int Current { get; private set; }
 39        object IEnumerator.Current
 40        {
 41            get
 42            {
 3143                ChronicleGuard.ThrowIfTrue((uint)_index >= (uint)_count, message: "Enumerator is before the first elemen
 1344                return Current;
 45            }
 46        }
 47
 48        /// <inheritdoc/>
 49        public bool MoveNext()
 50        {
 11151            ChronicleGuard.ThrowIfTrue(_version != _set._version, message: "Collection was modified during enumeration."
 52
 10753            int next = _index + 1;
 10754            if (next >= _count)
 55            {
 5156                _index = _count;
 5157                Current = default;
 5158                return false;
 59            }
 60
 5661            _index = next;
 5662            Current = _keys[_index];
 5663            return true;
 64        }
 65
 66        /// <inheritdoc/>
 67        public void Reset()
 68        {
 1069            ChronicleGuard.ThrowIfTrue(_version != _set._version, message: "Collection was modified during enumeration."
 70
 771            _index = -1;
 772            Current = default;
 773        }
 74
 75        /// <inheritdoc/>
 3876        public void Dispose() => _index = -1;
 77    }
 78}
Generated by: ReportGenerator 5.5.12.0
11/05/2026 - 04:17:34
GitHub | reportgenerator.io

Methods/Properties

.ctor()
.ctor(System.Int32)
.ctor(System.Int32,System.Int32)
.ctor(SwiftCollections.SwiftArrayState`1<System.Int32>)
get_Count()
get_DenseCapacity()
get_SparseCapacity()
get_IsReadOnly()
get_IsSynchronized()
get_SyncRoot()
get_DenseKeys()
get_Keys()
get_State()
set_State(SwiftCollections.SwiftArrayState`1<System.Int32>)
RestoreDenseKeys(System.Int32[])
ValidateDenseKeys(System.String)
RestoreSparseLookup(System.Int32,System.String)
Contains(System.Int32)
ContainsKey(System.Int32)
Add(System.Int32)
TryAdd(System.Int32)
System.Collections.Generic.ICollection<System.Int32>.Add(System.Int32)
Remove(System.Int32)
Clear()
Clear(System.Boolean)
ExceptWith(System.Collections.Generic.IEnumerable`1<System.Int32>)
IntersectWith(System.Collections.Generic.IEnumerable`1<System.Int32>)
IsProperSubsetOf(System.Collections.Generic.IEnumerable`1<System.Int32>)
IsProperSupersetOf(System.Collections.Generic.IEnumerable`1<System.Int32>)
IsSubsetOf(System.Collections.Generic.IEnumerable`1<System.Int32>)
IsSupersetOf(System.Collections.Generic.IEnumerable`1<System.Int32>)
Overlaps(System.Collections.Generic.IEnumerable`1<System.Int32>)
SetEquals(System.Collections.Generic.IEnumerable`1<System.Int32>)
SymmetricExceptWith(System.Collections.Generic.IEnumerable`1<System.Int32>)
UnionWith(System.Collections.Generic.IEnumerable`1<System.Int32>)
RemoveWhereMissingFrom(SwiftCollections.SwiftSparseSet)
RemoveWhereMissingFrom(System.Collections.Generic.ISet`1<System.Int32>)
AllKeysIn(SwiftCollections.SwiftSparseSet)
AllKeysIn(System.Collections.Generic.ISet`1<System.Int32>)
IsSubsetOfSparseSet(SwiftCollections.SwiftSparseSet)
IsSubsetOfSet(System.Collections.Generic.ISet`1<System.Int32>)
SetEqualsSparseSet(SwiftCollections.SwiftSparseSet)
SetEqualsSet(System.Collections.Generic.ISet`1<System.Int32>)
SymmetricExceptWithSet(System.Collections.Generic.IEnumerable`1<System.Int32>)
EnsureDenseCapacity(System.Int32)
EnsureSparseCapacity(System.Int32)
TrimExcess()
TrimDenseStorage()
TrimSparseLookup()
AsReadOnlySpan()
GetDense(System.Int32[]&,System.Int32&)
CopyKeysTo(SwiftCollections.SwiftList`1<System.Int32>)
CopySortedKeysTo(SwiftCollections.SwiftList`1<System.Int32>)
CopyTo(System.Int32[],System.Int32)
System.Collections.ICollection.CopyTo(System.Array,System.Int32)
CloneTo(System.Collections.Generic.ICollection`1<System.Int32>)
GetEnumerator()
System.Collections.Generic.IEnumerable<System.Int32>.GetEnumerator()
System.Collections.IEnumerable.GetEnumerator()
GetRequiredSparseCapacity(System.Int32)
.ctor(SwiftCollections.SwiftSparseSet)
System.Collections.IEnumerator.get_Current()
MoveNext()
Reset()
Dispose()