CSC1020 Homework 7

Overview

The Queue interface in Java defines a number of methods to access, add, and remove items from a queue structure, maintaining FIFO by adding at the end of the queue and removing from the beginning of the queue. We are going to implement the Queue interface, but rather than implement a traditional queue we are going to, by changing the way elements are added to the queue, create a PriorityQueue.

PriorityQueue

A PriorityQueue is a structure that adds elements to a Queue, but stores these elements in some order, usually based on a data value contained in the element. Polling the PriorityQueue returns the first element in the queue, as usual, but it is not necessarily FIFO. An example would be if we had a PriorityQueue that stored Integer objects, the queue would be sorted low to high, so the following code:

PriorityQueue<Integer> nums = new PriorityQueue<>();
nums.add(5);
nums.add(3);
System.out.println(nums.poll());

would print 3.

When implementing a PriorityQueue, there are two things that need to change from a regular Queue:

1. <E> must be Comparable

There is a requirement that any Object type assigned to an element in the PriorityQueue must be able to be compared with other elements, otherwise there will be no way to keep the queue ordered. To ensure that when defining the PriorityQueue in the header you need to specify that any generic type E must implement the Comparable interface using the following structure:

<E extends Comparable<? super E>>

This states that any type declared in the class must either implement the Comparable interface itself or inherit from some superclass that does.

The Comparable Interface

The Comparable interface has a single abstract method, compareTo(T o), that compares the given object to a second object that has been passed in as a parameter and returns:

negative integer    if the given object is "less than" the second object
0                   if the given object and the second object are equal
positive integer    if the given object is "greater than" the second object

For this assignment, two elements are considered equal for ordering purposes when compareTo() returns 0.

"Less than" and "greater than" can be numeric, alphabetical, or any ordering that is defined within the compareTo() method. Strings, for example, compare characters lexicographically based on their character values.

2. Add/Offer

The add() and offer() methods will compare the element being added to the existing elements in the queue, using the Comparable interface's compareTo() method, and insert the element in the appropriate location relative to the existing elements.

The queue should be maintained from the least element to the greatest element according to compareTo(). Therefore, peek(), element(), poll(), and remove() will operate on the least element currently in the queue.

If two elements compare as equal, the new element is inserted after the existing element. If there are multiple existing elements that compare as equal, the new element will always be added after all of the existing elements with that same priority.

Both add() and offer() must:

• return true when a non-null element is successfully added;
• throw a NullPointerException if the element being added is null;
• preserve the required priority ordering.

Because our backing data structure does not have a fixed capacity, add() and offer() have the same behavior in this assignment. Both methods must be overridden in PriorityQueue, but one method may delegate to the other rather than duplicating the insertion logic.

Requirements

• Complete the partial implementation of the SJQueue with the following restrictions:

  • Use a LinkedList as the backing data structure.
  • Use the provided protected final LinkedList<E> data field as the backing structure.
  • You may ignore any methods that throw an UnsupportedOperationException.
  • Carefully follow the Javadocs provided.
    • Verify that the proper exceptions are being caught, thrown, and handled.
    • Do not catch and re-throw an exception generated by your backing data structure unless you need to change the exception type.

• Write a new PriorityQueue class that inherits from SJQueue.

  • The PriorityQueue should only accept objects that can be compared using the Comparable interface.
  • You should only override the add() and offer() methods. The rest of the inherited methods should remain the same.
  • These methods will be functionally the same, as our backing data structure does not have a fixed capacity, but both are expected to operate identically, so they both must be overridden.
  • You may create private helper methods if they help avoid duplicated code.

• Write a JUnit test suite that tests the add() and offer() methods of your PriorityQueue with the following boundary conditions:

  • adding a null element to the queue — this must throw a NullPointerException;
  • adding to an empty queue;
  • adding to a queue with one other different element;
  • adding to a queue with multiple different elements;
  • adding an element that belongs at the beginning of the queue;
  • adding an element that belongs in the middle of the queue;
  • adding an element that belongs at the end of the queue;
  • adding to a queue with multiple elements where exactly one existing element compares as equal to the element being added;
  • adding to a queue with multiple elements where several existing elements compare as equal to the element being added.

• Your tests should verify both:

  • the order of the elements after the operation; and
  • the return value from add() or offer().

• Use an existing type that implements Comparable, such as a String, Integer, or Double.

• You may use the SJQueue's toArray() method to assist with testing. Be aware that toArray() returns an Object array, so you may need to typecast your results.

• Remember that compareTo() may return any negative value or any positive value. Your implementation must not assume that comparisons return only -1, 0, or 1.