Task: Implementating the following Java interface and classes: Interface: PQueue Abstract class: AbstractPQueue Concrete classes: UnsortedPQueue and SortedPQueue

Requirements: The implementation of PQueue, AbstractPQueue and UnsortedPQueue must follow pseudocodes below. See implementation samples below.

Implement the SortedPQueue classes by using either ArrayList or LinkedList. List, ArrayList and LinkedList should be based on your earlier implementation in HW5. For those who didn't have a working version of the List, ArrayList and LinkedList implementation, please contact the TA for the assistance. Test: write a performance comparison program to compare the performance of the insert() and removeMin() operation of the two PQueues in running time. To do that, you need to construct one UnsortedPQueue and one SortedPQueue, respectively, by using the same data source, 1,000 data elements. In the performance comparison test, try to time the operation of inserting 1,000 elements and time the operation of removing the same 1,000 elements. Note, try to obtain the time stamps in milliseconds. You should provide a report similar to the following format:

UnsortedPQueue Insertion: xxx milliseconds SortedPQueue Insertion: xxx milliseconds UnsortedPQueue RemoveMin: xxx milliseconds SortedPQueue RemoveMin: xxx milliseconds

Each student submits one copy of the source code: PQueue.java, PQEntry, EntryComparator, AbstractPQueue.java, UnsortedPQueueu.java, SortedPQueue.java and Test.java, as well as all the Java source code related.

LinkedList Implementation public class LinkedList implements List {

private Link head;

private int size;

/**

* constructor to initialize the list

*/

public LinkedList() {

head = null;

size = 0;

}

@Override

public int size() {

return size;

}

@Override

public boolean isEmpty() {

return size == 0;

}

@Override

public Object get(int index) throws OutRangeException {

if (index < 0 || index >= size) {

throw new OutRangeException("Invalid index " + index);

}

// getting a reference

Link reference = head;

int i = 0;

/**

* looping until the required index is found

*/

while (i < index) {

reference = reference.getNext();

i++;

}

// returning element at given index

return reference.getData();

}

@Override

public void set(int index, Object o) throws OutRangeException {

if (index < 0 || index >= size) {

throw new OutRangeException("Invalid index " + index);

}

Link reference = head;

int i = 0;

while (i < index) {

reference = reference.getNext();

i++;

}

reference.setData(o);

}

@Override

public void add(int index, Object o) throws OutRangeException {

if (index < 0 || index > size) {

throw new OutRangeException("Invalid index " + index);

}

if (index == 0) {

/**

* Adding head element

*/

Link link = new Link(o);

link.setNext(head);

head = link;

size++;

} else {

Link reference = head;

int i = 0;

while (i < index - 1) {

reference = reference.getNext();

i++;

}

/**

* adding new element in the middle of current reference and next

* node (if exists)

*/

Link link = new Link(o);

link.setNext(reference.getNext());

reference.setNext(link);

size++;

}

}

@Override

public Object remove(int index) throws OutRangeException {

if (index < 0 || index >= size) {

throw new OutRangeException("Invalid index " + index);

}

if (index == 0) {

Object data = head.getData();

head = head.getNext();

size--;

return data;

}

Link reference = head;

int i = 0;

while (i < index - 1) {

reference = reference.getNext();

i++;

}

Object data = reference.getNext().getData();

/**

* making current reference point to the next of next element (if

* exists), hereby dropping the middle element

*/

reference.setNext(reference.getNext().getNext());

size--;

return data;

}

@Override

public String toString() {

String data = "[";

Link reference = head;

for (int i = 0; i < size; i++) {

data += reference.getData();

if (i != size - 1) {

data += ",";

}

reference = reference.getNext();

}

data += "]";

return data;

}

}

ArrayList Implementation

public class ArrayList implements List {

// attributes

private Object items[];

private int size;

/**

* constructor with argument to set the capacity of array

*/

public ArrayList(int capacity) {

items = new Object[capacity];

size = 0;

}

@Override

public int size() {

return size;

}

@Override

public boolean isEmpty() {

return size == 0;

}

@Override

public Object get(int index) throws OutRangeException {

if (index < 0 || index >= size) {

throw new OutRangeException("Invalid index " + index);

}

// returning element at given index

return items[index];

}

@Override

public void set(int index, Object o) throws OutRangeException {

if (index < 0 || index >= size) {

throw new OutRangeException("Invalid index " + index);

}

// setting new element at given index

items[index] = o;

}

@Override

public void add(int index, Object o) throws OutRangeException {

if (index < 0 || index > size) {

throw new OutRangeException("Invalid index " + index);

}

if (size < items.length) {

/**

* shifting following elements to the right

*/

for (int i = size - 1; i >= index; i--) {

items[i + 1] = items[i];

}

/**

* Adding element at index

*/

items[index] = o;

size++;

}

}

@Override

public Object remove(int index) throws OutRangeException {

if (index < 0 || index >= size) {

throw new OutRangeException("Invalid index " + index);

}

Object item = items[index];

/**

* Shifting remaining elements to the left to occupy the vacant space

*/

for (int i = index; i < size - 1; i++) {

items[i] = items[i + 1];

}

size--;

return item;

}

@Override

public String toString() {

/**

* returns a String representation of list

*/

String data = "[";

for (int i = 0; i < size; i++) {

data += items[i];

if (i != size - 1) {

data += ",";

}

}

data += "]";

return data;

} }

class PQEntry { private integer key; private String value;

public PQEntry (integer k, String v) { this.key = k; this.value = v; }

public integer getkey() { return this.key;; }

public string getvalue() { return this.value; }

public interface PQueue { public int size(); public boolean isEmpty(); public PQEntry insert (integer key, string value); public PQEntry removeMin(); public PQEntry min(); }

public abstract class Abstract PQueue implements PQueue { private Entry comparator comp; protected Abstract PQueue() { this.(new Entrycomparator(); } protected AbstractPQueue (Entry comparator c) { comp = c; } protected int compare (PQEntry a, PQEntry b) { return comp.compare(a,b); } }

public class unsorted PQueue extends Abstract PQueue { private List list = new LinkedList(); public Unsorted PQueue() {super();} public Unsorted PQueue (EntryComparator comp) { super(comp); }

public PQEntry insert (Integer key, String value) { PQEntry newest = new PQEntry (key,value); try { list.add(list.size(),newest); } catch (OutRangeException e) { System.out.println("Out of Range"); } return newest; }

private int findMin() { int min = 0; if (size() == 1) return min;

for (int i = 1; i if (compare((PQEntry) list.get(min), (PQEntry)list.get(i)>0) min = i; } } catch (OutRangeException e) {System.out.println ("Out of Range"):} return min; }

public PQEntry min { if (isEmpty()) return null; PQEntry answer = null; try { answer = (PQEntry)list.get(findMin()); }catch (OutRangeException e) {System.out.println ("...");} return answer; }

public PQEntry removeMin() { if listEmpty() return null; PQEntry answer = null try { answer = (PQEntry) list.remove (findMin()); } catch (OutRangeException e) {System.out.println ("...");} return answer; }