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