< Summary

Class:Towel.DataStructures.Map
Assembly:Towel
File(s):File 1: /home/runner/work/Towel/Towel/Sources/Towel/DataStructures/Map.cs
Covered lines:37
Uncovered lines:25
Coverable lines:62
Total lines:893
Line coverage:59.6% (37 of 62)
Covered branches:11
Total branches:32
Branch coverage:34.3% (11 of 32)

Metrics

MethodBranch coverage Cyclomatic complexity Line coverage
File 1: Update(...)100%10%
File 1: AddOrUpdate(...)100%10%
File 1: Update(...)0%40%
File 1: AddOrUpdate(...)25%471.42%
File 1: TryUpdate(...)0%20%
File 1: TryAddOrUpdate(...)0%20%
File 1: Add(...)75%4100%
File 1: Set(...)25%471.42%
File 1: Get(...)75%4100%
File 1: Keys(...)50%2100%
File 1: Keys(...)100%1100%
File 1: KeysBreak(...)0%20%
File 1: Pairs(...)50%2100%
File 1: Pairs(...)100%1100%
File 1: PairsBreak(...)50%2100%

File(s)

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

#LineLine coverage
 1namespace Towel.DataStructures;
 2
 3/// <summary>A map between instances of two types. The polymorphism base for Map implementations in Towel.</summary>
 4/// <typeparam name="T">The generic type to be stored in this data structure.</typeparam>
 5/// <typeparam name="TKey">The type of keys used to look up items in this structure.</typeparam>
 6public interface IMap<T, TKey> : IDataStructure<T>,
 7  DataStructure.ICountable,
 8  DataStructure.IClearable,
 9  DataStructure.IAuditable<TKey>,
 10  DataStructure.IRemovable<TKey>
 11{
 12  #region Properties
 13
 14  /// <summary>Allows indexed look-up of the structure. (Set does not replace the Add() method)</summary>
 15  /// <param name="key">The "index" to access of the structure.</param>
 16  /// <returns>The value at the index of the requested key.</returns>
 17  T this[TKey key] { get; set; }
 18
 19  #endregion
 20
 21  #region Methods
 22
 23  /// <summary>Tries to get a value by key.</summary>
 24  /// <param name="key">The key of the value to get.</param>
 25  /// <returns>
 26  /// - <see cref="bool"/> Success: true if the key was found or false if not.<br/>
 27  /// - <see cref="Exception"/>? Exception: the exception that occured if the get failed.<br/>
 28  /// - <typeparamref name="T"/>? Value: the value if the key was found or default if not.
 29  /// </returns>
 30  (bool Success, Exception? Exception, T? Value) TryGet(TKey key);
 31
 32  /// <summary>Sets value in the map.</summary>
 33  /// <param name="key">The key of the value.</param>
 34  /// <param name="value">The value to be set.</param>
 35  /// <returns>
 36  /// - <see cref="bool"/> Success: true if the key+value was set or false if not.<br/>
 37  /// - <see cref="Exception"/>? Exception: the exception that occured if the set failed.<br/>
 38  /// - <see cref="bool"/>? Existed: if the key existed prior to being set<br/>
 39  /// - <typeparamref name="T"/>? OldValue: the previous value if the key existed prior to being set
 40  /// </returns>
 41  (bool Success, Exception? Exception, bool? Existed, T? OldValue) TrySet(TKey key, T value);
 42
 43  /// <summary>Tries to add a value to the map.</summary>
 44  /// <param name="key">The key of the value.</param>
 45  /// <param name="value">The value to be added.</param>
 46  /// <returns>
 47  /// - <see cref="bool"/> Success: true if the key+value was added or false if not<br/>
 48  /// - <see cref="Exception"/>? Exception: the exception that occured if the add failed
 49  /// </returns>
 50  (bool Success, Exception? Exception) TryAdd(TKey key, T value);
 51
 52  /// <summary>Tries to update a value in the map the relative key exists.</summary>
 53  /// <typeparam name="TRemovePredicate">The type of predicate determining if the pair should be removed.</typeparam>
 54  /// <typeparam name="TUpdate">The type of function to update the value.</typeparam>
 55  /// <param name="key">The key of the value to update.</param>
 56  /// <param name="removePredicate">The predicate determining if the pair should be removed.</param>
 57  /// <param name="update">The function to update the value relative to the key.</param>
 58  /// <returns>
 59  /// - <see cref="bool"/> Success: true if the key was found or false if not<br/>
 60  /// - <see cref="Exception"/>? Exception: the exception that occured if the add failed<br/>
 61  /// - <typeparamref name="T"/>? OldValue: the non-updated value if the key was found or default if not<br/>
 62  /// - <typeparamref name="T"/>? NewValue: the updated value if the key was found or default if not
 63  /// </returns>
 64  (bool Success, Exception? Exception, bool? Removed, T? OldValue, T? NewValue) TryRemoveOrUpdate<TRemovePredicate, TUpd
 65    where TRemovePredicate : struct, IFunc<T, bool>
 66    where TUpdate : struct, IFunc<T, T>;
 67
 68  /// <summary>Tries to update a value in the map the relative key exists.</summary>
 69  /// <typeparam name="TUpdate">The type of function to update the value.</typeparam>
 70  /// <param name="key">The key of the value to update.</param>
 71  /// <param name="update">The function to update the value relative to the key.</param>
 72  /// <returns>
 73  /// - <see cref="bool"/> Success: true if the key was found or false if not<br/>
 74  /// - <see cref="Exception"/>? Exception: the exception that occured if the add failed<br/>
 75  /// - <typeparamref name="T"/>? OldValue: the non-updated value if the key was found or default if not<br/>
 76  /// - <typeparamref name="T"/>? NewValue: the updated value if the key was found or default if not
 77  /// </returns>
 78  (bool Success, Exception? Exception, T? OldValue, T? NewValue) TryUpdate<TUpdate>(TKey key, TUpdate update = default)
 79    where TUpdate : struct, IFunc<T, T>;
 80
 81  /// <summary>Adds or updates the value at the given key.</summary>
 82  /// <typeparam name="TUpdate">The type of function to update the value if present.</typeparam>
 83  /// <param name="key">The key of the value to add or update.</param>
 84  /// <param name="value">The value to add if not already present.</param>
 85  /// <param name="update">The function to update the value if present.</param>
 86  /// <returns>
 87  /// - <see cref="bool"/> Success: true if the value was added or updated or false if not.<br/>
 88  /// - <see cref="Exception"/>? Exception: the exception that occured if the add or update failed.<br/>
 89  /// - <see cref="bool"/>? Existed: if the key existed prior to the add or update<br/>
 90  /// - <typeparamref name="T"/>? OldValue: the old value if the key existed prior to the add or update
 91  /// </returns>
 92  (bool Success, Exception? Exception, bool? Existed, T? OldValue) TryAddOrUpdate<TUpdate>(TKey key, T value, TUpdate up
 93    where TUpdate : struct, IFunc<T, T>;
 94
 95  /// <summary>Gets an enumerator that will traverse the keys of the map.</summary>
 96  /// <returns>An enumerator that will traverse the keys of the map.</returns>
 97  System.Collections.Generic.IEnumerable<TKey> GetKeys();
 98
 99  /// <summary>Gets an array with all the keys in the map.</summary>
 100  /// <returns>An array with all the keys in the map.</returns>
 101  TKey[] KeysToArray();
 102
 103  /// <summary>Performs a function on every key in a map.</summary>
 104  /// <typeparam name="TStep">The type of the step function.</typeparam>
 105  /// <param name="step">The step function to perform on every key.</param>
 106  /// <returns>The status of traversal.</returns>
 107  StepStatus KeysBreak<TStep>(TStep step = default)
 108    where TStep : struct, IFunc<TKey, StepStatus>;
 109
 110  /// <summary>Gets an enumerator that will traverse the pairs of the map.</summary>
 111  /// <returns>An enumerator that will traverse the pairs of the map.</returns>
 112  System.Collections.Generic.IEnumerable<(T Value, TKey Key)> GetPairs();
 113
 114  /// <summary>Gets an array with all the pairs in the map.</summary>
 115  /// <returns>An array with all the pairs in the map.</returns>
 116  (T Value, TKey Key)[] PairsToArray();
 117
 118  /// <summary>Performs a function on every pair in a map.</summary>
 119  /// <typeparam name="TStep">The type of the step function.</typeparam>
 120  /// <param name="step">The step function to perform on every pair.</param>
 121  /// <returns>The status of traversal.</returns>
 122  StepStatus PairsBreak<TStep>(TStep step = default)
 123    where TStep : struct, IFunc<(T Value, TKey Key), StepStatus>;
 124
 125  #endregion
 126}
 127
 128/// <summary>Static Extension class for Map interface implementers.</summary>
 129public static class Map
 130{
 131  #region Extensions Methods
 132
 133  /// <summary>Updates a value in the map the relative key exists.</summary>
 134  /// <typeparam name="T">The type of values in the map.</typeparam>
 135  /// <typeparam name="TKey">The type of keys in the map.</typeparam>
 136  /// <param name="map">The map to update the value in.</param>
 137  /// <param name="key">The key of the value to update.</param>
 138  /// <param name="update">The function to update the value relative to the key.</param>
 139  /// <returns>
 140  /// (<typeparamref name="T"/> OldValue, <typeparamref name="T"/> NewValue)<br/>
 141  /// - <typeparamref name="T"/> OldValue: the value relative tothe key before to the update<br/>
 142  /// - <typeparamref name="T"/> NewValue: the value relative tothe key after to the update
 143  /// </returns>
 144  public static (T OldValue, T NewValue) Update<T, TKey>(this IMap<T, TKey> map, TKey key, Func<T, T> update) =>
 0145    map.Update<T, TKey, SFunc<T, T>>(key, update);
 146
 147  /// <summary>Adds or updates the value at the given key.</summary>
 148  /// <typeparam name="T">The type of values in the map.</typeparam>
 149  /// <typeparam name="TKey">The type of keys in the map.</typeparam>
 150  /// <param name="map">The map to add or update the value in.</param>
 151  /// <param name="key">The key of the value to add or update.</param>
 152  /// <param name="value">The value to add if not already present.</param>
 153  /// <param name="update">The function to update the value if present.</param>
 154  /// <returns>
 155  /// (<see cref="bool"/> Existed, <typeparamref name="T"/> OldValue)<br/>
 156  /// - <see cref="bool"/> Existed: true if the key was already in the map<br/>
 157  /// - <typeparamref name="T"/> OldValue: the value relative tothe key before to the update if it existed or default
 158  /// </returns>
 159  public static (bool Existed, T? OldValue) AddOrUpdate<T, TKey>(this IMap<T, TKey> map, TKey key, T value, Func<T, T> u
 0160    map.AddOrUpdate<T, TKey, SFunc<T, T>>(key, value, update);
 161
 162  /// <summary>Updates a value in the map the relative key exists.</summary>
 163  /// <typeparam name="T">The type of values in the map.</typeparam>
 164  /// <typeparam name="TKey">The type of keys in the map.</typeparam>
 165  /// <typeparam name="TUpdate">The type of function to update the value.</typeparam>
 166  /// <param name="map">The map to update the value in.</param>
 167  /// <param name="key">The key of the value to update.</param>
 168  /// <param name="update">The function to update the value relative to the key.</param>
 169  /// <returns>
 170  /// (<typeparamref name="T"/> OldValue, <typeparamref name="T"/> NewValue)<br/>
 171  /// - <typeparamref name="T"/> OldValue: the value relative tothe key before to the update<br/>
 172  /// - <typeparamref name="T"/> NewValue: the value relative tothe key after to the update
 173  /// </returns>
 174  public static (T OldValue, T NewValue) Update<T, TKey, TUpdate>(this IMap<T, TKey> map, TKey key, TUpdate update = def
 175    where TUpdate : struct, IFunc<T, T>
 0176  {
 0177    var (success, exception, oldValue, newValue) = map.TryUpdate(key, update);
 0178    if (!success)
 0179    {
 0180      throw exception ?? new ArgumentException($"{nameof(Update)} failed but the {nameof(exception)} is null");
 181    }
 0182    return (oldValue!, newValue!);
 0183  }
 184
 185  /// <summary>Adds or updates the value at the given key.</summary>
 186  /// <typeparam name="T">The type of values in the map.</typeparam>
 187  /// <typeparam name="TKey">The type of keys in the map.</typeparam>
 188  /// <typeparam name="TUpdate">The type of function to update the value.</typeparam>
 189  /// <param name="map">The map to add or update the value in.</param>
 190  /// <param name="key">The key of the value to add or update.</param>
 191  /// <param name="value">The value to add if not already present.</param>
 192  /// <param name="update">The function to update the value if present.</param>
 193  /// <returns>
 194  /// - <see cref="bool"/> Existed: true if the key was already in the map<br/>
 195  /// - <typeparamref name="T"/> OldValue: the value relative tothe key before to the update if it existed or default
 196  /// </returns>
 197  public static (bool Existed, T? OldValue) AddOrUpdate<T, TKey, TUpdate>(this IMap<T, TKey> map, TKey key, T value, TUp
 198    where TUpdate : struct, IFunc<T, T>
 70199  {
 70200    var (success, exception, existed, oldValue) = map.TryAddOrUpdate(key, value, update);
 70201    if (!success)
 0202    {
 0203      throw exception ?? new ArgumentException($"{nameof(AddOrUpdate)} failed but the {nameof(exception)} is null");
 204    }
 70205    return (existed!.Value, oldValue);
 70206  }
 207
 208  /// <summary>Tries to update a value in the map the relative key exists.</summary>
 209  /// <typeparam name="T">The type of values in the map.</typeparam>
 210  /// <typeparam name="TKey">The type of keys in the map.</typeparam>
 211  /// <param name="map">The map to update the value in.</param>
 212  /// <param name="key">The key of the value to update.</param>
 213  /// <param name="update">The function to update the value relative to the key.</param>
 214  /// <returns>
 215  /// - <see cref="bool"/> Success: true if the key was found or false if not<br/>
 216  /// - <see cref="Exception"/>? Exception: the exception that occured if the update failed<br/>
 217  /// - <typeparamref name="T"/>? OldValue: the value if the key was found or default if not<br/>
 218  /// - <typeparamref name="T"/>? NewValue: the value if the key was found or default if not
 219  /// </returns>
 220  public static (bool Success, Exception? Exception, T? OldValue, T? NewValue) TryUpdate<T, TKey>(this IMap<T, TKey> map
 0221  {
 0222    if (update is null) throw new ArgumentNullException(nameof(update));
 0223    return map.TryUpdate<SFunc<T, T>>(key, update);
 0224  }
 225
 226  /// <summary>Tries to add or update the value at the given key.</summary>
 227  /// <typeparam name="T">The type of values in the map.</typeparam>
 228  /// <typeparam name="TKey">The type of keys in the map.</typeparam>
 229  /// <param name="map">The map to add or update the value in.</param>
 230  /// <param name="key">The key of the value to add or update.</param>
 231  /// <param name="value">The value to add if not already present.</param>
 232  /// <param name="update">The function to update the value if present.</param>
 233  /// <returns>
 234  /// - <see cref="bool"/> Success: true if the value was added or updated or false if not.<br/>
 235  /// - <see cref="Exception"/>? Exception: the exception that occured if the add or update failed<br/>
 236  /// - <see cref="bool"/>? Existed: true if the key-value pair was added or updated or false<br/>
 237  /// - <typeparamref name="T"/>? OldValue: the previous value if the key existed before the add or update operation
 238  /// </returns>
 239  public static (bool Success, Exception? Exception, bool? Existed, T? OldValue) TryAddOrUpdate<T, TKey>(this IMap<T, TK
 0240  {
 0241    if (update is null) throw new ArgumentNullException(nameof(update));
 0242    return map.TryAddOrUpdate<SFunc<T, T>>(key, value, update);
 0243  }
 244
 245  /// <summary>Adds a value to a map by key.</summary>
 246  /// <typeparam name="T">The type of values in the map.</typeparam>
 247  /// <typeparam name="TKey">The type of keys in the map.</typeparam>
 248  /// <param name="map">The map to add the value to.</param>
 249  /// <param name="key">The key of the value to get.</param>
 250  /// <param name="value">The value to add to the map.</param>
 251  public static void Add<T, TKey>(this IMap<T, TKey> map, TKey key, T value)
 400135252  {
 400135253    var (success, exception) = map.TryAdd(key, value);
 400135254    if (!success)
 6255    {
 6256      throw exception ?? new ArgumentException($"{nameof(Add)} failed but the {nameof(exception)} is null");
 257    }
 400129258  }
 259
 260  /// <summary>Sets a value in a map relative to a key.</summary>
 261  /// <typeparam name="T">The type of the value.</typeparam>
 262  /// <typeparam name="TKey">The type of the key.</typeparam>
 263  /// <param name="map">The map to set the value in.</param>
 264  /// <param name="key">The key.</param>
 265  /// <param name="value">The value.</param>
 266  /// <returns>
 267  /// (<see cref="bool"/> Existed, <typeparamref name="T"/> OldValue)<br/>
 268  /// - <see cref="bool"/> Existed: true if the key was already in the map<br/>
 269  /// - <typeparamref name="T"/> OldValue: the value relative tothe key before to the update if it existed or default
 270  /// </returns>
 271  public static (bool Existed, T? OldValue) Set<T, TKey>(this IMap<T, TKey> map, TKey key, T value)
 201210272  {
 201210273    var (success, exception, existed, oldValue) = map.TrySet(key, value);
 201210274    if (!success)
 0275    {
 0276      throw exception ?? new ArgumentException($"{nameof(Set)} failed but the {nameof(exception)} is null");
 277    }
 201210278    return (existed!.Value, oldValue);
 201210279  }
 280
 281  /// <summary>Gets a value in a map relative to a key.</summary>
 282  /// <typeparam name="T">The type of the value.</typeparam>
 283  /// <typeparam name="TKey">The type of the key.</typeparam>
 284  /// <param name="map">The map to set the value in.</param>
 285  /// <param name="key">The key.</param>
 286  /// <returns>The value relative to the key.</returns>
 287  public static T Get<T, TKey>(this IMap<T, TKey> map, TKey key)
 400198288  {
 400198289    var (success, exception, value) = map.TryGet(key);
 400198290    if (!success)
 1291    {
 1292      throw exception ?? new ArgumentException($"{nameof(Get)} failed but the {nameof(exception)} is null");
 293    }
 400197294    return value!;
 400197295  }
 296
 297  /// <summary>Performs a function on every key in a map.</summary>
 298  /// <typeparam name="T">The type of values in the map.</typeparam>
 299  /// <typeparam name="TKey">The type of keys in the map.</typeparam>
 300  /// <param name="map">The map to traverse the keys of.</param>
 301  /// <param name="step">The step function to perform on every key.</param>
 302  public static void Keys<T, TKey>(this IMap<T, TKey> map, Action<TKey> step)
 31303  {
 31304    if (step is null) throw new ArgumentNullException(nameof(step));
 31305    map.Keys<T, TKey, SAction<TKey>>(step);
 31306  }
 307
 308  /// <summary>Performs a function on every key in a map.</summary>
 309  /// <typeparam name="T">The type of values in the map.</typeparam>
 310  /// <typeparam name="TKey">The type of keys in the map.</typeparam>
 311  /// <typeparam name="TStep">The type of step function to perform on every key.</typeparam>
 312  /// <param name="map">The map to traverse the keys of.</param>
 313  /// <param name="step">The step function to perform on every key.</param>
 314  public static void Keys<T, TKey, TStep>(this IMap<T, TKey> map, TStep step = default)
 315    where TStep : struct, IAction<TKey> =>
 31316    map.KeysBreak<StepBreakFromAction<TKey, TStep>>(step);
 317
 318  /// <summary>Performs a function on every key in a map.</summary>
 319  /// <typeparam name="T">The type of values in the map.</typeparam>
 320  /// <typeparam name="TKey">The type of keys in the map.</typeparam>
 321  /// <param name="map">The map to traverse the keys of.</param>
 322  /// <param name="step">The step function to perform on every key.</param>
 323  /// <returns>The status of the traversal.</returns>
 324  public static StepStatus KeysBreak<T, TKey>(this IMap<T, TKey> map, Func<TKey, StepStatus> step)
 0325  {
 0326    if (step is null) throw new ArgumentNullException(nameof(step));
 0327    return map.KeysBreak<SFunc<TKey, StepStatus>>(step);
 0328  }
 329
 330  /// <summary>Performs a function on every pair in a map.</summary>
 331  /// <typeparam name="T">The type of values in the map.</typeparam>
 332  /// <typeparam name="TKey">The type of keys in the map.</typeparam>
 333  /// <param name="map">The map to traverse the pairs of.</param>
 334  /// <param name="step">The step function to perform on every pair.</param>
 335  public static void Pairs<T, TKey>(this IMap<T, TKey> map, Action<(T Value, TKey Key)> step)
 5336  {
 5337    if (step is null) throw new ArgumentNullException(nameof(step));
 5338    map.Pairs<T, TKey, SAction<(T Value, TKey Key)>>(step);
 5339  }
 340
 341  /// <summary>Performs a function on every pair in a map.</summary>
 342  /// <typeparam name="T">The type of values in the map.</typeparam>
 343  /// <typeparam name="TKey">The type of keys in the map.</typeparam>
 344  /// <typeparam name="TStep">The type of step function to perform on every pair.</typeparam>
 345  /// <param name="map">The map to traverse the pairs of.</param>
 346  /// <param name="step">The step function to perform on every pair.</param>
 347  public static void Pairs<T, TKey, TStep>(this IMap<T, TKey> map, TStep step = default)
 348    where TStep : struct, IAction<(T Value, TKey Key)> =>
 5349    map.PairsBreak<StepBreakFromAction<(T Value, TKey Key), TStep>>(step);
 350
 351  /// <summary>Performs a function on every pair in a map.</summary>
 352  /// <typeparam name="T">The type of values in the map.</typeparam>
 353  /// <typeparam name="TKey">The type of keys in the map.</typeparam>
 354  /// <param name="map">The map to traverse the pairs of.</param>
 355  /// <param name="step">The step function to perform on every pair.</param>
 356  /// <returns>The status of the traversal.</returns>
 357  public static StepStatus PairsBreak<T, TKey>(this IMap<T, TKey> map, Func<(T Value, TKey Key), StepStatus> step)
 1358  {
 1359    if (step is null) throw new ArgumentNullException(nameof(step));
 1360    return map.PairsBreak<SFunc<(T Value, TKey Key), StepStatus>>(step);
 1361  }
 362
 363  #endregion
 364}
 365
 366/// <summary>Static helpers.</summary>
 367public static class MapHashLinked
 368{
 369  #region Extension Methods
 370
 371  /// <summary>Constructs a new <see cref="MapHashLinked{T, K, TEquate, THash}"/>.</summary>
 372  /// <typeparam name="T">The type of values stored in this data structure.</typeparam>
 373  /// <typeparam name="TKey">The type of keys used to look up values.</typeparam>
 374  /// <param name="equate">The function for comparing <typeparamref name="T"/> values for equality.</param>
 375  /// <param name="hash">The function for hashing <typeparamref name="T"/> values.</param>
 376  /// <returns>The new constructed <see cref="MapHashLinked{T, K, TEquate, THash}"/>.</returns>
 377  public static MapHashLinked<T, TKey, SFunc<TKey, TKey, bool>, SFunc<TKey, int>> New<T, TKey>(
 378    Func<TKey, TKey, bool>? equate = null,
 379    Func<TKey, int>? hash = null) =>
 380    new(equate ?? Equate, hash ?? Hash);
 381
 382  #endregion
 383}
 384
 385/// <summary>An unsorted structure of unique items.</summary>
 386/// <typeparam name="T">The generic type of the structure.</typeparam>
 387/// <typeparam name="TKey">The generic key type of this map.</typeparam>
 388/// <typeparam name="TEquate">The type of function for quality checking <typeparamref name="TKey"/> values.</typeparam>
 389/// <typeparam name="THash">The type of function for hashing <typeparamref name="TKey"/> values.</typeparam>
 390public class MapHashLinked<T, TKey, TEquate, THash> : IMap<T, TKey>,
 391  ICloneable<MapHashLinked<T, TKey, TEquate, THash>>,
 392  DataStructure.IEquating<TKey, TEquate>,
 393  DataStructure.IHashing<TKey, THash>
 394  where TEquate : struct, IFunc<TKey, TKey, bool>
 395  where THash : struct, IFunc<TKey, int>
 396{
 397  internal const float _maxLoadFactor = .7f;
 398  internal const float _minLoadFactor = .3f;
 399
 400  internal TEquate _equate;
 401  internal THash _hash;
 402  internal Node?[] _table;
 403  internal int _count;
 404
 405  #region Nested Types
 406
 407  internal class Node
 408  {
 409    internal TKey Key;
 410    internal T Value;
 411    internal Node? Next;
 412
 413    internal Node(T value, TKey key, Node? next = null)
 414    {
 415      Value = value;
 416      Key = key;
 417      Next = next;
 418    }
 419  }
 420
 421  #endregion
 422
 423  #region Constructors
 424
 425  /// <summary>Constructs a new <see cref="MapHashLinked{T, K, TEquate, THash}"/>.</summary>
 426  /// <param name="equate">The function for quality checking <typeparamref name="TKey"/> values.</param>
 427  /// <param name="hash">The function for hashing <typeparamref name="TKey"/> values.</param>
 428  /// <param name="expectedCount">The expected count of the map.</param>
 429  public MapHashLinked(
 430    TEquate equate = default,
 431    THash hash = default,
 432    int? expectedCount = null)
 433  {
 434    if (expectedCount.HasValue && expectedCount.Value > 0)
 435    {
 436      int tableSize = (int)(expectedCount.Value * (1 / _maxLoadFactor));
 437      while (!IsPrime(tableSize))
 438      {
 439        tableSize++;
 440      }
 441      _table = new Node[tableSize];
 442    }
 443    else
 444    {
 445      _table = new Node[2];
 446    }
 447    _equate = equate;
 448    _hash = hash;
 449    _count = 0;
 450  }
 451
 452  /// <summary>This constructor is for cloning purposes.</summary>
 453  /// <param name="map">The map to clone.</param>
 454  internal MapHashLinked(MapHashLinked<T, TKey, TEquate, THash> map)
 455  {
 456    _equate = map._equate;
 457    _hash = map._hash;
 458    _table = (Node[])map._table.Clone();
 459    _count = map._count;
 460  }
 461
 462  #endregion
 463
 464  #region Properties
 465
 466  /// <summary>The current size of the hashed table.</summary>
 467  public int TableSize => _table.Length;
 468
 469  /// <inheritdoc/>
 470  public int Count => _count;
 471
 472  /// <inheritdoc/>
 473  public THash Hash => _hash;
 474
 475  /// <inheritdoc/>
 476  public TEquate Equate => _equate;
 477
 478  /// <summary>Gets the value of a specified key.</summary>
 479  /// <param name="key">The key to get the value of.</param>
 480  /// <returns>The value of the key.</returns>
 481  public T this[TKey key] { get => this.Get(key); set => this.Set(key, value); }
 482
 483  #endregion
 484
 485  #region Methods
 486
 487  internal int GetLocation(TKey key) => (_hash.Invoke(key) & int.MaxValue) % _table.Length;
 488
 489  /// <inheritdoc/>
 490  public (bool Success, Exception? Exception) TryAdd(TKey key, T value)
 491  {
 492    int location = GetLocation(key);
 493    for (Node? node = _table[location]; node is not null; node = node.Next)
 494    {
 495      if (_equate.Invoke(node.Key, key))
 496      {
 497        return (false, new ArgumentException("Attempting to add a duplicate key to a map.", nameof(key)));
 498      }
 499    }
 500    _table[location] = new Node(value: value, key: key, next: _table[location]);
 501    _count++;
 502    if (_count > _table.Length * _maxLoadFactor)
 503    {
 504      float tableSizeFloat = (_count * 2) * (1 / _maxLoadFactor);
 505      if (tableSizeFloat <= int.MaxValue)
 506      {
 507        int tableSize = (int)tableSizeFloat;
 508        while (!IsPrime(tableSize))
 509        {
 510          tableSize++;
 511        }
 512        Resize(tableSize);
 513      }
 514    }
 515    return (true, null);
 516  }
 517
 518  /// <inheritdoc/>
 519  public (bool Success, Exception? Exception, bool? Existed, T? OldValue) TryAddOrUpdate<TUpdate>(TKey key, T value, TUp
 520    where TUpdate : struct, IFunc<T, T>
 521  {
 522    int location = GetLocation(key);
 523    for (Node? node = _table[location]; node is not null; node = node.Next)
 524    {
 525      if (_equate.Invoke(node.Key, key))
 526      {
 527        T oldValue = node.Value;
 528        node.Value = update.Invoke(node.Value);
 529        return (true, null, true, oldValue);
 530      }
 531    }
 532    _table[location] = new Node(
 533      value: value,
 534      key: key,
 535      next: _table[location]);
 536    _count++;
 537    if (_count > _table.Length * _maxLoadFactor)
 538    {
 539      float tableSizeFloat = (_count * 2) * (1 / _maxLoadFactor);
 540      if (tableSizeFloat <= int.MaxValue)
 541      {
 542        int tableSize = (int)tableSizeFloat;
 543        while (!IsPrime(tableSize))
 544        {
 545          tableSize++;
 546        }
 547        Resize(tableSize);
 548      }
 549    }
 550    return (true, null, false, default);
 551  }
 552
 553  /// <inheritdoc/>
 554  public (bool Success, Exception? Exception, bool? Removed, T? OldValue, T? NewValue) TryRemoveOrUpdate<TRemovePredicat
 555    where TRemovePredicate : struct, IFunc<T, bool>
 556    where TUpdate : struct, IFunc<T, T>
 557  {
 558    int location = GetLocation(key);
 559
 560    for (Node? node = _table[location], previous = null; node is not null; previous = node, node = node.Next)
 561    {
 562      if (_equate.Invoke(node.Key, key))
 563      {
 564        if (removePredicate.Invoke(node.Value))
 565        {
 566          if (previous is null)
 567          {
 568            _table[location] = node.Next;
 569          }
 570          else
 571          {
 572            previous.Next = node.Next;
 573          }
 574          _count--;
 575          return (true, null, true, node.Value, default);
 576        }
 577        else
 578        {
 579          T oldValue = node.Value;
 580          node.Value = update.Invoke(node.Value);
 581          return (true, null, false, oldValue, node.Value);
 582        }
 583      }
 584    }
 585    return (false, new ArgumentException(paramName: nameof(key), message: "key not found"), default, default, default);
 586  }
 587
 588  /// <inheritdoc/>
 589  public (bool Success, Exception? Exception, T? OldValue, T? NewValue) TryUpdate<TUpdate>(TKey key, TUpdate update = de
 590    where TUpdate : struct, IFunc<T, T>
 591  {
 592    int location = GetLocation(key);
 593    for (Node? node = _table[location]; node is not null; node = node.Next)
 594    {
 595      if (_equate.Invoke(node.Key, key))
 596      {
 597        T oldValue = node.Value;
 598        node.Value = update.Invoke(node.Value);
 599        return (true, null, oldValue, node.Value);
 600      }
 601    }
 602    return (false, new ArgumentException(paramName: nameof(key), message: "key not found"), default, default);
 603  }
 604
 605  /// <inheritdoc/>
 606  public (bool Success, Exception? Exception, T? Value) TryGet(TKey key)
 607  {
 608    int location = GetLocation(key);
 609    for (Node? node = _table[location]; node is not null; node = node.Next)
 610    {
 611      if (_equate.Invoke(node.Key, key))
 612      {
 613        return (true, null, node.Value);
 614      }
 615    }
 616    return (false, new ArgumentException("Attempting to get a value from the map that has not been added.", nameof(key))
 617  }
 618
 619  /// <inheritdoc/>
 620  public (bool Success, Exception? Exception, bool? Existed, T? OldValue) TrySet(TKey key, T value)
 621  {
 622    int location = GetLocation(key);
 623    for (Node? node = _table[location]; node is not null; node = node.Next)
 624    {
 625      if (_equate.Invoke(node.Key, key))
 626      {
 627        T oldValue = node.Value;
 628        node.Value = value;
 629        return (true, null, true, oldValue);
 630      }
 631    }
 632    _table[location] = new Node(
 633      value: value,
 634      key: key,
 635      next: _table[location]);
 636    _count++;
 637    if (_count > _table.Length * _maxLoadFactor)
 638    {
 639      float tableSizeFloat = (_count * 2) * (1 / _maxLoadFactor);
 640      if (tableSizeFloat <= int.MaxValue)
 641      {
 642        int tableSize = (int)tableSizeFloat;
 643        while (!IsPrime(tableSize))
 644        {
 645          tableSize++;
 646        }
 647        Resize(tableSize);
 648      }
 649    }
 650    return (true, null, false, default);
 651  }
 652
 653  /// <inheritdoc/>
 654  public (bool Success, Exception? Exception) TryRemove(TKey key)
 655  {
 656    var (success, exception) = TryRemoveWithoutTrim(key);
 657    if (!success)
 658    {
 659      return (false, exception);
 660    }
 661    else if (_table.Length > 2 && _count < _table.Length * _minLoadFactor)
 662    {
 663      int tableSize = (int)(_count * (1 / _maxLoadFactor));
 664      while (!IsPrime(tableSize))
 665      {
 666        tableSize++;
 667      }
 668      Resize(tableSize);
 669    }
 670    return (true, null);
 671  }
 672
 673  /// <summary>Tries to remove a keyed value without shrinking the hash table.</summary>
 674  /// <param name="key">The key of the value to remove.</param>
 675  /// <returns>True if the removal was successful for false if not.</returns>
 676  public (bool Success, Exception? Exception) TryRemoveWithoutTrim(TKey key)
 677  {
 678    int location = GetLocation(key);
 679    for (Node? node = _table[location], previous = null; node is not null; previous = node, node = node.Next)
 680    {
 681      if (_equate.Invoke(node.Key, key))
 682      {
 683        if (previous is null)
 684        {
 685          _table[location] = node.Next;
 686        }
 687        else
 688        {
 689          previous.Next = node.Next;
 690        }
 691        _count--;
 692        return (true, null);
 693      }
 694    }
 695    return (false, new ArgumentException("Attempting to remove a key that is no in a map.", nameof(key)));
 696  }
 697
 698  internal void Resize(int tableSize)
 699  {
 700    if (tableSize == _table.Length)
 701    {
 702      return;
 703    }
 704
 705    Node?[] temp = _table;
 706    _table = new Node[tableSize];
 707
 708    for (int i = 0; i < temp.Length; i++)
 709    {
 710      for (Node? node = temp[i]; node is not null; node = temp[i])
 711      {
 712        temp[i] = node.Next;
 713
 714        int hashCode = _hash.Invoke(node.Key);
 715        int location = (hashCode & int.MaxValue) % _table.Length;
 716
 717        node.Next = _table[location];
 718        _table[location] = node;
 719      }
 720    }
 721  }
 722
 723  /// <summary>
 724  /// Trims the table to an appropriate size based on the current count.<br/>
 725  /// Runtime: O(n), Ω(1)
 726  /// </summary>
 727  public void Trim()
 728  {
 729    int tableSize = _count;
 730    while (!IsPrime(tableSize))
 731    {
 732      tableSize++;
 733    }
 734    Resize(tableSize);
 735  }
 736
 737  /// <inheritdoc/>
 738  public MapHashLinked<T, TKey, TEquate, THash> Clone() => new(this);
 739
 740  /// <inheritdoc/>
 741  public bool Contains(TKey key)
 742  {
 743    int location = GetLocation(key);
 744    for (Node? node = _table[location]; node is not null; node = node.Next)
 745    {
 746      if (_equate.Invoke(node.Key, key))
 747      {
 748        return true;
 749      }
 750    }
 751    return false;
 752  }
 753
 754  /// <inheritdoc/>
 755  public void Clear()
 756  {
 757    _table = new Node[2];
 758    _count = 0;
 759  }
 760
 761  /// <inheritdoc/>
 762  public StepStatus StepperBreak<TStep>(TStep step = default)
 763    where TStep : struct, IFunc<T, StepStatus>
 764  {
 765    for (int i = 0; i < _table.Length; i++)
 766    {
 767      for (Node? node = _table[i]; node is not null; node = node.Next)
 768      {
 769        if (step.Invoke(node.Value) is Break)
 770        {
 771          return Break;
 772        }
 773      }
 774    }
 775    return Continue;
 776  }
 777
 778  /// <inheritdoc/>
 779  public StepStatus KeysBreak<TStep>(TStep step = default)
 780    where TStep : struct, IFunc<TKey, StepStatus>
 781  {
 782    for (int i = 0; i < _table.Length; i++)
 783    {
 784      for (Node? node = _table[i]; node is not null; node = node.Next)
 785      {
 786        if (step.Invoke(node.Key) is Break)
 787        {
 788          return Break;
 789        }
 790      }
 791    }
 792    return Continue;
 793  }
 794
 795  /// <inheritdoc/>
 796  public System.Collections.Generic.IEnumerable<TKey> GetKeys()
 797  {
 798    for (int i = 0; i < _table.Length; i++)
 799    {
 800      for (Node? node = _table[i]; node is not null; node = node.Next)
 801      {
 802        yield return node.Key;
 803      }
 804    }
 805  }
 806
 807  /// <inheritdoc/>
 808  public StepStatus PairsBreak<TStep>(TStep step = default)
 809    where TStep : struct, IFunc<(T Value, TKey Key), StepStatus>
 810  {
 811    for (int i = 0; i < _table.Length; i++)
 812    {
 813      for (Node? node = _table[i]; node is not null; node = node.Next)
 814      {
 815        if (step.Invoke((node.Value, node.Key)) is Break)
 816        {
 817          return Break;
 818        }
 819      }
 820    }
 821    return Continue;
 822  }
 823
 824  /// <inheritdoc/>
 825  public System.Collections.Generic.IEnumerable<(T Value, TKey Key)> GetPairs()
 826  {
 827    for (int i = 0; i < _table.Length; i++)
 828    {
 829      for (Node? node = _table[i]; node is not null; node = node.Next)
 830      {
 831        yield return (node.Value, node.Key);
 832      }
 833    }
 834  }
 835
 836  System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator() => GetEnumerator();
 837
 838  /// <inheritdoc/>
 839  public System.Collections.Generic.IEnumerator<T> GetEnumerator()
 840  {
 841    for (int i = 0; i < _table.Length; i++)
 842    {
 843      for (Node? node = _table[i]; node is not null; node = node.Next)
 844      {
 845        yield return node.Value;
 846      }
 847    }
 848  }
 849
 850  /// <inheritdoc/>
 851  public T[] ToArray()
 852  {
 853    T[] array = new T[_count];
 854    for (int i = 0, index = 0; i < _table.Length; i++)
 855    {
 856      for (Node? node = _table[i]; node is not null; node = node.Next)
 857      {
 858        array[index++] = node.Value;
 859      }
 860    }
 861    return array;
 862  }
 863
 864  /// <inheritdoc/>
 865  public TKey[] KeysToArray()
 866  {
 867    TKey[] array = new TKey[_count];
 868    for (int i = 0, index = 0; i < _table.Length; i++)
 869    {
 870      for (Node? node = _table[i]; node is not null; node = node.Next)
 871      {
 872        array[index++] = node.Key;
 873      }
 874    }
 875    return array;
 876  }
 877
 878  /// <inheritdoc/>
 879  public (T Value, TKey Key)[] PairsToArray()
 880  {
 881    (T Value, TKey Key)[] array = new (T Value, TKey Key)[_count];
 882    for (int i = 0, index = 0; i < _table.Length; i++)
 883    {
 884      for (Node? node = _table[i]; node is not null; node = node.Next)
 885      {
 886        array[index++] = (node.Value, node.Key);
 887      }
 888    }
 889    return array;
 890  }
 891
 892  #endregion
 893}
Generated by: ReportGenerator 4.8.11.0
08/14/2022 - 14:40:42
GitHub | www.palmmedia.de

Methods/Properties

Update(...)
AddOrUpdate(...)
Update(...)
AddOrUpdate(...)
TryUpdate(...)
TryAddOrUpdate(...)
Add(...)
Set(...)
Get(...)
Keys(...)
Keys(...)
KeysBreak(...)
Pairs(...)
Pairs(...)
PairsBreak(...)