src/java.base/share/classes/java/util/AbstractList.java

rev 11832 : [mq]: 8079136-NestedSubList

@@ -491,13 +491,24 @@
      *         {@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));
+                new RandomAccessSubList<>(this, null, 0, fromIndex, toIndex) :
+                new SubList<>(this, null, 0, 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
 
     /**

@@ -619,101 +630,93 @@
         if (index < 0 || index > size())
             throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
     }
 
     private String outOfBoundsMsg(int index) {
-        return "Index: "+index+", Size: "+size();
+        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;
+    final AbstractList<E> root;
+    final SubList<E> parent;
+    final int offset;
+    int size;
+
+    SubList(AbstractList<E> root, SubList<E> parent,
+            int offset, int fromIndex, int toIndex) {
+        this.root = root;
+        this.parent = parent;
+        this.offset = offset + fromIndex;
+        this.size = toIndex - fromIndex;
+        this.modCount = root.modCount;
     }
 
     public E set(int index, E element) {
         rangeCheck(index);
         checkForComodification();
-        return l.set(index+offset, element);
+        return root.set(offset + index, element);
     }
 
     public E get(int index) {
         rangeCheck(index);
         checkForComodification();
-        return l.get(index+offset);
+        return root.get(offset + index);
     }
 
     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++;
+        root.add(offset + index, element);
+        updateSizeAndModCount(1);
     }
 
     public E remove(int index) {
         rangeCheck(index);
         checkForComodification();
-        E result = l.remove(index+offset);
-        this.modCount = l.modCount;
-        size--;
+        E result = root.remove(offset + index);
+        updateSizeAndModCount(-1);
         return result;
     }
 
     protected void removeRange(int fromIndex, int toIndex) {
         checkForComodification();
-        l.removeRange(fromIndex+offset, toIndex+offset);
-        this.modCount = l.modCount;
-        size -= (toIndex-fromIndex);
+        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)
+        if (cSize == 0)
             return false;
-
         checkForComodification();
-        l.addAll(offset+index, c);
-        this.modCount = l.modCount;
-        size += cSize;
+        root.addAll(offset + index, c);
+        updateSizeAndModCount(cSize);
         return true;
     }
 
     public Iterator<E> iterator() {
         return listIterator();
     }
 
-    public ListIterator<E> listIterator(final int index) {
+    public ListIterator<E> listIterator(int index) {
         checkForComodification();
         rangeCheckForAdd(index);
 
         return new ListIterator<E>() {
-            private final ListIterator<E> i = l.listIterator(index+offset);
+            private final ListIterator<E> i =
+                    root.listIterator(offset + index);
 
             public boolean hasNext() {
                 return nextIndex() < size;
             }
 

@@ -743,28 +746,27 @@
                 return i.previousIndex() - offset;
             }
 
             public void remove() {
                 i.remove();
-                SubList.this.modCount = l.modCount;
-                size--;
+                updateSizeAndModCount(-1);
             }
 
             public void set(E e) {
                 i.set(e);
             }
 
             public void add(E e) {
                 i.add(e);
-                SubList.this.modCount = l.modCount;
-                size++;
+                updateSizeAndModCount(1);
             }
         };
     }
 
     public List<E> subList(int fromIndex, int toIndex) {
-        return new SubList<>(this, fromIndex, toIndex);
+        subListRangeCheck(fromIndex, toIndex, size);
+        return new SubList<>(root, this, offset, fromIndex, toIndex);
     }
 
     private void rangeCheck(int index) {
         if (index < 0 || index >= size)
             throw new IndexOutOfBoundsException(outOfBoundsMsg(index));

@@ -774,23 +776,37 @@
         if (index < 0 || index > size)
             throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
     }
 
     private String outOfBoundsMsg(int index) {
-        return "Index: "+index+", Size: "+size;
+        return "Index: " + index + ", Size: " + size;
     }
 
     private void checkForComodification() {
-        if (this.modCount != l.modCount)
+        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);
+    }
 }
 
-class RandomAccessSubList<E> extends SubList<E> implements RandomAccess {
-    RandomAccessSubList(AbstractList<E> list, int fromIndex, int toIndex) {
-        super(list, fromIndex, toIndex);
+class RandomAccessSubList<E> extends SubList<E>
+        implements RandomAccess {
+
+    RandomAccessSubList(AbstractList<E> root, SubList<E> parent,
+            int offset, int fromIndex, int toIndex) {
+        super(root, parent, offset, fromIndex, toIndex);
     }
 
     public List<E> subList(int fromIndex, int toIndex) {
-        return new RandomAccessSubList<>(this, fromIndex, toIndex);
+        subListRangeCheck(fromIndex, toIndex, size);
+        return new RandomAccessSubList<>(root, this, offset,
+                fromIndex, toIndex);
     }
 }