< Summary

Class:Towel.DataStructures.Trie
Assembly:Towel
File(s):File 1: /home/runner/work/Towel/Towel/Sources/Towel/DataStructures/Trie.cs
Covered lines:0
Uncovered lines:19
Coverable lines:19
Total lines:659
Line coverage:0% (0 of 19)
Covered branches:0
Total branches:12
Branch coverage:0% (0 of 12)

Metrics

MethodBranch coverage Cyclomatic complexity Line coverage
File 1: Add(...)0%40%
File 1: Get(...)0%40%
File 1: Remove(...)0%40%

File(s)

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

#LineLine coverage
 1namespace Towel.DataStructures;
 2
 3/// <summary>Extension methods for <see cref="ITrie{T}"/> and <see cref="ITrie{T, D}"/>.</summary>
 4public static class Trie
 5{
 6  #region Extensions Methods
 7
 8  /// <summary>Adds a value.</summary>
 9  /// <typeparam name="T">The type of value.</typeparam>
 10  /// <typeparam name="TData">The type of the data.</typeparam>
 11  /// <param name="trie">The trie to add the value to.</param>
 12  /// <param name="value">The value to be added.</param>
 13  /// <param name="stepper">The keys of the relative value.</param>
 14  public static void Add<T, TData>(this ITrie<T, TData> trie, TData value, Action<Action<T>> stepper)
 015  {
 016    var (success, exception) = trie.TryAdd(value, stepper);
 017    if (!success)
 018    {
 019      throw exception ?? new ArgumentException($"{nameof(Add)} failed but the {nameof(exception)} is null");
 20    }
 021  }
 22
 23  /// <summary>Gets a value.</summary>
 24  /// <typeparam name="T">The type of value.</typeparam>
 25  /// <typeparam name="TData">The type of the data.</typeparam>
 26  /// <param name="trie">The trie to get the value from.</param>
 27  /// <param name="stepper">The keys of the relative value.</param>
 28  /// <returns>The value.</returns>
 29  public static TData Get<T, TData>(this ITrie<T, TData> trie, Action<Action<T>> stepper)
 030  {
 031    var (success, value, exception) = trie.TryGet(stepper);
 032    if (!success)
 033    {
 034      throw exception ?? new ArgumentException($"{nameof(Get)} failed but the {nameof(exception)} is null");
 35    }
 036    return value!;
 037  }
 38
 39  /// <summary>Removes a value.</summary>
 40  /// <typeparam name="T">The type of value.</typeparam>
 41  /// <typeparam name="TData">The type of the data.</typeparam>
 42  /// <param name="trie">The trie to remove the value from.</param>
 43  /// <param name="stepper">The keys to store the value relative to.</param>
 44  public static void Remove<T, TData>(this ITrie<T, TData> trie, Action<Action<T>> stepper)
 045  {
 046    var (success, exception) = trie.TryRemove(stepper);
 047    if (!success)
 048    {
 049      throw exception ?? new ArgumentException($"{nameof(Remove)} failed but the {nameof(exception)} is null");
 50    }
 051  }
 52
 53  #endregion
 54}
 55
 56/// <summary>A trie data structure that allows partial value sharing to reduce redundant memory.</summary>
 57/// <typeparam name="T">The type of values in the trie.</typeparam>
 58public interface ITrie<T> : IDataStructure<Action<Action<T>>>,
 59  DataStructure.ICountable,
 60  DataStructure.IClearable,
 61  DataStructure.IAddable<Action<Action<T>>>,
 62  DataStructure.IRemovable<Action<Action<T>>>,
 63  DataStructure.IAuditable<Action<Action<T>>>
 64{
 65
 66}
 67
 68/// <summary>Static helpers.</summary>
 69public static class TrieLinkedHashLinked
 70{
 71  #region Extension Methods
 72
 73  /// <summary>Constructs a new <see cref="TrieLinkedHashLinked{T, TEquate, THash}"/>.</summary>
 74  /// <typeparam name="T">The type of values stored in this data structure.</typeparam>
 75  /// <param name="equate">The function for comparing <typeparamref name="T"/> values for equality.</param>
 76  /// <param name="hash">The function for hashing <typeparamref name="T"/> values.</param>
 77  /// <returns>The new constructed <see cref="TrieLinkedHashLinked{T, TEquate, THash}"/>.</returns>
 78  public static TrieLinkedHashLinked<T, SFunc<T, T, bool>, SFunc<T, int>> New<T>(
 79    Func<T, T, bool>? equate = null,
 80    Func<T, int>? hash = null) =>
 81    new(equate ?? Equate, hash ?? Hash);
 82
 83  /// <summary>Constructs a new <see cref="TrieLinkedHashLinked{T, D, TEquate, THash}"/>.</summary>
 84  /// <typeparam name="T">The type of values stored in this data structure.</typeparam>
 85  /// <typeparam name="TData">The additional data type to store with each leaf.</typeparam>
 86  /// <param name="equate">The function for comparing <typeparamref name="T"/> values for equality.</param>
 87  /// <param name="hash">The function for hashing <typeparamref name="T"/> values.</param>
 88  /// <returns>The new constructed <see cref="TrieLinkedHashLinked{T, D, TEquate, THash}"/>.</returns>
 89  public static TrieLinkedHashLinked<T, TData, SFunc<T, T, bool>, SFunc<T, int>> New<T, TData>(
 90    Func<T, T, bool>? equate = null,
 91    Func<T, int>? hash = null) =>
 92    new(equate ?? Equate, hash ?? Hash);
 93
 94  #endregion
 95}
 96
 97/// <summary>A trie data structure that allows partial value sharing to reduce redundant memory.</summary>
 98/// <typeparam name="T">The type of values in the trie.</typeparam>
 99/// <typeparam name="TEquate">The type of function for quality checking <typeparamref name="T"/> values.</typeparam>
 100/// <typeparam name="THash">The type of function for hashing <typeparamref name="T"/> values.</typeparam>
 101public class TrieLinkedHashLinked<T, TEquate, THash> : ITrie<T>,
 102  ICloneable<TrieLinkedHashLinked<T, TEquate, THash>>,
 103  DataStructure.IEquating<T, TEquate>,
 104  DataStructure.IHashing<T, THash>
 105  where TEquate : struct, IFunc<T, T, bool>
 106  where THash : struct, IFunc<T, int>
 107{
 108  internal MapHashLinked<Node, T, TEquate, THash> _map;
 109  internal int _count;
 110
 111  #region Nested Types
 112
 113  internal class Node
 114  {
 115    internal MapHashLinked<Node, T, TEquate, THash> Map;
 116    internal bool IsLeaf;
 117    internal int Count;
 118
 119    public Node(MapHashLinked<Node, T, TEquate, THash> map) => Map = map;
 120  }
 121
 122  #endregion
 123
 124  #region Constructors
 125
 126  /// <summary>Constructs a new trie that uses linked hash tables of linked lists.</summary>
 127  /// <param name="equate">The equality delegate for the keys.</param>
 128  /// <param name="hash">The hashing function for the keys.</param>
 129  public TrieLinkedHashLinked(TEquate equate = default, THash hash = default)
 130  {
 131    _count = 0;
 132    _map = new(equate, hash);
 133  }
 134
 135  /// <summary>This constructor is for cloning purposes.</summary>
 136  /// <param name="trie">The trie to clone.</param>
 137  public TrieLinkedHashLinked(TrieLinkedHashLinked<T, TEquate, THash> trie)
 138  {
 139    _count = trie._count;
 140    _map = trie._map.Clone();
 141  }
 142
 143  #endregion
 144
 145  #region Properties
 146
 147  /// <summary>The current count of the trie.</summary>
 148  public int Count => _count;
 149  /// <summary>The equality function of the keys.</summary>
 150  public TEquate Equate => _map.Equate;
 151  /// <summary>The hash fucntion for the keys.</summary>
 152  public THash Hash => _map.Hash;
 153
 154  #endregion
 155
 156  #region Methods
 157
 158  /// <inheritdoc/>
 159  public (bool Success, Exception? Exception) TryAdd(Action<Action<T>> stepper)
 160  {
 161    if (stepper is null)
 162    {
 163      return (false, new ArgumentNullException(nameof(stepper)));
 164    }
 165    IStack<Node> stack = new StackLinked<Node>();
 166    Node? node = null;
 167    stepper(key =>
 168    {
 169      var map = node is null ? _map : node.Map;
 170      if (map.Contains(key))
 171      {
 172        node = map[key];
 173      }
 174      else
 175      {
 176        Node temp = new(map: new(Equate, Hash));
 177        map[key] = temp;
 178        node = temp;
 179      }
 180      stack.Push(node);
 181    });
 182    if (node is null)
 183    {
 184      return (false, new ArgumentException("Stepper was empty.", nameof(stepper)));
 185    }
 186    else if (node.IsLeaf)
 187    {
 188      return (false, new ArgumentException("Attempted to add an already existing item.", nameof(stepper)));
 189    }
 190    else
 191    {
 192      node.IsLeaf = true;
 193      stack.Stepper(n => n.Count++);
 194      _count++;
 195      return (true, null);
 196    }
 197  }
 198
 199  /// <inheritdoc/>
 200  public (bool Success, Exception? Exception) TryRemove(Action<Action<T>> stepper)
 201  {
 202    if (stepper is null)
 203    {
 204      return (false, new ArgumentNullException(nameof(stepper)));
 205    }
 206    StackLinked<(T, MapHashLinked<Node, T, TEquate, THash>, Node)> stack = new();
 207    T finalKey;
 208    MapHashLinked<Node, T, TEquate, THash>? finalMap = null;
 209    Node? node = null;
 210    Exception? exception = null;
 211    stepper(key =>
 212    {
 213      finalKey = key;
 214      finalMap = node is null ? _map : node.Map;
 215      if (finalMap.Contains(key))
 216      {
 217        node = finalMap[key];
 218      }
 219      else
 220      {
 221        exception ??= new ArgumentException("Attempted to remove a non-existing item.", nameof(stepper));
 222      }
 223      stack.Push((finalKey, finalMap, node!));
 224    });
 225    if (exception is not null)
 226    {
 227      return (false, exception);
 228    }
 229    else if (node is null)
 230    {
 231      return (false, new ArgumentException("Stepper was empty.", nameof(stepper)));
 232    }
 233    else if (!node.IsLeaf)
 234    {
 235      return (false, new ArgumentException("Attempted to remove a non-existing item.", nameof(stepper)));
 236    }
 237    else
 238    {
 239      bool remove = true;
 240      while (stack.Count > 0)
 241      {
 242        var (k, m, n) = stack.Pop();
 243        n.Count--;
 244        if (remove && n.Count is 0)
 245        {
 246          m.Remove(k);
 247        }
 248        else
 249        {
 250          remove = false;
 251        }
 252      }
 253      _count--;
 254      return (true, null);
 255    }
 256  }
 257
 258  /// <inheritdoc/>
 259  public bool Contains(Action<Action<T>> stepper)
 260  {
 261    if (stepper is null) throw new ArgumentNullException(nameof(stepper));
 262    Node? node = null;
 263    bool contains = true;
 264    stepper(key =>
 265    {
 266      if (!contains)
 267      {
 268        return;
 269      }
 270      else
 271      {
 272        var map = node is null ? _map : node.Map;
 273        if (map.Contains(key))
 274        {
 275          node = map[key];
 276        }
 277        else
 278        {
 279          contains = false;
 280        }
 281      }
 282    });
 283    if (node is null)
 284    {
 285      throw new ArgumentException("Stepper was empty.", nameof(stepper));
 286    }
 287    return node.IsLeaf;
 288  }
 289
 290  /// <inheritdoc/>
 291  public void Clear()
 292  {
 293    _count = 0;
 294    _map.Clear();
 295  }
 296
 297  /// <inheritdoc/>
 298  public StepStatus StepperBreak<TStep>(TStep step = default)
 299    where TStep : struct, IFunc<Action<Action<T>>, StepStatus>
 300  {
 301    StepStatus Stepper(Node node, Action<Action<T>> stepper)
 302    {
 303      if (node.IsLeaf)
 304      {
 305        if (step.Invoke(stepper) is Break)
 306        {
 307          return Break;
 308        }
 309      }
 310      return node.Map.PairsBreak(pair =>
 311        Stepper(pair.Value, x => { stepper(x); x(pair.Key); }) is Break
 312          ? Break
 313          : Continue);
 314    }
 315    return _map.PairsBreak(pair => Stepper(pair.Value, x => x(pair.Key)));
 316  }
 317
 318  System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator() => GetEnumerator();
 319
 320  /// <inheritdoc/>
 321  public System.Collections.Generic.IEnumerator<Action<Action<T>>> GetEnumerator()
 322  {
 323#warning TODO: optimize
 324    IList<Action<Action<T>>> list = new ListLinked<Action<Action<T>>>();
 325    this.Stepper(x => list.Add(x));
 326    return list.GetEnumerator();
 327  }
 328
 329  /// <inheritdoc/>
 330  public TrieLinkedHashLinked<T, TEquate, THash> Clone() => new(this);
 331
 332  /// <inheritdoc/>
 333  public Action<Action<T>>[] ToArray()
 334  {
 335#warning TODO: optimize
 336    Action<Action<T>>[] array = new Action<Action<T>>[_count];
 337    int i = 0;
 338    this.Stepper(x => array[i++] = x);
 339    return array;
 340  }
 341
 342  #endregion
 343}
 344
 345/// <summary>A trie data structure that allows partial value sharing to reduce redundant memory.</summary>
 346/// <typeparam name="T">The type of values in the trie.</typeparam>
 347/// <typeparam name="TData">The additional data type to store with each leaf.</typeparam>
 348public interface ITrie<T, TData> : IDataStructure<(Action<Action<T>>, TData)>,
 349  DataStructure.ICountable,
 350  DataStructure.IClearable,
 351  DataStructure.IAuditable<Action<Action<T>>>
 352{
 353  #region Methods
 354
 355  /// <summary>Tries to add a value to the trie.</summary>
 356  /// <param name="value">The value to add.</param>
 357  /// <param name="stepper">The relative keys of the value.</param>
 358  /// <returns>True if the value was added or false if not.</returns>
 359  (bool Success, Exception? Exception) TryAdd(TData value, Action<Action<T>> stepper);
 360
 361  /// <summary>Tries to get a value.</summary>
 362  /// <param name="stepper">The relative keys of the value.</param>
 363  /// <returns>True if the remove was successful or false if not.</returns>
 364  (bool Success, TData? Value, Exception? Exception) TryGet(Action<Action<T>> stepper);
 365
 366  /// <summary>Tries to remove a value.</summary>
 367  /// <param name="stepper">The relative keys of the value.</param>
 368  /// <returns>True if the remove was successful or false if not.</returns>
 369  (bool Success, Exception? Exception) TryRemove(Action<Action<T>> stepper);
 370
 371  #endregion
 372}
 373
 374/// <summary>A trie data structure that allows partial value sharing to reduce redundant memory.</summary>
 375/// <typeparam name="T">The type of values in the trie.</typeparam>
 376/// <typeparam name="TData">The additional data type to store with each leaf.</typeparam>
 377/// <typeparam name="TEquate">The type of function for quality checking <typeparamref name="T"/> values.</typeparam>
 378/// <typeparam name="THash">The type of function for hashing <typeparamref name="T"/> values.</typeparam>
 379public class TrieLinkedHashLinked<T, TData, TEquate, THash> : ITrie<T, TData>,
 380  ICloneable<TrieLinkedHashLinked<T, TData, TEquate, THash>>,
 381  DataStructure.ICountable,
 382  DataStructure.IClearable,
 383  DataStructure.IEquating<T, TEquate>,
 384  DataStructure.IHashing<T, THash>
 385  where TEquate : struct, IFunc<T, T, bool>
 386  where THash : struct, IFunc<T, int>
 387{
 388  internal MapHashLinked<Node, T, TEquate, THash> _map;
 389  internal int _count;
 390
 391  #region Nested Types
 392
 393  internal class Node
 394  {
 395    internal MapHashLinked<Node, T, TEquate, THash> Map;
 396    internal TData? Value;
 397    internal bool HasValue;
 398    internal int Count;
 399
 400    public Node(MapHashLinked<Node, T, TEquate, THash> map) => Map = map;
 401  }
 402
 403  #endregion
 404
 405  #region Constructors
 406
 407  /// <summary>Constructs a new trie that uses linked hash tables of linked lists.</summary>
 408  /// <param name="equate">The equality delegate for the keys.</param>
 409  /// <param name="hash">The hashing function for the keys.</param>
 410  public TrieLinkedHashLinked(TEquate equate = default, THash hash = default)
 411  {
 412    _count = 0;
 413    _map = new(equate, hash);
 414  }
 415
 416  /// <summary>This constructor is for cloning purposes.</summary>
 417  /// <param name="trie">The trie to clone.</param>
 418  public TrieLinkedHashLinked(TrieLinkedHashLinked<T, TData, TEquate, THash> trie)
 419  {
 420    _count = trie._count;
 421    _map = trie._map.Clone();
 422  }
 423
 424  #endregion
 425
 426  #region Properties
 427
 428  /// <summary>The current count of the trie.</summary>
 429  public int Count => _count;
 430  /// <summary>The equality function of the keys.</summary>
 431  public TEquate Equate => _map.Equate;
 432  /// <summary>The hash fucntion for the keys.</summary>
 433  public THash Hash => _map.Hash;
 434
 435  #endregion
 436
 437  #region Methods
 438
 439  /// <inheritdoc/>
 440  public (bool Success, Exception? Exception) TryAdd(TData value, Action<Action<T>> stepper)
 441  {
 442    if (stepper is null)
 443    {
 444      return (false, new ArgumentNullException(nameof(stepper)));
 445    }
 446    StackLinked<Node> stack = new();
 447    Node? node = null;
 448    stepper(key =>
 449    {
 450      var map = node is null ? _map : node.Map;
 451      if (map.Contains(key))
 452      {
 453        node = map[key];
 454      }
 455      else
 456      {
 457        Node temp = new(map: new(Equate, Hash));
 458        map[key] = temp;
 459        node = temp;
 460      }
 461      stack.Push(node);
 462    });
 463    if (node is null)
 464    {
 465      return (false, new ArgumentException("Stepper was empty.", nameof(stepper)));
 466    }
 467    else if (node.HasValue)
 468    {
 469      return (false, new ArgumentException("Attempted to add an already existing item.", nameof(stepper)));
 470    }
 471    else
 472    {
 473      node.Value = value;
 474      node.HasValue = true;
 475      stack.Stepper(n => n.Count++);
 476      _count++;
 477      return (true, null);
 478    }
 479  }
 480
 481  /// <inheritdoc/>
 482  public (bool Success, TData? Value, Exception? Exception) TryGet(Action<Action<T>> stepper)
 483  {
 484    if (stepper is null)
 485    {
 486      return (false, default, new ArgumentNullException(nameof(stepper)));
 487    }
 488    Node? node = null;
 489    stepper(key =>
 490    {
 491      var map = node is null ? _map : node.Map;
 492      if (map.Contains(key))
 493      {
 494        node = map[key];
 495      }
 496      else
 497      {
 498        Node temp = new(map: new(Equate, Hash));
 499        map[key] = temp;
 500        node = temp;
 501      }
 502    });
 503    if (node is null)
 504    {
 505      return (false, default, new ArgumentException("Stepper was empty.", nameof(stepper)));
 506    }
 507    else if (!node.HasValue)
 508    {
 509      return (false, default, new ArgumentException("Attempted to get a non-existing item.", nameof(stepper)));
 510    }
 511    else
 512    {
 513      return (true, node.Value, null);
 514    }
 515  }
 516
 517  /// <inheritdoc/>
 518  public (bool Success, Exception? Exception) TryRemove(Action<Action<T>> stepper)
 519  {
 520    if (stepper is null)
 521    {
 522      return (false, new ArgumentNullException(nameof(stepper)));
 523    }
 524    StackLinked<(T, MapHashLinked<Node, T, TEquate, THash>, Node)> stack = new();
 525    T finalKey;
 526    MapHashLinked<Node, T, TEquate, THash> finalMap;
 527    Node? node = null;
 528    Exception? capturedException = null;
 529    stepper(key =>
 530    {
 531      finalKey = key;
 532      finalMap = node is null ? _map : node.Map;
 533      if (finalMap.Contains(key))
 534      {
 535        node = finalMap[key];
 536      }
 537      else
 538      {
 539        capturedException ??= new ArgumentException("Attempted to remove a non-existing item.", nameof(stepper));
 540      }
 541      stack.Push((finalKey, finalMap, node!));
 542    });
 543    if (capturedException is not null)
 544    {
 545      return (false, capturedException);
 546    }
 547    else if (node is null)
 548    {
 549      return (false, new ArgumentException("Stepper was empty.", nameof(stepper)));
 550    }
 551    else if (!node.HasValue)
 552    {
 553      return (false, new ArgumentException("Attempted to remove a non-existing item.", nameof(stepper)));
 554    }
 555    else
 556    {
 557      bool remove = true;
 558      while (stack.Count > 0)
 559      {
 560        var (k, m, n) = stack.Pop();
 561        n.Count--;
 562        if (remove && n.Count is 0)
 563        {
 564          m.Remove(k);
 565        }
 566        else
 567        {
 568          remove = false;
 569        }
 570      }
 571      _count--;
 572      return (true, null);
 573    }
 574  }
 575
 576  /// <inheritdoc/>
 577  public bool Contains(Action<Action<T>> stepper)
 578  {
 579    if (stepper is null) throw new ArgumentNullException(nameof(stepper));
 580    Node? node = null;
 581    bool contains = true;
 582    stepper(key =>
 583    {
 584      if (!contains)
 585      {
 586        return;
 587      }
 588      else
 589      {
 590        var map = node is null ? _map : node.Map;
 591        if (map.Contains(key))
 592        {
 593          node = map[key];
 594        }
 595        else
 596        {
 597          contains = false;
 598        }
 599      }
 600    });
 601    if (node is null)
 602    {
 603      throw new ArgumentException("Stepper was empty.", nameof(stepper));
 604    }
 605    return node.HasValue;
 606  }
 607
 608  /// <inheritdoc/>
 609  public void Clear()
 610  {
 611    _count = 0;
 612    _map.Clear();
 613  }
 614
 615  /// <inheritdoc/>
 616  public StepStatus StepperBreak<TStep>(TStep step = default)
 617    where TStep : struct, IFunc<(Action<Action<T>>, TData), StepStatus>
 618  {
 619    StepStatus Stepper(Node node, Action<Action<T>> stepper)
 620    {
 621      if (node.HasValue)
 622      {
 623        if (step.Invoke((stepper, node.Value!)) is Break)
 624        {
 625          return Break;
 626        }
 627      }
 628      return node.Map.PairsBreak(pair => Stepper(pair.Value, x => { stepper(x); x(pair.Key); }));
 629    }
 630    return _map.PairsBreak(pair => Stepper(pair.Value, x => x(pair.Key)));
 631  }
 632
 633  System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator() =>
 634    GetEnumerator();
 635
 636  /// <inheritdoc/>
 637  public System.Collections.Generic.IEnumerator<(Action<Action<T>>, TData)> GetEnumerator()
 638  {
 639#warning TODO: optimize
 640    IList<(Action<Action<T>>, TData)> list = new ListLinked<(Action<Action<T>>, TData)>();
 641    this.Stepper(x => list.Add(x));
 642    return list.GetEnumerator();
 643  }
 644
 645  /// <inheritdoc/>
 646  public TrieLinkedHashLinked<T, TData, TEquate, THash> Clone() => new(this);
 647
 648  /// <inheritdoc/>
 649  public (Action<Action<T>>, TData)[] ToArray()
 650  {
 651#warning TODO: optimize
 652    (Action<Action<T>>, TData)[] array = new (Action<Action<T>>, TData)[_count];
 653    int i = 0;
 654    this.Stepper(x => array[i++] = x);
 655    return array;
 656  }
 657
 658  #endregion
 659}
Generated by: ReportGenerator 4.8.11.0
08/14/2022 - 14:40:44
GitHub | www.palmmedia.de

Methods/Properties

Add(...)
Get(...)
Remove(...)