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