Source for java.util.ArrayList

   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 &gt; 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 &lt; 0 || index &gt;= 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 &lt; 0 || index &gt;= 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 &lt; 0 || index &gt; 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 &lt; 0 || index &gt;= 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 &lt; 0 || index &gt; 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 &gt; 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 &gt; 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:       raiseBoundsError(index);
 476:   }
 477: 
 478:   /**
 479:    * Checks that the index is in the range of existing elements (exclusive).
 480:    *
 481:    * @param index the index to check
 482:    * @throws IndexOutOfBoundsException if index &gt;= size
 483:    */
 484:   private void checkBoundExclusive(int index)
 485:   {
 486:     // Implementation note: we do not check for negative ranges here, since
 487:     // use of a negative index will cause an ArrayIndexOutOfBoundsException,
 488:     // a subclass of the required exception, with no effort on our part.
 489:     if (index >= size)
 490:       raiseBoundsError(index);
 491:   }
 492: 
 493:   /**
 494:    * Raise the ArrayIndexOfOutBoundsException.
 495:    *
 496:    * @param index the index of the access
 497:    * @throws IndexOutOfBoundsException unconditionally
 498:    */
 499:   private void raiseBoundsError(int index)
 500:   {
 501:     // Implementaion note: put in a separate method to make the JITs job easier
 502:     // (separate common from uncommon code at method boundaries when trivial to
 503:     // do so).
 504:     throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
 505:   }
 506: 
 507: 
 508:   /**
 509:    * Remove from this list all elements contained in the given collection.
 510:    * This is not public, due to Sun's API, but this performs in linear
 511:    * time while the default behavior of AbstractList would be quadratic.
 512:    *
 513:    * @param c the collection to filter out
 514:    * @return true if this list changed
 515:    * @throws NullPointerException if c is null
 516:    */
 517:   boolean removeAllInternal(Collection<?> c)
 518:   {
 519:     int i;
 520:     int j;
 521:     for (i = 0; i < size; i++)
 522:       if (c.contains(data[i]))
 523:         break;
 524:     if (i == size)
 525:       return false;
 526: 
 527:     modCount++;
 528:     for (j = i++; i < size; i++)
 529:       if (! c.contains(data[i]))
 530:         data[j++] = data[i];
 531:     size -= i - j;
 532:     return true;
 533:   }
 534: 
 535:   /**
 536:    * Retain in this vector only the elements contained in the given collection.
 537:    * This is not public, due to Sun's API, but this performs in linear
 538:    * time while the default behavior of AbstractList would be quadratic.
 539:    *
 540:    * @param c the collection to filter by
 541:    * @return true if this vector changed
 542:    * @throws NullPointerException if c is null
 543:    * @since 1.2
 544:    */
 545:   boolean retainAllInternal(Collection<?> c)
 546:   {
 547:     int i;
 548:     int j;
 549:     for (i = 0; i < size; i++)
 550:       if (! c.contains(data[i]))
 551:         break;
 552:     if (i == size)
 553:       return false;
 554: 
 555:     modCount++;
 556:     for (j = i++; i < size; i++)
 557:       if (c.contains(data[i]))
 558:         data[j++] = data[i];
 559:     size -= i - j;
 560:     return true;
 561:   }
 562: 
 563:   /**
 564:    * Serializes this object to the given stream.
 565:    *
 566:    * @param s the stream to write to
 567:    * @throws IOException if the underlying stream fails
 568:    * @serialData the size field (int), the length of the backing array
 569:    *             (int), followed by its elements (Objects) in proper order.
 570:    */
 571:   private void writeObject(ObjectOutputStream s) throws IOException
 572:   {
 573:     // The 'size' field.
 574:     s.defaultWriteObject();
 575:     // We serialize unused list entries to preserve capacity.
 576:     int len = data.length;
 577:     s.writeInt(len);
 578:     // it would be more efficient to just write "size" items,
 579:     // this need readObject read "size" items too.
 580:     for (int i = 0; i < size; i++)
 581:       s.writeObject(data[i]);
 582:   }
 583: 
 584:   /**
 585:    * Deserializes this object from the given stream.
 586:    *
 587:    * @param s the stream to read from
 588:    * @throws ClassNotFoundException if the underlying stream fails
 589:    * @throws IOException if the underlying stream fails
 590:    * @serialData the size field (int), the length of the backing array
 591:    *             (int), followed by its elements (Objects) in proper order.
 592:    */
 593:   private void readObject(ObjectInputStream s)
 594:     throws IOException, ClassNotFoundException
 595:   {
 596:     // the `size' field.
 597:     s.defaultReadObject();
 598:     int capacity = s.readInt();
 599:     data = (E[]) new Object[capacity];
 600:     for (int i = 0; i < size; i++)
 601:       data[i] = (E) s.readObject();
 602:   }
 603: }