Port java.util.Collection.removeIf from OpenJDK8
Source code is taken from jdk8u60.
Bug: 27538943
Change-Id: I485c024f87871e33d2f455be9807775601af77ee
diff --git a/harmony-tests/src/test/java/org/apache/harmony/tests/java/util/ArrayListTest.java b/harmony-tests/src/test/java/org/apache/harmony/tests/java/util/ArrayListTest.java
index 0e9b161..87b1cd9 100644
--- a/harmony-tests/src/test/java/org/apache/harmony/tests/java/util/ArrayListTest.java
+++ b/harmony-tests/src/test/java/org/apache/harmony/tests/java/util/ArrayListTest.java
@@ -32,6 +32,8 @@
import tests.support.Support_ListTest;
import libcore.java.util.ForEachRemainingTester;
+import static libcore.java.util.RemoveIfTester.*;
+
public class ArrayListTest extends junit.framework.TestCase {
List alist;
@@ -1139,6 +1141,14 @@
}
}
+ public void test_removeIf() {
+ runBasicRemoveIfTests(ArrayList<Integer>::new);
+ runBasicRemoveIfTestsUnordered(ArrayList<Integer>::new);
+ runRemoveIfOnEmpty(ArrayList<Integer>::new);
+ testRemoveIfNPE(ArrayList<Integer>::new);
+ testRemoveIfCME(ArrayList<Integer>::new);
+ }
+
/**
* Sets up the fixture, for example, open a network connection. This method
* is called before a test is executed.
diff --git a/harmony-tests/src/test/java/org/apache/harmony/tests/java/util/CollectionsTest.java b/harmony-tests/src/test/java/org/apache/harmony/tests/java/util/CollectionsTest.java
index d5503f8..8b45079 100644
--- a/harmony-tests/src/test/java/org/apache/harmony/tests/java/util/CollectionsTest.java
+++ b/harmony-tests/src/test/java/org/apache/harmony/tests/java/util/CollectionsTest.java
@@ -1649,6 +1649,13 @@
// Correct
}
+ try {
+ c.removeIf(x -> true);
+ fail("Allowed modification of collection");
+ } catch (UnsupportedOperationException e) {
+ // Correct
+ }
+
Collection myCollection = new ArrayList();
myCollection.add(new Integer(20));
myCollection.add(null);
@@ -1704,6 +1711,13 @@
// Correct
}
+ try {
+ c.removeIf(x -> true);
+ fail("Allowed modification of list");
+ } catch (UnsupportedOperationException e) {
+ // Correct
+ }
+
// test with a Random Access List
List smallList = new ArrayList();
smallList.add(null);
@@ -1837,6 +1851,12 @@
} catch (UnsupportedOperationException e) {
// Correct
}
+ try {
+ c.removeIf(x -> true);
+ fail("Allowed modification of set");
+ } catch (UnsupportedOperationException e) {
+ // Correct
+ }
Set mySet = Collections.unmodifiableSet(new HashSet());
assertTrue("Should not contain null", !mySet.contains(null));
@@ -1897,20 +1917,18 @@
assertTrue("Returned set missing elements", c.contains(i.next()));
try {
c.add(new Object());
- } catch (UnsupportedOperationException e) {
- exception = true;
- // Correct
- }
- if (!exception) {
fail("Allowed modification of set");
- }
+ } catch (UnsupportedOperationException e) {}
+
try {
c.remove(new Object());
- } catch (UnsupportedOperationException e) {
- // Correct
- return;
- }
- fail("Allowed modification of set");
+ fail("Allowed modification of set");
+ } catch (UnsupportedOperationException expected) {}
+
+ try {
+ c.removeIf(x -> true);
+ fail("Allowed modification of set");
+ } catch (UnsupportedOperationException expected) {}
}
/**
diff --git a/harmony-tests/src/test/java/org/apache/harmony/tests/java/util/LinkedListTest.java b/harmony-tests/src/test/java/org/apache/harmony/tests/java/util/LinkedListTest.java
index 1904aa9..da01e34 100644
--- a/harmony-tests/src/test/java/org/apache/harmony/tests/java/util/LinkedListTest.java
+++ b/harmony-tests/src/test/java/org/apache/harmony/tests/java/util/LinkedListTest.java
@@ -28,7 +28,6 @@
import java.util.ListIterator;
import java.util.NoSuchElementException;
import java.util.Spliterator;
-import java.util.Vector;
import libcore.java.util.ForEachRemainingTester;
import libcore.java.util.SpliteratorTester;
@@ -37,6 +36,8 @@
import tests.support.Support_ListTest;
+import static libcore.java.util.RemoveIfTester.*;
+
public class LinkedListTest extends junit.framework.TestCase {
LinkedList ll;
@@ -982,6 +983,14 @@
}
}
+ public void test_removeIf() {
+ runBasicRemoveIfTests(LinkedList<Integer>::new);
+ runBasicRemoveIfTestsUnordered(LinkedList<Integer>::new);
+ runRemoveIfOnEmpty(LinkedList<Integer>::new);
+ testRemoveIfNPE(LinkedList<Integer>::new);
+ testRemoveIfCME(LinkedList<Integer>::new);
+ }
+
/**
* java.util.LinkedList#Serialization()
*/
diff --git a/harmony-tests/src/test/java/org/apache/harmony/tests/java/util/VectorTest.java b/harmony-tests/src/test/java/org/apache/harmony/tests/java/util/VectorTest.java
index 0b56eec..a6f5626 100644
--- a/harmony-tests/src/test/java/org/apache/harmony/tests/java/util/VectorTest.java
+++ b/harmony-tests/src/test/java/org/apache/harmony/tests/java/util/VectorTest.java
@@ -27,12 +27,15 @@
import java.util.ConcurrentModificationException;
import java.util.Enumeration;
import java.util.HashSet;
+import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.NoSuchElementException;
import java.util.Spliterator;
import java.util.Vector;
+import static libcore.java.util.RemoveIfTester.*;
+
public class VectorTest extends junit.framework.TestCase {
private Vector tVector = new Vector();
@@ -1464,6 +1467,14 @@
}
}
+ public void test_removeIf() {
+ runBasicRemoveIfTests(Vector<Integer>::new);
+ runBasicRemoveIfTestsUnordered(Vector<Integer>::new);
+ runRemoveIfOnEmpty(Vector<Integer>::new);
+ testRemoveIfNPE(Vector<Integer>::new);
+ testRemoveIfCME(Vector<Integer>::new);
+ }
+
/**
* Sets up the fixture, for example, open a network connection. This method
* is called before a test is executed.
diff --git a/luni/src/test/java/libcore/java/util/RemoveIfTester.java b/luni/src/test/java/libcore/java/util/RemoveIfTester.java
new file mode 100644
index 0000000..f0fdd42
--- /dev/null
+++ b/luni/src/test/java/libcore/java/util/RemoveIfTester.java
@@ -0,0 +1,99 @@
+/*
+ * Copyright (C) 2016 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License
+ */
+
+package libcore.java.util;
+
+import java.util.Collection;
+import java.util.ConcurrentModificationException;
+import java.util.function.Predicate;
+import java.util.function.Supplier;
+
+import static junit.framework.Assert.assertTrue;
+import static junit.framework.Assert.fail;
+
+/**
+ * Tests behavior common to all implementations of {@link Collection#removeIf(Predicate)}.
+ */
+public class RemoveIfTester {
+
+ private static final Predicate<Integer> isEven = x -> x % 2 == 0;
+ private static final Predicate<Integer> isOdd = isEven.negate();
+
+ public static void runBasicRemoveIfTests(Supplier<Collection<Integer>> supp) {
+ Collection<Integer> integers = supp.get();
+ for (int h = 0; h < 100; ++h) {
+ // Insert some ordered integers.
+ integers.add(h);
+ }
+
+ integers.removeIf(isEven);
+ Integer prev = null;
+ for (Integer i : integers) {
+ assertTrue(i % 2 != 0);
+ if (prev != null) {
+ assertTrue(prev <= i);
+ }
+ prev = i;
+ }
+
+ integers.removeIf(isOdd);
+ assertTrue(integers.isEmpty());
+ }
+
+ public static void runBasicRemoveIfTestsUnordered(Supplier<Collection<Integer>> supp) {
+ Collection<Integer> integers = supp.get();
+ for (int h = 0; h < 100; ++h) {
+ // Insert a bunch of arbitrary integers.
+ integers.add((h >>> 2) ^ (h >>> 5) ^ (h >>> 11) ^ (h >>> 17));
+ }
+
+ integers.removeIf(isEven);
+ for (Integer i : integers) {
+ assertTrue(i % 2 != 0);
+ }
+
+ integers.removeIf(isOdd);
+ assertTrue(integers.isEmpty());
+ }
+
+ /**
+ * Removing from an empty collection should not fail.
+ */
+ public static void runRemoveIfOnEmpty(Supplier<Collection<Integer>> supp) {
+ supp.get().removeIf(x -> {
+ fail();
+ return false;
+ });
+ }
+
+ public static void testRemoveIfNPE(Supplier<Collection<Integer>> supp) {
+ try {
+ supp.get().removeIf(null);
+ fail();
+ } catch (NullPointerException expected) {}
+ }
+
+ public static void testRemoveIfCME(Supplier<Collection<Integer>> supp) {
+ Collection<Integer> c = supp.get();
+ c.add(0);
+
+ try {
+ c.removeIf(x -> {c.add(42); return true;});
+ fail();
+ } catch (ConcurrentModificationException expected) {
+ }
+ }
+}
diff --git a/ojluni/src/main/java/java/util/ArrayList.java b/ojluni/src/main/java/java/util/ArrayList.java
index c6ecd33..fec492c 100755
--- a/ojluni/src/main/java/java/util/ArrayList.java
+++ b/ojluni/src/main/java/java/util/ArrayList.java
@@ -27,6 +27,7 @@
package java.util;
import java.util.function.Consumer;
+import java.util.function.Predicate;
/**
* Resizable-array implementation of the <tt>List</tt> interface. Implements
@@ -1366,4 +1367,47 @@
return Spliterator.ORDERED | Spliterator.SIZED | Spliterator.SUBSIZED;
}
}
+
+ @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;
+ }
}
diff --git a/ojluni/src/main/java/java/util/Collection.java b/ojluni/src/main/java/java/util/Collection.java
index 72ee9ae..9f0227f 100755
--- a/ojluni/src/main/java/java/util/Collection.java
+++ b/ojluni/src/main/java/java/util/Collection.java
@@ -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
@@ -366,6 +368,42 @@
*/
boolean removeAll(Collection<?> c);
+
+ /**
+ * Removes all of the elements of this collection that satisfy the given
+ * predicate. Errors or runtime exceptions thrown during iteration or 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 elements cannot be removed
+ * from this collection. Implementations may throw this exception if a
+ * matching element cannot be removed or if, in general, removal is not
+ * supported.
+ * @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
diff --git a/ojluni/src/main/java/java/util/Collections.java b/ojluni/src/main/java/java/util/Collections.java
index 8baf0e7..9912283 100755
--- a/ojluni/src/main/java/java/util/Collections.java
+++ b/ojluni/src/main/java/java/util/Collections.java
@@ -33,7 +33,7 @@
import java.util.function.BiConsumer;
import java.util.function.BiFunction;
import java.util.function.Consumer;
-
+import java.util.function.Predicate;
/**
* This class consists exclusively of static methods that operate on or return
@@ -1146,6 +1146,10 @@
public void forEach(Consumer<? super E> action) {
c.forEach(action);
}
+ @Override
+ public boolean removeIf(Predicate<? super E> filter) {
+ throw new UnsupportedOperationException();
+ }
@SuppressWarnings("unchecked")
@Override
public Spliterator<E> spliterator() {
@@ -1813,6 +1817,10 @@
synchronized (mutex) {c.forEach(consumer);}
}
@Override
+ public boolean removeIf(Predicate<? super E> filter) {
+ synchronized (mutex) {return c.removeIf(filter);}
+ }
+ @Override
public Spliterator<E> spliterator() {
return c.spliterator(); // Must be manually synched by user!
}
@@ -2536,6 +2544,10 @@
@Override
public void forEach(Consumer<? super E> action) {c.forEach(action);}
@Override
+ public boolean removeIf(Predicate<? super E> filter) {
+ return c.removeIf(filter);
+ }
+ @Override
public Spliterator<E> spliterator() {return c.spliterator();}
}
@@ -3356,6 +3368,11 @@
Objects.requireNonNull(action);
}
@Override
+ public boolean removeIf(Predicate<? super E> filter) {
+ Objects.requireNonNull(filter);
+ return false;
+ }
+ @Override
public Spliterator<E> spliterator() { return Spliterators.emptySpliterator(); }
// Preserves singleton property
@@ -3435,6 +3452,12 @@
public int hashCode() { return 1; }
+ @Override
+ public boolean removeIf(Predicate<? super E> filter) {
+ Objects.requireNonNull(filter);
+ return false;
+ }
+
// Override default methods in Collection
@Override
public void forEach(Consumer<? super E> action) {
@@ -3584,6 +3607,10 @@
public void forEach(Consumer<? super E> action) {
action.accept(element);
}
+ @Override
+ public boolean removeIf(Predicate<? super E> filter) {
+ throw new UnsupportedOperationException();
+ }
}
/**
@@ -3630,6 +3657,10 @@
public void forEach(Consumer<? super E> action) {
action.accept(element);
}
+ @Override
+ public boolean removeIf(Predicate<? super E> filter) {
+ throw new UnsupportedOperationException();
+ }
}
/**
@@ -4190,6 +4221,10 @@
public void forEach(Consumer<? super E> action) {
s.forEach(action);
}
+ @Override
+ public boolean removeIf(Predicate<? super E> filter) {
+ return s.removeIf(filter);
+ }
private void readObject(java.io.ObjectInputStream stream)
throws IOException, ClassNotFoundException
@@ -4251,5 +4286,8 @@
// Override default methods in Collection
@Override
public void forEach(Consumer<? super E> action) {q.forEach(action);}
+ public boolean removeIf(Predicate<? super E> filter) {
+ return q.removeIf(filter);
+ }
}
}
diff --git a/ojluni/src/main/java/java/util/Vector.java b/ojluni/src/main/java/java/util/Vector.java
index f43326f..6afdfbd 100755
--- a/ojluni/src/main/java/java/util/Vector.java
+++ b/ojluni/src/main/java/java/util/Vector.java
@@ -26,6 +26,7 @@
package java.util;
import java.util.function.Consumer;
+import java.util.function.Predicate;
/**
* The {@code Vector} class implements a growable array of
@@ -1355,4 +1356,48 @@
return Spliterator.ORDERED | Spliterator.SIZED | Spliterator.SUBSIZED;
}
}
+
+ @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;
+ }
}
