Implement a priority queue capable of holding objects of an arbitrary type T. Implement the queue using ArrayList as an underlying data structure. A priority queue is a type of list where every item added to the queue also has an associated priority. Your class should support the following methods:

• No-argument constructor - allocates an empty array list of objects of type Pair
• add(T item, int priority) - adds a new item to the queue with the associated propriety.
• remove() - returns the item with the highest priority (largest integer priority number) and removes it from the queue. If the user attempts to remove from an empty queue, returns null.
• isEmpty() - returns true if the priority queue is empty, false if it is not.

In order to implement storage of items together with the priority keys make aprivate inner classcalled Pair. To learn how to set up an inner private class see the material here:InnerClassesSavitch.pdfDownload InnerClassesSavitch.pdf

The Pair class must have two fields: value of type T and a priority of type int. It also has to have the following methods:

• a constructor Pair(T value, int priority)
• int getPriority() - accessor for priority field
• T getValue() - accessor for value field

Requirement:

Do not use standard Java PriorityQueue or any other standard Java generic other than ArrayList as an underlying data structure.

Sample use of the InefficientPriorityQueue data structure InefficientPriorityQueue q = new InefficientPriorityQueue(); q.add("x", 10); q.add("y", 1); q.add("z", 3); System.out.println(q.remove()) // prints "x" System.out.println(q.remove()) // prints "z" System.out.println(q.remove()) // prints "y"

CODE PROVIDED:

import java.io.PrintStream;

/** * * @author AV */ public class TestsInefficientPriorityQueue { /** * All tests for Generic Methods class * @return total score for AggregationClass part of assignment */ public static void allTestsInefficientPriorityQueue(PrintStream out) { out.println(" ----Tests for InefficientPriorityQueue generic Class----"); testSet04InefficientPriorityQueue(out); testSet05InefficientPriorityQueue(out); } /** * Set of unit tests for InefficientPriorityQueue constructor, add(), and isEmpty() methods * @param outputStream stream to direct output into * @return number of points earned for this unit. 0 is returned if even one of the tests failed */ public static void testSet04InefficientPriorityQueue(PrintStream outputStream) { outputStream.println(" ----Test Set 4 ----"); InefficientPriorityQueue q1 = new InefficientPriorityQueue(); // Test #1

if(q1.isEmpty()) { outputStream.printf("%-80s%-10s ", "Test Set 04: Test one for isEmpty()", "PASSED"); } else outputStream.printf("%-80s%-10s ", "Test Set 04: Test one for isEmpty()", "FAILED");

// Test #2 Date d1 = new Date(1, 1, 2019); Date d2 = new Date(2, 3, 2020); Date d3 = new Date(3, 4, 2020);

q1.add(d1, 10); q1.add(d2, 1); q1.add(d3, 15); InefficientPriorityQueue q2 = new InefficientPriorityQueue(); String s1 = "Just for testing"; String s2 = "Two"; String s3 = "Three"; q2.add(s1, 2); q2.add(s2, 3); q2.add(s3, 5); if(!q1.isEmpty()) { outputStream.printf("%-80s%-10s ", "Test Set 04: Test two for isEmpty() and add()", "PASSED"); } else outputStream.printf("%-80s%-10s ", "Test Set 04: Test two for isEmpty() and add()", "FAILED");

} /** * Set of unit tests for remove()( will be indirectly testing add(), and isEmpty() methods) * @param outputStream stream to direct output into * @return number of points earned for this unit. 0 is returned if even one of the tests failed */ public static void testSet05InefficientPriorityQueue(PrintStream outputStream) { outputStream.println(" ----Test Set 5 ----"); InefficientPriorityQueue q2 = new InefficientPriorityQueue();

// Test #2 String s1 = "Just for testing"; String s2 = "Two"; String s3 = "Three"; String s4 = "Four"; String s5 = "Five"; String s6 = "Six"; q2.add(s1, 2); q2.add(s2, 5); q2.add(s3, 3); q2.add(s4, 1); // queue contains (s4, 1); (s1, 2); (s3, 3); (s2, 5) String r1 = (String)q2.remove(); //(s2, 5) removed String r2 = (String)q2.remove(); //(s3, 3) removed // queue contains (s4, 1); (s1, 2) q2.add(s5, 5); q2.add(s6, 0); // queue contains (s6, 0); (s4, 1); (s1, 2); (s5, 5) String r3 = (String)q2.remove(); //(s5, 5) removed String r4 = (String)q2.remove(); //(s1, 5) removed String r5 = (String)q2.remove(); //(s4, 5) removed String r6 = (String)q2.remove(); //(s6, 5) removed // queue is empty // Test #1 if(q2.isEmpty()) { outputStream.printf("%-80s%-10s ", "Test Set 05: Test for remove() and isEmpty()", "PASSED"); } else outputStream.printf("%-80s%-10s ", "Test Set 05: Test for remove() and isEmpty()", "FAILED"); // Test #2 if(r1.equals(s2) && r2.equals(s3) && r3.equals(s5) && r4.equals(s1) && r5.equals(s4) && r6.equals(s6)) { outputStream.printf("%-80s%-10s ", "Test Set 05: Test for remove() in correct order", "PASSED"); } else outputStream.printf("%-80s%-10s ", "Test Set 05: Test for remove() in correct order", "FAILED"); // Test #3 if(q2.remove()==null) { outputStream.printf("%-80s%-10s ", "Test Set 05: Test for remove() from empty queue", "PASSED"); }

} }