Task: Implementating the following Java interface and classes: Interface: PQueue
ID: 3917871 • Letter: T
Question
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;
}
Explanation / Answer
PQueue.java
import java.util.ArrayList;
// Interface class PQueue
public interface PQueue {
// Declare an insert() method
public void insert(ArrayList<Integer> arr, int x);
}
AbstractPQueue.java
import java.util.ArrayList;
//An abstract class AbstractPQueue
public abstract class AbstractPQueue {
// An abstract method removeMin()
public abstract void removeMin(ArrayList<Integer> arr1);
}abstract void removeMin(ArrayList<Integer>arr1);
}
UnsortedPQueue.java
import java.util.ArrayList;
import java.util.Random;
// Class definition of UnsortedPQueue
public class UnsortedPQueue extends AbstractPQueue implements PQueue {
// Definition of insert() method
@Override
public void insert(ArrayList<Integer> arr1, int x) {
arr1.add(x);
}
// Definition of removeMin() method
@Override
public void removeMin(ArrayList<Integer> arr1) {
int min = Integer.MAX_VALUE;
int minIndex;
int i;
for (i = 0; i < 1000; i++) {
if (arr1.get(i) < min) {
min = arr1.get(i);
minIndex = i;
}
}
arr1.remove(i);
}
}
SortedPQueue.java
import java.util.ArrayList;
// Class definition of SortedPQueue
public class SortedPQueue extends AbstractPQueue implements PQueue {
// Definition of insert() method
@Override
public void insert(ArrayList<Integer> arr1, int x) {
for (int i = 0; i < 1000; i++) {
arr1.add(i);
}
}
// Definition of removeMin() method
@Override
public void removeMin(ArrayList<Integer> arr1) {
arr1.remove(0);
}
}
Main.java
import java.util.ArrayList;
import java.util.Random;
public class Main {
public static void main(String[] args) {
ArrayList<Integer> arrSort = new ArrayList<Integer>();
for (int i = 0; i < 1000; i++) {
arrSort.add(i);
}
ArrayList<Integer> arrunSort = new ArrayList<Integer>();
// using random function to add unsorted 1000 elements
Random r1 = new Random();
for (int i = 0; i < 1000; i++) {
arrunSort.add(r1.nextInt());
}
UnsortedPQueue upq = new UnsortedPQueue();
SortedPQueue spq = new SortedPQueue();
// PQueue insertion for unsorted elements
long startTime, endTime;
startTime = System.currentTimeMillis();
upq.insert(arrunSort, 1203);
endTime = System.currentTimeMillis();
System.out.println("UnsortedPQueue Insertion " + (endTime - startTime) + " ms");
//PQueue insertion for sorted elements
startTime = System.currentTimeMillis();
spq.insert(arrSort, 1023);
endTime = System.currentTimeMillis();
System.out.println("sortedPQueue Insertion " + (endTime - startTime) + " ms");
// PQueue deletion for unsorted elements
startTime = System.currentTimeMillis();
upq.removeMin(arrunSort);
endTime = System.currentTimeMillis();
System.out.println("UnsortedPQueue Deletion " + (endTime - startTime) + " ms");
// PQueue deletion for sorted elements
startTime = System.currentTimeMillis();
spq.removeMin(arrSort);
endTime = System.currentTimeMillis();
System.out.println("SortedPQueue Deletion " + (endTime - startTime) + " ms");
}
}
-----------------------------------------------------------------------------------------------------------
Sample output:
UnsortedPQueue Insertion 0 ms
sortedPQueue Insertion 0 ms
UnsortedPQueue Deletion 1 ms
SortedPQueue Deletion 0 ms
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.