< Summary

Class:Towel.DataStructures.AvlTreeLinked<T1, T2>
Assembly:Towel
File(s):File 1: /home/runner/work/Towel/Towel/Sources/Towel/DataStructures/AvlTree.cs
Covered lines:174
Uncovered lines:129
Coverable lines:303
Total lines:524
Line coverage:57.4% (174 of 303)
Covered branches:39
Total branches:108
Branch coverage:36.1% (39 of 108)

Metrics

MethodBranch coverage Cyclomatic complexity Line coverage
File 1: .ctor(...)100%1100%
File 1: .ctor(...)100%1100%
File 1: .ctor(...)0%20%
File 1: get_CurrentLeast()0%40%
File 1: get_CurrentGreatest()0%40%
File 1: get_Compare()100%1100%
File 1: get_Count()100%1100%
File 1: TryAdd(...)100%1100%
File 1: Clear()100%10%
File 1: Clone()100%10%
File 1: Contains(...)100%1100%
File 1: ContainsSift(...)62.5%880%
File 1: TryGet(...)0%60%
File 1: TryRemove(...)100%1100%
File 1: TryRemoveSift(...)100%2100%
File 1: StepperBreak(...)100%1100%
File 1: StepperBreak(...)0%20%
File 1: StepperReverseBreak(...)100%10%
File 1: StepperReverseBreak(...)0%20%
File 1: System.Collections.IEnumerable.GetEnumerator()100%10%
File 1: GetEnumerator()100%1100%
File 1: Balance(...)100%8100%
File 1: Height(...)100%2100%
File 1: RemoveLeftMost(...)100%2100%
File 1: RemoveRightMost(...)50%266.66%
File 1: SetHeight(...)100%1100%
File 1: ToArray()100%10%

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) =>
 36    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
 143161    internal Node(
 143162      T value,
 143163      int height = default,
 143164      Node? leftChild = null,
 143165      Node? rightChild = null)
 143166    {
 143167      Value = value;
 143168      Height = height;
 143169      LeftChild = leftChild;
 143170      RightChild = rightChild;
 143171    }
 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>
 1780  public AvlTreeLinked(TCompare compare = default)
 1781  {
 1782    _root = null;
 1783    _count = 0;
 1784    _compare = compare;
 1785  }
 86
 87  /// <summary>This constructor if for cloning purposes.</summary>
 88  /// <param name="tree">The tree to clone.</param>
 089  internal AvlTreeLinked(AvlTreeLinked<T, TCompare> tree)
 090  {
 91    static Node Clone(Node node) =>
 092      new(
 093        value: node.Value,
 094        height: node.Height,
 095        leftChild: node.LeftChild is null ? null : Clone(node.LeftChild),
 096        rightChild: node.RightChild is null ? null : Clone(node.RightChild));
 097    _root = tree._root is null ? null : Clone(tree._root);
 098    _count = tree._count;
 099    _compare = tree._compare;
 0100  }
 101
 102  #endregion
 103
 104  #region Properties
 105
 106  /// <inheritdoc/>
 107  public T CurrentLeast
 108  {
 109    get
 0110    {
 0111      if (_root is null) throw new InvalidOperationException("Attempting to get the current least value from an empty AV
 0112      Node node = _root;
 0113      while (node.LeftChild is not null)
 0114      {
 0115        node = node.LeftChild;
 0116      }
 0117      return node.Value;
 0118    }
 119  }
 120
 121  /// <inheritdoc/>
 122  public T CurrentGreatest
 123  {
 124    get
 0125    {
 0126      if (_root is null) throw new InvalidOperationException("Attempting to get the current greatest value from an empty
 0127      Node node = _root;
 0128      while (node.RightChild is not null)
 0129      {
 0130        node = node.RightChild;
 0131      }
 0132      return node.Value;
 0133    }
 134  }
 135
 136  /// <inheritdoc/>
 3420137  public TCompare Compare => _compare;
 138
 139  /// <inheritdoc/>
 6016140  public int Count => _count;
 141
 142  #endregion
 143
 144  #region Methods
 145
 146  /// <inheritdoc/>
 147  public (bool Success, Exception? Exception) TryAdd(T value)
 1433148  {
 1433149    Exception? capturedException = null;
 150    Node? Add(Node? node)
 12740151    {
 12740152      if (node is null)
 1431153      {
 1431154        _count++;
 1431155        return new Node(value: value);
 156      }
 11309157      CompareResult compareResult = _compare.Invoke(node.Value, value);
 11309158      switch (compareResult)
 159      {
 22614160        case Less:    node.RightChild = Add(node.RightChild); break;
 0161        case Greater: node.LeftChild  = Add(node.LeftChild);  break;
 162        case Equal:
 2163          capturedException = new ArgumentException($"Adding to add a duplicate value to an {nameof(AvlTreeLinked<T, TCo
 2164          return node;
 165        default:
 0166          capturedException = compareResult.IsDefined()
 0167            ? new TowelBugException($"Unhandled {nameof(CompareResult)} value: {compareResult}.")
 0168            : new ArgumentException($"Invalid {nameof(TCompare)} function; an undefined {nameof(CompareResult)} was retu
 0169          break;
 170      }
 11307171      return capturedException is null ? Balance(node) : node;
 12740172    }
 1433173    _root = Add(_root);
 1433174    return (capturedException is null, capturedException);
 1433175  }
 176
 177  /// <inheritdoc/>
 178  public void Clear()
 0179  {
 0180    _root = null;
 0181    _count = 0;
 0182  }
 183
 184  /// <inheritdoc/>
 0185  public AvlTreeLinked<T, TCompare> Clone() => new(this);
 186
 187  /// <inheritdoc/>
 2212188  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>
 2212193  {
 2212194    Node? node = _root;
 19380195    while (node is not null)
 18374196    {
 18374197      CompareResult compareResult = sift.Invoke(node.Value);
 18374198      switch (compareResult)
 199      {
 25406200        case Less:    node = node.RightChild; break;
 8930201        case Greater: node = node.LeftChild;  break;
 1206202        case Equal:   return true;
 203        default:
 0204          throw compareResult.IsDefined()
 0205            ? new TowelBugException($"Unhandled {nameof(CompareResult)} value: {compareResult}.")
 0206            : new ArgumentException($"Invalid {nameof(TCompare)} function; an undefined {nameof(CompareResult)} was retu
 207      }
 17168208    }
 1006209    return false;
 2212210  }
 211
 212  /// <inheritdoc/>
 213  public (bool Success, T? Value, Exception? Exception) TryGet<TSift>(TSift sift = default)
 214    where TSift : struct, IFunc<T, CompareResult>
 0215  {
 0216    Node? node = _root;
 0217    while (node is not null)
 0218    {
 0219      CompareResult compareResult = sift.Invoke(node.Value);
 0220      switch (compareResult)
 221      {
 0222        case Less:    node = node.LeftChild;  break;
 0223        case Greater: node = node.RightChild; break;
 0224        case Equal: return (true, node.Value, null);
 0225        default: return (false, default, new ArgumentException($"Invalid {nameof(TCompare)} function; an undefined {name
 226      }
 0227    }
 0228    return (false, default, new InvalidOperationException("Attempting to get a non-existing value from an AVL tree."));
 0229  }
 230
 231  /// <inheritdoc/>
 1208232  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>
 1208237  {
 1208238    Exception? exception = null;
 239    Node? Remove(Node? node)
 8635240    {
 8635241      if (node is not null)
 8633242      {
 8633243        CompareResult compareResult = sift.Invoke(node.Value);
 8633244        switch (compareResult)
 245        {
 6614246          case Less:    node.RightChild = Remove(node.RightChild); break;
 8240247          case Greater: node.LeftChild  = Remove(node.LeftChild);  break;
 248          case Equal:
 1206249            if (node.RightChild is not null)
 589250            {
 589251              node.RightChild = RemoveLeftMost(node.RightChild, out Node leftMostOfRight);
 589252              leftMostOfRight.RightChild = node.RightChild;
 589253              leftMostOfRight.LeftChild = node.LeftChild;
 589254              node = leftMostOfRight;
 589255            }
 617256            else if (node.LeftChild is not null)
 69257            {
 69258              node.LeftChild = RemoveRightMost(node.LeftChild, out Node rightMostOfLeft);
 69259              rightMostOfLeft.RightChild = node.RightChild;
 69260              rightMostOfLeft.LeftChild = node.LeftChild;
 69261              node = rightMostOfLeft;
 69262            }
 263            else
 548264            {
 548265              return null;
 266            }
 658267            break;
 268          default:
 0269            exception = new ArgumentException($"Invalid {nameof(TCompare)} function; an undefined {nameof(CompareResult)
 0270            return node;
 271        }
 8085272        SetHeight(node);
 8085273        return Balance(node);
 274      }
 2275      exception = new ArgumentException("Attempting to remove a non-existing entry.");
 2276      return node;
 8635277    }
 1208278    _root = Remove(_root);
 1208279    if (exception is null)
 1206280    {
 1206281      _count--;
 1206282    }
 1208283    return (exception is null, exception);
 1208284  }
 285
 286  /// <inheritdoc/>
 287  public StepStatus StepperBreak<TStep>(TStep step = default)
 288    where TStep : struct, IFunc<T, StepStatus>
 2007289  {
 290    StepStatus Stepper(Node? node)
 2002059291    {
 2002059292      if (node is not null)
 1000026293      {
 1000026294        if (Stepper(node.LeftChild) is Break ||
 1000026295          step.Invoke(node.Value) is Break ||
 1000026296          Stepper(node.RightChild) is Break)
 0297          return Break;
 1000026298      }
 2002059299      return Continue;
 2002059300    }
 2007301    return Stepper(_root);
 2007302  }
 303
 304  /// <inheritdoc/>
 305  public virtual StepStatus StepperBreak<TStep>(T minimum, T maximum, TStep step = default)
 306    where TStep : struct, IFunc<T, StepStatus>
 0307  {
 308    StepStatus Stepper(Node? node)
 0309    {
 0310      if (node is not null)
 0311      {
 0312        if (_compare.Invoke(node.Value, minimum) is Less)
 0313        {
 0314          return Stepper(node.RightChild);
 315        }
 0316        else if (_compare.Invoke(node.Value, maximum) is Greater)
 0317        {
 0318          return Stepper(node.LeftChild);
 319        }
 320        else
 0321        {
 0322          if (Stepper(node.LeftChild) is Break ||
 0323            step.Invoke(node.Value) is Break ||
 0324            Stepper(node.RightChild) is Break)
 0325            return Break;
 0326        }
 0327      }
 0328      return Continue;
 0329    }
 0330    if (_compare.Invoke(minimum, maximum) is Greater)
 0331    {
 0332      throw new InvalidOperationException("!(" + nameof(minimum) + " <= " + nameof(maximum) + ")");
 333    }
 0334    return Stepper(_root);
 0335  }
 336
 337  /// <inheritdoc/>
 338  public StepStatus StepperReverseBreak<TStep>(TStep step = default)
 339    where TStep : struct, IFunc<T, StepStatus>
 0340  {
 341    StepStatus StepperReverse(Node? node)
 0342    {
 0343      if (node is not null)
 0344      {
 0345        if (StepperReverse(node.LeftChild) is Break ||
 0346          step.Invoke(node.Value) is Break ||
 0347          StepperReverse(node.RightChild) is Break)
 0348          return Break;
 0349      }
 0350      return Continue;
 0351    }
 0352    return StepperReverse(_root);
 0353  }
 354
 355  /// <inheritdoc/>
 356  public virtual StepStatus StepperReverseBreak<TStep>(T minimum, T maximum, TStep step = default)
 357    where TStep : struct, IFunc<T, StepStatus>
 0358  {
 359    StepStatus StepperReverse(Node? node)
 0360    {
 0361      if (node is not null)
 0362      {
 0363        if (_compare.Invoke(node.Value, minimum) is Less)
 0364        {
 0365          return StepperReverse(node.RightChild);
 366        }
 0367        else if (_compare.Invoke(node.Value, maximum) is Greater)
 0368        {
 0369          return StepperReverse(node.LeftChild);
 370        }
 371        else
 0372        {
 0373          if (StepperReverse(node.LeftChild) is Break ||
 0374            step.Invoke(node.Value) is Break ||
 0375            StepperReverse(node.RightChild) is Break)
 0376            return Break;
 0377        }
 0378      }
 0379      return Continue;
 0380    }
 0381    if (_compare.Invoke(minimum, maximum) is Greater)
 0382    {
 0383      throw new InvalidOperationException("!(" + nameof(minimum) + " <= " + nameof(maximum) + ")");
 384    }
 0385    return StepperReverse(_root);
 0386  }
 387
 0388  System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator() => GetEnumerator();
 389
 390  /// <inheritdoc/>
 391  public System.Collections.Generic.IEnumerator<T> GetEnumerator()
 7392  {
 393#warning TODO: optimize using stack
 7394    IList<T> list = new ListLinked<T>();
 33395    this.Stepper(x => list.Add(x));
 7396    return list.GetEnumerator();
 7397  }
 398
 399  internal static Node Balance(Node node)
 19842400  {
 401    static Node RotateSingleLeft(Node node)
 1515402    {
 1515403      Node temp = node.RightChild!;
 1515404      node.RightChild = temp.LeftChild;
 1515405      temp.LeftChild = node;
 1515406      SetHeight(node);
 1515407      SetHeight(temp);
 1515408      return temp;
 1515409    }
 410
 411    static Node RotateDoubleLeft(Node node)
 26412    {
 26413      Node temp = node.RightChild!.LeftChild!;
 26414      node.RightChild.LeftChild = temp.RightChild;
 26415      temp.RightChild = node.RightChild;
 26416      node.RightChild = temp.LeftChild;
 26417      temp.LeftChild = node;
 26418      SetHeight(temp.LeftChild);
 26419      SetHeight(temp.RightChild);
 26420      SetHeight(temp);
 26421      return temp;
 26422    }
 423
 424    static Node RotateSingleRight(Node node)
 58425    {
 58426      Node temp = node.LeftChild!;
 58427      node.LeftChild = temp.RightChild;
 58428      temp.RightChild = node;
 58429      SetHeight(node);
 58430      SetHeight(temp);
 58431      return temp;
 58432    }
 433
 434    static Node RotateDoubleRight(Node node)
 39435    {
 39436      Node temp = node.LeftChild!.RightChild!;
 39437      node.LeftChild.RightChild = temp.LeftChild;
 39438      temp.LeftChild = node.LeftChild;
 39439      node.LeftChild = temp.RightChild;
 39440      temp.RightChild = node;
 39441      SetHeight(temp.RightChild);
 39442      SetHeight(temp.LeftChild);
 39443      SetHeight(temp);
 39444      return temp;
 39445    }
 446
 19842447    if (Height(node.LeftChild) == Height(node.RightChild) + 2)
 97448    {
 97449      return Height(node.LeftChild!.LeftChild) > Height(node.RightChild)
 97450        ? RotateSingleRight(node)
 97451        : RotateDoubleRight(node);
 452    }
 19745453    else if (Height(node.RightChild) == Height(node.LeftChild) + 2)
 1541454    {
 1541455      return Height(node.RightChild!.RightChild) > Height(node.LeftChild)
 1541456        ? RotateSingleLeft(node)
 1541457        : RotateDoubleLeft(node);
 458    }
 18204459    SetHeight(node);
 18204460    return node;
 19842461  }
 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>
 142610469  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)
 1039477  {
 1039478    if (node.LeftChild is null)
 589479    {
 589480      leftMost = node;
 589481      return node.RightChild!;
 482    }
 450483    node.LeftChild = RemoveLeftMost(node.LeftChild, out leftMost);
 450484    SetHeight(node);
 450485    return Balance(node);
 1039486  }
 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)
 69494  {
 69495    if (node.RightChild is null)
 69496    {
 69497      rightMost = node;
 69498      return node.LeftChild!;
 499    }
 0500    node.RightChild = RemoveRightMost(node.RightChild, out rightMost);
 0501    SetHeight(node);
 0502    return Balance(node);
 69503  }
 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) =>
 30080511    node.Height = Math.Max(Height(node.LeftChild), Height(node.RightChild)) + 1;
 512
 513  /// <inheritdoc/>
 514  public T[] ToArray()
 0515  {
 516#warning TODO: optimize
 0517    T[] array = new T[_count];
 0518    int i = 0;
 0519    this.Stepper(x => array[i++] = x);
 0520    return array;
 0521  }
 522
 523  #endregion
 524}
Generated by: ReportGenerator 4.8.11.0
08/14/2022 - 14:40:42
GitHub | www.palmmedia.de

Methods/Properties

.ctor(...)
.ctor(...)
.ctor(...)
get_CurrentLeast()
get_CurrentGreatest()
get_Compare()
get_Count()
TryAdd(...)
Clear()
Clone()
Contains(...)
ContainsSift(...)
TryGet(...)
TryRemove(...)
TryRemoveSift(...)
StepperBreak(...)
StepperBreak(...)
StepperReverseBreak(...)
StepperReverseBreak(...)
System.Collections.IEnumerable.GetEnumerator()
GetEnumerator()
Balance(...)
Height(...)
RemoveLeftMost(...)
RemoveRightMost(...)
SetHeight(...)
ToArray()