1 /* 2 * Copyright (C) 2007 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.testing.IteratorFeature.UNMODIFIABLE; 20 import static com.google.common.truth.Truth.assertThat; 21 import static java.util.Arrays.asList; 22 import static java.util.Collections.singletonList; 23 24 import com.google.common.annotations.GwtCompatible; 25 import com.google.common.base.Function; 26 import com.google.common.collect.testing.IteratorTester; 27 28 import junit.framework.TestCase; 29 30 import java.io.Serializable; 31 import java.util.ArrayList; 32 import java.util.Collection; 33 import java.util.Collections; 34 import java.util.Iterator; 35 import java.util.LinkedList; 36 import java.util.List; 37 import java.util.ListIterator; 38 import java.util.NoSuchElementException; 39 import java.util.RandomAccess; 40 41 /** 42 * Unit test for {@code Lists}. 43 * 44 * @author Kevin Bourrillion 45 * @author Mike Bostock 46 * @author Jared Levy 47 */ 48 @GwtCompatible(emulated = true) 49 public class ListsTest extends TestCase { 50 51 private static final Collection<Integer> SOME_COLLECTION 52 = asList(0, 1, 1); 53 54 private static final Iterable<Integer> SOME_ITERABLE = new SomeIterable(); 55 56 private static final class RemoveFirstFunction 57 implements Function<String, String>, Serializable { 58 @Override 59 public String apply(String from) { 60 return (from.length() == 0) ? from : from.substring(1); 61 } 62 } 63 64 private static class SomeIterable implements Iterable<Integer>, Serializable { 65 @Override 66 public Iterator<Integer> iterator() { 67 return SOME_COLLECTION.iterator(); 68 } 69 private static final long serialVersionUID = 0; 70 } 71 72 private static final List<Integer> SOME_LIST 73 = Lists.newArrayList(1, 2, 3, 4); 74 75 private static final List<Integer> SOME_SEQUENTIAL_LIST 76 = Lists.newLinkedList(asList(1, 2, 3, 4)); 77 78 private static final List<String> SOME_STRING_LIST 79 = asList("1", "2", "3", "4"); 80 81 private static final Function<Number, String> SOME_FUNCTION 82 = new SomeFunction(); 83 84 private static class SomeFunction 85 implements Function<Number, String>, Serializable { 86 @Override 87 public String apply(Number n) { 88 return String.valueOf(n); 89 } 90 private static final long serialVersionUID = 0; 91 } 92 93 public void testCharactersOfIsView() { 94 StringBuilder builder = new StringBuilder("abc"); 95 List<Character> chars = Lists.charactersOf(builder); 96 assertEquals(asList('a', 'b', 'c'), chars); 97 builder.append("def"); 98 assertEquals( 99 asList('a', 'b', 'c', 'd', 'e', 'f'), chars); 100 builder.deleteCharAt(5); 101 assertEquals( 102 asList('a', 'b', 'c', 'd', 'e'), chars); 103 } 104 105 public void testNewArrayListEmpty() { 106 ArrayList<Integer> list = Lists.newArrayList(); 107 assertEquals(Collections.emptyList(), list); 108 } 109 110 public void testNewArrayListWithCapacity() { 111 ArrayList<Integer> list = Lists.newArrayListWithCapacity(0); 112 assertEquals(Collections.emptyList(), list); 113 114 ArrayList<Integer> bigger = Lists.newArrayListWithCapacity(256); 115 assertEquals(Collections.emptyList(), bigger); 116 } 117 118 public void testNewArrayListWithCapacity_negative() { 119 try { 120 Lists.newArrayListWithCapacity(-1); 121 fail(); 122 } catch (IllegalArgumentException expected) { 123 } 124 } 125 126 public void testNewArrayListWithExpectedSize() { 127 ArrayList<Integer> list = Lists.newArrayListWithExpectedSize(0); 128 assertEquals(Collections.emptyList(), list); 129 130 ArrayList<Integer> bigger = Lists.newArrayListWithExpectedSize(256); 131 assertEquals(Collections.emptyList(), bigger); 132 } 133 134 public void testNewArrayListWithExpectedSize_negative() { 135 try { 136 Lists.newArrayListWithExpectedSize(-1); 137 fail(); 138 } catch (IllegalArgumentException expected) { 139 } 140 } 141 142 public void testNewArrayListVarArgs() { 143 ArrayList<Integer> list = Lists.newArrayList(0, 1, 1); 144 assertEquals(SOME_COLLECTION, list); 145 } 146 147 public void testComputeArrayListCapacity() { 148 assertEquals(5, Lists.computeArrayListCapacity(0)); 149 assertEquals(13, Lists.computeArrayListCapacity(8)); 150 assertEquals(89, Lists.computeArrayListCapacity(77)); 151 assertEquals(22000005, Lists.computeArrayListCapacity(20000000)); 152 assertEquals(Integer.MAX_VALUE, 153 Lists.computeArrayListCapacity(Integer.MAX_VALUE - 1000)); 154 } 155 156 public void testNewArrayListFromCollection() { 157 ArrayList<Integer> list = Lists.newArrayList(SOME_COLLECTION); 158 assertEquals(SOME_COLLECTION, list); 159 } 160 161 public void testNewArrayListFromIterable() { 162 ArrayList<Integer> list = Lists.newArrayList(SOME_ITERABLE); 163 assertEquals(SOME_COLLECTION, list); 164 } 165 166 public void testNewArrayListFromIterator() { 167 ArrayList<Integer> list = Lists.newArrayList(SOME_COLLECTION.iterator()); 168 assertEquals(SOME_COLLECTION, list); 169 } 170 171 public void testNewLinkedListEmpty() { 172 LinkedList<Integer> list = Lists.newLinkedList(); 173 assertEquals(Collections.emptyList(), list); 174 } 175 176 public void testNewLinkedListFromCollection() { 177 LinkedList<Integer> list = Lists.newLinkedList(SOME_COLLECTION); 178 assertEquals(SOME_COLLECTION, list); 179 } 180 181 public void testNewLinkedListFromIterable() { 182 LinkedList<Integer> list = Lists.newLinkedList(SOME_ITERABLE); 183 assertEquals(SOME_COLLECTION, list); 184 } 185 186 /** 187 * This is just here to illustrate how {@code Arrays#asList} differs from 188 * {@code Lists#newArrayList}. 189 */ 190 public void testArraysAsList() { 191 List<String> ourWay = Lists.newArrayList("foo", "bar", "baz"); 192 List<String> otherWay = asList("foo", "bar", "baz"); 193 194 // They're logically equal 195 assertEquals(ourWay, otherWay); 196 197 // The result of Arrays.asList() is mutable 198 otherWay.set(0, "FOO"); 199 assertEquals("FOO", otherWay.get(0)); 200 201 // But it can't grow 202 try { 203 otherWay.add("nope"); 204 fail("no exception thrown"); 205 } catch (UnsupportedOperationException expected) { 206 } 207 208 // And it can't shrink 209 try { 210 otherWay.remove(2); 211 fail("no exception thrown"); 212 } catch (UnsupportedOperationException expected) { 213 } 214 } 215 216 private void checkFooBarBazList(List<String> list) { 217 assertThat(list).has().exactly("foo", "bar", "baz").inOrder(); 218 assertEquals(3, list.size()); 219 assertIndexIsOutOfBounds(list, -1); 220 assertEquals("foo", list.get(0)); 221 assertEquals("bar", list.get(1)); 222 assertEquals("baz", list.get(2)); 223 assertIndexIsOutOfBounds(list, 3); 224 } 225 226 public void testAsList1Small() { 227 List<String> list = Lists.asList("foo", new String[0]); 228 assertThat(list).has().item("foo"); 229 assertEquals(1, list.size()); 230 assertIndexIsOutOfBounds(list, -1); 231 assertEquals("foo", list.get(0)); 232 assertIndexIsOutOfBounds(list, 1); 233 assertTrue(list instanceof RandomAccess); 234 235 new IteratorTester<String>(3, UNMODIFIABLE, singletonList("foo"), 236 IteratorTester.KnownOrder.KNOWN_ORDER) { 237 @Override protected Iterator<String> newTargetIterator() { 238 return Lists.asList("foo", new String[0]).iterator(); 239 } 240 }.test(); 241 } 242 243 public void testAsList2() { 244 List<String> list = Lists.asList("foo", "bar", new String[] { "baz" }); 245 checkFooBarBazList(list); 246 assertTrue(list instanceof RandomAccess); 247 248 new IteratorTester<String>(5, UNMODIFIABLE, asList("foo", "bar", 249 "baz"), IteratorTester.KnownOrder.KNOWN_ORDER) { 250 @Override protected Iterator<String> newTargetIterator() { 251 return Lists.asList("foo", "bar", new String[] {"baz"}).iterator(); 252 } 253 }.test(); 254 } 255 256 private static void assertIndexIsOutOfBounds(List<String> list, int index) { 257 try { 258 list.get(index); 259 fail(); 260 } catch (IndexOutOfBoundsException expected) { 261 } 262 } 263 264 public void testReverseViewRandomAccess() { 265 List<Integer> fromList = Lists.newArrayList(SOME_LIST); 266 List<Integer> toList = Lists.reverse(fromList); 267 assertReverseView(fromList, toList); 268 } 269 270 public void testReverseViewSequential() { 271 List<Integer> fromList = Lists.newLinkedList(SOME_SEQUENTIAL_LIST); 272 List<Integer> toList = Lists.reverse(fromList); 273 assertReverseView(fromList, toList); 274 } 275 276 private static void assertReverseView(List<Integer> fromList, 277 List<Integer> toList) { 278 /* fromList modifications reflected in toList */ 279 fromList.set(0, 5); 280 assertEquals(asList(4, 3, 2, 5), toList); 281 fromList.add(6); 282 assertEquals(asList(6, 4, 3, 2, 5), toList); 283 fromList.add(2, 9); 284 assertEquals(asList(6, 4, 3, 9, 2, 5), toList); 285 fromList.remove(Integer.valueOf(2)); 286 assertEquals(asList(6, 4, 3, 9, 5), toList); 287 fromList.remove(3); 288 assertEquals(asList(6, 3, 9, 5), toList); 289 290 /* toList modifications reflected in fromList */ 291 toList.remove(0); 292 assertEquals(asList(5, 9, 3), fromList); 293 toList.add(7); 294 assertEquals(asList(7, 5, 9, 3), fromList); 295 toList.add(5); 296 assertEquals(asList(5, 7, 5, 9, 3), fromList); 297 toList.remove(Integer.valueOf(5)); 298 assertEquals(asList(5, 7, 9, 3), fromList); 299 toList.set(1, 8); 300 assertEquals(asList(5, 7, 8, 3), fromList); 301 toList.clear(); 302 assertEquals(Collections.emptyList(), fromList); 303 } 304 305 private static <E> List<E> list(E... elements) { 306 return ImmutableList.copyOf(elements); 307 } 308 309 @SuppressWarnings("unchecked") // varargs! 310 public void testCartesianProduct_binary1x1() { 311 assertThat(Lists.cartesianProduct(list(1), list(2))).has().item(list(1, 2)); 312 } 313 314 @SuppressWarnings("unchecked") // varargs! 315 public void testCartesianProduct_binary1x2() { 316 assertThat(Lists.cartesianProduct(list(1), list(2, 3))) 317 .has().exactly(list(1, 2), list(1, 3)).inOrder(); 318 } 319 320 @SuppressWarnings("unchecked") // varargs! 321 public void testCartesianProduct_binary2x2() { 322 assertThat(Lists.cartesianProduct(list(1, 2), list(3, 4))) 323 .has().exactly(list(1, 3), list(1, 4), list(2, 3), list(2, 4)).inOrder(); 324 } 325 326 @SuppressWarnings("unchecked") // varargs! 327 public void testCartesianProduct_2x2x2() { 328 assertThat(Lists.cartesianProduct(list(0, 1), list(0, 1), list(0, 1))).has().exactly( 329 list(0, 0, 0), list(0, 0, 1), list(0, 1, 0), list(0, 1, 1), 330 list(1, 0, 0), list(1, 0, 1), list(1, 1, 0), list(1, 1, 1)).inOrder(); 331 } 332 333 @SuppressWarnings("unchecked") // varargs! 334 public void testCartesianProduct_contains() { 335 List<List<Integer>> actual = Lists.cartesianProduct(list(1, 2), list(3, 4)); 336 assertTrue(actual.contains(list(1, 3))); 337 assertTrue(actual.contains(list(1, 4))); 338 assertTrue(actual.contains(list(2, 3))); 339 assertTrue(actual.contains(list(2, 4))); 340 assertFalse(actual.contains(list(3, 1))); 341 } 342 343 @SuppressWarnings("unchecked") // varargs! 344 public void testCartesianProduct_unrelatedTypes() { 345 List<Integer> x = list(1, 2); 346 List<String> y = list("3", "4"); 347 348 List<Object> exp1 = list((Object) 1, "3"); 349 List<Object> exp2 = list((Object) 1, "4"); 350 List<Object> exp3 = list((Object) 2, "3"); 351 List<Object> exp4 = list((Object) 2, "4"); 352 353 assertThat(Lists.<Object>cartesianProduct(x, y)) 354 .has().exactly(exp1, exp2, exp3, exp4).inOrder(); 355 } 356 357 @SuppressWarnings("unchecked") // varargs! 358 public void testCartesianProductTooBig() { 359 List<String> list = Collections.nCopies(10000, "foo"); 360 try { 361 Lists.cartesianProduct(list, list, list, list, list); 362 fail("Expected IAE"); 363 } catch (IllegalArgumentException expected) {} 364 } 365 366 public void testTransformHashCodeRandomAccess() { 367 List<String> list = Lists.transform(SOME_LIST, SOME_FUNCTION); 368 assertEquals(SOME_STRING_LIST.hashCode(), list.hashCode()); 369 } 370 371 public void testTransformHashCodeSequential() { 372 List<String> list = Lists.transform(SOME_SEQUENTIAL_LIST, SOME_FUNCTION); 373 assertEquals(SOME_STRING_LIST.hashCode(), list.hashCode()); 374 } 375 376 public void testTransformModifiableRandomAccess() { 377 List<Integer> fromList = Lists.newArrayList(SOME_LIST); 378 List<String> list = Lists.transform(fromList, SOME_FUNCTION); 379 assertTransformModifiable(list); 380 } 381 382 public void testTransformModifiableSequential() { 383 List<Integer> fromList = Lists.newLinkedList(SOME_SEQUENTIAL_LIST); 384 List<String> list = Lists.transform(fromList, SOME_FUNCTION); 385 assertTransformModifiable(list); 386 } 387 388 private static void assertTransformModifiable(List<String> list) { 389 try { 390 list.add("5"); 391 fail("transformed list is addable"); 392 } catch (UnsupportedOperationException expected) {} 393 list.remove(0); 394 assertEquals(asList("2", "3", "4"), list); 395 list.remove("3"); 396 assertEquals(asList("2", "4"), list); 397 try { 398 list.set(0, "5"); 399 fail("transformed list is setable"); 400 } catch (UnsupportedOperationException expected) {} 401 list.clear(); 402 assertEquals(Collections.emptyList(), list); 403 } 404 405 public void testTransformViewRandomAccess() { 406 List<Integer> fromList = Lists.newArrayList(SOME_LIST); 407 List<String> toList = Lists.transform(fromList, SOME_FUNCTION); 408 assertTransformView(fromList, toList); 409 } 410 411 public void testTransformViewSequential() { 412 List<Integer> fromList = Lists.newLinkedList(SOME_SEQUENTIAL_LIST); 413 List<String> toList = Lists.transform(fromList, SOME_FUNCTION); 414 assertTransformView(fromList, toList); 415 } 416 417 private static void assertTransformView(List<Integer> fromList, 418 List<String> toList) { 419 /* fromList modifications reflected in toList */ 420 fromList.set(0, 5); 421 assertEquals(asList("5", "2", "3", "4"), toList); 422 fromList.add(6); 423 assertEquals(asList("5", "2", "3", "4", "6"), toList); 424 fromList.remove(Integer.valueOf(2)); 425 assertEquals(asList("5", "3", "4", "6"), toList); 426 fromList.remove(2); 427 assertEquals(asList("5", "3", "6"), toList); 428 429 /* toList modifications reflected in fromList */ 430 toList.remove(2); 431 assertEquals(asList(5, 3), fromList); 432 toList.remove("5"); 433 assertEquals(asList(3), fromList); 434 toList.clear(); 435 assertEquals(Collections.emptyList(), fromList); 436 } 437 438 public void testTransformRandomAccess() { 439 List<String> list = Lists.transform(SOME_LIST, SOME_FUNCTION); 440 assertTrue(list instanceof RandomAccess); 441 } 442 443 public void testTransformSequential() { 444 List<String> list = Lists.transform(SOME_SEQUENTIAL_LIST, SOME_FUNCTION); 445 assertFalse(list instanceof RandomAccess); 446 } 447 448 public void testTransformListIteratorRandomAccess() { 449 List<Integer> fromList = Lists.newArrayList(SOME_LIST); 450 List<String> list = Lists.transform(fromList, SOME_FUNCTION); 451 assertTransformListIterator(list); 452 } 453 454 public void testTransformListIteratorSequential() { 455 List<Integer> fromList = Lists.newLinkedList(SOME_SEQUENTIAL_LIST); 456 List<String> list = Lists.transform(fromList, SOME_FUNCTION); 457 assertTransformListIterator(list); 458 } 459 460 public void testTransformPreservesIOOBEsThrownByFunction() { 461 try { 462 Lists.transform(ImmutableList.of("foo", "bar"), new Function<String, String>() { 463 @Override 464 public String apply(String input) { 465 throw new IndexOutOfBoundsException(); 466 } 467 }).toArray(); 468 fail(); 469 } catch (IndexOutOfBoundsException expected) { 470 // success 471 } 472 } 473 474 private static void assertTransformListIterator(List<String> list) { 475 ListIterator<String> iterator = list.listIterator(1); 476 assertEquals(1, iterator.nextIndex()); 477 assertEquals("2", iterator.next()); 478 assertEquals("3", iterator.next()); 479 assertEquals("4", iterator.next()); 480 assertEquals(4, iterator.nextIndex()); 481 try { 482 iterator.next(); 483 fail("did not detect end of list"); 484 } catch (NoSuchElementException expected) {} 485 assertEquals(3, iterator.previousIndex()); 486 assertEquals("4", iterator.previous()); 487 assertEquals("3", iterator.previous()); 488 assertEquals("2", iterator.previous()); 489 assertTrue(iterator.hasPrevious()); 490 assertEquals("1", iterator.previous()); 491 assertFalse(iterator.hasPrevious()); 492 assertEquals(-1, iterator.previousIndex()); 493 try { 494 iterator.previous(); 495 fail("did not detect beginning of list"); 496 } catch (NoSuchElementException expected) {} 497 iterator.remove(); 498 assertEquals(asList("2", "3", "4"), list); 499 assertFalse(list.isEmpty()); 500 501 // An UnsupportedOperationException or IllegalStateException may occur. 502 try { 503 iterator.add("1"); 504 fail("transformed list iterator is addable"); 505 } catch (UnsupportedOperationException expected) { 506 } catch (IllegalStateException expected) {} 507 try { 508 iterator.set("1"); 509 fail("transformed list iterator is settable"); 510 } catch (UnsupportedOperationException expected) { 511 } catch (IllegalStateException expected) {} 512 } 513 514 public void testTransformIteratorRandomAccess() { 515 List<Integer> fromList = Lists.newArrayList(SOME_LIST); 516 List<String> list = Lists.transform(fromList, SOME_FUNCTION); 517 assertTransformIterator(list); 518 } 519 520 public void testTransformIteratorSequential() { 521 List<Integer> fromList = Lists.newLinkedList(SOME_SEQUENTIAL_LIST); 522 List<String> list = Lists.transform(fromList, SOME_FUNCTION); 523 assertTransformIterator(list); 524 } 525 526 /** 527 * We use this class to avoid the need to suppress generics checks with 528 * easy mock. 529 */ 530 private interface IntegerList extends List<Integer> {} 531 532 private static void assertTransformIterator(List<String> list) { 533 Iterator<String> iterator = list.iterator(); 534 assertTrue(iterator.hasNext()); 535 assertEquals("1", iterator.next()); 536 assertTrue(iterator.hasNext()); 537 assertEquals("2", iterator.next()); 538 assertTrue(iterator.hasNext()); 539 assertEquals("3", iterator.next()); 540 assertTrue(iterator.hasNext()); 541 assertEquals("4", iterator.next()); 542 assertFalse(iterator.hasNext()); 543 try { 544 iterator.next(); 545 fail("did not detect end of list"); 546 } catch (NoSuchElementException expected) {} 547 iterator.remove(); 548 assertEquals(asList("1", "2", "3"), list); 549 assertFalse(iterator.hasNext()); 550 } 551 552 public void testPartition_badSize() { 553 List<Integer> source = Collections.singletonList(1); 554 try { 555 Lists.partition(source, 0); 556 fail(); 557 } catch (IllegalArgumentException expected) { 558 } 559 } 560 561 public void testPartition_empty() { 562 List<Integer> source = Collections.emptyList(); 563 List<List<Integer>> partitions = Lists.partition(source, 1); 564 assertTrue(partitions.isEmpty()); 565 assertEquals(0, partitions.size()); 566 } 567 568 public void testPartition_1_1() { 569 List<Integer> source = Collections.singletonList(1); 570 List<List<Integer>> partitions = Lists.partition(source, 1); 571 assertEquals(1, partitions.size()); 572 assertEquals(Collections.singletonList(1), partitions.get(0)); 573 } 574 575 public void testPartition_1_2() { 576 List<Integer> source = Collections.singletonList(1); 577 List<List<Integer>> partitions = Lists.partition(source, 2); 578 assertEquals(1, partitions.size()); 579 assertEquals(Collections.singletonList(1), partitions.get(0)); 580 } 581 582 public void testPartition_2_1() { 583 List<Integer> source = asList(1, 2); 584 List<List<Integer>> partitions = Lists.partition(source, 1); 585 assertEquals(2, partitions.size()); 586 assertEquals(Collections.singletonList(1), partitions.get(0)); 587 assertEquals(Collections.singletonList(2), partitions.get(1)); 588 } 589 590 public void testPartition_3_2() { 591 List<Integer> source = asList(1, 2, 3); 592 List<List<Integer>> partitions = Lists.partition(source, 2); 593 assertEquals(2, partitions.size()); 594 assertEquals(asList(1, 2), partitions.get(0)); 595 assertEquals(asList(3), partitions.get(1)); 596 } 597 598 public void testPartitionRandomAccessFalse() { 599 List<Integer> source = Lists.newLinkedList(asList(1, 2, 3)); 600 List<List<Integer>> partitions = Lists.partition(source, 2); 601 assertFalse(partitions instanceof RandomAccess); 602 assertFalse(partitions.get(0) instanceof RandomAccess); 603 assertFalse(partitions.get(1) instanceof RandomAccess); 604 } 605 606 // TODO: use the ListTestSuiteBuilder 607 608 public void testPartition_view() { 609 List<Integer> list = asList(1, 2, 3); 610 List<List<Integer>> partitions = Lists.partition(list, 3); 611 612 // Changes before the partition is retrieved are reflected 613 list.set(0, 3); 614 615 Iterator<List<Integer>> iterator = partitions.iterator(); 616 617 // Changes before the partition is retrieved are reflected 618 list.set(1, 4); 619 620 List<Integer> first = iterator.next(); 621 622 // Changes after are too (unlike Iterables.partition) 623 list.set(2, 5); 624 625 assertEquals(asList(3, 4, 5), first); 626 627 // Changes to a sublist also write through to the original list 628 first.set(1, 6); 629 assertEquals(asList(3, 6, 5), list); 630 } 631 632 public void testPartitionSize_1() { 633 List<Integer> list = asList(1, 2, 3); 634 assertEquals(1, Lists.partition(list, Integer.MAX_VALUE).size()); 635 assertEquals(1, Lists.partition(list, Integer.MAX_VALUE - 1).size()); 636 } 637 } 638