copyonwritearraylist.java

采用JAVA开发

/*
  File: CopyOnWriteArrayList.java

  Written by Doug Lea. Adapted and released, under explicit
  permission, from JDK1.2 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.
     *
     * This software is the confidential and proprietary information
     * of Sun Microsystems, Inc. ("Confidential Information").  You
     * shall not disclose such Confidential Information and shall use
     * it only in accordance with the terms of the license agreement
     * you entered into with Sun.

  History:
  Date       Who                What
  21Jun1998  dl               Create public version
   9Oct1999  dl               faster equals
  29jun2001  dl               Serialization methods now private
*/

package EDU.oswego.cs.dl.util.concurrent;
import java.util.*;

/**
 * This class implements a variant of java.util.ArrayList in which
 * all mutative operations (add, set, and so on) are implemented
 * by making a fresh copy of the underlying array.
 * <p>
 * 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.) 
 * <p>
 * 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.)
 * <p>
 * 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 :-).
 * <p>
 * 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.
 * <p>
 * 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.
 * <p>
 * <p>[<a href="http://gee.cs.oswego.edu/dl/classes/EDU/oswego/cs/dl/util/concurrent/intro.html"> Introduction to this package. </a>]
 * @see CopyOnWriteArraySet
 **/


public class CopyOnWriteArrayList implements List, Cloneable, java.io.Serializable {
  /**
   * 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
   **/
  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.  
   */
  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 <code>n</code>
   * elements of the provided array, starting at position <code>first</code>.
   * 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  <code>true</code> if this list has no components;
   *          <code>false</code> 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 <code>equals</code> method. 
   *
   * @param   elem   an object.
   * @return  the index of the first occurrence of the argument in this
   *          list; returns <code>-1</code> 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
   **/

  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 <code>index</code>, and testing for equality using 
   * the <code>equals</code> 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 <code>index</code> or later in the
   *          List; returns <code>-1</code> 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.
   * <p>
   * 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 <em>only</em> 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
   * 		  &lt; 0 || index &gt;= 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 &lt; 0 || index &gt;= 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;
  }