< Summary

Information
Class: SwiftCollections.SwiftHashSet<T>
Assembly: SwiftCollections
File(s): /home/runner/work/SwiftCollections/SwiftCollections/src/SwiftCollections/Collection/SwiftHashSet.cs
Line coverage
100%
Covered lines: 374
Uncovered lines: 0
Coverable lines: 374
Total lines: 1029
Line coverage: 100%
Branch coverage
100%
Covered branches: 206
Total branches: 206
Branch coverage: 100%
Method coverage

Feature is only available for sponsors

Upgrade to PRO version

Metrics

MethodBranch coverage Crap Score Cyclomatic complexity Line coverage
.ctor()100%11100%
.ctor(...)100%11100%
.ctor(...)100%11100%
.ctor(...)100%44100%
.ctor(...)100%11100%
get_Count()100%11100%
get_Comparer()100%11100%
System.Collections.Generic.ICollection<T>.get_IsReadOnly()100%11100%
get_Item(...)100%11100%
get_State()100%22100%
set_State(...)100%66100%
Add(...)100%11100%
System.Collections.Generic.ICollection<T>.Add(...)100%11100%
AddRange(...)100%66100%
AddKnownCountRange(...)100%44100%
AddUnknownCountRange(...)100%44100%
InsertIfNotExists(...)100%2626100%
Remove(...)100%1414100%
Clear()100%44100%
CheckLoadThreshold()100%22100%
EnsureCapacityForAddRange(...)100%22100%
EnsureCapacity(...)100%22100%
Resize(...)100%88100%
TrimExcess()100%1212100%
CalculateAdaptiveResizeFactors(...)100%66100%
Initialize(...)100%22100%
Contains(...)100%11100%
Exists(...)100%66100%
Find(...)100%66100%
TryGetValue(...)100%22100%
CopyTo(...)100%44100%
SetComparer(...)100%22100%
SwitchToRandomizedComparer()100%11100%
RehashEntries()100%88100%
FindEntry(...)100%1414100%
GetEnumerator()100%11100%
System.Collections.Generic.IEnumerable<T>.GetEnumerator()100%11100%
System.Collections.IEnumerable.GetEnumerator()100%11100%
.ctor(...)100%11100%
get_Current()100%11100%
System.Collections.IEnumerator.get_Current()100%11100%
MoveNext()100%44100%
Reset()100%11100%
Dispose()100%11100%
ExceptWith(...)100%44100%
IntersectWith(...)100%88100%
IsProperSubsetOf(...)100%88100%
IsProperSupersetOf(...)100%66100%
IsSubsetOf(...)100%88100%
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/SwiftHashSet.cs

#LineLine coverage
 1//=======================================================================
 2// SwiftHashSet.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 MemoryPack;
 15using SwiftCollections.Diagnostics;
 16using SwiftCollections.Utility;
 17
 18namespace SwiftCollections;
 19
 20/// <summary>
 21/// Represents a high-performance set of unique values with efficient operations for addition, removal, and lookup
 22/// </summary>
 23/// <typeparam name="T">The type of elements in the set.</typeparam>
 24/// <remarks>
 25/// The comparer is not serialized. After deserialization the set reverts
 26/// to the same default comparer selection used by a new instance. String values
 27/// use SwiftCollections' deterministic default comparer. Object values use a
 28/// SwiftCollections comparer that hashes strings deterministically, while other
 29/// object-value determinism still depends on the underlying value type's
 30/// <see cref="object.GetHashCode()"/> implementation. Other types use
 31/// <see cref="EqualityComparer{T}.Default"/>.
 32///
 33/// If a custom comparer is required it can be reapplied using
 34/// <see cref="SetComparer(IEqualityComparer{T})"/>.
 35/// </remarks>
 36[Serializable]
 37[JsonConverter(typeof(StateJsonConverterFactory))]
 38[MemoryPackable]
 39public sealed partial class SwiftHashSet<T> : IStateBacked<SwiftArrayState<T>>, ISet<T>, ICollection<T>, IEnumerable<T>,
 40    where T : notnull
 41{
 42    #region Constants
 43
 44    /// <summary>
 45    /// The default initial capacity of the set.
 46    /// </summary>
 47    public const int DefaultCapacity = 8;
 48
 49    /// <summary>
 50    /// Determines the maximum allowable load factor before resizing the hash set to maintain performance.
 51    /// </summary>
 52    private const float _LoadFactorThreshold = 0.85f;
 53
 54    #endregion
 55
 56    #region Fields
 57
 58    /// <summary>
 59    /// The array containing the entries of the SwiftHashSet.
 60    /// </summary>
 61    /// <remarks>
 62    /// Capacity will always be a power of two for efficient pooling cache.
 63    /// </remarks>
 64    internal Entry[] _entries;
 65
 66    /// <summary>
 67    /// The total number of entries in the hash set
 68    /// </summary>
 69    private int _count;
 70
 71    private int _lastIndex;
 72
 73    /// <summary>
 74    /// A mask used for efficiently computing the entry index from a hash code.
 75    /// This is typically the size of the entry array minus one, assuming the size is a power of two.
 76    /// </summary>
 77    private int _entryMask;
 78
 79    /// <summary>
 80    /// The comparer used to determine equality of keys and to generate hash codes.
 81    /// </summary>
 82    private IEqualityComparer<T> _comparer;
 83
 84    /// <summary>
 85    /// Specifies the dynamic growth factor for resizing, adjusted based on recent usage patterns.
 86    /// </summary>
 87    private int _adaptiveResizeFactor;
 88
 89    /// <summary>
 90    /// Tracks the count threshold at which the hash set should resize based on the load factor.
 91    /// </summary>
 92    private uint _nextResizeCount;
 93
 94    /// <summary>
 95    /// Represents the moving average of the fill rate, used to dynamically adjust resizing behavior.
 96    /// </summary>
 97    private double _movingFillRate;
 98
 99    private int _maxStepCount;
 100
 101    /// <summary>
 102    /// A version counter used to track modifications to the set.
 103    /// Incremented on mutations to detect changes during enumeration and ensure enumerator validity.
 104    /// </summary>
 105    private uint _version;
 106
 107    #endregion
 108
 109    #region Nested Types
 110
 111    /// <summary>
 112    /// Represents a single value in the set, including its hash code for quick access.
 113    /// </summary>
 114    internal struct Entry
 115    {
 116        public T Value;
 117        public int HashCode;    // Lower 31 bits of hash code, -1 if deleted probe tombstone
 118        public bool IsUsed;
 119    }
 120
 121    #endregion
 122
 123    #region Constructors
 124
 125    /// <summary>
 126    /// Initialize a new instance of <see cref="SwiftHashSet{T}"/> with customizable capacity and comparer for optimal p
 127    /// </summary>
 144128    public SwiftHashSet() : this(DefaultCapacity, null) { }
 129
 130    /// <inheritdoc cref="SwiftHashSet()"/>
 12131    public SwiftHashSet(IEqualityComparer<T>? comparer) : this(DefaultCapacity, comparer) { }
 132
 133    /// <summary>
 134    /// Initializes a new instance of the <see cref="SwiftHashSet{T}"/> class that is empty and has the default initial 
 135    /// </summary>
 92136    public SwiftHashSet(int capacity, IEqualityComparer<T>? comparer = null)
 137    {
 92138        Initialize(capacity, comparer);
 139
 92140        SwiftThrowHelper.ThrowIfNull(_entries, nameof(_entries));
 92141        SwiftThrowHelper.ThrowIfNull(_comparer, nameof(_comparer));
 92142    }
 143
 144    /// <summary>
 145    /// Initializes a new instance of the <see cref="SwiftHashSet{T}"/> class that contains elements copied from the spe
 146    /// </summary>
 147    /// <param name="collection">The collection whose elements are copied to the new set.</param>
 148    /// <param name="comparer">The comparer to use when comparing elements.</param>
 42149    public SwiftHashSet(IEnumerable<T> collection, IEqualityComparer<T>? comparer = null)
 150    {
 42151        SwiftThrowHelper.ThrowIfNull(collection, nameof(collection));
 152
 42153        int count = (collection as ICollection<T>)?.Count ?? DefaultCapacity;
 42154        int size = (int)(count / _LoadFactorThreshold);  // Dynamic padding based on collision estimation
 42155        Initialize(size, comparer);
 156
 42157        SwiftThrowHelper.ThrowIfNull(_entries, nameof(_entries));
 42158        SwiftThrowHelper.ThrowIfNull(_comparer, nameof(_comparer));
 159
 356160        foreach (T item in collection)
 136161            InsertIfNotExists(item);
 42162    }
 163
 164    ///  <summary>
 165    ///  Initializes a new instance of the <see cref="SwiftHashSet{T}"/> class with the specified <see cref="SwiftArrayS
 166    ///  </summary>
 167    ///  <param name="state">The state containing the internal array, count, offset, and version for initialization.</pa
 168    [MemoryPackConstructor]
 7169    public SwiftHashSet(SwiftArrayState<T> state)
 170    {
 7171        State = state;
 172
 7173        SwiftThrowHelper.ThrowIfNull(_entries, nameof(_entries));
 7174        SwiftThrowHelper.ThrowIfNull(_comparer, nameof(_comparer));
 7175    }
 176
 177    #endregion
 178
 179    #region Properties
 180
 181    /// <summary>
 182    /// Gets the number of elements contained in the set.
 183    /// </summary>
 184    [JsonIgnore]
 185    [MemoryPackIgnore]
 83186    public int Count => _count;
 187
 188    /// <summary>
 189    /// Gets the <see cref="IEqualityComparer{T}"/> object that is used to determine equality for the values in the set.
 190    /// </summary>
 191    [JsonIgnore]
 192    [MemoryPackIgnore]
 14193    public IEqualityComparer<T> Comparer => _comparer;
 194
 195    [JsonIgnore]
 196    [MemoryPackIgnore]
 1197    bool ICollection<T>.IsReadOnly => false;
 198
 199    /// <summary>
 200    /// Gets the stored value that matches the specified key.
 201    /// </summary>
 202    /// <param name="key">The lookup value used to find an equal element in the set.</param>
 203    /// <exception cref="KeyNotFoundException">No matching value exists in the set.</exception>
 204    [JsonIgnore]
 205    [MemoryPackIgnore]
 206    public T this[T key]
 207    {
 208        get
 209        {
 2210            int index = FindEntry(key);
 2211            SwiftThrowHelper.ThrowIfKeyInvalid(index, key);
 1212            return _entries[index].Value;
 213        }
 214    }
 215
 216    /// <summary>
 217    /// Gets or sets the current state of the array, including its items and structure.
 218    /// </summary>
 219    /// <remarks>
 220    /// Setting this property replaces the contents of the array with the items from the specified state.
 221    /// If the provided state is empty, the array is cleared.
 222    /// The setter is intended for internal use and may reset internal versioning.
 223    /// </remarks>
 224    [JsonInclude]
 225    [MemoryPackInclude]
 226    public SwiftArrayState<T> State
 227    {
 228        get
 229        {
 6230            if (_count == 0)
 1231                return new SwiftArrayState<T>(Array.Empty<T>());
 232
 5233            T[] items = new T[_count];
 5234            CopyTo(items, 0);
 235
 5236            return new SwiftArrayState<T>(items);
 237        }
 238        internal set
 239        {
 7240            SwiftThrowHelper.ThrowIfNull(value.Items, nameof(value));
 241
 7242            T[] items = value.Items;
 7243            int count = items.Length;
 244
 7245            if (count == 0)
 246            {
 1247                Initialize(DefaultCapacity);
 1248                _count = 0;
 1249                _version = 0;
 1250                return;
 251            }
 252
 6253            int size = (int)(count / _LoadFactorThreshold);
 6254            Initialize(size);
 255
 60256            foreach (T item in items)
 24257                if (item != null)
 23258                    InsertIfNotExists(item);
 259
 6260            _version = 0;
 6261        }
 262    }
 263
 264    #endregion
 265
 266    #region Collection Manipulation
 267
 268    /// <inheritdoc/>
 269    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 270    public bool Add(T item)
 271    {
 215803272        CheckLoadThreshold();
 215803273        return InsertIfNotExists(item);
 274    }
 275
 1276    void ICollection<T>.Add(T item) => Add(item);
 277
 278    /// <summary>
 279    /// Adds the elements of the specified collection to the set, ignoring null values and duplicates.
 280    /// </summary>
 281    /// <remarks>
 282    /// If the source collection is the same instance as the set, the method returns without making any changes.
 283    /// The method preserves single-pass enumeration for sources that do not support multiple iterations.</remarks>
 284    /// <param name="items">The collection of elements to add to the set. Elements that are null or already present in t
 285    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 286    public void AddRange(IEnumerable<T> items)
 287    {
 5288        SwiftThrowHelper.ThrowIfNull(items, nameof(items));
 289
 5290        if (ReferenceEquals(this, items))
 1291            return;
 292
 4293        if (items is ICollection<T> collection)
 294        {
 2295            AddKnownCountRange(collection, collection.Count);
 2296            return;
 297        }
 298
 2299        if (items is IReadOnlyCollection<T> readOnlyCollection)
 300        {
 1301            AddKnownCountRange(readOnlyCollection, readOnlyCollection.Count);
 1302            return;
 303        }
 304
 1305        AddUnknownCountRange(items);
 1306    }
 307
 308    private void AddKnownCountRange(IEnumerable<T> items, int count)
 309    {
 3310        EnsureCapacityForAddRange(count);
 311
 20312        foreach (T item in items)
 7313            if (item != null)
 7314                InsertIfNotExists(item);
 3315    }
 316
 317    private void AddUnknownCountRange(IEnumerable<T> items)
 318    {
 8319        foreach (T item in items)
 3320            if (item != null)
 3321                Add(item);
 1322    }
 323
 324    /// <summary>
 325    /// Adds the specified element to the set if it's not already present.
 326    /// </summary>
 327    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 328    private bool InsertIfNotExists(T item)
 329    {
 215970330        SwiftThrowHelper.ThrowIfNullGeneric(item, nameof(item));
 331
 215969332        int hashCode = _comparer.GetHashCode(item) & 0x7FFFFFFF;
 215969333        int entryIndex = hashCode & _entryMask;
 334
 215969335        int firstDeletedIndex = -1;
 215969336        int step = 1;
 215969337        int probeLimit = _entries.Length;
 373187338        while ((uint)step <= (uint)probeLimit)
 339        {
 373186340            ref Entry entry = ref _entries[entryIndex];
 373186341            if (entry.IsUsed)
 342            {
 157210343                if (entry.HashCode == hashCode && _comparer.Equals(entry.Value, item))
 13344                    return false; // Item already exists
 345            }
 215976346            else if (entry.HashCode == -1)
 347            {
 29348                if (firstDeletedIndex < 0) firstDeletedIndex = entryIndex;
 349            }
 350            else
 351            {
 352                break;
 353            }
 354
 157218355            entryIndex = (entryIndex + step * step) & _entryMask; // Quadratic probing
 157218356            step++;
 357        }
 358
 215956359        if (firstDeletedIndex >= 0)
 7360            entryIndex = firstDeletedIndex;
 215949361        else if ((uint)step > (uint)probeLimit)
 362        {
 1363            Resize(_entries.Length * _adaptiveResizeFactor);
 1364            return InsertIfNotExists(item);
 365        }
 366
 331624367        if ((uint)entryIndex > (uint)_lastIndex) _lastIndex = entryIndex;
 368
 215955369        _entries[entryIndex].HashCode = hashCode;
 215955370        _entries[entryIndex].Value = item;
 215955371        _entries[entryIndex].IsUsed = true;
 215955372        _count++;
 215955373        _version++;
 374
 215955375        if ((uint)step > (uint)_maxStepCount)
 376        {
 2443377            _maxStepCount = step;
 2443378            if (_comparer is not IRandomedEqualityComparer &&
 2443379                _maxStepCount > 100 &&
 2443380                SwiftHashTools.IsWellKnownEqualityComparer(_comparer))
 1381                SwitchToRandomizedComparer();  // Attempt to recompute hash code with potential randomization for better
 382        }
 383
 215955384        return true;
 385    }
 386
 387    /// <summary>
 388    /// Removes the specified element from the set.
 389    /// </summary>
 390    /// <param name="item">The element to remove from the set.</param>
 391    /// <returns>
 392    /// True if the element is successfully found and removed; otherwise, false.
 393    /// </returns>
 394    public bool Remove(T item)
 395    {
 100568396        SwiftThrowHelper.ThrowIfNullGeneric(item, nameof(item));
 397
 100567398        int hashCode = _comparer.GetHashCode(item) & 0x7FFFFFFF;
 100567399        int entryIndex = hashCode & _entryMask;
 400
 100567401        int step = 0;
 150468402        while ((uint)step <= (uint)_lastIndex)
 403        {
 150467404            ref Entry entry = ref _entries[entryIndex];
 405            // Stop probing if an unused entry is found (not deleted)
 150467406            if (!entry.IsUsed && entry.HashCode != -1)
 4407                return false;
 150463408            if (entry.IsUsed && entry.HashCode == hashCode && _comparer.Equals(entry.Value, item))
 409            {
 410                // Mark entry as deleted
 100562411                entry.IsUsed = false;
 100562412                entry.Value = default!;
 100562413                entry.HashCode = -1;
 100562414                _count--;
 100563415                if ((uint)_count == 0) _lastIndex = 0;
 100562416                _version++;
 100562417                return true;
 418            }
 419
 420            // Entry not found in expected entry, it either doesn't exist or was moved via quadratic probing
 49901421            step++;
 49901422            entryIndex = (entryIndex + step * step) & _entryMask;
 423        }
 1424        return false; // Item not found after full loop
 425    }
 426
 427    /// <summary>
 428    /// Removes all elements from the set.
 429    /// </summary>
 430    public void Clear()
 431    {
 2090432        if ((uint)_count == 0) return;
 433
 37602434        for (uint i = 0; i <= (uint)_lastIndex; i++)
 435        {
 436            // Clear is a full reset, not a delete; future probes must be able to stop
 437            // at these now-empty slots instead of treating them as tombstones.
 16713438            _entries[i].HashCode = 0;
 16713439            _entries[i].Value = default!;
 16713440            _entries[i].IsUsed = false;
 441        }
 442
 2088443        _count = 0;
 2088444        _lastIndex = 0;
 2088445        _maxStepCount = 0;
 2088446        _movingFillRate = 0;
 2088447        _adaptiveResizeFactor = 4;
 448
 2088449        _version++;
 2088450    }
 451
 452    #endregion
 453
 454    #region Capacity Management
 455
 456    /// <summary>
 457    /// Ensures that the hash set is resized when the current load factor exceeds the predefined threshold.
 458    /// </summary>
 459    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 460    private void CheckLoadThreshold()
 461    {
 215803462        if ((uint)_count >= _nextResizeCount)
 35463            Resize(_entries.Length * _adaptiveResizeFactor);
 215803464    }
 465
 466    /// <summary>
 467    /// Ensures there is enough room to add a batch of items without repeatedly checking the load threshold.
 468    /// </summary>
 469    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 470    private void EnsureCapacityForAddRange(int incomingCount)
 471    {
 3472        if (incomingCount <= 0)
 1473            return;
 474
 2475        long requiredCount = (long)_count + incomingCount;
 2476        SwiftThrowHelper.ThrowIfTrue(requiredCount > int.MaxValue, message: "The collection is too large.");
 477
 2478        double minimumCapacity = Math.Ceiling(requiredCount / (double)_LoadFactorThreshold);
 2479        EnsureCapacity((int)Math.Min(minimumCapacity, int.MaxValue));
 2480    }
 481
 482    /// <summary>
 483    /// Ensures that the set can hold up to the specified number of elements without resizing.
 484    /// </summary>
 485    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 486    public void EnsureCapacity(int capacity)
 487    {
 5488        capacity = SwiftHashTools.NextPowerOfTwo(capacity);  // Capacity must be a power of 2 for proper masking
 5489        if (capacity > _entries.Length)
 3490            Resize(capacity);
 5491    }
 492
 493    /// <summary>
 494    /// Resizes the hash set to the specified capacity, redistributing all entries to maintain efficiency.
 495    /// </summary>
 496    /// <param name="newSize"></param>
 497    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 498    private void Resize(int newSize)
 499    {
 39500        Entry[] newEntries = new Entry[newSize];
 39501        int newMask = newSize - 1;
 502
 39503        int lastIndex = 0;
 184578504        for (uint i = 0; i <= (uint)_lastIndex; i++)
 505        {
 92250506            if (_entries[i].IsUsed)
 507            {
 85688508                ref Entry oldEntry = ref _entries[i];
 85688509                int newIndex = oldEntry.HashCode & newMask;
 510                // If current entry not available, perform Quadratic probing to find the next available entry
 85688511                int step = 1;
 90616512                while (newEntries[newIndex].IsUsed)
 513                {
 4928514                    newIndex = (newIndex + step * step) & newMask;
 4928515                    step++;
 516                }
 85688517                newEntries[newIndex] = oldEntry;
 134287518                if (newIndex > lastIndex) lastIndex = newIndex;
 519            }
 520        }
 521
 39522        _lastIndex = lastIndex;
 523
 39524        CalculateAdaptiveResizeFactors(newSize);
 525
 39526        _entries = newEntries;
 39527        _entryMask = newMask;
 528
 39529        _version++;
 39530    }
 531
 532    /// <summary>
 533    /// Sets the capacity of a <see cref="SwiftHashSet{T}"/> to the actual
 534    /// number of elements it contains, rounded up to a nearby next power of 2 value.
 535    /// </summary>
 536    public void TrimExcess()
 537    {
 3538        int newSize = _count <= DefaultCapacity ? DefaultCapacity : SwiftHashTools.NextPowerOfTwo(_count);
 4539        if (newSize >= _entries.Length) return;
 540
 2541        Entry[] newEntries = new Entry[newSize];
 2542        int newMask = newSize - 1;
 543
 2544        int lastIndex = 0;
 40545        for (int i = 0; i <= (uint)_lastIndex; i++)
 546        {
 18547            if (_entries[i].IsUsed)
 548            {
 15549                ref Entry oldEntry = ref _entries[i];
 15550                int newIndex = oldEntry.HashCode & newMask;
 551                // If current entry not available, perform quadratic probing to find the next available entry
 15552                int step = 1;
 18553                while (newEntries[newIndex].IsUsed)
 554                {
 3555                    newIndex = (newIndex + step * step) & newMask;
 3556                    step++;
 557                }
 15558                newEntries[newIndex] = oldEntry;
 28559                if (newIndex > lastIndex) lastIndex = newIndex;
 560            }
 561        }
 562
 2563        _lastIndex = lastIndex;
 564
 2565        CalculateAdaptiveResizeFactors(newSize);
 566
 2567        _entryMask = newMask;
 2568        _entries = newEntries;
 569
 2570        _version++;
 2571    }
 572
 573    /// <summary>
 574    ///  Updates adaptive resize parameters based on the current fill rate to balance memory usage and performance.
 575    /// </summary>
 576    /// <param name="newSize"></param>
 577    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 578    private void CalculateAdaptiveResizeFactors(int newSize)
 579    {
 580        // Calculate current fill rate and update moving average
 41581        double currentFillRate = (double)_count / newSize;
 41582        _movingFillRate = _movingFillRate == 0 ? currentFillRate : (_movingFillRate * 0.7 + currentFillRate * 0.3);
 583
 41584        if (_movingFillRate > 0.3f)
 3585            _adaptiveResizeFactor = 2; // Growth stabilizing
 38586        else if (_movingFillRate < 0.28f)
 37587            _adaptiveResizeFactor = 4; // Rapid growth
 588
 589        // Reset the resize threshold based on the new size
 41590        _nextResizeCount = (uint)(newSize * _LoadFactorThreshold);
 41591    }
 592
 593    #endregion
 594
 595    #region Utility Methods
 596
 597    /// <summary>
 598    /// Initializes the hash set with a given capacity, ensuring it starts with an optimal internal structure.
 599    /// </summary>
 600    /// <param name="capacity"></param>
 601    /// <param name="comparer"></param>
 602    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 603    private void Initialize(int capacity, IEqualityComparer<T>? comparer = null)
 604    {
 141605        _comparer = SwiftHashTools.GetDefaultEqualityComparer(comparer);
 606
 141607        int size = capacity < DefaultCapacity ? DefaultCapacity : SwiftHashTools.NextPowerOfTwo(capacity);
 141608        _entries = new Entry[size];
 141609        _entryMask = size - 1;
 610
 141611        _nextResizeCount = (uint)(size * _LoadFactorThreshold);
 141612        _adaptiveResizeFactor = 4; // start agressive
 141613        _movingFillRate = 0.0;
 141614    }
 615
 616    /// <summary>
 617    /// Determines whether the set contains the specified element.
 618    /// </summary>
 619    /// <param name="item">The element to locate in the set.</param>
 620    /// <returns>
 621    /// True if the set contains the specified element; otherwise, false.
 622    /// </returns>
 623    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 1387624    public bool Contains(T item) => FindEntry(item) >= 0;
 625
 626    /// <summary>
 627    /// Determines whether the <see cref="SwiftHashSet{T}"/> contains an element that matches the conditions defined by 
 628    /// </summary>
 629    /// <param name="match">The predicate that defines the conditions of the element to search for.</param>
 630    /// <returns><c>true</c> if the <see cref="SwiftHashSet{T}"/> contains one or more elements that match the specified
 631    public bool Exists(Predicate<T> match)
 632    {
 3633        SwiftThrowHelper.ThrowIfNull(match, nameof(match));
 634
 16635        for (int i = 0; i <= _lastIndex; i++)
 636        {
 7637            if (_entries[i].IsUsed && match(_entries[i].Value))
 1638                return true;
 639        }
 640
 1641        return false;
 642    }
 643
 644    /// <summary>
 645    /// Searches for an element that matches the conditions defined by the specified predicate, and returns the first ma
 646    /// </summary>
 647    /// <param name="match">The predicate that defines the conditions of the element to search for.</param>
 648    /// <returns>The first element that matches the conditions defined by the specified predicate, if found; otherwise, 
 649    public T Find(Predicate<T> match)
 650    {
 2651        SwiftThrowHelper.ThrowIfNull(match, nameof(match));
 652
 16653        for (int i = 0; i <= _lastIndex; i++)
 654        {
 7655            if (_entries[i].IsUsed && match(_entries[i].Value))
 1656                return _entries[i].Value;
 657        }
 658
 1659        return default!;
 660    }
 661
 662    /// <summary>
 663    /// Searches the set for a given value and returns the equal value it finds, if any.
 664    /// </summary>
 665    public bool TryGetValue(T expected, out T actual)
 666    {
 2667        int index = FindEntry(expected);
 2668        if (index >= 0)
 669        {
 1670            actual = _entries[index].Value;
 1671            return true;
 672        }
 1673        actual = default!;
 1674        return false;
 675    }
 676
 677    /// <summary>
 678    /// Copies the elements of the set to an array, starting at the specified array index.
 679    /// </summary>
 680    public void CopyTo(T[] array, int arrayIndex)
 681    {
 11682        SwiftThrowHelper.ThrowIfNull(array, nameof(array));
 10683        SwiftThrowHelper.ThrowIfArrayIndexInvalid(arrayIndex, array.Length);
 8684        SwiftThrowHelper.ThrowIfArgument(array.Length - arrayIndex < _count, nameof(array), "The array is not large enou
 685
 112686        for (uint i = 0; i <= (uint)_lastIndex; i++)
 687        {
 49688            if (_entries[i].IsUsed)
 28689                array[arrayIndex++] = _entries[i].Value;
 690        }
 7691    }
 692
 693    /// <summary>
 694    /// Switches the hash set's comparer and rehashes all entries
 695    /// using the new comparer to redistribute them across <see cref="_entries"/>.
 696    /// </summary>
 697    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 698    public void SetComparer(IEqualityComparer<T>? comparer = null)
 699    {
 5700        SwiftThrowHelper.ThrowIfNull(comparer, nameof(comparer));
 4701        if (ReferenceEquals(comparer, _comparer))
 1702            return;
 703
 3704        _comparer = comparer;
 3705        RehashEntries();
 3706    }
 707
 708    /// <summary>
 709    /// Replaces the hash set's comparer with a randomized comparer to mitigate high collision rates.
 710    /// </summary>
 711    private void SwitchToRandomizedComparer()
 712    {
 1713        _comparer = (IEqualityComparer<T>)SwiftHashTools.GetSwiftEqualityComparer(_comparer);
 714
 1715        RehashEntries();
 1716        _maxStepCount = 0;
 717
 1718        _version++;
 1719    }
 720
 721    /// <summary>
 722    /// Reconstructs the internal entry structure to align with updated hash codes, ensuring efficient access and storag
 723    /// </summary>
 724    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 725    private void RehashEntries()
 726    {
 4727        Entry[] newEntries = new Entry[_entries.Length];
 4728        int newMask = newEntries.Length - 1;
 729
 4730        int lastIndex = 0;
 584731        for (uint i = 0; i <= (uint)_lastIndex; i++)
 732        {
 288733            if (_entries[i].IsUsed)
 734            {
 101735                ref Entry oldEntry = ref _entries[i];
 101736                oldEntry.HashCode = _comparer.GetHashCode(oldEntry.Value) & 0x7FFFFFFF;
 101737                int newIndex = oldEntry.HashCode & newMask;
 101738                int step = 1;
 130739                while (newEntries[newIndex].IsUsed)
 740                {
 29741                    newIndex = (newIndex + step * step) & newMask; // Quadratic probing
 29742                    step++;
 743                }
 101744                newEntries[newIndex] = _entries[i];
 117745                if (newIndex > lastIndex) lastIndex = newIndex;
 746            }
 747        }
 748
 4749        _lastIndex = lastIndex;
 750
 4751        _entryMask = newMask;
 4752        _entries = newEntries;
 753
 4754        _version++;
 4755    }
 756
 757    /// <summary>
 758    /// Searches for an entry in the hash set by following its probing sequence, returning its index if found.
 759    /// </summary>
 760    /// <param name="item"></param>
 761    /// <returns></returns>
 762    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 763    private int FindEntry(T item)
 764    {
 1392765        if (item == null) return -1;
 766
 1390767        int hashCode = _comparer.GetHashCode(item) & 0x7FFFFFFF;
 1390768        int entryIndex = hashCode & _entryMask;
 769
 1390770        int step = 0;
 13575771        while ((uint)step <= (uint)_lastIndex)
 772        {
 13574773            ref Entry entry = ref _entries[entryIndex];
 774            // Stop probing if an unused entry is found (not deleted)
 13574775            if (!entry.IsUsed && entry.HashCode != -1)
 530776                return -1;
 13044777            if (entry.IsUsed && entry.HashCode == hashCode && _comparer.Equals(entry.Value, item))
 859778                return entryIndex; // Match found
 779
 780            // Perform quadratic probing to see if maybe the entry was shifted.
 12185781            step++;
 12185782            entryIndex = (entryIndex + step * step) & _entryMask;
 783
 784        }
 1785        return -1; // Item not found, full loop completed
 786    }
 787
 788    #endregion
 789
 790    #region Enumerators
 791
 792    /// <summary>
 793    /// Returns an enumerator that iterates through the set.
 794    /// </summary>
 38795    public SwiftHashSetEnumerator GetEnumerator() => new(this);
 16796    IEnumerator<T> IEnumerable<T>.GetEnumerator() => GetEnumerator();
 1797    IEnumerator IEnumerable.GetEnumerator() => GetEnumerator();
 798
 799    /// <summary>
 800    /// Provides an enumerator for iterating through the elements of the hash set, ensuring consistency during enumerati
 801    /// </summary>
 802    public struct SwiftHashSetEnumerator : IEnumerator<T>, IEnumerator, IDisposable
 803    {
 804        private readonly SwiftHashSet<T> _set;
 805        private readonly Entry[] _entries;
 806        private readonly uint _version;
 807        private int _index;
 808        private T _current;
 809
 810        internal SwiftHashSetEnumerator(SwiftHashSet<T> set)
 811        {
 38812            _set = set;
 38813            _version = set._version;
 38814            _entries = set._entries; // Cache the entry array
 38815            _index = -1;
 38816            _current = default!;
 38817        }
 818
 819        /// <inheritdoc/>
 75820        public readonly T Current => _current;
 821
 822        readonly object IEnumerator.Current
 823        {
 824            get
 825            {
 1826                SwiftThrowHelper.ThrowIfTrue(_index > (uint)_set._lastIndex, message: "Enumeration has either not starte
 1827                return _current;
 828            }
 829        }
 830
 831        /// <inheritdoc/>
 832        public bool MoveNext()
 833        {
 107834            SwiftThrowHelper.ThrowIfTrue(_version != _set._version, message: "Collection was modified during enumeration
 835
 106836            uint last = (uint)_set._lastIndex;
 170837            while (++_index <= last)
 838            {
 138839                if (_entries[_index].IsUsed)
 840                {
 74841                    _current = _entries[_index].Value;
 74842                    return true;
 843                }
 844            }
 845
 32846            _current = default!;
 32847            return false;
 848        }
 849
 850        /// <inheritdoc/>
 851        public void Reset()
 852        {
 1853            SwiftThrowHelper.ThrowIfTrue(_version != _set._version, message: "Collection was modified during enumeration
 854
 1855            _index = -1;
 1856            _current = default!;
 1857        }
 858
 859        /// <inheritdoc/>
 35860        public void Dispose() => _index = -1;
 861    }
 862
 863    #endregion
 864
 865    #region ISet<T> Implementations
 866
 867    /// <inheritdoc/>
 868    public void ExceptWith(IEnumerable<T> other)
 869    {
 2870        SwiftThrowHelper.ThrowIfNull(other, nameof(other));
 871
 2872        if (ReferenceEquals(this, other))
 873        {
 1874            Clear();
 1875            return;
 876        }
 877
 1878        var otherSet = new SwiftHashSet<T>(other, _comparer);
 879
 8880        foreach (var item in otherSet)
 3881            Remove(item);
 1882    }
 883
 884    /// <inheritdoc/>
 885    public void IntersectWith(IEnumerable<T> other)
 886    {
 2887        SwiftThrowHelper.ThrowIfNull(other, nameof(other));
 888
 2889        if (ReferenceEquals(this, other))
 1890            return;
 891
 1892        var otherSet = new SwiftHashSet<T>(other, _comparer);
 893
 12894        for (int i = 0; i <= _lastIndex; i++)
 895        {
 5896            if (_entries[i].IsUsed)
 897            {
 4898                var value = _entries[i].Value;
 4899                if (!otherSet.Contains(value))
 2900                    Remove(value);
 901            }
 902        }
 1903    }
 904
 905    /// <inheritdoc/>
 906    public bool IsProperSubsetOf(IEnumerable<T> other)
 907    {
 3908        SwiftThrowHelper.ThrowIfNull(other, nameof(other));
 909
 3910        var otherSet = new SwiftHashSet<T>(other, _comparer);
 911
 3912        if (Count >= otherSet.Count)
 1913            return false;
 914
 14915        for (int i = 0; i <= _lastIndex; i++)
 6916            if (_entries[i].IsUsed && !otherSet.Contains(_entries[i].Value))
 1917                return false;
 918
 1919        return true;
 920    }
 921
 922    /// <inheritdoc/>
 923    public bool IsProperSupersetOf(IEnumerable<T> other)
 924    {
 3925        SwiftThrowHelper.ThrowIfNull(other, nameof(other));
 926
 3927        var otherSet = new SwiftHashSet<T>(other, _comparer);
 928
 3929        if (Count <= otherSet.Count)
 1930            return false;
 931
 9932        foreach (var item in otherSet)
 3933            if (!Contains(item))
 1934                return false;
 935
 1936        return true;
 1937    }
 938
 939    /// <inheritdoc/>
 940    public bool IsSubsetOf(IEnumerable<T> other)
 941    {
 3942        SwiftThrowHelper.ThrowIfNull(other, nameof(other));
 943
 3944        var otherSet = new SwiftHashSet<T>(other, _comparer);
 945
 3946        if (otherSet.Count < Count)
 1947            return false;
 948
 14949        for (int i = 0; i <= _lastIndex; i++)
 6950            if (_entries[i].IsUsed && !otherSet.Contains(_entries[i].Value))
 1951                return false;
 952
 1953        return true;
 954    }
 955
 956    /// <inheritdoc/>
 957    public bool IsSupersetOf(IEnumerable<T> other)
 958    {
 2959        SwiftThrowHelper.ThrowIfNull(other, nameof(other));
 960
 13961        foreach (var item in other)
 962        {
 5963            if (!Contains(item))
 1964                return false;
 965        }
 966
 1967        return true;
 1968    }
 969
 970    /// <inheritdoc/>
 971    public bool Overlaps(IEnumerable<T> other)
 972    {
 2973        SwiftThrowHelper.ThrowIfNull(other, nameof(other));
 974
 9975        foreach (var item in other)
 3976            if (Contains(item))
 1977                return true;
 978
 1979        return false;
 1980    }
 981
 982    /// <inheritdoc/>
 983    public bool SetEquals(IEnumerable<T> other)
 984    {
 10985        SwiftThrowHelper.ThrowIfNull(other, nameof(other));
 986
 10987        var otherSet = new SwiftHashSet<T>(other, _comparer);
 988
 10989        if (otherSet.Count != Count)
 1990            return false;
 991
 76992        foreach (var item in otherSet)
 30993            if (!Contains(item))
 2994                return false;
 995
 7996        return true;
 2997    }
 998
 999    /// <inheritdoc/>
 1000    public void SymmetricExceptWith(IEnumerable<T> other)
 1001    {
 21002        SwiftThrowHelper.ThrowIfNull(other, nameof(other));
 1003
 21004        if (ReferenceEquals(this, other))
 1005        {
 11006            Clear();
 11007            return;
 1008        }
 1009
 11010        var otherSet = new SwiftHashSet<T>(other, _comparer);
 1011
 61012        foreach (var item in otherSet)
 1013        {
 21014            if (!Remove(item))
 11015                Add(item);
 1016        }
 11017    }
 1018
 1019    /// <inheritdoc/>
 1020    public void UnionWith(IEnumerable<T> other)
 1021    {
 11022        SwiftThrowHelper.ThrowIfNull(other, nameof(other));
 1023
 61024        foreach (var item in other)
 21025            Add(item);
 11026    }
 1027
 1028    #endregion
 1029}
Generated by: ReportGenerator 5.5.11.0
08/05/2026 - 03:54:48
GitHub | reportgenerator.io

Methods/Properties

.ctor()
.ctor(System.Collections.Generic.IEqualityComparer`1<T>)
.ctor(System.Int32,System.Collections.Generic.IEqualityComparer`1<T>)
.ctor(System.Collections.Generic.IEnumerable`1<T>,System.Collections.Generic.IEqualityComparer`1<T>)
.ctor(SwiftCollections.SwiftArrayState`1<T>)
get_Count()
get_Comparer()
System.Collections.Generic.ICollection<T>.get_IsReadOnly()
get_Item(T)
get_State()
set_State(SwiftCollections.SwiftArrayState`1<T>)
Add(T)
System.Collections.Generic.ICollection<T>.Add(T)
AddRange(System.Collections.Generic.IEnumerable`1<T>)
AddKnownCountRange(System.Collections.Generic.IEnumerable`1<T>,System.Int32)
AddUnknownCountRange(System.Collections.Generic.IEnumerable`1<T>)
InsertIfNotExists(T)
Remove(T)
Clear()
CheckLoadThreshold()
EnsureCapacityForAddRange(System.Int32)
EnsureCapacity(System.Int32)
Resize(System.Int32)
TrimExcess()
CalculateAdaptiveResizeFactors(System.Int32)
Initialize(System.Int32,System.Collections.Generic.IEqualityComparer`1<T>)
Contains(T)
Exists(System.Predicate`1<T>)
Find(System.Predicate`1<T>)
TryGetValue(T,T&)
CopyTo(T[],System.Int32)
SetComparer(System.Collections.Generic.IEqualityComparer`1<T>)
SwitchToRandomizedComparer()
RehashEntries()
FindEntry(T)
GetEnumerator()
System.Collections.Generic.IEnumerable<T>.GetEnumerator()
System.Collections.IEnumerable.GetEnumerator()
.ctor(SwiftCollections.SwiftHashSet`1<T>)
get_Current()
System.Collections.IEnumerator.get_Current()
MoveNext()
Reset()
Dispose()
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>)