476 * after bounds-checking the index and adjusting for the offset. The
477 * {@code addAll(Collection c)} method merely returns {@code addAll(size,
478 * c)}.
479 *
480 * <p>The {@code listIterator(int)} method returns a "wrapper object"
481 * over a list iterator on the backing list, which is created with the
482 * corresponding method on the backing list. The {@code iterator} method
483 * merely returns {@code listIterator()}, and the {@code size} method
484 * merely returns the subclass's {@code size} field.
485 *
486 * <p>All methods first check to see if the actual {@code modCount} of
487 * the backing list is equal to its expected value, and throw a
488 * {@code ConcurrentModificationException} if it is not.
489 *
490 * @throws IndexOutOfBoundsException if an endpoint index value is out of range
491 * {@code (fromIndex < 0 || toIndex > size)}
492 * @throws IllegalArgumentException if the endpoint indices are out of order
493 * {@code (fromIndex > toIndex)}
494 */
495 public List<E> subList(int fromIndex, int toIndex) {
496 return (this instanceof RandomAccess ?
497 new RandomAccessSubList<>(this, fromIndex, toIndex) :
498 new SubList<>(this, fromIndex, toIndex));
499 }
500
501 // Comparison and hashing
502
503 /**
504 * Compares the specified object with this list for equality. Returns
505 * {@code true} if and only if the specified object is also a list, both
506 * lists have the same size, and all corresponding pairs of elements in
507 * the two lists are <i>equal</i>. (Two elements {@code e1} and
508 * {@code e2} are <i>equal</i> if {@code (e1==null ? e2==null :
509 * e1.equals(e2))}.) In other words, two lists are defined to be
510 * equal if they contain the same elements in the same order.
511 *
512 * @implSpec
513 * This implementation first checks if the specified object is this
514 * list. If so, it returns {@code true}; if not, it checks if the
515 * specified object is a list. If not, it returns {@code false}; if so,
516 * it iterates over both lists, comparing corresponding pairs of elements.
517 * If any comparison returns {@code false}, this method returns
518 * {@code false}. If either iterator runs out of elements before the
519 * other it returns {@code false} (as the lists are of unequal length);
520 * otherwise it returns {@code true} when the iterations complete.
604 *
605 * <p><b>Use of this field by subclasses is optional.</b> If a subclass
606 * wishes to provide fail-fast iterators (and list iterators), then it
607 * merely has to increment this field in its {@code add(int, E)} and
608 * {@code remove(int)} methods (and any other methods that it overrides
609 * that result in structural modifications to the list). A single call to
610 * {@code add(int, E)} or {@code remove(int)} must add no more than
611 * one to this field, or the iterators (and list iterators) will throw
612 * bogus {@code ConcurrentModificationExceptions}. If an implementation
613 * does not wish to provide fail-fast iterators, this field may be
614 * ignored.
615 */
616 protected transient int modCount = 0;
617
618 private void rangeCheckForAdd(int index) {
619 if (index < 0 || index > size())
620 throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
621 }
622
623 private String outOfBoundsMsg(int index) {
624 return "Index: "+index+", Size: "+size();
625 }
626 }
627
628 class SubList<E> extends AbstractList<E> {
629 private final AbstractList<E> l;
630 private final int offset;
631 private int size;
632
633 SubList(AbstractList<E> list, int fromIndex, int toIndex) {
634 if (fromIndex < 0)
635 throw new IndexOutOfBoundsException("fromIndex = " + fromIndex);
636 if (toIndex > list.size())
637 throw new IndexOutOfBoundsException("toIndex = " + toIndex);
638 if (fromIndex > toIndex)
639 throw new IllegalArgumentException("fromIndex(" + fromIndex +
640 ") > toIndex(" + toIndex + ")");
641 l = list;
642 offset = fromIndex;
643 size = toIndex - fromIndex;
644 this.modCount = l.modCount;
645 }
646
647 public E set(int index, E element) {
648 rangeCheck(index);
649 checkForComodification();
650 return l.set(index+offset, element);
651 }
652
653 public E get(int index) {
654 rangeCheck(index);
655 checkForComodification();
656 return l.get(index+offset);
657 }
658
659 public int size() {
660 checkForComodification();
661 return size;
662 }
663
664 public void add(int index, E element) {
665 rangeCheckForAdd(index);
666 checkForComodification();
667 l.add(index+offset, element);
668 this.modCount = l.modCount;
669 size++;
670 }
671
672 public E remove(int index) {
673 rangeCheck(index);
674 checkForComodification();
675 E result = l.remove(index+offset);
676 this.modCount = l.modCount;
677 size--;
678 return result;
679 }
680
681 protected void removeRange(int fromIndex, int toIndex) {
682 checkForComodification();
683 l.removeRange(fromIndex+offset, toIndex+offset);
684 this.modCount = l.modCount;
685 size -= (toIndex-fromIndex);
686 }
687
688 public boolean addAll(Collection<? extends E> c) {
689 return addAll(size, c);
690 }
691
692 public boolean addAll(int index, Collection<? extends E> c) {
693 rangeCheckForAdd(index);
694 int cSize = c.size();
695 if (cSize==0)
696 return false;
697
698 checkForComodification();
699 l.addAll(offset+index, c);
700 this.modCount = l.modCount;
701 size += cSize;
702 return true;
703 }
704
705 public Iterator<E> iterator() {
706 return listIterator();
707 }
708
709 public ListIterator<E> listIterator(final int index) {
710 checkForComodification();
711 rangeCheckForAdd(index);
712
713 return new ListIterator<E>() {
714 private final ListIterator<E> i = l.listIterator(index+offset);
715
716 public boolean hasNext() {
717 return nextIndex() < size;
718 }
719
720 public E next() {
721 if (hasNext())
722 return i.next();
723 else
724 throw new NoSuchElementException();
725 }
726
727 public boolean hasPrevious() {
728 return previousIndex() >= 0;
729 }
730
731 public E previous() {
732 if (hasPrevious())
733 return i.previous();
734 else
735 throw new NoSuchElementException();
736 }
737
738 public int nextIndex() {
739 return i.nextIndex() - offset;
740 }
741
742 public int previousIndex() {
743 return i.previousIndex() - offset;
744 }
745
746 public void remove() {
747 i.remove();
748 SubList.this.modCount = l.modCount;
749 size--;
750 }
751
752 public void set(E e) {
753 i.set(e);
754 }
755
756 public void add(E e) {
757 i.add(e);
758 SubList.this.modCount = l.modCount;
759 size++;
760 }
761 };
762 }
763
764 public List<E> subList(int fromIndex, int toIndex) {
765 return new SubList<>(this, fromIndex, toIndex);
766 }
767
768 private void rangeCheck(int index) {
769 if (index < 0 || index >= size)
770 throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
771 }
772
773 private void rangeCheckForAdd(int index) {
774 if (index < 0 || index > size)
775 throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
776 }
777
778 private String outOfBoundsMsg(int index) {
779 return "Index: "+index+", Size: "+size;
780 }
781
782 private void checkForComodification() {
783 if (this.modCount != l.modCount)
784 throw new ConcurrentModificationException();
785 }
786 }
787
788 class RandomAccessSubList<E> extends SubList<E> implements RandomAccess {
789 RandomAccessSubList(AbstractList<E> list, int fromIndex, int toIndex) {
790 super(list, fromIndex, toIndex);
791 }
792
793 public List<E> subList(int fromIndex, int toIndex) {
794 return new RandomAccessSubList<>(this, fromIndex, toIndex);
795 }
796 }
|
476 * after bounds-checking the index and adjusting for the offset. The
477 * {@code addAll(Collection c)} method merely returns {@code addAll(size,
478 * c)}.
479 *
480 * <p>The {@code listIterator(int)} method returns a "wrapper object"
481 * over a list iterator on the backing list, which is created with the
482 * corresponding method on the backing list. The {@code iterator} method
483 * merely returns {@code listIterator()}, and the {@code size} method
484 * merely returns the subclass's {@code size} field.
485 *
486 * <p>All methods first check to see if the actual {@code modCount} of
487 * the backing list is equal to its expected value, and throw a
488 * {@code ConcurrentModificationException} if it is not.
489 *
490 * @throws IndexOutOfBoundsException if an endpoint index value is out of range
491 * {@code (fromIndex < 0 || toIndex > size)}
492 * @throws IllegalArgumentException if the endpoint indices are out of order
493 * {@code (fromIndex > toIndex)}
494 */
495 public List<E> subList(int fromIndex, int toIndex) {
496 subListRangeCheck(fromIndex, toIndex, size());
497 return (this instanceof RandomAccess ?
498 new RandomAccessSubList<>(this, fromIndex, toIndex) :
499 new SubList<>(this, fromIndex, toIndex));
500 }
501
502 static void subListRangeCheck(int fromIndex, int toIndex, int size) {
503 if (fromIndex < 0)
504 throw new IndexOutOfBoundsException("fromIndex = " + fromIndex);
505 if (toIndex > size)
506 throw new IndexOutOfBoundsException("toIndex = " + toIndex);
507 if (fromIndex > toIndex)
508 throw new IllegalArgumentException("fromIndex(" + fromIndex +
509 ") > toIndex(" + toIndex + ")");
510 }
511
512 // Comparison and hashing
513
514 /**
515 * Compares the specified object with this list for equality. Returns
516 * {@code true} if and only if the specified object is also a list, both
517 * lists have the same size, and all corresponding pairs of elements in
518 * the two lists are <i>equal</i>. (Two elements {@code e1} and
519 * {@code e2} are <i>equal</i> if {@code (e1==null ? e2==null :
520 * e1.equals(e2))}.) In other words, two lists are defined to be
521 * equal if they contain the same elements in the same order.
522 *
523 * @implSpec
524 * This implementation first checks if the specified object is this
525 * list. If so, it returns {@code true}; if not, it checks if the
526 * specified object is a list. If not, it returns {@code false}; if so,
527 * it iterates over both lists, comparing corresponding pairs of elements.
528 * If any comparison returns {@code false}, this method returns
529 * {@code false}. If either iterator runs out of elements before the
530 * other it returns {@code false} (as the lists are of unequal length);
531 * otherwise it returns {@code true} when the iterations complete.
615 *
616 * <p><b>Use of this field by subclasses is optional.</b> If a subclass
617 * wishes to provide fail-fast iterators (and list iterators), then it
618 * merely has to increment this field in its {@code add(int, E)} and
619 * {@code remove(int)} methods (and any other methods that it overrides
620 * that result in structural modifications to the list). A single call to
621 * {@code add(int, E)} or {@code remove(int)} must add no more than
622 * one to this field, or the iterators (and list iterators) will throw
623 * bogus {@code ConcurrentModificationExceptions}. If an implementation
624 * does not wish to provide fail-fast iterators, this field may be
625 * ignored.
626 */
627 protected transient int modCount = 0;
628
629 private void rangeCheckForAdd(int index) {
630 if (index < 0 || index > size())
631 throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
632 }
633
634 private String outOfBoundsMsg(int index) {
635 return "Index: " + index + ", Size: " + size();
636 }
637 }
638
639 class SubList<E> extends AbstractList<E> {
640 final AbstractList<E> root;
641 final SubList<E> parent;
642 final int offset;
643 int size;
644
645 /**
646 * Constructs a sublist of an arbitrary AbstractList, which is
647 * not a SubList itself.
648 */
649 public SubList(AbstractList<E> root, int fromIndex, int toIndex) {
650 this.root = root;
651 this.parent = null;
652 this.offset = fromIndex;
653 this.size = toIndex - fromIndex;
654 this.modCount = root.modCount;
655 }
656
657 /**
658 * Constructs a sublist of another SubList.
659 */
660 protected SubList(SubList<E> parent, int fromIndex, int toIndex) {
661 this.root = parent.root;
662 this.parent = parent;
663 this.offset = parent.offset + fromIndex;
664 this.size = toIndex - fromIndex;
665 this.modCount = root.modCount;
666 }
667
668 public E set(int index, E element) {
669 rangeCheck(index);
670 checkForComodification();
671 return root.set(offset + index, element);
672 }
673
674 public E get(int index) {
675 rangeCheck(index);
676 checkForComodification();
677 return root.get(offset + index);
678 }
679
680 public int size() {
681 checkForComodification();
682 return size;
683 }
684
685 public void add(int index, E element) {
686 rangeCheckForAdd(index);
687 checkForComodification();
688 root.add(offset + index, element);
689 updateSizeAndModCount(1);
690 }
691
692 public E remove(int index) {
693 rangeCheck(index);
694 checkForComodification();
695 E result = root.remove(offset + index);
696 updateSizeAndModCount(-1);
697 return result;
698 }
699
700 protected void removeRange(int fromIndex, int toIndex) {
701 checkForComodification();
702 root.removeRange(offset + fromIndex, offset + toIndex);
703 updateSizeAndModCount(fromIndex - toIndex);
704 }
705
706 public boolean addAll(Collection<? extends E> c) {
707 return addAll(size, c);
708 }
709
710 public boolean addAll(int index, Collection<? extends E> c) {
711 rangeCheckForAdd(index);
712 int cSize = c.size();
713 if (cSize == 0)
714 return false;
715 checkForComodification();
716 root.addAll(offset + index, c);
717 updateSizeAndModCount(cSize);
718 return true;
719 }
720
721 public Iterator<E> iterator() {
722 return listIterator();
723 }
724
725 public ListIterator<E> listIterator(int index) {
726 checkForComodification();
727 rangeCheckForAdd(index);
728
729 return new ListIterator<E>() {
730 private final ListIterator<E> i =
731 root.listIterator(offset + index);
732
733 public boolean hasNext() {
734 return nextIndex() < size;
735 }
736
737 public E next() {
738 if (hasNext())
739 return i.next();
740 else
741 throw new NoSuchElementException();
742 }
743
744 public boolean hasPrevious() {
745 return previousIndex() >= 0;
746 }
747
748 public E previous() {
749 if (hasPrevious())
750 return i.previous();
751 else
752 throw new NoSuchElementException();
753 }
754
755 public int nextIndex() {
756 return i.nextIndex() - offset;
757 }
758
759 public int previousIndex() {
760 return i.previousIndex() - offset;
761 }
762
763 public void remove() {
764 i.remove();
765 updateSizeAndModCount(-1);
766 }
767
768 public void set(E e) {
769 i.set(e);
770 }
771
772 public void add(E e) {
773 i.add(e);
774 updateSizeAndModCount(1);
775 }
776 };
777 }
778
779 public List<E> subList(int fromIndex, int toIndex) {
780 subListRangeCheck(fromIndex, toIndex, size);
781 return new SubList<>(this, fromIndex, toIndex);
782 }
783
784 private void rangeCheck(int index) {
785 if (index < 0 || index >= size)
786 throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
787 }
788
789 private void rangeCheckForAdd(int index) {
790 if (index < 0 || index > size)
791 throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
792 }
793
794 private String outOfBoundsMsg(int index) {
795 return "Index: " + index + ", Size: " + size;
796 }
797
798 private void checkForComodification() {
799 if (root.modCount != this.modCount)
800 throw new ConcurrentModificationException();
801 }
802
803 private void updateSizeAndModCount(int sizeChange) {
804 SubList<E> slist = this;
805 do {
806 slist.size += sizeChange;
807 slist.modCount = root.modCount;
808 slist = slist.parent;
809 } while (slist != null);
810 }
811 }
812
813 class RandomAccessSubList<E> extends SubList<E>
814 implements RandomAccess {
815
816 /**
817 * Constructs a sublist of an arbitrary AbstractList, which is
818 * not a RandomAccessSubList itself.
819 */
820 RandomAccessSubList(AbstractList<E> root,
821 int fromIndex, int toIndex) {
822 super(root, fromIndex, toIndex);
823 }
824
825 /**
826 * Constructs a sublist of another RandomAccessSubList.
827 */
828 RandomAccessSubList(RandomAccessSubList<E> parent,
829 int fromIndex, int toIndex) {
830 super(parent, fromIndex, toIndex);
831 }
832
833 public List<E> subList(int fromIndex, int toIndex) {
834 subListRangeCheck(fromIndex, toIndex, size);
835 return new RandomAccessSubList<>(this, fromIndex, toIndex);
836 }
837 }
|