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.
521 *
522 * @param o the object to be compared for equality with this list
523 * @return {@code true} if the specified object is equal to this list
524 */
525 public boolean equals(Object o) {
526 if (o == this)
527 return true;
528 if (!(o instanceof List))
529 return false;
530
531 ListIterator<E> e1 = listIterator();
532 ListIterator<?> e2 = ((List<?>) o).listIterator();
533 while (e1.hasNext() && e2.hasNext()) {
534 E o1 = e1.next();
535 Object o2 = e2.next();
536 if (!(o1==null ? o2==null : o1.equals(o2)))
537 return false;
538 }
539 return !(e1.hasNext() || e2.hasNext());
540 }
541
542 /**
543 * Returns the hash code value for this list.
544 *
545 * @implSpec
546 * This implementation uses exactly the code that is used to define the
547 * list hash function in the documentation for the {@link List#hashCode}
548 * method.
549 *
550 * @return the hash code value for this list
551 */
552 public int hashCode() {
553 int hashCode = 1;
554 for (E e : this)
555 hashCode = 31*hashCode + (e==null ? 0 : e.hashCode());
556 return hashCode;
557 }
558
559 /**
560 * Removes from this list all of the elements whose index is between
561 * {@code fromIndex}, inclusive, and {@code toIndex}, exclusive.
562 * Shifts any succeeding elements to the left (reduces their index).
563 * This call shortens the list by {@code (toIndex - fromIndex)} elements.
564 * (If {@code toIndex==fromIndex}, this operation has no effect.)
565 *
566 * <p>This method is called by the {@code clear} operation on this list
567 * and its subLists. Overriding this method to take advantage of
568 * the internals of the list implementation can <i>substantially</i>
569 * improve the performance of the {@code clear} operation on this list
570 * and its subLists.
571 *
572 * @implSpec
573 * This implementation gets a list iterator positioned before
574 * {@code fromIndex}, and repeatedly calls {@code ListIterator.next}
575 * followed by {@code ListIterator.remove} until the entire range has
576 * been removed. <b>Note: if {@code ListIterator.remove} requires linear
577 * time, this implementation requires quadratic time.</b>
578 *
579 * @param fromIndex index of first element to be removed
580 * @param toIndex index after last element to be removed
581 */
582 protected void removeRange(int fromIndex, int toIndex) {
583 ListIterator<E> it = listIterator(fromIndex);
584 for (int i=0, n=toIndex-fromIndex; i<n; i++) {
585 it.next();
586 it.remove();
587 }
588 }
589
590 /**
591 * The number of times this list has been <i>structurally modified</i>.
592 * Structural modifications are those that change the size of the
593 * list, or otherwise perturb it in such a fashion that iterations in
594 * progress may yield incorrect results.
595 *
596 * <p>This field is used by the iterator and list iterator implementation
597 * returned by the {@code iterator} and {@code listIterator} methods.
598 * If the value of this field changes unexpectedly, the iterator (or list
599 * iterator) will throw a {@code ConcurrentModificationException} in
600 * response to the {@code next}, {@code remove}, {@code previous},
601 * {@code set} or {@code add} operations. This provides
602 * <i>fail-fast</i> behavior, rather than non-deterministic behavior in
603 * the face of concurrent modification during iteration.
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, 0, fromIndex, toIndex) :
499 new SubList(this, 0, 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 private class SubList extends AbstractList<E> {
513 final AbstractList<E> parent;
514 final int offset;
515 int size;
516
517 SubList(AbstractList<E> parent,
518 int offset, int fromIndex, int toIndex) {
519 this.parent = parent;
520 this.offset = offset + fromIndex;
521 this.size = toIndex - fromIndex;
522 this.modCount = AbstractList.this.modCount;
523 }
524
525 public E set(int index, E element) {
526 rangeCheck(index);
527 checkForComodification();
528 return AbstractList.this.set(index + offset, element);
529 }
530
531 public E get(int index) {
532 rangeCheck(index);
533 checkForComodification();
534 return AbstractList.this.get(index + offset);
535 }
536
537 public int size() {
538 checkForComodification();
539 return size;
540 }
541
542 public void add(int index, E element) {
543 rangeCheckForAdd(index);
544 checkForComodification();
545 AbstractList.this.add(index + offset, element);
546 updateSizeAndModCount(1, AbstractList.this.modCount);
547 }
548
549 public E remove(int index) {
550 rangeCheck(index);
551 checkForComodification();
552 E result = AbstractList.this.remove(index + offset);
553 updateSizeAndModCount(-1, AbstractList.this.modCount);
554 return result;
555 }
556
557 protected void removeRange(int fromIndex, int toIndex) {
558 checkForComodification();
559 AbstractList.this.removeRange(offset + fromIndex,
560 offset + toIndex);
561 updateSizeAndModCount(fromIndex - toIndex,
562 AbstractList.this.modCount);
563 }
564
565 public boolean addAll(Collection<? extends E> c) {
566 return addAll(size, c);
567 }
568
569 public boolean addAll(int index, Collection<? extends E> c) {
570 rangeCheckForAdd(index);
571 int cSize = c.size();
572 if (cSize == 0)
573 return false;
574 checkForComodification();
575 AbstractList.this.addAll(offset + index, c);
576 updateSizeAndModCount(cSize,
577 AbstractList.this.modCount);
578 return true;
579 }
580
581 public Iterator<E> iterator() {
582 return listIterator();
583 }
584
585 public ListIterator<E> listIterator(final int index) {
586 checkForComodification();
587 rangeCheckForAdd(index);
588
589 return new ListIterator<E>() {
590 private final ListIterator<E> i =
591 AbstractList.this.listIterator(offset + index);
592
593 public boolean hasNext() {
594 return nextIndex() < size;
595 }
596
597 public E next() {
598 if (hasNext())
599 return i.next();
600 else
601 throw new NoSuchElementException();
602 }
603
604 public boolean hasPrevious() {
605 return previousIndex() >= 0;
606 }
607
608 public E previous() {
609 if (hasPrevious())
610 return i.previous();
611 else
612 throw new NoSuchElementException();
613 }
614
615 public int nextIndex() {
616 return i.nextIndex() - offset;
617 }
618
619 public int previousIndex() {
620 return i.previousIndex() - offset;
621 }
622
623 public void remove() {
624 i.remove();
625 updateSizeAndModCount(-1,
626 AbstractList.this.modCount);
627 }
628
629 public void set(E e) {
630 i.set(e);
631 }
632
633 public void add(E e) {
634 i.add(e);
635 updateSizeAndModCount(1,
636 AbstractList.this.modCount);
637 }
638 };
639 }
640
641 public List<E> subList(int fromIndex, int toIndex) {
642 subListRangeCheck(fromIndex, toIndex, size);
643 return AbstractList.this.new SubList(this, offset, fromIndex,
644 toIndex);
645 }
646
647 private void rangeCheck(int index) {
648 if (index < 0 || index >= size)
649 throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
650 }
651
652 private void rangeCheckForAdd(int index) {
653 if (index < 0 || index > size)
654 throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
655 }
656
657 private String outOfBoundsMsg(int index) {
658 return "Index: " + index + ", Size: " + size;
659 }
660
661 private void checkForComodification() {
662 if (AbstractList.this.modCount != this.modCount)
663 throw new ConcurrentModificationException();
664 }
665
666 private void updateSizeAndModCount(int sizeChange, int modCount) {
667 AbstractList<E> alist = this;
668 do {
669 SubList slist = (SubList)alist;
670 slist.size += sizeChange;
671 slist.modCount = modCount;
672 alist = slist.parent;
673 } while (alist instanceof AbstractList.SubList);
674 }
675 }
676
677 private class RandomAccessSubList extends SubList implements RandomAccess {
678 RandomAccessSubList(AbstractList<E> list, int offset,
679 int fromIndex, int toIndex) {
680 super(list, offset, fromIndex, toIndex);
681 }
682
683 public List<E> subList(int fromIndex, int toIndex) {
684 subListRangeCheck(fromIndex, toIndex, size);
685 return AbstractList.this.new RandomAccessSubList(this, offset,
686 fromIndex, toIndex);
687 }
688 }
689
690 // Comparison and hashing
691
692 /**
693 * Compares the specified object with this list for equality. Returns
694 * {@code true} if and only if the specified object is also a list, both
695 * lists have the same size, and all corresponding pairs of elements in
696 * the two lists are <i>equal</i>. (Two elements {@code e1} and
697 * {@code e2} are <i>equal</i> if {@code (e1==null ? e2==null :
698 * e1.equals(e2))}.) In other words, two lists are defined to be
699 * equal if they contain the same elements in the same order.
700 *
701 * @implSpec
702 * This implementation first checks if the specified object is this
703 * list. If so, it returns {@code true}; if not, it checks if the
704 * specified object is a list. If not, it returns {@code false}; if so,
705 * it iterates over both lists, comparing corresponding pairs of elements.
706 * If any comparison returns {@code false}, this method returns
707 * {@code false}. If either iterator runs out of elements before the
708 * other it returns {@code false} (as the lists are of unequal length);
709 * otherwise it returns {@code true} when the iterations complete.
710 *
711 * @param o the object to be compared for equality with this list
712 * @return {@code true} if the specified object is equal to this list
713 */
714 public boolean equals(Object o) {
715 if (o == this)
716 return true;
717 if (!(o instanceof List))
718 return false;
719
720 ListIterator<E> e1 = listIterator();
721 ListIterator<?> e2 = ((List<?>) o).listIterator();
722 while (e1.hasNext() && e2.hasNext()) {
723 E o1 = e1.next();
724 Object o2 = e2.next();
725 if (!(o1==null ? o2==null : o1.equals(o2)))
726 return false;
727 }
728 return !(e1.hasNext() || e2.hasNext());
729 }
730
731 /**
732 * Returns the hash code value for this list.
733 *
734 * @implSpec
735 * This implementation uses exactly the code that is used to define the
736 * list hash function in the documentation for the {@link List#hashCode}
737 * method.
738 *
739 * @return the hash code value for this list
740 */
741 public int hashCode() {
742 int hashCode = 1;
743 for (E e : this)
744 hashCode = 31*hashCode + (e==null ? 0 : e.hashCode());
745 return hashCode;
746 }
747
748 /**
749 * Removes from this list all of the elements whose index is between
750 * {@code fromIndex}, inclusive, and {@code toIndex}, exclusive.
751 * Shifts any succeeding elements to the left (reduces their index).
752 * This call shortens the list by {@code (toIndex - fromIndex)} elements.
753 * (If {@code toIndex==fromIndex}, this operation has no effect.)
754 *
755 * <p>This method is called by the {@code clear} operation on this list
756 * and its subLists. Overriding this method to take advantage of
757 * the internals of the list implementation can <i>substantially</i>
758 * improve the performance of the {@code clear} operation on this list
759 * and its subLists.
760 *
761 * @implSpec
762 * This implementation gets a list iterator positioned before
763 * {@code fromIndex}, and repeatedly calls {@code ListIterator.next}
764 * followed by {@code ListIterator.remove} until the entire range has
765 * been removed. <b>Note: if {@code ListIterator.remove} requires linear
766 * time, this implementation requires quadratic time.</b>
767 *
768 * @param fromIndex index of first element to be removed
769 * @param toIndex index after last element to be removed
770 */
771 protected void removeRange(int fromIndex, int toIndex) {
772 ListIterator<E> it = listIterator(fromIndex);
773 for (int i=0, n=toIndex-fromIndex; i<n; i++) {
774 it.next();
775 it.remove();
776 }
777 }
778
779 /**
780 * The number of times this list has been <i>structurally modified</i>.
781 * Structural modifications are those that change the size of the
782 * list, or otherwise perturb it in such a fashion that iterations in
783 * progress may yield incorrect results.
784 *
785 * <p>This field is used by the iterator and list iterator implementation
786 * returned by the {@code iterator} and {@code listIterator} methods.
787 * If the value of this field changes unexpectedly, the iterator (or list
788 * iterator) will throw a {@code ConcurrentModificationException} in
789 * response to the {@code next}, {@code remove}, {@code previous},
790 * {@code set} or {@code add} operations. This provides
791 * <i>fail-fast</i> behavior, rather than non-deterministic behavior in
792 * the face of concurrent modification during iteration.
793 *
794 * <p><b>Use of this field by subclasses is optional.</b> If a subclass
795 * wishes to provide fail-fast iterators (and list iterators), then it
796 * merely has to increment this field in its {@code add(int, E)} and
797 * {@code remove(int)} methods (and any other methods that it overrides
798 * that result in structural modifications to the list). A single call to
799 * {@code add(int, E)} or {@code remove(int)} must add no more than
800 * one to this field, or the iterators (and list iterators) will throw
801 * bogus {@code ConcurrentModificationExceptions}. If an implementation
802 * does not wish to provide fail-fast iterators, this field may be
803 * ignored.
804 */
805 protected transient int modCount = 0;
806
807 private void rangeCheckForAdd(int index) {
808 if (index < 0 || index > size())
809 throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
810 }
811
812 private String outOfBoundsMsg(int index) {
813 return "Index: " + index + ", Size: " + size();
814 }
815 }
|