View Javadoc
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.truth.Truth.assertThat;
22  import static java.util.Arrays.asList;
23  import static java.util.Collections.nCopies;
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  
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      assertThat(permutationSet).has().item(list);
83  
84      Iterator<List<Integer>> permutations = permutationSet.iterator();
85  
86      assertNextPermutation(Lists.<Integer>newArrayList(), permutations);
87      assertNoMorePermutations(permutations);
88    }
89  
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  
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 
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 
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 
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 
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 
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 
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 
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 
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 
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 
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 
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 
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 
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 
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 
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 
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 
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 
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