//
// Simplified array list code with counters to count number of operations
//    This version starts with an array of size 1; in practice it would
//    be a lot more efficient to start at something like 10, but starting
//    at one gives numbers that are easier to analyze.
//
public class SimpleArrayList<E>
{
   @SuppressWarnings("unchecked")
   protected E[] data = (E[])new Object[0];
   protected int count;

   private static long assignments = 0;  // for measuring speed
   public static long getAssignmentCount() { return assignments; }
   public static void resetAssignmentCount() { assignments = 0; }
   
   public E get(int index) {
      return data[index];
   }
   public void add(E value) {
      ensureCapacity(count + 1);
      ++assignments;
      data[count] = value;
      ++count;
   }
   public void add(int index, E value) {
      ensureCapacity(count + 1);
      for(int i = count - 1; i >= index; --i) {
         ++assignments;
         data[i + 1] = data[i];
      }
      ++assignments;
      data[index] = value;
      ++count;
   }
   public void ensureCapacity(int targetSize) {
      if ( targetSize > data.length ) {
         // ensure at least doubling size of array
         if ( targetSize < data.length * 2)
            targetSize = data.length * 2;
         @SuppressWarnings("unchecked")
         E[] newData = (E[])new Object[targetSize];
         for(int i = 0; i < data.length; ++i) {
            ++assignments;
            newData[i] = data[i];
         }
         data = newData;
      }
   }
   public int size() {
      return count;
   }
   public boolean isEmpty() {
      return count == 0;
   }
   @SuppressWarnings("unchecked")
   public void clear() {
      data = (E[])new Object[0];
      count = 0;
   }
}