1. /*
  2. * @(#)ArrayList.java 1.47 03/12/19
  3. *
  4. * Copyright 2004 Sun Microsystems, Inc. All rights reserved.
  5. * SUN PROPRIETARY/CONFIDENTIAL. Use is subject to license terms.
  6. */
  7. package java.util;
  8. /**
  9. * Resizable-array implementation of the <tt>List</tt> interface. Implements
  10. * all optional list operations, and permits all elements, including
  11. * <tt>null</tt>. In addition to implementing the <tt>List</tt> interface,
  12. * this class provides methods to manipulate the size of the array that is
  13. * used internally to store the list. (This class is roughly equivalent to
  14. * <tt>Vector</tt>, except that it is unsynchronized.)<p>
  15. *
  16. * The <tt>size</tt>, <tt>isEmpty</tt>, <tt>get</tt>, <tt>set</tt>,
  17. * <tt>iterator</tt>, and <tt>listIterator</tt> operations run in constant
  18. * time. The <tt>add</tt> operation runs in <i>amortized constant time</i>,
  19. * that is, adding n elements requires O(n) time. All of the other operations
  20. * run in linear time (roughly speaking). The constant factor is low compared
  21. * to that for the <tt>LinkedList</tt> implementation.<p>
  22. *
  23. * Each <tt>ArrayList</tt> instance has a <i>capacity</i>. The capacity is
  24. * the size of the array used to store the elements in the list. It is always
  25. * at least as large as the list size. As elements are added to an ArrayList,
  26. * its capacity grows automatically. The details of the growth policy are not
  27. * specified beyond the fact that adding an element has constant amortized
  28. * time cost.<p>
  29. *
  30. * An application can increase the capacity of an <tt>ArrayList</tt> instance
  31. * before adding a large number of elements using the <tt>ensureCapacity</tt>
  32. * operation. This may reduce the amount of incremental reallocation.<p>
  33. *
  34. * <strong>Note that this implementation is not synchronized.</strong> If
  35. * multiple threads access an <tt>ArrayList</tt> instance concurrently, and at
  36. * least one of the threads modifies the list structurally, it <i>must</i> be
  37. * synchronized externally. (A structural modification is any operation that
  38. * adds or deletes one or more elements, or explicitly resizes the backing
  39. * array; merely setting the value of an element is not a structural
  40. * modification.) This is typically accomplished by synchronizing on some
  41. * object that naturally encapsulates the list. If no such object exists, the
  42. * list should be "wrapped" using the <tt>Collections.synchronizedList</tt>
  43. * method. This is best done at creation time, to prevent accidental
  44. * unsynchronized access to the list:
  45. * <pre>
  46. * List list = Collections.synchronizedList(new ArrayList(...));
  47. * </pre><p>
  48. *
  49. * The iterators returned by this class's <tt>iterator</tt> and
  50. * <tt>listIterator</tt> methods are <i>fail-fast</i>: if list is structurally
  51. * modified at any time after the iterator is created, in any way except
  52. * through the iterator's own remove or add methods, the iterator will throw a
  53. * ConcurrentModificationException. Thus, in the face of concurrent
  54. * modification, the iterator fails quickly and cleanly, rather than risking
  55. * arbitrary, non-deterministic behavior at an undetermined time in the
  56. * future.<p>
  57. *
  58. * Note that the fail-fast behavior of an iterator cannot be guaranteed
  59. * as it is, generally speaking, impossible to make any hard guarantees in the
  60. * presence of unsynchronized concurrent modification. Fail-fast iterators
  61. * throw <tt>ConcurrentModificationException</tt> on a best-effort basis.
  62. * Therefore, it would be wrong to write a program that depended on this
  63. * exception for its correctness: <i>the fail-fast behavior of iterators
  64. * should be used only to detect bugs.</i><p>
  65. *
  66. * This class is a member of the
  67. * <a href="{@docRoot}/../guide/collections/index.html">
  68. * Java Collections Framework</a>.
  69. *
  70. * @author Josh Bloch
  71. * @author Neal Gafter
  72. * @version 1.47, 12/19/03
  73. * @see Collection
  74. * @see List
  75. * @see LinkedList
  76. * @see Vector
  77. * @see Collections#synchronizedList(List)
  78. * @since 1.2
  79. */
  80. public class ArrayList<E> extends AbstractList<E>
  81. implements List<E>, RandomAccess, Cloneable, java.io.Serializable
  82. {
  83. private static final long serialVersionUID = 8683452581122892189L;
  84. /**
  85. * The array buffer into which the elements of the ArrayList are stored.
  86. * The capacity of the ArrayList is the length of this array buffer.
  87. */
  88. private transient E[] elementData;
  89. /**
  90. * The size of the ArrayList (the number of elements it contains).
  91. *
  92. * @serial
  93. */
  94. private int size;
  95. /**
  96. * Constructs an empty list with the specified initial capacity.
  97. *
  98. * @param initialCapacity the initial capacity of the list.
  99. * @exception IllegalArgumentException if the specified initial capacity
  100. * is negative
  101. */
  102. public ArrayList(int initialCapacity) {
  103. super();
  104. if (initialCapacity < 0)
  105. throw new IllegalArgumentException("Illegal Capacity: "+
  106. initialCapacity);
  107. this.elementData = (E[])new Object[initialCapacity];
  108. }
  109. /**
  110. * Constructs an empty list with an initial capacity of ten.
  111. */
  112. public ArrayList() {
  113. this(10);
  114. }
  115. /**
  116. * Constructs a list containing the elements of the specified
  117. * collection, in the order they are returned by the collection's
  118. * iterator. The <tt>ArrayList</tt> instance has an initial capacity of
  119. * 110% the size of the specified collection.
  120. *
  121. * @param c the collection whose elements are to be placed into this list.
  122. * @throws NullPointerException if the specified collection is null.
  123. */
  124. public ArrayList(Collection<? extends E> c) {
  125. size = c.size();
  126. // Allow 10% room for growth
  127. elementData = (E[])new Object[
  128. (int)Math.min((size*110L)/100,Integer.MAX_VALUE)];
  129. c.toArray(elementData);
  130. }
  131. /**
  132. * Trims the capacity of this <tt>ArrayList</tt> instance to be the
  133. * list's current size. An application can use this operation to minimize
  134. * the storage of an <tt>ArrayList</tt> instance.
  135. */
  136. public void trimToSize() {
  137. modCount++;
  138. int oldCapacity = elementData.length;
  139. if (size < oldCapacity) {
  140. Object oldData[] = elementData;
  141. elementData = (E[])new Object[size];
  142. System.arraycopy(oldData, 0, elementData, 0, size);
  143. }
  144. }
  145. /**
  146. * Increases the capacity of this <tt>ArrayList</tt> instance, if
  147. * necessary, to ensure that it can hold at least the number of elements
  148. * specified by the minimum capacity argument.
  149. *
  150. * @param minCapacity the desired minimum capacity.
  151. */
  152. public void ensureCapacity(int minCapacity) {
  153. modCount++;
  154. int oldCapacity = elementData.length;
  155. if (minCapacity > oldCapacity) {
  156. Object oldData[] = elementData;
  157. int newCapacity = (oldCapacity * 3)/2 + 1;
  158. if (newCapacity < minCapacity)
  159. newCapacity = minCapacity;
  160. elementData = (E[])new Object[newCapacity];
  161. System.arraycopy(oldData, 0, elementData, 0, size);
  162. }
  163. }
  164. /**
  165. * Returns the number of elements in this list.
  166. *
  167. * @return the number of elements in this list.
  168. */
  169. public int size() {
  170. return size;
  171. }
  172. /**
  173. * Tests if this list has no elements.
  174. *
  175. * @return <tt>true</tt> if this list has no elements;
  176. * <tt>false</tt> otherwise.
  177. */
  178. public boolean isEmpty() {
  179. return size == 0;
  180. }
  181. /**
  182. * Returns <tt>true</tt> if this list contains the specified element.
  183. *
  184. * @param elem element whose presence in this List is to be tested.
  185. * @return <code>true</code> if the specified element is present;
  186. * <code>false</code> otherwise.
  187. */
  188. public boolean contains(Object elem) {
  189. return indexOf(elem) >= 0;
  190. }
  191. /**
  192. * Searches for the first occurence of the given argument, testing
  193. * for equality using the <tt>equals</tt> method.
  194. *
  195. * @param elem an object.
  196. * @return the index of the first occurrence of the argument in this
  197. * list; returns <tt>-1</tt> if the object is not found.
  198. * @see Object#equals(Object)
  199. */
  200. public int indexOf(Object elem) {
  201. if (elem == null) {
  202. for (int i = 0; i < size; i++)
  203. if (elementData[i]==null)
  204. return i;
  205. } else {
  206. for (int i = 0; i < size; i++)
  207. if (elem.equals(elementData[i]))
  208. return i;
  209. }
  210. return -1;
  211. }
  212. /**
  213. * Returns the index of the last occurrence of the specified object in
  214. * this list.
  215. *
  216. * @param elem the desired element.
  217. * @return the index of the last occurrence of the specified object in
  218. * this list; returns -1 if the object is not found.
  219. */
  220. public int lastIndexOf(Object elem) {
  221. if (elem == null) {
  222. for (int i = size-1; i >= 0; i--)
  223. if (elementData[i]==null)
  224. return i;
  225. } else {
  226. for (int i = size-1; i >= 0; i--)
  227. if (elem.equals(elementData[i]))
  228. return i;
  229. }
  230. return -1;
  231. }
  232. /**
  233. * Returns a shallow copy of this <tt>ArrayList</tt> instance. (The
  234. * elements themselves are not copied.)
  235. *
  236. * @return a clone of this <tt>ArrayList</tt> instance.
  237. */
  238. public Object clone() {
  239. try {
  240. ArrayList<E> v = (ArrayList<E>) super.clone();
  241. v.elementData = (E[])new Object[size];
  242. System.arraycopy(elementData, 0, v.elementData, 0, size);
  243. v.modCount = 0;
  244. return v;
  245. } catch (CloneNotSupportedException e) {
  246. // this shouldn't happen, since we are Cloneable
  247. throw new InternalError();
  248. }
  249. }
  250. /**
  251. * Returns an array containing all of the elements in this list
  252. * in the correct order.
  253. *
  254. * @return an array containing all of the elements in this list
  255. * in the correct order.
  256. */
  257. public Object[] toArray() {
  258. Object[] result = new Object[size];
  259. System.arraycopy(elementData, 0, result, 0, size);
  260. return result;
  261. }
  262. /**
  263. * Returns an array containing all of the elements in this list in the
  264. * correct order; the runtime type of the returned array is that of the
  265. * specified array. If the list fits in the specified array, it is
  266. * returned therein. Otherwise, a new array is allocated with the runtime
  267. * type of the specified array and the size of this list.<p>
  268. *
  269. * If the list fits in the specified array with room to spare (i.e., the
  270. * array has more elements than the list), the element in the array
  271. * immediately following the end of the collection is set to
  272. * <tt>null</tt>. This is useful in determining the length of the list
  273. * <i>only</i> if the caller knows that the list does not contain any
  274. * <tt>null</tt> elements.
  275. *
  276. * @param a the array into which the elements of the list are to
  277. * be stored, if it is big enough; otherwise, a new array of the
  278. * same runtime type is allocated for this purpose.
  279. * @return an array containing the elements of the list.
  280. * @throws ArrayStoreException if the runtime type of a is not a supertype
  281. * of the runtime type of every element in this list.
  282. */
  283. public <T> T[] toArray(T[] a) {
  284. if (a.length < size)
  285. a = (T[])java.lang.reflect.Array.
  286. newInstance(a.getClass().getComponentType(), size);
  287. System.arraycopy(elementData, 0, a, 0, size);
  288. if (a.length > size)
  289. a[size] = null;
  290. return a;
  291. }
  292. // Positional Access Operations
  293. /**
  294. * Returns the element at the specified position in this list.
  295. *
  296. * @param index index of element to return.
  297. * @return the element at the specified position in this list.
  298. * @throws IndexOutOfBoundsException if index is out of range <tt>(index
  299. * < 0 || index >= size())</tt>.
  300. */
  301. public E get(int index) {
  302. RangeCheck(index);
  303. return elementData[index];
  304. }
  305. /**
  306. * Replaces the element at the specified position in this list with
  307. * the specified element.
  308. *
  309. * @param index index of element to replace.
  310. * @param element element to be stored at the specified position.
  311. * @return the element previously at the specified position.
  312. * @throws IndexOutOfBoundsException if index out of range
  313. * <tt>(index < 0 || index >= size())</tt>.
  314. */
  315. public E set(int index, E element) {
  316. RangeCheck(index);
  317. E oldValue = elementData[index];
  318. elementData[index] = element;
  319. return oldValue;
  320. }
  321. /**
  322. * Appends the specified element to the end of this list.
  323. *
  324. * @param o element to be appended to this list.
  325. * @return <tt>true</tt> (as per the general contract of Collection.add).
  326. */
  327. public boolean add(E o) {
  328. ensureCapacity(size + 1); // Increments modCount!!
  329. elementData[size++] = o;
  330. return true;
  331. }
  332. /**
  333. * Inserts the specified element at the specified position in this
  334. * list. Shifts the element currently at that position (if any) and
  335. * any subsequent elements to the right (adds one to their indices).
  336. *
  337. * @param index index at which the specified element is to be inserted.
  338. * @param element element to be inserted.
  339. * @throws IndexOutOfBoundsException if index is out of range
  340. * <tt>(index < 0 || index > size())</tt>.
  341. */
  342. public void add(int index, E element) {
  343. if (index > size || index < 0)
  344. throw new IndexOutOfBoundsException(
  345. "Index: "+index+", Size: "+size);
  346. ensureCapacity(size+1); // Increments modCount!!
  347. System.arraycopy(elementData, index, elementData, index + 1,
  348. size - index);
  349. elementData[index] = element;
  350. size++;
  351. }
  352. /**
  353. * Removes the element at the specified position in this list.
  354. * Shifts any subsequent elements to the left (subtracts one from their
  355. * indices).
  356. *
  357. * @param index the index of the element to removed.
  358. * @return the element that was removed from the list.
  359. * @throws IndexOutOfBoundsException if index out of range <tt>(index
  360. * < 0 || index >= size())</tt>.
  361. */
  362. public E remove(int index) {
  363. RangeCheck(index);
  364. modCount++;
  365. E oldValue = elementData[index];
  366. int numMoved = size - index - 1;
  367. if (numMoved > 0)
  368. System.arraycopy(elementData, index+1, elementData, index,
  369. numMoved);
  370. elementData[--size] = null; // Let gc do its work
  371. return oldValue;
  372. }
  373. /**
  374. * Removes a single instance of the specified element from this
  375. * list, if it is present (optional operation). More formally,
  376. * removes an element <tt>e</tt> such that <tt>(o==null ? e==null :
  377. * o.equals(e))</tt>, if the list contains one or more such
  378. * elements. Returns <tt>true</tt> if the list contained the
  379. * specified element (or equivalently, if the list changed as a
  380. * result of the call).<p>
  381. *
  382. * @param o element to be removed from this list, if present.
  383. * @return <tt>true</tt> if the list contained the specified element.
  384. */
  385. public boolean remove(Object o) {
  386. if (o == null) {
  387. for (int index = 0; index < size; index++)
  388. if (elementData[index] == null) {
  389. fastRemove(index);
  390. return true;
  391. }
  392. } else {
  393. for (int index = 0; index < size; index++)
  394. if (o.equals(elementData[index])) {
  395. fastRemove(index);
  396. return true;
  397. }
  398. }
  399. return false;
  400. }
  401. /*
  402. * Private remove method that skips bounds checking and does not
  403. * return the value removed.
  404. */
  405. private void fastRemove(int index) {
  406. modCount++;
  407. int numMoved = size - index - 1;
  408. if (numMoved > 0)
  409. System.arraycopy(elementData, index+1, elementData, index,
  410. numMoved);
  411. elementData[--size] = null; // Let gc do its work
  412. }
  413. /**
  414. * Removes all of the elements from this list. The list will
  415. * be empty after this call returns.
  416. */
  417. public void clear() {
  418. modCount++;
  419. // Let gc do its work
  420. for (int i = 0; i < size; i++)
  421. elementData[i] = null;
  422. size = 0;
  423. }
  424. /**
  425. * Appends all of the elements in the specified Collection to the end of
  426. * this list, in the order that they are returned by the
  427. * specified Collection's Iterator. The behavior of this operation is
  428. * undefined if the specified Collection is modified while the operation
  429. * is in progress. (This implies that the behavior of this call is
  430. * undefined if the specified Collection is this list, and this
  431. * list is nonempty.)
  432. *
  433. * @param c the elements to be inserted into this list.
  434. * @return <tt>true</tt> if this list changed as a result of the call.
  435. * @throws NullPointerException if the specified collection is null.
  436. */
  437. public boolean addAll(Collection<? extends E> c) {
  438. Object[] a = c.toArray();
  439. int numNew = a.length;
  440. ensureCapacity(size + numNew); // Increments modCount
  441. System.arraycopy(a, 0, elementData, size, numNew);
  442. size += numNew;
  443. return numNew != 0;
  444. }
  445. /**
  446. * Inserts all of the elements in the specified Collection into this
  447. * list, starting at the specified position. Shifts the element
  448. * currently at that position (if any) and any subsequent elements to
  449. * the right (increases their indices). The new elements will appear
  450. * in the list in the order that they are returned by the
  451. * specified Collection's iterator.
  452. *
  453. * @param index index at which to insert first element
  454. * from the specified collection.
  455. * @param c elements to be inserted into this list.
  456. * @return <tt>true</tt> if this list changed as a result of the call.
  457. * @throws IndexOutOfBoundsException if index out of range <tt>(index
  458. * < 0 || index > size())</tt>.
  459. * @throws NullPointerException if the specified Collection is null.
  460. */
  461. public boolean addAll(int index, Collection<? extends E> c) {
  462. if (index > size || index < 0)
  463. throw new IndexOutOfBoundsException(
  464. "Index: " + index + ", Size: " + size);
  465. Object[] a = c.toArray();
  466. int numNew = a.length;
  467. ensureCapacity(size + numNew); // Increments modCount
  468. int numMoved = size - index;
  469. if (numMoved > 0)
  470. System.arraycopy(elementData, index, elementData, index + numNew,
  471. numMoved);
  472. System.arraycopy(a, 0, elementData, index, numNew);
  473. size += numNew;
  474. return numNew != 0;
  475. }
  476. /**
  477. * Removes from this List all of the elements whose index is between
  478. * fromIndex, inclusive and toIndex, exclusive. Shifts any succeeding
  479. * elements to the left (reduces their index).
  480. * This call shortens the list by <tt>(toIndex - fromIndex)</tt> elements.
  481. * (If <tt>toIndex==fromIndex</tt>, this operation has no effect.)
  482. *
  483. * @param fromIndex index of first element to be removed.
  484. * @param toIndex index after last element to be removed.
  485. */
  486. protected void removeRange(int fromIndex, int toIndex) {
  487. modCount++;
  488. int numMoved = size - toIndex;
  489. System.arraycopy(elementData, toIndex, elementData, fromIndex,
  490. numMoved);
  491. // Let gc do its work
  492. int newSize = size - (toIndex-fromIndex);
  493. while (size != newSize)
  494. elementData[--size] = null;
  495. }
  496. /**
  497. * Check if the given index is in range. If not, throw an appropriate
  498. * runtime exception. This method does *not* check if the index is
  499. * negative: It is always used immediately prior to an array access,
  500. * which throws an ArrayIndexOutOfBoundsException if index is negative.
  501. */
  502. private void RangeCheck(int index) {
  503. if (index >= size)
  504. throw new IndexOutOfBoundsException(
  505. "Index: "+index+", Size: "+size);
  506. }
  507. /**
  508. * Save the state of the <tt>ArrayList</tt> instance to a stream (that
  509. * is, serialize it).
  510. *
  511. * @serialData The length of the array backing the <tt>ArrayList</tt>
  512. * instance is emitted (int), followed by all of its elements
  513. * (each an <tt>Object</tt>) in the proper order.
  514. */
  515. private void writeObject(java.io.ObjectOutputStream s)
  516. throws java.io.IOException{
  517. // Write out element count, and any hidden stuff
  518. s.defaultWriteObject();
  519. // Write out array length
  520. s.writeInt(elementData.length);
  521. // Write out all elements in the proper order.
  522. for (int i=0; i<size; i++)
  523. s.writeObject(elementData[i]);
  524. }
  525. /**
  526. * Reconstitute the <tt>ArrayList</tt> instance from a stream (that is,
  527. * deserialize it).
  528. */
  529. private void readObject(java.io.ObjectInputStream s)
  530. throws java.io.IOException, ClassNotFoundException {
  531. // Read in size, and any hidden stuff
  532. s.defaultReadObject();
  533. // Read in array length and allocate array
  534. int arrayLength = s.readInt();
  535. Object[] a = elementData = (E[])new Object[arrayLength];
  536. // Read in all elements in the proper order.
  537. for (int i=0; i<size; i++)
  538. a[i] = s.readObject();
  539. }
  540. }