< Summary

Information
Class: SwiftCollections.SwiftPackedSet<T>
Assembly: SwiftCollections
File(s): /home/runner/work/SwiftCollections/SwiftCollections/src/SwiftCollections/Collection/SwiftPackedSet.cs
Line coverage
100%
Covered lines: 192
Uncovered lines: 0
Coverable lines: 192
Total lines: 581
Line coverage: 100%
Branch coverage
98%
Covered branches: 85
Total branches: 86
Branch coverage: 98.8%
Method coverage

Feature is only available for sponsors

Upgrade to PRO version

Metrics

MethodBranch coverage Crap Score Cyclomatic complexity Line coverage
.cctor()100%11100%
.ctor()100%11100%
.ctor(...)100%22100%
.ctor(...)100%11100%
get_Count()100%11100%
get_Capacity()100%11100%
get_IsSynchronized()100%11100%
get_SyncRoot()50%22100%
get_Dense()100%11100%
get_IsReadOnly()100%11100%
get_State()100%11100%
set_State(...)100%66100%
Contains(...)100%11100%
AsReadOnlySpan()100%11100%
Exists(...)100%44100%
Find(...)100%44100%
Add(...)100%22100%
System.Collections.Generic.ICollection<T>.Add(...)100%11100%
Remove(...)100%66100%
Clear()100%44100%
EnsureCapacity(...)100%22100%
GetEnumerator()100%11100%
System.Collections.Generic.IEnumerable<T>.GetEnumerator()100%11100%
System.Collections.IEnumerable.GetEnumerator()100%11100%
.ctor(...)100%11100%
System.Collections.IEnumerator.get_Current()100%11100%
MoveNext()100%22100%
Reset()100%11100%
Dispose()100%11100%
CloneTo(...)100%22100%
CopyTo(...)100%11100%
ExceptWith(...)100%44100%
IntersectWith(...)100%66100%
IsProperSubsetOf(...)100%66100%
IsProperSupersetOf(...)100%66100%
IsSubsetOf(...)100%66100%
IsSupersetOf(...)100%44100%
Overlaps(...)100%44100%
SetEquals(...)100%66100%
SymmetricExceptWith(...)100%66100%
UnionWith(...)100%22100%

File(s)

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

#LineLine coverage
 1//=======================================================================
 2// SwiftPackedSet.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 Chronicler;
 9using MemoryPack;
 10using SwiftCollections.Diagnostics;
 11using SwiftCollections.Utility;
 12using System;
 13using System.Collections;
 14using System.Collections.Generic;
 15using System.Runtime.CompilerServices;
 16using System.Text.Json.Serialization;
 17
 18namespace SwiftCollections;
 19
 20/// <summary>
 21/// Represents a high-performance set that stores unique values in a densely packed array
 22/// while providing O(1) lookups via an internal hash map.
 23/// </summary>
 24/// <remarks>
 25/// <para>
 26/// <see cref="SwiftPackedSet{T}"/> maintains values in a contiguous array for extremely
 27/// cache-friendly iteration while using a hash-based lookup table to guarantee fast
 28/// membership tests and removals.
 29/// </para>
 30/// <para>
 31/// Removal uses a swap-back strategy that keeps the dense storage contiguous but does not
 32/// preserve ordering. As a result, iteration order is not guaranteed to remain stable.
 33/// </para>
 34/// <para>
 35/// This structure is commonly used in high-performance systems such as ECS (Entity Component Systems)
 36/// where dense iteration speed is critical.
 37/// </para>
 38/// </remarks>
 39/// <typeparam name="T">The type of elements contained in the set.</typeparam>
 40[Serializable]
 41[JsonConverter(typeof(StateJsonConverterFactory))]
 42[MemoryPackable]
 43public sealed partial class SwiftPackedSet<T> : IStateBacked<SwiftArrayState<T>>, ISwiftCloneable<T>, ISet<T>, IEnumerab
 44    where T : notnull
 45{
 46    #region Constants
 47
 48    /// <summary>
 49    /// Represents the default initial capacity value used when no specific capacity is provided.
 50    /// </summary>
 51    public const int DefaultCapacity = 8;
 52
 253    private static readonly bool _clearReleasedSlots = RuntimeHelpers.IsReferenceOrContainsReferences<T>();
 54
 55    #endregion
 56
 57    #region Fields
 58
 59    private T[] _dense;
 60    private SwiftDictionary<T, int> _lookup;
 61    private int _count;
 62
 63    [NonSerialized]
 64    private uint _version;
 65
 66    [NonSerialized]
 67    private object? _syncRoot;
 68
 69    #endregion
 70
 71    #region Constructors
 72
 73    /// <summary>
 74    /// Initializes a new instance of the SwiftPackedSet class with the default capacity.
 75    /// </summary>
 9676    public SwiftPackedSet() : this(DefaultCapacity) { }
 77
 78    /// <summary>
 79    /// Initializes a new instance of the SwiftPackedSet class with the specified initial capacity.
 80    /// </summary>
 81    /// <remarks>
 82    /// The actual capacity is rounded up to the next power of two greater than or equal to the specified value,
 83    /// unless the specified value is less than or equal to the default capacity.
 84    /// </remarks>
 85    /// <param name="capacity">
 86    /// The initial number of elements that the set can contain before resizing.
 87    /// If less than or equal to the default capacity, the default capacity is used.
 88    /// Must be non-negative.
 89    /// </param>
 4990    public SwiftPackedSet(int capacity)
 91    {
 4992        capacity = capacity <= DefaultCapacity
 4993            ? DefaultCapacity
 4994            : SwiftHashTools.NextPowerOfTwo(capacity);
 95
 4996        _dense = new T[capacity];
 4997        _lookup = new SwiftDictionary<T, int>(capacity);
 4998    }
 99
 100    /// <summary>
 101    /// Initializes a new instance of the SwiftPackedSet class with the specified array state.
 102    /// </summary>
 103    /// <param name="state">The state object that provides the initial data and configuration for the set. Cannot be nul
 104    [MemoryPackConstructor]
 7105    public SwiftPackedSet(SwiftArrayState<T> state)
 106    {
 7107        State = state;
 108
 7109        SwiftThrowHelper.ThrowIfNull(_dense, nameof(_dense));
 7110        SwiftThrowHelper.ThrowIfNull(_lookup, nameof(_lookup));
 7111    }
 112
 113    #endregion
 114
 115    #region Properties
 116
 117    /// <summary>
 118    /// Gets the number of elements contained in the collection.
 119    /// </summary>
 120    [JsonIgnore]
 121    [MemoryPackIgnore]
 19122    public int Count => _count;
 123
 124    /// <summary>
 125    /// Gets the total number of elements that the collection can hold without resizing.
 126    /// </summary>
 127    [JsonIgnore]
 128    [MemoryPackIgnore]
 4129    public int Capacity => _dense.Length;
 130
 131    /// <summary>
 132    /// Gets a value indicating whether access to the collection is synchronized (thread safe).
 133    /// </summary>
 134    [JsonIgnore]
 135    [MemoryPackIgnore]
 1136    public bool IsSynchronized => false;
 137
 138    /// <inheritdoc/>
 139    [JsonIgnore]
 140    [MemoryPackIgnore]
 1141    public object SyncRoot => _syncRoot ??= new object();
 142
 143    /// <summary>
 144    /// Gets the underlying dense array of elements.
 145    /// </summary>
 146    [JsonIgnore]
 147    [MemoryPackIgnore]
 8148    public T[] Dense => _dense;
 149
 150    /// <inheritdoc/>
 151    [JsonIgnore]
 152    [MemoryPackIgnore]
 1153    public bool IsReadOnly => false;
 154
 155    /// <summary>
 156    /// Gets or sets the current state of the array, including its items and order.
 157    /// </summary>
 158    /// <remarks>
 159    /// Use this property to capture or restore the array's contents and structure.
 160    /// Setting this property replaces the entire array with the provided state.
 161    /// </remarks>
 162    [JsonInclude]
 163    [MemoryPackInclude]
 164    public SwiftArrayState<T> State
 165    {
 166        get
 167        {
 6168            var values = new T[_count];
 6169            Array.Copy(_dense, values, _count);
 170
 6171            return new SwiftArrayState<T>(values);
 172        }
 173        internal set
 174        {
 7175            SwiftThrowHelper.ThrowIfNull(value.Items, nameof(value.Items));
 176
 7177            var values = value.Items;
 178
 7179            int n = values.Length;
 7180            int newCapacity = n < DefaultCapacity
 7181                ? DefaultCapacity
 7182                : SwiftHashTools.NextPowerOfTwo(n);
 183
 7184            _dense = new T[newCapacity];
 7185            _lookup = new SwiftDictionary<T, int>(newCapacity);
 186
 7187            if (n > 0)
 188            {
 4189                Array.Copy(values, _dense, n);
 190
 2022191                for (int i = 0; i < n; i++)
 1007192                    _lookup.Add(values[i], i);
 193            }
 194
 7195            _count = n;
 7196            _version++;
 7197        }
 198    }
 199
 200    #endregion
 201
 202    #region Core Operations
 203
 204    /// <inheritdoc/>
 205    public bool Contains(T value)
 1036206        => _lookup.ContainsKey(value);
 207
 208    /// <summary>
 209    /// Returns a read-only span over the populated dense portion of the set.
 210    /// </summary>
 1211    public ReadOnlySpan<T> AsReadOnlySpan() => _dense.AsSpan(0, _count);
 212
 213    /// <summary>
 214    /// Determines whether the <see cref="SwiftPackedSet{T}"/> contains an element that matches the conditions defined b
 215    /// </summary>
 216    /// <param name="match">The predicate that defines the conditions of the element to search for.</param>
 217    /// <returns><c>true</c> if the <see cref="SwiftPackedSet{T}"/> contains one or more elements that match the specifi
 218    public bool Exists(Predicate<T> match)
 219    {
 3220        SwiftThrowHelper.ThrowIfNull(match, nameof(match));
 221
 10222        for (int i = 0; i < _count; i++)
 223        {
 4224            if (match(_dense[i]))
 1225                return true;
 226        }
 227
 1228        return false;
 229    }
 230
 231    /// <summary>
 232    /// Searches for an element that matches the conditions defined by the specified predicate, and returns the first ma
 233    /// </summary>
 234    /// <param name="match">The predicate that defines the conditions of the element to search for.</param>
 235    /// <returns>The first element that matches the conditions defined by the specified predicate, if found; otherwise, 
 236    public T Find(Predicate<T> match)
 237    {
 2238        SwiftThrowHelper.ThrowIfNull(match, nameof(match));
 239
 10240        for (int i = 0; i < _count; i++)
 241        {
 4242            if (match(_dense[i]))
 1243                return _dense[i];
 244        }
 245
 1246        return default!;
 247    }
 248
 249    /// <inheritdoc/>
 250    public bool Add(T value)
 251    {
 11097252        if (_lookup.ContainsKey(value))
 1253            return false;
 254
 11096255        EnsureCapacity(_count + 1);
 256
 11096257        _dense[_count] = value;
 11096258        _lookup.Add(value, _count);
 259
 11096260        _count++;
 11096261        _version++;
 262
 11096263        return true;
 264    }
 265
 1266    void ICollection<T>.Add(T item) => Add(item);
 267
 268    /// <inheritdoc/>
 269    public bool Remove(T value)
 270    {
 5013271        if (!_lookup.TryGetValue(value, out int index))
 3272            return false;
 273
 5010274        int last = --_count;
 275
 5010276        if (index != last)
 277        {
 5006278            T moved = _dense[last];
 279
 5006280            _dense[index] = moved;
 5006281            _lookup[moved] = index;
 282        }
 283
 5010284        if (_clearReleasedSlots)
 3285            _dense[last] = default!;
 5010286        _lookup.Remove(value);
 287
 5010288        _version++;
 5010289        return true;
 290    }
 291
 292    /// <inheritdoc/>
 293    public void Clear()
 294    {
 8295        if (_count == 0) return;
 296
 6297        if (_clearReleasedSlots)
 1298            Array.Clear(_dense, 0, _count);
 6299        _lookup.Clear();
 300
 6301        _count = 0;
 6302        _version++;
 6303    }
 304
 305    #endregion
 306
 307    #region Capacity
 308
 309    /// <summary>
 310    /// Ensures that the internal storage has at least the specified capacity, expanding it if necessary.
 311    /// </summary>
 312    /// <remarks>
 313    /// If the current capacity is less than the specified value, the internal storage is resized to
 314    /// the next power of two greater than or equal to the specified capacity.
 315    /// Existing elements are preserved.
 316    /// </remarks>
 317    /// <param name="capacity">The minimum number of elements that the internal storage should be able to hold. Must be 
 318    public void EnsureCapacity(int capacity)
 319    {
 11097320        int newCapacity = SwiftHashTools.NextPowerOfTwo(capacity);
 11097321        if (newCapacity <= _dense.Length)
 11079322            return;
 323
 18324        var newArray = new T[newCapacity];
 18325        Array.Copy(_dense, newArray, _count);
 326
 18327        _dense = newArray;
 18328    }
 329
 330    #endregion
 331
 332    #region Enumeration
 333
 334    /// <inheritdoc cref="IEnumerable.GetEnumerator()"/>
 15335    public SwiftPackedSetEnumerator GetEnumerator() => new(this);
 12336    IEnumerator<T> IEnumerable<T>.GetEnumerator() => GetEnumerator();
 1337    IEnumerator IEnumerable.GetEnumerator() => GetEnumerator();
 338
 339    /// <summary>
 340    /// Enumerates the elements of a <see cref="SwiftPackedSet{T}"/> collection.
 341    /// </summary>
 342    /// <remarks>
 343    /// The enumerator is invalidated if the collection is modified after the enumerator is created.
 344    /// In such cases, calling MoveNext or Reset will throw an InvalidOperationException.
 345    /// </remarks>
 346    public struct SwiftPackedSetEnumerator : IEnumerator<T>
 347    {
 348        private readonly SwiftPackedSet<T> _set;
 349        private readonly uint _version;
 350        private int _index;
 351
 352        internal SwiftPackedSetEnumerator(SwiftPackedSet<T> set)
 353        {
 15354            _set = set;
 15355            _version = set._version;
 15356            _index = -1;
 15357            Current = default!;
 15358        }
 359
 360        /// <inheritdoc/>
 361        public T Current { get; private set; }
 362
 2363        object IEnumerator.Current => Current;
 364
 365        /// <inheritdoc/>
 366        public bool MoveNext()
 367        {
 19368            SwiftThrowHelper.ThrowIfTrue(_version != _set._version, message: "Collection was modified during enumeration
 369
 18370            int next = _index + 1;
 18371            if (next >= _set._count)
 372            {
 12373                Current = default!;
 12374                return false;
 375            }
 376
 6377            _index = next;
 6378            Current = _set._dense[next];
 6379            return true;
 380        }
 381
 382        /// <inheritdoc/>
 383        public void Reset()
 384        {
 2385            SwiftThrowHelper.ThrowIfTrue(_version != _set._version, message: "Collection was modified during enumeration
 386
 1387            _index = -1;
 1388            Current = default!;
 1389        }
 390
 391        /// <inheritdoc/>
 12392        public void Dispose() => _index = -1;
 393    }
 394
 395    #endregion
 396
 397    #region Clone
 398
 399    /// <inheritdoc/>
 400    public void CloneTo(ICollection<T> output)
 401    {
 1402        SwiftThrowHelper.ThrowIfNull(output, nameof(output));
 403
 1404        output.Clear();
 405
 6406        for (int i = 0; i < _count; i++)
 2407            output.Add(_dense[i]);
 1408    }
 409
 410    /// <inheritdoc/>
 411    public void CopyTo(T[] array, int arrayIndex)
 412    {
 3413        SwiftThrowHelper.ThrowIfNull(array, nameof(array));
 3414        SwiftThrowHelper.ThrowIfArrayIndexInvalid(arrayIndex, array.Length);
 2415        SwiftThrowHelper.ThrowIfArgument(array.Length - arrayIndex < _count, nameof(array), "Destination array is not lo
 416
 1417        Array.Copy(_dense, 0, array, arrayIndex, _count);
 1418    }
 419
 420    #endregion
 421
 422    #region ISet<T> Implementations
 423
 424    /// <inheritdoc/>
 425    public void ExceptWith(IEnumerable<T> other)
 426    {
 2427        SwiftThrowHelper.ThrowIfNull(other, nameof(other));
 428
 2429        if (ReferenceEquals(this, other))
 430        {
 1431            Clear();
 1432            return;
 433        }
 434
 1435        var otherSet = new SwiftHashSet<T>(other);
 436
 8437        foreach (var item in otherSet)
 3438            Remove(item);
 1439    }
 440
 441    /// <inheritdoc/>
 442    public void IntersectWith(IEnumerable<T> other)
 443    {
 2444        SwiftThrowHelper.ThrowIfNull(other, nameof(other));
 445
 2446        if (ReferenceEquals(this, other))
 1447            return;
 448
 1449        var otherSet = new SwiftHashSet<T>(other);
 450
 10451        for (int i = _count - 1; i >= 0; i--)
 452        {
 4453            var value = _dense[i];
 4454            if (!otherSet.Contains(value))
 2455                Remove(value);
 456        }
 1457    }
 458
 459    /// <inheritdoc/>
 460    public bool IsProperSubsetOf(IEnumerable<T> other)
 461    {
 3462        SwiftThrowHelper.ThrowIfNull(other, nameof(other));
 463
 3464        var set = new SwiftHashSet<T>(other);
 465
 3466        if (_count >= set.Count)
 1467            return false;
 468
 14469        for (int i = 0; i < _count; i++)
 6470            if (!set.Contains(_dense[i]))
 1471                return false;
 472
 1473        return true;
 474    }
 475
 476    /// <inheritdoc/>
 477    public bool IsProperSupersetOf(IEnumerable<T> other)
 478    {
 3479        SwiftThrowHelper.ThrowIfNull(other, nameof(other));
 480
 3481        var set = new SwiftHashSet<T>(other);
 482
 3483        if (_count <= set.Count)
 1484            return false;
 485
 9486        foreach (var item in set)
 3487            if (!Contains(item))
 1488                return false;
 489
 1490        return true;
 1491    }
 492
 493    /// <inheritdoc/>
 494    public bool IsSubsetOf(IEnumerable<T> other)
 495    {
 3496        SwiftThrowHelper.ThrowIfNull(other, nameof(other));
 497
 3498        var set = new SwiftHashSet<T>(other);
 499
 3500        if (_count > set.Count)
 1501            return false;
 502
 14503        for (int i = 0; i < _count; i++)
 6504            if (!set.Contains(_dense[i]))
 1505                return false;
 506
 1507        return true;
 508    }
 509
 510    /// <inheritdoc/>
 511    public bool IsSupersetOf(IEnumerable<T> other)
 512    {
 2513        SwiftThrowHelper.ThrowIfNull(other, nameof(other));
 514
 13515        foreach (var item in other)
 5516            if (!Contains(item))
 1517                return false;
 518
 1519        return true;
 1520    }
 521
 522    /// <inheritdoc/>
 523    public bool Overlaps(IEnumerable<T> other)
 524    {
 2525        SwiftThrowHelper.ThrowIfNull(other, nameof(other));
 526
 9527        foreach (var item in other)
 3528            if (Contains(item))
 1529                return true;
 530
 1531        return false;
 1532    }
 533
 534    /// <inheritdoc/>
 535    public bool SetEquals(IEnumerable<T> other)
 536    {
 6537        SwiftThrowHelper.ThrowIfNull(other, nameof(other));
 538
 6539        var set = new SwiftHashSet<T>(other);
 540
 6541        if (_count != set.Count)
 1542            return false;
 543
 38544        for (int i = 0; i < _count; i++)
 15545            if (!set.Contains(_dense[i]))
 1546                return false;
 547
 4548        return true;
 549    }
 550
 551    /// <inheritdoc/>
 552    public void SymmetricExceptWith(IEnumerable<T> other)
 553    {
 2554        SwiftThrowHelper.ThrowIfNull(other, nameof(other));
 555
 2556        if (ReferenceEquals(this, other))
 557        {
 1558            Clear();
 1559            return;
 560        }
 561
 1562        var set = new SwiftHashSet<T>(other);
 563
 6564        foreach (var item in set)
 565        {
 2566            if (!Remove(item))
 1567                Add(item);
 568        }
 1569    }
 570
 571    /// <inheritdoc/>
 572    public void UnionWith(IEnumerable<T> other)
 573    {
 1574        SwiftThrowHelper.ThrowIfNull(other, nameof(other));
 575
 6576        foreach (var item in other)
 2577            Add(item);
 1578    }
 579
 580    #endregion
 581}
Generated by: ReportGenerator 5.5.10.0
07/01/2026 - 04:31:31
GitHub | reportgenerator.io

Methods/Properties

.cctor()
.ctor()
.ctor(System.Int32)
.ctor(SwiftCollections.SwiftArrayState`1<T>)
get_Count()
get_Capacity()
get_IsSynchronized()
get_SyncRoot()
get_Dense()
get_IsReadOnly()
get_State()
set_State(SwiftCollections.SwiftArrayState`1<T>)
Contains(T)
AsReadOnlySpan()
Exists(System.Predicate`1<T>)
Find(System.Predicate`1<T>)
Add(T)
System.Collections.Generic.ICollection<T>.Add(T)
Remove(T)
Clear()
EnsureCapacity(System.Int32)
GetEnumerator()
System.Collections.Generic.IEnumerable<T>.GetEnumerator()
System.Collections.IEnumerable.GetEnumerator()
.ctor(SwiftCollections.SwiftPackedSet`1<T>)
System.Collections.IEnumerator.get_Current()
MoveNext()
Reset()
Dispose()
CloneTo(System.Collections.Generic.ICollection`1<T>)
CopyTo(T[],System.Int32)
ExceptWith(System.Collections.Generic.IEnumerable`1<T>)
IntersectWith(System.Collections.Generic.IEnumerable`1<T>)
IsProperSubsetOf(System.Collections.Generic.IEnumerable`1<T>)
IsProperSupersetOf(System.Collections.Generic.IEnumerable`1<T>)
IsSubsetOf(System.Collections.Generic.IEnumerable`1<T>)
IsSupersetOf(System.Collections.Generic.IEnumerable`1<T>)
Overlaps(System.Collections.Generic.IEnumerable`1<T>)
SetEquals(System.Collections.Generic.IEnumerable`1<T>)
SymmetricExceptWith(System.Collections.Generic.IEnumerable`1<T>)
UnionWith(System.Collections.Generic.IEnumerable`1<T>)