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 &gt; 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 &lt; 0 || index &gt;= 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 &lt; 0 || index &gt;= 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 &lt; 0 || index &gt; 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 &lt; 0 || index &gt;= 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 &lt; 0 || index &gt; 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 &gt; 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 &gt; 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 &gt;= 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    }