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
