ListsTest.java revision 0888a09821a98ac0680fad765217302858e70fa4 
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
17package com.google.common.collect;
18
19import static com.google.common.base.Preconditions.checkNotNull;
20import static com.google.common.collect.testing.IteratorFeature.UNMODIFIABLE;
21import static java.util.Arrays.asList;
22import static java.util.Collections.singletonList;
23import static org.truth0.Truth.ASSERT;
24
25import com.google.common.annotations.GwtCompatible;
26import com.google.common.annotations.GwtIncompatible;
27import com.google.common.base.Function;
28import com.google.common.base.Functions;
29import com.google.common.collect.testing.IteratorTester;
30import com.google.common.collect.testing.ListTestSuiteBuilder;
31import com.google.common.collect.testing.TestStringListGenerator;
32import com.google.common.collect.testing.features.CollectionFeature;
33import com.google.common.collect.testing.features.CollectionSize;
34import com.google.common.collect.testing.features.ListFeature;
35import com.google.common.collect.testing.google.ListGenerators.CharactersOfCharSequenceGenerator;
36import com.google.common.collect.testing.google.ListGenerators.CharactersOfStringGenerator;
37import com.google.common.testing.NullPointerTester;
38import com.google.common.testing.SerializableTester;
39
40import junit.framework.Test;
41import junit.framework.TestCase;
42import junit.framework.TestSuite;
43
44import org.easymock.EasyMock;
45
46import java.io.Serializable;
47import java.util.ArrayList;
48import java.util.Collection;
49import java.util.Collections;
50import java.util.Iterator;
51import java.util.LinkedList;
52import java.util.List;
53import java.util.ListIterator;
54import java.util.NoSuchElementException;
55import java.util.RandomAccess;
56import 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)
66public 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
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
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
104    public String apply(Number n) {
105      return String.valueOf(n);
106    }
107    private static final long serialVersionUID = 0;
108  }
109
110  @GwtIncompatible("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
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
274  public void testNewArrayListEmpty() {
275    ArrayList<Integer> list = Lists.newArrayList();
276    assertEquals(Collections.emptyList(), list);
277  }
278
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
287  public void testNewArrayListWithCapacity_negative() {
288    try {
289      Lists.newArrayListWithCapacity(-1);
290      fail();
291    } catch (IllegalArgumentException expected) {
292    }
293  }
294
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
303  public void testNewArrayListWithExpectedSize_negative() {
304    try {
305      Lists.newArrayListWithExpectedSize(-1);
306      fail();
307    } catch (IllegalArgumentException expected) {
308    }
309  }
310
311  public void testNewArrayListVarArgs() {
312    ArrayList<Integer> list = Lists.newArrayList(0, 1, 1);
313    assertEquals(SOME_COLLECTION, list);
314  }
315
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
325  public void testNewArrayListFromCollection() {
326    ArrayList<Integer> list = Lists.newArrayList(SOME_COLLECTION);
327    assertEquals(SOME_COLLECTION, list);
328  }
329
330  public void testNewArrayListFromIterable() {
331    ArrayList<Integer> list = Lists.newArrayList(SOME_ITERABLE);
332    assertEquals(SOME_COLLECTION, list);
333  }
334
335  public void testNewArrayListFromIterator() {
336    ArrayList<Integer> list = Lists.newArrayList(SOME_COLLECTION.iterator());
337    assertEquals(SOME_COLLECTION, list);
338  }
339
340  public void testNewLinkedListEmpty() {
341    LinkedList<Integer> list = Lists.newLinkedList();
342    assertEquals(Collections.emptyList(), list);
343  }
344
345  public void testNewLinkedListFromCollection() {
346    LinkedList<Integer> list = Lists.newLinkedList(SOME_COLLECTION);
347    assertEquals(SOME_COLLECTION, list);
348  }
349
350  public void testNewLinkedListFromIterable() {
351    LinkedList<Integer> list = Lists.newLinkedList(SOME_ITERABLE);
352    assertEquals(SOME_COLLECTION, list);
353  }
354
355  @GwtIncompatible("CopyOnWriteArrayList")
356  public void testNewCOWALEmpty() {
357    CopyOnWriteArrayList<Integer> list = Lists.newCopyOnWriteArrayList();
358    assertEquals(Collections.emptyList(), list);
359  }
360
361  @GwtIncompatible("CopyOnWriteArrayList")
362  public void testNewCOWALFromIterable() {
363    CopyOnWriteArrayList<Integer> list = Lists.newCopyOnWriteArrayList(
364        SOME_ITERABLE);
365    assertEquals(SOME_COLLECTION, list);
366  }
367
368  @GwtIncompatible("NullPointerTester")
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   */
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")
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
420  private void checkFooBarBazList(List<String> list) {
421    ASSERT.that(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
430  public void testAsList1Small() {
431    List<String> list = Lists.asList("foo", new String[0]);
432    ASSERT.that(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
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")
461  public void testAsList2Small() {
462    List<String> list = Lists.asList("foo", "bar", new String[0]);
463    ASSERT.that(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
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
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
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
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
529  private static <E> List<E> list(E... elements) {
530    return ImmutableList.copyOf(elements);
531  }
532
533  @SuppressWarnings("unchecked") // varargs!
534  public void testCartesianProduct_binary1x1() {
535    ASSERT.that(Lists.cartesianProduct(list(1), list(2))).has().item(list(1, 2));
536  }
537
538  @SuppressWarnings("unchecked") // varargs!
539  public void testCartesianProduct_binary1x2() {
540    ASSERT.that(Lists.cartesianProduct(list(1), list(2, 3)))
541        .has().exactly(list(1, 2), list(1, 3)).inOrder();
542  }
543
544  @SuppressWarnings("unchecked") // varargs!
545  public void testCartesianProduct_binary2x2() {
546    ASSERT.that(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!
551  public void testCartesianProduct_2x2x2() {
552    ASSERT.that(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!
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!
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    ASSERT.that(Lists.<Object>cartesianProduct(x, y))
578        .has().exactly(exp1, exp2, exp3, exp4).inOrder();
579  }
580
581  @SuppressWarnings("unchecked") // varargs!
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
590  public void testTransformHashCodeRandomAccess() {
591    List<String> list = Lists.transform(SOME_LIST, SOME_FUNCTION);
592    assertEquals(SOME_STRING_LIST.hashCode(), list.hashCode());
593  }
594
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
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
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
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
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
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
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
662  public void testTransformRandomAccess() {
663    List<String> list = Lists.transform(SOME_LIST, SOME_FUNCTION);
664    assertTrue(list instanceof RandomAccess);
665  }
666
667  public void testTransformSequential() {
668    List<String> list = Lists.transform(SOME_SEQUENTIAL_LIST, SOME_FUNCTION);
669    assertFalse(list instanceof RandomAccess);
670  }
671
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
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
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
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
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
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")
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
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
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
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
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
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
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
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.")
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
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
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
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")
902  public void testPartitionSize_2() {
903    assertEquals(2, Lists.partition(Collections.nCopies(0x40000001, 1), 0x40000000).size());
904  }
905}
906