< Summary

Information
Class: SwiftCollections.SwiftHashSet<T>
Assembly: SwiftCollections
File(s): /home/runner/work/SwiftCollections/SwiftCollections/src/SwiftCollections/Collection/SwiftHashSet.cs
Line coverage
96%
Covered lines: 361
Uncovered lines: 13
Coverable lines: 374
Total lines: 1020
Line coverage: 96.5%
Branch coverage
93%
Covered branches: 194
Total branches: 208
Branch coverage: 93.2%
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(...)75%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(...)95.83%242493.54%
Remove(...)92.85%1414100%
Clear()100%44100%
CheckLoadThreshold()100%22100%
EnsureCapacityForAddRange(...)75%44100%
EnsureCapacity(...)100%22100%
Resize(...)100%88100%
TrimExcess()91.66%1212100%
CalculateAdaptiveResizeFactors(...)100%66100%
Initialize(...)100%22100%
Contains(...)100%11100%
Exists(...)100%66100%
Find(...)100%66100%
TryGetValue(...)100%22100%
CopyTo(...)100%44100%
SetComparer(...)50%2283.33%
SwitchToRandomizedComparer()50%2285.71%
RehashEntries()100%88100%
FindEntry(...)92.85%141492.3%
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(...)75%4475%
IntersectWith(...)87.5%8890%
IsProperSubsetOf(...)87.5%8887.5%
IsProperSupersetOf(...)83.33%6677.77%
IsSubsetOf(...)87.5%8887.5%
IsSupersetOf(...)100%44100%
Overlaps(...)100%44100%
SetEquals(...)83.33%6688.88%
SymmetricExceptWith(...)100%66100%
UnionWith(...)100%22100%

File(s)

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

#LineLine coverage
 1using Chronicler;
 2using MemoryPack;
 3using System;
 4using System.Collections;
 5using System.Collections.Generic;
 6using System.Runtime.CompilerServices;
 7using System.Text.Json.Serialization;
 8
 9namespace SwiftCollections;
 10
 11/// <summary>
 12/// Represents a high-performance set of unique values with efficient operations for addition, removal, and lookup
 13/// </summary>
 14/// <typeparam name="T">The type of elements in the set.</typeparam>
 15/// <remarks>
 16/// The comparer is not serialized. After deserialization the set reverts
 17/// to the same default comparer selection used by a new instance. String values
 18/// use SwiftCollections' deterministic default comparer. Object values use a
 19/// SwiftCollections comparer that hashes strings deterministically, while other
 20/// object-value determinism still depends on the underlying value type's
 21/// <see cref="object.GetHashCode()"/> implementation. Other types use
 22/// <see cref="EqualityComparer{T}.Default"/>.
 23///
 24/// If a custom comparer is required it can be reapplied using
 25/// <see cref="SetComparer(IEqualityComparer{T})"/>.
 26/// </remarks>
 27[Serializable]
 28[JsonConverter(typeof(StateJsonConverterFactory))]
 29[MemoryPackable]
 30public sealed partial class SwiftHashSet<T> : IStateBacked<SwiftArrayState<T>>, ISet<T>, ICollection<T>, IEnumerable<T>,
 31    where T : notnull
 32{
 33    #region Constants
 34
 35    /// <summary>
 36    /// The default initial capacity of the set.
 37    /// </summary>
 38    public const int DefaultCapacity = 8;
 39
 40    /// <summary>
 41    /// Determines the maximum allowable load factor before resizing the hash set to maintain performance.
 42    /// </summary>
 43    private const float _LoadFactorThreshold = 0.85f;
 44
 45    #endregion
 46
 47    #region Fields
 48
 49    /// <summary>
 50    /// The array containing the entries of the SwiftHashSet.
 51    /// </summary>
 52    /// <remarks>
 53    /// Capacity will always be a power of two for efficient pooling cache.
 54    /// </remarks>
 55    private Entry[] _entries;
 56
 57    /// <summary>
 58    /// The total number of entries in the hash set
 59    /// </summary>
 60    private int _count;
 61
 62    private int _lastIndex;
 63
 64    /// <summary>
 65    /// A mask used for efficiently computing the entry index from a hash code.
 66    /// This is typically the size of the entry array minus one, assuming the size is a power of two.
 67    /// </summary>
 68    private int _entryMask;
 69
 70    /// <summary>
 71    /// The comparer used to determine equality of keys and to generate hash codes.
 72    /// </summary>
 73    private IEqualityComparer<T> _comparer;
 74
 75    /// <summary>
 76    /// Specifies the dynamic growth factor for resizing, adjusted based on recent usage patterns.
 77    /// </summary>
 78    private int _adaptiveResizeFactor;
 79
 80    /// <summary>
 81    /// Tracks the count threshold at which the hash set should resize based on the load factor.
 82    /// </summary>
 83    private uint _nextResizeCount;
 84
 85    /// <summary>
 86    /// Represents the moving average of the fill rate, used to dynamically adjust resizing behavior.
 87    /// </summary>
 88    private double _movingFillRate;
 89
 90    private int _maxStepCount;
 91
 92    /// <summary>
 93    /// A version counter used to track modifications to the set.
 94    /// Incremented on mutations to detect changes during enumeration and ensure enumerator validity.
 95    /// </summary>
 96    private uint _version;
 97
 98    #endregion
 99
 100    #region Nested Types
 101
 102    /// <summary>
 103    /// Represents a single value in the set, including its hash code for quick access.
 104    /// </summary>
 105    private struct Entry
 106    {
 107        public T Value;
 108        public int HashCode;    // Lower 31 bits of hash code, -1 if deleted probe tombstone
 109        public bool IsUsed;
 110    }
 111
 112    #endregion
 113
 114    #region Constructors
 115
 116    /// <summary>
 117    /// Initialize a new instance of <see cref="SwiftHashSet{T}"/> with customizable capacity and comparer for optimal p
 118    /// </summary>
 126119    public SwiftHashSet() : this(DefaultCapacity, null) { }
 120
 121    /// <inheritdoc cref="SwiftHashSet()"/>
 12122    public SwiftHashSet(IEqualityComparer<T>? comparer) : this(DefaultCapacity, comparer) { }
 123
 124    /// <summary>
 125    /// Initializes a new instance of the <see cref="SwiftHashSet{T}"/> class that is empty and has the default initial 
 126    /// </summary>
 77127    public SwiftHashSet(int capacity, IEqualityComparer<T>? comparer = null)
 128    {
 77129        Initialize(capacity, comparer);
 130
 77131        SwiftThrowHelper.ThrowIfNull(_entries, nameof(_entries));
 77132        SwiftThrowHelper.ThrowIfNull(_comparer, nameof(_comparer));
 77133    }
 134
 135    /// <summary>
 136    /// Initializes a new instance of the <see cref="SwiftHashSet{T}"/> class that contains elements copied from the spe
 137    /// </summary>
 138    /// <param name="collection">The collection whose elements are copied to the new set.</param>
 139    /// <param name="comparer">The comparer to use when comparing elements.</param>
 33140    public SwiftHashSet(IEnumerable<T> collection, IEqualityComparer<T>? comparer = null)
 141    {
 33142        SwiftThrowHelper.ThrowIfNull(collection, nameof(collection));
 143
 33144        int count = (collection as ICollection<T>)?.Count ?? DefaultCapacity;
 33145        int size = (int)(count / _LoadFactorThreshold);  // Dynamic padding based on collision estimation
 33146        Initialize(size, comparer);
 147
 33148        SwiftThrowHelper.ThrowIfNull(_entries, nameof(_entries));
 33149        SwiftThrowHelper.ThrowIfNull(_comparer, nameof(_comparer));
 150
 286151        foreach (T item in collection)
 110152            InsertIfNotExists(item);
 33153    }
 154
 155    ///  <summary>
 156    ///  Initializes a new instance of the <see cref="SwiftHashSet{T}"/> class with the specified <see cref="SwiftArrayS
 157    ///  </summary>
 158    ///  <param name="state">The state containing the internal array, count, offset, and version for initialization.</pa
 159    [MemoryPackConstructor]
 6160    public SwiftHashSet(SwiftArrayState<T> state)
 161    {
 6162        State = state;
 163
 6164        SwiftThrowHelper.ThrowIfNull(_entries, nameof(_entries));
 6165        SwiftThrowHelper.ThrowIfNull(_comparer, nameof(_comparer));
 6166    }
 167
 168    #endregion
 169
 170    #region Properties
 171
 172    /// <summary>
 173    /// Gets the number of elements contained in the set.
 174    /// </summary>
 175    [JsonIgnore]
 176    [MemoryPackIgnore]
 65177    public int Count => _count;
 178
 179    /// <summary>
 180    /// Gets the <see cref="IEqualityComparer{T}"/> object that is used to determine equality for the values in the set.
 181    /// </summary>
 182    [JsonIgnore]
 183    [MemoryPackIgnore]
 13184    public IEqualityComparer<T> Comparer => _comparer;
 185
 186    [JsonIgnore]
 187    [MemoryPackIgnore]
 1188    bool ICollection<T>.IsReadOnly => false;
 189
 190    /// <summary>
 191    /// Gets the stored value that matches the specified key.
 192    /// </summary>
 193    /// <param name="key">The lookup value used to find an equal element in the set.</param>
 194    /// <exception cref="KeyNotFoundException">No matching value exists in the set.</exception>
 195    [JsonIgnore]
 196    [MemoryPackIgnore]
 197    public T this[T key]
 198    {
 199        get
 200        {
 2201            int index = FindEntry(key);
 2202            SwiftThrowHelper.ThrowIfKeyInvalid(index, key);
 1203            return _entries[index].Value;
 204        }
 205    }
 206
 207    /// <summary>
 208    /// Gets or sets the current state of the array, including its items and structure.
 209    /// </summary>
 210    /// <remarks>
 211    /// Setting this property replaces the contents of the array with the items from the specified state.
 212    /// If the provided state is empty, the array is cleared.
 213    /// The setter is intended for internal use and may reset internal versioning.
 214    /// </remarks>
 215    [JsonInclude]
 216    [MemoryPackInclude]
 217    public SwiftArrayState<T> State
 218    {
 219        get
 220        {
 6221            if (_count == 0)
 1222                return new SwiftArrayState<T>(Array.Empty<T>());
 223
 5224            T[] items = new T[_count];
 5225            CopyTo(items, 0);
 226
 5227            return new SwiftArrayState<T>(items);
 228        }
 229        internal set
 230        {
 6231            SwiftThrowHelper.ThrowIfNull(value.Items, nameof(value));
 232
 6233            T[] items = value.Items;
 6234            int count = items.Length;
 235
 6236            if (count == 0)
 237            {
 1238                Initialize(DefaultCapacity);
 1239                _count = 0;
 1240                _version = 0;
 1241                return;
 242            }
 243
 5244            int size = (int)(count / _LoadFactorThreshold);
 5245            Initialize(size);
 246
 54247            foreach (T item in items)
 22248                if (item != null)
 22249                    InsertIfNotExists(item);
 250
 5251            _version = 0;
 5252        }
 253    }
 254
 255    #endregion
 256
 257    #region Collection Manipulation
 258
 259    /// <inheritdoc/>
 260    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 261    public bool Add(T item)
 262    {
 214603263        CheckLoadThreshold();
 214603264        return InsertIfNotExists(item);
 265    }
 266
 1267    void ICollection<T>.Add(T item) => Add(item);
 268
 269    /// <summary>
 270    /// Adds the elements of the specified collection to the set, ignoring null values and duplicates.
 271    /// </summary>
 272    /// <remarks>
 273    /// If the source collection is the same instance as the set, the method returns without making any changes.
 274    /// The method preserves single-pass enumeration for sources that do not support multiple iterations.</remarks>
 275    /// <param name="items">The collection of elements to add to the set. Elements that are null or already present in t
 276    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 277    public void AddRange(IEnumerable<T> items)
 278    {
 5279        SwiftThrowHelper.ThrowIfNull(items, nameof(items));
 280
 5281        if (ReferenceEquals(this, items))
 1282            return;
 283
 4284        if (items is ICollection<T> collection)
 285        {
 2286            AddKnownCountRange(collection, collection.Count);
 2287            return;
 288        }
 289
 2290        if (items is IReadOnlyCollection<T> readOnlyCollection)
 291        {
 1292            AddKnownCountRange(readOnlyCollection, readOnlyCollection.Count);
 1293            return;
 294        }
 295
 1296        AddUnknownCountRange(items);
 1297    }
 298
 299    private void AddKnownCountRange(IEnumerable<T> items, int count)
 300    {
 3301        EnsureCapacityForAddRange(count);
 302
 20303        foreach (T item in items)
 7304            if (item != null)
 7305                InsertIfNotExists(item);
 3306    }
 307
 308    private void AddUnknownCountRange(IEnumerable<T> items)
 309    {
 8310        foreach (T item in items)
 3311            if (item != null)
 3312                Add(item);
 1313    }
 314
 315    /// <summary>
 316    /// Adds the specified element to the set if it's not already present.
 317    /// </summary>
 318    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 319    private bool InsertIfNotExists(T item)
 320    {
 214742321        SwiftThrowHelper.ThrowIfNullGeneric(item, nameof(item));
 322
 214741323        int hashCode = _comparer.GetHashCode(item) & 0x7FFFFFFF;
 214741324        int entryIndex = hashCode & _entryMask;
 325
 214741326        int firstDeletedIndex = -1;
 214741327        int step = 1;
 214741328        int probeLimit = _entries.Length;
 365537329        while ((uint)step <= (uint)probeLimit)
 330        {
 365537331            ref Entry entry = ref _entries[entryIndex];
 365537332            if (entry.IsUsed)
 333            {
 150787334                if (entry.HashCode == hashCode && _comparer.Equals(entry.Value, item))
 13335                    return false; // Item already exists
 336            }
 214750337            else if (entry.HashCode == -1)
 338            {
 30339                if (firstDeletedIndex < 0) firstDeletedIndex = entryIndex;
 340            }
 341            else
 342            {
 343                break;
 344            }
 345
 150796346            entryIndex = (entryIndex + step * step) & _entryMask; // Quadratic probing
 150796347            step++;
 348        }
 349
 214728350        if (firstDeletedIndex >= 0)
 7351            entryIndex = firstDeletedIndex;
 214721352        else if ((uint)step > (uint)probeLimit)
 353        {
 0354            Resize(_entries.Length * _adaptiveResizeFactor);
 0355            return InsertIfNotExists(item);
 356        }
 357
 329305358        if ((uint)entryIndex > (uint)_lastIndex) _lastIndex = entryIndex;
 359
 214728360        _entries[entryIndex].HashCode = hashCode;
 214728361        _entries[entryIndex].Value = item;
 214728362        _entries[entryIndex].IsUsed = true;
 214728363        _count++;
 214728364        _version++;
 365
 214728366        if ((uint)step > (uint)_maxStepCount)
 367        {
 1248368            _maxStepCount = step;
 1248369            if (_comparer is not IRandomedEqualityComparer && _maxStepCount > 100)
 1370                SwitchToRandomizedComparer();  // Attempt to recompute hash code with potential randomization for better
 371        }
 372
 214728373        return true;
 374    }
 375
 376    /// <summary>
 377    /// Removes the specified element from the set.
 378    /// </summary>
 379    /// <param name="item">The element to remove from the set.</param>
 380    /// <returns>
 381    /// True if the element is successfully found and removed; otherwise, false.
 382    /// </returns>
 383    public bool Remove(T item)
 384    {
 100567385        SwiftThrowHelper.ThrowIfNullGeneric(item, nameof(item));
 386
 100566387        int hashCode = _comparer.GetHashCode(item) & 0x7FFFFFFF;
 100566388        int entryIndex = hashCode & _entryMask;
 389
 100566390        int step = 0;
 149944391        while ((uint)step <= (uint)_lastIndex)
 392        {
 149943393            ref Entry entry = ref _entries[entryIndex];
 394            // Stop probing if an unused entry is found (not deleted)
 149943395            if (!entry.IsUsed && entry.HashCode != -1)
 4396                return false;
 149939397            if (entry.IsUsed && entry.HashCode == hashCode && _comparer.Equals(entry.Value, item))
 398            {
 399                // Mark entry as deleted
 100561400                entry.IsUsed = false;
 100561401                entry.Value = default!;
 100561402                entry.HashCode = -1;
 100561403                _count--;
 100561404                if ((uint)_count == 0) _lastIndex = 0;
 100561405                _version++;
 100561406                return true;
 407            }
 408
 409            // Entry not found in expected entry, it either doesn't exist or was moved via quadratic probing
 49378410            step++;
 49378411            entryIndex = (entryIndex + step * step) & _entryMask;
 412        }
 1413        return false; // Item not found after full loop
 414    }
 415
 416    /// <summary>
 417    /// Removes all elements from the set.
 418    /// </summary>
 419    public void Clear()
 420    {
 1049421        if ((uint)_count == 0) return;
 422
 18984423        for (uint i = 0; i <= (uint)_lastIndex; i++)
 424        {
 425            // Clear is a full reset, not a delete; future probes must be able to stop
 426            // at these now-empty slots instead of treating them as tombstones.
 8445427            _entries[i].HashCode = 0;
 8445428            _entries[i].Value = default!;
 8445429            _entries[i].IsUsed = false;
 430        }
 431
 1047432        _count = 0;
 1047433        _lastIndex = 0;
 1047434        _maxStepCount = 0;
 1047435        _movingFillRate = 0;
 1047436        _adaptiveResizeFactor = 4;
 437
 1047438        _version++;
 1047439    }
 440
 441    #endregion
 442
 443    #region Capacity Management
 444
 445    /// <summary>
 446    /// Ensures that the hash set is resized when the current load factor exceeds the predefined threshold.
 447    /// </summary>
 448    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 449    private void CheckLoadThreshold()
 450    {
 214603451        if ((uint)_count >= _nextResizeCount)
 35452            Resize(_entries.Length * _adaptiveResizeFactor);
 214603453    }
 454
 455    /// <summary>
 456    /// Ensures there is enough room to add a batch of items without repeatedly checking the load threshold.
 457    /// </summary>
 458    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 459    private void EnsureCapacityForAddRange(int incomingCount)
 460    {
 3461        if (incomingCount <= 0)
 1462            return;
 463
 2464        long requiredCount = (long)_count + incomingCount;
 2465        SwiftThrowHelper.ThrowIfTrue(requiredCount > int.MaxValue, message: "The collection is too large.");
 466
 2467        double minimumCapacity = Math.Ceiling(requiredCount / (double)_LoadFactorThreshold);
 2468        EnsureCapacity(minimumCapacity >= int.MaxValue ? int.MaxValue : (int)minimumCapacity);
 2469    }
 470
 471    /// <summary>
 472    /// Ensures that the set can hold up to the specified number of elements without resizing.
 473    /// </summary>
 474    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 475    public void EnsureCapacity(int capacity)
 476    {
 4477        capacity = SwiftHashTools.NextPowerOfTwo(capacity);  // Capacity must be a power of 2 for proper masking
 4478        if (capacity > _entries.Length)
 2479            Resize(capacity);
 4480    }
 481
 482    /// <summary>
 483    /// Resizes the hash set to the specified capacity, redistributing all entries to maintain efficiency.
 484    /// </summary>
 485    /// <param name="newSize"></param>
 486    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 487    private void Resize(int newSize)
 488    {
 37489        Entry[] newEntries = new Entry[newSize];
 37490        int newMask = newSize - 1;
 491
 37492        int lastIndex = 0;
 184526493        for (uint i = 0; i <= (uint)_lastIndex; i++)
 494        {
 92226495            if (_entries[i].IsUsed)
 496            {
 85668497                ref Entry oldEntry = ref _entries[i];
 85668498                int newIndex = oldEntry.HashCode & newMask;
 499                // If current entry not available, perform Quadratic probing to find the next available entry
 85668500                int step = 1;
 90522501                while (newEntries[newIndex].IsUsed)
 502                {
 4854503                    newIndex = (newIndex + step * step) & newMask;
 4854504                    step++;
 505                }
 85668506                newEntries[newIndex] = oldEntry;
 134272507                if (newIndex > lastIndex) lastIndex = newIndex;
 508            }
 509        }
 510
 37511        _lastIndex = lastIndex;
 512
 37513        CalculateAdaptiveResizeFactors(newSize);
 514
 37515        _entries = newEntries;
 37516        _entryMask = newMask;
 517
 37518        _version++;
 37519    }
 520
 521    /// <summary>
 522    /// Sets the capacity of a <see cref="SwiftHashSet{T}"/> to the actual
 523    /// number of elements it contains, rounded up to a nearby next power of 2 value.
 524    /// </summary>
 525    public void TrimExcess()
 526    {
 2527        int newSize = _count <= DefaultCapacity ? DefaultCapacity : SwiftHashTools.NextPowerOfTwo(_count);
 2528        if (newSize >= _entries.Length) return;
 529
 2530        Entry[] newEntries = new Entry[newSize];
 2531        int newMask = newSize - 1;
 532
 2533        int lastIndex = 0;
 40534        for (int i = 0; i <= (uint)_lastIndex; i++)
 535        {
 18536            if (_entries[i].IsUsed)
 537            {
 15538                ref Entry oldEntry = ref _entries[i];
 15539                int newIndex = oldEntry.HashCode & newMask;
 540                // If current entry not available, perform quadratic probing to find the next available entry
 15541                int step = 1;
 18542                while (newEntries[newIndex].IsUsed)
 543                {
 3544                    newIndex = (newIndex + step * step) & newMask;
 3545                    step++;
 546                }
 15547                newEntries[newIndex] = oldEntry;
 28548                if (newIndex > lastIndex) lastIndex = newIndex;
 549            }
 550        }
 551
 2552        _lastIndex = lastIndex;
 553
 2554        CalculateAdaptiveResizeFactors(newSize);
 555
 2556        _entryMask = newMask;
 2557        _entries = newEntries;
 558
 2559        _version++;
 2560    }
 561
 562    /// <summary>
 563    ///  Updates adaptive resize parameters based on the current fill rate to balance memory usage and performance.
 564    /// </summary>
 565    /// <param name="newSize"></param>
 566    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 567    private void CalculateAdaptiveResizeFactors(int newSize)
 568    {
 569        // Calculate current fill rate and update moving average
 39570        double currentFillRate = (double)_count / newSize;
 39571        _movingFillRate = _movingFillRate == 0 ? currentFillRate : (_movingFillRate * 0.7 + currentFillRate * 0.3);
 572
 39573        if (_movingFillRate > 0.3f)
 3574            _adaptiveResizeFactor = 2; // Growth stabilizing
 36575        else if (_movingFillRate < 0.28f)
 36576            _adaptiveResizeFactor = 4; // Rapid growth
 577
 578        // Reset the resize threshold based on the new size
 39579        _nextResizeCount = (uint)(newSize * _LoadFactorThreshold);
 39580    }
 581
 582    #endregion
 583
 584    #region Utility Methods
 585
 586    /// <summary>
 587    /// Initializes the hash set with a given capacity, ensuring it starts with an optimal internal structure.
 588    /// </summary>
 589    /// <param name="capacity"></param>
 590    /// <param name="comparer"></param>
 591    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 592    private void Initialize(int capacity, IEqualityComparer<T>? comparer = null)
 593    {
 116594        _comparer = SwiftHashTools.GetDefaultEqualityComparer(comparer);
 595
 116596        int size = capacity < DefaultCapacity ? DefaultCapacity : SwiftHashTools.NextPowerOfTwo(capacity);
 116597        _entries = new Entry[size];
 116598        _entryMask = size - 1;
 599
 116600        _nextResizeCount = (uint)(size * _LoadFactorThreshold);
 116601        _adaptiveResizeFactor = 4; // start agressive
 116602        _movingFillRate = 0.0;
 116603    }
 604
 605    /// <summary>
 606    /// Determines whether the set contains the specified element.
 607    /// </summary>
 608    /// <param name="item">The element to locate in the set.</param>
 609    /// <returns>
 610    /// True if the set contains the specified element; otherwise, false.
 611    /// </returns>
 612    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 1244613    public bool Contains(T item) => FindEntry(item) >= 0;
 614
 615    /// <summary>
 616    /// Determines whether the <see cref="SwiftHashSet{T}"/> contains an element that matches the conditions defined by 
 617    /// </summary>
 618    /// <param name="match">The predicate that defines the conditions of the element to search for.</param>
 619    /// <returns><c>true</c> if the <see cref="SwiftHashSet{T}"/> contains one or more elements that match the specified
 620    public bool Exists(Predicate<T> match)
 621    {
 3622        SwiftThrowHelper.ThrowIfNull(match, nameof(match));
 623
 16624        for (int i = 0; i <= _lastIndex; i++)
 625        {
 7626            if (_entries[i].IsUsed && match(_entries[i].Value))
 1627                return true;
 628        }
 629
 1630        return false;
 631    }
 632
 633    /// <summary>
 634    /// Searches for an element that matches the conditions defined by the specified predicate, and returns the first ma
 635    /// </summary>
 636    /// <param name="match">The predicate that defines the conditions of the element to search for.</param>
 637    /// <returns>The first element that matches the conditions defined by the specified predicate, if found; otherwise, 
 638    public T Find(Predicate<T> match)
 639    {
 2640        SwiftThrowHelper.ThrowIfNull(match, nameof(match));
 641
 16642        for (int i = 0; i <= _lastIndex; i++)
 643        {
 7644            if (_entries[i].IsUsed && match(_entries[i].Value))
 1645                return _entries[i].Value;
 646        }
 647
 1648        return default!;
 649    }
 650
 651    /// <summary>
 652    /// Searches the set for a given value and returns the equal value it finds, if any.
 653    /// </summary>
 654    public bool TryGetValue(T expected, out T actual)
 655    {
 2656        int index = FindEntry(expected);
 2657        if (index >= 0)
 658        {
 1659            actual = _entries[index].Value;
 1660            return true;
 661        }
 1662        actual = default!;
 1663        return false;
 664    }
 665
 666    /// <summary>
 667    /// Copies the elements of the set to an array, starting at the specified array index.
 668    /// </summary>
 669    public void CopyTo(T[] array, int arrayIndex)
 670    {
 11671        SwiftThrowHelper.ThrowIfNull(array, nameof(array));
 10672        SwiftThrowHelper.ThrowIfArrayIndexInvalid(arrayIndex, array.Length, message: "Array index is out of range.");
 8673        SwiftThrowHelper.ThrowIfArgument(array.Length - arrayIndex < _count, nameof(array), "The array is not large enou
 674
 114675        for (uint i = 0; i <= (uint)_lastIndex; i++)
 676        {
 50677            if (_entries[i].IsUsed)
 28678                array[arrayIndex++] = _entries[i].Value;
 679        }
 7680    }
 681
 682    /// <summary>
 683    /// Switches the hash set's comparer and rehashes all entries
 684    /// using the new comparer to redistribute them across <see cref="_entries"/>.
 685    /// </summary>
 686    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 687    public void SetComparer(IEqualityComparer<T>? comparer = null)
 688    {
 3689        SwiftThrowHelper.ThrowIfNull(comparer, nameof(comparer));
 3690        if (ReferenceEquals(comparer, _comparer))
 0691            return;
 692
 3693        _comparer = comparer;
 3694        RehashEntries();
 3695    }
 696
 697    /// <summary>
 698    /// Replaces the hash set's comparer with a randomized comparer to mitigate high collision rates.
 699    /// </summary>
 700    private void SwitchToRandomizedComparer()
 701    {
 1702        if (SwiftHashTools.IsWellKnownEqualityComparer(_comparer))
 1703            _comparer = (IEqualityComparer<T>)SwiftHashTools.GetSwiftEqualityComparer(_comparer);
 0704        else return; // nothing to do here
 705
 1706        RehashEntries();
 1707        _maxStepCount = 0;
 708
 1709        _version++;
 1710    }
 711
 712    /// <summary>
 713    /// Reconstructs the internal entry structure to align with updated hash codes, ensuring efficient access and storag
 714    /// </summary>
 715    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 716    private void RehashEntries()
 717    {
 4718        Entry[] newEntries = new Entry[_entries.Length];
 4719        int newMask = newEntries.Length - 1;
 720
 4721        int lastIndex = 0;
 584722        for (uint i = 0; i <= (uint)_lastIndex; i++)
 723        {
 288724            if (_entries[i].IsUsed)
 725            {
 101726                ref Entry oldEntry = ref _entries[i];
 101727                oldEntry.HashCode = _comparer.GetHashCode(oldEntry.Value) & 0x7FFFFFFF;
 101728                int newIndex = oldEntry.HashCode & newMask;
 101729                int step = 1;
 116730                while (newEntries[newIndex].IsUsed)
 731                {
 15732                    newIndex = (newIndex + step * step) & newMask; // Quadratic probing
 15733                    step++;
 734                }
 101735                newEntries[newIndex] = _entries[i];
 117736                if (newIndex > lastIndex) lastIndex = newIndex;
 737            }
 738        }
 739
 4740        _lastIndex = lastIndex;
 741
 4742        _entryMask = newMask;
 4743        _entries = newEntries;
 744
 4745        _version++;
 4746    }
 747
 748    /// <summary>
 749    /// Searches for an entry in the hash set by following its probing sequence, returning its index if found.
 750    /// </summary>
 751    /// <param name="item"></param>
 752    /// <returns></returns>
 753    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 754    private int FindEntry(T item)
 755    {
 1249756        if (item == null) return -1;
 757
 1247758        int hashCode = _comparer.GetHashCode(item) & 0x7FFFFFFF;
 1247759        int entryIndex = hashCode & _entryMask;
 760
 1247761        int step = 0;
 6720762        while ((uint)step <= (uint)_lastIndex)
 763        {
 6720764            ref Entry entry = ref _entries[entryIndex];
 765            // Stop probing if an unused entry is found (not deleted)
 6720766            if (!entry.IsUsed && entry.HashCode != -1)
 525767                return -1;
 6195768            if (entry.IsUsed && entry.HashCode == hashCode && _comparer.Equals(entry.Value, item))
 722769                return entryIndex; // Match found
 770
 771            // Perform quadratic probing to see if maybe the entry was shifted.
 5473772            step++;
 5473773            entryIndex = (entryIndex + step * step) & _entryMask;
 774
 775        }
 0776        return -1; // Item not found, full loop completed
 777    }
 778
 779    #endregion
 780
 781    #region Enumerators
 782
 783    /// <summary>
 784    /// Returns an enumerator that iterates through the set.
 785    /// </summary>
 31786    public SwiftHashSetEnumerator GetEnumerator() => new(this);
 13787    IEnumerator<T> IEnumerable<T>.GetEnumerator() => GetEnumerator();
 1788    IEnumerator IEnumerable.GetEnumerator() => GetEnumerator();
 789
 790    /// <summary>
 791    /// Provides an enumerator for iterating through the elements of the hash set, ensuring consistency during enumerati
 792    /// </summary>
 793    public struct SwiftHashSetEnumerator : IEnumerator<T>, IEnumerator, IDisposable
 794    {
 795        private readonly SwiftHashSet<T> _set;
 796        private readonly Entry[] _entries;
 797        private readonly uint _version;
 798        private int _index;
 799        private T _current;
 800
 801        internal SwiftHashSetEnumerator(SwiftHashSet<T> set)
 802        {
 31803            _set = set;
 31804            _version = set._version;
 31805            _entries = set._entries; // Cache the entry array
 31806            _index = -1;
 31807            _current = default!;
 31808        }
 809
 810        /// <inheritdoc/>
 62811        public readonly T Current => _current;
 812
 813        readonly object IEnumerator.Current
 814        {
 815            get
 816            {
 1817                SwiftThrowHelper.ThrowIfTrue(_index > (uint)_set._lastIndex, message: "Enumeration has either not starte
 1818                return _current;
 819            }
 820        }
 821
 822        /// <inheritdoc/>
 823        public bool MoveNext()
 824        {
 90825            SwiftThrowHelper.ThrowIfTrue(_version != _set._version, message: "Collection was modified during enumeration
 826
 89827            uint last = (uint)_set._lastIndex;
 137828            while (++_index <= last)
 829            {
 110830                if (_entries[_index].IsUsed)
 831                {
 62832                    _current = _entries[_index].Value;
 62833                    return true;
 834                }
 835            }
 836
 27837            _current = default!;
 27838            return false;
 839        }
 840
 841        /// <inheritdoc/>
 842        public void Reset()
 843        {
 1844            SwiftThrowHelper.ThrowIfTrue(_version != _set._version, message: "Collection was modified during enumeration
 845
 1846            _index = -1;
 1847            _current = default!;
 1848        }
 849
 850        /// <inheritdoc/>
 28851        public void Dispose() => _index = -1;
 852    }
 853
 854    #endregion
 855
 856    #region ISet<T> Implementations
 857
 858    /// <inheritdoc/>
 859    public void ExceptWith(IEnumerable<T> other)
 860    {
 1861        SwiftThrowHelper.ThrowIfNull(other, nameof(other));
 862
 1863        if (ReferenceEquals(this, other))
 864        {
 0865            Clear();
 0866            return;
 867        }
 868
 1869        var otherSet = new SwiftHashSet<T>(other, _comparer);
 870
 8871        foreach (var item in otherSet)
 3872            Remove(item);
 1873    }
 874
 875    /// <inheritdoc/>
 876    public void IntersectWith(IEnumerable<T> other)
 877    {
 1878        SwiftThrowHelper.ThrowIfNull(other, nameof(other));
 879
 1880        if (ReferenceEquals(this, other))
 0881            return;
 882
 1883        var otherSet = new SwiftHashSet<T>(other, _comparer);
 884
 12885        for (int i = 0; i <= _lastIndex; i++)
 886        {
 5887            if (_entries[i].IsUsed)
 888            {
 4889                var value = _entries[i].Value;
 4890                if (!otherSet.Contains(value))
 2891                    Remove(value);
 892            }
 893        }
 1894    }
 895
 896    /// <inheritdoc/>
 897    public bool IsProperSubsetOf(IEnumerable<T> other)
 898    {
 2899        SwiftThrowHelper.ThrowIfNull(other, nameof(other));
 900
 2901        var otherSet = new SwiftHashSet<T>(other, _comparer);
 902
 2903        if (Count >= otherSet.Count)
 1904            return false;
 905
 8906        for (int i = 0; i <= _lastIndex; i++)
 3907            if (_entries[i].IsUsed && !otherSet.Contains(_entries[i].Value))
 0908                return false;
 909
 1910        return true;
 911    }
 912
 913    /// <inheritdoc/>
 914    public bool IsProperSupersetOf(IEnumerable<T> other)
 915    {
 2916        SwiftThrowHelper.ThrowIfNull(other, nameof(other));
 917
 2918        var otherSet = new SwiftHashSet<T>(other, _comparer);
 919
 2920        if (Count <= otherSet.Count)
 1921            return false;
 922
 4923        foreach (var item in otherSet)
 1924            if (!Contains(item))
 0925                return false;
 926
 1927        return true;
 0928    }
 929
 930    /// <inheritdoc/>
 931    public bool IsSubsetOf(IEnumerable<T> other)
 932    {
 2933        SwiftThrowHelper.ThrowIfNull(other, nameof(other));
 934
 2935        var otherSet = new SwiftHashSet<T>(other, _comparer);
 936
 2937        if (otherSet.Count < Count)
 1938            return false;
 939
 8940        for (int i = 0; i <= _lastIndex; i++)
 3941            if (_entries[i].IsUsed && !otherSet.Contains(_entries[i].Value))
 0942                return false;
 943
 1944        return true;
 945    }
 946
 947    /// <inheritdoc/>
 948    public bool IsSupersetOf(IEnumerable<T> other)
 949    {
 2950        SwiftThrowHelper.ThrowIfNull(other, nameof(other));
 951
 13952        foreach (var item in other)
 953        {
 5954            if (!Contains(item))
 1955                return false;
 956        }
 957
 1958        return true;
 1959    }
 960
 961    /// <inheritdoc/>
 962    public bool Overlaps(IEnumerable<T> other)
 963    {
 2964        SwiftThrowHelper.ThrowIfNull(other, nameof(other));
 965
 9966        foreach (var item in other)
 3967            if (Contains(item))
 1968                return true;
 969
 1970        return false;
 1971    }
 972
 973    /// <inheritdoc/>
 974    public bool SetEquals(IEnumerable<T> other)
 975    {
 6976        SwiftThrowHelper.ThrowIfNull(other, nameof(other));
 977
 6978        var otherSet = new SwiftHashSet<T>(other, _comparer);
 979
 6980        if (otherSet.Count != Count)
 0981            return false;
 982
 53983        foreach (var item in otherSet)
 21984            if (!Contains(item))
 1985                return false;
 986
 5987        return true;
 1988    }
 989
 990    /// <inheritdoc/>
 991    public void SymmetricExceptWith(IEnumerable<T> other)
 992    {
 2993        SwiftThrowHelper.ThrowIfNull(other, nameof(other));
 994
 2995        if (ReferenceEquals(this, other))
 996        {
 1997            Clear();
 1998            return;
 999        }
 1000
 11001        var otherSet = new SwiftHashSet<T>(other, _comparer);
 1002
 61003        foreach (var item in otherSet)
 1004        {
 21005            if (!Remove(item))
 11006                Add(item);
 1007        }
 11008    }
 1009
 1010    /// <inheritdoc/>
 1011    public void UnionWith(IEnumerable<T> other)
 1012    {
 11013        SwiftThrowHelper.ThrowIfNull(other, nameof(other));
 1014
 61015        foreach (var item in other)
 21016            Add(item);
 11017    }
 1018
 1019    #endregion
 1020}
Generated by: ReportGenerator 5.5.10.0
05/19/2026 - 03:35:54
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>)