Class SortedLinkedListPriorityQueue<T>

An IPriorityQueue<T> implementation based on a sorted linked list of its items. On top of basic operations it also supports IUpdatablePriorityQueue<T>, IPeekKthPriorityQueue<T> and IMergeablePriorityQueue<T, TPQTarget>. operations.

Inheritance

System.Object

SortedLinkedListPriorityQueue<T>

Implements

IUpdatablePriorityQueue<T>

IPeekKthPriorityQueue<T>

IMergeablePriorityQueue<T, SortedLinkedListPriorityQueue<T>>

IPriorityQueue<T>

IEnumerable<T>

Inherited Members

System.Object.Equals(System.Object)

System.Object.Equals(System.Object, System.Object)

System.Object.GetHashCode()

System.Object.GetType()

System.Object.MemberwiseClone()

System.Object.ReferenceEquals(System.Object, System.Object)

System.Object.ToString()

Namespace: MoreStructures.PriorityQueues.LinkedList

Assembly: MoreStructures.dll

Syntax

public sealed class SortedLinkedListPriorityQueue<T> : IUpdatablePriorityQueue<T>, IPeekKthPriorityQueue<T>, IMergeablePriorityQueue<T, SortedLinkedListPriorityQueue<T>>, IPriorityQueue<T>

Type Parameters

Name	Description
T

Remarks

ADVANTAGES AND DISADVANTAGES
This represents one of the simplest implementations of a Priority Queue.
It provides O(1) count and amortized extraction, at the cost of all other operations, which are O(n).
Runtime behavior is specular to ArrayListPriorityQueue<T>, which can perform an insertion in constant time, but requires a linear amount of time to extract a value.
If extraction performance is the only highly critical operation, to the point that a constant time performance is the only acceptable runtime, and not even the logarithmic time extraction of a tree-based solution can be applied, this implementation may be the best choice.
An advantage over ArrayListPriorityQueue<T> is that this solution can also offer constant-time merging and still similar simplicity of implementation.
When data insertion performance is also a concern, or the main concern, a more balanced solution in terms of complexity of its operations should be preferred.

Constructors

SortedLinkedListPriorityQueue()

Builds an empty priority queue.

Declaration

public SortedLinkedListPriorityQueue()

SortedLinkedListPriorityQueue(LinkedList<PrioritizedItem<T>>)

Builds a priority queue using the provided linked list as direct backing structure.

Declaration

public SortedLinkedListPriorityQueue(LinkedList<PrioritizedItem<T>> items)

Parameters

Type	Name	Description
MoreStructures.PriorityQueues.LinkedList<MoreStructures.PriorityQueues.PrioritizedItem<T>>	items	The structure to be used as backing structure.

Remarks

The provided linked list is not copied over: it is used directly as backing structure for the queue.
Therefore, operations mutating the queue such as Push(T, Int32) will alter the content of the items linked list.

SortedLinkedListPriorityQueue(IEnumerable<PrioritizedItem<T>>)

Builds a priority queue using the provided items to populate its backing structure.

Declaration

public SortedLinkedListPriorityQueue(IEnumerable<PrioritizedItem<T>> items)

Parameters

Type	Name	Description
System.Collections.IEnumerable<MoreStructures.PriorityQueues.PrioritizedItem<T>>	items	The items to be added to the queue.

Remarks

The provided sequence is enumerated, sorted in descending order of priority (taking into account to break ties), then copied over onto a dedicated linked list.
So, the provided sequence is not used directly as backing structure for the queue.
Therefore, operations mutating the queue won't alter the provided items sequence.

Properties

Count

Declaration

public int Count { get; }

Property Value

Type	Description
System.Int32

Remarks

Calls Count on the underlying list.
Time and Space Complexity are O(1).

Methods

Clear()

Declaration

public void Clear()

Remarks

Just clears the underlying linked list.
Time and Space Complexity is O(1).

GetEnumerator()

Declaration

public IEnumerator<T> GetEnumerator()

Returns

Type	Description
System.Collections.IEnumerator<T>

Remarks

Returns the items in the underlying linked list, which is already sorted in descending order of priority.
Time Complexity is O(n) (when fully enumerated). Space Complexity is O(1).

GetPrioritiesOf(T)

Declaration

public IEnumerable<int> GetPrioritiesOf(T item)

Parameters

Type	Name	Description
T	item

Returns

Type	Description
System.Collections.IEnumerable<System.Int32>

Remarks

Linearly scans the underlying linked list, looking for MoreStructures.PriorityQueues.PrioritizedItem<T> having an item equals to the provided item (System.Object.Equals(System.Object, System.Object) is used to compare the two items of type T).
It then selects all priorities found for item and builds a SortedLinkedListPriorityQueue<T> of System.Int32 values out of them.
Such a priority queue is returned as result.
Time Complexity is O(n * Teq) and Space Complexity is O(Seq), where Teq and Seq are the time and space cost of comparing two items of type T.

MergeFrom(SortedLinkedListPriorityQueue<T>)

Declaration

public void MergeFrom(SortedLinkedListPriorityQueue<T> targetPriorityQueue)

Parameters

Type	Name	Description
SortedLinkedListPriorityQueue<T>	targetPriorityQueue

Remarks

Does 2-way merging on the underlying linked lists, which are already sorted in descending order of priority.
Time and Space Complexity are O(n + m), where n and m are the number of items in this queue and in the target, respectively.

Peek()

Declaration

public PrioritizedItem<T> Peek()

Returns

Type	Description
MoreStructures.PriorityQueues.PrioritizedItem<T>

Remarks

Returns the first item in the underlying linked list, raising when the list is empty.
Time Complexity is O(1). Space Complexity is O(1).

PeekKth(Int32)

Declaration

public PrioritizedItem<T>? PeekKth(int k)

Parameters

Type	Name	Description
System.Int32	k

Returns

Type	Description
System.Nullable<MoreStructures.PriorityQueues.PrioritizedItem<T>>

Remarks

Takes advantage of the fact that the underlying linked list of items is already sorted in descending order by priority, and returns the k-th item of the list.
Time Complexity is O(k). Space Complexity is O(1).
The k-th item of the list cannot be accessed in constant time, because linked lists don't support direct random access.

Pop()

Declaration

public PrioritizedItem<T> Pop()

Returns

Type	Description
MoreStructures.PriorityQueues.PrioritizedItem<T>

Remarks

Peek() the item with the highest priority from the underlying linked lists, which is the first item in the chain.
Then removes such an the item from the front of the linked list and returns it as result.
Time Complexity is O(1). Space Complexity is O(1).

Push(T, Int32)

Declaration

public void Push(T item, int priority)

Parameters

Type	Name	Description
T	item
System.Int32	priority

Remarks

Finds the item I in the linked list with the highest priority, smaller than the priority of the provided priority.
Then adds a new instance, having as value a new MoreStructures.PriorityQueues.PrioritizedItem<T> with the provided item and priority, just before the item I.
If such a I doesn't exist, prepend the new at the front of the linked list.
Time Complexity is O(n). Space Complexity is O(1).
Remark: while the linked list is sorted by priority, binary search it's not possible, due to lack of direct random access support.

Remove(T)

Declaration

public PrioritizedItem<T>? Remove(T item)

Parameters

Type	Name	Description
T	item

Returns

Type	Description
System.Nullable<MoreStructures.PriorityQueues.PrioritizedItem<T>>

Remarks

Linearly scans the underlying linked list, looking for the first node with the item equals to the provided item (System.Object.Equals(System.Object, System.Object) is used to compare the two items of type T).
If multiple occurrences of item are present with the same highest priority, the one with the lowest is considered of higher priority, and comes before any other in the list. That guarantees stability.
If no such node is found, nothing is changed and null is returned.
Otherwise the node is removed from the list and returned as result.
Time Complexity is O(n * Teq) and Space Complexity is O(Seq), where Teq and Seq are the time and space cost of comparing two items of type T.

UpdatePriority(T, Int32)

Declaration

public PrioritizedItem<T> UpdatePriority(T item, int newPriority)

Parameters

Type	Name	Description
T	item
System.Int32	newPriority

Returns

Type	Description
MoreStructures.PriorityQueues.PrioritizedItem<T>

Remarks

Removes the occurrence of item with highest priority from the underlying linked list (the first encountered while navigating the list).
If no occurrence of item is found, an is thrown.
Then pushes the provided item with the given newPriority.
Both removal and push operations require linked list traversal and update.
Therefore, Time Complexity is O(n). Space Complexity is O(1).

Explicit Interface Implementations

IEnumerable.GetEnumerator()

Declaration

IEnumerator IEnumerable.GetEnumerator()

Returns

Type	Description
System.Collections.IEnumerator

Remarks

Implements

IUpdatablePriorityQueue<T>

IPeekKthPriorityQueue<T>

IMergeablePriorityQueue<T, TPQTarget>

IPriorityQueue<T>

IEnumerable<>

Extension Methods

SuffixStructureNodeExtensions.GetAllSuffixesFor<TEdge, TNode>(TNode, TextWithTerminator)

UpdatablePriorityQueueExtensions.PushOrUpdate<T>(IUpdatablePriorityQueue<T>, T, Int32)

UpdatablePriorityQueueExtensions.PopAll<T>(IPriorityQueue<T>)