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.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
39
40
41
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
137 assertEquals(479001600 , Collections2.orderedPermutations(
138 newArrayList(1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12)).size());
139
140 assertEquals(Integer.MAX_VALUE, Collections2.orderedPermutations(
141 newArrayList(1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13)).size());
142
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
148 assertEquals(1391975640 , Collections2.orderedPermutations(
149 concat(nCopies(20, 1), nCopies(14, 2))).size());
150
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
284 assertEquals(Integer.MAX_VALUE, Collections2.permutations(newArrayList(
285 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13)).size());
286
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