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