1 /* 2 * Copyright (C) 2014 The Android Open Source Project 3 * Copyright (c) 1997, 2013, Oracle and/or its affiliates. All rights reserved. 4 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. 5 * 6 * This code is free software; you can redistribute it and/or modify it 7 * under the terms of the GNU General Public License version 2 only, as 8 * published by the Free Software Foundation. Oracle designates this 9 * particular file as subject to the "Classpath" exception as provided 10 * by Oracle in the LICENSE file that accompanied this code. 11 * 12 * This code is distributed in the hope that it will be useful, but WITHOUT 13 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 14 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 15 * version 2 for more details (a copy is included in the LICENSE file that 16 * accompanied this code). 17 * 18 * You should have received a copy of the GNU General Public License version 19 * 2 along with this work; if not, write to the Free Software Foundation, 20 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. 21 * 22 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA 23 * or visit www.oracle.com if you need additional information or have any 24 * questions. 25 */ 26 27 package java.util; 28 29 import java.util.function.Consumer; 30 import java.util.function.Predicate; 31 import java.util.function.UnaryOperator; 32 33 /** 34 * Resizable-array implementation of the <tt>List</tt> interface. Implements 35 * all optional list operations, and permits all elements, including 36 * <tt>null</tt>. In addition to implementing the <tt>List</tt> interface, 37 * this class provides methods to manipulate the size of the array that is 38 * used internally to store the list. (This class is roughly equivalent to 39 * <tt>Vector</tt>, except that it is unsynchronized.) 40 * 41 * <p>The <tt>size</tt>, <tt>isEmpty</tt>, <tt>get</tt>, <tt>set</tt>, 42 * <tt>iterator</tt>, and <tt>listIterator</tt> operations run in constant 43 * time. The <tt>add</tt> operation runs in <i>amortized constant time</i>, 44 * that is, adding n elements requires O(n) time. All of the other operations 45 * run in linear time (roughly speaking). The constant factor is low compared 46 * to that for the <tt>LinkedList</tt> implementation. 47 * 48 * <p>Each <tt>ArrayList</tt> instance has a <i>capacity</i>. The capacity is 49 * the size of the array used to store the elements in the list. It is always 50 * at least as large as the list size. As elements are added to an ArrayList, 51 * its capacity grows automatically. The details of the growth policy are not 52 * specified beyond the fact that adding an element has constant amortized 53 * time cost. 54 * 55 * <p>An application can increase the capacity of an <tt>ArrayList</tt> instance 56 * before adding a large number of elements using the <tt>ensureCapacity</tt> 57 * operation. This may reduce the amount of incremental reallocation. 58 * 59 * <p><strong>Note that this implementation is not synchronized.</strong> 60 * If multiple threads access an <tt>ArrayList</tt> instance concurrently, 61 * and at least one of the threads modifies the list structurally, it 62 * <i>must</i> be synchronized externally. (A structural modification is 63 * any operation that adds or deletes one or more elements, or explicitly 64 * resizes the backing array; merely setting the value of an element is not 65 * a structural modification.) This is typically accomplished by 66 * synchronizing on some object that naturally encapsulates the list. 67 * 68 * If no such object exists, the list should be "wrapped" using the 69 * {@link Collections#synchronizedList Collections.synchronizedList} 70 * method. This is best done at creation time, to prevent accidental 71 * unsynchronized access to the list:<pre> 72 * List list = Collections.synchronizedList(new ArrayList(...));</pre> 73 * 74 * <p><a name="fail-fast"> 75 * The iterators returned by this class's {@link #iterator() iterator} and 76 * {@link #listIterator(int) listIterator} methods are <em>fail-fast</em>:</a> 77 * if the list is structurally modified at any time after the iterator is 78 * created, in any way except through the iterator's own 79 * {@link ListIterator#remove() remove} or 80 * {@link ListIterator#add(Object) add} methods, the iterator will throw a 81 * {@link ConcurrentModificationException}. Thus, in the face of 82 * concurrent modification, the iterator fails quickly and cleanly, rather 83 * than risking arbitrary, non-deterministic behavior at an undetermined 84 * time in the future. 85 * 86 * <p>Note that the fail-fast behavior of an iterator cannot be guaranteed 87 * as it is, generally speaking, impossible to make any hard guarantees in the 88 * presence of unsynchronized concurrent modification. Fail-fast iterators 89 * throw {@code ConcurrentModificationException} on a best-effort basis. 90 * Therefore, it would be wrong to write a program that depended on this 91 * exception for its correctness: <i>the fail-fast behavior of iterators 92 * should be used only to detect bugs.</i> 93 * 94 * <p>This class is a member of the 95 * <a href="{@docRoot}openjdk-redirect.html?v=8&path=/technotes/guides/collections/index.html"> 96 * Java Collections Framework</a>. 97 * 98 * @author Josh Bloch 99 * @author Neal Gafter 100 * @see Collection 101 * @see List 102 * @see LinkedList 103 * @see Vector 104 * @since 1.2 105 */ 106 /* 107 * Android-changed: 108 * - AOSP commit 3be987f0f18648b3c532c8b89d09505e18594241 109 * Inline for improved performance: 110 * - checkForComodification 111 * - elementData() 112 * - rangeCheck() 113 * - rangeCheckForAdd() 114 * - AOSP commit b10b2a3ab693cfd6156d06ffe4e00ce69b9c9194 115 * Fix ConcurrentModificationException in ArrayList iterators. 116 * - AOSP commit a68b1a5ba82ef8cc19aafdce7d9c7f9631943f84 117 * Throw AIOOBE when toIndex < fromIndex. 118 */ 119 public class ArrayList<E> extends AbstractList<E> 120 implements List<E>, RandomAccess, Cloneable, java.io.Serializable 121 { 122 private static final long serialVersionUID = 8683452581122892189L; 123 124 /** 125 * Default initial capacity. 126 */ 127 private static final int DEFAULT_CAPACITY = 10; 128 129 /** 130 * Shared empty array instance used for empty instances. 131 */ 132 private static final Object[] EMPTY_ELEMENTDATA = {}; 133 134 /** 135 * Shared empty array instance used for default sized empty instances. We 136 * distinguish this from EMPTY_ELEMENTDATA to know how much to inflate when 137 * first element is added. 138 */ 139 private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}; 140 141 /** 142 * The array buffer into which the elements of the ArrayList are stored. 143 * The capacity of the ArrayList is the length of this array buffer. Any 144 * empty ArrayList with elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA 145 * will be expanded to DEFAULT_CAPACITY when the first element is added. 146 */ 147 // Android-note: Also accessed from java.util.Collections 148 transient Object[] elementData; // non-private to simplify nested class access 149 150 /** 151 * The size of the ArrayList (the number of elements it contains). 152 * 153 * @serial 154 */ 155 private int size; 156 157 /** 158 * Constructs an empty list with the specified initial capacity. 159 * 160 * @param initialCapacity the initial capacity of the list 161 * @throws IllegalArgumentException if the specified initial capacity 162 * is negative 163 */ ArrayList(int initialCapacity)164 public ArrayList(int initialCapacity) { 165 if (initialCapacity > 0) { 166 this.elementData = new Object[initialCapacity]; 167 } else if (initialCapacity == 0) { 168 this.elementData = EMPTY_ELEMENTDATA; 169 } else { 170 throw new IllegalArgumentException("Illegal Capacity: "+ 171 initialCapacity); 172 } 173 } 174 175 /** 176 * Constructs an empty list with an initial capacity of ten. 177 */ ArrayList()178 public ArrayList() { 179 this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA; 180 } 181 182 /** 183 * Constructs a list containing the elements of the specified 184 * collection, in the order they are returned by the collection's 185 * iterator. 186 * 187 * @param c the collection whose elements are to be placed into this list 188 * @throws NullPointerException if the specified collection is null 189 */ ArrayList(Collection<? extends E> c)190 public ArrayList(Collection<? extends E> c) { 191 elementData = c.toArray(); 192 if ((size = elementData.length) != 0) { 193 // c.toArray might (incorrectly) not return Object[] (see 6260652) 194 if (elementData.getClass() != Object[].class) 195 elementData = Arrays.copyOf(elementData, size, Object[].class); 196 } else { 197 // replace with empty array. 198 this.elementData = EMPTY_ELEMENTDATA; 199 } 200 } 201 202 /** 203 * Trims the capacity of this <tt>ArrayList</tt> instance to be the 204 * list's current size. An application can use this operation to minimize 205 * the storage of an <tt>ArrayList</tt> instance. 206 */ trimToSize()207 public void trimToSize() { 208 modCount++; 209 if (size < elementData.length) { 210 elementData = (size == 0) 211 ? EMPTY_ELEMENTDATA 212 : Arrays.copyOf(elementData, size); 213 } 214 } 215 216 /** 217 * Increases the capacity of this <tt>ArrayList</tt> instance, if 218 * necessary, to ensure that it can hold at least the number of elements 219 * specified by the minimum capacity argument. 220 * 221 * @param minCapacity the desired minimum capacity 222 */ ensureCapacity(int minCapacity)223 public void ensureCapacity(int minCapacity) { 224 int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA) 225 // any size if not default element table 226 ? 0 227 // larger than default for default empty table. It's already 228 // supposed to be at default size. 229 : DEFAULT_CAPACITY; 230 231 if (minCapacity > minExpand) { 232 ensureExplicitCapacity(minCapacity); 233 } 234 } 235 ensureCapacityInternal(int minCapacity)236 private void ensureCapacityInternal(int minCapacity) { 237 if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { 238 minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity); 239 } 240 241 ensureExplicitCapacity(minCapacity); 242 } 243 ensureExplicitCapacity(int minCapacity)244 private void ensureExplicitCapacity(int minCapacity) { 245 modCount++; 246 247 // overflow-conscious code 248 if (minCapacity - elementData.length > 0) 249 grow(minCapacity); 250 } 251 252 /** 253 * The maximum size of array to allocate. 254 * Some VMs reserve some header words in an array. 255 * Attempts to allocate larger arrays may result in 256 * OutOfMemoryError: Requested array size exceeds VM limit 257 */ 258 private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8; 259 260 /** 261 * Increases the capacity to ensure that it can hold at least the 262 * number of elements specified by the minimum capacity argument. 263 * 264 * @param minCapacity the desired minimum capacity 265 */ grow(int minCapacity)266 private void grow(int minCapacity) { 267 // overflow-conscious code 268 int oldCapacity = elementData.length; 269 int newCapacity = oldCapacity + (oldCapacity >> 1); 270 if (newCapacity - minCapacity < 0) 271 newCapacity = minCapacity; 272 if (newCapacity - MAX_ARRAY_SIZE > 0) 273 newCapacity = hugeCapacity(minCapacity); 274 // minCapacity is usually close to size, so this is a win: 275 elementData = Arrays.copyOf(elementData, newCapacity); 276 } 277 hugeCapacity(int minCapacity)278 private static int hugeCapacity(int minCapacity) { 279 if (minCapacity < 0) // overflow 280 throw new OutOfMemoryError(); 281 return (minCapacity > MAX_ARRAY_SIZE) ? 282 Integer.MAX_VALUE : 283 MAX_ARRAY_SIZE; 284 } 285 286 /** 287 * Returns the number of elements in this list. 288 * 289 * @return the number of elements in this list 290 */ size()291 public int size() { 292 return size; 293 } 294 295 /** 296 * Returns <tt>true</tt> if this list contains no elements. 297 * 298 * @return <tt>true</tt> if this list contains no elements 299 */ isEmpty()300 public boolean isEmpty() { 301 return size == 0; 302 } 303 304 /** 305 * Returns <tt>true</tt> if this list contains the specified element. 306 * More formally, returns <tt>true</tt> if and only if this list contains 307 * at least one element <tt>e</tt> such that 308 * <tt>(o==null ? e==null : o.equals(e))</tt>. 309 * 310 * @param o element whose presence in this list is to be tested 311 * @return <tt>true</tt> if this list contains the specified element 312 */ contains(Object o)313 public boolean contains(Object o) { 314 return indexOf(o) >= 0; 315 } 316 317 /** 318 * Returns the index of the first occurrence of the specified element 319 * in this list, or -1 if this list does not contain the element. 320 * More formally, returns the lowest index <tt>i</tt> such that 321 * <tt>(o==null ? get(i)==null : o.equals(get(i)))</tt>, 322 * or -1 if there is no such index. 323 */ indexOf(Object o)324 public int indexOf(Object o) { 325 if (o == null) { 326 for (int i = 0; i < size; i++) 327 if (elementData[i]==null) 328 return i; 329 } else { 330 for (int i = 0; i < size; i++) 331 if (o.equals(elementData[i])) 332 return i; 333 } 334 return -1; 335 } 336 337 /** 338 * Returns the index of the last occurrence of the specified element 339 * in this list, or -1 if this list does not contain the element. 340 * More formally, returns the highest index <tt>i</tt> such that 341 * <tt>(o==null ? get(i)==null : o.equals(get(i)))</tt>, 342 * or -1 if there is no such index. 343 */ lastIndexOf(Object o)344 public int lastIndexOf(Object o) { 345 if (o == null) { 346 for (int i = size-1; i >= 0; i--) 347 if (elementData[i]==null) 348 return i; 349 } else { 350 for (int i = size-1; i >= 0; i--) 351 if (o.equals(elementData[i])) 352 return i; 353 } 354 return -1; 355 } 356 357 /** 358 * Returns a shallow copy of this <tt>ArrayList</tt> instance. (The 359 * elements themselves are not copied.) 360 * 361 * @return a clone of this <tt>ArrayList</tt> instance 362 */ clone()363 public Object clone() { 364 try { 365 ArrayList<?> v = (ArrayList<?>) super.clone(); 366 v.elementData = Arrays.copyOf(elementData, size); 367 v.modCount = 0; 368 return v; 369 } catch (CloneNotSupportedException e) { 370 // this shouldn't happen, since we are Cloneable 371 throw new InternalError(e); 372 } 373 } 374 375 /** 376 * Returns an array containing all of the elements in this list 377 * in proper sequence (from first to last element). 378 * 379 * <p>The returned array will be "safe" in that no references to it are 380 * maintained by this list. (In other words, this method must allocate 381 * a new array). The caller is thus free to modify the returned array. 382 * 383 * <p>This method acts as bridge between array-based and collection-based 384 * APIs. 385 * 386 * @return an array containing all of the elements in this list in 387 * proper sequence 388 */ toArray()389 public Object[] toArray() { 390 return Arrays.copyOf(elementData, size); 391 } 392 393 /** 394 * Returns an array containing all of the elements in this list in proper 395 * sequence (from first to last element); the runtime type of the returned 396 * array is that of the specified array. If the list fits in the 397 * specified array, it is returned therein. Otherwise, a new array is 398 * allocated with the runtime type of the specified array and the size of 399 * this list. 400 * 401 * <p>If the list fits in the specified array with room to spare 402 * (i.e., the array has more elements than the list), the element in 403 * the array immediately following the end of the collection is set to 404 * <tt>null</tt>. (This is useful in determining the length of the 405 * list <i>only</i> if the caller knows that the list does not contain 406 * any null elements.) 407 * 408 * @param a the array into which the elements of the list are to 409 * be stored, if it is big enough; otherwise, a new array of the 410 * same runtime type is allocated for this purpose. 411 * @return an array containing the elements of the list 412 * @throws ArrayStoreException if the runtime type of the specified array 413 * is not a supertype of the runtime type of every element in 414 * this list 415 * @throws NullPointerException if the specified array is null 416 */ 417 @SuppressWarnings("unchecked") toArray(T[] a)418 public <T> T[] toArray(T[] a) { 419 if (a.length < size) 420 // Make a new array of a's runtime type, but my contents: 421 return (T[]) Arrays.copyOf(elementData, size, a.getClass()); 422 System.arraycopy(elementData, 0, a, 0, size); 423 if (a.length > size) 424 a[size] = null; 425 return a; 426 } 427 428 /** 429 * Returns the element at the specified position in this list. 430 * 431 * @param index index of the element to return 432 * @return the element at the specified position in this list 433 * @throws IndexOutOfBoundsException {@inheritDoc} 434 */ get(int index)435 public E get(int index) { 436 if (index >= size) 437 throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); 438 439 return (E) elementData[index]; 440 } 441 442 /** 443 * Replaces the element at the specified position in this list with 444 * the specified element. 445 * 446 * @param index index of the element to replace 447 * @param element element to be stored at the specified position 448 * @return the element previously at the specified position 449 * @throws IndexOutOfBoundsException {@inheritDoc} 450 */ set(int index, E element)451 public E set(int index, E element) { 452 if (index >= size) 453 throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); 454 455 E oldValue = (E) elementData[index]; 456 elementData[index] = element; 457 return oldValue; 458 } 459 460 /** 461 * Appends the specified element to the end of this list. 462 * 463 * @param e element to be appended to this list 464 * @return <tt>true</tt> (as specified by {@link Collection#add}) 465 */ add(E e)466 public boolean add(E e) { 467 ensureCapacityInternal(size + 1); // Increments modCount!! 468 elementData[size++] = e; 469 return true; 470 } 471 472 /** 473 * Inserts the specified element at the specified position in this 474 * list. Shifts the element currently at that position (if any) and 475 * any subsequent elements to the right (adds one to their indices). 476 * 477 * @param index index at which the specified element is to be inserted 478 * @param element element to be inserted 479 * @throws IndexOutOfBoundsException {@inheritDoc} 480 */ add(int index, E element)481 public void add(int index, E element) { 482 if (index > size || index < 0) 483 throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); 484 485 ensureCapacityInternal(size + 1); // Increments modCount!! 486 System.arraycopy(elementData, index, elementData, index + 1, 487 size - index); 488 elementData[index] = element; 489 size++; 490 } 491 492 /** 493 * Removes the element at the specified position in this list. 494 * Shifts any subsequent elements to the left (subtracts one from their 495 * indices). 496 * 497 * @param index the index of the element to be removed 498 * @return the element that was removed from the list 499 * @throws IndexOutOfBoundsException {@inheritDoc} 500 */ remove(int index)501 public E remove(int index) { 502 if (index >= size) 503 throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); 504 505 modCount++; 506 E oldValue = (E) elementData[index]; 507 508 int numMoved = size - index - 1; 509 if (numMoved > 0) 510 System.arraycopy(elementData, index+1, elementData, index, 511 numMoved); 512 elementData[--size] = null; // clear to let GC do its work 513 514 return oldValue; 515 } 516 517 /** 518 * Removes the first occurrence of the specified element from this list, 519 * if it is present. If the list does not contain the element, it is 520 * unchanged. More formally, removes the element with the lowest index 521 * <tt>i</tt> such that 522 * <tt>(o==null ? get(i)==null : o.equals(get(i)))</tt> 523 * (if such an element exists). Returns <tt>true</tt> if this list 524 * contained the specified element (or equivalently, if this list 525 * changed as a result of the call). 526 * 527 * @param o element to be removed from this list, if present 528 * @return <tt>true</tt> if this list contained the specified element 529 */ remove(Object o)530 public boolean remove(Object o) { 531 if (o == null) { 532 for (int index = 0; index < size; index++) 533 if (elementData[index] == null) { 534 fastRemove(index); 535 return true; 536 } 537 } else { 538 for (int index = 0; index < size; index++) 539 if (o.equals(elementData[index])) { 540 fastRemove(index); 541 return true; 542 } 543 } 544 return false; 545 } 546 547 /* 548 * Private remove method that skips bounds checking and does not 549 * return the value removed. 550 */ fastRemove(int index)551 private void fastRemove(int index) { 552 modCount++; 553 int numMoved = size - index - 1; 554 if (numMoved > 0) 555 System.arraycopy(elementData, index+1, elementData, index, 556 numMoved); 557 elementData[--size] = null; // clear to let GC do its work 558 } 559 560 /** 561 * Removes all of the elements from this list. The list will 562 * be empty after this call returns. 563 */ clear()564 public void clear() { 565 modCount++; 566 567 // clear to let GC do its work 568 for (int i = 0; i < size; i++) 569 elementData[i] = null; 570 571 size = 0; 572 } 573 574 /** 575 * Appends all of the elements in the specified collection to the end of 576 * this list, in the order that they are returned by the 577 * specified collection's Iterator. The behavior of this operation is 578 * undefined if the specified collection is modified while the operation 579 * is in progress. (This implies that the behavior of this call is 580 * undefined if the specified collection is this list, and this 581 * list is nonempty.) 582 * 583 * @param c collection containing elements to be added to this list 584 * @return <tt>true</tt> if this list changed as a result of the call 585 * @throws NullPointerException if the specified collection is null 586 */ addAll(Collection<? extends E> c)587 public boolean addAll(Collection<? extends E> c) { 588 Object[] a = c.toArray(); 589 int numNew = a.length; 590 ensureCapacityInternal(size + numNew); // Increments modCount 591 System.arraycopy(a, 0, elementData, size, numNew); 592 size += numNew; 593 return numNew != 0; 594 } 595 596 /** 597 * Inserts all of the elements in the specified collection into this 598 * list, starting at the specified position. Shifts the element 599 * currently at that position (if any) and any subsequent elements to 600 * the right (increases their indices). The new elements will appear 601 * in the list in the order that they are returned by the 602 * specified collection's iterator. 603 * 604 * @param index index at which to insert the first element from the 605 * specified collection 606 * @param c collection containing elements to be added to this list 607 * @return <tt>true</tt> if this list changed as a result of the call 608 * @throws IndexOutOfBoundsException {@inheritDoc} 609 * @throws NullPointerException if the specified collection is null 610 */ addAll(int index, Collection<? extends E> c)611 public boolean addAll(int index, Collection<? extends E> c) { 612 if (index > size || index < 0) 613 throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); 614 615 Object[] a = c.toArray(); 616 int numNew = a.length; 617 ensureCapacityInternal(size + numNew); // Increments modCount 618 619 int numMoved = size - index; 620 if (numMoved > 0) 621 System.arraycopy(elementData, index, elementData, index + numNew, 622 numMoved); 623 624 System.arraycopy(a, 0, elementData, index, numNew); 625 size += numNew; 626 return numNew != 0; 627 } 628 629 /** 630 * Removes from this list all of the elements whose index is between 631 * {@code fromIndex}, inclusive, and {@code toIndex}, exclusive. 632 * Shifts any succeeding elements to the left (reduces their index). 633 * This call shortens the list by {@code (toIndex - fromIndex)} elements. 634 * (If {@code toIndex==fromIndex}, this operation has no effect.) 635 * 636 * @throws IndexOutOfBoundsException if {@code fromIndex} or 637 * {@code toIndex} is out of range 638 * ({@code fromIndex < 0 || 639 * fromIndex >= size() || 640 * toIndex > size() || 641 * toIndex < fromIndex}) 642 */ removeRange(int fromIndex, int toIndex)643 protected void removeRange(int fromIndex, int toIndex) { 644 // Android-changed: Throw an IOOBE if toIndex < fromIndex as documented. 645 // All the other cases (negative indices, or indices greater than the size 646 // will be thrown by System#arrayCopy. 647 if (toIndex < fromIndex) { 648 throw new IndexOutOfBoundsException("toIndex < fromIndex"); 649 } 650 651 modCount++; 652 int numMoved = size - toIndex; 653 System.arraycopy(elementData, toIndex, elementData, fromIndex, 654 numMoved); 655 656 // clear to let GC do its work 657 int newSize = size - (toIndex-fromIndex); 658 for (int i = newSize; i < size; i++) { 659 elementData[i] = null; 660 } 661 size = newSize; 662 } 663 664 /** 665 * Constructs an IndexOutOfBoundsException detail message. 666 * Of the many possible refactorings of the error handling code, 667 * this "outlining" performs best with both server and client VMs. 668 */ outOfBoundsMsg(int index)669 private String outOfBoundsMsg(int index) { 670 return "Index: "+index+", Size: "+size; 671 } 672 673 /** 674 * Removes from this list all of its elements that are contained in the 675 * specified collection. 676 * 677 * @param c collection containing elements to be removed from this list 678 * @return {@code true} if this list changed as a result of the call 679 * @throws ClassCastException if the class of an element of this list 680 * is incompatible with the specified collection 681 * (<a href="Collection.html#optional-restrictions">optional</a>) 682 * @throws NullPointerException if this list contains a null element and the 683 * specified collection does not permit null elements 684 * (<a href="Collection.html#optional-restrictions">optional</a>), 685 * or if the specified collection is null 686 * @see Collection#contains(Object) 687 */ removeAll(Collection<?> c)688 public boolean removeAll(Collection<?> c) { 689 Objects.requireNonNull(c); 690 return batchRemove(c, false); 691 } 692 693 /** 694 * Retains only the elements in this list that are contained in the 695 * specified collection. In other words, removes from this list all 696 * of its elements that are not contained in the specified collection. 697 * 698 * @param c collection containing elements to be retained in this list 699 * @return {@code true} if this list changed as a result of the call 700 * @throws ClassCastException if the class of an element of this list 701 * is incompatible with the specified collection 702 * (<a href="Collection.html#optional-restrictions">optional</a>) 703 * @throws NullPointerException if this list contains a null element and the 704 * specified collection does not permit null elements 705 * (<a href="Collection.html#optional-restrictions">optional</a>), 706 * or if the specified collection is null 707 * @see Collection#contains(Object) 708 */ retainAll(Collection<?> c)709 public boolean retainAll(Collection<?> c) { 710 Objects.requireNonNull(c); 711 return batchRemove(c, true); 712 } 713 batchRemove(Collection<?> c, boolean complement)714 private boolean batchRemove(Collection<?> c, boolean complement) { 715 final Object[] elementData = this.elementData; 716 int r = 0, w = 0; 717 boolean modified = false; 718 try { 719 for (; r < size; r++) 720 if (c.contains(elementData[r]) == complement) 721 elementData[w++] = elementData[r]; 722 } finally { 723 // Preserve behavioral compatibility with AbstractCollection, 724 // even if c.contains() throws. 725 if (r != size) { 726 System.arraycopy(elementData, r, 727 elementData, w, 728 size - r); 729 w += size - r; 730 } 731 if (w != size) { 732 // clear to let GC do its work 733 for (int i = w; i < size; i++) 734 elementData[i] = null; 735 modCount += size - w; 736 size = w; 737 modified = true; 738 } 739 } 740 return modified; 741 } 742 743 /** 744 * Save the state of the <tt>ArrayList</tt> instance to a stream (that 745 * is, serialize it). 746 * 747 * @serialData The length of the array backing the <tt>ArrayList</tt> 748 * instance is emitted (int), followed by all of its elements 749 * (each an <tt>Object</tt>) in the proper order. 750 */ writeObject(java.io.ObjectOutputStream s)751 private void writeObject(java.io.ObjectOutputStream s) 752 throws java.io.IOException{ 753 // Write out element count, and any hidden stuff 754 int expectedModCount = modCount; 755 s.defaultWriteObject(); 756 757 // Write out size as capacity for behavioural compatibility with clone() 758 s.writeInt(size); 759 760 // Write out all elements in the proper order. 761 for (int i=0; i<size; i++) { 762 s.writeObject(elementData[i]); 763 } 764 765 if (modCount != expectedModCount) { 766 throw new ConcurrentModificationException(); 767 } 768 } 769 770 /** 771 * Reconstitute the <tt>ArrayList</tt> instance from a stream (that is, 772 * deserialize it). 773 */ readObject(java.io.ObjectInputStream s)774 private void readObject(java.io.ObjectInputStream s) 775 throws java.io.IOException, ClassNotFoundException { 776 elementData = EMPTY_ELEMENTDATA; 777 778 // Read in size, and any hidden stuff 779 s.defaultReadObject(); 780 781 // Read in capacity 782 s.readInt(); // ignored 783 784 if (size > 0) { 785 // be like clone(), allocate array based upon size not capacity 786 ensureCapacityInternal(size); 787 788 Object[] a = elementData; 789 // Read in all elements in the proper order. 790 for (int i=0; i<size; i++) { 791 a[i] = s.readObject(); 792 } 793 } 794 } 795 796 /** 797 * Returns a list iterator over the elements in this list (in proper 798 * sequence), starting at the specified position in the list. 799 * The specified index indicates the first element that would be 800 * returned by an initial call to {@link ListIterator#next next}. 801 * An initial call to {@link ListIterator#previous previous} would 802 * return the element with the specified index minus one. 803 * 804 * <p>The returned list iterator is <a href="#fail-fast"><i>fail-fast</i></a>. 805 * 806 * @throws IndexOutOfBoundsException {@inheritDoc} 807 */ listIterator(int index)808 public ListIterator<E> listIterator(int index) { 809 if (index < 0 || index > size) 810 throw new IndexOutOfBoundsException("Index: "+index); 811 return new ListItr(index); 812 } 813 814 /** 815 * Returns a list iterator over the elements in this list (in proper 816 * sequence). 817 * 818 * <p>The returned list iterator is <a href="#fail-fast"><i>fail-fast</i></a>. 819 * 820 * @see #listIterator(int) 821 */ listIterator()822 public ListIterator<E> listIterator() { 823 return new ListItr(0); 824 } 825 826 /** 827 * Returns an iterator over the elements in this list in proper sequence. 828 * 829 * <p>The returned iterator is <a href="#fail-fast"><i>fail-fast</i></a>. 830 * 831 * @return an iterator over the elements in this list in proper sequence 832 */ iterator()833 public Iterator<E> iterator() { 834 return new Itr(); 835 } 836 837 /** 838 * An optimized version of AbstractList.Itr 839 */ 840 private class Itr implements Iterator<E> { 841 // Android-changed: Add "limit" field to detect end of iteration. 842 // The "limit" of this iterator. This is the size of the list at the time the 843 // iterator was created. Adding & removing elements will invalidate the iteration 844 // anyway (and cause next() to throw) so saving this value will guarantee that the 845 // value of hasNext() remains stable and won't flap between true and false when elements 846 // are added and removed from the list. 847 protected int limit = ArrayList.this.size; 848 849 int cursor; // index of next element to return 850 int lastRet = -1; // index of last element returned; -1 if no such 851 int expectedModCount = modCount; 852 hasNext()853 public boolean hasNext() { 854 return cursor < limit; 855 } 856 857 @SuppressWarnings("unchecked") next()858 public E next() { 859 if (modCount != expectedModCount) 860 throw new ConcurrentModificationException(); 861 int i = cursor; 862 if (i >= limit) 863 throw new NoSuchElementException(); 864 Object[] elementData = ArrayList.this.elementData; 865 if (i >= elementData.length) 866 throw new ConcurrentModificationException(); 867 cursor = i + 1; 868 return (E) elementData[lastRet = i]; 869 } 870 remove()871 public void remove() { 872 if (lastRet < 0) 873 throw new IllegalStateException(); 874 if (modCount != expectedModCount) 875 throw new ConcurrentModificationException(); 876 877 try { 878 ArrayList.this.remove(lastRet); 879 cursor = lastRet; 880 lastRet = -1; 881 expectedModCount = modCount; 882 limit--; 883 } catch (IndexOutOfBoundsException ex) { 884 throw new ConcurrentModificationException(); 885 } 886 } 887 888 @Override 889 @SuppressWarnings("unchecked") forEachRemaining(Consumer<? super E> consumer)890 public void forEachRemaining(Consumer<? super E> consumer) { 891 Objects.requireNonNull(consumer); 892 final int size = ArrayList.this.size; 893 int i = cursor; 894 if (i >= size) { 895 return; 896 } 897 final Object[] elementData = ArrayList.this.elementData; 898 if (i >= elementData.length) { 899 throw new ConcurrentModificationException(); 900 } 901 while (i != size && modCount == expectedModCount) { 902 consumer.accept((E) elementData[i++]); 903 } 904 // update once at end of iteration to reduce heap write traffic 905 cursor = i; 906 lastRet = i - 1; 907 908 if (modCount != expectedModCount) 909 throw new ConcurrentModificationException(); 910 } 911 } 912 913 /** 914 * An optimized version of AbstractList.ListItr 915 */ 916 private class ListItr extends Itr implements ListIterator<E> { ListItr(int index)917 ListItr(int index) { 918 super(); 919 cursor = index; 920 } 921 hasPrevious()922 public boolean hasPrevious() { 923 return cursor != 0; 924 } 925 nextIndex()926 public int nextIndex() { 927 return cursor; 928 } 929 previousIndex()930 public int previousIndex() { 931 return cursor - 1; 932 } 933 934 @SuppressWarnings("unchecked") previous()935 public E previous() { 936 if (modCount != expectedModCount) 937 throw new ConcurrentModificationException(); 938 int i = cursor - 1; 939 if (i < 0) 940 throw new NoSuchElementException(); 941 Object[] elementData = ArrayList.this.elementData; 942 if (i >= elementData.length) 943 throw new ConcurrentModificationException(); 944 cursor = i; 945 return (E) elementData[lastRet = i]; 946 } 947 set(E e)948 public void set(E e) { 949 if (lastRet < 0) 950 throw new IllegalStateException(); 951 if (modCount != expectedModCount) 952 throw new ConcurrentModificationException(); 953 954 try { 955 ArrayList.this.set(lastRet, e); 956 } catch (IndexOutOfBoundsException ex) { 957 throw new ConcurrentModificationException(); 958 } 959 } 960 add(E e)961 public void add(E e) { 962 if (modCount != expectedModCount) 963 throw new ConcurrentModificationException(); 964 965 try { 966 int i = cursor; 967 ArrayList.this.add(i, e); 968 cursor = i + 1; 969 lastRet = -1; 970 expectedModCount = modCount; 971 limit++; 972 } catch (IndexOutOfBoundsException ex) { 973 throw new ConcurrentModificationException(); 974 } 975 } 976 } 977 978 /** 979 * Returns a view of the portion of this list between the specified 980 * {@code fromIndex}, inclusive, and {@code toIndex}, exclusive. (If 981 * {@code fromIndex} and {@code toIndex} are equal, the returned list is 982 * empty.) The returned list is backed by this list, so non-structural 983 * changes in the returned list are reflected in this list, and vice-versa. 984 * The returned list supports all of the optional list operations. 985 * 986 * <p>This method eliminates the need for explicit range operations (of 987 * the sort that commonly exist for arrays). Any operation that expects 988 * a list can be used as a range operation by passing a subList view 989 * instead of a whole list. For example, the following idiom 990 * removes a range of elements from a list: 991 * <pre> 992 * list.subList(from, to).clear(); 993 * </pre> 994 * Similar idioms may be constructed for {@link #indexOf(Object)} and 995 * {@link #lastIndexOf(Object)}, and all of the algorithms in the 996 * {@link Collections} class can be applied to a subList. 997 * 998 * <p>The semantics of the list returned by this method become undefined if 999 * the backing list (i.e., this list) is <i>structurally modified</i> in 1000 * any way other than via the returned list. (Structural modifications are 1001 * those that change the size of this list, or otherwise perturb it in such 1002 * a fashion that iterations in progress may yield incorrect results.) 1003 * 1004 * @throws IndexOutOfBoundsException {@inheritDoc} 1005 * @throws IllegalArgumentException {@inheritDoc} 1006 */ subList(int fromIndex, int toIndex)1007 public List<E> subList(int fromIndex, int toIndex) { 1008 subListRangeCheck(fromIndex, toIndex, size); 1009 return new SubList(this, 0, fromIndex, toIndex); 1010 } 1011 subListRangeCheck(int fromIndex, int toIndex, int size)1012 static void subListRangeCheck(int fromIndex, int toIndex, int size) { 1013 if (fromIndex < 0) 1014 throw new IndexOutOfBoundsException("fromIndex = " + fromIndex); 1015 if (toIndex > size) 1016 throw new IndexOutOfBoundsException("toIndex = " + toIndex); 1017 if (fromIndex > toIndex) 1018 throw new IllegalArgumentException("fromIndex(" + fromIndex + 1019 ") > toIndex(" + toIndex + ")"); 1020 } 1021 1022 private class SubList extends AbstractList<E> implements RandomAccess { 1023 private final AbstractList<E> parent; 1024 private final int parentOffset; 1025 private final int offset; 1026 int size; 1027 SubList(AbstractList<E> parent, int offset, int fromIndex, int toIndex)1028 SubList(AbstractList<E> parent, 1029 int offset, int fromIndex, int toIndex) { 1030 this.parent = parent; 1031 this.parentOffset = fromIndex; 1032 this.offset = offset + fromIndex; 1033 this.size = toIndex - fromIndex; 1034 this.modCount = ArrayList.this.modCount; 1035 } 1036 set(int index, E e)1037 public E set(int index, E e) { 1038 if (index < 0 || index >= this.size) 1039 throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); 1040 if (ArrayList.this.modCount != this.modCount) 1041 throw new ConcurrentModificationException(); 1042 E oldValue = (E) ArrayList.this.elementData[offset + index]; 1043 ArrayList.this.elementData[offset + index] = e; 1044 return oldValue; 1045 } 1046 get(int index)1047 public E get(int index) { 1048 if (index < 0 || index >= this.size) 1049 throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); 1050 if (ArrayList.this.modCount != this.modCount) 1051 throw new ConcurrentModificationException(); 1052 return (E) ArrayList.this.elementData[offset + index]; 1053 } 1054 size()1055 public int size() { 1056 if (ArrayList.this.modCount != this.modCount) 1057 throw new ConcurrentModificationException(); 1058 return this.size; 1059 } 1060 add(int index, E e)1061 public void add(int index, E e) { 1062 if (index < 0 || index > this.size) 1063 throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); 1064 if (ArrayList.this.modCount != this.modCount) 1065 throw new ConcurrentModificationException(); 1066 parent.add(parentOffset + index, e); 1067 this.modCount = parent.modCount; 1068 this.size++; 1069 } 1070 remove(int index)1071 public E remove(int index) { 1072 if (index < 0 || index >= this.size) 1073 throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); 1074 if (ArrayList.this.modCount != this.modCount) 1075 throw new ConcurrentModificationException(); 1076 E result = parent.remove(parentOffset + index); 1077 this.modCount = parent.modCount; 1078 this.size--; 1079 return result; 1080 } 1081 removeRange(int fromIndex, int toIndex)1082 protected void removeRange(int fromIndex, int toIndex) { 1083 if (ArrayList.this.modCount != this.modCount) 1084 throw new ConcurrentModificationException(); 1085 parent.removeRange(parentOffset + fromIndex, 1086 parentOffset + toIndex); 1087 this.modCount = parent.modCount; 1088 this.size -= toIndex - fromIndex; 1089 } 1090 addAll(Collection<? extends E> c)1091 public boolean addAll(Collection<? extends E> c) { 1092 return addAll(this.size, c); 1093 } 1094 addAll(int index, Collection<? extends E> c)1095 public boolean addAll(int index, Collection<? extends E> c) { 1096 if (index < 0 || index > this.size) 1097 throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); 1098 int cSize = c.size(); 1099 if (cSize==0) 1100 return false; 1101 1102 if (ArrayList.this.modCount != this.modCount) 1103 throw new ConcurrentModificationException(); 1104 parent.addAll(parentOffset + index, c); 1105 this.modCount = parent.modCount; 1106 this.size += cSize; 1107 return true; 1108 } 1109 iterator()1110 public Iterator<E> iterator() { 1111 return listIterator(); 1112 } 1113 listIterator(final int index)1114 public ListIterator<E> listIterator(final int index) { 1115 if (ArrayList.this.modCount != this.modCount) 1116 throw new ConcurrentModificationException(); 1117 if (index < 0 || index > this.size) 1118 throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); 1119 final int offset = this.offset; 1120 1121 return new ListIterator<E>() { 1122 int cursor = index; 1123 int lastRet = -1; 1124 int expectedModCount = ArrayList.this.modCount; 1125 1126 public boolean hasNext() { 1127 return cursor != SubList.this.size; 1128 } 1129 1130 @SuppressWarnings("unchecked") 1131 public E next() { 1132 if (expectedModCount != ArrayList.this.modCount) 1133 throw new ConcurrentModificationException(); 1134 int i = cursor; 1135 if (i >= SubList.this.size) 1136 throw new NoSuchElementException(); 1137 Object[] elementData = ArrayList.this.elementData; 1138 if (offset + i >= elementData.length) 1139 throw new ConcurrentModificationException(); 1140 cursor = i + 1; 1141 return (E) elementData[offset + (lastRet = i)]; 1142 } 1143 1144 public boolean hasPrevious() { 1145 return cursor != 0; 1146 } 1147 1148 @SuppressWarnings("unchecked") 1149 public E previous() { 1150 if (expectedModCount != ArrayList.this.modCount) 1151 throw new ConcurrentModificationException(); 1152 int i = cursor - 1; 1153 if (i < 0) 1154 throw new NoSuchElementException(); 1155 Object[] elementData = ArrayList.this.elementData; 1156 if (offset + i >= elementData.length) 1157 throw new ConcurrentModificationException(); 1158 cursor = i; 1159 return (E) elementData[offset + (lastRet = i)]; 1160 } 1161 1162 @SuppressWarnings("unchecked") 1163 public void forEachRemaining(Consumer<? super E> consumer) { 1164 Objects.requireNonNull(consumer); 1165 final int size = SubList.this.size; 1166 int i = cursor; 1167 if (i >= size) { 1168 return; 1169 } 1170 final Object[] elementData = ArrayList.this.elementData; 1171 if (offset + i >= elementData.length) { 1172 throw new ConcurrentModificationException(); 1173 } 1174 while (i != size && modCount == expectedModCount) { 1175 consumer.accept((E) elementData[offset + (i++)]); 1176 } 1177 // update once at end of iteration to reduce heap write traffic 1178 lastRet = cursor = i; 1179 if (expectedModCount != ArrayList.this.modCount) 1180 throw new ConcurrentModificationException(); 1181 } 1182 1183 public int nextIndex() { 1184 return cursor; 1185 } 1186 1187 public int previousIndex() { 1188 return cursor - 1; 1189 } 1190 1191 public void remove() { 1192 if (lastRet < 0) 1193 throw new IllegalStateException(); 1194 if (expectedModCount != ArrayList.this.modCount) 1195 throw new ConcurrentModificationException(); 1196 1197 try { 1198 SubList.this.remove(lastRet); 1199 cursor = lastRet; 1200 lastRet = -1; 1201 expectedModCount = ArrayList.this.modCount; 1202 } catch (IndexOutOfBoundsException ex) { 1203 throw new ConcurrentModificationException(); 1204 } 1205 } 1206 1207 public void set(E e) { 1208 if (lastRet < 0) 1209 throw new IllegalStateException(); 1210 if (expectedModCount != ArrayList.this.modCount) 1211 throw new ConcurrentModificationException(); 1212 1213 try { 1214 ArrayList.this.set(offset + lastRet, e); 1215 } catch (IndexOutOfBoundsException ex) { 1216 throw new ConcurrentModificationException(); 1217 } 1218 } 1219 1220 public void add(E e) { 1221 if (expectedModCount != ArrayList.this.modCount) 1222 throw new ConcurrentModificationException(); 1223 1224 try { 1225 int i = cursor; 1226 SubList.this.add(i, e); 1227 cursor = i + 1; 1228 lastRet = -1; 1229 expectedModCount = ArrayList.this.modCount; 1230 } catch (IndexOutOfBoundsException ex) { 1231 throw new ConcurrentModificationException(); 1232 } 1233 } 1234 }; 1235 } 1236 subList(int fromIndex, int toIndex)1237 public List<E> subList(int fromIndex, int toIndex) { 1238 subListRangeCheck(fromIndex, toIndex, size); 1239 return new SubList(this, offset, fromIndex, toIndex); 1240 } 1241 outOfBoundsMsg(int index)1242 private String outOfBoundsMsg(int index) { 1243 return "Index: "+index+", Size: "+this.size; 1244 } 1245 spliterator()1246 public Spliterator<E> spliterator() { 1247 if (modCount != ArrayList.this.modCount) 1248 throw new ConcurrentModificationException(); 1249 return new ArrayListSpliterator<E>(ArrayList.this, offset, 1250 offset + this.size, this.modCount); 1251 } 1252 } 1253 1254 @Override forEach(Consumer<? super E> action)1255 public void forEach(Consumer<? super E> action) { 1256 Objects.requireNonNull(action); 1257 final int expectedModCount = modCount; 1258 @SuppressWarnings("unchecked") 1259 final E[] elementData = (E[]) this.elementData; 1260 final int size = this.size; 1261 for (int i=0; modCount == expectedModCount && i < size; i++) { 1262 action.accept(elementData[i]); 1263 } 1264 // Android-note: 1265 // Iterator will not throw a CME if we add something while iterating over the *last* element 1266 // forEach will throw a CME in this case. 1267 if (modCount != expectedModCount) { 1268 throw new ConcurrentModificationException(); 1269 } 1270 } 1271 1272 /** 1273 * Creates a <em><a href="Spliterator.html#binding">late-binding</a></em> 1274 * and <em>fail-fast</em> {@link Spliterator} over the elements in this 1275 * list. 1276 * 1277 * <p>The {@code Spliterator} reports {@link Spliterator#SIZED}, 1278 * {@link Spliterator#SUBSIZED}, and {@link Spliterator#ORDERED}. 1279 * Overriding implementations should document the reporting of additional 1280 * characteristic values. 1281 * 1282 * @return a {@code Spliterator} over the elements in this list 1283 * @since 1.8 1284 */ 1285 @Override spliterator()1286 public Spliterator<E> spliterator() { 1287 return new ArrayListSpliterator<>(this, 0, -1, 0); 1288 } 1289 1290 /** Index-based split-by-two, lazily initialized Spliterator */ 1291 static final class ArrayListSpliterator<E> implements Spliterator<E> { 1292 1293 /* 1294 * If ArrayLists were immutable, or structurally immutable (no 1295 * adds, removes, etc), we could implement their spliterators 1296 * with Arrays.spliterator. Instead we detect as much 1297 * interference during traversal as practical without 1298 * sacrificing much performance. We rely primarily on 1299 * modCounts. These are not guaranteed to detect concurrency 1300 * violations, and are sometimes overly conservative about 1301 * within-thread interference, but detect enough problems to 1302 * be worthwhile in practice. To carry this out, we (1) lazily 1303 * initialize fence and expectedModCount until the latest 1304 * point that we need to commit to the state we are checking 1305 * against; thus improving precision. (This doesn't apply to 1306 * SubLists, that create spliterators with current non-lazy 1307 * values). (2) We perform only a single 1308 * ConcurrentModificationException check at the end of forEach 1309 * (the most performance-sensitive method). When using forEach 1310 * (as opposed to iterators), we can normally only detect 1311 * interference after actions, not before. Further 1312 * CME-triggering checks apply to all other possible 1313 * violations of assumptions for example null or too-small 1314 * elementData array given its size(), that could only have 1315 * occurred due to interference. This allows the inner loop 1316 * of forEach to run without any further checks, and 1317 * simplifies lambda-resolution. While this does entail a 1318 * number of checks, note that in the common case of 1319 * list.stream().forEach(a), no checks or other computation 1320 * occur anywhere other than inside forEach itself. The other 1321 * less-often-used methods cannot take advantage of most of 1322 * these streamlinings. 1323 */ 1324 1325 private final ArrayList<E> list; 1326 private int index; // current index, modified on advance/split 1327 private int fence; // -1 until used; then one past last index 1328 private int expectedModCount; // initialized when fence set 1329 1330 /** Create new spliterator covering the given range */ ArrayListSpliterator(ArrayList<E> list, int origin, int fence, int expectedModCount)1331 ArrayListSpliterator(ArrayList<E> list, int origin, int fence, 1332 int expectedModCount) { 1333 this.list = list; // OK if null unless traversed 1334 this.index = origin; 1335 this.fence = fence; 1336 this.expectedModCount = expectedModCount; 1337 } 1338 getFence()1339 private int getFence() { // initialize fence to size on first use 1340 int hi; // (a specialized variant appears in method forEach) 1341 ArrayList<E> lst; 1342 if ((hi = fence) < 0) { 1343 if ((lst = list) == null) 1344 hi = fence = 0; 1345 else { 1346 expectedModCount = lst.modCount; 1347 hi = fence = lst.size; 1348 } 1349 } 1350 return hi; 1351 } 1352 trySplit()1353 public ArrayListSpliterator<E> trySplit() { 1354 int hi = getFence(), lo = index, mid = (lo + hi) >>> 1; 1355 return (lo >= mid) ? null : // divide range in half unless too small 1356 new ArrayListSpliterator<E>(list, lo, index = mid, 1357 expectedModCount); 1358 } 1359 tryAdvance(Consumer<? super E> action)1360 public boolean tryAdvance(Consumer<? super E> action) { 1361 if (action == null) 1362 throw new NullPointerException(); 1363 int hi = getFence(), i = index; 1364 if (i < hi) { 1365 index = i + 1; 1366 @SuppressWarnings("unchecked") E e = (E)list.elementData[i]; 1367 action.accept(e); 1368 if (list.modCount != expectedModCount) 1369 throw new ConcurrentModificationException(); 1370 return true; 1371 } 1372 return false; 1373 } 1374 forEachRemaining(Consumer<? super E> action)1375 public void forEachRemaining(Consumer<? super E> action) { 1376 int i, hi, mc; // hoist accesses and checks from loop 1377 ArrayList<E> lst; Object[] a; 1378 if (action == null) 1379 throw new NullPointerException(); 1380 if ((lst = list) != null && (a = lst.elementData) != null) { 1381 if ((hi = fence) < 0) { 1382 mc = lst.modCount; 1383 hi = lst.size; 1384 } 1385 else 1386 mc = expectedModCount; 1387 if ((i = index) >= 0 && (index = hi) <= a.length) { 1388 for (; i < hi; ++i) { 1389 @SuppressWarnings("unchecked") E e = (E) a[i]; 1390 action.accept(e); 1391 } 1392 if (lst.modCount == mc) 1393 return; 1394 } 1395 } 1396 throw new ConcurrentModificationException(); 1397 } 1398 estimateSize()1399 public long estimateSize() { 1400 return (long) (getFence() - index); 1401 } 1402 characteristics()1403 public int characteristics() { 1404 return Spliterator.ORDERED | Spliterator.SIZED | Spliterator.SUBSIZED; 1405 } 1406 } 1407 1408 @Override removeIf(Predicate<? super E> filter)1409 public boolean removeIf(Predicate<? super E> filter) { 1410 Objects.requireNonNull(filter); 1411 // figure out which elements are to be removed 1412 // any exception thrown from the filter predicate at this stage 1413 // will leave the collection unmodified 1414 int removeCount = 0; 1415 final BitSet removeSet = new BitSet(size); 1416 final int expectedModCount = modCount; 1417 final int size = this.size; 1418 for (int i=0; modCount == expectedModCount && i < size; i++) { 1419 @SuppressWarnings("unchecked") 1420 final E element = (E) elementData[i]; 1421 if (filter.test(element)) { 1422 removeSet.set(i); 1423 removeCount++; 1424 } 1425 } 1426 if (modCount != expectedModCount) { 1427 throw new ConcurrentModificationException(); 1428 } 1429 1430 // shift surviving elements left over the spaces left by removed elements 1431 final boolean anyToRemove = removeCount > 0; 1432 if (anyToRemove) { 1433 final int newSize = size - removeCount; 1434 for (int i=0, j=0; (i < size) && (j < newSize); i++, j++) { 1435 i = removeSet.nextClearBit(i); 1436 elementData[j] = elementData[i]; 1437 } 1438 for (int k=newSize; k < size; k++) { 1439 elementData[k] = null; // Let gc do its work 1440 } 1441 this.size = newSize; 1442 if (modCount != expectedModCount) { 1443 throw new ConcurrentModificationException(); 1444 } 1445 modCount++; 1446 } 1447 1448 return anyToRemove; 1449 } 1450 1451 @Override 1452 @SuppressWarnings("unchecked") replaceAll(UnaryOperator<E> operator)1453 public void replaceAll(UnaryOperator<E> operator) { 1454 Objects.requireNonNull(operator); 1455 final int expectedModCount = modCount; 1456 final int size = this.size; 1457 for (int i=0; modCount == expectedModCount && i < size; i++) { 1458 elementData[i] = operator.apply((E) elementData[i]); 1459 } 1460 if (modCount != expectedModCount) { 1461 throw new ConcurrentModificationException(); 1462 } 1463 modCount++; 1464 } 1465 1466 @Override 1467 @SuppressWarnings("unchecked") sort(Comparator<? super E> c)1468 public void sort(Comparator<? super E> c) { 1469 final int expectedModCount = modCount; 1470 Arrays.sort((E[]) elementData, 0, size, c); 1471 if (modCount != expectedModCount) { 1472 throw new ConcurrentModificationException(); 1473 } 1474 modCount++; 1475 } 1476 } 1477