Program 8

Collection Classes via Linked Lists

Advanced Programming/Practicum
15-200

Introduction This programming assignment is designed to improve your knowledge of collection classes (from the inside), while exercising your skills in writing class implementations using linked lists. The first program is to write a class named CircularLinkedQueue that implements the OrderedCollection interface using queue semantics and a special kind of linked list. The second program is to write a class named LinkedPriorityQueue that implements the OrderedCollection interface (which also serves as the interface for priority queues), using priority queue semantics and a linear linked list. The third program is to write a class named LinkedMap that implements the Map interface. Note that all these classes must implement correctly working iterators too (only the map iterator must support a remove operation; the other can throw the UnsuportedOperationException).

For the first two classes, you will modify the standard ordered collection driver to test them. You should download the Ordered Collections Demonstration and use this as the driver for the first two classes that you are writing here, along with two copies of the LinkedQueue class. Edit each as a starting point for creating the CircularLinkedQueue and the LinkedPriorityQueue classes (or use the ArrayPriorityQueue to start the LinkedPriorityQueue: it has priority queueness, but not linked listness). You should understand all aspects of the LinkedQueue class (including its nested/inner classes for iterators) before writing your solutions. Update the driver (it uses a tiny bit of reflection) to allow it to test these two new classes as well.

The LinkedMap has its own driver application. You can download and unzip the Start Project Folder, which contains a starting point for the LinkedMap class that you are to write, and a driver for it. Do this part of the assignment last.

After you are finished with all three parts, place these project folders into a folder whose name combines your names (if programming in pairs) and the program number (e.g., pattis-stehlik-8). Then zip this folder and dropoff that single zip file. If you are programming in a pair you should submit only one project: either partner can submit it.

As always, you can check the behavior of your programs against mine by downloading and running my Executable, to help you understand the specification of the problem and observe the programmer/user interaction that you are to implement Of course, the semantics of these classes are the same those already written for these interfaces, so you classes should perform equivalently (except for their efficiency, and the order that iterators produce values).

Queue via Circular Linked List The CircularLinkedQueue class must implement the OrderedCollection interface and the standard queue semantics: FIFO. Write this class to declare and use only one instance variable, rear, which refers to the LAST node in a circular linked list: this node, in its next field stores a reference to the first node, instead of null. You CANNOT store a front instance variable in the implementation of this class! Notice the methods written in the AbstractOrderedCollection which manipulate the protected fields modCount and objectCount. Ensure that you do the correct thing if you overrride any of these methods.

Although at first it is counter-intuitive, to be able to refer to both the front and rear of a queue quickly, the the one reference you define should be to the list node at the rear of the linked list: its next field refers to the front, so both are reachable very quickly -in a constant amount of time- through this single instance variable. A multi-node queue is pictured below (the top picture shows the queue in a normal orientation, but the bottom picture shows a queue that is easier to think about).

  Note that a circular linked list with one node has a next instance variables that refers to itself! Thus, the front of a non-empty queue is always referred to by rear.next (even if the queue contains just one node). Before coding, first draw pictures of how add and remove change such a structure: when queue is empty, contains one node, and contains a few nodes. Study these pictures and use the knowledge you gain when coding these methods. Write the simpliest code possible. Every operation performed on a circular linked list should produce a circular linked list.

Again, you can have only one instance variable refering to the circular linked list implementing the queue (e.g., rear, not front). All operations on this data structure should run in O(1): no operations in this implementation should require looping!

Priority Queue via Linked List The LinkedPriorityQueue class must also implement the OrderedCollection interface and the standard priority queue semantics. You have already written a priority queue (implemented using an array), so you should be familiar with the semantics of its methods (and the use of the Comparator interface, used in its constructor). In this assignment, you must represent the priority queue by a linear linked list, with the list ordered from highest to lowest priority; this makes it easy to remove and peek at the highest priority values.

That is, whenever a value is added, it is linked into the list in the correct position, to preserve the priority ordering. Whenever a value is removed, it is removed quickly from the front of this linked list.

Notice the methods written in the AbstractOrderedCollection which manipulate the protected fields modCount and objectCount. Ensure that you do the correct thing if you overrride any of these methods. Here you should have only one instance variable refering to the linked list implementing the priority queue: front; there is no reason to quickly access the last value in this kind of queue.

Map via Linked List The LinkedMap class must implement the Map interface; it extends the AbstractMap. Recall that you can examine the source code for this interface and abstract class by looking in the Java directory at the file src.jar or src.zip (both can be examined as zip files, as can other concrete classes implementing maps: HashMap and TreeMap). In the LinkedMap class you must you must implement the following methods: clear, containsKey, containsValue, get, isEmpty, put, remove, and size. The AbstractMap class implements all the other methods in terms of these.

For this assignment you MUST use a HEADER list to implement this class: it guarantees that every "real" (data containing) node in the map is preceded by some other node (even if it is only the header). Such an assumption can simplify your code dramatically. You should define one instance variable that refers to the header of this list, and two others representing the cached object count and modification count (used for throwing ConcurrentModificationException in the iterator).

Note that this class already defines a simple nested Entry class that implements the Map.Entry nested interface (specified in the Map interface). This class defined key and value fields, and also defines a next field -used for linking these enteries in a list.

In addition, you must define the LinkedMap iterator, including a working remove method. See the Simple Queue with Iterator Demonstration for one example of such an iterator, which is discussed in the Iterators section of the the Collections and Iterators lecture.

You do not have to to define the entrySet, keySet, or values methods: these methods are implemented to return objects constructed from inner classes that are already defined in the ListMap class, but are not functional until you correctly write the LinkedMapIterator class. All three of these collections are backed by the LinkedMap class, which delegate some methods and uses extended iterators. You can study this code and ask questions about it, but you do not have to understand it to get the code you must write to work correctly.

Finally, you will use also use JUnit to test/debug your map class in this assignment. You should download the JUnit Map folder and put both files it contains (junit-4.1.jar and MapTest.java) into the project in which you are writing the . You can run either the driver or the MapTest class to test you class. When a JUnit test fails, you will have to look up the line in the MapTest.java file to understand the failure. You might even edit MapTest.java, putting print statements near the failed test to help you understand the state of the map and why it failed.

Eventually, all the tests that it performs should run correctly (if you have any problems, please contact me or the staff). You can use this JUnit test driver in one of two ways.

  • Use it towards the end, after you have tested various methods with the manual driver.
  • Use it right from the beginning, as you write/debug all your map code.
In either case, you can add the JUnit materials to your project (even if you don't use them). Remember, if JUnit fails to finish testing your code, it is probably because you have written an infinite loop that doesn't return to the tester.
Extra Credit There is one point of extra credit on this assignment.
  • I'll give one point of extra credit to students who write a GOOD JUnit tester for their priority queue class. See the JUnit code for testing the map. I'll provide another reference to JUnit testing here soon (there are whole books written on the subject). FYI JUnit testing works via Java reflection.