I need help with this java Data Structures assignment. Thanks The System.nanoTim
ID: 3827916 • Letter: I
Question
I need help with this java Data Structures assignment. Thanks
The System.nanoTime() is used to measure the Runtime
Runtime Class Code
import java.util.Arrays;
public class RunTime {
private static final int MAX = 10;
private long[] runtimes;
private int count;
public RunTime() {
this.runtimes = new long[MAX];
this.count += 0;
}
public void addRuntime(long runTime) {
if (this.count == MAX) {
for (int i = 0; i < (MAX - 1); i++) {
this.runtimes[i] = this.runtimes[i + 1];
}
this.runtimes[MAX - 1] = runTime;
} else {
this.runtimes[count] = runTime;
this.count += 1;
}
}
public double getAverageRunTime() {
double sum = 0;
for (int i = 0; i < this.count; i++) {
sum += this.runtimes[i];
}
return (sum / this.count);
}
public long getLastRunTime() {
return this.runtimes[this.count - 1];
}
public long[] getRunTimes() {
return Arrays.copyOf(this.runtimes, this.count);
}
public void resetRunTimes() {
for (int i = 0; i < MAX; i++) {
this.runtimes[i] = 0;
}
}
}
ListInterface Methods
LinkedLinkNode
Driver Interface Methods
Details 1. RunTime Class You will copy the RunTime class that you created in Homework 1 to the project you are using for this assignment. 2. Array Based List Class You will write the ArrayBasedList. java class which will implement the List Interface. The interface may be downloaded from ListInterfaceiava. Please note that you do not inherit from the RunTime class. 3. Linked List Class You will write the LinkedList java class which will implement the List Interface The interface may be downloaded from ListInterface.iava Please note that you do not inherit from the RunTime class. 4. Linked list Node Class Your will write the LinkedListNode. Please see the Linked List Documentation for all the methods you will need. Please note that you do not inherit from the RunTime class. 5. Driver Class You will write the Driver ava class which will implement the Driver Interface. The interface may be downloaded from DriverInterface.iava.Explanation / Answer
LinkedListNode.java:
public class LinkedListNode<I extends Comparable<I>> {
I data;
LinkedListNode<I> next;
LinkedListNode(I data){
this.data = data;
this.next = null;
}
LinkedListNode(I data, LinkedListNode<I> next){
this.next = next;
this.data = data;
}
public I getData() {
return data;
}
public void setData(I data) {
this.data = data;
}
public LinkedListNode<I> getNext() {
return next;
}
public void setNext(LinkedListNode<I> next) {
this.next = next;
}
}
ListInterface.java:
public interface ListInterface<I> {
int size();
boolean isEmpty();
void add(I obj);
boolean add(I obj, int index);
boolean addSorted(I obj);
I get(int index);
I replace(I obj, int index);
boolean remove(int index);
void removeAll();
}
DriverInterface.java:
public interface DriverInterface {
public enum ListType {
ArrayBasedList, LinkedList;
}
public enum TestType {
AddSortedOdd, AddSortedEven, AddAll, AddAllAtIndexZero, RemoveAllEven, RemoveAllOdd;
}
public ListInterface<Integer> createList(DriverInterface.ListType listType, DriverInterface.TestType testType);
public ListInterface<Integer> initializeList(ListInterface<Integer> list, int firstNumber, int lastNumber, int increment, Integer index);
double memoryUsage();
RunTime runTestCase(DriverInterface.ListType listType, DriverInterface.TestType testType, int numberOfTimes);
}
Driver.java:
public class Driver implements DriverInterface{
public static void main(String[] args) {
Driver d = new Driver();
d.runTestCase(TestType.AddSortedOdd);
d.runTestCase(TestType.AddSortedEven);
d.runTestCase(TestType.AddAll);
d.runTestCase(TestType.AddAllAtIndexZero);
d.runTestCase(TestType.RemoveAllEven);
d.runTestCase(TestType.RemoveAllOdd);
}
public void runTestCase(DriverInterface.TestType testType) {
System.out.println("Running test Case: " + testType);
System.out.print(" ");
for(int i=1; i<=10; i++) {
System.out.print("Run " + i + " ");
}
System.out.print("Avergae " +" ");
System.out.print("Memory Usage " +" ");
System.out.print(" ");
for(int i=1; i<=10; i++) {
System.out.print("Seconds ");
}
System.out.print("Seconds ");
System.out.print("Mega Bytes " +" ");
System.out.print(" ");
for(int i=1; i<=10; i++) {
System.out.print("------- ");
}
System.out.print("------- ");
System.out.print("------------- ");
RunTime rt = runTestCase(ListType.ArrayBasedList, testType, 10);
System.out.print("ArrayBasedList ");
for(long l: rt.getRunTimes()) {
System.out.print(l/1000 + " ");
}
System.out.print(rt.getAverageRunTime()/1000 + " ");
System.out.print(memoryUsage() + " ");
rt = runTestCase(ListType.LinkedList, testType, 10);
System.out.print("LinkedList ");
for(long l: rt.getRunTimes()) {
System.out.print(l/1000 + " ");
}
System.out.print(rt.getAverageRunTime()/1000 + " ");
System.out.print(memoryUsage() + " ");
}
@Override
public ListInterface<Integer> createList(ListType listType,
TestType testType) {
ListInterface<Integer> list = null;
if(listType.equals(ListType.ArrayBasedList)) {
list = new ArrayBasedList<>();
} else if(listType.equals(ListType.LinkedList)) {
list = new LinkedList<>();
}
if(testType.equals(TestType.AddSortedOdd)) {
list = initializeList(list, 1, 9999, 2, null);
} else if(testType.equals(TestType.AddSortedEven)) {
list = initializeList(list, 2, 10000, 2, null);
} else if(testType.equals(TestType.AddAll)) {
list = initializeList(list, 1, 10000, 1, null);
} else if(testType.equals(TestType.AddAllAtIndexZero)) {
list = initializeList(list, 1, 10000, 1, 0);
} else if(testType.equals(TestType.RemoveAllEven)) {
list = initializeList(list, 1, 10000, 1, null);
} else if(testType.equals(TestType.RemoveAllOdd)) {
list = initializeList(list, 1, 10000, 1, null);
}
return list;
}
@Override
public ListInterface<Integer> initializeList(ListInterface<Integer> list,
int firstNumber, int lastNumber, int increment, Integer index) {
for(int i= firstNumber; i <= lastNumber; i+= increment) {
if(index == null)
list.add(i);
else
list.add(i, index);
}
return list;
}
@Override
public double memoryUsage() {
Runtime systemRunTime = Runtime.getRuntime();
return systemRunTime.totalMemory() - systemRunTime.freeMemory();
}
public RunTime runTestCase(ListType listType, TestType testType,
int numberOfTimes) {
RunTime runtime = new RunTime();
for(int i=0; i< numberOfTimes; i++) {
long start = System.nanoTime();
ListInterface<Integer> list= createList(listType, testType);
if(testType.equals(TestType.RemoveAllEven)) {
for(int j=0; j< list.size(); ) {
if(list.get(j)%2 == 0) {
list.remove(j);
} else {
j++;
}
}
} else if(testType.equals(TestType.RemoveAllOdd)) {
for(int j=0; j< list.size(); ) {
if(list.get(j)%2 == 1) {
list.remove(j);
} else {
j++;
}
}
}
long end = System.nanoTime();
runtime.addRuntime(end - start);
}
return runtime;
}
}
ArrayBasedList.java:
import java.util.ArrayList;
public class ArrayBasedList<I extends Comparable<I>> implements ListInterface<I>{
ArrayList<I> list = new ArrayList<>();
@Override
public int size() {
return list.size();
}
@Override
public boolean isEmpty() {
return list.isEmpty();
}
@Override
public void add(I obj) {
list.add(obj);
}
@Override
public boolean add(I obj, int index) {
if(index >= 0 && index <= list.size()) {
list.add(index, obj);
return true;
}
return false;
}
@Override
public boolean addSorted(I obj) {
int i=0;
for(I a: list) {
// object need to go to i index
if(obj.compareTo(a) < 0) {
break;
}
}
add(obj, i);
return true;
}
@Override
public I get(int index) {
if(index >= 0 && index < list.size()) {
return list.get(index);
}
return null;
}
@Override
public I replace(I obj, int index) {
if(index >= 0 && index < list.size()) {
return list.set(index, obj);
}
return null;
}
@Override
public boolean remove(int index) {
if(index >= 0 && index < list.size()) {
list.remove(index);
return true;
}
return false;
}
@Override
public void removeAll() {
list.clear();
}
}
LinkedList.java:
public class LinkedList<I extends Comparable<I>> implements ListInterface<I>{
java.util.LinkedList<I> list = new java.util.LinkedList<>();
@Override
public int size() {
return list.size();
}
@Override
public boolean isEmpty() {
return list.isEmpty();
}
@Override
public void add(I obj) {
list.add(obj);
}
@Override
public boolean add(I obj, int index) {
if(index >= 0 && index <= list.size()) {
list.add(index, obj);
return true;
}
return false;
}
@Override
public boolean addSorted(I obj) {
int i=0;
for(I a: list) {
// object need to go to i index
if(obj.compareTo(a) < 0) {
break;
}
}
add(obj, i);
return true;
}
@Override
public I get(int index) {
if(index >= 0 && index < list.size()) {
return list.get(index);
}
return null;
}
@Override
public I replace(I obj, int index) {
if(index >= 0 && index < list.size()) {
return list.set(index, obj);
}
return null;
}
@Override
public boolean remove(int index) {
if(index >= 0 && index < list.size()) {
list.remove(index);
return true;
}
return false;
}
@Override
public void removeAll() {
list.clear();
}
}
Sample Output:
Running test Case: AddSortedOdd
Run 1 Run 2 Run 3 Run 4 Run 5 Run 6 Run 7 Run 8 Run 9 Run 10 Avergae Memory Usage
Seconds Seconds Seconds Seconds Seconds Seconds Seconds Seconds Seconds Seconds Seconds Mega Bytes
------- ------- ------- ------- ------- ------- ------- ------- ------- ------- ------- -------------
ArrayBasedList 2507 433 397 435 380 387 379 353 361 351 598.8066 5385440.0
LinkedList 2690 862 2174 193 184 189 175 180 182 183 701.6646 8069840.0
Running test Case: AddSortedEven
Run 1 Run 2 Run 3 Run 4 Run 5 Run 6 Run 7 Run 8 Run 9 Run 10 Avergae Memory Usage
Seconds Seconds Seconds Seconds Seconds Seconds Seconds Seconds Seconds Seconds Seconds Mega Bytes
------- ------- ------- ------- ------- ------- ------- ------- ------- ------- ------- -------------
ArrayBasedList 630 271 323 932 1215 854 372 467 424 359 585.1071 9412016.0
LinkedList 283 292 256 367 286 305 279 280 280 257 289.0729 1.0754192E7
Running test Case: AddAll
Run 1 Run 2 Run 3 Run 4 Run 5 Run 6 Run 7 Run 8 Run 9 Run 10 Avergae Memory Usage
Seconds Seconds Seconds Seconds Seconds Seconds Seconds Seconds Seconds Seconds Seconds Mega Bytes
------- ------- ------- ------- ------- ------- ------- ------- ------- ------- ------- -------------
ArrayBasedList 560 345 338 339 348 351 347 352 338 355 367.7448 1.478072E7
LinkedList 341 336 342 341 339 348 352 352 359 409 352.3047 1.880732E7
Running test Case: AddAllAtIndexZero
Run 1 Run 2 Run 3 Run 4 Run 5 Run 6 Run 7 Run 8 Run 9 Run 10 Avergae Memory Usage
Seconds Seconds Seconds Seconds Seconds Seconds Seconds Seconds Seconds Seconds Seconds Mega Bytes
------- ------- ------- ------- ------- ------- ------- ------- ------- ------- ------- -------------
ArrayBasedList 13144 7984 6145 5516 5543 5623 5526 5514 5710 5477 6618.6009 2.1491688E7
LinkedList 2537 1585 1433 1240 1120 1130 1003 771 799 801 1242.3264 2.5518264E7
Running test Case: RemoveAllEven
Run 1 Run 2 Run 3 Run 4 Run 5 Run 6 Run 7 Run 8 Run 9 Run 10 Avergae Memory Usage
Seconds Seconds Seconds Seconds Seconds Seconds Seconds Seconds Seconds Seconds Seconds Mega Bytes
------- ------- ------- ------- ------- ------- ------- ------- ------- ------- ------- -------------
ArrayBasedList 8353 5215 3925 3886 8943 3975 3553 4163 3573 3573 4916.5157 2.8202632E7
LinkedList 60975 51166 49472 59108 55618 57676 61164 90474 58799 51267 59572.4504 3.2229232E7
Running test Case: RemoveAllOdd
Run 1 Run 2 Run 3 Run 4 Run 5 Run 6 Run 7 Run 8 Run 9 Run 10 Avergae Memory Usage
Seconds Seconds Seconds Seconds Seconds Seconds Seconds Seconds Seconds Seconds Seconds Mega Bytes
------- ------- ------- ------- ------- ------- ------- ------- ------- ------- ------- -------------
ArrayBasedList 3068 3072 2990 2837 2850 2921 2894 2999 2843 2838 2931.7831 3.6318304E7
LinkedList 64096 49953 49232 49114 60600 49173 53374 51813 94664 54233 57625.6038 4.0344904E7