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

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 RootishArrayDeque that has only O(sqrt(n)) wasted space. The performance requirements for a RootishArrayDeque are:

size(), get(i), and set(i,x) each run in constant amortized time.

remove(i) and add(i,x) each run in O(1+min{i,n-i}) amortized time

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.

testPart2(rad) that takes as input a List called rad and tests if it satisfies the requirements for Question 2:

This function should do all kinds of correctness tests on rad.

This function should tests if the running time of the remove(i) and add(i,x) is indeed O(1+min{i,n-i}).

RootishArrayDeque

package comp2402a2;

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

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

public RootishArrayDeque(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");
// set(i, x);
}

public T remove(int i) {
if (i < 0 || i > size() - 1) throw new IndexOutOfBoundsException();
// Put your own code here
throw new UnsupportedOperationException("size(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> rad = new ArrayDeque<Integer>(Integer.class);
List<Integer> rad = new RootishArrayDeque<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++) {
rad.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++) {
rad.add(0, 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++) {
rad.remove(rad.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++) {
rad.remove(0);
}
s.stop();
System.out.println("done (" + s.elapsedSeconds() + "s)");
}

}

RootishArrayStack.java

package comp2402a2;

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

/**
* This class implements the List interface using a collection of arrays of
* sizes 1, 2, 3, 4, and so on. The main advantages of this over an
* implementation like ArrayList is that there is never more than O(sqrt(size())
* space being used to store anything other than the List elements themselves.
* Insertions and removals take O(size() - i) amortized time.
*
* This provides a space-efficient implementation of an ArrayList.
* The total space used beyond what is required to store elements is O(sqrt(n))
* @author morin
*
* @param <T> the type of objects stored in this list
*/
public class RootishArrayStack<T> extends AbstractList<T> {
/**
* The type of objects stored in this list
*/
Factory<T> f;

/*
* The blocks that contains the list elements
*/
List<T[]> blocks;

/**
* The number of elements in the list
*/
int n;

/**
* Convert a list index i into a block number
* @param i
* @return the index of the block that contains list
* element i
*/
protected static int i2b(int i) {
double db = (-3.0 + Math.sqrt(9 + 8*i)) / 2.0;
int b = (int)Math.ceil(db);
return b;
}

protected void grow() {
blocks.add(f.newArray(blocks.size()+1));
}

protected void shrink() {
int r = blocks.size();
while (r > 0 && (r-2)*(r-1)/2 >= n) {
blocks.remove(blocks.size()-1);
r--;
}
}

public T get(int i) {
if (i < 0 || i > n - 1) throw new IndexOutOfBoundsException();
int b = i2b(i);
int j = i - b*(b+1)/2;
return blocks.get(b)[j];
}

public T set(int i, T x) {
if (i < 0 || i > n - 1) throw new IndexOutOfBoundsException();
int b = i2b(i);
int j = i - b*(b+1)/2;
T y = blocks.get(b)[j];
blocks.get(b)[j] = x;
return y;
}

public void add(int i, T x) {
if (i < 0 || i > n) throw new IndexOutOfBoundsException();
int r = blocks.size();
if (r*(r+1)/2 < n + 1) grow();
n++;
for (int j = n-1; j > i; j--)
set(j, get(j-1));
set(i, x);
}

public T remove(int i) {
if (i < 0 || i > n - 1) throw new IndexOutOfBoundsException();
T x = get(i);
for (int j = i; j < n-1; j++)
set(j, get(j+1));
n--;
int r = blocks.size();
if ((r-2)*(r-1)/2 >= n) shrink();
return x;
}

public int size() {
return n;
}

public RootishArrayStack(Class<T> t) {
f = new Factory<T>(t);
n = 0;
blocks = new ArrayList<T[]>();
}

public void clear() {
blocks.clear();
n = 0;
}
}

Testing.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

package comp2402a2;

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;

}

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)");
}

}

Related Questions

Navigate

• Browse (All)
• Browse H
• Subjects

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