1/*
2 * Copyright (C) 2016 The Android Open Source Project
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 *      http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License
15 */
16
17package libcore.java.util;
18
19
20import java.util.ArrayList;
21import java.util.Collections;
22import java.util.Comparator;
23import java.util.HashSet;
24import java.util.Spliterator;
25import java.util.function.Consumer;
26
27import static junit.framework.Assert.assertEquals;
28import static junit.framework.Assert.assertFalse;
29import static junit.framework.Assert.assertNull;
30import static junit.framework.Assert.assertTrue;
31import static junit.framework.Assert.fail;
32
33public class SpliteratorTester {
34    public static <T> void runBasicIterationTests(Spliterator<T> spliterator,
35            ArrayList<T> expectedElements) {
36        ArrayList<T> recorder = new ArrayList<T>(expectedElements.size());
37        Consumer<T> consumer = (T value) -> recorder.add(value);
38
39        // tryAdvance.
40        assertTrue(spliterator.tryAdvance(consumer));
41        assertEquals(expectedElements.get(0), recorder.get(0));
42
43        // forEachRemaining.
44        spliterator.forEachRemaining(consumer);
45        assertEquals(expectedElements, recorder);
46
47        // There should be no more elements remaining in this spliterator.
48        assertFalse(spliterator.tryAdvance(consumer));
49        spliterator.forEachRemaining((T) -> fail());
50    }
51
52    public static <T> void runBasicIterationTests_unordered(Spliterator<T> spliterator,
53            ArrayList<T> expectedElements, Comparator<T> comparator) {
54        ArrayList<T> recorder = new ArrayList<T>(expectedElements.size());
55        Consumer<T> consumer = (T value) -> recorder.add(value);
56
57        // tryAdvance.
58        assertTrue(spliterator.tryAdvance(consumer));
59        assertTrue(expectedElements.contains(recorder.get(0)));
60
61        // forEachRemaining.
62        spliterator.forEachRemaining(consumer);
63        Collections.sort(expectedElements, comparator);
64        Collections.sort(recorder, comparator);
65        assertEquals(expectedElements, recorder);
66
67        // There should be no more elements remaining in this spliterator.
68        assertFalse(spliterator.tryAdvance(consumer));
69        spliterator.forEachRemaining((T) -> fail());
70    }
71
72    private static <T> void recordAndAssertBasicIteration(
73            Spliterator<T> spliterator, ArrayList<T> recorder) {
74        spliterator.tryAdvance(value -> recorder.add(value));
75        spliterator.forEachRemaining(value -> recorder.add(value));
76
77        // There shouldn't be any elements left in the spliterator.
78        assertFalse(spliterator.tryAdvance(value -> recorder.add(value)));
79        spliterator.tryAdvance(value -> fail());
80
81        // And all subsequent splits should fail.
82        assertNull(spliterator.trySplit());
83    }
84
85    public static void testSpliteratorNPE(Spliterator<?> spliterator) {
86        try {
87            spliterator.tryAdvance(null);
88            fail();
89        } catch (NullPointerException expected) {
90        }
91
92        try {
93            spliterator.forEachRemaining(null);
94            fail();
95        } catch (NullPointerException expected) {
96        }
97    }
98
99    public static <T extends Comparable<T>> void runBasicSplitTests(
100            Iterable<T> spliterable, ArrayList<T> expectedElements) {
101        runBasicSplitTests(spliterable, expectedElements, T::compareTo);
102    }
103
104    public static <T> void runBasicSplitTests(Spliterator<T> spliterator,
105            ArrayList<T> expectedElements, Comparator<T> comparator) {
106        ArrayList<T> recorder = new ArrayList<>();
107
108        // Advance the original spliterator by one element.
109        assertTrue(spliterator.tryAdvance(value -> recorder.add(value)));
110
111        // Try splitting it.
112        Spliterator<T> split1 = spliterator.trySplit();
113        if (split1 != null) {
114            // Try to split the resulting split.
115            Spliterator<T> split1_1 = split1.trySplit();
116            Spliterator<T> split1_2 = split1.trySplit();
117            if (split1_1 != null) {
118                recordAndAssertBasicIteration(split1_1, recorder);
119            }
120            if (split1_2 != null) {
121                recordAndAssertBasicIteration(split1_2, recorder);
122            }
123
124            // Iterate over the remainder of split1.
125            recordAndAssertBasicIteration(split1, recorder);
126        }
127
128        // Try to split the original iterator again.
129        Spliterator<T> split2 = spliterator.trySplit();
130        if (split2 != null) {
131            recordAndAssertBasicIteration(split2, recorder);
132        }
133
134        // Record all remaining elements of the original spliterator.
135        recordAndAssertBasicIteration(spliterator, recorder);
136
137        Collections.sort(expectedElements, comparator);
138        Collections.sort(recorder, comparator);
139        assertEquals(expectedElements, recorder);
140    }
141
142    /**
143     * Note that the contract of trySplit() is generally quite weak (as it must be). There
144     * are no demands about when the spliterator can or cannot split itself. In general, this
145     * test is quite loose. All it does is exercise the basic methods on the splits (if any)
146     * and confirms that the union of all elements in the split is the collection that was
147     * iterated over.
148     */
149    public static <T> void runBasicSplitTests(Iterable<T> spliterable,
150            ArrayList<T> expectedElements, Comparator<T> comparator) {
151        runBasicSplitTests(spliterable.spliterator(), expectedElements, comparator);
152    }
153
154    public static <T> void runOrderedTests(Iterable<T> spliterable) {
155        ArrayList<T> iteration1 = new ArrayList<>();
156        ArrayList<T> iteration2 = new ArrayList<>();
157
158        spliterable.spliterator().forEachRemaining(value -> iteration1.add(value));
159        spliterable.spliterator().forEachRemaining(value -> iteration2.add(value));
160
161        assertEquals(iteration1, iteration2);
162
163        iteration1.clear();
164        iteration2.clear();
165
166        spliterable.spliterator().trySplit().forEachRemaining(value -> iteration1.add(value));
167        spliterable.spliterator().trySplit().forEachRemaining(value -> iteration2.add(value));
168        assertEquals(iteration1, iteration2);
169    }
170
171    public static <T> void runSizedTests(Spliterator<T> spliterator, int expectedSize) {
172        assertEquals(expectedSize, spliterator.estimateSize());
173        assertEquals(expectedSize, spliterator.getExactSizeIfKnown());
174    }
175
176    public static <T> void runSizedTests(Iterable<T> spliterable, int expectedSize) {
177        runSizedTests(spliterable.spliterator(), expectedSize);
178    }
179
180    public static <T> void runSubSizedTests(Spliterator<T> spliterator, int expectedSize) {
181        assertEquals(expectedSize, spliterator.estimateSize());
182        assertEquals(expectedSize, spliterator.getExactSizeIfKnown());
183
184
185        Spliterator<T> split1 = spliterator.trySplit();
186        assertEquals(expectedSize, spliterator.estimateSize() + split1.estimateSize());
187        assertEquals(expectedSize, spliterator.getExactSizeIfKnown() + split1.getExactSizeIfKnown());
188    }
189
190    public static <T> void runSubSizedTests(Iterable<T> spliterable, int expectedSize) {
191        runSubSizedTests(spliterable.spliterator(), expectedSize);
192    }
193
194    public static <T> void runDistinctTests(Iterable<T> spliterable) {
195        HashSet<T> distinct = new HashSet<>();
196        ArrayList<T> allElements = new ArrayList<>();
197
198        Spliterator<T> spliterator = spliterable.spliterator();
199        Spliterator<T> split1 = spliterator.trySplit();
200
201        // First test that iterating via the spliterator using forEachRemaining
202        // yields distinct elements.
203        spliterator.forEachRemaining(value -> { distinct.add(value); allElements.add(value); });
204        split1.forEachRemaining(value -> { distinct.add(value); allElements.add(value); });
205        assertEquals(distinct.size(), allElements.size());
206
207        distinct.clear();
208        allElements.clear();
209        spliterator = spliterable.spliterator();
210        split1 = spliterator.trySplit();
211
212        // Then test whether using tryAdvance yields the same results.
213        while (spliterator.tryAdvance(value -> { distinct.add(value); allElements.add(value); })) {
214        }
215
216        while (split1.tryAdvance(value -> { distinct.add(value); allElements.add(value); })) {
217        }
218
219        assertEquals(distinct.size(), allElements.size());
220    }
221
222    public static <T> void runSortedTests(Iterable<T> spliterable, Comparator<T> comparator) {
223        Spliterator<T> spliterator = spliterable.spliterator();
224        Spliterator<T> split1 = spliterator.trySplit();
225
226        ArrayList<T> elements = new ArrayList<>();
227        spliterator.forEachRemaining(value -> elements.add(value));
228
229        ArrayList<T> sortedElements = new ArrayList<>(elements);
230        Collections.sort(sortedElements, comparator);
231        assertEquals(elements, sortedElements);
232
233        elements.clear();
234
235        split1.forEachRemaining(value -> elements.add(value));
236        sortedElements = new ArrayList<>(elements);
237        Collections.sort(sortedElements, comparator);
238        assertEquals(elements, sortedElements);
239    }
240
241    public static <T extends Comparable<T>> void runSortedTests(Iterable<T> spliterable) {
242        runSortedTests(spliterable, T::compareTo);
243    }
244}
245