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.2 by dl, Fri Nov 25 13:34:29 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.  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
#	Line 175 | 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
179	<	*/
180	<	/**
181	<	* Increases the capacity of this <tt>ArrayList</tt> instance, if
182	<	* necessary, to ensure that it can hold at least the number of elements
183	<	* specified by the minimum capacity argument.
184	<	*
185	<	* @param   minCapacity   the desired minimum capacity
156	>	* @param minCapacity the desired minimum capacity
157		*/
158		public void ensureCapacity(int minCapacity) {
159		modCount++;
#	Line 191 | 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 348 | 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
358	–	// Positional Access Operations
359	–
334		/**
335		* Returns the element at the specified position in this list.
336		*
#	Line 366 | 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 381 | 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);
385	<
358	>	indexOutOfBounds(index, size);
359		E oldValue = (E) elementData[index];
360		elementData[index] = element;
361		return oldValue;
#	Line 395 | 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 415 | 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;
420	<	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 437 | 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);
441	<	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 545 | 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(
549	<	"Index: " + index + ", Size: " + size);
522	>	indexOutOfBounds(index, size);
523
524		Object[] a = c.toArray();
525		int numNew = a.length;
#	Line 608 | 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 631 | Line 604 | public class ArrayList<E> extends Abstra
604		for (int i=0; i<size; i++)
605		a[i] = s.readObject();
606		}
634	–
635	–
636	–	/**
637	–	* Returns a list-iterator of the elements in this list (in proper
638	–	* sequence), starting at the specified position in the list.
639	–	* Obeys the general contract of <tt>List.listIterator(int)</tt>.<p>
640	–	*
641	–	* The list-iterator is <i>fail-fast</i>: if the list is structurally
642	–	* modified at any time after the Iterator is created, in any way except
643	–	* through the list-iterator's own <tt>remove</tt> or <tt>add</tt>
644	–	* methods, the list-iterator will throw a
645	–	* <tt>ConcurrentModificationException</tt>.  Thus, in the face of
646	–	* concurrent modification, the iterator fails quickly and cleanly, rather
647	–	* than risking arbitrary, non-deterministic behavior at an undetermined
648	–	* time in the future.
649	–	*
650	–	* @param index index of the first element to be returned from the
651	–	*              list-iterator (by a call to <tt>next</tt>)
652	–	* @return a ListIterator of the elements in this list (in proper
653	–	*         sequence), starting at the specified position in the list
654	–	* @throws IndexOutOfBoundsException {@inheritDoc}
655	–	* @see List#listIterator(int)
656	–	*/
657	–	public ListIterator<E> listIterator(int index) {
658	–	if (index < 0 || index > size)
659	–	throw new IndexOutOfBoundsException("Index: "+index);
660	–	return new ArrayListIterator(index);
661	–	}
662	–
663	–	/**
664	–	* Returns an iterator over the elements in this list in proper sequence.
665	–	*
666	–	* @return an iterator over the elements in this list in proper sequence
667	–	*/
668	–	public Iterator<E> iterator() {
669	–	return new ArrayListIterator(0);
670	–	}
671	–
672	–	/**
673	–	* A streamlined version of AbstractList.Itr
674	–	*/
675	–	final class ArrayListIterator implements ListIterator<E> {
676	–	int cursor;           // index of next element to return;
677	–	int lastRet;          // index of last element, or -1 if no such
678	–	int expectedModCount; // to check for CME
679	–
680	–	ArrayListIterator(int index) {
681	–	cursor = index;
682	–	lastRet = -1;
683	–	expectedModCount = modCount;
684	–	}
685	–
686	–	public boolean hasNext() {
687	–	return cursor < size;
688	–	}
689	–
690	–	public boolean hasPrevious() {
691	–	return cursor > 0;
692	–	}
693	–
694	–	public int nextIndex() {
695	–	return cursor;
696	–	}
697	–
698	–	public int previousIndex() {
699	–	return cursor - 1;
700	–	}
701	–
702	–	public E next() {
703	–	if (expectedModCount == modCount) {
704	–	int i = cursor;
705	–	if (i < size) {
706	–	try {
707	–	E e = (E)elementData[i];
708	–	lastRet = i;
709	–	cursor = i + 1;
710	–	return e;
711	–	} catch (IndexOutOfBoundsException fallthrough) {
712	–	}
713	–	}
714	–	}
715	–	// Prefer reporting CME if applicable on failures
716	–	if (expectedModCount == modCount)
717	–	throw new NoSuchElementException();
718	–	throw new ConcurrentModificationException();
719	–	}
720	–
721	–	public E previous() {
722	–	if (expectedModCount == modCount) {
723	–	int i = cursor - 1;
724	–	if (i < size) {
725	–	try {
726	–	E e = (E)elementData[i];
727	–	lastRet = i;
728	–	cursor = i;
729	–	return e;
730	–	} catch (IndexOutOfBoundsException fallthrough) {
731	–	}
732	–	}
733	–	}
734	–	if (expectedModCount == modCount)
735	–	throw new NoSuchElementException();
736	–	throw new ConcurrentModificationException();
737	–	}
738	–
739	–	public void remove() {
740	–	if (lastRet < 0)
741	–	throw new IllegalStateException();
742	–	if (modCount != expectedModCount)
743	–	throw new ConcurrentModificationException();
744	–	ArrayList.this.remove(lastRet);
745	–	if (lastRet < cursor)
746	–	cursor--;
747	–	lastRet = -1;
748	–	expectedModCount = modCount;
749	–	}
750	–
751	–	public void set(E e) {
752	–	if (lastRet < 0)
753	–	throw new IllegalStateException();
754	–	if (modCount != expectedModCount)
755	–	throw new ConcurrentModificationException();
756	–	ArrayList.this.set(lastRet, e);
757	–	expectedModCount = modCount;
758	–	}
759	–
760	–	public void add(E e) {
761	–	if (modCount != expectedModCount)
762	–	throw new ConcurrentModificationException();
763	–	ArrayList.this.add(cursor++, e);
764	–	lastRet = -1;
765	–	expectedModCount = modCount;
766	–	}
767	–	}
768	–
607		}

Diff Legend

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