arraylist.java

这是一款基于PlaceLab软件开发的导航系统中间件的客户端程序.

/* ArrayList.java -- JDK1.2's answer to Vector; this is an array-backed
 implementation of the List interface
 Copyright (C) 1998, 1999, 2000, 2001, 2004 Free Software Foundation, Inc.

 This file is part of GNU Classpath.

 GNU Classpath is free software; you can redistribute it and/or modify
 it under the terms of the GNU General Public License as published by
 the Free Software Foundation; either version 2, or (at your option)
 any later version.

 GNU Classpath 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 for more details.

 You should have received a copy of the GNU General Public License
 along with GNU Classpath; see the file COPYING.  If not, write to the
 Free Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
 02111-1307 USA.

 Linking this library statically or dynamically with other modules is
 making a combined work based on this library.  Thus, the terms and
 conditions of the GNU General Public License cover the whole
 combination.

 As a special exception, the copyright holders of this library give you
 permission to link this library with independent modules to produce an
 executable, regardless of the license terms of these independent
 modules, and to copy and distribute the resulting executable under
 terms of your choice, provided that you also meet, for each linked
 independent module, the terms and conditions of the license of that
 module.  An independent module is a module which is not derived from
 or based on this library.  If you modify this library, you may extend
 this exception to your version of the library, but you are not
 obligated to do so.  If you do not wish to do so, delete this
 exception statement from your version. */

package org.placelab.collections;

//import java.io.IOException;
//import java.io.ObjectInputStream;
//import java.io.ObjectOutputStream;
//import java.io.Serializable;

/**
 * An array-backed implementation of the List interface. This implements all
 * optional list operations, and permits null elements, so that it is better
 * than Vector, which it replaces. Random access is roughly constant time, and
 * iteration is roughly linear time, so it is nice and fast, with less overhead
 * than a LinkedList.
 * <p>
 * 
 * Each list has a capacity, and as the array reaches that capacity it is
 * automatically transferred to a larger array. You also have access to
 * ensureCapacity and trimToSize to control the backing array's size, avoiding
 * reallocation or wasted memory.
 * <p>
 * 
 * ArrayList is not synchronized, so if you need multi-threaded access, consider
 * using: <br>
 * <code>List l = Collections.synchronizedList(new ArrayList(...));</code>
 * <p>
 * 
 * The iterators are <i>fail-fast </i>, meaning that any structural
 * modification, except for <code>remove()</code> called on the iterator
 * itself, cause the iterator to throw a {@link ConcurrentModificationException}
 * rather than exhibit non-deterministic behavior.
 * 
 * 
 * 
 * 
 * @see Collection
 * @see List
 * @see LinkedList
 * @see AbstractList
 */
public class ArrayList extends AbstractList implements List, RandomAccess,
		Cloneable {//, Serializable {
	/**
	 * Compatible with JDK 1.2
	 */
	private static final long serialVersionUID = 8683452581122892189L;

	/**
	 * The default capacity for new ArrayLists.
	 */
	private static final int DEFAULT_CAPACITY = 16;

	/**
	 * The number of elements in this list.
	 * 
	 * @serial the list size
	 */
	private int size;

	/**
	 * Where the data is stored.
	 */
	private transient Object[] data;

	/**
	 * Construct a new ArrayList with the supplied initial capacity.
	 * 
	 * @param capacity
	 *            initial capacity of this ArrayList
	 * @throws IllegalArgumentException
	 *             if capacity is negative
	 */
	public ArrayList(int capacity) {
		// Must explicitly check, to get correct exception.
		if (capacity < 0)
			throw new IllegalArgumentException();
		data = new Object[capacity];
	}

	/**
	 * Construct a new ArrayList with the default capcity (16).
	 */
	public ArrayList() {
		this(DEFAULT_CAPACITY);
	}

	/**
	 * Construct a new ArrayList, and initialize it with the elements in the
	 * supplied Collection. The initial capacity is 110% of the Collection's
	 * size.
	 * 
	 * @param c
	 *            the collection whose elements will initialize this list
	 * @throws NullPointerException
	 *             if c is null
	 */
	public ArrayList(Collection c) {
		this((int) (c.size() * 1.1f));
		addAll(c);
	}

	/**
	 * Trims the capacity of this List to be equal to its size; a memory saver.
	 */
	public void trimToSize() {
		// Not a structural change from the perspective of iterators on this
		// list,
		// so don't update modCount.
		if (size != data.length) {
			Object[] newData = new Object[size];
			System.arraycopy(data, 0, newData, 0, size);
			data = newData;
		}
	}

	/**
	 * Guarantees that this list will have at least enough capacity to hold
	 * minCapacity elements. This implementation will grow the list to
	 * max(current * 2, minCapacity) if (minCapacity &gt; current). The JCL says
	 * explictly that "this method increases its capacity to minCap", while the
	 * JDK 1.3 online docs specify that the list will grow to at least the size
	 * specified.
	 * 
	 * @param minCapacity
	 *            the minimum guaranteed capacity
	 */
	public void ensureCapacity(int minCapacity) {
		int current = data.length;

		if (minCapacity > current) {
			Object[] newData = new Object[Math.max(current * 2, minCapacity)];
			System.arraycopy(data, 0, newData, 0, size);
			data = newData;
		}
	}

	/**
	 * Returns the number of elements in this list.
	 * 
	 * @return the list size
	 */
	public int size() {
		return size;
	}

	/**
	 * Checks if the list is empty.
	 * 
	 * @return true if there are no elements
	 */
	public boolean isEmpty() {
		return size == 0;
	}

	/**
	 * Returns true iff element is in this ArrayList.
	 * 
	 * @param e
	 *            the element whose inclusion in the List is being tested
	 * @return true if the list contains e
	 */
	public boolean contains(Object e) {
		return indexOf(e) != -1;
	}

	/**
	 * Returns the lowest index at which element appears in this List, or -1 if
	 * it does not appear.
	 * 
	 * @param e
	 *            the element whose inclusion in the List is being tested
	 * @return the index where e was found
	 */
	public int indexOf(Object e) {
		for (int i = 0; i < size; i++)
			if (equals(e, data[i]))
				return i;
		return -1;
	}

	/**
	 * Returns the highest index at which element appears in this List, or -1 if
	 * it does not appear.
	 * 
	 * @param e
	 *            the element whose inclusion in the List is being tested
	 * @return the index where e was found
	 */
	public int lastIndexOf(Object e) {
		for (int i = size - 1; i >= 0; i--)
			if (equals(e, data[i]))
				return i;
		return -1;
	}

	/**
	 * Creates a shallow copy of this ArrayList (elements are not cloned).
	 * 
	 * @return the cloned object
	 */
	public Object pclone() {
		ArrayList clone = null;
		try {
			clone = (ArrayList) super.pclone();
			
			if(data != null) {
			    clone.data = new Object[data.length];
			    for(int i=0;i<data.length;i++) clone.data[i]=data[i];
			}
			//clone.data = (Object[]) data.pclone();
		} catch (CloneNotSupportedException e) {
			// Impossible to get here.
		}
		return clone;
	}

	/**
	 * Returns an Object array containing all of the elements in this ArrayList.
	 * The array is independent of this list.
	 * 
	 * @return an array representation of this list
	 */
	public Object[] toArray() {
		Object[] array = new Object[size];
		System.arraycopy(data, 0, array, 0, size);
		return array;
	}

	/**
	 * Returns an Array whose component type is the runtime component type of
	 * the passed-in Array. The returned Array is populated with all of the
	 * elements in this ArrayList. If the passed-in Array is not large enough to
	 * store all of the elements in this List, a new Array will be created and
	 * returned; if the passed-in Array is <i>larger </i> than the size of this
	 * List, then size() index will be set to null.
	 * 
	 * @param a
	 *            the passed-in Array
	 * @return an array representation of this list
	 * @throws ArrayStoreException
	 *             if the runtime type of a does not allow an element in this
	 *             list
	 * @throws NullPointerException
	 *             if a is null
	 */
	public void toArray(Object[] a) {
		if (a.length < size)
			throw new ArrayIndexOutOfBoundsException(
					"this array is too small to hold the collection");
		else if (a.length > size)
			a[size] = null;
		System.arraycopy(data, 0, a, 0, size);
	}

	/**
	 * Retrieves the element at the user-supplied index.
	 * 
	 * @param index
	 *            the index of the element we are fetching
	 * @throws IndexOutOfBoundsException
	 *             if index &lt; 0 || index &gt;= size()
	 */