--- jsr166/src/main/java/util/ArrayList.java	2016/11/04 03:09:27	1.37
+++ jsr166/src/main/java/util/ArrayList.java	2016/11/14 21:16:43	1.42
@@ -423,6 +423,11 @@ public class ArrayList<E> extends Abstra
         return (E) elementData[index];
     }
 
+    @SuppressWarnings("unchecked")
+    static <E> E elementAt(Object[] es, int index) {
+        return (E) es[index];
+    }
+
     /**
      * Returns the element at the specified position in this list.
      *
@@ -496,6 +501,7 @@ public class ArrayList<E> extends Abstra
                          s - index);
         elementData[index] = element;
         size = s + 1;
+        // checkInvariants();
     }
 
     /**
@@ -519,6 +525,7 @@ public class ArrayList<E> extends Abstra
                              numMoved);
         elementData[--size] = null; // clear to let GC do its work
 
+        // checkInvariants();
         return oldValue;
     }
 
@@ -552,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.
      */
@@ -571,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;
     }
 
@@ -604,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;
     }
 
@@ -642,6 +646,7 @@ public class ArrayList<E> extends Abstra
                              numMoved);
         System.arraycopy(a, 0, elementData, index, numNew);
         size = s + numNew;
+        // checkInvariants();
         return true;
     }
 
@@ -664,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();
     }
 
     /**
@@ -716,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);
     }
 
     /**
@@ -736,36 +736,38 @@ 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 size = this.size;
         final boolean modified;
         int r;
         // Optimize for initial run of survivors
-        for (r = 0; r < size; r++)
-            if (c.contains(es[r]) != complement)
-                break;
-        if (modified = (r < size)) {
+        for (r = from; r < end && c.contains(es[r]) == complement; r++)
+            ;
+        if (modified = (r < end)) {
             int w = r++;
             try {
-                for (Object e; r < size; r++)
+                for (Object e; r < end; r++)
                     if (c.contains(e = es[r]) == complement)
                         es[w++] = e;
             } catch (Throwable ex) {
                 // Preserve behavioral compatibility with AbstractCollection,
                 // even if c.contains() throws.
-                System.arraycopy(es, r, es, w, size - r);
-                w += size - r;
+                System.arraycopy(es, r, es, w, end - r);
+                w += end - r;
                 throw ex;
             } finally {
-                modCount += size - w;
-                Arrays.fill(es, (this.size = w), size, 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;
     }
 
@@ -1115,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();
         }
@@ -1178,7 +1207,8 @@ public class ArrayList<E> extends Abstra
                         consumer.accept((E) elementData[offset + (i++)]);
                     }
                     // update once at end of iteration to reduce heap write traffic
-                    lastRet = cursor = i;
+                    cursor = i;
+                    lastRet = i - 1;
                     checkForComodification();
                 }
 
@@ -1346,15 +1376,12 @@ public class ArrayList<E> extends Abstra
     public void forEach(Consumer<? super E> action) {
         Objects.requireNonNull(action);
         final int expectedModCount = modCount;
-        @SuppressWarnings("unchecked")
-        final E[] elementData = (E[]) this.elementData;
+        final Object[] es = elementData;
         final int size = this.size;
-        for (int i=0; modCount == expectedModCount && i < size; i++) {
-            action.accept(elementData[i]);
-        }
-        if (modCount != expectedModCount) {
+        for (int i = 0; modCount == expectedModCount && i < size; i++)
+            action.accept(elementAt(es, i));
+        if (modCount != expectedModCount)
             throw new ConcurrentModificationException();
-        }
     }
 
     /**
@@ -1415,7 +1442,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
@@ -1493,54 +1520,73 @@ public class ArrayList<E> extends Abstra
         }
     }
 
-    @SuppressWarnings("unchecked")
+    // A tiny bit set implementation
+
+    private static long[] nBits(int n) {
+        return new long[((n - 1) >> 6) + 1];
+    }
+    private static void setBit(long[] bits, int i) {
+        bits[i >> 6] |= 1L << i;
+    }
+    private static boolean isClear(long[] bits, int i) {
+        return (bits[i >> 6] & (1L << i)) == 0;
+    }
+
     @Override
     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 size = this.size;
         final boolean modified;
-        int r;
+        int i;
         // Optimize for initial run of survivors
-        for (r = 0; r < size; r++)
-            if (filter.test((E) es[r]))
-                break;
-        if (modified = (r < size)) {
+        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
+        // elements to delete, a second pass to physically expunge.
+        if (modified = (i < end)) {
             expectedModCount++;
             modCount++;
-            int w = r++;
-            try {
-                for (E e; r < size; r++)
-                    if (!filter.test(e = (E) es[r]))
-                        es[w++] = e;
-            } catch (Throwable ex) {
-                // copy remaining elements
-                System.arraycopy(es, r, es, w, size - r);
-                w += size - r;
-                throw ex;
-            } finally {
-                Arrays.fill(es, (this.size = w), size, null);
-            }
+            final int beg = i;
+            final long[] deathRow = nBits(end - beg);
+            deathRow[0] = 1L;   // set bit 0
+            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];
+            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;
     }
 
     @Override
-    @SuppressWarnings("unchecked")
     public void replaceAll(UnaryOperator<E> operator) {
         Objects.requireNonNull(operator);
         final int expectedModCount = modCount;
+        final Object[] es = elementData;
         final int size = this.size;
-        for (int i=0; modCount == expectedModCount && i < size; i++) {
-            elementData[i] = operator.apply((E) elementData[i]);
-        }
-        if (modCount != expectedModCount) {
+        for (int i = 0; modCount == expectedModCount && i < size; i++)
+            es[i] = operator.apply(elementAt(es, i));
+        if (modCount != expectedModCount)
             throw new ConcurrentModificationException();
-        }
         modCount++;
+        // checkInvariants();
     }
 
     @Override
@@ -1548,9 +1594,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;
     }
 }