copyonwritearraylist.java

采用JAVA开发

  /**
   * 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.
   *
   * @exception IndexOutOfBoundsException index out of range (index
   * 		  &lt; 0 || index &gt;= size()).
   * @param index the index of the element to removed.
   */
  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 <code>e</code> such that <code>(o==null ? e==null :
   * o.equals(e))</code>, 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 fromIndex index after last element to be removed.
   * @exception IndexOutOfBoundsException fromIndex or toIndex out of
   *		  range (fromIndex &lt; 0 || fromIndex &gt;= size() || toIndex
   *		  &gt; size() || toIndex &lt; 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.
   * <p>
   * 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.
   * <p>
   *
   * @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
   *		  &lt; 0 || index &gt; 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.
   */
  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).
   *
   * @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).
   */
  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++) {