< Summary

Class:Towel.DataStructures.SetHashLinked
Assembly:Towel
File(s):File 1: /home/runner/work/Towel/Towel/Sources/Towel/DataStructures/Set.cs
Covered lines:1
Uncovered lines:0
Coverable lines:1
Total lines:317
Line coverage:100% (1 of 1)
Covered branches:4
Total branches:4
Branch coverage:100% (4 of 4)

Metrics

MethodBranch coverage Cyclomatic complexity Line coverage
File 1: New(...)100%4100%

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) =>
 2003628    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
 59    internal Node(T value, Node? next = null)
 60    {
 61      Value = value;
 62      Next = next;
 63    }
 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>
 74  public SetHashLinked(
 75    TEquate equate = default,
 76    THash hash = default,
 77    int? expectedCount = null)
 78  {
 79    if (expectedCount.HasValue && expectedCount.Value > 0)
 80    {
 81      int tableSize = (int)(expectedCount.Value * (1 / _maxLoadFactor));
 82      while (!IsPrime(tableSize))
 83      {
 84        tableSize++;
 85      }
 86      _table = new Node[tableSize];
 87    }
 88    else
 89    {
 90      _table = new Node[2];
 91    }
 92    _equate = equate;
 93    _hash = hash;
 94    _count = 0;
 95  }
 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>
 102  internal SetHashLinked(SetHashLinked<T, TEquate, THash> set)
 103  {
 104    _equate = set._equate;
 105    _hash = set._hash;
 106    _table = (Node[])set._table.Clone();
 107    _count = set._count;
 108  }
 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>
 118  public int TableSize => _table.Length;
 119
 120  /// <summary>
 121  /// The current number of values in the set.<br/>
 122  /// Runtime: O(1)
 123  /// </summary>
 124  public int Count => _count;
 125
 126  /// <inheritdoc/>
 127  public THash Hash => _hash;
 128
 129  /// <inheritdoc/>
 130  public TEquate Equate => _equate;
 131
 132  #endregion
 133
 134  #region Methods
 135
 136  internal int GetLocation(T value) =>
 137    (_hash.Invoke(value) & int.MaxValue) % _table.Length;
 138
 139  /// <inheritdoc/>
 140  public (bool Success, Exception? Exception) TryAdd(T value)
 141  {
 142    int location = GetLocation(value);
 143    for (Node? node = _table[location]; node is not null; node = node.Next)
 144    {
 145      if (_equate.Invoke(node.Value, value))
 146      {
 147        return (false, new ArgumentException("Attempting to add a duplicate value to a set.", nameof(value)));
 148      }
 149    }
 150    _table[location] = new Node(value: value, next: _table[location]);
 151    if (++_count > _table.Length * _maxLoadFactor)
 152    {
 153      float tableSizeFloat = (_count * 2) * (1 / _maxLoadFactor);
 154      if (tableSizeFloat <= int.MaxValue)
 155      {
 156        int tableSize = (int)tableSizeFloat;
 157        while (!IsPrime(tableSize))
 158        {
 159          tableSize++;
 160        }
 161        Resize(tableSize);
 162      }
 163    }
 164    return (true, null);
 165  }
 166
 167  /// <inheritdoc/>
 168  public (bool Success, Exception? Exception) TryRemove(T value)
 169  {
 170    var (success, exception) = TryRemoveWithoutTrim(value);
 171    if (!success)
 172    {
 173      return (false, exception);
 174    }
 175    else if (_table.Length > 2 && _count < _table.Length * _minLoadFactor)
 176    {
 177      int tableSize = (int)(_count * (1 / _maxLoadFactor));
 178      while (!IsPrime(tableSize))
 179      {
 180        tableSize++;
 181      }
 182      Resize(tableSize);
 183    }
 184    return (true, null);
 185  }
 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)
 191  {
 192    int location = GetLocation(value);
 193    for (Node? node = _table[location], previous = null; node is not null; previous = node, node = node.Next)
 194    {
 195      if (_equate.Invoke(node.Value, value))
 196      {
 197        if (previous is null)
 198        {
 199          _table[location] = node.Next;
 200        }
 201        else
 202        {
 203          previous.Next = node.Next;
 204        }
 205        _count--;
 206        return (true, null);
 207      }
 208    }
 209    return (false, new ArgumentException("Attempting to remove a value that is no in a set.", nameof(value)));
 210  }
 211
 212  /// <summary>Resizes the table.</summary>
 213  /// <param name="tableSize">The desired size of the table.</param>
 214  internal void Resize(int tableSize)
 215  {
 216    if (tableSize == _table.Length)
 217    {
 218      return;
 219    }
 220    Node?[] temp = _table;
 221    _table = new Node[tableSize];
 222    for (int i = 0; i < temp.Length; i++)
 223    {
 224      for (Node? node = temp[i]; node is not null; node = temp[i])
 225      {
 226        temp[i] = node.Next;
 227        int location = GetLocation(node.Value);
 228        node.Next = _table[location];
 229        _table[location] = node;
 230      }
 231    }
 232  }
 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()
 239  {
 240    int tableSize = _count;
 241    while (!IsPrime(tableSize))
 242    {
 243      tableSize++;
 244    }
 245    Resize(tableSize);
 246  }
 247
 248  /// <inheritdoc/>
 249  public SetHashLinked<T, TEquate, THash> Clone() => new(this);
 250
 251  /// <inheritdoc/>
 252  public bool Contains(T value)
 253  {
 254    int location = GetLocation(value);
 255    for (Node? node = _table[location]; node is not null; node = node.Next)
 256    {
 257      if (_equate.Invoke(node.Value, value))
 258      {
 259        return true;
 260      }
 261    }
 262    return false;
 263  }
 264
 265  /// <inheritdoc/>
 266  public void Clear()
 267  {
 268    _table = new Node[2];
 269    _count = 0;
 270  }
 271
 272  /// <inheritdoc/>
 273  public StepStatus StepperBreak<TStep>(TStep step = default) where TStep : struct, IFunc<T, StepStatus>
 274  {
 275    for (int i = 0; i < _table.Length; i++)
 276    {
 277      for (Node? node = _table[i]; node is not null; node = node.Next)
 278      {
 279        if (step.Invoke(node.Value) is Break)
 280        {
 281          return Break;
 282        }
 283      }
 284    }
 285    return Continue;
 286  }
 287
 288  System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator() => GetEnumerator();
 289
 290  /// <inheritdoc/>
 291  public System.Collections.Generic.IEnumerator<T> GetEnumerator()
 292  {
 293    for (int i = 0; i < _table.Length; i++)
 294    {
 295      for (Node? node = _table[i]; node is not null; node = node.Next)
 296      {
 297        yield return node.Value;
 298      }
 299    }
 300  }
 301
 302  /// <inheritdoc/>
 303  public T[] ToArray()
 304  {
 305    T[] array = new T[_count];
 306    for (int i = 0, index = 0; i < _table.Length; i++)
 307    {
 308      for (Node? node = _table[i]; node is not null; node = node.Next, index++)
 309      {
 310        array[index] = node.Value;
 311      }
 312    }
 313    return array;
 314  }
 315
 316  #endregion
 317}
Generated by: ReportGenerator 4.8.11.0
08/14/2022 - 14:40:44
GitHub | www.palmmedia.de

Methods/Properties

New(...)