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)


Copyright 2003 by University of Maryland, College Park, MD 20742, USA All rights reserved.