edu.umd.cs.jazz.util
Class ZPriorityQueue

java.lang.Object
  |
  +--edu.umd.cs.jazz.util.ZPriorityQueue

public class ZPriorityQueue

extends java.lang.Object

ZPriorityQueue is a heap based PriorityQueue that stores objects of type java.lang.Comparable. The default ordering is by maximum value.

Author:

Jesse Grosjean

Field Summary

static int	QUEUE_MAXIMUM_ORDERING
static int	QUEUE_MINIMUM_ORDERING

Constructor Summary

ZPriorityQueue()
Construct a new priority queue, ordering by maximum value.

ZPriorityQueue(int aOrdering)
Construct a new priority queue.

Method Summary

protected void	contract()
protected java.util.ArrayList	elements()
protected void	exchange(int a, int b)
protected void	expand()
java.lang.Object	extractFirst() Return the first object in the queue.
java.lang.Object	first() Return the first object in the queue.
protected java.lang.Comparable	get(int index)
protected void	heapify(int index)
void	insert(java.lang.Comparable aComparable) Insert a new item into the queue.
boolean	isEmpty() Return true if the queue is empty.
protected boolean	isProposedOrderCorrect(java.lang.Comparable aProposedFirst, java.lang.Comparable aProposedSecond)
protected int	left(int index)
protected int	parent(int index)
protected int	right(int index)
protected void	set(int index, java.lang.Comparable aComparable)
int	size() Return the number of items currently in the queue.

Methods inherited from class java.lang.Object

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

Field Detail

QUEUE_MAXIMUM_ORDERING

public static final int QUEUE_MAXIMUM_ORDERING

See Also:

Constant Field Values

QUEUE_MINIMUM_ORDERING

public static final int QUEUE_MINIMUM_ORDERING

See Also:

Constant Field Values

Constructor Detail

ZPriorityQueue

public ZPriorityQueue()

Construct a new priority queue, ordering by maximum value.

ZPriorityQueue

public ZPriorityQueue(int aOrdering)

Construct a new priority queue.

Parameters:

aOrdering - determines the ordering of items stored in the queue. use ZPriorityQueue.QUEUE_MAXIMUM_ORDERING or ZPriorityQueue.QUEUE_MINIMUM_ORDERING

Method Detail

insert

public void insert(java.lang.Comparable aComparable)

Insert a new item into the queue.

first

public java.lang.Object first()

Return the first object in the queue. This will either be the maximum or minimum valued object as determined by the queue ordering. This operation does not remove the object from the queue.

extractFirst

public java.lang.Object extractFirst()

Return the first object in the queue. This will either be the maximum or minimum valued object as determined by the queue ordering. This operation removes the object from the queue.

size

public int size()

Return the number of items currently in the queue.

isEmpty

public boolean isEmpty()

Return true if the queue is empty.

elements

protected java.util.ArrayList elements()

parent

protected int parent(int index)

left

protected int left(int index)

right

protected int right(int index)

heapify

protected void heapify(int index)

exchange

protected void exchange(int a,
                        int b)

get

protected java.lang.Comparable get(int index)

set

protected void set(int index,
                   java.lang.Comparable aComparable)

expand

protected void expand()

contract

protected void contract()

isProposedOrderCorrect

protected boolean isProposedOrderCorrect(java.lang.Comparable aProposedFirst,
                                         java.lang.Comparable aProposedSecond)