content: /*
   * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
   *
   * This code is free software; you can redistribute it and/or modify it
   * under the terms of the GNU General Public License version 2 only, as
   * published by the Free Software Foundation.  Oracle designates this
   * particular file as subject to the "Classpath" exception as provided
   * by Oracle in the LICENSE file that accompanied this code.
   *
   * This code is distributed in the hope that it will be useful, but WITHOUT
   * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
   * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
   * version 2 for more details (a copy is included in the LICENSE file that
   * accompanied this code).
   *
   * You should have received a copy of the GNU General Public License version
   * 2 along with this work; if not, write to the Free Software Foundation,
   * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
   *
   * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
   * or visit www.oracle.com if you need additional information or have any
   * questions.
   */
  
  /*
   * Written by Doug Lea with assistance from members of JCP JSR-166
   * Expert Group.  Adapted and released, under explicit permission,
   * from JDK ArrayList.java which carries the following copyright:
   *
   * Copyright 1997 by Sun Microsystems, Inc.,
   * 901 San Antonio Road, Palo Alto, California, 94303, U.S.A.
   * All rights reserved.
   */
  
  package java.util.concurrent;
  
  import java.util.AbstractList;
  import java.util.Arrays;
  import java.util.Collection;
  import java.util.Comparator;
  import java.util.ConcurrentModificationException;
  import java.util.Iterator;
  import java.util.List;
  import java.util.ListIterator;
  import java.util.NoSuchElementException;
  import java.util.Objects;
  import java.util.RandomAccess;
  import java.util.Spliterator;
  import java.util.Spliterators;
  import java.util.function.Consumer;
  import java.util.function.Predicate;
  import java.util.function.UnaryOperator;
  
  // Android-changed: Removed javadoc link to collections framework docs
  
  /**
   * A thread-safe variant of {@link java.util.ArrayList} in which all mutative
   * operations ({@code add}, {@code set}, and so on) are implemented by
   * making a fresh copy of the underlying array.
   *
   * <p>This is ordinarily too costly, but may be <em>more</em> 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 {@code ConcurrentModificationException}.
   * The iterator will not reflect additions, removals, or changes to
   * the list since the iterator was created.  Element-changing
   * operations on iterators themselves ({@code remove}, {@code set}, and
   * {@code add}) are not supported. These methods throw
   * {@code UnsupportedOperationException}.
   *
   * <p>All elements are permitted, including {@code null}.
   *
   * <p>Memory consistency effects: As with other concurrent
   * collections, actions in a thread prior to placing an object into a
   * {@code CopyOnWriteArrayList}
   * <a href="package-summary.html#MemoryVisibility"><i>happen-before</i></a>
   * actions subsequent to the access or removal of that element from
   * the {@code CopyOnWriteArrayList} in another thread.
   *
   * @since 1.5
   * @author Doug Lea
   * @param <E> the type of elements held in this list
   */
  public class CopyOnWriteArrayList<E>
      implements List<E>, RandomAccess, Cloneable, java.io.Serializable {
      private static final long serialVersionUID = 8673264195747942595L;
  
      /**
       * The lock protecting all mutators.  (We have a mild preference
       * for builtin monitors over ReentrantLock when either will do.)
       */
      final transient Object lock = new Object();
  
      /** The array, accessed only via getArray/setArray. */
      private transient volatile Object[] array;
  
      /**
       * Gets the array.  Non-private so as to also be accessible
       * from CopyOnWriteArraySet class.
       */
      final Object[] getArray() {
          return array;
      }
  
      /**
       * Sets the array.
       */
      final 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<? extends E> c) {
          Object[] elements;
          if (c.getClass() == CopyOnWriteArrayList.class)
              elements = ((CopyOnWriteArrayList<?>)c).getArray();
          else {
              elements = c.toArray();
              // defend against c.toArray (incorrectly) not returning Object[]
              // (see e.g. https://bugs.openjdk.java.net/browse/JDK-6260652)
              if (elements.getClass() != Object[].class)
                  elements = Arrays.copyOf(elements, elements.length, Object[].class);
          }
          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(E[] toCopyIn) {
          setArray(Arrays.copyOf(toCopyIn, toCopyIn.length, Object[].class));
      }
  
      /**
       * Returns the number of elements in this list.
       *
       * @return the number of elements in this list
       */
      public int size() {
          return getArray().length;
      }
  
      /**
       * Returns {@code true} if this list contains no elements.
       *
       * @return {@code true} if this list contains no elements
       */
      public boolean isEmpty() {
          return size() == 0;
      }
  
      /**
       * 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 {@code true} if this list contains the specified element.
       * More formally, returns {@code true} if and only if this list contains
       * at least one element {@code e} such that {@code Objects.equals(o, e)}.
       *
       * @param o element whose presence in this list is to be tested
       * @return {@code 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 {@code index}, or returns -1 if
       * the element is not found.
       * More formally, returns the lowest index {@code i} such that
       * {@code i >= index && Objects.equals(get(i), e)},
       * 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 {@code index} or later in the list;
       *         {@code -1} if the element is not found.
       * @throws IndexOutOfBoundsException if the specified index is negative
       */
      public int indexOf(E 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 {@code index}, or returns -1 if
       * the element is not found.
       * More formally, returns the highest index {@code i} such that
       * {@code i <= index && Objects.equals(get(i), e)},
       * 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 {@code 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(E 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 {
              @SuppressWarnings("unchecked")
              CopyOnWriteArrayList<E> clone =
                  (CopyOnWriteArrayList<E>) super.clone();
              clone.resetLock();
              return 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).
       *
       * <p>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.
       *
       * <p>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 Arrays.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.
       *
       * <p>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
       * {@code null}.  (This is useful in determining the length of this
       * list <i>only</i> if the caller knows that this list does not contain
       * any null elements.)
       *
       * <p>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.
       *
       * <p>Suppose {@code 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 {@code String}:
       *
       * <pre> {@code String[] y = x.toArray(new String[0]);}</pre>
       *
       * Note that {@code toArray(new Object[0])} is identical in function to
       * {@code toArray()}.
       *
       * @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 all the elements in this list
       * @throws ArrayStoreException if the runtime type of the specified array
       *         is not a supertype of the runtime type of every element in
       *         this list
       * @throws NullPointerException if the specified array is null
       */
      @SuppressWarnings("unchecked")
      public <T> T[] toArray(T[] a) {
          Object[] elements = getArray();
          int len = elements.length;
          if (a.length < len)
              return (T[]) Arrays.copyOf(elements, len, a.getClass());
          else {
              System.arraycopy(elements, 0, a, 0, len);
              if (a.length > len)
                  a[len] = null;
              return a;
          }
      }
  
      // Positional Access Operations
  
      @SuppressWarnings("unchecked")
      private E get(Object[] a, int index) {
          return (E) a[index];
      }
  
      static String outOfBounds(int index, int size) {
          return "Index: " + index + ", Size: " + size;
      }
  
      /**
       * {@inheritDoc}
       *
       * @throws IndexOutOfBoundsException {@inheritDoc}
       */
      public E get(int index) {
          return get(getArray(), index);
      }
  
      /**
       * Replaces the element at the specified position in this list with the
       * specified element.
       *
       * @throws IndexOutOfBoundsException {@inheritDoc}
       */
      public E set(int index, E element) {
          synchronized (lock) {
              Object[] elements = getArray();
              E oldValue = get(elements, index);
  
              if (oldValue != element) {
                  int len = elements.length;
                  Object[] newElements = Arrays.copyOf(elements, len);
                  newElements[index] = element;
                  setArray(newElements);
              } else {
                  // Not quite a no-op; ensures volatile write semantics
                  setArray(elements);
              }
              return oldValue;
          }
      }
  
      /**
       * Appends the specified element to the end of this list.
       *
       * @param e element to be appended to this list
       * @return {@code true} (as specified by {@link Collection#add})
       */
      public boolean add(E e) {
          synchronized (lock) {
              Object[] elements = getArray();
              int len = elements.length;
              Object[] newElements = Arrays.copyOf(elements, len + 1);
              newElements[len] = e;
              setArray(newElements);
              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).
       *
       * @throws IndexOutOfBoundsException {@inheritDoc}
       */
      public void add(int index, E element) {
          synchronized (lock) {
              Object[] elements = getArray();
              int len = elements.length;
              if (index > len || index < 0)
                  throw new IndexOutOfBoundsException(outOfBounds(index, len));
              Object[] newElements;
              int numMoved = len - index;
              if (numMoved == 0)
                  newElements = Arrays.copyOf(elements, len + 1);
              else {
                  newElements = new Object[len + 1];
                  System.arraycopy(elements, 0, newElements, 0, index);
                  System.arraycopy(elements, index, newElements, index + 1,
                                   numMoved);
              }
              newElements[index] = element;
              setArray(newElements);
          }
      }
  
      /**
       * 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.
       *
       * @throws IndexOutOfBoundsException {@inheritDoc}
       */
      public E remove(int index) {
          synchronized (lock) {
              Object[] elements = getArray();
              int len = elements.length;
              E oldValue = get(elements, index);
              int numMoved = len - index - 1;
              if (numMoved == 0)
                  setArray(Arrays.copyOf(elements, len - 1));
              else {
                  Object[] newElements = new Object[len - 1];
                  System.arraycopy(elements, 0, newElements, 0, index);
                  System.arraycopy(elements, index + 1, newElements, index,
                                   numMoved);
                  setArray(newElements);
              }
              return oldValue;
          }
      }
  
      /**
       * Removes the first occurrence of the specified element from this list,
       * if it is present.  If this list does not contain the element, it is
       * unchanged.  More formally, removes the element with the lowest index
       * {@code i} such that {@code Objects.equals(o, get(i))}
       * (if such an element exists).  Returns {@code true} if this list
       * contained the specified element (or equivalently, if this list
       * changed as a result of the call).
       *
       * @param o element to be removed from this list, if present
       * @return {@code true} if this list contained the specified element
       */
      public boolean remove(Object o) {
          Object[] snapshot = getArray();
          int index = indexOf(o, snapshot, 0, snapshot.length);
          return (index < 0) ? false : remove(o, snapshot, index);
      }
  
      /**
       * A version of remove(Object) using the strong hint that given
       * recent snapshot contains o at the given index.
       */
      private boolean remove(Object o, Object[] snapshot, int index) {
          synchronized (lock) {
              Object[] current = getArray();
              int len = current.length;
              if (snapshot != current) findIndex: {
                  int prefix = Math.min(index, len);
                  for (int i = 0; i < prefix; i++) {
                      if (current[i] != snapshot[i]
                          && Objects.equals(o, current[i])) {
                          index = i;
                          break findIndex;
                      }
                  }
                  if (index >= len)
                      return false;
                  if (current[index] == o)
                      break findIndex;
                  index = indexOf(o, current, index, len);
                  if (index < 0)
                      return false;
              }
              Object[] newElements = new Object[len - 1];
              System.arraycopy(current, 0, newElements, 0, index);
              System.arraycopy(current, index + 1,
                               newElements, index,
                               len - index - 1);
              setArray(newElements);
              return true;
          }
      }
  
      /**
       * Removes from this list all of the elements whose index is between
       * {@code fromIndex}, inclusive, and {@code toIndex}, exclusive.
       * Shifts any succeeding elements to the left (reduces their index).
       * This call shortens the list by {@code (toIndex - fromIndex)} elements.
       * (If {@code 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
       * @throws IndexOutOfBoundsException if fromIndex or toIndex out of range
       *         ({@code fromIndex < 0 || toIndex > size() || toIndex < fromIndex})
       */
      void removeRange(int fromIndex, int toIndex) {
          synchronized (lock) {
              Object[] elements = getArray();
              int len = elements.length;
  
              if (fromIndex < 0 || toIndex > len || toIndex < fromIndex)
                  throw new IndexOutOfBoundsException();
              int newlen = len - (toIndex - fromIndex);
              int numMoved = len - toIndex;
              if (numMoved == 0)
                  setArray(Arrays.copyOf(elements, newlen));
              else {
                  Object[] newElements = new Object[newlen];
                  System.arraycopy(elements, 0, newElements, 0, fromIndex);
                  System.arraycopy(elements, toIndex, newElements,
                                   fromIndex, numMoved);
                  setArray(newElements);
              }
          }
      }
  
      /**
       * Appends the element, if not present.
       *
       * @param e element to be added to this list, if absent
       * @return {@code true} if the element was added
       */
      public boolean addIfAbsent(E e) {
          Object[] snapshot = getArray();
          return indexOf(e, snapshot, 0, snapshot.length) >= 0 ? false :
              addIfAbsent(e, snapshot);
      }
  
      /**
       * A version of addIfAbsent using the strong hint that given
       * recent snapshot does not contain e.
       */
      private boolean addIfAbsent(E e, Object[] snapshot) {
          synchronized (lock) {
              Object[] current = getArray();
              int len = current.length;
              if (snapshot != current) {
                  // Optimize for lost race to another addXXX operation
                  int common = Math.min(snapshot.length, len);
                  for (int i = 0; i < common; i++)
                      if (current[i] != snapshot[i]
                          && Objects.equals(e, current[i]))
                          return false;
                  if (indexOf(e, current, common, len) >= 0)
                          return false;
              }
              Object[] newElements = Arrays.copyOf(current, len + 1);
              newElements[len] = e;
              setArray(newElements);
              return true;
          }
      }
  
      /**
       * Returns {@code true} if this list contains all of the elements of the
       * specified collection.
       *
       * @param c collection to be checked for containment in this list
       * @return {@code true} if this list contains all of the elements of the
       *         specified collection
       * @throws NullPointerException if the specified collection is null
       * @see #contains(Object)
       */
      public boolean containsAll(Collection<?> c) {
          Object[] elements = getArray();
          int len = elements.length;
          for (Object e : c) {
              if (indexOf(e, elements, 0, len) < 0)
                  return false;
          }
          return true;
      }
  
      /**
       * Removes from this list 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.
       *
       * @param c collection containing elements to be removed from this list
       * @return {@code true} if this list changed as a result of the call
       * @throws ClassCastException if the class of an element of this list
       *         is incompatible with the specified collection
       * (<a href="../Collection.html#optional-restrictions">optional</a>)
       * @throws NullPointerException if this list contains a null element and the
       *         specified collection does not permit null elements
       * (<a href="../Collection.html#optional-restrictions">optional</a>),
       *         or if the specified collection is null
       * @see #remove(Object)
       */
      public boolean removeAll(Collection<?> c) {
          if (c == null) throw new NullPointerException();
          synchronized (lock) {
              Object[] elements = getArray();
              int len = elements.length;
              if (len != 0) {
                  // temp array holds those elements we know we want to keep
                  int newlen = 0;
                  Object[] temp = new Object[len];
                  for (int i = 0; i < len; ++i) {
                      Object element = elements[i];
                      if (!c.contains(element))
                          temp[newlen++] = element;
                  }
                  if (newlen != len) {
                      setArray(Arrays.copyOf(temp, newlen));
                      return true;
                  }
              }
              return false;
          }
      }
  
      /**
       * Retains only the elements in this list that are contained in the
       * specified collection.  In other words, removes from this list all of
       * its elements that are not contained in the specified collection.
       *
       * @param c collection containing elements to be retained in this list
       * @return {@code true} if this list changed as a result of the call
       * @throws ClassCastException if the class of an element of this list
       *         is incompatible with the specified collection
       * (<a href="{@docRoot}/../api/java/util/Collection.html#optional-restrictions">optional</a>)
       * @throws NullPointerException if this list contains a null element and the
       *         specified collection does not permit null elements
       * (<a href="{@docRoot}/../api/java/util/Collection.html#optional-restrictions">optional</a>),
       *         or if the specified collection is null
       * @see #remove(Object)
       */
      public boolean retainAll(Collection<?> c) {
          if (c == null) throw new NullPointerException();
          synchronized (lock) {
              Object[] elements = getArray();
              int len = elements.length;
              if (len != 0) {
                  // temp array holds those elements we know we want to keep
                  int newlen = 0;
                  Object[] temp = new Object[len];
                  for (int i = 0; i < len; ++i) {
                      Object element = elements[i];
                      if (c.contains(element))
                          temp[newlen++] = element;
                  }
                  if (newlen != len) {
                      setArray(Arrays.copyOf(temp, newlen));
                      return true;
                  }
              }
              return false;
          }
      }
  
      /**
       * 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 collection containing elements to be added to this list
       * @return the number of elements added
       * @throws NullPointerException if the specified collection is null
       * @see #addIfAbsent(Object)
       */
      public int addAllAbsent(Collection<? extends E> c) {
          Object[] cs = c.toArray();
          if (cs.length == 0)
              return 0;
          synchronized (lock) {
              Object[] elements = getArray();
              int len = elements.length;
              int added = 0;
              // uniquify and compact elements in cs
              for (int i = 0; i < cs.length; ++i) {
                  Object e = cs[i];
                  if (indexOf(e, elements, 0, len) < 0 &&
                      indexOf(e, cs, 0, added) < 0)
                      cs[added++] = e;
              }
              if (added > 0) {
                  Object[] newElements = Arrays.copyOf(elements, len + added);
                  System.arraycopy(cs, 0, newElements, len, added);
                  setArray(newElements);
              }
              return added;
          }
      }
  
      /**
       * Removes all of the elements from this list.
       * The list will be empty after this call returns.
       */
      public void clear() {
          synchronized (lock) {
              setArray(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 collection containing elements to be added to this list
       * @return {@code true} if this list changed as a result of the call
       * @throws NullPointerException if the specified collection is null
       * @see #add(Object)
       */
      public boolean addAll(Collection<? extends E> c) {
          Object[] cs = (c.getClass() == CopyOnWriteArrayList.class) ?
              ((CopyOnWriteArrayList<?>)c).getArray() : c.toArray();
          if (cs.length == 0)
              return false;
          synchronized (lock) {
              Object[] elements = getArray();
              int len = elements.length;
              if (len == 0 && cs.getClass() == Object[].class)
                  setArray(cs);
              else {
                  Object[] newElements = Arrays.copyOf(elements, len + cs.length);
                  System.arraycopy(cs, 0, newElements, len, cs.length);
                  setArray(newElements);
              }
              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 this list in the order that they are returned by the
       * specified collection's iterator.
       *
       * @param index index at which to insert the first element
       *        from the specified collection
       * @param c collection containing elements to be added to this list
       * @return {@code true} if this list changed as a result of the call
       * @throws IndexOutOfBoundsException {@inheritDoc}
       * @throws NullPointerException if the specified collection is null
       * @see #add(int,Object)
       */
      public boolean addAll(int index, Collection<? extends E> c) {
          Object[] cs = c.toArray();
          synchronized (lock) {
              Object[] elements = getArray();
              int len = elements.length;
              if (index > len || index < 0)
                  throw new IndexOutOfBoundsException(outOfBounds(index, len));
              if (cs.length == 0)
                  return false;
              int numMoved = len - index;
              Object[] newElements;
              if (numMoved == 0)
                  newElements = Arrays.copyOf(elements, len + cs.length);
              else {
                  newElements = new Object[len + cs.length];
                  System.arraycopy(elements, 0, newElements, 0, index);
                  System.arraycopy(elements, index,
                                   newElements, index + cs.length,
                                   numMoved);
              }
              System.arraycopy(cs, 0, newElements, index, cs.length);
              setArray(newElements);
              return true;
          }
      }
  
      public void forEach(Consumer<? super E> action) {
          if (action == null) throw new NullPointerException();
          for (Object x : getArray()) {
              @SuppressWarnings("unchecked") E e = (E) x;
              action.accept(e);
          }
      }
  
      public boolean removeIf(Predicate<? super E> filter) {
          if (filter == null) throw new NullPointerException();
          synchronized (lock) {
              final Object[] elements = getArray();
              final int len = elements.length;
              int i;
              for (i = 0; i < len; i++) {
                  @SuppressWarnings("unchecked") E e = (E) elements[i];
                  if (filter.test(e)) {
                      int newlen = i;
                      final Object[] newElements = new Object[len - 1];
                      System.arraycopy(elements, 0, newElements, 0, newlen);
                      for (i++; i < len; i++) {
                          @SuppressWarnings("unchecked") E x = (E) elements[i];
                          if (!filter.test(x))
                              newElements[newlen++] = x;
                      }
                      setArray((newlen == len - 1)
                               ? newElements // one match => one copy
                               : Arrays.copyOf(newElements, newlen));
                      return true;
                  }
              }
              return false;       // zero matches => zero copies
          }
      }
  
      public void replaceAll(UnaryOperator<E> operator) {
          if (operator == null) throw new NullPointerException();
          synchronized (lock) {
              Object[] elements = getArray();
              int len = elements.length;
              Object[] newElements = Arrays.copyOf(elements, len);
              for (int i = 0; i < len; ++i) {
                  @SuppressWarnings("unchecked") E e = (E) elements[i];
                  newElements[i] = operator.apply(e);
              }
              setArray(newElements);
          }
      }
  
      public void sort(Comparator<? super E> c) {
          synchronized (lock) {
              Object[] elements = getArray();
              Object[] newElements = Arrays.copyOf(elements, elements.length);
              @SuppressWarnings("unchecked") E[] es = (E[])newElements;
              Arrays.sort(es, c);
              setArray(newElements);
          }
      }
  
      /**
       * Saves this list to a stream (that is, serializes it).
       *
       * @param s the stream
       * @throws java.io.IOException if an I/O error occurs
       * @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 {
  
          s.defaultWriteObject();
  
          Object[] elements = getArray();
          // Write out array length
          s.writeInt(elements.length);
  
          // Write out all elements in the proper order.
          for (Object element : elements)
              s.writeObject(element);
      }
  
      /**
       * Reconstitutes this list from a stream (that is, deserializes it).
       * @param s the stream
       * @throws ClassNotFoundException if the class of a serialized object
       *         could not be found
       * @throws java.io.IOException if an I/O error occurs
       */
      private void readObject(java.io.ObjectInputStream s)
          throws java.io.IOException, ClassNotFoundException {
  
          s.defaultReadObject();
  
          // bind to new lock
          resetLock();
  
          // Read in array length and allocate array
          int len = s.readInt();
          Object[] elements = new Object[len];
  
          // Read in all elements in the proper order.
          for (int i = 0; i < len; i++)
              elements[i] = s.readObject();
          setArray(elements);
      }
  
      /**
       * Returns a string representation of this list.  The string
       * representation consists of the string representations of the list's
       * elements in the order they are returned by its iterator, enclosed in
       * square brackets ({@code "[]"}).  Adjacent elements are separated by
       * the characters {@code ", "} (comma and space).  Elements are
       * converted to strings as by {@link String#valueOf(Object)}.
       *
       * @return a string representation of this list
       */
      public String toString() {
          return Arrays.toString(getArray());
      }
  
      /**
       * Compares the specified object with this list for equality.
       * Returns {@code true} if the specified object is the same object
       * as this object, or if it is also a {@link List} and the sequence
       * of elements returned by an {@linkplain List#iterator() iterator}
       * over the specified list is the same as the sequence returned by
       * an iterator over this list.  The two sequences are considered to
       * be the same if they have the same length and corresponding
       * elements at the same position in the sequence are <em>equal</em>.
       * Two elements {@code e1} and {@code e2} are considered
       * <em>equal</em> if {@code Objects.equals(e1, e2)}.
       *
       * @param o the object to be compared for equality with this list
       * @return {@code 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<?> list = (List<?>)o;
          Iterator<?> it = list.iterator();
          Object[] elements = getArray();
          for (int i = 0, len = elements.length; i < len; i++)
              if (!it.hasNext() || !Objects.equals(elements[i], it.next()))
                  return false;
          if (it.hasNext())
              return false;
          return true;
      }
  
      /**
       * Returns the hash code value for this list.
       *
       * <p>This implementation uses the definition in {@link List#hashCode}.
       *
       * @return the hash code value for this list
       */
      public int hashCode() {
          int hashCode = 1;
          for (Object x : getArray())
              hashCode = 31 * hashCode + (x == null ? 0 : x.hashCode());
          return hashCode;
      }
  
      /**
       * Returns an iterator over the elements in this list in proper sequence.
       *
       * <p>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 <em>NOT</em> support the
       * {@code remove} method.
       *
       * @return an iterator over the elements in this list in proper sequence
       */
      public Iterator<E> iterator() {
          return new COWIterator<E>(getArray(), 0);
      }
  
      /**
       * {@inheritDoc}
       *
       * <p>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 <em>NOT</em> support the
       * {@code remove}, {@code set} or {@code add} methods.
       */
      public ListIterator<E> listIterator() {
          return new COWIterator<E>(getArray(), 0);
      }
  
      /**
       * {@inheritDoc}
       *
       * <p>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 <em>NOT</em> support the
       * {@code remove}, {@code set} or {@code add} methods.
       *
       * @throws IndexOutOfBoundsException {@inheritDoc}
       */
      public ListIterator<E> listIterator(int index) {
          Object[] elements = getArray();
          int len = elements.length;
          if (index < 0 || index > len)
              throw new IndexOutOfBoundsException(outOfBounds(index, len));
  
          return new COWIterator<E>(elements, index);
      }
  
      /**
       * Returns a {@link Spliterator} over the elements in this list.
       *
       * <p>The {@code Spliterator} reports {@link Spliterator#IMMUTABLE},
       * {@link Spliterator#ORDERED}, {@link Spliterator#SIZED}, and
       * {@link Spliterator#SUBSIZED}.
       *
       * <p>The spliterator provides a snapshot of the state of the list
       * when the spliterator was constructed. No synchronization is needed while
       * operating on the spliterator.
       *
       * @return a {@code Spliterator} over the elements in this list
       * @since 1.8
       */
      public Spliterator<E> spliterator() {
          return Spliterators.spliterator
              (getArray(), Spliterator.IMMUTABLE | Spliterator.ORDERED);
      }
  
      static final class COWIterator<E> implements ListIterator<E> {
          /** Snapshot of the array */
          private final Object[] snapshot;
          /** Index of element to be returned by subsequent call to next.  */
          private int cursor;
  
          COWIterator(Object[] elements, int initialCursor) {
              cursor = initialCursor;
              snapshot = elements;
          }
  
          public boolean hasNext() {
              return cursor < snapshot.length;
          }
  
          public boolean hasPrevious() {
              return cursor > 0;
          }
  
          @SuppressWarnings("unchecked")
          public E next() {
              if (! hasNext())
                  throw new NoSuchElementException();
              return (E) snapshot[cursor++];
          }
  
          @SuppressWarnings("unchecked")
          public E previous() {
              if (! hasPrevious())
                  throw new NoSuchElementException();
              return (E) snapshot[--cursor];
          }
  
          public int nextIndex() {
              return cursor;
          }
  
          public int previousIndex() {
              return cursor-1;
          }
  
          /**
           * Not supported. Always throws UnsupportedOperationException.
           * @throws UnsupportedOperationException always; {@code remove}
           *         is not supported by this iterator.
           */
          public void remove() {
              throw new UnsupportedOperationException();
          }
  
          /**
           * Not supported. Always throws UnsupportedOperationException.
           * @throws UnsupportedOperationException always; {@code set}
           *         is not supported by this iterator.
           */
          public void set(E e) {
              throw new UnsupportedOperationException();
          }
  
          /**
           * Not supported. Always throws UnsupportedOperationException.
           * @throws UnsupportedOperationException always; {@code add}
           *         is not supported by this iterator.
           */
          public void add(E e) {
              throw new UnsupportedOperationException();
          }
  
          @Override
          @SuppressWarnings("unchecked")
          public void forEachRemaining(Consumer<? super E> action) {
              Objects.requireNonNull(action);
              final int size = snapshot.length;
              for (int i = cursor; i < size; i++) {
                  action.accept((E) snapshot[i]);
              }
              cursor = size;
          }
      }
  
      /**
       * Returns a view of the portion of this list between
       * {@code fromIndex}, inclusive, and {@code toIndex}, exclusive.
       * The returned list is backed by this list, so changes in the
       * returned list are reflected in this list.
       *
       * <p>The semantics of the list returned by this method become
       * undefined if the backing list (i.e., this list) is modified in
       * any way other than via the returned list.
       *
       * @param fromIndex low endpoint (inclusive) of the subList
       * @param toIndex high endpoint (exclusive) of the subList
       * @return a view of the specified range within this list
       * @throws IndexOutOfBoundsException {@inheritDoc}
       */
      public List<E> subList(int fromIndex, int toIndex) {
          synchronized (lock) {
              Object[] elements = getArray();
              int len = elements.length;
              if (fromIndex < 0 || toIndex > len || fromIndex > toIndex)
                  throw new IndexOutOfBoundsException();
              return new COWSubList<E>(this, fromIndex, toIndex);
          }
      }
  
      /**
       * Sublist for CopyOnWriteArrayList.
       * This class extends AbstractList merely for convenience, to
       * avoid having to define addAll, etc. This doesn't hurt, but
       * is wasteful.  This class does not need or use modCount
       * mechanics in AbstractList, but does need to check for
       * concurrent modification using similar mechanics.  On each
       * operation, the array that we expect the backing list to use
       * is checked and updated.  Since we do this for all of the
       * base operations invoked by those defined in AbstractList,
       * all is well.  While inefficient, this is not worth
       * improving.  The kinds of list operations inherited from
       * AbstractList are already so slow on COW sublists that
       * adding a bit more space/time doesn't seem even noticeable.
       */
      private static class COWSubList<E>
          extends AbstractList<E>
          implements RandomAccess
      {
          private final CopyOnWriteArrayList<E> l;
          private final int offset;
          private int size;
          private Object[] expectedArray;
  
          // only call this holding l's lock
          COWSubList(CopyOnWriteArrayList<E> list,
                     int fromIndex, int toIndex) {
              // assert Thread.holdsLock(list.lock);
              l = list;
              expectedArray = l.getArray();
              offset = fromIndex;
              size = toIndex - fromIndex;
          }
  
          // only call this holding l's lock
          private void checkForComodification() {
              // assert Thread.holdsLock(l.lock);
              if (l.getArray() != expectedArray)
                  throw new ConcurrentModificationException();
          }
  
          // only call this holding l's lock
          private void rangeCheck(int index) {
              // assert Thread.holdsLock(l.lock);
              if (index < 0 || index >= size)
                  throw new IndexOutOfBoundsException(outOfBounds(index, size));
          }
  
          public E set(int index, E element) {
              synchronized (l.lock) {
                  rangeCheck(index);
                  checkForComodification();
                  E x = l.set(index+offset, element);
                  expectedArray = l.getArray();
                  return x;
              }
          }
  
          public E get(int index) {
              synchronized (l.lock) {
                  rangeCheck(index);
                  checkForComodification();
                  return l.get(index+offset);
              }
          }
  
          public int size() {
              synchronized (l.lock) {
                  checkForComodification();
                  return size;
              }
          }
  
          public void add(int index, E element) {
              synchronized (l.lock) {
                  checkForComodification();
                  if (index < 0 || index > size)
                      throw new IndexOutOfBoundsException
                          (outOfBounds(index, size));
                  l.add(index+offset, element);
                  expectedArray = l.getArray();
                  size++;
              }
          }
  
          public void clear() {
              synchronized (l.lock) {
                  checkForComodification();
                  l.removeRange(offset, offset+size);
                  expectedArray = l.getArray();
                  size = 0;
              }
          }
  
          public E remove(int index) {
              synchronized (l.lock) {
                  rangeCheck(index);
                  checkForComodification();
                  E result = l.remove(index+offset);
                  expectedArray = l.getArray();
                  size--;
                  return result;
              }
          }
  
          public boolean remove(Object o) {
              int index = indexOf(o);
              if (index == -1)
                  return false;
              remove(index);
              return true;
          }
  
          public Iterator<E> iterator() {
              synchronized (l.lock) {
                  checkForComodification();
                  return new COWSubListIterator<E>(l, 0, offset, size);
              }
          }
  
          public ListIterator<E> listIterator(int index) {
              synchronized (l.lock) {
                  checkForComodification();
                  if (index < 0 || index > size)
                      throw new IndexOutOfBoundsException
                          (outOfBounds(index, size));
                  return new COWSubListIterator<E>(l, index, offset, size);
              }
          }
  
          public List<E> subList(int fromIndex, int toIndex) {
              synchronized (l.lock) {
                  checkForComodification();
                  if (fromIndex < 0 || toIndex > size || fromIndex > toIndex)
                      throw new IndexOutOfBoundsException();
                  return new COWSubList<E>(l, fromIndex + offset,
                                           toIndex + offset);
              }
          }
  
          public void forEach(Consumer<? super E> action) {
              if (action == null) throw new NullPointerException();
              int lo = offset;
              int hi = offset + size;
              Object[] a = expectedArray;
              if (l.getArray() != a)
                  throw new ConcurrentModificationException();
              if (lo < 0 || hi > a.length)
                  throw new IndexOutOfBoundsException();
              for (int i = lo; i < hi; ++i) {
                  @SuppressWarnings("unchecked") E e = (E) a[i];
                  action.accept(e);
              }
          }
  
          public void replaceAll(UnaryOperator<E> operator) {
              if (operator == null) throw new NullPointerException();
              synchronized (l.lock) {
                  int lo = offset;
                  int hi = offset + size;
                  Object[] elements = expectedArray;
                  if (l.getArray() != elements)
                      throw new ConcurrentModificationException();
                  int len = elements.length;
                  if (lo < 0 || hi > len)
                      throw new IndexOutOfBoundsException();
                  Object[] newElements = Arrays.copyOf(elements, len);
                  for (int i = lo; i < hi; ++i) {
                      @SuppressWarnings("unchecked") E e = (E) elements[i];
                      newElements[i] = operator.apply(e);
                  }
                  l.setArray(expectedArray = newElements);
              }
          }
  
          public void sort(Comparator<? super E> c) {
              synchronized (l.lock) {
                  int lo = offset;
                  int hi = offset + size;
                  Object[] elements = expectedArray;
                  if (l.getArray() != elements)
                      throw new ConcurrentModificationException();
                  int len = elements.length;
                  if (lo < 0 || hi > len)
                      throw new IndexOutOfBoundsException();
                  Object[] newElements = Arrays.copyOf(elements, len);
                  @SuppressWarnings("unchecked") E[] es = (E[])newElements;
                  Arrays.sort(es, lo, hi, c);
                  l.setArray(expectedArray = newElements);
              }
          }
  
          public boolean removeAll(Collection<?> c) {
              if (c == null) throw new NullPointerException();
              boolean removed = false;
              synchronized (l.lock) {
                  int n = size;
                  if (n > 0) {
                      int lo = offset;
                      int hi = offset + n;
                      Object[] elements = expectedArray;
                      if (l.getArray() != elements)
                          throw new ConcurrentModificationException();
                      int len = elements.length;
                      if (lo < 0 || hi > len)
                          throw new IndexOutOfBoundsException();
                      int newSize = 0;
                      Object[] temp = new Object[n];
                      for (int i = lo; i < hi; ++i) {
                          Object element = elements[i];
                          if (!c.contains(element))
                              temp[newSize++] = element;
                      }
                      if (newSize != n) {
                          Object[] newElements = new Object[len - n + newSize];
                          System.arraycopy(elements, 0, newElements, 0, lo);
                          System.arraycopy(temp, 0, newElements, lo, newSize);
                          System.arraycopy(elements, hi, newElements,
                                           lo + newSize, len - hi);
                          size = newSize;
                          removed = true;
                          l.setArray(expectedArray = newElements);
                      }
                  }
              }
              return removed;
          }
  
          public boolean retainAll(Collection<?> c) {
              if (c == null) throw new NullPointerException();
              boolean removed = false;
              synchronized (l.lock) {
                  int n = size;
                  if (n > 0) {
                      int lo = offset;
                      int hi = offset + n;
                      Object[] elements = expectedArray;
                      if (l.getArray() != elements)
                          throw new ConcurrentModificationException();
                      int len = elements.length;
                      if (lo < 0 || hi > len)
                          throw new IndexOutOfBoundsException();
                      int newSize = 0;
                      Object[] temp = new Object[n];
                      for (int i = lo; i < hi; ++i) {
                          Object element = elements[i];
                          if (c.contains(element))
                              temp[newSize++] = element;
                      }
                      if (newSize != n) {
                          Object[] newElements = new Object[len - n + newSize];
                          System.arraycopy(elements, 0, newElements, 0, lo);
                          System.arraycopy(temp, 0, newElements, lo, newSize);
                          System.arraycopy(elements, hi, newElements,
                                           lo + newSize, len - hi);
                          size = newSize;
                          removed = true;
                          l.setArray(expectedArray = newElements);
                      }
                  }
              }
              return removed;
          }
  
          public boolean removeIf(Predicate<? super E> filter) {
              if (filter == null) throw new NullPointerException();
              boolean removed = false;
              synchronized (l.lock) {
                  int n = size;
                  if (n > 0) {
                      int lo = offset;
                      int hi = offset + n;
                      Object[] elements = expectedArray;
                      if (l.getArray() != elements)
                          throw new ConcurrentModificationException();
                      int len = elements.length;
                      if (lo < 0 || hi > len)
                          throw new IndexOutOfBoundsException();
                      int newSize = 0;
                      Object[] temp = new Object[n];
                      for (int i = lo; i < hi; ++i) {
                          @SuppressWarnings("unchecked") E e = (E) elements[i];
                          if (!filter.test(e))
                              temp[newSize++] = e;
                      }
                      if (newSize != n) {
                          Object[] newElements = new Object[len - n + newSize];
                          System.arraycopy(elements, 0, newElements, 0, lo);
                          System.arraycopy(temp, 0, newElements, lo, newSize);
                          System.arraycopy(elements, hi, newElements,
                                           lo + newSize, len - hi);
                          size = newSize;
                          removed = true;
                          l.setArray(expectedArray = newElements);
                      }
                  }
              }
              return removed;
          }
  
          public Spliterator<E> spliterator() {
              int lo = offset;
              int hi = offset + size;
              Object[] a = expectedArray;
              if (l.getArray() != a)
                  throw new ConcurrentModificationException();
              if (lo < 0 || hi > a.length)
                  throw new IndexOutOfBoundsException();
              return Spliterators.spliterator
                  (a, lo, hi, Spliterator.IMMUTABLE | Spliterator.ORDERED);
          }
  
      }
  
      private static class COWSubListIterator<E> implements ListIterator<E> {
          private final ListIterator<E> it;
          private final int offset;
          private final int size;
  
          COWSubListIterator(List<E> l, int index, int offset, int size) {
              this.offset = offset;
              this.size = size;
              it = l.listIterator(index+offset);
          }
  
          public boolean hasNext() {
              return nextIndex() < size;
          }
  
          public E next() {
              if (hasNext())
                  return it.next();
              else
                  throw new NoSuchElementException();
          }
  
          public boolean hasPrevious() {
              return previousIndex() >= 0;
          }
  
          public E previous() {
              if (hasPrevious())
                  return it.previous();
              else
                  throw new NoSuchElementException();
          }
  
          public int nextIndex() {
              return it.nextIndex() - offset;
          }
  
          public int previousIndex() {
              return it.previousIndex() - offset;
          }
  
          public void remove() {
              throw new UnsupportedOperationException();
          }
  
          public void set(E e) {
              throw new UnsupportedOperationException();
          }
  
          public void add(E e) {
              throw new UnsupportedOperationException();
          }
  
          @Override
          @SuppressWarnings("unchecked")
          public void forEachRemaining(Consumer<? super E> action) {
              Objects.requireNonNull(action);
              while (nextIndex() < size) {
                  action.accept(it.next());
              }
          }
      }
  
      // Support for resetting lock while deserializing
      private void resetLock() {
          U.putObjectVolatile(this, LOCK, new Object());
      }
      private static final sun.misc.Unsafe U = sun.misc.Unsafe.getUnsafe();
      private static final long LOCK;
      static {
          try {
              LOCK = U.objectFieldOffset
                  (CopyOnWriteArrayList.class.getDeclaredField("lock"));
          } catch (ReflectiveOperationException e) {
              throw new Error(e);
          }
      }
  }
  