// We store the element type as the type of the internal array.

// Disadvantage: Empty lists are a bit bigger.

// Methods will throw ArrayStoreException if trying to add

// element of wrong type.

persistable sclass SynchronizedTypedArrayList<A> extends SynchronizedArrayList_Base<A> implements RandomAccess, Cloneable {

  private static final int DEFAULT_CAPACITY = 10;

  transient Object[] elementData; // non-private to simplify nested class access

  private int size;

  private *() {} // for persistence only - sadly this doesn't actually restrict access since we're an inner class

  *(Class<A> elementType) {

    this(elementType, 0);

  }

  *(Class<A> elementType, int initialCapacity) {

      if (initialCapacity >= 0)

        elementData = newArray(elementType, initialCapacity);

      else

        throw new IllegalArgumentException("Illegal Capacity: "+

          initialCapacity);

  }

  *(Class<A> elementType, Cl<? extends A> c) {

    this(elementType, c.size());

    addAll(c);

  }

  public synchronized void trimToSize() {

      modCount++;

      if (size < elementData.length) {

          elementData = Arrays.copyOf(elementData, size);

      }

  }

  public synchronized void ensureCapacity(int minCapacity) {

      int minExpand = elementData.length != 0

          ? 0

          : DEFAULT_CAPACITY;

      if (minCapacity > minExpand) {

          ensureExplicitCapacity(minCapacity);

      }

  }

  private void ensureCapacityInternal(int minCapacity) {

      if (elementData.length == 0)

        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);

      ensureExplicitCapacity(minCapacity);

  }

  private void ensureExplicitCapacity(int minCapacity) {

      modCount++;

      // overflow-conscious code

      if (minCapacity - elementData.length > 0)

          grow(minCapacity);

  }

  private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

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

      // minCapacity is usually close to size, so this is a win:

      elementData = Arrays.copyOf(elementData, newCapacity);

  }

  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 synchronized int size() {

      return size;

  }

  public synchronized boolean isEmpty() {

      return size == 0;

  }

  public boolean contains(Object o) {

      return indexOf(o) >= 0;

  }

  public synchronized int indexOf(Object o) {

      if (o == null) {

          for (int i = 0; i < size; i++)

              if (elementData[i]==null)

                  return i;

      } else {

          for (int i = 0; i < size; i++)

              if (o.equals(elementData[i]))

                  return i;

      }

      return -1;

  }

  public synchronized int lastIndexOf(Object o) {

      if (o == null) {

          for (int i = size-1; i >= 0; i--)

              if (elementData[i]==null)

                  return i;

      } else {

          for (int i = size-1; i >= 0; i--)

              if (o.equals(elementData[i]))

                  return i;

      }

      return -1;

  }

  public synchronized Object clone() {

    ret new SynchronizedTypedArrayList(elementType(), this);

  }

  public synchronized Object[] toArray() {

      return Arrays.copyOf(elementData, size);

  }

  @SuppressWarnings("unchecked")

  public synchronized  <T> T[] toArray(T[] a) {

      if (a.length < size)

          // Make a new array of a's runtime type, but my contents:

          return (T[]) Arrays.copyOf(elementData, size, a.getClass());

      System.arraycopy(elementData, 0, a, 0, size);

      if (a.length > size)

          a[size] = null;

      return a;

  }

  // Positional Access Operations

  @SuppressWarnings("unchecked")

  A elementData(int index) {

      return (A) elementData[index];

  }

  public synchronized A get(int index) {

      rangeCheck(index);

      return elementData(index);

  }

  public synchronized A set(int index, A element) {

      rangeCheck(index);

      A oldValue = elementData(index);

      elementData[index] = element;

      return oldValue;

  }

  public synchronized boolean add(A e) {

      ensureCapacityInternal(size + 1);  // Increments modCount!!

      elementData[size] = e;

      size++; // Increment only afterwards to make sure store went through

      true;

  }

  public synchronized void add(int index, A element) {

      rangeCheckForAdd(index);

      ensureCapacityInternal(size + 1);  // Increments modCount!!

      System.arraycopy(elementData, index, elementData, index + 1,

                       size - index);

      elementData[index] = element;

      size++;

  }

  public synchronized A remove(int index) {

      rangeCheck(index);

      modCount++;

      A oldValue = elementData(index);

      int numMoved = size - index - 1;

      if (numMoved > 0)

          System.arraycopy(elementData, index+1, elementData, index,

                           numMoved);

      elementData[--size] = null; // clear to let GC do its work

      return oldValue;

  }

  public synchronized boolean remove(Object o) {

      if (o == null) {

          for (int index = 0; index < size; index++)

              if (elementData[index] == null) {

                  fastRemove(index);

                  return true;

              }

      } else {

          for (int index = 0; index < size; index++)

              if (o.equals(elementData[index])) {

                  fastRemove(index);

                  return true;

              }

      }

      return false;

  }

  private void fastRemove(int index) {

      modCount++;

      int numMoved = size - index - 1;

      if (numMoved > 0)

          System.arraycopy(elementData, index+1, elementData, index,

                           numMoved);

      elementData[--size] = null; // clear to let GC do its work

  }

  public synchronized void clear() {

      modCount++;

      // clear to let GC do its work

      for (int i = 0; i < size; i++)

          elementData[i] = null;

      size = 0;

  }

  public synchronized boolean addAll(Collection<? extends A> c) {

      Object[] a = c.toArray();

      int numNew = a.length;

      ensureCapacityInternal(size + numNew);  // Increments modCount

      System.arraycopy(a, 0, elementData, size, numNew);

      size += numNew;

      return numNew != 0;

  }

  public synchronized boolean addAll(int index, Collection<? extends A> c) {

      rangeCheckForAdd(index);

      Object[] a = c.toArray();

      int numNew = a.length;

      ensureCapacityInternal(size + numNew);  // Increments modCount

      int numMoved = size - index;

      if (numMoved > 0)

          System.arraycopy(elementData, index, elementData, index + numNew,

                           numMoved);

      System.arraycopy(a, 0, elementData, index, numNew);

      size += numNew;

      return numNew != 0;

  }

  public synchronized void removeRange(int fromIndex, int toIndex) {

      modCount++;

      int numMoved = size - toIndex;

      System.arraycopy(elementData, toIndex, elementData, fromIndex,

                       numMoved);

      // clear to let GC do its work

      int newSize = size - (toIndex-fromIndex);

      for (int i = newSize; i < size; i++) {

          elementData[i] = null;

      }

      size = newSize;

  }

  private void rangeCheck(int index) {

      if (index >= size)

          throw new IndexOutOfBoundsException(outOfBoundsMsg(index));

  }

  private void rangeCheckForAdd(int index) {

      if (index > size || index < 0)

          throw new IndexOutOfBoundsException(outOfBoundsMsg(index));

  }

  /**

   * Constructs an IndexOutOfBoundsException detail message.

   * Of the many possible refactorings of the error handling code,

   * this "outlining" performs best with both server and client VMs.

   */

  private String outOfBoundsMsg(int index) {

      return "Index: "+index+", Size: "+size;

  }

  public synchronized boolean removeAll(Collection<?> c) {

      Objects.requireNonNull(c);

      return batchRemove(c, false);

  }

  public synchronized boolean retainAll(Collection<?> c) {

      Objects.requireNonNull(c);

      return batchRemove(c, true);

  }

  private boolean batchRemove(Collection<?> c, boolean complement) {

      final Object[] elementData = this.elementData;

      int r = 0, w = 0;

      boolean modified = false;

      try {

          for (; r < size; r++)

              if (c.contains(elementData[r]) == complement)

                  elementData[w++] = elementData[r];

      } finally {

          // Preserve behavioral compatibility with AbstractCollection,

          // even if c.contains() throws.

          if (r != size) {

              System.arraycopy(elementData, r,

                               elementData, w,

                               size - r);

              w += size - r;

          }

          if (w != size) {

              // clear to let GC do its work

              for (int i = w; i < size; i++)

                  elementData[i] = null;

              modCount += size - w;

              size = w;

              modified = true;

          }

      }

      return modified;

  }

  /**

   * Returns a list iterator over the elements in this list (in proper

   * sequence), starting at the specified position in the list.

   * The specified index indicates the first element that would be

   * returned by an initial call to {@link ListIterator#next next}.

   * An initial call to {@link ListIterator#previous previous} would

   * return the element with the specified index minus one.

   *

   * <p>The returned list iterator is <a href="#fail-fast"><i>fail-fast</i></a>.

   *

   * @throws IndexOutOfBoundsException {@inheritDoc}

   */

  public synchronized ListIterator<A> listIterator(int index) {

      if (index < 0 || index > size)

          throw new IndexOutOfBoundsException("Index: "+index);

      return new ListItr(index);

  }

  /**

   * Returns a list iterator over the elements in this list (in proper

   * sequence).

   *

   * <p>The returned list iterator is <a href="#fail-fast"><i>fail-fast</i></a>.

   *

   * @see #listIterator(int)

   */

  public ListIterator<A> listIterator() {

      return new ListItr(0);

  }

  /**

   * Returns an iterator over the elements in this list in proper sequence.

   *

   * <p>The returned iterator is <a href="#fail-fast"><i>fail-fast</i></a>.

   *

   * @return an iterator over the elements in this list in proper sequence

   */

  public Iterator<A> iterator() {

      return concurrentlyIterateList(this);

  }

  /**

   * An optimized version of AbstractList.Itr

   */

  private class Itr implements Iterator<A> {

      int cursor;       // index of next element to return

      int lastRet = -1; // index of last element returned; -1 if no such

      int expectedModCount = modCount;

      public boolean hasNext() {

          return cursor != size;

      }

      @SuppressWarnings("unchecked")

      public A next() {

          checkForComodification();

          int i = cursor;

          if (i >= size)

              throw new NoSuchElementException();

          Object[] elementData = SynchronizedTypedArrayList.this.elementData;

          if (i >= elementData.length)

              throw new ConcurrentModificationException();

          cursor = i + 1;

          return (A) elementData[lastRet = i];

      }

      public void remove() {

          if (lastRet < 0)

              throw new IllegalStateException();

          checkForComodification();

          try {

              SynchronizedTypedArrayList.this.remove(lastRet);

              cursor = lastRet;

              lastRet = -1;

              expectedModCount = modCount;

          } catch (IndexOutOfBoundsException ex) {

              throw new ConcurrentModificationException();

          }

      }

      final void checkForComodification() {

          if (modCount != expectedModCount)

              throw new ConcurrentModificationException();

      }

  }

  /**

   * An optimized version of AbstractList.ListItr - TODO: replace with concurrent iterator or synchronize

   */

  private class ListItr extends Itr implements ListIterator<A> {

      ListItr(int index) {

          super();

          cursor = index;

      }

      public boolean hasPrevious() {

          return cursor != 0;

      }

      public int nextIndex() {

          return cursor;

      }

      public int previousIndex() {

          return cursor - 1;

      }

      @SuppressWarnings("unchecked")

      public A previous() {

          checkForComodification();

          int i = cursor - 1;

          if (i < 0)

              throw new NoSuchElementException();

          Object[] elementData = SynchronizedTypedArrayList.this.elementData;

          if (i >= elementData.length)

              throw new ConcurrentModificationException();

          cursor = i;

          return (A) elementData[lastRet = i];

      }

      public void set(A e) {

          if (lastRet < 0)

              throw new IllegalStateException();

          checkForComodification();

          try {

              SynchronizedTypedArrayList.this.set(lastRet, e);

          } catch (IndexOutOfBoundsException ex) {

              throw new ConcurrentModificationException();

          }

      }

      public void add(A e) {

          checkForComodification();

          try {

              int i = cursor;

              SynchronizedTypedArrayList.this.add(i, e);

              cursor = i + 1;

              lastRet = -1;

              expectedModCount = modCount;

          } catch (IndexOutOfBoundsException ex) {

              throw new ConcurrentModificationException();

          }

      }

  }

  public List<A> subList(int fromIndex, int toIndex) {

      _subListRangeCheck(fromIndex, toIndex, size);

      return new SubList(this, 0, fromIndex, toIndex);

  }

  private class SubList extends SynchronizedArrayList_Base<A> implements RandomAccess {

      private final SynchronizedArrayList_Base<A> parent;

      private final int parentOffset;

      private final int offset;

      int size;

      SubList(SynchronizedArrayList_Base<A> parent,

              int offset, int fromIndex, int toIndex) {

          this.parent = parent;

          this.parentOffset = fromIndex;

          this.offset = offset + fromIndex;

          this.size = toIndex - fromIndex;

          this.modCount = SynchronizedTypedArrayList.this.modCount;

      }

      public A set(int index, A e) { synchronized(SynchronizedTypedArrayList.this) {

          rangeCheck(index);

          checkForComodification();

          A oldValue = SynchronizedTypedArrayList.this.elementData(offset + index);

          SynchronizedTypedArrayList.this.elementData[offset + index] = e;

          return oldValue;

      }}

      public A get(int index) { synchronized(SynchronizedTypedArrayList.this) {

          rangeCheck(index);

          checkForComodification();

          return SynchronizedTypedArrayList.this.elementData(offset + index);

      }}

      public int size() { synchronized(SynchronizedTypedArrayList.this) {

          checkForComodification();

          return this.size;

      }}

      public void add(int index, A e) { synchronized(SynchronizedTypedArrayList.this) {

          rangeCheckForAdd(index);

          checkForComodification();

          parent.add(parentOffset + index, e);

          this.modCount = parent.modCount();

          this.size++;

      }}

      public A remove(int index) { synchronized(SynchronizedTypedArrayList.this) {

          rangeCheck(index);

          checkForComodification();

          A result = parent.remove(parentOffset + index);

          this.modCount = parent.modCount();

          this.size--;

          return result;

      }}

      public void removeRange(int fromIndex, int toIndex) { synchronized(SynchronizedTypedArrayList.this) {

          checkForComodification();

          parent.removeRange(parentOffset + fromIndex,

                             parentOffset + toIndex);

          this.modCount = parent.modCount();

          this.size -= toIndex - fromIndex;

      }}

      public boolean addAll(Collection<? extends A> c) {

          return addAll(this.size, c);

      }

      public boolean addAll(int index, Collection<? extends A> c) { synchronized(SynchronizedTypedArrayList.this) {

          rangeCheckForAdd(index);

          int cSize = c.size();

          if (cSize==0)

              return false;

          checkForComodification();

          parent.addAll(parentOffset + index, c);

          this.modCount = parent.modCount();

          this.size += cSize;

          return true;

      }}

      public Iterator<A> iterator() {

          return listIterator();

      }

      public ListIterator<A> listIterator(final int index) { synchronized(SynchronizedTypedArrayList.this) {

          checkForComodification();

          rangeCheckForAdd(index);

          final int offset = this.offset;

          return new ListIterator<A>() {

              int cursor = index;

              int lastRet = -1;

              int expectedModCount = SynchronizedTypedArrayList.this.modCount;

              public boolean hasNext() {

                  return cursor != SubList.this.size;

              }

              @SuppressWarnings("unchecked")

              public A next() {

                  checkForComodification();

                  int i = cursor;

                  if (i >= SubList.this.size)

                      throw new NoSuchElementException();

                  Object[] elementData = SynchronizedTypedArrayList.this.elementData;

                  if (offset + i >= elementData.length)

                      throw new ConcurrentModificationException();

                  cursor = i + 1;

                  return (A) elementData[offset + (lastRet = i)];

              }

              public boolean hasPrevious() {

                  return cursor != 0;

              }

              @SuppressWarnings("unchecked")

              public A previous() {

                  checkForComodification();

                  int i = cursor - 1;

                  if (i < 0)

                      throw new NoSuchElementException();

                  Object[] elementData = SynchronizedTypedArrayList.this.elementData;

                  if (offset + i >= elementData.length)

                      throw new ConcurrentModificationException();

                  cursor = i;

                  return (A) elementData[offset + (lastRet = i)];

              }

              public int nextIndex() {

                  return cursor;

              }

              public int previousIndex() {

                  return cursor - 1;

              }

              public void remove() {

                  if (lastRet < 0)

                      throw new IllegalStateException();

                  checkForComodification();

                  try {

                      SubList.this.remove(lastRet);

                      cursor = lastRet;

                      lastRet = -1;

                      expectedModCount = SynchronizedTypedArrayList.this.modCount;

                  } catch (IndexOutOfBoundsException ex) {

                      throw new ConcurrentModificationException();

                  }

              }

              public void set(A e) {

                  if (lastRet < 0)

                      throw new IllegalStateException();

                  checkForComodification();

                  try {

                      SynchronizedTypedArrayList.this.set(offset + lastRet, e);

                  } catch (IndexOutOfBoundsException ex) {

                      throw new ConcurrentModificationException();

                  }

              }

              public void add(A e) {

                  checkForComodification();

                  try {

                      int i = cursor;

                      SubList.this.add(i, e);

                      cursor = i + 1;

                      lastRet = -1;

                      expectedModCount = SynchronizedTypedArrayList.this.modCount;

                  } catch (IndexOutOfBoundsException ex) {

                      throw new ConcurrentModificationException();

                  }

              }

              final void checkForComodification() {

                  if (expectedModCount != SynchronizedTypedArrayList.this.modCount)

                      throw new ConcurrentModificationException();

              }

          };

      }}

      public List<A> subList(int fromIndex, int toIndex) { synchronized(SynchronizedTypedArrayList.this) {

          _subListRangeCheck(fromIndex, toIndex, size);

          return new SubList(parent, offset, fromIndex, toIndex);

      }}

      private void rangeCheck(int index) {

          if (index < 0 || index >= this.size)

              throw new IndexOutOfBoundsException(outOfBoundsMsg(index));

      }

      private void rangeCheckForAdd(int index) {

          if (index < 0 || index > this.size)

              throw new IndexOutOfBoundsException(outOfBoundsMsg(index));

      }

      private String outOfBoundsMsg(int index) {

          return "Index: "+index+", Size: "+this.size;

      }

      private void checkForComodification() {

          if (SynchronizedTypedArrayList.this.modCount != this.modCount)

              throw new ConcurrentModificationException();

      }

  }

  @Override

  @SuppressWarnings("unchecked")

  public synchronized void sort(Comparator<? super A> c) {

      final int expectedModCount = modCount;

      Arrays.sort((A[]) elementData, 0, size, c);

      if (modCount != expectedModCount) {

          throw new ConcurrentModificationException();

      }

      modCount++;

  }

  Class<? extends A> elementType() {

    ret arrayElementType(elementData);

  }

}