--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/jdk/test/java/util/Iterator/IteratorDefaults.java Mon May 06 20:54:48 2013 -0700
@@ -0,0 +1,425 @@
+/*
+ * 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 org.testng.annotations.Test;
+
+import java.lang.reflect.Constructor;
+import java.util.ArrayList;
+import java.util.Arrays;
+import java.util.Collection;
+import java.util.Collections;
+import java.util.Iterator;
+import java.util.List;
+import java.util.ListIterator;
+import java.util.NoSuchElementException;
+
+import static org.testng.Assert.assertEquals;
+import static org.testng.Assert.assertFalse;
+import static org.testng.Assert.assertTrue;
+import static org.testng.Assert.fail;
+
+/**
+ * @test
+ * @run testng IteratorDefaults
+ * @summary test extension methods on Iterator
+ */
+@Test
+public class IteratorDefaults {
+
+ 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);
+ }
+ }
+
+ public void testRemoveUnsupported() {
+ final Iterator iterator = new Iterator() {
+ @Override
+ public boolean hasNext() {
+ return false;
+ }
+ @Override
+ public Object next() {
+ return null;
+ }
+ };
+
+ try {
+ iterator.remove();
+ fail("expected UnsupportedOperationException from remove not thrown");
+ } catch (UnsupportedOperationException ignore) {
+ }
+ }
+
+ public void testRemoveOverride() {
+ final IteratorWithRemove iterator = new IteratorWithRemove();
+ iterator.remove();
+ assertTrue(iterator.removed);
+ }
+
+ public void testForEach() throws Exception {
+ final Integer[] data = new Integer[1000];
+ for (int i=0; i < data.length; i++) {
+ data[i] = i;
+ }
+ final List<Integer> source = Arrays.asList(data);
+
+ final String[] iterableCollectionClasses = {
+ "java.util.ArrayDeque",
+ "java.util.ArrayList",
+ "java.util.HashSet",
+ "java.util.LinkedHashSet",
+ "java.util.LinkedList",
+ "java.util.PriorityQueue",
+ "java.util.TreeSet",
+ "java.util.Vector",
+ "java.util.concurrent.ConcurrentLinkedDeque",
+ "java.util.concurrent.ConcurrentLinkedQueue",
+ "java.util.concurrent.ConcurrentSkipListSet",
+ "java.util.concurrent.CopyOnWriteArrayList",
+ "java.util.concurrent.CopyOnWriteArraySet",
+ "java.util.concurrent.LinkedBlockingDeque",
+ "java.util.concurrent.LinkedBlockingQueue",
+ "java.util.concurrent.LinkedTransferQueue",
+ "java.util.concurrent.PriorityBlockingQueue"
+ };
+
+ for (final String iterableClass : iterableCollectionClasses) {
+ final Iterable<Integer> iterable =
+ (Iterable<Integer>) Class.forName(iterableClass).newInstance();
+ ((Collection<Integer>) iterable).addAll(source);
+ final Iterator<Integer> iterator = iterable.iterator();
+ final List<Integer> target = new ArrayList<>(source.size());
+ iterator.forEachRemaining(target::add);
+ if ("java.util.HashSet".equals(iterableClass)) {
+ target.sort((x, y) -> x - y);
+ assertEquals(target, source);
+ } else {
+ assertEquals(target, source);
+ }
+
+ // verify that for an iterator that has been advanced via next(),
+ // forEach starts from the current location, not zero
+ final int OFFSET = 5;
+ final List<Integer> reference2 = new ArrayList<>(source).subList(OFFSET, source.size());
+ final List<Integer> removed2 = new ArrayList<>(OFFSET);
+ final Iterator<Integer> iterator2 = iterable.iterator();
+ for (int i=0; i < OFFSET; i++) {
+ // advance the iterator by OFFSET, saving iterated elements
+ removed2.add(iterator2.next());
+ }
+ final List<Integer> target2 = new ArrayList<>(reference2.size());
+ iterator2.forEachRemaining(target2::add);
+ if ("java.util.HashSet".equals(iterableClass)) {
+ assertEquals(target2.size(), reference2.size());
+ target2.addAll(removed2);
+ target2.sort((x, y) -> x - y);
+ assertEquals(target2, source);
+ assertEquals(target2.subList(OFFSET, source.size()), reference2);
+ } else {
+ assertEquals(target2, reference2);
+ }
+ }
+ }
+
+ public void testForEachSubList() throws Exception {
+ final Integer[] data = new Integer[100];
+ for (int i = 0; i < data.length; i++) {
+ data[i] = i;
+ }
+ final List<Integer> source = Arrays.asList(data);
+ final String[] listClasses = {
+ "java.util.ArrayList",
+ "java.util.LinkedList",
+ "java.util.Vector",
+ "java.util.concurrent.CopyOnWriteArrayList"
+ };
+ for (final String listClass : listClasses) {
+ final List<Integer> list =
+ (List<Integer>) Class.forName(listClass).newInstance();
+ list.addAll(source);
+ trimmedSubList(list, new Callback() {
+ @Override
+ public void call(final List<Integer> list) {
+ if (list.size() < 1) {
+ return;
+ }
+ final List<Integer> target = new ArrayList<>(list.size());
+ final ListIterator<Integer> iterator = list.listIterator();
+ assertTrue(iterator.hasNext());
+ assertFalse(iterator.hasPrevious());
+ assertEquals(iterator.nextIndex(), 0);
+ assertEquals(iterator.previousIndex(), -1);
+
+ iterator.forEachRemaining(target::add);
+ assertEquals(target, list);
+
+ assertFalse(iterator.hasNext());
+ assertTrue(iterator.hasPrevious());
+ assertEquals(iterator.nextIndex(), list.size());
+ assertEquals(iterator.previousIndex(), list.size() - 1);
+
+ try {
+ iterator.next();
+ fail(listClass + " iterator advanced beyond end");
+ } catch (NoSuchElementException ignore) {
+ }
+ }
+ });
+ }
+ }
+
+ public void testOptimizedForEach() throws Exception {
+ final Integer[] data = new Integer[1000 * 1000];
+ for (int i=0; i < data.length; i++) {
+ data[i] = i;
+ }
+ final List<Integer> source = Arrays.asList(data);
+
+ final String[] listClasses = {
+ "java.util.ArrayList",
+ "java.util.LinkedList",
+ "java.util.Vector",
+ "java.util.concurrent.CopyOnWriteArrayList"
+ };
+
+ final int OFFSET = 3;
+ final List<Integer> target = new ArrayList<>(source);
+ for (final String listClass : listClasses) {
+ final List<Integer> list =
+ (List<Integer>) Class.forName(listClass).newInstance();
+ list.addAll(source);
+ final ListIterator<Integer> iterator = list.listIterator();
+ assertFalse(iterator.hasPrevious());
+ for (int i=0; i < OFFSET; i++) {
+ iterator.next();
+ }
+ assertTrue(iterator.hasNext());
+ assertTrue(iterator.hasPrevious());
+ assertEquals(iterator.nextIndex(), OFFSET);
+ assertEquals(iterator.previousIndex(), OFFSET - 1);
+
+ iterator.forEachRemaining(e -> {
+ target.set(e, e + 1);
+ });
+ for (int i=OFFSET; i < data.length; i++) {
+ assertEquals(target.get(i).intValue(), source.get(i)+1);
+ }
+
+ assertFalse(iterator.hasNext());
+ assertTrue(iterator.hasPrevious());
+ assertEquals(iterator.nextIndex(), data.length);
+ assertEquals(iterator.previousIndex(), data.length - 1);
+
+ // CopyOnWriteArrayList.listIterator().remove() is unsupported
+ if (!"java.util.concurrent.CopyOnWriteArrayList".equals(listClass)) {
+ for (int i = data.length - 1; i >= 0; i--) {
+ iterator.remove(); // must not throw
+ if (i > 0) {
+ iterator.previous();
+ }
+ }
+ assertTrue(list.isEmpty());
+ }
+
+ try {
+ iterator.next();
+ fail(listClass + " iterator advanced beyond end");
+ } catch (NoSuchElementException ignore) {
+ }
+ }
+ }
+
+ @Test(enabled = false)
+ public void compareForEachPerformance() throws Exception {
+ final Integer[] data = new Integer[1000 * 100];
+ for (int i=0; i < data.length; i++) {
+ data[i] = i;
+ }
+ final List<Integer> source = Arrays.asList(data);
+
+ final String[] iterableCollectionClasses = {
+ "java.util.ArrayList", // warmup, results discarded
+ "java.util.ArrayDeque",
+ "java.util.ArrayList",
+ "java.util.HashSet",
+ "java.util.LinkedHashSet",
+ "java.util.LinkedList",
+ "java.util.PriorityQueue",
+ "java.util.TreeSet",
+ "java.util.Vector",
+ "java.util.concurrent.ConcurrentLinkedDeque",
+ "java.util.concurrent.ConcurrentLinkedQueue",
+ "java.util.concurrent.ConcurrentSkipListSet",
+ "java.util.concurrent.CopyOnWriteArrayList",
+ "java.util.concurrent.CopyOnWriteArraySet",
+ "java.util.concurrent.LinkedBlockingDeque",
+ "java.util.concurrent.LinkedBlockingQueue",
+ "java.util.concurrent.LinkedTransferQueue",
+ "java.util.concurrent.PriorityBlockingQueue"
+ };
+
+ boolean warmup = true;
+ final int ITERATIONS = 10;
+ final Integer[] target = new Integer[source.size()];
+ for (final String iterableClass : iterableCollectionClasses) {
+ final Class<? extends Collection<Integer>> type =
+ (Class<? extends Collection<Integer>>) Class.forName(iterableClass);
+ final Constructor<? extends Collection<Integer>> copyConstructor =
+ type.getConstructor(Collection.class);
+ final Iterable<Integer> iterable = copyConstructor.newInstance(source);
+ final Iterable<Integer> reference =
+ Collections.unmodifiableCollection((Collection<Integer>) iterable);
+
+ for (int i=0; i < ITERATIONS; i++) {
+ final Iterator<Integer> iterator = reference.iterator();
+ final long forEachStart = System.nanoTime();
+ iterator.forEachRemaining(x -> {target[x.intValue()] = x;});
+ final long forEachEnd = System.nanoTime();
+
+ final Iterator<Integer> iterator2 = reference.iterator();
+ Integer x;
+ final long iteratorStart = System.nanoTime();
+ while (iterator2.hasNext()) {
+ x = iterator2.next();
+ target[x.intValue()] = x;
+ }
+ final long iteratorEnd = System.nanoTime();
+
+ if (warmup) { continue; } // warmup, discard results
+ final long forEachTime = forEachEnd - forEachStart;
+ final long iteratorTime = iteratorEnd - iteratorStart;
+ final long speedup = iteratorTime - forEachTime;
+ System.out.print(iterableClass);
+ System.out.print(" iterator: ");
+ System.out.print(iteratorTime);
+ System.out.print(", forEach: ");
+ System.out.print(forEachTime);
+ System.out.print(", speedup: ");
+ System.out.print(speedup);
+ System.out.print(" (");
+ System.out.print((speedup * 100) / iteratorTime);
+ System.out.print("%)\n");
+ }
+ if (warmup) { warmup = false; }
+ System.out.println();
+ }
+ }
+
+ @Test(enabled = false)
+ public void compareSubListForEachPerformance() throws Exception {
+ final Integer[] data = new Integer[1000 * 100];
+ for (int i = 0; i < data.length; i++) {
+ data[i] = i;
+ }
+ final List<Integer> source = Arrays.asList(data);
+
+ final String[] listClasses = {
+ "java.util.ArrayList", // warmup, results discarded
+ "java.util.ArrayList",
+ "java.util.LinkedList",
+ "java.util.Vector",
+ "java.util.concurrent.CopyOnWriteArrayList"
+ };
+
+ boolean warmup = true;
+ final int ITERATIONS = 10;
+ final Integer[] target = new Integer[source.size()];
+ for (final String listClass : listClasses) {
+ final Class<? extends List<Integer >> type =
+ (Class<? extends List<Integer>>) Class.forName(listClass);
+ final Constructor<? extends List<Integer >> copyConstructor =
+ type.getConstructor(Collection.class);
+ final List<Integer> iterable = copyConstructor.newInstance(source);
+ final List<Integer> reference = Collections.unmodifiableList(iterable);
+
+ for (int i = 0; i < ITERATIONS; i++) {
+ final Iterator<Integer> iterator = reference.subList(42, reference.size() - 37).iterator();
+ final long forEachStart = System.nanoTime();
+ iterator.forEachRemaining(x -> {
+ target[x.intValue()] = x;
+ });
+ final long forEachEnd = System.nanoTime();
+
+ final Iterator<Integer> iterator2 = reference.iterator();
+ Integer x;
+ final long iteratorStart = System.nanoTime();
+ while (iterator2.hasNext()) {
+ x = iterator2.next();
+ target[x.intValue()] = x;
+ }
+ final long iteratorEnd = System.nanoTime();
+
+ if (warmup) { continue; } // warmup, discard results
+ final long forEachTime = forEachEnd - forEachStart;
+ final long iteratorTime = iteratorEnd - iteratorStart;
+ final long speedup = iteratorTime - forEachTime;
+ System.out.print(listClass);
+ System.out.print(" iterator: ");
+ System.out.print(iteratorTime);
+ System.out.print(", forEach: ");
+ System.out.print(forEachTime);
+ System.out.print(", speedup: ");
+ System.out.print(speedup);
+ System.out.print(" (");
+ System.out.print((speedup * 100) / iteratorTime);
+ System.out.print("%)\n");
+ }
+ if (warmup) { warmup = false; }
+ System.out.println();
+ }
+ }
+
+ static class IteratorWithRemove implements Iterator {
+
+ public boolean removed;
+
+ IteratorWithRemove() {
+ removed = false;
+ }
+
+ @Override
+ public boolean hasNext() {
+ return false;
+ }
+
+ @Override
+ public Object next() {
+ return null;
+ }
+
+ @Override
+ public void remove() {
+ removed = true;
+ }
+ }
+}