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.6 by jsr166, Sat Nov 26 04:35:16 2005 UTC vs.
Revision 1.24 by jsr166, Sun May 20 07:54:01 2007 UTC

# Line 1 | Line 1
1   /*
2 < * %W% %E%
2 > * Copyright 1997-2007 Sun Microsystems, Inc.  All Rights Reserved.
3 > * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
4   *
5 < * Copyright 2005 Sun Microsystems, Inc. All rights reserved.
6 < * SUN PROPRIETARY/CONFIDENTIAL. Use is subject to license terms.
5 > * This code is free software; you can redistribute it and/or modify it
6 > * under the terms of the GNU General Public License version 2 only, as
7 > * published by the Free Software Foundation.  Sun designates this
8 > * particular file as subject to the "Classpath" exception as provided
9 > * by Sun in the LICENSE file that accompanied this code.
10 > *
11 > * This code is distributed in the hope that it will be useful, but WITHOUT
12 > * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 > * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
14 > * version 2 for more details (a copy is included in the LICENSE file that
15 > * accompanied this code).
16 > *
17 > * You should have received a copy of the GNU General Public License version
18 > * 2 along with this work; if not, write to the Free Software Foundation,
19 > * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
20 > *
21 > * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa Clara,
22 > * CA 95054 USA or visit www.sun.com if you need additional information or
23 > * have any questions.
24   */
25  
26   package java.util;
9 – import java.util.*; // for javadoc (till 6280605 is fixed)
27  
28   /**
29   * Resizable-array implementation of the <tt>List</tt> interface.  Implements
# Line 67 | Line 84 | import java.util.*; // for javadoc (till
84   * should be used only to detect bugs.</i><p>
85   *
86   * This class is a member of the
87 < * <a href="{@docRoot}/../guide/collections/index.html">
87 > * <a href="{@docRoot}/../technotes/guides/collections/index.html">
88   * Java Collections Framework</a>.
89   *
90   * @author  Josh Bloch
# Line 123 | Line 140 | public class ArrayList<E> extends Abstra
140      /**
141       * Constructs a list containing the elements of the specified
142       * collection, in the order they are returned by the collection's
143 <     * iterator.  The <tt>ArrayList</tt> instance has an initial capacity of
127 <     * 110% the size of the specified collection.
143 >     * iterator.
144       *
145       * @param c the collection whose elements are to be placed into this list
146       * @throws NullPointerException if the specified collection is null
147       */
148      public ArrayList(Collection<? extends E> c) {
133 –        int size = c.size();
134 –        // 10% for growth
135 –        int cap = ((size/10)+1)*11;
136 –        if (cap > 0) {
137 –            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);
148 –    }
149 –
150 –    private void initFromConcurrentlyMutating(Collection<? extends E> c) {
149          elementData = c.toArray();
150          size = elementData.length;
151          // c.toArray might (incorrectly) not return Object[] (see 6260652)
# Line 155 | Line 153 | public class ArrayList<E> extends Abstra
153              elementData = Arrays.copyOf(elementData, size, Object[].class);
154      }
155  
158 –    private final static Object UNALLOCATED = new Object();
159 –
156      /**
157       * Trims the capacity of this <tt>ArrayList</tt> instance to be the
158       * list's current size.  An application can use this operation to minimize
# Line 189 | Line 185 | public class ArrayList<E> extends Abstra
185       * @param minCapacity the desired minimum capacity
186       */
187      private void growArray(int minCapacity) {
188 +        if (minCapacity < 0) // overflow
189 +            throw new OutOfMemoryError();
190          int oldCapacity = elementData.length;
191          // Double size if small; else grow by 50%
192 <        int newCapacity = ((oldCapacity < 64)?
193 <                           (oldCapacity * 2):
194 <                           ((oldCapacity * 3)/2 + 1));
192 >        int newCapacity = ((oldCapacity < 64) ?
193 >                           ((oldCapacity + 1) * 2) :
194 >                           ((oldCapacity / 2) * 3));
195 >        if (newCapacity < 0) // overflow
196 >            newCapacity = Integer.MAX_VALUE;
197          if (newCapacity < minCapacity)
198              newCapacity = minCapacity;
199          elementData = Arrays.copyOf(elementData, newCapacity);
# Line 343 | Line 343 | public class ArrayList<E> extends Abstra
343      // Positional Access Operations
344  
345      /**
346 <     * Creates and returns an appropriate exception for indexing errors.
346 >     * Throws an appropriate exception for indexing errors.
347       */
348 <    private static IndexOutOfBoundsException rangeException(int i, int s) {
349 <        return new IndexOutOfBoundsException("Index: " + i + ", Size: " + s);
348 >    private static void indexOutOfBounds(int i, int s) {
349 >        throw new IndexOutOfBoundsException("Index: " + i + ", Size: " + s);
350      }
351  
352      /**
# Line 358 | Line 358 | public class ArrayList<E> extends Abstra
358       */
359      public E get(int index) {
360          if (index >= size)
361 <            throw rangeException(index, size);
362 <        return (E)elementData[index];
361 >            indexOutOfBounds(index, size);
362 >        return (E) elementData[index];
363      }
364  
365      /**
# Line 373 | Line 373 | public class ArrayList<E> extends Abstra
373       */
374      public E set(int index, E element) {
375          if (index >= size)
376 <             throw rangeException(index, size);
377 <
376 >            indexOutOfBounds(index, size);
377          E oldValue = (E) elementData[index];
378          elementData[index] = element;
379          return oldValue;
# Line 387 | Line 386 | public class ArrayList<E> extends Abstra
386       * @return <tt>true</tt> (as specified by {@link Collection#add})
387       */
388      public boolean add(E e) {
389 <        ++modCount;
390 <        int s = size++;
389 >        modCount++;
390 >        int s = size;
391          if (s >= elementData.length)
392              growArray(s + 1);
393          elementData[s] = e;
394 <        return true;
394 >        size = s + 1;
395 >        return true;
396      }
397  
398      /**
# Line 407 | Line 407 | public class ArrayList<E> extends Abstra
407      public void add(int index, E element) {
408          int s = size;
409          if (index > s || index < 0)
410 <            throw rangeException(index, s);
411 <        ++modCount;
412 <        size = s + 1;
410 >            indexOutOfBounds(index, s);
411 >        modCount++;
412          if (s >= elementData.length)
413              growArray(s + 1);
414 <        System.arraycopy(elementData, index, elementData, index + 1,
415 <                         s - index);
414 >        System.arraycopy(elementData, index,
415 >                         elementData, index + 1, s - index);
416          elementData[index] = element;
417 +        size = s + 1;
418      }
419  
420      /**
# Line 429 | Line 429 | public class ArrayList<E> extends Abstra
429      public E remove(int index) {
430          int s = size - 1;
431          if (index > s)
432 <            throw rangeException(index, size);
433 <        size = s;
432 >            indexOutOfBounds(index, size);
433          modCount++;
434 <        Object oldValue = elementData[index];
434 >        E oldValue = (E) elementData[index];
435          int numMoved = s - index;
436          if (numMoved > 0)
437 <            System.arraycopy(elementData, index+1, elementData, index,
438 <                             numMoved);
439 <        elementData[s] = null; // forget removed element
440 <        return (E)oldValue;
437 >            System.arraycopy(elementData, index + 1,
438 >                             elementData, index, numMoved);
439 >        elementData[s] = null;
440 >        size = s;
441 >        return oldValue;
442      }
443  
444      /**
# Line 537 | Line 537 | public class ArrayList<E> extends Abstra
537       */
538      public boolean addAll(int index, Collection<? extends E> c) {
539          if (index > size || index < 0)
540 <            throw new IndexOutOfBoundsException(
541 <                "Index: " + index + ", Size: " + size);
540 >            indexOutOfBounds(index, size);
541  
542          Object[] a = c.toArray();
543          int numNew = a.length;
# Line 600 | Line 599 | public class ArrayList<E> extends Abstra
599          for (int i=0; i<size; i++)
600              s.writeObject(elementData[i]);
601  
602 <        if (modCount != expectedModCount) {
602 >        if (expectedModCount != modCount) {
603              throw new ConcurrentModificationException();
604          }
605  
# Line 623 | Line 622 | public class ArrayList<E> extends Abstra
622          for (int i=0; i<size; i++)
623              a[i] = s.readObject();
624      }
626 –
627 –
628 –    /**
629 –     * Returns a list-iterator of the elements in this list (in proper
630 –     * sequence), starting at the specified position in the list.
631 –     * Obeys the general contract of <tt>List.listIterator(int)</tt>.<p>
632 –     *
633 –     * The list-iterator is <i>fail-fast</i>: if the list is structurally
634 –     * modified at any time after the Iterator is created, in any way except
635 –     * through the list-iterator's own <tt>remove</tt> or <tt>add</tt>
636 –     * methods, the list-iterator will throw a
637 –     * <tt>ConcurrentModificationException</tt>.  Thus, in the face of
638 –     * concurrent modification, the iterator fails quickly and cleanly, rather
639 –     * than risking arbitrary, non-deterministic behavior at an undetermined
640 –     * time in the future.
641 –     *
642 –     * @param index index of the first element to be returned from the
643 –     *              list-iterator (by a call to <tt>next</tt>)
644 –     * @return a ListIterator of the elements in this list (in proper
645 –     *         sequence), starting at the specified position in the list
646 –     * @throws IndexOutOfBoundsException {@inheritDoc}
647 –     * @see List#listIterator(int)
648 –     */
649 –    public ListIterator<E> listIterator(int index) {
650 –        if (index < 0 || index > size)
651 –            throw new IndexOutOfBoundsException("Index: "+index);
652 –        return new ArrayListIterator(index);
653 –    }
654 –
655 –    /**
656 –     * Returns an iterator over the elements in this list in proper sequence.
657 –     *
658 –     * @return an iterator over the elements in this list in proper sequence
659 –     */
660 –    public Iterator<E> iterator() {
661 –        return new ArrayListIterator(0);
662 –    }
663 –
664 –    /**
665 –     * A streamlined version of AbstractList.Itr
666 –     */
667 –    final class ArrayListIterator implements ListIterator<E> {
668 –        int cursor;           // index of next element to return;
669 –        int lastRet;          // index of last element, or -1 if no such
670 –        int expectedModCount; // to check for CME
671 –
672 –        ArrayListIterator(int index) {
673 –            cursor = index;
674 –            lastRet = -1;
675 –            expectedModCount = modCount;
676 –        }
677 –
678 –        public boolean hasNext() {
679 –            return cursor < size;
680 –        }
681 –
682 –        public boolean hasPrevious() {
683 –            return cursor > 0;
684 –        }
685 –
686 –        public int nextIndex() {
687 –            return cursor;
688 –        }
689 –
690 –        public int previousIndex() {
691 –            return cursor - 1;
692 –        }
693 –
694 –        public E next() {
695 –            if (expectedModCount == modCount) {
696 –                int i = cursor;
697 –                if (i < size) {
698 –                    try {
699 –                        E e = (E)elementData[i];
700 –                        lastRet = i;
701 –                        cursor = i + 1;
702 –                        return e;
703 –                    } catch (IndexOutOfBoundsException fallthrough) {
704 –                    }
705 –                }
706 –            }
707 –            // Prefer reporting CME if applicable on failures
708 –            if (expectedModCount == modCount)
709 –                throw new NoSuchElementException();
710 –            throw new ConcurrentModificationException();
711 –        }
712 –
713 –        public E previous() {
714 –            if (expectedModCount == modCount) {
715 –                int i = cursor - 1;
716 –                if (i < size) {
717 –                    try {
718 –                        E e = (E)elementData[i];
719 –                        lastRet = i;
720 –                        cursor = i;
721 –                        return e;
722 –                    } catch (IndexOutOfBoundsException fallthrough) {
723 –                    }
724 –                }
725 –            }
726 –            if (expectedModCount == modCount)
727 –                throw new NoSuchElementException();
728 –            throw new ConcurrentModificationException();
729 –        }
730 –
731 –        public void remove() {
732 –            if (lastRet < 0)
733 –                throw new IllegalStateException();
734 –            if (modCount != expectedModCount)
735 –                throw new ConcurrentModificationException();
736 –            ArrayList.this.remove(lastRet);
737 –            if (lastRet < cursor)
738 –                cursor--;
739 –            lastRet = -1;
740 –            expectedModCount = modCount;
741 –        }
742 –
743 –        public void set(E e) {
744 –            if (lastRet < 0)
745 –                throw new IllegalStateException();
746 –            if (modCount != expectedModCount)
747 –                throw new ConcurrentModificationException();
748 –            ArrayList.this.set(lastRet, e);
749 –            expectedModCount = modCount;
750 –        }
751 –
752 –        public void add(E e) {
753 –            if (modCount != expectedModCount)
754 –                throw new ConcurrentModificationException();
755 –            ArrayList.this.add(cursor++, e);
756 –            lastRet = -1;
757 –            expectedModCount = modCount;
758 –        }
759 –    }
760 –
625   }

Diff Legend

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