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 |
|
|
39 |
|
* collection being implemented admits a more efficient implementation.<p> |
40 |
|
* |
41 |
|
* This class is a member of the |
42 |
< |
* <a href="{@docRoot}/../guide/collections/index.html"> |
42 |
> |
* <a href="{@docRoot}/../technotes/guides/collections/index.html"> |
43 |
|
* Java Collections Framework</a>. |
44 |
|
* |
45 |
|
* @author Josh Bloch |
46 |
|
* @author Neal Gafter |
47 |
< |
* @version 1.37, 01/18/03 |
47 |
> |
* @version %I%, %G% |
48 |
|
* @see Collection |
49 |
|
* @see List |
50 |
|
* @see AbstractSequentialList |
342 |
|
} |
343 |
|
|
344 |
|
public E next() { |
345 |
< |
try { |
346 |
< |
int i = cursor; |
347 |
< |
E next = get(i); |
348 |
< |
lastRet = i; |
349 |
< |
cursor = i + 1; |
350 |
< |
return next; |
351 |
< |
} catch (IndexOutOfBoundsException ex) { |
352 |
< |
throw new NoSuchElementException(); |
353 |
< |
} finally { |
354 |
< |
if (expectedModCount != modCount) |
355 |
< |
throw new ConcurrentModificationException(); |
356 |
< |
} |
345 |
> |
checkForComodification(); |
346 |
> |
try { |
347 |
> |
E next = get(cursor); |
348 |
> |
lastRet = cursor++; |
349 |
> |
return next; |
350 |
> |
} catch (IndexOutOfBoundsException e) { |
351 |
> |
checkForComodification(); |
352 |
> |
throw new NoSuchElementException(); |
353 |
> |
} |
354 |
|
} |
355 |
|
|
356 |
|
public void remove() { |
357 |
|
if (lastRet == -1) |
358 |
|
throw new IllegalStateException(); |
359 |
< |
if (expectedModCount != modCount) |
360 |
< |
throw new ConcurrentModificationException(); |
359 |
> |
checkForComodification(); |
360 |
> |
|
361 |
|
try { |
362 |
|
AbstractList.this.remove(lastRet); |
363 |
|
if (lastRet < cursor) |
368 |
|
throw new ConcurrentModificationException(); |
369 |
|
} |
370 |
|
} |
371 |
+ |
|
372 |
+ |
final void checkForComodification() { |
373 |
+ |
if (modCount != expectedModCount) |
374 |
+ |
throw new ConcurrentModificationException(); |
375 |
+ |
} |
376 |
|
} |
377 |
< |
|
377 |
> |
|
378 |
|
private class ListItr extends Itr implements ListIterator<E> { |
379 |
|
ListItr(int index) { |
380 |
|
cursor = index; |
384 |
|
return cursor != 0; |
385 |
|
} |
386 |
|
|
385 |
– |
public int nextIndex() { |
386 |
– |
return cursor; |
387 |
– |
} |
388 |
– |
|
389 |
– |
public int previousIndex() { |
390 |
– |
return cursor - 1; |
391 |
– |
} |
392 |
– |
|
387 |
|
public E previous() { |
388 |
+ |
checkForComodification(); |
389 |
|
try { |
390 |
|
int i = cursor - 1; |
391 |
< |
E prev = get(i); |
392 |
< |
lastRet = i; |
393 |
< |
cursor = i; |
394 |
< |
return prev; |
395 |
< |
} catch (IndexOutOfBoundsException ex) { |
391 |
> |
E previous = get(i); |
392 |
> |
lastRet = cursor = i; |
393 |
> |
return previous; |
394 |
> |
} catch (IndexOutOfBoundsException e) { |
395 |
> |
checkForComodification(); |
396 |
|
throw new NoSuchElementException(); |
402 |
– |
} finally { |
403 |
– |
if (expectedModCount != modCount) |
404 |
– |
throw new ConcurrentModificationException(); |
397 |
|
} |
398 |
|
} |
399 |
|
|
400 |
+ |
public int nextIndex() { |
401 |
+ |
return cursor; |
402 |
+ |
} |
403 |
+ |
|
404 |
+ |
public int previousIndex() { |
405 |
+ |
return cursor-1; |
406 |
+ |
} |
407 |
+ |
|
408 |
|
public void set(E e) { |
409 |
|
if (lastRet == -1) |
410 |
|
throw new IllegalStateException(); |
411 |
< |
if (expectedModCount != modCount) |
412 |
< |
throw new ConcurrentModificationException(); |
411 |
> |
checkForComodification(); |
412 |
> |
|
413 |
|
try { |
414 |
|
AbstractList.this.set(lastRet, e); |
415 |
|
expectedModCount = modCount; |
419 |
|
} |
420 |
|
|
421 |
|
public void add(E e) { |
422 |
< |
if (expectedModCount != modCount) |
423 |
< |
throw new ConcurrentModificationException(); |
422 |
> |
checkForComodification(); |
423 |
> |
|
424 |
|
try { |
425 |
|
int i = cursor; |
426 |
|
AbstractList.this.add(i, e); |
470 |
|
*/ |
471 |
|
public List<E> subList(int fromIndex, int toIndex) { |
472 |
|
return (this instanceof RandomAccess ? |
473 |
< |
new RandomAccessSubList<E>(this, fromIndex, toIndex) : |
474 |
< |
new SubList<E>(this, fromIndex, toIndex)); |
473 |
> |
new RandomAccessSubList(this, this, fromIndex, fromIndex, toIndex) : |
474 |
> |
new SubList(this, this, fromIndex, fromIndex, toIndex)); |
475 |
|
} |
476 |
|
|
477 |
|
// Comparison and hashing |
593 |
|
protected transient int modCount = 0; |
594 |
|
} |
595 |
|
|
596 |
+ |
/** |
597 |
+ |
* Generic sublists. Non-nested to enable construction by other |
598 |
+ |
* classes in this package. |
599 |
+ |
*/ |
600 |
|
class SubList<E> extends AbstractList<E> { |
601 |
< |
private AbstractList<E> l; |
602 |
< |
private int offset; |
603 |
< |
private int size; |
604 |
< |
private int expectedModCount; |
605 |
< |
|
606 |
< |
SubList(AbstractList<E> list, int fromIndex, int toIndex) { |
601 |
> |
/* |
602 |
> |
* A SubList has both a "base", the ultimate backing list, as well |
603 |
> |
* as a "parent", which is the list or sublist creating this |
604 |
> |
* sublist. All methods that may cause structural modifications |
605 |
> |
* must propagate through the parent link, with O(k) performance |
606 |
> |
* where k is sublist depth. For example in the case of a |
607 |
> |
* sub-sub-list, invoking remove(x) will result in a chain of |
608 |
> |
* three remove calls. However, all other non-structurally |
609 |
> |
* modifying methods can bypass this chain, and relay directly to |
610 |
> |
* the base list. In particular, doing so signficantly speeds up |
611 |
> |
* the performance of iterators for deeply-nested sublists. |
612 |
> |
*/ |
613 |
> |
final AbstractList<E> base; // Backing list |
614 |
> |
final AbstractList<E> parent; // Parent list |
615 |
> |
final int baseOffset; // index wrt base |
616 |
> |
final int parentOffset; // index wrt parent |
617 |
> |
int length; // Number of elements in this sublist |
618 |
> |
|
619 |
> |
SubList(AbstractList<E> base, |
620 |
> |
AbstractList<E> parent, |
621 |
> |
int baseIndex, |
622 |
> |
int fromIndex, |
623 |
> |
int toIndex) { |
624 |
|
if (fromIndex < 0) |
625 |
|
throw new IndexOutOfBoundsException("fromIndex = " + fromIndex); |
626 |
< |
if (toIndex > list.size()) |
626 |
> |
if (toIndex > parent.size()) |
627 |
|
throw new IndexOutOfBoundsException("toIndex = " + toIndex); |
628 |
|
if (fromIndex > toIndex) |
629 |
|
throw new IllegalArgumentException("fromIndex(" + fromIndex + |
630 |
|
") > toIndex(" + toIndex + ")"); |
631 |
< |
l = list; |
632 |
< |
offset = fromIndex; |
633 |
< |
size = toIndex - fromIndex; |
634 |
< |
expectedModCount = l.modCount; |
631 |
> |
this.base = base; |
632 |
> |
this.parent = parent; |
633 |
> |
this.baseOffset = baseIndex; |
634 |
> |
this.parentOffset = fromIndex; |
635 |
> |
this.length = toIndex - fromIndex; |
636 |
> |
this.modCount = base.modCount; |
637 |
> |
} |
638 |
> |
|
639 |
> |
/** |
640 |
> |
* Returns an IndexOutOfBoundsException with nicer message |
641 |
> |
*/ |
642 |
> |
private IndexOutOfBoundsException indexError(int index) { |
643 |
> |
return new IndexOutOfBoundsException("Index: " + index + |
644 |
> |
", Size: " + length); |
645 |
|
} |
646 |
|
|
647 |
|
public E set(int index, E element) { |
648 |
< |
rangeCheck(index); |
649 |
< |
checkForComodification(); |
650 |
< |
return l.set(index+offset, element); |
648 |
> |
if (index < 0 || index >= length) |
649 |
> |
throw indexError(index); |
650 |
> |
if (base.modCount != modCount) |
651 |
> |
throw new ConcurrentModificationException(); |
652 |
> |
return base.set(index + baseOffset, element); |
653 |
|
} |
654 |
|
|
655 |
|
public E get(int index) { |
656 |
< |
rangeCheck(index); |
657 |
< |
checkForComodification(); |
658 |
< |
return l.get(index+offset); |
656 |
> |
if (index < 0 || index >= length) |
657 |
> |
throw indexError(index); |
658 |
> |
if (base.modCount != modCount) |
659 |
> |
throw new ConcurrentModificationException(); |
660 |
> |
return base.get(index + baseOffset); |
661 |
|
} |
662 |
|
|
663 |
|
public int size() { |
664 |
< |
checkForComodification(); |
665 |
< |
return size; |
664 |
> |
if (base.modCount != modCount) |
665 |
> |
throw new ConcurrentModificationException(); |
666 |
> |
return length; |
667 |
|
} |
668 |
|
|
669 |
|
public void add(int index, E element) { |
670 |
< |
if (index<0 || index>size) |
671 |
< |
throw new IndexOutOfBoundsException(); |
672 |
< |
checkForComodification(); |
673 |
< |
l.add(index+offset, element); |
674 |
< |
expectedModCount = l.modCount; |
675 |
< |
size++; |
676 |
< |
modCount++; |
670 |
> |
if (index < 0 || index>length) |
671 |
> |
throw indexError(index); |
672 |
> |
if (base.modCount != modCount) |
673 |
> |
throw new ConcurrentModificationException(); |
674 |
> |
parent.add(index + parentOffset, element); |
675 |
> |
length++; |
676 |
> |
modCount = base.modCount; |
677 |
|
} |
678 |
|
|
679 |
|
public E remove(int index) { |
680 |
< |
rangeCheck(index); |
681 |
< |
checkForComodification(); |
682 |
< |
E result = l.remove(index+offset); |
683 |
< |
expectedModCount = l.modCount; |
684 |
< |
size--; |
685 |
< |
modCount++; |
680 |
> |
if (index < 0 || index >= length) |
681 |
> |
throw indexError(index); |
682 |
> |
if (base.modCount != modCount) |
683 |
> |
throw new ConcurrentModificationException(); |
684 |
> |
E result = parent.remove(index + parentOffset); |
685 |
> |
length--; |
686 |
> |
modCount = base.modCount; |
687 |
|
return result; |
688 |
|
} |
689 |
|
|
690 |
|
protected void removeRange(int fromIndex, int toIndex) { |
691 |
< |
checkForComodification(); |
692 |
< |
l.removeRange(fromIndex+offset, toIndex+offset); |
693 |
< |
expectedModCount = l.modCount; |
694 |
< |
size -= (toIndex-fromIndex); |
695 |
< |
modCount++; |
691 |
> |
if (base.modCount != modCount) |
692 |
> |
throw new ConcurrentModificationException(); |
693 |
> |
parent.removeRange(fromIndex + parentOffset, toIndex + parentOffset); |
694 |
> |
length -= (toIndex-fromIndex); |
695 |
> |
modCount = base.modCount; |
696 |
|
} |
697 |
|
|
698 |
|
public boolean addAll(Collection<? extends E> c) { |
699 |
< |
return addAll(size, c); |
699 |
> |
return addAll(length, c); |
700 |
|
} |
701 |
|
|
702 |
|
public boolean addAll(int index, Collection<? extends E> c) { |
703 |
< |
if (index<0 || index>size) |
704 |
< |
throw new IndexOutOfBoundsException( |
668 |
< |
"Index: "+index+", Size: "+size); |
703 |
> |
if (index < 0 || index > length) |
704 |
> |
throw indexError(index); |
705 |
|
int cSize = c.size(); |
706 |
|
if (cSize==0) |
707 |
|
return false; |
708 |
|
|
709 |
< |
checkForComodification(); |
710 |
< |
l.addAll(offset+index, c); |
711 |
< |
expectedModCount = l.modCount; |
712 |
< |
size += cSize; |
713 |
< |
modCount++; |
709 |
> |
if (base.modCount != modCount) |
710 |
> |
throw new ConcurrentModificationException(); |
711 |
> |
parent.addAll(parentOffset + index, c); |
712 |
> |
length += cSize; |
713 |
> |
modCount = base.modCount; |
714 |
|
return true; |
715 |
|
} |
716 |
|
|
717 |
+ |
public List<E> subList(int fromIndex, int toIndex) { |
718 |
+ |
return new SubList(base, this, fromIndex + baseOffset, |
719 |
+ |
fromIndex, toIndex); |
720 |
+ |
} |
721 |
+ |
|
722 |
|
public Iterator<E> iterator() { |
723 |
< |
return listIterator(); |
723 |
> |
return new SubListIterator(this, 0); |
724 |
|
} |
725 |
|
|
726 |
< |
public ListIterator<E> listIterator(final int index) { |
727 |
< |
checkForComodification(); |
728 |
< |
if (index<0 || index>size) |
688 |
< |
throw new IndexOutOfBoundsException( |
689 |
< |
"Index: "+index+", Size: "+size); |
726 |
> |
public ListIterator<E> listIterator() { |
727 |
> |
return new SubListIterator(this, 0); |
728 |
> |
} |
729 |
|
|
730 |
< |
return new ListIterator<E>() { |
731 |
< |
private ListIterator<E> i = l.listIterator(index+offset); |
730 |
> |
public ListIterator<E> listIterator(int index) { |
731 |
> |
if (index < 0 || index>length) |
732 |
> |
throw indexError(index); |
733 |
> |
return new SubListIterator(this, index); |
734 |
> |
} |
735 |
|
|
736 |
< |
public boolean hasNext() { |
737 |
< |
return nextIndex() < size; |
738 |
< |
} |
736 |
> |
/** |
737 |
> |
* Generic sublist iterator obeying fastfail semantics via |
738 |
> |
* modCount. The hasNext and next methods locally check for |
739 |
> |
* in-range indices before relaying to backing list to get |
740 |
> |
* element. If this either encounters an unexpected modCount or |
741 |
> |
* fails, the backing list must have been concurrently modified, |
742 |
> |
* and is so reported. The add and remove methods performing |
743 |
> |
* structural modifications instead relay them through the |
744 |
> |
* sublist. |
745 |
> |
*/ |
746 |
> |
private static final class SubListIterator<E> implements ListIterator<E> { |
747 |
> |
final SubList<E> outer; // Sublist creating this iteraor |
748 |
> |
final AbstractList<E> base; // base list |
749 |
> |
final int offset; // Cursor offset wrt base |
750 |
> |
int cursor; // Current index |
751 |
> |
int fence; // Upper bound on cursor |
752 |
> |
int lastRet; // Index of returned element, or -1 |
753 |
> |
int expectedModCount; // Expected modCount of base |
754 |
> |
|
755 |
> |
SubListIterator(SubList<E> list, int index) { |
756 |
> |
this.lastRet = -1; |
757 |
> |
this.cursor = index; |
758 |
> |
this.outer = list; |
759 |
> |
this.offset = list.baseOffset; |
760 |
> |
this.fence = list.length; |
761 |
> |
this.base = list.base; |
762 |
> |
this.expectedModCount = base.modCount; |
763 |
> |
} |
764 |
|
|
765 |
< |
public E next() { |
766 |
< |
if (hasNext()) |
767 |
< |
return i.next(); |
701 |
< |
else |
702 |
< |
throw new NoSuchElementException(); |
703 |
< |
} |
765 |
> |
public boolean hasNext() { |
766 |
> |
return cursor < fence; |
767 |
> |
} |
768 |
|
|
769 |
< |
public boolean hasPrevious() { |
770 |
< |
return previousIndex() >= 0; |
771 |
< |
} |
769 |
> |
public boolean hasPrevious() { |
770 |
> |
return cursor > 0; |
771 |
> |
} |
772 |
|
|
773 |
< |
public E previous() { |
774 |
< |
if (hasPrevious()) |
775 |
< |
return i.previous(); |
712 |
< |
else |
713 |
< |
throw new NoSuchElementException(); |
714 |
< |
} |
773 |
> |
public int nextIndex() { |
774 |
> |
return cursor; |
775 |
> |
} |
776 |
|
|
777 |
< |
public int nextIndex() { |
778 |
< |
return i.nextIndex() - offset; |
779 |
< |
} |
777 |
> |
public int previousIndex() { |
778 |
> |
return cursor - 1; |
779 |
> |
} |
780 |
|
|
781 |
< |
public int previousIndex() { |
782 |
< |
return i.previousIndex() - offset; |
781 |
> |
public E next() { |
782 |
> |
int i = cursor; |
783 |
> |
if (cursor >= fence) |
784 |
> |
throw new NoSuchElementException(); |
785 |
> |
if (expectedModCount == base.modCount) { |
786 |
> |
try { |
787 |
> |
Object next = base.get(i + offset); |
788 |
> |
lastRet = i; |
789 |
> |
cursor = i + 1; |
790 |
> |
return (E)next; |
791 |
> |
} catch (IndexOutOfBoundsException fallThrough) { |
792 |
> |
} |
793 |
|
} |
794 |
+ |
throw new ConcurrentModificationException(); |
795 |
+ |
} |
796 |
|
|
797 |
< |
public void remove() { |
798 |
< |
i.remove(); |
799 |
< |
expectedModCount = l.modCount; |
800 |
< |
size--; |
801 |
< |
modCount++; |
797 |
> |
public E previous() { |
798 |
> |
int i = cursor - 1; |
799 |
> |
if (i < 0) |
800 |
> |
throw new NoSuchElementException(); |
801 |
> |
if (expectedModCount == base.modCount) { |
802 |
> |
try { |
803 |
> |
Object prev = base.get(i + offset); |
804 |
> |
lastRet = i; |
805 |
> |
cursor = i; |
806 |
> |
return (E)prev; |
807 |
> |
} catch (IndexOutOfBoundsException fallThrough) { |
808 |
> |
} |
809 |
|
} |
810 |
+ |
throw new ConcurrentModificationException(); |
811 |
+ |
} |
812 |
|
|
813 |
< |
public void set(E e) { |
814 |
< |
i.set(e); |
813 |
> |
public void set(E e) { |
814 |
> |
if (lastRet < 0) |
815 |
> |
throw new IllegalStateException(); |
816 |
> |
if (expectedModCount != base.modCount) |
817 |
> |
throw new ConcurrentModificationException(); |
818 |
> |
try { |
819 |
> |
outer.set(lastRet, e); |
820 |
> |
expectedModCount = base.modCount; |
821 |
> |
} catch (IndexOutOfBoundsException ex) { |
822 |
> |
throw new ConcurrentModificationException(); |
823 |
|
} |
824 |
+ |
} |
825 |
|
|
826 |
< |
public void add(E e) { |
827 |
< |
i.add(e); |
828 |
< |
expectedModCount = l.modCount; |
829 |
< |
size++; |
830 |
< |
modCount++; |
826 |
> |
public void remove() { |
827 |
> |
int i = lastRet; |
828 |
> |
if (i < 0) |
829 |
> |
throw new IllegalStateException(); |
830 |
> |
if (expectedModCount != base.modCount) |
831 |
> |
throw new ConcurrentModificationException(); |
832 |
> |
try { |
833 |
> |
outer.remove(i); |
834 |
> |
if (i < cursor) |
835 |
> |
cursor--; |
836 |
> |
lastRet = -1; |
837 |
> |
fence = outer.length; |
838 |
> |
expectedModCount = base.modCount; |
839 |
> |
} catch (IndexOutOfBoundsException ex) { |
840 |
> |
throw new ConcurrentModificationException(); |
841 |
|
} |
842 |
< |
}; |
742 |
< |
} |
743 |
< |
|
744 |
< |
public List<E> subList(int fromIndex, int toIndex) { |
745 |
< |
return new SubList<E>(this, fromIndex, toIndex); |
746 |
< |
} |
842 |
> |
} |
843 |
|
|
844 |
< |
private void rangeCheck(int index) { |
845 |
< |
if (index<0 || index>=size) |
846 |
< |
throw new IndexOutOfBoundsException("Index: "+index+ |
847 |
< |
",Size: "+size); |
844 |
> |
public void add(E e) { |
845 |
> |
if (expectedModCount != base.modCount) |
846 |
> |
throw new ConcurrentModificationException(); |
847 |
> |
try { |
848 |
> |
int i = cursor; |
849 |
> |
outer.add(i, e); |
850 |
> |
cursor = i + 1; |
851 |
> |
lastRet = -1; |
852 |
> |
fence = outer.length; |
853 |
> |
expectedModCount = base.modCount; |
854 |
> |
} catch (IndexOutOfBoundsException ex) { |
855 |
> |
throw new ConcurrentModificationException(); |
856 |
> |
} |
857 |
> |
} |
858 |
|
} |
859 |
|
|
754 |
– |
private void checkForComodification() { |
755 |
– |
if (l.modCount != expectedModCount) |
756 |
– |
throw new ConcurrentModificationException(); |
757 |
– |
} |
860 |
|
} |
861 |
|
|
862 |
|
class RandomAccessSubList<E> extends SubList<E> implements RandomAccess { |
863 |
< |
RandomAccessSubList(AbstractList<E> list, int fromIndex, int toIndex) { |
864 |
< |
super(list, fromIndex, toIndex); |
863 |
> |
RandomAccessSubList(AbstractList<E> base, |
864 |
> |
AbstractList<E> parent, int baseIndex, |
865 |
> |
int fromIndex, int toIndex) { |
866 |
> |
super(base, parent, baseIndex, fromIndex, toIndex); |
867 |
|
} |
868 |
|
|
869 |
|
public List<E> subList(int fromIndex, int toIndex) { |
870 |
< |
return new RandomAccessSubList<E>(this, fromIndex, toIndex); |
870 |
> |
return new RandomAccessSubList(base, this, fromIndex + baseOffset, |
871 |
> |
fromIndex, toIndex); |
872 |
|
} |
873 |
|
} |
874 |
+ |
|