1 /*
2 * Copyright (c) 2012, Oracle and/or its affiliates. All rights reserved.
3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
4 *
5 * This code is free software; you can redistribute it and/or modify it
6 * under the terms of the GNU General Public License version 2 only, as
7 * published by the Free Software Foundation.
8 *
9 * This code is distributed in the hope that it will be useful, but WITHOUT
10 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
11 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
12 * version 2 for more details (a copy is included in the LICENSE file that
13 * accompanied this code).
14 *
15 * You should have received a copy of the GNU General Public License version
16 * 2 along with this work; if not, write to the Free Software Foundation,
17 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
18 *
19 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
20 * or visit www.oracle.com if you need additional information or have any
21 * questions.
22 */
23
24 import org.testng.annotations.Test;
25
26 import java.lang.reflect.Constructor;
27 import java.util.ArrayList;
28 import java.util.Arrays;
29 import java.util.Collection;
30 import java.util.Collections;
31 import java.util.Iterator;
32 import java.util.List;
33 import java.util.ListIterator;
34 import java.util.NoSuchElementException;
35
36 import static org.testng.Assert.assertEquals;
37 import static org.testng.Assert.assertFalse;
38 import static org.testng.Assert.assertTrue;
39 import static org.testng.Assert.fail;
40
41 /**
42 * @test
43 * @run testng IteratorDefaults
44 * @summary test extension methods on Iterator
45 */
46 @Test
47 public class IteratorDefaults {
48
49 private static interface Callback {
50 void call(List<Integer> list);
51 }
52
53 // call the callback for each recursive subList
54 private void trimmedSubList(final List<Integer> list, final Callback callback) {
55 int size = list.size();
56 if (size > 1) {
57 // trim 1 element from both ends
58 final List<Integer> subList = list.subList(1, size - 1);
59 callback.call(subList);
60 trimmedSubList(subList, callback);
61 }
62 }
63
64 public void testRemoveUnsupported() {
65 final Iterator iterator = new Iterator() {
66 @Override
67 public boolean hasNext() {
68 return false;
69 }
70 @Override
71 public Object next() {
72 return null;
73 }
74 };
75
76 try {
77 iterator.remove();
78 fail("expected UnsupportedOperationException from remove not thrown");
79 } catch (UnsupportedOperationException ignore) {
80 }
81 }
82
83 public void testRemoveOverride() {
84 final IteratorWithRemove iterator = new IteratorWithRemove();
85 iterator.remove();
86 assertTrue(iterator.removed);
87 }
88
89 public void testForEach() throws Exception {
90 final Integer[] data = new Integer[1000];
91 for (int i=0; i < data.length; i++) {
92 data[i] = i;
93 }
94 final List<Integer> source = Arrays.asList(data);
95
96 final String[] iterableCollectionClasses = {
97 "java.util.ArrayDeque",
98 "java.util.ArrayList",
99 "java.util.HashSet",
100 "java.util.LinkedHashSet",
101 "java.util.LinkedList",
102 "java.util.PriorityQueue",
103 "java.util.TreeSet",
104 "java.util.Vector",
105 "java.util.concurrent.ConcurrentLinkedDeque",
106 "java.util.concurrent.ConcurrentLinkedQueue",
107 "java.util.concurrent.ConcurrentSkipListSet",
108 "java.util.concurrent.CopyOnWriteArrayList",
109 "java.util.concurrent.CopyOnWriteArraySet",
110 "java.util.concurrent.LinkedBlockingDeque",
111 "java.util.concurrent.LinkedBlockingQueue",
112 "java.util.concurrent.LinkedTransferQueue",
113 "java.util.concurrent.PriorityBlockingQueue"
114 };
115
116 for (final String iterableClass : iterableCollectionClasses) {
117 final Iterable<Integer> iterable =
118 (Iterable<Integer>) Class.forName(iterableClass).newInstance();
119 ((Collection<Integer>) iterable).addAll(source);
120 final Iterator<Integer> iterator = iterable.iterator();
121 final List<Integer> target = new ArrayList<>(source.size());
122 iterator.forEachRemaining(target::add);
123 if ("java.util.HashSet".equals(iterableClass)) {
124 target.sort((x, y) -> x - y);
125 assertEquals(target, source);
126 } else {
127 assertEquals(target, source);
128 }
129
130 // verify that for an iterator that has been advanced via next(),
131 // forEach starts from the current location, not zero
132 final int OFFSET = 5;
133 final List<Integer> reference2 = new ArrayList<>(source).subList(OFFSET, source.size());
134 final List<Integer> removed2 = new ArrayList<>(OFFSET);
135 final Iterator<Integer> iterator2 = iterable.iterator();
136 for (int i=0; i < OFFSET; i++) {
137 // advance the iterator by OFFSET, saving iterated elements
138 removed2.add(iterator2.next());
139 }
140 final List<Integer> target2 = new ArrayList<>(reference2.size());
141 iterator2.forEachRemaining(target2::add);
142 if ("java.util.HashSet".equals(iterableClass)) {
143 assertEquals(target2.size(), reference2.size());
144 target2.addAll(removed2);
145 target2.sort((x, y) -> x - y);
146 assertEquals(target2, source);
147 assertEquals(target2.subList(OFFSET, source.size()), reference2);
148 } else {
149 assertEquals(target2, reference2);
150 }
151 }
152 }
153
154 public void testForEachSubList() throws Exception {
155 final Integer[] data = new Integer[100];
156 for (int i = 0; i < data.length; i++) {
157 data[i] = i;
158 }
159 final List<Integer> source = Arrays.asList(data);
160 final String[] listClasses = {
161 "java.util.ArrayList",
162 "java.util.LinkedList",
163 "java.util.Vector",
164 "java.util.concurrent.CopyOnWriteArrayList"
165 };
166 for (final String listClass : listClasses) {
167 final List<Integer> list =
168 (List<Integer>) Class.forName(listClass).newInstance();
169 list.addAll(source);
170 trimmedSubList(list, new Callback() {
171 @Override
172 public void call(final List<Integer> list) {
173 if (list.size() < 1) {
174 return;
175 }
176 final List<Integer> target = new ArrayList<>(list.size());
177 final ListIterator<Integer> iterator = list.listIterator();
178 assertTrue(iterator.hasNext());
179 assertFalse(iterator.hasPrevious());
180 assertEquals(iterator.nextIndex(), 0);
181 assertEquals(iterator.previousIndex(), -1);
182
183 iterator.forEachRemaining(target::add);
184 assertEquals(target, list);
185
186 assertFalse(iterator.hasNext());
187 assertTrue(iterator.hasPrevious());
188 assertEquals(iterator.nextIndex(), list.size());
189 assertEquals(iterator.previousIndex(), list.size() - 1);
190
191 try {
192 iterator.next();
193 fail(listClass + " iterator advanced beyond end");
194 } catch (NoSuchElementException ignore) {
195 }
196 }
197 });
198 }
199 }
200
201 public void testOptimizedForEach() throws Exception {
202 final Integer[] data = new Integer[1000 * 1000];
203 for (int i=0; i < data.length; i++) {
204 data[i] = i;
205 }
206 final List<Integer> source = Arrays.asList(data);
207
208 final String[] listClasses = {
209 "java.util.ArrayList",
210 "java.util.LinkedList",
211 "java.util.Vector",
212 "java.util.concurrent.CopyOnWriteArrayList"
213 };
214
215 final int OFFSET = 3;
216 final List<Integer> target = new ArrayList<>(source);
217 for (final String listClass : listClasses) {
218 final List<Integer> list =
219 (List<Integer>) Class.forName(listClass).newInstance();
220 list.addAll(source);
221 final ListIterator<Integer> iterator = list.listIterator();
222 assertFalse(iterator.hasPrevious());
223 for (int i=0; i < OFFSET; i++) {
224 iterator.next();
225 }
226 assertTrue(iterator.hasNext());
227 assertTrue(iterator.hasPrevious());
228 assertEquals(iterator.nextIndex(), OFFSET);
229 assertEquals(iterator.previousIndex(), OFFSET - 1);
230
231 iterator.forEachRemaining(e -> {
232 target.set(e, e + 1);
233 });
234 for (int i=OFFSET; i < data.length; i++) {
235 assertEquals(target.get(i).intValue(), source.get(i)+1);
236 }
237
238 assertFalse(iterator.hasNext());
239 assertTrue(iterator.hasPrevious());
240 assertEquals(iterator.nextIndex(), data.length);
241 assertEquals(iterator.previousIndex(), data.length - 1);
242
243 // CopyOnWriteArrayList.listIterator().remove() is unsupported
244 if (!"java.util.concurrent.CopyOnWriteArrayList".equals(listClass)) {
245 for (int i = data.length - 1; i >= 0; i--) {
246 iterator.remove(); // must not throw
247 if (i > 0) {
248 iterator.previous();
249 }
250 }
251 assertTrue(list.isEmpty());
252 }
253
254 try {
255 iterator.next();
256 fail(listClass + " iterator advanced beyond end");
257 } catch (NoSuchElementException ignore) {
258 }
259 }
260 }
261
262 @Test(enabled = false)
263 public void compareForEachPerformance() throws Exception {
264 final Integer[] data = new Integer[1000 * 100];
265 for (int i=0; i < data.length; i++) {
266 data[i] = i;
267 }
268 final List<Integer> source = Arrays.asList(data);
269
270 final String[] iterableCollectionClasses = {
271 "java.util.ArrayList", // warmup, results discarded
272 "java.util.ArrayDeque",
273 "java.util.ArrayList",
274 "java.util.HashSet",
275 "java.util.LinkedHashSet",
276 "java.util.LinkedList",
277 "java.util.PriorityQueue",
278 "java.util.TreeSet",
279 "java.util.Vector",
280 "java.util.concurrent.ConcurrentLinkedDeque",
281 "java.util.concurrent.ConcurrentLinkedQueue",
282 "java.util.concurrent.ConcurrentSkipListSet",
283 "java.util.concurrent.CopyOnWriteArrayList",
284 "java.util.concurrent.CopyOnWriteArraySet",
285 "java.util.concurrent.LinkedBlockingDeque",
286 "java.util.concurrent.LinkedBlockingQueue",
287 "java.util.concurrent.LinkedTransferQueue",
288 "java.util.concurrent.PriorityBlockingQueue"
289 };
290
291 boolean warmup = true;
292 final int ITERATIONS = 10;
293 final Integer[] target = new Integer[source.size()];
294 for (final String iterableClass : iterableCollectionClasses) {
295 final Class<? extends Collection<Integer>> type =
296 (Class<? extends Collection<Integer>>) Class.forName(iterableClass);
297 final Constructor<? extends Collection<Integer>> copyConstructor =
298 type.getConstructor(Collection.class);
299 final Iterable<Integer> iterable = copyConstructor.newInstance(source);
300 final Iterable<Integer> reference =
301 Collections.unmodifiableCollection((Collection<Integer>) iterable);
302
303 for (int i=0; i < ITERATIONS; i++) {
304 final Iterator<Integer> iterator = reference.iterator();
305 final long forEachStart = System.nanoTime();
306 iterator.forEachRemaining(x -> {target[x.intValue()] = x;});
307 final long forEachEnd = System.nanoTime();
308
309 final Iterator<Integer> iterator2 = reference.iterator();
310 Integer x;
311 final long iteratorStart = System.nanoTime();
312 while (iterator2.hasNext()) {
313 x = iterator2.next();
314 target[x.intValue()] = x;
315 }
316 final long iteratorEnd = System.nanoTime();
317
318 if (warmup) { continue; } // warmup, discard results
319 final long forEachTime = forEachEnd - forEachStart;
320 final long iteratorTime = iteratorEnd - iteratorStart;
321 final long speedup = iteratorTime - forEachTime;
322 System.out.print(iterableClass);
323 System.out.print(" iterator: ");
324 System.out.print(iteratorTime);
325 System.out.print(", forEach: ");
326 System.out.print(forEachTime);
327 System.out.print(", speedup: ");
328 System.out.print(speedup);
329 System.out.print(" (");
330 System.out.print((speedup * 100) / iteratorTime);
331 System.out.print("%)\n");
332 }
333 if (warmup) { warmup = false; }
334 System.out.println();
335 }
336 }
337
338 @Test(enabled = false)
339 public void compareSubListForEachPerformance() throws Exception {
340 final Integer[] data = new Integer[1000 * 100];
341 for (int i = 0; i < data.length; i++) {
342 data[i] = i;
343 }
344 final List<Integer> source = Arrays.asList(data);
345
346 final String[] listClasses = {
347 "java.util.ArrayList", // warmup, results discarded
348 "java.util.ArrayList",
349 "java.util.LinkedList",
350 "java.util.Vector",
351 "java.util.concurrent.CopyOnWriteArrayList"
352 };
353
354 boolean warmup = true;
355 final int ITERATIONS = 10;
356 final Integer[] target = new Integer[source.size()];
357 for (final String listClass : listClasses) {
358 final Class<? extends List<Integer >> type =
359 (Class<? extends List<Integer>>) Class.forName(listClass);
360 final Constructor<? extends List<Integer >> copyConstructor =
361 type.getConstructor(Collection.class);
362 final List<Integer> iterable = copyConstructor.newInstance(source);
363 final List<Integer> reference = Collections.unmodifiableList(iterable);
364
365 for (int i = 0; i < ITERATIONS; i++) {
366 final Iterator<Integer> iterator = reference.subList(42, reference.size() - 37).iterator();
367 final long forEachStart = System.nanoTime();
368 iterator.forEachRemaining(x -> {
369 target[x.intValue()] = x;
370 });
371 final long forEachEnd = System.nanoTime();
372
373 final Iterator<Integer> iterator2 = reference.iterator();
374 Integer x;
375 final long iteratorStart = System.nanoTime();
376 while (iterator2.hasNext()) {
377 x = iterator2.next();
378 target[x.intValue()] = x;
379 }
380 final long iteratorEnd = System.nanoTime();
381
382 if (warmup) { continue; } // warmup, discard results
383 final long forEachTime = forEachEnd - forEachStart;
384 final long iteratorTime = iteratorEnd - iteratorStart;
385 final long speedup = iteratorTime - forEachTime;
386 System.out.print(listClass);
387 System.out.print(" iterator: ");
388 System.out.print(iteratorTime);
389 System.out.print(", forEach: ");
390 System.out.print(forEachTime);
391 System.out.print(", speedup: ");
392 System.out.print(speedup);
393 System.out.print(" (");
394 System.out.print((speedup * 100) / iteratorTime);
395 System.out.print("%)\n");
396 }
397 if (warmup) { warmup = false; }
398 System.out.println();
399 }
400 }
401
402 static class IteratorWithRemove implements Iterator {
403
404 public boolean removed;
405
406 IteratorWithRemove() {
407 removed = false;
408 }
409
410 @Override
411 public boolean hasNext() {
412 return false;
413 }
414
415 @Override
416 public Object next() {
417 return null;
418 }
419
420 @Override
421 public void remove() {
422 removed = true;
423 }
424 }
425 }