< Summary

Information
Class: MoreStructures.PriorityQueues.LinkedList.SortedLinkedListPriorityQueue<T>
Assembly: MoreStructures
File(s): /home/runner/work/MoreStructures/MoreStructures/MoreStructures/PriorityQueues/LinkedList/SortedLinkedListPriorityQueue.cs
Line coverage
100%
Covered lines: 107
Uncovered lines: 0
Coverable lines: 107
Total lines: 334
Line coverage: 100%
Branch coverage
100%
Covered branches: 44
Total branches: 44
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%
FindOccurrenceWithHighestPrioritySmallerThan(...)100%6100%
FindOccurrenceWithHighestPriorityOf(...)100%4100%
.ctor(...)100%1100%
.ctor()100%1100%
.ctor(...)100%2100%
get_Count()100%1100%
GetEnumerator()100%2100%
System.Collections.IEnumerable.GetEnumerator()100%1100%
Peek()100%2100%
Pop()100%2100%
Push(...)100%2100%
GetPrioritiesOf(...)100%4100%
UpdatePriority(...)100%2100%
Remove(...)100%2100%
PeekKth(...)100%6100%
MergeFrom(...)100%10100%
Clear()100%1100%

File(s)

/home/runner/work/MoreStructures/MoreStructures/MoreStructures/PriorityQueues/LinkedList/SortedLinkedListPriorityQueue.cs

#LineLine coverage
 1using System.Collections;
 2
 3namespace MoreStructures.PriorityQueues.LinkedList;
 4
 5/// <summary>
 6/// An <see cref="IPriorityQueue{T}"/> implementation based on a <b>sorted linked list</b> of its items.
 7/// On top of basic operations it also supports <see cref="IUpdatablePriorityQueue{T}"/>,
 8/// <see cref="IPeekKthPriorityQueue{T}"/> and <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 extraction, at the cost of all other operations, which are O(n).
 19///     <br/>
 20///     Runtime behavior is specular to <see cref="ArrayList.ArrayListPriorityQueue{T}"/>, which can perform an
 21///     insertion in constant time, but requires a linear amount of time to extract a value.
 22///     <br/>
 23///     If extraction performance is the only highly critical operation, to the point that a constant time performance
 24///     is the only acceptable runtime, and not even the logarithmic time extraction of a tree-based solution can be
 25///     applied, this implementation may be the best choice.
 26///     <br/>
 27///     An advantage over <see cref="ArrayList.ArrayListPriorityQueue{T}"/> is that this solution can also offer
 28///     constant-time merging and still similar simplicity of implementation.
 29///     <br/>
 30///     When data insertion 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///     </para>
 33/// </remarks>
 34public sealed class SortedLinkedListPriorityQueue<T>
 35    : IUpdatablePriorityQueue<T>, IPeekKthPriorityQueue<T>, IMergeablePriorityQueue<T, SortedLinkedListPriorityQueue<T>>
 36    where T : notnull
 37{
 38    /// <summary>
 39    /// A non-negative, zero-based, monotonically strictly increasing counter, incremented at every insertion into this
 40    /// data structure by a <see cref="Push(T, int)"/>.
 41    /// </summary>
 1422342    private int CurrentPushTimestamp { get; set; } = 0;
 43
 44    /// <summary>
 45    /// The <see cref="LinkedList{T}"/> of <see cref="PrioritizedItem{T}"/> backing the linked list heap.
 46    /// </summary>
 1468247    private LinkedList<PrioritizedItem<T>> Items { get; set; }
 48
 49    private LinkedListNode<PrioritizedItem<T>>? FindOccurrenceWithHighestPrioritySmallerThan(PrioritizedItem<T> item)
 404550    {
 404551        LinkedListNode<PrioritizedItem<T>>? current = Items.First;
 404552        if (current == null)
 25153            return null;
 54
 379455        LinkedListNode<PrioritizedItem<T>>? previous = null;
 88051356        while (current != null && current.Value.CompareTo(item) > 0)
 87671957        {
 87671958            previous = current;
 87671959            current = current.Next;
 87671960        }
 61
 379462        return previous;
 404563    }
 64
 65    private LinkedListNode<PrioritizedItem<T>>? FindOccurrenceWithHighestPriorityOf(T item)
 12066    {
 230667        for (var current = Items.First; current != null; current = current.Next)
 114368            if (Equals(current.Value.Item, item))
 11069                return current;
 70
 1071        return null;
 12072    }
 73
 74    /// <summary>
 75    /// Builds a priority queue using the provided linked list as <b>direct</b> backing structure.
 76    /// </summary>
 77    /// <param name="items">The <see cref="LinkedList{T}"/> structure to be used as backing structure.</param>
 78    /// <remarks>
 79    /// The provided linked list is not copied over: it is used directly as backing structure for the queue.
 80    /// <br/>
 81    /// Therefore, operations mutating the queue such as <see cref="Push(T, int)"/> will alter the content of the
 82    /// <paramref name="items"/> linked list.
 83    /// </remarks>
 22184    public SortedLinkedListPriorityQueue(LinkedList<PrioritizedItem<T>> items)
 22185    {
 22186        Items = items;
 22187    }
 88
 89    /// <summary>
 90    /// Builds an empty priority queue.
 91    /// </summary>
 21992    public SortedLinkedListPriorityQueue() : this(new List<PrioritizedItem<T>>())
 21993    {
 21994    }
 95
 96    /// <summary>
 97    /// Builds a priority queue using the provided items to populate its backing structure.
 98    /// </summary>
 99    /// <param name="items">The items to be added to the queue.</param>
 100    /// <remarks>
 101    /// The provided sequence is enumerated, sorted in descending order of priority (taking into account
 102    /// <see cref="PrioritizedItem{T}.PushTimestamp"/> to break ties), then copied over onto a dedicated linked list.
 103    /// <br/>
 104    /// So, the provided sequence is not used directly as backing structure for the queue.
 105    /// <br/>
 106    /// Therefore, operations mutating the queue won't alter the provided <paramref name="items"/> sequence.
 107    /// </remarks>
 108    public SortedLinkedListPriorityQueue(IEnumerable<PrioritizedItem<T>> items)
 224109        : this(new LinkedList<PrioritizedItem<T>>(items.OrderByDescending(i => i)))
 220110    {
 220111    }
 112
 113    /// <inheritdoc path="//*[not(self::remarks)]"/>
 114    /// <remarks>
 115    /// Calls <see cref="Count"/> on the underlying list.
 116    /// <br/>
 117    /// Time and Space Complexity are O(1).
 118    /// </remarks>
 236119    public int Count => Items.Count;
 120
 121    /// <inheritdoc path="//*[not(self::remarks)]"/>
 122    /// <remarks>
 123    /// Returns the items in the underlying linked list, which is already sorted in descending order of priority.
 124    /// <br/>
 125    /// Time Complexity is O(n) (when fully enumerated). Space Complexity is O(1).
 126    /// </remarks>
 3037127    public IEnumerator<T> GetEnumerator() => Items.Select(n => n.Item).GetEnumerator();
 128
 129    /// <inheritdoc path="//*[not(self::remarks)]"/>
 130    /// <remarks>
 131    ///     <inheritdoc cref="GetEnumerator"/>
 132    /// </remarks>
 1133    IEnumerator IEnumerable.GetEnumerator() => GetEnumerator();
 134
 135    /// <inheritdoc path="//*[not(self::remarks)]"/>
 136    /// <remarks>
 137    /// Returns the first item in the underlying linked list, raising <see cref="InvalidOperationException"/> when the
 138    /// list is empty.
 139    /// <br/>
 140    /// Time Complexity is O(1). Space Complexity is O(1).
 141    /// </remarks>
 142    public PrioritizedItem<T> Peek()
 1319143    {
 1319144        if (Items.Count == 0)
 3145            throw new InvalidOperationException($"Can't ${nameof(Peek)} on an empty queue.");
 146
 1316147        return Items.First();
 1316148    }
 149
 150    /// <inheritdoc path="//*[not(self::remarks)]"/>
 151    /// <remarks>
 152    /// <see cref="Peek"/> the item with the highest priority from the underlying linked lists, which is the first item
 153    /// in the chain.
 154    /// <br/>
 155    /// Then removes such an the item from the front of the linked list and returns it as result.
 156    /// <br/>
 157    /// Time Complexity is O(1). Space Complexity is O(1).
 158    /// </remarks>
 159    public PrioritizedItem<T> Pop()
 1258160    {
 1258161        if (Items.Count == 0)
 3162            throw new InvalidOperationException($"Can't ${nameof(Pop)} on an empty queue.");
 163
 1255164        var result = Peek();
 1255165        Items.RemoveFirst();
 1255166        return result;
 1255167    }
 168
 169    /// <inheritdoc path="//*[not(self::remarks)]"/>
 170    /// <remarks>
 171    /// Finds the item I in the linked list with the highest priority, smaller than the priority of the provided
 172    /// <paramref name="priority"/>.
 173    /// <br/>
 174    /// Then adds a new <see cref="LinkedListNode{T}"/> instance, having as value a new
 175    /// <see cref="PrioritizedItem{T}"/> with the provided <paramref name="item"/> and <paramref name="priority"/>,
 176    /// just before the item I.
 177    /// <br/>
 178    /// If such a I doesn't exist, prepend the new <see cref="LinkedListNode{T}"/> at the front of the linked list.
 179    /// <br/>
 180    /// Time Complexity is O(n). Space Complexity is O(1).
 181    /// <br/>
 182    /// Remark: while the linked list is sorted by priority, binary search it's not possible, due to lack of direct
 183    /// random access support.
 184    /// </remarks>
 185    public void Push(T item, int priority)
 4045186    {
 4045187        var prioritizedItem = new PrioritizedItem<T>(item, priority, CurrentPushTimestamp++);
 4045188        var highestSmallerNode = FindOccurrenceWithHighestPrioritySmallerThan(prioritizedItem);
 4045189        if (highestSmallerNode == null)
 686190            Items.AddFirst(prioritizedItem);
 191        else
 3359192            Items.AddAfter(highestSmallerNode, prioritizedItem);
 4045193    }
 194
 195    /// <inheritdoc path="//*[not(self::remarks)]"/>
 196    /// <remarks>
 197    /// Linearly scans the underlying linked list, looking for <see cref="PrioritizedItem{T}"/> having an item equals
 198    /// to the provided <paramref name="item"/> (<see cref="object.Equals(object?, object?)"/> is used to compare the
 199    /// two items of type <typeparamref name="T"/>).
 200    /// <br/>
 201    /// It then selects all priorities found for <paramref name="item"/> and builds a
 202    /// <see cref="SortedLinkedListPriorityQueue{T}"/> of <see cref="int"/> values out of them.
 203    /// <br/>
 204    /// Such a priority queue is returned as result.
 205    /// <br/>
 206    /// Time Complexity is O(n * Teq) and Space Complexity is O(Seq), where Teq and Seq are the time and space cost of
 207    /// comparing two items of type <typeparamref name="T"/>.
 208    /// </remarks>
 209    public IEnumerable<int> GetPrioritiesOf(T item)
 41210    {
 41211        var priorities = Items
 78212            .Where(prioritizedItem => Equals(prioritizedItem.Item, item))
 85213            .Select(prioritizedItem => prioritizedItem.Priority);
 41214        var priorityQueue = new SortedLinkedListPriorityQueue<int>();
 211215        foreach (var priority in priorities)
 44216            priorityQueue.Push(priority, priority);
 41217        return priorityQueue;
 41218    }
 219
 220    /// <inheritdoc path="//*[not(self::remarks)]"/>
 221    /// <remarks>
 222    /// Removes the occurrence of <paramref name="item"/> with highest priority from the underlying linked list (the
 223    /// first encountered while navigating the list).
 224    /// <br/>
 225    /// If no occurrence of <paramref name="item"/> is found, an <see cref="InvalidOperationException"/> is thrown.
 226    /// <br/>
 227    /// Then pushes the provided <paramref name="item"/> with the given <paramref name="newPriority"/>.
 228    /// <br/>
 229    /// Both removal and push operations require linked list traversal and update.
 230    /// <br/>
 231    /// Therefore, Time Complexity is O(n). Space Complexity is O(1).
 232    /// </remarks>
 233    public PrioritizedItem<T> UpdatePriority(T item, int newPriority)
 97234    {
 97235        var oldItem = Remove(item);
 97236        if (oldItem == null)
 3237            throw new InvalidOperationException("The specified item is not in the queue.");
 94238        Push(item, newPriority);
 94239        return oldItem.Value;
 94240    }
 241
 242    /// <inheritdoc path="//*[not(self::remarks)]"/>
 243    /// <remarks>
 244    /// Linearly scans the underlying linked list, looking for the first node with the item equals to the provided
 245    /// <paramref name="item"/> (<see cref="object.Equals(object?, object?)"/> is used to compare the two items of type
 246    /// <typeparamref name="T"/>).
 247    /// <br/>
 248    /// If multiple occurrences of <paramref name="item"/> are present with the same highest priority, the one with the
 249    /// lowest <see cref="PrioritizedItem{T}.PushTimestamp"/> is considered of higher priority, and comes before any
 250    /// other in the list. That guarantees <b>stability</b>.
 251    /// <br/>
 252    /// If no such node is found, nothing is changed and <see langword="null"/> is returned.
 253    /// <br/>
 254    /// Otherwise the node is removed from the list and returned as result.
 255    /// <br/>
 256    /// Time Complexity is O(n * Teq) and Space Complexity is O(Seq), where Teq and Seq are the time and space cost of
 257    /// comparing two items of type <typeparamref name="T"/>.
 258    /// </remarks>
 259    public PrioritizedItem<T>? Remove(T item)
 120260    {
 120261        var itemNode = FindOccurrenceWithHighestPriorityOf(item);
 262
 120263        if (itemNode == null)
 10264            return null;
 265
 110266        Items.Remove(itemNode);
 110267        return itemNode.Value;
 120268    }
 269
 270    /// <inheritdoc path="//*[not(self::remarks)]"/>
 271    /// <remarks>
 272    /// Takes advantage of the fact that the underlying linked list of items is already sorted in descending order by
 273    /// priority, and returns the <paramref name="k"/>-th item of the list.
 274    /// <br/>
 275    /// Time Complexity is O(k). Space Complexity is O(1).
 276    /// <br/>
 277    /// The <paramref name="k"/>-th item of the list cannot be accessed in constant time, because linked lists don't
 278    /// support direct random access.
 279    /// </remarks>
 280    public PrioritizedItem<T>? PeekKth(int k)
 26281    {
 26282        if (k < 0)
 2283            throw new ArgumentException("Must be non-negative.", nameof(k));
 24284        if (k >= Items.Count)
 8285            return null;
 16286        if (k == 0)
 5287            return Peek();
 288
 11289        return Items.ElementAt(k);
 24290    }
 291
 292    /// <inheritdoc path="//*[not(self::remarks)]"/>
 293    /// <remarks>
 294    /// Does 2-way merging on the underlying linked lists, which are already sorted in descending order of priority.
 295    /// <br/>
 296    /// Time and Space Complexity are O(n + m), where n and m are the number of items in this queue and in the target,
 297    /// respectively.
 298    /// </remarks>
 299    public void MergeFrom(SortedLinkedListPriorityQueue<T> targetPriorityQueue)
 119300    {
 119301        var first = Items.First;
 119302        var second = targetPriorityQueue.Items.First;
 119303        var merged = new LinkedList<PrioritizedItem<T>>();
 3075304        while (first != null || second != null)
 2956305        {
 306            PrioritizedItem<T> prioritizedItem;
 2956307            if (second == null || (first != null && first.Value.Priority >= second.Value.Priority))
 1639308            {
 1639309                prioritizedItem = new(first!.Value.Item, first.Value.Priority, CurrentPushTimestamp++);
 1639310                first = first.Next;
 1639311            }
 312            else
 1317313            {
 1317314                prioritizedItem = new(second.Value.Item, second.Value.Priority, CurrentPushTimestamp++);
 1317315                second = second.Next;
 1317316            }
 2956317            merged.AddLast(prioritizedItem);
 2956318        }
 319
 119320        Items = merged;
 119321        targetPriorityQueue.Clear();
 119322    }
 323
 324    /// <inheritdoc path="//*[not(self::remarks)]"/>
 325    /// <remarks>
 326    /// Just clears the underlying linked list.
 327    /// <br/>
 328    /// Time and Space Complexity is O(1).
 329    /// </remarks>
 330    public void Clear()
 174331    {
 174332        Items.Clear();
 174333    }
 334}
Generated by: ReportGenerator 5.1.19.0
03/19/2023 - 17:28:50
GitHub | reportgenerator.io

Methods/Properties

get_CurrentPushTimestamp()
get_Items()
FindOccurrenceWithHighestPrioritySmallerThan(MoreStructures.PriorityQueues.PrioritizedItem`1<T>)
FindOccurrenceWithHighestPriorityOf(T)
.ctor(System.Collections.Generic.LinkedList`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)
MergeFrom(MoreStructures.PriorityQueues.LinkedList.SortedLinkedListPriorityQueue`1<T>)
Clear()