< Summary

Information
Class: MoreStructures.PriorityQueues.FibonacciHeap.UpdatableFibonacciHeapPriorityQueue<T>
Assembly: MoreStructures
File(s): /home/runner/work/MoreStructures/MoreStructures/MoreStructures/PriorityQueues/FibonacciHeap/UpdatableFibonacciHeapPriorityQueue.cs
Line coverage
100%
Covered lines: 72
Uncovered lines: 0
Coverable lines: 72
Total lines: 227
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%
UpdatePriority(...)100%6100%
UpdateRootPriority(...)100%2100%
UpdateNonRootPriority(...)100%8100%

File(s)

/home/runner/work/MoreStructures/MoreStructures/MoreStructures/PriorityQueues/FibonacciHeap/UpdatableFibonacciHeapPriorityQueue.cs

#LineLine coverage
 1using MoreStructures.PriorityQueues.BinomialHeap;
 2
 3namespace MoreStructures.PriorityQueues.FibonacciHeap;
 4
 5/// <summary>
 6/// A refinement of <see cref="FibonacciHeapPriorityQueue{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 UpdatableFibonacciHeapPriorityQueue<T> : FibonacciHeapPriorityQueue<T>, IUpdatablePriorityQueue<T>
 15    where T : notnull
 16{
 746017    private DuplicatedItemsResolution<T, FibonacciHeapPriorityQueue<int>> DuplicatedItemsResolution { get; } = new();
 18
 19    #region Public API
 20
 21    /// <inheritdoc path="//*[not(self::remarks)]"/>
 22    /// <remarks>
 23    /// Clears the <see cref="FibonacciHeapPriorityQueue{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    ///     - Both <see cref="BinomialHeapPriorityQueue{T}.Peek"/> and <see cref="UpdatePriority(T, int)"/> have
 58    ///       constant Time and Space Complexity (update having constant amortized complexity).
 59    ///       <br/>
 60    ///     - However, <see cref="BinomialHeapPriorityQueue{T}.Pop"/> has 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)
 26166    {
 26167        if (Count == 0)
 7568            return null;
 18669        var maxPrioritizedItem = Peek();
 18670        var treeNodeInFibonacciHeap = DuplicatedItemsResolution.FindTreeNode(item);
 18671        if (treeNodeInFibonacciHeap == null)
 15072            return null;
 73
 3674        var oldPrioritizedItem = treeNodeInFibonacciHeap.PrioritizedItem;
 3675        UpdatePriority(treeNodeInFibonacciHeap, maxPrioritizedItem.Priority + 1, oldPrioritizedItem.PushTimestamp);
 3676        Pop();
 3677        return oldPrioritizedItem;
 26178    }
 79
 80    /// <inheritdoc path="//*[not(self::remarks)]"/>
 81    /// <remarks>
 82    ///     <inheritdoc cref="DuplicatedItemsResolution{T, THeap}.FindTreeNode(T)"/>
 83    ///     <para id="algorithm-update">
 84    ///     ALGORITHM - FIBONACCI HEAP UPDATE PART
 85    ///     <br/>
 86    ///     - The algorith behaves quite differently, depending on whether the new priority for the specified item is
 87    ///       higher or equal than P, as opposed to when it's lower.
 88    ///       <br/>
 89    ///     - When the priority is higher or equal and the node is a root, there is no structural change to the heap.
 90    ///       The value of priority is updated and the reference to the max priority is checked and potentially
 91    ///       updated.
 92    ///       <br/>
 93    ///     - When the priority is higher or equal and the node is not a root, the node is promoted to a root and its
 94    ///       loser flag is reset. If the parent of the node was flagged as a loser, the parent is promoted to root
 95    ///       too, and its loser flag is reset as well. That continues up to the first ancestor which is not a loser.
 96    ///       <br/>
 97    ///     - When the priority is lower, the node is not promoted to a root. Its children are, instead. As in the
 98    ///       <see cref="BinomialHeapPriorityQueue{T}.Pop"/>, merging and max root reference update take place.
 99    ///       <br/>
 100    ///     - Finally, the <see cref="PrioritizedItem{T}"/> before the update is returned as result.
 101    ///     </para>
 102    ///     <para id="complexity-update">
 103    ///     COMPLEXITY - FIBONACCI HEAP UPDATE PART
 104    ///     <br/>
 105    ///     - The complexity is different depending on the value of new priority for the specified item being higher
 106    ///       or equal than the highest in the queue for that item, or lower.
 107    ///       <br/>
 108    ///     - When the value is bigger or equal than P, Time and Space Complexity are O(1), amortized.
 109    ///       <br/>
 110    ///     - When the value is smaller than P, Time Complexity and Space Complexity are both O(log(n)). Same analysis
 111    ///       as for <see cref="BinomialHeapPriorityQueue{T}.Pop"/> applies (since very similar operations are
 112    ///       performed).
 113    ///     </para>
 114    ///     <para id="complexity">
 115    ///     COMPLEXITY - OVERALL
 116    ///     <br/>
 117    ///     - When the value is bigger or equal than P, Time Complexity is O(dup_factor) and Space Complexity is O(1),
 118    ///       amortized.
 119    ///       <br/>
 120    ///     - When the value is smaller than P, Time Complexity is O(log(n) + dup_factor) and Space Complexity is O(1).
 121    ///     </para>
 122    /// </remarks>
 123    public PrioritizedItem<T> UpdatePriority(T item, int newPriority)
 102124    {
 102125        var treeNodeInFibonacciHeap = DuplicatedItemsResolution.FindTreeNode(item);
 102126        if (treeNodeInFibonacciHeap == null)
 3127            throw new InvalidOperationException("The specified item is not in the queue.");
 99128        return UpdatePriority(treeNodeInFibonacciHeap, newPriority, CurrentPushTimestamp++);
 99129    }
 130
 131    #endregion
 132
 133    #region Hooks
 134
 135    /// <inheritdoc cref="UpdatableBinomialHeapPriorityQueue{T}.RaiseItemPushed"/>
 136    protected override void RaiseItemPushed(TreeNode<T> newRoot) =>
 5144137        DuplicatedItemsResolution.RaiseItemPushed(newRoot);
 138
 139    /// <inheritdoc cref="UpdatableBinomialHeapPriorityQueue{T}.RaiseItemPopping"/>
 140    protected override void RaiseItemPopping(TreeNode<T> root) =>
 1452141        DuplicatedItemsResolution.RaiseItemPopping(root);
 142
 143    /// <inheritdoc cref="UpdatableBinomialHeapPriorityQueue{T}.RaiseItemPriorityChanged"/>
 144    private void RaiseItemPriorityChanged(TreeNode<T> treeNode, PrioritizedItem<T> itemBefore) =>
 135145        DuplicatedItemsResolution.RaiseItemPriorityChanged(treeNode, itemBefore);
 146
 147    #endregion
 148
 149    #region Helpers
 150
 151    private PrioritizedItem<T> UpdatePriority(TreeNode<T> treeNode, int newPriority, int newPushTimestamp)
 135152    {
 135153        var newPrioritizedItem =
 135154            new PrioritizedItem<T>(treeNode.PrioritizedItem.Item, newPriority, newPushTimestamp, PushTimestampEras[^1]);
 135155        var oldPrioritizedItem = treeNode.PrioritizedItem;
 135156        treeNode.PrioritizedItem = newPrioritizedItem;
 157
 135158        RaiseItemPriorityChanged(treeNode, oldPrioritizedItem);
 159
 160        // Remark: due to push timestamps, priorities can never be equal: only strictly lower or strictly higher
 135161        if (oldPrioritizedItem.CompareTo(newPrioritizedItem) <= 0)
 75162        {
 75163            if (treeNode.RootsListNode is not null)
 35164                UpdateRootPriority(treeNode, newPrioritizedItem);
 165            else
 40166                UpdateNonRootPriority(treeNode);
 75167        }
 168        else
 60169        {
 362170            foreach (var child in treeNode.Children.ToList())
 91171                PromoteChildToRoot(child);
 172
 60173            MergeEquiDegreeTrees();
 60174            UpdateMaxRootsListNode();
 60175        }
 176
 135177        return oldPrioritizedItem;
 135178    }
 179
 180    private void UpdateRootPriority(
 181        TreeNode<T> treeNode, PrioritizedItem<T> newPrioritizedItem)
 35182    {
 183        // The item is at the root of a tree and the new priority is higher => the heap constraints on the tree
 184        // are not violated, so just check and possibly update the reference to the root with max priority.
 35185        if (MaxRootsListNode!.Value.PrioritizedItem.CompareTo(newPrioritizedItem) < 0)
 6186            MaxRootsListNode = treeNode.RootsListNode;
 35187    }
 188
 189    private void UpdateNonRootPriority(TreeNode<T> treeNode)
 40190    {
 191        // The item is not at the root of a tree and the new priority is higher => the heap constraints on the
 192        // sub-tree of the item are not violated, by the transitivity of max.
 193        // However, the heap constraints on the items of the tree above the item may be violated.
 194        // So promote the child to root.
 40195        var parentNode = treeNode.Parent;
 40196        PromoteChildToRoot(treeNode);
 197
 198        // If the new root, with increased priority, has a priority higher than the current max, update the reference
 199        // to the root with max priority, to point to the new root.
 40200        if (MaxRootsListNode!.Value.PrioritizedItem.CompareTo(treeNode.PrioritizedItem) < 0)
 18201            MaxRootsListNode = treeNode.RootsListNode;
 202
 203        // Now, focus on the ancenstors of the disowned child: if its parent has already lost a child before (i.e.
 204        // it's in the losers set), it's itself promoted to the root. Same applies to the grand-parent and so on,
 205        // up until the first ancenstor which is not a loser, or the root.
 40206        var ancestorNode = parentNode;
 47207        while (ancestorNode != null)
 47208        {
 47209            if (ancestorNode.IsALoser)
 11210            {
 11211                var parentOfAncestorNode = ancestorNode.Parent;
 11212                if (parentOfAncestorNode == null)
 4213                    break;
 214
 7215                PromoteChildToRoot(ancestorNode);
 7216                ancestorNode = parentOfAncestorNode;
 7217            }
 218            else
 36219            {
 36220                ancestorNode.IsALoser = true;
 36221                break;
 222            }
 7223        }
 40224    }
 225
 226    #endregion
 227}
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>)
UpdatePriority(MoreStructures.PriorityQueues.BinomialHeap.TreeNode`1<T>,System.Int32,System.Int32)
UpdateRootPriority(MoreStructures.PriorityQueues.BinomialHeap.TreeNode`1<T>,MoreStructures.PriorityQueues.PrioritizedItem`1<T>)
UpdateNonRootPriority(MoreStructures.PriorityQueues.BinomialHeap.TreeNode`1<T>)