001 /*
002 * Copyright (C) 2007 Google Inc.
003 *
004 * Licensed under the Apache License, Version 2.0 (the "License");
005 * you may not use this file except in compliance with the License.
006 * You may obtain a copy of the License at
007 *
008 * http://www.apache.org/licenses/LICENSE-2.0
009 *
010 * Unless required by applicable law or agreed to in writing, software
011 * distributed under the License is distributed on an "AS IS" BASIS,
012 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
013 * See the License for the specific language governing permissions and
014 * limitations under the License.
015 */
016
017 package com.google.common.collect;
018
019 import static com.google.common.base.Preconditions.checkArgument;
020 import static com.google.common.base.Preconditions.checkElementIndex;
021 import static com.google.common.base.Preconditions.checkNotNull;
022
023 import com.google.common.annotations.GwtCompatible;
024 import com.google.common.annotations.VisibleForTesting;
025 import com.google.common.base.Function;
026 import com.google.common.primitives.Ints;
027
028 import java.io.Serializable;
029 import java.util.AbstractList;
030 import java.util.AbstractSequentialList;
031 import java.util.ArrayList;
032 import java.util.Arrays;
033 import java.util.Collection;
034 import java.util.Collections;
035 import java.util.Iterator;
036 import java.util.LinkedList;
037 import java.util.List;
038 import java.util.ListIterator;
039 import java.util.RandomAccess;
040
041 import javax.annotation.Nullable;
042
043 /**
044 * Static utility methods pertaining to {@link List} instances. Also see this
045 * class's counterparts {@link Sets} and {@link Maps}.
046 *
047 * @author Kevin Bourrillion
048 * @author Mike Bostock
049 * @since 2 (imported from Google Collections Library)
050 */
051 @GwtCompatible
052 public final class Lists {
053 private Lists() {}
054
055 // ArrayList
056
057 /**
058 * Creates a <i>mutable</i>, empty {@code ArrayList} instance.
059 *
060 * <p><b>Note:</b> if mutability is not required, use {@link
061 * ImmutableList#of()} instead.
062 *
063 * @return a new, empty {@code ArrayList}
064 */
065 @GwtCompatible(serializable = true)
066 public static <E> ArrayList<E> newArrayList() {
067 return new ArrayList<E>();
068 }
069
070 /**
071 * Creates a <i>mutable</i> {@code ArrayList} instance containing the given
072 * elements.
073 *
074 * <p><b>Note:</b> if mutability is not required and the elements are
075 * non-null, use an overload of {@link ImmutableList#of()} (for varargs) or
076 * {@link ImmutableList#copyOf(Object[])} (for an array) instead.
077 *
078 * @param elements the elements that the list should contain, in order
079 * @return a new {@code ArrayList} containing those elements
080 */
081 @GwtCompatible(serializable = true)
082 public static <E> ArrayList<E> newArrayList(E... elements) {
083 checkNotNull(elements); // for GWT
084 // Avoid integer overflow when a large array is passed in
085 int capacity = computeArrayListCapacity(elements.length);
086 ArrayList<E> list = new ArrayList<E>(capacity);
087 Collections.addAll(list, elements);
088 return list;
089 }
090
091 @VisibleForTesting static int computeArrayListCapacity(int arraySize) {
092 checkArgument(arraySize >= 0);
093
094 // TODO: Figure out the right behavior, and document it
095 return Ints.saturatedCast(5L + arraySize + (arraySize / 10));
096 }
097
098 /**
099 * Creates a <i>mutable</i> {@code ArrayList} instance containing the given
100 * elements.
101 *
102 * <p><b>Note:</b> if mutability is not required and the elements are
103 * non-null, use {@link ImmutableList#copyOf(Iterator)} instead.
104 *
105 * @param elements the elements that the list should contain, in order
106 * @return a new {@code ArrayList} containing those elements
107 */
108 @GwtCompatible(serializable = true)
109 public static <E> ArrayList<E> newArrayList(Iterable<? extends E> elements) {
110 checkNotNull(elements); // for GWT
111 // Let ArrayList's sizing logic work, if possible
112 if (elements instanceof Collection) {
113 @SuppressWarnings("unchecked")
114 Collection<? extends E> collection = (Collection<? extends E>) elements;
115 return new ArrayList<E>(collection);
116 } else {
117 return newArrayList(elements.iterator());
118 }
119 }
120
121 /**
122 * Creates a <i>mutable</i> {@code ArrayList} instance containing the given
123 * elements.
124 *
125 * <p><b>Note:</b> if mutability is not required and the elements are
126 * non-null, use {@link ImmutableList#copyOf(Iterator)} instead.
127 *
128 * @param elements the elements that the list should contain, in order
129 * @return a new {@code ArrayList} containing those elements
130 */
131 @GwtCompatible(serializable = true)
132 public static <E> ArrayList<E> newArrayList(Iterator<? extends E> elements) {
133 checkNotNull(elements); // for GWT
134 ArrayList<E> list = newArrayList();
135 while (elements.hasNext()) {
136 list.add(elements.next());
137 }
138 return list;
139 }
140
141 /**
142 * Creates an {@code ArrayList} instance backed by an array of the
143 * <i>exact</i> size specified; equivalent to
144 * {@link ArrayList#ArrayList(int)}.
145 *
146 * <p><b>Note:</b> if you know the exact size your list will be, consider
147 * using a fixed-size list ({@link Arrays#asList(Object[])}) or an {@link
148 * ImmutableList} instead of a growable {@link ArrayList}.
149 *
150 * <p><b>Note:</b> If you have only an <i>estimate</i> of the eventual size of
151 * the list, consider padding this estimate by a suitable amount, or simply
152 * use {@link #newArrayListWithExpectedSize(int)} instead.
153 *
154 * @param initialArraySize the exact size of the initial backing array for
155 * the returned array list ({@code ArrayList} documentation calls this
156 * value the "capacity")
157 * @return a new, empty {@code ArrayList} which is guaranteed not to resize
158 * itself unless its size reaches {@code initialArraySize + 1}
159 * @throws IllegalArgumentException if {@code initialArraySize} is negative
160 */
161 @GwtCompatible(serializable = true)
162 public static <E> ArrayList<E> newArrayListWithCapacity(
163 int initialArraySize) {
164 return new ArrayList<E>(initialArraySize);
165 }
166
167 /**
168 * Creates an {@code ArrayList} instance sized appropriately to hold an
169 * <i>estimated</i> number of elements without resizing. A small amount of
170 * padding is added in case the estimate is low.
171 *
172 * <p><b>Note:</b> If you know the <i>exact</i> number of elements the list
173 * will hold, or prefer to calculate your own amount of padding, refer to
174 * {@link #newArrayListWithCapacity(int)}.
175 *
176 * @param estimatedSize an estimate of the eventual {@link List#size()} of
177 * the new list
178 * @return a new, empty {@code ArrayList}, sized appropriately to hold the
179 * estimated number of elements
180 * @throws IllegalArgumentException if {@code estimatedSize} is negative
181 */
182 @GwtCompatible(serializable = true)
183 public static <E> ArrayList<E> newArrayListWithExpectedSize(
184 int estimatedSize) {
185 return new ArrayList<E>(computeArrayListCapacity(estimatedSize));
186 }
187
188 // LinkedList
189
190 /**
191 * Creates an empty {@code LinkedList} instance.
192 *
193 * <p><b>Note:</b> if you need an immutable empty {@link List}, use
194 * {@link Collections#emptyList} instead.
195 *
196 * @return a new, empty {@code LinkedList}
197 */
198 @GwtCompatible(serializable = true)
199 public static <E> LinkedList<E> newLinkedList() {
200 return new LinkedList<E>();
201 }
202
203 /**
204 * Creates a {@code LinkedList} instance containing the given elements.
205 *
206 * @param elements the elements that the list should contain, in order
207 * @return a new {@code LinkedList} containing those elements
208 */
209 @GwtCompatible(serializable = true)
210 public static <E> LinkedList<E> newLinkedList(
211 Iterable<? extends E> elements) {
212 LinkedList<E> list = newLinkedList();
213 for (E element : elements) {
214 list.add(element);
215 }
216 return list;
217 }
218
219 /**
220 * Returns an unmodifiable list containing the specified first element and
221 * backed by the specified array of additional elements. Changes to the {@code
222 * rest} array will be reflected in the returned list. Unlike {@link
223 * Arrays#asList}, the returned list is unmodifiable.
224 *
225 * <p>This is useful when a varargs method needs to use a signature such as
226 * {@code (Foo firstFoo, Foo... moreFoos)}, in order to avoid overload
227 * ambiguity or to enforce a minimum argument count.
228 *
229 * <p>The returned list is serializable and implements {@link RandomAccess}.
230 *
231 * @param first the first element
232 * @param rest an array of additional elements, possibly empty
233 * @return an unmodifiable list containing the specified elements
234 */
235 public static <E> List<E> asList(@Nullable E first, E[] rest) {
236 return new OnePlusArrayList<E>(first, rest);
237 }
238
239 /** @see Lists#asList(Object, Object[]) */
240 private static class OnePlusArrayList<E> extends AbstractList<E>
241 implements Serializable, RandomAccess {
242 final E first;
243 final E[] rest;
244
245 OnePlusArrayList(@Nullable E first, E[] rest) {
246 this.first = first;
247 this.rest = checkNotNull(rest);
248 }
249 @Override public int size() {
250 return rest.length + 1;
251 }
252 @Override public E get(int index) {
253 // check explicitly so the IOOBE will have the right message
254 checkElementIndex(index, size());
255 return (index == 0) ? first : rest[index - 1];
256 }
257 private static final long serialVersionUID = 0;
258 }
259
260 /**
261 * Returns an unmodifiable list containing the specified first and second
262 * element, and backed by the specified array of additional elements. Changes
263 * to the {@code rest} array will be reflected in the returned list. Unlike
264 * {@link Arrays#asList}, the returned list is unmodifiable.
265 *
266 * <p>This is useful when a varargs method needs to use a signature such as
267 * {@code (Foo firstFoo, Foo secondFoo, Foo... moreFoos)}, in order to avoid
268 * overload ambiguity or to enforce a minimum argument count.
269 *
270 * <p>The returned list is serializable and implements {@link RandomAccess}.
271 *
272 * @param first the first element
273 * @param second the second element
274 * @param rest an array of additional elements, possibly empty
275 * @return an unmodifiable list containing the specified elements
276 */
277 public static <E> List<E> asList(
278 @Nullable E first, @Nullable E second, E[] rest) {
279 return new TwoPlusArrayList<E>(first, second, rest);
280 }
281
282 /** @see Lists#asList(Object, Object, Object[]) */
283 private static class TwoPlusArrayList<E> extends AbstractList<E>
284 implements Serializable, RandomAccess {
285 final E first;
286 final E second;
287 final E[] rest;
288
289 TwoPlusArrayList(@Nullable E first, @Nullable E second, E[] rest) {
290 this.first = first;
291 this.second = second;
292 this.rest = checkNotNull(rest);
293 }
294 @Override public int size() {
295 return rest.length + 2;
296 }
297 @Override public E get(int index) {
298 switch (index) {
299 case 0:
300 return first;
301 case 1:
302 return second;
303 default:
304 // check explicitly so the IOOBE will have the right message
305 checkElementIndex(index, size());
306 return rest[index - 2];
307 }
308 }
309 private static final long serialVersionUID = 0;
310 }
311
312 /**
313 * Returns a list that applies {@code function} to each element of {@code
314 * fromList}. The returned list is a transformed view of {@code fromList};
315 * changes to {@code fromList} will be reflected in the returned list and vice
316 * versa.
317 *
318 * <p>Since functions are not reversible, the transform is one-way and new
319 * items cannot be stored in the returned list. The {@code add},
320 * {@code addAll} and {@code set} methods are unsupported in the returned
321 * list.
322 *
323 * <p>The function is applied lazily, invoked when needed. This is necessary
324 * for the returned list to be a view, but it means that the function will be
325 * applied many times for bulk operations like {@link List#contains} and
326 * {@link List#hashCode}. For this to perform well, {@code function} should be
327 * fast. To avoid lazy evaluation when the returned list doesn't need to be a
328 * view, copy the returned list into a new list of your choosing.
329 *
330 * <p>If {@code fromList} implements {@link RandomAccess}, so will the
331 * returned list. The returned list always implements {@link Serializable},
332 * but serialization will succeed only when {@code fromList} and
333 * {@code function} are serializable. The returned list is threadsafe if the
334 * supplied list and function are.
335 */
336 public static <F, T> List<T> transform(
337 List<F> fromList, Function<? super F, ? extends T> function) {
338 return (fromList instanceof RandomAccess)
339 ? new TransformingRandomAccessList<F, T>(fromList, function)
340 : new TransformingSequentialList<F, T>(fromList, function);
341 }
342
343 /**
344 * Implementation of a sequential transforming list.
345 *
346 * @see Lists#transform
347 */
348 private static class TransformingSequentialList<F, T>
349 extends AbstractSequentialList<T> implements Serializable {
350 final List<F> fromList;
351 final Function<? super F, ? extends T> function;
352
353 TransformingSequentialList(
354 List<F> fromList, Function<? super F, ? extends T> function) {
355 this.fromList = checkNotNull(fromList);
356 this.function = checkNotNull(function);
357 }
358 /**
359 * The default implementation inherited is based on iteration and removal of
360 * each element which can be overkill. That's why we forward this call
361 * directly to the backing list.
362 */
363 @Override public void clear() {
364 fromList.clear();
365 }
366 @Override public int size() {
367 return fromList.size();
368 }
369 @Override public ListIterator<T> listIterator(final int index) {
370 final ListIterator<F> delegate = fromList.listIterator(index);
371 return new ListIterator<T>() {
372 public void add(T e) {
373 throw new UnsupportedOperationException();
374 }
375
376 public boolean hasNext() {
377 return delegate.hasNext();
378 }
379
380 public boolean hasPrevious() {
381 return delegate.hasPrevious();
382 }
383
384 public T next() {
385 return function.apply(delegate.next());
386 }
387
388 public int nextIndex() {
389 return delegate.nextIndex();
390 }
391
392 public T previous() {
393 return function.apply(delegate.previous());
394 }
395
396 public int previousIndex() {
397 return delegate.previousIndex();
398 }
399
400 public void remove() {
401 delegate.remove();
402 }
403
404 public void set(T e) {
405 throw new UnsupportedOperationException("not supported");
406 }
407 };
408 }
409
410 private static final long serialVersionUID = 0;
411 }
412
413 /**
414 * Implementation of a transforming random access list. We try to make as many
415 * of these methods pass-through to the source list as possible so that the
416 * performance characteristics of the source list and transformed list are
417 * similar.
418 *
419 * @see Lists#transform
420 */
421 private static class TransformingRandomAccessList<F, T>
422 extends AbstractList<T> implements RandomAccess, Serializable {
423 final List<F> fromList;
424 final Function<? super F, ? extends T> function;
425
426 TransformingRandomAccessList(
427 List<F> fromList, Function<? super F, ? extends T> function) {
428 this.fromList = checkNotNull(fromList);
429 this.function = checkNotNull(function);
430 }
431 @Override public void clear() {
432 fromList.clear();
433 }
434 @Override public T get(int index) {
435 return function.apply(fromList.get(index));
436 }
437 @Override public boolean isEmpty() {
438 return fromList.isEmpty();
439 }
440 @Override public T remove(int index) {
441 return function.apply(fromList.remove(index));
442 }
443 @Override public int size() {
444 return fromList.size();
445 }
446 private static final long serialVersionUID = 0;
447 }
448
449 /**
450 * Returns consecutive {@linkplain List#subList(int, int) sublists} of a list,
451 * each of the same size (the final list may be smaller). For example,
452 * partitioning a list containing {@code [a, b, c, d, e]} with a partition
453 * size of 3 yields {@code [[a, b, c], [d, e]]} -- an outer list containing
454 * two inner lists of three and two elements, all in the original order.
455 *
456 * <p>The outer list is unmodifiable, but reflects the latest state of the
457 * source list. The inner lists are sublist views of the original list,
458 * produced on demand using {@link List#subList(int, int)}, and are subject
459 * to all the usual caveats about modification as explained in that API.
460 *
461 * @param list the list to return consecutive sublists of
462 * @param size the desired size of each sublist (the last may be
463 * smaller)
464 * @return a list of consecutive sublists
465 * @throws IllegalArgumentException if {@code partitionSize} is nonpositive
466 */
467 public static <T> List<List<T>> partition(List<T> list, int size) {
468 checkNotNull(list);
469 checkArgument(size > 0);
470 return (list instanceof RandomAccess)
471 ? new RandomAccessPartition<T>(list, size)
472 : new Partition<T>(list, size);
473 }
474
475 private static class Partition<T> extends AbstractList<List<T>> {
476 final List<T> list;
477 final int size;
478
479 Partition(List<T> list, int size) {
480 this.list = list;
481 this.size = size;
482 }
483
484 @Override public List<T> get(int index) {
485 int listSize = size();
486 checkElementIndex(index, listSize);
487 int start = index * size;
488 int end = Math.min(start + size, list.size());
489 return list.subList(start, end);
490 }
491
492 @Override public int size() {
493 return (list.size() + size - 1) / size;
494 }
495
496 @Override public boolean isEmpty() {
497 return list.isEmpty();
498 }
499 }
500
501 private static class RandomAccessPartition<T> extends Partition<T>
502 implements RandomAccess {
503 RandomAccessPartition(List<T> list, int size) {
504 super(list, size);
505 }
506 }
507 }