Coding Project

This is the project portion. It covers Linked data structures, linked lists, binary search trees, Java programming. There are $3$ parts. Submit completed work in a zip file.

Basic Requirements

In this assignment you will provide two implementations of the DoubleEndedPriorityQueue interface specified as follows:

package cis$18$c;$$

public interface DoubleEndedPriorityQueue

$\{$

$$ void makeEmpty$()$;$$

$$ void add$($ AnyType x $)$;$$

$$ AnyType deleteMin$()$;$$

$$ AnyType deleteMax$()$;$$

$$ AnyType findMin$()$;$$

$$ AnyType findMax$()$;$$

$$ boolean isEmpty$()$;$$

$\}$

Note that duplicates may be inserted. If more than one item is tied as minimum$/$maximum$,$ then the deletion operation removes exactly one occurrence, leaving others in place. If the find or delete operations are invoked on an empty DoubleEndedPriorityQueue, then you should throw an unchecked runtime exception of type cis$18$c$.$ UnderflowException. $($Note the name of the class: the test program will fail if you return null or throw an UnderflowException that is not part of package cis$18$c$).$ Recall also that any implementation class would be expected to provide a toString method. Your toString method must list all the elements in the collection, in sorted order, in LINEAR TIME. The test program will be provided here FinalTestCode Download FinalTestCode$$It is important that you write sufficient test cases on your own to convince yourself that your logic works.

Linked List Implementation

In the linked list implementation, you should use a doubly$-$linked list, maintaining a reference to both the first and last nodes. Thus, the private representation looks like:

$$ private Comparator cmp;$$

$$ private Node first $=$ null;

$$ private Node last $=$ null;$$

In this implementation, when the collection is empty, both first and last are null. No header or tail nodes should be used. Your implementation class must be cis$18$c$.$ListDoubleEndedPriorityQueue.

$$

Binary Search Tree Implementation

In the binary search tree implementation, which is completely unrelated to the linked list implementation above, you will use an unbalanced binary search tree. Since duplicates are allowed, each node will have to store a singly$-$linked list of all the entries that are considered identical. Two values are identical if the comparator returns $0,$ even if the objects are unequal according to the equals method. A sketch of the private representation looks something like this:

$$ private Comparator cmp;$$

$$ private Node root $=$ null;$$

$$ private void toString$($ Node t$,$ StringBuffer sb $)$

$\{...$ the recursive routine to be called by toString $...\}$

$$ private static class Node

$\{$

$$ private Node left;

$$ private Node right;

$$ private ListNode items;

$$ private static class ListNode

$\{$

$$ private AnyType data;

$$ private ListNode next;

$$ public ListNode$($ AnyType d$,$ ListNode n $)$

$\{$ data $=$ d; next $=$ n; $\}$

$\}$

$$ public Node$($ AnyType data $)$

$\{$

$$ left $=$ right $=$ null;

$$ items $=$ new ListNode$($ data, null $)$;

$\}$

$\}$

In accessing objects of type ListNode from the TreeDoubleEndedPriorityQueue class, it may be necessary to use Node.ListNode as the qualified class name, depending on the context. Of course, ListNode cannot be viewed from outside TreeDoubleEndedPriorityQueue.

Observe that when you insert or remove into the double$-$ended priority queue, $($tree$)$ nodes are created only when you add an element that does not compare to $0$ with any other element in the tree. Tree nodes are removed only when the item to be removed was the only item in its node.

You will definitely need to use recursion to implement toString, and you must use string buffers with appends to avoid quadratic behavior. The other routines do not necessarily require recursion but the use of recursion is at your discretion and may simplify some logic.