Package org.apache.lucene.util

Class LongHeap

java.lang.Object

org.apache.lucene.util.LongHeap

public abstract class LongHeap
extends Object

A heap that stores longs; a primitive priority queue that like all priority queues 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). This heap provides unbounded growth via push(long), and bounded-size insertion based on its nominal maxSize via insertWithOverflow(long). The heap may be either a min heap, in which case the least element is the smallest integer, or a max heap, when it is the largest, depending on the Order parameter.

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

Nested Class Summary

Nested Classes

Modifier and Type	Class	Description
static class	LongHeap.Order	Used to specify the ordering of the heap.

Method Summary

Modifier and Type	Method	Description
void	clear()	Removes all entries from the PriorityQueue.
static LongHeap	create(LongHeap.Order order, int maxSize)
long	get(int i)	Return the element at the ith location in the heap array.
protected long[]	getHeapArray()	This method returns the internal heap array.
boolean	insertWithOverflow(long value)	Adds a value to an LongHeap in log(size) time.
abstract boolean	lessThan(long a, long b)	Determines the ordering of objects in this priority queue.
long	pop()	Removes and returns the least element of the PriorityQueue in log(size) time.
long	push(long element)	Adds a value in log(size) time.
void	pushAll(LongHeap other)
int	size()	Returns the number of elements currently stored in the PriorityQueue.
long	top()	Returns the least element of the LongHeap in constant time.
long	updateTop(long value)	Replace the top of the pq with newTop.

Methods inherited from class java.lang.Object

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

Method Detail

create

public static LongHeap create(LongHeap.Order order,
                              int maxSize)

lessThan

public abstract boolean lessThan(long a,
                                 long 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.

push

public final long push(long element)

Adds a value in log(size) time. Grows unbounded as needed to accommodate new values.

Returns:

the new 'top' element in the queue.

insertWithOverflow

public boolean insertWithOverflow(long value)

Adds a value to an LongHeap in log(size) time. If the number of values would exceed the heap's maxSize, the least value is discarded.

Returns:

whether the value was added (unless the heap is full, or the new value is less than the top value)

top

public final long top()

Returns the least element of the LongHeap in constant time. It is up to the caller to verify that the heap is not empty; no checking is done, and if no elements have been added, 0 is returned.

pop

public final long pop()

Removes and returns the least element of the PriorityQueue in log(size) time.

Throws:

IllegalStateException - if the LongHeap is empty.

updateTop

public final long updateTop(long value)

Replace the top of the pq with newTop. Should be called when the top value changes. Still log(n) worst case, but it's at least twice as fast to

 pq.updateTop(value);
 

instead of

 pq.pop();
 pq.push(value);
 

Calling this method on an empty LongHeap has no visible effect.

Parameters:

value - the new element that is less than the current top.

Returns:

the new 'top' element after shuffling the heap.

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.

pushAll

public void pushAll(LongHeap other)

get

public long get(int i)

Return the element at the ith location in the heap array. Use for iterating over elements when the order doesn't matter. Note that the valid arguments range from [1, size].

getHeapArray

protected final long[] getHeapArray()

This method returns the internal heap array.

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