Overview | Package | Class | Use | Tree | Deprecated | Help
PREV CLASS NEXT CLASS | FRAMES NO FRAMES
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD

## org.apache.lucene.util
Class PriorityQueue<T>

    java.lang.Object
      org.apache.lucene.util.PriorityQueue<T>

Direct Known Subclasses:
  FieldValueHitQueue

    public abstract class PriorityQueue<T>

extends 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 will pre-allocate a full array of length `maxSize+1` if instantiated via the `PriorityQueue(int,boolean)` constructor with `prepopulate` set to `true`.

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

Constructor Summary
`PriorityQueue(int maxSize)`
`PriorityQueue(int maxSize, boolean prepopulate)`

Method Summary
`T` | `add(T element)` Adds an Object to a PriorityQueue in log(size) time.
`void` | `clear()` Removes all entries from the PriorityQueue.
`protected Object[]` | `getHeapArray()` This method returns the internal heap array as Object[].
`protected T` | `getSentinelObject()` This method can be overridden by extending classes to return a sentinel object which will be used by the `PriorityQueue(int,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.
`T` | `insertWithOverflow(T element)` Adds an Object to a PriorityQueue in log(size) time.
`protected abstract boolean` | `lessThan(T a, T b)` Determines the ordering of objects in this priority queue.
`T` | `pop()` Removes and returns the least element of the PriorityQueue in log(size) time.
`int` | `size()` Returns the number of elements currently stored in the PriorityQueue.
`T` | `top()` Returns the least element of the PriorityQueue in constant time.
`T` | `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`

Constructor Detail

### PriorityQueue

    public PriorityQueue(int maxSize)

### PriorityQueue

    public PriorityQueue(int maxSize,
                         boolean prepopulate)

Method Detail

### lessThan

    protected abstract boolean lessThan(T a,
                                        T b)

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

  Returns:
    `true` iff parameter `a` is less than parameter `b`.

### getSentinelObject

    protected T getSentinelObject()

  This method can be overridden by extending classes to return a sentinel object which will be used by the `PriorityQueue(int,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(int,boolean)` constructor `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.

### add

    public final T add(T 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.

### insertWithOverflow

    public T insertWithOverflow(T element)

  Adds an Object to a PriorityQueue 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.

### top

    public final T top()

  Returns the least element of the PriorityQueue in constant time.

### pop

    public final T pop()

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

### updateTop

    public final 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);

  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.

### getHeapArray

    protected final Object[] getHeapArray()

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

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

Overview | Package | Class | Use | Tree | Deprecated | Help
PREV CLASS NEXT CLASS | FRAMES NO FRAMES
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD

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