Homework Assignment 3
I have provided a skeleton of the edu.gmu.cs.queue.PriorityQueue
class which you should modify
and complete. The queue uses a heap similar to that created in homework 2. Aside from
implementing the methods of the queue class, you will need to implement the compareTo
method in the PriorityItem
class. This class is holds the priority value (a primitive int
)
, a timestamp, and the actual data that is put into the queue.
This assignment is significantly shorter than past assignments, but please get an early start because I will not be able to accept late assignments.
Some basic unit tests are provided to help check your implementation; however, passing these tests does not mean an implementation is correct. There are edge cases not checked by the provided unit tests and this assignment includes requirements not unit-testable.
Table of Contents
Download
The skeleton project may be downloaded here. (Not yet, contact me for the project archive.)
Due date
Your project, including all source code, must be submitted by midnight on December 12th.
Submissions are accepted over email.
Requirements
-
Implement all methods in the
edu.gmu.cs.queue.PriorityQueue
class file.- Methods that should throw exceptions in error cases are marked with Java's builtin syntax "throws <ExceptionType>".
-
Implement the
compareTo
method inedu.gmu.cs.queue.PriorityItem
. For the example,x.compareTo(y)
, a -1 should be returned when x is less than y, a +1 should be returned when x is greater than y, and 0 should be returned when x and y are equal.-
Keep in mind that you should be using both the priority number
(higher value means more important) and the timestamp
(which is a
long
type, earlier times have smaller value).
-
Keep in mind that you should be using both the priority number
(higher value means more important) and the timestamp
(which is a
Suggestions
- Write private helper methods to help keep any of your methods from becoming too big or complicated.
Project layout
The project has the following directory layout:
-
PriorityQueue/
-
src/
- all program source code
-
build/
- all program class files
-
lib/
- all project library dependencies
-
dist/
-
lib/
- classes packaged in JAR file
-
lib/
-
test/
- all test classes
- build.xml
-
src/
Building and testing
The build.xml file is an ant build file. Ant is a Java build tool that can be used to simplify the process of building, testing, deploying, and running Java programs.
Ant may not already be installed on your computer but can be obtained from here. Some IDEs, such as Eclipse, may include ant. Please feel free to use whatever development tools and IDEs you prefer.
You will also need the JDK installed to compile your code. The JDK can be obtained from here.
To build all source files and create the JAR file:
-
ant dist
The dist
task is the default for our build file, so you may also run:
-
ant
If you would like to clean all compiled classes run:
-
ant clean
To run the unit tests:
-
ant test
HTML generated by org-mode 6.35i in emacs 23