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.20 by jsr166, Fri Apr 21 20:49:03 2006 UTC vs.
Revision 1.28 by jsr166, Mon May 19 00:32:45 2008 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 2006 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;
#	Line 13 | Line 31 | package java.util;
31		* <tt>null</tt>.  In addition to implementing the <tt>List</tt> interface,
32		* this class provides methods to manipulate the size of the array that is
33		* used internally to store the list.  (This class is roughly equivalent to
34	<	* <tt>Vector</tt>, except that it is unsynchronized.)<p>
34	>	* <tt>Vector</tt>, except that it is unsynchronized.)
35		*
36	<	* The <tt>size</tt>, <tt>isEmpty</tt>, <tt>get</tt>, <tt>set</tt>,
36	>	* <p>The <tt>size</tt>, <tt>isEmpty</tt>, <tt>get</tt>, <tt>set</tt>,
37		* <tt>iterator</tt>, and <tt>listIterator</tt> operations run in constant
38		* time.  The <tt>add</tt> operation runs in <i>amortized constant time</i>,
39		* that is, adding n elements requires O(n) time.  All of the other operations
40		* run in linear time (roughly speaking).  The constant factor is low compared
41	<	* to that for the <tt>LinkedList</tt> implementation.<p>
41	>	* to that for the <tt>LinkedList</tt> implementation.
42		*
43	<	* Each <tt>ArrayList</tt> instance has a <i>capacity</i>.  The capacity is
43	>	* <p>Each <tt>ArrayList</tt> instance has a <i>capacity</i>.  The capacity is
44		* the size of the array used to store the elements in the list.  It is always
45		* at least as large as the list size.  As elements are added to an ArrayList,
46		* its capacity grows automatically.  The details of the growth policy are not
47		* specified beyond the fact that adding an element has constant amortized
48	<	* time cost.<p>
48	>	* time cost.
49		*
50	<	* An application can increase the capacity of an <tt>ArrayList</tt> instance
50	>	* <p>An application can increase the capacity of an <tt>ArrayList</tt> instance
51		* before adding a large number of elements using the <tt>ensureCapacity</tt>
52		* operation.  This may reduce the amount of incremental reallocation.
53		*
#	Line 48 | Line 66 | package java.util;
66		* unsynchronized access to the list:<pre>
67		*   List list = Collections.synchronizedList(new ArrayList(...));</pre>
68		*
69	<	* <p>The iterators returned by this class's <tt>iterator</tt> and
70	<	* <tt>listIterator</tt> methods are <i>fail-fast</i>: if the list is
71	<	* structurally modified at any time after the iterator is created, in any way
72	<	* except through the iterator's own <tt>remove</tt> or <tt>add</tt> methods,
73	<	* the iterator will throw a {@link ConcurrentModificationException}.  Thus, in
74	<	* the face of concurrent modification, the iterator fails quickly and cleanly,
75	<	* rather than risking arbitrary, non-deterministic behavior at an undetermined
76	<	* time in the future.<p>
69	>	* <p><a name="fail-fast"/>
70	>	* The iterators returned by this class's {@link #iterator() iterator} and
71	>	* {@link #listIterator(int) listIterator} methods are <em>fail-fast</em>:
72	>	* if the list is structurally modified at any time after the iterator is
73	>	* created, in any way except through the iterator's own
74	>	* {@link ListIterator#remove() remove} or
75	>	* {@link ListIterator#add(Object) add} methods, the iterator will throw a
76	>	* {@link ConcurrentModificationException}.  Thus, in the face of
77	>	* concurrent modification, the iterator fails quickly and cleanly, rather
78	>	* than risking arbitrary, non-deterministic behavior at an undetermined
79	>	* time in the future.
80		*
81	<	* Note that the fail-fast behavior of an iterator cannot be guaranteed
81	>	* <p>Note that the fail-fast behavior of an iterator cannot be guaranteed
82		* as it is, generally speaking, impossible to make any hard guarantees in the
83		* presence of unsynchronized concurrent modification.  Fail-fast iterators
84	<	* throw <tt>ConcurrentModificationException</tt> on a best-effort basis.
84	>	* throw {@code ConcurrentModificationException} on a best-effort basis.
85		* Therefore, it would be wrong to write a program that depended on this
86	<	* exception for its correctness: <i>the fail-fast behavior of iterators
87	<	* should be used only to detect bugs.</i><p>
86	>	* exception for its correctness:  <i>the fail-fast behavior of iterators
87	>	* should be used only to detect bugs.</i>
88		*
89	<	* This class is a member of the
90	<	* <a href="{@docRoot}/../guide/collections/index.html">
89	>	* <p>This class is a member of the
90	>	* <a href="{@docRoot}/../technotes/guides/collections/index.html">
91		* Java Collections Framework</a>.
92		*
93		* @author  Josh Bloch
94		* @author  Neal Gafter
95	<	* @version %I%, %G%
96	<	* @see     Collection
97	<	* @see     List
98	<	* @see     LinkedList
78	<	* @see     Vector
95	>	* @see     Collection
96	>	* @see     List
97	>	* @see     LinkedList
98	>	* @see     Vector
99		* @since   1.2
100		*/
101
#	Line 100 | Line 120 | public class ArrayList<E> extends Abstra
120		/**
121		* Constructs an empty list with the specified initial capacity.
122		*
123	<	* @param initialCapacity the initial capacity of the list
124	<	* @throws IllegalArgumentException if the specified initial capacity
125	<	*         is negative
123	>	* @param   initialCapacity   the initial capacity of the list
124	>	* @exception IllegalArgumentException if the specified initial capacity
125	>	*            is negative
126		*/
127		public ArrayList(int initialCapacity) {
128	<	super();
128	>	super();
129		if (initialCapacity < 0)
130		throw new IllegalArgumentException("Illegal Capacity: "+
131		initialCapacity);
132	<	this.elementData = new Object[initialCapacity];
132	>	this.elementData = new Object[initialCapacity];
133		}
134
135		/**
136		* Constructs an empty list with an initial capacity of ten.
137		*/
138		public ArrayList() {
139	<	this(10);
139	>	this(10);
140		}
141
142		/**
#	Line 128 | Line 148 | public class ArrayList<E> extends Abstra
148		* @throws NullPointerException if the specified collection is null
149		*/
150		public ArrayList(Collection<? extends E> c) {
151	<	elementData = c.toArray();
152	<	size = elementData.length;
153	<	// c.toArray might (incorrectly) not return Object[] (see 6260652)
154	<	if (elementData.getClass() != Object[].class)
155	<	elementData = Arrays.copyOf(elementData, size, Object[].class);
136	<	}
137	<
138	<	private void initFromConcurrentlyMutating(Collection<? extends E> c) {
139	<	elementData = c.toArray();
140	<	size = elementData.length;
141	<	// c.toArray might (incorrectly) not return Object[] (see 6260652)
142	<	if (elementData.getClass() != Object[].class)
143	<	elementData = Arrays.copyOf(elementData, size, Object[].class);
151	>	elementData = c.toArray();
152	>	size = elementData.length;
153	>	// c.toArray might (incorrectly) not return Object[] (see 6260652)
154	>	if (elementData.getClass() != Object[].class)
155	>	elementData = Arrays.copyOf(elementData, size, Object[].class);
156		}
157
146	–	private final static Object UNALLOCATED = new Object();
147	–
158		/**
159		* Trims the capacity of this <tt>ArrayList</tt> instance to be the
160		* list's current size.  An application can use this operation to minimize
161		* the storage of an <tt>ArrayList</tt> instance.
162		*/
163		public void trimToSize() {
164	<	modCount++;
165	<	int oldCapacity = elementData.length;
166	<	if (size < oldCapacity) {
164	>	modCount++;
165	>	int oldCapacity = elementData.length;
166	>	if (size < oldCapacity) {
167		elementData = Arrays.copyOf(elementData, size);
168	<	}
168	>	}
169		}
170
171		/**
#	Line 163 | Line 173 | public class ArrayList<E> extends Abstra
173		* necessary, to ensure that it can hold at least the number of elements
174		* specified by the minimum capacity argument.
175		*
176	<	* @param minCapacity the desired minimum capacity
176	>	* @param   minCapacity   the desired minimum capacity
177		*/
178		public void ensureCapacity(int minCapacity) {
179	<	modCount++;
180	<	if (minCapacity > elementData.length)
181	<	growArray(minCapacity);
182	<	}
183	<
184	<	/**
185	<	* Increases the capacity of the array.
186	<	*
187	<	* @param minCapacity the desired minimum capacity
188	<	*/
179	<	private void growArray(int minCapacity) {
180	<	if (minCapacity < 0) // overflow
181	<	throw new OutOfMemoryError();
182	<	int oldCapacity = elementData.length;
183	<	// Double size if small; else grow by 50%
184	<	int newCapacity = ((oldCapacity < 64) ?
185	<	((oldCapacity + 1) * 2) :
186	<	((oldCapacity / 2) * 3));
187	<	if (newCapacity < 0) // overflow
188	<	newCapacity = Integer.MAX_VALUE;
189	<	if (newCapacity < minCapacity)
190	<	newCapacity = minCapacity;
191	<	elementData = Arrays.copyOf(elementData, newCapacity);
179	>	modCount++;
180	>	int oldCapacity = elementData.length;
181	>	if (minCapacity > oldCapacity) {
182	>	Object oldData[] = elementData;
183	>	int newCapacity = (oldCapacity * 3)/2 + 1;
184	>	if (newCapacity < minCapacity)
185	>	newCapacity = minCapacity;
186	>	// minCapacity is usually close to size, so this is a win:
187	>	elementData = Arrays.copyOf(elementData, newCapacity);
188	>	}
189		}
190
191		/**
#	Line 197 | Line 194 | public class ArrayList<E> extends Abstra
194		* @return the number of elements in this list
195		*/
196		public int size() {
197	<	return size;
197	>	return size;
198		}
199
200		/**
#	Line 206 | Line 203 | public class ArrayList<E> extends Abstra
203		* @return <tt>true</tt> if this list contains no elements
204		*/
205		public boolean isEmpty() {
206	<	return size == 0;
206	>	return size == 0;
207		}
208
209		/**
#	Line 219 | Line 216 | public class ArrayList<E> extends Abstra
216		* @return <tt>true</tt> if this list contains the specified element
217		*/
218		public boolean contains(Object o) {
219	<	return indexOf(o) >= 0;
219	>	return indexOf(o) >= 0;
220		}
221
222		/**
#	Line 230 | Line 227 | public class ArrayList<E> extends Abstra
227		* or -1 if there is no such index.
228		*/
229		public int indexOf(Object o) {
230	<	if (o == null) {
231	<	for (int i = 0; i < size; i++)
232	<	if (elementData[i]==null)
233	<	return i;
234	<	} else {
235	<	for (int i = 0; i < size; i++)
236	<	if (o.equals(elementData[i]))
237	<	return i;
238	<	}
239	<	return -1;
230	>	if (o == null) {
231	>	for (int i = 0; i < size; i++)
232	>	if (elementData[i]==null)
233	>	return i;
234	>	} else {
235	>	for (int i = 0; i < size; i++)
236	>	if (o.equals(elementData[i]))
237	>	return i;
238	>	}
239	>	return -1;
240		}
241
242		/**
#	Line 250 | Line 247 | public class ArrayList<E> extends Abstra
247		* or -1 if there is no such index.
248		*/
249		public int lastIndexOf(Object o) {
250	<	if (o == null) {
251	<	for (int i = size-1; i >= 0; i--)
252	<	if (elementData[i]==null)
253	<	return i;
254	<	} else {
255	<	for (int i = size-1; i >= 0; i--)
256	<	if (o.equals(elementData[i]))
257	<	return i;
258	<	}
259	<	return -1;
250	>	if (o == null) {
251	>	for (int i = size-1; i >= 0; i--)
252	>	if (elementData[i]==null)
253	>	return i;
254	>	} else {
255	>	for (int i = size-1; i >= 0; i--)
256	>	if (o.equals(elementData[i]))
257	>	return i;
258	>	}
259	>	return -1;
260		}
261
262		/**
#	Line 269 | Line 266 | public class ArrayList<E> extends Abstra
266		* @return a clone of this <tt>ArrayList</tt> instance
267		*/
268		public Object clone() {
269	<	try {
270	<	ArrayList<E> v = (ArrayList<E>) super.clone();
271	<	v.elementData = Arrays.copyOf(elementData, size);
272	<	v.modCount = 0;
273	<	return v;
274	<	} catch (CloneNotSupportedException e) {
275	<	// this shouldn't happen, since we are Cloneable
276	<	throw new InternalError();
277	<	}
269	>	try {
270	>	@SuppressWarnings("unchecked")
271	>	ArrayList<E> v = (ArrayList<E>) super.clone();
272	>	v.elementData = Arrays.copyOf(elementData, size);
273	>	v.modCount = 0;
274	>	return v;
275	>	} catch (CloneNotSupportedException e) {
276	>	// this shouldn't happen, since we are Cloneable
277	>	throw new InternalError();
278	>	}
279		}
280
281		/**
#	Line 322 | Line 320 | public class ArrayList<E> extends Abstra
320		*         this list
321		* @throws NullPointerException if the specified array is null
322		*/
323	+	@SuppressWarnings("unchecked")
324		public <T> T[] toArray(T[] a) {
325		if (a.length < size)
326		// Make a new array of a's runtime type, but my contents:
327		return (T[]) Arrays.copyOf(elementData, size, a.getClass());
328	<	System.arraycopy(elementData, 0, a, 0, size);
328	>	System.arraycopy(elementData, 0, a, 0, size);
329		if (a.length > size)
330		a[size] = null;
331		return a;
#	Line 334 | Line 333 | public class ArrayList<E> extends Abstra
333
334		// Positional Access Operations
335
336	<	/**
337	<	* Throws an appropriate exception for indexing errors.
338	<	*/
340	<	private static void indexOutOfBounds(int i, int s) {
341	<	throw new IndexOutOfBoundsException("Index: " + i + ", Size: " + s);
336	>	@SuppressWarnings("unchecked")
337	>	E elementData(int index) {
338	>	return (E) elementData[index];
339		}
340
341		/**
#	Line 349 | Line 346 | public class ArrayList<E> extends Abstra
346		* @throws IndexOutOfBoundsException {@inheritDoc}
347		*/
348		public E get(int index) {
349	<	if (index >= size)
350	<	indexOutOfBounds(index, size);
351	<	return (E) elementData[index];
349	>	rangeCheck(index);
350	>
351	>	return elementData(index);
352		}
353
354		/**
#	Line 364 | Line 361 | public class ArrayList<E> extends Abstra
361		* @throws IndexOutOfBoundsException {@inheritDoc}
362		*/
363		public E set(int index, E element) {
364	<	if (index >= size)
365	<	indexOutOfBounds(index, size);
366	<	E oldValue = (E) elementData[index];
367	<	elementData[index] = element;
368	<	return oldValue;
364	>	rangeCheck(index);
365	>
366	>	E oldValue = elementData(index);
367	>	elementData[index] = element;
368	>	return oldValue;
369		}
370
371		/**
#	Line 378 | Line 375 | public class ArrayList<E> extends Abstra
375		* @return <tt>true</tt> (as specified by {@link Collection#add})
376		*/
377		public boolean add(E e) {
378	<	modCount++;
379	<	int s = size;
380	<	if (s >= elementData.length)
384	<	growArray(s + 1);
385	<	elementData[s] = e;
386	<	size = s + 1;
387	<	return true;
378	>	ensureCapacity(size + 1);  // Increments modCount!!
379	>	elementData[size++] = e;
380	>	return true;
381		}
382
383		/**
#	Line 397 | Line 390 | public class ArrayList<E> extends Abstra
390		* @throws IndexOutOfBoundsException {@inheritDoc}
391		*/
392		public void add(int index, E element) {
393	<	int s = size;
394	<	if (index > s || index < 0)
395	<	indexOutOfBounds(index, s);
396	<	modCount++;
397	<	if (s >= elementData.length)
398	<	growArray(s + 1);
399	<	System.arraycopy(elementData, index,
407	<	elementData, index + 1, s - index);
408	<	elementData[index] = element;
409	<	size = s + 1;
393	>	rangeCheckForAdd(index);
394	>
395	>	ensureCapacity(size+1);  // Increments modCount!!
396	>	System.arraycopy(elementData, index, elementData, index + 1,
397	>	size - index);
398	>	elementData[index] = element;
399	>	size++;
400		}
401
402		/**
#	Line 419 | Line 409 | public class ArrayList<E> extends Abstra
409		* @throws IndexOutOfBoundsException {@inheritDoc}
410		*/
411		public E remove(int index) {
412	<	int s = size - 1;
413	<	if (index > s)
414	<	indexOutOfBounds(index, size);
415	<	modCount++;
416	<	E oldValue = (E) elementData[index];
417	<	int numMoved = s - index;
418	<	if (numMoved > 0)
419	<	System.arraycopy(elementData, index + 1,
420	<	elementData, index, numMoved);
421	<	elementData[s] = null;
422	<	size = s;
423	<	return oldValue;
412	>	rangeCheck(index);
413	>
414	>	modCount++;
415	>	E oldValue = elementData(index);
416	>
417	>	int numMoved = size - index - 1;
418	>	if (numMoved > 0)
419	>	System.arraycopy(elementData, index+1, elementData, index,
420	>	numMoved);
421	>	elementData[--size] = null; // Let gc do its work
422	>
423	>	return oldValue;
424		}
425
426		/**
#	Line 447 | Line 437 | public class ArrayList<E> extends Abstra
437		* @return <tt>true</tt> if this list contained the specified element
438		*/
439		public boolean remove(Object o) {
440	<	if (o == null) {
440	>	if (o == null) {
441	>	for (int index = 0; index < size; index++)
442	>	if (elementData[index] == null) {
443	>	fastRemove(index);
444	>	return true;
445	>	}
446	>	} else {
447		for (int index = 0; index < size; index++)
448	<	if (elementData[index] == null) {
449	<	fastRemove(index);
450	<	return true;
451	<	}
456	<	} else {
457	<	for (int index = 0; index < size; index++)
458	<	if (o.equals(elementData[index])) {
459	<	fastRemove(index);
460	<	return true;
461	<	}
448	>	if (o.equals(elementData[index])) {
449	>	fastRemove(index);
450	>	return true;
451	>	}
452		}
453	<	return false;
453	>	return false;
454		}
455
456		/*
#	Line 481 | Line 471 | public class ArrayList<E> extends Abstra
471		* be empty after this call returns.
472		*/
473		public void clear() {
474	<	modCount++;
474	>	modCount++;
475
476	<	// Let gc do its work
477	<	for (int i = 0; i < size; i++)
478	<	elementData[i] = null;
476	>	// Let gc do its work
477	>	for (int i = 0; i < size; i++)
478	>	elementData[i] = null;
479
480	<	size = 0;
480	>	size = 0;
481		}
482
483		/**
#	Line 504 | Line 494 | public class ArrayList<E> extends Abstra
494		* @throws NullPointerException if the specified collection is null
495		*/
496		public boolean addAll(Collection<? extends E> c) {
497	<	Object[] a = c.toArray();
497	>	Object[] a = c.toArray();
498		int numNew = a.length;
499	<	ensureCapacity(size + numNew);  // Increments modCount
499	>	ensureCapacity(size + numNew);  // Increments modCount
500		System.arraycopy(a, 0, elementData, size, numNew);
501		size += numNew;
502	<	return numNew != 0;
502	>	return numNew != 0;
503		}
504
505		/**
#	Line 528 | Line 518 | public class ArrayList<E> extends Abstra
518		* @throws NullPointerException if the specified collection is null
519		*/
520		public boolean addAll(int index, Collection<? extends E> c) {
521	<	if (index > size || index < 0)
532	<	indexOutOfBounds(index, size);
521	>	rangeCheckForAdd(index);
522
523	<	Object[] a = c.toArray();
524	<	int numNew = a.length;
525	<	ensureCapacity(size + numNew);  // Increments modCount
526	<
527	<	int numMoved = size - index;
528	<	if (numMoved > 0)
529	<	System.arraycopy(elementData, index, elementData, index + numNew,
530	<	numMoved);
523	>	Object[] a = c.toArray();
524	>	int numNew = a.length;
525	>	ensureCapacity(size + numNew);  // Increments modCount
526	>
527	>	int numMoved = size - index;
528	>	if (numMoved > 0)
529	>	System.arraycopy(elementData, index, elementData, index + numNew,
530	>	numMoved);
531
532		System.arraycopy(a, 0, elementData, index, numNew);
533	<	size += numNew;
534	<	return numNew != 0;
533	>	size += numNew;
534	>	return numNew != 0;
535		}
536
537		/**
538		* Removes from this list all of the elements whose index is between
539	<	* <tt>fromIndex</tt>, inclusive, and <tt>toIndex</tt>, exclusive.
539	>	* {@code fromIndex}, inclusive, and {@code toIndex}, exclusive.
540		* Shifts any succeeding elements to the left (reduces their index).
541	<	* This call shortens the list by <tt>(toIndex - fromIndex)</tt> elements.
542	<	* (If <tt>toIndex==fromIndex</tt>, this operation has no effect.)
541	>	* This call shortens the list by {@code (toIndex - fromIndex)} elements.
542	>	* (If {@code toIndex==fromIndex}, this operation has no effect.)
543		*
544	<	* @param fromIndex index of first element to be removed
545	<	* @param toIndex index after last element to be removed
546	<	* @throws IndexOutOfBoundsException if fromIndex or toIndex out of
547	<	*              range (fromIndex &lt; 0 || fromIndex &gt;= size() || toIndex
548	<	*              &gt; size() || toIndex &lt; fromIndex)
544	>	* @throws IndexOutOfBoundsException if {@code fromIndex} or
545	>	*         {@code toIndex} is out of range
546	>	*         ({@code fromIndex < 0 ||
547	>	*          fromIndex >= size() ||
548	>	*          toIndex > size() ||
549	>	*          toIndex < fromIndex})
550		*/
551		protected void removeRange(int fromIndex, int toIndex) {
552	<	modCount++;
553	<	int numMoved = size - toIndex;
552	>	modCount++;
553	>	int numMoved = size - toIndex;
554		System.arraycopy(elementData, toIndex, elementData, fromIndex,
555		numMoved);
556
557	<	// Let gc do its work
558	<	int newSize = size - (toIndex-fromIndex);
559	<	while (size != newSize)
560	<	elementData[--size] = null;
557	>	// Let gc do its work
558	>	int newSize = size - (toIndex-fromIndex);
559	>	while (size != newSize)
560	>	elementData[--size] = null;
561	>	}
562	>
563	>	/**
564	>	* Checks if the given index is in range.  If not, throws an appropriate
565	>	* runtime exception.  This method does *not* check if the index is
566	>	* negative: It is always used immediately prior to an array access,
567	>	* which throws an ArrayIndexOutOfBoundsException if index is negative.
568	>	*/
569	>	private void rangeCheck(int index) {
570	>	if (index >= size)
571	>	throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
572	>	}
573	>
574	>	/**
575	>	* A version of rangeCheck used by add and addAll.
576	>	*/
577	>	private void rangeCheckForAdd(int index) {
578	>	if (index > size || index < 0)
579	>	throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
580	>	}
581	>
582	>	/**
583	>	* Constructs an IndexOutOfBoundsException detail message.
584	>	* Of the many possible refactorings of the error handling code,
585	>	* this "outlining" performs best with both server and client VMs.
586	>	*/
587	>	private String outOfBoundsMsg(int index) {
588	>	return "Index: "+index+", Size: "+size;
589	>	}
590	>
591	>	/**
592	>	* Removes from this list all of its elements that are contained in the
593	>	* specified collection.
594	>	*
595	>	* @param c collection containing elements to be removed from this list
596	>	* @return {@code true} if this list changed as a result of the call
597	>	* @throws ClassCastException if the class of an element of this list
598	>	*         is incompatible with the specified collection (optional)
599	>	* @throws NullPointerException if this list contains a null element and the
600	>	*         specified collection does not permit null elements (optional),
601	>	*         or if the specified collection is null
602	>	* @see Collection#contains(Object)
603	>	*/
604	>	public boolean removeAll(Collection<?> c) {
605	>	return batchRemove(c, false);
606	>	}
607	>
608	>	/**
609	>	* Retains only the elements in this list that are contained in the
610	>	* specified collection.  In other words, removes from this list all
611	>	* of its elements that are not contained in the specified collection.
612	>	*
613	>	* @param c collection containing elements to be retained in this list
614	>	* @return {@code true} if this list changed as a result of the call
615	>	* @throws ClassCastException if the class of an element of this list
616	>	*         is incompatible with the specified collection (optional)
617	>	* @throws NullPointerException if this list contains a null element and the
618	>	*         specified collection does not permit null elements (optional),
619	>	*         or if the specified collection is null
620	>	* @see Collection#contains(Object)
621	>	*/
622	>	public boolean retainAll(Collection<?> c) {
623	>	return batchRemove(c, true);
624	>	}
625	>
626	>	private boolean batchRemove(Collection<?> c, boolean complement) {
627	>	final Object[] elementData = this.elementData;
628	>	int r = 0, w = 0;
629	>	boolean modified = false;
630	>	try {
631	>	for (; r < size; r++)
632	>	if (c.contains(elementData[r]) == complement)
633	>	elementData[w++] = elementData[r];
634	>	} finally {
635	>	// Preserve behavioral compatibility with AbstractCollection,
636	>	// even if c.contains() throws.
637	>	if (r != size) {
638	>	System.arraycopy(elementData, r,
639	>	elementData, w,
640	>	size - r);
641	>	w += size - r;
642	>	}
643	>	if (w != size) {
644	>	for (int i = w; i < size; i++)
645	>	elementData[i] = null;
646	>	modCount += size - w;
647	>	size = w;
648	>	modified = true;
649	>	}
650	>	}
651	>	return modified;
652		}
653
654		/**
#	Line 580 | Line 661 | public class ArrayList<E> extends Abstra
661		*/
662		private void writeObject(java.io.ObjectOutputStream s)
663		throws java.io.IOException{
664	<	// Write out element count, and any hidden stuff
665	<	int expectedModCount = modCount;
666	<	s.defaultWriteObject();
664	>	// Write out element count, and any hidden stuff
665	>	int expectedModCount = modCount;
666	>	s.defaultWriteObject();
667
668		// Write out array length
669		s.writeInt(elementData.length);
670
671	<	// Write out all elements in the proper order.
672	<	for (int i=0; i<size; i++)
671	>	// Write out all elements in the proper order.
672	>	for (int i=0; i<size; i++)
673		s.writeObject(elementData[i]);
674
675	<	if (expectedModCount != modCount) {
675	>	if (modCount != expectedModCount) {
676		throw new ConcurrentModificationException();
677		}
678
#	Line 603 | Line 684 | public class ArrayList<E> extends Abstra
684		*/
685		private void readObject(java.io.ObjectInputStream s)
686		throws java.io.IOException, ClassNotFoundException {
687	<	// Read in size, and any hidden stuff
688	<	s.defaultReadObject();
687	>	// Read in size, and any hidden stuff
688	>	s.defaultReadObject();
689
690		// Read in array length and allocate array
691		int arrayLength = s.readInt();
692		Object[] a = elementData = new Object[arrayLength];
693
694	<	// Read in all elements in the proper order.
695	<	for (int i=0; i<size; i++)
694	>	// Read in all elements in the proper order.
695	>	for (int i=0; i<size; i++)
696		a[i] = s.readObject();
697		}
698	+
699	+	/**
700	+	* Returns a list iterator over the elements in this list (in proper
701	+	* sequence), starting at the specified position in the list.
702	+	* The specified index indicates the first element that would be
703	+	* returned by an initial call to {@link ListIterator#next next}.
704	+	* An initial call to {@link ListIterator#previous previous} would
705	+	* return the element with the specified index minus one.
706	+	*
707	+	* <p>The returned list iterator is <a href="#fail-fast"><i>fail-fast</i></a>.
708	+	*
709	+	* @throws IndexOutOfBoundsException {@inheritDoc}
710	+	*/
711	+	public ListIterator<E> listIterator(int index) {
712	+	if (index < 0 || index > size)
713	+	throw new IndexOutOfBoundsException("Index: "+index);
714	+	return new ListItr(index);
715	+	}
716	+
717	+	/**
718	+	* Returns a list iterator over the elements in this list (in proper
719	+	* sequence).
720	+	*
721	+	* <p>The returned list iterator is <a href="#fail-fast"><i>fail-fast</i></a>.
722	+	*
723	+	* @see #listIterator(int)
724	+	*/
725	+	public ListIterator<E> listIterator() {
726	+	return new ListItr(0);
727	+	}
728	+
729	+	/**
730	+	* Returns an iterator over the elements in this list in proper sequence.
731	+	*
732	+	* <p>The returned iterator is <a href="#fail-fast"><i>fail-fast</i></a>.
733	+	*
734	+	* @return an iterator over the elements in this list in proper sequence
735	+	*/
736	+	public Iterator<E> iterator() {
737	+	return new Itr();
738	+	}
739	+
740	+	/**
741	+	* An optimized version of AbstractList.Itr
742	+	*/
743	+	private class Itr implements Iterator<E> {
744	+	int cursor;       // index of next element to return
745	+	int lastRet = -1; // index of last element returned; -1 if no such
746	+	int expectedModCount = modCount;
747	+
748	+	public boolean hasNext() {
749	+	return cursor != size;
750	+	}
751	+
752	+	@SuppressWarnings("unchecked")
753	+	public E next() {
754	+	checkForComodification();
755	+	int i = cursor;
756	+	if (i >= size)
757	+	throw new NoSuchElementException();
758	+	Object[] elementData = ArrayList.this.elementData;
759	+	if (i >= elementData.length)
760	+	throw new ConcurrentModificationException();
761	+	cursor = i + 1;
762	+	return (E) elementData[lastRet = i];
763	+	}
764	+
765	+	public void remove() {
766	+	if (lastRet < 0)
767	+	throw new IllegalStateException();
768	+	checkForComodification();
769	+
770	+	try {
771	+	ArrayList.this.remove(lastRet);
772	+	cursor = lastRet;
773	+	lastRet = -1;
774	+	expectedModCount = modCount;
775	+	} catch (IndexOutOfBoundsException ex) {
776	+	throw new ConcurrentModificationException();
777	+	}
778	+	}
779	+
780	+	final void checkForComodification() {
781	+	if (modCount != expectedModCount)
782	+	throw new ConcurrentModificationException();
783	+	}
784	+	}
785	+
786	+	/**
787	+	* An optimized version of AbstractList.ListItr
788	+	*/
789	+	private class ListItr extends Itr implements ListIterator<E> {
790	+	ListItr(int index) {
791	+	super();
792	+	cursor = index;
793	+	}
794	+
795	+	public boolean hasPrevious() {
796	+	return cursor != 0;
797	+	}
798	+
799	+	public int nextIndex() {
800	+	return cursor;
801	+	}
802	+
803	+	public int previousIndex() {
804	+	return cursor - 1;
805	+	}
806	+
807	+	@SuppressWarnings("unchecked")
808	+	public E previous() {
809	+	checkForComodification();
810	+	int i = cursor - 1;
811	+	if (i < 0)
812	+	throw new NoSuchElementException();
813	+	Object[] elementData = ArrayList.this.elementData;
814	+	if (i >= elementData.length)
815	+	throw new ConcurrentModificationException();
816	+	cursor = i;
817	+	return (E) elementData[lastRet = i];
818	+	}
819	+
820	+	public void set(E e) {
821	+	if (lastRet < 0)
822	+	throw new IllegalStateException();
823	+	checkForComodification();
824	+
825	+	try {
826	+	ArrayList.this.set(lastRet, e);
827	+	} catch (IndexOutOfBoundsException ex) {
828	+	throw new ConcurrentModificationException();
829	+	}
830	+	}
831	+
832	+	public void add(E e) {
833	+	checkForComodification();
834	+
835	+	try {
836	+	int i = cursor;
837	+	ArrayList.this.add(i, e);
838	+	cursor = i + 1;
839	+	lastRet = -1;
840	+	expectedModCount = modCount;
841	+	} catch (IndexOutOfBoundsException ex) {
842	+	throw new ConcurrentModificationException();
843	+	}
844	+	}
845	+	}
846	+
847	+	/**
848	+	* Returns a view of the portion of this list between the specified
849	+	* {@code fromIndex}, inclusive, and {@code toIndex}, exclusive.  (If
850	+	* {@code fromIndex} and {@code toIndex} are equal, the returned list is
851	+	* empty.)  The returned list is backed by this list, so non-structural
852	+	* changes in the returned list are reflected in this list, and vice-versa.
853	+	* The returned list supports all of the optional list operations.
854	+	*
855	+	* <p>This method eliminates the need for explicit range operations (of
856	+	* the sort that commonly exist for arrays).  Any operation that expects
857	+	* a list can be used as a range operation by passing a subList view
858	+	* instead of a whole list.  For example, the following idiom
859	+	* removes a range of elements from a list:
860	+	* <pre>
861	+	*      list.subList(from, to).clear();
862	+	* </pre>
863	+	* Similar idioms may be constructed for {@link #indexOf(Object)} and
864	+	* {@link #lastIndexOf(Object)}, and all of the algorithms in the
865	+	* {@link Collections} class can be applied to a subList.
866	+	*
867	+	* <p>The semantics of the list returned by this method become undefined if
868	+	* the backing list (i.e., this list) is <i>structurally modified</i> in
869	+	* any way other than via the returned list.  (Structural modifications are
870	+	* those that change the size of this list, or otherwise perturb it in such
871	+	* a fashion that iterations in progress may yield incorrect results.)
872	+	*
873	+	* @throws IndexOutOfBoundsException {@inheritDoc}
874	+	* @throws IllegalArgumentException {@inheritDoc}
875	+	*/
876	+	public List<E> subList(int fromIndex, int toIndex) {
877	+	subListRangeCheck(fromIndex, toIndex, size);
878	+	return new SubList(this, 0, fromIndex, toIndex);
879	+	}
880	+
881	+	static void subListRangeCheck(int fromIndex, int toIndex, int size) {
882	+	if (fromIndex < 0)
883	+	throw new IndexOutOfBoundsException("fromIndex = " + fromIndex);
884	+	if (toIndex > size)
885	+	throw new IndexOutOfBoundsException("toIndex = " + toIndex);
886	+	if (fromIndex > toIndex)
887	+	throw new IllegalArgumentException("fromIndex(" + fromIndex +
888	+	") > toIndex(" + toIndex + ")");
889	+	}
890	+
891	+	private class SubList extends AbstractList<E> implements RandomAccess {
892	+	private final AbstractList<E> parent;
893	+	private final int parentOffset;
894	+	private final int offset;
895	+	int size;
896	+
897	+	SubList(AbstractList<E> parent,
898	+	int offset, int fromIndex, int toIndex) {
899	+	this.parent = parent;
900	+	this.parentOffset = fromIndex;
901	+	this.offset = offset + fromIndex;
902	+	this.size = toIndex - fromIndex;
903	+	this.modCount = ArrayList.this.modCount;
904	+	}
905	+
906	+	public E set(int index, E e) {
907	+	rangeCheck(index);
908	+	checkForComodification();
909	+	E oldValue = ArrayList.this.elementData(offset + index);
910	+	ArrayList.this.elementData[offset + index] = e;
911	+	return oldValue;
912	+	}
913	+
914	+	public E get(int index) {
915	+	rangeCheck(index);
916	+	checkForComodification();
917	+	return ArrayList.this.elementData(offset + index);
918	+	}
919	+
920	+	public int size() {
921	+	checkForComodification();
922	+	return this.size;
923	+	}
924	+
925	+	public void add(int index, E e) {
926	+	rangeCheckForAdd(index);
927	+	checkForComodification();
928	+	parent.add(parentOffset + index, e);
929	+	this.modCount = parent.modCount;
930	+	this.size++;
931	+	}
932	+
933	+	public E remove(int index) {
934	+	rangeCheck(index);
935	+	checkForComodification();
936	+	E result = parent.remove(parentOffset + index);
937	+	this.modCount = parent.modCount;
938	+	this.size--;
939	+	return result;
940	+	}
941	+
942	+	protected void removeRange(int fromIndex, int toIndex) {
943	+	checkForComodification();
944	+	parent.removeRange(parentOffset + fromIndex,
945	+	parentOffset + toIndex);
946	+	this.modCount = parent.modCount;
947	+	this.size -= toIndex - fromIndex;
948	+	}
949	+
950	+	public boolean addAll(Collection<? extends E> c) {
951	+	return addAll(this.size, c);
952	+	}
953	+
954	+	public boolean addAll(int index, Collection<? extends E> c) {
955	+	rangeCheckForAdd(index);
956	+	int cSize = c.size();
957	+	if (cSize==0)
958	+	return false;
959	+
960	+	checkForComodification();
961	+	parent.addAll(parentOffset + index, c);
962	+	this.modCount = parent.modCount;
963	+	this.size += cSize;
964	+	return true;
965	+	}
966	+
967	+	public Iterator<E> iterator() {
968	+	return listIterator();
969	+	}
970	+
971	+	public ListIterator<E> listIterator(final int index) {
972	+	checkForComodification();
973	+	rangeCheckForAdd(index);
974	+	final int offset = this.offset;
975	+
976	+	return new ListIterator<E>() {
977	+	int cursor = index;
978	+	int lastRet = -1;
979	+	int expectedModCount = ArrayList.this.modCount;
980	+
981	+	public boolean hasNext() {
982	+	return cursor != SubList.this.size;
983	+	}
984	+
985	+	@SuppressWarnings("unchecked")
986	+	public E next() {
987	+	checkForComodification();
988	+	int i = cursor;
989	+	if (i >= SubList.this.size)
990	+	throw new NoSuchElementException();
991	+	Object[] elementData = ArrayList.this.elementData;
992	+	if (offset + i >= elementData.length)
993	+	throw new ConcurrentModificationException();
994	+	cursor = i + 1;
995	+	return (E) elementData[offset + (lastRet = i)];
996	+	}
997	+
998	+	public boolean hasPrevious() {
999	+	return cursor != 0;
1000	+	}
1001	+
1002	+	@SuppressWarnings("unchecked")
1003	+	public E previous() {
1004	+	checkForComodification();
1005	+	int i = cursor - 1;
1006	+	if (i < 0)
1007	+	throw new NoSuchElementException();
1008	+	Object[] elementData = ArrayList.this.elementData;
1009	+	if (offset + i >= elementData.length)
1010	+	throw new ConcurrentModificationException();
1011	+	cursor = i;
1012	+	return (E) elementData[offset + (lastRet = i)];
1013	+	}
1014	+
1015	+	public int nextIndex() {
1016	+	return cursor;
1017	+	}
1018	+
1019	+	public int previousIndex() {
1020	+	return cursor - 1;
1021	+	}
1022	+
1023	+	public void remove() {
1024	+	if (lastRet < 0)
1025	+	throw new IllegalStateException();
1026	+	checkForComodification();
1027	+
1028	+	try {
1029	+	SubList.this.remove(lastRet);
1030	+	cursor = lastRet;
1031	+	lastRet = -1;
1032	+	expectedModCount = ArrayList.this.modCount;
1033	+	} catch (IndexOutOfBoundsException ex) {
1034	+	throw new ConcurrentModificationException();
1035	+	}
1036	+	}
1037	+
1038	+	public void set(E e) {
1039	+	if (lastRet < 0)
1040	+	throw new IllegalStateException();
1041	+	checkForComodification();
1042	+
1043	+	try {
1044	+	ArrayList.this.set(offset + lastRet, e);
1045	+	} catch (IndexOutOfBoundsException ex) {
1046	+	throw new ConcurrentModificationException();
1047	+	}
1048	+	}
1049	+
1050	+	public void add(E e) {
1051	+	checkForComodification();
1052	+
1053	+	try {
1054	+	int i = cursor;
1055	+	SubList.this.add(i, e);
1056	+	cursor = i + 1;
1057	+	lastRet = -1;
1058	+	expectedModCount = ArrayList.this.modCount;
1059	+	} catch (IndexOutOfBoundsException ex) {
1060	+	throw new ConcurrentModificationException();
1061	+	}
1062	+	}
1063	+
1064	+	final void checkForComodification() {
1065	+	if (expectedModCount != ArrayList.this.modCount)
1066	+	throw new ConcurrentModificationException();
1067	+	}
1068	+	};
1069	+	}
1070	+
1071	+	public List<E> subList(int fromIndex, int toIndex) {
1072	+	subListRangeCheck(fromIndex, toIndex, size);
1073	+	return new SubList(this, offset, fromIndex, toIndex);
1074	+	}
1075	+
1076	+	private void rangeCheck(int index) {
1077	+	if (index < 0 || index >= this.size)
1078	+	throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
1079	+	}
1080	+
1081	+	private void rangeCheckForAdd(int index) {
1082	+	if (index < 0 || index > this.size)
1083	+	throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
1084	+	}
1085	+
1086	+	private String outOfBoundsMsg(int index) {
1087	+	return "Index: "+index+", Size: "+this.size;
1088	+	}
1089	+
1090	+	private void checkForComodification() {
1091	+	if (ArrayList.this.modCount != this.modCount)
1092	+	throw new ConcurrentModificationException();
1093	+	}
1094	+	}
1095		}

Diff Legend

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