Task: Implementating the following Java interface and classes: Interface: PQueue
ID: 3917462 • 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 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
Please see implementation of classes below. Let me know if you need anyhting else.
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;
}
}
Explanation / Answer
ANSWER:
--------------------interface PQueue---------------------
package com.comp.impl;
import java.util.ArrayList;
//An interface which has insert method
public interface PQueue {
public void insert(ArrayList<Integer>arr,int x);
}
--------------------------AbstractPQueue class--------------------------
package com.comp.impl;
import java.util.ArrayList;
//An abstract class which has removeMin method
public abstract class AbstractPQueue {
public abstract void removeMin(ArrayList<Integer>arr1);
}
------------------------------unsortedPQueue concrete class-----------------------------
package com.comp.queue;
import java.util.ArrayList;
import java.util.Random;
import com.comp.impl.AbstractPQueue;
import com.comp.impl.PQueue;
/*this class will calculate the performance comparison of removeMin and insertion of 1000 elements
* of unsorted list
*/
public class UnsortedPQueue extends AbstractPQueue implements PQueue {
@Override
public void insert(ArrayList<Integer>arr1,int x) {
arr1.add(x);
}
@Override
public void removeMin(ArrayList<Integer>arr1) {
//comparing with the minimum value adn removing it
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 concrete class-----------------------
package com.comp.queue;
import java.util.ArrayList;
import com.comp.impl.AbstractPQueue;
import com.comp.impl.PQueue;
/* this class will calculate the performance comparison of removeMin and insertion of 1000 elements
* of sorted list
*/
public class SortedPQueue extends AbstractPQueue implements PQueue{
@Override
public void insert(ArrayList<Integer>arr1,int x) {
for(int i=0;i<1000;i++ ){
arr1.add(i);
}
}
@Override
public void removeMin(ArrayList<Integer>arr1) {
//for the sorted list, minimum element is at index 0
arr1.remove(0);
}
}
---------------------------------Main class--------------------------------------
package com.comp.main;
import java.util.ArrayList;
import java.util.Random;
import com.comp.queue.SortedPQueue;
import com.comp.queue.UnsortedPQueue;
public class StarterMain {
public static void main(String[] args) {
ArrayList<Integer> arrSort = new ArrayList<Integer>();
//sorted list
for(int i=0;i<1000;i++ ){
arrSort.add(i);
}
ArrayList<Integer> arrunSort = new ArrayList<Integer>();
//Adding unsorted 1000 elements using random function
Random r1 = new Random();
for(int i=0;i<1000;i++){
arrunSort.add(r1.nextInt());
}
//this class will perform the comparison checks for both insertion and remove min operation
UnsortedPQueue upq = new UnsortedPQueue();
SortedPQueue spq = new SortedPQueue();
//unsorted PQueue insertion
long startTime,endTime;
startTime = System.currentTimeMillis();
upq.insert(arrunSort,1203);
endTime = System.currentTimeMillis();
System.out.println("UnsortedPQueue Insertion "+ (endTime-startTime)+" ms");
//sorted PQueue insertion
startTime = System.currentTimeMillis();
spq.insert(arrSort,1023);
endTime = System.currentTimeMillis();
System.out.println("sortedPQueue Insertion "+ (endTime-startTime)+" ms");
//unsortedPQueue remove min
startTime = System.currentTimeMillis();
upq.removeMin(arrunSort);
endTime = System.currentTimeMillis();
System.out.println("UnsortedPQueue Deletion "+ (endTime-startTime)+" ms");
//sortedPQueue remove min
//unsortedPQueue remove min
startTime = System.currentTimeMillis();
spq.removeMin(arrSort);
endTime = System.currentTimeMillis();
System.out.println("SortedPQueue Deletion "+ (endTime-startTime)+" ms");
}
}
************************************************************************************************
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.