jdsl.core.api
Interface PriorityQueue

All Known Implementing Classes:
SequenceLocPriorityQueue, BTHeap

public abstract interface PriorityQueue
extends KeyBasedContainer

A priority queue is a partially-ordered container that allows for removal of the element with lowest (or highest, depending on the comparator used) priority. It does not specify any implementation; one implementation, however, is with a heap, which gives O(log N) time complexity for the two basic operations: insert(.) and removeMax().

The elements need to be comparable using whatever means the PQ has of making comparisons. If an element is not comparable, the priority queue will throw an InvalidElementException.

Author:
Mark Handy (mdh), Roberto Tamassia (rt)

Method Summary
 void insertItem(java.lang.Object key, java.lang.Object element)
          Add a (key,element) pair to the set maintained by the priority queue, making whatever internal adjustments are necessary.
 Locator min()
          Allows access to element with first priority without removing it from the PriorityQueue.
 java.lang.Object minElement()
          Inspect the element (not the key) with first priority, without modifying the priority queue.
 java.lang.Object minKey()
          Inspect the key with first priority, without modifying the priority queue.
 java.lang.Object removeMinElement()
          Remove a (key,element) pair with first priority, making whatever internal adjustments are necessary.
 
Methods inherited from interface jdsl.core.api.KeyBasedContainer
insert, insert, keys, locators, makeLocator, remove, replaceElement, replaceKey
 
Methods inherited from interface jdsl.core.api.Container
elements, newContainer
 
Methods inherited from interface jdsl.simple.api.SimpleContainer
isEmpty, size
 

Method Detail

min

public Locator min()
            throws EmptyContainerException
Allows access to element with first priority without removing it from the PriorityQueue.

Returns:
Locator to the element with first priority
Throws:
EmptyContainerException - if the PriorityQueue is empty

minElement

public java.lang.Object minElement()
                            throws EmptyContainerException
Inspect the element (not the key) with first priority, without modifying the priority queue.
Returns:
The client element associated with a key of first priority
Throws:
EmptyContainerException - if the PriorityQueue is empty

minKey

public java.lang.Object minKey()
                        throws EmptyContainerException
Inspect the key with first priority, without modifying the priority queue.
Returns:
A key of first priority among those in the priority queue
Throws:
EmptyContainerException - if the PriorityQueue is empty

insertItem

public void insertItem(java.lang.Object key,
                       java.lang.Object element)
                throws InvalidKeyException
Add a (key,element) pair to the set maintained by the priority queue, making whatever internal adjustments are necessary.
Parameters:
key - An object comparable under the implementation's comparison scheme
element - An arbitrary object the client associates with the key

removeMinElement

public java.lang.Object removeMinElement()
                                  throws EmptyContainerException
Remove a (key,element) pair with first priority, making whatever internal adjustments are necessary.
Returns:
The client element (not the key) removed
Throws:
EmptyContainerException - if the PriorityQueue is empty