--- jsr166/src/main/java/util/ArrayList.java	2016/11/13 02:10:09	1.39
+++ jsr166/src/main/java/util/ArrayList.java	2016/11/13 21:07:40	1.41
@@ -501,6 +501,7 @@ public class ArrayList<E> extends Abstra
                          s - index);
         elementData[index] = element;
         size = s + 1;
+        // checkInvariants();
     }
 
     /**
@@ -524,6 +525,7 @@ public class ArrayList<E> extends Abstra
                              numMoved);
         elementData[--size] = null; // clear to let GC do its work
 
+        // checkInvariants();
         return oldValue;
     }
 
@@ -557,7 +559,7 @@ public class ArrayList<E> extends Abstra
         return false;
     }
 
-    /*
+    /**
      * Private remove method that skips bounds checking and does not
      * return the value removed.
      */
@@ -576,11 +578,7 @@ public class ArrayList<E> extends Abstra
      */
     public void clear() {
         modCount++;
-
-        // clear to let GC do its work
-        for (int i = 0; i < size; i++)
-            elementData[i] = null;
-
+        Arrays.fill(elementData, 0, size, null);
         size = 0;
     }
 
@@ -609,6 +607,7 @@ public class ArrayList<E> extends Abstra
             elementData = grow(s + numNew);
         System.arraycopy(a, 0, elementData, s, numNew);
         size = s + numNew;
+        // checkInvariants();
         return true;
     }
 
@@ -647,6 +646,7 @@ public class ArrayList<E> extends Abstra
                              numMoved);
         System.arraycopy(a, 0, elementData, index, numNew);
         size = s + numNew;
+        // checkInvariants();
         return true;
     }
 
@@ -669,16 +669,11 @@ public class ArrayList<E> extends Abstra
                     outOfBoundsMsg(fromIndex, toIndex));
         }
         modCount++;
-        int numMoved = size - toIndex;
-        System.arraycopy(elementData, toIndex, elementData, fromIndex,
-                         numMoved);
-
-        // clear to let GC do its work
-        int newSize = size - (toIndex-fromIndex);
-        for (int i = newSize; i < size; i++) {
-            elementData[i] = null;
-        }
-        size = newSize;
+        final Object[] es = elementData;
+        final int oldSize = size;
+        System.arraycopy(es, toIndex, es, fromIndex, oldSize - toIndex);
+        Arrays.fill(es, size -= (toIndex - fromIndex), oldSize, null);
+        // checkInvariants();
     }
 
     /**
@@ -721,7 +716,7 @@ public class ArrayList<E> extends Abstra
      * @see Collection#contains(Object)
      */
     public boolean removeAll(Collection<?> c) {
-        return batchRemove(c, false);
+        return batchRemove(c, false, 0, size);
     }
 
     /**
@@ -741,17 +736,17 @@ public class ArrayList<E> extends Abstra
      * @see Collection#contains(Object)
      */
     public boolean retainAll(Collection<?> c) {
-        return batchRemove(c, true);
+        return batchRemove(c, true, 0, size);
     }
 
-    private boolean batchRemove(Collection<?> c, boolean complement) {
+    boolean batchRemove(Collection<?> c, boolean complement,
+                        final int from, final int end) {
         Objects.requireNonNull(c);
         final Object[] es = elementData;
-        final int end = size;
         final boolean modified;
         int r;
         // Optimize for initial run of survivors
-        for (r = 0; r < end && c.contains(es[r]) == complement; r++)
+        for (r = from; r < end && c.contains(es[r]) == complement; r++)
             ;
         if (modified = (r < end)) {
             int w = r++;
@@ -766,10 +761,13 @@ public class ArrayList<E> extends Abstra
                 w += end - r;
                 throw ex;
             } finally {
-                modCount += end - w;
-                Arrays.fill(es, size = w, end, null);
+                final int oldSize = size, deleted = end - w;
+                modCount += deleted;
+                System.arraycopy(es, end, es, w, oldSize - end);
+                Arrays.fill(es, size -= deleted, oldSize, null);
             }
         }
+        // checkInvariants();
         return modified;
     }
 
@@ -1119,6 +1117,33 @@ public class ArrayList<E> extends Abstra
             return true;
         }
 
+        public boolean removeAll(Collection<?> c) {
+            return batchRemove(c, false);
+        }
+
+        public boolean retainAll(Collection<?> c) {
+            return batchRemove(c, true);
+        }
+
+        private boolean batchRemove(Collection<?> c, boolean complement) {
+            checkForComodification();
+            int oldSize = root.size;
+            boolean modified =
+                root.batchRemove(c, complement, offset, offset + size);
+            if (modified)
+                updateSizeAndModCount(root.size - oldSize);
+            return modified;
+        }
+
+        public boolean removeIf(Predicate<? super E> filter) {
+            checkForComodification();
+            int oldSize = root.size;
+            boolean modified = root.removeIf(filter, offset, offset + size);
+            if (modified)
+                updateSizeAndModCount(root.size - oldSize);
+            return modified;
+        }
+
         public Iterator<E> iterator() {
             return listIterator();
         }
@@ -1352,12 +1377,10 @@ public class ArrayList<E> extends Abstra
         final int expectedModCount = modCount;
         final Object[] es = elementData;
         final int size = this.size;
-        for (int i = 0; modCount == expectedModCount && i < size; i++) {
+        for (int i = 0; modCount == expectedModCount && i < size; i++)
             action.accept(elementAt(es, i));
-        }
-        if (modCount != expectedModCount) {
+        if (modCount != expectedModCount)
             throw new ConcurrentModificationException();
-        }
     }
 
     /**
@@ -1418,7 +1441,7 @@ public class ArrayList<E> extends Abstra
         private int fence; // -1 until used; then one past last index
         private int expectedModCount; // initialized when fence set
 
-        /** Create new spliterator covering the given  range */
+        /** Create new spliterator covering the given range */
         ArrayListSpliterator(ArrayList<E> list, int origin, int fence,
                              int expectedModCount) {
             this.list = list; // OK if null unless traversed
@@ -1509,15 +1532,19 @@ public class ArrayList<E> extends Abstra
     }
 
     @Override
-        public boolean removeIf(Predicate<? super E> filter) {
+    public boolean removeIf(Predicate<? super E> filter) {
+        return removeIf(filter, 0, size);
+    }
+
+    boolean removeIf(Predicate<? super E> filter,
+                     final int from, final int end) {
         Objects.requireNonNull(filter);
         int expectedModCount = modCount;
         final Object[] es = elementData;
-        final int end = size;
         final boolean modified;
         int i;
         // Optimize for initial run of survivors
-        for (i = 0; i < end && !filter.test(elementAt(es, i)); i++)
+        for (i = from; i < end && !filter.test(elementAt(es, i)); i++)
             ;
         // Tolerate predicates that reentrantly access the collection for
         // read (but writers still get CME), so traverse once to find
@@ -1531,14 +1558,19 @@ public class ArrayList<E> extends Abstra
             for (i = beg + 1; i < end; i++)
                 if (filter.test(elementAt(es, i)))
                     setBit(deathRow, i - beg);
+            if (modCount != expectedModCount)
+                throw new ConcurrentModificationException();
             int w = beg;
             for (i = beg; i < end; i++)
                 if (isClear(deathRow, i - beg))
                     es[w++] = es[i];
-            Arrays.fill(es, size = w, end, null);
+            final int oldSize = size;
+            System.arraycopy(es, end, es, w, oldSize - end);
+            Arrays.fill(es, size -= (end - w), oldSize, null);
         }
         if (modCount != expectedModCount)
             throw new ConcurrentModificationException();
+        // checkInvariants();
         return modified;
     }
 
@@ -1548,13 +1580,12 @@ public class ArrayList<E> extends Abstra
         final int expectedModCount = modCount;
         final Object[] es = elementData;
         final int size = this.size;
-        for (int i=0; modCount == expectedModCount && i < size; i++) {
+        for (int i = 0; modCount == expectedModCount && i < size; i++)
             es[i] = operator.apply(elementAt(es, i));
-        }
-        if (modCount != expectedModCount) {
+        if (modCount != expectedModCount)
             throw new ConcurrentModificationException();
-        }
         modCount++;
+        // checkInvariants();
     }
 
     @Override
@@ -1562,9 +1593,14 @@ public class ArrayList<E> extends Abstra
     public void sort(Comparator<? super E> c) {
         final int expectedModCount = modCount;
         Arrays.sort((E[]) elementData, 0, size, c);
-        if (modCount != expectedModCount) {
+        if (modCount != expectedModCount)
             throw new ConcurrentModificationException();
-        }
         modCount++;
+        // checkInvariants();
+    }
+
+    void checkInvariants() {
+        // assert size >= 0;
+        // assert size == elementData.length || elementData[size] == null;
     }
 }