The first two of these collection classes share the same subinterface, OrderedCollection the third uses the Collection subinterface. Each has its own special sub-subinterface, Queue, PriorityQueue, and Set, but only PriorityQueue includes any new methods. Each implementation extends one abstract classes (which itself extends AbstractOrderedCollection or AbstractCollection). Primarily, the implementation specifies an actual data structure (linked list) and the methods that implement the collection's operations (methods that must appear in the concrete class or should appear there to improve the speed over some inherited methods).

Note that the Iterable interface, which the OrderedCollection and Collection interfaces extend, specifies just that a method named iterator is defined: to return an Iterator.

IMPORTANT: I have written implementations for these same collections using arrays; although this assignment uses linked lists, there are still many strong similarities in all these implementations. So, I encourage you to examine these implementations closely while you are writing your linked list implementations. These array implementations are all included in the collections.jar file that you build a path to in this assignment.

You must write all your implementations using linked lists: a linear-linked list for Queue, a header linked list for PriorityQueue, and a trailer linked list for Set. The constuctors in the PriorityQueue class must be passed an object constructed from some class that implements the Comparator interface, for specifying how to prioritize all the values added to it.

The toString method in each class should include the name of the class, followed by, in brackets, the size and the order of values in the list. For example, if we add a, then add b, then add c into a queue, its toString should show as LinkedQueue[3:a->b->c->null]. In a header list, we skip showing the value in the first/header node, as that node is not really in the collection represented by the list; likewise, in a trailer list, we skip showing the value in the last/trailer node, for the same reason. The toString method is not tested in the JUnit test, but is useful for debugging when running the DriverForOrderedCollection.

After you have written your classes, you will run each against my JUnit tests to verify (a bit too strong of a word here) that it is correct. You will find it useful to begin testing your classes with the DriverForOrderedCollection or DriverForCollection, which you can run from collection.jar once you build a path to this library in the project. With these drivers, you can individually test any methods in your classes interactively, and see their results (returned values and state changes, frequently using the toString menu item).

The following programming assignments this quarter will require you to perform a similar task: implement some collection class via some advanced data structure that we have studied. Most will have a JUnit test (and a driver) and speed test similar to this one, so this assignment will also allow you to learn and get used to such a method of testing your classes.

Download and unzip the following Eclipse project Start and use it to start working on this program. For each part of this assignmnment you will update and submit a single .java file in the project (see the Checkmate submission for this assignment for more details).

You should work on this assignment in pairs, with someone in your lab section. Try to find someone who lives near you, with a similar work schedule: e.g., talk about whether you like to work morning, nights, weekends.

Only one student should submit the assignment, but both student's names should appear in the comments at the top of each submitted program. Please turn in each program as you finish it, so that I can accurately assess the progress of the class as a whole during this assignment.

Print this document and carefully read it, marking any parts that contain important detailed information that you find (for review while you work on this assignment and before you turn in the files).

Although we can easily compute the number of values in linked list by traversing it, instead we will declare and update an extra instance variable named objectCount to cache the size (incrementing and decrementing it, as values are successfully added/removed from the queue) so we don't have to traverse the list to compute this value.

The class LinkedQueue declares the required instance variables and declares stubs for all the needed methods: just fill in these stubs; note that this class compiles correctly but fails most JUnit tests because its method bodies are empty.

Finally, fill in the complexity class information at the top of the class file as comments, based on your implementation. See the common sections below pertaining to iterators and testing.

So, we cannot ask, "What is the priority of a value." But, we can ask "Which of two values has the higher priority", using such a Comparator. For example, we cannot ask for the priority of a String value, but we can ask which of two String values has the higher priority.

We can implement priority queues naively (although not very efficiently) with one instance variable, which refers to a linked list whose first value is the highest priority value, and whose remaining values occur in decreasing priority; when adding a value to a priority queue, we insert it at the right spot, keeping the list ordered from highest to lowest priority; when removing the highest priority value from a priority queue, we remove it from the front. Instead of a plain linked-list, you must implement the priority queue queue using a "Header node" first in the linked list. Doing so should simplify writing the most complicated method: adding a value to the priority queue: write this method very simply.

Although we can easily compute the number of values in linked list by traversing it, instead we will declare and update an extra instance variable named objectCount to cache the size (incrementing and decrementing it as values are successfully added/removed from the priority queue) so we don't have to traverse the list to compute this value.

The class HeaderLinkedPriorityQueue declares the required instance variables declares stubs for all the needed methods: just fill in these stubs; note that this class compiles correctly but fails most JUnit tests because its method bodies are empty.

Finally, fill in the complexity class information at the top of the class file as comments, based on your implementation. See the common sections below pertaining to iterators and testing.

Although we can easily compute the number of values in linked list by traversing it, instead we will declare and update an extra instance variable named objectCount to cache the size (incrementing and decrementing it as values are successfully added/removed from the priority queue) so we don't have to traverse the list to compute this value.

The class TrailerLinkedSet declares the required instance variables declares stubs for all the needed methods: just fill in these stubs; note that this class compiles correctly but fails most JUnit tests because its method bodies are empty..

Finally, fill in the complexity class information at the top of the class file as comments, based on your implementation. See the common sections below pertaining to iterators and testing.

Note that iterators for OrderedCollection classes return values in the order that they would be removed from the collection: FIFO for queue and priority ordering for a priority queue; for sets, which aren't ordered, iterators can return the set values in any order. Given how these linked lists represent collections (queue: front to rear; priority queue: highest to lowest priority; set any order), the order of iterating through these collections is the same as the order of traversing their linked list implementation from beginning to end, which makes the hasNext and next methods straightforward to implement.

To pass the special JUnit tests that focus on iterators, you must write more code in the next and remove methods, to complete them. To this end, I have supplied the declaration and intialization of a few extra instance variables, but these variables are not all used in the code I supplied: you have to write more code that uses them correctly.

• You can observe how the expectedModCount and removedAlready instance variables are used in the array implementations of these classes (they are used equivalently here).

• You can use whatever other references I supply (previous, seen, and next) to remove values carefully from the list in the iterator. Generally, the instance variables, if supplied, should refer to the node whose value the next method will return (next), to the node whose value the next method just returned (seen), and to the node whose that come before the seen one in the linked list (previous; not needed in the TrailerLinkedSet, because of its special removal property).

  Generally after the next method is called, these three values refer to consecutive values in the linked list being iterated over: it should be the case that previous.next == seen and seen.next == next.

  This relationship doesn't hold (a) when we just start iterating (there has been no seen value, and there is no value previous to seen) and (b) after a call to remove which removes the seen value; in this case previous.next == next if we did not just remove the first value in the linked list (which is a special case).

Also, next and remove must throw an exception if the collection has been modified (via any command / mutator methods) since the iterator was constructed; note, it is OK for an iterator to mutate the data structure via remove and continue iterating on it (although other iterators will fail).

So, you should carefully manipulate the next, seen, and previous (if present) instance variables to meet all the requirements for the hasNext, next, and remove methods. Note that you should hand-simulate/debug your code for the following cases; some may require special code to recognize and process these cases.

1. removing values at the front of the list several times in a row
2. calling next when the previously seen value was NOT removed
3. calling next when the previously seen value was removed,

Again, you can see how these constraints are accomplished in the array implementations of these classes, which are SIMPLER than how they are accomplished with linked lists (because we can more easily access array indices like i-1). For linked list implementations, implementing remove is a bit more complicated to implement, but more EFFICIENT, because values in arrays must be shifted (causing the complexity class of remove to be O(N) in arrays).

The easiest way to start debugging is by using the DriverForOrderedCollection and DriverForCollection programs. When each of these programs start, it prompts you to enter the name of the collection class that you want to test/debug (if you set up the libraries correctly). Then, it allows you to perform any method call supported by the collection classes, and check the results, typically by calling the toString method, to show the state of the collection class (or view the debugger). Of course, you must get the toString method to work before calling it to debug other methods. Although, if you don't override the toString method in your implementation, your class will inherit a simpler toString method from one of the abstract collections, using an iterator (only its hasNext and next methods) to produce a String that includes all the values in the collection, but in the wrong format.

After you debug your code with the driver, try running the appropciate JUnit test. Again, this form of testing is useful only as you approach a finished solution. We will use the JUnit test, and visual inspection, to grade this assignment. Important Note: You can put System.out.print statements in the JUnit code (but don't accidentally remove any of the assertions, otherwise you won't be fully checking your code the way we will) while you are debugging your classes.

When you run the JUnit tests, choose the default values for the first, third, and fourth questions; for the second question enter the index of the collection class that you want to test. Besides an indication of which tests pass and fail, the console window will show a speed for the speed test (which will vary depending on how fast a machine you run your code on): don't worry about it.

You can also examine the execution of these classes by using the debugger and/or by inserting System.out.print statements in your code or the JUnit test code.