ViewVC Help

View File | Revision Log | Show Annotations | Download File | Root Listing

root/jsr166/jsr166/src/main/java/util/ArrayList.java

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.14 by jsr166, Mon Dec 5 02:56:59 2005 UTC

#	Line 1 | Line 1
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
#	Line 101 | Line 101 | public class ArrayList<E> extends Abstra
101		/**
102		* Constructs an empty list with the specified initial capacity.
103		*
104	<	* @param   initialCapacity   the initial capacity of the list
105	<	* @exception IllegalArgumentException if the specified initial capacity
106	<	*            is negative
104	>	* @param initialCapacity the initial capacity of the list
105	>	* @throws IllegalArgumentException if the specified initial capacity
106	>	*         is negative
107		*/
108		public ArrayList(int initialCapacity) {
109		super();
#	Line 123 | Line 123 | public class ArrayList<E> extends Abstra
123		/**
124		* Constructs a list containing the elements of the specified
125		* collection, in the order they are returned by the collection's
126	<	* iterator.
126	>	* iterator.  The <tt>ArrayList</tt> instance has an initial capacity of
127	>	* 110% the size of the specified collection.
128		*
129		* @param c the collection whose elements are to be placed into this list
130		* @throws NullPointerException if the specified collection is null
131		*/
132		public ArrayList(Collection<? extends E> c) {
133	<	Object[] a = c.toArray();
134	<	// If c.toArray incorrectly doesn't return Object[], copy it.
135	<	if (a.getClass() != Object[].class)
136	<	a = Arrays.copyOf(a, a.length, Object[].class);
137	<	elementData = a;
138	<	size = a.length;
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) {
151	>	elementData = c.toArray();
152	>	size = elementData.length;
153	>	// c.toArray might (incorrectly) not return Object[] (see 6260652)
154	>	if (elementData.getClass() != Object[].class)
155	>	elementData = Arrays.copyOf(elementData, size, Object[].class);
156		}
157
158	+	private final static Object UNALLOCATED = new Object();
159	+
160		/**
161		* Trims the capacity of this <tt>ArrayList</tt> instance to be the
162		* list's current size.  An application can use this operation to minimize
#	Line 155 | Line 175 | public class ArrayList<E> extends Abstra
175		* necessary, to ensure that it can hold at least the number of elements
176		* specified by the minimum capacity argument.
177		*
178	<	* @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
178	>	* @param minCapacity the desired minimum capacity
179		*/
180		public void ensureCapacity(int minCapacity) {
181		modCount++;
#	Line 171 | Line 184 | public class ArrayList<E> extends Abstra
184		}
185
186		/**
187	<	* Increase the capacity of the array.
188	<	* @param   minCapacity   the desired minimum capacity
187	>	* Increases the capacity of the array.
188	>	*
189	>	* @param minCapacity the desired minimum capacity
190		*/
191		private void growArray(int minCapacity) {
192	+	if (minCapacity < 0) // overflow
193	+	throw new OutOfMemoryError();
194		int oldCapacity = elementData.length;
195		// Double size if small; else grow by 50%
196	<	int newCapacity = ((oldCapacity < 64)?
197	<	(oldCapacity * 2):
198	<	((oldCapacity * 3)/2 + 1));
196	>	int newCapacity = ((oldCapacity < 64)?
197	>	((oldCapacity + 1) * 2):
198	>	((oldCapacity / 2) * 3));
199	>	if (newCapacity < 0) // overflow
200	>	newCapacity = Integer.MAX_VALUE;
201		if (newCapacity < minCapacity)
202		newCapacity = minCapacity;
203		elementData = Arrays.copyOf(elementData, newCapacity);
#	Line 328 | Line 346 | public class ArrayList<E> extends Abstra
346
347		// Positional Access Operations
348
349	<	/**
350	<	* Create and return an appropriate exception for indexing errors
349	>	/**
350	>	* Returns error message string for IndexOutOfBoundsExceptions
351		*/
352	<	private static IndexOutOfBoundsException rangeException(int i, int s) {
353	<	return new IndexOutOfBoundsException("Index: " + i + ", Size: " + s);
352	>	private String ioobe(int index) {
353	>	return "Index: " + index + ", Size: " + size;
354		}
355
338	–	// Positional Access Operations
339	–
356		/**
357		* Returns the element at the specified position in this list.
358		*
#	Line 346 | Line 362 | public class ArrayList<E> extends Abstra
362		*/
363		public E get(int index) {
364		if (index >= size)
365	<	throw rangeException(index, size);
365	>	throw new IndexOutOfBoundsException(ioobe(index));
366		return (E)elementData[index];
367		}
368
#	Line 361 | Line 377 | public class ArrayList<E> extends Abstra
377		*/
378		public E set(int index, E element) {
379		if (index >= size)
380	<	throw rangeException(index, size);
380	>	throw new IndexOutOfBoundsException(ioobe(index));
381
382		E oldValue = (E) elementData[index];
383		elementData[index] = element;
#	Line 375 | Line 391 | public class ArrayList<E> extends Abstra
391		* @return <tt>true</tt> (as specified by {@link Collection#add})
392		*/
393		public boolean add(E e) {
394	<	++modCount;
395	<	int s = size++;
394	>	modCount++;
395	>	int s = size;
396		if (s >= elementData.length)
397		growArray(s + 1);
398		elementData[s] = e;
399	+	size = s + 1;
400		return true;
401		}
402
#	Line 395 | Line 412 | public class ArrayList<E> extends Abstra
412		public void add(int index, E element) {
413		int s = size;
414		if (index > s || index < 0)
415	<	throw rangeException(index, s);
416	<	++modCount;
400	<	size = s + 1;
415	>	throw new IndexOutOfBoundsException(ioobe(index));
416	>	modCount++;
417		if (s >= elementData.length)
418		growArray(s + 1);
419	<	System.arraycopy(elementData, index, elementData, index + 1,
420	<	s - index);
419	>	System.arraycopy(elementData, index,
420	>	elementData, index + 1, s - index);
421		elementData[index] = element;
422	+	size = s + 1;
423		}
424
425		/**
#	Line 417 | Line 434 | public class ArrayList<E> extends Abstra
434		public E remove(int index) {
435		int s = size - 1;
436		if (index > s)
437	<	throw rangeException(index, size);
421	<	size = s;
437	>	throw new IndexOutOfBoundsException(ioobe(index));
438		modCount++;
439	<	Object oldValue = elementData[index];
439	>	E oldValue = (E)elementData[index];
440		int numMoved = s - index;
441		if (numMoved > 0)
442	<	System.arraycopy(elementData, index+1, elementData, index,
443	<	numMoved);
444	<	elementData[s] = null; // forget removed element
445	<	return (E)oldValue;
442	>	System.arraycopy(elementData, index + 1,
443	>	elementData, index, numMoved);
444	>	elementData[s] = null;
445	>	size = s;
446	>	return oldValue;
447		}
448
449		/**
#	Line 525 | Line 542 | public class ArrayList<E> extends Abstra
542		*/
543		public boolean addAll(int index, Collection<? extends E> c) {
544		if (index > size || index < 0)
545	<	throw new IndexOutOfBoundsException(
529	<	"Index: " + index + ", Size: " + size);
545	>	throw new IndexOutOfBoundsException(ioobe(index));
546
547		Object[] a = c.toArray();
548		int numNew = a.length;
#	Line 588 | Line 604 | public class ArrayList<E> extends Abstra
604		for (int i=0; i<size; i++)
605		s.writeObject(elementData[i]);
606
607	<	if (modCount != expectedModCount) {
607	>	if (expectedModCount != modCount) {
608		throw new ConcurrentModificationException();
609		}
610
#	Line 636 | Line 652 | public class ArrayList<E> extends Abstra
652		*/
653		public ListIterator<E> listIterator(int index) {
654		if (index < 0 || index > size)
655	<	throw new IndexOutOfBoundsException("Index: "+index);
655	>	throw new IndexOutOfBoundsException(ioobe(index));
656		return new ArrayListIterator(index);
657		}
658	<
658	>
659	>	/**
660	>	* {@inheritDoc}
661	>	*/
662	>	public ListIterator<E> listIterator() {
663	>	return new ArrayListIterator(0);
664	>	}
665	>
666		/**
667		* Returns an iterator over the elements in this list in proper sequence.
668		*
#	Line 650 | Line 673 | public class ArrayList<E> extends Abstra
673		}
674
675		/**
676	<	* A streamlined version of AbstractList.Itr
676	>	* A streamlined version of AbstractList.ListItr
677		*/
678		final class ArrayListIterator implements ListIterator<E> {
679		int cursor;           // index of next element to return;
#	Line 664 | Line 687 | public class ArrayList<E> extends Abstra
687		}
688
689		public boolean hasNext() {
690	<	return cursor < size;
690	>	return cursor != size;
691		}
692
693		public boolean hasPrevious() {
694	<	return cursor > 0;
694	>	return cursor != 0;
695		}
696
697		public int nextIndex() {
#	Line 680 | Line 703 | public class ArrayList<E> extends Abstra
703		}
704
705		public E next() {
706	<	if (expectedModCount == modCount) {
706	>	try {
707		int i = cursor;
708	<	if (i < size) {
709	<	try {
710	<	E e = (E)elementData[i];
711	<	lastRet = i;
712	<	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)
708	>	E next = get(i);
709	>	lastRet = i;
710	>	cursor = i + 1;
711	>	return next;
712	>	} catch (IndexOutOfBoundsException ex) {
713		throw new NoSuchElementException();
714	<	throw new ConcurrentModificationException();
714	>	} finally {
715	>	if (expectedModCount != modCount)
716	>	throw new ConcurrentModificationException();
717	>	}
718		}
719
720		public E previous() {
721	<	if (expectedModCount == modCount) {
721	>	try {
722		int i = cursor - 1;
723	<	if (i < size) {
724	<	try {
725	<	E e = (E)elementData[i];
726	<	lastRet = i;
727	<	cursor = i;
709	<	return e;
710	<	} catch (IndexOutOfBoundsException fallthrough) {
711	<	}
712	<	}
713	<	}
714	<	if (expectedModCount == modCount)
723	>	E prev = get(i);
724	>	lastRet = i;
725	>	cursor = i;
726	>	return prev;
727	>	} catch (IndexOutOfBoundsException ex) {
728		throw new NoSuchElementException();
729	<	throw new ConcurrentModificationException();
729	>	} finally {
730	>	if (expectedModCount != modCount)
731	>	throw new ConcurrentModificationException();
732	>	}
733		}
734
735		public void remove() {
736		if (lastRet < 0)
737		throw new IllegalStateException();
738	<	if (modCount != expectedModCount)
738	>	if (expectedModCount != modCount)
739		throw new ConcurrentModificationException();
740		ArrayList.this.remove(lastRet);
741		if (lastRet < cursor)
#	Line 731 | Line 747 | public class ArrayList<E> extends Abstra
747		public void set(E e) {
748		if (lastRet < 0)
749		throw new IllegalStateException();
750	<	if (modCount != expectedModCount)
750	>	if (expectedModCount != modCount)
751		throw new ConcurrentModificationException();
752		ArrayList.this.set(lastRet, e);
753		expectedModCount = modCount;
754		}
755
756		public void add(E e) {
757	<	if (modCount != expectedModCount)
757	>	if (expectedModCount != modCount)
758		throw new ConcurrentModificationException();
759	<	ArrayList.this.add(cursor++, e);
760	<	lastRet = -1;
761	<	expectedModCount = modCount;
759	>	try {
760	>	ArrayList.this.add(cursor++, e);
761	>	lastRet = -1;
762	>	expectedModCount = modCount;
763	>	} catch (IndexOutOfBoundsException ex) {
764	>	throw new ConcurrentModificationException();
765	>	}
766		}
767		}
748	–
768		}

Diff Legend

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