ViewVC Help

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

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

Comparing jsr166/src/main/java/util/AbstractList.java (file contents):
Revision 1.17 by jsr166, Sun May 20 07:54:01 2007 UTC vs.
Revision 1.18 by jsr166, Tue Sep 11 15:24:16 2007 UTC

#	Line 1 | Line 1
1		/*
2	<	* Copyright 1997-2006 Sun Microsystems, Inc.  All Rights Reserved.
2	>	* Copyright 1997-2007 Sun Microsystems, Inc.  All Rights Reserved.
3		* DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
4		*
5		* This code is free software; you can redistribute it and/or modify it
#	Line 255 | Line 255 | public abstract class AbstractList<E> ex
255		* @throws IndexOutOfBoundsException     {@inheritDoc}
256		*/
257		public boolean addAll(int index, Collection<? extends E> c) {
258	+	rangeCheckForAdd(index);
259		boolean modified = false;
260		Iterator<? extends E> e = c.iterator();
261		while (e.hasNext()) {
#	Line 275 | Line 276 | public abstract class AbstractList<E> ex
276		* {@code get(int)}, and {@code remove(int)} methods.
277		*
278		* <p>Note that the iterator returned by this method will throw an
279	<	* {@code UnsupportedOperationException} in response to its
279	>	* {@link UnsupportedOperationException} in response to its
280		* {@code remove} method unless the list's {@code remove(int)} method is
281		* overridden.
282		*
283		* <p>This implementation can be made to throw runtime exceptions in the
284		* face of concurrent modification, as described in the specification
285	<	* for the (protected) {@code modCount} field.
285	>	* for the (protected) {@link #modCount} field.
286		*
287		* @return an iterator over the elements in this list in proper sequence
287	–	*
288	–	* @see #modCount
288		*/
289		public Iterator<E> iterator() {
290		return new Itr();
#	Line 313 | Line 312 | public abstract class AbstractList<E> ex
312		* and {@code remove(int)} methods.
313		*
314		* <p>Note that the list iterator returned by this implementation will
315	<	* throw an {@code UnsupportedOperationException} in response to its
315	>	* throw an {@link UnsupportedOperationException} in response to its
316		* {@code remove}, {@code set} and {@code add} methods unless the
317		* list's {@code remove(int)}, {@code set(int, E)}, and
318		* {@code add(int, E)} methods are overridden.
319		*
320		* <p>This implementation can be made to throw runtime exceptions in the
321		* face of concurrent modification, as described in the specification for
322	<	* the (protected) {@code modCount} field.
322	>	* the (protected) {@link #modCount} field.
323		*
324		* @throws IndexOutOfBoundsException {@inheritDoc}
326	–	*
327	–	* @see #modCount
325		*/
326		public ListIterator<E> listIterator(final int index) {
327	<	if (index<0 || index>size())
331	<	throw new IndexOutOfBoundsException("Index: "+index);
327	>	rangeCheckForAdd(index);
328
329		return new ListItr(index);
330		}
#	Line 360 | Line 356 | public abstract class AbstractList<E> ex
356		public E next() {
357		checkForComodification();
358		try {
359	<	E next = get(cursor);
360	<	lastRet = cursor++;
359	>	int i = cursor;
360	>	E next = get(i);
361	>	lastRet = i;
362	>	cursor = i + 1;
363		return next;
364		} catch (IndexOutOfBoundsException e) {
365		checkForComodification();
#	Line 370 | Line 368 | public abstract class AbstractList<E> ex
368		}
369
370		public void remove() {
371	<	if (lastRet == -1)
371	>	if (lastRet < 0)
372		throw new IllegalStateException();
373		checkForComodification();
374
#	Line 422 | Line 420 | public abstract class AbstractList<E> ex
420		}
421
422		public void set(E e) {
423	<	if (lastRet == -1)
423	>	if (lastRet < 0)
424		throw new IllegalStateException();
425		checkForComodification();
426
#	Line 438 | Line 436 | public abstract class AbstractList<E> ex
436		checkForComodification();
437
438		try {
439	<	int i = cursor;
439	>	int i = cursor;
440		AbstractList.this.add(i, e);
443	–	cursor = i + 1;
441		lastRet = -1;
442	+	cursor = i + 1;
443		expectedModCount = modCount;
444		} catch (IndexOutOfBoundsException ex) {
445		throw new ConcurrentModificationException();
#	Line 479 | Line 477 | public abstract class AbstractList<E> ex
477		* the backing list is equal to its expected value, and throw a
478		* {@code ConcurrentModificationException} if it is not.
479		*
480	<	* @throws IndexOutOfBoundsException endpoint index value out of range
480	>	* @throws IndexOutOfBoundsException if an endpoint index value is out of range
481		*         {@code (fromIndex < 0 || toIndex > size)}
482		* @throws IllegalArgumentException if the endpoint indices are out of order
483		*         {@code (fromIndex > toIndex)}
484		*/
485		public List<E> subList(int fromIndex, int toIndex) {
486		return (this instanceof RandomAccess ?
487	<	new RandomAccessSubList(this, this, fromIndex, fromIndex, toIndex) :
488	<	new SubList(this, this, fromIndex, fromIndex, toIndex));
487	>	new RandomAccessSubList<E>(this, fromIndex, toIndex) :
488	>	new SubList<E>(this, fromIndex, toIndex));
489		}
490
491		// Comparison and hashing
#	Line 499 | Line 497 | public abstract class AbstractList<E> ex
497		* the two lists are <i>equal</i>.  (Two elements {@code e1} and
498		* {@code e2} are <i>equal</i> if {@code (e1==null ? e2==null :
499		* e1.equals(e2))}.)  In other words, two lists are defined to be
500	<	* equal if they contain the same elements in the same order.
500	>	* equal if they contain the same elements in the same order.<p>
501		*
502	<	* <p>This implementation first checks if the specified object is this
502	>	* This implementation first checks if the specified object is this
503		* list. If so, it returns {@code true}; if not, it checks if the
504		* specified object is a list. If not, it returns {@code false}; if so,
505		* it iterates over both lists, comparing corresponding pairs of elements.
#	Line 541 | Line 539 | public abstract class AbstractList<E> ex
539		*/
540		public int hashCode() {
541		int hashCode = 1;
542	<	Iterator<E> i = iterator();
543	<	while (i.hasNext()) {
546	<	E obj = i.next();
547	<	hashCode = 31*hashCode + (obj==null ? 0 : obj.hashCode());
548	<	}
542	>	for (E e : this)
543	>	hashCode = 31*hashCode + (e==null ? 0 : e.hashCode());
544		return hashCode;
545		}
546
#	Line 553 | Line 548 | public abstract class AbstractList<E> ex
548		* Removes from this list all of the elements whose index is between
549		* {@code fromIndex}, inclusive, and {@code toIndex}, exclusive.
550		* Shifts any succeeding elements to the left (reduces their index).
551	<	* This call shortens the ArrayList by {@code (toIndex - fromIndex)}
552	<	* elements.  (If {@code toIndex==fromIndex}, this operation has no
558	<	* effect.)
551	>	* This call shortens the list by {@code (toIndex - fromIndex)} elements.
552	>	* (If {@code toIndex==fromIndex}, this operation has no effect.)
553		*
554		* <p>This method is called by the {@code clear} operation on this list
555		* and its subLists.  Overriding this method to take advantage of
#	Line 607 | Line 601 | public abstract class AbstractList<E> ex
601		* ignored.
602		*/
603		protected transient int modCount = 0;
604	+
605	+	private void rangeCheckForAdd(int index) {
606	+	if (index < 0 || index > size())
607	+	throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
608	+	}
609	+
610	+	private String outOfBoundsMsg(int index) {
611	+	return "Index: "+index+", Size: "+size();
612	+	}
613		}
614
612	–	/**
613	–	* Generic sublists. Non-nested to enable construction by other
614	–	* classes in this package.
615	–	*/
615		class SubList<E> extends AbstractList<E> {
616	<	/*
617	<	* A SubList has both a "base", the ultimate backing list, as well
618	<	* as a "parent", which is the list or sublist creating this
619	<	* sublist. All methods that may cause structural modifications
620	<	* must propagate through the parent link, with O(k) performance
622	<	* where k is sublist depth. For example in the case of a
623	<	* sub-sub-list, invoking remove(x) will result in a chain of
624	<	* three remove calls. However, all other non-structurally
625	<	* modifying methods can bypass this chain, and relay directly to
626	<	* the base list. In particular, doing so signficantly speeds up
627	<	* the performance of iterators for deeply-nested sublists.
628	<	*/
629	<	final AbstractList<E> base;   // Backing list
630	<	final AbstractList<E> parent; // Parent list
631	<	final int baseOffset;         // index wrt base
632	<	final int parentOffset;       // index wrt parent
633	<	int length;                   // Number of elements in this sublist
634	<
635	<	SubList(AbstractList<E> base,
636	<	AbstractList<E> parent,
637	<	int baseIndex,
638	<	int fromIndex,
639	<	int toIndex) {
616	>	private final AbstractList<E> l;
617	>	private final int offset;
618	>	private int size;
619	>
620	>	SubList(AbstractList<E> list, int fromIndex, int toIndex) {
621		if (fromIndex < 0)
622		throw new IndexOutOfBoundsException("fromIndex = " + fromIndex);
623	<	if (toIndex > parent.size())
623	>	if (toIndex > list.size())
624		throw new IndexOutOfBoundsException("toIndex = " + toIndex);
625		if (fromIndex > toIndex)
626		throw new IllegalArgumentException("fromIndex(" + fromIndex +
627		") > toIndex(" + toIndex + ")");
628	<	this.base = base;
629	<	this.parent = parent;
630	<	this.baseOffset = baseIndex;
631	<	this.parentOffset = fromIndex;
651	<	this.length = toIndex - fromIndex;
652	<	this.modCount = base.modCount;
653	<	}
654	<
655	<	/**
656	<	* Returns an IndexOutOfBoundsException with nicer message
657	<	*/
658	<	private IndexOutOfBoundsException indexError(int index) {
659	<	return new IndexOutOfBoundsException("Index: " + index +
660	<	", Size: " + length);
628	>	l = list;
629	>	offset = fromIndex;
630	>	size = toIndex - fromIndex;
631	>	this.modCount = l.modCount;
632		}
633
634		public E set(int index, E element) {
635	<	if (index < 0 || index >= length)
636	<	throw indexError(index);
637	<	if (base.modCount != modCount)
667	<	throw new ConcurrentModificationException();
668	<	return base.set(index + baseOffset, element);
635	>	rangeCheck(index);
636	>	checkForComodification();
637	>	return l.set(index+offset, element);
638		}
639
640		public E get(int index) {
641	<	if (index < 0 || index >= length)
642	<	throw indexError(index);
643	<	if (base.modCount != modCount)
675	<	throw new ConcurrentModificationException();
676	<	return base.get(index + baseOffset);
641	>	rangeCheck(index);
642	>	checkForComodification();
643	>	return l.get(index+offset);
644		}
645
646		public int size() {
647	<	if (base.modCount != modCount)
648	<	throw new ConcurrentModificationException();
682	<	return length;
647	>	checkForComodification();
648	>	return size;
649		}
650
651		public void add(int index, E element) {
652	<	if (index < 0 || index>length)
653	<	throw indexError(index);
654	<	if (base.modCount != modCount)
655	<	throw new ConcurrentModificationException();
656	<	parent.add(index + parentOffset, element);
691	<	length++;
692	<	modCount = base.modCount;
652	>	rangeCheckForAdd(index);
653	>	checkForComodification();
654	>	l.add(index+offset, element);
655	>	this.modCount = l.modCount;
656	>	size++;
657		}
658
659		public E remove(int index) {
660	<	if (index < 0 || index >= length)
661	<	throw indexError(index);
662	<	if (base.modCount != modCount)
663	<	throw new ConcurrentModificationException();
664	<	E result = parent.remove(index + parentOffset);
701	<	length--;
702	<	modCount = base.modCount;
660	>	rangeCheck(index);
661	>	checkForComodification();
662	>	E result = l.remove(index+offset);
663	>	this.modCount = l.modCount;
664	>	size--;
665		return result;
666		}
667
668		protected void removeRange(int fromIndex, int toIndex) {
669	<	if (base.modCount != modCount)
670	<	throw new ConcurrentModificationException();
671	<	parent.removeRange(fromIndex + parentOffset, toIndex + parentOffset);
672	<	length -= (toIndex-fromIndex);
711	<	modCount = base.modCount;
669	>	checkForComodification();
670	>	l.removeRange(fromIndex+offset, toIndex+offset);
671	>	this.modCount = l.modCount;
672	>	size -= (toIndex-fromIndex);
673		}
674
675		public boolean addAll(Collection<? extends E> c) {
676	<	return addAll(length, c);
676	>	return addAll(size, c);
677		}
678
679		public boolean addAll(int index, Collection<? extends E> c) {
680	<	if (index < 0 || index > length)
720	<	throw indexError(index);
680	>	rangeCheckForAdd(index);
681		int cSize = c.size();
682		if (cSize==0)
683		return false;
684
685	<	if (base.modCount != modCount)
686	<	throw new ConcurrentModificationException();
687	<	parent.addAll(parentOffset + index, c);
688	<	length += cSize;
729	<	modCount = base.modCount;
685	>	checkForComodification();
686	>	l.addAll(offset+index, c);
687	>	this.modCount = l.modCount;
688	>	size += cSize;
689		return true;
690		}
691
733	–	public List<E> subList(int fromIndex, int toIndex) {
734	–	return new SubList(base, this, fromIndex + baseOffset,
735	–	fromIndex, toIndex);
736	–	}
737	–
692		public Iterator<E> iterator() {
693	<	return new SubListIterator(this, 0);
693	>	return listIterator();
694		}
695
696	<	public ListIterator<E> listIterator() {
697	<	return new SubListIterator(this, 0);
698	<	}
745	<
746	<	public ListIterator<E> listIterator(int index) {
747	<	if (index < 0 || index>length)
748	<	throw indexError(index);
749	<	return new SubListIterator(this, index);
750	<	}
696	>	public ListIterator<E> listIterator(final int index) {
697	>	checkForComodification();
698	>	rangeCheckForAdd(index);
699
700	<	/**
701	<	* Generic sublist iterator obeying fastfail semantics via
754	<	* modCount.  The hasNext and next methods locally check for
755	<	* in-range indices before relaying to backing list to get
756	<	* element. If this either encounters an unexpected modCount or
757	<	* fails, the backing list must have been concurrently modified,
758	<	* and is so reported.  The add and remove methods performing
759	<	* structural modifications instead relay them through the
760	<	* sublist.
761	<	*/
762	<	private static final class SubListIterator<E> implements ListIterator<E> {
763	<	final SubList<E> outer;       // Sublist creating this iteraor
764	<	final AbstractList<E> base;   // base list
765	<	final int offset;             // Cursor offset wrt base
766	<	int cursor;                   // Current index
767	<	int fence;                    // Upper bound on cursor
768	<	int lastRet;                  // Index of returned element, or -1
769	<	int expectedModCount;         // Expected modCount of base
770	<
771	<	SubListIterator(SubList<E> list, int index) {
772	<	this.lastRet = -1;
773	<	this.cursor = index;
774	<	this.outer = list;
775	<	this.offset = list.baseOffset;
776	<	this.fence = list.length;
777	<	this.base = list.base;
778	<	this.expectedModCount = base.modCount;
779	<	}
700	>	return new ListIterator<E>() {
701	>	private final ListIterator<E> i = l.listIterator(index+offset);
702
703	<	public boolean hasNext() {
704	<	return cursor < fence;
705	<	}
703	>	public boolean hasNext() {
704	>	return nextIndex() < size;
705	>	}
706
707	<	public boolean hasPrevious() {
708	<	return cursor > 0;
709	<	}
707	>	public E next() {
708	>	if (hasNext())
709	>	return i.next();
710	>	else
711	>	throw new NoSuchElementException();
712	>	}
713
714	<	public int nextIndex() {
715	<	return cursor;
716	<	}
714	>	public boolean hasPrevious() {
715	>	return previousIndex() >= 0;
716	>	}
717
718	<	public int previousIndex() {
719	<	return cursor - 1;
720	<	}
718	>	public E previous() {
719	>	if (hasPrevious())
720	>	return i.previous();
721	>	else
722	>	throw new NoSuchElementException();
723	>	}
724
725	<	public E next() {
726	<	int i = cursor;
799	<	if (cursor >= fence)
800	<	throw new NoSuchElementException();
801	<	if (expectedModCount == base.modCount) {
802	<	try {
803	<	Object next = base.get(i + offset);
804	<	lastRet = i;
805	<	cursor = i + 1;
806	<	return (E)next;
807	<	} catch (IndexOutOfBoundsException fallThrough) {
808	<	}
725	>	public int nextIndex() {
726	>	return i.nextIndex() - offset;
727		}
810	–	throw new ConcurrentModificationException();
811	–	}
728
729	<	public E previous() {
730	<	int i = cursor - 1;
815	<	if (i < 0)
816	<	throw new NoSuchElementException();
817	<	if (expectedModCount == base.modCount) {
818	<	try {
819	<	Object prev = base.get(i + offset);
820	<	lastRet = i;
821	<	cursor = i;
822	<	return (E)prev;
823	<	} catch (IndexOutOfBoundsException fallThrough) {
824	<	}
729	>	public int previousIndex() {
730	>	return i.previousIndex() - offset;
731		}
826	–	throw new ConcurrentModificationException();
827	–	}
732
733	<	public void set(E e) {
734	<	if (lastRet < 0)
735	<	throw new IllegalStateException();
736	<	if (expectedModCount != base.modCount)
833	<	throw new ConcurrentModificationException();
834	<	try {
835	<	outer.set(lastRet, e);
836	<	expectedModCount = base.modCount;
837	<	} catch (IndexOutOfBoundsException ex) {
838	<	throw new ConcurrentModificationException();
733	>	public void remove() {
734	>	i.remove();
735	>	SubList.this.modCount = l.modCount;
736	>	size--;
737		}
840	–	}
738
739	<	public void remove() {
740	<	int i = lastRet;
844	<	if (i < 0)
845	<	throw new IllegalStateException();
846	<	if (expectedModCount != base.modCount)
847	<	throw new ConcurrentModificationException();
848	<	try {
849	<	outer.remove(i);
850	<	if (i < cursor)
851	<	cursor--;
852	<	lastRet = -1;
853	<	fence = outer.length;
854	<	expectedModCount = base.modCount;
855	<	} catch (IndexOutOfBoundsException ex) {
856	<	throw new ConcurrentModificationException();
739	>	public void set(E e) {
740	>	i.set(e);
741		}
858	–	}
742
743	<	public void add(E e) {
744	<	if (expectedModCount != base.modCount)
745	<	throw new ConcurrentModificationException();
746	<	try {
864	<	int i = cursor;
865	<	outer.add(i, e);
866	<	cursor = i + 1;
867	<	lastRet = -1;
868	<	fence = outer.length;
869	<	expectedModCount = base.modCount;
870	<	} catch (IndexOutOfBoundsException ex) {
871	<	throw new ConcurrentModificationException();
743	>	public void add(E e) {
744	>	i.add(e);
745	>	SubList.this.modCount = l.modCount;
746	>	size++;
747		}
748	<	}
748	>	};
749		}
750
751	+	public List<E> subList(int fromIndex, int toIndex) {
752	+	return new SubList<E>(this, fromIndex, toIndex);
753	+	}
754	+
755	+	private void rangeCheck(int index) {
756	+	if (index < 0 || index >= size)
757	+	throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
758	+	}
759	+
760	+	private void rangeCheckForAdd(int index) {
761	+	if (index < 0 || index > size)
762	+	throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
763	+	}
764	+
765	+	private String outOfBoundsMsg(int index) {
766	+	return "Index: "+index+", Size: "+size;
767	+	}
768	+
769	+	private void checkForComodification() {
770	+	if (this.modCount != l.modCount)
771	+	throw new ConcurrentModificationException();
772	+	}
773		}
774
775		class RandomAccessSubList<E> extends SubList<E> implements RandomAccess {
776	<	RandomAccessSubList(AbstractList<E> base,
777	<	AbstractList<E> parent, int baseIndex,
881	<	int fromIndex, int toIndex) {
882	<	super(base, parent, baseIndex, fromIndex, toIndex);
776	>	RandomAccessSubList(AbstractList<E> list, int fromIndex, int toIndex) {
777	>	super(list, fromIndex, toIndex);
778		}
779
780		public List<E> subList(int fromIndex, int toIndex) {
781	<	return new RandomAccessSubList(base, this, fromIndex + baseOffset,
887	<	fromIndex, toIndex);
781	>	return new RandomAccessSubList<E>(this, fromIndex, toIndex);
782		}
783		}

Diff Legend

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