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.

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
private static class	PriorityQueueRVM.PriorityQueueNode A local class that holds the nodes of the priority tree

Field Summary

Fields

Modifier and Type	Field and Description
private int	numElements the number of elements actually in the queue
private PriorityQueueRVM.PriorityQueueNode[]	queue the queue, we use elements 1..queue.length

Constructor Summary

Constructors

Modifier	Constructor and Description
protected	PriorityQueueRVM()

Method Summary

Modifier and Type	Method and Description
Object	deleteMin() Remove and return the front (minimum) object
void	insert(double _priority, Object _data) Insert the object passed with the priority value passed
protected boolean	isEmpty() Checks if the queue is empty
int	numElements() Determines number of elements in the queue
private void	reheapify(int startingElement) Starting at the position passed, swap with parent until heap condition is satisfied, i.e., bubble up
double	rootValue() Return the priority of front object without removing it
String	toString() Prints the contents of the queue

Methods inherited from class java.lang.Object

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

Field Detail

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

Constructor Detail

PriorityQueueRVM

protected PriorityQueueRVM()

Method Detail

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