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 java.util.Arrays.asList;
22 import static java.util.Collections.nCopies;
23 import static org.truth0.Truth.ASSERT;
24 
25 import com.google.common.annotations.GwtCompatible;
26 import com.google.common.base.Function;
27 import com.google.common.base.Predicate;
28 
29 import junit.framework.TestCase;
30 
31 import java.util.Collection;
32 import java.util.Collections;
33 import java.util.Iterator;
34 import java.util.List;
35 import java.util.NoSuchElementException;
36 
37 /**
38  * Tests for {@link Collections2}.
39  *
40  * @author Chris Povirk
41  * @author Jared Levy
42  */
43 @GwtCompatible(emulated = true)
44 public class Collections2Test extends TestCase {
45 
46   static final Predicate<String> NOT_YYY_ZZZ = new Predicate<String>() {
47       @Override
48       public boolean apply(String input) {
49         return !"yyy".equals(input) && !"zzz".equals(input);
50       }
51   };
52 
53   static final Predicate<String> LENGTH_1 = new Predicate<String>() {
54     @Override
55     public boolean apply(String input) {
56       return input.length() == 1;
57     }
58   };
59 
60   static final Predicate<String> STARTS_WITH_VOWEL = new Predicate<String>() {
61     @Override
62     public boolean apply(String input) {
63       return asList('a', 'e', 'i', 'o', 'u').contains(input.charAt(0));
64     }
65   };
66 
67   private static final Function<String, String> REMOVE_FIRST_CHAR
68       = new Function<String, String>() {
69         @Override
70         public String apply(String from) {
71           return ((from == null) || "".equals(from))
72               ? null : from.substring(1);
73         }
74       };
75 
testOrderedPermutationSetEmpty()76   public void testOrderedPermutationSetEmpty() {
77     List<Integer> list = newArrayList();
78     Collection<List<Integer>> permutationSet =
79         Collections2.orderedPermutations(list);
80 
81     assertEquals(1, permutationSet.size());
82     ASSERT.that(permutationSet).has().item(list);
83 
84     Iterator<List<Integer>> permutations = permutationSet.iterator();
85 
86     assertNextPermutation(Lists.<Integer>newArrayList(), permutations);
87     assertNoMorePermutations(permutations);
88   }
89 
testOrderedPermutationSetOneElement()90   public void testOrderedPermutationSetOneElement() {
91     List<Integer> list = newArrayList(1);
92     Iterator<List<Integer>> permutations =
93         Collections2.orderedPermutations(list).iterator();
94 
95     assertNextPermutation(newArrayList(1), permutations);
96     assertNoMorePermutations(permutations);
97   }
98 
testOrderedPermutationSetThreeElements()99   public void testOrderedPermutationSetThreeElements() {
100     List<String> list = newArrayList("b", "a", "c");
101     Iterator<List<String>> permutations =
102         Collections2.orderedPermutations(list).iterator();
103 
104     assertNextPermutation(newArrayList("a", "b", "c"), permutations);
105     assertNextPermutation(newArrayList("a", "c", "b"), permutations);
106     assertNextPermutation(newArrayList("b", "a", "c"), permutations);
107     assertNextPermutation(newArrayList("b", "c", "a"), permutations);
108     assertNextPermutation(newArrayList("c", "a", "b"), permutations);
109     assertNextPermutation(newArrayList("c", "b", "a"), permutations);
110     assertNoMorePermutations(permutations);
111   }
112 
testOrderedPermutationSetRepeatedElements()113   public void testOrderedPermutationSetRepeatedElements() {
114     List<Integer> list = newArrayList(1, 1, 2, 2);
115     Iterator<List<Integer>> permutations =
116         Collections2.orderedPermutations(list, Ordering.natural()).iterator();
117 
118     assertNextPermutation(newArrayList(1, 1, 2, 2), permutations);
119     assertNextPermutation(newArrayList(1, 2, 1, 2), permutations);
120     assertNextPermutation(newArrayList(1, 2, 2, 1), permutations);
121     assertNextPermutation(newArrayList(2, 1, 1, 2), permutations);
122     assertNextPermutation(newArrayList(2, 1, 2, 1), permutations);
123     assertNextPermutation(newArrayList(2, 2, 1, 1), permutations);
124     assertNoMorePermutations(permutations);
125   }
126 
testOrderedPermutationSetRepeatedElementsSize()127   public void testOrderedPermutationSetRepeatedElementsSize() {
128     List<Integer> list = newArrayList(1, 1, 1, 1, 2, 2, 3);
129     Collection<List<Integer>> permutations =
130         Collections2.orderedPermutations(list, Ordering.natural());
131 
132     assertPermutationsCount(105, permutations);
133   }
134 
testOrderedPermutationSetSizeOverflow()135   public void testOrderedPermutationSetSizeOverflow() {
136     // 12 elements won't overflow
137     assertEquals(479001600 /*12!*/, Collections2.orderedPermutations(
138         newArrayList(1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12)).size());
139     // 13 elements overflow an int
140     assertEquals(Integer.MAX_VALUE, Collections2.orderedPermutations(
141         newArrayList(1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13)).size());
142     // 21 elements overflow a long
143     assertEquals(Integer.MAX_VALUE, Collections2.orderedPermutations(
144         newArrayList(1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15,
145             16, 17, 18, 19, 20, 21)).size());
146 
147     // Almost force an overflow in the binomial coefficient calculation
148     assertEquals(1391975640 /*C(34,14)*/, Collections2.orderedPermutations(
149         concat(nCopies(20, 1), nCopies(14, 2))).size());
150     // Do force an overflow in the binomial coefficient calculation
151     assertEquals(Integer.MAX_VALUE, Collections2.orderedPermutations(
152         concat(nCopies(21, 1), nCopies(14, 2))).size());
153   }
154 
testOrderedPermutationSetContains()155   public void testOrderedPermutationSetContains() {
156     List<Integer> list = newArrayList(3, 2, 1);
157     Collection<List<Integer>> permutationSet =
158         Collections2.orderedPermutations(list);
159 
160     assertTrue(permutationSet.contains(newArrayList(1, 2, 3)));
161     assertTrue(permutationSet.contains(newArrayList(2, 3, 1)));
162     assertFalse(permutationSet.contains(newArrayList(1, 2)));
163     assertFalse(permutationSet.contains(newArrayList(1, 1, 2, 3)));
164     assertFalse(permutationSet.contains(newArrayList(1, 2, 3, 4)));
165     assertFalse(permutationSet.contains(null));
166   }
167 
testPermutationSetEmpty()168   public void testPermutationSetEmpty() {
169     Collection<List<Integer>> permutationSet =
170         Collections2.permutations(Collections.<Integer>emptyList());
171 
172     assertEquals(1, permutationSet.size());
173     assertTrue(permutationSet.contains(Collections.<Integer> emptyList()));
174 
175     Iterator<List<Integer>> permutations = permutationSet.iterator();
176     assertNextPermutation(Collections.<Integer> emptyList(), permutations);
177     assertNoMorePermutations(permutations);
178   }
179 
testPermutationSetOneElement()180   public void testPermutationSetOneElement() {
181     Iterator<List<Integer>> permutations =
182         Collections2.permutations(Collections.<Integer> singletonList(1))
183         .iterator();
184     assertNextPermutation(newArrayList(1), permutations);
185     assertNoMorePermutations(permutations);
186   }
187 
testPermutationSetTwoElements()188   public void testPermutationSetTwoElements() {
189     Iterator<List<Integer>> permutations = Collections2.permutations(
190         newArrayList(1, 2)).iterator();
191     assertNextPermutation(newArrayList(1, 2), permutations);
192     assertNextPermutation(newArrayList(2, 1), permutations);
193     assertNoMorePermutations(permutations);
194   }
195 
testPermutationSetThreeElements()196   public void testPermutationSetThreeElements() {
197     Iterator<List<Integer>> permutations = Collections2.permutations(
198         newArrayList(1, 2, 3)).iterator();
199     assertNextPermutation(newArrayList(1, 2, 3), permutations);
200     assertNextPermutation(newArrayList(1, 3, 2), permutations);
201     assertNextPermutation(newArrayList(3, 1, 2), permutations);
202 
203     assertNextPermutation(newArrayList(3, 2, 1), permutations);
204     assertNextPermutation(newArrayList(2, 3, 1), permutations);
205     assertNextPermutation(newArrayList(2, 1, 3), permutations);
206     assertNoMorePermutations(permutations);
207   }
208 
testPermutationSetThreeElementsOutOfOrder()209   public void testPermutationSetThreeElementsOutOfOrder() {
210     Iterator<List<Integer>> permutations = Collections2.permutations(
211         newArrayList(3, 2, 1)).iterator();
212     assertNextPermutation(newArrayList(3, 2, 1), permutations);
213     assertNextPermutation(newArrayList(3, 1, 2), permutations);
214     assertNextPermutation(newArrayList(1, 3, 2), permutations);
215 
216     assertNextPermutation(newArrayList(1, 2, 3), permutations);
217     assertNextPermutation(newArrayList(2, 1, 3), permutations);
218     assertNextPermutation(newArrayList(2, 3, 1), permutations);
219     assertNoMorePermutations(permutations);
220   }
221 
testPermutationSetThreeRepeatedElements()222   public void testPermutationSetThreeRepeatedElements() {
223     Iterator<List<Integer>> permutations = Collections2.permutations(
224         newArrayList(1, 1, 2)).iterator();
225     assertNextPermutation(newArrayList(1, 1, 2), permutations);
226     assertNextPermutation(newArrayList(1, 2, 1), permutations);
227     assertNextPermutation(newArrayList(2, 1, 1), permutations);
228     assertNextPermutation(newArrayList(2, 1, 1), permutations);
229     assertNextPermutation(newArrayList(1, 2, 1), permutations);
230     assertNextPermutation(newArrayList(1, 1, 2), permutations);
231     assertNoMorePermutations(permutations);
232   }
233 
testPermutationSetFourElements()234   public void testPermutationSetFourElements() {
235     Iterator<List<Integer>> permutations = Collections2.permutations(
236         newArrayList(1, 2, 3, 4)).iterator();
237     assertNextPermutation(newArrayList(1, 2, 3, 4), permutations);
238     assertNextPermutation(newArrayList(1, 2, 4, 3), permutations);
239     assertNextPermutation(newArrayList(1, 4, 2, 3), permutations);
240     assertNextPermutation(newArrayList(4, 1, 2, 3), permutations);
241 
242     assertNextPermutation(newArrayList(4, 1, 3, 2), permutations);
243     assertNextPermutation(newArrayList(1, 4, 3, 2), permutations);
244     assertNextPermutation(newArrayList(1, 3, 4, 2), permutations);
245     assertNextPermutation(newArrayList(1, 3, 2, 4), permutations);
246 
247     assertNextPermutation(newArrayList(3, 1, 2, 4), permutations);
248     assertNextPermutation(newArrayList(3, 1, 4, 2), permutations);
249     assertNextPermutation(newArrayList(3, 4, 1, 2), permutations);
250     assertNextPermutation(newArrayList(4, 3, 1, 2), permutations);
251 
252     assertNextPermutation(newArrayList(4, 3, 2, 1), permutations);
253     assertNextPermutation(newArrayList(3, 4, 2, 1), permutations);
254     assertNextPermutation(newArrayList(3, 2, 4, 1), permutations);
255     assertNextPermutation(newArrayList(3, 2, 1, 4), permutations);
256 
257     assertNextPermutation(newArrayList(2, 3, 1, 4), permutations);
258     assertNextPermutation(newArrayList(2, 3, 4, 1), permutations);
259     assertNextPermutation(newArrayList(2, 4, 3, 1), permutations);
260     assertNextPermutation(newArrayList(4, 2, 3, 1), permutations);
261 
262     assertNextPermutation(newArrayList(4, 2, 1, 3), permutations);
263     assertNextPermutation(newArrayList(2, 4, 1, 3), permutations);
264     assertNextPermutation(newArrayList(2, 1, 4, 3), permutations);
265     assertNextPermutation(newArrayList(2, 1, 3, 4), permutations);
266     assertNoMorePermutations(permutations);
267   }
268 
testPermutationSetSize()269   public void testPermutationSetSize() {
270     assertPermutationsCount(1,
271         Collections2.permutations(Collections.<Integer>emptyList()));
272     assertPermutationsCount(1, Collections2.permutations(newArrayList(1)));
273     assertPermutationsCount(2, Collections2.permutations(newArrayList(1, 2)));
274     assertPermutationsCount(6,
275         Collections2.permutations(newArrayList(1, 2, 3)));
276     assertPermutationsCount(5040,
277         Collections2.permutations(newArrayList(1, 2, 3, 4, 5, 6, 7)));
278     assertPermutationsCount(40320,
279         Collections2.permutations(newArrayList(1, 2, 3, 4, 5, 6, 7, 8)));
280   }
281 
testPermutationSetSizeOverflow()282   public void testPermutationSetSizeOverflow() {
283     // 13 elements overflow an int
284     assertEquals(Integer.MAX_VALUE, Collections2.permutations(newArrayList(
285         1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13)).size());
286     // 21 elements overflow a long
287     assertEquals(Integer.MAX_VALUE, Collections2.orderedPermutations(
288         newArrayList(1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15,
289             16, 17, 18, 19, 20)).size());
290     assertEquals(Integer.MAX_VALUE, Collections2.orderedPermutations(
291         newArrayList(1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15,
292             16, 17, 18, 19, 20, 21)).size());
293   }
294 
testPermutationSetContains()295   public void testPermutationSetContains() {
296     List<Integer> list = newArrayList(3, 2, 1);
297     Collection<List<Integer>> permutationSet =
298         Collections2.permutations(list);
299 
300     assertTrue(permutationSet.contains(newArrayList(1, 2, 3)));
301     assertTrue(permutationSet.contains(newArrayList(2, 3, 1)));
302     assertFalse(permutationSet.contains(newArrayList(1, 2)));
303     assertFalse(permutationSet.contains(newArrayList(1, 1, 2, 3)));
304     assertFalse(permutationSet.contains(newArrayList(1, 2, 3, 4)));
305     assertFalse(permutationSet.contains(null));
306   }
307 
assertNextPermutation(List<T> expectedPermutation, Iterator<List<T>> permutations)308   private <T> void assertNextPermutation(List<T> expectedPermutation,
309       Iterator<List<T>> permutations) {
310     assertTrue("Expected another permutation, but there was none.",
311         permutations.hasNext());
312     assertEquals(expectedPermutation, permutations.next());
313   }
314 
assertNoMorePermutations( Iterator<List<T>> permutations)315   private <T> void assertNoMorePermutations(
316       Iterator<List<T>> permutations) {
317     assertFalse("Expected no more permutations, but there was one.",
318         permutations.hasNext());
319     try {
320       permutations.next();
321       fail("Expected NoSuchElementException.");
322     } catch (NoSuchElementException expected) {}
323   }
324 
assertPermutationsCount(int expected, Collection<List<T>> permutationSet)325   private <T> void assertPermutationsCount(int expected,
326       Collection<List<T>> permutationSet) {
327     assertEquals(expected, permutationSet.size());
328     Iterator<List<T>> permutations = permutationSet.iterator();
329     for (int i = 0; i < expected; i++) {
330       assertTrue(permutations.hasNext());
331       permutations.next();
332     }
333     assertNoMorePermutations(permutations);
334   }
335 
testToStringImplWithNullEntries()336   public void testToStringImplWithNullEntries() throws Exception {
337     List<String> list = Lists.newArrayList();
338     list.add("foo");
339     list.add(null);
340 
341     assertEquals(list.toString(), Collections2.toStringImpl(list));
342   }
343 
344 }
345 
346