< Summary

Class:Towel.DataStructures.RedBlackTreeLinked
Assembly:Towel
File(s):File 1: /home/runner/work/Towel/Towel/Sources/Towel/DataStructures/RedBlackTree.cs
Covered lines:1
Uncovered lines:0
Coverable lines:1
Total lines:677
Line coverage:100% (1 of 1)
Covered branches:2
Total branches:2
Branch coverage:100% (2 of 2)

Metrics

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

File(s)

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

#LineLine coverage
 1namespace Towel.DataStructures;
 2
 3/// <summary>A self sorting binary tree using the red-black tree algorithms.</summary>
 4/// <typeparam name="T">The type of values stored in this data structure.</typeparam>
 5public interface IRedBlackTree<T> : ISortedBinaryTree<T>
 6{
 7
 8}
 9
 10/// <summary>A self sorting binary tree using the red-black tree algorithms.</summary>
 11/// <typeparam name="T">The type of values stored in this data structure.</typeparam>
 12/// <typeparam name="TCompare">The type that is comparing <typeparamref name="T"/> values.</typeparam>
 13public interface IRedBlackTree<T, TCompare> : IRedBlackTree<T>, ISortedBinaryTree<T, TCompare>
 14  where TCompare : struct, IFunc<T, T, CompareResult>
 15{
 16
 17}
 18
 19/// <summary>Static helpers for <see cref="IRedBlackTree{T}"/> and <see cref="IRedBlackTree{T, TCompare}"/>.</summary>
 20public static class RedBlackTree
 21{
 22
 23}
 24
 25/// <summary>Static helpers for <see cref="RedBlackTreeLinked{T, TCompare}"/>.</summary>
 26public static class RedBlackTreeLinked
 27{
 28  #region Extension Methods
 29
 30  /// <summary>Constructs a new <see cref="RedBlackTreeLinked{T, TCompare}"/>.</summary>
 31  /// <typeparam name="T">The type of values stored in this data structure.</typeparam>
 32  /// <param name="compare">The function for comparing <typeparamref name="T"/> values.</param>
 33  /// <returns>The new constructed <see cref="RedBlackTreeLinked{T, TCompare}"/>.</returns>
 34  public static RedBlackTreeLinked<T, SFunc<T, T, CompareResult>> New<T>(
 35    Func<T, T, CompareResult>? compare = null) =>
 1636    new(compare ?? Compare);
 37
 38  #endregion
 39}
 40
 41/// <summary>A self sorting binary tree using the red-black tree algorithms.</summary>
 42/// <typeparam name="T">The type of values stored in this data structure.</typeparam>
 43/// <typeparam name="TCompare">The type that is comparing <typeparamref name="T"/> values.</typeparam>
 44public class RedBlackTreeLinked<T, TCompare> : IRedBlackTree<T, TCompare>, ICloneable<RedBlackTreeLinked<T, TCompare>>
 45  where TCompare : struct, IFunc<T, T, CompareResult>
 46{
 47  internal const bool Red = true;
 48  internal const bool Black = false;
 49  internal readonly Node _sentinelNode = new(value: default!, color: Black, leftChild: null!, rightChild: null!);
 50
 51  internal TCompare _compare;
 52  internal int _count;
 53  internal Node _root;
 54
 55  #region Nested Types
 56
 57  internal class Node
 58  {
 59    internal T Value;
 60    internal bool Color;
 61    internal Node? Parent;
 62    internal Node LeftChild;
 63    internal Node RightChild;
 64
 65    public Node(
 66      T value,
 67      Node leftChild,
 68      Node rightChild,
 69      bool color = Red,
 70      Node? parent = null)
 71    {
 72      Value = value;
 73      Color = color;
 74      Parent = parent;
 75      LeftChild = leftChild;
 76      RightChild = rightChild;
 77    }
 78  }
 79
 80  #endregion
 81
 82  #region Constructors
 83
 84  /// <summary>Constructs a new Red Black Tree.</summary>
 85  /// <param name="compare">The comparison method to be used when sorting the values of the tree.</param>
 86  public RedBlackTreeLinked(TCompare compare = default)
 87  {
 88    _root = _sentinelNode;
 89    _compare = compare;
 90  }
 91
 92  /// <summary>Constructor for cloning purposes.</summary>
 93  /// <param name="tree">The tree to be cloned.</param>
 94  internal RedBlackTreeLinked(RedBlackTreeLinked<T, TCompare> tree)
 95  {
 96    Node Clone(Node node, Node? parent)
 97    {
 98      if (node == _sentinelNode)
 99      {
 100        return _sentinelNode;
 101      }
 102      Node clone = new(
 103        value: node.Value,
 104        color: node.Color,
 105        parent: parent,
 106        leftChild: null!,
 107        rightChild: null!);
 108      clone.LeftChild = node.LeftChild == _sentinelNode ? _sentinelNode : Clone(node.LeftChild, clone);
 109      clone.RightChild = node.RightChild == _sentinelNode ? _sentinelNode : Clone(node.RightChild, clone);
 110      return clone;
 111    }
 112    _compare = tree._compare;
 113    _count = tree._count;
 114    _root = Clone(tree._root, null);
 115  }
 116
 117  #endregion
 118
 119  #region Properties
 120
 121  /// <inheritdoc/>
 122  public T CurrentLeast
 123  {
 124    get
 125    {
 126      if (_root == _sentinelNode)
 127      {
 128        throw new InvalidOperationException("Attempting to get the least value from an empty tree.");
 129      }
 130      Node node = _root;
 131      while (node.LeftChild != _sentinelNode)
 132      {
 133        node = node.LeftChild;
 134      }
 135      return node.Value;
 136    }
 137  }
 138
 139  /// <inheritdoc/>
 140  public T CurrentGreatest
 141  {
 142    get
 143    {
 144      if (_root == _sentinelNode)
 145      {
 146        throw new InvalidOperationException("Attempting to get the greatest value from an empty tree.");
 147      }
 148      Node node = _root;
 149      while (node.RightChild != _sentinelNode)
 150      {
 151        node = node.RightChild;
 152      }
 153      return node.Value;
 154    }
 155  }
 156
 157  /// <inheritdoc/>
 158  public int Count => _count;
 159
 160  /// <inheritdoc/>
 161  public TCompare Compare => _compare;
 162
 163  #endregion
 164
 165  #region Methods
 166
 167  /// <inheritdoc/>
 168  public (bool Success, Exception? Exception) TryAdd(T value)
 169  {
 170    Exception? exception = null;
 171    Node addition = new(value: value, leftChild: _sentinelNode, rightChild: _sentinelNode);
 172    Node node = _root;
 173    while (node != _sentinelNode)
 174    {
 175      addition.Parent = node;
 176      CompareResult compareResult = _compare.Invoke(value, node.Value);
 177      switch (compareResult)
 178      {
 179        case Less:    node = node.LeftChild; break;
 180        case Greater: node = node.RightChild; break;
 181        case Equal:
 182          exception = new ArgumentException($"Adding to add a duplicate value to a {nameof(RedBlackTreeLinked<T, TCompar
 183          goto Break;
 184        default:
 185          exception = new ArgumentException($"Invalid {nameof(TCompare)} function; an undefined {nameof(CompareResult)} 
 186          goto Break;
 187      }
 188    }
 189  Break:
 190    if (exception is not null)
 191    {
 192      return (false, exception);
 193    }
 194    if (addition.Parent is not null)
 195    {
 196      CompareResult compareResult = _compare.Invoke(addition.Value, addition.Parent.Value);
 197      switch (compareResult)
 198      {
 199        case Less:    addition.Parent.LeftChild  = addition; break;
 200        case Greater: addition.Parent.RightChild = addition; break;
 201        case Equal:   exception = new CorruptedDataStructureException(); break;
 202        default:
 203          exception = new ArgumentException($"Invalid {nameof(TCompare)} function; an undefined {nameof(CompareResult)} 
 204          break;
 205      }
 206    }
 207    else
 208    {
 209      _root = addition;
 210    }
 211    if (exception is not null)
 212    {
 213      return (false, exception);
 214    }
 215    BalanceAddition(addition);
 216    _count += 1;
 217    return (true, null);
 218  }
 219
 220  /// <inheritdoc/>
 221  public void Clear()
 222  {
 223    _root = _sentinelNode;
 224    _count = 0;
 225  }
 226
 227  /// <inheritdoc/>
 228  public RedBlackTreeLinked<T, TCompare> Clone() => new(this);
 229
 230  /// <inheritdoc/>
 231  public bool Contains(T value) => ContainsSift<SiftFromCompareAndValue<T, TCompare>>(new(value, Compare));
 232
 233  /// <inheritdoc/>
 234  public bool ContainsSift<TSift>(TSift sift = default)
 235    where TSift : struct, IFunc<T, CompareResult>
 236  {
 237    Node node = _root;
 238    while (node != _sentinelNode && node is not null)
 239    {
 240      CompareResult compareResult = sift.Invoke(node.Value);
 241      switch (compareResult)
 242      {
 243        case Less:    node = node.RightChild; break;
 244        case Greater: node = node.LeftChild;  break;
 245        case Equal:   return true;
 246        default: throw new ArgumentException($"Invalid {nameof(TCompare)} function; an undefined {nameof(CompareResult)}
 247      }
 248    }
 249    return false;
 250  }
 251
 252  /// <inheritdoc/>
 253  public (bool Success, T? Value, Exception? Exception) TryGet<TSift>(TSift sift = default)
 254    where TSift : struct, IFunc<T, CompareResult>
 255  {
 256    Node node = _root;
 257    while (node != _sentinelNode)
 258    {
 259      CompareResult compareResult = sift.Invoke(node.Value);
 260      switch (compareResult)
 261      {
 262        case Less:    node = node.LeftChild; break;
 263        case Greater: node = node.RightChild; break;
 264        case Equal: return (true, node.Value, null);
 265        default:
 266          throw compareResult.IsDefined()
 267            ? new TowelBugException($"Unhandled {nameof(CompareResult)} value: {compareResult}.")
 268            : new ArgumentException($"Invalid {nameof(TCompare)} function; an undefined {nameof(CompareResult)} was retu
 269      }
 270    }
 271    return (false, default, new ArgumentException("Attempting to get a non-existing value."));
 272  }
 273
 274  /// <inheritdoc/>
 275  public (bool Success, Exception? Exception) TryRemove(T value) => TryRemoveSift<SiftFromCompareAndValue<T, TCompare>>(
 276
 277  /// <inheritdoc/>
 278  public (bool Success, Exception? Exception) TryRemoveSift<TSift>(TSift sift = default)
 279    where TSift : struct, IFunc<T, CompareResult>
 280  {
 281    Node node;
 282    node = _root;
 283    while (node != _sentinelNode)
 284    {
 285      CompareResult compareResult = sift.Invoke(node.Value);
 286      switch (compareResult)
 287      {
 288        case Less:    node = node.RightChild; break;
 289        case Greater: node = node.LeftChild; break;
 290        case Equal:
 291          if (node == _sentinelNode)
 292          {
 293            return (false, new ArgumentException("Attempting to remove a non-existing entry."));
 294          }
 295          Remove(node);
 296          _count -= 1;
 297          return (true, null);
 298        default:
 299          return (false, new ArgumentException($"Invalid {nameof(TCompare)} function; an undefined {nameof(CompareResult
 300      }
 301    }
 302    return (false, new ArgumentException("Attempting to remove a non-existing entry."));
 303  }
 304
 305  internal void Remove(Node removal)
 306  {
 307    Node x;
 308    Node temp;
 309    if (removal.LeftChild == _sentinelNode || removal.RightChild == _sentinelNode)
 310    {
 311      temp = removal;
 312    }
 313    else
 314    {
 315      temp = removal.RightChild;
 316      while (temp.LeftChild != _sentinelNode)
 317      {
 318        temp = temp.LeftChild;
 319      }
 320    }
 321    if (temp.LeftChild != _sentinelNode)
 322    {
 323      x = temp.LeftChild;
 324    }
 325    else
 326    {
 327      x = temp.RightChild;
 328    }
 329    x.Parent = temp.Parent;
 330    if (temp.Parent is not null)
 331    {
 332      if (temp == temp.Parent.LeftChild)
 333      {
 334        temp.Parent.LeftChild = x;
 335      }
 336      else
 337      {
 338        temp.Parent.RightChild = x;
 339      }
 340    }
 341    else
 342    {
 343      _root = x;
 344    }
 345    if (temp != removal)
 346    {
 347      removal.Value = temp.Value;
 348    }
 349    if (temp.Color == Black)
 350    {
 351      BalanceRemoval(x);
 352    }
 353  }
 354
 355  /// <inheritdoc/>
 356  public StepStatus StepperBreak<TStep>(TStep step = default)
 357    where TStep : struct, IFunc<T, StepStatus>
 358  {
 359    StepStatus Stepper(Node node)
 360    {
 361      if (node != _sentinelNode)
 362      {
 363        if (Stepper(node.LeftChild) is Break ||
 364          step.Invoke(node.Value) is Break ||
 365          Stepper(node.RightChild) is Break)
 366          return Break;
 367      }
 368      return Continue;
 369    }
 370    return Stepper(_root);
 371  }
 372
 373  /// <inheritdoc/>
 374  public virtual StepStatus StepperBreak<TStep>(T minimum, T maximum, TStep step = default)
 375    where TStep : struct, IFunc<T, StepStatus>
 376  {
 377    StepStatus Stepper(Node node)
 378    {
 379      if (node != _sentinelNode)
 380      {
 381        if (_compare.Invoke(node.Value, minimum) is Less)
 382        {
 383          return Stepper(node.RightChild);
 384        }
 385        else if (_compare.Invoke(node.Value, maximum) is Greater)
 386        {
 387          return Stepper(node.LeftChild);
 388        }
 389        else
 390        {
 391          if (Stepper(node.LeftChild) is Break ||
 392            step.Invoke(node.Value) is Break ||
 393            Stepper(node.RightChild) is Break)
 394            return Break;
 395        }
 396      }
 397      return Continue;
 398    }
 399    if (_compare.Invoke(minimum, maximum) is Greater)
 400    {
 401      throw new InvalidOperationException("!(" + nameof(minimum) + " <= " + nameof(maximum) + ")");
 402    }
 403    return Stepper(_root);
 404  }
 405
 406  /// <inheritdoc/>
 407  public StepStatus StepperReverseBreak<TStep>(TStep step = default)
 408    where TStep : struct, IFunc<T, StepStatus>
 409  {
 410    StepStatus StepperReverse(Node node)
 411    {
 412      if (node != _sentinelNode)
 413      {
 414        if (StepperReverse(node.LeftChild) is Break ||
 415          step.Invoke(node.Value) is Break ||
 416          StepperReverse(node.RightChild) is Break)
 417          return Break;
 418      }
 419      return Continue;
 420    }
 421    return StepperReverse(_root);
 422  }
 423
 424  /// <inheritdoc/>
 425  public virtual StepStatus StepperReverseBreak<TStep>(T minimum, T maximum, TStep step = default)
 426    where TStep : struct, IFunc<T, StepStatus>
 427  {
 428    StepStatus StepperReverse(Node node)
 429    {
 430      if (node != _sentinelNode)
 431      {
 432        if (_compare.Invoke(node.Value, minimum) is Less)
 433        {
 434          return StepperReverse(node.RightChild);
 435        }
 436        else if (_compare.Invoke(node.Value, maximum) is Greater)
 437        {
 438          return StepperReverse(node.LeftChild);
 439        }
 440        else
 441        {
 442          if (StepperReverse(node.LeftChild) is Break ||
 443            step.Invoke(node.Value) is Break ||
 444            StepperReverse(node.RightChild) is Break)
 445            return Break;
 446        }
 447      }
 448      return Continue;
 449    }
 450    if (_compare.Invoke(minimum, maximum) is Greater)
 451    {
 452      throw new InvalidOperationException("!(" + nameof(minimum) + " <= " + nameof(maximum) + ")");
 453    }
 454    return StepperReverse(_root);
 455  }
 456
 457  System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator() => GetEnumerator();
 458
 459  /// <inheritdoc/>
 460  public System.Collections.Generic.IEnumerator<T> GetEnumerator()
 461  {
 462    Node? GetNextNode(Node node)
 463    {
 464      if (node.RightChild != _sentinelNode)
 465      {
 466        return GetLeftMostNode(node.RightChild);
 467      }
 468      var parent = node.Parent;
 469      while (parent is not null && node == parent.RightChild)
 470      {
 471        node = parent;
 472        parent = parent.Parent;
 473      }
 474      return parent;
 475    }
 476    if (_count > 0)
 477    {
 478      for (var node = GetLeftMostNode(_root); node is not null; node = GetNextNode(node))
 479      {
 480        yield return node.Value;
 481      }
 482    }
 483  }
 484
 485  internal void BalanceAddition(Node balancing)
 486  {
 487    Node temp;
 488    while (balancing != _root && balancing.Parent!.Color == Red)
 489    {
 490      if (balancing.Parent == balancing.Parent.Parent!.LeftChild)
 491      {
 492        temp = balancing.Parent.Parent.RightChild;
 493        if (temp is not null && temp.Color == Red)
 494        {
 495          balancing.Parent.Color = Black;
 496          temp.Color = Black;
 497          balancing.Parent.Parent.Color = Red;
 498          balancing = balancing.Parent.Parent;
 499        }
 500        else
 501        {
 502          if (balancing == balancing.Parent.RightChild)
 503          {
 504            balancing = balancing.Parent;
 505            RotateLeft(balancing);
 506          }
 507          balancing.Parent!.Color = Black;
 508          balancing.Parent.Parent!.Color = Red;
 509          RotateRight(balancing.Parent.Parent);
 510        }
 511      }
 512      else
 513      {
 514        temp = balancing.Parent.Parent.LeftChild;
 515        if (temp is not null && temp.Color == Red)
 516        {
 517          balancing.Parent.Color = Black;
 518          temp.Color = Black;
 519          balancing.Parent.Parent.Color = Red;
 520          balancing = balancing.Parent.Parent;
 521        }
 522        else
 523        {
 524          if (balancing == balancing.Parent.LeftChild)
 525          {
 526            balancing = balancing.Parent;
 527            RotateRight(balancing);
 528          }
 529          balancing.Parent!.Color = Black;
 530          balancing.Parent.Parent!.Color = Red;
 531          RotateLeft(balancing.Parent.Parent);
 532        }
 533      }
 534    }
 535    _root.Color = Black;
 536  }
 537
 538  internal void RotateLeft(Node redBlackTree)
 539  {
 540    Node temp = redBlackTree.RightChild;
 541    redBlackTree.RightChild = temp.LeftChild;
 542    if (temp.LeftChild != _sentinelNode)
 543      temp.LeftChild.Parent = redBlackTree;
 544    if (temp != _sentinelNode)
 545      temp.Parent = redBlackTree.Parent;
 546    if (redBlackTree.Parent is not null)
 547    {
 548      if (redBlackTree == redBlackTree.Parent.LeftChild)
 549        redBlackTree.Parent.LeftChild = temp;
 550      else
 551        redBlackTree.Parent.RightChild = temp;
 552    }
 553    else
 554    {
 555      _root = temp;
 556    }
 557    temp.LeftChild = redBlackTree;
 558    if (redBlackTree != _sentinelNode)
 559      redBlackTree.Parent = temp;
 560  }
 561
 562  internal void RotateRight(Node redBlacktree)
 563  {
 564    Node temp = redBlacktree.LeftChild;
 565    redBlacktree.LeftChild = temp.RightChild;
 566    if (temp.RightChild != _sentinelNode)
 567      temp.RightChild.Parent = redBlacktree;
 568    if (temp != _sentinelNode)
 569      temp.Parent = redBlacktree.Parent;
 570    if (redBlacktree.Parent is not null)
 571    {
 572      if (redBlacktree == redBlacktree.Parent.RightChild)
 573        redBlacktree.Parent.RightChild = temp;
 574      else
 575        redBlacktree.Parent.LeftChild = temp;
 576    }
 577    else
 578    {
 579      _root = temp;
 580    }
 581    temp.RightChild = redBlacktree;
 582    if (redBlacktree != _sentinelNode)
 583      redBlacktree.Parent = temp;
 584  }
 585
 586  internal void BalanceRemoval(Node balancing)
 587  {
 588    Node temp;
 589    while (balancing != _root && balancing.Color == Black)
 590    {
 591      if (balancing == balancing.Parent!.LeftChild)
 592      {
 593        temp = balancing.Parent.RightChild;
 594        if (temp.Color == Red)
 595        {
 596          temp.Color = Black;
 597          balancing.Parent.Color = Red;
 598          RotateLeft(balancing.Parent);
 599          temp = balancing.Parent.RightChild;
 600        }
 601        if (temp.LeftChild.Color == Black && temp.RightChild.Color == Black)
 602        {
 603          temp.Color = Red;
 604          balancing = balancing.Parent;
 605        }
 606        else
 607        {
 608          if (temp.RightChild.Color == Black)
 609          {
 610            temp.LeftChild.Color = Black;
 611            temp.Color = Red;
 612            RotateRight(temp);
 613            temp = balancing.Parent.RightChild;
 614          }
 615          temp.Color = balancing.Parent.Color;
 616          balancing.Parent.Color = Black;
 617          temp.RightChild.Color = Black;
 618          RotateLeft(balancing.Parent);
 619          balancing = _root;
 620        }
 621      }
 622      else
 623      {
 624        temp = balancing.Parent.LeftChild;
 625        if (temp.Color == Red)
 626        {
 627          temp.Color = Black;
 628          balancing.Parent.Color = Red;
 629          RotateRight(balancing.Parent);
 630          temp = balancing.Parent.LeftChild;
 631        }
 632        if (temp.RightChild.Color == Black && temp.LeftChild.Color == Black)
 633        {
 634          temp.Color = Red;
 635          balancing = balancing.Parent;
 636        }
 637        else
 638        {
 639          if (temp.LeftChild.Color == Black)
 640          {
 641            temp.RightChild.Color = Black;
 642            temp.Color = Red;
 643            RotateLeft(temp);
 644            temp = balancing.Parent.LeftChild;
 645          }
 646          temp.Color = balancing.Parent.Color;
 647          balancing.Parent.Color = Black;
 648          temp.LeftChild.Color = Black;
 649          RotateRight(balancing.Parent);
 650          balancing = _root;
 651        }
 652      }
 653    }
 654    balancing.Color = Black;
 655  }
 656
 657  internal Node GetLeftMostNode(Node node)
 658  {
 659    while (node.LeftChild is not null && node.LeftChild != _sentinelNode)
 660    {
 661      node = node.LeftChild;
 662    }
 663    return node;
 664  }
 665
 666  /// <inheritdoc/>
 667  public T[] ToArray()
 668  {
 669#warning TODO: optimize
 670    T[] array = new T[_count];
 671    int i = 0;
 672    this.Stepper(x => array[i++] = x);
 673    return array;
 674  }
 675
 676  #endregion
 677}
Generated by: ReportGenerator 4.8.11.0
08/14/2022 - 14:40:44
GitHub | www.palmmedia.de

Methods/Properties

New(...)