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 private static class SubList<E> extends AbstractList<E> {
639 private final AbstractList<E> root;
640 private final SubList<E> parent;
641 private final int offset;
642 protected int size;
643
644 /**
645 * Constructs a sublist of an arbitrary AbstractList, which is
646 * not a SubList itself.
647 */
648 public SubList(AbstractList<E> root, int fromIndex, int toIndex) {
649 this.root = root;
650 this.parent = null;
651 this.offset = fromIndex;
652 this.size = toIndex - fromIndex;
653 this.modCount = root.modCount;
654 }
655
656 /**
657 * Constructs a sublist of another SubList.
658 */
659 protected SubList(SubList<E> parent, int fromIndex, int toIndex) {
660 this.root = parent.root;
661 this.parent = parent;
662 this.offset = parent.offset + fromIndex;
663 this.size = toIndex - fromIndex;
664 this.modCount = root.modCount;
665 }
666
667 public E set(int index, E element) {
668 rangeCheck(index);
669 checkForComodification();
670 return root.set(offset + index, element);
671 }
672
673 public E get(int index) {
674 rangeCheck(index);
675 checkForComodification();
676 return root.get(offset + index);
677 }
678
679 public int size() {
680 checkForComodification();
681 return size;
682 }
683
684 public void add(int index, E element) {
685 rangeCheckForAdd(index);
686 checkForComodification();
687 root.add(offset + index, element);
688 updateSizeAndModCount(1);
689 }
690
691 public E remove(int index) {
692 rangeCheck(index);
693 checkForComodification();
694 E result = root.remove(offset + index);
695 updateSizeAndModCount(-1);
696 return result;
697 }
698
699 protected void removeRange(int fromIndex, int toIndex) {
700 checkForComodification();
701 root.removeRange(offset + fromIndex, offset + toIndex);
702 updateSizeAndModCount(fromIndex - toIndex);
703 }
704
705 public boolean addAll(Collection<? extends E> c) {
706 return addAll(size, c);
707 }
708
709 public boolean addAll(int index, Collection<? extends E> c) {
710 rangeCheckForAdd(index);
711 int cSize = c.size();
712 if (cSize == 0)
713 return false;
714 checkForComodification();
715 root.addAll(offset + index, c);
716 updateSizeAndModCount(cSize);
717 return true;
718 }
719
720 public Iterator<E> iterator() {
721 return listIterator();
722 }
723
724 public ListIterator<E> listIterator(int index) {
725 checkForComodification();
726 rangeCheckForAdd(index);
727
728 return new ListIterator<E>() {
729 private final ListIterator<E> i =
730 root.listIterator(offset + index);
731
732 public boolean hasNext() {
733 return nextIndex() < size;
734 }
735
736 public E next() {
737 if (hasNext())
738 return i.next();
739 else
740 throw new NoSuchElementException();
741 }
742
743 public boolean hasPrevious() {
744 return previousIndex() >= 0;
745 }
746
747 public E previous() {
748 if (hasPrevious())
749 return i.previous();
750 else
751 throw new NoSuchElementException();
752 }
753
754 public int nextIndex() {
755 return i.nextIndex() - offset;
756 }
757
758 public int previousIndex() {
759 return i.previousIndex() - offset;
760 }
761
762 public void remove() {
763 i.remove();
764 updateSizeAndModCount(-1);
765 }
766
767 public void set(E e) {
768 i.set(e);
769 }
770
771 public void add(E e) {
772 i.add(e);
773 updateSizeAndModCount(1);
774 }
775 };
776 }
777
778 public List<E> subList(int fromIndex, int toIndex) {
779 subListRangeCheck(fromIndex, toIndex, size);
780 return new SubList<>(this, fromIndex, toIndex);
781 }
782
783 private void rangeCheck(int index) {
784 if (index < 0 || index >= size)
785 throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
786 }
787
788 private void rangeCheckForAdd(int index) {
789 if (index < 0 || index > size)
790 throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
791 }
792
793 private String outOfBoundsMsg(int index) {
794 return "Index: " + index + ", Size: " + size;
795 }
796
797 private void checkForComodification() {
798 if (root.modCount != this.modCount)
799 throw new ConcurrentModificationException();
800 }
801
802 private void updateSizeAndModCount(int sizeChange) {
803 SubList<E> slist = this;
804 do {
805 slist.size += sizeChange;
806 slist.modCount = root.modCount;
807 slist = slist.parent;
808 } while (slist != null);
809 }
810 }
811
812 private static class RandomAccessSubList<E>
813 extends SubList<E> implements RandomAccess {
814
815 /**
816 * Constructs a sublist of an arbitrary AbstractList, which is
817 * not a RandomAccessSubList itself.
818 */
819 RandomAccessSubList(AbstractList<E> root,
820 int fromIndex, int toIndex) {
821 super(root, fromIndex, toIndex);
822 }
823
824 /**
825 * Constructs a sublist of another RandomAccessSubList.
826 */
827 RandomAccessSubList(RandomAccessSubList<E> parent,
828 int fromIndex, int toIndex) {
829 super(parent, fromIndex, toIndex);
830 }
831
832 public List<E> subList(int fromIndex, int toIndex) {
833 subListRangeCheck(fromIndex, toIndex, size);
834 return new RandomAccessSubList<>(this, fromIndex, toIndex);
835 }
836 }
837 }
|