< Summary

Information
Class: MoreStructures.PriorityQueues.BinomialHeap.DuplicatedItemsResolution<T1, T2>
Assembly: MoreStructures
File(s): /home/runner/work/MoreStructures/MoreStructures/MoreStructures/PriorityQueues/BinomialHeap/DuplicatedItemsResolution.cs
Line coverage
100%
Covered lines: 50
Uncovered lines: 0
Coverable lines: 50
Total lines: 215
Line coverage: 100%
Branch coverage
100%
Covered branches: 18
Total branches: 18
Branch coverage: 100%
Method coverage

Feature is only available for sponsors

Upgrade to PRO version

Metrics

MethodBranch coverage Cyclomatic complexity Line coverage
get_ItemToPushTimestamps()100%1100%
get_PushTimestampToTreeNode()100%1100%
Clear()100%1100%
GetPrioritiesOf(...)100%6100%
FindTreeNode(...)100%10100%
RaiseItemPushed(...)100%2100%
RaiseItemPopping(...)100%1100%
RaiseItemPriorityChanged(...)100%1100%
RaiseItemsSwapped(...)100%1100%

File(s)

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

#LineLine coverage
 1namespace MoreStructures.PriorityQueues.BinomialHeap;
 2
 3/// <summary>
 4/// An object storing and keeping up-to-date the "<typeparamref name="TItems"/> to <see cref="TreeNode{T}"/>"
 5/// back-references, necessary to find back the <see cref="TreeNode{T}"/> in the heap with highest priority for a given
 6/// item, without exposing iterators to the client.
 7/// </summary>
 8/// <typeparam name="TItems"><inheritdoc cref="IPriorityQueue{T}"/></typeparam>
 9/// <typeparam name="THeap">
 10/// A type constructor for an heap of <see cref="int"/>. Needed to store all push timestamps for each item.
 11/// </typeparam>
 12/// <remarks>
 13/// In order to support updates and deletions of items, two additional data structures are introduced:
 14/// <br/>
 15/// - a <see cref="Dictionary{TKey, TValue}"/> Item2PT, mapping items <c>I</c> of type <typeparamref name="TItems"/> to
 16///   <typeparamref name="THeap"/> instances, containing <see cref="PrioritizedItem{T}.PushTimestamp"/>
 17///   values of type <see cref="int"/>, of <see cref="PrioritizedItem{T}"/> instances containing <c>I</c>.
 18///   <br/>
 19/// - a <see cref="Dictionary{TKey, TValue}"/> PT2Idx from <see cref="PrioritizedItem{T}.PushTimestamp"/> values to
 20///   <see cref="TreeNode{T}"/> of type <see cref="int"/>, into the backing <typeparamref name="THeap"/> structure of
 21///   this priority queue.
 22///   <br/>
 23/// <br/>
 24/// Every time a request to remove or update an item <c>I</c> from the priority queue is made, Item2PT is used to
 25/// retrieve all the <see cref="PrioritizedItem{T}.PushTimestamp"/> values of <see cref="PrioritizedItem{T}"/>
 26/// instances with item.
 27/// <br/>
 28/// Those push timestamps can be multiple because the same item can be added multiple times to the queue.
 29/// <br/>
 30/// The push timestamps are organized themselves in per-item priority queues, with the same priority as the items
 31/// in the main priority queue.
 32/// <br/>
 33/// This way, the push timestamp of highest priority for a given item can be peeked in constant time and extracted in
 34/// logarithmic time.
 35/// <br/>
 36/// Once the timestamp of highest priority has been found, the corresponding <see cref="TreeNode{T}"/> (if any) in the
 37/// backing <typeparamref name="THeap"/> structure of this priority queue can be found in constant time via the PT2Idx
 38/// dictionary.
 39/// </remarks>
 40public class DuplicatedItemsResolution<TItems, THeap>
 41    where TItems : notnull
 42    where THeap : IPriorityQueue<int>, new()
 43{
 2757144    private Dictionary<TItems, THeap> ItemToPushTimestamps { get; } = new();
 2099545    private Dictionary<int, TreeNode<TItems>> PushTimestampToTreeNode { get; } = new();
 46
 47    /// <summary>
 48    /// Clears the content of this object.
 49    /// </summary>
 50    public void Clear()
 34351    {
 34352        ItemToPushTimestamps.Clear();
 34353        PushTimestampToTreeNode.Clear();
 34354    }
 55
 56    /// <inheritdoc cref="IUpdatablePriorityQueue{T}.GetPrioritiesOf(T)" path="//*[not(self::remarks)]"/>
 57    /// <remarks>
 58    ///     <para id="algorithm">
 59    ///     ALGORITHM
 60    ///     <br/>
 61    ///     - First, the priority queue of push timestamps for the provided <paramref name="item"/> is retrieved from
 62    ///       the dictionary of per-item queues of push timestamps.
 63    ///       <br/>
 64    ///     - If such a queue is not found, <paramref name="item"/> is not present in the main priority queue, and an
 65    ///       empty sequence is returned.
 66    ///       <br/>
 67    ///     - Otherwise, the queue is iterated over, getting the <see cref="TreeNode{T}"/> corresponding to each
 68    ///       timestamp extracted from the queue, where such node is still in a heap (it may have been detached since).
 69    ///       <br/>
 70    ///     - The <see cref="TreeNode{T}"/>  is used to make a direct access to
 71    ///       the corresponding <see cref="PrioritizedItem{T}"/>. The priority is taken from
 72    ///       <see cref="PrioritizedItem{T}.Priority"/>.
 73    ///     </para>
 74    ///     <para id="complexity">
 75    ///     COMPLEXITY
 76    ///     <br/>
 77    ///     - Retrieving the priority queue of push timestamps from the dictionary of per-item priority queues is a
 78    ///       O(1) operation.
 79    ///       <br/>
 80    ///     - Iterating such a priority queue requires duplicating the underlying data structure, which is a
 81    ///       O(dup_factor) operation, where dup_factor is the average number of occurrences of an item in the data
 82    ///       structure (1 means no duplicates, 2 means the item appears twice, etc.).
 83    ///       <br/>
 84    ///     - Retrieving the <see cref="TreeNode{T}"/> from the push timestamp and the priority from the
 85    ///       <see cref="PrioritizedItem{T}"/> instance are both constant-time operations.
 86    ///       <br/>
 87    ///     - Therefore Time and Space Complexity are O(dup_factor), where dup_factor is
 88    ///       the average number of occurrences of an item in the data structure (1 means no duplicates, 2 means the
 89    ///       item appears twice, etc.).
 90    ///     </para>
 91    /// </remarks>
 92    public IEnumerable<int> GetPrioritiesOf(TItems item)
 5293    {
 5294        if (!ItemToPushTimestamps.TryGetValue(item, out var pushTimestamps))
 895            return Enumerable.Empty<int>();
 96
 4497        return
 4498            from pushTimestamp in pushTimestamps
 9699            where PushTimestampToTreeNode.ContainsKey(pushTimestamp)
 56100            let treeNode = PushTimestampToTreeNode[pushTimestamp]
 56101            where treeNode.IsInAHeap
 100102            select treeNode.PrioritizedItem.Priority;
 52103    }
 104
 105    /// <summary>
 106    /// Retrieves the <see cref="TreeNode{T}"/> associated with the provided <paramref name="item"/> in the queue,
 107    /// selecting the one of highest priority in case of duplicates (i.e. multiple occurrences of
 108    /// <paramref name="item"/> within the priority queue).
 109    /// </summary>
 110    /// <param name="item">The item to be mapped to a <see cref="TreeNode{T}"/>.</param>
 111    /// <returns>The corresponding <see cref="TreeNode{T}"/>.</returns>
 112    /// <exception cref="InvalidOperationException">
 113    /// Raised when the provided <paramref name="item"/> is not found in the queue, so it can't be mapped to a
 114    /// <see cref="TreeNode{T}"/>.
 115    /// </exception>
 116    /// <remarks>
 117    ///     <para id = "algorithm-treenode-retrieval" >
 118    ///     ALGORITHM - TREENODE RETRIEVAL PART
 119    ///     <br/>
 120    ///     - The priority queue of push timestamps for the provided <paramref name="item"/> is retrieved from the
 121    ///       dictionary of per-item queues of push timestamps.
 122    ///       <br/>
 123    ///     - If such a priority queue is not found, it means that <paramref name="item"/> is not present in the main
 124    ///       priority queue either. So, an <see cref="InvalidOperationException"/> is thrown.
 125    ///       <br/>
 126    ///     - If the priority queue is found, push timestamps are popped from it until the root of the priority queue
 127    ///       contains a valid timestamp ts, i.e. a timestamp present in the dictionary mapping timestamps to
 128    ///       <see cref="TreeNode{T}"/> instances and the <see cref="TreeNode{T}.IsInAHeap"/>.
 129    ///       <br/>
 130    ///     - If such a timestamp is not found, it means that that <paramref name="item"/> used to be present in the
 131    ///       main priority, but it is not anymore. So, an <see cref="InvalidOperationException"/> is thrown.
 132    ///       <br/>
 133    ///     - If such a timestamp is found, the <see cref="PrioritizedItem{T}"/> can be accessed via the
 134    ///       <see cref="TreeNode{T}.PrioritizedItem"/> property.
 135    ///     </para>
 136    ///     <para id="complexity-treenode-retrieval">
 137    ///     COMPLEXITY - TREENODE RETRIEVAL PART
 138    ///     <br/>
 139    ///     - Retrieving the priority queue associated with the <paramref name="item"/> is a O(1) operation.
 140    ///       <br/>
 141    ///     - Finding the right push timestamp may require a number of <see cref="BinomialHeapPriorityQueue{T}.Pop"/>
 142    ///       proportional to the number of times the priority of <paramref name="item"/> has been changed.
 143    ///       <br/>
 144    ///     - In the worst case, such number is equal to the number of insertion of <paramref name="item"/>.
 145    ///       <br/>
 146    ///     - Therefore, Time Complexity is O(dup_factor) and Space Complexity is O(1), where dup_factor is
 147    ///       the average number of occurrences of an item in the data structure (1 means no duplicates, 2 means the
 148    ///       item appears twice, etc.).
 149    ///     </para>
 150    /// </remarks>
 151    public TreeNode<TItems>? FindTreeNode(TItems item)
 1368152    {
 1368153        if (!ItemToPushTimestamps.TryGetValue(item, out var pushTimestamps))
 1019154            return null;
 155
 349156        TreeNode<TItems>? treeNode = null;
 448157        while (
 448158            pushTimestamps.Count > 0 &&
 448159            (!PushTimestampToTreeNode.TryGetValue(pushTimestamps.Peek().Item, out treeNode) || !treeNode.IsInAHeap))
 99160        {
 99161            pushTimestamps.Pop();
 99162        }
 163
 349164        if (pushTimestamps.Count == 0)
 2165            return null;
 166
 347167        return treeNode;
 1368168    }
 169
 170    /// <summary>
 171    /// To be invoked just after a <paramref name="newRoot"/> has been pushed into the heap.
 172    /// </summary>
 173    /// <param name="newRoot">The new root pushed into the heap forest.</param>
 174    public void RaiseItemPushed(TreeNode<TItems> newRoot)
 11915175    {
 11915176        var prioritizedItem = newRoot.PrioritizedItem;
 11915177        PushTimestampToTreeNode[prioritizedItem.PushTimestamp] = newRoot;
 11915178        if (!ItemToPushTimestamps.TryGetValue(prioritizedItem.Item, out var pushTimestamps))
 11559179            ItemToPushTimestamps[prioritizedItem.Item] = pushTimestamps = new THeap();
 11915180        pushTimestamps.Push(prioritizedItem.PushTimestamp, prioritizedItem.Priority);
 11915181    }
 182
 183    /// <summary>
 184    /// To be invoked just before the provided <paramref name="root"/> is popped from the heap.
 185    /// </summary>
 186    /// <param name="root">The root about to be popped from the heap forest.</param>
 187    public void RaiseItemPopping(TreeNode<TItems> root)
 5244188    {
 5244189        PushTimestampToTreeNode.Remove(root.PrioritizedItem.PushTimestamp);
 5244190    }
 191
 192    /// <summary>
 193    /// To be invoked just after the priority of a <see cref="TreeNode{T}"/> has changed.
 194    /// </summary>
 195    /// <param name="treeNode">The node in the heap which has changed priority.</param>
 196    /// <param name="itemBefore">The <see cref="PrioritizedItem{T}"/> as it was before the priority change.</param>
 197    public void RaiseItemPriorityChanged(TreeNode<TItems> treeNode, PrioritizedItem<TItems> itemBefore)
 347198    {
 347199        var itemAfter = treeNode.PrioritizedItem;
 347200        PushTimestampToTreeNode.Remove(itemBefore.PushTimestamp);
 347201        PushTimestampToTreeNode[itemAfter.PushTimestamp] = treeNode;
 347202        ItemToPushTimestamps[itemAfter.Item].Push(itemAfter.PushTimestamp, itemAfter.Priority);
 347203    }
 204
 205    /// <summary>
 206    /// Invoked just after two items have had their <see cref="PrioritizedItem{T}"/> swapped.
 207    /// </summary>
 208    /// <param name="treeNode1">The first node.</param>
 209    /// <param name="treeNode2">The second node.</param>
 210    public void RaiseItemsSwapped(TreeNode<TItems> treeNode1, TreeNode<TItems> treeNode2)
 107211    {
 107212        PushTimestampToTreeNode[treeNode1.PrioritizedItem.PushTimestamp] = treeNode1;
 107213        PushTimestampToTreeNode[treeNode2.PrioritizedItem.PushTimestamp] = treeNode2;
 107214    }
 215}
Generated by: ReportGenerator 5.1.19.0
03/19/2023 - 17:28:50
GitHub | reportgenerator.io

Methods/Properties

get_ItemToPushTimestamps()
get_PushTimestampToTreeNode()
Clear()
GetPrioritiesOf(TItems)
FindTreeNode(TItems)
RaiseItemPushed(MoreStructures.PriorityQueues.BinomialHeap.TreeNode`1<TItems>)
RaiseItemPopping(MoreStructures.PriorityQueues.BinomialHeap.TreeNode`1<TItems>)
RaiseItemPriorityChanged(MoreStructures.PriorityQueues.BinomialHeap.TreeNode`1<TItems>,MoreStructures.PriorityQueues.PrioritizedItem`1<TItems>)
RaiseItemsSwapped(MoreStructures.PriorityQueues.BinomialHeap.TreeNode`1<TItems>,MoreStructures.PriorityQueues.BinomialHeap.TreeNode`1<TItems>)