rcm.util
Class PriorityQueue

java.lang.Object
  |
  +--rcm.util.PriorityQueue

public class PriorityQueue
extends java.lang.Object

Priority queue. Objects stored in a priority queue must implement the Prioritized interface.


Constructor Summary
PriorityQueue()
          Make an empty PriorityQueue.
PriorityQueue(int initialCapacity)
          Make an empty PriorityQueue with an initial capacity.
 
Method Summary
 void clear()
          Remove all objects from queue.
 boolean delete(Prioritized x)
          Delete an object from queue.
 java.lang.Object deleteMin()
          Get and delete the object with lowest priority.
static void dump(PriorityQueue q)
           
 java.util.Enumeration elements()
          Enumerate the objects in the queue, in no particular order
 boolean empty()
          Test whether queue is empty.
 java.lang.Object getMin()
          Get object with lowest priority from queue.
static void main(java.lang.String[] args)
           
 void put(Prioritized x)
          Put an object on the queue.
 int size()
          Get number of objects in queue.
 void update()
          Rebuild priority queuein case the priorities of its elements have changed since they were inserted.
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Constructor Detail

PriorityQueue

public PriorityQueue()
Make an empty PriorityQueue.


PriorityQueue

public PriorityQueue(int initialCapacity)
Make an empty PriorityQueue with an initial capacity.

Parameters:
initialCapacity - number of elements initially allocated in queue
Method Detail

put

public void put(Prioritized x)
Put an object on the queue. Doesn't check for duplicate puts.

Parameters:
x - object to put on the queue

getMin

public java.lang.Object getMin()
Get object with lowest priority from queue.

Returns:
object with lowest priority, or null if queue is empty

deleteMin

public java.lang.Object deleteMin()
Get and delete the object with lowest priority.

Returns:
object with lowest priority, or null if queue is empty

delete

public boolean delete(Prioritized x)
Delete an object from queue. If object was inserted more than once, this method deletes only one occurrence of it.

Parameters:
x - object to delete
Returns:
true if x was found and deleted, false if x not found in queue

clear

public void clear()
Remove all objects from queue.


elements

public java.util.Enumeration elements()
Enumerate the objects in the queue, in no particular order

Returns:
enumeration of objects in queue

size

public int size()
Get number of objects in queue.

Returns:
number of objects

empty

public boolean empty()
Test whether queue is empty.

Returns:
true iff queue is empty.

update

public void update()
Rebuild priority queuein case the priorities of its elements have changed since they were inserted. If the priority of any element changes, this method must be called to update the priority queue.


main

public static void main(java.lang.String[] args)

dump

public static void dump(PriorityQueue q)