org.apache.lucene.util

Class PriorityQueue

java.lang.Object

org.apache.lucene.util.PriorityQueue

Direct Known Subclasses:

FieldSortedHitQueue

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.

Constructor Summary

Constructors

Constructor and Description
PriorityQueue()

Method Summary

Modifier and Type	Method and Description
void	adjustTop() Should be called when the Object at top changes values.
void	clear() Removes all entries from the PriorityQueue.
boolean	insert(java.lang.Object element) Adds element to the PriorityQueue in log(size) time if either the PriorityQueue is not full, or not lessThan(element, top()).
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.
java.lang.Object	pop() Removes and returns the least element of the PriorityQueue in log(size) time.
void	put(java.lang.Object element) Adds an Object to a PriorityQueue in log(size) time.
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.

Methods inherited from class java.lang.Object

equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

PriorityQueue

public PriorityQueue()

Method Detail

put

public final void put(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 a RuntimeException (ArrayIndexOutOfBound) is thrown.

insert

public boolean insert(java.lang.Object element)

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()

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); }
 

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.