1. /*
  2. * @(#)ArrayList.java 1.41 03/01/23
  3. *
  4. * Copyright 2003 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. * @version 1.41, 01/23/03
  72. * @see Collection
  73. * @see List
  74. * @see LinkedList
  75. * @see Vector
  76. * @see Collections#synchronizedList(List)
  77. * @since 1.2
  78. */
  79. public class ArrayList extends AbstractList
  80. implements List, RandomAccess, Cloneable, java.io.Serializable
  81. {
  82. private static final long serialVersionUID = 8683452581122892189L;
  83. /**
  84. * The array buffer into which the elements of the ArrayList are stored.
  85. * The capacity of the ArrayList is the length of this array buffer.
  86. */
  87. private transient Object elementData[];
  88. /**
  89. * The size of the ArrayList (the number of elements it contains).
  90. *
  91. * @serial
  92. */
  93. private int size;
  94. /**
  95. * Constructs an empty list with the specified initial capacity.
  96. *
  97. * @param initialCapacity the initial capacity of the list.
  98. * @exception IllegalArgumentException if the specified initial capacity
  99. * is negative
  100. */
  101. public ArrayList(int initialCapacity) {
  102. super();
  103. if (initialCapacity < 0)
  104. throw new IllegalArgumentException("Illegal Capacity: "+
  105. initialCapacity);
  106. this.elementData = new Object[initialCapacity];
  107. }
  108. /**
  109. * Constructs an empty list with an initial capacity of ten.
  110. */
  111. public ArrayList() {
  112. this(10);
  113. }
  114. /**
  115. * Constructs a list containing the elements of the specified
  116. * collection, in the order they are returned by the collection's
  117. * iterator. The <tt>ArrayList</tt> instance has an initial capacity of
  118. * 110% the size of the specified collection.
  119. *
  120. * @param c the collection whose elements are to be placed into this list.
  121. * @throws NullPointerException if the specified collection is null.
  122. */
  123. public ArrayList(Collection c) {
  124. size = c.size();
  125. // Allow 10% room for growth
  126. elementData = new Object[
  127. (int)Math.min((size*110L)/100,Integer.MAX_VALUE)];
  128. c.toArray(elementData);
  129. }
  130. /**
  131. * Trims the capacity of this <tt>ArrayList</tt> instance to be the
  132. * list's current size. An application can use this operation to minimize
  133. * the storage of an <tt>ArrayList</tt> instance.
  134. */
  135. public void trimToSize() {
  136. modCount++;
  137. int oldCapacity = elementData.length;
  138. if (size < oldCapacity) {
  139. Object oldData[] = elementData;
  140. elementData = new Object[size];
  141. System.arraycopy(oldData, 0, elementData, 0, size);
  142. }
  143. }
  144. /**
  145. * Increases the capacity of this <tt>ArrayList</tt> instance, if
  146. * necessary, to ensure that it can hold at least the number of elements
  147. * specified by the minimum capacity argument.
  148. *
  149. * @param minCapacity the desired minimum capacity.
  150. */
  151. public void ensureCapacity(int minCapacity) {
  152. modCount++;
  153. int oldCapacity = elementData.length;
  154. if (minCapacity > oldCapacity) {
  155. Object oldData[] = elementData;
  156. int newCapacity = (oldCapacity * 3)/2 + 1;
  157. if (newCapacity < minCapacity)
  158. newCapacity = minCapacity;
  159. elementData = new Object[newCapacity];
  160. System.arraycopy(oldData, 0, elementData, 0, size);
  161. }
  162. }
  163. /**
  164. * Returns the number of elements in this list.
  165. *
  166. * @return the number of elements in this list.
  167. */
  168. public int size() {
  169. return size;
  170. }
  171. /**
  172. * Tests if this list has no elements.
  173. *
  174. * @return <tt>true</tt> if this list has no elements;
  175. * <tt>false</tt> otherwise.
  176. */
  177. public boolean isEmpty() {
  178. return size == 0;
  179. }
  180. /**
  181. * Returns <tt>true</tt> if this list contains the specified element.
  182. *
  183. * @param elem element whose presence in this List is to be tested.
  184. * @return <code>true</code> if the specified element is present;
  185. * <code>false</code> otherwise.
  186. */
  187. public boolean contains(Object elem) {
  188. return indexOf(elem) >= 0;
  189. }
  190. /**
  191. * Searches for the first occurence of the given argument, testing
  192. * for equality using the <tt>equals</tt> method.
  193. *
  194. * @param elem an object.
  195. * @return the index of the first occurrence of the argument in this
  196. * list; returns <tt>-1</tt> if the object is not found.
  197. * @see Object#equals(Object)
  198. */
  199. public int indexOf(Object elem) {
  200. if (elem == null) {
  201. for (int i = 0; i < size; i++)
  202. if (elementData[i]==null)
  203. return i;
  204. } else {
  205. for (int i = 0; i < size; i++)
  206. if (elem.equals(elementData[i]))
  207. return i;
  208. }
  209. return -1;
  210. }
  211. /**
  212. * Returns the index of the last occurrence of the specified object in
  213. * this list.
  214. *
  215. * @param elem the desired element.
  216. * @return the index of the last occurrence of the specified object in
  217. * this list; returns -1 if the object is not found.
  218. */
  219. public int lastIndexOf(Object elem) {
  220. if (elem == null) {
  221. for (int i = size-1; i >= 0; i--)
  222. if (elementData[i]==null)
  223. return i;
  224. } else {
  225. for (int i = size-1; i >= 0; i--)
  226. if (elem.equals(elementData[i]))
  227. return i;
  228. }
  229. return -1;
  230. }
  231. /**
  232. * Returns a shallow copy of this <tt>ArrayList</tt> instance. (The
  233. * elements themselves are not copied.)
  234. *
  235. * @return a clone of this <tt>ArrayList</tt> instance.
  236. */
  237. public Object clone() {
  238. try {
  239. ArrayList v = (ArrayList)super.clone();
  240. v.elementData = new Object[size];
  241. System.arraycopy(elementData, 0, v.elementData, 0, size);
  242. v.modCount = 0;
  243. return v;
  244. } catch (CloneNotSupportedException e) {
  245. // this shouldn't happen, since we are Cloneable
  246. throw new InternalError();
  247. }
  248. }
  249. /**
  250. * Returns an array containing all of the elements in this list
  251. * in the correct order.
  252. *
  253. * @return an array containing all of the elements in this list
  254. * in the correct order.
  255. */
  256. public Object[] toArray() {
  257. Object[] result = new Object[size];
  258. System.arraycopy(elementData, 0, result, 0, size);
  259. return result;
  260. }
  261. /**
  262. * Returns an array containing all of the elements in this list in the
  263. * correct order; the runtime type of the returned array is that of the
  264. * specified array. If the list fits in the specified array, it is
  265. * returned therein. Otherwise, a new array is allocated with the runtime
  266. * type of the specified array and the size of this list.<p>
  267. *
  268. * If the list fits in the specified array with room to spare (i.e., the
  269. * array has more elements than the list), the element in the array
  270. * immediately following the end of the collection is set to
  271. * <tt>null</tt>. This is useful in determining the length of the list
  272. * <i>only</i> if the caller knows that the list does not contain any
  273. * <tt>null</tt> elements.
  274. *
  275. * @param a the array into which the elements of the list are to
  276. * be stored, if it is big enough; otherwise, a new array of the
  277. * same runtime type is allocated for this purpose.
  278. * @return an array containing the elements of the list.
  279. * @throws ArrayStoreException if the runtime type of a is not a supertype
  280. * of the runtime type of every element in this list.
  281. */
  282. public Object[] toArray(Object a[]) {
  283. if (a.length < size)
  284. a = (Object[])java.lang.reflect.Array.newInstance(
  285. a.getClass().getComponentType(), size);
  286. System.arraycopy(elementData, 0, a, 0, size);
  287. if (a.length > size)
  288. a[size] = null;
  289. return a;
  290. }
  291. // Positional Access Operations
  292. /**
  293. * Returns the element at the specified position in this list.
  294. *
  295. * @param index index of element to return.
  296. * @return the element at the specified position in this list.
  297. * @throws IndexOutOfBoundsException if index is out of range <tt>(index
  298. * < 0 || index >= size())</tt>.
  299. */
  300. public Object get(int index) {
  301. RangeCheck(index);
  302. return elementData[index];
  303. }
  304. /**
  305. * Replaces the element at the specified position in this list with
  306. * the specified element.
  307. *
  308. * @param index index of element to replace.
  309. * @param element element to be stored at the specified position.
  310. * @return the element previously at the specified position.
  311. * @throws IndexOutOfBoundsException if index out of range
  312. * <tt>(index < 0 || index >= size())</tt>.
  313. */
  314. public Object set(int index, Object element) {
  315. RangeCheck(index);
  316. Object oldValue = elementData[index];
  317. elementData[index] = element;
  318. return oldValue;
  319. }
  320. /**
  321. * Appends the specified element to the end of this list.
  322. *
  323. * @param o element to be appended to this list.
  324. * @return <tt>true</tt> (as per the general contract of Collection.add).
  325. */
  326. public boolean add(Object o) {
  327. ensureCapacity(size + 1); // Increments modCount!!
  328. elementData[size++] = o;
  329. return true;
  330. }
  331. /**
  332. * Inserts the specified element at the specified position in this
  333. * list. Shifts the element currently at that position (if any) and
  334. * any subsequent elements to the right (adds one to their indices).
  335. *
  336. * @param index index at which the specified element is to be inserted.
  337. * @param element element to be inserted.
  338. * @throws IndexOutOfBoundsException if index is out of range
  339. * <tt>(index < 0 || index > size())</tt>.
  340. */
  341. public void add(int index, Object element) {
  342. if (index > size || index < 0)
  343. throw new IndexOutOfBoundsException(
  344. "Index: "+index+", Size: "+size);
  345. ensureCapacity(size+1); // Increments modCount!!
  346. System.arraycopy(elementData, index, elementData, index + 1,
  347. size - index);
  348. elementData[index] = element;
  349. size++;
  350. }
  351. /**
  352. * Removes the element at the specified position in this list.
  353. * Shifts any subsequent elements to the left (subtracts one from their
  354. * indices).
  355. *
  356. * @param index the index of the element to removed.
  357. * @return the element that was removed from the list.
  358. * @throws IndexOutOfBoundsException if index out of range <tt>(index
  359. * < 0 || index >= size())</tt>.
  360. */
  361. public Object remove(int index) {
  362. RangeCheck(index);
  363. modCount++;
  364. Object oldValue = elementData[index];
  365. int numMoved = size - index - 1;
  366. if (numMoved > 0)
  367. System.arraycopy(elementData, index+1, elementData, index,
  368. numMoved);
  369. elementData[--size] = null; // Let gc do its work
  370. return oldValue;
  371. }
  372. /**
  373. * Removes all of the elements from this list. The list will
  374. * be empty after this call returns.
  375. */
  376. public void clear() {
  377. modCount++;
  378. // Let gc do its work
  379. for (int i = 0; i < size; i++)
  380. elementData[i] = null;
  381. size = 0;
  382. }
  383. /**
  384. * Appends all of the elements in the specified Collection to the end of
  385. * this list, in the order that they are returned by the
  386. * specified Collection's Iterator. The behavior of this operation is
  387. * undefined if the specified Collection is modified while the operation
  388. * is in progress. (This implies that the behavior of this call is
  389. * undefined if the specified Collection is this list, and this
  390. * list is nonempty.)
  391. *
  392. * @param c the elements to be inserted into this list.
  393. * @return <tt>true</tt> if this list changed as a result of the call.
  394. * @throws NullPointerException if the specified collection is null.
  395. */
  396. public boolean addAll(Collection c) {
  397. Object[] a = c.toArray();
  398. int numNew = a.length;
  399. ensureCapacity(size + numNew); // Increments modCount
  400. System.arraycopy(a, 0, elementData, size, numNew);
  401. size += numNew;
  402. return numNew != 0;
  403. }
  404. /**
  405. * Inserts all of the elements in the specified Collection into this
  406. * list, starting at the specified position. Shifts the element
  407. * currently at that position (if any) and any subsequent elements to
  408. * the right (increases their indices). The new elements will appear
  409. * in the list in the order that they are returned by the
  410. * specified Collection's iterator.
  411. *
  412. * @param index index at which to insert first element
  413. * from the specified collection.
  414. * @param c elements to be inserted into this list.
  415. * @return <tt>true</tt> if this list changed as a result of the call.
  416. * @throws IndexOutOfBoundsException if index out of range <tt>(index
  417. * < 0 || index > size())</tt>.
  418. * @throws NullPointerException if the specified Collection is null.
  419. */
  420. public boolean addAll(int index, Collection c) {
  421. if (index > size || index < 0)
  422. throw new IndexOutOfBoundsException(
  423. "Index: " + index + ", Size: " + size);
  424. Object[] a = c.toArray();
  425. int numNew = a.length;
  426. ensureCapacity(size + numNew); // Increments modCount
  427. int numMoved = size - index;
  428. if (numMoved > 0)
  429. System.arraycopy(elementData, index, elementData, index + numNew,
  430. numMoved);
  431. System.arraycopy(a, 0, elementData, index, numNew);
  432. size += numNew;
  433. return numNew != 0;
  434. }
  435. /**
  436. * Removes from this List all of the elements whose index is between
  437. * fromIndex, inclusive and toIndex, exclusive. Shifts any succeeding
  438. * elements to the left (reduces their index).
  439. * This call shortens the list by <tt>(toIndex - fromIndex)</tt> elements.
  440. * (If <tt>toIndex==fromIndex</tt>, this operation has no effect.)
  441. *
  442. * @param fromIndex index of first element to be removed.
  443. * @param toIndex index after last element to be removed.
  444. */
  445. protected void removeRange(int fromIndex, int toIndex) {
  446. modCount++;
  447. int numMoved = size - toIndex;
  448. System.arraycopy(elementData, toIndex, elementData, fromIndex,
  449. numMoved);
  450. // Let gc do its work
  451. int newSize = size - (toIndex-fromIndex);
  452. while (size != newSize)
  453. elementData[--size] = null;
  454. }
  455. /**
  456. * Check if the given index is in range. If not, throw an appropriate
  457. * runtime exception. This method does *not* check if the index is
  458. * negative: It is always used immediately prior to an array access,
  459. * which throws an ArrayIndexOutOfBoundsException if index is negative.
  460. */
  461. private void RangeCheck(int index) {
  462. if (index >= size)
  463. throw new IndexOutOfBoundsException(
  464. "Index: "+index+", Size: "+size);
  465. }
  466. /**
  467. * Save the state of the <tt>ArrayList</tt> instance to a stream (that
  468. * is, serialize it).
  469. *
  470. * @serialData The length of the array backing the <tt>ArrayList</tt>
  471. * instance is emitted (int), followed by all of its elements
  472. * (each an <tt>Object</tt>) in the proper order.
  473. */
  474. private void writeObject(java.io.ObjectOutputStream s)
  475. throws java.io.IOException{
  476. // Write out element count, and any hidden stuff
  477. s.defaultWriteObject();
  478. // Write out array length
  479. s.writeInt(elementData.length);
  480. // Write out all elements in the proper order.
  481. for (int i=0; i<size; i++)
  482. s.writeObject(elementData[i]);
  483. }
  484. /**
  485. * Reconstitute the <tt>ArrayList</tt> instance from a stream (that is,
  486. * deserialize it).
  487. */
  488. private void readObject(java.io.ObjectInputStream s)
  489. throws java.io.IOException, ClassNotFoundException {
  490. // Read in size, and any hidden stuff
  491. s.defaultReadObject();
  492. // Read in array length and allocate array
  493. int arrayLength = s.readInt();
  494. elementData = new Object[arrayLength];
  495. // Read in all elements in the proper order.
  496. for (int i=0; i<size; i++)
  497. elementData[i] = s.readObject();
  498. }
  499. }