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