net.jxta.search.util
Class PriorityQueue

java.lang.Object
  |
  +--net.jxta.search.util.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.


Constructor Summary
PriorityQueue()
           
 
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 startSize)
          Subclass constructors must call this.
protected  void initialize(int startSize, int growthFactor)
           
protected abstract  boolean lessThan(java.lang.Object a, java.lang.Object b)
          Determines the ordering of objects in this priority queue.
 java.lang.Object pop()
          Removes and returns the least element of the PriorityQueue in log(size) time.
 void put(java.lang.Object element)
          Adds an Object to a PriorityQueue in log(size) time.
 int size()
          Returns the number of elements currently stored in the PriorityQueue.
 java.lang.Object top()
          Returns the least element of the PriorityQueue in constant time.
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Constructor Detail

PriorityQueue

public PriorityQueue()
Method Detail

lessThan

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

initialize

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

initialize

protected final void initialize(int startSize,
                                int growthFactor)

put

public final void put(java.lang.Object element)
Adds an Object to a PriorityQueue in log(size) time.

top

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

pop

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

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); }
 

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.