1 /* ArrayList.java -- JDK1.2's answer to Vector; this is an array-backed
2 implementation of the List interface
3 Copyright (C) 1998, 1999, 2000, 2001, 2004, 2005 Free Software Foundation, Inc.
5 This file is part of GNU Classpath.
7 GNU Classpath is free software; you can redistribute it and/or modify
8 it under the terms of the GNU General Public License as published by
9 the Free Software Foundation; either version 2, or (at your option)
12 GNU Classpath is distributed in the hope that it will be useful, but
13 WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
15 General Public License for more details.
17 You should have received a copy of the GNU General Public License
18 along with GNU Classpath; see the file COPYING. If not, write to the
19 Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
22 Linking this library statically or dynamically with other modules is
23 making a combined work based on this library. Thus, the terms and
24 conditions of the GNU General Public License cover the whole
27 As a special exception, the copyright holders of this library give you
28 permission to link this library with independent modules to produce an
29 executable, regardless of the license terms of these independent
30 modules, and to copy and distribute the resulting executable under
31 terms of your choice, provided that you also meet, for each linked
32 independent module, the terms and conditions of the license of that
33 module. An independent module is a module which is not derived from
34 or based on this library. If you modify this library, you may extend
35 this exception to your version of the library, but you are not
36 obligated to do so. If you do not wish to do so, delete this
37 exception statement from your version. */
42 /*import java.io.IOException;
43 import java.io.ObjectInputStream;
44 import java.io.ObjectOutputStream;
45 import java.io.Serializable;
46 import java.lang.reflect.Array;
49 * An array-backed implementation of the List interface. This implements
50 * all optional list operations, and permits null elements, so that it is
51 * better than Vector, which it replaces. Random access is roughly constant
52 * time, and iteration is roughly linear time, so it is nice and fast, with
53 * less overhead than a LinkedList.
56 * Each list has a capacity, and as the array reaches that capacity it
57 * is automatically transferred to a larger array. You also have access to
58 * ensureCapacity and trimToSize to control the backing array's size, avoiding
59 * reallocation or wasted memory.
62 * ArrayList is not synchronized, so if you need multi-threaded access,
64 * <code>List l = Collections.synchronizedList(new ArrayList(...));</code>
67 * The iterators are <i>fail-fast</i>, meaning that any structural
68 * modification, except for <code>remove()</code> called on the iterator
69 * itself, cause the iterator to throw a
70 * {@link ConcurrentModificationException} rather than exhibit
71 * non-deterministic behavior.
73 * @author Jon A. Zeppieri
74 * @author Bryce McKinlay
75 * @author Eric Blake (ebb9@email.byu.edu)
80 * @see Collections#synchronizedList(List)
82 * @status updated to 1.4
84 //public class ArrayList<E> extends AbstractList<E>
85 // implements List<E>, RandomAccess, Cloneable, Serializable
86 public class ArrayList implements List, Cloneable, Serializable
88 protected transient int modCount;
90 * Compatible with JDK 1.2
92 private static final long serialVersionUID = 8683452581122892189L;
95 * The default capacity for new ArrayLists.
97 private static final int DEFAULT_CAPACITY = 10;
100 * The number of elements in this list.
101 * @serial the list size
106 * Where the data is stored.
108 //private transient E[] data;
109 private transient Object[] data;
112 * Construct a new ArrayList with the supplied initial capacity.
114 * @param capacity initial capacity of this ArrayList
115 * @throws IllegalArgumentException if capacity is negative
117 public ArrayList(int capacity)
119 // Must explicitly check, to get correct exception.
121 throw new Error("Illegal Argument Exception")/*IllegalArgumentException()*/;
122 data = (Object/*E*/[]) new Object[capacity];
126 * Construct a new ArrayList with the default capacity (16).
130 this(DEFAULT_CAPACITY);
134 * Construct a new ArrayList, and initialize it with the elements
135 * in the supplied Collection. The initial capacity is 110% of the
138 * @param c the collection whose elements will initialize this list
139 * @throws NullPointerException if c is null
141 public ArrayList(Collection/*<? extends E>*/ c)
143 this((int) (c.size() * 1.1f));
148 * Trims the capacity of this List to be equal to its size;
151 public void trimToSize()
153 // Not a structural change from the perspective of iterators on this list,
154 // so don't update modCount.
155 if (size != data.length)
157 Object/*E*/[] newData = /*(ObjectE[])*/ new Object[size];
158 System.arraycopy(data, 0, newData, 0, size);
164 * Guarantees that this list will have at least enough capacity to
165 * hold minCapacity elements. This implementation will grow the list to
166 * max(current * 2, minCapacity) if (minCapacity > current). The JCL says
167 * explictly that "this method increases its capacity to minCap", while
168 * the JDK 1.3 online docs specify that the list will grow to at least the
171 * @param minCapacity the minimum guaranteed capacity
173 public void ensureCapacity(int minCapacity)
175 int current = data.length;
177 if (minCapacity > current)
179 Object/*E*/[] newData = /*(E[])*/ new Object[Math.max(current * 2, minCapacity)];
180 System.arraycopy(data, 0, newData, 0, size);
186 * Returns the number of elements in this list.
188 * @return the list size
196 * Checks if the list is empty.
198 * @return true if there are no elements
200 public boolean isEmpty()
206 * Returns true iff element is in this ArrayList.
208 * @param e the element whose inclusion in the List is being tested
209 * @return true if the list contains e
211 public boolean contains(Object e)
213 return indexOf(e) != -1;
217 * Returns the lowest index at which element appears in this List, or
218 * -1 if it does not appear.
220 * @param e the element whose inclusion in the List is being tested
221 * @return the index where e was found
223 public int indexOf(Object e)
225 for (int i = 0; i < size; i++)
226 if (equals(e, data[i]))
232 * Returns the highest index at which element appears in this List, or
233 * -1 if it does not appear.
235 * @param e the element whose inclusion in the List is being tested
236 * @return the index where e was found
238 public int lastIndexOf(Object e)
240 for (int i = size - 1; i >= 0; i--)
241 if (equals(e, data[i]))
246 boolean equals(Object o1, Object o2)
248 return o1 == null ? o2 == null : o1.equals(o2);
252 * Creates a shallow copy of this ArrayList (elements are not cloned).
254 * @return the cloned object
256 /*public Object clone()
258 ArrayList<E> clone = null;
261 clone = (ArrayList<E>) super.clone();
262 //clone = new ArrayList();
263 clone.data = (E[]) data.clone();
265 catch (CloneNotSupportedException e)
267 // Impossible to get here.
273 * Returns an Object array containing all of the elements in this ArrayList.
274 * The array is independent of this list.
276 * @return an array representation of this list
278 public Object[] toArray()
280 Object/*E*/[] array = /*(E[])*/ new Object[size];
281 System.arraycopy(data, 0, array, 0, size);
286 * Returns an Array whose component type is the runtime component type of
287 * the passed-in Array. The returned Array is populated with all of the
288 * elements in this ArrayList. If the passed-in Array is not large enough
289 * to store all of the elements in this List, a new Array will be created
290 * and returned; if the passed-in Array is <i>larger</i> than the size
291 * of this List, then size() index will be set to null.
293 * @param a the passed-in Array
294 * @return an array representation of this list
295 * @throws ArrayStoreException if the runtime type of a does not allow
296 * an element in this list
297 * @throws NullPointerException if a is null
299 /*public <T> T[] toArray(T[] a)
302 a = (T[]) Array.newInstance(a.getClass().getComponentType(), size);
303 else if (a.length > size)
305 System.arraycopy(data, 0, a, 0, size);
310 * Retrieves the element at the user-supplied index.
312 * @param index the index of the element we are fetching
313 * @throws IndexOutOfBoundsException if index < 0 || index >= size()
315 public Object/*E*/ get(int index)
317 checkBoundExclusive(index);
322 * Sets the element at the specified index. The new element, e,
323 * can be an object of any type or null.
325 * @param index the index at which the element is being set
326 * @param e the element to be set
327 * @return the element previously at the specified index
328 * @throws IndexOutOfBoundsException if index < 0 || index >= 0
330 public Object/*E*/ set(int index, Object/*E*/ e)
332 checkBoundExclusive(index);
333 Object/*E*/ result = data[index];
339 * Appends the supplied element to the end of this list.
340 * The element, e, can be an object of any type or null.
342 * @param e the element to be appended to this list
343 * @return true, the add will always succeed
345 public boolean add(Object/*E*/ e)
348 if (size == data.length)
349 ensureCapacity(size + 1);
355 * Adds the supplied element at the specified index, shifting all
356 * elements currently at that index or higher one to the right.
357 * The element, e, can be an object of any type or null.
359 * @param index the index at which the element is being added
360 * @param e the item being added
361 * @throws IndexOutOfBoundsException if index < 0 || index > size()
363 public void add(int index, Object/*E*/ e)
365 checkBoundInclusive(index);
367 if (size == data.length)
368 ensureCapacity(size + 1);
370 System.arraycopy(data, index, data, index + 1, size - index);
376 * Removes the element at the user-supplied index.
378 * @param index the index of the element to be removed
379 * @return the removed Object
380 * @throws IndexOutOfBoundsException if index < 0 || index >= size()
382 public Object/*E*/ remove(int index)
384 checkBoundExclusive(index);
385 Object/*E*/ r = data[index];
388 System.arraycopy(data, index + 1, data, index, size - index);
389 // Aid for garbage collection by releasing this pointer.
395 * Removes all elements from this List
402 // Allow for garbage collection.
403 //Arrays.fill(data, 0, size, null);
404 for(int i = 0; i < size; i++) {
412 * Add each element in the supplied Collection to this List. It is undefined
413 * what happens if you modify the list while this is taking place; for
414 * example, if the collection contains this list. c can contain objects
415 * of any type, as well as null values.
417 * @param c a Collection containing elements to be added to this List
418 * @return true if the list was modified, in other words c is not empty
419 * @throws NullPointerException if c is null
421 /*public boolean addAll(Collection<? extends E> c)
423 return addAll(size, c);
427 * Add all elements in the supplied collection, inserting them beginning
428 * at the specified index. c can contain objects of any type, as well
431 * @param index the index at which the elements will be inserted
432 * @param c the Collection containing the elements to be inserted
433 * @throws IndexOutOfBoundsException if index < 0 || index > 0
434 * @throws NullPointerException if c is null
436 /*public boolean addAll(int index, Collection<? extends E> c)
438 checkBoundInclusive(index);
439 Iterator<? extends E> itr = c.iterator();
440 int csize = c.size();
443 if (csize + size > data.length)
444 ensureCapacity(size + csize);
445 int end = index + csize;
446 if (size > 0 && index != size)
447 System.arraycopy(data, index, data, end, size - index);
449 for ( ; index < end; index++)
450 data[index] = itr.next();
455 * Removes all elements in the half-open interval [fromIndex, toIndex).
456 * Does nothing when toIndex is equal to fromIndex.
458 * @param fromIndex the first index which will be removed
459 * @param toIndex one greater than the last index which will be removed
460 * @throws IndexOutOfBoundsException if fromIndex > toIndex
462 protected void removeRange(int fromIndex, int toIndex)
464 int change = toIndex - fromIndex;
468 System.arraycopy(data, toIndex, data, fromIndex, size - toIndex);
472 throw new Error("Index Out Of Bounds Exception")/*IndexOutOfBoundsException()*/;
476 * Checks that the index is in the range of possible elements (inclusive).
478 * @param index the index to check
479 * @throws IndexOutOfBoundsException if index > size
481 private void checkBoundInclusive(int index)
483 // Implementation note: we do not check for negative ranges here, since
484 // use of a negative index will cause an ArrayIndexOutOfBoundsException,
485 // a subclass of the required exception, with no effort on our part.
487 raiseBoundsError(index);
491 * Checks that the index is in the range of existing elements (exclusive).
493 * @param index the index to check
494 * @throws IndexOutOfBoundsException if index >= size
496 private void checkBoundExclusive(int index)
498 // Implementation note: we do not check for negative ranges here, since
499 // use of a negative index will cause an ArrayIndexOutOfBoundsException,
500 // a subclass of the required exception, with no effort on our part.
502 raiseBoundsError(index);
506 * Raise the ArrayIndexOfOutBoundsException.
508 * @param index the index of the access
509 * @throws IndexOutOfBoundsException unconditionally
511 private void raiseBoundsError(int index)
513 // Implementaion note: put in a separate method to make the JITs job easier
514 // (separate common from uncommon code at method boundaries when trivial to
516 throw new Error/*IndexOutOfBoundsException*/("IndexOutOfBoundsException Index: " + index + ", Size: " + size);
521 * Remove from this list all elements contained in the given collection.
522 * This is not public, due to Sun's API, but this performs in linear
523 * time while the default behavior of AbstractList would be quadratic.
525 * @param c the collection to filter out
526 * @return true if this list changed
527 * @throws NullPointerException if c is null
529 /*boolean removeAllInternal(Collection<?> c)
533 for (i = 0; i < size; i++)
534 if (c.contains(data[i]))
540 for (j = i++; i < size; i++)
541 if (! c.contains(data[i]))
548 * Retain in this vector only the elements contained in the given collection.
549 * This is not public, due to Sun's API, but this performs in linear
550 * time while the default behavior of AbstractList would be quadratic.
552 * @param c the collection to filter by
553 * @return true if this vector changed
554 * @throws NullPointerException if c is null
557 /*boolean retainAllInternal(Collection<?> c)
561 for (i = 0; i < size; i++)
562 if (! c.contains(data[i]))
568 for (j = i++; i < size; i++)
569 if (c.contains(data[i]))
576 * Serializes this object to the given stream.
578 * @param s the stream to write to
579 * @throws IOException if the underlying stream fails
580 * @serialData the size field (int), the length of the backing array
581 * (int), followed by its elements (Objects) in proper order.
583 /*private void writeObject(ObjectOutputStream s) throws IOException
586 s.defaultWriteObject();
587 // We serialize unused list entries to preserve capacity.
588 int len = data.length;
590 // it would be more efficient to just write "size" items,
591 // this need readObject read "size" items too.
592 for (int i = 0; i < size; i++)
593 s.writeObject(data[i]);
597 * Deserializes this object from the given stream.
599 * @param s the stream to read from
600 * @throws ClassNotFoundException if the underlying stream fails
601 * @throws IOException if the underlying stream fails
602 * @serialData the size field (int), the length of the backing array
603 * (int), followed by its elements (Objects) in proper order.
605 /*private void readObject(ObjectInputStream s)
606 throws IOException, ClassNotFoundException
609 s.defaultReadObject();
610 int capacity = s.readInt();
611 data = (E[]) new Object[capacity];
612 for (int i = 0; i < size; i++)
613 data[i] = (E) s.readObject();
616 public ArrayListIterator iterator()
618 // Bah, Sun's implementation forbids using listIterator(0).
619 return new ArrayListIterator(this);