Hello please read the question properly and provide appropriate code answer to i

ID: 3592205 • Letter: H

Question

Hello please read the question properly and provide appropriate code answer to it. and show result on screen that the code works. It should shay true after compiling. all the classes required are given. This requires java to solve.

Question

Implement a Treque (triple-ended queue). This is an implementation of the List interface that allows for fast modifications at the front, back, and middle. You can make your Treque a subclass of AbstractList so that you don't have to write all the List methods from scratch. The performance requirements for a Treque are:

size(), get(i), and set(i,x) should each take constant time (O(1)).

add(i,x) and remove(i) should be fast if the value of i is close to 0, n or n/2. More precisely, the amortized running time of these operations should be O(1 + min{i, n-i, |n/2-i|}).

Testing Part

Within the Tester class, write the following functions, all of which return true if all tests are successful or false if any test fails.

testPart1(ell) that takes as input a List called ell, and tests if it satisfies the requirements for Question 1:

This function should do all kinds of correctness tests on ell

This function should check that all methods run in the specified time. In particular, it should check that add(i,x) and remove(i) are fast when O(1 + min{i, n-i, |n/2 - i|}) is small.

Treque.java

package comp2402a2;

import java.util.AbstractList;
import java.util.List;

/**
*/
public class Treque<T> extends AbstractList<T> {
/**
* You decide on the instance variables you need.
*/

public Treque(Class<T> t) {
// Put your own code here
throw new UnsupportedOperationException("Constructor not yet implemented");
}

public T get(int i) {
if (i < 0 || i > size() - 1) throw new IndexOutOfBoundsException();
// Put your own code here instead of throwing this exception
throw new UnsupportedOperationException("get(i) not yet implemented");
}

public T set(int i, T x) {
if (i < 0 || i > size() - 1) throw new IndexOutOfBoundsException();
// Put your own code here instead of throwing this exception
throw new UnsupportedOperationException("set(i,x) not yet implemented");
}

public void add(int i, T x) {
if (i < 0 || i > size()) throw new IndexOutOfBoundsException();
// Put your own code here
throw new UnsupportedOperationException("add(i,x) not yet implemented");
}

public T remove(int i) {
if (i < 0 || i > size() - 1) throw new IndexOutOfBoundsException();
// Put your own code here
throw new UnsupportedOperationException("remove(i) not yet implemented");
}

public int size() {
// Put your own code here
throw new UnsupportedOperationException("size() not yet implemented");
}

public static void main(String[] args) {
//List<Integer> tr = new ArrayDeque<Integer>(Integer.class);
List<Integer> tr = new Treque<Integer>(Integer.class);
int K = 1000000;
Stopwatch s = new Stopwatch();
System.out.print("Appending " + K + " items...");
System.out.flush();
s.start();
for (int i = 0; i < K; i++) {
tr.add(i);
}
s.stop();
System.out.println("done (" + s.elapsedSeconds() + "s)");

System.out.print("Prepending " + K + " items...");
System.out.flush();
s.start();
for (int i = 0; i < K; i++) {
tr.add(0, i);
}
s.stop();
System.out.println("done (" + s.elapsedSeconds() + "s)");

System.out.print("Midpending(?!) " + K + " items...");
System.out.flush();
s.start();
for (int i = 0; i < K; i++) {
tr.add(tr.size()/2, i);
}
s.stop();
System.out.println("done (" + s.elapsedSeconds() + "s)");

System.out.print("Removing " + K + " items from the back...");
System.out.flush();
s.start();
for (int i = 0; i < K; i++) {
tr.remove(tr.size()-1);
}
s.stop();
System.out.println("done (" + s.elapsedSeconds() + "s)");

System.out.print("Removing " + K + " items from the front...");
System.out.flush();
s.start();
for (int i = 0; i < K; i++) {
tr.remove(0);
}
s.stop();
System.out.println("done (" + s.elapsedSeconds() + "s)");

System.out.print("Removing " + K + " items from the middle...");
System.out.flush();
s.start();
for (int i = 0; i < K; i++) {
tr.remove(tr.size()/2);
}
s.stop();
System.out.println("done (" + s.elapsedSeconds() + "s)");
}

}

Abstraction Table

package comp2402a2;

/**
*/
public interface AbstractTable<T> {
/**
* You decide on the instance variables you need.
*/

public int rows();
public int cols();
public T get(int i, int j);
public T set(int i, int j, T x);
public void addRow(int i);
public void removeRow(int i);
public void addCol(int j);
public void removeCol(int j);
public String toString();
}

Tester.java

package comp2402a2;
import java.util.List;

/**
*/
public class Tester {
public static boolean testPart1(List<Integer> ell) {
return true;
}

public static boolean testPart2(List<Integer> ell) {
return true;
}

public static boolean testPart3(AbstractTable<Integer> ell) {
return true;
}

}

Stopwatch.java

package comp2402a2;

public class Stopwatch {
protected long start, stop;

public void start() {
start = System.nanoTime();
}

public void stop() {
stop = System.nanoTime();
}

public double elapsedSeconds() {
return (stop-start)*1e-9;
}
}

Explanation / Answer

import java.util.AbstractList;
import java.util.List;

/**
*/
public class Treque<T> extends AbstractList<T> {

int size =0;

Private Object q[1000]; // default value for size of list is 1000

public Treque(Class<T> t) {

q = new Object[1000];

}

public T get(int i) {

if (i < 0 || i > size() - 1) throw new IndexOutOfBoundsException();
return (T) q[i];
}

public T set(int i, T x) {
if (i < 0 || i > size() - 1) throw new IndexOutOfBoundsException();

q[i] = x;

return (T) q[i];

}

public void add(int i, T x) {
if (i < 0 || i > size()) throw new IndexOutOfBoundsException();

q [i] = x;

size++;

}

public T remove(int i) {
if (i < 0 || i > size() - 1) throw new IndexOutOfBoundsException();

Object O;

O = q[i] ;

q[i] = null ;

size-- ;

return (T)O;

}

public int size() {

return size;

}

System.out.print("Prepending " + K + " items...");
System.out.flush();
s.start();
for (int i = 0; i < K; i++) {
tr.add(0, i);
}
s.stop();
System.out.println("done (" + s.elapsedSeconds() + "s)");

}

Navigate

Hello please read the question properly and provide appropriate code answer to i

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

Hello please read the question properly and provide appropriate code answer to i

Question

Explanation / Answer

Related Questions

Navigate