< Summary

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

Metrics

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

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) =>
 453    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?)"/>
 75  public HeapArray(TCompare compare = default, int? minimumCapacity = null)
 76  {
 77    if (minimumCapacity is not null && minimumCapacity.Value < 1) throw new ArgumentOutOfRangeException(message: "value.
 78    _compare = compare;
 79    _minimumCapacity = minimumCapacity;
 80    _array = new T[(_minimumCapacity ?? 0) + _root];
 81    _count = 0;
 82  }
 83
 84  internal HeapArray(HeapArray<T, TCompare> heap)
 85  {
 86    _compare = heap._compare;
 87    _minimumCapacity = heap._minimumCapacity;
 88    _array = (T[])heap._array.Clone();
 89    _count = heap._count;
 90  }
 91
 92  #endregion
 93
 94  #region Properties
 95
 96  /// <inheritdoc/>
 97  public TCompare Compare => _compare;
 98
 99  /// <summary>
 100  /// The maximum items the queue can hold.<br/>
 101  /// Runtime: O(1)
 102  /// </summary>
 103  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  {
 111    get => _minimumCapacity;
 112    set
 113    {
 114      if (value is not null)
 115      {
 116        if (value.Value < 1) throw new ArgumentOutOfRangeException(message: "value.Value < 1", paramName: nameof(value))
 117        else if (value.Value > _array.Length + 1) Array.Resize<T>(ref _array, value.Value + 1);
 118      }
 119      _minimumCapacity = value;
 120    }
 121  }
 122
 123  /// <inheritdoc/>
 124  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>
 133  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>
 138  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>
 143  internal static int Parent(int child) => child / 2;
 144
 145  /// <inheritdoc/>
 146  public void Enqueue(T value)
 147  {
 148    if (_count + 1 >= _array.Length)
 149    {
 150      if (_array.Length is int.MaxValue)
 151      {
 152        throw new InvalidOperationException("this heap has become too large");
 153      }
 154      Array.Resize<T>(ref _array, _array.Length > int.MaxValue / 2 ? int.MaxValue : _array.Length * 2);
 155    }
 156    _count++;
 157    _array[_count] = value;
 158    ShiftUp(_count);
 159  }
 160
 161  /// <inheritdoc/>
 162  public T Dequeue()
 163  {
 164    if (_count > 0)
 165    {
 166      T removal = _array[_root];
 167      Swap(ref _array[_root], ref _array[_count]);
 168      _count--;
 169      ShiftDown(_root);
 170      return removal;
 171    }
 172    throw new InvalidOperationException("Attempting to remove from an empty priority queue.");
 173  }
 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)
 181  {
 182    int i;
 183    for (i = 1; i <= _count; i++)
 184    {
 185      if (_compare.Invoke(item, _array[i]) is Equal)
 186      {
 187        break;
 188      }
 189    }
 190    if (i > _count)
 191    {
 192      throw new InvalidOperationException("Attempting to re-queue an item that is not in the heap.");
 193    }
 194    ShiftUp(i);
 195    ShiftDown(i);
 196  }
 197
 198  /// <inheritdoc/>
 199  public T Peek()
 200  {
 201    if (_count > 0)
 202    {
 203      return _array[_root];
 204    }
 205    throw new InvalidOperationException("Attempting to peek at an empty priority queue.");
 206  }
 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)
 214  {
 215    int parent;
 216    while ((parent = Parent(index)) > 0 && _compare.Invoke(_array[index], _array[parent]) is Greater)
 217    {
 218      Swap(ref _array[index], ref _array[parent]);
 219      index = parent;
 220    }
 221  }
 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)
 229  {
 230    int leftChild, rightChild;
 231    while ((leftChild = LeftChild(index)) <= _count)
 232    {
 233      int down = leftChild;
 234      if ((rightChild = RightChild(index)) <= _count && _compare.Invoke(_array[rightChild], _array[leftChild]) is Greate
 235      {
 236        down = rightChild;
 237      }
 238      if (_compare.Invoke(_array[down], _array[index]) is Less)
 239      {
 240        break;
 241      }
 242      Swap(ref _array[index], ref _array[down]);
 243      index = down;
 244    }
 245  }
 246
 247  /// <inheritdoc/>
 248  public void Clear() => _count = 0;
 249
 250  /// <inheritdoc/>
 251  public T[] ToArray() => _array[1..(_count + 1)];
 252
 253  System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator() => GetEnumerator();
 254
 255  /// <inheritdoc/>
 256  public System.Collections.Generic.IEnumerator<T> GetEnumerator()
 257  {
 258    for (int i = 1; i <= _count; i++)
 259    {
 260      yield return _array[i];
 261    }
 262  }
 263
 264  /// <inheritdoc/>
 265  public StepStatus StepperBreak<TStep>(TStep step = default)
 266    where TStep : struct, IFunc<T, StepStatus> =>
 267    _array.StepperBreak(1, _count + 1, step);
 268
 269  /// <inheritdoc/>
 270  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

New(...)