ViewVC Help
View File | Revision Log | Show Annotations | Download File | Root Listing
root/jsr166/jsr166/src/main/java/util/ArrayList.java
(Generate patch)

Comparing jsr166/src/main/java/util/ArrayList.java (file contents):
Revision 1.2 by dl, Fri Nov 25 13:34:29 2005 UTC vs.
Revision 1.19 by dl, Wed Apr 19 15:07:14 2006 UTC

# Line 1 | Line 1
1   /*
2 < * %W% %E%
2 > * @(#)ArrayList.java   1.56 06/03/14
3   *
4 < * Copyright 2005 Sun Microsystems, Inc. All rights reserved.
4 > * Copyright 2006 Sun Microsystems, Inc. All rights reserved.
5   * SUN PROPRIETARY/CONFIDENTIAL. Use is subject to license terms.
6   */
7  
8   package java.util;
9 – import java.util.*; // for javadoc (till 6280605 is fixed)
9  
10   /**
11   * Resizable-array implementation of the <tt>List</tt> interface.  Implements
# Line 72 | Line 71 | import java.util.*; // for javadoc (till
71   *
72   * @author  Josh Bloch
73   * @author  Neal Gafter
74 < * @version %I%, %G%
74 > * @version 1.56, 03/14/06
75   * @see     Collection
76   * @see     List
77   * @see     LinkedList
# Line 101 | Line 100 | public class ArrayList<E> extends Abstra
100      /**
101       * Constructs an empty list with the specified initial capacity.
102       *
103 <     * @param   initialCapacity   the initial capacity of the list
104 <     * @exception IllegalArgumentException if the specified initial capacity
105 <     *            is negative
103 >     * @param initialCapacity the initial capacity of the list
104 >     * @throws IllegalArgumentException if the specified initial capacity
105 >     *         is negative
106       */
107      public ArrayList(int initialCapacity) {
108          super();
# Line 123 | Line 122 | public class ArrayList<E> extends Abstra
122      /**
123       * Constructs a list containing the elements of the specified
124       * collection, in the order they are returned by the collection's
125 <     * iterator.  The <tt>ArrayList</tt> instance has an initial capacity of
127 <     * 110% the size of the specified collection.
125 >     * iterator.
126       *
127       * @param c the collection whose elements are to be placed into this list
128       * @throws NullPointerException if the specified collection is null
129       */
130      public ArrayList(Collection<? extends E> c) {
131 <        int size = c.size();
132 <        // 10% for growth
133 <        int cap = ((size/10)+1)*11;
134 <        if (cap > 0) {
135 <            Object[] a = new Object[cap];
138 <            a[size] = a[size+1] = UNALLOCATED;
139 <            Object[] b = c.toArray(a);
140 <            if (b[size] == null && b[size+1] == UNALLOCATED) {
141 <                b[size+1] = null;
142 <                elementData = b;
143 <                this.size = size;
144 <                return;
145 <            }
146 <        }
147 <        initFromConcurrentlyMutating(c);
131 >        elementData = c.toArray();
132 >        size = elementData.length;
133 >        // c.toArray might (incorrectly) not return Object[] (see 6260652)
134 >        if (elementData.getClass() != Object[].class)
135 >            elementData = Arrays.copyOf(elementData, size, Object[].class);
136      }
137 <    
137 >
138      private void initFromConcurrentlyMutating(Collection<? extends E> c) {
139          elementData = c.toArray();
140          size = elementData.length;
# Line 154 | Line 142 | public class ArrayList<E> extends Abstra
142          if (elementData.getClass() != Object[].class)
143              elementData = Arrays.copyOf(elementData, size, Object[].class);
144      }
145 <    
145 >
146      private final static Object UNALLOCATED = new Object();
147 <    
147 >
148      /**
149       * Trims the capacity of this <tt>ArrayList</tt> instance to be the
150       * list's current size.  An application can use this operation to minimize
# Line 175 | Line 163 | public class ArrayList<E> extends Abstra
163       * necessary, to ensure that it can hold at least the number of elements
164       * specified by the minimum capacity argument.
165       *
166 <     * @param   minCapacity   the desired minimum capacity
179 <     */
180 <    /**
181 <     * Increases the capacity of this <tt>ArrayList</tt> instance, if
182 <     * necessary, to ensure that it can hold at least the number of elements
183 <     * specified by the minimum capacity argument.
184 <     *
185 <     * @param   minCapacity   the desired minimum capacity
166 >     * @param minCapacity the desired minimum capacity
167       */
168      public void ensureCapacity(int minCapacity) {
169          modCount++;
# Line 191 | Line 172 | public class ArrayList<E> extends Abstra
172      }
173  
174      /**
175 <     * Increase the capacity of the array.
176 <     * @param   minCapacity   the desired minimum capacity
175 >     * Increases the capacity of the array.
176 >     *
177 >     * @param minCapacity the desired minimum capacity
178       */
179      private void growArray(int minCapacity) {
180 +        if (minCapacity < 0) // overflow
181 +            throw new OutOfMemoryError();
182          int oldCapacity = elementData.length;
183          // Double size if small; else grow by 50%
184 <        int newCapacity = ((oldCapacity < 64)?
185 <                           (oldCapacity * 2):
186 <                           ((oldCapacity * 3)/2 + 1));
184 >        int newCapacity = ((oldCapacity < 64) ?
185 >                           ((oldCapacity + 1) * 2) :
186 >                           ((oldCapacity / 2) * 3));
187 >        if (newCapacity < 0) // overflow
188 >            newCapacity = Integer.MAX_VALUE;
189          if (newCapacity < minCapacity)
190              newCapacity = minCapacity;
191          elementData = Arrays.copyOf(elementData, newCapacity);
# Line 348 | Line 334 | public class ArrayList<E> extends Abstra
334  
335      // Positional Access Operations
336  
337 <    /**
338 <     * Create and return an appropriate exception for indexing errors
337 >    /**
338 >     * Throws an appropriate exception for indexing errors.
339       */
340 <    private static IndexOutOfBoundsException rangeException(int i, int s) {
341 <        return new IndexOutOfBoundsException("Index: " + i + ", Size: " + s);
340 >    private static void indexOutOfBounds(int i, int s) {
341 >        throw new IndexOutOfBoundsException("Index: " + i + ", Size: " + s);
342      }
343  
358 –    // Positional Access Operations
359 –
344      /**
345       * Returns the element at the specified position in this list.
346       *
# Line 366 | Line 350 | public class ArrayList<E> extends Abstra
350       */
351      public E get(int index) {
352          if (index >= size)
353 <            throw rangeException(index, size);
354 <        return (E)elementData[index];
353 >            indexOutOfBounds(index, size);
354 >        return (E) elementData[index];
355      }
356  
357      /**
# Line 381 | Line 365 | public class ArrayList<E> extends Abstra
365       */
366      public E set(int index, E element) {
367          if (index >= size)
368 <             throw rangeException(index, size);
385 <
368 >            indexOutOfBounds(index, size);
369          E oldValue = (E) elementData[index];
370          elementData[index] = element;
371          return oldValue;
# Line 395 | Line 378 | public class ArrayList<E> extends Abstra
378       * @return <tt>true</tt> (as specified by {@link Collection#add})
379       */
380      public boolean add(E e) {
381 <        ++modCount;
382 <        int s = size++;
381 >        modCount++;
382 >        int s = size;
383          if (s >= elementData.length)
384              growArray(s + 1);
385          elementData[s] = e;
386 <        return true;
386 >        size = s + 1;
387 >        return true;
388      }
389  
390      /**
# Line 415 | Line 399 | public class ArrayList<E> extends Abstra
399      public void add(int index, E element) {
400          int s = size;
401          if (index > s || index < 0)
402 <            throw rangeException(index, s);
403 <        ++modCount;
420 <        size = s + 1;
402 >            indexOutOfBounds(index, s);
403 >        modCount++;
404          if (s >= elementData.length)
405              growArray(s + 1);
406 <        System.arraycopy(elementData, index, elementData, index + 1,
407 <                         s - index);
406 >        System.arraycopy(elementData, index,
407 >                         elementData, index + 1, s - index);
408          elementData[index] = element;
409 +        size = s + 1;
410      }
411  
412      /**
# Line 437 | Line 421 | public class ArrayList<E> extends Abstra
421      public E remove(int index) {
422          int s = size - 1;
423          if (index > s)
424 <            throw rangeException(index, size);
441 <        size = s;
424 >            indexOutOfBounds(index, size);
425          modCount++;
426 <        Object oldValue = elementData[index];
426 >        E oldValue = (E) elementData[index];
427          int numMoved = s - index;
428          if (numMoved > 0)
429 <            System.arraycopy(elementData, index+1, elementData, index,
430 <                             numMoved);
431 <        elementData[s] = null; // forget removed element
432 <        return (E)oldValue;
429 >            System.arraycopy(elementData, index + 1,
430 >                             elementData, index, numMoved);
431 >        elementData[s] = null;
432 >        size = s;
433 >        return oldValue;
434      }
435  
436      /**
# Line 545 | Line 529 | public class ArrayList<E> extends Abstra
529       */
530      public boolean addAll(int index, Collection<? extends E> c) {
531          if (index > size || index < 0)
532 <            throw new IndexOutOfBoundsException(
549 <                "Index: " + index + ", Size: " + size);
532 >            indexOutOfBounds(index, size);
533  
534          Object[] a = c.toArray();
535          int numNew = a.length;
# Line 608 | Line 591 | public class ArrayList<E> extends Abstra
591          for (int i=0; i<size; i++)
592              s.writeObject(elementData[i]);
593  
594 <        if (modCount != expectedModCount) {
594 >        if (expectedModCount != modCount) {
595              throw new ConcurrentModificationException();
596          }
597  
# Line 631 | Line 614 | public class ArrayList<E> extends Abstra
614          for (int i=0; i<size; i++)
615              a[i] = s.readObject();
616      }
634 –
635 –
636 –    /**
637 –     * Returns a list-iterator of the elements in this list (in proper
638 –     * sequence), starting at the specified position in the list.
639 –     * Obeys the general contract of <tt>List.listIterator(int)</tt>.<p>
640 –     *
641 –     * The list-iterator is <i>fail-fast</i>: if the list is structurally
642 –     * modified at any time after the Iterator is created, in any way except
643 –     * through the list-iterator's own <tt>remove</tt> or <tt>add</tt>
644 –     * methods, the list-iterator will throw a
645 –     * <tt>ConcurrentModificationException</tt>.  Thus, in the face of
646 –     * concurrent modification, the iterator fails quickly and cleanly, rather
647 –     * than risking arbitrary, non-deterministic behavior at an undetermined
648 –     * time in the future.
649 –     *
650 –     * @param index index of the first element to be returned from the
651 –     *              list-iterator (by a call to <tt>next</tt>)
652 –     * @return a ListIterator of the elements in this list (in proper
653 –     *         sequence), starting at the specified position in the list
654 –     * @throws IndexOutOfBoundsException {@inheritDoc}
655 –     * @see List#listIterator(int)
656 –     */
657 –    public ListIterator<E> listIterator(int index) {
658 –        if (index < 0 || index > size)
659 –            throw new IndexOutOfBoundsException("Index: "+index);
660 –        return new ArrayListIterator(index);
661 –    }
662 –
663 –    /**
664 –     * Returns an iterator over the elements in this list in proper sequence.
665 –     *
666 –     * @return an iterator over the elements in this list in proper sequence
667 –     */
668 –    public Iterator<E> iterator() {
669 –        return new ArrayListIterator(0);
670 –    }
671 –
672 –    /**
673 –     * A streamlined version of AbstractList.Itr
674 –     */
675 –    final class ArrayListIterator implements ListIterator<E> {
676 –        int cursor;           // index of next element to return;
677 –        int lastRet;          // index of last element, or -1 if no such
678 –        int expectedModCount; // to check for CME
679 –
680 –        ArrayListIterator(int index) {
681 –            cursor = index;
682 –            lastRet = -1;
683 –            expectedModCount = modCount;
684 –        }
685 –
686 –        public boolean hasNext() {
687 –            return cursor < size;
688 –        }
689 –
690 –        public boolean hasPrevious() {
691 –            return cursor > 0;
692 –        }
693 –
694 –        public int nextIndex() {
695 –            return cursor;
696 –        }
697 –
698 –        public int previousIndex() {
699 –            return cursor - 1;
700 –        }
701 –
702 –        public E next() {
703 –            if (expectedModCount == modCount) {
704 –                int i = cursor;
705 –                if (i < size) {
706 –                    try {
707 –                        E e = (E)elementData[i];
708 –                        lastRet = i;
709 –                        cursor = i + 1;
710 –                        return e;
711 –                    } catch (IndexOutOfBoundsException fallthrough) {
712 –                    }
713 –                }
714 –            }
715 –            // Prefer reporting CME if applicable on failures
716 –            if (expectedModCount == modCount)
717 –                throw new NoSuchElementException();
718 –            throw new ConcurrentModificationException();
719 –        }
720 –
721 –        public E previous() {
722 –            if (expectedModCount == modCount) {
723 –                int i = cursor - 1;
724 –                if (i < size) {
725 –                    try {
726 –                        E e = (E)elementData[i];
727 –                        lastRet = i;
728 –                        cursor = i;
729 –                        return e;
730 –                    } catch (IndexOutOfBoundsException fallthrough) {
731 –                    }
732 –                }
733 –            }
734 –            if (expectedModCount == modCount)
735 –                throw new NoSuchElementException();
736 –            throw new ConcurrentModificationException();
737 –        }
738 –
739 –        public void remove() {
740 –            if (lastRet < 0)
741 –                throw new IllegalStateException();
742 –            if (modCount != expectedModCount)
743 –                throw new ConcurrentModificationException();
744 –            ArrayList.this.remove(lastRet);
745 –            if (lastRet < cursor)
746 –                cursor--;
747 –            lastRet = -1;
748 –            expectedModCount = modCount;
749 –        }
750 –
751 –        public void set(E e) {
752 –            if (lastRet < 0)
753 –                throw new IllegalStateException();
754 –            if (modCount != expectedModCount)
755 –                throw new ConcurrentModificationException();
756 –            ArrayList.this.set(lastRet, e);
757 –            expectedModCount = modCount;
758 –        }
759 –
760 –        public void add(E e) {
761 –            if (modCount != expectedModCount)
762 –                throw new ConcurrentModificationException();
763 –            ArrayList.this.add(cursor++, e);
764 –            lastRet = -1;
765 –            expectedModCount = modCount;
766 –        }
767 –    }
768 –
617   }

Diff Legend

– Removed lines
+ Added lines
< Changed lines
> Changed lines