copyonwritearraylist.java

Wicket一个开发Java Web应用程序框架。它使得开发web应用程序变得容易而轻松。 Wicket利用一个POJO data beans组件使得它可以与任何持久层技术相结合。

/*
  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 org.apache.wicket.util.concurrent;

import java.util.AbstractList;
import java.util.Collection;
import java.util.ConcurrentModificationException;
import java.util.Iterator;
import java.util.List;
import java.util.ListIterator;
import java.util.NoSuchElementException;

/**
 * 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
{

	private static final long serialVersionUID = 1L;

	/**
	 * The held array. Directly access only within synchronized methods
	 */
	protected transient Object[] array_;

	/**
	 * Accessor to the array intended to be called from within unsynchronized read-only methods
	 * 
	 * @return The internal array
	 */
	protected synchronized Object[] array()
	{
		return array_;
	}

	/**
	 * Constructs an empty list
	 * 
	 */
	public CopyOnWriteArrayList()
	{
		array_ = new Object[0];
	}

	/**
	 * Constructs an list containing the elements of the specified Collection, in the order they are
	 * returned by the Collection's iterator.
	 * 
	 * @param c
	 *            The collection to get the objects from.
	 */
	public CopyOnWriteArrayList(Collection c)
	{
		array_ = new Object[c.size()];
		Iterator i = c.iterator();
		int size = 0;
		while (i.hasNext())
		{
			array_[size++] = i.next();
		}
	}

	/**
	 * Create a new CopyOnWriteArrayList holding a copy of given array
	 * 
	 * @param toCopyIn
	 *            the array. A copy of this array is used as the internal array.
	 */
	public CopyOnWriteArrayList(Object[] toCopyIn)
	{
		copyIn(toCopyIn, 0, toCopyIn.length);
	}

	/**
	 * Replace the held array with a copy of the <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 occurrence 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
	 * 
	 * @param elem
	 * @param elementData
	 * @param len
	 * @return The index that is found. -1 if not found
	 */

	protected static int indexOf(Object elem, Object[] elementData, int len)
	{
		if (elem == null)
		{
			for (int i = 0; i < len; i++)
			{
				if (elementData[i] == null)
				{
					return i;
				}
			}
		}
		else
		{
			for (int i = 0; i < len; i++)
			{
				if (elem.equals(elementData[i]))
				{
					return i;
				}
			}
		}
		return -1;
	}

	/**
	 * Searches for the first occurrence 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;
	}

	/**
	 * 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;