gov.nist.antd.merlin.algorithm.route.util
Interface PriorityQueue

All Known Implementing Classes:

BinaryHeap, PairingHeap

public interface PriorityQueue

This is the interface for PriorityQueue.

 This class was developed at the National Institute of Standards and
 Technology by employees of the Federal Government in the course of
 their official duties. Pursuant to title 17 Section 105 of the United
 States Code this software is not subject to copyright protection and
 is in the public domain.
 NIST assumes no responsibility whatsoever for its use by other parties,
 and makes no guarantees, expressed or implied, about its quality,
 reliability, or any other characteristic.
 

 We would appreciate acknowledgement if the software is used.
 

 NIST ALLOWS FREE USE OF THIS SOFTWARE IN ITS "AS IS" CONDITION AND
 DISCLAIM ANY LIABILITY OF ANY KIND FOR ANY DAMAGES WHATSOEVER RESULTING
 FROM THE USE OF THIS SOFTWARE.
 

Version:

1.1

 VERSION CONTROL

 -------------------------------------------------------------------------

 Name - YYYY/MM/DD - VERSION - ACTION

 rouil - 2001/07/11 - 1.0 - Source created

 rouil - 2002/01/29 - 1.1 - Changed package

 

 

 

Author:

borchert

, rouil

Nested Class Summary

static interface

PriorityQueue.Position The Position interface represents a type that can be used for the decreaseKey operation.

Method Summary

void	decreaseKey(PriorityQueue.Position p, java.lang.Comparable newVal) Change the value of the item stored in the pairing heap.
java.lang.Comparable	deleteMin() Remove the smallest item from the priority queue.
java.lang.Comparable	findMin() Find the smallest item in the priority queue.
PriorityQueue.Position	insert(java.lang.Comparable x) Insert into the priority queue, maintaining heap order.
boolean	isEmpty() Test if the priority queue is logically empty.
void	makeEmpty() Make the priority queue logically empty.
int	size() Returns the size.

Method Detail

insert

public PriorityQueue.Position insert(java.lang.Comparable x)

Insert into the priority queue, maintaining heap order. Duplicates are allowed.

Parameters:

x - the item to insert.

Returns:

may return a Position useful for decreaseKey.

findMin

public java.lang.Comparable findMin()

Find the smallest item in the priority queue.

Returns:

the smallest item.

Throws:

UnderflowException - if empty.

deleteMin

public java.lang.Comparable deleteMin()

Remove the smallest item from the priority queue.

Returns:

the smallest item.

Throws:

UnderflowException - if empty.

isEmpty

public boolean isEmpty()

Test if the priority queue is logically empty.

Returns:

true if empty, false otherwise.

makeEmpty

public void makeEmpty()

Make the priority queue logically empty.

size

public int size()

Returns the size.

Returns:

current size.

decreaseKey

public void decreaseKey(PriorityQueue.Position p,
                        java.lang.Comparable newVal)

Change the value of the item stored in the pairing heap. This is considered an advanced operation and might not be supported by all priority queues. A priority queue will signal its intention to not support decreaseKey by having insert return null consistently.

Parameters:

p - any non-null Position returned by insert.

newVal - the new value, which must be smaller than the currently stored value.

Throws:

java.lang.IllegalArgumentException - if p invalid