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
89 * Compatible with JDK 1.2
91 private static final long serialVersionUID = 8683452581122892189L;
94 * The default capacity for new ArrayLists.
96 private static final int DEFAULT_CAPACITY = 10;
99 * The number of elements in this list.
100 * @serial the list size
105 * Where the data is stored.
107 //private transient E[] data;
108 private transient Object[] data;
111 * Construct a new ArrayList with the supplied initial capacity.
113 * @param capacity initial capacity of this ArrayList
114 * @throws IllegalArgumentException if capacity is negative
116 public ArrayList(int capacity)
118 // Must explicitly check, to get correct exception.
120 throw new Error("Illegal Argument Exception")/*IllegalArgumentException()*/;
121 data = (Object/*E*/[]) new Object[capacity];
125 * Construct a new ArrayList with the default capacity (16).
129 this(DEFAULT_CAPACITY);
133 * Construct a new ArrayList, and initialize it with the elements
134 * in the supplied Collection. The initial capacity is 110% of the
137 * @param c the collection whose elements will initialize this list
138 * @throws NullPointerException if c is null
140 /*public ArrayList(Collection<? extends E> c)
142 this((int) (c.size() * 1.1f));
147 * Trims the capacity of this List to be equal to its size;
150 public void trimToSize()
152 // Not a structural change from the perspective of iterators on this list,
153 // so don't update modCount.
154 if (size != data.length)
156 Object/*E*/[] newData = /*(ObjectE[])*/ new Object[size];
157 System.arraycopy(data, 0, newData, 0, size);
163 * Guarantees that this list will have at least enough capacity to
164 * hold minCapacity elements. This implementation will grow the list to
165 * max(current * 2, minCapacity) if (minCapacity > current). The JCL says
166 * explictly that "this method increases its capacity to minCap", while
167 * the JDK 1.3 online docs specify that the list will grow to at least the
170 * @param minCapacity the minimum guaranteed capacity
172 public void ensureCapacity(int minCapacity)
174 int current = data.length;
176 if (minCapacity > current)
178 Object/*E*/[] newData = /*(E[])*/ new Object[Math.max(current * 2, minCapacity)];
179 System.arraycopy(data, 0, newData, 0, size);
185 * Returns the number of elements in this list.
187 * @return the list size
195 * Checks if the list is empty.
197 * @return true if there are no elements
199 public boolean isEmpty()
205 * Returns true iff element is in this ArrayList.
207 * @param e the element whose inclusion in the List is being tested
208 * @return true if the list contains e
210 public boolean contains(Object e)
212 return indexOf(e) != -1;
216 * Returns the lowest index at which element appears in this List, or
217 * -1 if it does not appear.
219 * @param e the element whose inclusion in the List is being tested
220 * @return the index where e was found
222 public int indexOf(Object e)
224 for (int i = 0; i < size; i++)
225 if (equals(e, data[i]))
231 * Returns the highest index at which element appears in this List, or
232 * -1 if it does not appear.
234 * @param e the element whose inclusion in the List is being tested
235 * @return the index where e was found
237 public int lastIndexOf(Object e)
239 for (int i = size - 1; i >= 0; i--)
240 if (equals(e, data[i]))
246 * Creates a shallow copy of this ArrayList (elements are not cloned).
248 * @return the cloned object
250 public Object clone()
252 ArrayList/*<E>*/ clone = null;
255 //clone = (ArrayList<E>) super.clone();
256 clone = new ArrayList();
257 clone.data = /*(E[])*/ data.clone();
259 /*catch (CloneNotSupportedException e)
261 // Impossible to get here.
267 * Returns an Object array containing all of the elements in this ArrayList.
268 * The array is independent of this list.
270 * @return an array representation of this list
272 public Object[] toArray()
274 Object/*E*/[] array = /*(E[])*/ new Object[size];
275 System.arraycopy(data, 0, array, 0, size);
280 * Returns an Array whose component type is the runtime component type of
281 * the passed-in Array. The returned Array is populated with all of the
282 * elements in this ArrayList. If the passed-in Array is not large enough
283 * to store all of the elements in this List, a new Array will be created
284 * and returned; if the passed-in Array is <i>larger</i> than the size
285 * of this List, then size() index will be set to null.
287 * @param a the passed-in Array
288 * @return an array representation of this list
289 * @throws ArrayStoreException if the runtime type of a does not allow
290 * an element in this list
291 * @throws NullPointerException if a is null
293 /*public <T> T[] toArray(T[] a)
296 a = (T[]) Array.newInstance(a.getClass().getComponentType(), size);
297 else if (a.length > size)
299 System.arraycopy(data, 0, a, 0, size);
304 * Retrieves the element at the user-supplied index.
306 * @param index the index of the element we are fetching
307 * @throws IndexOutOfBoundsException if index < 0 || index >= size()
309 public Object/*E*/ get(int index)
311 checkBoundExclusive(index);
316 * Sets the element at the specified index. The new element, e,
317 * can be an object of any type or null.
319 * @param index the index at which the element is being set
320 * @param e the element to be set
321 * @return the element previously at the specified index
322 * @throws IndexOutOfBoundsException if index < 0 || index >= 0
324 public Object/*E*/ set(int index, Object/*E*/ e)
326 checkBoundExclusive(index);
327 Object/*E*/ result = data[index];
333 * Appends the supplied element to the end of this list.
334 * The element, e, can be an object of any type or null.
336 * @param e the element to be appended to this list
337 * @return true, the add will always succeed
339 public boolean add(Object/*E*/ e)
342 if (size == data.length)
343 ensureCapacity(size + 1);
349 * Adds the supplied element at the specified index, shifting all
350 * elements currently at that index or higher one to the right.
351 * The element, e, can be an object of any type or null.
353 * @param index the index at which the element is being added
354 * @param e the item being added
355 * @throws IndexOutOfBoundsException if index < 0 || index > size()
357 public void add(int index, Object/*E*/ e)
359 checkBoundInclusive(index);
361 if (size == data.length)
362 ensureCapacity(size + 1);
364 System.arraycopy(data, index, data, index + 1, size - index);
370 * Removes the element at the user-supplied index.
372 * @param index the index of the element to be removed
373 * @return the removed Object
374 * @throws IndexOutOfBoundsException if index < 0 || index >= size()
376 public Object/*E*/ remove(int index)
378 checkBoundExclusive(index);
379 Object/*E*/ r = data[index];
382 System.arraycopy(data, index + 1, data, index, size - index);
383 // Aid for garbage collection by releasing this pointer.
389 * Removes all elements from this List
396 // Allow for garbage collection.
397 Arrays.fill(data, 0, size, null);
403 * Add each element in the supplied Collection to this List. It is undefined
404 * what happens if you modify the list while this is taking place; for
405 * example, if the collection contains this list. c can contain objects
406 * of any type, as well as null values.
408 * @param c a Collection containing elements to be added to this List
409 * @return true if the list was modified, in other words c is not empty
410 * @throws NullPointerException if c is null
412 /*public boolean addAll(Collection<? extends E> c)
414 return addAll(size, c);
418 * Add all elements in the supplied collection, inserting them beginning
419 * at the specified index. c can contain objects of any type, as well
422 * @param index the index at which the elements will be inserted
423 * @param c the Collection containing the elements to be inserted
424 * @throws IndexOutOfBoundsException if index < 0 || index > 0
425 * @throws NullPointerException if c is null
427 /*public boolean addAll(int index, Collection<? extends E> c)
429 checkBoundInclusive(index);
430 Iterator<? extends E> itr = c.iterator();
431 int csize = c.size();
434 if (csize + size > data.length)
435 ensureCapacity(size + csize);
436 int end = index + csize;
437 if (size > 0 && index != size)
438 System.arraycopy(data, index, data, end, size - index);
440 for ( ; index < end; index++)
441 data[index] = itr.next();
446 * Removes all elements in the half-open interval [fromIndex, toIndex).
447 * Does nothing when toIndex is equal to fromIndex.
449 * @param fromIndex the first index which will be removed
450 * @param toIndex one greater than the last index which will be removed
451 * @throws IndexOutOfBoundsException if fromIndex > toIndex
453 protected void removeRange(int fromIndex, int toIndex)
455 int change = toIndex - fromIndex;
459 System.arraycopy(data, toIndex, data, fromIndex, size - toIndex);
463 throw new Error("Index Out Of Bounds Exception")/*IndexOutOfBoundsException()*/;
467 * Checks that the index is in the range of possible elements (inclusive).
469 * @param index the index to check
470 * @throws IndexOutOfBoundsException if index > size
472 private void checkBoundInclusive(int index)
474 // Implementation note: we do not check for negative ranges here, since
475 // use of a negative index will cause an ArrayIndexOutOfBoundsException,
476 // a subclass of the required exception, with no effort on our part.
478 raiseBoundsError(index);
482 * Checks that the index is in the range of existing elements (exclusive).
484 * @param index the index to check
485 * @throws IndexOutOfBoundsException if index >= size
487 private void checkBoundExclusive(int index)
489 // Implementation note: we do not check for negative ranges here, since
490 // use of a negative index will cause an ArrayIndexOutOfBoundsException,
491 // a subclass of the required exception, with no effort on our part.
493 raiseBoundsError(index);
497 * Raise the ArrayIndexOfOutBoundsException.
499 * @param index the index of the access
500 * @throws IndexOutOfBoundsException unconditionally
502 private void raiseBoundsError(int index)
504 // Implementaion note: put in a separate method to make the JITs job easier
505 // (separate common from uncommon code at method boundaries when trivial to
507 throw new Error/*IndexOutOfBoundsException*/("IndexOutOfBoundsException Index: " + index + ", Size: " + size);
512 * Remove from this list all elements contained in the given collection.
513 * This is not public, due to Sun's API, but this performs in linear
514 * time while the default behavior of AbstractList would be quadratic.
516 * @param c the collection to filter out
517 * @return true if this list changed
518 * @throws NullPointerException if c is null
520 /*boolean removeAllInternal(Collection<?> c)
524 for (i = 0; i < size; i++)
525 if (c.contains(data[i]))
531 for (j = i++; i < size; i++)
532 if (! c.contains(data[i]))
539 * Retain in this vector only the elements contained in the given collection.
540 * This is not public, due to Sun's API, but this performs in linear
541 * time while the default behavior of AbstractList would be quadratic.
543 * @param c the collection to filter by
544 * @return true if this vector changed
545 * @throws NullPointerException if c is null
548 /*boolean retainAllInternal(Collection<?> c)
552 for (i = 0; i < size; i++)
553 if (! c.contains(data[i]))
559 for (j = i++; i < size; i++)
560 if (c.contains(data[i]))
567 * Serializes this object to the given stream.
569 * @param s the stream to write to
570 * @throws IOException if the underlying stream fails
571 * @serialData the size field (int), the length of the backing array
572 * (int), followed by its elements (Objects) in proper order.
574 /*private void writeObject(ObjectOutputStream s) throws IOException
577 s.defaultWriteObject();
578 // We serialize unused list entries to preserve capacity.
579 int len = data.length;
581 // it would be more efficient to just write "size" items,
582 // this need readObject read "size" items too.
583 for (int i = 0; i < size; i++)
584 s.writeObject(data[i]);
588 * Deserializes this object from the given stream.
590 * @param s the stream to read from
591 * @throws ClassNotFoundException if the underlying stream fails
592 * @throws IOException if the underlying stream fails
593 * @serialData the size field (int), the length of the backing array
594 * (int), followed by its elements (Objects) in proper order.
596 /*private void readObject(ObjectInputStream s)
597 throws IOException, ClassNotFoundException
600 s.defaultReadObject();
601 int capacity = s.readInt();
602 data = (E[]) new Object[capacity];
603 for (int i = 0; i < size; i++)
604 data[i] = (E) s.readObject();