org.jikesrvm.util
Class PriorityQueueRVM

java.lang.Object
  org.jikesrvm.util.PriorityQueueRVM

Direct Known Subclasses:

BlockingPriorityQueue

public class PriorityQueueRVM
extends Object

This class implements a priority queue using the standard (balanced partially-ordered tree, i.e., "heap") algorithm. Smaller priority objects are in the front of the queue.

queue

private PriorityQueueRVM.PriorityQueueNode[] queue

the queue, we use elements 1..queue.length

numElements

private int numElements

the number of elements actually in the queue

PriorityQueueRVM

protected PriorityQueueRVM()

numElements

public final int numElements()

Determines number of elements in the queue

Returns:

number of elements in the queue

isEmpty

protected final boolean isEmpty()

Checks if the queue is empty

Returns:

is the queue empty?

reheapify

private void reheapify(int startingElement)

Starting at the position passed, swap with parent until heap condition is satisfied, i.e., bubble up

Parameters:

startingElement - the position to start at

insert

public void insert(double _priority,
                   Object _data)

Insert the object passed with the priority value passed

Parameters:

_priority - the priority of the inserted object

_data - the object to insert

deleteMin

public Object deleteMin()

Remove and return the front (minimum) object

Returns:

the front (minimum) object or null if the queue is empty.

rootValue

public final double rootValue()

Return the priority of front object without removing it

Returns:

the priority of the front object

toString

public String toString()

Prints the contents of the queue

Overrides:

toString in class Object

Returns:

the queue contents