< Summary

Class:Towel.DataStructures.AvlTreeLinked
Assembly:Towel
File(s):File 1: /home/runner/work/Towel/Towel/Sources/Towel/DataStructures/AvlTree.cs
Covered lines:1
Uncovered lines:0
Coverable lines:1
Total lines:524
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/AvlTree.cs

#LineLine coverage
 1namespace Towel.DataStructures;
 2
 3/// <summary>A self-sorting binary tree based on the heights of each node.</summary>
 4/// <typeparam name="T">The type of values stored in this data structure.</typeparam>
 5public interface IAvlTree<T> : ISortedBinaryTree<T>
 6{
 7
 8}
 9
 10/// <summary>A self-sorting binary tree based on the heights of each node.</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 IAvlTree<T, TCompare> : IAvlTree<T>, ISortedBinaryTree<T, TCompare>
 14  where TCompare : struct, IFunc<T, T, CompareResult>
 15{
 16
 17}
 18
 19/// <summary>Static helpers for <see cref="IAvlTree{T}"/> and <see cref="IAvlTree{T, TCompare}"/>.</summary>
 20public static class AvlTree
 21{
 22
 23}
 24
 25/// <summary>Static helpers for <see cref="AvlTreeLinked{T, TCompare}"/>.</summary>
 26public static class AvlTreeLinked
 27{
 28  #region Extension Methods
 29
 30  /// <summary>Constructs a new <see cref="AvlTreeLinked{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="AvlTreeLinked{T, TCompare}"/>.</returns>
 34  public static AvlTreeLinked<T, SFunc<T, T, CompareResult>> New<T>(
 35    Func<T, T, CompareResult>? compare = null) =>
 1736    new(compare ?? Compare);
 37
 38  #endregion
 39}
 40
 41/// <summary>A self-sorting binary tree based on the heights of each node.</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 AvlTreeLinked<T, TCompare> : IAvlTree<T, TCompare>,
 45  ICloneable<AvlTreeLinked<T, TCompare>>
 46  where TCompare : struct, IFunc<T, T, CompareResult>
 47{
 48  internal Node? _root;
 49  internal int _count;
 50  internal TCompare _compare;
 51
 52  #region Nested Types
 53
 54  internal class Node
 55  {
 56    internal T Value;
 57    internal Node? LeftChild;
 58    internal Node? RightChild;
 59    internal int Height;
 60
 61    internal Node(
 62      T value,
 63      int height = default,
 64      Node? leftChild = null,
 65      Node? rightChild = null)
 66    {
 67      Value = value;
 68      Height = height;
 69      LeftChild = leftChild;
 70      RightChild = rightChild;
 71    }
 72  }
 73
 74  #endregion
 75
 76  #region Constructors
 77
 78  /// <summary>Constructs an AVL Tree.</summary>
 79  /// <param name="compare">The comparison function for sorting <typeparamref name="T"/> values.</param>
 80  public AvlTreeLinked(TCompare compare = default)
 81  {
 82    _root = null;
 83    _count = 0;
 84    _compare = compare;
 85  }
 86
 87  /// <summary>This constructor if for cloning purposes.</summary>
 88  /// <param name="tree">The tree to clone.</param>
 89  internal AvlTreeLinked(AvlTreeLinked<T, TCompare> tree)
 90  {
 91    static Node Clone(Node node) =>
 92      new(
 93        value: node.Value,
 94        height: node.Height,
 95        leftChild: node.LeftChild is null ? null : Clone(node.LeftChild),
 96        rightChild: node.RightChild is null ? null : Clone(node.RightChild));
 97    _root = tree._root is null ? null : Clone(tree._root);
 98    _count = tree._count;
 99    _compare = tree._compare;
 100  }
 101
 102  #endregion
 103
 104  #region Properties
 105
 106  /// <inheritdoc/>
 107  public T CurrentLeast
 108  {
 109    get
 110    {
 111      if (_root is null) throw new InvalidOperationException("Attempting to get the current least value from an empty AV
 112      Node node = _root;
 113      while (node.LeftChild is not null)
 114      {
 115        node = node.LeftChild;
 116      }
 117      return node.Value;
 118    }
 119  }
 120
 121  /// <inheritdoc/>
 122  public T CurrentGreatest
 123  {
 124    get
 125    {
 126      if (_root is null) throw new InvalidOperationException("Attempting to get the current greatest value from an empty
 127      Node node = _root;
 128      while (node.RightChild is not null)
 129      {
 130        node = node.RightChild;
 131      }
 132      return node.Value;
 133    }
 134  }
 135
 136  /// <inheritdoc/>
 137  public TCompare Compare => _compare;
 138
 139  /// <inheritdoc/>
 140  public int Count => _count;
 141
 142  #endregion
 143
 144  #region Methods
 145
 146  /// <inheritdoc/>
 147  public (bool Success, Exception? Exception) TryAdd(T value)
 148  {
 149    Exception? capturedException = null;
 150    Node? Add(Node? node)
 151    {
 152      if (node is null)
 153      {
 154        _count++;
 155        return new Node(value: value);
 156      }
 157      CompareResult compareResult = _compare.Invoke(node.Value, value);
 158      switch (compareResult)
 159      {
 160        case Less:    node.RightChild = Add(node.RightChild); break;
 161        case Greater: node.LeftChild  = Add(node.LeftChild);  break;
 162        case Equal:
 163          capturedException = new ArgumentException($"Adding to add a duplicate value to an {nameof(AvlTreeLinked<T, TCo
 164          return node;
 165        default:
 166          capturedException = compareResult.IsDefined()
 167            ? new TowelBugException($"Unhandled {nameof(CompareResult)} value: {compareResult}.")
 168            : new ArgumentException($"Invalid {nameof(TCompare)} function; an undefined {nameof(CompareResult)} was retu
 169          break;
 170      }
 171      return capturedException is null ? Balance(node) : node;
 172    }
 173    _root = Add(_root);
 174    return (capturedException is null, capturedException);
 175  }
 176
 177  /// <inheritdoc/>
 178  public void Clear()
 179  {
 180    _root = null;
 181    _count = 0;
 182  }
 183
 184  /// <inheritdoc/>
 185  public AvlTreeLinked<T, TCompare> Clone() => new(this);
 186
 187  /// <inheritdoc/>
 188  public bool Contains(T value) => ContainsSift<SiftFromCompareAndValue<T, TCompare>>(new(value, Compare));
 189
 190  /// <inheritdoc/>
 191  public bool ContainsSift<TSift>(TSift sift = default)
 192    where TSift : struct, IFunc<T, CompareResult>
 193  {
 194    Node? node = _root;
 195    while (node is not null)
 196    {
 197      CompareResult compareResult = sift.Invoke(node.Value);
 198      switch (compareResult)
 199      {
 200        case Less:    node = node.RightChild; break;
 201        case Greater: node = node.LeftChild;  break;
 202        case Equal:   return true;
 203        default:
 204          throw compareResult.IsDefined()
 205            ? new TowelBugException($"Unhandled {nameof(CompareResult)} value: {compareResult}.")
 206            : new ArgumentException($"Invalid {nameof(TCompare)} function; an undefined {nameof(CompareResult)} was retu
 207      }
 208    }
 209    return false;
 210  }
 211
 212  /// <inheritdoc/>
 213  public (bool Success, T? Value, Exception? Exception) TryGet<TSift>(TSift sift = default)
 214    where TSift : struct, IFunc<T, CompareResult>
 215  {
 216    Node? node = _root;
 217    while (node is not null)
 218    {
 219      CompareResult compareResult = sift.Invoke(node.Value);
 220      switch (compareResult)
 221      {
 222        case Less:    node = node.LeftChild;  break;
 223        case Greater: node = node.RightChild; break;
 224        case Equal: return (true, node.Value, null);
 225        default: return (false, default, new ArgumentException($"Invalid {nameof(TCompare)} function; an undefined {name
 226      }
 227    }
 228    return (false, default, new InvalidOperationException("Attempting to get a non-existing value from an AVL tree."));
 229  }
 230
 231  /// <inheritdoc/>
 232  public (bool Success, Exception? Exception) TryRemove(T value) => TryRemoveSift<SiftFromCompareAndValue<T, TCompare>>(
 233
 234  /// <inheritdoc/>
 235  public (bool Success, Exception? Exception) TryRemoveSift<TSift>(TSift sift = default)
 236    where TSift : struct, IFunc<T, CompareResult>
 237  {
 238    Exception? exception = null;
 239    Node? Remove(Node? node)
 240    {
 241      if (node is not null)
 242      {
 243        CompareResult compareResult = sift.Invoke(node.Value);
 244        switch (compareResult)
 245        {
 246          case Less:    node.RightChild = Remove(node.RightChild); break;
 247          case Greater: node.LeftChild  = Remove(node.LeftChild);  break;
 248          case Equal:
 249            if (node.RightChild is not null)
 250            {
 251              node.RightChild = RemoveLeftMost(node.RightChild, out Node leftMostOfRight);
 252              leftMostOfRight.RightChild = node.RightChild;
 253              leftMostOfRight.LeftChild = node.LeftChild;
 254              node = leftMostOfRight;
 255            }
 256            else if (node.LeftChild is not null)
 257            {
 258              node.LeftChild = RemoveRightMost(node.LeftChild, out Node rightMostOfLeft);
 259              rightMostOfLeft.RightChild = node.RightChild;
 260              rightMostOfLeft.LeftChild = node.LeftChild;
 261              node = rightMostOfLeft;
 262            }
 263            else
 264            {
 265              return null;
 266            }
 267            break;
 268          default:
 269            exception = new ArgumentException($"Invalid {nameof(TCompare)} function; an undefined {nameof(CompareResult)
 270            return node;
 271        }
 272        SetHeight(node);
 273        return Balance(node);
 274      }
 275      exception = new ArgumentException("Attempting to remove a non-existing entry.");
 276      return node;
 277    }
 278    _root = Remove(_root);
 279    if (exception is null)
 280    {
 281      _count--;
 282    }
 283    return (exception is null, exception);
 284  }
 285
 286  /// <inheritdoc/>
 287  public StepStatus StepperBreak<TStep>(TStep step = default)
 288    where TStep : struct, IFunc<T, StepStatus>
 289  {
 290    StepStatus Stepper(Node? node)
 291    {
 292      if (node is not null)
 293      {
 294        if (Stepper(node.LeftChild) is Break ||
 295          step.Invoke(node.Value) is Break ||
 296          Stepper(node.RightChild) is Break)
 297          return Break;
 298      }
 299      return Continue;
 300    }
 301    return Stepper(_root);
 302  }
 303
 304  /// <inheritdoc/>
 305  public virtual StepStatus StepperBreak<TStep>(T minimum, T maximum, TStep step = default)
 306    where TStep : struct, IFunc<T, StepStatus>
 307  {
 308    StepStatus Stepper(Node? node)
 309    {
 310      if (node is not null)
 311      {
 312        if (_compare.Invoke(node.Value, minimum) is Less)
 313        {
 314          return Stepper(node.RightChild);
 315        }
 316        else if (_compare.Invoke(node.Value, maximum) is Greater)
 317        {
 318          return Stepper(node.LeftChild);
 319        }
 320        else
 321        {
 322          if (Stepper(node.LeftChild) is Break ||
 323            step.Invoke(node.Value) is Break ||
 324            Stepper(node.RightChild) is Break)
 325            return Break;
 326        }
 327      }
 328      return Continue;
 329    }
 330    if (_compare.Invoke(minimum, maximum) is Greater)
 331    {
 332      throw new InvalidOperationException("!(" + nameof(minimum) + " <= " + nameof(maximum) + ")");
 333    }
 334    return Stepper(_root);
 335  }
 336
 337  /// <inheritdoc/>
 338  public StepStatus StepperReverseBreak<TStep>(TStep step = default)
 339    where TStep : struct, IFunc<T, StepStatus>
 340  {
 341    StepStatus StepperReverse(Node? node)
 342    {
 343      if (node is not null)
 344      {
 345        if (StepperReverse(node.LeftChild) is Break ||
 346          step.Invoke(node.Value) is Break ||
 347          StepperReverse(node.RightChild) is Break)
 348          return Break;
 349      }
 350      return Continue;
 351    }
 352    return StepperReverse(_root);
 353  }
 354
 355  /// <inheritdoc/>
 356  public virtual StepStatus StepperReverseBreak<TStep>(T minimum, T maximum, TStep step = default)
 357    where TStep : struct, IFunc<T, StepStatus>
 358  {
 359    StepStatus StepperReverse(Node? node)
 360    {
 361      if (node is not null)
 362      {
 363        if (_compare.Invoke(node.Value, minimum) is Less)
 364        {
 365          return StepperReverse(node.RightChild);
 366        }
 367        else if (_compare.Invoke(node.Value, maximum) is Greater)
 368        {
 369          return StepperReverse(node.LeftChild);
 370        }
 371        else
 372        {
 373          if (StepperReverse(node.LeftChild) is Break ||
 374            step.Invoke(node.Value) is Break ||
 375            StepperReverse(node.RightChild) is Break)
 376            return Break;
 377        }
 378      }
 379      return Continue;
 380    }
 381    if (_compare.Invoke(minimum, maximum) is Greater)
 382    {
 383      throw new InvalidOperationException("!(" + nameof(minimum) + " <= " + nameof(maximum) + ")");
 384    }
 385    return StepperReverse(_root);
 386  }
 387
 388  System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator() => GetEnumerator();
 389
 390  /// <inheritdoc/>
 391  public System.Collections.Generic.IEnumerator<T> GetEnumerator()
 392  {
 393#warning TODO: optimize using stack
 394    IList<T> list = new ListLinked<T>();
 395    this.Stepper(x => list.Add(x));
 396    return list.GetEnumerator();
 397  }
 398
 399  internal static Node Balance(Node node)
 400  {
 401    static Node RotateSingleLeft(Node node)
 402    {
 403      Node temp = node.RightChild!;
 404      node.RightChild = temp.LeftChild;
 405      temp.LeftChild = node;
 406      SetHeight(node);
 407      SetHeight(temp);
 408      return temp;
 409    }
 410
 411    static Node RotateDoubleLeft(Node node)
 412    {
 413      Node temp = node.RightChild!.LeftChild!;
 414      node.RightChild.LeftChild = temp.RightChild;
 415      temp.RightChild = node.RightChild;
 416      node.RightChild = temp.LeftChild;
 417      temp.LeftChild = node;
 418      SetHeight(temp.LeftChild);
 419      SetHeight(temp.RightChild);
 420      SetHeight(temp);
 421      return temp;
 422    }
 423
 424    static Node RotateSingleRight(Node node)
 425    {
 426      Node temp = node.LeftChild!;
 427      node.LeftChild = temp.RightChild;
 428      temp.RightChild = node;
 429      SetHeight(node);
 430      SetHeight(temp);
 431      return temp;
 432    }
 433
 434    static Node RotateDoubleRight(Node node)
 435    {
 436      Node temp = node.LeftChild!.RightChild!;
 437      node.LeftChild.RightChild = temp.LeftChild;
 438      temp.LeftChild = node.LeftChild;
 439      node.LeftChild = temp.RightChild;
 440      temp.RightChild = node;
 441      SetHeight(temp.RightChild);
 442      SetHeight(temp.LeftChild);
 443      SetHeight(temp);
 444      return temp;
 445    }
 446
 447    if (Height(node.LeftChild) == Height(node.RightChild) + 2)
 448    {
 449      return Height(node.LeftChild!.LeftChild) > Height(node.RightChild)
 450        ? RotateSingleRight(node)
 451        : RotateDoubleRight(node);
 452    }
 453    else if (Height(node.RightChild) == Height(node.LeftChild) + 2)
 454    {
 455      return Height(node.RightChild!.RightChild) > Height(node.LeftChild)
 456        ? RotateSingleLeft(node)
 457        : RotateDoubleLeft(node);
 458    }
 459    SetHeight(node);
 460    return node;
 461  }
 462
 463  /// <summary>
 464  /// This is just a protection against the null valued leaf nodes, which have a height of "-1".<br/>
 465  /// Runtime: O(1)
 466  /// </summary>
 467  /// <param name="node">The node to find the hight of.</param>
 468  /// <returns>Returns "-1" if null (leaf) or the height property of the node.</returns>
 469  internal static int Height(Node? node) => node is null ? -1 : node.Height;
 470
 471  /// <summary>Removes the left-most child of an AVL Tree node and returns it
 472  /// through the out parameter.</summary>
 473  /// <param name="node">The tree to remove the left-most child from.</param>
 474  /// <param name="leftMost">The left-most child of this AVL tree.</param>
 475  /// <returns>The updated tree with the removal.</returns>
 476  internal static Node RemoveLeftMost(Node node, out Node leftMost)
 477  {
 478    if (node.LeftChild is null)
 479    {
 480      leftMost = node;
 481      return node.RightChild!;
 482    }
 483    node.LeftChild = RemoveLeftMost(node.LeftChild, out leftMost);
 484    SetHeight(node);
 485    return Balance(node);
 486  }
 487
 488  /// <summary>Removes the right-most child of an AVL Tree node and returns it
 489  /// through the out parameter.</summary>
 490  /// <param name="node">The tree to remove the right-most child from.</param>
 491  /// <param name="rightMost">The right-most child of this AVL tree.</param>
 492  /// <returns>The updated tree with the removal.</returns>
 493  internal static Node RemoveRightMost(Node node, out Node rightMost)
 494  {
 495    if (node.RightChild is null)
 496    {
 497      rightMost = node;
 498      return node.LeftChild!;
 499    }
 500    node.RightChild = RemoveRightMost(node.RightChild, out rightMost);
 501    SetHeight(node);
 502    return Balance(node);
 503  }
 504
 505  /// <summary>
 506  /// Sets the height of a tree based on its children's heights.<br/>
 507  /// Runtime: O(1)
 508  /// </summary>
 509  /// <param name="node">The tree to have its height adjusted.</param>
 510  internal static void SetHeight(Node node) =>
 511    node.Height = Math.Max(Height(node.LeftChild), Height(node.RightChild)) + 1;
 512
 513  /// <inheritdoc/>
 514  public T[] ToArray()
 515  {
 516#warning TODO: optimize
 517    T[] array = new T[_count];
 518    int i = 0;
 519    this.Stepper(x => array[i++] = x);
 520    return array;
 521  }
 522
 523  #endregion
 524}
Generated by: ReportGenerator 4.8.11.0
08/14/2022 - 14:40:42
GitHub | www.palmmedia.de

Methods/Properties

New(...)