org.apache.lucene.util

Class PriorityQueue


public abstract class PriorityQueue
extends java.lang.Object

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.

Method Summary

void
adjustTop()
Should be called when the Object at top changes values.
void
clear()
Removes all entries from the PriorityQueue.
protected void
initialize(int maxSize)
Subclass constructors must call this.
boolean
insert(Object element)
Adds element to the PriorityQueue in log(size) time if either the PriorityQueue is not full, or not lessThan(element, top()).
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)
Adds an Object to a PriorityQueue in log(size) time.
int
size()
Returns the number of elements currently stored in the PriorityQueue.
Object
top()
Returns the least element of the PriorityQueue in constant time.

Method Details

adjustTop

public final void adjustTop()
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.adjustTop(); }
 
instead of
  { o = pq.pop(); o.change(); pq.push(o); }
 

clear

public final void clear()
Removes all entries from the PriorityQueue.

initialize

protected final void initialize(int maxSize)
Subclass constructors must call this.

insert

public boolean insert(Object element)
Adds element to the PriorityQueue in log(size) time if either the PriorityQueue is not full, or not lessThan(element, top()).
Parameters:
element -
Returns:
true if element is added, false otherwise.

lessThan

protected abstract boolean lessThan(Object a,
                                    Object b)
Determines the ordering of objects in this priority queue. Subclasses must define this one method.

pop

public final Object pop()
Removes and returns the least element of the PriorityQueue in log(size) time.

put

public final void put(Object element)
Adds an Object to a PriorityQueue in log(size) time. If one tries to add more objects than maxSize from initialize a RuntimeException (ArrayIndexOutOfBound) is thrown.

size

public final int size()
Returns the number of elements currently stored in the PriorityQueue.

top

public final Object top()
Returns the least element of the PriorityQueue in constant time.

Copyright © 2000-2006 Apache Software Foundation. All Rights Reserved.