giden.GRDS
Class PriorityQueue

java.lang.Object
  |
  +--giden.GRDS.PriorityQueue
Direct Known Subclasses:
PQList

public abstract class PriorityQueue
extends java.lang.Object

Copyright (c) 1993-2004 C. R. Coullard, D. S. Dilworth, J. H. Owen, All Rights Reserved.
We make no representations or warranties about the suitability of the software, either express or implied, including but not limited to the implied warranties of merchantability, fitness for a particular purpose, or non-infringement. We shall not be liable for any damages suffered by user as a result of using, modifying or distributing this software or its derivatives.

PriorityQueue (PQ) is a class that stores objects with associated integer values. Objects can be retrieved from the PQ sorted by the integer value (smallest to largest). The integer value associated with an object can be decreased.

PriorityQueue is an abstract base class, and hence can not be directly created. Currently GIDEN only supports the PQList priority queue that is derived from the PriorityQueue class. Other types of PQ classes (e.g. PQHeap) may be developed in the future and they will use a similar (if not identical) set of interface methods and parameters.

Copyright (c) 1993-2003 C. R. Coullard, D. S. Dilworth, J. H. Owen, All Rights Reserved.

Version:
4.0a 2004 08 27
Author:
D. S. Dilworth
See Also:
Network, Queue, BoundedQueue, LinkList, PQList

Constructor Summary
PriorityQueue()
          Creates a Priority Queue (PQ)
 
Method Summary
 void DecreaseValue(java.lang.Object item, int value)
          Decreases the value of the item
 Edge DeleteMinEdge()
          Deletes the edge with the smallest value
 Node DeleteMinNode()
          Deletes the node with the smallest value
 Edge GetMinEdge()
          Gets the edge with the smallest value
 Node GetMinNode()
          Gets the node with the smallest value
 int GetSize()
          Gets the number of elements in this PQ
 void Insert(java.lang.Object item, int value)
          Inserts the object with its value into this PQ
 boolean IsEmpty()
          Tests if this PQ is empty
 boolean IsMember(java.lang.Object object)
          Test if the object is a member of this PQ
 boolean NotEmpty()
          Test if the PQ is not empty
 
Methods inherited from class java.lang.Object
equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Constructor Detail

PriorityQueue

public PriorityQueue()
Creates a Priority Queue (PQ)
Method Detail

Insert

public void Insert(java.lang.Object item,
                   int value)
Inserts the object with its value into this PQ
Parameters:
item - The item to insert
value - The value to assign to the item

GetSize

public int GetSize()
Gets the number of elements in this PQ
Returns:
The size of this PQ

IsEmpty

public boolean IsEmpty()
Tests if this PQ is empty
Returns:
True if the PQ is empty, else false
See Also:
NotEmpty()

NotEmpty

public boolean NotEmpty()
Test if the PQ is not empty
Returns:
True if the PQ is not empty, else false
See Also:
IsEmpty()

GetMinNode

public Node GetMinNode()
Gets the node with the smallest value
Returns:
The node with the smallest value. This method does not delete the node
See Also:
DeleteMinNode()

DeleteMinNode

public Node DeleteMinNode()
Deletes the node with the smallest value
Returns:
The node with the smallest value. This method deletes the node.
See Also:
GetMinNode()

GetMinEdge

public Edge GetMinEdge()
Gets the edge with the smallest value
Returns:
The edge with the smallest value. This method does not delete the edge
See Also:
DeleteMinEdge()

DeleteMinEdge

public Edge DeleteMinEdge()
Deletes the edge with the smallest value
Returns:
The edge with the smallest value. This method deletes the edge.
See Also:
GetMinEdge()

IsMember

public boolean IsMember(java.lang.Object object)
Test if the object is a member of this PQ
Parameters:
object - The object to test
Returns:
True if the object is a member of the PQ

DecreaseValue

public void DecreaseValue(java.lang.Object item,
                          int value)
Decreases the value of the item
Parameters:
item - The item whose value is to be changed
value - The new value for the item