Class PriorityQueue<T>
A PriorityQueue<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.
NOTE: this class will pre-allocate a full array of
length maxSize+1
if instantiated via the
PriorityQueue(Int32, Boolean) constructor with
prepopulate
set to true
. That maximum
size can grow as we insert elements over the time.
Note
This API is for internal purposes only and might change in incompatible ways in the next release.
Inherited Members
Namespace: Lucene.Net.Util
Assembly: Lucene.Net.dll
Syntax
[Serializable]
public abstract class PriorityQueue<T>
Type Parameters
Name | Description |
---|---|
T |
Constructors
| Improve this Doc View SourcePriorityQueue(Int32)
Declaration
protected PriorityQueue(int maxSize)
Parameters
Type | Name | Description |
---|---|---|
System.Int32 | maxSize |
PriorityQueue(Int32, Boolean)
Declaration
protected PriorityQueue(int maxSize, bool prepopulate)
Parameters
Type | Name | Description |
---|---|---|
System.Int32 | maxSize | |
System.Boolean | prepopulate |
Properties
| Improve this Doc View SourceCount
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 |
---|---|
System.Int32 |
HeapArray
This method returns the internal heap array as T[].
Note
This API is for internal purposes only and might change in incompatible ways in the next release.
Declaration
protected T[] HeapArray { get; }
Property Value
Type | Description |
---|---|
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
| Improve this Doc View SourceAdd(T)
Adds an Object to a PriorityQueue<T> in log(size) time. If one tries to add more objects than Lucene.Net.Util.PriorityQueue`1.maxSize from initialize and it is not possible to resize the heap, an System.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()
GetSentinelObject()
This method can be overridden by extending classes to return a sentinel object which will be used by the PriorityQueue(Int32, Boolean) constructor to fill the queue, so that the code which uses that queue can always assume it's full and only change the top without attempting to insert any new object.
Those sentinel values should always compare worse than any non-sentinel value (i.e., LessThan(T, T) should always favor the non-sentinel values).
By default, this method returns false
, which means the queue will not be
filled with sentinel values. Otherwise, the value returned will be used to
pre-populate the queue. Adds sentinel values to the queue.
If this method is extended to return a non-null value, then the following usage pattern is recommended:
// extends GetSentinelObject() to return a non-null value.
PriorityQueue<MyObject> pq = new MyQueue<MyObject>(numHits);
// save the 'top' element, which is guaranteed to not be null.
MyObject pqTop = pq.Top;
<...>
// now in order to add a new element, which is 'better' than top (after
// you've verified it is better), it is as simple as:
pqTop.Change().
pqTop = pq.UpdateTop();
NOTE: if this method returns a non-null
value, it will be called by
the PriorityQueue(Int32, Boolean) constructor
Count times, relying on a new object to be returned and will not
check if it's null
again. Therefore you should ensure any call to this
method creates a new instance and behaves consistently, e.g., it cannot
return null
if it previously returned non-null
.
Declaration
protected virtual T GetSentinelObject()
Returns
Type | Description |
---|---|
T | The sentinel object to use to pre-populate the queue, or |
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 virtual 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 Lucene.Net.Util.PriorityQueue`1.maxSize elements.
Declaration
public virtual T InsertWithOverflow(T element)
Parameters
Type | Name | Description |
---|---|---|
T | element |
Returns
Type | Description |
---|---|
T |
LessThan(T, T)
Determines the ordering of objects in this priority queue. Subclasses must define this one method.
Declaration
protected abstract bool LessThan(T a, T b)
Parameters
Type | Name | Description |
---|---|---|
T | a | |
T | b |
Returns
Type | Description |
---|---|
System.Boolean |
|
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. |