Show / Hide Table of Contents

    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.

    This is a Lucene.NET INTERNAL API, use at your own risk
    Inheritance
    System.Object
    PriorityQueue<T>
    FieldValueHitQueue<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: Lucene.Net.Util
    Assembly: Lucene.Net.dll
    Syntax
    public abstract class PriorityQueue<T>
    Type Parameters
    Name Description
    T

    Constructors

    | Improve this Doc View Source

    PriorityQueue(Int32)

    Declaration
    public PriorityQueue(int maxSize)
    Parameters
    Type Name Description
    System.Int32 maxSize
    | Improve this Doc View Source

    PriorityQueue(Int32, Boolean)

    Declaration
    public PriorityQueue(int maxSize, bool prepopulate)
    Parameters
    Type Name Description
    System.Int32 maxSize
    System.Boolean prepopulate

    Properties

    | Improve this Doc View Source

    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
    System.Int32
    | Improve this Doc View Source

    HeapArray

    This method returns the internal heap array as T[].

    This is a Lucene.NET INTERNAL API, use at your own risk
    Declaration
    protected T[] HeapArray { get; }
    Property Value
    Type Description
    T[]
    | Improve this Doc View Source

    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 Source

    Add(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.

    | Improve this Doc View Source

    Clear()

    Removes all entries from the PriorityQueue<T>.

    Declaration
    public void Clear()
    | Improve this Doc View Source

    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 null if sentinel objects are not supported.

    | Improve this Doc View Source

    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
    | Improve this Doc View Source

    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

    true if parameter a is less than parameter b.

    | Improve this Doc View Source

    Pop()

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

    Declaration
    public T Pop()
    Returns
    Type Description
    T
    | Improve this Doc View Source

    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.

    Extension Methods

    Number.IsNumber(Object)
    • Improve this Doc
    • View Source
    Back to top Copyright © 2019 Licensed to the Apache Software Foundation (ASF)