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.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
43
44
45
46
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
188
189
190 public void testArraysAsList() {
191 List<String> ourWay = Lists.newArrayList("foo", "bar", "baz");
192 List<String> otherWay = asList("foo", "bar", "baz");
193
194
195 assertEquals(ourWay, otherWay);
196
197
198 otherWay.set(0, "FOO");
199 assertEquals("FOO", otherWay.get(0));
200
201
202 try {
203 otherWay.add("nope");
204 fail("no exception thrown");
205 } catch (UnsupportedOperationException expected) {
206 }
207
208
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
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
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")
310 public void testCartesianProduct_binary1x1() {
311 assertThat(Lists.cartesianProduct(list(1), list(2))).has().item(list(1, 2));
312 }
313
314 @SuppressWarnings("unchecked")
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")
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")
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")
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")
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")
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
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
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
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
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
528
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
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
613 list.set(0, 3);
614
615 Iterator<List<Integer>> iterator = partitions.iterator();
616
617
618 list.set(1, 4);
619
620 List<Integer> first = iterator.next();
621
622
623 list.set(2, 5);
624
625 assertEquals(asList(3, 4, 5), first);
626
627
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 }