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