Struct ValuePriorityQueue<T>

A ValuePriorityQueue<T> maintains a partial ordering of its elements such that the element with least priority can always be found in constant time. Put()'s and Pop()'s require log(size) time.

This ref struct has the same behavior as PriorityQueue<T>, but can be used to reduce allocations in scenarios where ref structs are allowed. If the type of T is a struct the passed in Span<T> buffer may also be allocated on the stack, as allowed.

NOTE: The allocation size of the supplied Span<T> buffer must be maxSize+1. The GetArrayHeapSize(int) method can be used to get the correct calculation and to validate bounds of maxSize.

If instantiated with a constructor that accepts a ISentinelFactory<T>, that factory will be used to populate the elements of the array.

NOTE: The type of T may be either a class or a value type. But do note that it was specifically designed with nullable types in mind, so there may be cases where you need to use a nullable value type to get it to behave correctly.

Note

This API is for internal purposes only and might change in incompatible ways in the next release.

Inherited Members

ValueType.Equals(object)

ValueType.GetHashCode()

ValueType.ToString()

object.Equals(object, object)

object.GetType()

object.ReferenceEquals(object, object)

Namespace: Lucene.Net.Util

Assembly: Lucene.Net.dll

Syntax

public ref struct ValuePriorityQueue<T>

Type Parameters

Name	Description
T

Constructors

ValuePriorityQueue(Span<T>, IComparer<T>)

Initializes a new instance of ValuePriorityQueue<T> with the specified buffer and comparer.

Declaration

public ValuePriorityQueue(Span<T> buffer, IComparer<T> comparer)

Parameters

Type	Name	Description
Span<T>	buffer	The buffer to use for priority queue operations. To determine the correct size of buffer to allocate, use the GetArrayHeapSize(int) method.
IComparer<T>	comparer	An IComparer<T> implementation that is used to determine the order of items in the priority queue. Note that if the comparer returns 0, the value is treated no differently than if it were 1 (greater than).

Exceptions

Type	Condition
ArgumentNullException	comparer is null.

ValuePriorityQueue(Span<T>, IComparer<T>, ISentinelFactory<T>?)

Initializes a new instance of ValuePriorityQueue<T> with the specified buffer and comparer.

Declaration

public ValuePriorityQueue(Span<T> buffer, IComparer<T> comparer, ISentinelFactory<T>? sentinelFactory)

Parameters

Type	Name	Description
Span<T>	buffer	The buffer to use for priority queue operations. To determine the correct size of buffer to allocate, use the GetArrayHeapSize(int) method.
IComparer<T>	comparer	An IComparer<T> implementation that is used to determine the order of items in the priority queue. Note that if the comparer returns 0, the value is treated no differently than if it were 1 (greater than).
ISentinelFactory<T>	sentinelFactory	If not null, the queue will be pre-populated. This factory will be called buffer.Length - 1 times to get an instance to provide to each element in the queue. sentinelFactory should return a new instance on each call, but each sentinel instance should consistently represent the same value.

Exceptions

Type	Condition
ArgumentNullException	comparer is null.

See Also

ISentinelFactory<T>

Properties

Comparer

Gets the comparer used to determine the order of objects in this priority queue.

Declaration

public IComparer<T> Comparer { get; }

Property Value

Type	Description
IComparer<T>

Count

Returns the number of elements currently stored in the PriorityQueue<T>. NOTE: This was size() in Lucene.

Declaration

public int Count { get; }

Property Value

Type	Description
int

RawHeap

Returns the underlying storage of the queue.

Declaration

public Span<T> RawHeap { get; }

Property Value

Type	Description
Span<T>

Top

Returns the least element of the PriorityQueue<T> in constant time. Returns null if the queue is empty.

Declaration

public T Top { get; }

Property Value

Type	Description
T

Methods

Add(T)

Adds an Object to a PriorityQueue<T> in log(size) time. If one tries to add more objects than maxSize from initialize and it is not possible to resize the heap, an IndexOutOfRangeException is thrown.

Declaration

public T Add(T element)

Parameters

Type	Name	Description
T	element

Returns

Type	Description
T	The new 'top' element in the queue.

Clear()

Removes all entries from the PriorityQueue<T>.

Declaration

public void Clear()

Insert(T)

Adds an Object to a PriorityQueue<T> in log(size) time. If the given element is smaller than then full heap's minimum, it won't be added.

Declaration

public void Insert(T element)

Parameters

Type	Name	Description
T	element

InsertWithOverflow(T)

Adds an Object to a PriorityQueue<T> in log(size) time. It returns the object (if any) that was dropped off the heap because it was full. This can be the given parameter (in case it is smaller than the full heap's minimum, and couldn't be added), or another object that was previously the smallest value in the heap and now has been replaced by a larger one, or null if the queue wasn't yet full with maxSize elements.

Declaration

public T InsertWithOverflow(T element)

Parameters

Type	Name	Description
T	element

Returns

Type	Description
T

Pop()

Removes and returns the least element of the PriorityQueue<T> in log(size) time.

Declaration

public T Pop()

Returns

Type	Description
T

UpdateTop()

Should be called when the Object at top changes values. Still log(n) worst case, but it's at least twice as fast to

pq.Top.Change();
pq.UpdateTop();

instead of

o = pq.Pop();
o.Change();
pq.Push(o);

Declaration

public T UpdateTop()

Returns

Type	Description
T	The new 'top' element.