org.apache.solr.util
Class LongPriorityQueue

java.lang.Object
  org.apache.solr.util.LongPriorityQueue

public class LongPriorityQueue
extends Object

A native long priority queue.

NOTE: This API is for internal purposes only and might change in incompatible ways in the next release.

Field Summary

protected int	currentCapacity
protected long[]	heap
protected int	maxSize
protected long	sentinel
protected int	size

Constructor Summary

LongPriorityQueue(int initialSize, int maxSize, long sentinel)

Method Summary

long	add(long element) Adds an object to a PriorityQueue in log(size) time.
void	addNoCheck(long element) Adds an object to a PriorityQueue in log(size) time.
void	clear() Removes all entries from the PriorityQueue.
int	getCurrentCapacity()
long[]	getInternalArray() Returns the array used to hold the heap, with the smallest item at array[1] and the last (but not necessarily largest) at array[size()].
protected void	initialize(int sz)
boolean	insert(long element) inserts the element and returns true if this element caused another element to be dropped from the queue.
long	insertWithOverflow(long element) Adds an object to a PriorityQueue in log(size) time.
long	pop() Removes and returns the least element of the PriorityQueue in log(size) time.
void	resize(int sz)
int	size() Returns the number of elements currently stored in the PriorityQueue.
long[]	sort(int n) Pops the smallest n items from the heap, placing them in the internal array at arr[size] through arr[size-(n-1)] with the smallest (first element popped) being at arr[size].
long	top() Returns the least element of the PriorityQueue in constant time.
long	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

currentCapacity

protected int currentCapacity

maxSize

protected int maxSize

heap

protected long[] heap

sentinel

protected final long sentinel

Constructor Detail

LongPriorityQueue

public LongPriorityQueue(int initialSize,
                         int maxSize,
                         long sentinel)

Method Detail

initialize

protected void initialize(int sz)

getCurrentCapacity

public int getCurrentCapacity()

resize

public void resize(int sz)

add

public long add(long element)

Adds an object to a PriorityQueue in log(size) time. If one tries to add more objects than maxSize from initialize an ArrayIndexOutOfBoundsException is thrown.

Returns:

the new 'top' element in the queue.

addNoCheck

public void addNoCheck(long element)

Adds an object to a PriorityQueue in log(size) time. If one tries to add more objects than the current capacity, an ArrayIndexOutOfBoundsException is thrown.

insertWithOverflow

public long insertWithOverflow(long element)

Adds an object to a PriorityQueue in log(size) time. It returns the smallest object (if any) that was dropped off the heap because it was full, or the sentinel value. 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.

insert

public boolean insert(long element)

inserts the element and returns true if this element caused another element to be dropped from the queue.

top

public long top()

Returns the least element of the PriorityQueue in constant time.

pop

public long pop()

Removes and returns the least element of the PriorityQueue in log(size) time. Only valid if size() > 0.

updateTop

public long updateTop()

Should be called when the Object at top changes values.

Returns:

the new 'top' element.

size

public int size()

Returns the number of elements currently stored in the PriorityQueue.

getInternalArray

public long[] getInternalArray()

Returns the array used to hold the heap, with the smallest item at array[1] and the last (but not necessarily largest) at array[size()]. This is *not* fully sorted.

sort

public long[] sort(int n)

Pops the smallest n items from the heap, placing them in the internal array at arr[size] through arr[size-(n-1)] with the smallest (first element popped) being at arr[size]. The internal array is returned.

clear

public void clear()

Removes all entries from the PriorityQueue.