org.apache.solr.response

Class SortingResponseWriter.PriorityQueue<T>

java.lang.Object

org.apache.solr.response.SortingResponseWriter.PriorityQueue<T>

Enclosing class:

SortingResponseWriter

public abstract class SortingResponseWriter.PriorityQueue<T>
extends Object

Field Summary

Fields

Modifier and Type	Field and Description
protected int	maxSize
protected int	size

Constructor Summary

Constructors

Constructor and Description
SortingResponseWriter.PriorityQueue(int maxSize)
SortingResponseWriter.PriorityQueue(int maxSize, boolean prepopulate)

Method Summary

Methods

Modifier and Type	Method and 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.

Methods inherited from class java.lang.Object

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

Field Detail

size

protected int size

maxSize

protected final int maxSize

Constructor Detail

SortingResponseWriter.PriorityQueue

public SortingResponseWriter.PriorityQueue(int maxSize)

SortingResponseWriter.PriorityQueue

public SortingResponseWriter.PriorityQueue(int maxSize,
                                   boolean prepopulate)

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 to

 pq.top().change();
 pq.updateTop();
 

instead of

 o = 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.