1 /*
2 * Copyright (c) 2013, 2016, 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 /**
25 * @test
26 * @summary Spliterator traversing and splitting tests
27 * @run testng SpliteratorTraversingAndSplittingTest
28 * @bug 8020016 8071477
29 */
30
31 import org.testng.annotations.DataProvider;
32 import org.testng.annotations.Test;
33
34 import java.util.AbstractCollection;
35 import java.util.AbstractList;
36 import java.util.AbstractSet;
37 import java.util.ArrayDeque;
38 import java.util.ArrayList;
39 import java.util.Arrays;
40 import java.util.Collection;
41 import java.util.Collections;
42 import java.util.Comparator;
43 import java.util.Deque;
44 import java.util.HashMap;
45 import java.util.HashSet;
46 import java.util.IdentityHashMap;
47 import java.util.Iterator;
48 import java.util.LinkedHashMap;
49 import java.util.LinkedHashSet;
50 import java.util.LinkedList;
51 import java.util.List;
52 import java.util.Map;
53 import java.util.PriorityQueue;
54 import java.util.Set;
55 import java.util.SortedSet;
56 import java.util.Spliterator;
57 import java.util.Spliterators;
58 import java.util.Stack;
59 import java.util.TreeMap;
60 import java.util.TreeSet;
61 import java.util.Vector;
62 import java.util.WeakHashMap;
63 import java.util.concurrent.ArrayBlockingQueue;
64 import java.util.concurrent.ConcurrentHashMap;
65 import java.util.concurrent.ConcurrentLinkedQueue;
66 import java.util.concurrent.ConcurrentSkipListMap;
67 import java.util.concurrent.ConcurrentSkipListSet;
68 import java.util.concurrent.CopyOnWriteArrayList;
69 import java.util.concurrent.CopyOnWriteArraySet;
70 import java.util.concurrent.LinkedBlockingDeque;
71 import java.util.concurrent.LinkedBlockingQueue;
72 import java.util.concurrent.LinkedTransferQueue;
73 import java.util.concurrent.PriorityBlockingQueue;
74 import java.util.function.Consumer;
75 import java.util.function.DoubleConsumer;
76 import java.util.function.Function;
77 import java.util.function.IntConsumer;
78 import java.util.function.LongConsumer;
79 import java.util.function.Supplier;
80 import java.util.function.UnaryOperator;
81
82 import static org.testng.Assert.*;
83 import static org.testng.Assert.assertEquals;
84
85 @Test
86 public class SpliteratorTraversingAndSplittingTest {
87
88 private static final List<Integer> SIZES = Arrays.asList(0, 1, 10, 42);
89
90 private static final String LOW = new String(new char[] {Character.MIN_LOW_SURROGATE});
91 private static final String HIGH = new String(new char[] {Character.MIN_HIGH_SURROGATE});
92 private static final String HIGH_LOW = HIGH + LOW;
93 private static final String CHAR_HIGH_LOW = "A" + HIGH_LOW;
94 private static final String HIGH_LOW_CHAR = HIGH_LOW + "A";
95 private static final String CHAR_HIGH_LOW_CHAR = "A" + HIGH_LOW + "A";
96
97 private static final List<String> STRINGS = generateTestStrings();
98
99 private static List<String> generateTestStrings() {
100 List<String> strings = new ArrayList<>();
101 for (int n : Arrays.asList(1, 2, 3, 16, 17)) {
102 strings.add(generate("A", n));
103 strings.add(generate(LOW, n));
104 strings.add(generate(HIGH, n));
105 strings.add(generate(HIGH_LOW, n));
106 strings.add(generate(CHAR_HIGH_LOW, n));
107 strings.add(generate(HIGH_LOW_CHAR, n));
108 strings.add(generate(CHAR_HIGH_LOW_CHAR, n));
109 }
110 return strings;
111 }
112
113 private static String generate(String s, int n) {
114 StringBuilder sb = new StringBuilder();
115 for (int i = 0; i < n; i++) {
116 sb.append(s);
117 }
118 return sb.toString();
119 }
120
121 private static class SpliteratorDataBuilder<T> {
122 List<Object[]> data;
123
124 List<T> exp;
125
126 Map<T, T> mExp;
127
128 SpliteratorDataBuilder(List<Object[]> data, List<T> exp) {
129 this.data = data;
130 this.exp = exp;
131 this.mExp = createMap(exp);
132 }
133
134 Map<T, T> createMap(List<T> l) {
135 Map<T, T> m = new LinkedHashMap<>();
136 for (T t : l) {
137 m.put(t, t);
138 }
139 return m;
140 }
141
142 void add(String description, Collection<?> expected, Supplier<Spliterator<?>> s) {
143 description = joiner(description).toString();
144 data.add(new Object[]{description, expected, s});
145 }
146
147 void add(String description, Supplier<Spliterator<?>> s) {
148 add(description, exp, s);
149 }
150
151 void addCollection(Function<Collection<T>, ? extends Collection<T>> c) {
152 add("new " + c.apply(Collections.<T>emptyList()).getClass().getName() + ".spliterator()",
153 () -> c.apply(exp).spliterator());
154 }
155
156 void addList(Function<Collection<T>, ? extends List<T>> l) {
157 addCollection(l);
158 addCollection(l.andThen(list -> list.subList(0, list.size())));
159 }
160
161 void addMap(Function<Map<T, T>, ? extends Map<T, T>> m) {
162 String description = "new " + m.apply(Collections.<T, T>emptyMap()).getClass().getName();
163 addMap(m, description);
164 }
165
166 void addMap(Function<Map<T, T>, ? extends Map<T, T>> m, String description) {
167 add(description + ".keySet().spliterator()", () -> m.apply(mExp).keySet().spliterator());
168 add(description + ".values().spliterator()", () -> m.apply(mExp).values().spliterator());
169 add(description + ".entrySet().spliterator()", mExp.entrySet(), () -> m.apply(mExp).entrySet().spliterator());
170 }
171
172 StringBuilder joiner(String description) {
173 return new StringBuilder(description).
174 append(" {").
175 append("size=").append(exp.size()).
176 append("}");
177 }
178 }
179
180 static Object[][] spliteratorDataProvider;
181
182 @DataProvider(name = "Spliterator<Integer>")
183 public static Object[][] spliteratorDataProvider() {
184 if (spliteratorDataProvider != null) {
185 return spliteratorDataProvider;
186 }
187
188 List<Object[]> data = new ArrayList<>();
189 for (int size : SIZES) {
190 List<Integer> exp = listIntRange(size);
191 SpliteratorDataBuilder<Integer> db = new SpliteratorDataBuilder<>(data, exp);
192
193 // Direct spliterator methods
194
195 db.add("Spliterators.spliterator(Collection, ...)",
196 () -> Spliterators.spliterator(exp, 0));
197
198 db.add("Spliterators.spliterator(Iterator, ...)",
199 () -> Spliterators.spliterator(exp.iterator(), exp.size(), 0));
200
201 db.add("Spliterators.spliteratorUnknownSize(Iterator, ...)",
202 () -> Spliterators.spliteratorUnknownSize(exp.iterator(), 0));
203
204 db.add("Spliterators.spliterator(Spliterators.iteratorFromSpliterator(Spliterator ), ...)",
205 () -> Spliterators.spliterator(Spliterators.iterator(exp.spliterator()), exp.size(), 0));
206
207 db.add("Spliterators.spliterator(T[], ...)",
208 () -> Spliterators.spliterator(exp.toArray(new Integer[0]), 0));
209
210 db.add("Arrays.spliterator(T[], ...)",
211 () -> Arrays.spliterator(exp.toArray(new Integer[0])));
212
213 class SpliteratorFromIterator extends Spliterators.AbstractSpliterator<Integer> {
214 Iterator<Integer> it;
215
216 SpliteratorFromIterator(Iterator<Integer> it, long est) {
217 super(est, Spliterator.SIZED);
218 this.it = it;
219 }
220
221 @Override
222 public boolean tryAdvance(Consumer<? super Integer> action) {
223 if (action == null)
224 throw new NullPointerException();
225 if (it.hasNext()) {
226 action.accept(it.next());
227 return true;
228 }
229 else {
230 return false;
231 }
232 }
233 }
234 db.add("new Spliterators.AbstractSpliterator()",
235 () -> new SpliteratorFromIterator(exp.iterator(), exp.size()));
236
237 // Collections
238
239 // default method implementations
240
241 class AbstractCollectionImpl extends AbstractCollection<Integer> {
242 Collection<Integer> c;
243
244 AbstractCollectionImpl(Collection<Integer> c) {
245 this.c = c;
246 }
247
248 @Override
249 public Iterator<Integer> iterator() {
250 return c.iterator();
251 }
252
253 @Override
254 public int size() {
255 return c.size();
256 }
257 }
258 db.addCollection(
259 c -> new AbstractCollectionImpl(c));
260
261 class AbstractListImpl extends AbstractList<Integer> {
262 List<Integer> l;
263
264 AbstractListImpl(Collection<Integer> c) {
265 this.l = new ArrayList<>(c);
266 }
267
268 @Override
269 public Integer get(int index) {
270 return l.get(index);
271 }
272
273 @Override
274 public int size() {
275 return l.size();
276 }
277 }
278 db.addCollection(
279 c -> new AbstractListImpl(c));
280
281 class AbstractSetImpl extends AbstractSet<Integer> {
282 Set<Integer> s;
283
284 AbstractSetImpl(Collection<Integer> c) {
285 this.s = new HashSet<>(c);
286 }
287
288 @Override
289 public Iterator<Integer> iterator() {
290 return s.iterator();
291 }
292
293 @Override
294 public int size() {
295 return s.size();
296 }
297 }
298 db.addCollection(
299 c -> new AbstractSetImpl(c));
300
301 class AbstractSortedSetImpl extends AbstractSet<Integer> implements SortedSet<Integer> {
302 SortedSet<Integer> s;
303
304 AbstractSortedSetImpl(Collection<Integer> c) {
305 this.s = new TreeSet<>(c);
306 }
307
308 @Override
309 public Iterator<Integer> iterator() {
310 return s.iterator();
311 }
312
313 @Override
314 public int size() {
315 return s.size();
316 }
317
318 @Override
319 public Comparator<? super Integer> comparator() {
320 return s.comparator();
321 }
322
323 @Override
324 public SortedSet<Integer> subSet(Integer fromElement, Integer toElement) {
325 return s.subSet(fromElement, toElement);
326 }
327
328 @Override
329 public SortedSet<Integer> headSet(Integer toElement) {
330 return s.headSet(toElement);
331 }
332
333 @Override
334 public SortedSet<Integer> tailSet(Integer fromElement) {
335 return s.tailSet(fromElement);
336 }
337
338 @Override
339 public Integer first() {
340 return s.first();
341 }
342
343 @Override
344 public Integer last() {
345 return s.last();
346 }
347
348 @Override
349 public Spliterator<Integer> spliterator() {
350 return SortedSet.super.spliterator();
351 }
352 }
353 db.addCollection(
354 c -> new AbstractSortedSetImpl(c));
355
356 class IterableWrapper implements Iterable<Integer> {
357 final Iterable<Integer> it;
358
359 IterableWrapper(Iterable<Integer> it) {
360 this.it = it;
361 }
362
363 @Override
364 public Iterator<Integer> iterator() {
365 return it.iterator();
366 }
367 }
368 db.add("new Iterable.spliterator()",
369 () -> new IterableWrapper(exp).spliterator());
370
371 //
372
373 db.add("Arrays.asList().spliterator()",
374 () -> Spliterators.spliterator(Arrays.asList(exp.toArray(new Integer[0])), 0));
375
376 db.addList(ArrayList::new);
377
378 db.addList(LinkedList::new);
379
380 db.addList(Vector::new);
381
382
383 db.addCollection(HashSet::new);
384
385 db.addCollection(LinkedHashSet::new);
386
387 db.addCollection(TreeSet::new);
388
389
390 db.addCollection(c -> { Stack<Integer> s = new Stack<>(); s.addAll(c); return s;});
391
392 db.addCollection(PriorityQueue::new);
393
394 db.addCollection(ArrayDeque::new);
395
396
397 db.addCollection(ConcurrentSkipListSet::new);
398
399 if (size > 0) {
400 db.addCollection(c -> {
401 ArrayBlockingQueue<Integer> abq = new ArrayBlockingQueue<>(size);
402 abq.addAll(c);
403 return abq;
404 });
405 }
406
407 db.addCollection(PriorityBlockingQueue::new);
408
409 db.addCollection(LinkedBlockingQueue::new);
410
411 db.addCollection(LinkedTransferQueue::new);
412
413 db.addCollection(ConcurrentLinkedQueue::new);
414
415 db.addCollection(LinkedBlockingDeque::new);
416
417 db.addCollection(CopyOnWriteArrayList::new);
418
419 db.addCollection(CopyOnWriteArraySet::new);
420
421 if (size == 0) {
422 db.addCollection(c -> Collections.<Integer>emptySet());
423 db.addList(c -> Collections.<Integer>emptyList());
424 }
425 else if (size == 1) {
426 db.addCollection(c -> Collections.singleton(exp.get(0)));
427 db.addCollection(c -> Collections.singletonList(exp.get(0)));
428 }
429
430 {
431 Integer[] ai = new Integer[size];
432 Arrays.fill(ai, 1);
433 db.add(String.format("Collections.nCopies(%d, 1)", exp.size()),
434 Arrays.asList(ai),
435 () -> Collections.nCopies(exp.size(), 1).spliterator());
436 }
437
438 // Collections.synchronized/unmodifiable/checked wrappers
439 db.addCollection(Collections::unmodifiableCollection);
440 db.addCollection(c -> Collections.unmodifiableSet(new HashSet<>(c)));
441 db.addCollection(c -> Collections.unmodifiableSortedSet(new TreeSet<>(c)));
442 db.addList(c -> Collections.unmodifiableList(new ArrayList<>(c)));
443 db.addMap(Collections::unmodifiableMap);
444 db.addMap(m -> Collections.unmodifiableSortedMap(new TreeMap<>(m)));
445
446 db.addCollection(Collections::synchronizedCollection);
447 db.addCollection(c -> Collections.synchronizedSet(new HashSet<>(c)));
448 db.addCollection(c -> Collections.synchronizedSortedSet(new TreeSet<>(c)));
449 db.addList(c -> Collections.synchronizedList(new ArrayList<>(c)));
450 db.addMap(Collections::synchronizedMap);
451 db.addMap(m -> Collections.synchronizedSortedMap(new TreeMap<>(m)));
452
453 db.addCollection(c -> Collections.checkedCollection(c, Integer.class));
454 db.addCollection(c -> Collections.checkedQueue(new ArrayDeque<>(c), Integer.class));
455 db.addCollection(c -> Collections.checkedSet(new HashSet<>(c), Integer.class));
456 db.addCollection(c -> Collections.checkedSortedSet(new TreeSet<>(c), Integer.class));
457 db.addList(c -> Collections.checkedList(new ArrayList<>(c), Integer.class));
458 db.addMap(c -> Collections.checkedMap(c, Integer.class, Integer.class));
459 db.addMap(m -> Collections.checkedSortedMap(new TreeMap<>(m), Integer.class, Integer.class));
460
461 // Maps
462
463 db.addMap(HashMap::new);
464
465 db.addMap(m -> {
466 // Create a Map ensuring that for large sizes
467 // buckets will contain 2 or more entries
468 HashMap<Integer, Integer> cm = new HashMap<>(1, m.size() + 1);
469 // Don't use putAll which inflates the table by
470 // m.size() * loadFactor, thus creating a very sparse
471 // map for 1000 entries defeating the purpose of this test,
472 // in addition it will cause the split until null test to fail
473 // because the number of valid splits is larger than the
474 // threshold
475 for (Map.Entry<Integer, Integer> e : m.entrySet())
476 cm.put(e.getKey(), e.getValue());
477 return cm;
478 }, "new java.util.HashMap(1, size + 1)");
479
480 db.addMap(LinkedHashMap::new);
481
482 db.addMap(IdentityHashMap::new);
483
484 db.addMap(WeakHashMap::new);
485
486 db.addMap(m -> {
487 // Create a Map ensuring that for large sizes
488 // buckets will be consist of 2 or more entries
489 WeakHashMap<Integer, Integer> cm = new WeakHashMap<>(1, m.size() + 1);
490 for (Map.Entry<Integer, Integer> e : m.entrySet())
491 cm.put(e.getKey(), e.getValue());
492 return cm;
493 }, "new java.util.WeakHashMap(1, size + 1)");
494
495 // @@@ Descending maps etc
496 db.addMap(TreeMap::new);
497
498 db.addMap(ConcurrentHashMap::new);
499
500 db.addMap(ConcurrentSkipListMap::new);
501
502 if (size == 0) {
503 db.addMap(m -> Collections.<Integer, Integer>emptyMap());
504 }
505 else if (size == 1) {
506 db.addMap(m -> Collections.singletonMap(exp.get(0), exp.get(0)));
507 }
508 }
509
510 return spliteratorDataProvider = data.toArray(new Object[0][]);
511 }
512
513 private static List<Integer> listIntRange(int upTo) {
514 List<Integer> exp = new ArrayList<>();
515 for (int i = 0; i < upTo; i++)
516 exp.add(i);
517 return Collections.unmodifiableList(exp);
518 }
519
520 @Test(dataProvider = "Spliterator<Integer>")
521 @SuppressWarnings({"unchecked", "rawtypes"})
522 public void testNullPointerException(String description, Collection exp, Supplier<Spliterator> s) {
523 executeAndCatch(NullPointerException.class, () -> s.get().forEachRemaining(null));
524 executeAndCatch(NullPointerException.class, () -> s.get().tryAdvance(null));
525 }
526
527 @Test(dataProvider = "Spliterator<Integer>")
528 @SuppressWarnings({"unchecked", "rawtypes"})
529 public void testForEach(String description, Collection exp, Supplier<Spliterator> s) {
530 testForEach(exp, s, (Consumer<Object> b) -> b);
531 }
532
533 @Test(dataProvider = "Spliterator<Integer>")
534 @SuppressWarnings({"unchecked", "rawtypes"})
535 public void testTryAdvance(String description, Collection exp, Supplier<Spliterator> s) {
536 testTryAdvance(exp, s, (Consumer<Object> b) -> b);
537 }
538
539 @Test(dataProvider = "Spliterator<Integer>")
540 @SuppressWarnings({"unchecked", "rawtypes"})
541 public void testMixedTryAdvanceForEach(String description, Collection exp, Supplier<Spliterator> s) {
542 testMixedTryAdvanceForEach(exp, s, (Consumer<Object> b) -> b);
543 }
544
545 @Test(dataProvider = "Spliterator<Integer>")
546 @SuppressWarnings({"unchecked", "rawtypes"})
547 public void testSplitAfterFullTraversal(String description, Collection exp, Supplier<Spliterator> s) {
548 testSplitAfterFullTraversal(s, (Consumer<Object> b) -> b);
549 }
550
551 @Test(dataProvider = "Spliterator<Integer>")
552 @SuppressWarnings({"unchecked", "rawtypes"})
553 public void testSplitOnce(String description, Collection exp, Supplier<Spliterator> s) {
554 testSplitOnce(exp, s, (Consumer<Object> b) -> b);
555 }
556
557 @Test(dataProvider = "Spliterator<Integer>")
558 @SuppressWarnings({"unchecked", "rawtypes"})
559 public void testSplitSixDeep(String description, Collection exp, Supplier<Spliterator> s) {
560 testSplitSixDeep(exp, s, (Consumer<Object> b) -> b);
561 }
562
563 @Test(dataProvider = "Spliterator<Integer>")
564 @SuppressWarnings({"unchecked", "rawtypes"})
565 public void testSplitUntilNull(String description, Collection exp, Supplier<Spliterator> s) {
566 testSplitUntilNull(exp, s, (Consumer<Object> b) -> b);
567 }
568
569 //
570
571 private static class SpliteratorOfIntDataBuilder {
572 List<Object[]> data;
573
574 List<Integer> exp;
575
576 SpliteratorOfIntDataBuilder(List<Object[]> data, List<Integer> exp) {
577 this.data = data;
578 this.exp = exp;
579 }
580
581 void add(String description, List<Integer> expected, Supplier<Spliterator.OfInt> s) {
582 description = joiner(description).toString();
583 data.add(new Object[]{description, expected, s});
584 }
585
586 void add(String description, Supplier<Spliterator.OfInt> s) {
587 add(description, exp, s);
588 }
589
590 StringBuilder joiner(String description) {
591 return new StringBuilder(description).
592 append(" {").
593 append("size=").append(exp.size()).
594 append("}");
595 }
596 }
597
598 private static class SpliteratorOfIntCharDataBuilder {
599 List<Object[]> data;
600
601 String s;
602
603 List<Integer> expChars;
604
605 List<Integer> expCodePoints;
606
607 SpliteratorOfIntCharDataBuilder(List<Object[]> data, String s) {
608 this.data = data;
609 this.s = s;
610 this.expChars = transform(s, false);
611 this.expCodePoints = transform(s, true);
612 }
613
614 static List<Integer> transform(String s, boolean toCodePoints) {
615 List<Integer> l = new ArrayList<>();
616
617 if (!toCodePoints) {
618 for (int i = 0; i < s.length(); i++) {
619 l.add((int) s.charAt(i));
620 }
621 }
622 else {
623 for (int i = 0; i < s.length();) {
624 char c1 = s.charAt(i++);
625 int cp = c1;
626 if (Character.isHighSurrogate(c1) && i < s.length()) {
627 char c2 = s.charAt(i);
628 if (Character.isLowSurrogate(c2)) {
629 i++;
630 cp = Character.toCodePoint(c1, c2);
631 }
632 }
633 l.add(cp);
634 }
635 }
636 return l;
637 }
638
639 void add(String description, Function<String, CharSequence> f) {
640 description = description.replace("%s", s);
641 {
642 Supplier<Spliterator.OfInt> supplier = () -> f.apply(s).chars().spliterator();
643 data.add(new Object[]{description + ".chars().spliterator()", expChars, supplier});
644 }
645 {
646 Supplier<Spliterator.OfInt> supplier = () -> f.apply(s).codePoints().spliterator();
647 data.add(new Object[]{description + ".codePoints().spliterator()", expCodePoints, supplier});
648 }
649 }
650 }
651
652 static Object[][] spliteratorOfIntDataProvider;
653
654 @DataProvider(name = "Spliterator.OfInt")
655 public static Object[][] spliteratorOfIntDataProvider() {
656 if (spliteratorOfIntDataProvider != null) {
657 return spliteratorOfIntDataProvider;
658 }
659
660 List<Object[]> data = new ArrayList<>();
661 for (int size : SIZES) {
662 int exp[] = arrayIntRange(size);
663 SpliteratorOfIntDataBuilder db = new SpliteratorOfIntDataBuilder(data, listIntRange(size));
664
665 db.add("Spliterators.spliterator(int[], ...)",
666 () -> Spliterators.spliterator(exp, 0));
667
668 db.add("Arrays.spliterator(int[], ...)",
669 () -> Arrays.spliterator(exp));
670
671 db.add("Spliterators.spliterator(PrimitiveIterator.OfInt, ...)",
672 () -> Spliterators.spliterator(Spliterators.iterator(Arrays.spliterator(exp)), exp.length, 0));
673
674 db.add("Spliterators.spliteratorUnknownSize(PrimitiveIterator.OfInt, ...)",
675 () -> Spliterators.spliteratorUnknownSize(Spliterators.iterator(Arrays.spliterator(exp)), 0));
676
677 class IntSpliteratorFromArray extends Spliterators.AbstractIntSpliterator {
678 int[] a;
679 int index = 0;
680
681 IntSpliteratorFromArray(int[] a) {
682 super(a.length, Spliterator.SIZED);
683 this.a = a;
684 }
685
686 @Override
687 public boolean tryAdvance(IntConsumer action) {
688 if (action == null)
689 throw new NullPointerException();
690 if (index < a.length) {
691 action.accept(a[index++]);
692 return true;
693 }
694 else {
695 return false;
696 }
697 }
698 }
699 db.add("new Spliterators.AbstractIntAdvancingSpliterator()",
700 () -> new IntSpliteratorFromArray(exp));
701 }
702
703 // Class for testing default methods
704 class CharSequenceImpl implements CharSequence {
705 final String s;
706
707 public CharSequenceImpl(String s) {
708 this.s = s;
709 }
710
711 @Override
712 public int length() {
713 return s.length();
714 }
715
716 @Override
717 public char charAt(int index) {
718 return s.charAt(index);
719 }
720
721 @Override
722 public CharSequence subSequence(int start, int end) {
723 return s.subSequence(start, end);
724 }
725
726 @Override
727 public String toString() {
728 return s;
729 }
730 }
731
732 for (String string : STRINGS) {
733 SpliteratorOfIntCharDataBuilder cdb = new SpliteratorOfIntCharDataBuilder(data, string);
734 cdb.add("\"%s\"", s -> s);
735 cdb.add("new CharSequenceImpl(\"%s\")", CharSequenceImpl::new);
736 cdb.add("new StringBuilder(\"%s\")", StringBuilder::new);
737 cdb.add("new StringBuffer(\"%s\")", StringBuffer::new);
738 }
739
740 return spliteratorOfIntDataProvider = data.toArray(new Object[0][]);
741 }
742
743 private static int[] arrayIntRange(int upTo) {
744 int[] exp = new int[upTo];
745 for (int i = 0; i < upTo; i++)
746 exp[i] = i;
747 return exp;
748 }
749
750 private static UnaryOperator<Consumer<Integer>> intBoxingConsumer() {
751 class BoxingAdapter implements Consumer<Integer>, IntConsumer {
752 private final Consumer<Integer> b;
753
754 BoxingAdapter(Consumer<Integer> b) {
755 this.b = b;
756 }
757
758 @Override
759 public void accept(Integer value) {
760 throw new IllegalStateException();
761 }
762
763 @Override
764 public void accept(int value) {
765 b.accept(value);
766 }
767 }
768
769 return b -> new BoxingAdapter(b);
770 }
771
772 @Test(dataProvider = "Spliterator.OfInt")
773 public void testIntNullPointerException(String description, Collection<Integer> exp, Supplier<Spliterator.OfInt> s) {
774 executeAndCatch(NullPointerException.class, () -> s.get().forEachRemaining((IntConsumer) null));
775 executeAndCatch(NullPointerException.class, () -> s.get().tryAdvance((IntConsumer) null));
776 }
777
778 @Test(dataProvider = "Spliterator.OfInt")
779 public void testIntForEach(String description, Collection<Integer> exp, Supplier<Spliterator.OfInt> s) {
780 testForEach(exp, s, intBoxingConsumer());
781 }
782
783 @Test(dataProvider = "Spliterator.OfInt")
784 public void testIntTryAdvance(String description, Collection<Integer> exp, Supplier<Spliterator.OfInt> s) {
785 testTryAdvance(exp, s, intBoxingConsumer());
786 }
787
788 @Test(dataProvider = "Spliterator.OfInt")
789 public void testIntMixedTryAdvanceForEach(String description, Collection<Integer> exp, Supplier<Spliterator.OfInt> s) {
790 testMixedTryAdvanceForEach(exp, s, intBoxingConsumer());
791 }
792
793 @Test(dataProvider = "Spliterator.OfInt")
794 public void testIntSplitAfterFullTraversal(String description, Collection<Integer> exp, Supplier<Spliterator.OfInt> s) {
795 testSplitAfterFullTraversal(s, intBoxingConsumer());
796 }
797
798 @Test(dataProvider = "Spliterator.OfInt")
799 public void testIntSplitOnce(String description, Collection<Integer> exp, Supplier<Spliterator.OfInt> s) {
800 testSplitOnce(exp, s, intBoxingConsumer());
801 }
802
803 @Test(dataProvider = "Spliterator.OfInt")
804 public void testIntSplitSixDeep(String description, Collection<Integer> exp, Supplier<Spliterator.OfInt> s) {
805 testSplitSixDeep(exp, s, intBoxingConsumer());
806 }
807
808 @Test(dataProvider = "Spliterator.OfInt")
809 public void testIntSplitUntilNull(String description, Collection<Integer> exp, Supplier<Spliterator.OfInt> s) {
810 testSplitUntilNull(exp, s, intBoxingConsumer());
811 }
812
813 //
814
815 private static class SpliteratorOfLongDataBuilder {
816 List<Object[]> data;
817
818 List<Long> exp;
819
820 SpliteratorOfLongDataBuilder(List<Object[]> data, List<Long> exp) {
821 this.data = data;
822 this.exp = exp;
823 }
824
825 void add(String description, List<Long> expected, Supplier<Spliterator.OfLong> s) {
826 description = joiner(description).toString();
827 data.add(new Object[]{description, expected, s});
828 }
829
830 void add(String description, Supplier<Spliterator.OfLong> s) {
831 add(description, exp, s);
832 }
833
834 StringBuilder joiner(String description) {
835 return new StringBuilder(description).
836 append(" {").
837 append("size=").append(exp.size()).
838 append("}");
839 }
840 }
841
842 static Object[][] spliteratorOfLongDataProvider;
843
844 @DataProvider(name = "Spliterator.OfLong")
845 public static Object[][] spliteratorOfLongDataProvider() {
846 if (spliteratorOfLongDataProvider != null) {
847 return spliteratorOfLongDataProvider;
848 }
849
850 List<Object[]> data = new ArrayList<>();
851 for (int size : SIZES) {
852 long exp[] = arrayLongRange(size);
853 SpliteratorOfLongDataBuilder db = new SpliteratorOfLongDataBuilder(data, listLongRange(size));
854
855 db.add("Spliterators.spliterator(long[], ...)",
856 () -> Spliterators.spliterator(exp, 0));
857
858 db.add("Arrays.spliterator(long[], ...)",
859 () -> Arrays.spliterator(exp));
860
861 db.add("Spliterators.spliterator(PrimitiveIterator.OfLong, ...)",
862 () -> Spliterators.spliterator(Spliterators.iterator(Arrays.spliterator(exp)), exp.length, 0));
863
864 db.add("Spliterators.spliteratorUnknownSize(PrimitiveIterator.OfLong, ...)",
865 () -> Spliterators.spliteratorUnknownSize(Spliterators.iterator(Arrays.spliterator(exp)), 0));
866
867 class LongSpliteratorFromArray extends Spliterators.AbstractLongSpliterator {
868 long[] a;
869 int index = 0;
870
871 LongSpliteratorFromArray(long[] a) {
872 super(a.length, Spliterator.SIZED);
873 this.a = a;
874 }
875
876 @Override
877 public boolean tryAdvance(LongConsumer action) {
878 if (action == null)
879 throw new NullPointerException();
880 if (index < a.length) {
881 action.accept(a[index++]);
882 return true;
883 }
884 else {
885 return false;
886 }
887 }
888 }
889 db.add("new Spliterators.AbstractLongAdvancingSpliterator()",
890 () -> new LongSpliteratorFromArray(exp));
891 }
892
893 return spliteratorOfLongDataProvider = data.toArray(new Object[0][]);
894 }
895
896 private static List<Long> listLongRange(int upTo) {
897 List<Long> exp = new ArrayList<>();
898 for (long i = 0; i < upTo; i++)
899 exp.add(i);
900 return Collections.unmodifiableList(exp);
901 }
902
903 private static long[] arrayLongRange(int upTo) {
904 long[] exp = new long[upTo];
905 for (int i = 0; i < upTo; i++)
906 exp[i] = i;
907 return exp;
908 }
909
910 private static UnaryOperator<Consumer<Long>> longBoxingConsumer() {
911 class BoxingAdapter implements Consumer<Long>, LongConsumer {
912 private final Consumer<Long> b;
913
914 BoxingAdapter(Consumer<Long> b) {
915 this.b = b;
916 }
917
918 @Override
919 public void accept(Long value) {
920 throw new IllegalStateException();
921 }
922
923 @Override
924 public void accept(long value) {
925 b.accept(value);
926 }
927 }
928
929 return b -> new BoxingAdapter(b);
930 }
931
932 @Test(dataProvider = "Spliterator.OfLong")
933 public void testLongNullPointerException(String description, Collection<Long> exp, Supplier<Spliterator.OfLong> s) {
934 executeAndCatch(NullPointerException.class, () -> s.get().forEachRemaining((LongConsumer) null));
935 executeAndCatch(NullPointerException.class, () -> s.get().tryAdvance((LongConsumer) null));
936 }
937
938 @Test(dataProvider = "Spliterator.OfLong")
939 public void testLongForEach(String description, Collection<Long> exp, Supplier<Spliterator.OfLong> s) {
940 testForEach(exp, s, longBoxingConsumer());
941 }
942
943 @Test(dataProvider = "Spliterator.OfLong")
944 public void testLongTryAdvance(String description, Collection<Long> exp, Supplier<Spliterator.OfLong> s) {
945 testTryAdvance(exp, s, longBoxingConsumer());
946 }
947
948 @Test(dataProvider = "Spliterator.OfLong")
949 public void testLongMixedTryAdvanceForEach(String description, Collection<Long> exp, Supplier<Spliterator.OfLong> s) {
950 testMixedTryAdvanceForEach(exp, s, longBoxingConsumer());
951 }
952
953 @Test(dataProvider = "Spliterator.OfLong")
954 public void testLongSplitAfterFullTraversal(String description, Collection<Long> exp, Supplier<Spliterator.OfLong> s) {
955 testSplitAfterFullTraversal(s, longBoxingConsumer());
956 }
957
958 @Test(dataProvider = "Spliterator.OfLong")
959 public void testLongSplitOnce(String description, Collection<Long> exp, Supplier<Spliterator.OfLong> s) {
960 testSplitOnce(exp, s, longBoxingConsumer());
961 }
962
963 @Test(dataProvider = "Spliterator.OfLong")
964 public void testLongSplitSixDeep(String description, Collection<Long> exp, Supplier<Spliterator.OfLong> s) {
965 testSplitSixDeep(exp, s, longBoxingConsumer());
966 }
967
968 @Test(dataProvider = "Spliterator.OfLong")
969 public void testLongSplitUntilNull(String description, Collection<Long> exp, Supplier<Spliterator.OfLong> s) {
970 testSplitUntilNull(exp, s, longBoxingConsumer());
971 }
972
973 //
974
975 private static class SpliteratorOfDoubleDataBuilder {
976 List<Object[]> data;
977
978 List<Double> exp;
979
980 SpliteratorOfDoubleDataBuilder(List<Object[]> data, List<Double> exp) {
981 this.data = data;
982 this.exp = exp;
983 }
984
985 void add(String description, List<Double> expected, Supplier<Spliterator.OfDouble> s) {
986 description = joiner(description).toString();
987 data.add(new Object[]{description, expected, s});
988 }
989
990 void add(String description, Supplier<Spliterator.OfDouble> s) {
991 add(description, exp, s);
992 }
993
994 StringBuilder joiner(String description) {
995 return new StringBuilder(description).
996 append(" {").
997 append("size=").append(exp.size()).
998 append("}");
999 }
1000 }
1001
1002 static Object[][] spliteratorOfDoubleDataProvider;
1003
1004 @DataProvider(name = "Spliterator.OfDouble")
1005 public static Object[][] spliteratorOfDoubleDataProvider() {
1006 if (spliteratorOfDoubleDataProvider != null) {
1007 return spliteratorOfDoubleDataProvider;
1008 }
1009
1010 List<Object[]> data = new ArrayList<>();
1011 for (int size : SIZES) {
1012 double exp[] = arrayDoubleRange(size);
1013 SpliteratorOfDoubleDataBuilder db = new SpliteratorOfDoubleDataBuilder(data, listDoubleRange(size));
1014
1015 db.add("Spliterators.spliterator(double[], ...)",
1016 () -> Spliterators.spliterator(exp, 0));
1017
1018 db.add("Arrays.spliterator(double[], ...)",
1019 () -> Arrays.spliterator(exp));
1020
1021 db.add("Spliterators.spliterator(PrimitiveIterator.OfDouble, ...)",
1022 () -> Spliterators.spliterator(Spliterators.iterator(Arrays.spliterator(exp)), exp.length, 0));
1023
1024 db.add("Spliterators.spliteratorUnknownSize(PrimitiveIterator.OfDouble, ...)",
1025 () -> Spliterators.spliteratorUnknownSize(Spliterators.iterator(Arrays.spliterator(exp)), 0));
1026
1027 class DoubleSpliteratorFromArray extends Spliterators.AbstractDoubleSpliterator {
1028 double[] a;
1029 int index = 0;
1030
1031 DoubleSpliteratorFromArray(double[] a) {
1032 super(a.length, Spliterator.SIZED);
1033 this.a = a;
1034 }
1035
1036 @Override
1037 public boolean tryAdvance(DoubleConsumer action) {
1038 if (action == null)
1039 throw new NullPointerException();
1040 if (index < a.length) {
1041 action.accept(a[index++]);
1042 return true;
1043 }
1044 else {
1045 return false;
1046 }
1047 }
1048 }
1049 db.add("new Spliterators.AbstractDoubleAdvancingSpliterator()",
1050 () -> new DoubleSpliteratorFromArray(exp));
1051 }
1052
1053 return spliteratorOfDoubleDataProvider = data.toArray(new Object[0][]);
1054 }
1055
1056 private static List<Double> listDoubleRange(int upTo) {
1057 List<Double> exp = new ArrayList<>();
1058 for (double i = 0; i < upTo; i++)
1059 exp.add(i);
1060 return Collections.unmodifiableList(exp);
1061 }
1062
1063 private static double[] arrayDoubleRange(int upTo) {
1064 double[] exp = new double[upTo];
1065 for (int i = 0; i < upTo; i++)
1066 exp[i] = i;
1067 return exp;
1068 }
1069
1070 private static UnaryOperator<Consumer<Double>> doubleBoxingConsumer() {
1071 class BoxingAdapter implements Consumer<Double>, DoubleConsumer {
1072 private final Consumer<Double> b;
1073
1074 BoxingAdapter(Consumer<Double> b) {
1075 this.b = b;
1076 }
1077
1078 @Override
1079 public void accept(Double value) {
1080 throw new IllegalStateException();
1081 }
1082
1083 @Override
1084 public void accept(double value) {
1085 b.accept(value);
1086 }
1087 }
1088
1089 return b -> new BoxingAdapter(b);
1090 }
1091
1092 @Test(dataProvider = "Spliterator.OfDouble")
1093 public void testDoubleNullPointerException(String description, Collection<Double> exp, Supplier<Spliterator.OfDouble> s) {
1094 executeAndCatch(NullPointerException.class, () -> s.get().forEachRemaining((DoubleConsumer) null));
1095 executeAndCatch(NullPointerException.class, () -> s.get().tryAdvance((DoubleConsumer) null));
1096 }
1097
1098 @Test(dataProvider = "Spliterator.OfDouble")
1099 public void testDoubleForEach(String description, Collection<Double> exp, Supplier<Spliterator.OfDouble> s) {
1100 testForEach(exp, s, doubleBoxingConsumer());
1101 }
1102
1103 @Test(dataProvider = "Spliterator.OfDouble")
1104 public void testDoubleTryAdvance(String description, Collection<Double> exp, Supplier<Spliterator.OfDouble> s) {
1105 testTryAdvance(exp, s, doubleBoxingConsumer());
1106 }
1107
1108 @Test(dataProvider = "Spliterator.OfDouble")
1109 public void testDoubleMixedTryAdvanceForEach(String description, Collection<Double> exp, Supplier<Spliterator.OfDouble> s) {
1110 testMixedTryAdvanceForEach(exp, s, doubleBoxingConsumer());
1111 }
1112
1113 @Test(dataProvider = "Spliterator.OfDouble")
1114 public void testDoubleSplitAfterFullTraversal(String description, Collection<Double> exp, Supplier<Spliterator.OfDouble> s) {
1115 testSplitAfterFullTraversal(s, doubleBoxingConsumer());
1116 }
1117
1118 @Test(dataProvider = "Spliterator.OfDouble")
1119 public void testDoubleSplitOnce(String description, Collection<Double> exp, Supplier<Spliterator.OfDouble> s) {
1120 testSplitOnce(exp, s, doubleBoxingConsumer());
1121 }
1122
1123 @Test(dataProvider = "Spliterator.OfDouble")
1124 public void testDoubleSplitSixDeep(String description, Collection<Double> exp, Supplier<Spliterator.OfDouble> s) {
1125 testSplitSixDeep(exp, s, doubleBoxingConsumer());
1126 }
1127
1128 @Test(dataProvider = "Spliterator.OfDouble")
1129 public void testDoubleSplitUntilNull(String description, Collection<Double> exp, Supplier<Spliterator.OfDouble> s) {
1130 testSplitUntilNull(exp, s, doubleBoxingConsumer());
1131 }
1132
1133 //
1134
1135 private static <T, S extends Spliterator<T>> void testForEach(
1136 Collection<T> exp,
1137 Supplier<S> supplier,
1138 UnaryOperator<Consumer<T>> boxingAdapter) {
1139 S spliterator = supplier.get();
1140 long sizeIfKnown = spliterator.getExactSizeIfKnown();
1141 boolean isOrdered = spliterator.hasCharacteristics(Spliterator.ORDERED);
1142
1143 ArrayList<T> fromForEach = new ArrayList<>();
1144 spliterator = supplier.get();
1145 Consumer<T> addToFromForEach = boxingAdapter.apply(fromForEach::add);
1146 spliterator.forEachRemaining(addToFromForEach);
1147
1148 // Assert that forEach now produces no elements
1149 spliterator.forEachRemaining(boxingAdapter.apply(e -> fail("Spliterator.forEach produced an element after spliterator exhausted: " + e)));
1150 // Assert that tryAdvance now produce no elements
1151 spliterator.tryAdvance(boxingAdapter.apply(e -> fail("Spliterator.tryAdvance produced an element after spliterator exhausted: " + e)));
1152
1153 // assert that size, tryAdvance, and forEach are consistent
1154 if (sizeIfKnown >= 0) {
1155 assertEquals(sizeIfKnown, exp.size());
1156 }
1157 assertEquals(fromForEach.size(), exp.size());
1158
1159 assertContents(fromForEach, exp, isOrdered);
1160 }
1161
1162 private static <T, S extends Spliterator<T>> void testTryAdvance(
1163 Collection<T> exp,
1164 Supplier<S> supplier,
1165 UnaryOperator<Consumer<T>> boxingAdapter) {
1166 S spliterator = supplier.get();
1167 long sizeIfKnown = spliterator.getExactSizeIfKnown();
1168 boolean isOrdered = spliterator.hasCharacteristics(Spliterator.ORDERED);
1169
1170 spliterator = supplier.get();
1171 ArrayList<T> fromTryAdvance = new ArrayList<>();
1172 Consumer<T> addToFromTryAdvance = boxingAdapter.apply(fromTryAdvance::add);
1173 while (spliterator.tryAdvance(addToFromTryAdvance)) { }
1174
1175 // Assert that forEach now produces no elements
1176 spliterator.forEachRemaining(boxingAdapter.apply(e -> fail("Spliterator.forEach produced an element after spliterator exhausted: " + e)));
1177 // Assert that tryAdvance now produce no elements
1178 spliterator.tryAdvance(boxingAdapter.apply(e -> fail("Spliterator.tryAdvance produced an element after spliterator exhausted: " + e)));
1179
1180 // assert that size, tryAdvance, and forEach are consistent
1181 if (sizeIfKnown >= 0) {
1182 assertEquals(sizeIfKnown, exp.size());
1183 }
1184 assertEquals(fromTryAdvance.size(), exp.size());
1185
1186 assertContents(fromTryAdvance, exp, isOrdered);
1187 }
1188
1189 private static <T, S extends Spliterator<T>> void testMixedTryAdvanceForEach(
1190 Collection<T> exp,
1191 Supplier<S> supplier,
1192 UnaryOperator<Consumer<T>> boxingAdapter) {
1193 S spliterator = supplier.get();
1194 long sizeIfKnown = spliterator.getExactSizeIfKnown();
1195 boolean isOrdered = spliterator.hasCharacteristics(Spliterator.ORDERED);
1196
1197 // tryAdvance first few elements, then forEach rest
1198 ArrayList<T> dest = new ArrayList<>();
1199 spliterator = supplier.get();
1200 Consumer<T> addToDest = boxingAdapter.apply(dest::add);
1201 for (int i = 0; i < 10 && spliterator.tryAdvance(addToDest); i++) { }
1202 spliterator.forEachRemaining(addToDest);
1203
1204 // Assert that forEach now produces no elements
1205 spliterator.forEachRemaining(boxingAdapter.apply(e -> fail("Spliterator.forEach produced an element after spliterator exhausted: " + e)));
1206 // Assert that tryAdvance now produce no elements
1207 spliterator.tryAdvance(boxingAdapter.apply(e -> fail("Spliterator.tryAdvance produced an element after spliterator exhausted: " + e)));
1208
1209 if (sizeIfKnown >= 0) {
1210 assertEquals(sizeIfKnown, dest.size());
1211 }
1212 assertEquals(dest.size(), exp.size());
1213
1214 if (isOrdered) {
1215 assertEquals(dest, exp);
1216 }
1217 else {
1218 assertContentsUnordered(dest, exp);
1219 }
1220 }
1221
1222 private static <T, S extends Spliterator<T>> void testSplitAfterFullTraversal(
1223 Supplier<S> supplier,
1224 UnaryOperator<Consumer<T>> boxingAdapter) {
1225 // Full traversal using tryAdvance
1226 Spliterator<T> spliterator = supplier.get();
1227 while (spliterator.tryAdvance(boxingAdapter.apply(e -> { }))) { }
1228 Spliterator<T> split = spliterator.trySplit();
1229 assertNull(split);
1230
1231 // Full traversal using forEach
1232 spliterator = supplier.get();
1233 spliterator.forEachRemaining(boxingAdapter.apply(e -> {
1234 }));
1235 split = spliterator.trySplit();
1236 assertNull(split);
1237
1238 // Full traversal using tryAdvance then forEach
1239 spliterator = supplier.get();
1240 spliterator.tryAdvance(boxingAdapter.apply(e -> { }));
1241 spliterator.forEachRemaining(boxingAdapter.apply(e -> {
1242 }));
1243 split = spliterator.trySplit();
1244 assertNull(split);
1245 }
1246
1247 private static <T, S extends Spliterator<T>> void testSplitOnce(
1248 Collection<T> exp,
1249 Supplier<S> supplier,
1250 UnaryOperator<Consumer<T>> boxingAdapter) {
1251 S spliterator = supplier.get();
1252 long sizeIfKnown = spliterator.getExactSizeIfKnown();
1253 boolean isOrdered = spliterator.hasCharacteristics(Spliterator.ORDERED);
1254
1255 ArrayList<T> fromSplit = new ArrayList<>();
1256 Spliterator<T> s1 = supplier.get();
1257 Spliterator<T> s2 = s1.trySplit();
1258 long s1Size = s1.getExactSizeIfKnown();
1259 long s2Size = (s2 != null) ? s2.getExactSizeIfKnown() : 0;
1260 Consumer<T> addToFromSplit = boxingAdapter.apply(fromSplit::add);
1261 if (s2 != null)
1262 s2.forEachRemaining(addToFromSplit);
1263 s1.forEachRemaining(addToFromSplit);
1264
1265 if (sizeIfKnown >= 0) {
1266 assertEquals(sizeIfKnown, fromSplit.size());
1267 if (s1Size >= 0 && s2Size >= 0)
1268 assertEquals(sizeIfKnown, s1Size + s2Size);
1269 }
1270 assertContents(fromSplit, exp, isOrdered);
1271 }
1272
1273 private static <T, S extends Spliterator<T>> void testSplitSixDeep(
1274 Collection<T> exp,
1275 Supplier<S> supplier,
1276 UnaryOperator<Consumer<T>> boxingAdapter) {
1277 S spliterator = supplier.get();
1278 boolean isOrdered = spliterator.hasCharacteristics(Spliterator.ORDERED);
1279
1280 for (int depth=0; depth < 6; depth++) {
1281 List<T> dest = new ArrayList<>();
1282 spliterator = supplier.get();
1283
1284 assertRootSpliterator(spliterator);
1285
1286 // verify splitting with forEach
1287 visit(depth, 0, dest, spliterator, boxingAdapter, spliterator.characteristics(), false);
1288 assertContents(dest, exp, isOrdered);
1289
1290 // verify splitting with tryAdvance
1291 dest.clear();
1292 spliterator = supplier.get();
1293 visit(depth, 0, dest, spliterator, boxingAdapter, spliterator.characteristics(), true);
1294 assertContents(dest, exp, isOrdered);
1295 }
1296 }
1297
1298 private static <T, S extends Spliterator<T>> void visit(int depth, int curLevel,
1299 List<T> dest, S spliterator, UnaryOperator<Consumer<T>> boxingAdapter,
1300 int rootCharacteristics, boolean useTryAdvance) {
1301 if (curLevel < depth) {
1302 long beforeSize = spliterator.getExactSizeIfKnown();
1303 Spliterator<T> split = spliterator.trySplit();
1304 if (split != null) {
1305 assertSpliterator(split, rootCharacteristics);
1306 assertSpliterator(spliterator, rootCharacteristics);
1307
1308 if ((rootCharacteristics & Spliterator.SUBSIZED) != 0 &&
1309 (rootCharacteristics & Spliterator.SIZED) != 0) {
1310 assertEquals(beforeSize, split.estimateSize() + spliterator.estimateSize());
1311 }
1312 visit(depth, curLevel + 1, dest, split, boxingAdapter, rootCharacteristics, useTryAdvance);
1313 }
1314 visit(depth, curLevel + 1, dest, spliterator, boxingAdapter, rootCharacteristics, useTryAdvance);
1315 }
1316 else {
1317 long sizeIfKnown = spliterator.getExactSizeIfKnown();
1318 if (useTryAdvance) {
1319 Consumer<T> addToDest = boxingAdapter.apply(dest::add);
1320 int count = 0;
1321 while (spliterator.tryAdvance(addToDest)) {
1322 ++count;
1323 }
1324
1325 if (sizeIfKnown >= 0)
1326 assertEquals(sizeIfKnown, count);
1327
1328 // Assert that forEach now produces no elements
1329 spliterator.forEachRemaining(boxingAdapter.apply(e -> fail("Spliterator.forEach produced an element after spliterator exhausted: " + e)));
1330
1331 Spliterator<T> split = spliterator.trySplit();
1332 assertNull(split);
1333 }
1334 else {
1335 List<T> leafDest = new ArrayList<>();
1336 Consumer<T> addToLeafDest = boxingAdapter.apply(leafDest::add);
1337 spliterator.forEachRemaining(addToLeafDest);
1338
1339 if (sizeIfKnown >= 0)
1340 assertEquals(sizeIfKnown, leafDest.size());
1341
1342 // Assert that forEach now produces no elements
1343 spliterator.tryAdvance(boxingAdapter.apply(e -> fail("Spliterator.tryAdvance produced an element after spliterator exhausted: " + e)));
1344
1345 Spliterator<T> split = spliterator.trySplit();
1346 assertNull(split);
1347
1348 dest.addAll(leafDest);
1349 }
1350 }
1351 }
1352
1353 private static <T, S extends Spliterator<T>> void testSplitUntilNull(
1354 Collection<T> exp,
1355 Supplier<S> supplier,
1356 UnaryOperator<Consumer<T>> boxingAdapter) {
1357 Spliterator<T> s = supplier.get();
1358 boolean isOrdered = s.hasCharacteristics(Spliterator.ORDERED);
1359 assertRootSpliterator(s);
1360
1361 List<T> splits = new ArrayList<>();
1362 Consumer<T> c = boxingAdapter.apply(splits::add);
1363
1364 testSplitUntilNull(new SplitNode<T>(c, s));
1365 assertContents(splits, exp, isOrdered);
1366 }
1367
1368 private static class SplitNode<T> {
1369 // Constant for every node
1370 final Consumer<T> c;
1371 final int rootCharacteristics;
1372
1373 final Spliterator<T> s;
1374
1375 SplitNode(Consumer<T> c, Spliterator<T> s) {
1376 this(c, s.characteristics(), s);
1377 }
1378
1379 private SplitNode(Consumer<T> c, int rootCharacteristics, Spliterator<T> s) {
1380 this.c = c;
1381 this.rootCharacteristics = rootCharacteristics;
1382 this.s = s;
1383 }
1384
1385 SplitNode<T> fromSplit(Spliterator<T> split) {
1386 return new SplitNode<>(c, rootCharacteristics, split);
1387 }
1388 }
1389
1390 /**
1391 * Set the maximum stack capacity to 0.25MB. This should be more than enough to detect a bad spliterator
1392 * while not unduly disrupting test infrastructure given the test data sizes that are used are small.
1393 * Note that j.u.c.ForkJoinPool sets the max queue size to 64M (1 << 26).
1394 */
1395 private static final int MAXIMUM_STACK_CAPACITY = 1 << 18; // 0.25MB
1396
1397 private static <T> void testSplitUntilNull(SplitNode<T> e) {
1398 // Use an explicit stack to avoid a StackOverflowException when testing a Spliterator
1399 // that when repeatedly split produces a right-balanced (and maybe degenerate) tree, or
1400 // for a spliterator that is badly behaved.
1401 Deque<SplitNode<T>> stack = new ArrayDeque<>();
1402 stack.push(e);
1403
1404 int iteration = 0;
1405 while (!stack.isEmpty()) {
1406 assertTrue(iteration++ < MAXIMUM_STACK_CAPACITY, "Exceeded maximum stack modification count of 1 << 18");
1407
1408 e = stack.pop();
1409 Spliterator<T> parentAndRightSplit = e.s;
1410
1411 long parentEstimateSize = parentAndRightSplit.estimateSize();
1412 assertTrue(parentEstimateSize >= 0,
1413 String.format("Split size estimate %d < 0", parentEstimateSize));
1414
1415 long parentSize = parentAndRightSplit.getExactSizeIfKnown();
1416 Spliterator<T> leftSplit = parentAndRightSplit.trySplit();
1417 if (leftSplit == null) {
1418 parentAndRightSplit.forEachRemaining(e.c);
1419 continue;
1420 }
1421
1422 assertSpliterator(leftSplit, e.rootCharacteristics);
1423 assertSpliterator(parentAndRightSplit, e.rootCharacteristics);
1424
1425 if (parentEstimateSize != Long.MAX_VALUE && leftSplit.estimateSize() > 0 && parentAndRightSplit.estimateSize() > 0) {
1426 assertTrue(leftSplit.estimateSize() < parentEstimateSize,
1427 String.format("Left split size estimate %d >= parent split size estimate %d", leftSplit.estimateSize(), parentEstimateSize));
1428 assertTrue(parentAndRightSplit.estimateSize() < parentEstimateSize,
1429 String.format("Right split size estimate %d >= parent split size estimate %d", leftSplit.estimateSize(), parentEstimateSize));
1430 }
1431 else {
1432 assertTrue(leftSplit.estimateSize() <= parentEstimateSize,
1433 String.format("Left split size estimate %d > parent split size estimate %d", leftSplit.estimateSize(), parentEstimateSize));
1434 assertTrue(parentAndRightSplit.estimateSize() <= parentEstimateSize,
1435 String.format("Right split size estimate %d > parent split size estimate %d", leftSplit.estimateSize(), parentEstimateSize));
1436 }
1437
1438 long leftSize = leftSplit.getExactSizeIfKnown();
1439 long rightSize = parentAndRightSplit.getExactSizeIfKnown();
1440 if (parentSize >= 0 && leftSize >= 0 && rightSize >= 0)
1441 assertEquals(parentSize, leftSize + rightSize,
1442 String.format("exact left split size %d + exact right split size %d != parent exact split size %d",
1443 leftSize, rightSize, parentSize));
1444
1445 // Add right side to stack first so left side is popped off first
1446 stack.push(e.fromSplit(parentAndRightSplit));
1447 stack.push(e.fromSplit(leftSplit));
1448 }
1449 }
1450
1451 private static void assertRootSpliterator(Spliterator<?> s) {
1452 assertFalse(s.hasCharacteristics(Spliterator.SIZED | Spliterator.CONCURRENT),
1453 "Root spliterator should not be SIZED and CONCURRENT");
1454
1455 assertSpliterator(s);
1456 }
1457
1458 private static void assertSpliterator(Spliterator<?> s, int rootCharacteristics) {
1459 if ((rootCharacteristics & Spliterator.SUBSIZED) != 0) {
1460 assertTrue(s.hasCharacteristics(Spliterator.SUBSIZED),
1461 "Child split is not SUBSIZED when root split is SUBSIZED");
1462 }
1463 assertSpliterator(s);
1464 }
1465
1466 private static void assertSpliterator(Spliterator<?> s) {
1467 if (s.hasCharacteristics(Spliterator.SUBSIZED)) {
1468 assertTrue(s.hasCharacteristics(Spliterator.SIZED));
1469 }
1470 if (s.hasCharacteristics(Spliterator.SIZED)) {
1471 assertTrue(s.estimateSize() != Long.MAX_VALUE);
1472 assertTrue(s.getExactSizeIfKnown() >= 0);
1473 }
1474 try {
1475 s.getComparator();
1476 assertTrue(s.hasCharacteristics(Spliterator.SORTED));
1477 } catch (IllegalStateException e) {
1478 assertFalse(s.hasCharacteristics(Spliterator.SORTED));
1479 }
1480 }
1481
1482 private static<T> void assertContents(Collection<T> actual, Collection<T> expected, boolean isOrdered) {
1483 if (isOrdered) {
1484 assertEquals(actual, expected);
1485 }
1486 else {
1487 assertContentsUnordered(actual, expected);
1488 }
1489 }
1490
1491 private static<T> void assertContentsUnordered(Iterable<T> actual, Iterable<T> expected) {
1492 assertEquals(toBoxedMultiset(actual), toBoxedMultiset(expected));
1493 }
1494
1495 private static <T> Map<T, Integer> toBoxedMultiset(Iterable<T> c) {
1496 Map<T, Integer> result = new HashMap<>();
1497 c.forEach(e -> {
1498 if (result.containsKey(e)) result.put(e, result.get(e) + 1);
1499 else result.put(e, 1);
1500 });
1501 return result;
1502 }
1503
1504 private void executeAndCatch(Class<? extends Exception> expected, Runnable r) {
1505 Exception caught = null;
1506 try {
1507 r.run();
1508 }
1509 catch (Exception e) {
1510 caught = e;
1511 }
1512
1513 assertNotNull(caught,
1514 String.format("No Exception was thrown, expected an Exception of %s to be thrown",
1515 expected.getName()));
1516 assertTrue(expected.isInstance(caught),
1517 String.format("Exception thrown %s not an instance of %s",
1518 caught.getClass().getName(), expected.getName()));
1519 }
1520
1521 }