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.1 by dl, Fri Nov 25 13:27:05 2005 UTC vs.
Revision 1.23 by jsr166, Sun Jan 7 07:38:27 2007 UTC

# Line 1 | Line 1
1   /*
2   * %W% %E%
3   *
4 < * Copyright 2005 Sun Microsystems, Inc. All rights reserved.
4 > * Copyright 2007 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 67 | Line 66 | import java.util.*; // for javadoc (till
66   * should be used only to detect bugs.</i><p>
67   *
68   * This class is a member of the
69 < * <a href="{@docRoot}/../guide/collections/index.html">
69 > * <a href="{@docRoot}/../technotes/guides/collections/index.html">
70   * Java Collections Framework</a>.
71   *
72   * @author  Josh Bloch
# 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.  
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 <        Object[] a = c.toArray();
132 <        // If c.toArray incorrectly doesn't return Object[], copy it.
133 <        if (a.getClass() != Object[].class)
134 <            a = Arrays.copyOf(a, a.length, Object[].class);
135 <        elementData = a;
137 <        size = a.length;
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  
138      /**
# Line 155 | Line 153 | public class ArrayList<E> extends Abstra
153       * necessary, to ensure that it can hold at least the number of elements
154       * specified by the minimum capacity argument.
155       *
156 <     * @param   minCapacity   the desired minimum capacity
159 <     */
160 <    /**
161 <     * Increases the capacity of this <tt>ArrayList</tt> instance, if
162 <     * necessary, to ensure that it can hold at least the number of elements
163 <     * specified by the minimum capacity argument.
164 <     *
165 <     * @param   minCapacity   the desired minimum capacity
156 >     * @param minCapacity the desired minimum capacity
157       */
158      public void ensureCapacity(int minCapacity) {
159          modCount++;
# Line 171 | Line 162 | public class ArrayList<E> extends Abstra
162      }
163  
164      /**
165 <     * Increase the capacity of the array.
166 <     * @param   minCapacity   the desired minimum capacity
165 >     * Increases the capacity of the array.
166 >     *
167 >     * @param minCapacity the desired minimum capacity
168       */
169      private void growArray(int minCapacity) {
170 +        if (minCapacity < 0) // overflow
171 +            throw new OutOfMemoryError();
172          int oldCapacity = elementData.length;
173          // Double size if small; else grow by 50%
174 <        int newCapacity = ((oldCapacity < 64)?
175 <                           (oldCapacity * 2):
176 <                           ((oldCapacity * 3)/2 + 1));
174 >        int newCapacity = ((oldCapacity < 64) ?
175 >                           ((oldCapacity + 1) * 2) :
176 >                           ((oldCapacity / 2) * 3));
177 >        if (newCapacity < 0) // overflow
178 >            newCapacity = Integer.MAX_VALUE;
179          if (newCapacity < minCapacity)
180              newCapacity = minCapacity;
181          elementData = Arrays.copyOf(elementData, newCapacity);
# Line 328 | Line 324 | public class ArrayList<E> extends Abstra
324  
325      // Positional Access Operations
326  
327 <    /**
328 <     * Create and return an appropriate exception for indexing errors
327 >    /**
328 >     * Throws an appropriate exception for indexing errors.
329       */
330 <    private static IndexOutOfBoundsException rangeException(int i, int s) {
331 <        return new IndexOutOfBoundsException("Index: " + i + ", Size: " + s);
330 >    private static void indexOutOfBounds(int i, int s) {
331 >        throw new IndexOutOfBoundsException("Index: " + i + ", Size: " + s);
332      }
333  
338 –    // Positional Access Operations
339 –
334      /**
335       * Returns the element at the specified position in this list.
336       *
# Line 346 | Line 340 | public class ArrayList<E> extends Abstra
340       */
341      public E get(int index) {
342          if (index >= size)
343 <            throw rangeException(index, size);
344 <        return (E)elementData[index];
343 >            indexOutOfBounds(index, size);
344 >        return (E) elementData[index];
345      }
346  
347      /**
# Line 361 | Line 355 | public class ArrayList<E> extends Abstra
355       */
356      public E set(int index, E element) {
357          if (index >= size)
358 <             throw rangeException(index, size);
365 <
358 >            indexOutOfBounds(index, size);
359          E oldValue = (E) elementData[index];
360          elementData[index] = element;
361          return oldValue;
# Line 375 | Line 368 | public class ArrayList<E> extends Abstra
368       * @return <tt>true</tt> (as specified by {@link Collection#add})
369       */
370      public boolean add(E e) {
371 <        ++modCount;
372 <        int s = size++;
371 >        modCount++;
372 >        int s = size;
373          if (s >= elementData.length)
374              growArray(s + 1);
375          elementData[s] = e;
376 <        return true;
376 >        size = s + 1;
377 >        return true;
378      }
379  
380      /**
# Line 395 | Line 389 | public class ArrayList<E> extends Abstra
389      public void add(int index, E element) {
390          int s = size;
391          if (index > s || index < 0)
392 <            throw rangeException(index, s);
393 <        ++modCount;
400 <        size = s + 1;
392 >            indexOutOfBounds(index, s);
393 >        modCount++;
394          if (s >= elementData.length)
395              growArray(s + 1);
396 <        System.arraycopy(elementData, index, elementData, index + 1,
397 <                         s - index);
396 >        System.arraycopy(elementData, index,
397 >                         elementData, index + 1, s - index);
398          elementData[index] = element;
399 +        size = s + 1;
400      }
401  
402      /**
# Line 417 | Line 411 | public class ArrayList<E> extends Abstra
411      public E remove(int index) {
412          int s = size - 1;
413          if (index > s)
414 <            throw rangeException(index, size);
421 <        size = s;
414 >            indexOutOfBounds(index, size);
415          modCount++;
416 <        Object oldValue = elementData[index];
416 >        E oldValue = (E) elementData[index];
417          int numMoved = s - index;
418          if (numMoved > 0)
419 <            System.arraycopy(elementData, index+1, elementData, index,
420 <                             numMoved);
421 <        elementData[s] = null; // forget removed element
422 <        return (E)oldValue;
419 >            System.arraycopy(elementData, index + 1,
420 >                             elementData, index, numMoved);
421 >        elementData[s] = null;
422 >        size = s;
423 >        return oldValue;
424      }
425  
426      /**
# Line 525 | Line 519 | public class ArrayList<E> extends Abstra
519       */
520      public boolean addAll(int index, Collection<? extends E> c) {
521          if (index > size || index < 0)
522 <            throw new IndexOutOfBoundsException(
529 <                "Index: " + index + ", Size: " + size);
522 >            indexOutOfBounds(index, size);
523  
524          Object[] a = c.toArray();
525          int numNew = a.length;
# Line 588 | Line 581 | public class ArrayList<E> extends Abstra
581          for (int i=0; i<size; i++)
582              s.writeObject(elementData[i]);
583  
584 <        if (modCount != expectedModCount) {
584 >        if (expectedModCount != modCount) {
585              throw new ConcurrentModificationException();
586          }
587  
# Line 611 | Line 604 | public class ArrayList<E> extends Abstra
604          for (int i=0; i<size; i++)
605              a[i] = s.readObject();
606      }
614 –
615 –
616 –    /**
617 –     * Returns a list-iterator of the elements in this list (in proper
618 –     * sequence), starting at the specified position in the list.
619 –     * Obeys the general contract of <tt>List.listIterator(int)</tt>.<p>
620 –     *
621 –     * The list-iterator is <i>fail-fast</i>: if the list is structurally
622 –     * modified at any time after the Iterator is created, in any way except
623 –     * through the list-iterator's own <tt>remove</tt> or <tt>add</tt>
624 –     * methods, the list-iterator will throw a
625 –     * <tt>ConcurrentModificationException</tt>.  Thus, in the face of
626 –     * concurrent modification, the iterator fails quickly and cleanly, rather
627 –     * than risking arbitrary, non-deterministic behavior at an undetermined
628 –     * time in the future.
629 –     *
630 –     * @param index index of the first element to be returned from the
631 –     *              list-iterator (by a call to <tt>next</tt>)
632 –     * @return a ListIterator of the elements in this list (in proper
633 –     *         sequence), starting at the specified position in the list
634 –     * @throws IndexOutOfBoundsException {@inheritDoc}
635 –     * @see List#listIterator(int)
636 –     */
637 –    public ListIterator<E> listIterator(int index) {
638 –        if (index < 0 || index > size)
639 –            throw new IndexOutOfBoundsException("Index: "+index);
640 –        return new ArrayListIterator(index);
641 –    }
642 –
643 –    /**
644 –     * Returns an iterator over the elements in this list in proper sequence.
645 –     *
646 –     * @return an iterator over the elements in this list in proper sequence
647 –     */
648 –    public Iterator<E> iterator() {
649 –        return new ArrayListIterator(0);
650 –    }
651 –
652 –    /**
653 –     * A streamlined version of AbstractList.Itr
654 –     */
655 –    final class ArrayListIterator implements ListIterator<E> {
656 –        int cursor;           // index of next element to return;
657 –        int lastRet;          // index of last element, or -1 if no such
658 –        int expectedModCount; // to check for CME
659 –
660 –        ArrayListIterator(int index) {
661 –            cursor = index;
662 –            lastRet = -1;
663 –            expectedModCount = modCount;
664 –        }
665 –
666 –        public boolean hasNext() {
667 –            return cursor < size;
668 –        }
669 –
670 –        public boolean hasPrevious() {
671 –            return cursor > 0;
672 –        }
673 –
674 –        public int nextIndex() {
675 –            return cursor;
676 –        }
677 –
678 –        public int previousIndex() {
679 –            return cursor - 1;
680 –        }
681 –
682 –        public E next() {
683 –            if (expectedModCount == modCount) {
684 –                int i = cursor;
685 –                if (i < size) {
686 –                    try {
687 –                        E e = (E)elementData[i];
688 –                        lastRet = i;
689 –                        cursor = i + 1;
690 –                        return e;
691 –                    } catch (IndexOutOfBoundsException fallthrough) {
692 –                    }
693 –                }
694 –            }
695 –            // Prefer reporting CME if applicable on failures
696 –            if (expectedModCount == modCount)
697 –                throw new NoSuchElementException();
698 –            throw new ConcurrentModificationException();
699 –        }
700 –
701 –        public E previous() {
702 –            if (expectedModCount == modCount) {
703 –                int i = cursor - 1;
704 –                if (i < size) {
705 –                    try {
706 –                        E e = (E)elementData[i];
707 –                        lastRet = i;
708 –                        cursor = i;
709 –                        return e;
710 –                    } catch (IndexOutOfBoundsException fallthrough) {
711 –                    }
712 –                }
713 –            }
714 –            if (expectedModCount == modCount)
715 –                throw new NoSuchElementException();
716 –            throw new ConcurrentModificationException();
717 –        }
718 –
719 –        public void remove() {
720 –            if (lastRet < 0)
721 –                throw new IllegalStateException();
722 –            if (modCount != expectedModCount)
723 –                throw new ConcurrentModificationException();
724 –            ArrayList.this.remove(lastRet);
725 –            if (lastRet < cursor)
726 –                cursor--;
727 –            lastRet = -1;
728 –            expectedModCount = modCount;
729 –        }
730 –
731 –        public void set(E e) {
732 –            if (lastRet < 0)
733 –                throw new IllegalStateException();
734 –            if (modCount != expectedModCount)
735 –                throw new ConcurrentModificationException();
736 –            ArrayList.this.set(lastRet, e);
737 –            expectedModCount = modCount;
738 –        }
739 –
740 –        public void add(E e) {
741 –            if (modCount != expectedModCount)
742 –                throw new ConcurrentModificationException();
743 –            ArrayList.this.add(cursor++, e);
744 –            lastRet = -1;
745 –            expectedModCount = modCount;
746 –        }
747 –    }
748 –
607   }

Diff Legend

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