10888a09821a98ac0680fad765217302858e70fa4Paul Duffin/* 20888a09821a98ac0680fad765217302858e70fa4Paul Duffin * Copyright (C) 2007 The Guava Authors 30888a09821a98ac0680fad765217302858e70fa4Paul Duffin * 40888a09821a98ac0680fad765217302858e70fa4Paul Duffin * Licensed under the Apache License, Version 2.0 (the "License"); 50888a09821a98ac0680fad765217302858e70fa4Paul Duffin * you may not use this file except in compliance with the License. 60888a09821a98ac0680fad765217302858e70fa4Paul Duffin * You may obtain a copy of the License at 70888a09821a98ac0680fad765217302858e70fa4Paul Duffin * 80888a09821a98ac0680fad765217302858e70fa4Paul Duffin * http://www.apache.org/licenses/LICENSE-2.0 90888a09821a98ac0680fad765217302858e70fa4Paul Duffin * 100888a09821a98ac0680fad765217302858e70fa4Paul Duffin * Unless required by applicable law or agreed to in writing, software 110888a09821a98ac0680fad765217302858e70fa4Paul Duffin * distributed under the License is distributed on an "AS IS" BASIS, 120888a09821a98ac0680fad765217302858e70fa4Paul Duffin * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 130888a09821a98ac0680fad765217302858e70fa4Paul Duffin * See the License for the specific language governing permissions and 140888a09821a98ac0680fad765217302858e70fa4Paul Duffin * limitations under the License. 150888a09821a98ac0680fad765217302858e70fa4Paul Duffin */ 160888a09821a98ac0680fad765217302858e70fa4Paul Duffin 170888a09821a98ac0680fad765217302858e70fa4Paul Duffinpackage com.google.common.collect; 180888a09821a98ac0680fad765217302858e70fa4Paul Duffin 190888a09821a98ac0680fad765217302858e70fa4Paul Duffinimport static com.google.common.base.Preconditions.checkArgument; 200888a09821a98ac0680fad765217302858e70fa4Paul Duffinimport static com.google.common.base.Preconditions.checkElementIndex; 210888a09821a98ac0680fad765217302858e70fa4Paul Duffinimport static com.google.common.base.Preconditions.checkNotNull; 220888a09821a98ac0680fad765217302858e70fa4Paul Duffinimport static com.google.common.base.Preconditions.checkPositionIndex; 230888a09821a98ac0680fad765217302858e70fa4Paul Duffinimport static com.google.common.base.Preconditions.checkPositionIndexes; 240888a09821a98ac0680fad765217302858e70fa4Paul Duffinimport static com.google.common.base.Preconditions.checkState; 250888a09821a98ac0680fad765217302858e70fa4Paul Duffinimport static com.google.common.collect.CollectPreconditions.checkNonnegative; 260888a09821a98ac0680fad765217302858e70fa4Paul Duffinimport static com.google.common.collect.CollectPreconditions.checkRemove; 270888a09821a98ac0680fad765217302858e70fa4Paul Duffin 280888a09821a98ac0680fad765217302858e70fa4Paul Duffinimport com.google.common.annotations.Beta; 290888a09821a98ac0680fad765217302858e70fa4Paul Duffinimport com.google.common.annotations.GwtCompatible; 300888a09821a98ac0680fad765217302858e70fa4Paul Duffinimport com.google.common.annotations.VisibleForTesting; 310888a09821a98ac0680fad765217302858e70fa4Paul Duffinimport com.google.common.base.Function; 320888a09821a98ac0680fad765217302858e70fa4Paul Duffinimport com.google.common.base.Objects; 330888a09821a98ac0680fad765217302858e70fa4Paul Duffinimport com.google.common.math.IntMath; 340888a09821a98ac0680fad765217302858e70fa4Paul Duffinimport com.google.common.primitives.Ints; 350888a09821a98ac0680fad765217302858e70fa4Paul Duffin 360888a09821a98ac0680fad765217302858e70fa4Paul Duffinimport java.io.Serializable; 370888a09821a98ac0680fad765217302858e70fa4Paul Duffinimport java.math.RoundingMode; 380888a09821a98ac0680fad765217302858e70fa4Paul Duffinimport java.util.AbstractList; 390888a09821a98ac0680fad765217302858e70fa4Paul Duffinimport java.util.AbstractSequentialList; 400888a09821a98ac0680fad765217302858e70fa4Paul Duffinimport java.util.ArrayList; 410888a09821a98ac0680fad765217302858e70fa4Paul Duffinimport java.util.Arrays; 420888a09821a98ac0680fad765217302858e70fa4Paul Duffinimport java.util.Collection; 430888a09821a98ac0680fad765217302858e70fa4Paul Duffinimport java.util.Collections; 440888a09821a98ac0680fad765217302858e70fa4Paul Duffinimport java.util.Iterator; 450888a09821a98ac0680fad765217302858e70fa4Paul Duffinimport java.util.LinkedList; 460888a09821a98ac0680fad765217302858e70fa4Paul Duffinimport java.util.List; 470888a09821a98ac0680fad765217302858e70fa4Paul Duffinimport java.util.ListIterator; 480888a09821a98ac0680fad765217302858e70fa4Paul Duffinimport java.util.NoSuchElementException; 490888a09821a98ac0680fad765217302858e70fa4Paul Duffinimport java.util.RandomAccess; 500888a09821a98ac0680fad765217302858e70fa4Paul Duffin 510888a09821a98ac0680fad765217302858e70fa4Paul Duffinimport javax.annotation.Nullable; 520888a09821a98ac0680fad765217302858e70fa4Paul Duffin 530888a09821a98ac0680fad765217302858e70fa4Paul Duffin/** 540888a09821a98ac0680fad765217302858e70fa4Paul Duffin * Static utility methods pertaining to {@link List} instances. Also see this 550888a09821a98ac0680fad765217302858e70fa4Paul Duffin * class's counterparts {@link Sets}, {@link Maps} and {@link Queues}. 560888a09821a98ac0680fad765217302858e70fa4Paul Duffin * 570888a09821a98ac0680fad765217302858e70fa4Paul Duffin * <p>See the Guava User Guide article on <a href= 580888a09821a98ac0680fad765217302858e70fa4Paul Duffin * "http://code.google.com/p/guava-libraries/wiki/CollectionUtilitiesExplained#Lists"> 590888a09821a98ac0680fad765217302858e70fa4Paul Duffin * {@code Lists}</a>. 600888a09821a98ac0680fad765217302858e70fa4Paul Duffin * 610888a09821a98ac0680fad765217302858e70fa4Paul Duffin * @author Kevin Bourrillion 620888a09821a98ac0680fad765217302858e70fa4Paul Duffin * @author Mike Bostock 630888a09821a98ac0680fad765217302858e70fa4Paul Duffin * @author Louis Wasserman 640888a09821a98ac0680fad765217302858e70fa4Paul Duffin * @since 2.0 (imported from Google Collections Library) 650888a09821a98ac0680fad765217302858e70fa4Paul Duffin */ 660888a09821a98ac0680fad765217302858e70fa4Paul Duffin@GwtCompatible(emulated = true) 670888a09821a98ac0680fad765217302858e70fa4Paul Duffinpublic final class Lists { 680888a09821a98ac0680fad765217302858e70fa4Paul Duffin private Lists() {} 690888a09821a98ac0680fad765217302858e70fa4Paul Duffin 700888a09821a98ac0680fad765217302858e70fa4Paul Duffin // ArrayList 710888a09821a98ac0680fad765217302858e70fa4Paul Duffin 720888a09821a98ac0680fad765217302858e70fa4Paul Duffin /** 733ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * Creates a <i>mutable</i>, empty {@code ArrayList} instance (for Java 6 and 743ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * earlier). 750888a09821a98ac0680fad765217302858e70fa4Paul Duffin * 760888a09821a98ac0680fad765217302858e70fa4Paul Duffin * <p><b>Note:</b> if mutability is not required, use {@link 770888a09821a98ac0680fad765217302858e70fa4Paul Duffin * ImmutableList#of()} instead. 780888a09821a98ac0680fad765217302858e70fa4Paul Duffin * 793ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * <p><b>Note for Java 7 and later:</b> this method is now unnecessary and 803ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * should be treated as deprecated. Instead, use the {@code ArrayList} 813ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * {@linkplain ArrayList#ArrayList() constructor} directly, taking advantage 823ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * of the new <a href="http://goo.gl/iz2Wi">"diamond" syntax</a>. 830888a09821a98ac0680fad765217302858e70fa4Paul Duffin */ 840888a09821a98ac0680fad765217302858e70fa4Paul Duffin @GwtCompatible(serializable = true) 850888a09821a98ac0680fad765217302858e70fa4Paul Duffin public static <E> ArrayList<E> newArrayList() { 860888a09821a98ac0680fad765217302858e70fa4Paul Duffin return new ArrayList<E>(); 870888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 880888a09821a98ac0680fad765217302858e70fa4Paul Duffin 890888a09821a98ac0680fad765217302858e70fa4Paul Duffin /** 900888a09821a98ac0680fad765217302858e70fa4Paul Duffin * Creates a <i>mutable</i> {@code ArrayList} instance containing the given 910888a09821a98ac0680fad765217302858e70fa4Paul Duffin * elements. 920888a09821a98ac0680fad765217302858e70fa4Paul Duffin * 933ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * <p><b>Note:</b> essentially the only reason to use this method is when you 943ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * will need to add or remove elements later. Otherwise, for non-null elements 953ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * use {@link ImmutableList#of()} (for varargs) or {@link 963ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * ImmutableList#copyOf(Object[])} (for an array) instead. If any elements 973ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * might be null, or you need support for {@link List#set(int, Object)}, use 983ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * {@link Arrays#asList}. 990888a09821a98ac0680fad765217302858e70fa4Paul Duffin * 1003ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * <p>Note that even when you do need the ability to add or remove, this method 1013ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * provides only a tiny bit of syntactic sugar for {@code newArrayList(}{@link 1023ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * Arrays#asList asList}{@code (...))}, or for creating an empty list then 1033ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * calling {@link Collections#addAll}. This method is not actually very useful 1043ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * and will likely be deprecated in the future. 1050888a09821a98ac0680fad765217302858e70fa4Paul Duffin */ 1060888a09821a98ac0680fad765217302858e70fa4Paul Duffin @GwtCompatible(serializable = true) 1070888a09821a98ac0680fad765217302858e70fa4Paul Duffin public static <E> ArrayList<E> newArrayList(E... elements) { 1080888a09821a98ac0680fad765217302858e70fa4Paul Duffin checkNotNull(elements); // for GWT 1090888a09821a98ac0680fad765217302858e70fa4Paul Duffin // Avoid integer overflow when a large array is passed in 1100888a09821a98ac0680fad765217302858e70fa4Paul Duffin int capacity = computeArrayListCapacity(elements.length); 1110888a09821a98ac0680fad765217302858e70fa4Paul Duffin ArrayList<E> list = new ArrayList<E>(capacity); 1120888a09821a98ac0680fad765217302858e70fa4Paul Duffin Collections.addAll(list, elements); 1130888a09821a98ac0680fad765217302858e70fa4Paul Duffin return list; 1140888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 1150888a09821a98ac0680fad765217302858e70fa4Paul Duffin 1160888a09821a98ac0680fad765217302858e70fa4Paul Duffin @VisibleForTesting static int computeArrayListCapacity(int arraySize) { 1170888a09821a98ac0680fad765217302858e70fa4Paul Duffin checkNonnegative(arraySize, "arraySize"); 1180888a09821a98ac0680fad765217302858e70fa4Paul Duffin 1190888a09821a98ac0680fad765217302858e70fa4Paul Duffin // TODO(kevinb): Figure out the right behavior, and document it 1200888a09821a98ac0680fad765217302858e70fa4Paul Duffin return Ints.saturatedCast(5L + arraySize + (arraySize / 10)); 1210888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 1220888a09821a98ac0680fad765217302858e70fa4Paul Duffin 1230888a09821a98ac0680fad765217302858e70fa4Paul Duffin /** 1240888a09821a98ac0680fad765217302858e70fa4Paul Duffin * Creates a <i>mutable</i> {@code ArrayList} instance containing the given 1253ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * elements; a very thin shortcut for creating an empty list then calling 1263ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * {@link Iterables#addAll}. 1270888a09821a98ac0680fad765217302858e70fa4Paul Duffin * 1280888a09821a98ac0680fad765217302858e70fa4Paul Duffin * <p><b>Note:</b> if mutability is not required and the elements are 1293ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * non-null, use {@link ImmutableList#copyOf(Iterable)} instead. (Or, change 1303ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * {@code elements} to be a {@link FluentIterable} and call 1313ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * {@code elements.toList()}.) 1320888a09821a98ac0680fad765217302858e70fa4Paul Duffin * 1333ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * <p><b>Note for Java 7 and later:</b> if {@code elements} is a {@link 1343ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * Collection}, you don't need this method. Use the {@code ArrayList} 1353ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * {@linkplain ArrayList#ArrayList(Collection) constructor} directly, taking 1363ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * advantage of the new <a href="http://goo.gl/iz2Wi">"diamond" syntax</a>. 1370888a09821a98ac0680fad765217302858e70fa4Paul Duffin */ 1380888a09821a98ac0680fad765217302858e70fa4Paul Duffin @GwtCompatible(serializable = true) 1390888a09821a98ac0680fad765217302858e70fa4Paul Duffin public static <E> ArrayList<E> newArrayList(Iterable<? extends E> elements) { 1400888a09821a98ac0680fad765217302858e70fa4Paul Duffin checkNotNull(elements); // for GWT 1410888a09821a98ac0680fad765217302858e70fa4Paul Duffin // Let ArrayList's sizing logic work, if possible 1420888a09821a98ac0680fad765217302858e70fa4Paul Duffin return (elements instanceof Collection) 1430888a09821a98ac0680fad765217302858e70fa4Paul Duffin ? new ArrayList<E>(Collections2.cast(elements)) 1440888a09821a98ac0680fad765217302858e70fa4Paul Duffin : newArrayList(elements.iterator()); 1450888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 1460888a09821a98ac0680fad765217302858e70fa4Paul Duffin 1470888a09821a98ac0680fad765217302858e70fa4Paul Duffin /** 1480888a09821a98ac0680fad765217302858e70fa4Paul Duffin * Creates a <i>mutable</i> {@code ArrayList} instance containing the given 1493ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * elements; a very thin shortcut for creating an empty list and then calling 1503ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * {@link Iterators#addAll}. 1510888a09821a98ac0680fad765217302858e70fa4Paul Duffin * 1520888a09821a98ac0680fad765217302858e70fa4Paul Duffin * <p><b>Note:</b> if mutability is not required and the elements are 1530888a09821a98ac0680fad765217302858e70fa4Paul Duffin * non-null, use {@link ImmutableList#copyOf(Iterator)} instead. 1540888a09821a98ac0680fad765217302858e70fa4Paul Duffin */ 1550888a09821a98ac0680fad765217302858e70fa4Paul Duffin @GwtCompatible(serializable = true) 1560888a09821a98ac0680fad765217302858e70fa4Paul Duffin public static <E> ArrayList<E> newArrayList(Iterator<? extends E> elements) { 1570888a09821a98ac0680fad765217302858e70fa4Paul Duffin ArrayList<E> list = newArrayList(); 1580888a09821a98ac0680fad765217302858e70fa4Paul Duffin Iterators.addAll(list, elements); 1590888a09821a98ac0680fad765217302858e70fa4Paul Duffin return list; 1600888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 1610888a09821a98ac0680fad765217302858e70fa4Paul Duffin 1620888a09821a98ac0680fad765217302858e70fa4Paul Duffin /** 1633ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * Creates an {@code ArrayList} instance backed by an array with the specified 1643ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * initial size; simply delegates to {@link ArrayList#ArrayList(int)}. 1650888a09821a98ac0680fad765217302858e70fa4Paul Duffin * 1663ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * <p><b>Note for Java 7 and later:</b> this method is now unnecessary and 1673ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * should be treated as deprecated. Instead, use {@code new }{@link 1683ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * ArrayList#ArrayList(int) ArrayList}{@code <>(int)} directly, taking 1693ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * advantage of the new <a href="http://goo.gl/iz2Wi">"diamond" syntax</a>. 1703ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * (Unlike here, there is no risk of overload ambiguity, since the {@code 1713ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * ArrayList} constructors very wisely did not accept varargs.) 1720888a09821a98ac0680fad765217302858e70fa4Paul Duffin * 1730888a09821a98ac0680fad765217302858e70fa4Paul Duffin * @param initialArraySize the exact size of the initial backing array for 1740888a09821a98ac0680fad765217302858e70fa4Paul Duffin * the returned array list ({@code ArrayList} documentation calls this 1750888a09821a98ac0680fad765217302858e70fa4Paul Duffin * value the "capacity") 1760888a09821a98ac0680fad765217302858e70fa4Paul Duffin * @return a new, empty {@code ArrayList} which is guaranteed not to resize 1770888a09821a98ac0680fad765217302858e70fa4Paul Duffin * itself unless its size reaches {@code initialArraySize + 1} 1780888a09821a98ac0680fad765217302858e70fa4Paul Duffin * @throws IllegalArgumentException if {@code initialArraySize} is negative 1790888a09821a98ac0680fad765217302858e70fa4Paul Duffin */ 1800888a09821a98ac0680fad765217302858e70fa4Paul Duffin @GwtCompatible(serializable = true) 1810888a09821a98ac0680fad765217302858e70fa4Paul Duffin public static <E> ArrayList<E> newArrayListWithCapacity( 1820888a09821a98ac0680fad765217302858e70fa4Paul Duffin int initialArraySize) { 1830888a09821a98ac0680fad765217302858e70fa4Paul Duffin checkNonnegative(initialArraySize, "initialArraySize"); // for GWT. 1840888a09821a98ac0680fad765217302858e70fa4Paul Duffin return new ArrayList<E>(initialArraySize); 1850888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 1860888a09821a98ac0680fad765217302858e70fa4Paul Duffin 1870888a09821a98ac0680fad765217302858e70fa4Paul Duffin /** 1883ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * Creates an {@code ArrayList} instance to hold {@code estimatedSize} 1893ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * elements, <i>plus</i> an unspecified amount of padding; you almost 1903ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * certainly mean to call {@link #newArrayListWithCapacity} (see that method 1913ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * for further advice on usage). 1920888a09821a98ac0680fad765217302858e70fa4Paul Duffin * 1933ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * <p><b>Note:</b> This method will soon be deprecated. Even in the rare case 1943ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * that you do want some amount of padding, it's best if you choose your 1953ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * desired amount explicitly. 1960888a09821a98ac0680fad765217302858e70fa4Paul Duffin * 1970888a09821a98ac0680fad765217302858e70fa4Paul Duffin * @param estimatedSize an estimate of the eventual {@link List#size()} of 1980888a09821a98ac0680fad765217302858e70fa4Paul Duffin * the new list 1990888a09821a98ac0680fad765217302858e70fa4Paul Duffin * @return a new, empty {@code ArrayList}, sized appropriately to hold the 2000888a09821a98ac0680fad765217302858e70fa4Paul Duffin * estimated number of elements 2010888a09821a98ac0680fad765217302858e70fa4Paul Duffin * @throws IllegalArgumentException if {@code estimatedSize} is negative 2020888a09821a98ac0680fad765217302858e70fa4Paul Duffin */ 2030888a09821a98ac0680fad765217302858e70fa4Paul Duffin @GwtCompatible(serializable = true) 2040888a09821a98ac0680fad765217302858e70fa4Paul Duffin public static <E> ArrayList<E> newArrayListWithExpectedSize( 2050888a09821a98ac0680fad765217302858e70fa4Paul Duffin int estimatedSize) { 2060888a09821a98ac0680fad765217302858e70fa4Paul Duffin return new ArrayList<E>(computeArrayListCapacity(estimatedSize)); 2070888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 2080888a09821a98ac0680fad765217302858e70fa4Paul Duffin 2090888a09821a98ac0680fad765217302858e70fa4Paul Duffin // LinkedList 2100888a09821a98ac0680fad765217302858e70fa4Paul Duffin 2110888a09821a98ac0680fad765217302858e70fa4Paul Duffin /** 2123ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * Creates a <i>mutable</i>, empty {@code LinkedList} instance (for Java 6 and 2133ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * earlier). 2140888a09821a98ac0680fad765217302858e70fa4Paul Duffin * 2153ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * <p><b>Note:</b> if you won't be adding any elements to the list, use {@link 2163ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * ImmutableList#of()} instead. 2173ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * 2183ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * <p><b>Performance note:</b> {@link ArrayList} and {@link 2193ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * java.util.ArrayDeque} consistently outperform {@code LinkedList} except in 2203ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * certain rare and specific situations. Unless you have spent a lot of time 2213ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * benchmarking your specific needs, use one of those instead. 2220888a09821a98ac0680fad765217302858e70fa4Paul Duffin * 2233ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * <p><b>Note for Java 7 and later:</b> this method is now unnecessary and 2243ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * should be treated as deprecated. Instead, use the {@code LinkedList} 2253ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * {@linkplain LinkedList#LinkedList() constructor} directly, taking advantage 2263ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * of the new <a href="http://goo.gl/iz2Wi">"diamond" syntax</a>. 2270888a09821a98ac0680fad765217302858e70fa4Paul Duffin */ 2280888a09821a98ac0680fad765217302858e70fa4Paul Duffin @GwtCompatible(serializable = true) 2290888a09821a98ac0680fad765217302858e70fa4Paul Duffin public static <E> LinkedList<E> newLinkedList() { 2300888a09821a98ac0680fad765217302858e70fa4Paul Duffin return new LinkedList<E>(); 2310888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 2320888a09821a98ac0680fad765217302858e70fa4Paul Duffin 2330888a09821a98ac0680fad765217302858e70fa4Paul Duffin /** 2343ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * Creates a <i>mutable</i> {@code LinkedList} instance containing the given 2353ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * elements; a very thin shortcut for creating an empty list then calling 2363ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * {@link Iterables#addAll}. 2373ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * 2383ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * <p><b>Note:</b> if mutability is not required and the elements are 2393ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * non-null, use {@link ImmutableList#copyOf(Iterable)} instead. (Or, change 2403ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * {@code elements} to be a {@link FluentIterable} and call 2413ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * {@code elements.toList()}.) 2423ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * 2433ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * <p><b>Performance note:</b> {@link ArrayList} and {@link 2443ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * java.util.ArrayDeque} consistently outperform {@code LinkedList} except in 2453ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * certain rare and specific situations. Unless you have spent a lot of time 2463ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * benchmarking your specific needs, use one of those instead. 2470888a09821a98ac0680fad765217302858e70fa4Paul Duffin * 2483ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * <p><b>Note for Java 7 and later:</b> if {@code elements} is a {@link 2493ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * Collection}, you don't need this method. Use the {@code LinkedList} 2503ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * {@linkplain LinkedList#LinkedList(Collection) constructor} directly, taking 2513ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * advantage of the new <a href="http://goo.gl/iz2Wi">"diamond" syntax</a>. 2520888a09821a98ac0680fad765217302858e70fa4Paul Duffin */ 2530888a09821a98ac0680fad765217302858e70fa4Paul Duffin @GwtCompatible(serializable = true) 2540888a09821a98ac0680fad765217302858e70fa4Paul Duffin public static <E> LinkedList<E> newLinkedList( 2550888a09821a98ac0680fad765217302858e70fa4Paul Duffin Iterable<? extends E> elements) { 2560888a09821a98ac0680fad765217302858e70fa4Paul Duffin LinkedList<E> list = newLinkedList(); 2570888a09821a98ac0680fad765217302858e70fa4Paul Duffin Iterables.addAll(list, elements); 2580888a09821a98ac0680fad765217302858e70fa4Paul Duffin return list; 2590888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 2600888a09821a98ac0680fad765217302858e70fa4Paul Duffin 2610888a09821a98ac0680fad765217302858e70fa4Paul Duffin /** 2620888a09821a98ac0680fad765217302858e70fa4Paul Duffin * Returns an unmodifiable list containing the specified first element and 2630888a09821a98ac0680fad765217302858e70fa4Paul Duffin * backed by the specified array of additional elements. Changes to the {@code 2640888a09821a98ac0680fad765217302858e70fa4Paul Duffin * rest} array will be reflected in the returned list. Unlike {@link 2650888a09821a98ac0680fad765217302858e70fa4Paul Duffin * Arrays#asList}, the returned list is unmodifiable. 2660888a09821a98ac0680fad765217302858e70fa4Paul Duffin * 2670888a09821a98ac0680fad765217302858e70fa4Paul Duffin * <p>This is useful when a varargs method needs to use a signature such as 2680888a09821a98ac0680fad765217302858e70fa4Paul Duffin * {@code (Foo firstFoo, Foo... moreFoos)}, in order to avoid overload 2690888a09821a98ac0680fad765217302858e70fa4Paul Duffin * ambiguity or to enforce a minimum argument count. 2700888a09821a98ac0680fad765217302858e70fa4Paul Duffin * 2710888a09821a98ac0680fad765217302858e70fa4Paul Duffin * <p>The returned list is serializable and implements {@link RandomAccess}. 2720888a09821a98ac0680fad765217302858e70fa4Paul Duffin * 2730888a09821a98ac0680fad765217302858e70fa4Paul Duffin * @param first the first element 2740888a09821a98ac0680fad765217302858e70fa4Paul Duffin * @param rest an array of additional elements, possibly empty 2750888a09821a98ac0680fad765217302858e70fa4Paul Duffin * @return an unmodifiable list containing the specified elements 2760888a09821a98ac0680fad765217302858e70fa4Paul Duffin */ 2770888a09821a98ac0680fad765217302858e70fa4Paul Duffin public static <E> List<E> asList(@Nullable E first, E[] rest) { 2780888a09821a98ac0680fad765217302858e70fa4Paul Duffin return new OnePlusArrayList<E>(first, rest); 2790888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 2800888a09821a98ac0680fad765217302858e70fa4Paul Duffin 2810888a09821a98ac0680fad765217302858e70fa4Paul Duffin /** @see Lists#asList(Object, Object[]) */ 2820888a09821a98ac0680fad765217302858e70fa4Paul Duffin private static class OnePlusArrayList<E> extends AbstractList<E> 2830888a09821a98ac0680fad765217302858e70fa4Paul Duffin implements Serializable, RandomAccess { 2840888a09821a98ac0680fad765217302858e70fa4Paul Duffin final E first; 2850888a09821a98ac0680fad765217302858e70fa4Paul Duffin final E[] rest; 2860888a09821a98ac0680fad765217302858e70fa4Paul Duffin 2870888a09821a98ac0680fad765217302858e70fa4Paul Duffin OnePlusArrayList(@Nullable E first, E[] rest) { 2880888a09821a98ac0680fad765217302858e70fa4Paul Duffin this.first = first; 2890888a09821a98ac0680fad765217302858e70fa4Paul Duffin this.rest = checkNotNull(rest); 2900888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 2910888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Override public int size() { 2920888a09821a98ac0680fad765217302858e70fa4Paul Duffin return rest.length + 1; 2930888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 2940888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Override public E get(int index) { 2950888a09821a98ac0680fad765217302858e70fa4Paul Duffin // check explicitly so the IOOBE will have the right message 2960888a09821a98ac0680fad765217302858e70fa4Paul Duffin checkElementIndex(index, size()); 2970888a09821a98ac0680fad765217302858e70fa4Paul Duffin return (index == 0) ? first : rest[index - 1]; 2980888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 2990888a09821a98ac0680fad765217302858e70fa4Paul Duffin private static final long serialVersionUID = 0; 3000888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 3010888a09821a98ac0680fad765217302858e70fa4Paul Duffin 3020888a09821a98ac0680fad765217302858e70fa4Paul Duffin /** 3030888a09821a98ac0680fad765217302858e70fa4Paul Duffin * Returns an unmodifiable list containing the specified first and second 3040888a09821a98ac0680fad765217302858e70fa4Paul Duffin * element, and backed by the specified array of additional elements. Changes 3050888a09821a98ac0680fad765217302858e70fa4Paul Duffin * to the {@code rest} array will be reflected in the returned list. Unlike 3060888a09821a98ac0680fad765217302858e70fa4Paul Duffin * {@link Arrays#asList}, the returned list is unmodifiable. 3070888a09821a98ac0680fad765217302858e70fa4Paul Duffin * 3080888a09821a98ac0680fad765217302858e70fa4Paul Duffin * <p>This is useful when a varargs method needs to use a signature such as 3090888a09821a98ac0680fad765217302858e70fa4Paul Duffin * {@code (Foo firstFoo, Foo secondFoo, Foo... moreFoos)}, in order to avoid 3100888a09821a98ac0680fad765217302858e70fa4Paul Duffin * overload ambiguity or to enforce a minimum argument count. 3110888a09821a98ac0680fad765217302858e70fa4Paul Duffin * 3120888a09821a98ac0680fad765217302858e70fa4Paul Duffin * <p>The returned list is serializable and implements {@link RandomAccess}. 3130888a09821a98ac0680fad765217302858e70fa4Paul Duffin * 3140888a09821a98ac0680fad765217302858e70fa4Paul Duffin * @param first the first element 3150888a09821a98ac0680fad765217302858e70fa4Paul Duffin * @param second the second element 3160888a09821a98ac0680fad765217302858e70fa4Paul Duffin * @param rest an array of additional elements, possibly empty 3170888a09821a98ac0680fad765217302858e70fa4Paul Duffin * @return an unmodifiable list containing the specified elements 3180888a09821a98ac0680fad765217302858e70fa4Paul Duffin */ 3190888a09821a98ac0680fad765217302858e70fa4Paul Duffin public static <E> List<E> asList( 3200888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Nullable E first, @Nullable E second, E[] rest) { 3210888a09821a98ac0680fad765217302858e70fa4Paul Duffin return new TwoPlusArrayList<E>(first, second, rest); 3220888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 3230888a09821a98ac0680fad765217302858e70fa4Paul Duffin 3240888a09821a98ac0680fad765217302858e70fa4Paul Duffin /** @see Lists#asList(Object, Object, Object[]) */ 3250888a09821a98ac0680fad765217302858e70fa4Paul Duffin private static class TwoPlusArrayList<E> extends AbstractList<E> 3260888a09821a98ac0680fad765217302858e70fa4Paul Duffin implements Serializable, RandomAccess { 3270888a09821a98ac0680fad765217302858e70fa4Paul Duffin final E first; 3280888a09821a98ac0680fad765217302858e70fa4Paul Duffin final E second; 3290888a09821a98ac0680fad765217302858e70fa4Paul Duffin final E[] rest; 3300888a09821a98ac0680fad765217302858e70fa4Paul Duffin 3310888a09821a98ac0680fad765217302858e70fa4Paul Duffin TwoPlusArrayList(@Nullable E first, @Nullable E second, E[] rest) { 3320888a09821a98ac0680fad765217302858e70fa4Paul Duffin this.first = first; 3330888a09821a98ac0680fad765217302858e70fa4Paul Duffin this.second = second; 3340888a09821a98ac0680fad765217302858e70fa4Paul Duffin this.rest = checkNotNull(rest); 3350888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 3360888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Override public int size() { 3370888a09821a98ac0680fad765217302858e70fa4Paul Duffin return rest.length + 2; 3380888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 3390888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Override public E get(int index) { 3400888a09821a98ac0680fad765217302858e70fa4Paul Duffin switch (index) { 3410888a09821a98ac0680fad765217302858e70fa4Paul Duffin case 0: 3420888a09821a98ac0680fad765217302858e70fa4Paul Duffin return first; 3430888a09821a98ac0680fad765217302858e70fa4Paul Duffin case 1: 3440888a09821a98ac0680fad765217302858e70fa4Paul Duffin return second; 3450888a09821a98ac0680fad765217302858e70fa4Paul Duffin default: 3460888a09821a98ac0680fad765217302858e70fa4Paul Duffin // check explicitly so the IOOBE will have the right message 3470888a09821a98ac0680fad765217302858e70fa4Paul Duffin checkElementIndex(index, size()); 3480888a09821a98ac0680fad765217302858e70fa4Paul Duffin return rest[index - 2]; 3490888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 3500888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 3510888a09821a98ac0680fad765217302858e70fa4Paul Duffin private static final long serialVersionUID = 0; 3520888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 3530888a09821a98ac0680fad765217302858e70fa4Paul Duffin 3540888a09821a98ac0680fad765217302858e70fa4Paul Duffin /** 3550888a09821a98ac0680fad765217302858e70fa4Paul Duffin * Returns every possible list that can be formed by choosing one element 3560888a09821a98ac0680fad765217302858e70fa4Paul Duffin * from each of the given lists in order; the "n-ary 3570888a09821a98ac0680fad765217302858e70fa4Paul Duffin * <a href="http://en.wikipedia.org/wiki/Cartesian_product">Cartesian 3580888a09821a98ac0680fad765217302858e70fa4Paul Duffin * product</a>" of the lists. For example: <pre> {@code 3590888a09821a98ac0680fad765217302858e70fa4Paul Duffin * 3600888a09821a98ac0680fad765217302858e70fa4Paul Duffin * Lists.cartesianProduct(ImmutableList.of( 3610888a09821a98ac0680fad765217302858e70fa4Paul Duffin * ImmutableList.of(1, 2), 3620888a09821a98ac0680fad765217302858e70fa4Paul Duffin * ImmutableList.of("A", "B", "C")))}</pre> 3630888a09821a98ac0680fad765217302858e70fa4Paul Duffin * 3640888a09821a98ac0680fad765217302858e70fa4Paul Duffin * <p>returns a list containing six lists in the following order: 3650888a09821a98ac0680fad765217302858e70fa4Paul Duffin * 3660888a09821a98ac0680fad765217302858e70fa4Paul Duffin * <ul> 3670888a09821a98ac0680fad765217302858e70fa4Paul Duffin * <li>{@code ImmutableList.of(1, "A")} 3680888a09821a98ac0680fad765217302858e70fa4Paul Duffin * <li>{@code ImmutableList.of(1, "B")} 3690888a09821a98ac0680fad765217302858e70fa4Paul Duffin * <li>{@code ImmutableList.of(1, "C")} 3700888a09821a98ac0680fad765217302858e70fa4Paul Duffin * <li>{@code ImmutableList.of(2, "A")} 3710888a09821a98ac0680fad765217302858e70fa4Paul Duffin * <li>{@code ImmutableList.of(2, "B")} 3720888a09821a98ac0680fad765217302858e70fa4Paul Duffin * <li>{@code ImmutableList.of(2, "C")} 3730888a09821a98ac0680fad765217302858e70fa4Paul Duffin * </ul> 3740888a09821a98ac0680fad765217302858e70fa4Paul Duffin * 3750888a09821a98ac0680fad765217302858e70fa4Paul Duffin * <p>The result is guaranteed to be in the "traditional", lexicographical 3760888a09821a98ac0680fad765217302858e70fa4Paul Duffin * order for Cartesian products that you would get from nesting for loops: 3770888a09821a98ac0680fad765217302858e70fa4Paul Duffin * <pre> {@code 3780888a09821a98ac0680fad765217302858e70fa4Paul Duffin * 3790888a09821a98ac0680fad765217302858e70fa4Paul Duffin * for (B b0 : lists.get(0)) { 3800888a09821a98ac0680fad765217302858e70fa4Paul Duffin * for (B b1 : lists.get(1)) { 3810888a09821a98ac0680fad765217302858e70fa4Paul Duffin * ... 3820888a09821a98ac0680fad765217302858e70fa4Paul Duffin * ImmutableList<B> tuple = ImmutableList.of(b0, b1, ...); 3830888a09821a98ac0680fad765217302858e70fa4Paul Duffin * // operate on tuple 3840888a09821a98ac0680fad765217302858e70fa4Paul Duffin * } 3850888a09821a98ac0680fad765217302858e70fa4Paul Duffin * }}</pre> 3860888a09821a98ac0680fad765217302858e70fa4Paul Duffin * 3870888a09821a98ac0680fad765217302858e70fa4Paul Duffin * <p>Note that if any input list is empty, the Cartesian product will also be 3880888a09821a98ac0680fad765217302858e70fa4Paul Duffin * empty. If no lists at all are provided (an empty list), the resulting 3890888a09821a98ac0680fad765217302858e70fa4Paul Duffin * Cartesian product has one element, an empty list (counter-intuitive, but 3900888a09821a98ac0680fad765217302858e70fa4Paul Duffin * mathematically consistent). 3910888a09821a98ac0680fad765217302858e70fa4Paul Duffin * 3920888a09821a98ac0680fad765217302858e70fa4Paul Duffin * <p><i>Performance notes:</i> while the cartesian product of lists of size 3930888a09821a98ac0680fad765217302858e70fa4Paul Duffin * {@code m, n, p} is a list of size {@code m x n x p}, its actual memory 3940888a09821a98ac0680fad765217302858e70fa4Paul Duffin * consumption is much smaller. When the cartesian product is constructed, the 3950888a09821a98ac0680fad765217302858e70fa4Paul Duffin * input lists are merely copied. Only as the resulting list is iterated are 3960888a09821a98ac0680fad765217302858e70fa4Paul Duffin * the individual lists created, and these are not retained after iteration. 3970888a09821a98ac0680fad765217302858e70fa4Paul Duffin * 3980888a09821a98ac0680fad765217302858e70fa4Paul Duffin * @param lists the lists to choose elements from, in the order that 3990888a09821a98ac0680fad765217302858e70fa4Paul Duffin * the elements chosen from those lists should appear in the resulting 4000888a09821a98ac0680fad765217302858e70fa4Paul Duffin * lists 4010888a09821a98ac0680fad765217302858e70fa4Paul Duffin * @param <B> any common base class shared by all axes (often just {@link 4020888a09821a98ac0680fad765217302858e70fa4Paul Duffin * Object}) 4030888a09821a98ac0680fad765217302858e70fa4Paul Duffin * @return the Cartesian product, as an immutable list containing immutable 4040888a09821a98ac0680fad765217302858e70fa4Paul Duffin * lists 4050888a09821a98ac0680fad765217302858e70fa4Paul Duffin * @throws IllegalArgumentException if the size of the cartesian product would 4060888a09821a98ac0680fad765217302858e70fa4Paul Duffin * be greater than {@link Integer#MAX_VALUE} 4070888a09821a98ac0680fad765217302858e70fa4Paul Duffin * @throws NullPointerException if {@code lists}, any one of the {@code lists}, 4080888a09821a98ac0680fad765217302858e70fa4Paul Duffin * or any element of a provided list is null 4090888a09821a98ac0680fad765217302858e70fa4Paul Duffin */ static <B> List<List<B>> 4100888a09821a98ac0680fad765217302858e70fa4Paul Duffin cartesianProduct(List<? extends List<? extends B>> lists) { 4110888a09821a98ac0680fad765217302858e70fa4Paul Duffin return CartesianList.create(lists); 4120888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 4130888a09821a98ac0680fad765217302858e70fa4Paul Duffin 4140888a09821a98ac0680fad765217302858e70fa4Paul Duffin /** 4150888a09821a98ac0680fad765217302858e70fa4Paul Duffin * Returns every possible list that can be formed by choosing one element 4160888a09821a98ac0680fad765217302858e70fa4Paul Duffin * from each of the given lists in order; the "n-ary 4170888a09821a98ac0680fad765217302858e70fa4Paul Duffin * <a href="http://en.wikipedia.org/wiki/Cartesian_product">Cartesian 4180888a09821a98ac0680fad765217302858e70fa4Paul Duffin * product</a>" of the lists. For example: <pre> {@code 4190888a09821a98ac0680fad765217302858e70fa4Paul Duffin * 4200888a09821a98ac0680fad765217302858e70fa4Paul Duffin * Lists.cartesianProduct(ImmutableList.of( 4210888a09821a98ac0680fad765217302858e70fa4Paul Duffin * ImmutableList.of(1, 2), 4220888a09821a98ac0680fad765217302858e70fa4Paul Duffin * ImmutableList.of("A", "B", "C")))}</pre> 4230888a09821a98ac0680fad765217302858e70fa4Paul Duffin * 4240888a09821a98ac0680fad765217302858e70fa4Paul Duffin * <p>returns a list containing six lists in the following order: 4250888a09821a98ac0680fad765217302858e70fa4Paul Duffin * 4260888a09821a98ac0680fad765217302858e70fa4Paul Duffin * <ul> 4270888a09821a98ac0680fad765217302858e70fa4Paul Duffin * <li>{@code ImmutableList.of(1, "A")} 4280888a09821a98ac0680fad765217302858e70fa4Paul Duffin * <li>{@code ImmutableList.of(1, "B")} 4290888a09821a98ac0680fad765217302858e70fa4Paul Duffin * <li>{@code ImmutableList.of(1, "C")} 4300888a09821a98ac0680fad765217302858e70fa4Paul Duffin * <li>{@code ImmutableList.of(2, "A")} 4310888a09821a98ac0680fad765217302858e70fa4Paul Duffin * <li>{@code ImmutableList.of(2, "B")} 4320888a09821a98ac0680fad765217302858e70fa4Paul Duffin * <li>{@code ImmutableList.of(2, "C")} 4330888a09821a98ac0680fad765217302858e70fa4Paul Duffin * </ul> 4340888a09821a98ac0680fad765217302858e70fa4Paul Duffin * 4350888a09821a98ac0680fad765217302858e70fa4Paul Duffin * <p>The result is guaranteed to be in the "traditional", lexicographical 4360888a09821a98ac0680fad765217302858e70fa4Paul Duffin * order for Cartesian products that you would get from nesting for loops: 4370888a09821a98ac0680fad765217302858e70fa4Paul Duffin * <pre> {@code 4380888a09821a98ac0680fad765217302858e70fa4Paul Duffin * 4390888a09821a98ac0680fad765217302858e70fa4Paul Duffin * for (B b0 : lists.get(0)) { 4400888a09821a98ac0680fad765217302858e70fa4Paul Duffin * for (B b1 : lists.get(1)) { 4410888a09821a98ac0680fad765217302858e70fa4Paul Duffin * ... 4420888a09821a98ac0680fad765217302858e70fa4Paul Duffin * ImmutableList<B> tuple = ImmutableList.of(b0, b1, ...); 4430888a09821a98ac0680fad765217302858e70fa4Paul Duffin * // operate on tuple 4440888a09821a98ac0680fad765217302858e70fa4Paul Duffin * } 4450888a09821a98ac0680fad765217302858e70fa4Paul Duffin * }}</pre> 4460888a09821a98ac0680fad765217302858e70fa4Paul Duffin * 4470888a09821a98ac0680fad765217302858e70fa4Paul Duffin * <p>Note that if any input list is empty, the Cartesian product will also be 4480888a09821a98ac0680fad765217302858e70fa4Paul Duffin * empty. If no lists at all are provided (an empty list), the resulting 4490888a09821a98ac0680fad765217302858e70fa4Paul Duffin * Cartesian product has one element, an empty list (counter-intuitive, but 4500888a09821a98ac0680fad765217302858e70fa4Paul Duffin * mathematically consistent). 4510888a09821a98ac0680fad765217302858e70fa4Paul Duffin * 4520888a09821a98ac0680fad765217302858e70fa4Paul Duffin * <p><i>Performance notes:</i> while the cartesian product of lists of size 4530888a09821a98ac0680fad765217302858e70fa4Paul Duffin * {@code m, n, p} is a list of size {@code m x n x p}, its actual memory 4540888a09821a98ac0680fad765217302858e70fa4Paul Duffin * consumption is much smaller. When the cartesian product is constructed, the 4550888a09821a98ac0680fad765217302858e70fa4Paul Duffin * input lists are merely copied. Only as the resulting list is iterated are 4560888a09821a98ac0680fad765217302858e70fa4Paul Duffin * the individual lists created, and these are not retained after iteration. 4570888a09821a98ac0680fad765217302858e70fa4Paul Duffin * 4580888a09821a98ac0680fad765217302858e70fa4Paul Duffin * @param lists the lists to choose elements from, in the order that 4590888a09821a98ac0680fad765217302858e70fa4Paul Duffin * the elements chosen from those lists should appear in the resulting 4600888a09821a98ac0680fad765217302858e70fa4Paul Duffin * lists 4610888a09821a98ac0680fad765217302858e70fa4Paul Duffin * @param <B> any common base class shared by all axes (often just {@link 4620888a09821a98ac0680fad765217302858e70fa4Paul Duffin * Object}) 4630888a09821a98ac0680fad765217302858e70fa4Paul Duffin * @return the Cartesian product, as an immutable list containing immutable 4640888a09821a98ac0680fad765217302858e70fa4Paul Duffin * lists 4650888a09821a98ac0680fad765217302858e70fa4Paul Duffin * @throws IllegalArgumentException if the size of the cartesian product would 4660888a09821a98ac0680fad765217302858e70fa4Paul Duffin * be greater than {@link Integer#MAX_VALUE} 4670888a09821a98ac0680fad765217302858e70fa4Paul Duffin * @throws NullPointerException if {@code lists}, any one of the 4680888a09821a98ac0680fad765217302858e70fa4Paul Duffin * {@code lists}, or any element of a provided list is null 4690888a09821a98ac0680fad765217302858e70fa4Paul Duffin */ static <B> List<List<B>> 4700888a09821a98ac0680fad765217302858e70fa4Paul Duffin cartesianProduct(List<? extends B>... lists) { 4710888a09821a98ac0680fad765217302858e70fa4Paul Duffin return cartesianProduct(Arrays.asList(lists)); 4720888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 4730888a09821a98ac0680fad765217302858e70fa4Paul Duffin 4740888a09821a98ac0680fad765217302858e70fa4Paul Duffin /** 4750888a09821a98ac0680fad765217302858e70fa4Paul Duffin * Returns a list that applies {@code function} to each element of {@code 4760888a09821a98ac0680fad765217302858e70fa4Paul Duffin * fromList}. The returned list is a transformed view of {@code fromList}; 4770888a09821a98ac0680fad765217302858e70fa4Paul Duffin * changes to {@code fromList} will be reflected in the returned list and vice 4780888a09821a98ac0680fad765217302858e70fa4Paul Duffin * versa. 4790888a09821a98ac0680fad765217302858e70fa4Paul Duffin * 4800888a09821a98ac0680fad765217302858e70fa4Paul Duffin * <p>Since functions are not reversible, the transform is one-way and new 4810888a09821a98ac0680fad765217302858e70fa4Paul Duffin * items cannot be stored in the returned list. The {@code add}, 4820888a09821a98ac0680fad765217302858e70fa4Paul Duffin * {@code addAll} and {@code set} methods are unsupported in the returned 4830888a09821a98ac0680fad765217302858e70fa4Paul Duffin * list. 4840888a09821a98ac0680fad765217302858e70fa4Paul Duffin * 4850888a09821a98ac0680fad765217302858e70fa4Paul Duffin * <p>The function is applied lazily, invoked when needed. This is necessary 4860888a09821a98ac0680fad765217302858e70fa4Paul Duffin * for the returned list to be a view, but it means that the function will be 4870888a09821a98ac0680fad765217302858e70fa4Paul Duffin * applied many times for bulk operations like {@link List#contains} and 4880888a09821a98ac0680fad765217302858e70fa4Paul Duffin * {@link List#hashCode}. For this to perform well, {@code function} should be 4890888a09821a98ac0680fad765217302858e70fa4Paul Duffin * fast. To avoid lazy evaluation when the returned list doesn't need to be a 4900888a09821a98ac0680fad765217302858e70fa4Paul Duffin * view, copy the returned list into a new list of your choosing. 4910888a09821a98ac0680fad765217302858e70fa4Paul Duffin * 4920888a09821a98ac0680fad765217302858e70fa4Paul Duffin * <p>If {@code fromList} implements {@link RandomAccess}, so will the 4930888a09821a98ac0680fad765217302858e70fa4Paul Duffin * returned list. The returned list is threadsafe if the supplied list and 4940888a09821a98ac0680fad765217302858e70fa4Paul Duffin * function are. 4950888a09821a98ac0680fad765217302858e70fa4Paul Duffin * 4960888a09821a98ac0680fad765217302858e70fa4Paul Duffin * <p>If only a {@code Collection} or {@code Iterable} input is available, use 4970888a09821a98ac0680fad765217302858e70fa4Paul Duffin * {@link Collections2#transform} or {@link Iterables#transform}. 4980888a09821a98ac0680fad765217302858e70fa4Paul Duffin * 4990888a09821a98ac0680fad765217302858e70fa4Paul Duffin * <p><b>Note:</b> serializing the returned list is implemented by serializing 5000888a09821a98ac0680fad765217302858e70fa4Paul Duffin * {@code fromList}, its contents, and {@code function} -- <i>not</i> by 5010888a09821a98ac0680fad765217302858e70fa4Paul Duffin * serializing the transformed values. This can lead to surprising behavior, 5020888a09821a98ac0680fad765217302858e70fa4Paul Duffin * so serializing the returned list is <b>not recommended</b>. Instead, 5030888a09821a98ac0680fad765217302858e70fa4Paul Duffin * copy the list using {@link ImmutableList#copyOf(Collection)} (for example), 5040888a09821a98ac0680fad765217302858e70fa4Paul Duffin * then serialize the copy. Other methods similar to this do not implement 5050888a09821a98ac0680fad765217302858e70fa4Paul Duffin * serialization at all for this reason. 5060888a09821a98ac0680fad765217302858e70fa4Paul Duffin */ 5070888a09821a98ac0680fad765217302858e70fa4Paul Duffin public static <F, T> List<T> transform( 5080888a09821a98ac0680fad765217302858e70fa4Paul Duffin List<F> fromList, Function<? super F, ? extends T> function) { 5090888a09821a98ac0680fad765217302858e70fa4Paul Duffin return (fromList instanceof RandomAccess) 5100888a09821a98ac0680fad765217302858e70fa4Paul Duffin ? new TransformingRandomAccessList<F, T>(fromList, function) 5110888a09821a98ac0680fad765217302858e70fa4Paul Duffin : new TransformingSequentialList<F, T>(fromList, function); 5120888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 5130888a09821a98ac0680fad765217302858e70fa4Paul Duffin 5140888a09821a98ac0680fad765217302858e70fa4Paul Duffin /** 5150888a09821a98ac0680fad765217302858e70fa4Paul Duffin * Implementation of a sequential transforming list. 5160888a09821a98ac0680fad765217302858e70fa4Paul Duffin * 5170888a09821a98ac0680fad765217302858e70fa4Paul Duffin * @see Lists#transform 5180888a09821a98ac0680fad765217302858e70fa4Paul Duffin */ 5190888a09821a98ac0680fad765217302858e70fa4Paul Duffin private static class TransformingSequentialList<F, T> 5200888a09821a98ac0680fad765217302858e70fa4Paul Duffin extends AbstractSequentialList<T> implements Serializable { 5210888a09821a98ac0680fad765217302858e70fa4Paul Duffin final List<F> fromList; 5220888a09821a98ac0680fad765217302858e70fa4Paul Duffin final Function<? super F, ? extends T> function; 5230888a09821a98ac0680fad765217302858e70fa4Paul Duffin 5240888a09821a98ac0680fad765217302858e70fa4Paul Duffin TransformingSequentialList( 5250888a09821a98ac0680fad765217302858e70fa4Paul Duffin List<F> fromList, Function<? super F, ? extends T> function) { 5260888a09821a98ac0680fad765217302858e70fa4Paul Duffin this.fromList = checkNotNull(fromList); 5270888a09821a98ac0680fad765217302858e70fa4Paul Duffin this.function = checkNotNull(function); 5280888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 5290888a09821a98ac0680fad765217302858e70fa4Paul Duffin /** 5300888a09821a98ac0680fad765217302858e70fa4Paul Duffin * The default implementation inherited is based on iteration and removal of 5310888a09821a98ac0680fad765217302858e70fa4Paul Duffin * each element which can be overkill. That's why we forward this call 5320888a09821a98ac0680fad765217302858e70fa4Paul Duffin * directly to the backing list. 5330888a09821a98ac0680fad765217302858e70fa4Paul Duffin */ 5340888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Override public void clear() { 5350888a09821a98ac0680fad765217302858e70fa4Paul Duffin fromList.clear(); 5360888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 5370888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Override public int size() { 5380888a09821a98ac0680fad765217302858e70fa4Paul Duffin return fromList.size(); 5390888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 5400888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Override public ListIterator<T> listIterator(final int index) { 5410888a09821a98ac0680fad765217302858e70fa4Paul Duffin return new TransformedListIterator<F, T>(fromList.listIterator(index)) { 5420888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Override 5430888a09821a98ac0680fad765217302858e70fa4Paul Duffin T transform(F from) { 5440888a09821a98ac0680fad765217302858e70fa4Paul Duffin return function.apply(from); 5450888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 5460888a09821a98ac0680fad765217302858e70fa4Paul Duffin }; 5470888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 5480888a09821a98ac0680fad765217302858e70fa4Paul Duffin 5490888a09821a98ac0680fad765217302858e70fa4Paul Duffin private static final long serialVersionUID = 0; 5500888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 5510888a09821a98ac0680fad765217302858e70fa4Paul Duffin 5520888a09821a98ac0680fad765217302858e70fa4Paul Duffin /** 5530888a09821a98ac0680fad765217302858e70fa4Paul Duffin * Implementation of a transforming random access list. We try to make as many 5540888a09821a98ac0680fad765217302858e70fa4Paul Duffin * of these methods pass-through to the source list as possible so that the 5550888a09821a98ac0680fad765217302858e70fa4Paul Duffin * performance characteristics of the source list and transformed list are 5560888a09821a98ac0680fad765217302858e70fa4Paul Duffin * similar. 5570888a09821a98ac0680fad765217302858e70fa4Paul Duffin * 5580888a09821a98ac0680fad765217302858e70fa4Paul Duffin * @see Lists#transform 5590888a09821a98ac0680fad765217302858e70fa4Paul Duffin */ 5600888a09821a98ac0680fad765217302858e70fa4Paul Duffin private static class TransformingRandomAccessList<F, T> 5610888a09821a98ac0680fad765217302858e70fa4Paul Duffin extends AbstractList<T> implements RandomAccess, Serializable { 5620888a09821a98ac0680fad765217302858e70fa4Paul Duffin final List<F> fromList; 5630888a09821a98ac0680fad765217302858e70fa4Paul Duffin final Function<? super F, ? extends T> function; 5640888a09821a98ac0680fad765217302858e70fa4Paul Duffin 5650888a09821a98ac0680fad765217302858e70fa4Paul Duffin TransformingRandomAccessList( 5660888a09821a98ac0680fad765217302858e70fa4Paul Duffin List<F> fromList, Function<? super F, ? extends T> function) { 5670888a09821a98ac0680fad765217302858e70fa4Paul Duffin this.fromList = checkNotNull(fromList); 5680888a09821a98ac0680fad765217302858e70fa4Paul Duffin this.function = checkNotNull(function); 5690888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 5700888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Override public void clear() { 5710888a09821a98ac0680fad765217302858e70fa4Paul Duffin fromList.clear(); 5720888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 5730888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Override public T get(int index) { 5740888a09821a98ac0680fad765217302858e70fa4Paul Duffin return function.apply(fromList.get(index)); 5750888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 5760888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Override public Iterator<T> iterator() { 5770888a09821a98ac0680fad765217302858e70fa4Paul Duffin return listIterator(); 5780888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 5790888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Override public ListIterator<T> listIterator(int index) { 5800888a09821a98ac0680fad765217302858e70fa4Paul Duffin return new TransformedListIterator<F, T>(fromList.listIterator(index)) { 5810888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Override 5820888a09821a98ac0680fad765217302858e70fa4Paul Duffin T transform(F from) { 5830888a09821a98ac0680fad765217302858e70fa4Paul Duffin return function.apply(from); 5840888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 5850888a09821a98ac0680fad765217302858e70fa4Paul Duffin }; 5860888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 5870888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Override public boolean isEmpty() { 5880888a09821a98ac0680fad765217302858e70fa4Paul Duffin return fromList.isEmpty(); 5890888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 5900888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Override public T remove(int index) { 5910888a09821a98ac0680fad765217302858e70fa4Paul Duffin return function.apply(fromList.remove(index)); 5920888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 5930888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Override public int size() { 5940888a09821a98ac0680fad765217302858e70fa4Paul Duffin return fromList.size(); 5950888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 5960888a09821a98ac0680fad765217302858e70fa4Paul Duffin private static final long serialVersionUID = 0; 5970888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 5980888a09821a98ac0680fad765217302858e70fa4Paul Duffin 5990888a09821a98ac0680fad765217302858e70fa4Paul Duffin /** 6000888a09821a98ac0680fad765217302858e70fa4Paul Duffin * Returns consecutive {@linkplain List#subList(int, int) sublists} of a list, 6010888a09821a98ac0680fad765217302858e70fa4Paul Duffin * each of the same size (the final list may be smaller). For example, 6020888a09821a98ac0680fad765217302858e70fa4Paul Duffin * partitioning a list containing {@code [a, b, c, d, e]} with a partition 6030888a09821a98ac0680fad765217302858e70fa4Paul Duffin * size of 3 yields {@code [[a, b, c], [d, e]]} -- an outer list containing 6040888a09821a98ac0680fad765217302858e70fa4Paul Duffin * two inner lists of three and two elements, all in the original order. 6050888a09821a98ac0680fad765217302858e70fa4Paul Duffin * 6060888a09821a98ac0680fad765217302858e70fa4Paul Duffin * <p>The outer list is unmodifiable, but reflects the latest state of the 6070888a09821a98ac0680fad765217302858e70fa4Paul Duffin * source list. The inner lists are sublist views of the original list, 6080888a09821a98ac0680fad765217302858e70fa4Paul Duffin * produced on demand using {@link List#subList(int, int)}, and are subject 6090888a09821a98ac0680fad765217302858e70fa4Paul Duffin * to all the usual caveats about modification as explained in that API. 6100888a09821a98ac0680fad765217302858e70fa4Paul Duffin * 6110888a09821a98ac0680fad765217302858e70fa4Paul Duffin * @param list the list to return consecutive sublists of 6120888a09821a98ac0680fad765217302858e70fa4Paul Duffin * @param size the desired size of each sublist (the last may be 6130888a09821a98ac0680fad765217302858e70fa4Paul Duffin * smaller) 6140888a09821a98ac0680fad765217302858e70fa4Paul Duffin * @return a list of consecutive sublists 6150888a09821a98ac0680fad765217302858e70fa4Paul Duffin * @throws IllegalArgumentException if {@code partitionSize} is nonpositive 6160888a09821a98ac0680fad765217302858e70fa4Paul Duffin */ 6170888a09821a98ac0680fad765217302858e70fa4Paul Duffin public static <T> List<List<T>> partition(List<T> list, int size) { 6180888a09821a98ac0680fad765217302858e70fa4Paul Duffin checkNotNull(list); 6190888a09821a98ac0680fad765217302858e70fa4Paul Duffin checkArgument(size > 0); 6200888a09821a98ac0680fad765217302858e70fa4Paul Duffin return (list instanceof RandomAccess) 6210888a09821a98ac0680fad765217302858e70fa4Paul Duffin ? new RandomAccessPartition<T>(list, size) 6220888a09821a98ac0680fad765217302858e70fa4Paul Duffin : new Partition<T>(list, size); 6230888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 6240888a09821a98ac0680fad765217302858e70fa4Paul Duffin 6250888a09821a98ac0680fad765217302858e70fa4Paul Duffin private static class Partition<T> extends AbstractList<List<T>> { 6260888a09821a98ac0680fad765217302858e70fa4Paul Duffin final List<T> list; 6270888a09821a98ac0680fad765217302858e70fa4Paul Duffin final int size; 6280888a09821a98ac0680fad765217302858e70fa4Paul Duffin 6290888a09821a98ac0680fad765217302858e70fa4Paul Duffin Partition(List<T> list, int size) { 6300888a09821a98ac0680fad765217302858e70fa4Paul Duffin this.list = list; 6310888a09821a98ac0680fad765217302858e70fa4Paul Duffin this.size = size; 6320888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 6330888a09821a98ac0680fad765217302858e70fa4Paul Duffin 6340888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Override public List<T> get(int index) { 6350888a09821a98ac0680fad765217302858e70fa4Paul Duffin checkElementIndex(index, size()); 6360888a09821a98ac0680fad765217302858e70fa4Paul Duffin int start = index * size; 6370888a09821a98ac0680fad765217302858e70fa4Paul Duffin int end = Math.min(start + size, list.size()); 6380888a09821a98ac0680fad765217302858e70fa4Paul Duffin return list.subList(start, end); 6390888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 6400888a09821a98ac0680fad765217302858e70fa4Paul Duffin 6410888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Override public int size() { 6420888a09821a98ac0680fad765217302858e70fa4Paul Duffin return IntMath.divide(list.size(), size, RoundingMode.CEILING); 6430888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 6440888a09821a98ac0680fad765217302858e70fa4Paul Duffin 6450888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Override public boolean isEmpty() { 6460888a09821a98ac0680fad765217302858e70fa4Paul Duffin return list.isEmpty(); 6470888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 6480888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 6490888a09821a98ac0680fad765217302858e70fa4Paul Duffin 6500888a09821a98ac0680fad765217302858e70fa4Paul Duffin private static class RandomAccessPartition<T> extends Partition<T> 6510888a09821a98ac0680fad765217302858e70fa4Paul Duffin implements RandomAccess { 6520888a09821a98ac0680fad765217302858e70fa4Paul Duffin RandomAccessPartition(List<T> list, int size) { 6530888a09821a98ac0680fad765217302858e70fa4Paul Duffin super(list, size); 6540888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 6550888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 6560888a09821a98ac0680fad765217302858e70fa4Paul Duffin 6570888a09821a98ac0680fad765217302858e70fa4Paul Duffin /** 6580888a09821a98ac0680fad765217302858e70fa4Paul Duffin * Returns a view of the specified string as an immutable list of {@code 6590888a09821a98ac0680fad765217302858e70fa4Paul Duffin * Character} values. 6600888a09821a98ac0680fad765217302858e70fa4Paul Duffin * 6610888a09821a98ac0680fad765217302858e70fa4Paul Duffin * @since 7.0 6620888a09821a98ac0680fad765217302858e70fa4Paul Duffin */ 6630888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Beta public static ImmutableList<Character> charactersOf(String string) { 6640888a09821a98ac0680fad765217302858e70fa4Paul Duffin return new StringAsImmutableList(checkNotNull(string)); 6650888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 6660888a09821a98ac0680fad765217302858e70fa4Paul Duffin 6670888a09821a98ac0680fad765217302858e70fa4Paul Duffin @SuppressWarnings("serial") // serialized using ImmutableList serialization 6680888a09821a98ac0680fad765217302858e70fa4Paul Duffin private static final class StringAsImmutableList 6690888a09821a98ac0680fad765217302858e70fa4Paul Duffin extends ImmutableList<Character> { 6700888a09821a98ac0680fad765217302858e70fa4Paul Duffin 6710888a09821a98ac0680fad765217302858e70fa4Paul Duffin private final String string; 6720888a09821a98ac0680fad765217302858e70fa4Paul Duffin 6730888a09821a98ac0680fad765217302858e70fa4Paul Duffin StringAsImmutableList(String string) { 6740888a09821a98ac0680fad765217302858e70fa4Paul Duffin this.string = string; 6750888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 6760888a09821a98ac0680fad765217302858e70fa4Paul Duffin 6770888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Override public int indexOf(@Nullable Object object) { 6780888a09821a98ac0680fad765217302858e70fa4Paul Duffin return (object instanceof Character) 6790888a09821a98ac0680fad765217302858e70fa4Paul Duffin ? string.indexOf((Character) object) : -1; 6800888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 6810888a09821a98ac0680fad765217302858e70fa4Paul Duffin 6820888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Override public int lastIndexOf(@Nullable Object object) { 6830888a09821a98ac0680fad765217302858e70fa4Paul Duffin return (object instanceof Character) 6840888a09821a98ac0680fad765217302858e70fa4Paul Duffin ? string.lastIndexOf((Character) object) : -1; 6850888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 6860888a09821a98ac0680fad765217302858e70fa4Paul Duffin 6870888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Override public ImmutableList<Character> subList( 6880888a09821a98ac0680fad765217302858e70fa4Paul Duffin int fromIndex, int toIndex) { 6890888a09821a98ac0680fad765217302858e70fa4Paul Duffin checkPositionIndexes(fromIndex, toIndex, size()); // for GWT 6900888a09821a98ac0680fad765217302858e70fa4Paul Duffin return charactersOf(string.substring(fromIndex, toIndex)); 6910888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 6920888a09821a98ac0680fad765217302858e70fa4Paul Duffin 6930888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Override boolean isPartialView() { 6940888a09821a98ac0680fad765217302858e70fa4Paul Duffin return false; 6950888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 6960888a09821a98ac0680fad765217302858e70fa4Paul Duffin 6970888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Override public Character get(int index) { 6980888a09821a98ac0680fad765217302858e70fa4Paul Duffin checkElementIndex(index, size()); // for GWT 6990888a09821a98ac0680fad765217302858e70fa4Paul Duffin return string.charAt(index); 7000888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 7010888a09821a98ac0680fad765217302858e70fa4Paul Duffin 7020888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Override public int size() { 7030888a09821a98ac0680fad765217302858e70fa4Paul Duffin return string.length(); 7040888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 7050888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 7060888a09821a98ac0680fad765217302858e70fa4Paul Duffin 7070888a09821a98ac0680fad765217302858e70fa4Paul Duffin /** 7080888a09821a98ac0680fad765217302858e70fa4Paul Duffin * Returns a view of the specified {@code CharSequence} as a {@code 7090888a09821a98ac0680fad765217302858e70fa4Paul Duffin * List<Character>}, viewing {@code sequence} as a sequence of Unicode code 7100888a09821a98ac0680fad765217302858e70fa4Paul Duffin * units. The view does not support any modification operations, but reflects 7110888a09821a98ac0680fad765217302858e70fa4Paul Duffin * any changes to the underlying character sequence. 7120888a09821a98ac0680fad765217302858e70fa4Paul Duffin * 7130888a09821a98ac0680fad765217302858e70fa4Paul Duffin * @param sequence the character sequence to view as a {@code List} of 7140888a09821a98ac0680fad765217302858e70fa4Paul Duffin * characters 7150888a09821a98ac0680fad765217302858e70fa4Paul Duffin * @return an {@code List<Character>} view of the character sequence 7160888a09821a98ac0680fad765217302858e70fa4Paul Duffin * @since 7.0 7170888a09821a98ac0680fad765217302858e70fa4Paul Duffin */ 7180888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Beta public static List<Character> charactersOf(CharSequence sequence) { 7190888a09821a98ac0680fad765217302858e70fa4Paul Duffin return new CharSequenceAsList(checkNotNull(sequence)); 7200888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 7210888a09821a98ac0680fad765217302858e70fa4Paul Duffin 7220888a09821a98ac0680fad765217302858e70fa4Paul Duffin private static final class CharSequenceAsList 7230888a09821a98ac0680fad765217302858e70fa4Paul Duffin extends AbstractList<Character> { 7240888a09821a98ac0680fad765217302858e70fa4Paul Duffin private final CharSequence sequence; 7250888a09821a98ac0680fad765217302858e70fa4Paul Duffin 7260888a09821a98ac0680fad765217302858e70fa4Paul Duffin CharSequenceAsList(CharSequence sequence) { 7270888a09821a98ac0680fad765217302858e70fa4Paul Duffin this.sequence = sequence; 7280888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 7290888a09821a98ac0680fad765217302858e70fa4Paul Duffin 7300888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Override public Character get(int index) { 7310888a09821a98ac0680fad765217302858e70fa4Paul Duffin checkElementIndex(index, size()); // for GWT 7320888a09821a98ac0680fad765217302858e70fa4Paul Duffin return sequence.charAt(index); 7330888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 7340888a09821a98ac0680fad765217302858e70fa4Paul Duffin 7350888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Override public int size() { 7360888a09821a98ac0680fad765217302858e70fa4Paul Duffin return sequence.length(); 7370888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 7380888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 7390888a09821a98ac0680fad765217302858e70fa4Paul Duffin 7400888a09821a98ac0680fad765217302858e70fa4Paul Duffin /** 7410888a09821a98ac0680fad765217302858e70fa4Paul Duffin * Returns a reversed view of the specified list. For example, {@code 7420888a09821a98ac0680fad765217302858e70fa4Paul Duffin * Lists.reverse(Arrays.asList(1, 2, 3))} returns a list containing {@code 3, 7430888a09821a98ac0680fad765217302858e70fa4Paul Duffin * 2, 1}. The returned list is backed by this list, so changes in the returned 7440888a09821a98ac0680fad765217302858e70fa4Paul Duffin * list are reflected in this list, and vice-versa. The returned list supports 7450888a09821a98ac0680fad765217302858e70fa4Paul Duffin * all of the optional list operations supported by this list. 7460888a09821a98ac0680fad765217302858e70fa4Paul Duffin * 7470888a09821a98ac0680fad765217302858e70fa4Paul Duffin * <p>The returned list is random-access if the specified list is random 7480888a09821a98ac0680fad765217302858e70fa4Paul Duffin * access. 7490888a09821a98ac0680fad765217302858e70fa4Paul Duffin * 7500888a09821a98ac0680fad765217302858e70fa4Paul Duffin * @since 7.0 7510888a09821a98ac0680fad765217302858e70fa4Paul Duffin */ 7520888a09821a98ac0680fad765217302858e70fa4Paul Duffin public static <T> List<T> reverse(List<T> list) { 7530888a09821a98ac0680fad765217302858e70fa4Paul Duffin if (list instanceof ImmutableList) { 7540888a09821a98ac0680fad765217302858e70fa4Paul Duffin return ((ImmutableList<T>) list).reverse(); 7550888a09821a98ac0680fad765217302858e70fa4Paul Duffin } else if (list instanceof ReverseList) { 7560888a09821a98ac0680fad765217302858e70fa4Paul Duffin return ((ReverseList<T>) list).getForwardList(); 7570888a09821a98ac0680fad765217302858e70fa4Paul Duffin } else if (list instanceof RandomAccess) { 7580888a09821a98ac0680fad765217302858e70fa4Paul Duffin return new RandomAccessReverseList<T>(list); 7590888a09821a98ac0680fad765217302858e70fa4Paul Duffin } else { 7600888a09821a98ac0680fad765217302858e70fa4Paul Duffin return new ReverseList<T>(list); 7610888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 7620888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 7630888a09821a98ac0680fad765217302858e70fa4Paul Duffin 7640888a09821a98ac0680fad765217302858e70fa4Paul Duffin private static class ReverseList<T> extends AbstractList<T> { 7650888a09821a98ac0680fad765217302858e70fa4Paul Duffin private final List<T> forwardList; 7660888a09821a98ac0680fad765217302858e70fa4Paul Duffin 7670888a09821a98ac0680fad765217302858e70fa4Paul Duffin ReverseList(List<T> forwardList) { 7680888a09821a98ac0680fad765217302858e70fa4Paul Duffin this.forwardList = checkNotNull(forwardList); 7690888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 7700888a09821a98ac0680fad765217302858e70fa4Paul Duffin 7710888a09821a98ac0680fad765217302858e70fa4Paul Duffin List<T> getForwardList() { 7720888a09821a98ac0680fad765217302858e70fa4Paul Duffin return forwardList; 7730888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 7740888a09821a98ac0680fad765217302858e70fa4Paul Duffin 7750888a09821a98ac0680fad765217302858e70fa4Paul Duffin private int reverseIndex(int index) { 7760888a09821a98ac0680fad765217302858e70fa4Paul Duffin int size = size(); 7770888a09821a98ac0680fad765217302858e70fa4Paul Duffin checkElementIndex(index, size); 7780888a09821a98ac0680fad765217302858e70fa4Paul Duffin return (size - 1) - index; 7790888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 7800888a09821a98ac0680fad765217302858e70fa4Paul Duffin 7810888a09821a98ac0680fad765217302858e70fa4Paul Duffin private int reversePosition(int index) { 7820888a09821a98ac0680fad765217302858e70fa4Paul Duffin int size = size(); 7830888a09821a98ac0680fad765217302858e70fa4Paul Duffin checkPositionIndex(index, size); 7840888a09821a98ac0680fad765217302858e70fa4Paul Duffin return size - index; 7850888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 7860888a09821a98ac0680fad765217302858e70fa4Paul Duffin 7870888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Override public void add(int index, @Nullable T element) { 7880888a09821a98ac0680fad765217302858e70fa4Paul Duffin forwardList.add(reversePosition(index), element); 7890888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 7900888a09821a98ac0680fad765217302858e70fa4Paul Duffin 7910888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Override public void clear() { 7920888a09821a98ac0680fad765217302858e70fa4Paul Duffin forwardList.clear(); 7930888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 7940888a09821a98ac0680fad765217302858e70fa4Paul Duffin 7950888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Override public T remove(int index) { 7960888a09821a98ac0680fad765217302858e70fa4Paul Duffin return forwardList.remove(reverseIndex(index)); 7970888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 7980888a09821a98ac0680fad765217302858e70fa4Paul Duffin 7990888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Override protected void removeRange(int fromIndex, int toIndex) { 8000888a09821a98ac0680fad765217302858e70fa4Paul Duffin subList(fromIndex, toIndex).clear(); 8010888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 8020888a09821a98ac0680fad765217302858e70fa4Paul Duffin 8030888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Override public T set(int index, @Nullable T element) { 8040888a09821a98ac0680fad765217302858e70fa4Paul Duffin return forwardList.set(reverseIndex(index), element); 8050888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 8060888a09821a98ac0680fad765217302858e70fa4Paul Duffin 8070888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Override public T get(int index) { 8080888a09821a98ac0680fad765217302858e70fa4Paul Duffin return forwardList.get(reverseIndex(index)); 8090888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 8100888a09821a98ac0680fad765217302858e70fa4Paul Duffin 8110888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Override public int size() { 8120888a09821a98ac0680fad765217302858e70fa4Paul Duffin return forwardList.size(); 8130888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 8140888a09821a98ac0680fad765217302858e70fa4Paul Duffin 8150888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Override public List<T> subList(int fromIndex, int toIndex) { 8160888a09821a98ac0680fad765217302858e70fa4Paul Duffin checkPositionIndexes(fromIndex, toIndex, size()); 8170888a09821a98ac0680fad765217302858e70fa4Paul Duffin return reverse(forwardList.subList( 8180888a09821a98ac0680fad765217302858e70fa4Paul Duffin reversePosition(toIndex), reversePosition(fromIndex))); 8190888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 8200888a09821a98ac0680fad765217302858e70fa4Paul Duffin 8210888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Override public Iterator<T> iterator() { 8220888a09821a98ac0680fad765217302858e70fa4Paul Duffin return listIterator(); 8230888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 8240888a09821a98ac0680fad765217302858e70fa4Paul Duffin 8250888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Override public ListIterator<T> listIterator(int index) { 8260888a09821a98ac0680fad765217302858e70fa4Paul Duffin int start = reversePosition(index); 8270888a09821a98ac0680fad765217302858e70fa4Paul Duffin final ListIterator<T> forwardIterator = forwardList.listIterator(start); 8280888a09821a98ac0680fad765217302858e70fa4Paul Duffin return new ListIterator<T>() { 8290888a09821a98ac0680fad765217302858e70fa4Paul Duffin 8300888a09821a98ac0680fad765217302858e70fa4Paul Duffin boolean canRemoveOrSet; 8310888a09821a98ac0680fad765217302858e70fa4Paul Duffin 8320888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Override public void add(T e) { 8330888a09821a98ac0680fad765217302858e70fa4Paul Duffin forwardIterator.add(e); 8340888a09821a98ac0680fad765217302858e70fa4Paul Duffin forwardIterator.previous(); 8350888a09821a98ac0680fad765217302858e70fa4Paul Duffin canRemoveOrSet = false; 8360888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 8370888a09821a98ac0680fad765217302858e70fa4Paul Duffin 8380888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Override public boolean hasNext() { 8390888a09821a98ac0680fad765217302858e70fa4Paul Duffin return forwardIterator.hasPrevious(); 8400888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 8410888a09821a98ac0680fad765217302858e70fa4Paul Duffin 8420888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Override public boolean hasPrevious() { 8430888a09821a98ac0680fad765217302858e70fa4Paul Duffin return forwardIterator.hasNext(); 8440888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 8450888a09821a98ac0680fad765217302858e70fa4Paul Duffin 8460888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Override public T next() { 8470888a09821a98ac0680fad765217302858e70fa4Paul Duffin if (!hasNext()) { 8480888a09821a98ac0680fad765217302858e70fa4Paul Duffin throw new NoSuchElementException(); 8490888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 8500888a09821a98ac0680fad765217302858e70fa4Paul Duffin canRemoveOrSet = true; 8510888a09821a98ac0680fad765217302858e70fa4Paul Duffin return forwardIterator.previous(); 8520888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 8530888a09821a98ac0680fad765217302858e70fa4Paul Duffin 8540888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Override public int nextIndex() { 8550888a09821a98ac0680fad765217302858e70fa4Paul Duffin return reversePosition(forwardIterator.nextIndex()); 8560888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 8570888a09821a98ac0680fad765217302858e70fa4Paul Duffin 8580888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Override public T previous() { 8590888a09821a98ac0680fad765217302858e70fa4Paul Duffin if (!hasPrevious()) { 8600888a09821a98ac0680fad765217302858e70fa4Paul Duffin throw new NoSuchElementException(); 8610888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 8620888a09821a98ac0680fad765217302858e70fa4Paul Duffin canRemoveOrSet = true; 8630888a09821a98ac0680fad765217302858e70fa4Paul Duffin return forwardIterator.next(); 8640888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 8650888a09821a98ac0680fad765217302858e70fa4Paul Duffin 8660888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Override public int previousIndex() { 8670888a09821a98ac0680fad765217302858e70fa4Paul Duffin return nextIndex() - 1; 8680888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 8690888a09821a98ac0680fad765217302858e70fa4Paul Duffin 8700888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Override public void remove() { 8710888a09821a98ac0680fad765217302858e70fa4Paul Duffin checkRemove(canRemoveOrSet); 8720888a09821a98ac0680fad765217302858e70fa4Paul Duffin forwardIterator.remove(); 8730888a09821a98ac0680fad765217302858e70fa4Paul Duffin canRemoveOrSet = false; 8740888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 8750888a09821a98ac0680fad765217302858e70fa4Paul Duffin 8760888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Override public void set(T e) { 8770888a09821a98ac0680fad765217302858e70fa4Paul Duffin checkState(canRemoveOrSet); 8780888a09821a98ac0680fad765217302858e70fa4Paul Duffin forwardIterator.set(e); 8790888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 8800888a09821a98ac0680fad765217302858e70fa4Paul Duffin }; 8810888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 8820888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 8830888a09821a98ac0680fad765217302858e70fa4Paul Duffin 8840888a09821a98ac0680fad765217302858e70fa4Paul Duffin private static class RandomAccessReverseList<T> extends ReverseList<T> 8850888a09821a98ac0680fad765217302858e70fa4Paul Duffin implements RandomAccess { 8860888a09821a98ac0680fad765217302858e70fa4Paul Duffin RandomAccessReverseList(List<T> forwardList) { 8870888a09821a98ac0680fad765217302858e70fa4Paul Duffin super(forwardList); 8880888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 8890888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 8900888a09821a98ac0680fad765217302858e70fa4Paul Duffin 8910888a09821a98ac0680fad765217302858e70fa4Paul Duffin /** 8920888a09821a98ac0680fad765217302858e70fa4Paul Duffin * An implementation of {@link List#hashCode()}. 8930888a09821a98ac0680fad765217302858e70fa4Paul Duffin */ 8940888a09821a98ac0680fad765217302858e70fa4Paul Duffin static int hashCodeImpl(List<?> list) { 8950888a09821a98ac0680fad765217302858e70fa4Paul Duffin // TODO(user): worth optimizing for RandomAccess? 8960888a09821a98ac0680fad765217302858e70fa4Paul Duffin int hashCode = 1; 8970888a09821a98ac0680fad765217302858e70fa4Paul Duffin for (Object o : list) { 8980888a09821a98ac0680fad765217302858e70fa4Paul Duffin hashCode = 31 * hashCode + (o == null ? 0 : o.hashCode()); 8990888a09821a98ac0680fad765217302858e70fa4Paul Duffin 9000888a09821a98ac0680fad765217302858e70fa4Paul Duffin hashCode = ~~hashCode; 9010888a09821a98ac0680fad765217302858e70fa4Paul Duffin // needed to deal with GWT integer overflow 9020888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 9030888a09821a98ac0680fad765217302858e70fa4Paul Duffin return hashCode; 9040888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 9050888a09821a98ac0680fad765217302858e70fa4Paul Duffin 9060888a09821a98ac0680fad765217302858e70fa4Paul Duffin /** 9070888a09821a98ac0680fad765217302858e70fa4Paul Duffin * An implementation of {@link List#equals(Object)}. 9080888a09821a98ac0680fad765217302858e70fa4Paul Duffin */ 9090888a09821a98ac0680fad765217302858e70fa4Paul Duffin static boolean equalsImpl(List<?> list, @Nullable Object object) { 9100888a09821a98ac0680fad765217302858e70fa4Paul Duffin if (object == checkNotNull(list)) { 9110888a09821a98ac0680fad765217302858e70fa4Paul Duffin return true; 9120888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 9130888a09821a98ac0680fad765217302858e70fa4Paul Duffin if (!(object instanceof List)) { 9140888a09821a98ac0680fad765217302858e70fa4Paul Duffin return false; 9150888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 9160888a09821a98ac0680fad765217302858e70fa4Paul Duffin 9170888a09821a98ac0680fad765217302858e70fa4Paul Duffin List<?> o = (List<?>) object; 9180888a09821a98ac0680fad765217302858e70fa4Paul Duffin 9190888a09821a98ac0680fad765217302858e70fa4Paul Duffin return list.size() == o.size() 9200888a09821a98ac0680fad765217302858e70fa4Paul Duffin && Iterators.elementsEqual(list.iterator(), o.iterator()); 9210888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 9220888a09821a98ac0680fad765217302858e70fa4Paul Duffin 9230888a09821a98ac0680fad765217302858e70fa4Paul Duffin /** 9240888a09821a98ac0680fad765217302858e70fa4Paul Duffin * An implementation of {@link List#addAll(int, Collection)}. 9250888a09821a98ac0680fad765217302858e70fa4Paul Duffin */ 9260888a09821a98ac0680fad765217302858e70fa4Paul Duffin static <E> boolean addAllImpl( 9270888a09821a98ac0680fad765217302858e70fa4Paul Duffin List<E> list, int index, Iterable<? extends E> elements) { 9280888a09821a98ac0680fad765217302858e70fa4Paul Duffin boolean changed = false; 9290888a09821a98ac0680fad765217302858e70fa4Paul Duffin ListIterator<E> listIterator = list.listIterator(index); 9300888a09821a98ac0680fad765217302858e70fa4Paul Duffin for (E e : elements) { 9310888a09821a98ac0680fad765217302858e70fa4Paul Duffin listIterator.add(e); 9320888a09821a98ac0680fad765217302858e70fa4Paul Duffin changed = true; 9330888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 9340888a09821a98ac0680fad765217302858e70fa4Paul Duffin return changed; 9350888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 9360888a09821a98ac0680fad765217302858e70fa4Paul Duffin 9370888a09821a98ac0680fad765217302858e70fa4Paul Duffin /** 9380888a09821a98ac0680fad765217302858e70fa4Paul Duffin * An implementation of {@link List#indexOf(Object)}. 9390888a09821a98ac0680fad765217302858e70fa4Paul Duffin */ 9400888a09821a98ac0680fad765217302858e70fa4Paul Duffin static int indexOfImpl(List<?> list, @Nullable Object element) { 9410888a09821a98ac0680fad765217302858e70fa4Paul Duffin ListIterator<?> listIterator = list.listIterator(); 9420888a09821a98ac0680fad765217302858e70fa4Paul Duffin while (listIterator.hasNext()) { 9430888a09821a98ac0680fad765217302858e70fa4Paul Duffin if (Objects.equal(element, listIterator.next())) { 9440888a09821a98ac0680fad765217302858e70fa4Paul Duffin return listIterator.previousIndex(); 9450888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 9460888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 9470888a09821a98ac0680fad765217302858e70fa4Paul Duffin return -1; 9480888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 9490888a09821a98ac0680fad765217302858e70fa4Paul Duffin 9500888a09821a98ac0680fad765217302858e70fa4Paul Duffin /** 9510888a09821a98ac0680fad765217302858e70fa4Paul Duffin * An implementation of {@link List#lastIndexOf(Object)}. 9520888a09821a98ac0680fad765217302858e70fa4Paul Duffin */ 9530888a09821a98ac0680fad765217302858e70fa4Paul Duffin static int lastIndexOfImpl(List<?> list, @Nullable Object element) { 9540888a09821a98ac0680fad765217302858e70fa4Paul Duffin ListIterator<?> listIterator = list.listIterator(list.size()); 9550888a09821a98ac0680fad765217302858e70fa4Paul Duffin while (listIterator.hasPrevious()) { 9560888a09821a98ac0680fad765217302858e70fa4Paul Duffin if (Objects.equal(element, listIterator.previous())) { 9570888a09821a98ac0680fad765217302858e70fa4Paul Duffin return listIterator.nextIndex(); 9580888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 9590888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 9600888a09821a98ac0680fad765217302858e70fa4Paul Duffin return -1; 9610888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 9620888a09821a98ac0680fad765217302858e70fa4Paul Duffin 9630888a09821a98ac0680fad765217302858e70fa4Paul Duffin /** 9640888a09821a98ac0680fad765217302858e70fa4Paul Duffin * Returns an implementation of {@link List#listIterator(int)}. 9650888a09821a98ac0680fad765217302858e70fa4Paul Duffin */ 9660888a09821a98ac0680fad765217302858e70fa4Paul Duffin static <E> ListIterator<E> listIteratorImpl(List<E> list, int index) { 9670888a09821a98ac0680fad765217302858e70fa4Paul Duffin return new AbstractListWrapper<E>(list).listIterator(index); 9680888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 9690888a09821a98ac0680fad765217302858e70fa4Paul Duffin 9700888a09821a98ac0680fad765217302858e70fa4Paul Duffin /** 9710888a09821a98ac0680fad765217302858e70fa4Paul Duffin * An implementation of {@link List#subList(int, int)}. 9720888a09821a98ac0680fad765217302858e70fa4Paul Duffin */ 9730888a09821a98ac0680fad765217302858e70fa4Paul Duffin static <E> List<E> subListImpl( 9740888a09821a98ac0680fad765217302858e70fa4Paul Duffin final List<E> list, int fromIndex, int toIndex) { 9750888a09821a98ac0680fad765217302858e70fa4Paul Duffin List<E> wrapper; 9760888a09821a98ac0680fad765217302858e70fa4Paul Duffin if (list instanceof RandomAccess) { 9770888a09821a98ac0680fad765217302858e70fa4Paul Duffin wrapper = new RandomAccessListWrapper<E>(list) { 9780888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Override public ListIterator<E> listIterator(int index) { 9790888a09821a98ac0680fad765217302858e70fa4Paul Duffin return backingList.listIterator(index); 9800888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 9810888a09821a98ac0680fad765217302858e70fa4Paul Duffin 9820888a09821a98ac0680fad765217302858e70fa4Paul Duffin private static final long serialVersionUID = 0; 9830888a09821a98ac0680fad765217302858e70fa4Paul Duffin }; 9840888a09821a98ac0680fad765217302858e70fa4Paul Duffin } else { 9850888a09821a98ac0680fad765217302858e70fa4Paul Duffin wrapper = new AbstractListWrapper<E>(list) { 9860888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Override public ListIterator<E> listIterator(int index) { 9870888a09821a98ac0680fad765217302858e70fa4Paul Duffin return backingList.listIterator(index); 9880888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 9890888a09821a98ac0680fad765217302858e70fa4Paul Duffin 9900888a09821a98ac0680fad765217302858e70fa4Paul Duffin private static final long serialVersionUID = 0; 9910888a09821a98ac0680fad765217302858e70fa4Paul Duffin }; 9920888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 9930888a09821a98ac0680fad765217302858e70fa4Paul Duffin return wrapper.subList(fromIndex, toIndex); 9940888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 9950888a09821a98ac0680fad765217302858e70fa4Paul Duffin 9960888a09821a98ac0680fad765217302858e70fa4Paul Duffin private static class AbstractListWrapper<E> extends AbstractList<E> { 9970888a09821a98ac0680fad765217302858e70fa4Paul Duffin final List<E> backingList; 9980888a09821a98ac0680fad765217302858e70fa4Paul Duffin 9990888a09821a98ac0680fad765217302858e70fa4Paul Duffin AbstractListWrapper(List<E> backingList) { 10000888a09821a98ac0680fad765217302858e70fa4Paul Duffin this.backingList = checkNotNull(backingList); 10010888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 10020888a09821a98ac0680fad765217302858e70fa4Paul Duffin 10030888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Override public void add(int index, E element) { 10040888a09821a98ac0680fad765217302858e70fa4Paul Duffin backingList.add(index, element); 10050888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 10060888a09821a98ac0680fad765217302858e70fa4Paul Duffin 10070888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Override public boolean addAll(int index, Collection<? extends E> c) { 10080888a09821a98ac0680fad765217302858e70fa4Paul Duffin return backingList.addAll(index, c); 10090888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 10100888a09821a98ac0680fad765217302858e70fa4Paul Duffin 10110888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Override public E get(int index) { 10120888a09821a98ac0680fad765217302858e70fa4Paul Duffin return backingList.get(index); 10130888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 10140888a09821a98ac0680fad765217302858e70fa4Paul Duffin 10150888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Override public E remove(int index) { 10160888a09821a98ac0680fad765217302858e70fa4Paul Duffin return backingList.remove(index); 10170888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 10180888a09821a98ac0680fad765217302858e70fa4Paul Duffin 10190888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Override public E set(int index, E element) { 10200888a09821a98ac0680fad765217302858e70fa4Paul Duffin return backingList.set(index, element); 10210888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 10220888a09821a98ac0680fad765217302858e70fa4Paul Duffin 10230888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Override public boolean contains(Object o) { 10240888a09821a98ac0680fad765217302858e70fa4Paul Duffin return backingList.contains(o); 10250888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 10260888a09821a98ac0680fad765217302858e70fa4Paul Duffin 10270888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Override public int size() { 10280888a09821a98ac0680fad765217302858e70fa4Paul Duffin return backingList.size(); 10290888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 10300888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 10310888a09821a98ac0680fad765217302858e70fa4Paul Duffin 10320888a09821a98ac0680fad765217302858e70fa4Paul Duffin private static class RandomAccessListWrapper<E> 10330888a09821a98ac0680fad765217302858e70fa4Paul Duffin extends AbstractListWrapper<E> implements RandomAccess { 10340888a09821a98ac0680fad765217302858e70fa4Paul Duffin RandomAccessListWrapper(List<E> backingList) { 10350888a09821a98ac0680fad765217302858e70fa4Paul Duffin super(backingList); 10360888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 10370888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 10380888a09821a98ac0680fad765217302858e70fa4Paul Duffin 10390888a09821a98ac0680fad765217302858e70fa4Paul Duffin /** 10400888a09821a98ac0680fad765217302858e70fa4Paul Duffin * Used to avoid http://bugs.sun.com/view_bug.do?bug_id=6558557 10410888a09821a98ac0680fad765217302858e70fa4Paul Duffin */ 10420888a09821a98ac0680fad765217302858e70fa4Paul Duffin static <T> List<T> cast(Iterable<T> iterable) { 10430888a09821a98ac0680fad765217302858e70fa4Paul Duffin return (List<T>) iterable; 10440888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 10450888a09821a98ac0680fad765217302858e70fa4Paul Duffin} 1046