< Summary

Information
Class: MoreStructures.PriorityQueues.ArrayList.ArrayListPriorityQueue<T>
Assembly: MoreStructures
File(s): /home/runner/work/MoreStructures/MoreStructures/MoreStructures/PriorityQueues/ArrayList/ArrayListPriorityQueue.cs
Line coverage
100%
Covered lines: 104
Uncovered lines: 0
Coverable lines: 104
Total lines: 333
Line coverage: 100%
Branch coverage
100%
Covered branches: 40
Total branches: 40
Branch coverage: 100%
Method coverage

Feature is only available for sponsors

Upgrade to PRO version

Metrics

MethodBranch coverage Cyclomatic complexity Line coverage
get_CurrentPushTimestamp()100%1100%
get_Items()100%1100%
FindHighestPriorityOccurrence(...)100%2100%
.ctor(...)100%1100%
.ctor()100%1100%
.ctor(...)100%1100%
get_Count()100%1100%
GetEnumerator()100%4100%
System.Collections.IEnumerable.GetEnumerator()100%1100%
Peek()100%2100%
Pop()100%6100%
Push(...)100%1100%
GetPrioritiesOf(...)100%4100%
UpdatePriority(...)100%2100%
Remove(...)100%2100%
PeekKth(...)100%6100%
QuickFind(...)100%6100%
Partition(...)100%4100%
MergeFrom(...)100%2100%
Clear()100%1100%

File(s)

/home/runner/work/MoreStructures/MoreStructures/MoreStructures/PriorityQueues/ArrayList/ArrayListPriorityQueue.cs

#LineLine coverage
 1using System.Collections;
 2
 3namespace MoreStructures.PriorityQueues.ArrayList;
 4
 5/// <summary>
 6/// An <see cref="IPriorityQueue{T}"/> implementation based on an unsorted list of its items. On top of basic
 7/// operations it also supports <see cref="IUpdatablePriorityQueue{T}"/>, <see cref="IPeekKthPriorityQueue{T}"/> and
 8/// <see cref="IMergeablePriorityQueue{T, TPQTarget}"/>.
 9/// operations.
 10/// </summary>
 11/// <typeparam name="T"><inheritdoc cref="IPriorityQueue{T}"/></typeparam>
 12/// <remarks>
 13///     <para id="advantages">
 14///     ADVANTAGES AND DISADVANTAGES
 15///     <br/>
 16///     This represents one of the simplest implementations of a Priority Queue.
 17///     <br/>
 18///     It provides O(1) count and amortized insertion, at the cost of all other operations, which are O(n).
 19///     <br/>
 20///     If insertion performance is the only highly critical operation, to the point that a constant time performance
 21///     is the only acceptable runtime, and not even the logarithmic time insertion of a tree-based solution can be
 22///     applied, this implementation may be the best choice, although lazy approaches such as
 23///     <see cref="FibonacciHeap.FibonacciHeapPriorityQueue{T}"/> can provide constant-time insertion performance,
 24///     while keeping sub-linear complexity for all other operations.
 25///     <br/>
 26///     If merging performance is also important, a solution based on linked lists can offer constant-time merging and
 27///     still similar simplicity of implementation, same insertion performance and same tradeoff in terms of the
 28///     complexity of all other operations.
 29///     <br/>
 30///     When data extraction performance is also a concern, or the main concern, a more balanced solution in terms of
 31///     complexity of its operations should be preferred.
 32///     <br/>
 33///     This implementation can also be useful as a benchmark baseline in tests, when comparing against more complex
 34///     solutions.
 35///     </para>
 36/// </remarks>
 37public sealed class ArrayListPriorityQueue<T>
 38    : IUpdatablePriorityQueue<T>, IPeekKthPriorityQueue<T>, IMergeablePriorityQueue<T, ArrayListPriorityQueue<T>>
 39    where T : notnull
 40{
 41    /// <summary>
 42    /// A non-negative, zero-based, monotonically strictly increasing counter, incremented at every insertion into this
 43    /// data structure by a <see cref="Push(T, int)"/>.
 44    /// </summary>
 1333945    private int CurrentPushTimestamp { get; set; } = 0;
 46
 47    /// <summary>
 48    /// The <see cref="List{T}"/> of <see cref="PrioritizedItem{T}"/> backing the array list heap.
 49    /// </summary>
 153082550    private List<PrioritizedItem<T>> Items { get; }
 51
 52    private KeyValuePair<int, PrioritizedItem<T>> FindHighestPriorityOccurrence(T item)
 115653    {
 115654        return MoreLinq.MoreEnumerable
 115655            .Index(Items)
 501556            .Where(kvp => Equals(kvp.Value.Item, item))
 115657            .DefaultIfEmpty(KeyValuePair.Create(-1, new PrioritizedItem<T>()))
 243558            .MaxBy(kvp => kvp.Value);
 115659    }
 60
 61    /// <summary>
 62    /// Builds a priority queue using the provided list as <b>direct</b> backing structure.
 63    /// </summary>
 64    /// <param name="items">The <see cref="List{T}"/> structure to be used as backing structure.</param>
 65    /// <remarks>
 66    /// The provided list is not copied over: it is used directly as backing structure for the queue.
 67    /// <br/>
 68    /// Therefore, operations mutating the queue such as <see cref="Push(T, int)"/> will alter the content of the
 69    /// <paramref name="items"/> list.
 70    /// </remarks>
 50771    public ArrayListPriorityQueue(List<PrioritizedItem<T>> items)
 50772    {
 50773        Items = items;
 50774    }
 75
 76    /// <summary>
 77    /// Builds an empty priority queue.
 78    /// </summary>
 50579    public ArrayListPriorityQueue() : this(new List<PrioritizedItem<T>>())
 50580    {
 50581    }
 82
 83    /// <summary>
 84    /// Builds a priority queue using the provided items to populate its backing structure.
 85    /// </summary>
 86    /// <param name="items">The items to be added to the queue.</param>
 87    /// <remarks>
 88    /// The provided sequence is enumerated and copied over onto a dedicated list: it is not used directly as backing
 89    /// structure for the queue.
 90    /// <br/>
 91    /// Therefore, operations mutating the queue won't alter the provided <paramref name="items"/> sequence.
 92    /// </remarks>
 193    public ArrayListPriorityQueue(IEnumerable<PrioritizedItem<T>> items) : this(items.ToList())
 194    {
 195    }
 96
 97    /// <inheritdoc path="//*[not(self::remarks)]"/>
 98    /// <remarks>
 99    /// Calls <see cref="Count"/> on the underlying list.
 100    /// <br/>
 101    /// Time and Space Complexity are O(1).
 102    /// </remarks>
 1198103    public int Count => Items.Count;
 104
 105    /// <inheritdoc path="//*[not(self::remarks)]"/>
 106    /// <remarks>
 107    /// Sorts the underlying list in descending order of priority and selects the items.
 108    /// <br/>
 109    /// Time Complexity is O(n * log(n)) (when fully enumerated). Space Complexity is O(n), as required by sorting.
 110    /// </remarks>
 152111    public IEnumerator<T> GetEnumerator() => Items
 2893112        .OrderByDescending(itemAndPriority => itemAndPriority.Priority)
 2889113        .Select(itemAndPriority => itemAndPriority.Item)
 152114        .GetEnumerator();
 115
 116    /// <inheritdoc path="//*[not(self::remarks)]"/>
 117    /// <remarks>
 118    ///     <inheritdoc cref="GetEnumerator"/>
 119    /// </remarks>
 1120    IEnumerator IEnumerable.GetEnumerator() => GetEnumerator();
 121
 122    /// <inheritdoc path="//*[not(self::remarks)]"/>
 123    /// <remarks>
 124    /// Linearly scans the underlying list looking for the highest priority.
 125    /// <br/>
 126    /// Time Complexity is O(n). Space Complexity is O(1).
 127    /// </remarks>
 269128    public PrioritizedItem<T> Peek() => Items.MaxBy(itemAndPriority => itemAndPriority.Priority);
 129
 130    /// <inheritdoc path="//*[not(self::remarks)]"/>
 131    /// <remarks>
 132    /// Linearly scans the underlying list looking for the index with the highest priority.
 133    /// <br/>
 134    /// Then removes the item with such index from the underlying list and returns it as result.
 135    /// <br/>
 136    /// Time Complexity is O(n). Space Complexity is O(1).
 137    /// </remarks>
 138    public PrioritizedItem<T> Pop()
 2070139    {
 2070140        if (Items.Count == 0)
 3141            throw new InvalidOperationException($"Can't ${nameof(Pop)} on an empty queue.");
 142
 2067143        var maxIndex = 0;
 1012724144        for (var i = 1; i < Items.Count; i++)
 504295145            if (Items[maxIndex].Priority < Items[i].Priority)
 2151146                maxIndex = i;
 147
 2067148        var result = Items[maxIndex];
 2067149        Items.RemoveAt(maxIndex);
 2067150        return result;
 2067151    }
 152
 153    /// <inheritdoc path="//*[not(self::remarks)]"/>
 154    /// <remarks>
 155    /// Appends the provided <paramref name="item"/> with its <paramref name="priority"/> to the end of the underlying
 156    /// list.
 157    /// <br/>
 158    /// Time Complexity is O(n). Space Complexity is O(1) (amortized over multiple executions of
 159    /// <see cref="Push(T, int)"/>).
 160    /// </remarks>
 161    public void Push(T item, int priority)
 6416162    {
 6416163        Items.Add(new(item, priority, CurrentPushTimestamp++));
 6416164    }
 165
 166    /// <inheritdoc path="//*[not(self::remarks)]"/>
 167    /// <remarks>
 168    /// Linearly scans the underlying list looking for <see cref="PrioritizedItem{T}"/> having an item equals to the
 169    /// provided <paramref name="item"/> (<see cref="object.Equals(object?, object?)"/> is used to compare the two
 170    /// items of type <typeparamref name="T"/>).
 171    /// <br/>
 172    /// It then selects all priorities found for <paramref name="item"/> and builds a
 173    /// <see cref="ArrayListPriorityQueue{T}"/> of <see cref="int"/> values out of them.
 174    /// <br/>
 175    /// Such a priority queue is returned as result.
 176    /// <br/>
 177    /// Time Complexity is O(n * Teq) and Space Complexity is O(Seq), where Teq and Seq are the time and space cost of
 178    /// comparing two items of type <typeparamref name="T"/>.
 179    /// </remarks>
 180    public IEnumerable<int> GetPrioritiesOf(T item)
 41181    {
 41182        var priorities = Items
 78183            .Where(prioritizedItem => Equals(prioritizedItem.Item, item))
 85184            .Select(prioritizedItem => prioritizedItem.Priority);
 41185        var priorityQueue = new ArrayListPriorityQueue<int>();
 211186        foreach (var priority in priorities)
 44187            priorityQueue.Push(priority, priority);
 41188        return priorityQueue;
 41189    }
 190
 191    /// <inheritdoc path="//*[not(self::remarks)]"/>
 192    /// <remarks>
 193    /// Linearly scans the underlying list looking for the index of the item equals to the provided
 194    /// <paramref name="item"/> (<see cref="object.Equals(object?, object?)"/> is used to compare the two items of type
 195    /// <typeparamref name="T"/>) <b>with the highest priority</b>.
 196    /// <br/>
 197    /// If multiple occurrences of <paramref name="item"/> are present with the same highest priority, the one with the
 198    /// lowest <see cref="PrioritizedItem{T}.PushTimestamp"/> is selected, to guarantee <b>stability</b>.
 199    /// <br/>
 200    /// If no occurrence of <paramref name="item"/> is found, a <see cref="InvalidOperationException"/> is raised.
 201    /// <br/>
 202    /// Then replaces the <see cref="PrioritizedItem{T}"/> at such index with a new one having same
 203    /// <see cref="PrioritizedItem{T}.Item"/> and <see cref="PrioritizedItem{T}.PushTimestamp"/>, but
 204    /// <see cref="PrioritizedItem{T}.Priority"/> set to <paramref name="newPriority"/>.
 205    /// <br/>
 206    /// Finally returns the previously stored <see cref="PrioritizedItem{T}"/> at that index.
 207    /// <br/>
 208    /// Time Complexity is O(n * Teq) and Space Complexity is O(Seq), where Teq and Seq are the time and space cost of
 209    /// comparing two items of type <typeparamref name="T"/>.
 210    /// </remarks>
 211    public PrioritizedItem<T> UpdatePriority(T item, int newPriority)
 97212    {
 97213        var oldItem = Remove(item);
 97214        if (oldItem == null)
 3215            throw new InvalidOperationException("The specified item is not in the queue.");
 94216        Push(item, newPriority);
 94217        return oldItem.Value;
 94218    }
 219
 220    /// <inheritdoc path="//*[not(self::remarks)]"/>
 221    /// <remarks>
 222    /// Linearly scans the underlying list looking for the index of the item equals to the provided
 223    /// <paramref name="item"/> (<see cref="object.Equals(object?, object?)"/> is used to compare the two items of type
 224    /// <typeparamref name="T"/>).
 225    /// <br/>
 226    /// If multiple occurrences of <paramref name="item"/> are present with the same highest priority, the one with the
 227    /// lowest <see cref="PrioritizedItem{T}.PushTimestamp"/> is selected, to guarantee <b>stability</b>.
 228    /// <br/>
 229    /// If no such index is found, nothing is changed and <see langword="null"/> is returned.
 230    /// <br/>
 231    /// Otherwise the item at such position is removed from the list and returned as result.
 232    /// <br/>
 233    /// Time Complexity is O(n * Teq) and Space Complexity is O(Seq), where Teq and Seq are the time and space cost of
 234    /// comparing two items of type <typeparamref name="T"/>.
 235    /// </remarks>
 236    public PrioritizedItem<T>? Remove(T item)
 1156237    {
 1156238        var indexAndPrioritizedItem = FindHighestPriorityOccurrence(item);
 239
 1156240        if (indexAndPrioritizedItem.Key < 0)
 868241            return null;
 242
 288243        Items.RemoveAt(indexAndPrioritizedItem.Key);
 288244        return indexAndPrioritizedItem.Value;
 1156245    }
 246
 247    /// <inheritdoc path="//*[not(self::remarks)]"/>
 248    /// <remarks>
 249    /// Uses the Quick Select algorithm to find the <paramref name="k"/>-th largest element by
 250    /// <see cref="PrioritizedItem{T}.Priority"/> in the underlying list.
 251    /// <br/>
 252    /// Because Quick Select requires at least partial in-place sorting, the entire content of the underlying list is
 253    /// first copied into a temporary list, which is passed as target to the Quick Select procedure.
 254    /// <br/>
 255    /// Selected pivot is always at the end of the range of indexes in which selection is happening.
 256    /// <br/>
 257    /// So If input is already sorted in ascending order, Time Complexity is O(n^2), whereas in the average case Time
 258    /// Complexity is O(n). Space Complexity is always O(n).
 259    /// </remarks>
 260    public PrioritizedItem<T>? PeekKth(int k)
 36261    {
 36262        if (k < 0)
 2263            throw new ArgumentException("Must be non-negative.", nameof(k));
 34264        if (k >= Items.Count)
 8265            return null;
 26266        if (k == 0)
 6267            return Peek();
 268
 20269        var list = Items.ToList();
 20270        var index = QuickFind(list, k, 0, list.Count - 1);
 20271        return list[index];
 34272    }
 273
 274    private static int QuickFind(List<PrioritizedItem<T>> list, int k, int start, int end)
 73275    {
 75276        if (start == end) return start;
 277
 71278        int currentPivotIndex = Partition(list, start, end);
 279
 89280        if (currentPivotIndex == k) return currentPivotIndex;
 101281        if (currentPivotIndex > k) return QuickFind(list, k, start, currentPivotIndex - 1);
 5282        return QuickFind(list, k, currentPivotIndex + 1, end);
 73283    }
 284
 285    private static int Partition(List<PrioritizedItem<T>> list, int start, int end)
 71286    {
 71287        var pivotValue = list[end];
 71288        int currentPivotIndex = start - 1;
 882289        for (var j = start; j < end; j++) // Start included, end excluded
 370290        {
 370291            if (list[j].CompareTo(pivotValue) >= 0)
 348292            {
 348293                currentPivotIndex++;
 348294                (list[currentPivotIndex], list[j]) = (list[j], list[currentPivotIndex]);
 348295            }
 370296        }
 297
 71298        currentPivotIndex++;
 71299        (list[currentPivotIndex], list[end]) = (list[end], list[currentPivotIndex]);
 71300        return currentPivotIndex;
 71301    }
 302
 303    /// <inheritdoc path="//*[not(self::remarks)]"/>
 304    /// <remarks>
 305    /// Just pushes all items in the <paramref name="targetPriorityQueue"/> via <see cref="Push(T, int)"/>, which
 306    /// appends each item to the end.
 307    /// <br/>
 308    /// Then clears the content of the <paramref name="targetPriorityQueue"/>, to respect the contract defined by
 309    /// <see cref="IMergeablePriorityQueue{T, TPQTarget}"/>.
 310    /// <br/>
 311    /// Because the underlying structures of both source and target is an array list, there isn't an effective strategy
 312    /// for achieving sub-linear performance, and <see cref="Push(T, int)"/> gives the optimal linear performance.
 313    /// <br/>
 314    /// Time and Space Complexity are O(m), where m is the number of items in the target.
 315    /// </remarks>
 316    public void MergeFrom(ArrayListPriorityQueue<T> targetPriorityQueue)
 119317    {
 2991318        foreach (var prioritizedItem in targetPriorityQueue.Items)
 1317319            Push(prioritizedItem.Item, prioritizedItem.Priority);
 119320        targetPriorityQueue.Clear();
 119321    }
 322
 323    /// <inheritdoc path="//*[not(self::remarks)]"/>
 324    /// <remarks>
 325    /// Just clears the underlying array list.
 326    /// <br/>
 327    /// Time and Space Complexity is O(1).
 328    /// </remarks>
 329    public void Clear()
 174330    {
 174331        Items.Clear();
 174332    }
 333}
Generated by: ReportGenerator 5.1.19.0
03/19/2023 - 17:28:50
GitHub | reportgenerator.io

Methods/Properties

get_CurrentPushTimestamp()
get_Items()
FindHighestPriorityOccurrence(T)
.ctor(System.Collections.Generic.List`1<MoreStructures.PriorityQueues.PrioritizedItem`1<T>>)
.ctor()
.ctor(System.Collections.Generic.IEnumerable`1<MoreStructures.PriorityQueues.PrioritizedItem`1<T>>)
get_Count()
GetEnumerator()
System.Collections.IEnumerable.GetEnumerator()
Peek()
Pop()
Push(T,System.Int32)
GetPrioritiesOf(T)
UpdatePriority(T,System.Int32)
Remove(T)
PeekKth(System.Int32)
QuickFind(System.Collections.Generic.List`1<MoreStructures.PriorityQueues.PrioritizedItem`1<T>>,System.Int32,System.Int32,System.Int32)
Partition(System.Collections.Generic.List`1<MoreStructures.PriorityQueues.PrioritizedItem`1<T>>,System.Int32,System.Int32)
MergeFrom(MoreStructures.PriorityQueues.ArrayList.ArrayListPriorityQueue`1<T>)
Clear()