< Summary

Information
Class: MoreStructures.PriorityQueues.BinaryHeap.UpdatableBinaryHeapPriorityQueue<T>
Assembly: MoreStructures
File(s): /home/runner/work/MoreStructures/MoreStructures/MoreStructures/PriorityQueues/BinaryHeap/UpdatableBinaryHeapPriorityQueue.cs
Line coverage
100%
Covered lines: 54
Uncovered lines: 0
Coverable lines: 54
Total lines: 241
Line coverage: 100%
Branch coverage
100%
Covered branches: 14
Total branches: 14
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_PushTimestampToIndex()100%1100%
Clear()100%1100%
GetPrioritiesOf(...)100%2100%
UpdatePriority(...)100%2100%
Remove(...)100%8100%
RaiseItemPushed(...)100%2100%
RaiseItemPopping(...)100%1100%
RaiseItemsSwapped(...)100%1100%

File(s)

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

#LineLine coverage
 1namespace MoreStructures.PriorityQueues.BinaryHeap;
 2
 3/// <inheritdoc path="//*[not(self::summary or self::remarks)]"/>
 4/// <summary>
 5/// A refinement of <see cref="BinaryHeapPriorityQueue{T}"/> which supports <see cref="IUpdatablePriorityQueue{T}"/>
 6/// operations, such as retrieval and update of priorities and removal of items.
 7/// </summary>
 8/// <remarks>
 9///     In order to support updates and deletions, two additional data structures are introduced:
 10///     <br/>
 11///     - a <see cref="Dictionary{TKey, TValue}"/> Item2PT, mapping items <c>I</c> of type <typeparamref name="T"/> to
 12///       <see cref="BinaryHeapPriorityQueue{T}"/> instances, containing <see cref="PrioritizedItem{T}.PushTimestamp"/>
 13///       values of type <see cref="int"/>, of <see cref="PrioritizedItem{T}"/> instances containing <c>I</c>.
 14///       <br/>
 15///     - a <see cref="Dictionary{TKey, TValue}"/> PT2Idx from <see cref="PrioritizedItem{T}.PushTimestamp"/> values to
 16///       indexes of type <see cref="int"/>, into the backing list of the Binary Max Heap of this priority queue.
 17///       <br/>
 18///     <br/>
 19///     Every time a request to remove or update an item <c>I</c> from the priority queue is made, Item2PT is used to
 20///     retrieve all the <see cref="PrioritizedItem{T}.PushTimestamp"/> values of <see cref="PrioritizedItem{T}"/>
 21///     instances with item.
 22///     <br/>
 23///     Those push timestamps can be multiple because the same item can be added multiple times to the queue.
 24///     <br/>
 25///     The push timestamps are organized themselves in per-item priority queues, with the same priority as the items
 26///     in the main priority queue.
 27///     <br/>
 28///     This way, the push timestamp of highest priority for a given item can be peeked in constant time and extracted
 29///     in logarithmic time.
 30///     <br/>
 31///     Once the timestamp of highest priority has been found, the corresponding index (if any) in the backing list of
 32///     the Binary Max Heap of this priority queue can be found in constant time via the PT2Idx dictionary.
 33///     <br/>
 34///     Once the index is found, operations such as <see cref="Remove(T)"/> and <see cref="UpdatePriority(T, int)"/>
 35///     can be executed in logarithmic time, since restoring heap properties after the modification of a single item of
 36///     the heap requires a logarithmic number of sift down and/or sift up operations.
 37///     <br/>
 38///     <br/>
 39///     The two dictionaries are kept up-to-date by implementing the extensibility points provided by
 40///     <see cref="BinaryHeapPriorityQueue{T}"/>, after pushing, before popping and on items swapping.
 41/// </remarks>
 42public sealed class UpdatableBinaryHeapPriorityQueue<T> : BinaryHeapPriorityQueue<T>, IUpdatablePriorityQueue<T>
 43    where T : notnull
 44{
 1684645    private Dictionary<T, BinaryHeapPriorityQueue<int>> ItemToPushTimestamps { get; } = new();
 3493646    private Dictionary<int, int> PushTimestampToIndex { get; } = new();
 47
 48    #region Public API
 49
 50    /// <inheritdoc path="//*[not(self::remarks)]"/>
 51    /// <remarks>
 52    /// Clears the underlying array list and the additional dictionaries introduced to support updates and deletions.
 53    /// <br/>
 54    /// Time and Space Complexity is O(1).
 55    /// </remarks>
 56    public override void Clear()
 17457    {
 17458        base.Clear();
 17459        ItemToPushTimestamps.Clear();
 17460        PushTimestampToIndex.Clear();
 17461    }
 62
 63    /// <inheritdoc path="//*[not(self::remarks)]"/>
 64    /// <remarks>
 65    ///     <para id="algorithm">
 66    ///     ALGORITHM
 67    ///     <br/>
 68    ///     - First, the priority queue of push timestamps for the provided <paramref name="item"/> is retrieved from
 69    ///       the dictionary of per-item queues of push timestamps.
 70    ///       <br/>
 71    ///     - If such a queue is not found, <paramref name="item"/> is not present in the main priority queue, and an
 72    ///       empty sequence is returned.
 73    ///       <br/>
 74    ///     - Otherwise, the queue is iterated over, getting the index corresponding to each timestamp extracted from
 75    ///       the queue (where such index exists).
 76    ///       <br/>
 77    ///     - The index is used to make a direct access to the corresponding <see cref="PrioritizedItem{T}"/> in the
 78    ///       list backing the main priority queue. The priority is taken from
 79    ///       <see cref="PrioritizedItem{T}.Priority"/>.
 80    ///     </para>
 81    ///     <para id="complexity">
 82    ///     COMPLEXITY
 83    ///     <br/>
 84    ///     - Retrieving the priority queue of push timestamps from the dictionary of per-item priority queues is a
 85    ///       O(1) operation.
 86    ///       <br/>
 87    ///     - Iterating such a priority queue requires duplicating the underlying data structure, which is a
 88    ///       O(dup_factor) operation, where dup_factor is the average number of occurrences of an item in the data
 89    ///       structure (1 means no duplicates, 2 means the item appears twice, etc.).
 90    ///       <br/>
 91    ///     - Retrieving the index from the push timestamp and the priority from the <see cref="PrioritizedItem{T}"/>
 92    ///       instance are both constant-time operations.
 93    ///       <br/>
 94    ///     - Therefore Time and Space Complexity are O(dup_factor).
 95    ///     </para>
 96    /// </remarks>
 97    public IEnumerable<int> GetPrioritiesOf(T item)
 4198    {
 4199        if (!ItemToPushTimestamps.TryGetValue(item, out var pushTimestamps))
 5100            return Enumerable.Empty<int>();
 101
 36102        return
 36103            from pushTimestamp in pushTimestamps
 68104            where PushTimestampToIndex.ContainsKey(pushTimestamp)
 40105            let index = PushTimestampToIndex[pushTimestamp]
 76106            select Items[index].Priority;
 41107    }
 108
 109    /// <inheritdoc path="//*[not(self::remarks)]"/>
 110    /// <remarks>
 111    ///     <para id="algorithm">
 112    ///     ALGORITHM
 113    ///     <br/>
 114    ///     - It first removes the provided <paramref name="item"/> from the queue via <see cref="Remove(T)"/>.
 115    ///       <br/>
 116    ///     - Then, it pushes the same <paramref name="item"/> with <paramref name="newPriority"/> via
 117    ///       <see cref="BinaryHeapPriorityQueue{T}.Push(T, int)"/>.
 118    ///       <br/>
 119    ///     - Finally it returns the <see cref="PrioritizedItem{T}"/> removed in the first step.
 120    ///     </para>
 121    ///     <para id="complexity">
 122    ///     COMPLEXITY
 123    ///     <br/>
 124    ///     - Both <see cref="Remove(T)"/> and <see cref="BinaryHeapPriorityQueue{T}.Push(T, int)"/> have logarithmic
 125    ///       Time Complexity and constant Space Complexity.
 126    ///       <br/>
 127    ///     - Therefore, Time Complexity is O(log(n) + dup_factor) and Space Complexity is O(1), where dup_factor is
 128    ///       the average number of occurrences of an item in the data structure (1 means no duplicates, 2 means the
 129    ///       item appears twice, etc.).
 130    ///     </para>
 131    /// </remarks>
 132    public PrioritizedItem<T> UpdatePriority(T item, int newPriority)
 97133    {
 97134        var oldItem = Remove(item);
 97135        if (oldItem == null)
 3136            throw new InvalidOperationException("The specified item is not in the queue.");
 94137        Push(item, newPriority);
 94138        return oldItem.Value;
 94139    }
 140
 141    /// <inheritdoc path="//*[not(self::remarks)]"/>
 142    /// <remarks>
 143    ///     <para id="algorithm">
 144    ///     ALGORITHM
 145    ///     <br/>
 146    ///     - The priority queue of push timestamps for the provided <paramref name="item"/> is retrieved from the
 147    ///       dictionary of per-item queues of push timestamps.
 148    ///       <br/>
 149    ///     - If such a priority queue is not found, it means that <paramref name="item"/> is not present in the main
 150    ///       priority queue either. So, <see langword="null"/> is returned.
 151    ///       <br/>
 152    ///     - If the priority queue is found, push timestamps are popped from it until the root of the priority queue
 153    ///       contains a valid timestamp ts, i.e. a timestamp present in the dictionary mapping timestamps to indexes.
 154    ///       <br/>
 155    ///     - If such a timestamp is not found, it means that that <paramref name="item"/> used to be present in the
 156    ///       main priority, but it is not anymore. So, <see langword="null"/> is returned.
 157    ///       <br/>
 158    ///     - If such a timestamp is found, the backing list L for the main priority queue can be accessed via the
 159    ///       index i, corresponding to the timestamp ts, simply by <c>L[i]</c>. <c>L[i]</c> represents the item to be
 160    ///       removed.
 161    ///       <br/>
 162    ///     - The priority of <c>L[i]</c> is set to the highest priority in the queue + 1 and the item is made sift up
 163    ///       to the root, due to its new priority being the highest in the heap.
 164    ///       <br/>
 165    ///     - Finally, the item, now at the root of the heap, is removed via a
 166    ///       <see cref="BinaryHeapPriorityQueue{T}.Pop"/>.
 167    ///     </para>
 168    ///     <para id="complexity">
 169    ///     COMPLEXITY
 170    ///     <br/>
 171    ///     - Retrieving the priority queue associated with the <paramref name="item"/> is a O(1) operation.
 172    ///       <br/>
 173    ///     - Finding the right push timestamp may require a number of <see cref="BinaryHeapPriorityQueue{T}.Pop"/>
 174    ///       proportional to the number of times the priority of <paramref name="item"/> has been changed.
 175    ///       <br/>
 176    ///     - In the worst case, such number is equal to the number of insertion of <paramref name="item"/>.
 177    ///       <br/>
 178    ///     - Changing the priority of the <see cref="PrioritizedItem{T}"/> to remove requires constant work.
 179    ///       <br/>
 180    ///     - Sifting it up to the root and then popping it are both logarithmic in time and constant in space.
 181    ///       <br/>
 182    ///     - Therefore, Time Complexity is O(log(n) + dup_factor) and Space Complexity is O(1), where dup_factor is
 183    ///       the average number of occurrences of an item in the data structure (1 means no duplicates, 2 means the
 184    ///       item appears twice, etc.).
 185    ///     </para>
 186    /// </remarks>
 187    public PrioritizedItem<T>? Remove(T item)
 276188    {
 276189        if (!ItemToPushTimestamps.TryGetValue(item, out var pushTimestamps))
 129190            return null;
 191
 147192        int index = -1;
 198193        while (pushTimestamps.Count > 0 && !PushTimestampToIndex.TryGetValue(pushTimestamps.Peek().Item, out index))
 51194        {
 51195            pushTimestamps.Pop();
 51196        }
 197
 147198        if (pushTimestamps.Count == 0)
 6199            return null;
 200
 141201        var oldItem = Items[index];
 202
 203        // Because we only change priority, and both timestamp and index remain unchanged, there is no need to invoke
 204        // RaiseItemX methods.
 141205        Items[index] = Items[index] with { Priority = Peek().Priority + 1 };
 141206        Items.SiftUp(index);
 141207        Pop();
 208
 141209        return oldItem;
 276210    }
 211
 212    #endregion
 213
 214    #region Hooks
 215
 216    /// <inheritdoc/>
 217    protected override void RaiseItemPushed(int indexPushed)
 5467218    {
 5467219        var prioritizedItem = Items[indexPushed];
 5467220        PushTimestampToIndex[prioritizedItem.PushTimestamp] = indexPushed;
 5467221        if (!ItemToPushTimestamps.ContainsKey(prioritizedItem.Item))
 5206222            ItemToPushTimestamps[prioritizedItem.Item] = new BinaryHeapPriorityQueue<int>();
 5467223        ItemToPushTimestamps[prioritizedItem.Item].Push(prioritizedItem.PushTimestamp, prioritizedItem.Priority);
 5467224    }
 225
 226    /// <inheritdoc/>
 227    protected override void RaiseItemPopping(int indexPopped, int indexInBufferArea)
 1506228    {
 1506229        PushTimestampToIndex[Items[indexInBufferArea].PushTimestamp] = 0;
 1506230        PushTimestampToIndex.Remove(Items[indexPopped].PushTimestamp);
 1506231    }
 232
 233    /// <inheritdoc/>
 234    protected override void RaiseItemsSwapped(int index1, int index2)
 12884235    {
 12884236        PushTimestampToIndex[Items[index1].PushTimestamp] = index1;
 12884237        PushTimestampToIndex[Items[index2].PushTimestamp] = index2;
 12884238    }
 239
 240    #endregion
 241}
Generated by: ReportGenerator 5.1.19.0
03/19/2023 - 17:28:50
GitHub | reportgenerator.io

Methods/Properties

get_ItemToPushTimestamps()
get_PushTimestampToIndex()
Clear()
GetPrioritiesOf(T)
UpdatePriority(T,System.Int32)
Remove(T)
RaiseItemPushed(System.Int32)
RaiseItemPopping(System.Int32,System.Int32)
RaiseItemsSwapped(System.Int32,System.Int32)