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