< Summary

Line coverage
100%
Covered lines: 199
Uncovered lines: 0
Coverable lines: 199
Total lines: 624
Line coverage: 100%
Branch coverage
100%
Covered branches: 90
Total branches: 90
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: .cctor()100%11100%
File 1: .ctor()100%11100%
File 1: .ctor(...)100%22100%
File 1: .ctor(...)100%11100%
File 1: get_Count()100%11100%
File 1: get_Capacity()100%11100%
File 1: get_IsSynchronized()100%11100%
File 1: get_SyncRoot()100%22100%
File 1: get_Dense()100%11100%
File 1: get_IsReadOnly()100%11100%
File 1: get_State()100%11100%
File 1: set_State(...)100%66100%
File 1: Contains(...)100%11100%
File 1: AsReadOnlySpan()100%11100%
File 1: Exists(...)100%44100%
File 1: Find(...)100%44100%
File 1: Add(...)100%22100%
File 1: System.Collections.Generic.ICollection<T>.Add(...)100%11100%
File 1: Remove(...)100%66100%
File 1: Clear()100%44100%
File 1: Clear(...)100%44100%
File 1: EnsureCapacity(...)100%22100%
File 1: GetEnumerator()100%11100%
File 1: System.Collections.Generic.IEnumerable<T>.GetEnumerator()100%11100%
File 1: System.Collections.IEnumerable.GetEnumerator()100%11100%
File 1: CloneTo(...)100%22100%
File 1: CopyTo(...)100%11100%
File 1: ExceptWith(...)100%44100%
File 1: IntersectWith(...)100%66100%
File 1: IsProperSubsetOf(...)100%66100%
File 1: IsProperSupersetOf(...)100%66100%
File 1: IsSubsetOf(...)100%66100%
File 1: IsSupersetOf(...)100%44100%
File 1: Overlaps(...)100%44100%
File 1: SetEquals(...)100%66100%
File 1: SymmetricExceptWith(...)100%66100%
File 1: UnionWith(...)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/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 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 set that stores unique values in a densely packed array
 23/// while providing O(1) lookups via an internal hash map.
 24/// </summary>
 25/// <remarks>
 26/// <para>
 27/// <see cref="SwiftPackedSet{T}"/> maintains values in a contiguous array for extremely
 28/// cache-friendly iteration while using a hash-based lookup table to guarantee fast
 29/// membership tests and removals.
 30/// </para>
 31/// <para>
 32/// Removal uses a swap-back strategy that keeps the dense storage contiguous but does not
 33/// preserve ordering. As a result, iteration order is not guaranteed to remain stable.
 34/// </para>
 35/// <para>
 36/// This structure is commonly used in high-performance systems such as ECS (Entity Component Systems)
 37/// where dense iteration speed is critical.
 38/// </para>
 39/// </remarks>
 40/// <typeparam name="T">The type of elements contained in the set.</typeparam>
 41[Serializable]
 42[JsonConverter(typeof(StateJsonConverterFactory))]
 43[MemoryPackable]
 44public sealed partial class SwiftPackedSet<T> : IStateBacked<SwiftArrayState<T>>, ISwiftCloneable<T>, ISet<T>, IEnumerab
 45    where T : notnull
 46{
 47    #region Constants
 48
 49    /// <summary>
 50    /// Represents the default initial capacity value used when no specific capacity is provided.
 51    /// </summary>
 52    public const int DefaultCapacity = 8;
 53
 254    private static readonly bool _clearReleasedSlots = RuntimeHelpers.IsReferenceOrContainsReferences<T>();
 55
 56    #endregion
 57
 58    #region Fields
 59
 60    private T[] _dense;
 61    private SwiftDictionary<T, int> _lookup;
 62    private int _count;
 63
 64    [NonSerialized]
 65    private uint _version;
 66
 67    [NonSerialized]
 68    private object? _syncRoot;
 69
 70    #endregion
 71
 72    #region Constructors
 73
 74    /// <summary>
 75    /// Initializes a new instance of the SwiftPackedSet class with the default capacity.
 76    /// </summary>
 14477    public SwiftPackedSet() : this(DefaultCapacity) { }
 78
 79    /// <summary>
 80    /// Initializes a new instance of the SwiftPackedSet class with the specified initial capacity.
 81    /// </summary>
 82    /// <remarks>
 83    /// The actual capacity is rounded up to the next power of two greater than or equal to the specified value,
 84    /// unless the specified value is less than or equal to the default capacity.
 85    /// </remarks>
 86    /// <param name="capacity">
 87    /// The initial number of elements that the set can contain before resizing.
 88    /// If less than or equal to the default capacity, the default capacity is used.
 89    /// Must be non-negative.
 90    /// </param>
 7591    public SwiftPackedSet(int capacity)
 92    {
 7593        capacity = capacity <= DefaultCapacity
 7594            ? DefaultCapacity
 7595            : SwiftHashTools.NextPowerOfTwo(capacity);
 96
 7597        _dense = new T[capacity];
 7598        _lookup = new SwiftDictionary<T, int>(capacity);
 7599    }
 100
 101    /// <summary>
 102    /// Initializes a new instance of the SwiftPackedSet class with the specified array state.
 103    /// </summary>
 104    /// <param name="state">The state object that provides the initial data and configuration for the set. Cannot be nul
 105    [MemoryPackConstructor]
 8106    public SwiftPackedSet(SwiftArrayState<T> state)
 107    {
 8108        State = state;
 109
 8110        ChronicleGuard.ThrowIfNull(_dense, nameof(_dense));
 8111        ChronicleGuard.ThrowIfNull(_lookup, nameof(_lookup));
 8112    }
 113
 114    #endregion
 115
 116    #region Properties
 117
 118    /// <summary>
 119    /// Gets the number of elements contained in the collection.
 120    /// </summary>
 121    [JsonIgnore]
 122    [MemoryPackIgnore]
 21123    public int Count => _count;
 124
 125    /// <summary>
 126    /// Gets the total number of elements that the collection can hold without resizing.
 127    /// </summary>
 128    [JsonIgnore]
 129    [MemoryPackIgnore]
 5130    public int Capacity => _dense.Length;
 131
 132    /// <summary>
 133    /// Gets a value indicating whether access to the collection is synchronized (thread safe).
 134    /// </summary>
 135    [JsonIgnore]
 136    [MemoryPackIgnore]
 1137    public bool IsSynchronized => false;
 138
 139    /// <inheritdoc/>
 140    [JsonIgnore]
 141    [MemoryPackIgnore]
 3142    public object SyncRoot => _syncRoot ??= new object();
 143
 144    /// <summary>
 145    /// Gets the underlying dense array of elements.
 146    /// </summary>
 147    [JsonIgnore]
 148    [MemoryPackIgnore]
 12149    public T[] Dense => _dense;
 150
 151    /// <inheritdoc/>
 152    [JsonIgnore]
 153    [MemoryPackIgnore]
 1154    public bool IsReadOnly => false;
 155
 156    /// <summary>
 157    /// Gets or sets the current state of the array, including its items and order.
 158    /// </summary>
 159    /// <remarks>
 160    /// Use this property to capture or restore the array's contents and structure.
 161    /// Setting this property replaces the entire array with the provided state.
 162    /// </remarks>
 163    [JsonInclude]
 164    [MemoryPackInclude]
 165    public SwiftArrayState<T> State
 166    {
 167        get
 168        {
 6169            var values = new T[_count];
 6170            Array.Copy(_dense, values, _count);
 171
 6172            return new SwiftArrayState<T>(values);
 173        }
 174        internal set
 175        {
 8176            ChronicleGuard.ThrowIfNull(value.Items, nameof(value.Items));
 177
 8178            var values = value.Items;
 179
 8180            int n = values.Length;
 8181            int newCapacity = n < DefaultCapacity
 8182                ? DefaultCapacity
 8183                : SwiftHashTools.NextPowerOfTwo(n);
 184
 8185            _dense = new T[newCapacity];
 8186            _lookup = new SwiftDictionary<T, int>(newCapacity);
 187
 8188            if (n > 0)
 189            {
 5190                Array.Copy(values, _dense, n);
 191
 2042192                for (int i = 0; i < n; i++)
 1016193                    _lookup.Add(values[i], i);
 194            }
 195
 8196            _count = n;
 8197            _version++;
 8198        }
 199    }
 200
 201    #endregion
 202
 203    #region Core Operations
 204
 205    /// <inheritdoc/>
 206    public bool Contains(T value)
 1040207        => _lookup.ContainsKey(value);
 208
 209    /// <summary>
 210    /// Returns a read-only span over the populated dense portion of the set.
 211    /// </summary>
 1212    public ReadOnlySpan<T> AsReadOnlySpan() => _dense.AsSpan(0, _count);
 213
 214    /// <summary>
 215    /// Determines whether the <see cref="SwiftPackedSet{T}"/> contains an element that matches the conditions defined b
 216    /// </summary>
 217    /// <param name="match">The predicate that defines the conditions of the element to search for.</param>
 218    /// <returns><c>true</c> if the <see cref="SwiftPackedSet{T}"/> contains one or more elements that match the specifi
 219    public bool Exists(Predicate<T> match)
 220    {
 3221        ChronicleGuard.ThrowIfNull(match, nameof(match));
 222
 10223        for (int i = 0; i < _count; i++)
 224        {
 4225            if (match(_dense[i]))
 1226                return true;
 227        }
 228
 1229        return false;
 230    }
 231
 232    /// <summary>
 233    /// Searches for an element that matches the conditions defined by the specified predicate, and returns the first ma
 234    /// </summary>
 235    /// <param name="match">The predicate that defines the conditions of the element to search for.</param>
 236    /// <returns>The first element that matches the conditions defined by the specified predicate, if found; otherwise, 
 237    public T Find(Predicate<T> match)
 238    {
 2239        ChronicleGuard.ThrowIfNull(match, nameof(match));
 240
 10241        for (int i = 0; i < _count; i++)
 242        {
 4243            if (match(_dense[i]))
 1244                return _dense[i];
 245        }
 246
 1247        return default!;
 248    }
 249
 250    /// <inheritdoc/>
 251    public bool Add(T value)
 252    {
 11263253        if (_lookup.ContainsKey(value))
 4254            return false;
 255
 11259256        EnsureCapacity(_count + 1);
 257
 11259258        _dense[_count] = value;
 11259259        _lookup.Add(value, _count);
 260
 11259261        _count++;
 11259262        _version++;
 263
 11259264        return true;
 265    }
 266
 1267    void ICollection<T>.Add(T item) => Add(item);
 268
 269    /// <inheritdoc/>
 270    public bool Remove(T value)
 271    {
 5014272        if (!_lookup.TryGetValue(value, out int index))
 3273            return false;
 274
 5011275        int last = --_count;
 276
 5011277        if (index != last)
 278        {
 5007279            T moved = _dense[last];
 280
 5007281            _dense[index] = moved;
 5007282            _lookup[moved] = index;
 283        }
 284
 5011285        if (_clearReleasedSlots)
 3286            _dense[last] = default!;
 5011287        _lookup.Remove(value);
 288
 5011289        _version++;
 5011290        return true;
 291    }
 292
 293    /// <inheritdoc/>
 294    public void Clear()
 295    {
 149296        if (_count == 0) return;
 297
 139298        if (_clearReleasedSlots)
 131299            Array.Clear(_dense, 0, _count);
 139300        _lookup.Clear();
 301
 139302        _count = 0;
 139303        _version++;
 139304    }
 305
 306    /// <summary>
 307    /// Removes all elements, optionally releasing references throughout retained backing storage.
 308    /// </summary>
 309    /// <param name="clearRetainedReferences">If true, also releases references outside the live range; otherwise uses o
 310    /// <remarks>Capacity is preserved. Full reference cleanup can take time proportional to retained capacity.</remarks
 311    public void Clear(bool clearRetainedReferences)
 312    {
 136313        if (clearRetainedReferences && _clearReleasedSlots)
 314        {
 130315            Array.Clear(_dense, _count, _dense.Length - _count);
 130316            _lookup.Clear(clearRetainedReferences: true);
 317        }
 136318        Clear();
 136319    }
 320
 321    #endregion
 322
 323    #region Capacity
 324
 325    /// <summary>
 326    /// Ensures that the internal storage has at least the specified capacity, expanding it if necessary.
 327    /// </summary>
 328    /// <remarks>
 329    /// If the current capacity is less than the specified value, the internal storage is resized to
 330    /// the next power of two greater than or equal to the specified capacity.
 331    /// Existing elements are preserved.
 332    /// </remarks>
 333    /// <param name="capacity">The minimum number of elements that the internal storage should be able to hold. Must be 
 334    public void EnsureCapacity(int capacity)
 335    {
 11260336        int newCapacity = SwiftHashTools.NextPowerOfTwo(capacity);
 11260337        if (newCapacity <= _dense.Length)
 11242338            return;
 339
 18340        var newArray = new T[newCapacity];
 18341        Array.Copy(_dense, newArray, _count);
 342
 18343        _dense = newArray;
 18344    }
 345
 346    #endregion
 347
 348    #region Enumeration
 349
 350    /// <inheritdoc cref="IEnumerable.GetEnumerator()"/>
 55351    public SwiftPackedSetEnumerator GetEnumerator() => new(this);
 34352    IEnumerator<T> IEnumerable<T>.GetEnumerator() => GetEnumerator();
 19353    IEnumerator IEnumerable.GetEnumerator() => GetEnumerator();
 354
 355
 356
 357    #endregion
 358
 359    #region Clone
 360
 361    /// <inheritdoc/>
 362    public void CloneTo(ICollection<T> output)
 363    {
 1364        ChronicleGuard.ThrowIfNull(output, nameof(output));
 365
 1366        output.Clear();
 367
 6368        for (int i = 0; i < _count; i++)
 2369            output.Add(_dense[i]);
 1370    }
 371
 372    /// <inheritdoc/>
 373    public void CopyTo(T[] array, int arrayIndex)
 374    {
 4375        ChronicleGuard.ThrowIfNull(array, nameof(array));
 4376        ChronicleGuard.ThrowIfArrayIndexInvalid(arrayIndex, array.Length);
 3377        ChronicleGuard.ThrowIfArgument(array.Length - arrayIndex < _count, nameof(array), "Destination array is not long
 378
 2379        Array.Copy(_dense, 0, array, arrayIndex, _count);
 2380    }
 381
 382    #endregion
 383
 384    #region ISet<T> Implementations
 385
 386    /// <inheritdoc/>
 387    public void ExceptWith(IEnumerable<T> other)
 388    {
 2389        ChronicleGuard.ThrowIfNull(other, nameof(other));
 390
 2391        if (ReferenceEquals(this, other))
 392        {
 1393            Clear();
 1394            return;
 395        }
 396
 1397        var otherSet = new SwiftHashSet<T>(other);
 398
 8399        foreach (var item in otherSet)
 3400            Remove(item);
 1401    }
 402
 403    /// <inheritdoc/>
 404    public void IntersectWith(IEnumerable<T> other)
 405    {
 2406        ChronicleGuard.ThrowIfNull(other, nameof(other));
 407
 2408        if (ReferenceEquals(this, other))
 1409            return;
 410
 1411        var otherSet = new SwiftHashSet<T>(other);
 412
 10413        for (int i = _count - 1; i >= 0; i--)
 414        {
 4415            var value = _dense[i];
 4416            if (!otherSet.Contains(value))
 2417                Remove(value);
 418        }
 1419    }
 420
 421    /// <inheritdoc/>
 422    public bool IsProperSubsetOf(IEnumerable<T> other)
 423    {
 3424        ChronicleGuard.ThrowIfNull(other, nameof(other));
 425
 3426        var set = new SwiftHashSet<T>(other);
 427
 3428        if (_count >= set.Count)
 1429            return false;
 430
 14431        for (int i = 0; i < _count; i++)
 6432            if (!set.Contains(_dense[i]))
 1433                return false;
 434
 1435        return true;
 436    }
 437
 438    /// <inheritdoc/>
 439    public bool IsProperSupersetOf(IEnumerable<T> other)
 440    {
 3441        ChronicleGuard.ThrowIfNull(other, nameof(other));
 442
 3443        var set = new SwiftHashSet<T>(other);
 444
 3445        if (_count <= set.Count)
 1446            return false;
 447
 9448        foreach (var item in set)
 3449            if (!Contains(item))
 1450                return false;
 451
 1452        return true;
 1453    }
 454
 455    /// <inheritdoc/>
 456    public bool IsSubsetOf(IEnumerable<T> other)
 457    {
 3458        ChronicleGuard.ThrowIfNull(other, nameof(other));
 459
 3460        var set = new SwiftHashSet<T>(other);
 461
 3462        if (_count > set.Count)
 1463            return false;
 464
 14465        for (int i = 0; i < _count; i++)
 6466            if (!set.Contains(_dense[i]))
 1467                return false;
 468
 1469        return true;
 470    }
 471
 472    /// <inheritdoc/>
 473    public bool IsSupersetOf(IEnumerable<T> other)
 474    {
 2475        ChronicleGuard.ThrowIfNull(other, nameof(other));
 476
 13477        foreach (var item in other)
 5478            if (!Contains(item))
 1479                return false;
 480
 1481        return true;
 1482    }
 483
 484    /// <inheritdoc/>
 485    public bool Overlaps(IEnumerable<T> other)
 486    {
 2487        ChronicleGuard.ThrowIfNull(other, nameof(other));
 488
 9489        foreach (var item in other)
 3490            if (Contains(item))
 1491                return true;
 492
 1493        return false;
 1494    }
 495
 496    /// <inheritdoc/>
 497    public bool SetEquals(IEnumerable<T> other)
 498    {
 6499        ChronicleGuard.ThrowIfNull(other, nameof(other));
 500
 6501        var set = new SwiftHashSet<T>(other);
 502
 6503        if (_count != set.Count)
 1504            return false;
 505
 38506        for (int i = 0; i < _count; i++)
 15507            if (!set.Contains(_dense[i]))
 1508                return false;
 509
 4510        return true;
 511    }
 512
 513    /// <inheritdoc/>
 514    public void SymmetricExceptWith(IEnumerable<T> other)
 515    {
 2516        ChronicleGuard.ThrowIfNull(other, nameof(other));
 517
 2518        if (ReferenceEquals(this, other))
 519        {
 1520            Clear();
 1521            return;
 522        }
 523
 1524        var set = new SwiftHashSet<T>(other);
 525
 6526        foreach (var item in set)
 527        {
 2528            if (!Remove(item))
 1529                Add(item);
 530        }
 1531    }
 532
 533    /// <inheritdoc/>
 534    public void UnionWith(IEnumerable<T> other)
 535    {
 1536        ChronicleGuard.ThrowIfNull(other, nameof(other));
 537
 6538        foreach (var item in other)
 2539            Add(item);
 1540    }
 541
 542    #endregion
 543}

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

#LineLine coverage
 1//=======================================================================
 2// SwiftPackedSet.SwiftPackedSetEnumerator.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 SwiftPackedSet<T>
 16    where T : notnull
 17{
 18    /// <summary>
 19    /// Enumerates the elements of a <see cref="SwiftPackedSet{T}"/> collection.
 20    /// </summary>
 21    /// <remarks>
 22    /// The enumerator is invalidated if the collection is modified after the enumerator is created.
 23    /// In such cases, calling MoveNext or Reset will throw an InvalidOperationException.
 24    /// </remarks>
 25    public struct SwiftPackedSetEnumerator : IEnumerator<T>
 26    {
 27        private readonly SwiftPackedSet<T> _set;
 28        private readonly uint _version;
 29        private int _index;
 30
 31        internal SwiftPackedSetEnumerator(SwiftPackedSet<T> set)
 32        {
 5533            _set = set;
 5534            _version = set._version;
 5535            _index = -1;
 5536            Current = default!;
 5537        }
 38
 39        /// <inheritdoc/>
 40        public T Current { get; private set; }
 41
 42        object IEnumerator.Current
 43        {
 44            get
 45            {
 3246                ChronicleGuard.ThrowIfTrue((uint)_index >= (uint)_set._count, message: "Enumerator is before the first e
 1447                return Current!;
 48            }
 49        }
 50
 51        /// <inheritdoc/>
 52        public bool MoveNext()
 53        {
 10454            ChronicleGuard.ThrowIfTrue(_version != _set._version, message: "Collection was modified during enumeration."
 55
 10056            int next = _index + 1;
 10057            if (next >= _set._count)
 58            {
 5059                _index = _set._count;
 5060                Current = default!;
 5061                return false;
 62            }
 63
 5064            _index = next;
 5065            Current = _set._dense[next];
 5066            return true;
 67        }
 68
 69        /// <inheritdoc/>
 70        public void Reset()
 71        {
 1172            ChronicleGuard.ThrowIfTrue(_version != _set._version, message: "Collection was modified during enumeration."
 73
 774            _index = -1;
 775            Current = default!;
 776        }
 77
 78        /// <inheritdoc/>
 3779        public void Dispose() => _index = -1;
 80    }
 81}