GNU Classpath (0.20) | |
Frames | No Frames |
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 extends AbstractList 85: implements List, 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 Object[] 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 = 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 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: Object[] newData = 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: Object[] newData = 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 clone = null; 251: try 252: { 253: clone = (ArrayList) super.clone(); 254: clone.data = (Object[]) 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: Object[] array = 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 Object[] toArray(Object[] a) 291: { 292: if (a.length < size) 293: a = (Object[]) Array.newInstance(a.getClass().getComponentType(), 294: size); 295: else if (a.length > size) 296: a[size] = null; 297: System.arraycopy(data, 0, a, 0, size); 298: return a; 299: } 300: 301: /** 302: * Retrieves the element at the user-supplied index. 303: * 304: * @param index the index of the element we are fetching 305: * @throws IndexOutOfBoundsException if index < 0 || index >= size() 306: */ 307: public Object get(int index) 308: { 309: checkBoundExclusive(index); 310: return data[index]; 311: } 312: 313: /** 314: * Sets the element at the specified index. The new element, e, 315: * can be an object of any type or null. 316: * 317: * @param index the index at which the element is being set 318: * @param e the element to be set 319: * @return the element previously at the specified index 320: * @throws IndexOutOfBoundsException if index < 0 || index >= 0 321: */ 322: public Object set(int index, Object e) 323: { 324: checkBoundExclusive(index); 325: Object result = data[index]; 326: data[index] = e; 327: return result; 328: } 329: 330: /** 331: * Appends the supplied element to the end of this list. 332: * The element, e, can be an object of any type or null. 333: * 334: * @param e the element to be appended to this list 335: * @return true, the add will always succeed 336: */ 337: public boolean add(Object e) 338: { 339: modCount++; 340: if (size == data.length) 341: ensureCapacity(size + 1); 342: data[size++] = e; 343: return true; 344: } 345: 346: /** 347: * Adds the supplied element at the specified index, shifting all 348: * elements currently at that index or higher one to the right. 349: * The element, e, can be an object of any type or null. 350: * 351: * @param index the index at which the element is being added 352: * @param e the item being added 353: * @throws IndexOutOfBoundsException if index < 0 || index > size() 354: */ 355: public void add(int index, Object e) 356: { 357: checkBoundInclusive(index); 358: modCount++; 359: if (size == data.length) 360: ensureCapacity(size + 1); 361: if (index != size) 362: System.arraycopy(data, index, data, index + 1, size - index); 363: data[index] = e; 364: size++; 365: } 366: 367: /** 368: * Removes the element at the user-supplied index. 369: * 370: * @param index the index of the element to be removed 371: * @return the removed Object 372: * @throws IndexOutOfBoundsException if index < 0 || index >= size() 373: */ 374: public Object remove(int index) 375: { 376: checkBoundExclusive(index); 377: Object r = data[index]; 378: modCount++; 379: if (index != --size) 380: System.arraycopy(data, index + 1, data, index, size - index); 381: // Aid for garbage collection by releasing this pointer. 382: data[size] = null; 383: return r; 384: } 385: 386: /** 387: * Removes all elements from this List 388: */ 389: public void clear() 390: { 391: if (size > 0) 392: { 393: modCount++; 394: // Allow for garbage collection. 395: Arrays.fill(data, 0, size, null); 396: size = 0; 397: } 398: } 399: 400: /** 401: * Add each element in the supplied Collection to this List. It is undefined 402: * what happens if you modify the list while this is taking place; for 403: * example, if the collection contains this list. c can contain objects 404: * of any type, as well as null values. 405: * 406: * @param c a Collection containing elements to be added to this List 407: * @return true if the list was modified, in other words c is not empty 408: * @throws NullPointerException if c is null 409: */ 410: public boolean addAll(Collection c) 411: { 412: return addAll(size, c); 413: } 414: 415: /** 416: * Add all elements in the supplied collection, inserting them beginning 417: * at the specified index. c can contain objects of any type, as well 418: * as null values. 419: * 420: * @param index the index at which the elements will be inserted 421: * @param c the Collection containing the elements to be inserted 422: * @throws IndexOutOfBoundsException if index < 0 || index > 0 423: * @throws NullPointerException if c is null 424: */ 425: public boolean addAll(int index, Collection c) 426: { 427: checkBoundInclusive(index); 428: Iterator itr = c.iterator(); 429: int csize = c.size(); 430: 431: modCount++; 432: if (csize + size > data.length) 433: ensureCapacity(size + csize); 434: int end = index + csize; 435: if (size > 0 && index != size) 436: System.arraycopy(data, index, data, end, size - index); 437: size += csize; 438: for ( ; index < end; index++) 439: data[index] = itr.next(); 440: return csize > 0; 441: } 442: 443: /** 444: * Removes all elements in the half-open interval [fromIndex, toIndex). 445: * Does nothing when toIndex is equal to fromIndex. 446: * 447: * @param fromIndex the first index which will be removed 448: * @param toIndex one greater than the last index which will be removed 449: * @throws IndexOutOfBoundsException if fromIndex > toIndex 450: */ 451: protected void removeRange(int fromIndex, int toIndex) 452: { 453: int change = toIndex - fromIndex; 454: if (change > 0) 455: { 456: modCount++; 457: System.arraycopy(data, toIndex, data, fromIndex, size - toIndex); 458: size -= change; 459: } 460: else if (change < 0) 461: throw new IndexOutOfBoundsException(); 462: } 463: 464: /** 465: * Checks that the index is in the range of possible elements (inclusive). 466: * 467: * @param index the index to check 468: * @throws IndexOutOfBoundsException if index > size 469: */ 470: private void checkBoundInclusive(int index) 471: { 472: // Implementation note: we do not check for negative ranges here, since 473: // use of a negative index will cause an ArrayIndexOutOfBoundsException, 474: // a subclass of the required exception, with no effort on our part. 475: if (index > size) 476: throw new IndexOutOfBoundsException("Index: " + index + ", Size: " 477: + size); 478: } 479: 480: /** 481: * Checks that the index is in the range of existing elements (exclusive). 482: * 483: * @param index the index to check 484: * @throws IndexOutOfBoundsException if index >= size 485: */ 486: private void checkBoundExclusive(int index) 487: { 488: // Implementation note: we do not check for negative ranges here, since 489: // use of a negative index will cause an ArrayIndexOutOfBoundsException, 490: // a subclass of the required exception, with no effort on our part. 491: if (index >= size) 492: throw new IndexOutOfBoundsException("Index: " + index + ", Size: " 493: + size); 494: } 495: 496: /** 497: * Remove from this list all elements contained in the given collection. 498: * This is not public, due to Sun's API, but this performs in linear 499: * time while the default behavior of AbstractList would be quadratic. 500: * 501: * @param c the collection to filter out 502: * @return true if this list changed 503: * @throws NullPointerException if c is null 504: */ 505: boolean removeAllInternal(Collection c) 506: { 507: int i; 508: int j; 509: for (i = 0; i < size; i++) 510: if (c.contains(data[i])) 511: break; 512: if (i == size) 513: return false; 514: 515: modCount++; 516: for (j = i++; i < size; i++) 517: if (! c.contains(data[i])) 518: data[j++] = data[i]; 519: size -= i - j; 520: return true; 521: } 522: 523: /** 524: * Retain in this vector only the elements contained in the given collection. 525: * This is not public, due to Sun's API, but this performs in linear 526: * time while the default behavior of AbstractList would be quadratic. 527: * 528: * @param c the collection to filter by 529: * @return true if this vector changed 530: * @throws NullPointerException if c is null 531: * @since 1.2 532: */ 533: boolean retainAllInternal(Collection c) 534: { 535: int i; 536: int j; 537: for (i = 0; i < size; i++) 538: if (! c.contains(data[i])) 539: break; 540: if (i == size) 541: return false; 542: 543: modCount++; 544: for (j = i++; i < size; i++) 545: if (c.contains(data[i])) 546: data[j++] = data[i]; 547: size -= i - j; 548: return true; 549: } 550: 551: /** 552: * Serializes this object to the given stream. 553: * 554: * @param s the stream to write to 555: * @throws IOException if the underlying stream fails 556: * @serialData the size field (int), the length of the backing array 557: * (int), followed by its elements (Objects) in proper order. 558: */ 559: private void writeObject(ObjectOutputStream s) throws IOException 560: { 561: // The 'size' field. 562: s.defaultWriteObject(); 563: // We serialize unused list entries to preserve capacity. 564: int len = data.length; 565: s.writeInt(len); 566: // it would be more efficient to just write "size" items, 567: // this need readObject read "size" items too. 568: for (int i = 0; i < size; i++) 569: s.writeObject(data[i]); 570: } 571: 572: /** 573: * Deserializes this object from the given stream. 574: * 575: * @param s the stream to read from 576: * @throws ClassNotFoundException if the underlying stream fails 577: * @throws IOException if the underlying stream fails 578: * @serialData the size field (int), the length of the backing array 579: * (int), followed by its elements (Objects) in proper order. 580: */ 581: private void readObject(ObjectInputStream s) 582: throws IOException, ClassNotFoundException 583: { 584: // the `size' field. 585: s.defaultReadObject(); 586: int capacity = s.readInt(); 587: data = new Object[capacity]; 588: for (int i = 0; i < size; i++) 589: data[i] = s.readObject(); 590: } 591: }
GNU Classpath (0.20) |