< Summary

Information
Class: MoreStructures.PriorityQueues.BinaryHeap.BinaryHeapListWrapper<T>
Assembly: MoreStructures
File(s): /home/runner/work/MoreStructures/MoreStructures/MoreStructures/PriorityQueues/BinaryHeap/BinaryHeapListWrapper.cs
Line coverage
100%
Covered lines: 187
Uncovered lines: 0
Coverable lines: 187
Total lines: 435
Line coverage: 100%
Branch coverage
100%
Covered branches: 82
Total branches: 82
Branch coverage: 100%
Method coverage

Feature is only available for sponsors

Upgrade to PRO version

Metrics

MethodBranch coverage Cyclomatic complexity Line coverage
get_Items()100%1100%
get_Comparer()100%1100%
get_StoreHeapAtTheEnd()100%1100%
get_IndexDelta()100%1100%
get_HeapCount()100%1100%
get_RaiseItemPushed()100%1100%
get_RaiseItemPopping()100%1100%
get_RaiseItemsSwapped()100%1100%
.ctor(...)100%12100%
.ctor(...)100%1100%
RestoreHeapProperty()100%6100%
Peek()100%2100%
Pop()100%4100%
Push(...)100%8100%
PeekKth(...)100%12100%
PopAll()100%2100%
get_Comparer()100%1100%
.ctor(...)100%1100%
Compare(...)100%1100%
SiftUp(...)100%4100%
SiftDown(...)100%14100%
RootIndex()100%2100%
LastLeafIndex()100%2100%
NextLeafIndex()100%2100%
ParentOf(...)100%4100%
LeftChildOf(...)100%6100%
RightChildOf(...)100%6100%
get_ListCount()100%1100%
get_Item(...)100%1100%
set_Item(...)100%1100%
Clear()100%2100%
GetEnumerator()100%1100%

File(s)

/home/runner/work/MoreStructures/MoreStructures/MoreStructures/PriorityQueues/BinaryHeap/BinaryHeapListWrapper.cs

#LineLine coverage
 1using MoreLinq.Extensions;
 2
 3namespace MoreStructures.PriorityQueues.BinaryHeap;
 4
 5/// <summary>
 6/// A wrapper around a <see cref="IList{T}"/>, which preserve the max heap property on the subset of items of the list,
 7/// at the beginning or at the end of it.
 8/// </summary>
 9/// <typeparam name="T">The type of items in the wrapped list.</typeparam>
 10/// <remarks>
 11/// Heap items are either stored:
 12/// <br/>
 13/// - from index 0 to <see cref="HeapCount"/> - 1, i.e. at the beginning of the list,
 14///   <br/>
 15/// - or from index <see cref="ListCount"/> - <see cref="HeapCount"/> to <see cref="ListCount"/> - 1, i.e. at the end.
 16///   <br/>
 17/// That leaves a buffer of <see cref="ListCount"/> - <see cref="HeapCount"/> items, either at the end or at the
 18/// beginning of the list.
 19/// <br/>
 20/// The functionalities of this wrapper can be used to support HeapSort or a priority queue based on a Max Binary Heap.
 21/// <br/>
 22/// In the first case the buffer area is used (to store already sorted items). In the second case it is not.
 23/// </remarks>
 24public sealed class BinaryHeapListWrapper<T>
 25{
 53539026    private IList<T> Items { get; }
 18427927    private IComparer<T> Comparer { get; }
 43374728    private bool StoreHeapAtTheEnd { get; }
 21409329    private int IndexDelta { get; }
 30
 31    /// <summary>
 32    /// The number of items in the heap only, buffer area of the underlying list excluded.
 33    /// </summary>
 34    /// <remarks>
 35    /// May be smaller than the current <see cref="ICollection{T}.Count"/> of the underlying <see cref="IList{T}"/>,
 36    /// which in turn may be smaller than the current Length of the underlying <see cref="Array"/>.
 37    /// </remarks>
 27011738    public int HeapCount { get; private set; }
 39
 40    /// <summary>
 41    /// Invoked just after an item has been pushed into <see cref="Items"/> (at the end of the heap), and before the
 42    /// "sifting up" procedure is performed.
 43    /// </summary>
 44    /// <remarks>
 45    /// The actual index of the item pushed will be different than <see cref="ListCount"/> - 1, if
 46    /// <see cref="ListCount"/> is different than <see cref="HeapCount"/>, or if the heap is stored in reverse.
 47    /// </remarks>
 3044548    public Action<int> RaiseItemPushed { get; init; } = i => { };
 49
 50    /// <summary>
 51    /// Invoked just before an item is removed from <see cref="Items"/> (at the beginning of the heap), and before
 52    /// "sifting down" procedure is performed.
 53    /// </summary>
 54    /// <remarks>
 55    /// The actual index of the item pushed may be different than 0, if the heap is stored in reverse, in which case
 56    /// it is equal to <see cref="ListCount"/> - 1.
 57    /// <br/>
 58    /// Same applies to the index of the item pushed out of the heap (but still in the list, in the buffer area).
 59    /// </remarks>
 2466060    public Action<int, int> RaiseItemPopping { get; init; } = (i1, i2) => { };
 61
 62    /// <summary>
 63    /// Invoked just after two items have been swapped of position in <see cref="Items"/>.
 64    /// </summary>
 7714165    public Action<int, int> RaiseItemsSwapped { get; init; } = (i1, i2) => { };
 66
 67
 68    /// <summary>
 69    ///     <inheritdoc cref="BinaryHeapListWrapper{T}"/>
 70    ///     <br/>
 71    ///     Built around the provided <see cref="IList{T}"/> <paramref name="items"/>.
 72    /// </summary>
 73    /// <param name="items">The <see cref="IList{T}"/> of items to be wrapped.</param>
 74    /// <param name="comparer">The comparer to be used to establish a order relationship between items.</param>
 75    /// <param name="count">
 76    /// The size of the subset of <paramref name="items"/> to be kept in order according to the max heap property.
 77    /// <br/>
 78    /// Goes from index 0 to index <paramref name="count"/> - 1.
 79    /// <br/>
 80    /// Current size must be non-bigger than the <see cref="ICollection{T}.Count"/>.
 81    /// </param>
 82    /// <param name="storeHeapAtTheEnd">
 83    /// Whether heap items should be stored at the beginning or at the end of the <paramref name="items"/> list.
 84    /// <br/>
 85    /// By default heap items are stored at the beginning (root at index 0) and buffer are is at the end.
 86    /// </param>
 87    /// <param name="indexDelta">
 88    /// The delta, positive or negative, with which heap items will be stored in the <paramref name="items"/> list,
 89    /// w.r.t. the beginning (if <paramref name="storeHeapAtTheEnd"/> is <see langword="false"/>) or the end
 90    /// (if <paramref name="storeHeapAtTheEnd"/> is <see langword="true"/>) of the list.
 91    /// <br/>
 92    /// By default it is zero (i.e. no displacement).
 93    /// </param>
 600794    public BinaryHeapListWrapper(
 600795        IList<T> items, IComparer<T> comparer, int count, bool storeHeapAtTheEnd = false, int indexDelta = 0)
 600796    {
 600797        if (indexDelta < 0)
 298            throw new ArgumentException(
 299                $"Must be non-negative.", nameof(indexDelta));
 6005100        if (count < 0 || count + indexDelta > items.Count)
 86101            throw new ArgumentException(
 86102                $"Must be non-negative and at most size of {nameof(items)} - {nameof(indexDelta)}.", nameof(items));
 103
 5919104        Items = items;
 5919105        Comparer = comparer;
 5919106        HeapCount = count;
 5919107        StoreHeapAtTheEnd = storeHeapAtTheEnd;
 5919108        IndexDelta = indexDelta;
 109
 5919110        RestoreHeapProperty();
 5919111    }
 112
 113    /// <summary>
 114    ///     <inheritdoc cref="BinaryHeapListWrapper{T}"/>
 115    ///     <br/>
 116    ///     Built from the provided <see cref="BinaryHeapListWrapper{T}"/> <paramref name="source"/>.
 117    /// </summary>
 252118    public BinaryHeapListWrapper(BinaryHeapListWrapper<T> source)
 252119    {
 252120        Items = new List<T>(source.Items);
 252121        Comparer = source.Comparer;
 252122        HeapCount = source.HeapCount;
 252123        StoreHeapAtTheEnd = source.StoreHeapAtTheEnd;
 252124        IndexDelta = source.IndexDelta;
 125
 252126        RestoreHeapProperty();
 252127    }
 128
 129
 130    /// <summary>
 131    /// Restores the max heap property, ensuring that each node of the heap is at least as big as its children, if any.
 132    /// </summary>
 133    public void RestoreHeapProperty()
 6407134    {
 6407135        var rootIndex = RootIndex();
 6407136        var lastLeafIndex = LastLeafIndex();
 6407137        if (StoreHeapAtTheEnd)
 175138        {
 175139            var halfHeapIndex = Math.Max(lastLeafIndex, rootIndex - HeapCount / 2 - 1);
 1402140            for (var i = halfHeapIndex; i <= rootIndex; i++)
 526141                SiftDown(i);
 175142        }
 143        else
 6232144        {
 6232145            var halfHeapIndex = Math.Min(lastLeafIndex, rootIndex + HeapCount / 2 + 1);
 26556146            for (var i = halfHeapIndex; i >= rootIndex; i--)
 7046147                SiftDown(i);
 6232148        }
 6407149    }
 150
 151    /// <summary>
 152    /// Peeks the item with max priority from the root of the heap, if any.
 153    /// </summary>
 154    public T Peek()
 10277155    {
 10277156        if (HeapCount == 0)
 6157            throw new InvalidOperationException($"Can't {nameof(Peek)} on an empty heap.");
 10271158        return Items[RootIndex()];
 10271159    }
 160
 161    /// <summary>
 162    /// Pops the item with max priority from the root of the heap, if any, moving the last leaf to the now vacant root
 163    /// and sifting it down until the heap property is restored.
 164    /// </summary>
 165    /// <returns>The popped item.</returns>
 166    public T Pop()
 9810167    {
 9810168        if (HeapCount == 0)
 6169            throw new InvalidOperationException($"Can't {nameof(Pop)} on an empty heap.");
 170
 9804171        var rootHeapIndex = RootIndex();
 9804172        var lastHeapIndex = LastLeafIndex();
 173
 9804174        RaiseItemPopping(rootHeapIndex, lastHeapIndex);
 9804175        var result = Peek();
 176
 9804177        (Items[rootHeapIndex], Items[lastHeapIndex]) = (Items[lastHeapIndex], Items[rootHeapIndex]);
 9804178        HeapCount--;
 179
 9804180        if (HeapCount > 0)
 9212181            SiftDown(rootHeapIndex);
 9804182        return result;
 9804183    }
 184
 185    /// <summary>
 186    /// Pushes the provided <paramref name="item"/> into the heap, sifting it up until the max heap property is
 187    /// restored.
 188    /// </summary>
 189    /// <param name="item">The item to be added to the heap.</param>
 190    /// <param name="siftUp">
 191    ///     Whether the sift up procedure should be executed or not. By default it is set to <see langword="true"/>.
 192    ///     <br/>
 193    ///     If it is not executed, the max heap property will be temporary violated.
 194    ///     <br/>
 195    ///     The push may fail if the heap is stored at the back of the list and grows backwards (which is the layout
 196    ///     applied when <see cref="StoreHeapAtTheEnd"/> is set to <see langword="true"/>), if the buffer is empty
 197    ///     (i.e. if the last leaf of the heap has reached the front of the list, and adding a new leaf would require
 198    ///     adding an element before the position 0 of the list).
 199    ///     <br/>
 200    ///     The push never fails when the heap is stored at the front of the list and grows forwards, because the list
 201    ///     is able to grow at the back.
 202    /// </param>
 203    public void Push(T item, bool siftUp = true)
 16837204    {
 16837205        int index = NextLeafIndex();
 16837206        if (index >= 0 && index < ListCount)
 817207        {
 817208            Items[index] = item;
 817209        }
 210        else
 16020211        {
 16020212            if (StoreHeapAtTheEnd)
 66213                throw new InvalidOperationException(
 66214                    $"Cannot {nameof(Push)} on a heap which is stored at the end, when the buffer empty.");
 215
 15954216            Items.Add(item);
 15954217        }
 16771218        HeapCount++;
 16771219        RaiseItemPushed(index);
 220
 16771221        if (siftUp)
 14141222            SiftUp(index);
 16771223    }
 224
 225    /// <summary>
 226    /// Retrieves the item of the heap with priority <paramref name="k"/>, without extracting any of the items in the
 227    /// heap.
 228    /// </summary>
 229    /// <param name="k">The non-negative priority rank: 0 means highest priority, 1 second highest, etc.</param>
 230    /// <returns>
 231    /// The item with k-th highest priority if any, with <see langword="true"/> as valid flag.
 232    /// <br/>
 233    /// The default for <typeparamref name="T"/> otherwise, with <see langword="false"/> as valid flag.
 234    /// </returns>
 235    public (T? result, bool valid) PeekKth(int k)
 48236    {
 50237        if (k < 0) throw new ArgumentException("Must be non-negative.", nameof(k));
 54238        if (k >= HeapCount) return (default, false);
 47239        if (k == 0) return (Peek(), true);
 240
 29241        var candidates = new BinaryHeapListWrapper<(int, T)>(new List<(int, T)>(), new Item2Comparer(Comparer), 0);
 29242        var rootIndex = RootIndex();
 29243        candidates.Push((rootIndex, Items[rootIndex]));
 142244        while (k > 0)
 113245        {
 113246            var (maxIndex, _) = candidates.Pop();
 247
 113248            var leftChildIndex = LeftChildOf(maxIndex);
 113249            if (leftChildIndex >= 0)
 87250                candidates.Push((leftChildIndex, Items[leftChildIndex]));
 251
 113252            var rightChildIndex = RightChildOf(maxIndex);
 113253            if (rightChildIndex >= 0)
 75254                candidates.Push((rightChildIndex, Items[rightChildIndex]));
 255
 113256            k--;
 113257        }
 258
 29259        return (Items[candidates.Peek().Item1], true);
 46260    }
 261
 262    /// <summary>
 263    /// Pops all items of the heap in sequence, from the one with highest priority to the one with lowest priority.
 264    /// </summary>
 265    /// <returns>A sequence of <typeparamref name="T"/> instances.</returns>
 266    public IEnumerable<T> PopAll()
 134267    {
 1094268        while (HeapCount > 0)
 960269            yield return Pop();
 134270    }
 271
 312272    private sealed record Item2Comparer(IComparer<T> Comparer) : IComparer<(int, T)>
 29273    {
 254274        public int Compare((int, T) x, (int, T) y) => Comparer.Compare(x.Item2, y.Item2);
 29275    }
 276
 277    /// <summary>
 278    /// Restores the heap constraint on the item at the specified <paramref name="nodeIndex"/> w.r.t. its ancestors in
 279    /// the tree.
 280    /// </summary>
 281    /// <param name="nodeIndex">The index of the item to check.</param>
 282    internal void SiftUp(int nodeIndex)
 22451283    {
 22451284        var parentIndex = ParentOf(nodeIndex);
 285
 286        // If the node doesn't have a parent, it means we reached the root of the tree, so there is nothing to sift up.
 22451287        if (parentIndex < 0)
 6940288            return;
 289
 15511290        var parentValue = Items[parentIndex];
 15511291        var nodeValue = Items[nodeIndex];
 15511292        if (Comparer.Compare(parentValue, nodeValue) < 0)
 8169293        {
 8169294            Items[parentIndex] = nodeValue;
 8169295            Items[nodeIndex] = parentValue;
 8169296            RaiseItemsSwapped(parentIndex, nodeIndex);
 297
 8169298            SiftUp(parentIndex);
 8169299        }
 22451300    }
 301
 302    /// <summary>
 303    /// Restores the heap constraint on the item at the specified <paramref name="nodeIndex"/> w.r.t. its descendants
 304    /// in the tree.
 305    /// </summary>
 306    /// <param name="nodeIndex">The index of the item to check.</param>
 307    private void SiftDown(int nodeIndex)
 70720308    {
 70720309        var leftChildIndex = LeftChildOf(nodeIndex);
 310
 311        // If the node doesn't have a left child, it definitely has no right child, since the tree is complete.
 312        // Therefore the node is a leaf and there is nothing to sift down.
 70720313        if (leftChildIndex < 0)
 9835314            return;
 315
 60885316        var leftChildValue = Items[leftChildIndex];
 317
 60885318        var rightChildIndex = RightChildOf(nodeIndex);
 319
 320        // Cases where heap property is respected: node > left > right, node > right > left
 321        // Cases where heap property has to be restored:
 322        // - left > node and no right or left >= right => left becomes the new parent of node and right
 323        // - right > node and right > left => right becomes the new parent of left and node
 60885324        var nodeValue = Items[nodeIndex];
 60885325        if (Comparer.Compare(leftChildValue, nodeValue) > 0 &&
 60885326            (rightChildIndex < 0 || Comparer.Compare(leftChildValue, Items[rightChildIndex]) >= 0))
 28873327        {
 28873328            Items[nodeIndex] = leftChildValue;
 28873329            Items[leftChildIndex] = nodeValue;
 28873330            RaiseItemsSwapped(nodeIndex, leftChildIndex);
 331
 28873332            SiftDown(leftChildIndex);
 28873333        }
 32012334        else if (rightChildIndex >= 0 &&
 32012335            Comparer.Compare(Items[rightChildIndex], nodeValue) > 0 &&
 32012336            Comparer.Compare(Items[rightChildIndex], leftChildValue) > 0)
 25063337        {
 25063338            Items[nodeIndex] = Items[rightChildIndex];
 25063339            Items[rightChildIndex] = nodeValue;
 25063340            RaiseItemsSwapped(nodeIndex, rightChildIndex);
 341
 25063342            SiftDown(rightChildIndex);
 25063343        }
 70720344    }
 345
 213841346    private int RootIndex() => StoreHeapAtTheEnd ? ListCount - 1 - IndexDelta : IndexDelta;
 33048347    private int LastLeafIndex() => RootIndex() + (StoreHeapAtTheEnd ? 1 - HeapCount : HeapCount - 1);
 16837348    private int NextLeafIndex() => LastLeafIndex() + (StoreHeapAtTheEnd ? -1 : +1);
 349
 350    private int ParentOf(int nodeIndex)
 22451351    {
 22451352        var rootIndex = RootIndex();
 29391353        if (nodeIndex == rootIndex) return -1;
 354
 15511355        if (StoreHeapAtTheEnd)
 232356            return rootIndex - (rootIndex - nodeIndex - 1) / 2;
 15279357        return rootIndex + (nodeIndex - rootIndex - 1) / 2;
 22451358    }
 359
 360    private int LeftChildOf(int nodeIndex)
 70833361    {
 70833362        var rootIndex = RootIndex();
 363        int childIndex;
 70833364        if (StoreHeapAtTheEnd)
 1685365        {
 1685366            childIndex = rootIndex - 2 * (rootIndex - nodeIndex) - 1;
 1685367            return childIndex > rootIndex - HeapCount ? childIndex : -1;
 368        }
 369
 69148370        childIndex = rootIndex + 2 * (nodeIndex - rootIndex) + 1;
 69148371        return childIndex < rootIndex + HeapCount ? childIndex : -1;
 70833372    }
 373
 374    private int RightChildOf(int nodeIndex)
 60998375    {
 60998376        var rootIndex = RootIndex();
 377        int childIndex;
 60998378        if (StoreHeapAtTheEnd)
 1008379        {
 1008380            childIndex = rootIndex - 2 * (rootIndex - nodeIndex) - 2;
 1008381            return childIndex > rootIndex - HeapCount ? childIndex : -1;
 382        }
 383
 59990384        childIndex = rootIndex + 2 * (nodeIndex - rootIndex) + 2;
 59990385        return childIndex < rootIndex + HeapCount ? childIndex : -1;
 60998386    }
 387
 388    #region Access to Underlying List<T>
 389
 390    /// <summary>
 391    /// The number of items in the underlying list, heap and buffer are included.
 392    /// </summary>
 393    /// <remarks>
 394    /// It's always non-smaller than <see cref="HeapCount"/>, since all the heap items are contained in the underlying
 395    /// list.
 396    /// </remarks>
 23149397    public int ListCount => Items.Count;
 398
 399    /// <summary>
 400    /// Retrieves the <paramref name="index"/>-th item in the underlying list (heap or buffer).
 401    /// </summary>
 402    /// <param name="index">
 403    /// A non-negative <see cref="int"/>. It can be non-smaller than <see cref="HeapCount"/>, if an element of the
 404    /// buffer is being accessed, but it necessarily has to be smaller than the <see cref="ICollection{T}.Count"/> of
 405    /// the underlying <see cref="IList{T}"/>.
 406    /// </param>
 407    /// <returns>The item, an instance of type <typeparamref name="T"/>.</returns>
 408    public T this[int index]
 409    {
 34573410        get => Items[index];
 337411        set => Items[index] = value;
 412    }
 413
 414    /// <summary>
 415    /// Clears the underlying list (heap and buffer), wiping all its items out, if the list is not readonly.
 416    /// <br/>
 417    /// If it is readonly (e.g. an array), it just resets the <see cref="HeapCount"/>.
 418    /// </summary>
 419    public void Clear()
 349420    {
 349421        if (!Items.IsReadOnly)
 347422            Items.Clear();
 349423        HeapCount = 0;
 349424    }
 425
 426    /// <summary>
 427    /// Returns an enumerator of <typeparamref name="T"/> instances, going through all items of the underlying list,
 428    /// not just the first <see cref="HeapCount"/> items which form the heap, but also the buffer area at the end of the
 429    /// underlying list.
 430    /// </summary>
 431    /// <returns>An <see cref="IEnumerable{T}"/> of <typeparamref name="T"/>.</returns>
 238432    public IEnumerator<T> GetEnumerator() => Items.GetEnumerator();
 433
 434    #endregion
 435}
Generated by: ReportGenerator 5.1.19.0
03/19/2023 - 17:28:50
GitHub | reportgenerator.io

Methods/Properties

get_Items()
get_Comparer()
get_StoreHeapAtTheEnd()
get_IndexDelta()
get_HeapCount()
get_RaiseItemPushed()
get_RaiseItemPopping()
get_RaiseItemsSwapped()
.ctor(System.Collections.Generic.IList`1<T>,System.Collections.Generic.IComparer`1<T>,System.Int32,System.Boolean,System.Int32)
.ctor(MoreStructures.PriorityQueues.BinaryHeap.BinaryHeapListWrapper`1<T>)
RestoreHeapProperty()
Peek()
Pop()
Push(T,System.Boolean)
PeekKth(System.Int32)
PopAll()
get_Comparer()
.ctor(System.Collections.Generic.IComparer`1<T>)
Compare(System.ValueTuple`2<System.Int32,T>,System.ValueTuple`2<System.Int32,T>)
SiftUp(System.Int32)
SiftDown(System.Int32)
RootIndex()
LastLeafIndex()
NextLeafIndex()
ParentOf(System.Int32)
LeftChildOf(System.Int32)
RightChildOf(System.Int32)
get_ListCount()
get_Item(System.Int32)
set_Item(System.Int32,T)
Clear()
GetEnumerator()