< Summary

Information
Class: MoreStructures.PriorityQueues.BinomialHeap.UpdatableBinomialHeapPriorityQueue<T>
Assembly: MoreStructures
File(s): /home/runner/work/MoreStructures/MoreStructures/MoreStructures/PriorityQueues/BinomialHeap/UpdatableBinomialHeapPriorityQueue.cs
Line coverage
100%
Covered lines: 67
Uncovered lines: 0
Coverable lines: 67
Total lines: 233
Line coverage: 100%
Branch coverage
100%
Covered branches: 22
Total branches: 22
Branch coverage: 100%
Method coverage

Feature is only available for sponsors

Upgrade to PRO version

Metrics

MethodBranch coverage Cyclomatic complexity Line coverage
get_DuplicatedItemsResolution()100%1100%
Clear()100%1100%
GetPrioritiesOf(...)100%1100%
Remove(...)100%4100%
UpdatePriority(...)100%2100%
RaiseItemPushed(...)100%1100%
RaiseItemPopping(...)100%1100%
RaiseItemPriorityChanged(...)100%1100%
RaiseItemsSwapped(...)100%1100%
UpdatePriority(...)100%2100%
SiftUp(...)100%6100%
SiftDown(...)100%8100%

File(s)

/home/runner/work/MoreStructures/MoreStructures/MoreStructures/PriorityQueues/BinomialHeap/UpdatableBinomialHeapPriorityQueue.cs

#LineLine coverage
 1using MoreStructures.PriorityQueues.FibonacciHeap;
 2
 3namespace MoreStructures.PriorityQueues.BinomialHeap;
 4
 5/// <summary>
 6/// A refinement of <see cref="BinomialHeapPriorityQueue{T}"/> which supports <see cref="IUpdatablePriorityQueue{T}"/>
 7/// operations, such as retrieval and update of priorities and removal of items.
 8/// </summary>
 9/// <remarks>
 10/// Check <see cref="DuplicatedItemsResolution{T, THeap}"/> for detailed informations about how the mapping between
 11/// items of type <typeparamref name="T"/> and heap nodes of type <see cref="TreeNode{T}"/> is performed, in presence
 12/// of duplicates.
 13/// </remarks>
 14public sealed class UpdatableBinomialHeapPriorityQueue<T> : BinomialHeapPriorityQueue<T>, IUpdatablePriorityQueue<T>
 15    where T : notnull
 16{
 1389517    private DuplicatedItemsResolution<T, BinomialHeapPriorityQueue<int>> DuplicatedItemsResolution { get; } = new();
 18
 19    #region Public API
 20
 21    /// <inheritdoc path="//*[not(self::remarks)]"/>
 22    /// <remarks>
 23    /// Clears the <see cref="BinomialHeapPriorityQueue{T}"/> structures and the additional
 24    /// <see cref="DuplicatedItemsResolution{TItems, THeap}"/> object introduced to support updates and deletions.
 25    /// <br/>
 26    /// Time and Space Complexity is O(1).
 27    /// </remarks>
 28    public override void Clear()
 17129    {
 17130        base.Clear();
 17131        DuplicatedItemsResolution.Clear();
 17132    }
 33
 34    /// <inheritdoc path="//*[not(self::remarks)]"/>
 35    /// <remarks>
 36    ///     <inheritdoc cref="DuplicatedItemsResolution{T, THeap}.GetPrioritiesOf(T)"/>
 37    /// </remarks>
 2438    public IEnumerable<int> GetPrioritiesOf(T item) => DuplicatedItemsResolution.GetPrioritiesOf(item);
 39
 40    /// <inheritdoc path="//*[not(self::remarks)]"/>
 41    /// <remarks>
 42    ///     <para id="algorithm">
 43    ///     ALGORITHM
 44    ///     <br/>
 45    ///     - It first retrieves the max priority P from the max priority item the queue via
 46    ///       <see cref="BinomialHeapPriorityQueue{T}.Peek"/>.
 47    ///       <br/>
 48    ///     - Then, it updates the priority of the provided <paramref name="item"/> via
 49    ///       <see cref="UpdatePriority(T, int)"/>, setting it to P + 1 and making <paramref name="item"/> the one with
 50    ///       max priority.
 51    ///       <br/>
 52    ///     - Finally it pops the <paramref name="item"/> via <see cref="BinomialHeapPriorityQueue{T}.Pop"/>.
 53    ///     </para>
 54    ///     <para id="complexity">
 55    ///     COMPLEXITY
 56    ///     <br/>
 57    ///     - <see cref="BinomialHeapPriorityQueue{T}.Peek"/> has constant Time and Space Complexity.
 58    ///       <br/>
 59    ///     - However, <see cref="BinomialHeapPriorityQueue{T}.Pop"/> and <see cref="UpdatePriority(T, int)"/> have
 60    ///       logarithmic Time Complexity.
 61    ///       <br/>
 62    ///     - Therefore, Time Complexity is O(log(n) + dup_factor) and Space Complexity is O(1).
 63    ///     </para>
 64    /// </remarks>
 65    public PrioritizedItem<T>? Remove(T item)
 291066    {
 291067        if (Count == 0)
 192368            return null;
 69
 98770        var maxPrioritizedItem = Peek();
 98771        var treeNodeInBinomialHeap = DuplicatedItemsResolution.FindTreeNode(item);
 98772        if (treeNodeInBinomialHeap == null)
 86573            return null;
 74
 12275        var oldPrioritizedItem = treeNodeInBinomialHeap.PrioritizedItem;
 12276        UpdatePriority(treeNodeInBinomialHeap, maxPrioritizedItem.Priority + 1, oldPrioritizedItem.PushTimestamp);
 12277        Pop();
 12278        return oldPrioritizedItem;
 291079    }
 80
 81    /// <inheritdoc path="//*[not(self::remarks)]"/>
 82    /// <remarks>
 83    ///     <inheritdoc cref="DuplicatedItemsResolution{T, THeap}.FindTreeNode(T)"/>
 84    ///     <para id="algorithm-update">
 85    ///     ALGORITHM - BINOMIAL HEAP UPDATE PART
 86    ///     <br/>
 87    ///     - When the priority is higher or equal, the value of priority is updated and the node is sifted up the
 88    ///       tree, until the heap property is restored. If the root of the tree is reached, the reference to the max
 89    ///       priority is checked and potentially updated.
 90    ///       <br/>
 91    ///     - When the priority is lower, the value of priority is updated and the node is sifted down the tree, until
 92    ///       the heap property is restored. If the node was a root, a linear scan of all the roots is made, to update
 93    ///       the reference to the max priority, which may have changed due to the decrease in priority.
 94    ///       <br/>
 95    ///     - No merging is required, since no node has been added or removed from any of the tree of the heap forest.
 96    ///       Nodes have been swapped by sift up or sift down procedures, but the shape of each tree, and so the
 97    ///       layout of the forest, hasn't changed. Therefore the binomial heap shape hasn't been violated.
 98    ///       <br/>
 99    ///     - Finally, the <see cref="PrioritizedItem{T}"/> before the update is returned as result.
 100    ///     </para>
 101    ///     <para id="complexity-update">
 102    ///     COMPLEXITY - BINOMIAL HEAP UPDATE PART
 103    ///     <br/>
 104    ///     - Sift up, sift down and linear scan of roots are all logarithmic operations in time and constant in space.
 105    ///       <br/>
 106    ///     - Therefore, Time Complexity is O(log(n)) and Space Complexity is O(1).
 107    ///     </para>
 108    ///     <para id="complexity">
 109    ///     COMPLEXITY - OVERALL
 110    ///     <br/>
 111    ///     - Time Complexity is O(log(n) + dup_factor) and Space Complexity is O(1).
 112    ///       <br/>
 113    ///     - Notice how this is higher than the Time Complexity for the corresponding functionality in a Fibonacci
 114    ///       Heap, which supports both pushing and priority updating in constant time.
 115    ///     </para>
 116    /// </remarks>
 117    public PrioritizedItem<T> UpdatePriority(T item, int newPriority)
 93118    {
 93119        var treeNodeInBinomialHeap = DuplicatedItemsResolution.FindTreeNode(item);
 93120        if (treeNodeInBinomialHeap == null)
 3121            throw new InvalidOperationException("The specified item is not in the queue.");
 90122        return UpdatePriority(treeNodeInBinomialHeap, newPriority, CurrentPushTimestamp++);
 90123    }
 124
 125    #endregion
 126
 127    #region Hooks
 128
 129    /// <inheritdoc path="//*[not(self::remarks)]"/>
 130    /// <remarks>
 131    /// Hands over to <see cref="DuplicatedItemsResolution{T, THeap}.RaiseItemPushed(TreeNode{T})"/>.
 132    /// </remarks>
 133    protected override void RaiseItemPushed(TreeNode<T> newRoot) =>
 6769134        DuplicatedItemsResolution.RaiseItemPushed(newRoot);
 135
 136    /// <inheritdoc path="//*[not(self::remarks)]"/>
 137    /// <remarks>
 138    /// Hands over to <see cref="DuplicatedItemsResolution{T, THeap}.RaiseItemPopping(TreeNode{T})"/>.
 139    /// </remarks>
 140    protected override void RaiseItemPopping(TreeNode<T> root) =>
 3792141        DuplicatedItemsResolution.RaiseItemPopping(root);
 142
 143    /// <summary>
 144    /// Invoked just after the priority of the <see cref="PrioritizedItem{T}"/> of a <see cref="TreeNode{T}"/> in the
 145    /// heap has changed.
 146    /// </summary>
 147    /// <param name="treeNode">The node whose item has changed priority.</param>
 148    /// <param name="itemBefore">The <see cref="PrioritizedItem{T}"/> as it was before the change.</param>
 149    /// <remarks>
 150    /// Hands over to
 151    /// <see cref="DuplicatedItemsResolution{T, THeap}.RaiseItemPriorityChanged(TreeNode{T}, PrioritizedItem{T})"/>.
 152    /// </remarks>
 153    private void RaiseItemPriorityChanged(TreeNode<T> treeNode, PrioritizedItem<T> itemBefore) =>
 212154        DuplicatedItemsResolution.RaiseItemPriorityChanged(treeNode, itemBefore);
 155
 156    /// <summary>
 157    /// Invoked just after two items have had their <see cref="PrioritizedItem{T}"/> swapped.
 158    /// </summary>
 159    /// <param name="treeNode1">The first node.</param>
 160    /// <param name="treeNode2">The second node.</param>
 161    /// <remarks>
 162    /// Hands over to
 163    /// <see cref="DuplicatedItemsResolution{T, THeap}.RaiseItemsSwapped(TreeNode{T}, TreeNode{T})"/>.
 164    /// </remarks>
 165    private void RaiseItemsSwapped(TreeNode<T> treeNode1, TreeNode<T> treeNode2) =>
 107166        DuplicatedItemsResolution.RaiseItemsSwapped(treeNode1, treeNode2);
 167
 168    #endregion
 169
 170    #region Helpers
 171
 172    private PrioritizedItem<T> UpdatePriority(TreeNode<T> treeNode, int newPriority, int newPushTimestamp)
 212173    {
 212174        var newPrioritizedItem =
 212175            new PrioritizedItem<T>(treeNode.PrioritizedItem.Item, newPriority, newPushTimestamp, PushTimestampEras[^1]);
 212176        var oldPrioritizedItem = treeNode.PrioritizedItem;
 212177        treeNode.PrioritizedItem = newPrioritizedItem;
 178
 212179        RaiseItemPriorityChanged(treeNode, oldPrioritizedItem);
 180
 212181        if (newPrioritizedItem.CompareTo(oldPrioritizedItem) >= 0)
 152182            SiftUp(treeNode);
 183        else
 60184            SiftDown(treeNode);
 185
 212186        return oldPrioritizedItem;
 212187    }
 188
 189    private void SiftUp(TreeNode<T> treeNode)
 152190    {
 152191        var ancestor = treeNode;
 218192        while (
 218193            ancestor.Parent is TreeNode<T> ancestorParent &&
 218194            ancestorParent.PrioritizedItem.CompareTo(ancestor.PrioritizedItem) < 0)
 66195        {
 66196            (ancestor.PrioritizedItem, ancestorParent.PrioritizedItem) =
 66197                (ancestorParent.PrioritizedItem, ancestor.PrioritizedItem);
 66198            RaiseItemsSwapped(ancestor, ancestorParent);
 199
 66200            ancestor = ancestorParent;
 66201        }
 202
 203        // If we are in SiftUp, it means that the priority has increased. The SiftUp may have bubbled up the increase
 204        // up to the root of the tree. In such a case we need to check whether the new root has higher priority than
 205        // the current max priority root, and update it if necessary.
 152206        if (ancestor.RootsListNode != null)
 139207            UpdateMaxRootsListNodeAfterRootNewOrIncrease(ancestor.RootsListNode);
 152208    }
 209
 210    private void SiftDown(TreeNode<T> treeNode)
 60211    {
 60212        var descendant = treeNode;
 101213        while (
 141214            descendant.Children.MaxBy(c => c.PrioritizedItem) is TreeNode<T> descendantMaxChild &&
 101215            descendantMaxChild.PrioritizedItem.CompareTo(descendant.PrioritizedItem) > 0)
 41216        {
 41217            (descendant.PrioritizedItem, descendantMaxChild.PrioritizedItem) =
 41218                (descendantMaxChild.PrioritizedItem, descendant.PrioritizedItem);
 41219            RaiseItemsSwapped(descendant, descendantMaxChild);
 220
 41221            descendant = descendantMaxChild;
 41222        }
 223
 224        // If we are in SiftDown, it means that the priority has decreased. If the treeNode was a root, the SiftDown
 225        // may have moved the root down the tree, and promoted one of its child to being the root. And even if it
 226        // didn't happen, the root has now lower priority. So, if the max priority root was pointing to the root of
 227        // this tree, we need to update the current max priority root, performing a linear scan of the roots.
 60228        if (ReferenceEquals(MaxRootsListNode!.Value, treeNode))
 15229            UpdateMaxRootsListNode();
 60230    }
 231
 232    #endregion
 233}
Generated by: ReportGenerator 5.1.19.0
03/19/2023 - 17:28:50
GitHub | reportgenerator.io

Methods/Properties

get_DuplicatedItemsResolution()
Clear()
GetPrioritiesOf(T)
Remove(T)
UpdatePriority(T,System.Int32)
RaiseItemPushed(MoreStructures.PriorityQueues.BinomialHeap.TreeNode`1<T>)
RaiseItemPopping(MoreStructures.PriorityQueues.BinomialHeap.TreeNode`1<T>)
RaiseItemPriorityChanged(MoreStructures.PriorityQueues.BinomialHeap.TreeNode`1<T>,MoreStructures.PriorityQueues.PrioritizedItem`1<T>)
RaiseItemsSwapped(MoreStructures.PriorityQueues.BinomialHeap.TreeNode`1<T>,MoreStructures.PriorityQueues.BinomialHeap.TreeNode`1<T>)
UpdatePriority(MoreStructures.PriorityQueues.BinomialHeap.TreeNode`1<T>,System.Int32,System.Int32)
SiftUp(MoreStructures.PriorityQueues.BinomialHeap.TreeNode`1<T>)
SiftDown(MoreStructures.PriorityQueues.BinomialHeap.TreeNode`1<T>)