1 /*
2 * Copyright (c) 1997, 2013, Oracle and/or its affiliates. All rights reserved.
3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
4 *
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. Oracle designates this
8 * particular file as subject to the "Classpath" exception as provided
9 * by Oracle 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 Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
22 * or visit www.oracle.com if you need additional information or have any
23 * questions.
24 */
25
26 package java.util;
27
28 /**
29 * Resizable-array implementation of the <tt>List</tt> interface. Implements
30 * all optional list operations, and permits all elements, including
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.)
35 *
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.
42 *
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.
49 *
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 *
54 * <p><strong>Note that this implementation is not synchronized.</strong>
55 * If multiple threads access an <tt>ArrayList</tt> instance concurrently,
56 * and at least one of the threads modifies the list structurally, it
57 * <i>must</i> be synchronized externally. (A structural modification is
58 * any operation that adds or deletes one or more elements, or explicitly
59 * resizes the backing array; merely setting the value of an element is not
60 * a structural modification.) This is typically accomplished by
61 * synchronizing on some object that naturally encapsulates the list.
62 *
63 * If no such object exists, the list should be "wrapped" using the
64 * {@link Collections#synchronizedList Collections.synchronizedList}
65 * method. This is best done at creation time, to prevent accidental
66 * unsynchronized access to the list:<pre>
67 * List list = Collections.synchronizedList(new ArrayList(...));</pre>
68 *
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 * <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 {@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>
88 *
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 * @see Collection
96 * @see List
97 * @see LinkedList
98 * @see Vector
99 * @since 1.2
100 */
101
102 public class ArrayList<E> extends AbstractList<E>
103 implements List<E>, RandomAccess, Cloneable, java.io.Serializable
104 {
105 private static final long serialVersionUID = 8683452581122892189L;
106
107 private static final Object EMPTY_ELEMENTDATA[] = new Object[0];
108
109 /**
110 * The array buffer into which the elements of the ArrayList are stored.
111 * The capacity of the ArrayList is the length of this array buffer.
112 */
113 private transient Object[] elementData;
114
115 /**
116 * initial capacity.
117 */
118 private transient int initialCapacity;
119
120 /**
121 * The size of the ArrayList (the number of elements it contains).
122 *
123 * @serial
124 */
125 private int size;
126
127 /**
128 * Constructs an empty list with the specified initial capacity.
129 *
130 * @param initialCapacity the initial capacity of the list
131 * @throws IllegalArgumentException if the specified initial capacity
132 * is negative
133 */
134 public ArrayList(int initialCapacity) {
135 super();
136 if (initialCapacity < 0)
137 throw new IllegalArgumentException("Illegal Capacity: "+
138 initialCapacity);
139 this.initialCapacity = initialCapacity;
140 elementData = EMPTY_ELEMENTDATA;
141 }
142
143 /**
144 * Constructs an empty list with an initial capacity of ten.
145 */
146 public ArrayList() {
147 this(10);
148 }
149
150 /**
151 * Constructs a list containing the elements of the specified
152 * collection, in the order they are returned by the collection's
153 * iterator.
154 *
155 * @param c the collection whose elements are to be placed into this list
156 * @throws NullPointerException if the specified collection is null
157 */
158 public ArrayList(Collection<? extends E> c) {
159 elementData = c.toArray();
160 size = elementData.length;
161 // c.toArray might (incorrectly) not return Object[] (see 6260652)
162 if (elementData.getClass() != Object[].class)
163 elementData = Arrays.copyOf(elementData, size, Object[].class);
164 }
165
166 /**
167 * Trims the capacity of this <tt>ArrayList</tt> instance to be the
168 * list's current size. An application can use this operation to minimize
169 * the storage of an <tt>ArrayList</tt> instance.
170 */
171 public void trimToSize() {
172 modCount++;
173 if (size < elementData.length) {
174 elementData = Arrays.copyOf(elementData, size);
175 }
176 }
177
178 /**
179 * Increases the capacity of this <tt>ArrayList</tt> instance, if
180 * necessary, to ensure that it can hold at least the number of elements
181 * specified by the minimum capacity argument.
182 *
183 * @param minCapacity the desired minimum capacity
184 */
185 public void ensureCapacity(int minCapacity) {
186 if(elementData != EMPTY_ELEMENTDATA) {
187 if (minCapacity > 0)
188 ensureCapacityInternal(minCapacity);
189 } else {
190 // adjust eventual capacity if requested capacity is larger.
191 initialCapacity = Math.max(initialCapacity, minCapacity);
192 }
193 }
194
195 private void ensureCapacityInternal(int minCapacity) {
196 modCount++;
197 if(elementData == EMPTY_ELEMENTDATA) {
198 minCapacity = Math.max(initialCapacity, minCapacity);
199 }
200
201 // overflow-conscious code
202 if (minCapacity - elementData.length > 0)
203 grow(minCapacity);
204 }
205
206 /**
207 * The maximum size of array to allocate.
208 * Some VMs reserve some header words in an array.
209 * Attempts to allocate larger arrays may result in
210 * OutOfMemoryError: Requested array size exceeds VM limit
211 */
212 private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
213
214 /**
215 * Increases the capacity to ensure that it can hold at least the
216 * number of elements specified by the minimum capacity argument.
217 *
218 * @param minCapacity the desired minimum capacity
219 */
220 private void grow(int minCapacity) {
221 // overflow-conscious code
222 int oldCapacity = elementData.length;
223 int newCapacity = oldCapacity + (oldCapacity >> 1);
224 if (newCapacity - minCapacity < 0)
225 newCapacity = minCapacity;
226 if (newCapacity - MAX_ARRAY_SIZE > 0)
227 newCapacity = hugeCapacity(minCapacity);
228 // minCapacity is usually close to size, so this is a win:
229 elementData = Arrays.copyOf(elementData, newCapacity);
230 }
231
232 private static int hugeCapacity(int minCapacity) {
233 if (minCapacity < 0) // overflow
234 throw new OutOfMemoryError();
235 return (minCapacity > MAX_ARRAY_SIZE) ?
236 Integer.MAX_VALUE :
237 MAX_ARRAY_SIZE;
238 }
239
240 /**
241 * Returns the number of elements in this list.
242 *
243 * @return the number of elements in this list
244 */
245 public int size() {
246 return size;
247 }
248
249 /**
250 * Returns <tt>true</tt> if this list contains no elements.
251 *
252 * @return <tt>true</tt> if this list contains no elements
253 */
254 public boolean isEmpty() {
255 return size == 0;
256 }
257
258 /**
259 * Returns <tt>true</tt> if this list contains the specified element.
260 * More formally, returns <tt>true</tt> if and only if this list contains
261 * at least one element <tt>e</tt> such that
262 * <tt>(o==null ? e==null : o.equals(e))</tt>.
263 *
264 * @param o element whose presence in this list is to be tested
265 * @return <tt>true</tt> if this list contains the specified element
266 */
267 public boolean contains(Object o) {
268 return indexOf(o) >= 0;
269 }
270
271 /**
272 * Returns the index of the first occurrence of the specified element
273 * in this list, or -1 if this list does not contain the element.
274 * More formally, returns the lowest index <tt>i</tt> such that
275 * <tt>(o==null ? get(i)==null : o.equals(get(i)))</tt>,
276 * or -1 if there is no such index.
277 */
278 public int indexOf(Object o) {
279 if (o == null) {
280 for (int i = 0; i < size; i++)
281 if (elementData[i]==null)
282 return i;
283 } else {
284 for (int i = 0; i < size; i++)
285 if (o.equals(elementData[i]))
286 return i;
287 }
288 return -1;
289 }
290
291 /**
292 * Returns the index of the last occurrence of the specified element
293 * in this list, or -1 if this list does not contain the element.
294 * More formally, returns the highest index <tt>i</tt> such that
295 * <tt>(o==null ? get(i)==null : o.equals(get(i)))</tt>,
296 * or -1 if there is no such index.
297 */
298 public int lastIndexOf(Object o) {
299 if (o == null) {
300 for (int i = size-1; i >= 0; i--)
301 if (elementData[i]==null)
302 return i;
303 } else {
304 for (int i = size-1; i >= 0; i--)
305 if (o.equals(elementData[i]))
306 return i;
307 }
308 return -1;
309 }
310
311 /**
312 * Returns a shallow copy of this <tt>ArrayList</tt> instance. (The
313 * elements themselves are not copied.)
314 *
315 * @return a clone of this <tt>ArrayList</tt> instance
316 */
317 public Object clone() {
318 try {
319 ArrayList<?> v = (ArrayList<?>) super.clone();
320 v.elementData = Arrays.copyOf(elementData, size);
321 v.modCount = 0;
322 return v;
323 } catch (CloneNotSupportedException e) {
324 // this shouldn't happen, since we are Cloneable
325 throw new InternalError(e);
326 }
327 }
328
329 /**
330 * Returns an array containing all of the elements in this list
331 * in proper sequence (from first to last element).
332 *
333 * <p>The returned array will be "safe" in that no references to it are
334 * maintained by this list. (In other words, this method must allocate
335 * a new array). The caller is thus free to modify the returned array.
336 *
337 * <p>This method acts as bridge between array-based and collection-based
338 * APIs.
339 *
340 * @return an array containing all of the elements in this list in
341 * proper sequence
342 */
343 public Object[] toArray() {
344 return Arrays.copyOf(elementData, size);
345 }
346
347 /**
348 * Returns an array containing all of the elements in this list in proper
349 * sequence (from first to last element); the runtime type of the returned
350 * array is that of the specified array. If the list fits in the
351 * specified array, it is returned therein. Otherwise, a new array is
352 * allocated with the runtime type of the specified array and the size of
353 * this list.
354 *
355 * <p>If the list fits in the specified array with room to spare
356 * (i.e., the array has more elements than the list), the element in
357 * the array immediately following the end of the collection is set to
358 * <tt>null</tt>. (This is useful in determining the length of the
359 * list <i>only</i> if the caller knows that the list does not contain
360 * any null elements.)
361 *
362 * @param a the array into which the elements of the list are to
363 * be stored, if it is big enough; otherwise, a new array of the
364 * same runtime type is allocated for this purpose.
365 * @return an array containing the elements of the list
366 * @throws ArrayStoreException if the runtime type of the specified array
367 * is not a supertype of the runtime type of every element in
368 * this list
369 * @throws NullPointerException if the specified array is null
370 */
371 @SuppressWarnings("unchecked")
372 public <T> T[] toArray(T[] a) {
373 if (a.length < size)
374 // Make a new array of a's runtime type, but my contents:
375 return (T[]) Arrays.copyOf(elementData, size, a.getClass());
376 System.arraycopy(elementData, 0, a, 0, size);
377 if (a.length > size)
378 a[size] = null;
379 return a;
380 }
381
382 // Positional Access Operations
383
384 @SuppressWarnings("unchecked")
385 E elementData(int index) {
386 return (E) elementData[index];
387 }
388
389 /**
390 * Returns the element at the specified position in this list.
391 *
392 * @param index index of the element to return
393 * @return the element at the specified position in this list
394 * @throws IndexOutOfBoundsException {@inheritDoc}
395 */
396 public E get(int index) {
397 rangeCheck(index);
398
399 return elementData(index);
400 }
401
402 /**
403 * Replaces the element at the specified position in this list with
404 * the specified element.
405 *
406 * @param index index of the element to replace
407 * @param element element to be stored at the specified position
408 * @return the element previously at the specified position
409 * @throws IndexOutOfBoundsException {@inheritDoc}
410 */
411 public E set(int index, E element) {
412 rangeCheck(index);
413
414 E oldValue = elementData(index);
415 elementData[index] = element;
416 return oldValue;
417 }
418
419 /**
420 * Appends the specified element to the end of this list.
421 *
422 * @param e element to be appended to this list
423 * @return <tt>true</tt> (as specified by {@link Collection#add})
424 */
425 public boolean add(E e) {
426 ensureCapacityInternal(size + 1); // Increments modCount!!
427 elementData[size++] = e;
428 return true;
429 }
430
431 /**
432 * Inserts the specified element at the specified position in this
433 * list. Shifts the element currently at that position (if any) and
434 * any subsequent elements to the right (adds one to their indices).
435 *
436 * @param index index at which the specified element is to be inserted
437 * @param element element to be inserted
438 * @throws IndexOutOfBoundsException {@inheritDoc}
439 */
440 public void add(int index, E element) {
441 rangeCheckForAdd(index);
442
443 ensureCapacityInternal(size + 1); // Increments modCount!!
444 System.arraycopy(elementData, index, elementData, index + 1,
445 size - index);
446 elementData[index] = element;
447 size++;
448 }
449
450 /**
451 * Removes the element at the specified position in this list.
452 * Shifts any subsequent elements to the left (subtracts one from their
453 * indices).
454 *
455 * @param index the index of the element to be removed
456 * @return the element that was removed from the list
457 * @throws IndexOutOfBoundsException {@inheritDoc}
458 */
459 public E remove(int index) {
460 rangeCheck(index);
461
462 modCount++;
463 E oldValue = elementData(index);
464
465 int numMoved = size - index - 1;
466 if (numMoved > 0)
467 System.arraycopy(elementData, index+1, elementData, index,
468 numMoved);
469 elementData[--size] = null; // Let gc do its work
470
471 return oldValue;
472 }
473
474 /**
475 * Removes the first occurrence of the specified element from this list,
476 * if it is present. If the list does not contain the element, it is
477 * unchanged. More formally, removes the element with the lowest index
478 * <tt>i</tt> such that
479 * <tt>(o==null ? get(i)==null : o.equals(get(i)))</tt>
480 * (if such an element exists). Returns <tt>true</tt> if this list
481 * contained the specified element (or equivalently, if this list
482 * changed as a result of the call).
483 *
484 * @param o element to be removed from this list, if present
485 * @return <tt>true</tt> if this list contained the specified element
486 */
487 public boolean remove(Object o) {
488 if (o == null) {
489 for (int index = 0; index < size; index++)
490 if (elementData[index] == null) {
491 fastRemove(index);
492 return true;
493 }
494 } else {
495 for (int index = 0; index < size; index++)
496 if (o.equals(elementData[index])) {
497 fastRemove(index);
498 return true;
499 }
500 }
501 return false;
502 }
503
504 /*
505 * Private remove method that skips bounds checking and does not
506 * return the value removed.
507 */
508 private void fastRemove(int index) {
509 modCount++;
510 int numMoved = size - index - 1;
511 if (numMoved > 0)
512 System.arraycopy(elementData, index+1, elementData, index,
513 numMoved);
514 elementData[--size] = null; // Let gc do its work
515 }
516
517 /**
518 * Removes all of the elements from this list. The list will
519 * be empty after this call returns.
520 */
521 public void clear() {
522 modCount++;
523
524 // Let gc do its work
525 for (int i = 0; i < size; i++)
526 elementData[i] = null;
527
528 size = 0;
529 }
530
531 /**
532 * Appends all of the elements in the specified collection to the end of
533 * this list, in the order that they are returned by the
534 * specified collection's Iterator. The behavior of this operation is
535 * undefined if the specified collection is modified while the operation
536 * is in progress. (This implies that the behavior of this call is
537 * undefined if the specified collection is this list, and this
538 * list is nonempty.)
539 *
540 * @param c collection containing elements to be added to this list
541 * @return <tt>true</tt> if this list changed as a result of the call
542 * @throws NullPointerException if the specified collection is null
543 */
544 public boolean addAll(Collection<? extends E> c) {
545 Object[] a = c.toArray();
546 int numNew = a.length;
547 ensureCapacityInternal(size + numNew); // Increments modCount
548 System.arraycopy(a, 0, elementData, size, numNew);
549 size += numNew;
550 return numNew != 0;
551 }
552
553 /**
554 * Inserts all of the elements in the specified collection into this
555 * list, starting at the specified position. Shifts the element
556 * currently at that position (if any) and any subsequent elements to
557 * the right (increases their indices). The new elements will appear
558 * in the list in the order that they are returned by the
559 * specified collection's iterator.
560 *
561 * @param index index at which to insert the first element from the
562 * specified collection
563 * @param c collection containing elements to be added to this list
564 * @return <tt>true</tt> if this list changed as a result of the call
565 * @throws IndexOutOfBoundsException {@inheritDoc}
566 * @throws NullPointerException if the specified collection is null
567 */
568 public boolean addAll(int index, Collection<? extends E> c) {
569 rangeCheckForAdd(index);
570
571 Object[] a = c.toArray();
572 int numNew = a.length;
573 ensureCapacityInternal(size + numNew); // Increments modCount
574
575 int numMoved = size - index;
576 if (numMoved > 0)
577 System.arraycopy(elementData, index, elementData, index + numNew,
578 numMoved);
579
580 System.arraycopy(a, 0, elementData, index, numNew);
581 size += numNew;
582 return numNew != 0;
583 }
584
585 /**
586 * Removes from this list all of the elements whose index is between
587 * {@code fromIndex}, inclusive, and {@code toIndex}, exclusive.
588 * Shifts any succeeding elements to the left (reduces their index).
589 * This call shortens the list by {@code (toIndex - fromIndex)} elements.
590 * (If {@code toIndex==fromIndex}, this operation has no effect.)
591 *
592 * @throws IndexOutOfBoundsException if {@code fromIndex} or
593 * {@code toIndex} is out of range
594 * ({@code fromIndex < 0 ||
595 * fromIndex >= size() ||
596 * toIndex > size() ||
597 * toIndex < fromIndex})
598 */
599 protected void removeRange(int fromIndex, int toIndex) {
600 modCount++;
601 int numMoved = size - toIndex;
602 System.arraycopy(elementData, toIndex, elementData, fromIndex,
603 numMoved);
604
605 // Let gc do its work
606 int newSize = size - (toIndex-fromIndex);
607 while (size != newSize)
608 elementData[--size] = null;
609 }
610
611 /**
612 * Checks if the given index is in range. If not, throws an appropriate
613 * runtime exception. This method does *not* check if the index is
614 * negative: It is always used immediately prior to an array access,
615 * which throws an ArrayIndexOutOfBoundsException if index is negative.
616 */
617 private void rangeCheck(int index) {
618 if (index >= size)
619 throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
620 }
621
622 /**
623 * A version of rangeCheck used by add and addAll.
624 */
625 private void rangeCheckForAdd(int index) {
626 if (index > size || index < 0)
627 throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
628 }
629
630 /**
631 * Constructs an IndexOutOfBoundsException detail message.
632 * Of the many possible refactorings of the error handling code,
633 * this "outlining" performs best with both server and client VMs.
634 */
635 private String outOfBoundsMsg(int index) {
636 return "Index: "+index+", Size: "+size;
637 }
638
639 /**
640 * Removes from this list all of its elements that are contained in the
641 * specified collection.
642 *
643 * @param c collection containing elements to be removed from this list
644 * @return {@code true} if this list changed as a result of the call
645 * @throws ClassCastException if the class of an element of this list
646 * is incompatible with the specified collection
647 * (<a href="Collection.html#optional-restrictions">optional</a>)
648 * @throws NullPointerException if this list contains a null element and the
649 * specified collection does not permit null elements
650 * (<a href="Collection.html#optional-restrictions">optional</a>),
651 * or if the specified collection is null
652 * @see Collection#contains(Object)
653 */
654 public boolean removeAll(Collection<?> c) {
655 return batchRemove(c, false);
656 }
657
658 /**
659 * Retains only the elements in this list that are contained in the
660 * specified collection. In other words, removes from this list all
661 * of its elements that are not contained in the specified collection.
662 *
663 * @param c collection containing elements to be retained in this list
664 * @return {@code true} if this list changed as a result of the call
665 * @throws ClassCastException if the class of an element of this list
666 * is incompatible with the specified collection
667 * (<a href="Collection.html#optional-restrictions">optional</a>)
668 * @throws NullPointerException if this list contains a null element and the
669 * specified collection does not permit null elements
670 * (<a href="Collection.html#optional-restrictions">optional</a>),
671 * or if the specified collection is null
672 * @see Collection#contains(Object)
673 */
674 public boolean retainAll(Collection<?> c) {
675 return batchRemove(c, true);
676 }
677
678 private boolean batchRemove(Collection<?> c, boolean complement) {
679 final Object[] elementData = this.elementData;
680 int r = 0, w = 0;
681 boolean modified = false;
682 try {
683 for (; r < size; r++)
684 if (c.contains(elementData[r]) == complement)
685 elementData[w++] = elementData[r];
686 } finally {
687 // Preserve behavioral compatibility with AbstractCollection,
688 // even if c.contains() throws.
689 if (r != size) {
690 System.arraycopy(elementData, r,
691 elementData, w,
692 size - r);
693 w += size - r;
694 }
695 if (w != size) {
696 for (int i = w; i < size; i++)
697 elementData[i] = null;
698 modCount += size - w;
699 size = w;
700 modified = true;
701 }
702 }
703 return modified;
704 }
705
706 /**
707 * Save the state of the <tt>ArrayList</tt> instance to a stream (that
708 * is, serialize it).
709 *
710 * @serialData The length of the array backing the <tt>ArrayList</tt>
711 * instance is emitted (int), followed by all of its elements
712 * (each an <tt>Object</tt>) in the proper order.
713 */
714 private void writeObject(java.io.ObjectOutputStream s)
715 throws java.io.IOException{
716 // Write out element count, and any hidden stuff
717 int expectedModCount = modCount;
718 s.defaultWriteObject();
719
720 // Write out array length
721 s.writeInt((elementData == EMPTY_ELEMENTDATA) ? initialCapacity : elementData.length);
722
723 // Write out all elements in the proper order.
724 for (int i=0; i<size; i++)
725 s.writeObject(elementData[i]);
726
727 if (modCount != expectedModCount) {
728 throw new ConcurrentModificationException();
729 }
730 }
731
732 /**
733 * Reconstitute the <tt>ArrayList</tt> instance from a stream (that is,
734 * deserialize it).
735 */
736 private void readObject(java.io.ObjectInputStream s)
737 throws java.io.IOException, ClassNotFoundException {
738 // Read in size, and any hidden stuff
739 s.defaultReadObject();
740
741 // Read in array length
742 initialCapacity = s.readInt();
743 elementData = EMPTY_ELEMENTDATA;
744
745 // allocate array based upon size.
746 ensureCapacityInternal(size);
747
748 Object[] a = elementData;
749 // Read in all elements the proper order.
750 for (int i=0; i<size; i++)
751 a[i] = s.readObject();
752 }
753
754 /**
755 * Returns a list iterator over the elements in this list (in proper
756 * sequence), starting at the specified position in the list.
757 * The specified index indicates the first element that would be
758 * returned by an initial call to {@link ListIterator#next next}.
759 * An initial call to {@link ListIterator#previous previous} would
760 * return the element with the specified index minus one.
761 *
762 * <p>The returned list iterator is <a href="#fail-fast"><i>fail-fast</i></a>.
763 *
764 * @throws IndexOutOfBoundsException {@inheritDoc}
765 */
766 public ListIterator<E> listIterator(int index) {
767 if (index < 0 || index > size)
768 throw new IndexOutOfBoundsException("Index: "+index);
769 return new ListItr(index);
770 }
771
772 /**
773 * Returns a list iterator over the elements in this list (in proper
774 * sequence).
775 *
776 * <p>The returned list iterator is <a href="#fail-fast"><i>fail-fast</i></a>.
777 *
778 * @see #listIterator(int)
779 */
780 public ListIterator<E> listIterator() {
781 return new ListItr(0);
782 }
783
784 /**
785 * Returns an iterator over the elements in this list in proper sequence.
786 *
787 * <p>The returned iterator is <a href="#fail-fast"><i>fail-fast</i></a>.
788 *
789 * @return an iterator over the elements in this list in proper sequence
790 */
791 public Iterator<E> iterator() {
792 return new Itr();
793 }
794
795 /**
796 * An optimized version of AbstractList.Itr
797 */
798 private class Itr implements Iterator<E> {
799 int cursor; // index of next element to return
800 int lastRet = -1; // index of last element returned; -1 if no such
801 int expectedModCount = modCount;
802
803 public boolean hasNext() {
804 return cursor != size;
805 }
806
807 @SuppressWarnings("unchecked")
808 public E next() {
809 checkForComodification();
810 int i = cursor;
811 if (i >= size)
812 throw new NoSuchElementException();
813 Object[] elementData = ArrayList.this.elementData;
814 if (i >= elementData.length)
815 throw new ConcurrentModificationException();
816 cursor = i + 1;
817 return (E) elementData[lastRet = i];
818 }
819
820 public void remove() {
821 if (lastRet < 0)
822 throw new IllegalStateException();
823 checkForComodification();
824
825 try {
826 ArrayList.this.remove(lastRet);
827 cursor = lastRet;
828 lastRet = -1;
829 expectedModCount = modCount;
830 } catch (IndexOutOfBoundsException ex) {
831 throw new ConcurrentModificationException();
832 }
833 }
834
835 final void checkForComodification() {
836 if (modCount != expectedModCount)
837 throw new ConcurrentModificationException();
838 }
839 }
840
841 /**
842 * An optimized version of AbstractList.ListItr
843 */
844 private class ListItr extends Itr implements ListIterator<E> {
845 ListItr(int index) {
846 super();
847 cursor = index;
848 }
849
850 public boolean hasPrevious() {
851 return cursor != 0;
852 }
853
854 public int nextIndex() {
855 return cursor;
856 }
857
858 public int previousIndex() {
859 return cursor - 1;
860 }
861
862 @SuppressWarnings("unchecked")
863 public E previous() {
864 checkForComodification();
865 int i = cursor - 1;
866 if (i < 0)
867 throw new NoSuchElementException();
868 Object[] elementData = ArrayList.this.elementData;
869 if (i >= elementData.length)
870 throw new ConcurrentModificationException();
871 cursor = i;
872 return (E) elementData[lastRet = i];
873 }
874
875 public void set(E e) {
876 if (lastRet < 0)
877 throw new IllegalStateException();
878 checkForComodification();
879
880 try {
881 ArrayList.this.set(lastRet, e);
882 } catch (IndexOutOfBoundsException ex) {
883 throw new ConcurrentModificationException();
884 }
885 }
886
887 public void add(E e) {
888 checkForComodification();
889
890 try {
891 int i = cursor;
892 ArrayList.this.add(i, e);
893 cursor = i + 1;
894 lastRet = -1;
895 expectedModCount = modCount;
896 } catch (IndexOutOfBoundsException ex) {
897 throw new ConcurrentModificationException();
898 }
899 }
900 }
901
902 /**
903 * Returns a view of the portion of this list between the specified
904 * {@code fromIndex}, inclusive, and {@code toIndex}, exclusive. (If
905 * {@code fromIndex} and {@code toIndex} are equal, the returned list is
906 * empty.) The returned list is backed by this list, so non-structural
907 * changes in the returned list are reflected in this list, and vice-versa.
908 * The returned list supports all of the optional list operations.
909 *
910 * <p>This method eliminates the need for explicit range operations (of
911 * the sort that commonly exist for arrays). Any operation that expects
912 * a list can be used as a range operation by passing a subList view
913 * instead of a whole list. For example, the following idiom
914 * removes a range of elements from a list:
915 * <pre>
916 * list.subList(from, to).clear();
917 * </pre>
918 * Similar idioms may be constructed for {@link #indexOf(Object)} and
919 * {@link #lastIndexOf(Object)}, and all of the algorithms in the
920 * {@link Collections} class can be applied to a subList.
921 *
922 * <p>The semantics of the list returned by this method become undefined if
923 * the backing list (i.e., this list) is <i>structurally modified</i> in
924 * any way other than via the returned list. (Structural modifications are
925 * those that change the size of this list, or otherwise perturb it in such
926 * a fashion that iterations in progress may yield incorrect results.)
927 *
928 * @throws IndexOutOfBoundsException {@inheritDoc}
929 * @throws IllegalArgumentException {@inheritDoc}
930 */
931 public List<E> subList(int fromIndex, int toIndex) {
932 subListRangeCheck(fromIndex, toIndex, size);
933 return new SubList(this, 0, fromIndex, toIndex);
934 }
935
936 static void subListRangeCheck(int fromIndex, int toIndex, int size) {
937 if (fromIndex < 0)
938 throw new IndexOutOfBoundsException("fromIndex = " + fromIndex);
939 if (toIndex > size)
940 throw new IndexOutOfBoundsException("toIndex = " + toIndex);
941 if (fromIndex > toIndex)
942 throw new IllegalArgumentException("fromIndex(" + fromIndex +
943 ") > toIndex(" + toIndex + ")");
944 }
945
946 private class SubList extends AbstractList<E> implements RandomAccess {
947 private final AbstractList<E> parent;
948 private final int parentOffset;
949 private final int offset;
950 int size;
951
952 SubList(AbstractList<E> parent,
953 int offset, int fromIndex, int toIndex) {
954 this.parent = parent;
955 this.parentOffset = fromIndex;
956 this.offset = offset + fromIndex;
957 this.size = toIndex - fromIndex;
958 this.modCount = ArrayList.this.modCount;
959 }
960
961 public E set(int index, E e) {
962 rangeCheck(index);
963 checkForComodification();
964 E oldValue = ArrayList.this.elementData(offset + index);
965 ArrayList.this.elementData[offset + index] = e;
966 return oldValue;
967 }
968
969 public E get(int index) {
970 rangeCheck(index);
971 checkForComodification();
972 return ArrayList.this.elementData(offset + index);
973 }
974
975 public int size() {
976 checkForComodification();
977 return this.size;
978 }
979
980 public void add(int index, E e) {
981 rangeCheckForAdd(index);
982 checkForComodification();
983 parent.add(parentOffset + index, e);
984 this.modCount = parent.modCount;
985 this.size++;
986 }
987
988 public E remove(int index) {
989 rangeCheck(index);
990 checkForComodification();
991 E result = parent.remove(parentOffset + index);
992 this.modCount = parent.modCount;
993 this.size--;
994 return result;
995 }
996
997 protected void removeRange(int fromIndex, int toIndex) {
998 checkForComodification();
999 parent.removeRange(parentOffset + fromIndex,
1000 parentOffset + toIndex);
1001 this.modCount = parent.modCount;
1002 this.size -= toIndex - fromIndex;
1003 }
1004
1005 public boolean addAll(Collection<? extends E> c) {
1006 return addAll(this.size, c);
1007 }
1008
1009 public boolean addAll(int index, Collection<? extends E> c) {
1010 rangeCheckForAdd(index);
1011 int cSize = c.size();
1012 if (cSize==0)
1013 return false;
1014
1015 checkForComodification();
1016 parent.addAll(parentOffset + index, c);
1017 this.modCount = parent.modCount;
1018 this.size += cSize;
1019 return true;
1020 }
1021
1022 public Iterator<E> iterator() {
1023 return listIterator();
1024 }
1025
1026 public ListIterator<E> listIterator(final int index) {
1027 checkForComodification();
1028 rangeCheckForAdd(index);
1029 final int offset = this.offset;
1030
1031 return new ListIterator<E>() {
1032 int cursor = index;
1033 int lastRet = -1;
1034 int expectedModCount = ArrayList.this.modCount;
1035
1036 public boolean hasNext() {
1037 return cursor != SubList.this.size;
1038 }
1039
1040 @SuppressWarnings("unchecked")
1041 public E next() {
1042 checkForComodification();
1043 int i = cursor;
1044 if (i >= SubList.this.size)
1045 throw new NoSuchElementException();
1046 Object[] elementData = ArrayList.this.elementData;
1047 if (offset + i >= elementData.length)
1048 throw new ConcurrentModificationException();
1049 cursor = i + 1;
1050 return (E) elementData[offset + (lastRet = i)];
1051 }
1052
1053 public boolean hasPrevious() {
1054 return cursor != 0;
1055 }
1056
1057 @SuppressWarnings("unchecked")
1058 public E previous() {
1059 checkForComodification();
1060 int i = cursor - 1;
1061 if (i < 0)
1062 throw new NoSuchElementException();
1063 Object[] elementData = ArrayList.this.elementData;
1064 if (offset + i >= elementData.length)
1065 throw new ConcurrentModificationException();
1066 cursor = i;
1067 return (E) elementData[offset + (lastRet = i)];
1068 }
1069
1070 public int nextIndex() {
1071 return cursor;
1072 }
1073
1074 public int previousIndex() {
1075 return cursor - 1;
1076 }
1077
1078 public void remove() {
1079 if (lastRet < 0)
1080 throw new IllegalStateException();
1081 checkForComodification();
1082
1083 try {
1084 SubList.this.remove(lastRet);
1085 cursor = lastRet;
1086 lastRet = -1;
1087 expectedModCount = ArrayList.this.modCount;
1088 } catch (IndexOutOfBoundsException ex) {
1089 throw new ConcurrentModificationException();
1090 }
1091 }
1092
1093 public void set(E e) {
1094 if (lastRet < 0)
1095 throw new IllegalStateException();
1096 checkForComodification();
1097
1098 try {
1099 ArrayList.this.set(offset + lastRet, e);
1100 } catch (IndexOutOfBoundsException ex) {
1101 throw new ConcurrentModificationException();
1102 }
1103 }
1104
1105 public void add(E e) {
1106 checkForComodification();
1107
1108 try {
1109 int i = cursor;
1110 SubList.this.add(i, e);
1111 cursor = i + 1;
1112 lastRet = -1;
1113 expectedModCount = ArrayList.this.modCount;
1114 } catch (IndexOutOfBoundsException ex) {
1115 throw new ConcurrentModificationException();
1116 }
1117 }
1118
1119 final void checkForComodification() {
1120 if (expectedModCount != ArrayList.this.modCount)
1121 throw new ConcurrentModificationException();
1122 }
1123 };
1124 }
1125
1126 public List<E> subList(int fromIndex, int toIndex) {
1127 subListRangeCheck(fromIndex, toIndex, size);
1128 return new SubList(this, offset, fromIndex, toIndex);
1129 }
1130
1131 private void rangeCheck(int index) {
1132 if (index < 0 || index >= this.size)
1133 throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
1134 }
1135
1136 private void rangeCheckForAdd(int index) {
1137 if (index < 0 || index > this.size)
1138 throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
1139 }
1140
1141 private String outOfBoundsMsg(int index) {
1142 return "Index: "+index+", Size: "+this.size;
1143 }
1144
1145 private void checkForComodification() {
1146 if (ArrayList.this.modCount != this.modCount)
1147 throw new ConcurrentModificationException();
1148 }
1149 }
1150 }