Files Needed for this: PQueue.java, PQEntry, EntryComparator, AbstractPQueue.java, UnsortedPQueueu.java, SortedPQueue.java and Test.java

Use the notes to make this program compatible with notes

Also use the either ArrayList or LinkedList codes to work with

Task: Implementing 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 what I discussed in the class. Any other implementation will NOT receive any credit.

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 

ArrayList.java

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 = 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 = 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 size) {

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

}

if (size

/**

* 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 = 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

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

data += items[i];

if (i != size - 1) {

data += ",";

}

}

data += "]";

return data;

}

}

LInkedList.java

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 = 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

reference = reference.getNext();

i++;

}

// returning element at given index

return reference.getData();

}

@Override

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

if (index = size) {

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

}

Link reference = head;

int i = 0;

while (i

reference = reference.getNext();

i++;

}

reference.setData(o);

}

@Override

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

if (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

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 = 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

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

data += reference.getData();

if (i != size - 1) {

data += ",";

}

reference = reference.getNext();

}

data += "]";

return data;

}

}