/*
* Copyright (C) 2007 Google Inc.
*
* Licensed under the Apache License, Version 2.0 (the "License");
* you may not use this file except in compliance with the License.
* You may obtain a copy of the License at
*
* http://www.apache.org/licenses/LICENSE-2.0
*
* Unless required by applicable law or agreed to in writing, software
* distributed under the License is distributed on an "AS IS" BASIS,
* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
* See the License for the specific language governing permissions and
* limitations under the License.
*/
package com.google.common.collect;
import com.google.common.annotations.GwtCompatible;
import com.google.common.annotations.VisibleForTesting;
import com.google.common.base.Function;
import java.io.Serializable;
import java.util.AbstractList;
import java.util.AbstractSequentialList;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.Collections;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.ListIterator;
import java.util.RandomAccess;
import javax.annotation.Nullable;
import static com.google.common.base.Preconditions.checkArgument;
import static com.google.common.base.Preconditions.checkElementIndex;
import static com.google.common.base.Preconditions.checkNotNull;
/**
* Static utility methods pertaining to {@link List} instances. Also see this
* class's counterparts {@link Sets} and {@link Maps}.
*
* @author Kevin Bourrillion
* @author Mike Bostock
* @since 2010.01.04 <b>stable</b> (imported from Google Collections Library)
*/
@GwtCompatible
public final class Lists {
private Lists() {}
// ArrayList
/**
* Creates a <i>mutable</i>, empty {@code ArrayList} instance.
*
* <p><b>Note:</b> if mutability is not required, use {@link
* ImmutableList#of()} instead.
*
* @return a new, empty {@code ArrayList}
*/
@GwtCompatible(serializable = true)
public static <E> ArrayList<E> newArrayList() {
return new ArrayList<E>();
}
/**
* Creates a <i>mutable</i> {@code ArrayList} instance containing the given
* elements.
*
* <p><b>Note:</b> if mutability is not required and the elements are
* non-null, use {@link ImmutableList#of(Object[])} instead.
*
* @param elements the elements that the list should contain, in order
* @return a new {@code ArrayList} containing those elements
*/
@GwtCompatible(serializable = true)
public static <E> ArrayList<E> newArrayList(E... elements) {
checkNotNull(elements); // for GWT
// Avoid integer overflow when a large array is passed in
int capacity = computeArrayListCapacity(elements.length);
ArrayList<E> list = new ArrayList<E>(capacity);
Collections.addAll(list, elements);
return list;
}
@VisibleForTesting static int computeArrayListCapacity(int arraySize) {
checkArgument(arraySize >= 0);
// TODO: Figure out the right behavior, and document it
return (int) Math.min(5L + arraySize + (arraySize / 10), Integer.MAX_VALUE);
}
/**
* Creates a <i>mutable</i> {@code ArrayList} instance containing the given
* elements.
*
* <p><b>Note:</b> if mutability is not required and the elements are
* non-null, use {@link ImmutableList#copyOf(Iterator)} instead.
*
* @param elements the elements that the list should contain, in order
* @return a new {@code ArrayList} containing those elements
*/
@GwtCompatible(serializable = true)
public static <E> ArrayList<E> newArrayList(Iterable<? extends E> elements) {
checkNotNull(elements); // for GWT
// Let ArrayList's sizing logic work, if possible
if (elements instanceof Collection) {
@SuppressWarnings("unchecked")
Collection<? extends E> collection = (Collection<? extends E>) elements;
return new ArrayList<E>(collection);
} else {
return newArrayList(elements.iterator());
}
}
/**
* Creates a <i>mutable</i> {@code ArrayList} instance containing the given
* elements.
*
* <p><b>Note:</b> if mutability is not required and the elements are
* non-null, use {@link ImmutableList#copyOf(Iterator)} instead.
*
* @param elements the elements that the list should contain, in order
* @return a new {@code ArrayList} containing those elements
*/
@GwtCompatible(serializable = true)
public static <E> ArrayList<E> newArrayList(Iterator<? extends E> elements) {
checkNotNull(elements); // for GWT
ArrayList<E> list = newArrayList();
while (elements.hasNext()) {
list.add(elements.next());
}
return list;
}
/**
* Creates an {@code ArrayList} instance backed by an array of the
* <i>exact</i> size specified; equivalent to
* {@link ArrayList#ArrayList(int)}.
*
* <p><b>Note:</b> if you know the exact size your list will be, consider
* using a fixed-size list ({@link Arrays#asList(Object[])}) or an {@link
* ImmutableList} instead of a growable {@link ArrayList}.
*
* <p><b>Note:</b> If you have only an <i>estimate</i> of the eventual size of
* the list, consider padding this estimate by a suitable amount, or simply
* use {@link #newArrayListWithExpectedSize(int)} instead.
*
* @param initialArraySize the exact size of the initial backing array for
* the returned array list ({@code ArrayList} documentation calls this
* value the "capacity")
* @return a new, empty {@code ArrayList} which is guaranteed not to resize
* itself unless its size reaches {@code initialArraySize + 1}
* @throws IllegalArgumentException if {@code initialArraySize} is negative
*/
@GwtCompatible(serializable = true)
public static <E> ArrayList<E> newArrayListWithCapacity(
int initialArraySize) {
return new ArrayList<E>(initialArraySize);
}
/**
* Creates an {@code ArrayList} instance sized appropriately to hold an
* <i>estimated</i> number of elements without resizing. A small amount of
* padding is added in case the estimate is low.
*
* <p><b>Note:</b> If you know the <i>exact</i> number of elements the list
* will hold, or prefer to calculate your own amount of padding, refer to
* {@link #newArrayListWithCapacity(int)}.
*
* @param estimatedSize an estimate of the eventual {@link List#size()} of
* the new list
* @return a new, empty {@code ArrayList}, sized appropriately to hold the
* estimated number of elements
* @throws IllegalArgumentException if {@code estimatedSize} is negative
*/
@GwtCompatible(serializable = true)
public static <E> ArrayList<E> newArrayListWithExpectedSize(
int estimatedSize) {
return new ArrayList<E>(computeArrayListCapacity(estimatedSize));
}
// LinkedList
/**
* Creates an empty {@code LinkedList} instance.
*
* <p><b>Note:</b> if you need an immutable empty {@link List}, use
* {@link Collections#emptyList} instead.
*
* @return a new, empty {@code LinkedList}
*/
@GwtCompatible(serializable = true)
public static <E> LinkedList<E> newLinkedList() {
return new LinkedList<E>();
}
/**
* Creates a {@code LinkedList} instance containing the given elements.
*
* @param elements the elements that the list should contain, in order
* @return a new {@code LinkedList} containing those elements
*/
@GwtCompatible(serializable = true)
public static <E> LinkedList<E> newLinkedList(
Iterable<? extends E> elements) {
LinkedList<E> list = newLinkedList();
for (E element : elements) {
list.add(element);
}
return list;
}
/**
* Returns an unmodifiable list containing the specified first element and
* backed by the specified array of additional elements. Changes to the {@code
* rest} array will be reflected in the returned list. Unlike {@link
* Arrays#asList}, the returned list is unmodifiable.
*
* <p>This is useful when a varargs method needs to use a signature such as
* {@code (Foo firstFoo, Foo... moreFoos)}, in order to avoid overload
* ambiguity or to enforce a minimum argument count.
*
* <p>The returned list is serializable and implements {@link RandomAccess}.
*
* @param first the first element
* @param rest an array of additional elements, possibly empty
* @return an unmodifiable list containing the specified elements
*/
public static <E> List<E> asList(@Nullable E first, E[] rest) {
return new OnePlusArrayList<E>(first, rest);
}
/** @see Lists#asList(Object, Object[]) */
private static class OnePlusArrayList<E> extends AbstractList<E>
implements Serializable, RandomAccess {
final E first;
final E[] rest;
OnePlusArrayList(@Nullable E first, E[] rest) {
this.first = first;
this.rest = checkNotNull(rest);
}
@Override public int size() {
return rest.length + 1;
}
@Override public E get(int index) {
// check explicitly so the IOOBE will have the right message
checkElementIndex(index, size());
return (index == 0) ? first : rest[index - 1];
}
private static final long serialVersionUID = 0;
}
/**
* Returns an unmodifiable list containing the specified first and second
* element, and backed by the specified array of additional elements. Changes
* to the {@code rest} array will be reflected in the returned list. Unlike
* {@link Arrays#asList}, the returned list is unmodifiable.
*
* <p>This is useful when a varargs method needs to use a signature such as
* {@code (Foo firstFoo, Foo secondFoo, Foo... moreFoos)}, in order to avoid
* overload ambiguity or to enforce a minimum argument count.
*
* <p>The returned list is serializable and implements {@link RandomAccess}.
*
* @param first the first element
* @param second the second element
* @param rest an array of additional elements, possibly empty
* @return an unmodifiable list containing the specified elements
*/
public static <E> List<E> asList(
@Nullable E first, @Nullable E second, E[] rest) {
return new TwoPlusArrayList<E>(first, second, rest);
}
/** @see Lists#asList(Object, Object, Object[]) */
private static class TwoPlusArrayList<E> extends AbstractList<E>
implements Serializable, RandomAccess {
final E first;
final E second;
final E[] rest;
TwoPlusArrayList(@Nullable E first, @Nullable E second, E[] rest) {
this.first = first;
this.second = second;
this.rest = checkNotNull(rest);
}
@Override public int size() {
return rest.length + 2;
}
@Override public E get(int index) {
switch (index) {
case 0:
return first;
case 1:
return second;
default:
// check explicitly so the IOOBE will have the right message
checkElementIndex(index, size());
return rest[index - 2];
}
}
private static final long serialVersionUID = 0;
}
/**
* Returns a list that applies {@code function} to each element of {@code
* fromList}. The returned list is a transformed view of {@code fromList};
* changes to {@code fromList} will be reflected in the returned list and vice
* versa.
*
* <p>Since functions are not reversible, the transform is one-way and new
* items cannot be stored in the returned list. The {@code add},
* {@code addAll} and {@code set} methods are unsupported in the returned
* list.
*
* <p>The function is applied lazily, invoked when needed. This is necessary
* for the returned list to be a view, but it means that the function will be
* applied many times for bulk operations like {@link List#contains} and
* {@link List#hashCode}. For this to perform well, {@code function} should be
* fast. To avoid lazy evaluation when the returned list doesn't need to be a
* view, copy the returned list into a new list of your choosing.
*
* <p>If {@code fromList} implements {@link RandomAccess}, so will the
* returned list. The returned list always implements {@link Serializable},
* but serialization will succeed only when {@code fromList} and
* {@code function} are serializable. The returned list is threadsafe if the
* supplied list and function are.
*/
public static <F, T> List<T> transform(
List<F> fromList, Function<? super F, ? extends T> function) {
return (fromList instanceof RandomAccess)
? new TransformingRandomAccessList<F, T>(fromList, function)
: new TransformingSequentialList<F, T>(fromList, function);
}
/**
* Implementation of a sequential transforming list.
*
* @see Lists#transform
*/
private static class TransformingSequentialList<F, T>
extends AbstractSequentialList<T> implements Serializable {
final List<F> fromList;
final Function<? super F, ? extends T> function;
TransformingSequentialList(
List<F> fromList, Function<? super F, ? extends T> function) {
this.fromList = checkNotNull(fromList);
this.function = checkNotNull(function);
}
/**
* The default implementation inherited is based on iteration and removal of
* each element which can be overkill. That's why we forward this call
* directly to the backing list.
*/
@Override public void clear() {
fromList.clear();
}
@Override public int size() {
return fromList.size();
}
@Override public ListIterator<T> listIterator(final int index) {
final ListIterator<F> delegate = fromList.listIterator(index);
return new ListIterator<T>() {
public void add(T e) {
throw new UnsupportedOperationException();
}
public boolean hasNext() {
return delegate.hasNext();
}
public boolean hasPrevious() {
return delegate.hasPrevious();
}
public T next() {
return function.apply(delegate.next());
}
public int nextIndex() {
return delegate.nextIndex();
}
public T previous() {
return function.apply(delegate.previous());
}
public int previousIndex() {
return delegate.previousIndex();
}
public void remove() {
delegate.remove();
}
public void set(T e) {
throw new UnsupportedOperationException("not supported");
}
};
}
private static final long serialVersionUID = 0;
}
/**
* Implementation of a transforming random access list. We try to make as many
* of these methods pass-through to the source list as possible so that the
* performance characteristics of the source list and transformed list are
* similar.
*
* @see Lists#transform
*/
private static class TransformingRandomAccessList<F, T>
extends AbstractList<T> implements RandomAccess, Serializable {
final List<F> fromList;
final Function<? super F, ? extends T> function;
TransformingRandomAccessList(
List<F> fromList, Function<? super F, ? extends T> function) {
this.fromList = checkNotNull(fromList);
this.function = checkNotNull(function);
}
@Override public void clear() {
fromList.clear();
}
@Override public T get(int index) {
return function.apply(fromList.get(index));
}
@Override public boolean isEmpty() {
return fromList.isEmpty();
}
@Override public T remove(int index) {
return function.apply(fromList.remove(index));
}
@Override public int size() {
return fromList.size();
}
private static final long serialVersionUID = 0;
}
/**
* Returns consecutive {@linkplain List#subList(int, int) sublists} of a list,
* each of the same size (the final list may be smaller). For example,
* partitioning a list containing {@code [a, b, c, d, e]} with a partition
* size of 3 yields {@code [[a, b, c], [d, e]]} -- an outer list containing
* two inner lists of three and two elements, all in the original order.
*
* <p>The outer list is unmodifiable, but reflects the latest state of the
* source list. The inner lists are sublist views of the original list,
* produced on demand using {@link List#subList(int, int)}, and are subject
* to all the usual caveats about modification as explained in that API.
*
* @param list the list to return consecutive sublists of
* @param size the desired size of each sublist (the last may be
* smaller)
* @return a list of consecutive sublists
* @throws IllegalArgumentException if {@code partitionSize} is nonpositive
*/
public static <T> List<List<T>> partition(List<T> list, int size) {
checkNotNull(list);
checkArgument(size > 0);
return (list instanceof RandomAccess)
? new RandomAccessPartition<T>(list, size)
: new Partition<T>(list, size);
}
private static class Partition<T> extends AbstractList<List<T>> {
final List<T> list;
final int size;
Partition(List<T> list, int size) {
this.list = list;
this.size = size;
}
@Override public List<T> get(int index) {
int listSize = size();
checkElementIndex(index, listSize);
int start = index * size;
int end = Math.min(start + size, list.size());
return Platform.subList(list, start, end);
}
@Override public int size() {
return (list.size() + size - 1) / size;
}
@Override public boolean isEmpty() {
return list.isEmpty();
}
}
private static class RandomAccessPartition<T> extends Partition<T>
implements RandomAccess {
RandomAccessPartition(List<T> list, int size) {
super(list, size);
}
}
}