001 /* ArrayList.java -- JDK1.2's answer to Vector; this is an array-backed 002 implementation of the List interface 003 Copyright (C) 1998, 1999, 2000, 2001, 2004, 2005 Free Software Foundation, Inc. 004 005 This file is part of GNU Classpath. 006 007 GNU Classpath is free software; you can redistribute it and/or modify 008 it under the terms of the GNU General Public License as published by 009 the Free Software Foundation; either version 2, or (at your option) 010 any later version. 011 012 GNU Classpath is distributed in the hope that it will be useful, but 013 WITHOUT ANY WARRANTY; without even the implied warranty of 014 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 015 General Public License for more details. 016 017 You should have received a copy of the GNU General Public License 018 along with GNU Classpath; see the file COPYING. If not, write to the 019 Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 020 02110-1301 USA. 021 022 Linking this library statically or dynamically with other modules is 023 making a combined work based on this library. Thus, the terms and 024 conditions of the GNU General Public License cover the whole 025 combination. 026 027 As a special exception, the copyright holders of this library give you 028 permission to link this library with independent modules to produce an 029 executable, regardless of the license terms of these independent 030 modules, and to copy and distribute the resulting executable under 031 terms of your choice, provided that you also meet, for each linked 032 independent module, the terms and conditions of the license of that 033 module. An independent module is a module which is not derived from 034 or based on this library. If you modify this library, you may extend 035 this exception to your version of the library, but you are not 036 obligated to do so. If you do not wish to do so, delete this 037 exception statement from your version. */ 038 039 040 package java.util; 041 042 import java.io.IOException; 043 import java.io.ObjectInputStream; 044 import java.io.ObjectOutputStream; 045 import java.io.Serializable; 046 import java.lang.reflect.Array; 047 048 /** 049 * An array-backed implementation of the List interface. This implements 050 * all optional list operations, and permits null elements, so that it is 051 * better than Vector, which it replaces. Random access is roughly constant 052 * time, and iteration is roughly linear time, so it is nice and fast, with 053 * less overhead than a LinkedList. 054 * <p> 055 * 056 * Each list has a capacity, and as the array reaches that capacity it 057 * is automatically transferred to a larger array. You also have access to 058 * ensureCapacity and trimToSize to control the backing array's size, avoiding 059 * reallocation or wasted memory. 060 * <p> 061 * 062 * ArrayList is not synchronized, so if you need multi-threaded access, 063 * consider using:<br> 064 * <code>List l = Collections.synchronizedList(new ArrayList(...));</code> 065 * <p> 066 * 067 * The iterators are <i>fail-fast</i>, meaning that any structural 068 * modification, except for <code>remove()</code> called on the iterator 069 * itself, cause the iterator to throw a 070 * {@link ConcurrentModificationException} rather than exhibit 071 * non-deterministic behavior. 072 * 073 * @author Jon A. Zeppieri 074 * @author Bryce McKinlay 075 * @author Eric Blake (ebb9@email.byu.edu) 076 * @see Collection 077 * @see List 078 * @see LinkedList 079 * @see Vector 080 * @see Collections#synchronizedList(List) 081 * @see AbstractList 082 * @status updated to 1.4 083 */ 084 public class ArrayList<E> extends AbstractList<E> 085 implements List<E>, RandomAccess, Cloneable, Serializable 086 { 087 /** 088 * Compatible with JDK 1.2 089 */ 090 private static final long serialVersionUID = 8683452581122892189L; 091 092 /** 093 * The default capacity for new ArrayLists. 094 */ 095 private static final int DEFAULT_CAPACITY = 10; 096 097 /** 098 * The number of elements in this list. 099 * @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 }