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 |
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 |
118 |
|
/** |
119 |
|
* Constructs an empty list with the specified initial capacity. |
120 |
|
* |
121 |
< |
* @param initialCapacity the initial capacity of the list |
122 |
< |
* @exception IllegalArgumentException if the specified initial capacity |
123 |
< |
* is negative |
121 |
> |
* @param initialCapacity the initial capacity of the list |
122 |
> |
* @throws IllegalArgumentException if the specified initial capacity |
123 |
> |
* is negative |
124 |
|
*/ |
125 |
|
public ArrayList(int initialCapacity) { |
126 |
|
super(); |
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. |
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) { |
149 |
< |
Object[] a = c.toArray(); |
150 |
< |
// If c.toArray incorrectly doesn't return Object[], copy it. |
151 |
< |
if (a.getClass() != Object[].class) |
152 |
< |
a = Arrays.copyOf(a, a.length, Object[].class); |
153 |
< |
elementData = a; |
137 |
< |
size = a.length; |
149 |
> |
elementData = c.toArray(); |
150 |
> |
size = elementData.length; |
151 |
> |
// c.toArray might (incorrectly) not return Object[] (see 6260652) |
152 |
> |
if (elementData.getClass() != Object[].class) |
153 |
> |
elementData = Arrays.copyOf(elementData, size, Object[].class); |
154 |
|
} |
155 |
|
|
156 |
|
/** |
171 |
|
* necessary, to ensure that it can hold at least the number of elements |
172 |
|
* specified by the minimum capacity argument. |
173 |
|
* |
174 |
< |
* @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 |
174 |
> |
* @param minCapacity the desired minimum capacity |
175 |
|
*/ |
176 |
|
public void ensureCapacity(int minCapacity) { |
177 |
|
modCount++; |
180 |
|
} |
181 |
|
|
182 |
|
/** |
183 |
< |
* Increase the capacity of the array. |
184 |
< |
* @param minCapacity the desired minimum capacity |
183 |
> |
* Increases the capacity of the array. |
184 |
> |
* |
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); |
342 |
|
|
343 |
|
// Positional Access Operations |
344 |
|
|
345 |
< |
/** |
346 |
< |
* Create and return an appropriate exception for indexing errors |
345 |
> |
/** |
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 |
|
|
338 |
– |
// Positional Access Operations |
339 |
– |
|
352 |
|
/** |
353 |
|
* Returns the element at the specified position in this list. |
354 |
|
* |
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 |
|
/** |
373 |
|
*/ |
374 |
|
public E set(int index, E element) { |
375 |
|
if (index >= size) |
376 |
< |
throw rangeException(index, size); |
365 |
< |
|
376 |
> |
indexOutOfBounds(index, size); |
377 |
|
E oldValue = (E) elementData[index]; |
378 |
|
elementData[index] = element; |
379 |
|
return oldValue; |
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 |
|
/** |
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; |
400 |
< |
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 |
|
/** |
429 |
|
public E remove(int index) { |
430 |
|
int s = size - 1; |
431 |
|
if (index > s) |
432 |
< |
throw rangeException(index, size); |
421 |
< |
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 |
|
/** |
537 |
|
*/ |
538 |
|
public boolean addAll(int index, Collection<? extends E> c) { |
539 |
|
if (index > size || index < 0) |
540 |
< |
throw new IndexOutOfBoundsException( |
529 |
< |
"Index: " + index + ", Size: " + size); |
540 |
> |
indexOutOfBounds(index, size); |
541 |
|
|
542 |
|
Object[] a = c.toArray(); |
543 |
|
int numNew = a.length; |
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 |
|
|
622 |
|
for (int i=0; i<size; i++) |
623 |
|
a[i] = s.readObject(); |
624 |
|
} |
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 |
– |
|
625 |
|
} |