m865.datastructures
Class PriorityQueueAL

java.lang.Object
  extended bym865.datastructures.AbstractPriorityQueue
      extended bym865.datastructures.PriorityQueueAL
All Implemented Interfaces:
java.lang.Cloneable, java.util.Collection

public class PriorityQueueAL
extends AbstractPriorityQueue

This class implements a Queue using a dynamic array

Version:
2.1 09/26/05
Author:
Daniel D. Warner

Nested Class Summary
 class PriorityQueueAL.PriorityQueueALIterator
          The iterator for this PriorityQueueAL class.
 
Field Summary
protected  java.util.ArrayList v
          The dynamic array is implemented with the java.util.ArrayList
 
Fields inherited from class m865.datastructures.AbstractPriorityQueue
hash
 
Constructor Summary
  PriorityQueueAL()
          Constructs a queue whose dynamic array has the default initial size for a ArrayList.
  PriorityQueueAL(java.util.Collection c)
          Constructs a priority queue which is initialized with the objects in the specified collection.
  PriorityQueueAL(int capacity)
          Constructs a priority queue whose dynamic array has a specified initial size.
protected PriorityQueueAL(int hash, java.util.ArrayList v)
          Constructs a queue with a specified hash code and a clone of the specified ArrayList.
 
Method Summary
 void adjustPriority(Prioritizeable obj, java.lang.Comparable priority)
          Locates the specified object in the heap, changes its priority to the specified priority, and adjusts the location of the object in the heap.
protected  void bubbleUp(int child)
          Moves this item at the specified position up the heap according to its priority.
 void clear()
          Removes all the objects from this queue.
 java.lang.Object clone()
          The Cloneable Interface indicates that the clone method, which is inherited from Object, is implemented so that a true clone (a true and independent copy) of the object is returned.
 boolean contains(java.lang.Object obj)
          Determines whether the specified object is contained in the priority queue.
 java.lang.Object dequeue()
          Removes and returns the object at the beginning of the queue.
protected  java.lang.String dumpVector()
          This method dumps the array containing the priority queue.
 void enqueue(Prioritizeable pqi)
          Appends an object to the end of the queue.
 boolean equals(java.lang.Object obj)
          The test for equality.
 java.util.Iterator iterator()
          A factory method which returns an Iterator to the collection in this priority queue.
static void main(java.lang.String[] args)
          This main method tests the PriorityQueueAL class to insure that the elementary functions are correct.
 java.lang.Object peek()
          Returns the object at the beginning of the queue.
 boolean remove(java.lang.Object obj)
          Removes the specified object from this priority queue.
protected  void siftDown(int parent)
          Moves this item at the specified position down the heap according to its priority.
 int size()
          Determines the size of this queue.
 java.lang.String toString()
          List the objects in the priority queue in their priorty order.
 
Methods inherited from class m865.datastructures.AbstractPriorityQueue
add, addAll, containsAll, downdateHashCode, hashCode, isEmpty, removeAll, retainAll, toArray, toArray, updateHashCode
 
Methods inherited from class java.lang.Object
finalize, getClass, notify, notifyAll, wait, wait, wait
 

Field Detail

v

protected java.util.ArrayList v
The dynamic array is implemented with the java.util.ArrayList

Constructor Detail

PriorityQueueAL

public PriorityQueueAL(int capacity)
Constructs a priority queue whose dynamic array has a specified initial size. Whenever the dynamic array is increased, it's size will determined by the default ArrayList strategy, which traditionally doubles the size.

Parameters:
capacity - the initial size of the dynamic array.

PriorityQueueAL

public PriorityQueueAL()
Constructs a queue whose dynamic array has the default initial size for a ArrayList.


PriorityQueueAL

public PriorityQueueAL(java.util.Collection c)
Constructs a priority queue which is initialized with the objects in the specified collection. Only Prioritizable objects will be added to the priority queue.

Parameters:
c - the collection of objects to be initially added to this priority queue.

PriorityQueueAL

protected PriorityQueueAL(int hash,
                          java.util.ArrayList v)
Constructs a queue with a specified hash code and a clone of the specified ArrayList. This constuctor is only for use within the class and its subclasses.

Parameters:
hash - the hash code
v - the ArrayList to be cloned.
Method Detail

bubbleUp

protected void bubbleUp(int child)
Moves this item at the specified position up the heap according to its priority. At the end of this operation the head property is maintained - namely the priority of the parent is always greater than or equal to the priority of its children.

Parameters:
child - the index of the specified item

enqueue

public void enqueue(Prioritizeable pqi)
Appends an object to the end of the queue.

Specified by:
enqueue in class AbstractPriorityQueue
Parameters:
pqi - the object to be appended to the end of the queue.

siftDown

protected void siftDown(int parent)
Moves this item at the specified position down the heap according to its priority. At the end of this operation the head property is maintained - namely the priority of the parent is always greater than or equal to the priority of its children.

Parameters:
parent - the index of the specified item

dequeue

public java.lang.Object dequeue()
Removes and returns the object at the beginning of the queue.

Specified by:
dequeue in class AbstractPriorityQueue
Returns:
the object at the beginning of the queue or null if the queue is empty.

peek

public java.lang.Object peek()
Returns the object at the beginning of the queue. The queue remains unchanged.

Specified by:
peek in class AbstractPriorityQueue
Returns:
the object at the beginning of the queue or null if the queue is empty.

adjustPriority

public void adjustPriority(Prioritizeable obj,
                           java.lang.Comparable priority)
Locates the specified object in the heap, changes its priority to the specified priority, and adjusts the location of the object in the heap.

Specified by:
adjustPriority in class AbstractPriorityQueue
Parameters:
obj - the specified prioritizeable object
priority - the specified new priority

clear

public void clear()
Removes all the objects from this queue. This is one of the optional operations specified by the Collection Interface


clone

public java.lang.Object clone()
The Cloneable Interface indicates that the clone method, which is inherited from Object, is implemented so that a true clone (a true and independent copy) of the object is returned.

Returns:
a clone (a true and independent copy) of this queue.

contains

public boolean contains(java.lang.Object obj)
Determines whether the specified object is contained in the priority queue. This method overrides the corresponding method of the abstract class, because that method uses a PriorityQueueALIterator which is inefficient for this implementation of a heap with an ArrayList.

Specified by:
contains in interface java.util.Collection
Overrides:
contains in class AbstractPriorityQueue
Parameters:
obj - the specified object to be located in the heap.
Returns:
true if this collection contains the specified Prioritizeable.

equals

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

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

iterator

public java.util.Iterator iterator()
A factory method which returns an Iterator to the collection in this priority queue. This iterator will walk through this queue from the highest priority item to the lowest. It will throw a ConcurrentModificationException if the queue is altered during the iteration.

Returns:
a PriorityQueueALIterator which will iterate through this queue from the highest priority item to the lowest.

remove

public boolean remove(java.lang.Object obj)
Removes the specified object from this priority queue.

Parameters:
obj - the specified object to be removed
Returns:
true if the object is found in the priority queue

size

public int size()
Determines the size of this queue.

Returns:
the number of objects in this queue.

toString

public java.lang.String toString()
List the objects in the priority queue in their priorty order.

Overrides:
toString in class AbstractPriorityQueue
Returns:
a formatted string listing the objects in this queue

dumpVector

protected java.lang.String dumpVector()
This method dumps the array containing the priority queue.

Returns:
a formatted string listing the objects in the heap order as stored in the array list.

main

public static void main(java.lang.String[] args)
This main method tests the PriorityQueueAL class to insure that the elementary functions are correct.

Parameters:
args - optional command line argument that will be ignored.