1/* 2 * Licensed to the Apache Software Foundation (ASF) under one or more 3 * contributor license agreements. See the NOTICE file distributed with 4 * this work for additional information regarding copyright ownership. 5 * The ASF licenses this file to You under the Apache License, Version 2.0 6 * (the "License"); you may not use this file except in compliance with 7 * the License. You may obtain a copy of the License at 8 * 9 * http://www.apache.org/licenses/LICENSE-2.0 10 * 11 * Unless required by applicable law or agreed to in writing, software 12 * distributed under the License is distributed on an "AS IS" BASIS, 13 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 14 * See the License for the specific language governing permissions and 15 * limitations under the License. 16 */ 17 18package java.util; 19 20import java.io.IOException; 21import java.io.InvalidObjectException; 22import java.io.ObjectInputStream; 23import java.io.ObjectOutputStream; 24import java.io.Serializable; 25import java.lang.reflect.Array; 26import libcore.util.EmptyArray; 27 28/** 29 * ArrayList is an implementation of {@link List}, backed by an array. 30 * All optional operations including adding, removing, and replacing elements are supported. 31 * 32 * <p>All elements are permitted, including null. 33 * 34 * <p>This class is a good choice as your default {@code List} implementation. 35 * {@link Vector} synchronizes all operations, but not necessarily in a way that's 36 * meaningful to your application: synchronizing each call to {@code get}, for example, is not 37 * equivalent to synchronizing the list and iterating over it (which is probably what you intended). 38 * {@link java.util.concurrent.CopyOnWriteArrayList} is intended for the special case of very high 39 * concurrency, frequent traversals, and very rare mutations. 40 * 41 * @param <E> The element type of this list. 42 * @since 1.2 43 */ 44public class ArrayList<E> extends AbstractList<E> implements Cloneable, Serializable, RandomAccess { 45 /** 46 * The minimum amount by which the capacity of an ArrayList will increase. 47 * This tuning parameter controls a time-space tradeoff. This value (12) 48 * gives empirically good results and is arguably consistent with the 49 * RI's specified default initial capacity of 10: instead of 10, we start 50 * with 0 (sans allocation) and jump to 12. 51 */ 52 private static final int MIN_CAPACITY_INCREMENT = 12; 53 54 /** 55 * The number of elements in this list. 56 */ 57 int size; 58 59 /** 60 * The elements in this list, followed by nulls. 61 */ 62 transient Object[] array; 63 64 /** 65 * Constructs a new instance of {@code ArrayList} with the specified 66 * initial capacity. 67 * 68 * @param capacity 69 * the initial capacity of this {@code ArrayList}. 70 */ 71 public ArrayList(int capacity) { 72 if (capacity < 0) { 73 throw new IllegalArgumentException(); 74 } 75 array = (capacity == 0 ? EmptyArray.OBJECT : new Object[capacity]); 76 } 77 78 /** 79 * Constructs a new {@code ArrayList} instance with zero initial capacity. 80 */ 81 public ArrayList() { 82 array = EmptyArray.OBJECT; 83 } 84 85 /** 86 * Constructs a new instance of {@code ArrayList} containing the elements of 87 * the specified collection. 88 * 89 * @param collection 90 * the collection of elements to add. 91 */ 92 public ArrayList(Collection<? extends E> collection) { 93 Object[] a = collection.toArray(); 94 if (a.getClass() != Object[].class) { 95 Object[] newArray = new Object[a.length]; 96 System.arraycopy(a, 0, newArray, 0, a.length); 97 a = newArray; 98 } 99 array = a; 100 size = a.length; 101 } 102 103 /** 104 * Adds the specified object at the end of this {@code ArrayList}. 105 * 106 * @param object 107 * the object to add. 108 * @return always true 109 */ 110 @Override public boolean add(E object) { 111 Object[] a = array; 112 int s = size; 113 if (s == a.length) { 114 Object[] newArray = new Object[s + 115 (s < (MIN_CAPACITY_INCREMENT / 2) ? 116 MIN_CAPACITY_INCREMENT : s >> 1)]; 117 System.arraycopy(a, 0, newArray, 0, s); 118 array = a = newArray; 119 } 120 a[s] = object; 121 size = s + 1; 122 modCount++; 123 return true; 124 } 125 126 /** 127 * Inserts the specified object into this {@code ArrayList} at the specified 128 * location. The object is inserted before any previous element at the 129 * specified location. If the location is equal to the size of this 130 * {@code ArrayList}, the object is added at the end. 131 * 132 * @param index 133 * the index at which to insert the object. 134 * @param object 135 * the object to add. 136 * @throws IndexOutOfBoundsException 137 * when {@code location < 0 || location > size()} 138 */ 139 @Override public void add(int index, E object) { 140 Object[] a = array; 141 int s = size; 142 if (index > s || index < 0) { 143 throwIndexOutOfBoundsException(index, s); 144 } 145 146 if (s < a.length) { 147 System.arraycopy(a, index, a, index + 1, s - index); 148 } else { 149 // assert s == a.length; 150 Object[] newArray = new Object[newCapacity(s)]; 151 System.arraycopy(a, 0, newArray, 0, index); 152 System.arraycopy(a, index, newArray, index + 1, s - index); 153 array = a = newArray; 154 } 155 a[index] = object; 156 size = s + 1; 157 modCount++; 158 } 159 160 /** 161 * This method controls the growth of ArrayList capacities. It represents 162 * a time-space tradeoff: we don't want to grow lists too frequently 163 * (which wastes time and fragments storage), but we don't want to waste 164 * too much space in unused excess capacity. 165 * 166 * NOTE: This method is inlined into {@link #add(Object)} for performance. 167 * If you change the method, change it there too! 168 */ 169 private static int newCapacity(int currentCapacity) { 170 int increment = (currentCapacity < (MIN_CAPACITY_INCREMENT / 2) ? 171 MIN_CAPACITY_INCREMENT : currentCapacity >> 1); 172 return currentCapacity + increment; 173 } 174 175 /** 176 * Adds the objects in the specified collection to this {@code ArrayList}. 177 * 178 * @param collection 179 * the collection of objects. 180 * @return {@code true} if this {@code ArrayList} is modified, {@code false} 181 * otherwise. 182 */ 183 @Override public boolean addAll(Collection<? extends E> collection) { 184 Object[] newPart = collection.toArray(); 185 int newPartSize = newPart.length; 186 if (newPartSize == 0) { 187 return false; 188 } 189 Object[] a = array; 190 int s = size; 191 int newSize = s + newPartSize; // If add overflows, arraycopy will fail 192 if (newSize > a.length) { 193 int newCapacity = newCapacity(newSize - 1); // ~33% growth room 194 Object[] newArray = new Object[newCapacity]; 195 System.arraycopy(a, 0, newArray, 0, s); 196 array = a = newArray; 197 } 198 System.arraycopy(newPart, 0, a, s, newPartSize); 199 size = newSize; 200 modCount++; 201 return true; 202 } 203 204 /** 205 * Inserts the objects in the specified collection at the specified location 206 * in this List. The objects are added in the order they are returned from 207 * the collection's iterator. 208 * 209 * @param index 210 * the index at which to insert. 211 * @param collection 212 * the collection of objects. 213 * @return {@code true} if this {@code ArrayList} is modified, {@code false} 214 * otherwise. 215 * @throws IndexOutOfBoundsException 216 * when {@code location < 0 || location > size()} 217 */ 218 @Override 219 public boolean addAll(int index, Collection<? extends E> collection) { 220 int s = size; 221 if (index > s || index < 0) { 222 throwIndexOutOfBoundsException(index, s); 223 } 224 Object[] newPart = collection.toArray(); 225 int newPartSize = newPart.length; 226 if (newPartSize == 0) { 227 return false; 228 } 229 Object[] a = array; 230 int newSize = s + newPartSize; // If add overflows, arraycopy will fail 231 if (newSize <= a.length) { 232 System.arraycopy(a, index, a, index + newPartSize, s - index); 233 } else { 234 int newCapacity = newCapacity(newSize - 1); // ~33% growth room 235 Object[] newArray = new Object[newCapacity]; 236 System.arraycopy(a, 0, newArray, 0, index); 237 System.arraycopy(a, index, newArray, index + newPartSize, s-index); 238 array = a = newArray; 239 } 240 System.arraycopy(newPart, 0, a, index, newPartSize); 241 size = newSize; 242 modCount++; 243 return true; 244 } 245 246 /** 247 * This method was extracted to encourage VM to inline callers. 248 * TODO: when we have a VM that can actually inline, move the test in here too! 249 */ 250 static IndexOutOfBoundsException throwIndexOutOfBoundsException(int index, int size) { 251 throw new IndexOutOfBoundsException("Invalid index " + index + ", size is " + size); 252 } 253 254 /** 255 * Removes all elements from this {@code ArrayList}, leaving it empty. 256 * 257 * @see #isEmpty 258 * @see #size 259 */ 260 @Override public void clear() { 261 if (size != 0) { 262 Arrays.fill(array, 0, size, null); 263 size = 0; 264 modCount++; 265 } 266 } 267 268 /** 269 * Returns a new {@code ArrayList} with the same elements, the same size and 270 * the same capacity as this {@code ArrayList}. 271 * 272 * @return a shallow copy of this {@code ArrayList} 273 * @see java.lang.Cloneable 274 */ 275 @Override public Object clone() { 276 try { 277 ArrayList<?> result = (ArrayList<?>) super.clone(); 278 result.array = array.clone(); 279 return result; 280 } catch (CloneNotSupportedException e) { 281 throw new AssertionError(); 282 } 283 } 284 285 /** 286 * Ensures that after this operation the {@code ArrayList} can hold the 287 * specified number of elements without further growing. 288 * 289 * @param minimumCapacity 290 * the minimum capacity asked for. 291 */ 292 public void ensureCapacity(int minimumCapacity) { 293 Object[] a = array; 294 if (a.length < minimumCapacity) { 295 Object[] newArray = new Object[minimumCapacity]; 296 System.arraycopy(a, 0, newArray, 0, size); 297 array = newArray; 298 modCount++; 299 } 300 } 301 302 @SuppressWarnings("unchecked") @Override public E get(int index) { 303 if (index >= size) { 304 throwIndexOutOfBoundsException(index, size); 305 } 306 return (E) array[index]; 307 } 308 309 /** 310 * Returns the number of elements in this {@code ArrayList}. 311 * 312 * @return the number of elements in this {@code ArrayList}. 313 */ 314 @Override public int size() { 315 return size; 316 } 317 318 @Override public boolean isEmpty() { 319 return size == 0; 320 } 321 322 /** 323 * Searches this {@code ArrayList} for the specified object. 324 * 325 * @param object 326 * the object to search for. 327 * @return {@code true} if {@code object} is an element of this 328 * {@code ArrayList}, {@code false} otherwise 329 */ 330 @Override public boolean contains(Object object) { 331 Object[] a = array; 332 int s = size; 333 if (object != null) { 334 for (int i = 0; i < s; i++) { 335 if (object.equals(a[i])) { 336 return true; 337 } 338 } 339 } else { 340 for (int i = 0; i < s; i++) { 341 if (a[i] == null) { 342 return true; 343 } 344 } 345 } 346 return false; 347 } 348 349 @Override public int indexOf(Object object) { 350 Object[] a = array; 351 int s = size; 352 if (object != null) { 353 for (int i = 0; i < s; i++) { 354 if (object.equals(a[i])) { 355 return i; 356 } 357 } 358 } else { 359 for (int i = 0; i < s; i++) { 360 if (a[i] == null) { 361 return i; 362 } 363 } 364 } 365 return -1; 366 } 367 368 @Override public int lastIndexOf(Object object) { 369 Object[] a = array; 370 if (object != null) { 371 for (int i = size - 1; i >= 0; i--) { 372 if (object.equals(a[i])) { 373 return i; 374 } 375 } 376 } else { 377 for (int i = size - 1; i >= 0; i--) { 378 if (a[i] == null) { 379 return i; 380 } 381 } 382 } 383 return -1; 384 } 385 386 /** 387 * Removes the object at the specified location from this list. 388 * 389 * @param index 390 * the index of the object to remove. 391 * @return the removed object. 392 * @throws IndexOutOfBoundsException 393 * when {@code location < 0 || location >= size()} 394 */ 395 @Override public E remove(int index) { 396 Object[] a = array; 397 int s = size; 398 if (index >= s) { 399 throwIndexOutOfBoundsException(index, s); 400 } 401 @SuppressWarnings("unchecked") E result = (E) a[index]; 402 System.arraycopy(a, index + 1, a, index, --s - index); 403 a[s] = null; // Prevent memory leak 404 size = s; 405 modCount++; 406 return result; 407 } 408 409 @Override public boolean remove(Object object) { 410 Object[] a = array; 411 int s = size; 412 if (object != null) { 413 for (int i = 0; i < s; i++) { 414 if (object.equals(a[i])) { 415 System.arraycopy(a, i + 1, a, i, --s - i); 416 a[s] = null; // Prevent memory leak 417 size = s; 418 modCount++; 419 return true; 420 } 421 } 422 } else { 423 for (int i = 0; i < s; i++) { 424 if (a[i] == null) { 425 System.arraycopy(a, i + 1, a, i, --s - i); 426 a[s] = null; // Prevent memory leak 427 size = s; 428 modCount++; 429 return true; 430 } 431 } 432 } 433 return false; 434 } 435 436 @Override protected void removeRange(int fromIndex, int toIndex) { 437 if (fromIndex == toIndex) { 438 return; 439 } 440 Object[] a = array; 441 int s = size; 442 if (fromIndex >= s) { 443 throw new IndexOutOfBoundsException("fromIndex " + fromIndex 444 + " >= size " + size); 445 } 446 if (toIndex > s) { 447 throw new IndexOutOfBoundsException("toIndex " + toIndex 448 + " > size " + size); 449 } 450 if (fromIndex > toIndex) { 451 throw new IndexOutOfBoundsException("fromIndex " + fromIndex 452 + " > toIndex " + toIndex); 453 } 454 455 System.arraycopy(a, toIndex, a, fromIndex, s - toIndex); 456 int rangeSize = toIndex - fromIndex; 457 Arrays.fill(a, s - rangeSize, s, null); 458 size = s - rangeSize; 459 modCount++; 460 } 461 462 /** 463 * Replaces the element at the specified location in this {@code ArrayList} 464 * with the specified object. 465 * 466 * @param index 467 * the index at which to put the specified object. 468 * @param object 469 * the object to add. 470 * @return the previous element at the index. 471 * @throws IndexOutOfBoundsException 472 * when {@code location < 0 || location >= size()} 473 */ 474 @Override public E set(int index, E object) { 475 Object[] a = array; 476 if (index >= size) { 477 throwIndexOutOfBoundsException(index, size); 478 } 479 @SuppressWarnings("unchecked") E result = (E) a[index]; 480 a[index] = object; 481 return result; 482 } 483 484 /** 485 * Returns a new array containing all elements contained in this 486 * {@code ArrayList}. 487 * 488 * @return an array of the elements from this {@code ArrayList} 489 */ 490 @Override public Object[] toArray() { 491 int s = size; 492 Object[] result = new Object[s]; 493 System.arraycopy(array, 0, result, 0, s); 494 return result; 495 } 496 497 /** 498 * Returns an array containing all elements contained in this 499 * {@code ArrayList}. If the specified array is large enough to hold the 500 * elements, the specified array is used, otherwise an array of the same 501 * type is created. If the specified array is used and is larger than this 502 * {@code ArrayList}, the array element following the collection elements 503 * is set to null. 504 * 505 * @param contents 506 * the array. 507 * @return an array of the elements from this {@code ArrayList}. 508 * @throws ArrayStoreException 509 * when the type of an element in this {@code ArrayList} cannot 510 * be stored in the type of the specified array. 511 */ 512 @Override public <T> T[] toArray(T[] contents) { 513 int s = size; 514 if (contents.length < s) { 515 @SuppressWarnings("unchecked") T[] newArray 516 = (T[]) Array.newInstance(contents.getClass().getComponentType(), s); 517 contents = newArray; 518 } 519 System.arraycopy(this.array, 0, contents, 0, s); 520 if (contents.length > s) { 521 contents[s] = null; 522 } 523 return contents; 524 } 525 526 /** 527 * Sets the capacity of this {@code ArrayList} to be the same as the current 528 * size. 529 * 530 * @see #size 531 */ 532 public void trimToSize() { 533 int s = size; 534 if (s == array.length) { 535 return; 536 } 537 if (s == 0) { 538 array = EmptyArray.OBJECT; 539 } else { 540 Object[] newArray = new Object[s]; 541 System.arraycopy(array, 0, newArray, 0, s); 542 array = newArray; 543 } 544 modCount++; 545 } 546 547 @Override public Iterator<E> iterator() { 548 return new ArrayListIterator(); 549 } 550 551 private class ArrayListIterator implements Iterator<E> { 552 /** Number of elements remaining in this iteration */ 553 private int remaining = size; 554 555 /** Index of element that remove() would remove, or -1 if no such elt */ 556 private int removalIndex = -1; 557 558 /** The expected modCount value */ 559 private int expectedModCount = modCount; 560 561 public boolean hasNext() { 562 return remaining != 0; 563 } 564 565 @SuppressWarnings("unchecked") public E next() { 566 ArrayList<E> ourList = ArrayList.this; 567 int rem = remaining; 568 if (ourList.modCount != expectedModCount) { 569 throw new ConcurrentModificationException(); 570 } 571 if (rem == 0) { 572 throw new NoSuchElementException(); 573 } 574 remaining = rem - 1; 575 return (E) ourList.array[removalIndex = ourList.size - rem]; 576 } 577 578 public void remove() { 579 Object[] a = array; 580 int removalIdx = removalIndex; 581 if (modCount != expectedModCount) { 582 throw new ConcurrentModificationException(); 583 } 584 if (removalIdx < 0) { 585 throw new IllegalStateException(); 586 } 587 System.arraycopy(a, removalIdx + 1, a, removalIdx, remaining); 588 a[--size] = null; // Prevent memory leak 589 removalIndex = -1; 590 expectedModCount = ++modCount; 591 } 592 } 593 594 @Override public int hashCode() { 595 Object[] a = array; 596 int hashCode = 1; 597 for (int i = 0, s = size; i < s; i++) { 598 Object e = a[i]; 599 hashCode = 31 * hashCode + (e == null ? 0 : e.hashCode()); 600 } 601 return hashCode; 602 } 603 604 @Override public boolean equals(Object o) { 605 if (o == this) { 606 return true; 607 } 608 if (!(o instanceof List)) { 609 return false; 610 } 611 List<?> that = (List<?>) o; 612 int s = size; 613 if (that.size() != s) { 614 return false; 615 } 616 Object[] a = array; 617 if (that instanceof RandomAccess) { 618 for (int i = 0; i < s; i++) { 619 Object eThis = a[i]; 620 Object ethat = that.get(i); 621 if (eThis == null ? ethat != null : !eThis.equals(ethat)) { 622 return false; 623 } 624 } 625 } else { // Argument list is not random access; use its iterator 626 Iterator<?> it = that.iterator(); 627 for (int i = 0; i < s; i++) { 628 Object eThis = a[i]; 629 Object eThat = it.next(); 630 if (eThis == null ? eThat != null : !eThis.equals(eThat)) { 631 return false; 632 } 633 } 634 } 635 return true; 636 } 637 638 private static final long serialVersionUID = 8683452581122892189L; 639 640 private void writeObject(ObjectOutputStream stream) throws IOException { 641 stream.defaultWriteObject(); 642 stream.writeInt(array.length); 643 for (int i = 0; i < size; i++) { 644 stream.writeObject(array[i]); 645 } 646 } 647 648 private void readObject(ObjectInputStream stream) throws IOException, ClassNotFoundException { 649 stream.defaultReadObject(); 650 int cap = stream.readInt(); 651 if (cap < size) { 652 throw new InvalidObjectException( 653 "Capacity: " + cap + " < size: " + size); 654 } 655 array = (cap == 0 ? EmptyArray.OBJECT : new Object[cap]); 656 for (int i = 0; i < size; i++) { 657 array[i] = stream.readObject(); 658 } 659 } 660 } 661