001 /* ArrayList.java -- JDK1.2's answer to Vector; this is an array-backed
002 implementation of the List interface
003 Copyright (C) 1998, 1999, 2000, 2001, 2004, 2005 Free Software Foundation, Inc.
004
005 This file is part of GNU Classpath.
006
007 GNU Classpath is free software; you can redistribute it and/or modify
008 it under the terms of the GNU General Public License as published by
009 the Free Software Foundation; either version 2, or (at your option)
010 any later version.
011
012 GNU Classpath is distributed in the hope that it will be useful, but
013 WITHOUT ANY WARRANTY; without even the implied warranty of
014 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
015 General Public License for more details.
016
017 You should have received a copy of the GNU General Public License
018 along with GNU Classpath; see the file COPYING. If not, write to the
019 Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
020 02110-1301 USA.
021
022 Linking this library statically or dynamically with other modules is
023 making a combined work based on this library. Thus, the terms and
024 conditions of the GNU General Public License cover the whole
025 combination.
026
027 As a special exception, the copyright holders of this library give you
028 permission to link this library with independent modules to produce an
029 executable, regardless of the license terms of these independent
030 modules, and to copy and distribute the resulting executable under
031 terms of your choice, provided that you also meet, for each linked
032 independent module, the terms and conditions of the license of that
033 module. An independent module is a module which is not derived from
034 or based on this library. If you modify this library, you may extend
035 this exception to your version of the library, but you are not
036 obligated to do so. If you do not wish to do so, delete this
037 exception statement from your version. */
038
039
040 package java.util;
041
042 import java.io.IOException;
043 import java.io.ObjectInputStream;
044 import java.io.ObjectOutputStream;
045 import java.io.Serializable;
046 import java.lang.reflect.Array;
047
048 /**
049 * An array-backed implementation of the List interface. This implements
050 * all optional list operations, and permits null elements, so that it is
051 * better than Vector, which it replaces. Random access is roughly constant
052 * time, and iteration is roughly linear time, so it is nice and fast, with
053 * less overhead than a LinkedList.
054 * <p>
055 *
056 * Each list has a capacity, and as the array reaches that capacity it
057 * is automatically transferred to a larger array. You also have access to
058 * ensureCapacity and trimToSize to control the backing array's size, avoiding
059 * reallocation or wasted memory.
060 * <p>
061 *
062 * ArrayList is not synchronized, so if you need multi-threaded access,
063 * consider using:<br>
064 * <code>List l = Collections.synchronizedList(new ArrayList(...));</code>
065 * <p>
066 *
067 * The iterators are <i>fail-fast</i>, meaning that any structural
068 * modification, except for <code>remove()</code> called on the iterator
069 * itself, cause the iterator to throw a
070 * {@link ConcurrentModificationException} rather than exhibit
071 * non-deterministic behavior.
072 *
073 * @author Jon A. Zeppieri
074 * @author Bryce McKinlay
075 * @author Eric Blake (ebb9@email.byu.edu)
076 * @see Collection
077 * @see List
078 * @see LinkedList
079 * @see Vector
080 * @see Collections#synchronizedList(List)
081 * @see AbstractList
082 * @status updated to 1.4
083 */
084 public class ArrayList<E> extends AbstractList<E>
085 implements List<E>, RandomAccess, Cloneable, Serializable
086 {
087 /**
088 * Compatible with JDK 1.2
089 */
090 private static final long serialVersionUID = 8683452581122892189L;
091
092 /**
093 * The default capacity for new ArrayLists.
094 */
095 private static final int DEFAULT_CAPACITY = 10;
096
097 /**
098 * The number of elements in this list.
099 * @serial the list size
100 */
101 private int size;
102
103 /**
104 * Where the data is stored.
105 */
106 private transient E[] data;
107
108 /**
109 * Construct a new ArrayList with the supplied initial capacity.
110 *
111 * @param capacity initial capacity of this ArrayList
112 * @throws IllegalArgumentException if capacity is negative
113 */
114 public ArrayList(int capacity)
115 {
116 // Must explicitly check, to get correct exception.
117 if (capacity < 0)
118 throw new IllegalArgumentException();
119 data = (E[]) new Object[capacity];
120 }
121
122 /**
123 * Construct a new ArrayList with the default capacity (16).
124 */
125 public ArrayList()
126 {
127 this(DEFAULT_CAPACITY);
128 }
129
130 /**
131 * Construct a new ArrayList, and initialize it with the elements
132 * in the supplied Collection. The initial capacity is 110% of the
133 * Collection's size.
134 *
135 * @param c the collection whose elements will initialize this list
136 * @throws NullPointerException if c is null
137 */
138 public ArrayList(Collection<? extends E> c)
139 {
140 this((int) (c.size() * 1.1f));
141 addAll(c);
142 }
143
144 /**
145 * Trims the capacity of this List to be equal to its size;
146 * a memory saver.
147 */
148 public void trimToSize()
149 {
150 // Not a structural change from the perspective of iterators on this list,
151 // so don't update modCount.
152 if (size != data.length)
153 {
154 E[] newData = (E[]) new Object[size];
155 System.arraycopy(data, 0, newData, 0, size);
156 data = newData;
157 }
158 }
159
160 /**
161 * Guarantees that this list will have at least enough capacity to
162 * hold minCapacity elements. This implementation will grow the list to
163 * max(current * 2, minCapacity) if (minCapacity > current). The JCL says
164 * explictly that "this method increases its capacity to minCap", while
165 * the JDK 1.3 online docs specify that the list will grow to at least the
166 * size specified.
167 *
168 * @param minCapacity the minimum guaranteed capacity
169 */
170 public void ensureCapacity(int minCapacity)
171 {
172 int current = data.length;
173
174 if (minCapacity > current)
175 {
176 E[] newData = (E[]) new Object[Math.max(current * 2, minCapacity)];
177 System.arraycopy(data, 0, newData, 0, size);
178 data = newData;
179 }
180 }
181
182 /**
183 * Returns the number of elements in this list.
184 *
185 * @return the list size
186 */
187 public int size()
188 {
189 return size;
190 }
191
192 /**
193 * Checks if the list is empty.
194 *
195 * @return true if there are no elements
196 */
197 public boolean isEmpty()
198 {
199 return size == 0;
200 }
201
202 /**
203 * Returns true iff element is in this ArrayList.
204 *
205 * @param e the element whose inclusion in the List is being tested
206 * @return true if the list contains e
207 */
208 public boolean contains(Object e)
209 {
210 return indexOf(e) != -1;
211 }
212
213 /**
214 * Returns the lowest index at which element appears in this List, or
215 * -1 if it does not appear.
216 *
217 * @param e the element whose inclusion in the List is being tested
218 * @return the index where e was found
219 */
220 public int indexOf(Object e)
221 {
222 for (int i = 0; i < size; i++)
223 if (equals(e, data[i]))
224 return i;
225 return -1;
226 }
227
228 /**
229 * Returns the highest index at which element appears in this List, or
230 * -1 if it does not appear.
231 *
232 * @param e the element whose inclusion in the List is being tested
233 * @return the index where e was found
234 */
235 public int lastIndexOf(Object e)
236 {
237 for (int i = size - 1; i >= 0; i--)
238 if (equals(e, data[i]))
239 return i;
240 return -1;
241 }
242
243 /**
244 * Creates a shallow copy of this ArrayList (elements are not cloned).
245 *
246 * @return the cloned object
247 */
248 public Object clone()
249 {
250 ArrayList<E> clone = null;
251 try
252 {
253 clone = (ArrayList<E>) super.clone();
254 clone.data = (E[]) data.clone();
255 }
256 catch (CloneNotSupportedException e)
257 {
258 // Impossible to get here.
259 }
260 return clone;
261 }
262
263 /**
264 * Returns an Object array containing all of the elements in this ArrayList.
265 * The array is independent of this list.
266 *
267 * @return an array representation of this list
268 */
269 public Object[] toArray()
270 {
271 E[] array = (E[]) new Object[size];
272 System.arraycopy(data, 0, array, 0, size);
273 return array;
274 }
275
276 /**
277 * Returns an Array whose component type is the runtime component type of
278 * the passed-in Array. The returned Array is populated with all of the
279 * elements in this ArrayList. If the passed-in Array is not large enough
280 * to store all of the elements in this List, a new Array will be created
281 * and returned; if the passed-in Array is <i>larger</i> than the size
282 * of this List, then size() index will be set to null.
283 *
284 * @param a the passed-in Array
285 * @return an array representation of this list
286 * @throws ArrayStoreException if the runtime type of a does not allow
287 * an element in this list
288 * @throws NullPointerException if a is null
289 */
290 public <T> T[] toArray(T[] a)
291 {
292 if (a.length < size)
293 a = (T[]) Array.newInstance(a.getClass().getComponentType(), size);
294 else if (a.length > size)
295 a[size] = null;
296 System.arraycopy(data, 0, a, 0, size);
297 return a;
298 }
299
300 /**
301 * Retrieves the element at the user-supplied index.
302 *
303 * @param index the index of the element we are fetching
304 * @throws IndexOutOfBoundsException if index < 0 || index >= size()
305 */
306 public E get(int index)
307 {
308 checkBoundExclusive(index);
309 return data[index];
310 }
311
312 /**
313 * Sets the element at the specified index. The new element, e,
314 * can be an object of any type or null.
315 *
316 * @param index the index at which the element is being set
317 * @param e the element to be set
318 * @return the element previously at the specified index
319 * @throws IndexOutOfBoundsException if index < 0 || index >= 0
320 */
321 public E set(int index, E e)
322 {
323 checkBoundExclusive(index);
324 E result = data[index];
325 data[index] = e;
326 return result;
327 }
328
329 /**
330 * Appends the supplied element to the end of this list.
331 * The element, e, can be an object of any type or null.
332 *
333 * @param e the element to be appended to this list
334 * @return true, the add will always succeed
335 */
336 public boolean add(E e)
337 {
338 modCount++;
339 if (size == data.length)
340 ensureCapacity(size + 1);
341 data[size++] = e;
342 return true;
343 }
344
345 /**
346 * Adds the supplied element at the specified index, shifting all
347 * elements currently at that index or higher one to the right.
348 * The element, e, can be an object of any type or null.
349 *
350 * @param index the index at which the element is being added
351 * @param e the item being added
352 * @throws IndexOutOfBoundsException if index < 0 || index > size()
353 */
354 public void add(int index, E e)
355 {
356 checkBoundInclusive(index);
357 modCount++;
358 if (size == data.length)
359 ensureCapacity(size + 1);
360 if (index != size)
361 System.arraycopy(data, index, data, index + 1, size - index);
362 data[index] = e;
363 size++;
364 }
365
366 /**
367 * Removes the element at the user-supplied index.
368 *
369 * @param index the index of the element to be removed
370 * @return the removed Object
371 * @throws IndexOutOfBoundsException if index < 0 || index >= size()
372 */
373 public E remove(int index)
374 {
375 checkBoundExclusive(index);
376 E r = data[index];
377 modCount++;
378 if (index != --size)
379 System.arraycopy(data, index + 1, data, index, size - index);
380 // Aid for garbage collection by releasing this pointer.
381 data[size] = null;
382 return r;
383 }
384
385 /**
386 * Removes all elements from this List
387 */
388 public void clear()
389 {
390 if (size > 0)
391 {
392 modCount++;
393 // Allow for garbage collection.
394 Arrays.fill(data, 0, size, null);
395 size = 0;
396 }
397 }
398
399 /**
400 * Add each element in the supplied Collection to this List. It is undefined
401 * what happens if you modify the list while this is taking place; for
402 * example, if the collection contains this list. c can contain objects
403 * of any type, as well as null values.
404 *
405 * @param c a Collection containing elements to be added to this List
406 * @return true if the list was modified, in other words c is not empty
407 * @throws NullPointerException if c is null
408 */
409 public boolean addAll(Collection<? extends E> c)
410 {
411 return addAll(size, c);
412 }
413
414 /**
415 * Add all elements in the supplied collection, inserting them beginning
416 * at the specified index. c can contain objects of any type, as well
417 * as null values.
418 *
419 * @param index the index at which the elements will be inserted
420 * @param c the Collection containing the elements to be inserted
421 * @throws IndexOutOfBoundsException if index < 0 || index > 0
422 * @throws NullPointerException if c is null
423 */
424 public boolean addAll(int index, Collection<? extends E> c)
425 {
426 checkBoundInclusive(index);
427 Iterator<? extends E> itr = c.iterator();
428 int csize = c.size();
429
430 modCount++;
431 if (csize + size > data.length)
432 ensureCapacity(size + csize);
433 int end = index + csize;
434 if (size > 0 && index != size)
435 System.arraycopy(data, index, data, end, size - index);
436 size += csize;
437 for ( ; index < end; index++)
438 data[index] = itr.next();
439 return csize > 0;
440 }
441
442 /**
443 * Removes all elements in the half-open interval [fromIndex, toIndex).
444 * Does nothing when toIndex is equal to fromIndex.
445 *
446 * @param fromIndex the first index which will be removed
447 * @param toIndex one greater than the last index which will be removed
448 * @throws IndexOutOfBoundsException if fromIndex > toIndex
449 */
450 protected void removeRange(int fromIndex, int toIndex)
451 {
452 int change = toIndex - fromIndex;
453 if (change > 0)
454 {
455 modCount++;
456 System.arraycopy(data, toIndex, data, fromIndex, size - toIndex);
457 size -= change;
458 }
459 else if (change < 0)
460 throw new IndexOutOfBoundsException();
461 }
462
463 /**
464 * Checks that the index is in the range of possible elements (inclusive).
465 *
466 * @param index the index to check
467 * @throws IndexOutOfBoundsException if index > size
468 */
469 private void checkBoundInclusive(int index)
470 {
471 // Implementation note: we do not check for negative ranges here, since
472 // use of a negative index will cause an ArrayIndexOutOfBoundsException,
473 // a subclass of the required exception, with no effort on our part.
474 if (index > size)
475 raiseBoundsError(index);
476 }
477
478 /**
479 * Checks that the index is in the range of existing elements (exclusive).
480 *
481 * @param index the index to check
482 * @throws IndexOutOfBoundsException if index >= size
483 */
484 private void checkBoundExclusive(int index)
485 {
486 // Implementation note: we do not check for negative ranges here, since
487 // use of a negative index will cause an ArrayIndexOutOfBoundsException,
488 // a subclass of the required exception, with no effort on our part.
489 if (index >= size)
490 raiseBoundsError(index);
491 }
492
493 /**
494 * Raise the ArrayIndexOfOutBoundsException.
495 *
496 * @param index the index of the access
497 * @throws IndexOutOfBoundsException unconditionally
498 */
499 private void raiseBoundsError(int index)
500 {
501 // Implementaion note: put in a separate method to make the JITs job easier
502 // (separate common from uncommon code at method boundaries when trivial to
503 // do so).
504 throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
505 }
506
507
508 /**
509 * Remove from this list all elements contained in the given collection.
510 * This is not public, due to Sun's API, but this performs in linear
511 * time while the default behavior of AbstractList would be quadratic.
512 *
513 * @param c the collection to filter out
514 * @return true if this list changed
515 * @throws NullPointerException if c is null
516 */
517 boolean removeAllInternal(Collection<?> c)
518 {
519 int i;
520 int j;
521 for (i = 0; i < size; i++)
522 if (c.contains(data[i]))
523 break;
524 if (i == size)
525 return false;
526
527 modCount++;
528 for (j = i++; i < size; i++)
529 if (! c.contains(data[i]))
530 data[j++] = data[i];
531 size -= i - j;
532 return true;
533 }
534
535 /**
536 * Retain in this vector only the elements contained in the given collection.
537 * This is not public, due to Sun's API, but this performs in linear
538 * time while the default behavior of AbstractList would be quadratic.
539 *
540 * @param c the collection to filter by
541 * @return true if this vector changed
542 * @throws NullPointerException if c is null
543 * @since 1.2
544 */
545 boolean retainAllInternal(Collection<?> c)
546 {
547 int i;
548 int j;
549 for (i = 0; i < size; i++)
550 if (! c.contains(data[i]))
551 break;
552 if (i == size)
553 return false;
554
555 modCount++;
556 for (j = i++; i < size; i++)
557 if (c.contains(data[i]))
558 data[j++] = data[i];
559 size -= i - j;
560 return true;
561 }
562
563 /**
564 * Serializes this object to the given stream.
565 *
566 * @param s the stream to write to
567 * @throws IOException if the underlying stream fails
568 * @serialData the size field (int), the length of the backing array
569 * (int), followed by its elements (Objects) in proper order.
570 */
571 private void writeObject(ObjectOutputStream s) throws IOException
572 {
573 // The 'size' field.
574 s.defaultWriteObject();
575 // We serialize unused list entries to preserve capacity.
576 int len = data.length;
577 s.writeInt(len);
578 // it would be more efficient to just write "size" items,
579 // this need readObject read "size" items too.
580 for (int i = 0; i < size; i++)
581 s.writeObject(data[i]);
582 }
583
584 /**
585 * Deserializes this object from the given stream.
586 *
587 * @param s the stream to read from
588 * @throws ClassNotFoundException if the underlying stream fails
589 * @throws IOException if the underlying stream fails
590 * @serialData the size field (int), the length of the backing array
591 * (int), followed by its elements (Objects) in proper order.
592 */
593 private void readObject(ObjectInputStream s)
594 throws IOException, ClassNotFoundException
595 {
596 // the `size' field.
597 s.defaultReadObject();
598 int capacity = s.readInt();
599 data = (E[]) new Object[capacity];
600 for (int i = 0; i < size; i++)
601 data[i] = (E) s.readObject();
602 }
603 }