ViewVC Help

View File | Revision Log | Show Annotations | Download File | Root Listing

root/jsr166/jsr166/src/main/java/util/ArrayList.java

Comparing jsr166/src/main/java/util/ArrayList.java (file contents):
Revision 1.4 by jsr166, Sat Nov 26 03:12:10 2005 UTC vs.
Revision 1.24 by jsr166, Sun May 20 07:54:01 2007 UTC

#	Line 1 | Line 1
1		/*
2	<	* %W% %E%
2	>	* Copyright 1997-2007 Sun Microsystems, Inc.  All Rights Reserved.
3	>	* DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
4		*
5	<	* Copyright 2005 Sun Microsystems, Inc. All rights reserved.
6	<	* SUN PROPRIETARY/CONFIDENTIAL. Use is subject to license terms.
5	>	* This code is free software; you can redistribute it and/or modify it
6	>	* under the terms of the GNU General Public License version 2 only, as
7	>	* published by the Free Software Foundation.  Sun designates this
8	>	* particular file as subject to the "Classpath" exception as provided
9	>	* by Sun in the LICENSE file that accompanied this code.
10	>	*
11	>	* This code is distributed in the hope that it will be useful, but WITHOUT
12	>	* ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
13	>	* FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
14	>	* version 2 for more details (a copy is included in the LICENSE file that
15	>	* accompanied this code).
16	>	*
17	>	* You should have received a copy of the GNU General Public License version
18	>	* 2 along with this work; if not, write to the Free Software Foundation,
19	>	* Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
20	>	*
21	>	* Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa Clara,
22	>	* CA 95054 USA or visit www.sun.com if you need additional information or
23	>	* have any questions.
24		*/
25
26		package java.util;
9	–	import java.util.*; // for javadoc (till 6280605 is fixed)
27
28		/**
29		* Resizable-array implementation of the <tt>List</tt> interface.  Implements
#	Line 67 | Line 84 | import java.util.*; // for javadoc (till
84		* should be used only to detect bugs.</i><p>
85		*
86		* This class is a member of the
87	<	* <a href="{@docRoot}/../guide/collections/index.html">
87	>	* <a href="{@docRoot}/../technotes/guides/collections/index.html">
88		* Java Collections Framework</a>.
89		*
90		* @author  Josh Bloch
#	Line 101 | Line 118 | public class ArrayList<E> extends Abstra
118		/**
119		* Constructs an empty list with the specified initial capacity.
120		*
121	<	* @param   initialCapacity   the initial capacity of the list
122	<	* @exception IllegalArgumentException if the specified initial capacity
123	<	*            is negative
121	>	* @param initialCapacity the initial capacity of the list
122	>	* @throws IllegalArgumentException if the specified initial capacity
123	>	*         is negative
124		*/
125		public ArrayList(int initialCapacity) {
126		super();
#	Line 123 | Line 140 | public class ArrayList<E> extends Abstra
140		/**
141		* Constructs a list containing the elements of the specified
142		* collection, in the order they are returned by the collection's
143	<	* iterator.  The <tt>ArrayList</tt> instance has an initial capacity of
127	<	* 110% the size of the specified collection.
143	>	* iterator.
144		*
145		* @param c the collection whose elements are to be placed into this list
146		* @throws NullPointerException if the specified collection is null
147		*/
148		public ArrayList(Collection<? extends E> c) {
133	–	int size = c.size();
134	–	// 10% for growth
135	–	int cap = ((size/10)+1)*11;
136	–	if (cap > 0) {
137	–	Object[] a = new Object[cap];
138	–	a[size] = a[size+1] = UNALLOCATED;
139	–	Object[] b = c.toArray(a);
140	–	if (b[size] == null && b[size+1] == UNALLOCATED) {
141	–	b[size+1] = null;
142	–	elementData = b;
143	–	this.size = size;
144	–	return;
145	–	}
146	–	}
147	–	initFromConcurrentlyMutating(c);
148	–	}
149	–
150	–	private void initFromConcurrentlyMutating(Collection<? extends E> c) {
149		elementData = c.toArray();
150		size = elementData.length;
151		// c.toArray might (incorrectly) not return Object[] (see 6260652)
#	Line 155 | Line 153 | public class ArrayList<E> extends Abstra
153		elementData = Arrays.copyOf(elementData, size, Object[].class);
154		}
155
158	–	private final static Object UNALLOCATED = new Object();
159	–
156		/**
157		* Trims the capacity of this <tt>ArrayList</tt> instance to be the
158		* list's current size.  An application can use this operation to minimize
#	Line 175 | Line 171 | public class ArrayList<E> extends Abstra
171		* necessary, to ensure that it can hold at least the number of elements
172		* specified by the minimum capacity argument.
173		*
174	<	* @param   minCapacity   the desired minimum capacity
174	>	* @param minCapacity the desired minimum capacity
175		*/
176		public void ensureCapacity(int minCapacity) {
177		modCount++;
#	Line 184 | Line 180 | public class ArrayList<E> extends Abstra
180		}
181
182		/**
183	<	* Increase the capacity of the array.
184	<	* @param   minCapacity   the desired minimum capacity
183	>	* Increases the capacity of the array.
184	>	*
185	>	* @param minCapacity the desired minimum capacity
186		*/
187		private void growArray(int minCapacity) {
188	+	if (minCapacity < 0) // overflow
189	+	throw new OutOfMemoryError();
190		int oldCapacity = elementData.length;
191		// Double size if small; else grow by 50%
192	<	int newCapacity = ((oldCapacity < 64)?
193	<	(oldCapacity * 2):
194	<	((oldCapacity * 3)/2 + 1));
192	>	int newCapacity = ((oldCapacity < 64) ?
193	>	((oldCapacity + 1) * 2) :
194	>	((oldCapacity / 2) * 3));
195	>	if (newCapacity < 0) // overflow
196	>	newCapacity = Integer.MAX_VALUE;
197		if (newCapacity < minCapacity)
198		newCapacity = minCapacity;
199		elementData = Arrays.copyOf(elementData, newCapacity);
#	Line 342 | Line 343 | public class ArrayList<E> extends Abstra
343		// Positional Access Operations
344
345		/**
346	<	* Create and return an appropriate exception for indexing errors
346	>	* Throws an appropriate exception for indexing errors.
347		*/
348	<	private static IndexOutOfBoundsException rangeException(int i, int s) {
349	<	return new IndexOutOfBoundsException("Index: " + i + ", Size: " + s);
348	>	private static void indexOutOfBounds(int i, int s) {
349	>	throw new IndexOutOfBoundsException("Index: " + i + ", Size: " + s);
350		}
351
351	–	// Positional Access Operations
352	–
352		/**
353		* Returns the element at the specified position in this list.
354		*
#	Line 359 | Line 358 | public class ArrayList<E> extends Abstra
358		*/
359		public E get(int index) {
360		if (index >= size)
361	<	throw rangeException(index, size);
362	<	return (E)elementData[index];
361	>	indexOutOfBounds(index, size);
362	>	return (E) elementData[index];
363		}
364
365		/**
#	Line 374 | Line 373 | public class ArrayList<E> extends Abstra
373		*/
374		public E set(int index, E element) {
375		if (index >= size)
376	<	throw rangeException(index, size);
378	<
376	>	indexOutOfBounds(index, size);
377		E oldValue = (E) elementData[index];
378		elementData[index] = element;
379		return oldValue;
#	Line 388 | Line 386 | public class ArrayList<E> extends Abstra
386		* @return <tt>true</tt> (as specified by {@link Collection#add})
387		*/
388		public boolean add(E e) {
389	<	++modCount;
390	<	int s = size++;
389	>	modCount++;
390	>	int s = size;
391		if (s >= elementData.length)
392		growArray(s + 1);
393		elementData[s] = e;
394	<	return true;
394	>	size = s + 1;
395	>	return true;
396		}
397
398		/**
#	Line 408 | Line 407 | public class ArrayList<E> extends Abstra
407		public void add(int index, E element) {
408		int s = size;
409		if (index > s || index < 0)
410	<	throw rangeException(index, s);
411	<	++modCount;
413	<	size = s + 1;
410	>	indexOutOfBounds(index, s);
411	>	modCount++;
412		if (s >= elementData.length)
413		growArray(s + 1);
414	<	System.arraycopy(elementData, index, elementData, index + 1,
415	<	s - index);
414	>	System.arraycopy(elementData, index,
415	>	elementData, index + 1, s - index);
416		elementData[index] = element;
417	+	size = s + 1;
418		}
419
420		/**
#	Line 430 | Line 429 | public class ArrayList<E> extends Abstra
429		public E remove(int index) {
430		int s = size - 1;
431		if (index > s)
432	<	throw rangeException(index, size);
434	<	size = s;
432	>	indexOutOfBounds(index, size);
433		modCount++;
434	<	Object oldValue = elementData[index];
434	>	E oldValue = (E) elementData[index];
435		int numMoved = s - index;
436		if (numMoved > 0)
437	<	System.arraycopy(elementData, index+1, elementData, index,
438	<	numMoved);
439	<	elementData[s] = null; // forget removed element
440	<	return (E)oldValue;
437	>	System.arraycopy(elementData, index + 1,
438	>	elementData, index, numMoved);
439	>	elementData[s] = null;
440	>	size = s;
441	>	return oldValue;
442		}
443
444		/**
#	Line 538 | Line 537 | public class ArrayList<E> extends Abstra
537		*/
538		public boolean addAll(int index, Collection<? extends E> c) {
539		if (index > size || index < 0)
540	<	throw new IndexOutOfBoundsException(
542	<	"Index: " + index + ", Size: " + size);
540	>	indexOutOfBounds(index, size);
541
542		Object[] a = c.toArray();
543		int numNew = a.length;
#	Line 601 | Line 599 | public class ArrayList<E> extends Abstra
599		for (int i=0; i<size; i++)
600		s.writeObject(elementData[i]);
601
602	<	if (modCount != expectedModCount) {
602	>	if (expectedModCount != modCount) {
603		throw new ConcurrentModificationException();
604		}
605
#	Line 624 | Line 622 | public class ArrayList<E> extends Abstra
622		for (int i=0; i<size; i++)
623		a[i] = s.readObject();
624		}
627	–
628	–
629	–	/**
630	–	* Returns a list-iterator of the elements in this list (in proper
631	–	* sequence), starting at the specified position in the list.
632	–	* Obeys the general contract of <tt>List.listIterator(int)</tt>.<p>
633	–	*
634	–	* The list-iterator is <i>fail-fast</i>: if the list is structurally
635	–	* modified at any time after the Iterator is created, in any way except
636	–	* through the list-iterator's own <tt>remove</tt> or <tt>add</tt>
637	–	* methods, the list-iterator will throw a
638	–	* <tt>ConcurrentModificationException</tt>.  Thus, in the face of
639	–	* concurrent modification, the iterator fails quickly and cleanly, rather
640	–	* than risking arbitrary, non-deterministic behavior at an undetermined
641	–	* time in the future.
642	–	*
643	–	* @param index index of the first element to be returned from the
644	–	*              list-iterator (by a call to <tt>next</tt>)
645	–	* @return a ListIterator of the elements in this list (in proper
646	–	*         sequence), starting at the specified position in the list
647	–	* @throws IndexOutOfBoundsException {@inheritDoc}
648	–	* @see List#listIterator(int)
649	–	*/
650	–	public ListIterator<E> listIterator(int index) {
651	–	if (index < 0 || index > size)
652	–	throw new IndexOutOfBoundsException("Index: "+index);
653	–	return new ArrayListIterator(index);
654	–	}
655	–
656	–	/**
657	–	* Returns an iterator over the elements in this list in proper sequence.
658	–	*
659	–	* @return an iterator over the elements in this list in proper sequence
660	–	*/
661	–	public Iterator<E> iterator() {
662	–	return new ArrayListIterator(0);
663	–	}
664	–
665	–	/**
666	–	* A streamlined version of AbstractList.Itr
667	–	*/
668	–	final class ArrayListIterator implements ListIterator<E> {
669	–	int cursor;           // index of next element to return;
670	–	int lastRet;          // index of last element, or -1 if no such
671	–	int expectedModCount; // to check for CME
672	–
673	–	ArrayListIterator(int index) {
674	–	cursor = index;
675	–	lastRet = -1;
676	–	expectedModCount = modCount;
677	–	}
678	–
679	–	public boolean hasNext() {
680	–	return cursor < size;
681	–	}
682	–
683	–	public boolean hasPrevious() {
684	–	return cursor > 0;
685	–	}
686	–
687	–	public int nextIndex() {
688	–	return cursor;
689	–	}
690	–
691	–	public int previousIndex() {
692	–	return cursor - 1;
693	–	}
694	–
695	–	public E next() {
696	–	if (expectedModCount == modCount) {
697	–	int i = cursor;
698	–	if (i < size) {
699	–	try {
700	–	E e = (E)elementData[i];
701	–	lastRet = i;
702	–	cursor = i + 1;
703	–	return e;
704	–	} catch (IndexOutOfBoundsException fallthrough) {
705	–	}
706	–	}
707	–	}
708	–	// Prefer reporting CME if applicable on failures
709	–	if (expectedModCount == modCount)
710	–	throw new NoSuchElementException();
711	–	throw new ConcurrentModificationException();
712	–	}
713	–
714	–	public E previous() {
715	–	if (expectedModCount == modCount) {
716	–	int i = cursor - 1;
717	–	if (i < size) {
718	–	try {
719	–	E e = (E)elementData[i];
720	–	lastRet = i;
721	–	cursor = i;
722	–	return e;
723	–	} catch (IndexOutOfBoundsException fallthrough) {
724	–	}
725	–	}
726	–	}
727	–	if (expectedModCount == modCount)
728	–	throw new NoSuchElementException();
729	–	throw new ConcurrentModificationException();
730	–	}
731	–
732	–	public void remove() {
733	–	if (lastRet < 0)
734	–	throw new IllegalStateException();
735	–	if (modCount != expectedModCount)
736	–	throw new ConcurrentModificationException();
737	–	ArrayList.this.remove(lastRet);
738	–	if (lastRet < cursor)
739	–	cursor--;
740	–	lastRet = -1;
741	–	expectedModCount = modCount;
742	–	}
743	–
744	–	public void set(E e) {
745	–	if (lastRet < 0)
746	–	throw new IllegalStateException();
747	–	if (modCount != expectedModCount)
748	–	throw new ConcurrentModificationException();
749	–	ArrayList.this.set(lastRet, e);
750	–	expectedModCount = modCount;
751	–	}
752	–
753	–	public void add(E e) {
754	–	if (modCount != expectedModCount)
755	–	throw new ConcurrentModificationException();
756	–	ArrayList.this.add(cursor++, e);
757	–	lastRet = -1;
758	–	expectedModCount = modCount;
759	–	}
760	–	}
761	–
625		}

Diff Legend

–	Removed lines
+	Added lines
<	Changed lines
>	Changed lines