Last update: Wednesday, July 5, 9 AM.
Your assignment is to take an existing, inefficient implementation of a priority queue and modify it, creating a more efficient implementation that uses a heap. The code you are provided with also implements a priority queue in a job shop scenario, where the various jobs are scheduled in an unsophisticated way. You will implement two scheduling algorithms, both more sophisticated than the initial algorithm. With this first programming assignment, we will provide a fair amount of code and guidance.
You are provided with a number of different files that implement an inefficient version of a priority queue and a simple scheduling algorithm. The files are accessible on the web; this page contains the necessary links. The files are described below.
PriorityQueue.java: This is the file that you will have to change most extensively. It contains code for an abstract class PriorityQueue. The class is abstract because one of its methods is abstract (i.e., its code is unspecified). Abstract classes cannot be instantiated, but their subclasses can if they provide code to implement the abstract methods. PriorityQueue's public methods are:
abstract boolean before(Object,Object)
returns true iff the first Object comes before the second Object
void insert(Object)
place an item into the queue
boolean isEmpty()
check if the queue is empty
Object peek()
return the least item in the queue
Object get()
return the least item in the queue after deleting it
void clear()
remove everything from the queue
int size()
return the number of items in the queue
String toString()
return a String that indicates the contents of the priority queue
Job.java: This file contains the class Job, a class that represents a single job which needs to be accomplished. You will not need to change this file.
PQJob.java: This file contains the class PQJob, a class that implements a priority queue on Jobs using alphabetical order of the Jobs' names. PQJob is a subclass of the abstract class PriorityQueue; it overrides the before method to provide an ordering on items in the priority queue. You will not need to change this file.
PQTest.java: This file contains the class PQTest, an applet/application for testing the priority queue. You will only need to change one line of this file.
Instead of using an array as described in the text, your heap should use the class Vector. The current, inefficient version of PriorityQueue also uses Vector and you should be able to get some idea of how vectors are used by examining the code. The advantage of vectors is that they automatically grow when needed, in contrast to arrays, which have a fixed size.
For access to elements, a Vector acts more or less like an array, except you use v.elementAt(i) instead of v[i]. You can assign a value to position i within a Vector by using setElementAt(i). The current size of the vector v is given by v.size(). The method v.addElement(Object) adds the given Object as the last element in v. You will probably also want to make use of removeElementAt(int) which removes the element at the given location; it also moves any following elements to fill in the empty spot. You should also take a look at java.util.Vector in the Java API---look at the online help in MS Developer Studio or the Java API Documentation at javasoft on the Web.
Side Comment: Your version of PriorityQueue will be more efficient than the original version, but you won't be able to notice this by timing how fast things run in the testing program we provide. This is because the testing program always examines the entire contents of the Priority Queue after each operation in order to display a string representation of the priority queue. Presumably, if we weren't displaying the priority queue after each operation, then your new version would be noticeably faster for large queues. In any case, none of the queues you'll use will be that large.
The description given here is for running the program using Microsoft Developer Studio/Visual J++ 6.0. You don't have to use this software; there are several other products that can compile and run Java code.
See the MS Developer Studio handout for basic information on how to run Developer Studio, create projects, add and delete files, compile, run and debug your program, etc.
To run PQTest as a stand-alone application outside of Developer Studio: After compiling, there should be a file Project1.exe (or some other number) in your project directory produced by Developer Studio. Double click on it.
This is in part up to you. In general, in addition to testing some commonly-expected inputs, you need to test unusual inputs which are more likely to cause a program to fail. Another good rule of thumb is you should test with small data sets first, only testing larger inputs after you are confident the program works well on small amounts of data. To help you get started, at a minimum you should test as follows:
We want to see: