PLEASE COMPLETE THE QUESTION AND DO NOT JUST COPY AND PASTE THE QUESTION IN THE SOLUTION BOX. PLEASE..

"ROOTISHARRAYSTACK" USE THIS TO HELP WITH THE OTHER CLASS 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  the type of objects stored in this list  */ public class RootishArrayStack extends AbstractList { /**  * The type of objects stored in this list  */  Factory f; /*  * The blocks that contains the list elements  */  List 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  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  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  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  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) { f = new Factory(t); n = 0; blocks = new ArrayList(); } public void clear() { blocks.clear(); n = 0; } } 

"ROOTISHARRAYDEQUE" THAT'S WHERE CODE GOES import java.util.AbstractList; import java.util.List; import java.util.ArrayList; /**  */ public class RootishArrayDeque extends AbstractList { /**  * You decide on the instance variables you need.  */   public RootishArrayDeque(Class t) { // Put your own code here  throw new UnsupportedOperationException("Constructor not yet implemented"); } public T get(int i) { if (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  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  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  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 rad = new ArrayDeque(Integer.class);  List rad = new RootishArrayDeque(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 out.println("done (" + s.elapsedSeconds() + "s)"); System.out.print("Prepending " + K + " items..."); System.out.flush(); s.start(); for (int i = 0; i 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 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 out.println("done (" + s.elapsedSeconds() + "s)"); } } 

[Exercise 2.10 in the textbook] Implement a RootishArrayDeque that has only O(sqrt(n)) wasted space. The performance requirements for a RootishArrayDeque are: 1. size gt(i) and set(i,x) each run in constant amortized time. 2. remove() and add(i,x) each run in O(1+minfi, n-i) amortized time. Hint: I (and you) know of at least two ways to answer this question, and both of them make use of the RootishArrayStack implementation included in the assignment skeleton