Task1: implement a concrete ALPQueue class (an ArrayList based priority queue) that extends the AbstractPQueue discussed in the class, along with PQueue.java, ArrayList.java, List.java, PQEntry.java , EntryComparitor.java, and OutOfRangeException.java given in the class (any other different queue class implementation, even if it is implemented by yourself, will not receive any credit).

Task2: implement a concrete HeapPQueue class (a Heap based priority queue) that extends the AbstractPQueue discussed in the class. Similary, you also need PQueue.java, ArrayList.java, List.java, PQEntry.java , EntryComparitor.java, and OutOfRangeException.java given in the class (any other different queue class implementation, even if it is implemented by yourself, will not receive any credit). The ADT of HeapPQueue class is given below:

public class HeapPQueue extends AbstractPQueue { private ArrayList list = new ArrayList();; //constructor public int size(); public boolean isEmpty(); public void heapUp(int i); public void heapDown(int i); public PQEntry insert(Integer key, String value); public PQEntry removeMin(); public PQEntry min(); } 

Task3: write a performance test program to measure the performance of the above two classes in running time. To do that, you may want to construct two big priority queue instances: one for ALPQueue and one for HeapPQueue. Perform at least 5,000 (random numbers) insert() operations and 5,000 removeMin() operation for each priority queue. Your test program should print out the following information:

ALPQueue: insert 5000 elements: xxx ms remove 5000 elements: xxx ms HeapPQueue: insert 5000 elements: xxx ms remove 5000 elements: xxx ms

class code:

public interface PQueue {

int size();

boolean isEmpty();

PQEntry insert (Integer kay, string str);

PQEntry min();

PQEntry removeMin();

}

Public class PQEntry {

private Integer key;

private String value;

public PQEntry(Integerk, String v) {

key = k;

value = v;

}

public Integer getKey() {

return key;

}

public string getValue() {

return value;

}

public void setKey(Integer k) {

key = k;

}

public void setValue(string v) {

value = v;

}

}

Entry Comparator:

import java.util.Comparator;

public class EntryComparator implements comparator {

public int compare(object a, object b)

int akey = ((PQEntry)a).getKey();

int bket = ((PQEntry)b).getKey();

return akey - bkey;

}

}

public abstract class AbstractPQueue implements PQueue {

private Entry comparator comp;

protected AbstractPQueue() {

this(new Entry Comparator());

}

protected AbstractPQueue(EntryComparator c) {

comp = c;

}

protected int compare (PQueue a, PQueue b) {

return comp.compare(a,b);

}

abstract public int size();

public boolean isEmpty()

{

return size == 0;

}

public class ALPQueue extends AbstractPQueue {

private List list = new ArrayList();

public ALPQueue() {

super();

}

public ALPQueue (Entry Comparator c) {

Super();

}

public int size() {

return list.size();

}

private int findMin() {

int min = 0;

if(list.size() == 1)

return min;

try {

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

if(compare((PQEntry) list.get(min), (PQEntry) list.get(1)) > 0) {

min = 1; }

} catch (OutofRangeException e) {

System.out.println("Out of Range");

}

return min;

}

public PQEntry insert(Integer key, String value) {

PQEntry newest = new PQEntry(key, value);

try {

list.add(list.size(), newest);

}

catch (OutofRangeException e) {

System.out.println("Out of Range");

}

return newest;

}

public PQEntry min() {

if(list.isEmpty()) {return null;}

PQEntry en = null;

try {

en = (PQEntry) list.get(findMin());

} catch (OutofRangeException e) {

System.out.println("Out of Range");

} return en;

}

public PQEntry removeMin() {

if(list.isEmpty()) {return null;}

PQEntry en = null;

try {

en = (PQEntry) list.remove(findMin());

} catch (OutofRangeException e) {

System.out.println("Out of Range");

} return en;

}

public class QueueFullException extends Exception { public QueueFullException(String str) { System.out.println("QueueFullException:" + str);

} public QueueFullException (){ this("No space left");

}

}

public interface List {

public int size();

public boolean isEmpty();

public Object get(int i) throws OutOfRangeException;

public void set(int i, Object o) throws OutOfRangeException;

public void add(int i, Object o) throws OutOfRangeException;

public removes(int i) throws OutOfRangeException;

}

public class ArrayList implements List {

private int CAP;

private Object[] elements;

public ArrayList() {

this(100);

}

public ArrayList(int capacity) {

CAP = capacity;

size = 0;

elements = new Object[capactity];

}

public int size() {

return size;

} public boolean isEmpty() {

return size == 0;

} public Object get(int i) throws OutOfRangeException {

if(i < size)

{ return elements[i];

} else { throw OutOfRangeException("Out of Range");

} public void set( int i, Object e) throws OutOfRangeException {

if( i < size)

{ elements[i] = e;

} else throw OutOfRangeException("Out of Range");

} public void add(int i, Object e) throws OutOfRangeException {

if(i > size)

{ throws OutOfRangeException(); }

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

element[j+1] = element[j];

elements[i] = e;

size++

}

public Object remove(int i) throws OutOfRangeException

{ if (i > size) { throw OutOfRangeException("Out of Range"); }

Object o = element[i];

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

{ element[j] = element [j+1];

size--;

return 0;

}

}