EmptyCollectionException.java /* * Represents the situation in which a collection is empty. */ public class EmptyCollectionException extends RuntimeException { /* General class level objects */ /* * Sets up this exception with an appropriate message. * @param collection the name of the collection */ public EmptyCollectionException(String collection) { super("The " + collection + " is empty."); } }

PriorityNode.java

/* * Represents a node in a linked list. */ public class PriorityNode { /* General class level objects */

private PriorityNode _next; private T _element; private int _priority; private final int _MAX_PRIORITY = 100;

/* * Creates an empty node with a given priority. */ public PriorityNode(T elem, int priority) { // TODO To be completed as a Programming Project }

/* * Creates a node storing the specified element with a default priority. * * @param elem element to be stored */ public PriorityNode(T elem) { // TODO To be completed as a Programming Project }

/* * Returns the node that follows this one. * * @return reference to next node */ public PriorityNode getNext() { // TODO To be completed as a Programming Project }

/* * Sets the node that follows this one. * * @param node node to follow this one */ public void setNext(PriorityNode node) { // TODO To be completed as a Programming Project }

/* * Returns the element stored in this node. * * @return element stored at the node */ public T getElement() { // TODO To be completed as a Programming Project }

/* * Returns the priority of this node. * * @return element priority the node */ public int getPriority() { // TODO To be completed as a Programming Project }

/* * Sets the element stored in this node. * * @param elem element to be stored at this node */ public void setElement(T elem) { // TODO To be completed as a Programming Project } /* * optional toString() override. */ //public String toString() //{ // // TODO To be completed as a Programming Project //} }

PriorityQueue.java

/* * LinkedQueue represents a linked implementation of a queue. */ public class PriorityQueue implements PriorityQueueADT { /* General class level objects */

private int _count; private PriorityNode _head, _tail; /* * Constructor - Creates an empty queue. */ public PriorityQueue() { _count = 0; _head = _tail = null; } /* * Adds one element to the rear of this queue. * Higher priorities are inserted closer to the front of the queue * Items with the same priority are processed in normal queue order * * @param element the element to be added to the rear of the queue * @param priority relative priority of the queue item */ public void enqueue(T element, int priority) { // TODO To be completed as a Programming Project // add in-order insertion of the PriorityNode based on getPriority() value // the higher the priority is the closer to head it gets // equivalent priority is normal queue logic } /* * OVERLOAD: Adds the specified element to the tail of this queue with default * priority 0. * * @param element the element to be added to the tail of the queue */ public void enqueue(T element) { // TODO To be completed as a Programming Project } /* * Removes the element at the head of this queue and returns a reference to it. * * @return the element at the head of this queue * @throws EmptyCollectionException if the queue is empty */ public T dequeue() throws EmptyCollectionException { // TODO To be completed as a Programming Project } /* * Returns a reference to the element at the head of this queue. The element is * not removed from the queue. * * @return a reference to the first element in this queue * @throws EmptyCollectionsException if the queue is empty */ public T first() throws EmptyCollectionException { // TODO To be completed as a Programming Project } /* * Returns true if this queue is empty and false otherwise. * * @return true if this queue is empty */ public boolean isEmpty() { // TODO To be completed as a Programming Project } /* * Returns the number of elements currently in this queue. * * @return the number of elements in the queue */ public int size() { // TODO To be completed as a Programming Project } /* * Returns a string representation of this queue. Shows the list of PriorityNode * elements by position and queue priority * * @return the string representation of the queue */ public String toString() { // TODO To be completed as a Programming Project } }

PriorityQueueADT.java /* * QueueADT defines the interface to a queue collection. */ public interface PriorityQueueADT { /* General class level objects */

/* * Adds one element to the rear of this queue. * Higher priorities are inserted closer to the front of the queue * Items with the same priority are processed in normal queue order * * @param element the element to be added to the rear of the queue * @param priority relative priority of the queue item */ public void enqueue(T element, int priority);

/* * Removes and returns the element at the front of this queue. * * @return the element at the front of the queue */ public T dequeue();

/* * Returns without removing the element at the front of this queue. * * @return the first element in the queue */ public T first();

/* * Returns true if this queue contains no elements. * * @return true if this queue is empty */ public boolean isEmpty();

/* * Returns the number of elements in this queue. * * @return the integer representation of the size of the queue */ public int size();

/* * Returns a string representation of this queue. * * @return the string representation of the queue */ public String toString(); }

PriorityQueueTester.java

/* * Module for testing the operation of the priority queue class */ public class PriorityQueueTester { /* General class level objects */

public static void main(String[] args) { // basic tests of the Priority Queue Class // Add your own tests for further analysis // be sure to test Exception conditions

PriorityQueue pQ = new PriorityQueue();

pQ.enqueue("one"); pQ.enqueue("two", 2); pQ.enqueue("three", 3); pQ.enqueue("four", 4); pQ.enqueue("five", 5); pQ.enqueue("six", 6); pQ.enqueue("seven", 7); pQ.enqueue("eight"); pQ.enqueue("nine", 1); pQ.enqueue("ten", 1);

System.out.println("Front of queue: " + pQ.first()); System.out.println(pQ); // test removing all queue elements while (!pQ.isEmpty()) { System.out.print(pQ.dequeue() + " -> "); } System.out.println("(empty) ");

pQ.enqueue("one"); pQ.enqueue("two"); pQ.enqueue("three"); pQ.enqueue("four"); pQ.enqueue("five"); pQ.enqueue("six"); pQ.enqueue("seven"); pQ.enqueue("eight"); pQ.enqueue("nine"); pQ.enqueue("ten", 1000); pQ.enqueue("eleven", -200); System.out.println("Front of queue: " + pQ.first()); System.out.println(pQ); while (!pQ.isEmpty()) { System.out.print(pQ.dequeue() + " -> "); } System.out.println("(empty) "); // *** Add your own tests for further analysis ***

}

a situation where an enqueued item must be dequeued before items of lower priority. Requirements To ensure consistency among solutions each implementation must implement the following requirements. - A priority queue must always operate with common queue logic. - Linked list nodes must support a value for the relative priority with a positive value between 0 and 100 (inclusive). All other values must be defaulted to a valid value. - Priority values less than zero must be defaulted to zero and values greater than 100 default to 100 . - Items added to the queue must be ordered by priority with the highest values nearest the "dequeue" point. - Items with the same priority are ordered based on order received supporting the common queue, FIFO logic. - The tostring() method of the PriorityQueue object must generate output identical to provided test run output values. Classes There are 4 classes and 1 interface in the project, all provided in partial or complete form. The method structure for all classes has been provided. Your responsibility is to complete the implementation for all incomplete methods. - EmptyCollectionException - PriorityQueue T - PriorityQueueADT T - PriorityqueueTester Testing A basic testing module has been provided to demonstrate how the PriorityQueve can be exercised for accuracy. It is your responsibility to add further tests to look for issues around common "edge" conditions from enquing and dequing. Edge conditions for a linked list commonly include adding to the front or back of the list and inserting between nodes. Make sure that invalid priority values are properly defaulted by the PriorityNode object. Exceptions must be thrown when queue operations expected to return data happen with an empty queue. Test for exceptional conditions. Example Output Below is the output from the test module provided. Pay special attention to the formatting of the tostring () return value with each comma delimited item showing the node element value with its associated priority value. Front of queue: seven [seven:7, six:6, five:5, four:4, three: 3 , two:2, nine:1, ten: 1 , one: , eight:0] seven six five four three two nine ten one eight > (empty) Front of queue: ten ten one two three four five six seven eight nine > eleven (empty)