| java.lang.Object
 org.apache.lucene.util.PriorityQueue
All known Subclasses: org.apache.lucene.search.FieldDocSortedHitQueue, org.apache.lucene.search.spell.SuggestWordQueue, org.apache.lucene.search.FieldSortedHitQueue, org.apache.lucene.search.PhraseQueue, org.apache.lucene.search.HitQueue, org.apache.lucene.index.SegmentMergeQueue,
| PriorityQueue | | abstract public class PriorityQueue (Code) | | 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.
|
| Method Summary | |
| final public void | adjustTop()
Should be called when the Object at top changes values. | | final public void | clear()
Removes all entries from the PriorityQueue. | | final protected void | initialize(int maxSize)
Subclass constructors must call this. | | public boolean | insert(Object element)
Adds element to the PriorityQueue in log(size) time if either
the PriorityQueue is not full, or not lessThan(element, top()). | | public Object | insertWithOverflow(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. | | abstract protected boolean | lessThan(Object a, Object b)
Determines the ordering of objects in this priority queue. | | final public Object | pop()
Removes and returns the least element of the PriorityQueue in log(size)
time. | | final public void | put(Object element)
Adds an Object to a PriorityQueue in log(size) time. | | final public int | size()
Returns the number of elements currently stored in the PriorityQueue. | | final public Object | top()
Returns the least element of the PriorityQueue in constant time. |
| adjustTop | | final public void adjustTop()(Code) | | 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); }
|
| clear | | final public void clear()(Code) | | Removes all entries from the PriorityQueue.
|
| initialize | | final protected void initialize(int maxSize)(Code) | | Subclass constructors must call this.
|
| insert | | public boolean insert(Object element)(Code) | | Adds element to the PriorityQueue in log(size) time if either
the PriorityQueue is not full, or not lessThan(element, top()).
Parameters:
element - true if element is added, false otherwise. |
| insertWithOverflow | | public Object insertWithOverflow(Object element)(Code) | | 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.
|
| lessThan | | abstract protected boolean lessThan(Object a, Object b)(Code) | | Determines the ordering of objects in this priority queue. Subclasses
must define this one method.
|
| pop | | final public Object pop()(Code) | | Removes and returns the least element of the PriorityQueue in log(size)
time.
|
| put | | final public void put(Object element)(Code) | | 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.
|
| size | | final public int size()(Code) | | Returns the number of elements currently stored in the PriorityQueue.
|
| top | | final public Object top()(Code) | | Returns the least element of the PriorityQueue in constant time.
|
|
|