1
2
3
4
5
6
7
8
9
10
11
12
13
14
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
48
49
50
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
295 assertEquals(479001600 , Collections2.orderedPermutations(
296 newArrayList(1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12)).size());
297
298 assertEquals(Integer.MAX_VALUE, Collections2.orderedPermutations(
299 newArrayList(1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13)).size());
300
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
306 assertEquals(1391975640 , Collections2.orderedPermutations(
307 concat(nCopies(20, 1), nCopies(14, 2))).size());
308
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
442 assertEquals(Integer.MAX_VALUE, Collections2.permutations(newArrayList(
443 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13)).size());
444
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 }