Due: 12 noon 27 November 2000

1. The name of your class will be PrioQueue.
2. The queue itself will be represented by a binary tree organized as a heap.
3. The binary tree will be implemented using an array of Comparable. See pages 421-423 for a discussion of implementing a binary tree using an array. The Java interface Comparable is explained below.
4. The specification of PrioQueue is nearly identical to the specification of ObjectQueue. This specification is given on pages 351-353. The difference is substituting Comparable for Object.
5. Java's Comparable interface is described at http://java.sun.com/j2se/1.3/docs/api/java/lang/Comparable.html :
   "This interface imposes a total ordering on the objects of each class that implements it. This ordering is referred to as the class's natural ordering, and the class's compareTo method is referred to as its natural comparison method."
6. The Comparable interface consists only of the compareTo method, which has this specification:
   public int compareTo(Object o)
   Parameters:
   o - the Object to be compared.
   Returns:
   a negative integer, zero, or a positive integer depending on whether "this" object is less than, equal to, or greater than the parameter object.
   Throws:
   ClassCastException - if the parameter object's type prevents it from being compared to this Object.
7. String and the Java wrapper classes all implement Comparable. You need the array (detail #3) to be of type Comparable because the objects to be stored in the array must be capable of being strictly ordered. This is necessary to satisfy the first heap property: the item in a node must have value greater than or equal to that of the item in either of its children. The other heap property is that the tree be a complete binary tree (page 484).
8. You can base your implementation on the implementation of ObjectQueue. This implementation is given on pages 353-357 and can be downloaded from http://www.cs.colorado.edu/~main/edu/colorado/collections/ObjectQueue.java.
9. NOTE: Only two of the four instance variables from ObjectQueue are needed for PrioQueue. The variables front and rear are not needed because in an array-implemented heap, the items are always stored in array elements 0 through manyItems-1.
10. I have not (yet) provided a driver program. Here's how you know your PrioQueue class works correctly: regardless of the order in which items are inserted into the queue, each call to getFront will return the highest priority item still in the queue. An easy way to test it is using Integer items. It will later be used for SimEvent items and can be used to test the SimEvent class, which is described below.
11. Some of the ObjectQueue methods can be adapted for PrioQueue with little or no change. Your major concern will be with two methods: insert() to place an item into the priority queue and getFront() to remove one. A pseudo-code description for insert() is found in Figure 10.1 on page 487. A pseudo-code description for getFront() is found in Figure 10.2 on page 489.
12. Both insert and getFront require you to compare the values of two objects. This must be done using the compareTo method that those objects are assumed to possess (The objects are stored in an array, and the array is of interface Comparable. Therefore any objects stored in the array must be instances of a class which implements Comparable, and any class which implements Comparable is required to define compareTo.).

You must also implement this class of items to be stored in the PrioQueue. You will need it in homework 9.

• This class will be called SimEvent and it implements Comparable.
• SimEvent has two private int instance variables: time and type. Both will hold only non-negative values.
• SimEvent has a constructor which takes two parameters containing values for the instance variables.
• SimEvent has accessor methods for both instance variables: getTime and getType
• SimEvent has a toString method which returns the String "time = xxxx type = xxxx" (substitute values for x)
• SimEvent has the compareTo method, as required to correctly implement Comparable
• For ordering purposes, the earlier the event time, the higher its priority. If two events are to occur at the same time, the tie-breaker is event type. The higher the event type, the higher its priority.
• Specifically, here is how SimEvent objects e1 and e2 are ordered:
• e1 is equal to e2 if and only if e1.time == e2.time && e1.type == e2.type
• e1 is less than e2 if and only if e1.time > e2.time || ( e1.time == e2.time && e1.type < e2.type)
• e1 is greater than e2 if and only if e1.time < e2.time || ( e1.time == e2.time && e1.type > e2.type)
• Document the SimEvent class using javadoc-style comments.

When finished, submit PrioQueue.java and SimEvent.java to your upload folder.

[ Assignments | CSC 132 | Peter Sanderson | Computer Science | SMSU ]

Peter Sanderson ( PeteSanderson@smsu.edu )