| | 1 | | namespace 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> |
| | 5 | | public 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> |
| | 16 | | public 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) => |
| 20036 | 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> |
| | 37 | | public 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 | | } |