• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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.base.Preconditions.checkNotNull;
20 import static com.google.common.collect.testing.IteratorFeature.UNMODIFIABLE;
21 import static com.google.common.truth.Truth.assertThat;
22 import static java.util.Arrays.asList;
23 import static java.util.Collections.singletonList;
24 
25 import com.google.common.annotations.GwtCompatible;
26 import com.google.common.annotations.GwtIncompatible;
27 import com.google.common.base.Function;
28 import com.google.common.base.Functions;
29 import com.google.common.collect.testing.IteratorTester;
30 import com.google.common.collect.testing.ListTestSuiteBuilder;
31 import com.google.common.collect.testing.TestStringListGenerator;
32 import com.google.common.collect.testing.features.CollectionFeature;
33 import com.google.common.collect.testing.features.CollectionSize;
34 import com.google.common.collect.testing.features.ListFeature;
35 import com.google.common.collect.testing.google.ListGenerators.CharactersOfCharSequenceGenerator;
36 import com.google.common.collect.testing.google.ListGenerators.CharactersOfStringGenerator;
37 import com.google.common.testing.NullPointerTester;
38 import com.google.common.testing.SerializableTester;
39 
40 import junit.framework.Test;
41 import junit.framework.TestCase;
42 import junit.framework.TestSuite;
43 
44 import org.easymock.EasyMock;
45 
46 import java.io.Serializable;
47 import java.util.ArrayList;
48 import java.util.Collection;
49 import java.util.Collections;
50 import java.util.Iterator;
51 import java.util.LinkedList;
52 import java.util.List;
53 import java.util.ListIterator;
54 import java.util.NoSuchElementException;
55 import java.util.RandomAccess;
56 import java.util.concurrent.CopyOnWriteArrayList;
57 
58 /**
59  * Unit test for {@code Lists}.
60  *
61  * @author Kevin Bourrillion
62  * @author Mike Bostock
63  * @author Jared Levy
64  */
65 @GwtCompatible(emulated = true)
66 public class ListsTest extends TestCase {
67 
68   private static final Collection<Integer> SOME_COLLECTION
69       = asList(0, 1, 1);
70 
71   private static final Iterable<Integer> SOME_ITERABLE = new SomeIterable();
72 
73   private static final class RemoveFirstFunction
74       implements Function<String, String>, Serializable {
75     @Override
apply(String from)76     public String apply(String from) {
77       return (from.length() == 0) ? from : from.substring(1);
78     }
79   }
80 
81   private static class SomeIterable implements Iterable<Integer>, Serializable {
82     @Override
iterator()83     public Iterator<Integer> iterator() {
84       return SOME_COLLECTION.iterator();
85     }
86     private static final long serialVersionUID = 0;
87   }
88 
89   private static final List<Integer> SOME_LIST
90       = Lists.newArrayList(1, 2, 3, 4);
91 
92   private static final List<Integer> SOME_SEQUENTIAL_LIST
93       = Lists.newLinkedList(asList(1, 2, 3, 4));
94 
95   private static final List<String> SOME_STRING_LIST
96       = asList("1", "2", "3", "4");
97 
98   private static final Function<Number, String> SOME_FUNCTION
99       = new SomeFunction();
100 
101   private static class SomeFunction
102       implements Function<Number, String>, Serializable {
103     @Override
apply(Number n)104     public String apply(Number n) {
105       return String.valueOf(n);
106     }
107     private static final long serialVersionUID = 0;
108   }
109 
110   @GwtIncompatible("suite")
suite()111   public static Test suite() {
112     TestSuite suite = new TestSuite();
113     suite.addTestSuite(ListsTest.class);
114 
115     suite.addTest(ListTestSuiteBuilder.using(new TestStringListGenerator() {
116           @Override protected List<String> create(String[] elements) {
117             String[] rest = new String[elements.length - 1];
118             System.arraycopy(elements, 1, rest, 0, elements.length - 1);
119             return Lists.asList(elements[0], rest);
120           }
121         })
122         .named("Lists.asList, 2 parameter")
123         .withFeatures(CollectionSize.SEVERAL, CollectionSize.ONE,
124             CollectionFeature.SERIALIZABLE,
125             CollectionFeature.ALLOWS_NULL_VALUES)
126         .createTestSuite());
127 
128     suite.addTest(ListTestSuiteBuilder.using(new TestStringListGenerator() {
129           @Override protected List<String> create(String[] elements) {
130             String[] rest = new String[elements.length - 2];
131             System.arraycopy(elements, 2, rest, 0, elements.length - 2);
132             return Lists.asList(elements[0], elements[1], rest);
133           }
134         })
135         .named("Lists.asList, 3 parameter")
136         .withFeatures(CollectionSize.SEVERAL,
137             CollectionFeature.SERIALIZABLE,
138             CollectionFeature.ALLOWS_NULL_VALUES)
139         .createTestSuite());
140 
141     final Function<String, String> removeFirst
142         = new RemoveFirstFunction();
143 
144     suite.addTest(ListTestSuiteBuilder.using(new TestStringListGenerator() {
145           @Override protected List<String> create(String[] elements) {
146             List<String> fromList = Lists.newArrayList();
147             for (String element : elements) {
148               fromList.add("q" + checkNotNull(element));
149             }
150             return Lists.transform(fromList, removeFirst);
151           }
152         })
153         .named("Lists.transform, random access, no nulls")
154         .withFeatures(CollectionSize.ANY,
155             ListFeature.REMOVE_OPERATIONS,
156             CollectionFeature.SERIALIZABLE,
157             CollectionFeature.ALLOWS_NULL_QUERIES)
158         .createTestSuite());
159 
160     suite.addTest(ListTestSuiteBuilder.using(new TestStringListGenerator() {
161           @Override protected List<String> create(String[] elements) {
162             List<String> fromList = Lists.newLinkedList();
163             for (String element : elements) {
164               fromList.add("q" + checkNotNull(element));
165             }
166             return Lists.transform(fromList, removeFirst);
167           }
168         })
169         .named("Lists.transform, sequential access, no nulls")
170         .withFeatures(CollectionSize.ANY,
171             ListFeature.REMOVE_OPERATIONS,
172             CollectionFeature.SERIALIZABLE,
173             CollectionFeature.ALLOWS_NULL_QUERIES)
174         .createTestSuite());
175 
176     suite.addTest(ListTestSuiteBuilder.using(new TestStringListGenerator() {
177           @Override protected List<String> create(String[] elements) {
178             List<String> fromList = Lists.newArrayList(elements);
179             return Lists.transform(fromList, Functions.<String>identity());
180           }
181         })
182         .named("Lists.transform, random access, nulls")
183         .withFeatures(CollectionSize.ANY,
184             ListFeature.REMOVE_OPERATIONS,
185             CollectionFeature.SERIALIZABLE,
186             CollectionFeature.ALLOWS_NULL_VALUES)
187         .createTestSuite());
188 
189     suite.addTest(ListTestSuiteBuilder.using(new TestStringListGenerator() {
190           @Override protected List<String> create(String[] elements) {
191             List<String> fromList =
192                 Lists.newLinkedList(asList(elements));
193             return Lists.transform(fromList, Functions.<String>identity());
194           }
195         })
196         .named("Lists.transform, sequential access, nulls")
197         .withFeatures(CollectionSize.ANY,
198             ListFeature.REMOVE_OPERATIONS,
199             CollectionFeature.SERIALIZABLE,
200             CollectionFeature.ALLOWS_NULL_VALUES)
201         .createTestSuite());
202 
203     suite.addTest(ListTestSuiteBuilder.using(new TestStringListGenerator() {
204       @Override protected List<String> create(String[] elements) {
205         List<String> list = Lists.newArrayList();
206         for (int i = elements.length - 1; i >= 0; i--)
207           list.add(elements[i]);
208         return Lists.reverse(list);
209       }
210     }).named("Lists.reverse[ArrayList]").withFeatures(CollectionSize.ANY,
211         CollectionFeature.ALLOWS_NULL_VALUES, ListFeature.GENERAL_PURPOSE)
212         .createTestSuite());
213 
214     suite.addTest(ListTestSuiteBuilder.using(new TestStringListGenerator() {
215       @Override protected List<String> create(String[] elements) {
216         String[] reverseElements = new String[elements.length];
217         for (int i = elements.length - 1, j = 0; i >= 0; i--, j++)
218           reverseElements[j] = elements[i];
219         return Lists.reverse(asList(reverseElements));
220       }
221     }).named("Lists.reverse[Arrays.asList]").withFeatures(CollectionSize.ANY,
222         CollectionFeature.ALLOWS_NULL_VALUES, ListFeature.SUPPORTS_SET)
223         .createTestSuite());
224 
225     suite.addTest(ListTestSuiteBuilder.using(new TestStringListGenerator() {
226       @Override protected List<String> create(String[] elements) {
227         List<String> list = Lists.newLinkedList();
228         for (int i = elements.length - 1; i >= 0; i--)
229           list.add(elements[i]);
230         return Lists.reverse(list);
231       }
232     }).named("Lists.reverse[LinkedList]").withFeatures(CollectionSize.ANY,
233         CollectionFeature.ALLOWS_NULL_VALUES, ListFeature.GENERAL_PURPOSE)
234         .createTestSuite());
235 
236     suite.addTest(ListTestSuiteBuilder.using(new TestStringListGenerator() {
237       @Override protected List<String> create(String[] elements) {
238         ImmutableList.Builder<String> builder = ImmutableList.builder();
239         for (int i = elements.length - 1; i >= 0; i--)
240           builder.add(elements[i]);
241         return Lists.reverse(builder.build());
242       }
243     }).named("Lists.reverse[ImmutableList]").withFeatures(CollectionSize.ANY,
244         CollectionFeature.ALLOWS_NULL_QUERIES)
245         .createTestSuite());
246 
247     suite.addTest(ListTestSuiteBuilder.using(new CharactersOfStringGenerator())
248         .named("Lists.charactersOf[String]").withFeatures(
249             CollectionSize.ANY,
250             CollectionFeature.SERIALIZABLE,
251             CollectionFeature.ALLOWS_NULL_QUERIES)
252             .createTestSuite());
253 
254     suite.addTest(ListTestSuiteBuilder.using(new CharactersOfCharSequenceGenerator())
255         .named("Lists.charactersOf[CharSequence]").withFeatures(
256             CollectionSize.ANY, CollectionFeature.ALLOWS_NULL_QUERIES)
257             .createTestSuite());
258 
259     return suite;
260   }
261 
testCharactersOfIsView()262   public void testCharactersOfIsView() {
263     StringBuilder builder = new StringBuilder("abc");
264     List<Character> chars = Lists.charactersOf(builder);
265     assertEquals(asList('a', 'b', 'c'), chars);
266     builder.append("def");
267     assertEquals(
268         asList('a', 'b', 'c', 'd', 'e', 'f'), chars);
269     builder.deleteCharAt(5);
270     assertEquals(
271         asList('a', 'b', 'c', 'd', 'e'), chars);
272   }
273 
testNewArrayListEmpty()274   public void testNewArrayListEmpty() {
275     ArrayList<Integer> list = Lists.newArrayList();
276     assertEquals(Collections.emptyList(), list);
277   }
278 
testNewArrayListWithCapacity()279   public void testNewArrayListWithCapacity() {
280     ArrayList<Integer> list = Lists.newArrayListWithCapacity(0);
281     assertEquals(Collections.emptyList(), list);
282 
283     ArrayList<Integer> bigger = Lists.newArrayListWithCapacity(256);
284     assertEquals(Collections.emptyList(), bigger);
285   }
286 
testNewArrayListWithCapacity_negative()287   public void testNewArrayListWithCapacity_negative() {
288     try {
289       Lists.newArrayListWithCapacity(-1);
290       fail();
291     } catch (IllegalArgumentException expected) {
292     }
293   }
294 
testNewArrayListWithExpectedSize()295   public void testNewArrayListWithExpectedSize() {
296     ArrayList<Integer> list = Lists.newArrayListWithExpectedSize(0);
297     assertEquals(Collections.emptyList(), list);
298 
299     ArrayList<Integer> bigger = Lists.newArrayListWithExpectedSize(256);
300     assertEquals(Collections.emptyList(), bigger);
301   }
302 
testNewArrayListWithExpectedSize_negative()303   public void testNewArrayListWithExpectedSize_negative() {
304     try {
305       Lists.newArrayListWithExpectedSize(-1);
306       fail();
307     } catch (IllegalArgumentException expected) {
308     }
309   }
310 
testNewArrayListVarArgs()311   public void testNewArrayListVarArgs() {
312     ArrayList<Integer> list = Lists.newArrayList(0, 1, 1);
313     assertEquals(SOME_COLLECTION, list);
314   }
315 
testComputeArrayListCapacity()316   public void testComputeArrayListCapacity() {
317     assertEquals(5, Lists.computeArrayListCapacity(0));
318     assertEquals(13, Lists.computeArrayListCapacity(8));
319     assertEquals(89, Lists.computeArrayListCapacity(77));
320     assertEquals(22000005, Lists.computeArrayListCapacity(20000000));
321     assertEquals(Integer.MAX_VALUE,
322         Lists.computeArrayListCapacity(Integer.MAX_VALUE - 1000));
323   }
324 
testNewArrayListFromCollection()325   public void testNewArrayListFromCollection() {
326     ArrayList<Integer> list = Lists.newArrayList(SOME_COLLECTION);
327     assertEquals(SOME_COLLECTION, list);
328   }
329 
testNewArrayListFromIterable()330   public void testNewArrayListFromIterable() {
331     ArrayList<Integer> list = Lists.newArrayList(SOME_ITERABLE);
332     assertEquals(SOME_COLLECTION, list);
333   }
334 
testNewArrayListFromIterator()335   public void testNewArrayListFromIterator() {
336     ArrayList<Integer> list = Lists.newArrayList(SOME_COLLECTION.iterator());
337     assertEquals(SOME_COLLECTION, list);
338   }
339 
testNewLinkedListEmpty()340   public void testNewLinkedListEmpty() {
341     LinkedList<Integer> list = Lists.newLinkedList();
342     assertEquals(Collections.emptyList(), list);
343   }
344 
testNewLinkedListFromCollection()345   public void testNewLinkedListFromCollection() {
346     LinkedList<Integer> list = Lists.newLinkedList(SOME_COLLECTION);
347     assertEquals(SOME_COLLECTION, list);
348   }
349 
testNewLinkedListFromIterable()350   public void testNewLinkedListFromIterable() {
351     LinkedList<Integer> list = Lists.newLinkedList(SOME_ITERABLE);
352     assertEquals(SOME_COLLECTION, list);
353   }
354 
355   @GwtIncompatible("CopyOnWriteArrayList")
testNewCOWALEmpty()356   public void testNewCOWALEmpty() {
357     CopyOnWriteArrayList<Integer> list = Lists.newCopyOnWriteArrayList();
358     assertEquals(Collections.emptyList(), list);
359   }
360 
361   @GwtIncompatible("CopyOnWriteArrayList")
testNewCOWALFromIterable()362   public void testNewCOWALFromIterable() {
363     CopyOnWriteArrayList<Integer> list = Lists.newCopyOnWriteArrayList(
364         SOME_ITERABLE);
365     assertEquals(SOME_COLLECTION, list);
366   }
367 
368   @GwtIncompatible("NullPointerTester")
testNullPointerExceptions()369   public void testNullPointerExceptions() {
370     NullPointerTester tester = new NullPointerTester();
371     tester.testAllPublicStaticMethods(Lists.class);
372   }
373 
374   /**
375    * This is just here to illustrate how {@code Arrays#asList} differs from
376    * {@code Lists#newArrayList}.
377    */
testArraysAsList()378   public void testArraysAsList() {
379     List<String> ourWay = Lists.newArrayList("foo", "bar", "baz");
380     List<String> otherWay = asList("foo", "bar", "baz");
381 
382     // They're logically equal
383     assertEquals(ourWay, otherWay);
384 
385     // The result of Arrays.asList() is mutable
386     otherWay.set(0, "FOO");
387     assertEquals("FOO", otherWay.get(0));
388 
389     // But it can't grow
390     try {
391       otherWay.add("nope");
392       fail("no exception thrown");
393     } catch (UnsupportedOperationException expected) {
394     }
395 
396     // And it can't shrink
397     try {
398       otherWay.remove(2);
399       fail("no exception thrown");
400     } catch (UnsupportedOperationException expected) {
401     }
402   }
403 
404   @GwtIncompatible("SerializableTester")
testAsList1()405   public void testAsList1() {
406     List<String> list = Lists.asList("foo", new String[] { "bar", "baz" });
407     checkFooBarBazList(list);
408     SerializableTester.reserializeAndAssert(list);
409     assertTrue(list instanceof RandomAccess);
410 
411     new IteratorTester<String>(5, UNMODIFIABLE,
412         asList("foo", "bar", "baz"),
413         IteratorTester.KnownOrder.KNOWN_ORDER) {
414       @Override protected Iterator<String> newTargetIterator() {
415         return Lists.asList("foo", new String[] {"bar", "baz"}).iterator();
416       }
417     }.test();
418   }
419 
checkFooBarBazList(List<String> list)420   private void checkFooBarBazList(List<String> list) {
421     assertThat(list).has().exactly("foo", "bar", "baz").inOrder();
422     assertEquals(3, list.size());
423     assertIndexIsOutOfBounds(list, -1);
424     assertEquals("foo", list.get(0));
425     assertEquals("bar", list.get(1));
426     assertEquals("baz", list.get(2));
427     assertIndexIsOutOfBounds(list, 3);
428   }
429 
testAsList1Small()430   public void testAsList1Small() {
431     List<String> list = Lists.asList("foo", new String[0]);
432     assertThat(list).has().item("foo");
433     assertEquals(1, list.size());
434     assertIndexIsOutOfBounds(list, -1);
435     assertEquals("foo", list.get(0));
436     assertIndexIsOutOfBounds(list, 1);
437     assertTrue(list instanceof RandomAccess);
438 
439     new IteratorTester<String>(3, UNMODIFIABLE, singletonList("foo"),
440         IteratorTester.KnownOrder.KNOWN_ORDER) {
441       @Override protected Iterator<String> newTargetIterator() {
442         return Lists.asList("foo", new String[0]).iterator();
443       }
444     }.test();
445   }
446 
testAsList2()447   public void testAsList2() {
448     List<String> list = Lists.asList("foo", "bar", new String[] { "baz" });
449     checkFooBarBazList(list);
450     assertTrue(list instanceof RandomAccess);
451 
452     new IteratorTester<String>(5, UNMODIFIABLE, asList("foo", "bar",
453         "baz"), IteratorTester.KnownOrder.KNOWN_ORDER) {
454       @Override protected Iterator<String> newTargetIterator() {
455         return Lists.asList("foo", "bar", new String[] {"baz"}).iterator();
456       }
457     }.test();
458   }
459 
460   @GwtIncompatible("SerializableTester")
testAsList2Small()461   public void testAsList2Small() {
462     List<String> list = Lists.asList("foo", "bar", new String[0]);
463     assertThat(list).has().exactly("foo", "bar").inOrder();
464     assertEquals(2, list.size());
465     assertIndexIsOutOfBounds(list, -1);
466     assertEquals("foo", list.get(0));
467     assertEquals("bar", list.get(1));
468     assertIndexIsOutOfBounds(list, 2);
469     SerializableTester.reserializeAndAssert(list);
470     assertTrue(list instanceof RandomAccess);
471 
472     new IteratorTester<String>(5, UNMODIFIABLE, asList("foo", "bar"),
473         IteratorTester.KnownOrder.KNOWN_ORDER) {
474       @Override protected Iterator<String> newTargetIterator() {
475         return Lists.asList("foo", "bar", new String[0]).iterator();
476       }
477     }.test();
478   }
479 
assertIndexIsOutOfBounds(List<String> list, int index)480   private static void assertIndexIsOutOfBounds(List<String> list, int index) {
481     try {
482       list.get(index);
483       fail();
484     } catch (IndexOutOfBoundsException expected) {
485     }
486   }
487 
testReverseViewRandomAccess()488   public void testReverseViewRandomAccess() {
489     List<Integer> fromList = Lists.newArrayList(SOME_LIST);
490     List<Integer> toList = Lists.reverse(fromList);
491     assertReverseView(fromList, toList);
492   }
493 
testReverseViewSequential()494   public void testReverseViewSequential() {
495     List<Integer> fromList = Lists.newLinkedList(SOME_SEQUENTIAL_LIST);
496     List<Integer> toList = Lists.reverse(fromList);
497     assertReverseView(fromList, toList);
498   }
499 
assertReverseView(List<Integer> fromList, List<Integer> toList)500   private static void assertReverseView(List<Integer> fromList,
501       List<Integer> toList) {
502     /* fromList modifications reflected in toList */
503     fromList.set(0, 5);
504     assertEquals(asList(4, 3, 2, 5), toList);
505     fromList.add(6);
506     assertEquals(asList(6, 4, 3, 2, 5), toList);
507     fromList.add(2, 9);
508     assertEquals(asList(6, 4, 3, 9, 2, 5), toList);
509     fromList.remove(Integer.valueOf(2));
510     assertEquals(asList(6, 4, 3, 9, 5), toList);
511     fromList.remove(3);
512     assertEquals(asList(6, 3, 9, 5), toList);
513 
514     /* toList modifications reflected in fromList */
515     toList.remove(0);
516     assertEquals(asList(5, 9, 3), fromList);
517     toList.add(7);
518     assertEquals(asList(7, 5, 9, 3), fromList);
519     toList.add(5);
520     assertEquals(asList(5, 7, 5, 9, 3), fromList);
521     toList.remove(Integer.valueOf(5));
522     assertEquals(asList(5, 7, 9, 3), fromList);
523     toList.set(1, 8);
524     assertEquals(asList(5, 7, 8, 3), fromList);
525     toList.clear();
526     assertEquals(Collections.emptyList(), fromList);
527   }
528 
list(E... elements)529   private static <E> List<E> list(E... elements) {
530     return ImmutableList.copyOf(elements);
531   }
532 
533   @SuppressWarnings("unchecked") // varargs!
testCartesianProduct_binary1x1()534   public void testCartesianProduct_binary1x1() {
535     assertThat(Lists.cartesianProduct(list(1), list(2))).has().item(list(1, 2));
536   }
537 
538   @SuppressWarnings("unchecked") // varargs!
testCartesianProduct_binary1x2()539   public void testCartesianProduct_binary1x2() {
540     assertThat(Lists.cartesianProduct(list(1), list(2, 3)))
541         .has().exactly(list(1, 2), list(1, 3)).inOrder();
542   }
543 
544   @SuppressWarnings("unchecked") // varargs!
testCartesianProduct_binary2x2()545   public void testCartesianProduct_binary2x2() {
546     assertThat(Lists.cartesianProduct(list(1, 2), list(3, 4)))
547         .has().exactly(list(1, 3), list(1, 4), list(2, 3), list(2, 4)).inOrder();
548   }
549 
550   @SuppressWarnings("unchecked") // varargs!
testCartesianProduct_2x2x2()551   public void testCartesianProduct_2x2x2() {
552     assertThat(Lists.cartesianProduct(list(0, 1), list(0, 1), list(0, 1))).has().exactly(
553         list(0, 0, 0), list(0, 0, 1), list(0, 1, 0), list(0, 1, 1),
554         list(1, 0, 0), list(1, 0, 1), list(1, 1, 0), list(1, 1, 1)).inOrder();
555   }
556 
557   @SuppressWarnings("unchecked") // varargs!
testCartesianProduct_contains()558   public void testCartesianProduct_contains() {
559     List<List<Integer>> actual = Lists.cartesianProduct(list(1, 2), list(3, 4));
560     assertTrue(actual.contains(list(1, 3)));
561     assertTrue(actual.contains(list(1, 4)));
562     assertTrue(actual.contains(list(2, 3)));
563     assertTrue(actual.contains(list(2, 4)));
564     assertFalse(actual.contains(list(3, 1)));
565   }
566 
567   @SuppressWarnings("unchecked") // varargs!
testCartesianProduct_unrelatedTypes()568   public void testCartesianProduct_unrelatedTypes() {
569     List<Integer> x = list(1, 2);
570     List<String> y = list("3", "4");
571 
572     List<Object> exp1 = list((Object) 1, "3");
573     List<Object> exp2 = list((Object) 1, "4");
574     List<Object> exp3 = list((Object) 2, "3");
575     List<Object> exp4 = list((Object) 2, "4");
576 
577     assertThat(Lists.<Object>cartesianProduct(x, y))
578         .has().exactly(exp1, exp2, exp3, exp4).inOrder();
579   }
580 
581   @SuppressWarnings("unchecked") // varargs!
testCartesianProductTooBig()582   public void testCartesianProductTooBig() {
583     List<String> list = Collections.nCopies(10000, "foo");
584     try {
585       Lists.cartesianProduct(list, list, list, list, list);
586       fail("Expected IAE");
587     } catch (IllegalArgumentException expected) {}
588   }
589 
testTransformHashCodeRandomAccess()590   public void testTransformHashCodeRandomAccess() {
591     List<String> list = Lists.transform(SOME_LIST, SOME_FUNCTION);
592     assertEquals(SOME_STRING_LIST.hashCode(), list.hashCode());
593   }
594 
testTransformHashCodeSequential()595   public void testTransformHashCodeSequential() {
596     List<String> list = Lists.transform(SOME_SEQUENTIAL_LIST, SOME_FUNCTION);
597     assertEquals(SOME_STRING_LIST.hashCode(), list.hashCode());
598   }
599 
testTransformModifiableRandomAccess()600   public void testTransformModifiableRandomAccess() {
601     List<Integer> fromList = Lists.newArrayList(SOME_LIST);
602     List<String> list = Lists.transform(fromList, SOME_FUNCTION);
603     assertTransformModifiable(list);
604   }
605 
testTransformModifiableSequential()606   public void testTransformModifiableSequential() {
607     List<Integer> fromList = Lists.newLinkedList(SOME_SEQUENTIAL_LIST);
608     List<String> list = Lists.transform(fromList, SOME_FUNCTION);
609     assertTransformModifiable(list);
610   }
611 
assertTransformModifiable(List<String> list)612   private static void assertTransformModifiable(List<String> list) {
613     try {
614       list.add("5");
615       fail("transformed list is addable");
616     } catch (UnsupportedOperationException expected) {}
617     list.remove(0);
618     assertEquals(asList("2", "3", "4"), list);
619     list.remove("3");
620     assertEquals(asList("2", "4"), list);
621     try {
622       list.set(0, "5");
623       fail("transformed list is setable");
624     } catch (UnsupportedOperationException expected) {}
625     list.clear();
626     assertEquals(Collections.emptyList(), list);
627   }
628 
testTransformViewRandomAccess()629   public void testTransformViewRandomAccess() {
630     List<Integer> fromList = Lists.newArrayList(SOME_LIST);
631     List<String> toList = Lists.transform(fromList, SOME_FUNCTION);
632     assertTransformView(fromList, toList);
633   }
634 
testTransformViewSequential()635   public void testTransformViewSequential() {
636     List<Integer> fromList = Lists.newLinkedList(SOME_SEQUENTIAL_LIST);
637     List<String> toList = Lists.transform(fromList, SOME_FUNCTION);
638     assertTransformView(fromList, toList);
639   }
640 
assertTransformView(List<Integer> fromList, List<String> toList)641   private static void assertTransformView(List<Integer> fromList,
642       List<String> toList) {
643     /* fromList modifications reflected in toList */
644     fromList.set(0, 5);
645     assertEquals(asList("5", "2", "3", "4"), toList);
646     fromList.add(6);
647     assertEquals(asList("5", "2", "3", "4", "6"), toList);
648     fromList.remove(Integer.valueOf(2));
649     assertEquals(asList("5", "3", "4", "6"), toList);
650     fromList.remove(2);
651     assertEquals(asList("5", "3", "6"), toList);
652 
653     /* toList modifications reflected in fromList */
654     toList.remove(2);
655     assertEquals(asList(5, 3), fromList);
656     toList.remove("5");
657     assertEquals(asList(3), fromList);
658     toList.clear();
659     assertEquals(Collections.emptyList(), fromList);
660   }
661 
testTransformRandomAccess()662   public void testTransformRandomAccess() {
663     List<String> list = Lists.transform(SOME_LIST, SOME_FUNCTION);
664     assertTrue(list instanceof RandomAccess);
665   }
666 
testTransformSequential()667   public void testTransformSequential() {
668     List<String> list = Lists.transform(SOME_SEQUENTIAL_LIST, SOME_FUNCTION);
669     assertFalse(list instanceof RandomAccess);
670   }
671 
testTransformListIteratorRandomAccess()672   public void testTransformListIteratorRandomAccess() {
673     List<Integer> fromList = Lists.newArrayList(SOME_LIST);
674     List<String> list = Lists.transform(fromList, SOME_FUNCTION);
675     assertTransformListIterator(list);
676   }
677 
testTransformListIteratorSequential()678   public void testTransformListIteratorSequential() {
679     List<Integer> fromList = Lists.newLinkedList(SOME_SEQUENTIAL_LIST);
680     List<String> list = Lists.transform(fromList, SOME_FUNCTION);
681     assertTransformListIterator(list);
682   }
683 
testTransformPreservesIOOBEsThrownByFunction()684   public void testTransformPreservesIOOBEsThrownByFunction() {
685     try {
686       Lists.transform(ImmutableList.of("foo", "bar"), new Function<String, String>() {
687         @Override
688         public String apply(String input) {
689           throw new IndexOutOfBoundsException();
690         }
691       }).toArray();
692       fail();
693     } catch (IndexOutOfBoundsException expected) {
694       // success
695     }
696   }
697 
assertTransformListIterator(List<String> list)698   private static void assertTransformListIterator(List<String> list) {
699     ListIterator<String> iterator = list.listIterator(1);
700     assertEquals(1, iterator.nextIndex());
701     assertEquals("2", iterator.next());
702     assertEquals("3", iterator.next());
703     assertEquals("4", iterator.next());
704     assertEquals(4, iterator.nextIndex());
705     try {
706       iterator.next();
707       fail("did not detect end of list");
708     } catch (NoSuchElementException expected) {}
709     assertEquals(3, iterator.previousIndex());
710     assertEquals("4", iterator.previous());
711     assertEquals("3", iterator.previous());
712     assertEquals("2", iterator.previous());
713     assertTrue(iterator.hasPrevious());
714     assertEquals("1", iterator.previous());
715     assertFalse(iterator.hasPrevious());
716     assertEquals(-1, iterator.previousIndex());
717     try {
718       iterator.previous();
719       fail("did not detect beginning of list");
720     } catch (NoSuchElementException expected) {}
721     iterator.remove();
722     assertEquals(asList("2", "3", "4"), list);
723     assertFalse(list.isEmpty());
724 
725     // An UnsupportedOperationException or IllegalStateException may occur.
726     try {
727       iterator.add("1");
728       fail("transformed list iterator is addable");
729     } catch (UnsupportedOperationException expected) {
730     } catch (IllegalStateException expected) {}
731     try {
732       iterator.set("1");
733       fail("transformed list iterator is settable");
734     } catch (UnsupportedOperationException expected) {
735     } catch (IllegalStateException expected) {}
736   }
737 
testTransformIteratorRandomAccess()738   public void testTransformIteratorRandomAccess() {
739     List<Integer> fromList = Lists.newArrayList(SOME_LIST);
740     List<String> list = Lists.transform(fromList, SOME_FUNCTION);
741     assertTransformIterator(list);
742   }
743 
testTransformIteratorSequential()744   public void testTransformIteratorSequential() {
745     List<Integer> fromList = Lists.newLinkedList(SOME_SEQUENTIAL_LIST);
746     List<String> list = Lists.transform(fromList, SOME_FUNCTION);
747     assertTransformIterator(list);
748   }
749 
750   /**
751    * We use this class to avoid the need to suppress generics checks with
752    * easy mock.
753    */
754   private interface IntegerList extends List<Integer> {}
755 
756   /**
757    * This test depends on the fact that {@code AbstractSequentialList.iterator}
758    * transforms the {@code iterator()} call into a call on {@code
759    * listIterator(int)}. This is fine because the behavior is clearly
760    * documented so it's not expected to change.
761    */
762   @GwtIncompatible("EsayMock")
testTransformedSequentialIterationUsesBackingListIterationOnly()763   public void testTransformedSequentialIterationUsesBackingListIterationOnly() {
764     List<Integer> randomAccessList = Lists.newArrayList(SOME_SEQUENTIAL_LIST);
765     ListIterator<Integer> sampleListIterator =
766         SOME_SEQUENTIAL_LIST.listIterator();
767     List<Integer> listMock = EasyMock.createMock(IntegerList.class);
768     EasyMock.expect(listMock.size()).andReturn(SOME_SEQUENTIAL_LIST.size());
769     EasyMock.expect(listMock.listIterator(0)).andReturn(sampleListIterator);
770     EasyMock.replay(listMock);
771     List<String> transform = Lists.transform(listMock, SOME_FUNCTION);
772     assertTrue(Iterables.elementsEqual(
773         transform, Lists.transform(randomAccessList, SOME_FUNCTION)));
774     EasyMock.verify(listMock);
775   }
776 
assertTransformIterator(List<String> list)777   private static void assertTransformIterator(List<String> list) {
778     Iterator<String> iterator = list.iterator();
779     assertTrue(iterator.hasNext());
780     assertEquals("1", iterator.next());
781     assertTrue(iterator.hasNext());
782     assertEquals("2", iterator.next());
783     assertTrue(iterator.hasNext());
784     assertEquals("3", iterator.next());
785     assertTrue(iterator.hasNext());
786     assertEquals("4", iterator.next());
787     assertFalse(iterator.hasNext());
788     try {
789       iterator.next();
790       fail("did not detect end of list");
791     } catch (NoSuchElementException expected) {}
792     iterator.remove();
793     assertEquals(asList("1", "2", "3"), list);
794     assertFalse(iterator.hasNext());
795   }
796 
testPartition_badSize()797   public void testPartition_badSize() {
798     List<Integer> source = Collections.singletonList(1);
799     try {
800       Lists.partition(source, 0);
801       fail();
802     } catch (IllegalArgumentException expected) {
803     }
804   }
805 
testPartition_empty()806   public void testPartition_empty() {
807     List<Integer> source = Collections.emptyList();
808     List<List<Integer>> partitions = Lists.partition(source, 1);
809     assertTrue(partitions.isEmpty());
810     assertEquals(0, partitions.size());
811   }
812 
testPartition_1_1()813   public void testPartition_1_1() {
814     List<Integer> source = Collections.singletonList(1);
815     List<List<Integer>> partitions = Lists.partition(source, 1);
816     assertEquals(1, partitions.size());
817     assertEquals(Collections.singletonList(1), partitions.get(0));
818   }
819 
testPartition_1_2()820   public void testPartition_1_2() {
821     List<Integer> source = Collections.singletonList(1);
822     List<List<Integer>> partitions = Lists.partition(source, 2);
823     assertEquals(1, partitions.size());
824     assertEquals(Collections.singletonList(1), partitions.get(0));
825   }
826 
testPartition_2_1()827   public void testPartition_2_1() {
828     List<Integer> source = asList(1, 2);
829     List<List<Integer>> partitions = Lists.partition(source, 1);
830     assertEquals(2, partitions.size());
831     assertEquals(Collections.singletonList(1), partitions.get(0));
832     assertEquals(Collections.singletonList(2), partitions.get(1));
833   }
834 
testPartition_3_2()835   public void testPartition_3_2() {
836     List<Integer> source = asList(1, 2, 3);
837     List<List<Integer>> partitions = Lists.partition(source, 2);
838     assertEquals(2, partitions.size());
839     assertEquals(asList(1, 2), partitions.get(0));
840     assertEquals(asList(3), partitions.get(1));
841   }
842 
843   @GwtIncompatible("ArrayList.subList doesn't implement RandomAccess in GWT.")
testPartitionRandomAccessTrue()844   public void testPartitionRandomAccessTrue() {
845     List<Integer> source = asList(1, 2, 3);
846     List<List<Integer>> partitions = Lists.partition(source, 2);
847 
848     assertTrue("partition should be RandomAccess, but not: "
849         + partitions.getClass(),
850         partitions instanceof RandomAccess);
851 
852     assertTrue("partition[0] should be RandomAccess, but not: "
853         + partitions.get(0).getClass(),
854         partitions.get(0) instanceof RandomAccess);
855 
856     assertTrue("partition[1] should be RandomAccess, but not: "
857         + partitions.get(1).getClass(),
858         partitions.get(1) instanceof RandomAccess);
859   }
860 
testPartitionRandomAccessFalse()861   public void testPartitionRandomAccessFalse() {
862     List<Integer> source = Lists.newLinkedList(asList(1, 2, 3));
863     List<List<Integer>> partitions = Lists.partition(source, 2);
864     assertFalse(partitions instanceof RandomAccess);
865     assertFalse(partitions.get(0) instanceof RandomAccess);
866     assertFalse(partitions.get(1) instanceof RandomAccess);
867   }
868 
869   // TODO: use the ListTestSuiteBuilder
870 
testPartition_view()871   public void testPartition_view() {
872     List<Integer> list = asList(1, 2, 3);
873     List<List<Integer>> partitions = Lists.partition(list, 3);
874 
875     // Changes before the partition is retrieved are reflected
876     list.set(0, 3);
877 
878     Iterator<List<Integer>> iterator = partitions.iterator();
879 
880     // Changes before the partition is retrieved are reflected
881     list.set(1, 4);
882 
883     List<Integer> first = iterator.next();
884 
885     // Changes after are too (unlike Iterables.partition)
886     list.set(2, 5);
887 
888     assertEquals(asList(3, 4, 5), first);
889 
890     // Changes to a sublist also write through to the original list
891     first.set(1, 6);
892     assertEquals(asList(3, 6, 5), list);
893   }
894 
testPartitionSize_1()895   public void testPartitionSize_1() {
896     List<Integer> list = asList(1, 2, 3);
897     assertEquals(1, Lists.partition(list, Integer.MAX_VALUE).size());
898     assertEquals(1, Lists.partition(list, Integer.MAX_VALUE - 1).size());
899   }
900 
901   @GwtIncompatible("cannot do such a big explicit copy")
testPartitionSize_2()902   public void testPartitionSize_2() {
903     assertEquals(2, Lists.partition(Collections.nCopies(0x40000001, 1), 0x40000000).size());
904   }
905 }
906