< Summary

Class:Towel.DataStructures.SetHashLinked<T1, T2, T3>
Assembly:Towel
File(s):File 1: /home/runner/work/Towel/Towel/Sources/Towel/DataStructures/Set.cs
Covered lines:131
Uncovered lines:38
Coverable lines:169
Total lines:317
Line coverage:77.5% (131 of 169)
Covered branches:46
Total branches:56
Branch coverage:82.1% (46 of 56)

Metrics

MethodBranch coverage Cyclomatic complexity Line coverage
File 1: .ctor(...)100%1100%
File 1: .ctor(...)100%6100%
File 1: .ctor(...)100%10%
File 1: get_TableSize()100%10%
File 1: get_Count()100%1100%
File 1: get_Hash()100%10%
File 1: get_Equate()100%10%
File 1: GetLocation(...)100%1100%
File 1: TryAdd(...)100%10100%
File 1: TryRemove(...)87.5%887.5%
File 1: TryRemoveWithoutTrim(...)83.33%694.44%
File 1: Resize(...)83.33%688.23%
File 1: Trim()0%20%
File 1: Clone()100%10%
File 1: Contains(...)100%4100%
File 1: Clear()100%1100%
File 1: StepperBreak(...)83.33%683.33%
File 1: System.Collections.IEnumerable.GetEnumerator()100%10%
File 1: GetEnumerator()100%4100%
File 1: ToArray()0%40%

File(s)

/home/runner/work/Towel/Towel/Sources/Towel/DataStructures/Set.cs

#LineLine coverage
 1namespace Towel.DataStructures;
 2
 3/// <summary>An unsorted structure of unique items.</summary>
 4/// <typeparam name="T">The type of values to store in the set.</typeparam>
 5public interface ISet<T> : IDataStructure<T>,
 6  DataStructure.IAuditable<T>,
 7  DataStructure.IAddable<T>,
 8  DataStructure.IRemovable<T>,
 9  DataStructure.ICountable,
 10  DataStructure.IClearable
 11{
 12
 13}
 14
 15/// <summary>Static helpers for <see cref="SetHashLinked{T, Equate, THash}"/>.</summary>
 16public class SetHashLinked
 17{
 18  #region Extension Methods
 19
 20  /// <summary>Constructs a new <see cref="SetHashLinked{T, TEquate, THash}"/>.</summary>
 21  /// <typeparam name="T">The type of values stored in this data structure.</typeparam>
 22  /// <param name="equate">The function for comparing <typeparamref name="T"/> values for equality.</param>
 23  /// <param name="hash">The function for hashing <typeparamref name="T"/> values.</param>
 24  /// <returns>The new constructed <see cref="SetHashLinked{T, TEquate, THash}"/>.</returns>
 25  public static SetHashLinked<T, SFunc<T, T, bool>, SFunc<T, int>> New<T>(
 26    Func<T, T, bool>? equate = null,
 27    Func<T, int>? hash = null) =>
 28    new(equate ?? Equate, hash ?? Hash);
 29
 30  #endregion
 31}
 32
 33/// <summary>An unsorted structure of unique items implemented as a hashed table of linked lists.</summary>
 34/// <typeparam name="T">The type of values stored in this data structure.</typeparam>
 35/// <typeparam name="TEquate">The type of function for quality checking <typeparamref name="T"/> values.</typeparam>
 36/// <typeparam name="THash">The type of function for hashing <typeparamref name="T"/> values.</typeparam>
 37public class SetHashLinked<T, TEquate, THash> : ISet<T>,
 38  ICloneable<SetHashLinked<T, TEquate, THash>>,
 39  DataStructure.IEquating<T, TEquate>,
 40  DataStructure.IHashing<T, THash>
 41  where TEquate : struct, IFunc<T, T, bool>
 42  where THash : struct, IFunc<T, int>
 43{
 44  internal const float _maxLoadFactor = .7f;
 45  internal const float _minLoadFactor = .3f;
 46
 47  internal TEquate _equate;
 48  internal THash _hash;
 49  internal Node?[] _table;
 50  internal int _count;
 51
 52  #region Nested Types
 53
 54  internal class Node
 55  {
 56    internal T Value;
 57    internal Node? Next;
 58
 165396959    internal Node(T value, Node? next = null)
 165396960    {
 165396961      Value = value;
 165396962      Next = next;
 165396963    }
 64  }
 65
 66  #endregion
 67
 68  #region Constructors
 69
 70  /// <summary>Constructs a hashed set.</summary>
 71  /// <param name="equate">The function for quality checking <typeparamref name="T"/> values.</param>
 72  /// <param name="hash">The function for hashing <typeparamref name="T"/> values.</param>
 73  /// <param name="expectedCount">The expected count of the set.</param>
 2445874  public SetHashLinked(
 2445875    TEquate equate = default,
 2445876    THash hash = default,
 2445877    int? expectedCount = null)
 2445878  {
 2445879    if (expectedCount.HasValue && expectedCount.Value > 0)
 428880    {
 428881      int tableSize = (int)(expectedCount.Value * (1 / _maxLoadFactor));
 2452582      while (!IsPrime(tableSize))
 2023783      {
 2023784        tableSize++;
 2023785      }
 428886      _table = new Node[tableSize];
 428887    }
 88    else
 2017089    {
 2017090      _table = new Node[2];
 2017091    }
 2445892    _equate = equate;
 2445893    _hash = hash;
 2445894    _count = 0;
 2445895  }
 96
 97  /// <summary>
 98  /// This constructor is for cloning purposes.<br/>
 99  /// Runtime: O(n)
 100  /// </summary>
 101  /// <param name="set">The set to clone.</param>
 0102  internal SetHashLinked(SetHashLinked<T, TEquate, THash> set)
 0103  {
 0104    _equate = set._equate;
 0105    _hash = set._hash;
 0106    _table = (Node[])set._table.Clone();
 0107    _count = set._count;
 0108  }
 109
 110  #endregion
 111
 112  #region Properties
 113
 114  /// <summary>
 115  /// The current size of the hashed table.<br/>
 116  /// Runtime: O(1)
 117  /// </summary>
 0118  public int TableSize => _table.Length;
 119
 120  /// <summary>
 121  /// The current number of values in the set.<br/>
 122  /// Runtime: O(1)
 123  /// </summary>
 24301124  public int Count => _count;
 125
 126  /// <inheritdoc/>
 0127  public THash Hash => _hash;
 128
 129  /// <inheritdoc/>
 0130  public TEquate Equate => _equate;
 131
 132  #endregion
 133
 134  #region Methods
 135
 136  internal int GetLocation(T value) =>
 7500234137    (_hash.Invoke(value) & int.MaxValue) % _table.Length;
 138
 139  /// <inheritdoc/>
 140  public (bool Success, Exception? Exception) TryAdd(T value)
 1663761141  {
 1663761142    int location = GetLocation(value);
 4548586143    for (Node? node = _table[location]; node is not null; node = node.Next)
 620324144    {
 620324145      if (_equate.Invoke(node.Value, value))
 9792146      {
 9792147        return (false, new ArgumentException("Attempting to add a duplicate value to a set.", nameof(value)));
 148      }
 610532149    }
 1653969150    _table[location] = new Node(value: value, next: _table[location]);
 1653969151    if (++_count > _table.Length * _maxLoadFactor)
 80280152    {
 80280153      float tableSizeFloat = (_count * 2) * (1 / _maxLoadFactor);
 80280154      if (tableSizeFloat <= int.MaxValue)
 80280155      {
 80280156        int tableSize = (int)tableSizeFloat;
 180695157        while (!IsPrime(tableSize))
 100415158        {
 100415159          tableSize++;
 100415160        }
 80280161        Resize(tableSize);
 80280162      }
 80280163    }
 1653969164    return (true, null);
 1663761165  }
 166
 167  /// <inheritdoc/>
 168  public (bool Success, Exception? Exception) TryRemove(T value)
 66800169  {
 66800170    var (success, exception) = TryRemoveWithoutTrim(value);
 66800171    if (!success)
 0172    {
 0173      return (false, exception);
 174    }
 66800175    else if (_table.Length > 2 && _count < _table.Length * _minLoadFactor)
 52176    {
 52177      int tableSize = (int)(_count * (1 / _maxLoadFactor));
 102178      while (!IsPrime(tableSize))
 50179      {
 50180        tableSize++;
 50181      }
 52182      Resize(tableSize);
 52183    }
 66800184    return (true, null);
 66800185  }
 186
 187  /// <summary>Tries to remove a value from the set without shrinking the hash table.</summary>
 188  /// <param name="value">The value to remove.</param>
 189  /// <returns>True if the remove was successful or false if not.</returns>
 190  public (bool Success, Exception? Exception) TryRemoveWithoutTrim(T value)
 66800191  {
 66800192    int location = GetLocation(value);
 222345193    for (Node? node = _table[location], previous = null; node is not null; previous = node, node = node.Next)
 74115194    {
 74115195      if (_equate.Invoke(node.Value, value))
 66800196      {
 66800197        if (previous is null)
 60435198        {
 60435199          _table[location] = node.Next;
 60435200        }
 201        else
 6365202        {
 6365203          previous.Next = node.Next;
 6365204        }
 66800205        _count--;
 66800206        return (true, null);
 207      }
 7315208    }
 0209    return (false, new ArgumentException("Attempting to remove a value that is no in a set.", nameof(value)));
 66800210  }
 211
 212  /// <summary>Resizes the table.</summary>
 213  /// <param name="tableSize">The desired size of the table.</param>
 214  internal void Resize(int tableSize)
 80332215  {
 80332216    if (tableSize == _table.Length)
 0217    {
 0218      return;
 219    }
 80332220    Node?[] temp = _table;
 80332221    _table = new Node[tableSize];
 7178100222    for (int i = 0; i < temp.Length; i++)
 3508718223    {
 11654306224      for (Node? node = temp[i]; node is not null; node = temp[i])
 2318435225      {
 2318435226        temp[i] = node.Next;
 2318435227        int location = GetLocation(node.Value);
 2318435228        node.Next = _table[location];
 2318435229        _table[location] = node;
 2318435230      }
 3508718231    }
 80332232  }
 233
 234  /// <summary>
 235  /// Trims the table to an appropriate size based on the current count.<br/>
 236  /// Runtime: O(n), Ω(1)
 237  /// </summary>
 238  public void Trim()
 0239  {
 0240    int tableSize = _count;
 0241    while (!IsPrime(tableSize))
 0242    {
 0243      tableSize++;
 0244    }
 0245    Resize(tableSize);
 0246  }
 247
 248  /// <inheritdoc/>
 0249  public SetHashLinked<T, TEquate, THash> Clone() => new(this);
 250
 251  /// <inheritdoc/>
 252  public bool Contains(T value)
 3451238253  {
 3451238254    int location = GetLocation(value);
 10026026255    for (Node? node = _table[location]; node is not null; node = node.Next)
 2086200256    {
 2086200257      if (_equate.Invoke(node.Value, value))
 524425258      {
 524425259        return true;
 260      }
 1561775261    }
 2926813262    return false;
 3451238263  }
 264
 265  /// <inheritdoc/>
 266  public void Clear()
 9267  {
 9268    _table = new Node[2];
 9269    _count = 0;
 9270  }
 271
 272  /// <inheritdoc/>
 273  public StepStatus StepperBreak<TStep>(TStep step = default) where TStep : struct, IFunc<T, StepStatus>
 4274  {
 24275    for (int i = 0; i < _table.Length; i++)
 8276    {
 22277      for (Node? node = _table[i]; node is not null; node = node.Next)
 3278      {
 3279        if (step.Invoke(node.Value) is Break)
 0280        {
 0281          return Break;
 282        }
 3283      }
 8284    }
 4285    return Continue;
 4286  }
 287
 0288  System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator() => GetEnumerator();
 289
 290  /// <inheritdoc/>
 291  public System.Collections.Generic.IEnumerator<T> GetEnumerator()
 4292  {
 30293    for (int i = 0; i < _table.Length; i++)
 11294    {
 28295      for (Node? node = _table[i]; node is not null; node = node.Next)
 3296      {
 3297        yield return node.Value;
 3298      }
 11299    }
 4300  }
 301
 302  /// <inheritdoc/>
 303  public T[] ToArray()
 0304  {
 0305    T[] array = new T[_count];
 0306    for (int i = 0, index = 0; i < _table.Length; i++)
 0307    {
 0308      for (Node? node = _table[i]; node is not null; node = node.Next, index++)
 0309      {
 0310        array[index] = node.Value;
 0311      }
 0312    }
 0313    return array;
 0314  }
 315
 316  #endregion
 317}
Generated by: ReportGenerator 4.8.11.0
08/14/2022 - 14:40:44
GitHub | www.palmmedia.de

Methods/Properties

.ctor(...)
.ctor(...)
.ctor(...)
get_TableSize()
get_Count()
get_Hash()
get_Equate()
GetLocation(...)
TryAdd(...)
TryRemove(...)
TryRemoveWithoutTrim(...)
Resize(...)
Trim()
Clone()
Contains(...)
Clear()
StepperBreak(...)
System.Collections.IEnumerable.GetEnumerator()
GetEnumerator()
ToArray()