[Exercise 2.10 in the textbook] 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: 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.

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

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

}

}

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;

}

}