< Summary

Class:Towel.DataStructures.HeapArray<T1, T2>
Assembly:Towel
File(s):File 1: /home/runner/work/Towel/Towel/Sources/Towel/DataStructures/Heap.cs
Covered lines:54
Uncovered lines:50
Coverable lines:104
Total lines:273
Line coverage:51.9% (54 of 104)
Covered branches:20
Total branches:40
Branch coverage:50% (20 of 40)

Metrics

MethodBranch coverage Cyclomatic complexity Line coverage
File 1: .ctor(...)75%4100%
File 1: .ctor(...)100%10%
File 1: get_Compare()100%10%
File 1: get_CurrentCapacity()100%10%
File 1: get_MinimumCapacity()100%10%
File 1: set_MinimumCapacity(...)0%60%
File 1: get_Count()100%1100%
File 1: LeftChild(...)100%1100%
File 1: RightChild(...)100%1100%
File 1: Parent(...)100%1100%
File 1: Enqueue(...)66.66%683.33%
File 1: Dequeue()50%290%
File 1: Requeue(...)0%60%
File 1: Peek()0%20%
File 1: ShiftUp(...)100%4100%
File 1: ShiftDown(...)100%8100%
File 1: Clear()100%10%
File 1: ToArray()100%1100%
File 1: System.Collections.IEnumerable.GetEnumerator()100%10%
File 1: GetEnumerator()0%20%
File 1: StepperBreak(...)100%10%
File 1: Clone()100%10%

File(s)

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

#LineLine coverage
 1namespace Towel.DataStructures;
 2
 3/// <summary>Stores items based on priorities and allows access to the highest priority item.</summary>
 4/// <typeparam name="T">The type of values stored in this data structure.</typeparam>
 5public interface IHeap<T> : IDataStructure<T>,
 6  DataStructure.ICountable,
 7  DataStructure.IClearable
 8{
 9  #region Methods
 10
 11  /// <summary>Enqueues an item into the heap.</summary>
 12  /// <param name="value">The value to queue in the heap.</param>
 13  void Enqueue(T value);
 14  /// <summary>Removes and returns the highest priority item.</summary>
 15  /// <returns>The highest priority item from the heap.</returns>
 16  T Dequeue();
 17  /// <summary>Returns the highest priority item.</summary>
 18  /// <returns>The highest priority item in the heap.</returns>
 19  T Peek();
 20
 21  #endregion
 22}
 23
 24/// <summary>Stores items based on priorities and allows access to the highest priority item.</summary>
 25/// <typeparam name="T">The type of values stored in this data structure.</typeparam>
 26/// <typeparam name="TCompare">The type that is comparing <typeparamref name="T"/> values.</typeparam>
 27public interface IHeap<T, TCompare> : IHeap<T>,
 28  DataStructure.IComparing<T, TCompare>
 29  where TCompare : struct, IFunc<T, T, CompareResult>
 30{
 31
 32}
 33
 34/// <summary>Static helpers for <see cref="IAvlTree{T, TCompare}"/>.</summary>
 35public static class Heap
 36{
 37
 38}
 39
 40/// <summary>Static helpers for <see cref="HeapArray{T, TCompare}"/>.</summary>
 41public static class HeapArray
 42{
 43  #region Extension Methods
 44
 45  /// <summary>Constructs a new <see cref="HeapArray{T, TCompare}"/>.</summary>
 46  /// <typeparam name="T">The type of values stored in this data structure.</typeparam>
 47  /// <param name="compare">The function for comparing <typeparamref name="T"/> values.</param>
 48  /// <param name="minimumCapacity">The capacity you want this priority queue to have.</param>
 49  /// <returns>The newly constructed <see cref="HeapArray{T, TCompare}"/>.</returns>
 50  public static HeapArray<T, SFunc<T, T, CompareResult>> New<T>(
 51    Func<T, T, CompareResult>? compare = null,
 52    int? minimumCapacity = null) =>
 53    new(compare ?? Compare, minimumCapacity);
 54
 55  #endregion
 56}
 57
 58/// <summary>A heap with static priorities implemented as a array.</summary>
 59/// <typeparam name="T">The type of values stored in this data structure.</typeparam>
 60/// <typeparam name="TCompare">The type that is comparing <typeparamref name="T"/> values.</typeparam>
 61public class HeapArray<T, TCompare> : IHeap<T, TCompare>, IHeap<T>,
 62  ICloneable<HeapArray<T, TCompare>>
 63  where TCompare : struct, IFunc<T, T, CompareResult>
 64{
 65  internal const int _root = 1; // The root index of the heap.
 66
 67  internal TCompare _compare;
 68  internal T[] _array;
 69  internal int? _minimumCapacity;
 70  internal int _count;
 71
 72  #region Constructors
 73
 74  /// <inheritdoc cref="HeapArray.New{T}(Func{T, T, CompareResult}?, int?)"/>
 5475  public HeapArray(TCompare compare = default, int? minimumCapacity = null)
 5476  {
 5477    if (minimumCapacity is not null && minimumCapacity.Value < 1) throw new ArgumentOutOfRangeException(message: "value.
 5478    _compare = compare;
 5479    _minimumCapacity = minimumCapacity;
 5480    _array = new T[(_minimumCapacity ?? 0) + _root];
 5481    _count = 0;
 5482  }
 83
 084  internal HeapArray(HeapArray<T, TCompare> heap)
 085  {
 086    _compare = heap._compare;
 087    _minimumCapacity = heap._minimumCapacity;
 088    _array = (T[])heap._array.Clone();
 089    _count = heap._count;
 090  }
 91
 92  #endregion
 93
 94  #region Properties
 95
 96  /// <inheritdoc/>
 097  public TCompare Compare => _compare;
 98
 99  /// <summary>
 100  /// The maximum items the queue can hold.<br/>
 101  /// Runtime: O(1)
 102  /// </summary>
 0103  public int CurrentCapacity => _array.Length - 1;
 104
 105  /// <summary>
 106  /// The minumum capacity of this queue to limit low-level resizing.<br/>
 107  /// Runtime: O(1)
 108  /// </summary>
 109  public int? MinimumCapacity
 110  {
 0111    get => _minimumCapacity;
 112    set
 0113    {
 0114      if (value is not null)
 0115      {
 0116        if (value.Value < 1) throw new ArgumentOutOfRangeException(message: "value.Value < 1", paramName: nameof(value))
 0117        else if (value.Value > _array.Length + 1) Array.Resize<T>(ref _array, value.Value + 1);
 0118      }
 0119      _minimumCapacity = value;
 0120    }
 121  }
 122
 123  /// <inheritdoc/>
 194124  public int Count => _count;
 125
 126  #endregion
 127
 128  #region Methods
 129
 130  /// <summary>Gets the index of the left child of the provided item.</summary>
 131  /// <param name="parent">The item to find the left child of.</param>
 132  /// <returns>The index of the left child of the provided item.</returns>
 2163133  internal static int LeftChild(int parent) => parent * 2;
 134
 135  /// <summary>Gets the index of the right child of the provided item.</summary>
 136  /// <param name="parent">The item to find the right child of.</param>
 137  /// <returns>The index of the right child of the provided item.</returns>
 1757138  internal static int RightChild(int parent) => parent * 2 + 1;
 139
 140  /// <summary>Gets the index of the parent of the provided item.</summary>
 141  /// <param name="child">The item to find the parent of.</param>
 142  /// <returns>The index of the parent of the provided item.</returns>
 992143  internal static int Parent(int child) => child / 2;
 144
 145  /// <inheritdoc/>
 146  public void Enqueue(T value)
 554147  {
 554148    if (_count + 1 >= _array.Length)
 34149    {
 34150      if (_array.Length is int.MaxValue)
 0151      {
 0152        throw new InvalidOperationException("this heap has become too large");
 153      }
 34154      Array.Resize<T>(ref _array, _array.Length > int.MaxValue / 2 ? int.MaxValue : _array.Length * 2);
 34155    }
 554156    _count++;
 554157    _array[_count] = value;
 554158    ShiftUp(_count);
 554159  }
 160
 161  /// <inheritdoc/>
 162  public T Dequeue()
 470163  {
 470164    if (_count > 0)
 470165    {
 470166      T removal = _array[_root];
 470167      Swap(ref _array[_root], ref _array[_count]);
 470168      _count--;
 470169      ShiftDown(_root);
 470170      return removal;
 171    }
 0172    throw new InvalidOperationException("Attempting to remove from an empty priority queue.");
 470173  }
 174
 175  /// <summary>
 176  /// Requeues an item after a change has occured.<br/>
 177  /// Runtime: O(n)
 178  /// </summary>
 179  /// <param name="item">The item to requeue.</param>
 180  public void Requeue(T item)
 0181  {
 182    int i;
 0183    for (i = 1; i <= _count; i++)
 0184    {
 0185      if (_compare.Invoke(item, _array[i]) is Equal)
 0186      {
 0187        break;
 188      }
 0189    }
 0190    if (i > _count)
 0191    {
 0192      throw new InvalidOperationException("Attempting to re-queue an item that is not in the heap.");
 193    }
 0194    ShiftUp(i);
 0195    ShiftDown(i);
 0196  }
 197
 198  /// <inheritdoc/>
 199  public T Peek()
 0200  {
 0201    if (_count > 0)
 0202    {
 0203      return _array[_root];
 204    }
 0205    throw new InvalidOperationException("Attempting to peek at an empty priority queue.");
 0206  }
 207
 208  /// <summary>
 209  /// Standard priority queue algorithm for up sifting.<br/>
 210  /// Runtime: O(ln(n)), Ω(1)
 211  /// </summary>
 212  /// <param name="index">The index to be up sifted.</param>
 213  internal void ShiftUp(int index)
 554214  {
 215    int parent;
 992216    while ((parent = Parent(index)) > 0 && _compare.Invoke(_array[index], _array[parent]) is Greater)
 438217    {
 438218      Swap(ref _array[index], ref _array[parent]);
 438219      index = parent;
 438220    }
 554221  }
 222
 223  /// <summary>
 224  /// Standard priority queue algorithm for sifting down.<br/>
 225  /// Runtime: O(ln(n)), Ω(1)
 226  /// </summary>
 227  /// <param name="index">The index to be down sifted.</param>
 228  internal void ShiftDown(int index)
 470229  {
 230    int leftChild, rightChild;
 2163231    while ((leftChild = LeftChild(index)) <= _count)
 1757232    {
 1757233      int down = leftChild;
 1757234      if ((rightChild = RightChild(index)) <= _count && _compare.Invoke(_array[rightChild], _array[leftChild]) is Greate
 807235      {
 807236        down = rightChild;
 807237      }
 1757238      if (_compare.Invoke(_array[down], _array[index]) is Less)
 64239      {
 64240        break;
 241      }
 1693242      Swap(ref _array[index], ref _array[down]);
 1693243      index = down;
 1693244    }
 470245  }
 246
 247  /// <inheritdoc/>
 0248  public void Clear() => _count = 0;
 249
 250  /// <inheritdoc/>
 44251  public T[] ToArray() => _array[1..(_count + 1)];
 252
 0253  System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator() => GetEnumerator();
 254
 255  /// <inheritdoc/>
 256  public System.Collections.Generic.IEnumerator<T> GetEnumerator()
 0257  {
 0258    for (int i = 1; i <= _count; i++)
 0259    {
 0260      yield return _array[i];
 0261    }
 0262  }
 263
 264  /// <inheritdoc/>
 265  public StepStatus StepperBreak<TStep>(TStep step = default)
 266    where TStep : struct, IFunc<T, StepStatus> =>
 0267    _array.StepperBreak(1, _count + 1, step);
 268
 269  /// <inheritdoc/>
 0270  public HeapArray<T, TCompare> Clone() => new(this);
 271
 272  #endregion
 273}
Generated by: ReportGenerator 4.8.11.0
08/14/2022 - 14:40:42
GitHub | www.palmmedia.de

Methods/Properties

.ctor(...)
.ctor(...)
get_Compare()
get_CurrentCapacity()
get_MinimumCapacity()
set_MinimumCapacity(...)
get_Count()
LeftChild(...)
RightChild(...)
Parent(...)
Enqueue(...)
Dequeue()
Requeue(...)
Peek()
ShiftUp(...)
ShiftDown(...)
Clear()
ToArray()
System.Collections.IEnumerable.GetEnumerator()
GetEnumerator()
StepperBreak(...)
Clone()