|
||||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |
java.lang.Object org.apache.lucene.util.PriorityQueue
public abstract class PriorityQueue
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 Object[] |
heap
|
Constructor Summary | |
---|---|
PriorityQueue()
|
Method Summary | |
---|---|
Object |
add(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 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(Object element)
Deprecated. use insertWithOverflow(Object) instead, which
encourages objects reuse. |
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. |
protected abstract boolean |
lessThan(Object a,
Object b)
Determines the ordering of objects in this priority queue. |
Object |
pop()
Removes and returns the least element of the PriorityQueue in log(size) time. |
void |
put(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. |
Object |
top()
Returns the least element of the PriorityQueue in constant time. |
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 |
---|
protected Object[] heap
Constructor Detail |
---|
public PriorityQueue()
Method Detail |
---|
protected abstract boolean lessThan(Object a, Object b)
protected Object 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(Object, Object)
should always favor the
non-sentinel values).// 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.
protected final void initialize(int maxSize)
public final void put(Object element)
add(Object)
which returns the new top object,
saving an additional call to top()
.
public final Object add(Object element)
ArrayIndexOutOfBoundsException
is thrown.
public boolean insert(Object element)
insertWithOverflow(Object)
instead, which
encourages objects reuse.
element
-
public Object insertWithOverflow(Object element)
public final Object top()
public final Object pop()
public final void adjustTop()
updateTop()
which returns the new top element and
saves an additional call to top()
.
pq.top().change(); pq.adjustTop();instead of
o = pq.pop(); o.change(); pq.push(o);
public final Object 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 |