1 |
|
/* |
2 |
|
* %W% %E% |
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 |
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(); |
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) { |
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) { |
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 |
< |
|
158 |
< |
private final static Object UNALLOCATED = new Object(); |
159 |
< |
|
137 |
> |
|
138 |
|
/** |
139 |
|
* Trims the capacity of this <tt>ArrayList</tt> instance to be the |
140 |
|
* list's current size. An application can use this operation to minimize |
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 |
156 |
> |
* @param minCapacity the desired minimum capacity |
157 |
|
*/ |
158 |
|
public void ensureCapacity(int minCapacity) { |
159 |
|
modCount++; |
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); |
324 |
|
|
325 |
|
// Positional Access Operations |
326 |
|
|
327 |
< |
/** |
328 |
< |
* Create and return an appropriate exception for indexing errors |
327 |
> |
/** |
328 |
> |
* Returns error message string for IndexOutOfBoundsExceptions |
329 |
|
*/ |
330 |
< |
private static IndexOutOfBoundsException rangeException(int i, int s) { |
331 |
< |
return new IndexOutOfBoundsException("Index: " + i + ", Size: " + s); |
330 |
> |
private String ioobe(int index) { |
331 |
> |
return "Index: " + index + ", Size: " + size; |
332 |
|
} |
333 |
|
|
351 |
– |
// Positional Access Operations |
352 |
– |
|
334 |
|
/** |
335 |
|
* Returns the element at the specified position in this list. |
336 |
|
* |
340 |
|
*/ |
341 |
|
public E get(int index) { |
342 |
|
if (index >= size) |
343 |
< |
throw rangeException(index, size); |
343 |
> |
throw new IndexOutOfBoundsException(ioobe(index)); |
344 |
|
return (E)elementData[index]; |
345 |
|
} |
346 |
|
|
355 |
|
*/ |
356 |
|
public E set(int index, E element) { |
357 |
|
if (index >= size) |
358 |
< |
throw rangeException(index, size); |
358 |
> |
throw new IndexOutOfBoundsException(ioobe(index)); |
359 |
|
|
360 |
|
E oldValue = (E) elementData[index]; |
361 |
|
elementData[index] = element; |
369 |
|
* @return <tt>true</tt> (as specified by {@link Collection#add}) |
370 |
|
*/ |
371 |
|
public boolean add(E e) { |
372 |
< |
++modCount; |
373 |
< |
int s = size++; |
372 |
> |
modCount++; |
373 |
> |
int s = size; |
374 |
|
if (s >= elementData.length) |
375 |
|
growArray(s + 1); |
376 |
|
elementData[s] = e; |
377 |
+ |
size = s + 1; |
378 |
|
return true; |
379 |
|
} |
380 |
|
|
390 |
|
public void add(int index, E element) { |
391 |
|
int s = size; |
392 |
|
if (index > s || index < 0) |
393 |
< |
throw rangeException(index, s); |
394 |
< |
++modCount; |
413 |
< |
size = s + 1; |
393 |
> |
throw new IndexOutOfBoundsException(ioobe(index)); |
394 |
> |
modCount++; |
395 |
|
if (s >= elementData.length) |
396 |
|
growArray(s + 1); |
397 |
< |
System.arraycopy(elementData, index, elementData, index + 1, |
398 |
< |
s - index); |
397 |
> |
System.arraycopy(elementData, index, |
398 |
> |
elementData, index + 1, s - index); |
399 |
|
elementData[index] = element; |
400 |
+ |
size = s + 1; |
401 |
|
} |
402 |
|
|
403 |
|
/** |
412 |
|
public E remove(int index) { |
413 |
|
int s = size - 1; |
414 |
|
if (index > s) |
415 |
< |
throw rangeException(index, size); |
434 |
< |
size = s; |
415 |
> |
throw new IndexOutOfBoundsException(ioobe(index)); |
416 |
|
modCount++; |
417 |
< |
Object oldValue = elementData[index]; |
417 |
> |
E oldValue = (E)elementData[index]; |
418 |
|
int numMoved = s - index; |
419 |
|
if (numMoved > 0) |
420 |
< |
System.arraycopy(elementData, index+1, elementData, index, |
421 |
< |
numMoved); |
422 |
< |
elementData[s] = null; // forget removed element |
423 |
< |
return (E)oldValue; |
420 |
> |
System.arraycopy(elementData, index + 1, |
421 |
> |
elementData, index, numMoved); |
422 |
> |
elementData[s] = null; |
423 |
> |
size = s; |
424 |
> |
return oldValue; |
425 |
|
} |
426 |
|
|
427 |
|
/** |
520 |
|
*/ |
521 |
|
public boolean addAll(int index, Collection<? extends E> c) { |
522 |
|
if (index > size || index < 0) |
523 |
< |
throw new IndexOutOfBoundsException( |
542 |
< |
"Index: " + index + ", Size: " + size); |
523 |
> |
throw new IndexOutOfBoundsException(ioobe(index)); |
524 |
|
|
525 |
|
Object[] a = c.toArray(); |
526 |
|
int numNew = a.length; |
582 |
|
for (int i=0; i<size; i++) |
583 |
|
s.writeObject(elementData[i]); |
584 |
|
|
585 |
< |
if (modCount != expectedModCount) { |
585 |
> |
if (expectedModCount != modCount) { |
586 |
|
throw new ConcurrentModificationException(); |
587 |
|
} |
588 |
|
|
630 |
|
*/ |
631 |
|
public ListIterator<E> listIterator(int index) { |
632 |
|
if (index < 0 || index > size) |
633 |
< |
throw new IndexOutOfBoundsException("Index: "+index); |
633 |
> |
throw new IndexOutOfBoundsException(ioobe(index)); |
634 |
|
return new ArrayListIterator(index); |
635 |
|
} |
636 |
< |
|
636 |
> |
|
637 |
> |
/** |
638 |
> |
* {@inheritDoc} |
639 |
> |
*/ |
640 |
> |
public ListIterator<E> listIterator() { |
641 |
> |
return new ArrayListIterator(0); |
642 |
> |
} |
643 |
> |
|
644 |
|
/** |
645 |
|
* Returns an iterator over the elements in this list in proper sequence. |
646 |
|
* |
651 |
|
} |
652 |
|
|
653 |
|
/** |
654 |
< |
* A streamlined version of AbstractList.Itr |
654 |
> |
* A streamlined version of AbstractList.ListItr |
655 |
|
*/ |
656 |
|
final class ArrayListIterator implements ListIterator<E> { |
657 |
|
int cursor; // index of next element to return; |
665 |
|
} |
666 |
|
|
667 |
|
public boolean hasNext() { |
668 |
< |
return cursor < size; |
668 |
> |
return cursor != size; |
669 |
|
} |
670 |
|
|
671 |
|
public boolean hasPrevious() { |
672 |
< |
return cursor > 0; |
672 |
> |
return cursor != 0; |
673 |
|
} |
674 |
|
|
675 |
|
public int nextIndex() { |
681 |
|
} |
682 |
|
|
683 |
|
public E next() { |
684 |
< |
if (expectedModCount == modCount) { |
684 |
> |
try { |
685 |
|
int i = cursor; |
686 |
< |
if (i < size) { |
687 |
< |
try { |
688 |
< |
E e = (E)elementData[i]; |
689 |
< |
lastRet = i; |
690 |
< |
cursor = i + 1; |
703 |
< |
return e; |
704 |
< |
} catch (IndexOutOfBoundsException fallthrough) { |
705 |
< |
} |
706 |
< |
} |
707 |
< |
} |
708 |
< |
// Prefer reporting CME if applicable on failures |
709 |
< |
if (expectedModCount == modCount) |
686 |
> |
E next = get(i); |
687 |
> |
lastRet = i; |
688 |
> |
cursor = i + 1; |
689 |
> |
return next; |
690 |
> |
} catch (IndexOutOfBoundsException ex) { |
691 |
|
throw new NoSuchElementException(); |
692 |
< |
throw new ConcurrentModificationException(); |
692 |
> |
} finally { |
693 |
> |
if (expectedModCount != modCount) |
694 |
> |
throw new ConcurrentModificationException(); |
695 |
> |
} |
696 |
|
} |
697 |
|
|
698 |
|
public E previous() { |
699 |
< |
if (expectedModCount == modCount) { |
699 |
> |
try { |
700 |
|
int i = cursor - 1; |
701 |
< |
if (i < size) { |
702 |
< |
try { |
703 |
< |
E e = (E)elementData[i]; |
704 |
< |
lastRet = i; |
705 |
< |
cursor = i; |
722 |
< |
return e; |
723 |
< |
} catch (IndexOutOfBoundsException fallthrough) { |
724 |
< |
} |
725 |
< |
} |
726 |
< |
} |
727 |
< |
if (expectedModCount == modCount) |
701 |
> |
E prev = get(i); |
702 |
> |
lastRet = i; |
703 |
> |
cursor = i; |
704 |
> |
return prev; |
705 |
> |
} catch (IndexOutOfBoundsException ex) { |
706 |
|
throw new NoSuchElementException(); |
707 |
< |
throw new ConcurrentModificationException(); |
707 |
> |
} finally { |
708 |
> |
if (expectedModCount != modCount) |
709 |
> |
throw new ConcurrentModificationException(); |
710 |
> |
} |
711 |
|
} |
712 |
|
|
713 |
|
public void remove() { |
714 |
|
if (lastRet < 0) |
715 |
|
throw new IllegalStateException(); |
716 |
< |
if (modCount != expectedModCount) |
716 |
> |
if (expectedModCount != modCount) |
717 |
|
throw new ConcurrentModificationException(); |
718 |
|
ArrayList.this.remove(lastRet); |
719 |
|
if (lastRet < cursor) |
725 |
|
public void set(E e) { |
726 |
|
if (lastRet < 0) |
727 |
|
throw new IllegalStateException(); |
728 |
< |
if (modCount != expectedModCount) |
728 |
> |
if (expectedModCount != modCount) |
729 |
|
throw new ConcurrentModificationException(); |
730 |
|
ArrayList.this.set(lastRet, e); |
731 |
|
expectedModCount = modCount; |
732 |
|
} |
733 |
|
|
734 |
|
public void add(E e) { |
735 |
< |
if (modCount != expectedModCount) |
735 |
> |
if (expectedModCount != modCount) |
736 |
|
throw new ConcurrentModificationException(); |
737 |
< |
ArrayList.this.add(cursor++, e); |
738 |
< |
lastRet = -1; |
739 |
< |
expectedModCount = modCount; |
737 |
> |
try { |
738 |
> |
ArrayList.this.add(cursor++, e); |
739 |
> |
lastRet = -1; |
740 |
> |
expectedModCount = modCount; |
741 |
> |
} catch (IndexOutOfBoundsException ex) { |
742 |
> |
throw new ConcurrentModificationException(); |
743 |
> |
} |
744 |
|
} |
745 |
|
} |
761 |
– |
|
746 |
|
} |