There are very many different interesting ways to implement a priority queue, some using advanced data structures (heaps, binomial trees, etc). In this assignment you and your partner will implement a simple (and slow) one, using a 1-d array. Some partners will do it one way; some partners will do it another way. You and your partner are to implement the methods depending on the last name of you and your partner, using whoever's last name comes first in the alphabet. In the Pattis/Stehlik programming partners, the implementation is done according to Pattis. You are to implement your class using one of the two following ways.
If the last name starts with A-J, write the class so that the values in the priority queue appear in the array in no special order. The enqueue method should put its value at the rear of the array (doubling its length if necessary). The dequeue method should scan this array to find the value with the highest priority, remove it (by moving the current rear value to its position -after all, there is no order in the array), and return it. The peek methods works the same, but without removing the value.
If the last name starts with K-Z, write the class so that the values in the priority queue appear in the array in a special order: sorted from lowest priority (at index 0) to highest priority (at the highest index). The enqueue method should put its value in the correct position in the array (doubling its length if necessary). The dequeue method should remove the value at the highest index (it has the highest priority) and return it. The peek methods works the same, but without removing the value.
Some ground rules: You may not write/call any sorting method in your code. Write private helper methods to avoid duplicating code inside any methods (in one implementation, there is lots of code in dequeue and peek that is similar). When you remove any references from the array, ensure that you store null there: don't leave in a reference to any old values, or duplicate references to any values.
The only loose end is how to determine which value has the highest priority (needed either in the methods that enqueue or dequeue/peek). We want SimplePriorityQueue's to acquire this prioritizing information, not have any special ordering built into them. Also, we will not assign priorities to values, but just answer the question of whether one value has a higher priority than another. This is a perfect place to use the Comparator interface.
When we construct a SimplePriorityQueue we will supply it with an object constructed from a class implementing Comparator. Then, we can use the compare method of this object to determine the priority ordering of two values whenever we need to.
You will be required to write (and add to the project) a variety of classes that implement this interface (all in a package using your standard name, e.g., edu.uci.pat.ics22). In the first four implementations, you can assume Strings are being compared. This is for use in the general driver.
- StringByLength: the highest priority value is the shortest string.
- StringByLengthReverse: the highest priority value is the longest string.
- StringByValue: the highest priority value is the string with the smallest value (according to how values would be ordered in a dictionary).
- StringByValueIgnoreCase: the highest priority value is the string with the smallest value (again, via dictionary ordering), but this time ignoring case.
- IntegerIncreasing: the highest priority value is the smallest integer.
public class StringByLength implements Comparator {
public int compare(Object o1, Object o2)
{
String s1 = (String)o1;
String s2 = (String)o2;
return s2.length() - s1.length(); //Note the order of s2 and s1!
}
public boolean equals(Object o1)
{return (o1 instanceof StringByLength);}
}
Note that compare("ab","xyz") returns a positive value
(3-2 = 1) indicating that the first argument has a higher
priority than the second (smaller length).
Another way to implement this is return -(s1.length()-s2.length());
meaning that the priority is the opposite of the standard ordering: if
the first is less than the second, it has higher priority.
Examine the Application.java file. When it constructs a SimplePriorityQueue object, it passes it an object constructed from some class that implements the Comparator interface (i.e., an object constructed from one of the classes above). Run my executable to better understand the meanings of these Comparator classes; enqueue and dequeue lots of different values.
The SimplePriorityQueue class should define two constructors. The first takes an object from a class implementing Comparator and an and initial size for the array (which must be positive, otherwise throw an exception); the second just takes such an object (and by default uses an array of size 1). Hint: I used just three instance variables: one for the array; one for the amount of that array actually used, and one for the Comparator object.
Finally, modify the SimpleQueue provided in the start folder that you download (it is an excellent starting point because queues and priority queues have the same method names -and some even have the same semantics). Update its Javadoc to be correct for the SimplePriorityQueue class.
To generate the Javadoc for this class, select Project | Generate Javadoc... and then make sure the box for the entire project in the Select types for which Javadoc will be generated is fully checked (if you click the disclosure box, make sure both the packages -default and the one with your id- are checked. Examine the other options, but don't change them. Note that you can genrate Javadoc for users (showing only public information) and Javadoc for yourself (showing members with other access modifiers: just go with public).
For Destination browse to the folder containing this project.
For Javadoc command configure Eclipse to refer to the
javadoc.exe executable file in the bin folder where
the jdk is stored.
Finally click Finish; my Generate Javadoc window looked
like this.
.
The console window will show a trace of your Javadoc being generated. To examine/read the Javadoc, look in your project folder under Doc and double click the index.htm file. Submit the Javadoc with your project (don't remove it before zipping). We will look at it and ensure that you have updated it from queue to priority queue.