m865.datastructures
Class AbstractPriorityQueue

java.lang.Object
  extended by m865.datastructures.AbstractPriorityQueue
All Implemented Interfaces:
java.lang.Iterable, java.util.Collection
Direct Known Subclasses:
PriorityQueueAL

public abstract class AbstractPriorityQueue
extends java.lang.Object
implements java.util.Collection

Abstract class for the priority queue data structure. It implements enqueue, dequeue, peek, and all the methods of the Collections interface including the optional methods. Version 3.0 eliminated Cloneable to bring it in line with the java.util conventions.


Field Summary
protected  int hash
          The cached value of the hash code for the queue.
 
Constructor Summary
AbstractPriorityQueue()
           
 
Method Summary
 boolean add(java.lang.Object obj)
          Adds a Prioritizeable object to the priority queue.
 boolean addAll(java.util.Collection c)
          Adds each object of the specified collection to the priority queue.
abstract  void adjustPriority(Prioritizeable obj, java.lang.Comparable priority)
          Finds the object and adjusts its priority.
 boolean contains(java.lang.Object obj)
          Determines if the specified object is in the priority queue.
 boolean containsAll(java.util.Collection c)
          Determines if the specified collection is contained in the queue.
abstract  java.lang.Object dequeue()
          Removes and returns the object with the highest priority in the priority queue.
protected  void downdateHashCode(java.lang.Object obj)
          Downdates the hash code for this queue
abstract  void enqueue(Prioritizeable p)
          Adds a Prioritizeable to the priority queue.
 boolean equals(java.lang.Object obj)
          The test for equality.
 int hashCode()
          Returns the value of the hash code for this priority queue.
 boolean isEmpty()
          Determines whether the queue is empty.
abstract  java.lang.Object peek()
          Returns the object with the highest priority in the priority queue.
 boolean removeAll(java.util.Collection c)
          Insures that each element of the specified collection is removed from the the priority queue.
 boolean retainAll(java.util.Collection c)
          Removes all the elements of the priority queue that are not contained in the specified collection.
 java.lang.Object[] toArray()
          Creates an array containing the objects in this priority queue.
 java.lang.Object[] toArray(java.lang.Object[] a)
          Creates an array containing the objects in this priority queue.
 java.lang.String toString()
          List the objects in the queue
protected  void updateHashCode(java.lang.Object obj)
          Updates the hash code for this queue
 
Methods inherited from class java.lang.Object
clone, finalize, getClass, notify, notifyAll, wait, wait, wait
 
Methods inherited from interface java.util.Collection
clear, iterator, remove, size
 

Field Detail

hash

protected int hash
The cached value of the hash code for the queue. It is assumed that push, pop, clear, and clone methods will properly update this hash code. The cached value of the code should be used by iterators to check for any changes in the queue while the iterator is being used.

Constructor Detail

AbstractPriorityQueue

public AbstractPriorityQueue()
Method Detail

enqueue

public abstract void enqueue(Prioritizeable p)
Adds a Prioritizeable to the priority queue.

Parameters:
p - the Prioritizeable object to be added to the priority queue.

dequeue

public abstract java.lang.Object dequeue()
Removes and returns the object with the highest priority in the priority queue. Given two objects of equal priority, there is no guarantee as to which object will be returned.

Returns:
the object with the highest priority in the priority queue, or null if the queue is empty.

peek

public abstract java.lang.Object peek()
Returns the object with the highest priority in the priority queue. The priority queue remains unchanged.

Returns:
the object with the highest priority in the priority queue, or null if the queue is empty.

adjustPriority

public abstract void adjustPriority(Prioritizeable obj,
                                    java.lang.Comparable priority)
Finds the object and adjusts its priority.

Parameters:
obj - the object whose priority is to be changed
priority - the new priority for the object

add

public boolean add(java.lang.Object obj)
Adds a Prioritizeable object to the priority queue.

Specified by:
add in interface java.util.Collection
Parameters:
obj - the object to be added to the priority queue. A ClassCastException will be thrown if the object is not an instance of a Prioritizable.
Returns:
true if the object is not null, because the queue has been changed.

addAll

public boolean addAll(java.util.Collection c)
Adds each object of the specified collection to the priority queue.

Specified by:
addAll in interface java.util.Collection
Parameters:
c - the collection of objects to be added to the priority queue. A ClassCastException will be thrown if any object in the collection is not an instance of a Prioritizable.
Returns:
true if the collection has any elements, because the queue has been changed.

contains

public boolean contains(java.lang.Object obj)
Determines if the specified object is in the priority queue.

Specified by:
contains in interface java.util.Collection
Parameters:
obj - the object to be found in the priority queue.
Returns:
true - if the specified object is in the priority queue.

containsAll

public boolean containsAll(java.util.Collection c)
Determines if the specified collection is contained in the queue.

Specified by:
containsAll in interface java.util.Collection
Parameters:
c - the collection of objects to be found in the queue.
Returns:
true - if the queue contains all of the objects in the specified collection.

equals

public boolean equals(java.lang.Object obj)
The test for equality.

Specified by:
equals in interface java.util.Collection
Overrides:
equals in class java.lang.Object
Parameters:
obj - the object which may be equal to this priority queue.
Returns:
true - if the specified object is equal to this priority queue.

hashCode

public int hashCode()
Returns the value of the hash code for this priority queue. This method should return the same hash code for any two priority queues in the mthsc865.datastructures package that have the same objects stored in the same order.

Specified by:
hashCode in interface java.util.Collection
Overrides:
hashCode in class java.lang.Object
Returns:
hash - the hashcode for this priority queue

updateHashCode

protected void updateHashCode(java.lang.Object obj)
Updates the hash code for this queue

Parameters:
obj - the object being added to the queue

downdateHashCode

protected void downdateHashCode(java.lang.Object obj)
Downdates the hash code for this queue

Parameters:
obj - the object being removeed from the queue

isEmpty

public boolean isEmpty()
Determines whether the queue is empty.

Specified by:
isEmpty in interface java.util.Collection
Returns:
true - if this collection contains no elements.

removeAll

public boolean removeAll(java.util.Collection c)
Insures that each element of the specified collection is removed from the the priority queue.

Specified by:
removeAll in interface java.util.Collection
Parameters:
c - the specified collection
Returns:
true if the priority queuen has been modified.

retainAll

public boolean retainAll(java.util.Collection c)
Removes all the elements of the priority queue that are not contained in the specified collection.

Specified by:
retainAll in interface java.util.Collection
Parameters:
c - the specified collection
Returns:
true if the priority queuen has been modified.

toArray

public java.lang.Object[] toArray()
Creates an array containing the objects in this priority queue.

Specified by:
toArray in interface java.util.Collection
Returns:
an array of the objects in the priority queue. The elements in the array will be in their priority order

toArray

public java.lang.Object[] toArray(java.lang.Object[] a)
Creates an array containing the objects in this priority queue.

Specified by:
toArray in interface java.util.Collection
Parameters:
a - an array of objects whose run type is compatible with all the objects in the queue.
Returns:
an array of objects of the same type as the elements of a. If a is large enough, then all the objects in the priority queue are copied into a, with nulls stored in any extra empty entries of a. If a is not large enough, then the method returns a new array whose objects have the same type as a.

toString

public java.lang.String toString()
List the objects in the queue

Overrides:
toString in class java.lang.Object
Returns:
a formatted string listing the objects in this queue