package java.util;

public class ArrayList<T> implements List<T> {
  private static final int MinimumCapacity = 16;

  private Object[] array;
  private int size;

  public ArrayList(int capacity) {
    resize(capacity);
  }

  public ArrayList() {
    this(0);
  }

  public ArrayList(Collection<T> source) {
    this(source.size());
    for (T o : source) {
      add(o);
    }
  }

  private void grow() {
    if (array == null || size >= array.length) {
      resize(array == null ? MinimumCapacity : array.length * 2);
    }
  }

  private void shrink() {
    if (array.length / 2 >= MinimumCapacity && size <= array.length / 3) {
      resize(array.length / 2);
    } else if (size == 0) {
      resize(0);
    }
  }

  private void resize(int capacity) {
    Object[] newArray = null;
    if (capacity != 0) {
      if (array != null && array.length == capacity) {
        return;
      }

      newArray = new Object[capacity];
      if (array != null) {
        System.arraycopy(array, 0, newArray, 0, size);
      }
    }
    array = newArray;
  }

  private static boolean equal(Object a, Object b) {
    return (a == null && b == null) || (a != null && a.equals(b));
  }

  public int size() {
    return size;
  }

  public boolean contains(T element) {
    for (int i = 0; i < size; ++i) {
      if (equal(element, array[i])) {
        return true;
      }
    }
    return false;
  }

  public void add(int index, T element) {
    size = Math.max(size+1, index+1);
    grow();
    System.arraycopy(array, index, array, index+1, size-index-1);
    array[index] = element;
  }

  public boolean add(T element) {
    ++ size;
    grow();
    array[size - 1] = element;
    return true;
  }

  public int indexOf(T element) {
    for (int i = 0; i < size; ++i) {
      if (equal(element, array[i])) {
        return i;
      }
    }
    return -1;
  }

  public int lastIndexOf(T element) {
    for (int i = size; i >= 0; --i) {
      if (equal(element, array[i])) {
        return i;
      }
    }
    return -1;
  }

  public T get(int index) {
    if (index >= 0 && index < size) {
      return (T) array[index];
    } else {
      throw new IndexOutOfBoundsException(index + " not in [0, " + size + ")");
    }    
  }

  public T set(int index, T element) {
    if (index >= size) {
      resize(index+1);
    }
    Object oldValue = array[index];
    array[index] = element;
    return (T) oldValue;
  }

  public T remove(int index) {
    T v = get(index);

    if (index == size - 1) {
      array[index] = null;
    } else {
      System.arraycopy(array, index + 1, array, index, size - index);
    }

    -- size;
    shrink();

    return v;
  }

  public boolean remove(T element) {
    for (int i = 0; i < size; ++i) {
      if (equal(element, array[i])) {
        remove(i);
        return true;
      }
    }
    return false;
  }

  public boolean isEmpty() {
    return size() == 0;
  }

  public <S> S[] toArray(S[] a) {
    Object[] retVal = null;

    if (a.length >= size) {
      retVal = a;
    } else {
      retVal = new Object[size];
    }
    for (int i = 0; i < size; ++i) {
      retVal[i] = array[i];
    }
    if (a.length > size) {
      a[size] = null;
    }
    return (S[])retVal;
  }

  public void clear() {
    array = null;
    size = 0;
  }

  public Iterator<T> iterator() {
    return new Collections.ArrayListIterator(this);
  }

  public ListIterator<T> listIterator(int index) {
    return new Collections.ArrayListIterator(this, index);
  }

  public String toString() {
    return Collections.toString(this);
  }
}

@@ -2288,49 +2288,35 @@
  %3E= 
-size) %7B%0A      resize(index+1);%0A 
+0 && index %3C size) %7B%0A
    
-%7D%0A
    
- 
 Obje
@@ -2343,24 +2343,26 @@
 index%5D;%0A    
+  
 array%5Bindex%5D
@@ -2365,32 +2365,34 @@
 dex%5D = element;%0A
+  
     return (T) o
@@ -2396,24 +2396,123 @@
 ) oldValue;%0A
+    %7D else %7B%0A      throw new IndexOutOfBoundsException(index + %22 not in %5B0, %22 + size + %22)%22);%0A    %7D%0A
   %7D%0A%0A  publi

make ArrayList.set() do bounds checking