Collections Data Structure Java

 * This is ordinarily too costly, but it becomes attractive when traversal
 * operations vastly overwhelm mutations, and, especially, when you cannot or
 * don't want to synchronize traversals, yet need to preclude interference among
 * concurrent threads. The iterator method uses a reference to the state of the
 * array at the point that the iterator was created. This array never changes
 * during the lifetime of the iterator, so interference is impossible. (The
 * iterator will not traverse elements added or changed since the iterator was
 * created, but usually this is a desirable feature.)
 * 

 * As much code and documentation as possible was shamelessly copied from
 * java.util.ArrayList (Thanks, Josh!), with the intent of preserving all
 * semantics of ArrayList except for the copy-on-write property. (The java.util
 * collection code could not be subclassed here since all of the existing
 * collection classes assume elementwise mutability.)
 * 

 * Because of the copy-on-write policy, some one-by-one mutative operations in
 * the java.util.Arrays and java.util.Collections classes are so time/space
 * intensive as to never be worth calling (except perhaps as benchmarks for
 * garbage collectors :-).
 * 

 * Three methods are supported in addition to those described in List and
 * ArrayList. The addIfAbsent and addAllAbsent methods provide Set semantics for
 * add, and are used in CopyOnWriteArraySet. However, they can also be used
 * directly from this List version. The copyIn method (and a constructor that
 * invokes it) allow you to copy in an initial array to use. This method can be
 * useful when you first want to perform many operations on a plain array, and
 * then make a copy available for use through the collection API.
 * 

 * Due to their strict read-only nature, element-changing operations on
 * iterators (remove, set, and add) are not supported. These are the only
 * methods throwing UnsupportedOperationException.
 * 

 * 

[ * href="http://gee.cs.oswego.edu/dl/classes/EDU/oswego/cs/dl/util/concurrent/intro.html">
 * Introduction to this package. ]
 * 
 * @see CopyOnWriteArraySet
 */
public class CopyOnWriteArrayList implements List, Cloneable, java.io.Serializable
{
  private static final long serialVersionUID = 1L;
  /**
   * The held array. Directly access only within synchronized methods
   */
  protected transient Object[] array_;
  /**
   * Accessor to the array intended to be called from within unsynchronized
   * read-only methods
   * 
   * @return The internal array
   */
  protected synchronized Object[] array()
  {
    return array_;
  }
  /**
   * Constructs an empty list
   * 
   */
  public CopyOnWriteArrayList()
  {
    array_ = new Object[0];
  }
  /**
   * Constructs an list containing the elements of the specified Collection,
   * in the order they are returned by the Collection's iterator.
   * 
   * @param c The collection to get the objects from. 
   */
  public CopyOnWriteArrayList(Collection c)
  {
    array_ = new Object[c.size()];
    Iterator i = c.iterator();
    int size = 0;
    while (i.hasNext())
      array_[size++] = i.next();
  }
  /**
   * Create a new CopyOnWriteArrayList holding a copy of given array
   * 
   * @param toCopyIn
   *            the array. A copy of this array is used as the internal array.
   */
  public CopyOnWriteArrayList(Object[] toCopyIn)
  {
    copyIn(toCopyIn, 0, toCopyIn.length);
  }
  /**
   * Replace the held array with a copy of the n elements of
   * the provided array, starting at position first. To copy
   * an entire array, call with arguments (array, 0, array.length).
   * 
   * @param toCopyIn
   *            the array. A copy of the indicated elements of this array is
   *            used as the internal array.
   * @param first
   *            The index of first position of the array to start copying
   *            from.
   * @param n
   *            the number of elements to copy. This will be the new size of
   *            the list.
   */
  public synchronized void copyIn(Object[] toCopyIn, int first, int n)
  {
    array_ = new Object[n];
    System.arraycopy(toCopyIn, first, array_, 0, n);
  }
  /**
   * Returns the number of components in this list.
   * 
   * @return the number of components in this list.
   */
  public int size()
  {
    return array().length;
  }
  /**
   * Tests if this list has no components.
   * 
   * @return true if this list has no components;
   *         false otherwise.
   */
  public boolean isEmpty()
  {
    return size() == 0;
  }
  /**
   * Returns true if this list contains the specified element.
   * 
   * @param o
   *            element whose presence in this List is to be tested.
   */
  public boolean contains(Object elem)
  {
    Object[] elementData = array();
    int len = elementData.length;
    return indexOf(elem, elementData, len) >= 0;
  }
  /**
   * Searches for the first occurence of the given argument, testing for
   * equality using the equals method.
   * 
   * @param elem
   *            an object.
   * @return the index of the first occurrence of the argument in this list;
   *         returns -1 if the object is not found.
   * @see Object#equals(Object)
   */
  public int indexOf(Object elem)
  {
    Object[] elementData = array();
    int len = elementData.length;
    return indexOf(elem, elementData, len);
  }
  /**
   * static version allows repeated call without needed to grab lock for array
   * each time
   * @param elem 
   * @param elementData 
   * @param len 
   * @return The index that is found. -1 if not found
   */
  protected static int indexOf(Object elem, Object[] elementData, int len)
  {
    if (elem == null)
    {
      for (int i = 0; i < len; i++)
        if (elementData[i] == null)
          return i;
    }
    else
    {
      for (int i = 0; i < len; i++)
        if (elem.equals(elementData[i]))
          return i;
    }
    return -1;
  }
  /**
   * Searches for the first occurence of the given argument, beginning the
   * search at index, and testing for equality using the
   * equals method.
   * 
   * @param elem
   *            an object.
   * @param index
   *            the index to start searching from.
   * @return the index of the first occurrence of the object argument in this
   *         List at position index or later in the List;
   *         returns -1 if the object is not found.
   * @see Object#equals(Object)
   */
  // needed in order to compile on 1.2b3
  public int indexOf(Object elem, int index)
  {
    Object[] elementData = array();
    int elementCount = elementData.length;
    if (elem == null)
    {
      for (int i = index; i < elementCount; i++)
        if (elementData[i] == null)
          return i;
    }
    else
    {
      for (int i = index; i < elementCount; i++)
        if (elem.equals(elementData[i]))
          return i;
    }
    return -1;
  }
  /**
   * Returns the index of the last occurrence of the specified object in this
   * list.
   * 
   * @param elem
   *            the desired component.
   * @return the index of the last occurrence of the specified object in this
   *         list; returns -1 if the object is not found.
   */
  public int lastIndexOf(Object elem)
  {
    Object[] elementData = array();
    int len = elementData.length;
    return lastIndexOf(elem, elementData, len);
  }
  protected static int lastIndexOf(Object elem, Object[] elementData, int len)
  {
    if (elem == null)
    {
      for (int i = len - 1; i >= 0; i--)
        if (elementData[i] == null)
          return i;
    }
    else
    {
      for (int i = len - 1; i >= 0; i--)
        if (elem.equals(elementData[i]))
          return i;
    }
    return -1;
  }
  /**
   * Searches backwards for the specified object, starting from the specified
   * index, and returns an index to it.
   * 
   * @param elem
   *            the desired component.
   * @param index
   *            the index to start searching from.
   * @return the index of the last occurrence of the specified object in this
   *         List at position less than index in the List; -1 if the object is
   *         not found.
   */
  public int lastIndexOf(Object elem, int index)
  {
    // needed in order to compile on 1.2b3
    Object[] elementData = array();
    if (elem == null)
    {
      for (int i = index; i >= 0; i--)
        if (elementData[i] == null)
          return i;
    }
    else
    {
      for (int i = index; i >= 0; i--)
        if (elem.equals(elementData[i]))
          return i;
    }
    return -1;
  }
  /**
   * Returns a shallow copy of this list. (The elements themselves are not
   * copied.)
   * 
   * @return a clone of this list.
   */
  public Object clone()
  {
    try
    {
      Object[] elementData = array();
      CopyOnWriteArrayList v = (CopyOnWriteArrayList)super.clone();
      v.array_ = new Object[elementData.length];
      System.arraycopy(elementData, 0, v.array_, 0, elementData.length);
      return v;
    }
    catch (CloneNotSupportedException e)
    {
      // this shouldn't happen, since we are Cloneable
      throw new InternalError();
    }
  }
  /**
   * Returns an array containing all of the elements in this list in the
   * correct order.
   */
  public Object[] toArray()
  {
    Object[] elementData = array();
    Object[] result = new Object[elementData.length];
    System.arraycopy(elementData, 0, result, 0, elementData.length);
    return result;
  }
  /**
   * Returns an array containing all of the elements in this list in the
   * correct order. The runtime type of the returned array is that of the
   * specified array. If the list fits in the specified array, it is returned
   * therein. Otherwise, a new array is allocated with the runtime type of the
   * specified array and the size of this list.
   * 

   * If the list fits in the specified array with room to spare (i.e., the
   * array has more elements than the list), the element in the array
   * immediately following the end of the collection is set to null. This is
   * useful in determining the length of the list only if the
   * caller knows that the list does not contain any null elements.
   * 
   * @param a
   *            the array into which the elements of the list are to be
   *            stored, if it is big enough; otherwise, a new array of the
   *            same runtime type is allocated for this purpose.
   * @return an array containing the elements of the list.
   * @exception ArrayStoreException
   *                the runtime type of a is not a supertype of the runtime
   *                type of every element in this list.
   */
  public Object[] toArray(Object a[])
  {
    Object[] elementData = array();
    if (a.length < elementData.length)
      a = (Object[])java.lang.reflect.Array.newInstance(a.getClass().getComponentType(),
          elementData.length);
    System.arraycopy(elementData, 0, a, 0, elementData.length);
    if (a.length > elementData.length)
      a[elementData.length] = null;
    return a;
  }
  // Positional Access Operations
  /**
   * Returns the element at the specified position in this list.
   * 
   * @param index
   *            index of element to return.
   * @exception IndexOutOfBoundsException
   *                index is out of range (index < 0 || index >=
   *                size()).
   */
  public Object get(int index)
  {
    Object[] elementData = array();
    rangeCheck(index, elementData.length);
    return elementData[index];
  }
  /**
   * Replaces the element at the specified position in this list with the
   * specified element.
   * 
   * @param index
   *            index of element to replace.
   * @param element
   *            element to be stored at the specified position.
   * @return the element previously at the specified position.
   * @exception IndexOutOfBoundsException
   *                index out of range (index < 0 || index >= size()).
   */
  public synchronized Object set(int index, Object element)
  {
    int len = array_.length;
    rangeCheck(index, len);
    Object oldValue = array_[index];
    boolean same = (oldValue == element || (element != null && element.equals(oldValue)));
    if (!same)
    {
      Object[] newArray = new Object[len];
      System.arraycopy(array_, 0, newArray, 0, len);
      newArray[index] = element;
      array_ = newArray;
    }
    return oldValue;
  }
  /**
   * Appends the specified element to the end of this list.
   * 
   * @param element
   *            element to be appended to this list.
   * @return true (as per the general contract of Collection.add).
   */
  public synchronized boolean add(Object element)
  {
    int len = array_.length;
    Object[] newArray = new Object[len + 1];
    System.arraycopy(array_, 0, newArray, 0, len);
    newArray[len] = element;
    array_ = newArray;
    return true;
  }
  /**
   * Inserts the specified element at the specified position in this list.
   * Shifts the element currently at that position (if any) and any subsequent
   * elements to the right (adds one to their indices).
   * 
   * @param index
   *            index at which the specified element is to be inserted.
   * @param element
   *            element to be inserted.
   * @exception IndexOutOfBoundsException
   *                index is out of range (index < 0 || index > size()).
   */
  public synchronized void add(int index, Object element)
  {
    int len = array_.length;
    if (index > len || index < 0)
      throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + len);
    Object[] newArray = new Object[len + 1];
    System.arraycopy(array_, 0, newArray, 0, index);
    newArray[index] = element;
    System.arraycopy(array_, index, newArray, index + 1, len - index);
    array_ = newArray;
  }
  /**
   * Removes the element at the specified position in this list. Shifts any
   * subsequent elements to the left (subtracts one from their indices).
   * Returns the element that was removed from the list.
   * 
   * @param index
   *            the index of the element to removed.
   * @exception IndexOutOfBoundsException
   *                index out of range (index < 0 || index >= size()).
   */
  public synchronized Object remove(int index)
  {
    int len = array_.length;
    rangeCheck(index, len);
    Object oldValue = array_[index];
    Object[] newArray = new Object[len - 1];
    System.arraycopy(array_, 0, newArray, 0, index);
    int numMoved = len - index - 1;
    if (numMoved > 0)
      System.arraycopy(array_, index + 1, newArray, index, numMoved);
    array_ = newArray;
    return oldValue;
  }
  /**
   * Removes a single instance of the specified element from this Collection,
   * if it is present (optional operation). More formally, removes an element
   * e such that (o==null ? e==null :
   * o.equals(e)),
   * if the Collection contains one or more such elements. Returns true if the
   * Collection contained the specified element (or equivalently, if the
   * Collection changed as a result of the call).
   * 
   * @param element
   *            element to be removed from this Collection, if present.
   * @return true if the Collection changed as a result of the call.
   */
  public synchronized boolean remove(Object element)
  {
    int len = array_.length;
    if (len == 0)
      return false;
    // Copy while searching for element to remove
    // This wins in the normal case of element being present
    int newlen = len - 1;
    Object[] newArray = new Object[newlen];
    for (int i = 0; i < newlen; ++i)
    {
      if (element == array_[i] || (element != null && element.equals(array_[i])))
      {
        // found one; copy remaining and exit
        for (int k = i + 1; k < len; ++k)
          newArray[k - 1] = array_[k];
        array_ = newArray;
        return true;
      }
      else
        newArray[i] = array_[i];
    }
    // special handling for last cell
    if (element == array_[newlen] || (element != null && element.equals(array_[newlen])))
    {
      array_ = newArray;
      return true;
    }
    else
      return false; // throw away copy
  }
  /**
   * Removes from this List all of the elements whose index is between
   * fromIndex, inclusive and toIndex, exclusive. Shifts any succeeding
   * elements to the left (reduces their index). This call shortens the List
   * by (toIndex - fromIndex) elements. (If toIndex==fromIndex, this operation
   * has no effect.)
   * 
   * @param fromIndex
   *            index of first element to be removed.
   * @param toIndex
   *            index after last element to be removed.
   * @exception IndexOutOfBoundsException
   *                fromIndex or toIndex out of range (fromIndex < 0 ||
   *                fromIndex >= size() || toIndex > size() || toIndex
   *                < fromIndex).
   */
  public synchronized void removeRange(int fromIndex, int toIndex)
  {
    int len = array_.length;
    if (fromIndex < 0 || fromIndex >= len || toIndex > len || toIndex < fromIndex)
      throw new IndexOutOfBoundsException();
    int numMoved = len - toIndex;
    int newlen = len - (toIndex - fromIndex);
    Object[] newArray = new Object[newlen];
    System.arraycopy(array_, 0, newArray, 0, fromIndex);
    System.arraycopy(array_, toIndex, newArray, fromIndex, numMoved);
    array_ = newArray;
  }
  /**
   * Append the element if not present. This operation can be used to obtain
   * Set semantics for lists.
   * 
   * @param element
   *            element to be added to this Collection, if absent.
   * @return true if added
   */
  public synchronized boolean addIfAbsent(Object element)
  {
    // Copy while checking if already present.
    // This wins in the most common case where it is not present
    int len = array_.length;
    Object[] newArray = new Object[len + 1];
    for (int i = 0; i < len; ++i)
    {
      if (element == array_[i] || (element != null && element.equals(array_[i])))
        return false; // exit, throwing away copy
      else
        newArray[i] = array_[i];
    }
    newArray[len] = element;
    array_ = newArray;
    return true;
  }
  /**
   * Returns true if this Collection contains all of the elements in the
   * specified Collection.
   * 

   * This implementation iterates over the specified Collection, checking each
   * element returned by the Iterator in turn to see if it's contained in this
   * Collection. If all elements are so contained true is returned, otherwise
   * false.
   * 
   */
  public boolean containsAll(Collection c)
  {
    Object[] elementData = array();
    int len = elementData.length;
    Iterator e = c.iterator();
    while (e.hasNext())
      if (indexOf(e.next(), elementData, len) < 0)
        return false;
    return true;
  }
  /**
   * Removes from this Collection all of its elements that are contained in
   * the specified Collection. This is a particularly expensive operation in
   * this class because of the need for an internal temporary array.
   * 

   * 
   * @return true if this Collection changed as a result of the call.
   */
  public synchronized boolean removeAll(Collection c)
  {
    Object[] elementData = array_;
    int len = elementData.length;
    if (len == 0)
      return false;
    // temp array holds those elements we know we want to keep
    Object[] temp = new Object[len];
    int newlen = 0;
    for (int i = 0; i < len; ++i)
    {
      Object element = elementData[i];
      if (!c.contains(element))
      {
        temp[newlen++] = element;
      }
    }
    if (newlen == len)
      return false;
    // copy temp as new array
    Object[] newArray = new Object[newlen];
    System.arraycopy(temp, 0, newArray, 0, newlen);
    array_ = newArray;
    return true;
  }
  /**
   * Retains only the elements in this Collection that are contained in the
   * specified Collection (optional operation). In other words, removes from
   * this Collection all of its elements that are not contained in the
   * specified Collection.
   * 
   * @return true if this Collection changed as a result of the call.
   */
  public synchronized boolean retainAll(Collection c)
  {
    Object[] elementData = array_;
    int len = elementData.length;
    if (len == 0)
      return false;
    Object[] temp = new Object[len];
    int newlen = 0;
    for (int i = 0; i < len; ++i)
    {
      Object element = elementData[i];
      if (c.contains(element))
      {
        temp[newlen++] = element;
      }
    }
    if (newlen == len)
      return false;
    Object[] newArray = new Object[newlen];
    System.arraycopy(temp, 0, newArray, 0, newlen);
    array_ = newArray;
    return true;
  }
  /**
   * Appends all of the elements in the specified Collection that are not
   * already contained in this list, to the end of this list, in the order
   * that they are returned by the specified Collection's Iterator.
   * 
   * @param c
   *            elements to be added into this list.
   * @return the number of elements added
   */
  public synchronized int addAllAbsent(Collection c)
  {
    int numNew = c.size();
    if (numNew == 0)
      return 0;
    Object[] elementData = array_;
    int len = elementData.length;
    Object[] temp = new Object[numNew];
    int added = 0;
    Iterator e = c.iterator();
    while (e.hasNext())
    {
      Object element = e.next();
      if (indexOf(element, elementData, len) < 0)
      {
        if (indexOf(element, temp, added) < 0)
        {
          temp[added++] = element;
        }
      }
    }
    if (added == 0)
      return 0;
    Object[] newArray = new Object[len + added];
    System.arraycopy(elementData, 0, newArray, 0, len);
    System.arraycopy(temp, 0, newArray, len, added);
    array_ = newArray;
    return added;
  }
  /**
   * Removes all of the elements from this list.
   * 
   */
  public synchronized void clear()
  {
    array_ = new Object[0];
  }
  /**
   * Appends all of the elements in the specified Collection to the end of
   * this list, in the order that they are returned by the specified
   * Collection's Iterator.
   * 
   * @param c
   *            elements to be inserted into this list.
   */
  public synchronized boolean addAll(Collection c)
  {
    int numNew = c.size();
    if (numNew == 0)
      return false;
    int len = array_.length;
    Object[] newArray = new Object[len + numNew];
    System.arraycopy(array_, 0, newArray, 0, len);
    Iterator e = c.iterator();
    for (int i = 0; i < numNew; i++)
      newArray[len++] = e.next();
    array_ = newArray;
    return true;
  }
  /**
   * Inserts all of the elements in the specified Collection into this list,
   * starting at the specified position. Shifts the element currently at that
   * position (if any) and any subsequent elements to the right (increases
   * their indices). The new elements will appear in the list in the order
   * that they are returned by the specified Collection's iterator.
   * 
   * @param index
   *            index at which to insert first element from the specified
   *            collection.
   * @param c
   *            elements to be inserted into this list.
   * @exception IndexOutOfBoundsException
   *                index out of range (index < 0 || index > size()).
   */
  public synchronized boolean addAll(int index, Collection c)
  {
    int len = array_.length;
    if (index > len || index < 0)
      throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + len);
    int numNew = c.size();
    if (numNew == 0)
      return false;
    Object[] newArray = new Object[len + numNew];
    System.arraycopy(array_, 0, newArray, 0, len);
    int numMoved = len - index;
    if (numMoved > 0)
      System.arraycopy(array_, index, newArray, index + numNew, numMoved);
    Iterator e = c.iterator();
    for (int i = 0; i < numNew; i++)
      newArray[index++] = e.next();
    array_ = newArray;
    return true;
  }
  /**
   * Check if the given index is in range. If not, throw an appropriate
   * runtime exception.
   * @param index 
   * @param length 
   */
  protected void rangeCheck(int index, int length)
  {
    if (index >= length || index < 0)
      throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + length);
  }
  /**
   * Save the state of the list to a stream (i.e., serialize it).
   * @param s 
   * @throws java.io.IOException 
   * 
   * @serialData The length of the array backing the list is emitted (int),
   *             followed by all of its elements (each an Object) in the
   *             proper order.
   */
  private void writeObject(java.io.ObjectOutputStream s) throws java.io.IOException
  {
    // Write out element count, and any hidden stuff
    s.defaultWriteObject();
    Object[] elementData = array();
    // Write out array length
    s.writeInt(elementData.length);
    // Write out all elements in the proper order.
    for (int i = 0; i < elementData.length; i++)
      s.writeObject(elementData[i]);
  }
  /**
   * Reconstitute the list from a stream (i.e., deserialize it).
   * @param s 
   * @throws java.io.IOException 
   * @throws ClassNotFoundException 
   */
  private synchronized void readObject(java.io.ObjectInputStream s) throws java.io.IOException,
      ClassNotFoundException
  {
    // Read in size, and any hidden stuff
    s.defaultReadObject();
    // Read in array length and allocate array
    int arrayLength = s.readInt();
    Object[] elementData = new Object[arrayLength];
    // Read in all elements in the proper order.
    for (int i = 0; i < elementData.length; i++)
      elementData[i] = s.readObject();
    array_ = elementData;
  }
  /**
   * Returns a string representation of this Collection, containing the String
   * representation of each element.
   */
  public String toString()
  {
    StringBuffer buf = new StringBuffer();
    Iterator e = iterator();
    buf.append("[");
    int maxIndex = size() - 1;
    for (int i = 0; i <= maxIndex; i++)
    {
      buf.append(String.valueOf(e.next()));
      if (i < maxIndex)
        buf.append(", ");
    }
    buf.append("]");
    return buf.toString();
  }
  /**
   * Compares the specified Object with this List for equality. Returns true
   * if and only if the specified Object is also a List, both Lists have the
   * same size, and all corresponding pairs of elements in the two Lists are
   * equal. (Two elements e1 and e2
   * are equal if
   * (e1==null ? e2==null : e1.equals(e2)).) In other words,
   * two Lists are defined to be equal if they contain the same elements in
   * the same order.
   * 

   * This implementation first checks if the specified object is this List. If
   * so, it returns true; if not, it checks if the specified object is a List.
   * If not, it returns false; if so, it iterates over both lists, comparing
   * corresponding pairs of elements. If any comparison returns false, this
   * method returns false. If either Iterator runs out of elements before
   * before the other it returns false (as the Lists are of unequal length);
   * otherwise it returns true when the iterations complete.
   * 
   * @param o
   *            the Object to be compared for equality with this List.
   * @return true if the specified Object is equal to this List.
   */
  public boolean equals(Object o)
  {
    if (o == this)
      return true;
    if (!(o instanceof List))
      return false;
    List l2 = (List)(o);
    if (size() != l2.size())
      return false;
    ListIterator e1 = listIterator();
    ListIterator e2 = l2.listIterator();
    while (e1.hasNext())
    {
      Object o1 = e1.next();
      Object o2 = e2.next();
      if (!(o1 == null ? o2 == null : o1.equals(o2)))
        return false;
    }
    return true;
  }
  /**
   * Returns the hash code value for this List.
   * 

   * This implementation uses exactly the code that is used to define the List
   * hash function in the documentation for List.hashCode.
   */
  public int hashCode()
  {
    int hashCode = 1;
    Iterator i = iterator();
    while (i.hasNext())
    {
      Object obj = i.next();
      hashCode = 31 * hashCode + (obj == null ? 0 : obj.hashCode());
    }
    return hashCode;
  }
  /**
   * Returns an Iterator over the elements contained in this collection. The
   * iterator provides a snapshot of the state of the list when the iterator
   * was constructed. No synchronization is needed while traversing the
   * iterator. The iterator does NOT support the
   * remove method.
   */
  public Iterator iterator()
  {
    return new COWIterator(array(), 0);
  }
  /**
   * Returns an Iterator of the elements in this List (in proper sequence).
   * The iterator provides a snapshot of the state of the list when the
   * iterator was constructed. No synchronization is needed while traversing
   * the iterator. The iterator does NOT support the
   * remove, set, or add
   * methods.
   * 
   */
  public ListIterator listIterator()
  {
    return new COWIterator(array(), 0);
  }
  /**
   * Returns a ListIterator of 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
   * nextElement. An initial call to previousElement would return the element
   * with the specified index minus one. The ListIterator returned by this
   * implementation will throw an UnsupportedOperationException in its remove,
   * set and add methods.
   * 
   * @param index
   *            index of first element to be returned from the ListIterator
   *            (by a call to getNext).
   * @exception IndexOutOfBoundsException
   *                index is out of range (index < 0 || index > size()).
   */
  public ListIterator listIterator(final int index)
  {
    Object[] elementData = array();
    int len = elementData.length;
    if (index < 0 || index > len)
      throw new IndexOutOfBoundsException("Index: " + index);
    return new COWIterator(array(), index);
  }
  protected static class COWIterator implements ListIterator
  {
    /** Snapshot of the array * */
    protected final Object[] array;
    /**
     * Index of element to be returned by subsequent call to next.
     */
    protected int cursor;
    protected COWIterator(Object[] elementArray, int initialCursor)
    {
      array = elementArray;
      cursor = initialCursor;
    }
    public boolean hasNext()
    {
      return cursor < array.length;
    }
    public boolean hasPrevious()
    {
      return cursor > 0;
    }
    public Object next()
    {
      try
      {
        return array[cursor++];
      }
      catch (IndexOutOfBoundsException ex)
      {
        throw new NoSuchElementException();
      }
    }
    public Object previous()
    {
      try
      {
        return array[--cursor];
      }
      catch (IndexOutOfBoundsException e)
      {
        throw new NoSuchElementException();
      }
    }
    public int nextIndex()
    {
      return cursor;
    }
    public int previousIndex()
    {
      return cursor - 1;
    }
    /**
     * Not supported. Always throws UnsupportedOperationException.
     * 
     * @exception UnsupportedOperationException
     *                remove is not supported by this Iterator.
     */
    public void remove()
    {
      throw new UnsupportedOperationException();
    }
    /**
     * Not supported. Always throws UnsupportedOperationException.
     * 
     * @exception UnsupportedOperationException
     *                set is not supported by this Iterator.
     */
    public void set(Object o)
    {
      throw new UnsupportedOperationException();
    }
    /**
     * Not supported. Always throws UnsupportedOperationException.
     * 
     * @exception UnsupportedOperationException
     *                add is not supported by this Iterator.
     */
    public void add(Object o)
    {
      throw new UnsupportedOperationException();
    }
  }
  /**
   * Returns a view of the portion of this List between fromIndex, inclusive,
   * and toIndex, exclusive. The returned List is backed by this List, so
   * changes in the returned List are reflected in this List, and vice-versa.
   * While mutative operations are supported, they are probably not very
   * useful for CopyOnWriteArrays.
   *