• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
1 /*
2  * Copyright (C) 2008 The Guava Authors
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 
17 package com.google.common.collect;
18 
19 import static com.google.common.base.Strings.isNullOrEmpty;
20 import static com.google.common.collect.Iterables.concat;
21 import static com.google.common.collect.Lists.newArrayList;
22 import static com.google.common.collect.Lists.newLinkedList;
23 import static com.google.common.truth.Truth.assertThat;
24 import static java.util.Collections.nCopies;
25 
26 import com.google.common.annotations.GwtCompatible;
27 import com.google.common.annotations.GwtIncompatible;
28 import com.google.common.annotations.J2ktIncompatible;
29 import com.google.common.base.Predicate;
30 import com.google.common.collect.testing.CollectionTestSuiteBuilder;
31 import com.google.common.collect.testing.TestStringCollectionGenerator;
32 import com.google.common.collect.testing.features.CollectionFeature;
33 import com.google.common.collect.testing.features.CollectionSize;
34 import com.google.common.testing.NullPointerTester;
35 import java.util.Collection;
36 import java.util.Collections;
37 import java.util.Iterator;
38 import java.util.List;
39 import java.util.NoSuchElementException;
40 import junit.framework.Test;
41 import junit.framework.TestCase;
42 import junit.framework.TestSuite;
43 import org.checkerframework.checker.nullness.qual.Nullable;
44 
45 /**
46  * Tests for {@link Collections2}.
47  *
48  * @author Chris Povirk
49  * @author Jared Levy
50  */
51 @GwtCompatible(emulated = true)
52 @ElementTypesAreNonnullByDefault
53 public class Collections2Test extends TestCase {
54   @J2ktIncompatible
55   @GwtIncompatible // suite
suite()56   public static Test suite() {
57     TestSuite suite = new TestSuite(Collections2Test.class.getSimpleName());
58     suite.addTest(testsForFilter());
59     suite.addTest(testsForFilterAll());
60     suite.addTest(testsForFilterLinkedList());
61     suite.addTest(testsForFilterNoNulls());
62     suite.addTest(testsForFilterFiltered());
63     suite.addTest(testsForTransform());
64     suite.addTestSuite(Collections2Test.class);
65     return suite;
66   }
67 
68   static final Predicate<@Nullable String> NOT_YYY_ZZZ =
69       input -> !"yyy".equals(input) && !"zzz".equals(input);
70 
71   static final Predicate<String> LENGTH_1 = input -> input.length() == 1;
72 
73   @J2ktIncompatible
74   @GwtIncompatible // suite
testsForFilter()75   private static Test testsForFilter() {
76     return CollectionTestSuiteBuilder.using(
77             new TestStringCollectionGenerator() {
78               @Override
79               public Collection<String> create(String[] elements) {
80                 List<String> unfiltered = newArrayList();
81                 unfiltered.add("yyy");
82                 Collections.addAll(unfiltered, elements);
83                 unfiltered.add("zzz");
84                 return Collections2.filter(unfiltered, NOT_YYY_ZZZ);
85               }
86             })
87         .named("Collections2.filter")
88         .withFeatures(
89             CollectionFeature.SUPPORTS_ADD,
90             CollectionFeature.SUPPORTS_REMOVE,
91             CollectionFeature.ALLOWS_NULL_VALUES,
92             CollectionFeature.KNOWN_ORDER,
93             CollectionSize.ANY)
94         .createTestSuite();
95   }
96 
97   @J2ktIncompatible
98   @GwtIncompatible // suite
99   private static Test testsForFilterAll() {
100     return CollectionTestSuiteBuilder.using(
101             new TestStringCollectionGenerator() {
102               @Override
103               public Collection<String> create(String[] elements) {
104                 List<String> unfiltered = newArrayList();
105                 Collections.addAll(unfiltered, elements);
106                 return Collections2.filter(unfiltered, NOT_YYY_ZZZ);
107               }
108             })
109         .named("Collections2.filter")
110         .withFeatures(
111             CollectionFeature.SUPPORTS_ADD,
112             CollectionFeature.SUPPORTS_REMOVE,
113             CollectionFeature.ALLOWS_NULL_VALUES,
114             CollectionFeature.KNOWN_ORDER,
115             CollectionSize.ANY)
116         .createTestSuite();
117   }
118 
119   @J2ktIncompatible
120   @GwtIncompatible // suite
121   private static Test testsForFilterLinkedList() {
122     return CollectionTestSuiteBuilder.using(
123             new TestStringCollectionGenerator() {
124               @Override
125               public Collection<String> create(String[] elements) {
126                 List<String> unfiltered = newLinkedList();
127                 unfiltered.add("yyy");
128                 Collections.addAll(unfiltered, elements);
129                 unfiltered.add("zzz");
130                 return Collections2.filter(unfiltered, NOT_YYY_ZZZ);
131               }
132             })
133         .named("Collections2.filter")
134         .withFeatures(
135             CollectionFeature.SUPPORTS_ADD,
136             CollectionFeature.SUPPORTS_REMOVE,
137             CollectionFeature.ALLOWS_NULL_VALUES,
138             CollectionFeature.KNOWN_ORDER,
139             CollectionSize.ANY)
140         .createTestSuite();
141   }
142 
143   @J2ktIncompatible
144   @GwtIncompatible // suite
145   private static Test testsForFilterNoNulls() {
146     return CollectionTestSuiteBuilder.using(
147             new TestStringCollectionGenerator() {
148               @Override
149               public Collection<String> create(String[] elements) {
150                 List<String> unfiltered = newArrayList();
151                 unfiltered.add("yyy");
152                 unfiltered.addAll(ImmutableList.copyOf(elements));
153                 unfiltered.add("zzz");
154                 return Collections2.filter(unfiltered, LENGTH_1);
155               }
156             })
157         .named("Collections2.filter, no nulls")
158         .withFeatures(
159             CollectionFeature.SUPPORTS_ADD,
160             CollectionFeature.SUPPORTS_REMOVE,
161             CollectionFeature.ALLOWS_NULL_QUERIES,
162             CollectionFeature.KNOWN_ORDER,
163             CollectionSize.ANY)
164         .createTestSuite();
165   }
166 
167   @J2ktIncompatible
168   @GwtIncompatible // suite
169   private static Test testsForFilterFiltered() {
170     return CollectionTestSuiteBuilder.using(
171             new TestStringCollectionGenerator() {
172               @Override
173               public Collection<String> create(String[] elements) {
174                 List<String> unfiltered = newArrayList();
175                 unfiltered.add("yyy");
176                 unfiltered.addAll(ImmutableList.copyOf(elements));
177                 unfiltered.add("zzz");
178                 unfiltered.add("abc");
179                 return Collections2.filter(Collections2.filter(unfiltered, LENGTH_1), NOT_YYY_ZZZ);
180               }
181             })
182         .named("Collections2.filter, filtered input")
183         .withFeatures(
184             CollectionFeature.SUPPORTS_ADD,
185             CollectionFeature.SUPPORTS_REMOVE,
186             CollectionFeature.KNOWN_ORDER,
187             CollectionFeature.ALLOWS_NULL_QUERIES,
188             CollectionSize.ANY)
189         .createTestSuite();
190   }
191 
192   @J2ktIncompatible
193   @GwtIncompatible // suite
194   private static Test testsForTransform() {
195     return CollectionTestSuiteBuilder.using(
196             new TestStringCollectionGenerator() {
197               @Override
198               public Collection<@Nullable String> create(@Nullable String[] elements) {
199                 List<@Nullable String> list = newArrayList();
200                 for (String element : elements) {
201                   list.add((element == null) ? null : "q" + element);
202                 }
203                 return Collections2.transform(
204                     list, from -> isNullOrEmpty(from) ? null : from.substring(1));
205               }
206             })
207         .named("Collections2.transform")
208         .withFeatures(
209             CollectionFeature.REMOVE_OPERATIONS,
210             CollectionFeature.ALLOWS_NULL_VALUES,
211             CollectionFeature.KNOWN_ORDER,
212             CollectionSize.ANY)
213         .createTestSuite();
214   }
215 
216   @J2ktIncompatible
217   @GwtIncompatible // NullPointerTester
218   public void testNullPointerExceptions() {
219     NullPointerTester tester = new NullPointerTester();
220     tester.testAllPublicStaticMethods(Collections2.class);
221   }
222 
223   public void testOrderedPermutationSetEmpty() {
224     List<Integer> list = newArrayList();
225     Collection<List<Integer>> permutationSet = Collections2.orderedPermutations(list);
226 
227     assertEquals(1, permutationSet.size());
228     assertThat(permutationSet).contains(list);
229 
230     Iterator<List<Integer>> permutations = permutationSet.iterator();
231 
232     assertNextPermutation(Lists.<Integer>newArrayList(), permutations);
233     assertNoMorePermutations(permutations);
234   }
235 
236   public void testOrderedPermutationSetOneElement() {
237     List<Integer> list = newArrayList(1);
238     Iterator<List<Integer>> permutations = Collections2.orderedPermutations(list).iterator();
239 
240     assertNextPermutation(newArrayList(1), permutations);
241     assertNoMorePermutations(permutations);
242   }
243 
244   public void testOrderedPermutationSetThreeElements() {
245     List<String> list = newArrayList("b", "a", "c");
246     Iterator<List<String>> permutations = Collections2.orderedPermutations(list).iterator();
247 
248     assertNextPermutation(newArrayList("a", "b", "c"), permutations);
249     assertNextPermutation(newArrayList("a", "c", "b"), permutations);
250     assertNextPermutation(newArrayList("b", "a", "c"), permutations);
251     assertNextPermutation(newArrayList("b", "c", "a"), permutations);
252     assertNextPermutation(newArrayList("c", "a", "b"), permutations);
253     assertNextPermutation(newArrayList("c", "b", "a"), permutations);
254     assertNoMorePermutations(permutations);
255   }
256 
257   public void testOrderedPermutationSetRepeatedElements() {
258     List<Integer> list = newArrayList(1, 1, 2, 2);
259     Iterator<List<Integer>> permutations =
260         Collections2.orderedPermutations(list, Ordering.natural()).iterator();
261 
262     assertNextPermutation(newArrayList(1, 1, 2, 2), permutations);
263     assertNextPermutation(newArrayList(1, 2, 1, 2), permutations);
264     assertNextPermutation(newArrayList(1, 2, 2, 1), permutations);
265     assertNextPermutation(newArrayList(2, 1, 1, 2), permutations);
266     assertNextPermutation(newArrayList(2, 1, 2, 1), permutations);
267     assertNextPermutation(newArrayList(2, 2, 1, 1), permutations);
268     assertNoMorePermutations(permutations);
269   }
270 
271   public void testOrderedPermutationSetRepeatedElementsSize() {
272     List<Integer> list = newArrayList(1, 1, 1, 1, 2, 2, 3);
273     Collection<List<Integer>> permutations =
274         Collections2.orderedPermutations(list, Ordering.natural());
275 
276     assertPermutationsCount(105, permutations);
277   }
278 
279   public void testOrderedPermutationSetSizeOverflow() {
280     // 12 elements won't overflow
281     assertEquals(
282         479001600 /*12!*/,
283         Collections2.orderedPermutations(newArrayList(1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12))
284             .size());
285     // 13 elements overflow an int
286     assertEquals(
287         Integer.MAX_VALUE,
288         Collections2.orderedPermutations(newArrayList(1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13))
289             .size());
290     // 21 elements overflow a long
291     assertEquals(
292         Integer.MAX_VALUE,
293         Collections2.orderedPermutations(
294                 newArrayList(
295                     1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21))
296             .size());
297 
298     // Almost force an overflow in the binomial coefficient calculation
299     assertEquals(
300         1391975640 /*C(34,14)*/,
301         Collections2.orderedPermutations(concat(nCopies(20, 1), nCopies(14, 2))).size());
302     // Do force an overflow in the binomial coefficient calculation
303     assertEquals(
304         Integer.MAX_VALUE,
305         Collections2.orderedPermutations(concat(nCopies(21, 1), nCopies(14, 2))).size());
306   }
307 
308   public void testOrderedPermutationSetContains() {
309     List<Integer> list = newArrayList(3, 2, 1);
310     Collection<List<Integer>> permutationSet = Collections2.orderedPermutations(list);
311 
312     assertTrue(permutationSet.contains(newArrayList(1, 2, 3)));
313     assertTrue(permutationSet.contains(newArrayList(2, 3, 1)));
314     assertFalse(permutationSet.contains(newArrayList(1, 2)));
315     assertFalse(permutationSet.contains(newArrayList(1, 1, 2, 3)));
316     assertFalse(permutationSet.contains(newArrayList(1, 2, 3, 4)));
317     assertFalse(permutationSet.contains(null));
318   }
319 
320   public void testPermutationSetEmpty() {
321     Collection<List<Integer>> permutationSet =
322         Collections2.permutations(Collections.<Integer>emptyList());
323 
324     assertEquals(1, permutationSet.size());
325     assertTrue(permutationSet.contains(Collections.<Integer>emptyList()));
326 
327     Iterator<List<Integer>> permutations = permutationSet.iterator();
328     assertNextPermutation(Collections.<Integer>emptyList(), permutations);
329     assertNoMorePermutations(permutations);
330   }
331 
332   public void testPermutationSetOneElement() {
333     Iterator<List<Integer>> permutations =
334         Collections2.permutations(Collections.<Integer>singletonList(1)).iterator();
335     assertNextPermutation(newArrayList(1), permutations);
336     assertNoMorePermutations(permutations);
337   }
338 
339   public void testPermutationSetTwoElements() {
340     Iterator<List<Integer>> permutations = Collections2.permutations(newArrayList(1, 2)).iterator();
341     assertNextPermutation(newArrayList(1, 2), permutations);
342     assertNextPermutation(newArrayList(2, 1), permutations);
343     assertNoMorePermutations(permutations);
344   }
345 
346   public void testPermutationSetThreeElements() {
347     Iterator<List<Integer>> permutations =
348         Collections2.permutations(newArrayList(1, 2, 3)).iterator();
349     assertNextPermutation(newArrayList(1, 2, 3), permutations);
350     assertNextPermutation(newArrayList(1, 3, 2), permutations);
351     assertNextPermutation(newArrayList(3, 1, 2), permutations);
352 
353     assertNextPermutation(newArrayList(3, 2, 1), permutations);
354     assertNextPermutation(newArrayList(2, 3, 1), permutations);
355     assertNextPermutation(newArrayList(2, 1, 3), permutations);
356     assertNoMorePermutations(permutations);
357   }
358 
359   public void testPermutationSetThreeElementsOutOfOrder() {
360     Iterator<List<Integer>> permutations =
361         Collections2.permutations(newArrayList(3, 2, 1)).iterator();
362     assertNextPermutation(newArrayList(3, 2, 1), permutations);
363     assertNextPermutation(newArrayList(3, 1, 2), permutations);
364     assertNextPermutation(newArrayList(1, 3, 2), permutations);
365 
366     assertNextPermutation(newArrayList(1, 2, 3), permutations);
367     assertNextPermutation(newArrayList(2, 1, 3), permutations);
368     assertNextPermutation(newArrayList(2, 3, 1), permutations);
369     assertNoMorePermutations(permutations);
370   }
371 
372   public void testPermutationSetThreeRepeatedElements() {
373     Iterator<List<Integer>> permutations =
374         Collections2.permutations(newArrayList(1, 1, 2)).iterator();
375     assertNextPermutation(newArrayList(1, 1, 2), permutations);
376     assertNextPermutation(newArrayList(1, 2, 1), permutations);
377     assertNextPermutation(newArrayList(2, 1, 1), permutations);
378     assertNextPermutation(newArrayList(2, 1, 1), permutations);
379     assertNextPermutation(newArrayList(1, 2, 1), permutations);
380     assertNextPermutation(newArrayList(1, 1, 2), permutations);
381     assertNoMorePermutations(permutations);
382   }
383 
384   public void testPermutationSetFourElements() {
385     Iterator<List<Integer>> permutations =
386         Collections2.permutations(newArrayList(1, 2, 3, 4)).iterator();
387     assertNextPermutation(newArrayList(1, 2, 3, 4), permutations);
388     assertNextPermutation(newArrayList(1, 2, 4, 3), permutations);
389     assertNextPermutation(newArrayList(1, 4, 2, 3), permutations);
390     assertNextPermutation(newArrayList(4, 1, 2, 3), permutations);
391 
392     assertNextPermutation(newArrayList(4, 1, 3, 2), permutations);
393     assertNextPermutation(newArrayList(1, 4, 3, 2), permutations);
394     assertNextPermutation(newArrayList(1, 3, 4, 2), permutations);
395     assertNextPermutation(newArrayList(1, 3, 2, 4), permutations);
396 
397     assertNextPermutation(newArrayList(3, 1, 2, 4), permutations);
398     assertNextPermutation(newArrayList(3, 1, 4, 2), permutations);
399     assertNextPermutation(newArrayList(3, 4, 1, 2), permutations);
400     assertNextPermutation(newArrayList(4, 3, 1, 2), permutations);
401 
402     assertNextPermutation(newArrayList(4, 3, 2, 1), permutations);
403     assertNextPermutation(newArrayList(3, 4, 2, 1), permutations);
404     assertNextPermutation(newArrayList(3, 2, 4, 1), permutations);
405     assertNextPermutation(newArrayList(3, 2, 1, 4), permutations);
406 
407     assertNextPermutation(newArrayList(2, 3, 1, 4), permutations);
408     assertNextPermutation(newArrayList(2, 3, 4, 1), permutations);
409     assertNextPermutation(newArrayList(2, 4, 3, 1), permutations);
410     assertNextPermutation(newArrayList(4, 2, 3, 1), permutations);
411 
412     assertNextPermutation(newArrayList(4, 2, 1, 3), permutations);
413     assertNextPermutation(newArrayList(2, 4, 1, 3), permutations);
414     assertNextPermutation(newArrayList(2, 1, 4, 3), permutations);
415     assertNextPermutation(newArrayList(2, 1, 3, 4), permutations);
416     assertNoMorePermutations(permutations);
417   }
418 
419   public void testPermutationSetSize() {
420     assertPermutationsCount(1, Collections2.permutations(Collections.<Integer>emptyList()));
421     assertPermutationsCount(1, Collections2.permutations(newArrayList(1)));
422     assertPermutationsCount(2, Collections2.permutations(newArrayList(1, 2)));
423     assertPermutationsCount(6, Collections2.permutations(newArrayList(1, 2, 3)));
424     assertPermutationsCount(5040, Collections2.permutations(newArrayList(1, 2, 3, 4, 5, 6, 7)));
425     assertPermutationsCount(40320, Collections2.permutations(newArrayList(1, 2, 3, 4, 5, 6, 7, 8)));
426   }
427 
428   public void testPermutationSetSizeOverflow() {
429     // 13 elements overflow an int
430     assertEquals(
431         Integer.MAX_VALUE,
432         Collections2.permutations(newArrayList(1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13)).size());
433     // 21 elements overflow a long
434     assertEquals(
435         Integer.MAX_VALUE,
436         Collections2.orderedPermutations(
437                 newArrayList(1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20))
438             .size());
439     assertEquals(
440         Integer.MAX_VALUE,
441         Collections2.orderedPermutations(
442                 newArrayList(
443                     1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21))
444             .size());
445   }
446 
447   public void testPermutationSetContains() {
448     List<Integer> list = newArrayList(3, 2, 1);
449     Collection<List<Integer>> permutationSet = Collections2.permutations(list);
450 
451     assertTrue(permutationSet.contains(newArrayList(1, 2, 3)));
452     assertTrue(permutationSet.contains(newArrayList(2, 3, 1)));
453     assertFalse(permutationSet.contains(newArrayList(1, 2)));
454     assertFalse(permutationSet.contains(newArrayList(1, 1, 2, 3)));
455     assertFalse(permutationSet.contains(newArrayList(1, 2, 3, 4)));
456     assertFalse(permutationSet.contains(null));
457   }
458 
459   private <T> void assertNextPermutation(
460       List<T> expectedPermutation, Iterator<List<T>> permutations) {
461     assertTrue("Expected another permutation, but there was none.", permutations.hasNext());
462     assertEquals(expectedPermutation, permutations.next());
463   }
464 
465   private <T> void assertNoMorePermutations(Iterator<List<T>> permutations) {
466     assertFalse("Expected no more permutations, but there was one.", permutations.hasNext());
467     try {
468       permutations.next();
469       fail("Expected NoSuchElementException.");
470     } catch (NoSuchElementException expected) {
471     }
472   }
473 
474   private <T> void assertPermutationsCount(int expected, Collection<List<T>> permutationSet) {
475     assertEquals(expected, permutationSet.size());
476     Iterator<List<T>> permutations = permutationSet.iterator();
477     for (int i = 0; i < expected; i++) {
478       assertTrue(permutations.hasNext());
479       permutations.next();
480     }
481     assertNoMorePermutations(permutations);
482   }
483 
484   public void testToStringImplWithNullEntries() throws Exception {
485     List<@Nullable String> list = Lists.newArrayList();
486     list.add("foo");
487     list.add(null);
488 
489     assertEquals(list.toString(), Collections2.toStringImpl(list));
490   }
491 }
492