001: /*
002: * @(#)ArrayList.java 1.33 06/10/10
003: *
004: * Copyright 1990-2006 Sun Microsystems, Inc. All Rights Reserved.
005: * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER
006: *
007: * This program is free software; you can redistribute it and/or
008: * modify it under the terms of the GNU General Public License version
009: * 2 only, as published by the Free Software Foundation.
010: *
011: * This program is distributed in the hope that it will be useful, but
012: * WITHOUT ANY WARRANTY; without even the implied warranty of
013: * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
014: * General Public License version 2 for more details (a copy is
015: * included at /legal/license.txt).
016: *
017: * You should have received a copy of the GNU General Public License
018: * version 2 along with this work; if not, write to the Free Software
019: * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA
020: * 02110-1301 USA
021: *
022: * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa
023: * Clara, CA 95054 or visit www.sun.com if you need additional
024: * information or have any questions.
025: *
026: */
027:
028: package java.util;
029:
030: import sun.misc.CVM;
031:
032: /**
033: * Resizable-array implementation of the <tt>List</tt> interface. Implements
034: * all optional list operations, and permits all elements, including
035: * <tt>null</tt>. In addition to implementing the <tt>List</tt> interface,
036: * this class provides methods to manipulate the size of the array that is
037: * used internally to store the list. (This class is roughly equivalent to
038: * <tt>Vector</tt>, except that it is unsynchronized.)<p>
039: *
040: * The <tt>size</tt>, <tt>isEmpty</tt>, <tt>get</tt>, <tt>set</tt>,
041: * <tt>iterator</tt>, and <tt>listIterator</tt> operations run in constant
042: * time. The <tt>add</tt> operation runs in <i>amortized constant time</i>,
043: * that is, adding n elements requires O(n) time. All of the other operations
044: * run in linear time (roughly speaking). The constant factor is low compared
045: * to that for the <tt>LinkedList</tt> implementation.<p>
046: *
047: * Each <tt>ArrayList</tt> instance has a <i>capacity</i>. The capacity is
048: * the size of the array used to store the elements in the list. It is always
049: * at least as large as the list size. As elements are added to an ArrayList,
050: * its capacity grows automatically. The details of the growth policy are not
051: * specified beyond the fact that adding an element has constant amortized
052: * time cost.<p>
053: *
054: * An application can increase the capacity of an <tt>ArrayList</tt> instance
055: * before adding a large number of elements using the <tt>ensureCapacity</tt>
056: * operation. This may reduce the amount of incremental reallocation.<p>
057: *
058: * <strong>Note that this implementation is not synchronized.</strong> If
059: * multiple threads access an <tt>ArrayList</tt> instance concurrently, and at
060: * least one of the threads modifies the list structurally, it <i>must</i> be
061: * synchronized externally. (A structural modification is any operation that
062: * adds or deletes one or more elements, or explicitly resizes the backing
063: * array; merely setting the value of an element is not a structural
064: * modification.) This is typically accomplished by synchronizing on some
065: * object that naturally encapsulates the list. If no such object exists, the
066: * list should be "wrapped" using the <tt>Collections.synchronizedList</tt>
067: * method. This is best done at creation time, to prevent accidental
068: * unsynchronized access to the list:
069: * <pre>
070: * List list = Collections.synchronizedList(new ArrayList(...));
071: * </pre><p>
072: *
073: * The iterators returned by this class's <tt>iterator</tt> and
074: * <tt>listIterator</tt> methods are <i>fail-fast</i>: if list is structurally
075: * modified at any time after the iterator is created, in any way except
076: * through the iterator's own remove or add methods, the iterator will throw a
077: * ConcurrentModificationException. Thus, in the face of concurrent
078: * modification, the iterator fails quickly and cleanly, rather than risking
079: * arbitrary, non-deterministic behavior at an undetermined time in the
080: * future.<p>
081: *
082: * Note that the fail-fast behavior of an iterator cannot be guaranteed
083: * as it is, generally speaking, impossible to make any hard guarantees in the
084: * presence of unsynchronized concurrent modification. Fail-fast iterators
085: * throw <tt>ConcurrentModificationException</tt> on a best-effort basis.
086: * Therefore, it would be wrong to write a program that depended on this
087: * exception for its correctness: <i>the fail-fast behavior of iterators
088: * should be used only to detect bugs.</i><p>
089: *
090: * This class is a member of the
091: * <a href="{@docRoot}/../guide/collections/index.html">
092: * Java Collections Framework</a>.
093: *
094: * @author Josh Bloch
095: * @version 1.25, 02/02/00
096: * @see Collection
097: * @see List
098: * @see LinkedList
099: * @see Vector
100: * @see Collections#synchronizedList(List)
101: * @since 1.2
102: */
103:
104: public class ArrayList extends AbstractList implements List,
105: RandomAccess, Cloneable, java.io.Serializable {
106: private static final long serialVersionUID = 8683452581122892189L;
107:
108: /**
109: * The array buffer into which the elements of the ArrayList are stored.
110: * The capacity of the ArrayList is the length of this array buffer.
111: */
112: private transient Object elementData[];
113:
114: /**
115: * The size of the ArrayList (the number of elements it contains).
116: *
117: * @serial
118: */
119: private int size;
120:
121: /**
122: * Constructs an empty list with the specified initial capacity.
123: *
124: * @param initialCapacity the initial capacity of the list.
125: * @exception IllegalArgumentException if the specified initial capacity
126: * is negative
127: */
128: public ArrayList(int initialCapacity) {
129: super ();
130: if (initialCapacity < 0)
131: throw new IllegalArgumentException("Illegal Capacity: "
132: + initialCapacity);
133: this .elementData = new Object[initialCapacity];
134: }
135:
136: /**
137: * Constructs an empty list with an initial capacity of ten.
138: */
139: public ArrayList() {
140: this (10);
141: }
142:
143: /**
144: * Constructs a list containing the elements of the specified
145: * collection, in the order they are returned by the collection's
146: * iterator. The <tt>ArrayList</tt> instance has an initial capacity of
147: * 110% the size of the specified collection.
148: *
149: * @param c the collection whose elements are to be placed into this list.
150: * @throws NullPointerException if the specified collection is null.
151: */
152: public ArrayList(Collection c) {
153: size = c.size();
154: // Allow 10% room for growth
155: elementData = new Object[(int) Math.min((size * 110L) / 100,
156: Integer.MAX_VALUE)];
157: c.toArray(elementData);
158: }
159:
160: /**
161: * Trims the capacity of this <tt>ArrayList</tt> instance to be the
162: * list's current size. An application can use this operation to minimize
163: * the storage of an <tt>ArrayList</tt> instance.
164: */
165: public void trimToSize() {
166: modCount++;
167: int oldCapacity = elementData.length;
168: if (size < oldCapacity) {
169: Object oldData[] = elementData;
170: elementData = new Object[size];
171: /* IAI - 15 */
172: CVM.copyObjectArray(oldData, 0, elementData, 0, size);
173: /* IAI - 15 */
174: }
175: }
176:
177: /**
178: * Increases the capacity of this <tt>ArrayList</tt> instance, if
179: * necessary, to ensure that it can hold at least the number of elements
180: * specified by the minimum capacity argument.
181: *
182: * @param minCapacity the desired minimum capacity.
183: */
184: public void ensureCapacity(int minCapacity) {
185: modCount++;
186: int oldCapacity = elementData.length;
187: if (minCapacity > oldCapacity) {
188: Object oldData[] = elementData;
189: int newCapacity = (oldCapacity * 3) / 2 + 1;
190: if (newCapacity < minCapacity)
191: newCapacity = minCapacity;
192: elementData = new Object[newCapacity];
193: /* IAI - 15 */
194: CVM.copyObjectArray(oldData, 0, elementData, 0, size);
195: /* IAI - 15 */
196: }
197: }
198:
199: /**
200: * Returns the number of elements in this list.
201: *
202: * @return the number of elements in this list.
203: */
204: public int size() {
205: return size;
206: }
207:
208: /**
209: * Tests if this list has no elements.
210: *
211: * @return <tt>true</tt> if this list has no elements;
212: * <tt>false</tt> otherwise.
213: */
214: public boolean isEmpty() {
215: return size == 0;
216: }
217:
218: /**
219: * Returns <tt>true</tt> if this list contains the specified element.
220: *
221: * @param elem element whose presence in this List is to be tested.
222: * @return <code>true</code> if the specified element is present;
223: * <code>false</code> otherwise.
224: */
225: public boolean contains(Object elem) {
226: return indexOf(elem) >= 0;
227: }
228:
229: /**
230: * Searches for the first occurence of the given argument, testing
231: * for equality using the <tt>equals</tt> method.
232: *
233: * @param elem an object.
234: * @return the index of the first occurrence of the argument in this
235: * list; returns <tt>-1</tt> if the object is not found.
236: * @see Object#equals(Object)
237: */
238: public int indexOf(Object elem) {
239: if (elem == null) {
240: for (int i = 0; i < size; i++)
241: if (elementData[i] == null)
242: return i;
243: } else {
244: for (int i = 0; i < size; i++)
245: if (elem.equals(elementData[i]))
246: return i;
247: }
248: return -1;
249: }
250:
251: /**
252: * Returns the index of the last occurrence of the specified object in
253: * this list.
254: *
255: * @param elem the desired element.
256: * @return the index of the last occurrence of the specified object in
257: * this list; returns -1 if the object is not found.
258: */
259: public int lastIndexOf(Object elem) {
260: if (elem == null) {
261: for (int i = size - 1; i >= 0; i--)
262: if (elementData[i] == null)
263: return i;
264: } else {
265: for (int i = size - 1; i >= 0; i--)
266: if (elem.equals(elementData[i]))
267: return i;
268: }
269: return -1;
270: }
271:
272: /**
273: * Returns a shallow copy of this <tt>ArrayList</tt> instance. (The
274: * elements themselves are not copied.)
275: *
276: * @return a clone of this <tt>ArrayList</tt> instance.
277: */
278: public Object clone() {
279: try {
280: ArrayList v = (ArrayList) super .clone();
281: v.elementData = new Object[size];
282: /* IAI - 15 */
283: CVM.copyObjectArray(elementData, 0, v.elementData, 0, size);
284: /* IAI - 15 */
285: v.modCount = 0;
286: return v;
287: } catch (CloneNotSupportedException e) {
288: // this shouldn't happen, since we are Cloneable
289: throw new InternalError();
290: }
291: }
292:
293: /**
294: * Returns an array containing all of the elements in this list
295: * in the correct order.
296: *
297: * @return an array containing all of the elements in this list
298: * in the correct order.
299: */
300: public Object[] toArray() {
301: Object[] result = new Object[size];
302: System.arraycopy(elementData, 0, result, 0, size);
303: return result;
304: }
305:
306: /**
307: * Returns an array containing all of the elements in this list in the
308: * correct order; the runtime type of the returned array is that of the
309: * specified array. If the list fits in the specified array, it is
310: * returned therein. Otherwise, a new array is allocated with the runtime
311: * type of the specified array and the size of this list.<p>
312: *
313: * If the list fits in the specified array with room to spare (i.e., the
314: * array has more elements than the list), the element in the array
315: * immediately following the end of the collection is set to
316: * <tt>null</tt>. This is useful in determining the length of the list
317: * <i>only</i> if the caller knows that the list does not contain any
318: * <tt>null</tt> elements.
319: *
320: * @param a the array into which the elements of the list are to
321: * be stored, if it is big enough; otherwise, a new array of the
322: * same runtime type is allocated for this purpose.
323: * @return an array containing the elements of the list.
324: * @throws ArrayStoreException if the runtime type of a is not a supertype
325: * of the runtime type of every element in this list.
326: */
327: public Object[] toArray(Object a[]) {
328: if (a.length < size)
329: a = (Object[]) java.lang.reflect.Array.newInstance(a
330: .getClass().getComponentType(), size);
331:
332: System.arraycopy(elementData, 0, a, 0, size);
333:
334: if (a.length > size)
335: a[size] = null;
336:
337: return a;
338: }
339:
340: // Positional Access Operations
341:
342: /**
343: * Returns the element at the specified position in this list.
344: *
345: * @param index index of element to return.
346: * @return the element at the specified position in this list.
347: * @throws IndexOutOfBoundsException if index is out of range <tt>(index
348: * < 0 || index >= size())</tt>.
349: */
350: public Object get(int index) {
351: RangeCheck(index);
352:
353: return elementData[index];
354: }
355:
356: /**
357: * Replaces the element at the specified position in this list with
358: * the specified element.
359: *
360: * @param index index of element to replace.
361: * @param element element to be stored at the specified position.
362: * @return the element previously at the specified position.
363: * @throws IndexOutOfBoundsException if index out of range
364: * <tt>(index < 0 || index >= size())</tt>.
365: */
366: public Object set(int index, Object element) {
367: RangeCheck(index);
368:
369: Object oldValue = elementData[index];
370: elementData[index] = element;
371: return oldValue;
372: }
373:
374: /**
375: * Appends the specified element to the end of this list.
376: *
377: * @param o element to be appended to this list.
378: * @return <tt>true</tt> (as per the general contract of Collection.add).
379: */
380: public boolean add(Object o) {
381: ensureCapacity(size + 1); // Increments modCount!!
382: elementData[size++] = o;
383: return true;
384: }
385:
386: /**
387: * Inserts the specified element at the specified position in this
388: * list. Shifts the element currently at that position (if any) and
389: * any subsequent elements to the right (adds one to their indices).
390: *
391: * @param index index at which the specified element is to be inserted.
392: * @param element element to be inserted.
393: * @throws IndexOutOfBoundsException if index is out of range
394: * <tt>(index < 0 || index > size())</tt>.
395: */
396: public void add(int index, Object element) {
397: if (index > size || index < 0)
398: throw new IndexOutOfBoundsException("Index: " + index
399: + ", Size: " + size);
400:
401: ensureCapacity(size + 1); // Increments modCount!!
402: /* IAI - 15 */
403:
404: CVM.copyObjectArray(elementData, index, elementData, index + 1,
405: size - index);
406: /* IAI - 15 */
407: elementData[index] = element;
408: size++;
409: }
410:
411: /**
412: * Removes the element at the specified position in this list.
413: * Shifts any subsequent elements to the left (subtracts one from their
414: * indices).
415: *
416: * @param index the index of the element to removed.
417: * @return the element that was removed from the list.
418: * @throws IndexOutOfBoundsException if index out of range <tt>(index
419: * < 0 || index >= size())</tt>.
420: */
421: public Object remove(int index) {
422: RangeCheck(index);
423:
424: modCount++;
425: Object oldValue = elementData[index];
426:
427: int numMoved = size - index - 1;
428: if (numMoved > 0)
429: System.arraycopy(elementData, index + 1, elementData,
430: index, numMoved);
431: elementData[--size] = null; // Let gc do its work
432:
433: return oldValue;
434: }
435:
436: /**
437: * Removes all of the elements from this list. The list will
438: * be empty after this call returns.
439: */
440: public void clear() {
441: modCount++;
442:
443: // Let gc do its work
444: for (int i = 0; i < size; i++)
445: elementData[i] = null;
446:
447: size = 0;
448: }
449:
450: /**
451: * Appends all of the elements in the specified Collection to the end of
452: * this list, in the order that they are returned by the
453: * specified Collection's Iterator. The behavior of this operation is
454: * undefined if the specified Collection is modified while the operation
455: * is in progress. (This implies that the behavior of this call is
456: * undefined if the specified Collection is this list, and this
457: * list is nonempty.)
458: *
459: * @param c the elements to be inserted into this list.
460: * @return <tt>true</tt> if this list changed as a result of the call.
461: * @throws NullPointerException if the specified collection is null.
462: */
463: public boolean addAll(Collection c) {
464: Object[] a = c.toArray();
465: int numNew = a.length;
466: ensureCapacity(size + numNew); // Increments modCount
467: /* IAI - 15 */
468:
469: CVM.copyObjectArray(a, 0, elementData, size, numNew);
470: /* IAI - 15 */
471: size += numNew;
472: return numNew != 0;
473: }
474:
475: /**
476: * Inserts all of the elements in the specified Collection into this
477: * list, starting at the specified position. Shifts the element
478: * currently at that position (if any) and any subsequent elements to
479: * the right (increases their indices). The new elements will appear
480: * in the list in the order that they are returned by the
481: * specified Collection's iterator.
482: *
483: * @param index index at which to insert first element
484: * from the specified collection.
485: * @param c elements to be inserted into this list.
486: * @return <tt>true</tt> if this list changed as a result of the call.
487: * @throws IndexOutOfBoundsException if index out of range <tt>(index
488: * < 0 || index > size())</tt>.
489: * @throws NullPointerException if the specified Collection is null.
490: */
491: public boolean addAll(int index, Collection c) {
492: if (index > size || index < 0)
493: throw new IndexOutOfBoundsException("Index: " + index
494: + ", Size: " + size);
495:
496: Object[] a = c.toArray();
497: int numNew = a.length;
498: ensureCapacity(size + numNew); // Increments modCount
499:
500: int numMoved = size - index;
501: if (numMoved > 0) {
502: /* IAI - 15 */
503: CVM.copyObjectArray(elementData, index, elementData, index
504: + numNew, numMoved);
505: }
506:
507: CVM.copyObjectArray(a, 0, elementData, index, numNew);
508: /* IAI - 15 */
509: size += numNew;
510: return numNew != 0;
511: }
512:
513: /**
514: * Removes from this List all of the elements whose index is between
515: * fromIndex, inclusive and toIndex, exclusive. Shifts any succeeding
516: * elements to the left (reduces their index).
517: * This call shortens the list by <tt>(toIndex - fromIndex)</tt> elements.
518: * (If <tt>toIndex==fromIndex</tt>, this operation has no effect.)
519: *
520: * @param fromIndex index of first element to be removed.
521: * @param toIndex index after last element to be removed.
522: */
523: protected void removeRange(int fromIndex, int toIndex) {
524: modCount++;
525: int numMoved = size - toIndex;
526: System.arraycopy(elementData, toIndex, elementData, fromIndex,
527: numMoved);
528:
529: // Let gc do its work
530: int newSize = size - (toIndex - fromIndex);
531: while (size != newSize)
532: elementData[--size] = null;
533: }
534:
535: /**
536: * Check if the given index is in range. If not, throw an appropriate
537: * runtime exception. This method does *not* check if the index is
538: * negative: It is always used immediately prior to an array access,
539: * which throws an ArrayIndexOutOfBoundsException if index is negative.
540: */
541: private void RangeCheck(int index) {
542: if (index >= size)
543: throw new IndexOutOfBoundsException("Index: " + index
544: + ", Size: " + size);
545: }
546:
547: /**
548: * Save the state of the <tt>ArrayList</tt> instance to a stream (that
549: * is, serialize it).
550: *
551: * @serialData The length of the array backing the <tt>ArrayList</tt>
552: * instance is emitted (int), followed by all of its elements
553: * (each an <tt>Object</tt>) in the proper order.
554: */
555: private void writeObject(java.io.ObjectOutputStream s)
556: throws java.io.IOException {
557: // Write out element count, and any hidden stuff
558: s.defaultWriteObject();
559:
560: // Write out array length
561: s.writeInt(elementData.length);
562:
563: // Write out all elements in the proper order.
564: for (int i = 0; i < size; i++)
565: s.writeObject(elementData[i]);
566: }
567:
568: /**
569: * Reconstitute the <tt>ArrayList</tt> instance from a stream (that is,
570: * deserialize it).
571: */
572: private void readObject(java.io.ObjectInputStream s)
573: throws java.io.IOException, ClassNotFoundException {
574: // Read in size, and any hidden stuff
575: s.defaultReadObject();
576:
577: // Read in array length and allocate array
578: int arrayLength = s.readInt();
579: elementData = new Object[arrayLength];
580:
581: // Read in all elements in the proper order.
582: for (int i = 0; i < size; i++)
583: elementData[i] = s.readObject();
584: }
585: }
|