< prev index next >
src/java.base/share/classes/java/util/AbstractList.java
Print this page
rev 13550 : [mq]: 8079136-Nested-SubLists
*** 1,7 ****
/*
! * Copyright (c) 1997, 2012, Oracle and/or its affiliates. All rights reserved.
* DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
*
* This code is free software; you can redistribute it and/or modify it
* under the terms of the GNU General Public License version 2 only, as
* published by the Free Software Foundation. Oracle designates this
--- 1,7 ----
/*
! * Copyright (c) 1997, 2016, Oracle and/or its affiliates. All rights reserved.
* DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
*
* This code is free software; you can redistribute it and/or modify it
* under the terms of the GNU General Public License version 2 only, as
* published by the Free Software Foundation. Oracle designates this
*** 459,475 ****
/**
* {@inheritDoc}
*
* @implSpec
* This implementation returns a list that subclasses
! * {@code AbstractList}. The subclass stores, in private fields, the
! * offset of the subList within the backing list, the size of the subList
! * (which can change over its lifetime), and the expected
! * {@code modCount} value of the backing list. There are two variants
! * of the subclass, one of which implements {@code RandomAccess}.
! * If this list implements {@code RandomAccess} the returned list will
! * be an instance of the subclass that implements {@code RandomAccess}.
*
* <p>The subclass's {@code set(int, E)}, {@code get(int)},
* {@code add(int, E)}, {@code remove(int)}, {@code addAll(int,
* Collection)} and {@code removeRange(int, int)} methods all
* delegate to the corresponding methods on the backing abstract list,
--- 459,472 ----
/**
* {@inheritDoc}
*
* @implSpec
* This implementation returns a list that subclasses
! * {@code AbstractList}. There are two variants of the subclass,
! * one of which implements {@code RandomAccess}. If this list
! * implements {@code RandomAccess} the returned list will be an
! * instance of the subclass that implements {@code RandomAccess}.
*
* <p>The subclass's {@code set(int, E)}, {@code get(int)},
* {@code add(int, E)}, {@code remove(int)}, {@code addAll(int,
* Collection)} and {@code removeRange(int, int)} methods all
* delegate to the corresponding methods on the backing abstract list,
*** 491,505 ****
--- 488,513 ----
* {@code (fromIndex < 0 || toIndex > size)}
* @throws IllegalArgumentException if the endpoint indices are out of order
* {@code (fromIndex > toIndex)}
*/
public List<E> subList(int fromIndex, int toIndex) {
+ subListRangeCheck(fromIndex, toIndex, size());
return (this instanceof RandomAccess ?
new RandomAccessSubList<>(this, fromIndex, toIndex) :
new SubList<>(this, fromIndex, toIndex));
}
+ static void subListRangeCheck(int fromIndex, int toIndex, int size) {
+ if (fromIndex < 0)
+ throw new IndexOutOfBoundsException("fromIndex = " + fromIndex);
+ if (toIndex > size)
+ throw new IndexOutOfBoundsException("toIndex = " + toIndex);
+ if (fromIndex > toIndex)
+ throw new IllegalArgumentException("fromIndex(" + fromIndex +
+ ") > toIndex(" + toIndex + ")");
+ }
+
// Comparison and hashing
/**
* Compares the specified object with this list for equality. Returns
* {@code true} if and only if the specified object is also a list, both
*** 619,719 ****
if (index < 0 || index > size())
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
private String outOfBoundsMsg(int index) {
! return "Index: "+index+", Size: "+size();
}
- }
! class SubList<E> extends AbstractList<E> {
! private final AbstractList<E> l;
private final int offset;
! private int size;
! SubList(AbstractList<E> list, int fromIndex, int toIndex) {
! if (fromIndex < 0)
! throw new IndexOutOfBoundsException("fromIndex = " + fromIndex);
! if (toIndex > list.size())
! throw new IndexOutOfBoundsException("toIndex = " + toIndex);
! if (fromIndex > toIndex)
! throw new IllegalArgumentException("fromIndex(" + fromIndex +
! ") > toIndex(" + toIndex + ")");
! l = list;
! offset = fromIndex;
! size = toIndex - fromIndex;
! this.modCount = l.modCount;
}
public E set(int index, E element) {
rangeCheck(index);
checkForComodification();
! return l.set(index+offset, element);
}
public E get(int index) {
rangeCheck(index);
checkForComodification();
! return l.get(index+offset);
}
public int size() {
checkForComodification();
return size;
}
public void add(int index, E element) {
rangeCheckForAdd(index);
checkForComodification();
! l.add(index+offset, element);
! this.modCount = l.modCount;
! size++;
}
public E remove(int index) {
rangeCheck(index);
checkForComodification();
! E result = l.remove(index+offset);
! this.modCount = l.modCount;
! size--;
return result;
}
protected void removeRange(int fromIndex, int toIndex) {
checkForComodification();
! l.removeRange(fromIndex+offset, toIndex+offset);
! this.modCount = l.modCount;
! size -= (toIndex-fromIndex);
}
public boolean addAll(Collection<? extends E> c) {
return addAll(size, c);
}
public boolean addAll(int index, Collection<? extends E> c) {
rangeCheckForAdd(index);
int cSize = c.size();
! if (cSize==0)
return false;
-
checkForComodification();
! l.addAll(offset+index, c);
! this.modCount = l.modCount;
! size += cSize;
return true;
}
public Iterator<E> iterator() {
return listIterator();
}
! public ListIterator<E> listIterator(final int index) {
checkForComodification();
rangeCheckForAdd(index);
return new ListIterator<E>() {
! private final ListIterator<E> i = l.listIterator(index+offset);
public boolean hasNext() {
return nextIndex() < size;
}
--- 627,732 ----
if (index < 0 || index > size())
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
private String outOfBoundsMsg(int index) {
! return "Index: " + index + ", Size: " + size();
}
! private static class SubList<E> extends AbstractList<E> {
! private final AbstractList<E> root;
! private final SubList<E> parent;
private final int offset;
! protected int size;
! /**
! * Constructs a sublist of an arbitrary AbstractList, which is
! * not a SubList itself.
! */
! public SubList(AbstractList<E> root, int fromIndex, int toIndex) {
! this.root = root;
! this.parent = null;
! this.offset = fromIndex;
! this.size = toIndex - fromIndex;
! this.modCount = root.modCount;
! }
!
! /**
! * Constructs a sublist of another SubList.
! */
! protected SubList(SubList<E> parent, int fromIndex, int toIndex) {
! this.root = parent.root;
! this.parent = parent;
! this.offset = parent.offset + fromIndex;
! this.size = toIndex - fromIndex;
! this.modCount = root.modCount;
}
public E set(int index, E element) {
rangeCheck(index);
checkForComodification();
! return root.set(offset + index, element);
}
public E get(int index) {
rangeCheck(index);
checkForComodification();
! return root.get(offset + index);
}
public int size() {
checkForComodification();
return size;
}
public void add(int index, E element) {
rangeCheckForAdd(index);
checkForComodification();
! root.add(offset + index, element);
! updateSizeAndModCount(1);
}
public E remove(int index) {
rangeCheck(index);
checkForComodification();
! E result = root.remove(offset + index);
! updateSizeAndModCount(-1);
return result;
}
protected void removeRange(int fromIndex, int toIndex) {
checkForComodification();
! root.removeRange(offset + fromIndex, offset + toIndex);
! updateSizeAndModCount(fromIndex - toIndex);
}
public boolean addAll(Collection<? extends E> c) {
return addAll(size, c);
}
public boolean addAll(int index, Collection<? extends E> c) {
rangeCheckForAdd(index);
int cSize = c.size();
! if (cSize == 0)
return false;
checkForComodification();
! root.addAll(offset + index, c);
! updateSizeAndModCount(cSize);
return true;
}
public Iterator<E> iterator() {
return listIterator();
}
! public ListIterator<E> listIterator(int index) {
checkForComodification();
rangeCheckForAdd(index);
return new ListIterator<E>() {
! private final ListIterator<E> i =
! root.listIterator(offset + index);
public boolean hasNext() {
return nextIndex() < size;
}
*** 743,769 ****
return i.previousIndex() - offset;
}
public void remove() {
i.remove();
! SubList.this.modCount = l.modCount;
! size--;
}
public void set(E e) {
i.set(e);
}
public void add(E e) {
i.add(e);
! SubList.this.modCount = l.modCount;
! size++;
}
};
}
public List<E> subList(int fromIndex, int toIndex) {
return new SubList<>(this, fromIndex, toIndex);
}
private void rangeCheck(int index) {
if (index < 0 || index >= size)
--- 756,781 ----
return i.previousIndex() - offset;
}
public void remove() {
i.remove();
! updateSizeAndModCount(-1);
}
public void set(E e) {
i.set(e);
}
public void add(E e) {
i.add(e);
! updateSizeAndModCount(1);
}
};
}
public List<E> subList(int fromIndex, int toIndex) {
+ subListRangeCheck(fromIndex, toIndex, size);
return new SubList<>(this, fromIndex, toIndex);
}
private void rangeCheck(int index) {
if (index < 0 || index >= size)
*** 774,796 ****
if (index < 0 || index > size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
private String outOfBoundsMsg(int index) {
! return "Index: "+index+", Size: "+size;
}
private void checkForComodification() {
! if (this.modCount != l.modCount)
throw new ConcurrentModificationException();
}
- }
! class RandomAccessSubList<E> extends SubList<E> implements RandomAccess {
! RandomAccessSubList(AbstractList<E> list, int fromIndex, int toIndex) {
! super(list, fromIndex, toIndex);
}
public List<E> subList(int fromIndex, int toIndex) {
return new RandomAccessSubList<>(this, fromIndex, toIndex);
}
}
--- 786,834 ----
if (index < 0 || index > size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
private String outOfBoundsMsg(int index) {
! return "Index: " + index + ", Size: " + size;
}
private void checkForComodification() {
! if (root.modCount != this.modCount)
throw new ConcurrentModificationException();
}
! private void updateSizeAndModCount(int sizeChange) {
! SubList<E> slist = this;
! do {
! slist.size += sizeChange;
! slist.modCount = root.modCount;
! slist = slist.parent;
! } while (slist != null);
! }
! }
!
! private static class RandomAccessSubList<E>
! extends SubList<E> implements RandomAccess {
!
! /**
! * Constructs a sublist of an arbitrary AbstractList, which is
! * not a RandomAccessSubList itself.
! */
! RandomAccessSubList(AbstractList<E> root,
! int fromIndex, int toIndex) {
! super(root, fromIndex, toIndex);
! }
!
! /**
! * Constructs a sublist of another RandomAccessSubList.
! */
! RandomAccessSubList(RandomAccessSubList<E> parent,
! int fromIndex, int toIndex) {
! super(parent, fromIndex, toIndex);
}
public List<E> subList(int fromIndex, int toIndex) {
+ subListRangeCheck(fromIndex, toIndex, size);
return new RandomAccessSubList<>(this, fromIndex, toIndex);
}
+ }
}
< prev index next >