< prev index next >

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

Print this page
rev 11832 : [mq]: 8079136-NestedSubList

@@ -1004,252 +1004,11 @@
      * @throws IndexOutOfBoundsException {@inheritDoc}
      * @throws IllegalArgumentException {@inheritDoc}
      */
     public List<E> subList(int fromIndex, int toIndex) {
         subListRangeCheck(fromIndex, toIndex, size);
-        return new SubList(this, 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 + ")");
-    }
-
-    private class SubList extends AbstractList<E> implements RandomAccess {
-        private final AbstractList<E> parent;
-        private final int parentOffset;
-        private final int offset;
-        int size;
-
-        SubList(AbstractList<E> parent,
-                int offset, int fromIndex, int toIndex) {
-            this.parent = parent;
-            this.parentOffset = fromIndex;
-            this.offset = offset + fromIndex;
-            this.size = toIndex - fromIndex;
-            this.modCount = ArrayList.this.modCount;
-        }
-
-        public E set(int index, E e) {
-            rangeCheck(index);
-            checkForComodification();
-            E oldValue = ArrayList.this.elementData(offset + index);
-            ArrayList.this.elementData[offset + index] = e;
-            return oldValue;
-        }
-
-        public E get(int index) {
-            rangeCheck(index);
-            checkForComodification();
-            return ArrayList.this.elementData(offset + index);
-        }
-
-        public int size() {
-            checkForComodification();
-            return this.size;
-        }
-
-        public void add(int index, E e) {
-            rangeCheckForAdd(index);
-            checkForComodification();
-            parent.add(parentOffset + index, e);
-            this.modCount = parent.modCount;
-            this.size++;
-        }
-
-        public E remove(int index) {
-            rangeCheck(index);
-            checkForComodification();
-            E result = parent.remove(parentOffset + index);
-            this.modCount = parent.modCount;
-            this.size--;
-            return result;
-        }
-
-        protected void removeRange(int fromIndex, int toIndex) {
-            checkForComodification();
-            parent.removeRange(parentOffset + fromIndex,
-                               parentOffset + toIndex);
-            this.modCount = parent.modCount;
-            this.size -= toIndex - fromIndex;
-        }
-
-        public boolean addAll(Collection<? extends E> c) {
-            return addAll(this.size, c);
-        }
-
-        public boolean addAll(int index, Collection<? extends E> c) {
-            rangeCheckForAdd(index);
-            int cSize = c.size();
-            if (cSize==0)
-                return false;
-
-            checkForComodification();
-            parent.addAll(parentOffset + index, c);
-            this.modCount = parent.modCount;
-            this.size += cSize;
-            return true;
-        }
-
-        public Iterator<E> iterator() {
-            return listIterator();
-        }
-
-        public ListIterator<E> listIterator(final int index) {
-            checkForComodification();
-            rangeCheckForAdd(index);
-            final int offset = this.offset;
-
-            return new ListIterator<E>() {
-                int cursor = index;
-                int lastRet = -1;
-                int expectedModCount = ArrayList.this.modCount;
-
-                public boolean hasNext() {
-                    return cursor != SubList.this.size;
-                }
-
-                @SuppressWarnings("unchecked")
-                public E next() {
-                    checkForComodification();
-                    int i = cursor;
-                    if (i >= SubList.this.size)
-                        throw new NoSuchElementException();
-                    Object[] elementData = ArrayList.this.elementData;
-                    if (offset + i >= elementData.length)
-                        throw new ConcurrentModificationException();
-                    cursor = i + 1;
-                    return (E) elementData[offset + (lastRet = i)];
-                }
-
-                public boolean hasPrevious() {
-                    return cursor != 0;
-                }
-
-                @SuppressWarnings("unchecked")
-                public E previous() {
-                    checkForComodification();
-                    int i = cursor - 1;
-                    if (i < 0)
-                        throw new NoSuchElementException();
-                    Object[] elementData = ArrayList.this.elementData;
-                    if (offset + i >= elementData.length)
-                        throw new ConcurrentModificationException();
-                    cursor = i;
-                    return (E) elementData[offset + (lastRet = i)];
-                }
-
-                @SuppressWarnings("unchecked")
-                public void forEachRemaining(Consumer<? super E> consumer) {
-                    Objects.requireNonNull(consumer);
-                    final int size = SubList.this.size;
-                    int i = cursor;
-                    if (i >= size) {
-                        return;
-                    }
-                    final Object[] elementData = ArrayList.this.elementData;
-                    if (offset + i >= elementData.length) {
-                        throw new ConcurrentModificationException();
-                    }
-                    while (i != size && modCount == expectedModCount) {
-                        consumer.accept((E) elementData[offset + (i++)]);
-                    }
-                    // update once at end of iteration to reduce heap write traffic
-                    lastRet = cursor = i;
-                    checkForComodification();
-                }
-
-                public int nextIndex() {
-                    return cursor;
-                }
-
-                public int previousIndex() {
-                    return cursor - 1;
-                }
-
-                public void remove() {
-                    if (lastRet < 0)
-                        throw new IllegalStateException();
-                    checkForComodification();
-
-                    try {
-                        SubList.this.remove(lastRet);
-                        cursor = lastRet;
-                        lastRet = -1;
-                        expectedModCount = ArrayList.this.modCount;
-                    } catch (IndexOutOfBoundsException ex) {
-                        throw new ConcurrentModificationException();
-                    }
-                }
-
-                public void set(E e) {
-                    if (lastRet < 0)
-                        throw new IllegalStateException();
-                    checkForComodification();
-
-                    try {
-                        ArrayList.this.set(offset + lastRet, e);
-                    } catch (IndexOutOfBoundsException ex) {
-                        throw new ConcurrentModificationException();
-                    }
-                }
-
-                public void add(E e) {
-                    checkForComodification();
-
-                    try {
-                        int i = cursor;
-                        SubList.this.add(i, e);
-                        cursor = i + 1;
-                        lastRet = -1;
-                        expectedModCount = ArrayList.this.modCount;
-                    } catch (IndexOutOfBoundsException ex) {
-                        throw new ConcurrentModificationException();
-                    }
-                }
-
-                final void checkForComodification() {
-                    if (expectedModCount != ArrayList.this.modCount)
-                        throw new ConcurrentModificationException();
-                }
-            };
-        }
-
-        public List<E> subList(int fromIndex, int toIndex) {
-            subListRangeCheck(fromIndex, toIndex, size);
-            return new SubList(this, offset, fromIndex, toIndex);
-        }
-
-        private void rangeCheck(int index) {
-            if (index < 0 || index >= this.size)
-                throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
-        }
-
-        private void rangeCheckForAdd(int index) {
-            if (index < 0 || index > this.size)
-                throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
-        }
-
-        private String outOfBoundsMsg(int index) {
-            return "Index: "+index+", Size: "+this.size;
-        }
-
-        private void checkForComodification() {
-            if (ArrayList.this.modCount != this.modCount)
-                throw new ConcurrentModificationException();
-        }
-
-        public Spliterator<E> spliterator() {
-            checkForComodification();
-            return new ArrayListSpliterator<>(ArrayList.this, offset,
-                                              offset + this.size, this.modCount);
-        }
+        return new ArraySubList<>(this, null, 0, fromIndex, toIndex);
     }
 
     @Override
     public void forEach(Consumer<? super E> action) {
         Objects.requireNonNull(action);

@@ -1468,5 +1227,239 @@
             throw new ConcurrentModificationException();
         }
         modCount++;
     }
 }
+
+class ArraySubList<E> extends AbstractList<E> implements RandomAccess {
+    final ArrayList<E> root;
+    final ArraySubList<E> parent;
+    final int offset;
+    int size;
+
+    ArraySubList(ArrayList<E> root, ArraySubList<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();
+        E oldValue = root.elementData(offset + index);
+        root.elementData[offset + index] = element;
+        return oldValue;
+    }
+
+    public E get(int index) {
+        rangeCheck(index);
+        checkForComodification();
+        return root.elementData(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(this.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>() {
+            int cursor = index;
+            int lastRet = -1;
+            int expectedModCount = root.modCount;
+
+            public boolean hasNext() {
+                return cursor != ArraySubList.this.size;
+            }
+
+            @SuppressWarnings("unchecked")
+            public E next() {
+                checkForComodification();
+                int i = cursor;
+                if (i >= ArraySubList.this.size)
+                    throw new NoSuchElementException();
+                Object[] elementData = root.elementData;
+                if (offset + i >= elementData.length)
+                    throw new ConcurrentModificationException();
+                cursor = i + 1;
+                return (E) elementData[offset + (lastRet = i)];
+            }
+
+            public boolean hasPrevious() {
+                return cursor != 0;
+            }
+
+            @SuppressWarnings("unchecked")
+            public E previous() {
+                checkForComodification();
+                int i = cursor - 1;
+                if (i < 0)
+                    throw new NoSuchElementException();
+                Object[] elementData = root.elementData;
+                if (offset + i >= elementData.length)
+                    throw new ConcurrentModificationException();
+                cursor = i;
+                return (E) elementData[offset + (lastRet = i)];
+            }
+
+            @SuppressWarnings("unchecked")
+            public void forEachRemaining(Consumer<? super E> consumer) {
+                Objects.requireNonNull(consumer);
+                final int size = ArraySubList.this.size;
+                int i = cursor;
+                if (i >= size) {
+                    return;
+                }
+                final Object[] elementData = root.elementData;
+                if (offset + i >= elementData.length) {
+                    throw new ConcurrentModificationException();
+                }
+                while (i != size && modCount == expectedModCount) {
+                    consumer.accept((E) elementData[offset + (i++)]);
+                }
+                // update once at end of iteration to reduce heap write traffic
+                lastRet = cursor = i;
+                checkForComodification();
+            }
+
+            public int nextIndex() {
+                return cursor;
+            }
+
+            public int previousIndex() {
+                return cursor - 1;
+            }
+
+            public void remove() {
+                if (lastRet < 0)
+                    throw new IllegalStateException();
+                checkForComodification();
+
+                try {
+                    ArraySubList.this.remove(lastRet);
+                    cursor = lastRet;
+                    lastRet = -1;
+                    expectedModCount = root.modCount;
+                } catch (IndexOutOfBoundsException ex) {
+                    throw new ConcurrentModificationException();
+                }
+            }
+
+            public void set(E e) {
+                if (lastRet < 0)
+                    throw new IllegalStateException();
+                checkForComodification();
+
+                try {
+                    root.set(offset + lastRet, e);
+                } catch (IndexOutOfBoundsException ex) {
+                    throw new ConcurrentModificationException();
+                }
+            }
+
+            public void add(E e) {
+                checkForComodification();
+
+                try {
+                    int i = cursor;
+                    ArraySubList.this.add(i, e);
+                    cursor = i + 1;
+                    lastRet = -1;
+                    expectedModCount = root.modCount;
+                } catch (IndexOutOfBoundsException ex) {
+                    throw new ConcurrentModificationException();
+                }
+            }
+
+            final void checkForComodification() {
+                if (root.modCount != expectedModCount)
+                    throw new ConcurrentModificationException();
+            }
+        };
+    }
+
+    public List<E> subList(int fromIndex, int toIndex) {
+        subListRangeCheck(fromIndex, toIndex, size);
+        return new ArraySubList<>(root, this, offset, fromIndex, toIndex);
+    }
+
+    private void rangeCheck(int index) {
+        if (index < 0 || index >= size)
+            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
+    }
+
+    private void rangeCheckForAdd(int index) {
+        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 != modCount)
+            throw new ConcurrentModificationException();
+    }
+
+    private void updateSizeAndModCount(int sizeChange) {
+        ArraySubList<E> slist = this;
+        do {
+            slist.size += sizeChange;
+            slist.modCount = root.modCount;
+            slist = slist.parent;
+        } while (slist != null);
+    }
+
+    public Spliterator<E> spliterator() {
+        checkForComodification();
+        return new ArrayList.ArrayListSpliterator<>(root, offset,
+                offset + size, modCount);
+    }
+}
+
< prev index next >