Class UniquePriorityQueue<K, V, P>

Namespace

CounterpointCollective.Collections

Assembly

CounterpointCollective.UniquePriorityQueue.dll

A priority queue where each key is unique and associated with a value and a priority. When Enqueue(K, V, P) is called for a key already existing in the queue, its associated value and priority are updated. Dequeue operations always return the item with the highest priority.

public class UniquePriorityQueue<K, V, P> where K : notnull

Type Parameters

K

The type of keys in the queue. Must be non-nullable.

V

The type of values associated with the keys.

P

The type used for priority comparisons. Typically implements IComparable<T> or is used with a custom IComparer<T>.

Inheritance

object

UniquePriorityQueue<K, V, P>

Inherited Members

object.Equals(object)

object.Equals(object, object)

object.GetHashCode()

object.GetType()

object.MemberwiseClone()

object.ReferenceEquals(object, object)

object.ToString()

Constructors

UniquePriorityQueue()

Initializes a new instance of the UniquePriorityQueue<K, V, P> class using the default priority comparer for type P.

public UniquePriorityQueue()

UniquePriorityQueue(IComparer<P>)

Initializes a new instance of the UniquePriorityQueue<K, V, P> class using the specified priority comparer.

public UniquePriorityQueue(IComparer<P> priorityComparer)

Parameters

priorityComparer IComparer<P>

An IComparer<T> implementation used to determine the ordering of priorities in the queue.

Properties

Count

Get the number of unique keys currently in the queue.

public int Count { get; }

Property Value

int

Methods

Clear()

Removes all items from the queue.

public void Clear()

Enqueue(K, V, P)

Adds a key, value, and priority to the queue. If the key already exists, its value and priority are updated.

public void Enqueue(K k, V v, P p)

Parameters

k K

The key to add or update in the queue. Must be unique.

v V

The value associated with the key.

p P

The priority of the item.

Remarks

The operation has an amortized time complexity of O(log n).

Get(K)

Returns the value and priority associated with the specified key.

public (V Value, P Priority) Get(K k)

Parameters

k K

The key of the item to retrieve.

Returns

(V Value, P Priority)

A tuple containing the value and priority associated with the key.

Remarks

The operation has a time complexity of O(1).

Exceptions

KeyNotFoundException

Thrown if the specified key does not exist in the queue.

Peek()

Returns the item with the highest priority without removing it from the queue.

public (K key, V value, P priority) Peek()

Returns

(K key, V value, P priority)

A tuple containing the key, value, and priority of the highest-priority item.

Remarks

The operation has an amortized time complexity of O(log n).

Exceptions

InvalidOperationException

Thrown if the queue is empty.

Remove(K, out V, out P)

Removes the item with the specified key from the queue, if it exists.

public bool Remove(K s, out V value, out P priority)

Parameters

s K

The key of the item to remove.

value V

When this method returns, contains the value of the removed item, if successful; otherwise, the default value of V.

priority P

When this method returns, contains the priority of the removed item, if successful; otherwise, the default value of P.

Returns

bool

true if the item was found and removed; otherwise, false.

Remarks

The operation has an amortized time complexity of O(log n).

TryDequeue(out K, out V, out P)

Attempts to remove and return the item with the highest priority from the queue.

public bool TryDequeue(out K key, out V value, out P highestPriority)

Parameters

key K

When this method returns, contains the key of the removed item, if successful; otherwise, the default value of K.

value V

When this method returns, contains the value of the removed item, if successful; otherwise, the default value of V.

highestPriority P

When this method returns, contains the priority of the removed item, if successful; otherwise, the default value of P.

Returns

bool

true if an item was successfully removed; otherwise, false if the queue is empty.

Remarks

The operation has an amortized time complexity of O(log n).

TryGet(K, out V, out P)

Attempts to get the value and priority associated with the specified key without removing it from the queue.

public bool TryGet(K k, out V v, out P p)

Parameters

k K

The key of the item to look up.

v V

When this method returns, contains the value associated with the key, if found; otherwise, the default value of V.

p P

When this method returns, contains the priority associated with the key, if found; otherwise, the default value of P.

Returns

bool

true if the key exists in the queue; otherwise, false.

Remarks

The operation has a time complexity of O(1).

TryPeek(out K, out V, out P)

Attempts to return the item with the highest priority from the queue without removing it.

public bool TryPeek(out K key, out V value, out P highestPriority)

Parameters

key K

When this method returns, contains the key of the highest-priority item, if successful; otherwise, the default value of K.

value V

When this method returns, contains the value of the highest-priority item, if successful; otherwise, the default value of V.

highestPriority P

When this method returns, contains the priority of the highest-priority item, if successful; otherwise, the default value of P.

Returns

bool

true if the queue contains at least one item; otherwise, false.

Remarks

The operation has an amortized time complexity of O(log n).