| | | 1 | | namespace MoreStructures.PriorityQueues.Extensions; |
| | | 2 | | |
| | | 3 | | /// <summary> |
| | | 4 | | /// Extension methods for <see cref="IUpdatablePriorityQueue{T}"/> implementations. |
| | | 5 | | /// </summary> |
| | | 6 | | public static class UpdatablePriorityQueueExtensions |
| | | 7 | | { |
| | | 8 | | /// <summary> |
| | | 9 | | /// If the provided <paramref name="item"/> already is in the <paramref name="queue"/>, it updates its priority to |
| | | 10 | | /// the <paramref name="newPriority"/>. Otherwise, it pushes the <paramref name="item"/> in the |
| | | 11 | | /// <paramref name="queue"/>, with the priority <paramref name="newPriority"/>. |
| | | 12 | | /// </summary> |
| | | 13 | | /// <typeparam name="T">The type of items of the <paramref name="queue"/>.</typeparam> |
| | | 14 | | /// <param name="queue">The <see cref="IUpdatablePriorityQueue{T}"/> instance to update.</param> |
| | | 15 | | /// <param name="item">The item of type <typeparamref name="T"/> to be pushed or updated.</param> |
| | | 16 | | /// <param name="newPriority">The new priority value.</param> |
| | | 17 | | /// <returns> |
| | | 18 | | /// The <see cref="PrioritizedItem{T}"/> entry before the update, or <see langword="null"/>, if there was no entry |
| | | 19 | | /// of <paramref name="item"/> before the update (and a push has been done instead). |
| | | 20 | | /// </returns> |
| | | 21 | | /// <remarks> |
| | | 22 | | /// <para id="algorithm"> |
| | | 23 | | /// ALGORITHM |
| | | 24 | | /// <br/> |
| | | 25 | | /// - A <see cref="IUpdatablePriorityQueue{T}.Remove(T)"/> of the provided <paramref name="item"/> is |
| | | 26 | | /// attempted. |
| | | 27 | | /// <br/> |
| | | 28 | | /// - Then, a <see cref="IPriorityQueue{T}.Push(T, int)"/> of the same <paramref name="item"/> is made, with |
| | | 29 | | /// the <paramref name="newPriority"/>. |
| | | 30 | | /// <br/> |
| | | 31 | | /// - Finally, the removed item, if any, is returned as result. |
| | | 32 | | /// </para> |
| | | 33 | | /// <para id="complexity"> |
| | | 34 | | /// COMPLEXITY |
| | | 35 | | /// <br/> |
| | | 36 | | /// - Time Complexity is O(Tremove + Tpush) and Space Complexity is O(Sremove + Spush), where Tremove and |
| | | 37 | | /// Sremove are the time and space cost of <see cref="IUpdatablePriorityQueue{T}.Remove(T)"/> and Tpush and |
| | | 38 | | /// Spush are the time and space cost of <see cref="IPriorityQueue{T}.Push(T, int)"/>, respectively. |
| | | 39 | | /// </para> |
| | | 40 | | /// </remarks> |
| | | 41 | | public static PrioritizedItem<T>? PushOrUpdate<T>(this IUpdatablePriorityQueue<T> queue, T item, int newPriority) |
| | | 42 | | where T : notnull |
| | 4333 | 43 | | { |
| | 4333 | 44 | | var removedItem = queue.Remove(item); |
| | 4333 | 45 | | queue.Push(item, newPriority); |
| | 4333 | 46 | | return removedItem; |
| | 4333 | 47 | | } |
| | | 48 | | |
| | | 49 | | /// <summary> |
| | | 50 | | /// Pops in sequence all items of the provided <paramref name="queue"/>, returning the sequence of extracted items. |
| | | 51 | | /// </summary> |
| | | 52 | | /// <typeparam name="T">The type of items in the queue.</typeparam> |
| | | 53 | | /// <param name="queue">The <see cref="IPriorityQueue{T}"/>, to extract all items of.</param> |
| | | 54 | | /// <returns>A sequence of extracted <see cref="PrioritizedItem{T}"/>, in order of priority.</returns> |
| | | 55 | | public static IEnumerable<PrioritizedItem<T>> PopAll<T>(this IPriorityQueue<T> queue) |
| | | 56 | | where T : notnull |
| | 26 | 57 | | { |
| | 150 | 58 | | while (queue.Count > 0) |
| | 124 | 59 | | yield return queue.Pop(); |
| | 26 | 60 | | } |
| | | 61 | | } |