org.apache.lucene.util

## Class PriorityQueue

- java.lang.Object
- - org.apache.lucene.util.PriorityQueue

- Direct Known Subclasses:
    FieldSortedHitQueue, FieldValueHitQueue, FuzzyQuery.ScoreTermQueue

      public abstract class PriorityQueue
      extends java.lang.Object

  A PriorityQueue maintains a partial ordering of its elements such that the least element can always be found in constant time. Put()'s and pop()'s require log(size) time.

  NOTE: This class pre-allocates a full array of length `maxSize+1`, in `initialize(int)`.

- - ### Field Summary

    Fields
    Modifier and Type | Field and Description
    --- | ---
    `protected java.lang.Object[]` | `heap`

  - ### Constructor Summary

    Constructors
    Constructor and Description
    `PriorityQueue()`

  - ### Method Summary

    All Methods Instance Methods Abstract Methods Concrete Methods Deprecated Methods
    Modifier and Type | Method and Description
    --- | ---
    `java.lang.Object` | `add(java.lang.Object element)` Adds an Object to a PriorityQueue in log(size) time.
    `void` | `adjustTop()` Deprecated. use `updateTop()` which returns the new top element and saves an additional call to `top()`.
    `void` | `clear()` Removes all entries from the PriorityQueue.

    `protected java.lang.Object`

    `getSentinelObject()`
    This method can be overridden by extending classes to return a sentinel object which will be used by `initialize(int)` 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(Object, Object)` should always favor the non-sentinel values).
    By default, this method returns false, which means the queue will not be filled with sentinel values.

    `protected void` | `initialize(int maxSize)` Subclass constructors must call this.
    `boolean` | `insert(java.lang.Object element)` Deprecated. use `insertWithOverflow(Object)` instead, which encourages objects reuse.
    `java.lang.Object` | `insertWithOverflow(java.lang.Object element)` insertWithOverflow() is the same as insert() except its return value: it returns the object (if any) that was dropped off the heap because it was full.
    `protected abstract boolean` | `lessThan(java.lang.Object a, java.lang.Object b)` Determines the ordering of objects in this priority queue.
    `java.lang.Object` | `pop()` Removes and returns the least element of the PriorityQueue in log(size) time.
    `void` | `put(java.lang.Object element)` Deprecated. use `add(Object)` which returns the new top object, saving an additional call to `top()`.
    `int` | `size()` Returns the number of elements currently stored in the PriorityQueue.
    `java.lang.Object` | `top()` Returns the least element of the PriorityQueue in constant time.
    `java.lang.Object` | `updateTop()` Should be called when the Object at top changes values.

    - ### Methods inherited from class java.lang.Object

      `clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait`

- - ### Field Detail

    - #### heap

          protected java.lang.Object[] heap

  - ### Constructor Detail

    - #### PriorityQueue

          public PriorityQueue()

  - ### Method Detail

    - #### lessThan

          protected abstract boolean lessThan(java.lang.Object a,
                                              java.lang.Object b)

      Determines the ordering of objects in this priority queue. Subclasses must define this one method.

    - #### getSentinelObject

          protected java.lang.Object getSentinelObject()

      This method can be overridden by extending classes to return a sentinel object which will be used by `initialize(int)` 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(Object, Object)` 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 pq = new MyQueue(numHits);
           // save the 'top' element, which is guaranteed to not be null.
           MyObject pqTop = (MyObject) 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 `initialize(int)` `size()` 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.
      Returns:
        the sentinel object to use to pre-populate the queue, or null if sentinel objects are not supported.

    - #### initialize

          protected final void initialize(int maxSize)

      Subclass constructors must call this.

    - #### put

          public final void put(java.lang.Object element)

      Deprecated. use `add(Object)` which returns the new top object, saving an additional call to `top()`.
      Adds an Object to a PriorityQueue in log(size) time. If one tries to add more objects than maxSize from initialize a RuntimeException (ArrayIndexOutOfBound) is thrown.

    - #### add

          public final java.lang.Object add(java.lang.Object element)

      Adds an Object to a PriorityQueue in log(size) time. If one tries to add more objects than maxSize from initialize an `ArrayIndexOutOfBoundsException` is thrown.
      Returns:
        the new 'top' element in the queue.

    - #### insert

          public boolean insert(java.lang.Object element)

      Deprecated. use `insertWithOverflow(Object)` instead, which encourages objects reuse.
      Adds element to the PriorityQueue in log(size) time if either the PriorityQueue is not full, or not lessThan(element, top()).
      Parameters:
        `element` -
      Returns:
        true if element is added, false otherwise.

    - #### insertWithOverflow

          public java.lang.Object insertWithOverflow(java.lang.Object element)

      insertWithOverflow() is the same as insert() except its return value: 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.

    - #### top

          public final java.lang.Object top()

      Returns the least element of the PriorityQueue in constant time.

    - #### pop

          public final java.lang.Object pop()

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

    - #### adjustTop

          public final void adjustTop()

      Deprecated. use `updateTop()` which returns the new top element and saves an additional call to `top()`.
      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.adjustTop();

      instead of

           o = pq.pop();
           o.change();
           pq.push(o);

    - #### updateTop

          public final java.lang.Object 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);

      Returns:
        the new 'top' element.

    - #### size

          public final int size()

      Returns the number of elements currently stored in the PriorityQueue.

    - #### clear

          public final void clear()

      Removes all entries from the PriorityQueue.

Copyright © 2000-2016 Apache Software Foundation. All Rights Reserved.