ViewVC Help
View File | Revision Log | Show Annotations | Download File | Root Listing
root/jsr166/jsr166/src/main/java/util/AbstractList.java
(Generate patch)

Comparing jsr166/src/main/java/util/AbstractList.java (file contents):
Revision 1.5 by jsr166, Mon Dec 5 02:56:59 2005 UTC vs.
Revision 1.10 by jsr166, Fri Apr 21 20:49:03 2006 UTC

# Line 44 | Line 44 | package java.util;
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
# Line 342 | Line 342 | public abstract class AbstractList<E> ex
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)
# Line 371 | Line 368 | public abstract class AbstractList<E> ex
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;
# Line 382 | Line 384 | public abstract class AbstractList<E> ex
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;
# Line 419 | Line 419 | public abstract class AbstractList<E> ex
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);
# Line 470 | Line 470 | public abstract class AbstractList<E> ex
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
# Line 593 | Line 593 | public abstract class AbstractList<E> ex
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 +

Diff Legend

Removed lines
+ Added lines
< Changed lines
> Changed lines