1adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project/* 2adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * Licensed to the Apache Software Foundation (ASF) under one or more 3adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * contributor license agreements. See the NOTICE file distributed with 4adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * this work for additional information regarding copyright ownership. 5adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * The ASF licenses this file to You under the Apache License, Version 2.0 6adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * (the "License"); you may not use this file except in compliance with 7adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * the License. You may obtain a copy of the License at 8adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * 9adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * http://www.apache.org/licenses/LICENSE-2.0 10adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * 11adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * Unless required by applicable law or agreed to in writing, software 12adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * distributed under the License is distributed on an "AS IS" BASIS, 13adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 14adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * See the License for the specific language governing permissions and 15adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * limitations under the License. 16adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 17adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 18adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Projectpackage java.util; 19adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 20adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Projectimport java.io.IOException; 217de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Blochimport java.io.InvalidObjectException; 22adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Projectimport java.io.ObjectInputStream; 23adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Projectimport java.io.ObjectOutputStream; 24adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Projectimport java.io.Serializable; 25adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Projectimport java.lang.reflect.Array; 266186821cb13f4ac7ff50950c813394367e021eaeJesse Wilsonimport libcore.util.EmptyArray; 27adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 28adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project/** 29438d9883775e6ee31c097e2103a25571d2426cd9Elliott Hughes * ArrayList is an implementation of {@link List}, backed by an array. 30438d9883775e6ee31c097e2103a25571d2426cd9Elliott Hughes * All optional operations including adding, removing, and replacing elements are supported. 31f33eae7e84eb6d3b0f4e86b59605bb3de73009f3Elliott Hughes * 32438d9883775e6ee31c097e2103a25571d2426cd9Elliott Hughes * <p>All elements are permitted, including null. 33f33eae7e84eb6d3b0f4e86b59605bb3de73009f3Elliott Hughes * 34438d9883775e6ee31c097e2103a25571d2426cd9Elliott Hughes * <p>This class is a good choice as your default {@code List} implementation. 35438d9883775e6ee31c097e2103a25571d2426cd9Elliott Hughes * {@link Vector} synchronizes all operations, but not necessarily in a way that's 36438d9883775e6ee31c097e2103a25571d2426cd9Elliott Hughes * meaningful to your application: synchronizing each call to {@code get}, for example, is not 37438d9883775e6ee31c097e2103a25571d2426cd9Elliott Hughes * equivalent to synchronizing the list and iterating over it (which is probably what you intended). 38438d9883775e6ee31c097e2103a25571d2426cd9Elliott Hughes * {@link java.util.concurrent.CopyOnWriteArrayList} is intended for the special case of very high 39438d9883775e6ee31c097e2103a25571d2426cd9Elliott Hughes * concurrency, frequent traversals, and very rare mutations. 40f33eae7e84eb6d3b0f4e86b59605bb3de73009f3Elliott Hughes * 417de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch * @param <E> The element type of this list. 42f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson * @since 1.2 43adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 44693eacca9fa67ad79d1b35dbaad61c5ac1ac457cElliott Hughespublic class ArrayList<E> extends AbstractList<E> implements Cloneable, Serializable, RandomAccess { 457de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch /** 467de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch * The minimum amount by which the capacity of an ArrayList will increase. 477de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch * This tuning parameter controls a time-space tradeoff. This value (12) 487de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch * gives empirically good results and is arguably consistent with the 497de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch * RI's specified default initial capacity of 10: instead of 10, we start 507de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch * with 0 (sans allocation) and jump to 12. 517de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch */ 527de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch private static final int MIN_CAPACITY_INCREMENT = 12; 53adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 547de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch /** 557de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch * The number of elements in this list. 567de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch */ 577de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch int size; 58adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 59adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 607de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch * The elements in this list, followed by nulls. 61adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 627de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch transient Object[] array; 63adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 64adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 65adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * Constructs a new instance of {@code ArrayList} with the specified 667de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch * initial capacity. 67f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson * 68adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @param capacity 69adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * the initial capacity of this {@code ArrayList}. 70adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 71adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public ArrayList(int capacity) { 72f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson if (capacity < 0) { 73cff1616012dc0d56c2da9af2b9b1183e76c7e044Elliott Hughes throw new IllegalArgumentException("capacity < 0: " + capacity); 74adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 75693eacca9fa67ad79d1b35dbaad61c5ac1ac457cElliott Hughes array = (capacity == 0 ? EmptyArray.OBJECT : new Object[capacity]); 767de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch } 777de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch 787de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch /** 797de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch * Constructs a new {@code ArrayList} instance with zero initial capacity. 807de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch */ 817de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch public ArrayList() { 82693eacca9fa67ad79d1b35dbaad61c5ac1ac457cElliott Hughes array = EmptyArray.OBJECT; 83adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 84adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 85adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 86adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * Constructs a new instance of {@code ArrayList} containing the elements of 877de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch * the specified collection. 88f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson * 89adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @param collection 90adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * the collection of elements to add. 91adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 92adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public ArrayList(Collection<? extends E> collection) { 93e728d7cc9835669fcf5870b107cc95f52ee58070Kenny Root if (collection == null) { 94e728d7cc9835669fcf5870b107cc95f52ee58070Kenny Root throw new NullPointerException("collection == null"); 95e728d7cc9835669fcf5870b107cc95f52ee58070Kenny Root } 96e728d7cc9835669fcf5870b107cc95f52ee58070Kenny Root 977de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch Object[] a = collection.toArray(); 987de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch if (a.getClass() != Object[].class) { 997de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch Object[] newArray = new Object[a.length]; 1007de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch System.arraycopy(a, 0, newArray, 0, a.length); 1017de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch a = newArray; 1027de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch } 1037de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch array = a; 1047de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch size = a.length; 105adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 106f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson 1077de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch /** 1087de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch * Adds the specified object at the end of this {@code ArrayList}. 1097de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch * 1107de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch * @param object 1117de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch * the object to add. 1127de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch * @return always true 1137de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch */ 1147de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch @Override public boolean add(E object) { 1157de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch Object[] a = array; 1167de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch int s = size; 1177de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch if (s == a.length) { 1187de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch Object[] newArray = new Object[s + 1197de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch (s < (MIN_CAPACITY_INCREMENT / 2) ? 1207de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch MIN_CAPACITY_INCREMENT : s >> 1)]; 1217de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch System.arraycopy(a, 0, newArray, 0, s); 1227de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch array = a = newArray; 123adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 1247de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch a[s] = object; 1257de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch size = s + 1; 1267de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch modCount++; 1277de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch return true; 128adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 129adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 130adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 131adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * Inserts the specified object into this {@code ArrayList} at the specified 132adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * location. The object is inserted before any previous element at the 133adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * specified location. If the location is equal to the size of this 134adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * {@code ArrayList}, the object is added at the end. 135f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson * 1367de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch * @param index 137adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * the index at which to insert the object. 138adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @param object 139adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * the object to add. 140adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @throws IndexOutOfBoundsException 141de2ae30023028e82e4f5ae0c9e88b05649a4c1beElliott Hughes * when {@code location < 0 || location > size()} 142adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 1437de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch @Override public void add(int index, E object) { 1447de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch Object[] a = array; 1457de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch int s = size; 146a00b0e541a77ec76e0a327b2442147869c232ed0Jesse Wilson if (index > s || index < 0) { 1477de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch throwIndexOutOfBoundsException(index, s); 148adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 149adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 1507de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch if (s < a.length) { 1517de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch System.arraycopy(a, index, a, index + 1, s - index); 1527de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch } else { 1537de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch // assert s == a.length; 1547de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch Object[] newArray = new Object[newCapacity(s)]; 1557de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch System.arraycopy(a, 0, newArray, 0, index); 1567de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch System.arraycopy(a, index, newArray, index + 1, s - index); 1577de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch array = a = newArray; 1587de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch } 1597de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch a[index] = object; 1607de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch size = s + 1; 161adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project modCount++; 162adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 163adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 164adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 1657de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch * This method controls the growth of ArrayList capacities. It represents 1667de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch * a time-space tradeoff: we don't want to grow lists too frequently 1677de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch * (which wastes time and fragments storage), but we don't want to waste 1687de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch * too much space in unused excess capacity. 169f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson * 1707de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch * NOTE: This method is inlined into {@link #add(Object)} for performance. 1717de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch * If you change the method, change it there too! 172adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 1737de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch private static int newCapacity(int currentCapacity) { 1747de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch int increment = (currentCapacity < (MIN_CAPACITY_INCREMENT / 2) ? 1757de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch MIN_CAPACITY_INCREMENT : currentCapacity >> 1); 1767de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch return currentCapacity + increment; 177adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 178adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 179adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 1807de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch * Adds the objects in the specified collection to this {@code ArrayList}. 181f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson * 182adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @param collection 183adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * the collection of objects. 184adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @return {@code true} if this {@code ArrayList} is modified, {@code false} 185adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * otherwise. 186adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 1877de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch @Override public boolean addAll(Collection<? extends E> collection) { 1887de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch Object[] newPart = collection.toArray(); 1897de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch int newPartSize = newPart.length; 1907de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch if (newPartSize == 0) { 191a389b4a499f40379b0b204d7ba1c2057663d95c0Jesse Wilson return false; 192a389b4a499f40379b0b204d7ba1c2057663d95c0Jesse Wilson } 1937de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch Object[] a = array; 1947de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch int s = size; 1957de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch int newSize = s + newPartSize; // If add overflows, arraycopy will fail 1967de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch if (newSize > a.length) { 1977de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch int newCapacity = newCapacity(newSize - 1); // ~33% growth room 1987de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch Object[] newArray = new Object[newCapacity]; 1997de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch System.arraycopy(a, 0, newArray, 0, s); 2007de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch array = a = newArray; 201adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 2027de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch System.arraycopy(newPart, 0, a, s, newPartSize); 2037de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch size = newSize; 204a389b4a499f40379b0b204d7ba1c2057663d95c0Jesse Wilson modCount++; 205a389b4a499f40379b0b204d7ba1c2057663d95c0Jesse Wilson return true; 206adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 207adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 208adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 2097de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch * Inserts the objects in the specified collection at the specified location 2107de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch * in this List. The objects are added in the order they are returned from 2117de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch * the collection's iterator. 212f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson * 2137de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch * @param index 2147de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch * the index at which to insert. 215adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @param collection 216adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * the collection of objects. 217adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @return {@code true} if this {@code ArrayList} is modified, {@code false} 218adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * otherwise. 2197de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch * @throws IndexOutOfBoundsException 220de2ae30023028e82e4f5ae0c9e88b05649a4c1beElliott Hughes * when {@code location < 0 || location > size()} 221adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 222adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project @Override 2237de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch public boolean addAll(int index, Collection<? extends E> collection) { 224a00b0e541a77ec76e0a327b2442147869c232ed0Jesse Wilson int s = size; 225a00b0e541a77ec76e0a327b2442147869c232ed0Jesse Wilson if (index > s || index < 0) { 226a00b0e541a77ec76e0a327b2442147869c232ed0Jesse Wilson throwIndexOutOfBoundsException(index, s); 227a00b0e541a77ec76e0a327b2442147869c232ed0Jesse Wilson } 2287de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch Object[] newPart = collection.toArray(); 2297de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch int newPartSize = newPart.length; 2307de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch if (newPartSize == 0) { 231f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson return false; 232adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 2337de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch Object[] a = array; 2347de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch int newSize = s + newPartSize; // If add overflows, arraycopy will fail 2357de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch if (newSize <= a.length) { 2367de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch System.arraycopy(a, index, a, index + newPartSize, s - index); 2377de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch } else { 2387de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch int newCapacity = newCapacity(newSize - 1); // ~33% growth room 2397de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch Object[] newArray = new Object[newCapacity]; 2407de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch System.arraycopy(a, 0, newArray, 0, index); 2417de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch System.arraycopy(a, index, newArray, index + newPartSize, s-index); 2427de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch array = a = newArray; 2437de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch } 2447de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch System.arraycopy(newPart, 0, a, index, newPartSize); 2457de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch size = newSize; 246f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson modCount++; 247f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson return true; 248adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 249adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 250b9cc455ed89df1a0cf4186c92b352c9649995d96Elliott Hughes /** 251b9cc455ed89df1a0cf4186c92b352c9649995d96Elliott Hughes * This method was extracted to encourage VM to inline callers. 252b9cc455ed89df1a0cf4186c92b352c9649995d96Elliott Hughes * TODO: when we have a VM that can actually inline, move the test in here too! 253b9cc455ed89df1a0cf4186c92b352c9649995d96Elliott Hughes */ 25487201ff38d682b55f456c50da3e742459a56d258Brian Carlstrom static IndexOutOfBoundsException throwIndexOutOfBoundsException(int index, int size) { 255b9cc455ed89df1a0cf4186c92b352c9649995d96Elliott Hughes throw new IndexOutOfBoundsException("Invalid index " + index + ", size is " + size); 2567de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch } 2577de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch 258adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 259adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * Removes all elements from this {@code ArrayList}, leaving it empty. 260f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson * 261adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @see #isEmpty 262adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @see #size 263adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 2647de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch @Override public void clear() { 2657de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch if (size != 0) { 2667de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch Arrays.fill(array, 0, size, null); 2677de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch size = 0; 268adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project modCount++; 269adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 270adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 271adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 272adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 273adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * Returns a new {@code ArrayList} with the same elements, the same size and 274adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * the same capacity as this {@code ArrayList}. 275f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson * 276adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @return a shallow copy of this {@code ArrayList} 277adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @see java.lang.Cloneable 278adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 2797de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch @Override public Object clone() { 280adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project try { 2817de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch ArrayList<?> result = (ArrayList<?>) super.clone(); 2827de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch result.array = array.clone(); 2837de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch return result; 284adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } catch (CloneNotSupportedException e) { 2857de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch throw new AssertionError(); 286adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 287adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 288adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 289adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 290adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * Ensures that after this operation the {@code ArrayList} can hold the 291adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * specified number of elements without further growing. 292f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson * 293adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @param minimumCapacity 294adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * the minimum capacity asked for. 295adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 296adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public void ensureCapacity(int minimumCapacity) { 2977de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch Object[] a = array; 2987de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch if (a.length < minimumCapacity) { 2997de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch Object[] newArray = new Object[minimumCapacity]; 3007de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch System.arraycopy(a, 0, newArray, 0, size); 3017de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch array = newArray; 3027de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch modCount++; 303adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 304adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 305adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 3067de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch @SuppressWarnings("unchecked") @Override public E get(int index) { 3077de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch if (index >= size) { 3087de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch throwIndexOutOfBoundsException(index, size); 3097de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch } 3107de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch return (E) array[index]; 311adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 312adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 3137de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch /** 3147de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch * Returns the number of elements in this {@code ArrayList}. 3157de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch * 3167de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch * @return the number of elements in this {@code ArrayList}. 3177de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch */ 3187de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch @Override public int size() { 3197de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch return size; 3207de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch } 3217de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch 3227de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch @Override public boolean isEmpty() { 3237de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch return size == 0; 324adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 325adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 3267de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch /** 3277de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch * Searches this {@code ArrayList} for the specified object. 3287de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch * 3297de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch * @param object 3307de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch * the object to search for. 3317de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch * @return {@code true} if {@code object} is an element of this 3327de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch * {@code ArrayList}, {@code false} otherwise 3337de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch */ 3347de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch @Override public boolean contains(Object object) { 3357de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch Object[] a = array; 3367de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch int s = size; 3377de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch if (object != null) { 3387de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch for (int i = 0; i < s; i++) { 3397de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch if (object.equals(a[i])) { 3407de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch return true; 3417de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch } 342adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 343adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } else { 3447de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch for (int i = 0; i < s; i++) { 3457de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch if (a[i] == null) { 3467de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch return true; 3477de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch } 348adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 349adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 3507de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch return false; 351adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 352adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 3537de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch @Override public int indexOf(Object object) { 3547de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch Object[] a = array; 3557de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch int s = size; 356adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if (object != null) { 3577de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch for (int i = 0; i < s; i++) { 3587de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch if (object.equals(a[i])) { 3597de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch return i; 360adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 361adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 362adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } else { 3637de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch for (int i = 0; i < s; i++) { 3647de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch if (a[i] == null) { 3657de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch return i; 366adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 367adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 368adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 369adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return -1; 370adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 371adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 3727de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch @Override public int lastIndexOf(Object object) { 3737de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch Object[] a = array; 374adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if (object != null) { 3757de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch for (int i = size - 1; i >= 0; i--) { 3767de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch if (object.equals(a[i])) { 3777de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch return i; 378adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 379adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 380adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } else { 3817de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch for (int i = size - 1; i >= 0; i--) { 3827de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch if (a[i] == null) { 3837de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch return i; 384adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 385adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 386adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 387adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return -1; 388adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 389adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 390adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 391adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * Removes the object at the specified location from this list. 392f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson * 3937de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch * @param index 394adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * the index of the object to remove. 395adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @return the removed object. 396adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @throws IndexOutOfBoundsException 397de2ae30023028e82e4f5ae0c9e88b05649a4c1beElliott Hughes * when {@code location < 0 || location >= size()} 398adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 3997de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch @Override public E remove(int index) { 4007de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch Object[] a = array; 4017de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch int s = size; 4027de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch if (index >= s) { 4037de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch throwIndexOutOfBoundsException(index, s); 404adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 4057de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch @SuppressWarnings("unchecked") E result = (E) a[index]; 4067de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch System.arraycopy(a, index + 1, a, index, --s - index); 4077de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch a[s] = null; // Prevent memory leak 4087de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch size = s; 409adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project modCount++; 410adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return result; 411adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 412adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 4137de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch @Override public boolean remove(Object object) { 4147de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch Object[] a = array; 4157de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch int s = size; 4167de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch if (object != null) { 4177de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch for (int i = 0; i < s; i++) { 4187de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch if (object.equals(a[i])) { 4197de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch System.arraycopy(a, i + 1, a, i, --s - i); 4207de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch a[s] = null; // Prevent memory leak 4217de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch size = s; 4227de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch modCount++; 4237de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch return true; 4247de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch } 4257de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch } 4267de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch } else { 4277de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch for (int i = 0; i < s; i++) { 4287de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch if (a[i] == null) { 4297de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch System.arraycopy(a, i + 1, a, i, --s - i); 4307de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch a[s] = null; // Prevent memory leak 4317de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch size = s; 4327de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch modCount++; 4337de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch return true; 4347de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch } 4357de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch } 436adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 437adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return false; 438adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 439adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 4407de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch @Override protected void removeRange(int fromIndex, int toIndex) { 441a00b0e541a77ec76e0a327b2442147869c232ed0Jesse Wilson if (fromIndex == toIndex) { 442a00b0e541a77ec76e0a327b2442147869c232ed0Jesse Wilson return; 443a00b0e541a77ec76e0a327b2442147869c232ed0Jesse Wilson } 4447de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch Object[] a = array; 4457de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch int s = size; 4467de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch if (fromIndex >= s) { 4477de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch throw new IndexOutOfBoundsException("fromIndex " + fromIndex 4487de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch + " >= size " + size); 449adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 4507de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch if (toIndex > s) { 4517de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch throw new IndexOutOfBoundsException("toIndex " + toIndex 4527de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch + " > size " + size); 4537de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch } 4547de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch if (fromIndex > toIndex) { 4557de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch throw new IndexOutOfBoundsException("fromIndex " + fromIndex 4567de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch + " > toIndex " + toIndex); 4577de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch } 4587de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch 4597de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch System.arraycopy(a, toIndex, a, fromIndex, s - toIndex); 4607de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch int rangeSize = toIndex - fromIndex; 4617de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch Arrays.fill(a, s - rangeSize, s, null); 4627de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch size = s - rangeSize; 4637de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch modCount++; 464adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 465adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 466adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 467adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * Replaces the element at the specified location in this {@code ArrayList} 468adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * with the specified object. 469f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson * 4707de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch * @param index 471adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * the index at which to put the specified object. 472adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @param object 473adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * the object to add. 474adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @return the previous element at the index. 475adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @throws IndexOutOfBoundsException 476de2ae30023028e82e4f5ae0c9e88b05649a4c1beElliott Hughes * when {@code location < 0 || location >= size()} 477adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 4787de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch @Override public E set(int index, E object) { 4797de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch Object[] a = array; 4807de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch if (index >= size) { 4817de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch throwIndexOutOfBoundsException(index, size); 482adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 4837de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch @SuppressWarnings("unchecked") E result = (E) a[index]; 4847de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch a[index] = object; 4857de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch return result; 486adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 487adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 488adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 489adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * Returns a new array containing all elements contained in this 490adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * {@code ArrayList}. 491f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson * 492adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @return an array of the elements from this {@code ArrayList} 493adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 4947de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch @Override public Object[] toArray() { 4957de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch int s = size; 4967de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch Object[] result = new Object[s]; 4977de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch System.arraycopy(array, 0, result, 0, s); 498adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return result; 499adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 500adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 501adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 502adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * Returns an array containing all elements contained in this 503adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * {@code ArrayList}. If the specified array is large enough to hold the 504adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * elements, the specified array is used, otherwise an array of the same 505adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * type is created. If the specified array is used and is larger than this 506adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * {@code ArrayList}, the array element following the collection elements 507adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * is set to null. 508f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson * 509adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @param contents 510adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * the array. 511adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @return an array of the elements from this {@code ArrayList}. 512adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @throws ArrayStoreException 513adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * when the type of an element in this {@code ArrayList} cannot 514adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * be stored in the type of the specified array. 515adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 5167de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch @Override public <T> T[] toArray(T[] contents) { 5177de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch int s = size; 5187de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch if (contents.length < s) { 5197de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch @SuppressWarnings("unchecked") T[] newArray 5207de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch = (T[]) Array.newInstance(contents.getClass().getComponentType(), s); 5217de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch contents = newArray; 522adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 5237de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch System.arraycopy(this.array, 0, contents, 0, s); 5247de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch if (contents.length > s) { 5257de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch contents[s] = null; 526adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 527adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return contents; 528adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 529adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 530adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 531adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * Sets the capacity of this {@code ArrayList} to be the same as the current 532adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * size. 533f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson * 534adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @see #size 535adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 536adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public void trimToSize() { 5377de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch int s = size; 5387de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch if (s == array.length) { 5397de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch return; 5407de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch } 5417de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch if (s == 0) { 542693eacca9fa67ad79d1b35dbaad61c5ac1ac457cElliott Hughes array = EmptyArray.OBJECT; 5437de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch } else { 5447de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch Object[] newArray = new Object[s]; 5457de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch System.arraycopy(array, 0, newArray, 0, s); 5467de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch array = newArray; 5477de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch } 5487de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch modCount++; 5497de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch } 5507de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch 5517de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch @Override public Iterator<E> iterator() { 5527de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch return new ArrayListIterator(); 5537de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch } 5547de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch 5557de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch private class ArrayListIterator implements Iterator<E> { 5567de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch /** Number of elements remaining in this iteration */ 5577de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch private int remaining = size; 5587de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch 5597de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch /** Index of element that remove() would remove, or -1 if no such elt */ 5607de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch private int removalIndex = -1; 5617de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch 5627de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch /** The expected modCount value */ 5637de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch private int expectedModCount = modCount; 5647de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch 5657de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch public boolean hasNext() { 5667de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch return remaining != 0; 5677de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch } 5687de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch 5697de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch @SuppressWarnings("unchecked") public E next() { 5707de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch ArrayList<E> ourList = ArrayList.this; 5717de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch int rem = remaining; 5727de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch if (ourList.modCount != expectedModCount) { 5737de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch throw new ConcurrentModificationException(); 5747de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch } 5757de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch if (rem == 0) { 5767de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch throw new NoSuchElementException(); 5777de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch } 5787de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch remaining = rem - 1; 5797de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch return (E) ourList.array[removalIndex = ourList.size - rem]; 5807de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch } 5817de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch 5827de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch public void remove() { 5837de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch Object[] a = array; 5847de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch int removalIdx = removalIndex; 5857de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch if (modCount != expectedModCount) { 5867de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch throw new ConcurrentModificationException(); 5877de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch } 5887de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch if (removalIdx < 0) { 5897de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch throw new IllegalStateException(); 5907de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch } 5917de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch System.arraycopy(a, removalIdx + 1, a, removalIdx, remaining); 5927de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch a[--size] = null; // Prevent memory leak 5937de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch removalIndex = -1; 5947de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch expectedModCount = ++modCount; 5957de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch } 596adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 597adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 5987de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch @Override public int hashCode() { 5997de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch Object[] a = array; 6007de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch int hashCode = 1; 6017de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch for (int i = 0, s = size; i < s; i++) { 6027de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch Object e = a[i]; 6037de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch hashCode = 31 * hashCode + (e == null ? 0 : e.hashCode()); 6047de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch } 6057de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch return hashCode; 6067de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch } 6077de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch 6087de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch @Override public boolean equals(Object o) { 6097de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch if (o == this) { 6107de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch return true; 6117de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch } 6127de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch if (!(o instanceof List)) { 6137de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch return false; 6147de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch } 6157de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch List<?> that = (List<?>) o; 6167de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch int s = size; 6177de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch if (that.size() != s) { 6187de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch return false; 6197de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch } 6207de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch Object[] a = array; 6217de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch if (that instanceof RandomAccess) { 6227de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch for (int i = 0; i < s; i++) { 6237de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch Object eThis = a[i]; 6247de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch Object ethat = that.get(i); 6257de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch if (eThis == null ? ethat != null : !eThis.equals(ethat)) { 6267de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch return false; 6277de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch } 6287de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch } 6297de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch } else { // Argument list is not random access; use its iterator 6307de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch Iterator<?> it = that.iterator(); 6317de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch for (int i = 0; i < s; i++) { 6327de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch Object eThis = a[i]; 6337de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch Object eThat = it.next(); 6347de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch if (eThis == null ? eThat != null : !eThis.equals(eThat)) { 6357de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch return false; 6367de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch } 6377de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch } 6387de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch } 6397de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch return true; 6407de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch } 6417de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch 6427de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch private static final long serialVersionUID = 8683452581122892189L; 643adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 644adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project private void writeObject(ObjectOutputStream stream) throws IOException { 6457de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch stream.defaultWriteObject(); 646adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project stream.writeInt(array.length); 6477de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch for (int i = 0; i < size; i++) { 6487de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch stream.writeObject(array[i]); 649adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 650adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 651adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 652693eacca9fa67ad79d1b35dbaad61c5ac1ac457cElliott Hughes private void readObject(ObjectInputStream stream) throws IOException, ClassNotFoundException { 6537de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch stream.defaultReadObject(); 6547de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch int cap = stream.readInt(); 6557de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch if (cap < size) { 6567de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch throw new InvalidObjectException( 6577de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch "Capacity: " + cap + " < size: " + size); 6587de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch } 659693eacca9fa67ad79d1b35dbaad61c5ac1ac457cElliott Hughes array = (cap == 0 ? EmptyArray.OBJECT : new Object[cap]); 6607de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch for (int i = 0; i < size; i++) { 6617de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch array[i] = stream.readObject(); 662adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 663adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 6647de2d41b95fc968b0ccc530c28d66f003ff9ab2aJoshua Bloch } 665