sclass CircularArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, Serializable {
  private transient Object[] elementData;
  private int size;
  private int head;
  private int tail;
  
  *(int initialCapacity) {
  	if (initialCapacity < 0) {
  		throw new IllegalArgumentException(
  				"Illegal Capacity: " + initialCapacity);
  	}
  
  	elementData = new Object[initialCapacity];
  	size = tail = head = 0;
  }
  
  *() { this(10); }
  
  *(Collection<? extends E> c) {
  	elementData = c.toArray();
  	tail = 0;
  	size = head = elementData.length;
  
  	// c.toArray might (incorrectly) not return Object[] (see 6260652)
  	if (elementData.getClass() != Object[].class)
  		elementData = Arrays.copyOf(elementData, size, Object[].class);
  }
  
  private void copy(Object[] src, Object[] dest) {
  	System.arraycopy(src, 0, dest, 0, head);
  	System.arraycopy(src, src.length + tail, 
  			dest, dest.length + tail, -tail);
  }
  
  private void ensureCapacityInternal(int minCapacity) {
  	modCount++;
  
  	// overflow-conscious code
  	if (minCapacity - elementData.length > 0)
  		grow(minCapacity);
  }
  
  private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
  
  /**
   * Increases the capacity to ensure that it can hold at least the
   * number of elements specified by the minimum capacity argument.
   *
   * @param minCapacity the desired minimum capacity
   */
  private void grow(int minCapacity) {
  
  	// overflow-conscious code
  	int oldCapacity = elementData.length;
  	int newCapacity = oldCapacity + (oldCapacity >> 1);
  
  	if (newCapacity - minCapacity < 0)
  		newCapacity = minCapacity;
  
  	if (newCapacity - MAX_ARRAY_SIZE > 0)
  		newCapacity = hugeCapacity(minCapacity);
  
  	Object[] oldData = elementData;
  	elementData = new Object[newCapacity];
  
  	copy(oldData, elementData);
  }
  
  private static int hugeCapacity(int minCapacity) {
  	if (minCapacity < 0) // overflow
  		throw new OutOfMemoryError();
  
  	return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE;
  }
  
  public int size() {
  	return size;
  }
  
  public boolean isEmpty() {
  	return size == 0;
  }
  
  public boolean contains(Object o) {
  	return indexOf(o) >= 0;
  }
  
  public int indexOf(Object o) {
  	if (o == null) {
  		for (int i = 0; i < size; i++)
  			if (elementData[pos(i)] == null)
  				return i;
  	} else {
  		for (int i = 0; i < size; i++)
  			if (o.equals(elementData[pos(i)]))
  				return i;
  	}
  	return -1;
  }
  
  public int lastIndexOf(Object o) {
  	if (o == null) {
  		for (int i = size - 1; i >= 0; i--)
  			if (elementData[pos(i)] == null)
  				return i;
  	} else {
  		for (int i = size - 1; i >= 0; i--)
  			if (o.equals(elementData[pos(i)]))
  				return i;
  	}
  	return -1;
  }
  
  public Object clone() {
  	try {
  		@SuppressWarnings("unchecked")
  			CircularArrayList<E> c = (CircularArrayList<E>) super.clone();
  
  		c.elementData = new Object[size];
  		copy(elementData, c.elementData);
  		c.modCount = 0;
  		return c;
  	} catch (CloneNotSupportedException e) {
  		// this shouldn't happen, since we are Cloneable
  		throw new InternalError();
  	}
  }
  
  public Object[] toArray() {
  	Object[] a = new Object[size];
  
  	System.arraycopy(elementData, elementData.length + tail, a, 0, -tail);
  	System.arraycopy(elementData, 0, a, -tail, head);
  
  	return a;
  }
  
  public <T> T[] toArray(T[] a) {
  	if (a.length < size) {
  		// Make a new array of a's runtime type
  		a = ((Object)a.getClass() == (Object)Object[].class)
  				? (T[]) new Object[size]
  				: (T[]) Array.newInstance(a.getClass().getComponentType(), size);
  
  	}
  
  	System.arraycopy(elementData, elementData.length + tail, a, 0, -tail);
  	System.arraycopy(elementData, 0, a, -tail, head);
  
  	if (a.length > size) {
  		a[size] = null;
  	}
  
  	return a;
  }
  
  private int pos(int index) {
  	return (elementData.length + tail + index) % elementData.length;
  }
  
  public E get(int index) {
  	rangeCheck(index);
  
  	return (E) elementData[pos(index)];
  }
  
  public E set(int index, E element) {
  	rangeCheck(index);
  
  	int pos = pos(index);
  	E oldValue = (E) elementData[pos];
  	elementData[pos] = element;
  	return oldValue;
  }
  
  public boolean add(E e) {
  	ensureCapacityInternal(size + 1); // Increments modCount!!
  	elementData[head] = e;
  	head++;
  	size++;
  	return true;
  }
  
  public void add(int index, E element) {
  	rangeCheckForAdd(index);
  
  	ensureCapacityInternal(size + 1); // Increments modCount!!
  
  	int i = index + tail;
  	if (i <= 0) {
  
  		System.arraycopy(elementData, elementData.length + tail, 
  						 elementData, elementData.length + tail - 1, 
  						 index);
  
  		elementData[elementData.length + i - 1] = element;
  		tail--;
  	} else {
  
  		System.arraycopy(elementData, i, elementData, i + 1, size - index);
  		elementData[i] = element;
  		head++;
  	}
  
  	size++;
  }
  
  public E remove(int index) {
  	rangeCheck(index);
  
  	E value = (E) elementData[pos(index)];
  	fastRemove(index);
  
  	return value;
  }
  
  public boolean remove(Object o) {
  	if (o == null) {
  		for (int index = 0; index < size; index++)
  			if (elementData[pos(index)] == null) {
  				fastRemove(index);
  				return true;
  			}
  	} else {
  		for (int index = 0; index < size; index++)
  			if (o.equals(elementData[pos(index)])) {
  				fastRemove(index);
  				return true;
  			}
  	}
  	return false;
  }
  
  private void fastRemove(int index) {
  	modCount++;
  
  	int i = index + tail;
  	if (i < 0) {
  		int numMoved = index;
  		if (numMoved > 0)
  			System.arraycopy(elementData, elementData.length + tail, 
  							 elementData, elementData.length + tail + 1,
  							 numMoved);
  
  		elementData[elementData.length + tail] = null; // Let gc do its work
  		tail++;
  	} else {
  		int numMoved = size - index - 1;
  		if (numMoved > 0)
  			System.arraycopy(elementData, i + 1, elementData, i, numMoved);
  
  		head--;
  		elementData[head] = null; // Let gc do its work
  	}
  
  	size--;
  }
  
  public void clear() {
  	modCount++;
  
  	// Let gc do its work
  	for (int i = 0; i < size; i++)
  		elementData[pos(i)] = null;
  
  	size = tail = head = 0;
  }
  
  public boolean addAll(Collection<? extends E> c) {
  	Object[] a = c.toArray();
  	int numNew = a.length;
  	ensureCapacityInternal(size + numNew); // Increments modCount
  	System.arraycopy(a, 0, elementData, head, numNew);
  	head += numNew;
  	size += numNew;
  	return numNew != 0;
  }
  
  private void rangeCheck(int index) {
  	if (index >= size || index < 0) {
  		throw new IndexOutOfBoundsException(
  				"Index: " + index + ", Size: " + size);
  	}
  }
  
  private void rangeCheckForAdd(int index) {
  	if (index > size || index < 0)
  		throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
  }
  
  private String outOfBoundsMsg(int index) {
  	return "Index: " + index + ", Size: " + size;
  }
}