changeset 8342:3ca33647db95

8001647: default methods for Collections - forEach, removeIf, replaceAll, sort Reviewed-by: alanb, dholmes, mduigou, psandoz, smarks Contributed-by: Akhil Arora <akhil.arora@oracle.com>, Arne Siegel <v.a.ammodytes@googlemail.com>, Brian Goetz <brian.goetz@oracle.com>
author akhil
date Mon, 22 Apr 2013 09:19:34 -0700
parents 22a27dfd0510
children 2a78d8f1fec1
files src/share/classes/java/util/ArrayList.java src/share/classes/java/util/Collection.java src/share/classes/java/util/Collections.java src/share/classes/java/util/List.java src/share/classes/java/util/Vector.java src/share/classes/java/util/concurrent/CopyOnWriteArrayList.java test/java/util/Collection/CollectionDefaults.java test/java/util/Collection/ListDefaults.java test/java/util/Collection/testlibrary/CollectionAsserts.java test/java/util/Collection/testlibrary/CollectionSupplier.java
diffstat 10 files changed, 1796 insertions(+), 1 deletions(-) [+]
line wrap: on
line diff
--- a/src/share/classes/java/util/ArrayList.java	Mon Apr 22 11:39:53 2013 +0800
+++ b/src/share/classes/java/util/ArrayList.java	Mon Apr 22 09:19:34 2013 -0700
@@ -25,6 +25,10 @@
 
 package java.util;
 
+import java.util.function.Consumer;
+import java.util.function.Predicate;
+import java.util.function.UnaryOperator;
+
 /**
  * Resizable-array implementation of the <tt>List</tt> interface.  Implements
  * all optional list operations, and permits all elements, including
@@ -1168,4 +1172,88 @@
                 throw new ConcurrentModificationException();
         }
     }
+
+    @Override
+    public void forEach(Consumer<? super E> action) {
+        Objects.requireNonNull(action);
+        final int expectedModCount = modCount;
+        @SuppressWarnings("unchecked")
+        final E[] elementData = (E[]) this.elementData;
+        final int size = this.size;
+        for (int i=0; modCount == expectedModCount && i < size; i++) {
+            action.accept(elementData[i]);
+        }
+        if (modCount != expectedModCount) {
+            throw new ConcurrentModificationException();
+        }
+    }
+
+    @Override
+    public boolean removeIf(Predicate<? super E> filter) {
+        Objects.requireNonNull(filter);
+        // figure out which elements are to be removed
+        // any exception thrown from the filter predicate at this stage
+        // will leave the collection unmodified
+        int removeCount = 0;
+        final BitSet removeSet = new BitSet(size);
+        final int expectedModCount = modCount;
+        final int size = this.size;
+        for (int i=0; modCount == expectedModCount && i < size; i++) {
+            @SuppressWarnings("unchecked")
+            final E element = (E) elementData[i];
+            if (filter.test(element)) {
+                removeSet.set(i);
+                removeCount++;
+            }
+        }
+        if (modCount != expectedModCount) {
+            throw new ConcurrentModificationException();
+        }
+
+        // shift surviving elements left over the spaces left by removed elements
+        final boolean anyToRemove = removeCount > 0;
+        if (anyToRemove) {
+            final int newSize = size - removeCount;
+            for (int i=0, j=0; (i < size) && (j < newSize); i++, j++) {
+                i = removeSet.nextClearBit(i);
+                elementData[j] = elementData[i];
+            }
+            for (int k=newSize; k < size; k++) {
+                elementData[k] = null;  // Let gc do its work
+            }
+            this.size = newSize;
+            if (modCount != expectedModCount) {
+                throw new ConcurrentModificationException();
+            }
+            modCount++;
+        }
+
+        return anyToRemove;
+    }
+
+    @Override
+    @SuppressWarnings("unchecked")
+    public void replaceAll(UnaryOperator<E> operator) {
+        Objects.requireNonNull(operator);
+        final int expectedModCount = modCount;
+        final int size = this.size;
+        for (int i=0; modCount == expectedModCount && i < size; i++) {
+            elementData[i] = operator.apply((E) elementData[i]);
+        }
+        if (modCount != expectedModCount) {
+            throw new ConcurrentModificationException();
+        }
+        modCount++;
+    }
+
+    @Override
+    @SuppressWarnings("unchecked")
+    public void sort(Comparator<? super E> c) {
+        final int expectedModCount = modCount;
+        Arrays.sort((E[]) elementData, 0, size, c);
+        if (modCount != expectedModCount) {
+            throw new ConcurrentModificationException();
+        }
+        modCount++;
+    }
 }
--- a/src/share/classes/java/util/Collection.java	Mon Apr 22 11:39:53 2013 +0800
+++ b/src/share/classes/java/util/Collection.java	Mon Apr 22 09:19:34 2013 -0700
@@ -25,6 +25,8 @@
 
 package java.util;
 
+import java.util.function.Predicate;
+
 /**
  * The root interface in the <i>collection hierarchy</i>.  A collection
  * represents a group of objects, known as its <i>elements</i>.  Some
@@ -373,6 +375,40 @@
     boolean removeAll(Collection<?> c);
 
     /**
+     * Removes all of the elements of this collection that satisfy the given
+     * predicate.  Errors or runtime exceptions thrown by the predicate are
+     * relayed to the caller.
+     *
+     * @implSpec
+     * The default implementation traverses all elements of the collection using
+     * its {@link #iterator}.  Each matching element is removed using
+     * {@link Iterator#remove()}.  If the collection's iterator does not
+     * support removal then an {@code UnsupportedOperationException} will be
+     * thrown on the first matching element.
+     *
+     * @param filter a predicate which returns {@code true} for elements to be
+     *        removed
+     * @return {@code true} if any elements were removed
+     * @throws NullPointerException if the specified filter is null
+     * @throws UnsupportedOperationException if the {@code remove}
+     *         method is not supported by this collection's
+     *         {@link #iterator}
+     * @since 1.8
+     */
+    default boolean removeIf(Predicate<? super E> filter) {
+        Objects.requireNonNull(filter);
+        boolean removed = false;
+        final Iterator<E> each = iterator();
+        while (each.hasNext()) {
+            if (filter.test(each.next())) {
+                each.remove();
+                removed = true;
+            }
+        }
+        return removed;
+    }
+
+    /**
      * Retains only the elements in this collection that are contained in the
      * specified collection (optional operation).  In other words, removes from
      * this collection all of its elements that are not contained in the
--- a/src/share/classes/java/util/Collections.java	Mon Apr 22 11:39:53 2013 +0800
+++ b/src/share/classes/java/util/Collections.java	Mon Apr 22 09:19:34 2013 -0700
@@ -30,7 +30,10 @@
 import java.lang.reflect.Array;
 import java.util.function.BiConsumer;
 import java.util.function.BiFunction;
+import java.util.function.Consumer;
 import java.util.function.Function;
+import java.util.function.Predicate;
+import java.util.function.UnaryOperator;
 
 /**
  * This class consists exclusively of static methods that operate on or return
@@ -1110,6 +1113,15 @@
         public void clear() {
             throw new UnsupportedOperationException();
         }
+
+        @Override
+        public void forEach(Consumer<? super E> action) {
+            c.forEach(action);
+        }
+        @Override
+        public boolean removeIf(Predicate<? super E> filter) {
+            throw new UnsupportedOperationException();
+        }
     }
 
     /**
@@ -1240,6 +1252,16 @@
         public boolean addAll(int index, Collection<? extends E> c) {
             throw new UnsupportedOperationException();
         }
+
+        @Override
+        public void replaceAll(UnaryOperator<E> operator) {
+            throw new UnsupportedOperationException();
+        }
+        @Override
+        public void sort(Comparator<? super E> c) {
+            throw new UnsupportedOperationException();
+        }
+
         public ListIterator<E> listIterator()   {return listIterator(0);}
 
         public ListIterator<E> listIterator(final int index) {
@@ -1742,6 +1764,15 @@
         private void writeObject(ObjectOutputStream s) throws IOException {
             synchronized (mutex) {s.defaultWriteObject();}
         }
+
+        @Override
+        public void forEach(Consumer<? super E> action) {
+            synchronized (mutex) {c.forEach(action);}
+        }
+        @Override
+        public boolean removeIf(Predicate<? super E> filter) {
+            synchronized (mutex) {return c.removeIf(filter);}
+        }
     }
 
     /**
@@ -1996,6 +2027,15 @@
             }
         }
 
+        @Override
+        public void replaceAll(UnaryOperator<E> operator) {
+            synchronized (mutex) {list.replaceAll(operator);}
+        }
+        @Override
+        public void sort(Comparator<? super E> c) {
+            synchronized (mutex) {list.sort(c);}
+        }
+
         /**
          * SynchronizedRandomAccessList instances are serialized as
          * SynchronizedList instances to allow them to be deserialized
@@ -2492,6 +2532,15 @@
             // element as we added it)
             return c.addAll(checkedCopyOf(coll));
         }
+
+        @Override
+        public void forEach(Consumer<? super E> action) {
+            c.forEach(action);
+        }
+        @Override
+        public boolean removeIf(Predicate<? super E> filter) {
+            return c.removeIf(filter);
+        }
     }
 
     /**
@@ -2753,6 +2802,15 @@
         public List<E> subList(int fromIndex, int toIndex) {
             return new CheckedList<>(list.subList(fromIndex, toIndex), type);
         }
+
+        @Override
+        public void replaceAll(UnaryOperator<E> operator) {
+            list.replaceAll(operator);
+        }
+        @Override
+        public void sort(Comparator<? super E> c) {
+            list.sort(c);
+        }
     }
 
     /**
@@ -3416,6 +3474,16 @@
             return a;
         }
 
+        @Override
+        public void forEach(Consumer<? super E> action) {
+            Objects.requireNonNull(action);
+        }
+        @Override
+        public boolean removeIf(Predicate<? super E> filter) {
+            Objects.requireNonNull(filter);
+            return false;
+        }
+
         // Preserves singleton property
         private Object readResolve() {
             return EMPTY_SET;
@@ -3523,6 +3591,16 @@
         public E last() {
             throw new NoSuchElementException();
         }
+
+        @Override
+        public void forEach(Consumer<? super E> action) {
+            Objects.requireNonNull(action);
+        }
+        @Override
+        public boolean removeIf(Predicate<? super E> filter) {
+            Objects.requireNonNull(filter);
+            return false;
+        }
     }
 
     /**
@@ -3592,6 +3670,24 @@
 
         public int hashCode() { return 1; }
 
+        @Override
+        public void forEach(Consumer<? super E> action) {
+            Objects.requireNonNull(action);
+        }
+        @Override
+        public boolean removeIf(Predicate<? super E> filter) {
+            Objects.requireNonNull(filter);
+            return false;
+        }
+        @Override
+        public void replaceAll(UnaryOperator<E> operator) {
+            Objects.requireNonNull(operator);
+        }
+        @Override
+        public void sort(Comparator<? super E> c) {
+            Objects.requireNonNull(c);
+        }
+
         // Preserves singleton property
         private Object readResolve() {
             return EMPTY_LIST;
@@ -3770,6 +3866,15 @@
         public int size() {return 1;}
 
         public boolean contains(Object o) {return eq(o, element);}
+
+        @Override
+        public void forEach(Consumer<? super E> action) {
+            action.accept(element);
+        }
+        @Override
+        public boolean removeIf(Predicate<? super E> filter) {
+            throw new UnsupportedOperationException();
+        }
     }
 
     /**
@@ -3810,6 +3915,22 @@
               throw new IndexOutOfBoundsException("Index: "+index+", Size: 1");
             return element;
         }
+
+        @Override
+        public void forEach(Consumer<? super E> action) {
+            action.accept(element);
+        }
+        @Override
+        public boolean removeIf(Predicate<? super E> filter) {
+            throw new UnsupportedOperationException();
+        }
+        @Override
+        public void replaceAll(UnaryOperator<E> operator) {
+            throw new UnsupportedOperationException();
+        }
+        @Override
+        public void sort(Comparator<? super E> c) {
+        }
     }
 
     /**
@@ -4408,6 +4529,15 @@
         public boolean retainAll(Collection<?> c)   {return s.retainAll(c);}
         // addAll is the only inherited implementation
 
+        @Override
+        public void forEach(Consumer<? super E> action) {
+            s.forEach(action);
+        }
+        @Override
+        public boolean removeIf(Predicate<? super E> filter) {
+            return s.removeIf(filter);
+        }
+
         private static final long serialVersionUID = 2454657854757543876L;
 
         private void readObject(java.io.ObjectInputStream stream)
@@ -4466,5 +4596,14 @@
         public boolean removeAll(Collection<?> c)   {return q.removeAll(c);}
         public boolean retainAll(Collection<?> c)   {return q.retainAll(c);}
         // We use inherited addAll; forwarding addAll would be wrong
+
+        @Override
+        public void forEach(Consumer<? super E> action) {
+            q.forEach(action);
+        }
+        @Override
+        public boolean removeIf(Predicate<? super E> filter) {
+            return q.removeIf(filter);
+        }
     }
 }
--- a/src/share/classes/java/util/List.java	Mon Apr 22 11:39:53 2013 +0800
+++ b/src/share/classes/java/util/List.java	Mon Apr 22 09:19:34 2013 -0700
@@ -25,6 +25,8 @@
 
 package java.util;
 
+import java.util.function.UnaryOperator;
+
 /**
  * An ordered collection (also known as a <i>sequence</i>).  The user of this
  * interface has precise control over where in the list each element is
@@ -375,6 +377,64 @@
     boolean retainAll(Collection<?> c);
 
     /**
+     * Replaces each element of this list with the result of applying the
+     * operator to that element.  Errors or runtime exceptions thrown by
+     * the operator are relayed to the caller.
+     *
+     * @implSpec
+     * The default implementation is equivalent to, for this {@code list}:
+     * <pre>
+     * final ListIterator<E> li = list.listIterator();
+     * while (li.hasNext()) {
+     *   li.set(operator.apply(li.next()));
+     * }
+     * </pre>
+     * If the list's list-iterator does not support the {@code set} operation
+     * then an {@code UnsupportedOperationException} will be thrown when
+     * replacing the first element.
+     *
+     * @param operator the operator to apply to each element
+     * @throws UnsupportedOperationException if the {@code set}
+     *         operation is not supported by this list
+     * @throws NullPointerException if the specified operator is null or
+     *         if the element is replaced with a null value and this list
+     *         does not permit null elements
+     *         (<a href="Collection.html#optional-restrictions">optional</a>)
+     * @since 1.8
+     */
+    default void replaceAll(UnaryOperator<E> operator) {
+        Objects.requireNonNull(operator);
+        final ListIterator<E> li = this.listIterator();
+        while (li.hasNext()) {
+            li.set(operator.apply(li.next()));
+        }
+    }
+
+    /**
+     * Sorts this list using the supplied {@code Comparator} to compare elements.
+     *
+     * @implSpec
+     * The default implementation is equivalent to, for this {@code list}:
+     * <pre>Collections.sort(list, c)</pre>
+     *
+     * @param c the {@code Comparator} used to compare list elements.
+     *          A {@code null} value indicates that the elements'
+     *          {@linkplain Comparable natural ordering} should be used
+     * @throws ClassCastException if the list contains elements that are not
+     *         <i>mutually comparable</i> using the specified comparator
+     * @throws UnsupportedOperationException if the list's list-iterator does
+     *         not support the {@code set} operation
+     * @throws IllegalArgumentException
+     *         (<a href="Collection.html#optional-restrictions">optional</a>)
+     *         if the comparator is found to violate the {@link Comparator}
+     *         contract
+     * @since 1.8
+     */
+    default void sort(Comparator<? super E> c) {
+        Collections.sort(this, c);
+    }
+
+    /**
      * Removes all of the elements from this list (optional operation).
      * The list will be empty after this call returns.
      *
--- a/src/share/classes/java/util/Vector.java	Mon Apr 22 11:39:53 2013 +0800
+++ b/src/share/classes/java/util/Vector.java	Mon Apr 22 09:19:34 2013 -0700
@@ -25,6 +25,10 @@
 
 package java.util;
 
+import java.util.function.Consumer;
+import java.util.function.Predicate;
+import java.util.function.UnaryOperator;
+
 /**
  * The {@code Vector} class implements a growable array of
  * objects. Like an array, it contains components that can be
@@ -1209,4 +1213,89 @@
             lastRet = -1;
         }
     }
+
+    @Override
+    public synchronized void forEach(Consumer<? super E> action) {
+        Objects.requireNonNull(action);
+        final int expectedModCount = modCount;
+        @SuppressWarnings("unchecked")
+        final E[] elementData = (E[]) this.elementData;
+        final int elementCount = this.elementCount;
+        for (int i=0; modCount == expectedModCount && i < elementCount; i++) {
+            action.accept(elementData[i]);
+        }
+        if (modCount != expectedModCount) {
+            throw new ConcurrentModificationException();
+        }
+    }
+
+    @Override
+    @SuppressWarnings("unchecked")
+    public synchronized boolean removeIf(Predicate<? super E> filter) {
+        Objects.requireNonNull(filter);
+        // figure out which elements are to be removed
+        // any exception thrown from the filter predicate at this stage
+        // will leave the collection unmodified
+        int removeCount = 0;
+        final int size = elementCount;
+        final BitSet removeSet = new BitSet(size);
+        final int expectedModCount = modCount;
+        for (int i=0; modCount == expectedModCount && i < size; i++) {
+            @SuppressWarnings("unchecked")
+            final E element = (E) elementData[i];
+            if (filter.test(element)) {
+                removeSet.set(i);
+                removeCount++;
+            }
+        }
+        if (modCount != expectedModCount) {
+            throw new ConcurrentModificationException();
+        }
+
+        // shift surviving elements left over the spaces left by removed elements
+        final boolean anyToRemove = removeCount > 0;
+        if (anyToRemove) {
+            final int newSize = size - removeCount;
+            for (int i=0, j=0; (i < size) && (j < newSize); i++, j++) {
+                i = removeSet.nextClearBit(i);
+                elementData[j] = elementData[i];
+            }
+            for (int k=newSize; k < size; k++) {
+                elementData[k] = null;  // Let gc do its work
+            }
+            elementCount = newSize;
+            if (modCount != expectedModCount) {
+                throw new ConcurrentModificationException();
+            }
+            modCount++;
+        }
+
+        return anyToRemove;
+    }
+
+    @Override
+    @SuppressWarnings("unchecked")
+    public synchronized void replaceAll(UnaryOperator<E> operator) {
+        Objects.requireNonNull(operator);
+        final int expectedModCount = modCount;
+        final int size = elementCount;
+        for (int i=0; modCount == expectedModCount && i < size; i++) {
+            elementData[i] = operator.apply((E) elementData[i]);
+        }
+        if (modCount != expectedModCount) {
+            throw new ConcurrentModificationException();
+        }
+        modCount++;
+    }
+
+    @Override
+    @SuppressWarnings("unchecked")
+    public synchronized void sort(Comparator<? super E> c) {
+        final int expectedModCount = modCount;
+        Arrays.sort((E[]) elementData, 0, elementCount, c);
+        if (modCount != expectedModCount) {
+            throw new ConcurrentModificationException();
+        }
+        modCount++;
+    }
 }
--- a/src/share/classes/java/util/concurrent/CopyOnWriteArrayList.java	Mon Apr 22 11:39:53 2013 +0800
+++ b/src/share/classes/java/util/concurrent/CopyOnWriteArrayList.java	Mon Apr 22 09:19:34 2013 -0700
@@ -36,6 +36,9 @@
 package java.util.concurrent;
 import java.util.*;
 import java.util.concurrent.locks.ReentrantLock;
+import java.util.function.Consumer;
+import java.util.function.Predicate;
+import java.util.function.UnaryOperator;
 
 /**
  * A thread-safe variant of {@link java.util.ArrayList} in which all mutative
@@ -1260,9 +1263,58 @@
             }
         }
 
+        @Override
+        public void forEach(Consumer<? super E> action) {
+            @SuppressWarnings("unchecked")
+            final E[] elements = (E[]) l.getArray();
+            checkForComodification();
+            l.forEach(action, elements, offset, offset + size);
+        }
+
+        @Override
+        public void sort(Comparator<? super E> c) {
+            final ReentrantLock lock = l.lock;
+            lock.lock();
+            try {
+                checkForComodification();
+                l.sort(c, offset, offset + size);
+                expectedArray = l.getArray();
+            } finally {
+                lock.unlock();
+            }
+        }
+
+        @Override
+        public boolean removeIf(Predicate<? super E> filter) {
+            Objects.requireNonNull(filter);
+            final ReentrantLock lock = l.lock;
+            lock.lock();
+            try {
+                checkForComodification();
+                final int removeCount =
+                        l.removeIf(filter, offset, offset + size);
+                expectedArray = l.getArray();
+                size -= removeCount;
+                return removeCount > 0;
+            } finally {
+                lock.unlock();
+            }
+        }
+
+        @Override
+        public void replaceAll(UnaryOperator<E> operator) {
+            final ReentrantLock lock = l.lock;
+            lock.lock();
+            try {
+                checkForComodification();
+                l.replaceAll(operator, offset, offset + size);
+                expectedArray = l.getArray();
+            } finally {
+                lock.unlock();
+            }
+        }
     }
 
-
     private static class COWSubListIterator<E> implements ListIterator<E> {
         private final ListIterator<E> it;
         private final int offset;
@@ -1333,4 +1385,139 @@
             throw new Error(e);
         }
     }
+
+    @Override
+    @SuppressWarnings("unchecked")
+    public void forEach(Consumer<? super E> action) {
+        forEach(action, (E[]) getArray(), 0, size());
+    }
+
+    private void forEach(Consumer<? super E> action,
+                         final E[] elements,
+                         final int from, final int to) {
+        Objects.requireNonNull(action);
+        for (int i = from; i < to; i++) {
+            action.accept(elements[i]);
+        }
+    }
+
+    @Override
+    public void sort(Comparator<? super E> c) {
+        final ReentrantLock lock = this.lock;
+        lock.lock();
+        try {
+            sort(c, 0, size());
+        } finally {
+            lock.unlock();
+        }
+    }
+
+    // must be called with this.lock held
+    @SuppressWarnings("unchecked")
+    private void sort(Comparator<? super E> c, final int from, final int to) {
+        final E[] elements = (E[]) getArray();
+        final E[] newElements = Arrays.copyOf(elements, elements.length);
+        // only elements [from, to) are sorted
+        Arrays.sort(newElements, from, to, c);
+        setArray(newElements);
+    }
+
+    @Override
+    public boolean removeIf(Predicate<? super E> filter) {
+        Objects.requireNonNull(filter);
+        final ReentrantLock lock = this.lock;
+        lock.lock();
+        try {
+            return removeIf(filter, 0, size()) > 0;
+        } finally {
+            lock.unlock();
+        }
+    }
+
+    // must be called with this.lock held
+    private int removeIf(Predicate<? super E> filter, final int from, final int to) {
+        Objects.requireNonNull(filter);
+        final ReentrantLock lock = this.lock;
+        lock.lock();
+        try {
+            @SuppressWarnings("unchecked")
+            final E[] elements = (E[]) getArray();
+
+            // figure out which elements are to be removed
+            // any exception thrown from the filter predicate at this stage
+            // will leave the collection unmodified
+            int removeCount = 0;
+            final int range = to - from;
+            final BitSet removeSet = new BitSet(range);
+            for (int i = 0; i < range; i++) {
+                final E element = elements[from + i];
+                if (filter.test(element)) {
+                    // removeSet is zero-based to keep its size small
+                    removeSet.set(i);
+                    removeCount++;
+                }
+            }
+
+            // copy surviving elements into a new array
+            if (removeCount > 0) {
+                final int newSize = elements.length - removeCount;
+                final int newRange = newSize - from;
+                @SuppressWarnings("unchecked")
+                final E[] newElements = (E[]) new Object[newSize];
+                // copy elements before [from, to) unmodified
+                for (int i = 0; i < from; i++) {
+                    newElements[i] = elements[i];
+                }
+                // elements [from, to) are subject to removal
+                int j = 0;
+                for (int i = 0; (i < range) && (j < newRange); i++) {
+                    i = removeSet.nextClearBit(i);
+                    if (i >= range) {
+                        break;
+                    }
+                    newElements[from + (j++)] = elements[from + i];
+                }
+                // copy any remaining elements beyond [from, to)
+                j += from;
+                for (int i = to; (i < elements.length) && (j < newSize); i++) {
+                    newElements[j++] = elements[i];
+                }
+                setArray(newElements);
+            }
+
+            return removeCount;
+        } finally {
+            lock.unlock();
+        }
+    }
+
+    @Override
+    public void replaceAll(UnaryOperator<E> operator) {
+        Objects.requireNonNull(operator);
+        final ReentrantLock lock = this.lock;
+        lock.lock();
+        try {
+            replaceAll(operator, 0, size());
+        } finally {
+            lock.unlock();
+        }
+    }
+
+    // must be called with this.lock held
+    @SuppressWarnings("unchecked")
+    private void replaceAll(UnaryOperator<E> operator, final int from, final int to) {
+        final E[] elements = (E[]) getArray();
+        final E[] newElements = (E[]) new Object[elements.length];
+        for (int i = 0; i < from; i++) {
+            newElements[i] = elements[i];
+        }
+        // the operator is only applied to elements [from, to)
+        for (int i = from; i < to; i++) {
+            newElements[i] = operator.apply(elements[i]);
+        }
+        for (int i = to; i < elements.length; i++) {
+            newElements[i] = elements[i];
+        }
+        setArray(newElements);
+    }
 }
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/test/java/util/Collection/CollectionDefaults.java	Mon Apr 22 09:19:34 2013 -0700
@@ -0,0 +1,151 @@
+/*
+ * Copyright (c) 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.
+ *
+ * This code is distributed in the hope that it will be useful, but WITHOUT
+ * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
+ * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
+ * version 2 for more details (a copy is included in the LICENSE file that
+ * accompanied this code).
+ *
+ * You should have received a copy of the GNU General Public License version
+ * 2 along with this work; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
+ *
+ * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
+ * or visit www.oracle.com if you need additional information or have any
+ * questions.
+ */
+
+import java.util.Collections;
+import java.util.HashMap;
+import java.util.HashSet;
+import java.util.LinkedHashMap;
+import java.util.LinkedHashSet;
+import java.util.LinkedList;
+import java.util.List;
+import java.util.Set;
+
+import org.testng.annotations.DataProvider;
+import org.testng.annotations.Test;
+
+import static org.testng.Assert.assertTrue;
+import static org.testng.Assert.fail;
+
+import java.util.TreeMap;
+import java.util.TreeSet;
+import java.util.function.Predicate;
+
+/**
+ * @test
+ * @library testlibrary
+ * @build CollectionAsserts CollectionSupplier
+ * @run testng CollectionDefaults
+ * @summary Unit tests for extension methods on Collection
+ */
+public class CollectionDefaults {
+
+    public static final Predicate<Integer> pEven = x -> 0 == x % 2;
+    public static final Predicate<Integer> pOdd = x -> 1 == x % 2;
+
+    private static final String[] SET_CLASSES = {
+        "java.util.HashSet",
+        "java.util.LinkedHashSet",
+        "java.util.TreeSet"
+    };
+
+    private static final int SIZE = 100;
+
+    @DataProvider(name="setProvider", parallel=true)
+    public static Object[][] setCases() {
+        final List<Object[]> cases = new LinkedList<>();
+        cases.add(new Object[] { new HashSet<>() });
+        cases.add(new Object[] { new LinkedHashSet<>() });
+        cases.add(new Object[] { new TreeSet<>() });
+
+        cases.add(new Object[] { Collections.newSetFromMap(new HashMap<>()) });
+        cases.add(new Object[] { Collections.newSetFromMap(new LinkedHashMap()) });
+        cases.add(new Object[] { Collections.newSetFromMap(new TreeMap<>()) });
+
+        cases.add(new Object[] { new HashSet(){{add(42);}} });
+        cases.add(new Object[] { new LinkedHashSet(){{add(42);}} });
+        cases.add(new Object[] { new TreeSet(){{add(42);}} });
+        return cases.toArray(new Object[0][cases.size()]);
+    }
+
+    @Test(dataProvider = "setProvider")
+    public void testProvidedWithNull(final Set<Integer> set) throws Exception {
+        try {
+            set.forEach(null);
+            fail("expected NPE not thrown");
+        } catch (NullPointerException npe) {}
+        try {
+            set.removeIf(null);
+            fail("expected NPE not thrown");
+        } catch (NullPointerException npe) {}
+    }
+
+    @Test
+    public void testForEach() throws Exception {
+        final CollectionSupplier supplier = new CollectionSupplier(SET_CLASSES, SIZE);
+        for (final CollectionSupplier.TestCase test : supplier.get()) {
+            final Set<Integer> original = ((Set<Integer>) test.original);
+            final Set<Integer> set = ((Set<Integer>) test.collection);
+
+            try {
+                set.forEach(null);
+                fail("expected NPE not thrown");
+            } catch (NullPointerException npe) {}
+            if (test.className.equals("java.util.HashSet")) {
+                CollectionAsserts.assertContentsUnordered(set, original);
+            } else {
+                CollectionAsserts.assertContents(set, original);
+            }
+
+            final List<Integer> actual = new LinkedList<>();
+            set.forEach(actual::add);
+            if (test.className.equals("java.util.HashSet")) {
+                CollectionAsserts.assertContentsUnordered(actual, set);
+                CollectionAsserts.assertContentsUnordered(actual, original);
+            } else {
+                CollectionAsserts.assertContents(actual, set);
+                CollectionAsserts.assertContents(actual, original);
+            }
+        }
+    }
+
+    @Test
+    public void testRemoveIf() throws Exception {
+        final CollectionSupplier supplier = new CollectionSupplier(SET_CLASSES, SIZE);
+        for (final CollectionSupplier.TestCase test : supplier.get()) {
+            final Set<Integer> original = ((Set<Integer>) test.original);
+            final Set<Integer> set = ((Set<Integer>) test.collection);
+
+            try {
+                set.removeIf(null);
+                fail("expected NPE not thrown");
+            } catch (NullPointerException npe) {}
+            if (test.className.equals("java.util.HashSet")) {
+                CollectionAsserts.assertContentsUnordered(set, original);
+            } else {
+                CollectionAsserts.assertContents(set, original);
+            }
+
+            set.removeIf(pEven);
+            for (int i : set) {
+                assertTrue((i % 2) == 1);
+            }
+            for (int i : original) {
+                if (i % 2 == 1) {
+                    assertTrue(set.contains(i));
+                }
+            }
+            set.removeIf(pOdd);
+            assertTrue(set.isEmpty());
+        }
+    }
+}
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/test/java/util/Collection/ListDefaults.java	Mon Apr 22 09:19:34 2013 -0700
@@ -0,0 +1,530 @@
+/*
+ * Copyright (c) 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.
+ *
+ * This code is distributed in the hope that it will be useful, but WITHOUT
+ * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
+ * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
+ * version 2 for more details (a copy is included in the LICENSE file that
+ * accompanied this code).
+ *
+ * You should have received a copy of the GNU General Public License version
+ * 2 along with this work; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
+ *
+ * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
+ * or visit www.oracle.com if you need additional information or have any
+ * questions.
+ */
+
+import java.util.ArrayList;
+import java.util.Arrays;
+import java.util.Collections;
+import java.util.Comparator;
+import java.util.Comparators;
+import java.util.List;
+import java.util.LinkedList;
+import java.util.Stack;
+import java.util.TreeMap;
+import java.util.TreeSet;
+import java.util.Vector;
+import java.util.concurrent.CopyOnWriteArrayList;
+import java.util.concurrent.atomic.AtomicBoolean;
+import java.util.concurrent.atomic.AtomicInteger;
+
+import org.testng.annotations.DataProvider;
+import org.testng.annotations.Test;
+
+import static org.testng.Assert.assertEquals;
+import static org.testng.Assert.assertFalse;
+import static org.testng.Assert.assertTrue;
+import static org.testng.Assert.fail;
+
+import java.lang.reflect.Constructor;
+import java.util.ConcurrentModificationException;
+import java.util.function.Predicate;
+
+/**
+ * @test
+ * @library testlibrary
+ * @build CollectionAsserts CollectionSupplier
+ * @run testng ListDefaults
+ * @summary Unit tests for extension methods on List
+ */
+public class ListDefaults {
+
+    private static final String[] LIST_CLASSES = {
+        "java.util.ArrayList",
+        "java.util.LinkedList",
+        "java.util.Vector",
+        "java.util.concurrent.CopyOnWriteArrayList"
+    };
+
+    private static final String[] LIST_CME_CLASSES = {
+        "java.util.ArrayList",
+        "java.util.Vector"
+    };
+
+    private static final Predicate<Integer> pEven = x -> 0 == x % 2;
+    private static final Predicate<Integer> pOdd = x -> 1 == x % 2;
+
+    private static final Comparator<Integer> BIT_COUNT_COMPARATOR =
+            (x, y) -> Integer.bitCount(x) - Integer.bitCount(y);
+
+    private static final Comparator<AtomicInteger> ATOMIC_INTEGER_COMPARATOR =
+            (x, y) -> x.intValue() - y.intValue();
+
+    private static final int SIZE = 100;
+    private static final int SUBLIST_FROM = 20;
+    private static final int SUBLIST_TO = SIZE - 5;
+    private static final int SUBLIST_SIZE = SUBLIST_TO - SUBLIST_FROM;
+
+    private static interface Callback {
+        void call(List<Integer> list);
+    }
+
+    // call the callback for each recursive subList
+    private void trimmedSubList(final List<Integer> list, final Callback callback) {
+        int size = list.size();
+        if (size > 1) {
+            // trim 1 element from both ends
+            final List<Integer> subList = list.subList(1, size - 1);
+            callback.call(subList);
+            trimmedSubList(subList, callback);
+        }
+    }
+
+    @DataProvider(name="listProvider", parallel=true)
+    public static Object[][] listCases() {
+        final List<Object[]> cases = new LinkedList<>();
+        cases.add(new Object[] { new ArrayList<>() });
+        cases.add(new Object[] { new LinkedList<>() });
+        cases.add(new Object[] { new Vector<>() });
+        cases.add(new Object[] { new Stack<>() });
+        cases.add(new Object[] { new CopyOnWriteArrayList<>() });
+
+        cases.add(new Object[] { new ArrayList(){{add(42);}} });
+        cases.add(new Object[] { new LinkedList(){{add(42);}} });
+        cases.add(new Object[] { new Vector(){{add(42);}} });
+        cases.add(new Object[] { new Stack(){{add(42);}} });
+        cases.add(new Object[] { new CopyOnWriteArrayList(){{add(42);}} });
+        return cases.toArray(new Object[0][cases.size()]);
+    }
+
+    @Test(dataProvider = "listProvider")
+    public void testProvidedWithNull(final List<Integer> list) throws Exception {
+        try {
+            list.forEach(null);
+            fail("expected NPE not thrown");
+        } catch (NullPointerException npe) {}
+        try {
+            list.replaceAll(null);
+            fail("expected NPE not thrown");
+        } catch (NullPointerException npe) {}
+        try {
+            list.removeIf(null);
+            fail("expected NPE not thrown");
+        } catch (NullPointerException npe) {}
+    }
+
+    @Test
+    public void testForEach() throws Exception {
+        final CollectionSupplier supplier = new CollectionSupplier(LIST_CLASSES, SIZE);
+        for (final CollectionSupplier.TestCase test : supplier.get()) {
+            final List<Integer> original = ((List<Integer>) test.original);
+            final List<Integer> list = ((List<Integer>) test.collection);
+        }
+        for (final CollectionSupplier.TestCase test : supplier.get()) {
+            final List<Integer> original = ((List<Integer>) test.original);
+            final List<Integer> list = ((List<Integer>) test.collection);
+
+            try {
+                list.forEach(null);
+                fail("expected NPE not thrown");
+            } catch (NullPointerException npe) {}
+            CollectionAsserts.assertContents(list, original);
+
+            final List<Integer> actual = new LinkedList<>();
+            list.forEach(actual::add);
+            CollectionAsserts.assertContents(actual, list);
+            CollectionAsserts.assertContents(actual, original);
+
+            if (original.size() > SUBLIST_SIZE) {
+                final List<Integer> subList = original.subList(SUBLIST_FROM, SUBLIST_TO);
+                final List<Integer> actualSubList = new LinkedList<>();
+                subList.forEach(actualSubList::add);
+                assertEquals(actualSubList.size(), SUBLIST_SIZE);
+                for (int i = 0; i < SUBLIST_SIZE; i++) {
+                    assertEquals(actualSubList.get(i), original.get(i + SUBLIST_FROM));
+                }
+            }
+
+            trimmedSubList(list, new Callback() {
+                @Override
+                public void call(final List<Integer> list) {
+                    final List<Integer> actual = new LinkedList<>();
+                    list.forEach(actual::add);
+                    CollectionAsserts.assertContents(actual, list);
+                }
+            });
+        }
+    }
+
+    @Test
+    public void testRemoveIf() throws Exception {
+        final CollectionSupplier supplier = new CollectionSupplier(LIST_CLASSES, SIZE);
+
+        for (final CollectionSupplier.TestCase test : supplier.get()) {
+            final List<Integer> original = ((List<Integer>) test.original);
+            final List<Integer> list = ((List<Integer>) test.collection);
+
+            try {
+                list.removeIf(null);
+                fail("expected NPE not thrown");
+            } catch (NullPointerException npe) {}
+            CollectionAsserts.assertContents(list, original);
+
+            final AtomicInteger offset = new AtomicInteger(1);
+            while (list.size() > 0) {
+                removeFirst(original, list, offset);
+            }
+        }
+
+        for (final CollectionSupplier.TestCase test : supplier.get()) {
+            final List<Integer> original = ((List<Integer>) test.original);
+            final List<Integer> list = ((List<Integer>) test.collection);
+            list.removeIf(pOdd);
+            for (int i : list) {
+                assertTrue((i % 2) == 0);
+            }
+            for (int i : original) {
+                if (i % 2 == 0) {
+                    assertTrue(list.contains(i));
+                }
+            }
+            list.removeIf(pEven);
+            assertTrue(list.isEmpty());
+        }
+
+        for (final CollectionSupplier.TestCase test : supplier.get()) {
+            final List<Integer> original = ((List<Integer>) test.original);
+            final List<Integer> list = ((List<Integer>) test.collection);
+            final List<Integer> listCopy = new ArrayList<>(list);
+            if (original.size() > SUBLIST_SIZE) {
+                final List<Integer> subList = list.subList(SUBLIST_FROM, SUBLIST_TO);
+                final List<Integer> subListCopy = new ArrayList<>(subList);
+                listCopy.removeAll(subList);
+                subList.removeIf(pOdd);
+                for (int i : subList) {
+                    assertTrue((i % 2) == 0);
+                }
+                for (int i : subListCopy) {
+                    if (i % 2 == 0) {
+                        assertTrue(subList.contains(i));
+                    } else {
+                        assertFalse(subList.contains(i));
+                    }
+                }
+                subList.removeIf(pEven);
+                assertTrue(subList.isEmpty());
+                // elements outside the view should remain
+                CollectionAsserts.assertContents(list, listCopy);
+            }
+        }
+
+        for (final CollectionSupplier.TestCase test : supplier.get()) {
+            final List<Integer> list = ((List<Integer>) test.collection);
+            trimmedSubList(list, new Callback() {
+                @Override
+                public void call(final List<Integer> list) {
+                    final List<Integer> copy = new ArrayList<>(list);
+                    list.removeIf(pOdd);
+                    for (int i : list) {
+                        assertTrue((i % 2) == 0);
+                    }
+                    for (int i : copy) {
+                        if (i % 2 == 0) {
+                            assertTrue(list.contains(i));
+                        } else {
+                            assertFalse(list.contains(i));
+                        }
+                    }
+                }
+            });
+        }
+    }
+
+    // remove the first element
+    private void removeFirst(final List<Integer> original, final List<Integer> list, final AtomicInteger offset) {
+        final AtomicBoolean first = new AtomicBoolean(true);
+        list.removeIf(x -> first.getAndSet(false));
+        CollectionAsserts.assertContents(original.subList(offset.getAndIncrement(), original.size()), list);
+    }
+
+    @Test
+    public void testReplaceAll() throws Exception {
+        final int scale = 3;
+        final CollectionSupplier supplier = new CollectionSupplier(LIST_CLASSES, SIZE);
+        for (final CollectionSupplier.TestCase test : supplier.get()) {
+            final List<Integer> original = ((List<Integer>) test.original);
+            final List<Integer> list = ((List<Integer>) test.collection);
+
+            try {
+                list.replaceAll(null);
+                fail("expected NPE not thrown");
+            } catch (NullPointerException npe) {}
+            CollectionAsserts.assertContents(list, original);
+
+            list.replaceAll(x -> scale * x);
+            for (int i=0; i < original.size(); i++) {
+                assertTrue(list.get(i) == (scale * original.get(i)), "mismatch at index " + i);
+            }
+
+            if (original.size() > SUBLIST_SIZE) {
+                final List<Integer> subList = list.subList(SUBLIST_FROM, SUBLIST_TO);
+                subList.replaceAll(x -> x + 1);
+                // verify elements in view [from, to) were replaced
+                for (int i = 0; i < SUBLIST_SIZE; i++) {
+                    assertTrue(subList.get(i) == ((scale * original.get(i + SUBLIST_FROM)) + 1),
+                            "mismatch at sublist index " + i);
+                }
+                // verify that elements [0, from) remain unmodified
+                for (int i = 0; i < SUBLIST_FROM; i++) {
+                    assertTrue(list.get(i) == (scale * original.get(i)),
+                            "mismatch at original index " + i);
+                }
+                // verify that elements [to, size) remain unmodified
+                for (int i = SUBLIST_TO; i < list.size(); i++) {
+                    assertTrue(list.get(i) == (scale * original.get(i)),
+                            "mismatch at original index " + i);
+                }
+            }
+        }
+
+        for (final CollectionSupplier.TestCase test : supplier.get()) {
+            final List<Integer> list = ((List<Integer>) test.collection);
+            trimmedSubList(list, new Callback() {
+                @Override
+                public void call(final List<Integer> list) {
+                    final List<Integer> copy = new ArrayList<>(list);
+                    final int offset = 5;
+                    list.replaceAll(x -> offset + x);
+                    for (int i=0; i < copy.size(); i++) {
+                        assertTrue(list.get(i) == (offset + copy.get(i)), "mismatch at index " + i);
+                    }
+                }
+            });
+        }
+    }
+
+    @Test
+    public void testSort() throws Exception {
+        final CollectionSupplier supplier = new CollectionSupplier(LIST_CLASSES, SIZE);
+        for (final CollectionSupplier.TestCase test : supplier.get()) {
+            final List<Integer> original = ((List<Integer>) test.original);
+            final List<Integer> list = ((List<Integer>) test.collection);
+            CollectionSupplier.shuffle(list);
+            list.sort(Integer::compare);
+            CollectionAsserts.assertSorted(list, Integer::compare);
+            if (test.name.startsWith("reverse")) {
+                Collections.reverse(list);
+            }
+            CollectionAsserts.assertContents(list, original);
+
+            CollectionSupplier.shuffle(list);
+            list.sort(null);
+            CollectionAsserts.assertSorted(list, Comparators.<Integer>naturalOrder());
+            if (test.name.startsWith("reverse")) {
+                Collections.reverse(list);
+            }
+            CollectionAsserts.assertContents(list, original);
+
+            CollectionSupplier.shuffle(list);
+            list.sort(Comparators.<Integer>naturalOrder());
+            CollectionAsserts.assertSorted(list, Comparators.<Integer>naturalOrder());
+            if (test.name.startsWith("reverse")) {
+                Collections.reverse(list);
+            }
+            CollectionAsserts.assertContents(list, original);
+
+            CollectionSupplier.shuffle(list);
+            list.sort(Comparators.<Integer>reverseOrder());
+            CollectionAsserts.assertSorted(list, Comparators.<Integer>reverseOrder());
+            if (!test.name.startsWith("reverse")) {
+                Collections.reverse(list);
+            }
+            CollectionAsserts.assertContents(list, original);
+
+            CollectionSupplier.shuffle(list);
+            list.sort(BIT_COUNT_COMPARATOR);
+            CollectionAsserts.assertSorted(list, BIT_COUNT_COMPARATOR);
+            // check sort by verifying that bitCount increases and never drops
+            int minBitCount = 0;
+            int bitCount = 0;
+            for (final Integer i : list) {
+                bitCount = Integer.bitCount(i);
+                assertTrue(bitCount >= minBitCount);
+                minBitCount = bitCount;
+            }
+
+            @SuppressWarnings("unchecked")
+            final Class<? extends List<AtomicInteger>> type =
+                    (Class<? extends List<AtomicInteger>>) Class.forName(test.className);
+            final Constructor<? extends List<AtomicInteger>> defaultConstructor = type.getConstructor();
+            final List<AtomicInteger> incomparables = (List<AtomicInteger>) defaultConstructor.newInstance();
+
+            for (int i=0; i < test.original.size(); i++) {
+                incomparables.add(new AtomicInteger(i));
+            }
+            CollectionSupplier.shuffle(incomparables);
+            incomparables.sort(ATOMIC_INTEGER_COMPARATOR);
+            for (int i=0; i < test.original.size(); i++) {
+                assertEquals(i, incomparables.get(i).intValue());
+            }
+
+            if (original.size() > SUBLIST_SIZE) {
+                final List<Integer> copy = new ArrayList<>(list);
+                final List<Integer> subList = list.subList(SUBLIST_FROM, SUBLIST_TO);
+                CollectionSupplier.shuffle(subList);
+                subList.sort(Comparators.<Integer>naturalOrder());
+                CollectionAsserts.assertSorted(subList, Comparators.<Integer>naturalOrder());
+                // verify that elements [0, from) remain unmodified
+                for (int i = 0; i < SUBLIST_FROM; i++) {
+                    assertTrue(list.get(i) == copy.get(i),
+                            "mismatch at index " + i);
+                }
+                // verify that elements [to, size) remain unmodified
+                for (int i = SUBLIST_TO; i < list.size(); i++) {
+                    assertTrue(list.get(i) == copy.get(i),
+                            "mismatch at index " + i);
+                }
+            }
+        }
+
+        for (final CollectionSupplier.TestCase test : supplier.get()) {
+            final List<Integer> list = ((List<Integer>) test.collection);
+            trimmedSubList(list, new Callback() {
+                @Override
+                public void call(final List<Integer> list) {
+                    final List<Integer> copy = new ArrayList<>(list);
+                    CollectionSupplier.shuffle(list);
+                    list.sort(Comparators.<Integer>naturalOrder());
+                    CollectionAsserts.assertSorted(list, Comparators.<Integer>naturalOrder());
+                }
+            });
+        }
+    }
+
+    @Test
+    public void testForEachThrowsCME() throws Exception {
+        final CollectionSupplier supplier = new CollectionSupplier(LIST_CME_CLASSES, SIZE);
+        for (final CollectionSupplier.TestCase test : supplier.get()) {
+            final List<Integer> list = ((List<Integer>) test.collection);
+            if (list.size() <= 1) {
+                continue;
+            }
+            boolean gotException = false;
+            try {
+                // bad predicate that modifies its list, should throw CME
+                list.forEach((x) -> {list.add(x);});
+            } catch (ConcurrentModificationException cme) {
+                gotException = true;
+            }
+            if (!gotException) {
+                fail("expected CME was not thrown from " + test);
+            }
+        }
+    }
+
+    @Test
+    public void testRemoveIfThrowsCME() throws Exception {
+        final CollectionSupplier supplier = new CollectionSupplier(LIST_CME_CLASSES, SIZE);
+        for (final CollectionSupplier.TestCase test : supplier.get()) {
+            final List<Integer> list = ((List<Integer>) test.collection);
+            if (list.size() <= 1) {
+                continue;
+            }
+            boolean gotException = false;
+            try {
+                // bad predicate that modifies its list, should throw CME
+                list.removeIf((x) -> {return list.add(x);});
+            } catch (ConcurrentModificationException cme) {
+                gotException = true;
+            }
+            if (!gotException) {
+                fail("expected CME was not thrown from " + test);
+            }
+        }
+    }
+
+    @Test
+    public void testReplaceAllThrowsCME() throws Exception {
+        final CollectionSupplier supplier = new CollectionSupplier(LIST_CME_CLASSES, SIZE);
+        for (final CollectionSupplier.TestCase test : supplier.get()) {
+            final List<Integer> list = ((List<Integer>) test.collection);
+            if (list.size() <= 1) {
+                continue;
+            }
+            boolean gotException = false;
+            try {
+                // bad predicate that modifies its list, should throw CME
+                list.replaceAll(x -> {int n = 3 * x; list.add(n); return n;});
+            } catch (ConcurrentModificationException cme) {
+                gotException = true;
+            }
+            if (!gotException) {
+                fail("expected CME was not thrown from " + test);
+            }
+        }
+    }
+
+    @Test
+    public void testSortThrowsCME() throws Exception {
+        final CollectionSupplier supplier = new CollectionSupplier(LIST_CME_CLASSES, SIZE);
+        for (final CollectionSupplier.TestCase test : supplier.get()) {
+            final List<Integer> list = ((List<Integer>) test.collection);
+            if (list.size() <= 1) {
+                continue;
+            }
+            boolean gotException = false;
+            try {
+                // bad predicate that modifies its list, should throw CME
+                list.sort((x, y) -> {list.add(x); return x - y;});
+            } catch (ConcurrentModificationException cme) {
+                gotException = true;
+            }
+            if (!gotException) {
+                fail("expected CME was not thrown from " + test);
+            }
+        }
+    }
+
+    private static final List<Integer> SLICED_EXPECTED = Arrays.asList(0, 1, 2, 3, 5, 6, 7, 8, 9);
+    private static final List<Integer> SLICED_EXPECTED2 = Arrays.asList(0, 1, 2, 5, 6, 7, 8, 9);
+
+    @DataProvider(name="shortIntListProvider", parallel=true)
+    public static Object[][] intListCases() {
+        final Integer[] DATA = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
+        final List<Object[]> cases = new LinkedList<>();
+        cases.add(new Object[] { new ArrayList<>(Arrays.asList(DATA)) });
+        cases.add(new Object[] { new LinkedList<>(Arrays.asList(DATA)) });
+        cases.add(new Object[] { new Vector<>(Arrays.asList(DATA)) });
+        cases.add(new Object[] { new CopyOnWriteArrayList<>(Arrays.asList(DATA)) });
+        return cases.toArray(new Object[0][cases.size()]);
+    }
+
+    @Test(dataProvider = "shortIntListProvider")
+    public void testRemoveIfFromSlice(final List<Integer> list) throws Exception {
+        final List<Integer> sublist = list.subList(3, 6);
+        assertTrue(sublist.removeIf(x -> x == 4));
+        CollectionAsserts.assertContents(list, SLICED_EXPECTED);
+
+        final List<Integer> sublist2 = list.subList(2, 5);
+        assertTrue(sublist2.removeIf(x -> x == 3));
+        CollectionAsserts.assertContents(list, SLICED_EXPECTED2);
+    }
+}
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/test/java/util/Collection/testlibrary/CollectionAsserts.java	Mon Apr 22 09:19:34 2013 -0700
@@ -0,0 +1,211 @@
+/*
+ * Copyright (c) 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.
+ *
+ * This code is distributed in the hope that it will be useful, but WITHOUT
+ * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
+ * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
+ * version 2 for more details (a copy is included in the LICENSE file that
+ * accompanied this code).
+ *
+ * You should have received a copy of the GNU General Public License version
+ * 2 along with this work; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
+ *
+ * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
+ * or visit www.oracle.com if you need additional information or have any
+ * questions.
+ */
+
+import java.util.ArrayList;
+import java.util.Arrays;
+import java.util.Collections;
+import java.util.Comparator;
+import java.util.HashSet;
+import java.util.Iterator;
+import java.util.List;
+import java.util.Objects;
+import java.util.Set;
+
+import static org.testng.Assert.assertEquals;
+import static org.testng.Assert.assertTrue;
+import static org.testng.Assert.fail;
+
+/**
+ * @library
+ * CollectionAssert -- assertion methods for lambda test cases
+ */
+public class CollectionAsserts {
+
+    public static void assertCountSum(Iterable<? super Integer> it, int count, int sum) {
+        assertCountSum(it.iterator(), count, sum);
+    }
+
+    public static void assertCountSum(Iterator<? super Integer> it, int count, int sum) {
+        int c = 0;
+        int s = 0;
+        while (it.hasNext()) {
+            int i = (Integer) it.next();
+            c++;
+            s += i;
+        }
+
+        assertEquals(c, count);
+        assertEquals(s, sum);
+    }
+
+    public static void assertConcat(Iterator<Character> it, String result) {
+        StringBuilder sb = new StringBuilder();
+        while (it.hasNext()) {
+            sb.append(it.next());
+        }
+
+        assertEquals(result, sb.toString());
+    }
+
+    public static<T extends Comparable<? super T>> void assertSorted(Iterator<T> i) {
+        if (!i.hasNext())
+            return;
+        T last = i.next();
+        while (i.hasNext()) {
+            T t = i.next();
+            assertTrue(last.compareTo(t) <= 0);
+            assertTrue(t.compareTo(last) >= 0);
+            last = t;
+        }
+    }
+
+    public static<T> void assertSorted(Iterator<T> i, Comparator<? super T> comp) {
+        if (!i.hasNext())
+            return;
+        T last = i.next();
+        while (i.hasNext()) {
+            T t = i.next();
+            assertTrue(comp.compare(last, t) <= 0);
+            assertTrue(comp.compare(t, last) >= 0);
+            last = t;
+        }
+    }
+
+    public static<T extends Comparable<? super T>> void assertSorted(Iterable<T> iter) {
+        assertSorted(iter.iterator());
+    }
+
+    public static<T> void assertSorted(Iterable<T> iter, Comparator<? super T> comp) {
+        assertSorted(iter.iterator(), comp);
+    }
+
+    public static <T> void assertUnique(Iterable<T> iter) {
+        assertUnique(iter.iterator());
+    }
+
+    public static<T> void assertUnique(Iterator<T> iter) {
+        if (!iter.hasNext()) {
+            return;
+        }
+
+        Set<T> uniq = new HashSet<>();
+        while(iter.hasNext()) {
+            T each = iter.next();
+            assertTrue(!uniq.contains(each));
+            uniq.add(each);
+        }
+    }
+
+    public static<T> void assertContents(Iterable<T> actual, Iterable<T> expected) {
+        assertContents(actual.iterator(), expected.iterator());
+    }
+
+    public static<T> void assertContents(Iterator<T> actual, Iterator<T> expected) {
+        List<T> history = new ArrayList<>();
+
+        while (expected.hasNext()) {
+            if (!actual.hasNext()) {
+                List<T> expectedData = new ArrayList<>(history);
+                while (expected.hasNext())
+                    expectedData.add(expected.next());
+                fail(String.format("Premature end of data; expected=%s, found=%s", expectedData, history));
+            }
+            T a = actual.next();
+            T e = expected.next();
+            history.add(a);
+
+            if (!Objects.equals(a, e))
+                fail(String.format("Data mismatch; preceding=%s, nextExpected=%s, nextFound=%s", history, e, a));
+        }
+        if (actual.hasNext()) {
+            List<T> rest = new ArrayList<>();
+            while (actual.hasNext())
+                rest.add(actual.next());
+            fail(String.format("Unexpected data %s after %s", rest, history));
+        }
+    }
+
+    @SafeVarargs
+    @SuppressWarnings("varargs")
+    public static<T> void assertContents(Iterator<T> actual, T... expected) {
+        assertContents(actual, Arrays.asList(expected).iterator());
+    }
+
+    public static <T> boolean equalsContentsUnordered(Iterable<T> a, Iterable<T> b) {
+        Set<T> sa = new HashSet<>();
+        for (T t : a) {
+            sa.add(t);
+        }
+
+        Set<T> sb = new HashSet<>();
+        for (T t : b) {
+            sb.add(t);
+        }
+
+        return Objects.equals(sa, sb);
+    }
+
+    public static<T extends Comparable<? super T>> void assertContentsUnordered(Iterable<T> actual, Iterable<T> expected) {
+        ArrayList<T> one = new ArrayList<>();
+        for (T t : actual)
+            one.add(t);
+        ArrayList<T> two = new ArrayList<>();
+        for (T t : expected)
+            two.add(t);
+        Collections.sort(one);
+        Collections.sort(two);
+        assertContents(one, two);
+    }
+
+    static <T> void assertSplitContents(Iterable<Iterable<T>> splits, Iterable<T> list) {
+        Iterator<Iterable<T>> mI = splits.iterator();
+        Iterator<T> pI = null;
+        Iterator<T> lI = list.iterator();
+
+        while (lI.hasNext()) {
+            if (pI == null)
+                pI = mI.next().iterator();
+            while (!pI.hasNext()) {
+                if (!mI.hasNext()) {
+                    break;
+                }
+                else {
+                    pI = mI.next().iterator();
+                }
+            }
+            assertTrue(pI.hasNext());
+            T pT = pI.next();
+            T lT = lI.next();
+            assertEquals(pT, lT);
+        }
+
+        if (pI != null) {
+            assertTrue(!pI.hasNext());
+        }
+
+        while(mI.hasNext()) {
+            pI = mI.next().iterator();
+            assertTrue(!pI.hasNext());
+        }
+    }
+}
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/test/java/util/Collection/testlibrary/CollectionSupplier.java	Mon Apr 22 09:19:34 2013 -0700
@@ -0,0 +1,304 @@
+/*
+ * Copyright (c) 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.
+ *
+ * This code is distributed in the hope that it will be useful, but WITHOUT
+ * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
+ * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
+ * version 2 for more details (a copy is included in the LICENSE file that
+ * accompanied this code).
+ *
+ * You should have received a copy of the GNU General Public License version
+ * 2 along with this work; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
+ *
+ * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
+ * or visit www.oracle.com if you need additional information or have any
+ * questions.
+ */
+
+import java.lang.Exception;
+import java.lang.Integer;
+import java.lang.Iterable;
+import java.lang.Override;
+import java.util.Arrays;
+import java.util.LinkedList;
+import java.util.List;
+import java.util.Random;
+import java.util.Set;
+
+import org.testng.TestException;
+
+import static org.testng.Assert.assertTrue;
+
+import java.lang.reflect.Constructor;
+import java.util.Collection;
+import java.util.Collections;
+import java.util.function.Supplier;
+
+/**
+ * @library
+ * @summary A Supplier of test cases for Collection tests
+ */
+public final class CollectionSupplier implements Supplier<Iterable<CollectionSupplier.TestCase>> {
+
+    private final String[] classNames;
+    private final int size;
+
+    /**
+     * A Collection test case.
+     */
+    public static final class TestCase {
+
+        /**
+         * The name of the test case.
+         */
+        public final String name;
+
+        /**
+         * Class name of the instantiated Collection.
+         */
+        public final String className;
+
+        /**
+         * Unmodifiable reference collection, useful for comparisons.
+         */
+        public final Collection<Integer> original;
+
+        /**
+         * A modifiable test collection.
+         */
+        public final Collection<Integer> collection;
+
+        /**
+         * Create a Collection test case.
+         * @param name name of the test case
+         * @param className class name of the instantiated collection
+         * @param original reference collection
+         * @param collection the modifiable test collection
+         */
+        public TestCase(String name, String className,
+                Collection<Integer> original, Collection<Integer> collection) {
+            this.name = name;
+            this.className = className;
+            this.original =
+                    List.class.isAssignableFrom(original.getClass()) ?
+                    Collections.unmodifiableList((List<Integer>) original) :
+                    Set.class.isAssignableFrom(original.getClass()) ?
+                    Collections.unmodifiableSet((Set<Integer>) original) :
+                    Collections.unmodifiableCollection(original);
+            this.collection = collection;
+        }
+
+        @Override
+        public String toString() {
+            return name + " " + className +
+                    "\n original: " + original +
+                    "\n   target: " + collection;
+        }
+    }
+
+    /**
+     * Shuffle a list using a PRNG with known seed for repeatability
+     * @param list the list to be shuffled
+     */
+    public static <E> void shuffle(final List<E> list) {
+        // PRNG with known seed for repeatable tests
+        final Random prng = new Random(13);
+        final int size = list.size();
+        for (int i=0; i < size; i++) {
+            // random index in interval [i, size)
+            final int j = i + prng.nextInt(size - i);
+            // swap elements at indices i & j
+            final E e = list.get(i);
+            list.set(i, list.get(j));
+            list.set(j, e);
+        }
+    }
+
+    /**
+     * Create a {@code Supplier} that creates instances of specified collection
+     * classes of specified length.
+     *
+     * @param classNames class names that implement {@code Collection}
+     * @param size the desired size of each collection
+     */
+    public CollectionSupplier(String[] classNames, int size) {
+        this.classNames = Arrays.copyOf(classNames, classNames.length);
+        this.size = size;
+    }
+
+    @Override
+    public Iterable<TestCase> get() {
+        try {
+            return getThrows();
+        } catch (Exception e) {
+            throw new TestException(e);
+        }
+    }
+
+    private Iterable<TestCase> getThrows() throws Exception {
+        final Collection<TestCase> collections = new LinkedList<>();
+        for (final String className : classNames) {
+            @SuppressWarnings("unchecked")
+            final Class<? extends Collection<Integer>> type =
+                    (Class<? extends Collection<Integer>>) Class.forName(className);
+            final Constructor<? extends Collection<Integer>>
+                    defaultConstructor = type.getConstructor();
+            final Constructor<? extends Collection<Integer>>
+                    copyConstructor = type.getConstructor(Collection.class);
+
+            final Collection<Integer> empty = defaultConstructor.newInstance();
+            collections.add(new TestCase("empty",
+                    className,
+                    copyConstructor.newInstance(empty),
+                    empty));
+
+            final Collection<Integer> single = defaultConstructor.newInstance();
+            single.add(42);
+            collections.add(new TestCase("single",
+                    className,
+                    copyConstructor.newInstance(single),
+                    single));
+
+            final Collection<Integer> regular = defaultConstructor.newInstance();
+            for (int i=0; i < size; i++) {
+                regular.add(i);
+            }
+            collections.add(new TestCase("regular",
+                    className,
+                    copyConstructor.newInstance(regular),
+                    regular));
+
+            final Collection<Integer> reverse = defaultConstructor.newInstance();
+            for (int i=size; i >= 0; i--) {
+                reverse.add(i);
+            }
+            collections.add(new TestCase("reverse",
+                    className,
+                    copyConstructor.newInstance(reverse),
+                    reverse));
+
+            final Collection<Integer> odds = defaultConstructor.newInstance();
+            for (int i=0; i < size; i++) {
+                odds.add((i * 2) + 1);
+            }
+            collections.add(new TestCase("odds",
+                    className,
+                    copyConstructor.newInstance(odds),
+                    odds));
+
+            final Collection<Integer> evens = defaultConstructor.newInstance();
+            for (int i=0; i < size; i++) {
+                evens.add(i * 2);
+            }
+            collections.add(new TestCase("evens",
+                    className,
+                    copyConstructor.newInstance(evens),
+                    evens));
+
+            final Collection<Integer> fibonacci = defaultConstructor.newInstance();
+            int prev2 = 0;
+            int prev1 = 1;
+            for (int i=0; i < size; i++) {
+                final int n = prev1 + prev2;
+                if (n < 0) { // stop on overflow
+                    break;
+                }
+                fibonacci.add(n);
+                prev2 = prev1;
+                prev1 = n;
+            }
+            collections.add(new TestCase("fibonacci",
+                    className,
+                    copyConstructor.newInstance(fibonacci),
+                    fibonacci));
+
+            // variants where the size of the backing storage != reported size
+            // created by removing half of the elements
+
+            final Collection<Integer> emptyWithSlack = defaultConstructor.newInstance();
+            emptyWithSlack.add(42);
+            assertTrue(emptyWithSlack.remove(42));
+            collections.add(new TestCase("emptyWithSlack",
+                    className,
+                    copyConstructor.newInstance(emptyWithSlack),
+                    emptyWithSlack));
+
+            final Collection<Integer> singleWithSlack = defaultConstructor.newInstance();
+            singleWithSlack.add(42);
+            singleWithSlack.add(43);
+            assertTrue(singleWithSlack.remove(43));
+            collections.add(new TestCase("singleWithSlack",
+                    className,
+                    copyConstructor.newInstance(singleWithSlack),
+                    singleWithSlack));
+
+            final Collection<Integer> regularWithSlack = defaultConstructor.newInstance();
+            for (int i=0; i < (2 * size); i++) {
+                regularWithSlack.add(i);
+            }
+            assertTrue(regularWithSlack.removeIf((x) -> {return x >= size;}));
+            collections.add(new TestCase("regularWithSlack",
+                    className,
+                    copyConstructor.newInstance(regularWithSlack),
+                    regularWithSlack));
+
+            final Collection<Integer> reverseWithSlack = defaultConstructor.newInstance();
+            for (int i=2 * size; i >= 0; i--) {
+                reverseWithSlack.add(i);
+            }
+            assertTrue(reverseWithSlack.removeIf((x) -> {return x < size;}));
+            collections.add(new TestCase("reverseWithSlack",
+                    className,
+                    copyConstructor.newInstance(reverseWithSlack),
+                    reverseWithSlack));
+
+            final Collection<Integer> oddsWithSlack = defaultConstructor.newInstance();
+            for (int i = 0; i < 2 * size; i++) {
+                oddsWithSlack.add((i * 2) + 1);
+            }
+            assertTrue(oddsWithSlack.removeIf((x) -> {return x >= size;}));
+            collections.add(new TestCase("oddsWithSlack",
+                    className,
+                    copyConstructor.newInstance(oddsWithSlack),
+                    oddsWithSlack));
+
+            final Collection<Integer> evensWithSlack = defaultConstructor.newInstance();
+            for (int i = 0; i < 2 * size; i++) {
+                evensWithSlack.add(i * 2);
+            }
+            assertTrue(evensWithSlack.removeIf((x) -> {return x >= size;}));
+            collections.add(new TestCase("evensWithSlack",
+                    className,
+                    copyConstructor.newInstance(evensWithSlack),
+                    evensWithSlack));
+
+            final Collection<Integer> fibonacciWithSlack = defaultConstructor.newInstance();
+            prev2 = 0;
+            prev1 = 1;
+            for (int i=0; i < size; i++) {
+                final int n = prev1 + prev2;
+                if (n < 0) { // stop on overflow
+                    break;
+                }
+                fibonacciWithSlack.add(n);
+                prev2 = prev1;
+                prev1 = n;
+            }
+            assertTrue(fibonacciWithSlack.removeIf((x) -> {return x < 20;}));
+            collections.add(new TestCase("fibonacciWithSlack",
+                    className,
+                    copyConstructor.newInstance(fibonacciWithSlack),
+                    fibonacciWithSlack));
+
+        }
+
+        return collections;
+    }
+
+}