Collections Data Structure Java

 This is ordinarily too costly, but may be more efficient
 * than alternatives when traversal operations vastly outnumber
 * mutations, and is useful when you cannot or don't want to
 * synchronize traversals, yet need to preclude interference among
 * concurrent threads.  The "snapshot" style 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 and the iterator is
 * guaranteed not to throw ConcurrentModificationException.
 * The iterator will not reflect additions, removals, or changes to
 * the list since the iterator was created.  Element-changing
 * operations on iterators themselves (remove, set, and
 * add) are not supported. These methods throw
 * UnsupportedOperationException.
 *
 * 

All elements are permitted, including null.
 *
 * 

This class is a member of the
 * 
 * Java Collections Framework.
 *
 * @since 1.5
 * @author Doug Lea
 */
public class CopyOnWriteArrayList
    implements List, RandomAccess, Cloneable, java.io.Serializable {
    private static final long serialVersionUID = 8673264195747942595L;
    /** The array, accessed only via getArray/setArray. */
    private volatile transient Object[] array;
    /**
     * This has been made public to support more efficient iteration.
     * DO NOT MODIFY this array upon getting it.
     * Otherwise you risk wreaking havoc on your list. In fact, if you are
     * not the author of this comment, you probably shouldn't use it at all.
     * @return this lists internal array
     */
    public Object[]  getArray()    { return array; }
    
    void      setArray(Object[] a) { array = a; }
    /**
     * Creates an empty list.
     */
    public CopyOnWriteArrayList() {
        setArray(new Object[0]);
    }
    /**
     * Creates a list containing the elements of the specified
     * collection, in the order they are returned by the collection's
     * iterator.
     *
     * @param c the collection of initially held elements
     * @throws NullPointerException if the specified collection is null
     */
    public CopyOnWriteArrayList(Collection c) {
        Object[] elements = new Object[c.size()];
        int size = 0;
        for (Iterator itr = c.iterator(); itr.hasNext(); ) {
            Object e = itr.next();
            elements[size++] = e;
        }
        setArray(elements);
    }
    /**
     * Creates a list holding a copy of the given array.
     *
     * @param toCopyIn the array (a copy of this array is used as the
     *        internal array)
     * @throws NullPointerException if the specified array is null
     */
    public CopyOnWriteArrayList(Object[] toCopyIn) {
        copyIn(toCopyIn, 0, toCopyIn.length);
    }
    /**
     * Replaces 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.
     */
    private void copyIn(Object[] toCopyIn, int first, int n) {
        int limit = first + n;
        if (limit > toCopyIn.length)
            throw new IndexOutOfBoundsException();
        Object[] newElements = copyOfRange(toCopyIn, first, limit,
                                          Object[].class);
        synchronized (this) { setArray(newElements); }
    }
    /**
     * Returns the number of elements in this list.
     *
     * @return the number of elements in this list
     */
    public int size() {
        return getArray().length;
    }
    /**
     * Returns true if this list contains no elements.
     *
     * @return true if this list contains no elements
     */
    public boolean isEmpty() {
        return size() == 0;
    }
    /**
     * Test for equality, coping with nulls.
     */
    private static boolean eq(Object o1, Object o2) {
        return (o1 == null ? o2 == null : o1.equals(o2));
    }
    /**
     * static version of indexOf, to allow repeated calls without
     * needing to re-acquire array each time.
     * @param o element to search for
     * @param elements the array
     * @param index first index to search
     * @param fence one past last index to search
     * @return index of element, or -1 if absent
     */
    private static int indexOf(Object o, Object[] elements,
                               int index, int fence) {
        if (o == null) {
            for (int i = index; i < fence; i++)
                if (elements[i] == null)
                    return i;
        } else {
            for (int i = index; i < fence; i++)
                if (o.equals(elements[i]))
                    return i;
        }
        return -1;
    }
    /**
     * static version of lastIndexOf.
     * @param o element to search for
     * @param elements the array
     * @param index first index to search
     * @return index of element, or -1 if absent
     */
    private static int lastIndexOf(Object o, Object[] elements, int index) {
        if (o == null) {
            for (int i = index; i >= 0; i--)
                if (elements[i] == null)
                    return i;
        } else {
            for (int i = index; i >= 0; i--)
                if (o.equals(elements[i]))
                    return i;
        }
        return -1;
    }
    /**
     * Returns true if this list contains the specified element.
     * More formally, returns true if and only if this list contains
     * at least one element e such that
     * (o==null ? e==null : o.equals(e)).
     *
     * @param o element whose presence in this list is to be tested
     * @return true if this list contains the specified element
     */
    public boolean contains(Object o) {
        Object[] elements = getArray();
        return indexOf(o, elements, 0, elements.length) >= 0;
    }
    /**
     * {@inheritDoc}
     */
    public int indexOf(Object o) {
        Object[] elements = getArray();
        return indexOf(o, elements, 0, elements.length);
    }
    /**
     * Returns the index of the first occurrence of the specified element in
     * this list, searching forwards from index, or returns -1 if
     * the element is not found.
     * More formally, returns the lowest index i such that
     * (i >= index && (e==null ? get(i)==null : e.equals(get(i)))),
     * or -1 if there is no such index.
     *
     * @param e element to search for
     * @param index index to start searching from
     * @return the index of the first occurrence of the element in
     *         this list at position index or later in the list;
     *         -1 if the element is not found.
     * @throws IndexOutOfBoundsException if the specified index is negative
     */
    public int indexOf(Object e, int index) {
        Object[] elements = getArray();
        return indexOf(e, elements, index, elements.length);
    }
    /**
     * {@inheritDoc}
     */
    public int lastIndexOf(Object o) {
        Object[] elements = getArray();
        return lastIndexOf(o, elements, elements.length - 1);
    }
    /**
     * Returns the index of the last occurrence of the specified element in
     * this list, searching backwards from index, or returns -1 if
     * the element is not found.
     * More formally, returns the highest index i such that
     * (i <= index && (e==null ? get(i)==null : e.equals(get(i)))),
     * or -1 if there is no such index.
     *
     * @param e element to search for
     * @param index index to start searching backwards from
     * @return the index of the last occurrence of the element at position
     *         less than or equal to index in this list;
     *         -1 if the element is not found.
     * @throws IndexOutOfBoundsException if the specified index is greater
     *         than or equal to the current size of this list
     */
    public int lastIndexOf(Object e, int index) {
        Object[] elements = getArray();
        return lastIndexOf(e, elements, index);
    }
    /**
     * Returns a shallow copy of this list.  (The elements themselves
     * are not copied.)
     *
     * @return a clone of this list
     */
    public Object clone() {
        try {
            return super.clone();
        } 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 proper sequence (from first to last element).
     *
     * 

The returned array will be "safe" in that no references to it are
     * maintained by this list.  (In other words, this method must allocate
     * a new array).  The caller is thus free to modify the returned array.
     *
     * 

This method acts as bridge between array-based and collection-based
     * APIs.
     *
     * @return an array containing all the elements in this list
     */
    public Object[] toArray() {
        Object[] elements = getArray();
        return copyOf(elements, elements.length);
    }
    /**
     * Returns an array containing all of the elements in this list in
     * proper sequence (from first to last element); 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 this list fits in the specified array with room to spare
     * (i.e., the array has more elements than this list), the element in
     * the array immediately following the end of the list is set to
     * null.  (This is useful in determining the length of this
     * list only if the caller knows that this list does not contain
     * any null elements.)
     *
     * 

Like the {@link #toArray()} method, this method acts as bridge between
     * array-based and collection-based APIs.  Further, this method allows
     * precise control over the runtime type of the output array, and may,
     * under certain circumstances, be used to save allocation costs.
     *
     * 

Suppose x is a list known to contain only strings.
     * The following code can be used to dump the list into a newly
     * allocated array of String:
     *
     * 

     *     String[] y = x.toArray(new String[0]);

This implementation uses the definition in {@link List#hashCode}.
     *
     * @return the hash code value for this list
     */
    public int hashCode() {
        int hashCode = 1;
        Object[] elements = getArray();
        int len = elements.length;
        for (int i = 0; i < len; ++i) {
            Object obj = elements[i];
            hashCode = 31*hashCode + (obj==null ? 0 : obj.hashCode());
        }
        return hashCode;
    }
    /**
     * Returns an iterator over the elements in this list in proper sequence.
     *
     * 

The returned 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.
     *
     * @return an iterator over the elements in this list in proper sequence
     */
    public Iterator iterator() {
        return new COWIterator(getArray(), 0);
    }
    /**
     * {@inheritDoc}
     *
     * 

The returned 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(getArray(), 0);
    }
    /**
     * {@inheritDoc}
     *
     * 

The list iterator returned by this implementation will throw an
     * UnsupportedOperationException in its remove,
     * set and add methods.
     *
     * @throws IndexOutOfBoundsException {@inheritDoc}
     */
    public ListIterator listIterator(final int index) {
        Object[] elements = getArray();
        int len = elements.length;
        if (index < 0 || index > len)
            throw new IndexOutOfBoundsException("Index: " + index);
        return new COWIterator(getArray(), index);
    }
    private static class COWIterator implements ListIterator {
        /** Snapshot of the array **/
        private final Object[] snapshot;
        /** Index of element to be returned by subsequent call to next.  */
        private int cursor;
        private COWIterator(Object[] elements, int initialCursor) {
            cursor = initialCursor;
            snapshot = elements;
        }
        public boolean hasNext() {
            return cursor < snapshot.length;
        }
        public boolean hasPrevious() {
            return cursor > 0;
        }
        public Object next() {
            try {
                return (snapshot[cursor++]);
            } catch (IndexOutOfBoundsException ex) {
                throw new NoSuchElementException();
            }
        }
        public Object previous() {
            try {
                return (snapshot[--cursor]);
            } catch (IndexOutOfBoundsException e) {
                throw new NoSuchElementException();
            }
        }
        public int nextIndex() {
            return cursor;
        }
        public int previousIndex() {
            return cursor - 1;
        }
        /**
         * Not supported. Always throws UnsupportedOperationException.
         * @throws UnsupportedOperationException always; remove
         *         is not supported by this iterator.
         */
        public void remove() {
            throw new UnsupportedOperationException();
        }
        /**
         * Not supported. Always throws UnsupportedOperationException.
         * @throws UnsupportedOperationException always; set
         *         is not supported by this iterator.
         */
        public void set(Object e) {
            throw new UnsupportedOperationException();
        }
        /**
         * Not supported. Always throws UnsupportedOperationException.
         * @throws UnsupportedOperationException always; add
         *         is not supported by this iterator.
         */
        public void add(Object e) {
            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 CopyOnWriteArrayLists.
     *
     *