For this question you must implement a BlockedList class that implements the List interface. You may use any of the classes in JCF or in the textbook code. The constructor for this class takes an integer block size b and the implementation should have the following performance characteristics: a) get(i) and set(i,x) should run in O(1) time per operation b) add(i,x) and remove(i) should run in O(b+ min{i, n-i}/b) amortized time per operation.

package comp2402a2;

import java.util.AbstractList; import java.util.Collection;

/** * @author morin * * @param the type of objects stored in the List */ public class BlockedList extends AbstractList { /** * keeps track of the class of objects we store */ Factory f;

/** * The number of elements stored */ int n;

/** * The block size */ int b;

/** * Constructor * @param t the type of objects that are stored in this list * @param b the block size */ public BlockedList(Class t, int b) { f = new Factory(t); n = 0; // TODO: Implement this }

public int size() { return n; }

public T get(int i) { // TODO: Implement this if (i < 0 || i > n - 1) throw new IndexOutOfBoundsException(); return null; }

public T set(int i, T x) { // TODO: Implement this if (i < 0 || i > n - 1) throw new IndexOutOfBoundsException(); return null; }

public void add(int i, T x) { // TODO: Implement this if (i < 0 || i > n) throw new IndexOutOfBoundsException(); }

public T remove(int i) { // TODO: Implement this if (i < 0 || i > n - 1) throw new IndexOutOfBoundsException(); return null; } }