Package org.apache.solr.handler.export
Class PriorityQueue<T>
- java.lang.Object
-
- org.apache.solr.handler.export.PriorityQueue<T>
-
public abstract class PriorityQueue<T> extends Object
-
-
Constructor Summary
Constructors Constructor Description PriorityQueue(int maxSize)
PriorityQueue(int maxSize, boolean prepopulate)
-
Method Summary
All Methods Instance Methods Abstract Methods Concrete Methods Modifier and Type Method Description T
add(T element)
Adds an Object to a PriorityQueue in log(size) time.void
clear()
Removes all entries from the PriorityQueue.Object[]
getHeapArray()
This method returns the internal heap array as Object[].protected T
getSentinelObject()
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.
-
-
-
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()
-
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- 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 topq.top().change(); pq.updateTop();
instead ofo = 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
public 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.
-
-