Task: Implementating the following Java interface and classes: Interface: PQueue

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:

Submission:

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.

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

Navigate

• Browse (All)
• Browse T
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.