Part I: Implementation

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

Hint:Make use of the RootishArrayStack implementation included in the assignment skeleton

Part II: Testing

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

package comp2402a2;

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 < 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("size(i) not yet implemented"); }

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

}

________________________________________________________________________________________________________________

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 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 < 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) { f = new Factory(t); n = 0; blocks = new ArrayList(); }

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

_________________________________________________________________________________________________________________________

Tester.java

package comp2402a2; import java.util.List;

/** This class should orchestrate the testing of each part of the assignment. Testing should include correctness testing and efficiency testing. The testing methods below (e.g. testPart1()) should return false if the provided List is not correct/efficient. If the provided List is correct and efficient the method should return true within a short amount of time. Correctness testing involves verifying that all of the required operations are implemented and behave correctly. E.g. If your class implements the list interface does it work the same as any other list? A good way to test is to do the same operations on both your implementation and a known correct list implementation. An incorrect implementation will result in a different state of stored data. Efficiency testing involves verifying that the operations are implemented efficiently (according to the assignment guidelines). E.g. If an operation is supposed to run in constant time then it should be fast regardless of the size of your data structure. A good way to test is to do lots of fast operations and ensure they are completed within a short time. An inefficient implementation will take a long time to complete operations that should be fast. Note: the server will impose its own time limit on your tests, but you can do your own timing using the Stopwatch class: Stopwatch s = new Stopwatch(); System.out.println("Starting test: "); s.start(); ... do some testing ... s.stop(); System.out.println("Done in " + s.elapsedSeconds() + " seconds"); */ public class Tester { public static boolean testPart1(List ell) { //do correctness tests on Treque //do efficiency tests on Treque return true; }

public static boolean testPart2(List ell) { //do correctness tests on RootishArrayDeque //doo efficiency tests on RootishArrayDeque return true; }

public static boolean testPart3(AbstractTable ell) { return true; } public static void main(String[] args) { List tr = new Treque(Integer.class); System.out.println("testPart1 returns " + testPart1(tr));

List rad = new RootishArrayDeque(Integer.class); System.out.println("testPart2 returns " + testPart2(rad));

Table tbl = new Table<>(Integer.class); System.out.println("testPart3 returns " + testPart3(tbl)); }

}