1: /* ArrayList.java -- JDK1.2's answer to Vector; this is an array-backed 2: implementation of the List interface 3: Copyright (C) 1998, 1999, 2000, 2001, 2004, 2005 Free Software Foundation, Inc. 4: 5: This file is part of GNU Classpath. 6: 7: GNU Classpath is free software; you can redistribute it and/or modify 8: it under the terms of the GNU General Public License as published by 9: the Free Software Foundation; either version 2, or (at your option) 10: any later version. 11: 12: GNU Classpath is distributed in the hope that it will be useful, but 13: WITHOUT ANY WARRANTY; without even the implied warranty of 14: MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 15: General Public License for more details. 16: 17: You should have received a copy of the GNU General Public License 18: along with GNU Classpath; see the file COPYING. If not, write to the 19: Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 20: 02110-1301 USA. 21: 22: Linking this library statically or dynamically with other modules is 23: making a combined work based on this library. Thus, the terms and 24: conditions of the GNU General Public License cover the whole 25: combination. 26: 27: As a special exception, the copyright holders of this library give you 28: permission to link this library with independent modules to produce an 29: executable, regardless of the license terms of these independent 30: modules, and to copy and distribute the resulting executable under 31: terms of your choice, provided that you also meet, for each linked 32: independent module, the terms and conditions of the license of that 33: module. An independent module is a module which is not derived from 34: or based on this library. If you modify this library, you may extend 35: this exception to your version of the library, but you are not 36: obligated to do so. If you do not wish to do so, delete this 37: exception statement from your version. */ 38: 39: 40: package java.util; 41: 42: import java.io.IOException; 43: import java.io.ObjectInputStream; 44: import java.io.ObjectOutputStream; 45: import java.io.Serializable; 46: import java.lang.reflect.Array; 47: 48: /** 49: * An array-backed implementation of the List interface. This implements 50: * all optional list operations, and permits null elements, so that it is 51: * better than Vector, which it replaces. Random access is roughly constant 52: * time, and iteration is roughly linear time, so it is nice and fast, with 53: * less overhead than a LinkedList. 54: * <p> 55: * 56: * Each list has a capacity, and as the array reaches that capacity it 57: * is automatically transferred to a larger array. You also have access to 58: * ensureCapacity and trimToSize to control the backing array's size, avoiding 59: * reallocation or wasted memory. 60: * <p> 61: * 62: * ArrayList is not synchronized, so if you need multi-threaded access, 63: * consider using:<br> 64: * <code>List l = Collections.synchronizedList(new ArrayList(...));</code> 65: * <p> 66: * 67: * The iterators are <i>fail-fast</i>, meaning that any structural 68: * modification, except for <code>remove()</code> called on the iterator 69: * itself, cause the iterator to throw a 70: * {@link ConcurrentModificationException} rather than exhibit 71: * non-deterministic behavior. 72: * 73: * @author Jon A. Zeppieri 74: * @author Bryce McKinlay 75: * @author Eric Blake (ebb9@email.byu.edu) 76: * @see Collection 77: * @see List 78: * @see LinkedList 79: * @see Vector 80: * @see Collections#synchronizedList(List) 81: * @see AbstractList 82: * @status updated to 1.4 83: */ 84: public class ArrayList<E> extends AbstractList<E> 85: implements List<E>, RandomAccess, Cloneable, Serializable 86: { 87: /** 88: * Compatible with JDK 1.2 89: */ 90: private static final long serialVersionUID = 8683452581122892189L; 91: 92: /** 93: * The default capacity for new ArrayLists. 94: */ 95: private static final int DEFAULT_CAPACITY = 10; 96: 97: /** 98: * The number of elements in this list. 99: * @serial the list size 100: */ 101: private int size; 102: 103: /** 104: * Where the data is stored. 105: */ 106: private transient E[] data; 107: 108: /** 109: * Construct a new ArrayList with the supplied initial capacity. 110: * 111: * @param capacity initial capacity of this ArrayList 112: * @throws IllegalArgumentException if capacity is negative 113: */ 114: public ArrayList(int capacity) 115: { 116: // Must explicitly check, to get correct exception. 117: if (capacity < 0) 118: throw new IllegalArgumentException(); 119: data = (E[]) new Object[capacity]; 120: } 121: 122: /** 123: * Construct a new ArrayList with the default capacity (16). 124: */ 125: public ArrayList() 126: { 127: this(DEFAULT_CAPACITY); 128: } 129: 130: /** 131: * Construct a new ArrayList, and initialize it with the elements 132: * in the supplied Collection. The initial capacity is 110% of the 133: * Collection's size. 134: * 135: * @param c the collection whose elements will initialize this list 136: * @throws NullPointerException if c is null 137: */ 138: public ArrayList(Collection<? extends E> c) 139: { 140: this((int) (c.size() * 1.1f)); 141: addAll(c); 142: } 143: 144: /** 145: * Trims the capacity of this List to be equal to its size; 146: * a memory saver. 147: */ 148: public void trimToSize() 149: { 150: // Not a structural change from the perspective of iterators on this list, 151: // so don't update modCount. 152: if (size != data.length) 153: { 154: E[] newData = (E[]) new Object[size]; 155: System.arraycopy(data, 0, newData, 0, size); 156: data = newData; 157: } 158: } 159: 160: /** 161: * Guarantees that this list will have at least enough capacity to 162: * hold minCapacity elements. This implementation will grow the list to 163: * max(current * 2, minCapacity) if (minCapacity > current). The JCL says 164: * explictly that "this method increases its capacity to minCap", while 165: * the JDK 1.3 online docs specify that the list will grow to at least the 166: * size specified. 167: * 168: * @param minCapacity the minimum guaranteed capacity 169: */ 170: public void ensureCapacity(int minCapacity) 171: { 172: int current = data.length; 173: 174: if (minCapacity > current) 175: { 176: E[] newData = (E[]) new Object[Math.max(current * 2, minCapacity)]; 177: System.arraycopy(data, 0, newData, 0, size); 178: data = newData; 179: } 180: } 181: 182: /** 183: * Returns the number of elements in this list. 184: * 185: * @return the list size 186: */ 187: public int size() 188: { 189: return size; 190: } 191: 192: /** 193: * Checks if the list is empty. 194: * 195: * @return true if there are no elements 196: */ 197: public boolean isEmpty() 198: { 199: return size == 0; 200: } 201: 202: /** 203: * Returns true iff element is in this ArrayList. 204: * 205: * @param e the element whose inclusion in the List is being tested 206: * @return true if the list contains e 207: */ 208: public boolean contains(Object e) 209: { 210: return indexOf(e) != -1; 211: } 212: 213: /** 214: * Returns the lowest index at which element appears in this List, or 215: * -1 if it does not appear. 216: * 217: * @param e the element whose inclusion in the List is being tested 218: * @return the index where e was found 219: */ 220: public int indexOf(Object e) 221: { 222: for (int i = 0; i < size; i++) 223: if (equals(e, data[i])) 224: return i; 225: return -1; 226: } 227: 228: /** 229: * Returns the highest index at which element appears in this List, or 230: * -1 if it does not appear. 231: * 232: * @param e the element whose inclusion in the List is being tested 233: * @return the index where e was found 234: */ 235: public int lastIndexOf(Object e) 236: { 237: for (int i = size - 1; i >= 0; i--) 238: if (equals(e, data[i])) 239: return i; 240: return -1; 241: } 242: 243: /** 244: * Creates a shallow copy of this ArrayList (elements are not cloned). 245: * 246: * @return the cloned object 247: */ 248: public Object clone() 249: { 250: ArrayList<E> clone = null; 251: try 252: { 253: clone = (ArrayList<E>) super.clone(); 254: clone.data = (E[]) data.clone(); 255: } 256: catch (CloneNotSupportedException e) 257: { 258: // Impossible to get here. 259: } 260: return clone; 261: } 262: 263: /** 264: * Returns an Object array containing all of the elements in this ArrayList. 265: * The array is independent of this list. 266: * 267: * @return an array representation of this list 268: */ 269: public Object[] toArray() 270: { 271: E[] array = (E[]) new Object[size]; 272: System.arraycopy(data, 0, array, 0, size); 273: return array; 274: } 275: 276: /** 277: * Returns an Array whose component type is the runtime component type of 278: * the passed-in Array. The returned Array is populated with all of the 279: * elements in this ArrayList. If the passed-in Array is not large enough 280: * to store all of the elements in this List, a new Array will be created 281: * and returned; if the passed-in Array is <i>larger</i> than the size 282: * of this List, then size() index will be set to null. 283: * 284: * @param a the passed-in Array 285: * @return an array representation of this list 286: * @throws ArrayStoreException if the runtime type of a does not allow 287: * an element in this list 288: * @throws NullPointerException if a is null 289: */ 290: public <T> T[] toArray(T[] a) 291: { 292: if (a.length < size) 293: a = (T[]) Array.newInstance(a.getClass().getComponentType(), size); 294: else if (a.length > size) 295: a[size] = null; 296: System.arraycopy(data, 0, a, 0, size); 297: return a; 298: } 299: 300: /** 301: * Retrieves the element at the user-supplied index. 302: * 303: * @param index the index of the element we are fetching 304: * @throws IndexOutOfBoundsException if index < 0 || index >= size() 305: */ 306: public E get(int index) 307: { 308: checkBoundExclusive(index); 309: return data[index]; 310: } 311: 312: /** 313: * Sets the element at the specified index. The new element, e, 314: * can be an object of any type or null. 315: * 316: * @param index the index at which the element is being set 317: * @param e the element to be set 318: * @return the element previously at the specified index 319: * @throws IndexOutOfBoundsException if index < 0 || index >= 0 320: */ 321: public E set(int index, E e) 322: { 323: checkBoundExclusive(index); 324: E result = data[index]; 325: data[index] = e; 326: return result; 327: } 328: 329: /** 330: * Appends the supplied element to the end of this list. 331: * The element, e, can be an object of any type or null. 332: * 333: * @param e the element to be appended to this list 334: * @return true, the add will always succeed 335: */ 336: public boolean add(E e) 337: { 338: modCount++; 339: if (size == data.length) 340: ensureCapacity(size + 1); 341: data[size++] = e; 342: return true; 343: } 344: 345: /** 346: * Adds the supplied element at the specified index, shifting all 347: * elements currently at that index or higher one to the right. 348: * The element, e, can be an object of any type or null. 349: * 350: * @param index the index at which the element is being added 351: * @param e the item being added 352: * @throws IndexOutOfBoundsException if index < 0 || index > size() 353: */ 354: public void add(int index, E e) 355: { 356: checkBoundInclusive(index); 357: modCount++; 358: if (size == data.length) 359: ensureCapacity(size + 1); 360: if (index != size) 361: System.arraycopy(data, index, data, index + 1, size - index); 362: data[index] = e; 363: size++; 364: } 365: 366: /** 367: * Removes the element at the user-supplied index. 368: * 369: * @param index the index of the element to be removed 370: * @return the removed Object 371: * @throws IndexOutOfBoundsException if index < 0 || index >= size() 372: */ 373: public E remove(int index) 374: { 375: checkBoundExclusive(index); 376: E r = data[index]; 377: modCount++; 378: if (index != --size) 379: System.arraycopy(data, index + 1, data, index, size - index); 380: // Aid for garbage collection by releasing this pointer. 381: data[size] = null; 382: return r; 383: } 384: 385: /** 386: * Removes all elements from this List 387: */ 388: public void clear() 389: { 390: if (size > 0) 391: { 392: modCount++; 393: // Allow for garbage collection. 394: Arrays.fill(data, 0, size, null); 395: size = 0; 396: } 397: } 398: 399: /** 400: * Add each element in the supplied Collection to this List. It is undefined 401: * what happens if you modify the list while this is taking place; for 402: * example, if the collection contains this list. c can contain objects 403: * of any type, as well as null values. 404: * 405: * @param c a Collection containing elements to be added to this List 406: * @return true if the list was modified, in other words c is not empty 407: * @throws NullPointerException if c is null 408: */ 409: public boolean addAll(Collection<? extends E> c) 410: { 411: return addAll(size, c); 412: } 413: 414: /** 415: * Add all elements in the supplied collection, inserting them beginning 416: * at the specified index. c can contain objects of any type, as well 417: * as null values. 418: * 419: * @param index the index at which the elements will be inserted 420: * @param c the Collection containing the elements to be inserted 421: * @throws IndexOutOfBoundsException if index < 0 || index > 0 422: * @throws NullPointerException if c is null 423: */ 424: public boolean addAll(int index, Collection<? extends E> c) 425: { 426: checkBoundInclusive(index); 427: Iterator<? extends E> itr = c.iterator(); 428: int csize = c.size(); 429: 430: modCount++; 431: if (csize + size > data.length) 432: ensureCapacity(size + csize); 433: int end = index + csize; 434: if (size > 0 && index != size) 435: System.arraycopy(data, index, data, end, size - index); 436: size += csize; 437: for ( ; index < end; index++) 438: data[index] = itr.next(); 439: return csize > 0; 440: } 441: 442: /** 443: * Removes all elements in the half-open interval [fromIndex, toIndex). 444: * Does nothing when toIndex is equal to fromIndex. 445: * 446: * @param fromIndex the first index which will be removed 447: * @param toIndex one greater than the last index which will be removed 448: * @throws IndexOutOfBoundsException if fromIndex > toIndex 449: */ 450: protected void removeRange(int fromIndex, int toIndex) 451: { 452: int change = toIndex - fromIndex; 453: if (change > 0) 454: { 455: modCount++; 456: System.arraycopy(data, toIndex, data, fromIndex, size - toIndex); 457: size -= change; 458: } 459: else if (change < 0) 460: throw new IndexOutOfBoundsException(); 461: } 462: 463: /** 464: * Checks that the index is in the range of possible elements (inclusive). 465: * 466: * @param index the index to check 467: * @throws IndexOutOfBoundsException if index > size 468: */ 469: private void checkBoundInclusive(int index) 470: { 471: // Implementation note: we do not check for negative ranges here, since 472: // use of a negative index will cause an ArrayIndexOutOfBoundsException, 473: // a subclass of the required exception, with no effort on our part. 474: if (index > size) 475: throw new IndexOutOfBoundsException("Index: " + index + ", Size: " 476: + size); 477: } 478: 479: /** 480: * Checks that the index is in the range of existing elements (exclusive). 481: * 482: * @param index the index to check 483: * @throws IndexOutOfBoundsException if index >= size 484: */ 485: private void checkBoundExclusive(int index) 486: { 487: // Implementation note: we do not check for negative ranges here, since 488: // use of a negative index will cause an ArrayIndexOutOfBoundsException, 489: // a subclass of the required exception, with no effort on our part. 490: if (index >= size) 491: throw new IndexOutOfBoundsException("Index: " + index + ", Size: " 492: + size); 493: } 494: 495: /** 496: * Remove from this list all elements contained in the given collection. 497: * This is not public, due to Sun's API, but this performs in linear 498: * time while the default behavior of AbstractList would be quadratic. 499: * 500: * @param c the collection to filter out 501: * @return true if this list changed 502: * @throws NullPointerException if c is null 503: */ 504: boolean removeAllInternal(Collection<?> c) 505: { 506: int i; 507: int j; 508: for (i = 0; i < size; i++) 509: if (c.contains(data[i])) 510: break; 511: if (i == size) 512: return false; 513: 514: modCount++; 515: for (j = i++; i < size; i++) 516: if (! c.contains(data[i])) 517: data[j++] = data[i]; 518: size -= i - j; 519: return true; 520: } 521: 522: /** 523: * Retain in this vector only the elements contained in the given collection. 524: * This is not public, due to Sun's API, but this performs in linear 525: * time while the default behavior of AbstractList would be quadratic. 526: * 527: * @param c the collection to filter by 528: * @return true if this vector changed 529: * @throws NullPointerException if c is null 530: * @since 1.2 531: */ 532: boolean retainAllInternal(Collection<?> c) 533: { 534: int i; 535: int j; 536: for (i = 0; i < size; i++) 537: if (! c.contains(data[i])) 538: break; 539: if (i == size) 540: return false; 541: 542: modCount++; 543: for (j = i++; i < size; i++) 544: if (c.contains(data[i])) 545: data[j++] = data[i]; 546: size -= i - j; 547: return true; 548: } 549: 550: /** 551: * Serializes this object to the given stream. 552: * 553: * @param s the stream to write to 554: * @throws IOException if the underlying stream fails 555: * @serialData the size field (int), the length of the backing array 556: * (int), followed by its elements (Objects) in proper order. 557: */ 558: private void writeObject(ObjectOutputStream s) throws IOException 559: { 560: // The 'size' field. 561: s.defaultWriteObject(); 562: // We serialize unused list entries to preserve capacity. 563: int len = data.length; 564: s.writeInt(len); 565: // it would be more efficient to just write "size" items, 566: // this need readObject read "size" items too. 567: for (int i = 0; i < size; i++) 568: s.writeObject(data[i]); 569: } 570: 571: /** 572: * Deserializes this object from the given stream. 573: * 574: * @param s the stream to read from 575: * @throws ClassNotFoundException if the underlying stream fails 576: * @throws IOException if the underlying stream fails 577: * @serialData the size field (int), the length of the backing array 578: * (int), followed by its elements (Objects) in proper order. 579: */ 580: private void readObject(ObjectInputStream s) 581: throws IOException, ClassNotFoundException 582: { 583: // the `size' field. 584: s.defaultReadObject(); 585: int capacity = s.readInt(); 586: data = (E[]) new Object[capacity]; 587: for (int i = 0; i < size; i++) 588: data[i] = (E) s.readObject(); 589: } 590: }