In this assignment, you are asked to implement one public class, PriorityDoublyLinkedList, and two private inner classes: DNode and PriorityDoublyLinkedListIterator. Together, they implement a subset of the Java List interface (java.util.List) and the IPriority interface defined for this assignment. A template code of the class and the interface is provided in hw3.zip.
Objectives: To provide hands-on experience on concepts studied in class: implementation of a singly linked list class, overriding the equals() method of the Object class, generic classes, generic interfaces, and Java List interface and Iterator interface. This assignment should help you understand more about the subject matters and be able to apply them to solve real problems in the future.
Important: Please start your assignment early. The Java List interface has many methods. Read through the entire assignment to understand the requirements first before starting to design and code your classes. Frequently check the official clarification for corrections. Any clarification posted prior to 24 hours before the deadline are considered to be part of this specification. In addition, you are to read the Java 7 APIs at http://docs.oracle.com/javase/7/docs/api/ for the specification of the List and the ListIterator generic interfaces.
The PriorityDoublyLinkedList class uses a data structure called a circular doubly-linked list with priority. A list object of this class has a dummy head node that keeps object references to node objects of the first data item and the last data item in the list. A node object (of class DNode) is used for keeping an object reference to a data item in the list and object references of its neighboring nodes in the list. By traversing these object references from the head node, new data items can easily be added into or removed from the list. Null and duplicate data items are allowed in the list. Each data item is associated with a priority, which is an integer, ranging from 0 (inclusive) to the number of priority levels (exclusive) assigned to the list object when the list object is first instantiated. The priority of the dummy head node keeps the number of priority levels given to the constructor of the PriorityDoublyLinkedList class. The default priority of a node is also given as a required argument to the constructor of the PriorityDoublyLinkedList class. This default priority is used when a data item is added to the list without a specific priority. Refer to the Java template source code for the PriorityDoublyLinkedList class. The following figures show a progression of a PriorityDoublyLinkedList object when it is first instantiated and when new data items are added to the list. Be sure to read an explanation given in the caption of each figure as well.
Figure 1 shows a conceptual diagram of a PriorityDoublyLinkedList object when created with 4 priority levels and a default priority of 1. The object reference of the head node is stored in the head member variable/field of the class. The id field represents a unique identifier for each node. The range of values of the node id is from 0 to the maximum integer value. Since the head node is not associated with any data item, its data field is null. The head node is not counted as an element in the list. The arrows in the figure represent object references. The next field of the head node must reference either the first node in the list object or the head node itself when the list is empty. The prev field of the head node must reference either the last node in the list or the head node itself when the list is empty. In this figure, the list is initially empty. Therefore, both next and prev fields reference the head node. See image.
Figure 1. Conceptual diagram of a head node after an object of the PriorityDoublyLinkedList class was created by calling new PriorityDoublyLinkedList(4, 1). The number of priority levels of the list is kept in the prio field. The default priority of the list of 1 and is kept in a member variable of the class not shown in this figure. The default priority is not part of the head node.
Figure 2. Conceptual diagram of the PriorityDoublyLinkedList object in Figure 1 after a new data item with the object reference objref1 was added to the list using the add(E item) method. The add method adds the data item at the end of the list. A new node of the inner class DNode with the id of 1 was created. This node has a default priority of 1 since the add method does not have an argument to specify a specific priority for this data item. The next field of the head node now references node 1 since it is the first node added. The next field of the last node in the list (node 1 in this diagram) references back to the head node. The prev field of the head node also references the last node in the list (node 1 in this diagram). The prev field of node 1 references the head node. We use objref to represent an object reference for ease of presentation.
Figure 2 shows the conceptual diagram of the list object in Figure 1 after a new data item was added to the list using the add(E item) method. Your implementation must ensure that adding a new node at the end of the list is O(1). Your code should use the prev field of the head node to get the object reference of the last node in the list object and add the new node after the last node.
The correct end result for the add method is that the new node is added at the end of the list; the next field of the head node still references the first node in the list; the prev field of the head node references the last node in the list; and the links between the previous last node and the new last node indicate the correct node order in the list. The list is still circular.
Figures 3 and 4 show the same procedure applies for maintaining the node order in the list when using addWithPriority(int priority, E item) of the IPriority interface to add a new data item (objref2) with priority 0 to the end of the list followed by a new data item (objref3) with priority 0. For addWithPriority, the data item is associated with the specified priority instead of the default priority. See image.
Figure 3. Conceptual diagram of the PriorityDoublyLinkedList object in Figure 2 after a new data item with the object reference objref2 was added to the list using the add(int priority, E item) method with priority of 0. See image.
Figure 4. Conceptual diagram of the PriorityDoublyLinkedList object in Figure 3 after a new data item with the object reference objref3 was added to the list using the add(int priority, E item) method with priority of 0.
Given the state of the list object in Figure 4, calling the size() method of the List interface should return 3 as there are three data items in the list (regardless of priority). The head node is not counted. The sizeGivenPriority(0) method returns 2 as there are two data items with priority zero. They are kept in nodes with id 2 and 3. The sizeGivenPriority(1) method returns 1. The sizeGivenPriority(3) method returns 0 as there are no data items with this priority. The sizeGivenPriority(4) method throws IllegalArgumentException because the maximum priority is 3 (the number of priority levels – 1). The getNumPriorityLevels() method always returns 4 for this list object regardless of how many items are added or removed from the list since the number of priority levels is same for the entire life time of the list object. See image.
Figure 5 shows the result after a new null item with priority 1 was added to the front of the list with addFirstWithPriority(1, null).
The iteratorWithPriority(priority) method returns a PriorityDoublyLinkedListIterator object that iterates over only the elements with that priority. Given the state of the list object in Figure 5, calling the next() methods repeatedly with an iterator object returned from calling iteratorWithPriority(0) should return object references of data items kept in node id 2 and node id 3, respectively. Calling the next() methods with an iterator object returned from iteratorWithPriority(1) should return object references of data items kept in node id 4 and node id 1, respectively.
The iterator() method returns a PriorityDoublyLinkedListIterator object that iterates over all elements in the list regardless of their priority. The head node is used internally only and is not counted as an element in the list. Given the state of the list object in Figure 5, calling the next() method repeatedly with a PriorityDoublyLinkedListIterator object returned from calling iterator()should return the object references kept in nodes id 4, 1, 2, and 3, respectively. The listIterator() method behaves similarly.
Figure 6 shows the diagram of the list object when a node was removed. To keep the implementation simple, a new node does not reuse the node id of the node that has been removed from the list. See image.
Figure 6 shows the result after remove(objref2) was called on the list object shown in Figure 5. The node keeping objref2 was removed from the list object and the object references between neighboring nodes of the removed node were adjusted accordingly.
The PriorityDoublyLinkedList is to be implemented as a generic public class that implements Java List interface and the IPriority interface. Refer to the documentation in PriorityDoublyLinkedList.java on what methods require full implementation and what methods throw UnsupportedOperationException.
A few methods are required to be O(1). If it is not specified whether the method should be O(1), you can choose your own implementation, but it should not be too inefficient (e.g., O(n2) when it can be O(n)).
You are not required to submit JUnit test code for this assignment. You may share any test code for testing the PriorityDoublyLinkedList class on Blackboard Learn. The supported methods for the List interface using your implementation should behave exactly the same as those using java.util.LinkedList except when adding with priority or iterating with a given priority.
All public methods must have Javadoc comments following the standard Javadoc format, including descriptions of each parameter and any exceptions that might be thrown. You may introduce private methods, but these private methods must have either Javadoc or normal style comments explaining what the methods do. Add @author tag followed by your full name in each class source file.