|
||||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |
java.lang.Object org.apache.lucene.util.PriorityQueue<T>
public abstract class PriorityQueue<T>
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 | |
---|---|
protected T[] |
heap
|
Constructor Summary | |
---|---|
PriorityQueue()
|
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 T |
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(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. |
protected void |
initialize(int maxSize)
Subclass constructors must call this. |
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 |
Field Detail |
---|
protected T[] heap
Constructor Detail |
---|
public PriorityQueue()
Method Detail |
---|
protected abstract boolean lessThan(T a, T b)
true
iff parameter a is less than parameter b.protected T getSentinelObject()
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.lessThan(T, T)
should always favor the
non-sentinel values).// extends getSentinelObject() to return a non-null value. PriorityQueueNOTE: if this method returns a non-null value, it will be called bypq = new MyQueue (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();
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.
protected final void initialize(int maxSize)
public final T add(T element)
ArrayIndexOutOfBoundsException
is thrown.
public T insertWithOverflow(T element)
public final T top()
public final T pop()
public final T updateTop()
pq.top().change(); pq.updateTop();instead of
o = pq.pop(); o.change(); pq.push(o);
public final int size()
public final void clear()
|
||||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |