001 /*
002 * Copyright (C) 2007 The Guava Authors
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 import static com.google.common.base.Preconditions.checkPositionIndex;
023 import static com.google.common.base.Preconditions.checkPositionIndexes;
024 import static com.google.common.base.Preconditions.checkState;
025
026 import com.google.common.annotations.Beta;
027 import com.google.common.annotations.GwtCompatible;
028 import com.google.common.annotations.GwtIncompatible;
029 import com.google.common.annotations.VisibleForTesting;
030 import com.google.common.base.Function;
031 import com.google.common.base.Objects;
032 import com.google.common.primitives.Ints;
033
034 import java.io.Serializable;
035 import java.util.AbstractList;
036 import java.util.AbstractSequentialList;
037 import java.util.ArrayList;
038 import java.util.Arrays;
039 import java.util.Collection;
040 import java.util.Collections;
041 import java.util.Iterator;
042 import java.util.LinkedList;
043 import java.util.List;
044 import java.util.ListIterator;
045 import java.util.NoSuchElementException;
046 import java.util.RandomAccess;
047 import java.util.concurrent.CopyOnWriteArrayList;
048
049 import javax.annotation.Nullable;
050
051 /**
052 * Static utility methods pertaining to {@link List} instances. Also see this
053 * class's counterparts {@link Sets} and {@link Maps}.
054 *
055 * <p>See the Guava User Guide article on <a href=
056 * "http://code.google.com/p/guava-libraries/wiki/CollectionUtilitiesExplained#Lists">
057 * {@code Lists}</a>.
058 *
059 * @author Kevin Bourrillion
060 * @author Mike Bostock
061 * @author Louis Wasserman
062 * @since 2.0 (imported from Google Collections Library)
063 */
064 @GwtCompatible(emulated = true)
065 public final class Lists {
066 private Lists() {}
067
068 // ArrayList
069
070 /**
071 * Creates a <i>mutable</i>, empty {@code ArrayList} instance.
072 *
073 * <p><b>Note:</b> if mutability is not required, use {@link
074 * ImmutableList#of()} instead.
075 *
076 * @return a new, empty {@code ArrayList}
077 */
078 @GwtCompatible(serializable = true)
079 public static <E> ArrayList<E> newArrayList() {
080 return new ArrayList<E>();
081 }
082
083 /**
084 * Creates a <i>mutable</i> {@code ArrayList} instance containing the given
085 * elements.
086 *
087 * <p><b>Note:</b> if mutability is not required and the elements are
088 * non-null, use an overload of {@link ImmutableList#of()} (for varargs) or
089 * {@link ImmutableList#copyOf(Object[])} (for an array) instead.
090 *
091 * @param elements the elements that the list should contain, in order
092 * @return a new {@code ArrayList} containing those elements
093 */
094 @GwtCompatible(serializable = true)
095 public static <E> ArrayList<E> newArrayList(E... elements) {
096 checkNotNull(elements); // for GWT
097 // Avoid integer overflow when a large array is passed in
098 int capacity = computeArrayListCapacity(elements.length);
099 ArrayList<E> list = new ArrayList<E>(capacity);
100 Collections.addAll(list, elements);
101 return list;
102 }
103
104 @VisibleForTesting static int computeArrayListCapacity(int arraySize) {
105 checkArgument(arraySize >= 0);
106
107 // TODO(kevinb): Figure out the right behavior, and document it
108 return Ints.saturatedCast(5L + arraySize + (arraySize / 10));
109 }
110
111 /**
112 * Creates a <i>mutable</i> {@code ArrayList} instance containing the given
113 * elements.
114 *
115 * <p><b>Note:</b> if mutability is not required and the elements are
116 * non-null, use {@link ImmutableList#copyOf(Iterator)} instead.
117 *
118 * @param elements the elements that the list should contain, in order
119 * @return a new {@code ArrayList} containing those elements
120 */
121 @GwtCompatible(serializable = true)
122 public static <E> ArrayList<E> newArrayList(Iterable<? extends E> elements) {
123 checkNotNull(elements); // for GWT
124 // Let ArrayList's sizing logic work, if possible
125 return (elements instanceof Collection)
126 ? new ArrayList<E>(Collections2.cast(elements))
127 : newArrayList(elements.iterator());
128 }
129
130 /**
131 * Creates a <i>mutable</i> {@code ArrayList} instance containing the given
132 * elements.
133 *
134 * <p><b>Note:</b> if mutability is not required and the elements are
135 * non-null, use {@link ImmutableList#copyOf(Iterator)} instead.
136 *
137 * @param elements the elements that the list should contain, in order
138 * @return a new {@code ArrayList} containing those elements
139 */
140 @GwtCompatible(serializable = true)
141 public static <E> ArrayList<E> newArrayList(Iterator<? extends E> elements) {
142 checkNotNull(elements); // for GWT
143 ArrayList<E> list = newArrayList();
144 while (elements.hasNext()) {
145 list.add(elements.next());
146 }
147 return list;
148 }
149
150 /**
151 * Creates an {@code ArrayList} instance backed by an array of the
152 * <i>exact</i> size specified; equivalent to
153 * {@link ArrayList#ArrayList(int)}.
154 *
155 * <p><b>Note:</b> if you know the exact size your list will be, consider
156 * using a fixed-size list ({@link Arrays#asList(Object[])}) or an {@link
157 * ImmutableList} instead of a growable {@link ArrayList}.
158 *
159 * <p><b>Note:</b> If you have only an <i>estimate</i> of the eventual size of
160 * the list, consider padding this estimate by a suitable amount, or simply
161 * use {@link #newArrayListWithExpectedSize(int)} instead.
162 *
163 * @param initialArraySize the exact size of the initial backing array for
164 * the returned array list ({@code ArrayList} documentation calls this
165 * value the "capacity")
166 * @return a new, empty {@code ArrayList} which is guaranteed not to resize
167 * itself unless its size reaches {@code initialArraySize + 1}
168 * @throws IllegalArgumentException if {@code initialArraySize} is negative
169 */
170 @GwtCompatible(serializable = true)
171 public static <E> ArrayList<E> newArrayListWithCapacity(
172 int initialArraySize) {
173 checkArgument(initialArraySize >= 0); // for GWT.
174 return new ArrayList<E>(initialArraySize);
175 }
176
177 /**
178 * Creates an {@code ArrayList} instance sized appropriately to hold an
179 * <i>estimated</i> number of elements without resizing. A small amount of
180 * padding is added in case the estimate is low.
181 *
182 * <p><b>Note:</b> If you know the <i>exact</i> number of elements the list
183 * will hold, or prefer to calculate your own amount of padding, refer to
184 * {@link #newArrayListWithCapacity(int)}.
185 *
186 * @param estimatedSize an estimate of the eventual {@link List#size()} of
187 * the new list
188 * @return a new, empty {@code ArrayList}, sized appropriately to hold the
189 * estimated number of elements
190 * @throws IllegalArgumentException if {@code estimatedSize} is negative
191 */
192 @GwtCompatible(serializable = true)
193 public static <E> ArrayList<E> newArrayListWithExpectedSize(
194 int estimatedSize) {
195 return new ArrayList<E>(computeArrayListCapacity(estimatedSize));
196 }
197
198 // LinkedList
199
200 /**
201 * Creates an empty {@code LinkedList} instance.
202 *
203 * <p><b>Note:</b> if you need an immutable empty {@link List}, use
204 * {@link ImmutableList#of()} instead.
205 *
206 * @return a new, empty {@code LinkedList}
207 */
208 @GwtCompatible(serializable = true)
209 public static <E> LinkedList<E> newLinkedList() {
210 return new LinkedList<E>();
211 }
212
213 /**
214 * Creates a {@code LinkedList} instance containing the given elements.
215 *
216 * @param elements the elements that the list should contain, in order
217 * @return a new {@code LinkedList} containing those elements
218 */
219 @GwtCompatible(serializable = true)
220 public static <E> LinkedList<E> newLinkedList(
221 Iterable<? extends E> elements) {
222 LinkedList<E> list = newLinkedList();
223 for (E element : elements) {
224 list.add(element);
225 }
226 return list;
227 }
228
229 /**
230 * Creates an empty {@code CopyOnWriteArrayList} instance.
231 *
232 * <p><b>Note:</b> if you need an immutable empty {@link List}, use
233 * {@link Collections#emptyList} instead.
234 *
235 * @return a new, empty {@code CopyOnWriteArrayList}
236 * @since 12.0
237 */
238 @Beta
239 @GwtIncompatible("CopyOnWriteArrayList")
240 public static <E> CopyOnWriteArrayList<E> newCopyOnWriteArrayList() {
241 return new CopyOnWriteArrayList<E>();
242 }
243
244 /**
245 * Creates a {@code CopyOnWriteArrayList} instance containing the given elements.
246 *
247 * @param elements the elements that the list should contain, in order
248 * @return a new {@code CopyOnWriteArrayList} containing those elements
249 * @since 12.0
250 */
251 @Beta
252 @GwtIncompatible("CopyOnWriteArrayList")
253 public static <E> CopyOnWriteArrayList<E> newCopyOnWriteArrayList(
254 Iterable<? extends E> elements) {
255 // We copy elements to an ArrayList first, rather than incurring the
256 // quadratic cost of adding them to the COWAL directly.
257 Collection<? extends E> elementsCollection = (elements instanceof Collection)
258 ? Collections2.cast(elements)
259 : newArrayList(elements);
260 return new CopyOnWriteArrayList<E>(elementsCollection);
261 }
262
263 /**
264 * Returns an unmodifiable list containing the specified first element and
265 * backed by the specified array of additional elements. Changes to the {@code
266 * rest} array will be reflected in the returned list. Unlike {@link
267 * Arrays#asList}, the returned list is unmodifiable.
268 *
269 * <p>This is useful when a varargs method needs to use a signature such as
270 * {@code (Foo firstFoo, Foo... moreFoos)}, in order to avoid overload
271 * ambiguity or to enforce a minimum argument count.
272 *
273 * <p>The returned list is serializable and implements {@link RandomAccess}.
274 *
275 * @param first the first element
276 * @param rest an array of additional elements, possibly empty
277 * @return an unmodifiable list containing the specified elements
278 */
279 public static <E> List<E> asList(@Nullable E first, E[] rest) {
280 return new OnePlusArrayList<E>(first, rest);
281 }
282
283 /** @see Lists#asList(Object, Object[]) */
284 private static class OnePlusArrayList<E> extends AbstractList<E>
285 implements Serializable, RandomAccess {
286 final E first;
287 final E[] rest;
288
289 OnePlusArrayList(@Nullable E first, E[] rest) {
290 this.first = first;
291 this.rest = checkNotNull(rest);
292 }
293 @Override public int size() {
294 return rest.length + 1;
295 }
296 @Override public E get(int index) {
297 // check explicitly so the IOOBE will have the right message
298 checkElementIndex(index, size());
299 return (index == 0) ? first : rest[index - 1];
300 }
301 private static final long serialVersionUID = 0;
302 }
303
304 /**
305 * Returns an unmodifiable list containing the specified first and second
306 * element, and backed by the specified array of additional elements. Changes
307 * to the {@code rest} array will be reflected in the returned list. Unlike
308 * {@link Arrays#asList}, the returned list is unmodifiable.
309 *
310 * <p>This is useful when a varargs method needs to use a signature such as
311 * {@code (Foo firstFoo, Foo secondFoo, Foo... moreFoos)}, in order to avoid
312 * overload ambiguity or to enforce a minimum argument count.
313 *
314 * <p>The returned list is serializable and implements {@link RandomAccess}.
315 *
316 * @param first the first element
317 * @param second the second element
318 * @param rest an array of additional elements, possibly empty
319 * @return an unmodifiable list containing the specified elements
320 */
321 public static <E> List<E> asList(
322 @Nullable E first, @Nullable E second, E[] rest) {
323 return new TwoPlusArrayList<E>(first, second, rest);
324 }
325
326 /** @see Lists#asList(Object, Object, Object[]) */
327 private static class TwoPlusArrayList<E> extends AbstractList<E>
328 implements Serializable, RandomAccess {
329 final E first;
330 final E second;
331 final E[] rest;
332
333 TwoPlusArrayList(@Nullable E first, @Nullable E second, E[] rest) {
334 this.first = first;
335 this.second = second;
336 this.rest = checkNotNull(rest);
337 }
338 @Override public int size() {
339 return rest.length + 2;
340 }
341 @Override public E get(int index) {
342 switch (index) {
343 case 0:
344 return first;
345 case 1:
346 return second;
347 default:
348 // check explicitly so the IOOBE will have the right message
349 checkElementIndex(index, size());
350 return rest[index - 2];
351 }
352 }
353 private static final long serialVersionUID = 0;
354 }
355
356 /**
357 * Returns a list that applies {@code function} to each element of {@code
358 * fromList}. The returned list is a transformed view of {@code fromList};
359 * changes to {@code fromList} will be reflected in the returned list and vice
360 * versa.
361 *
362 * <p>Since functions are not reversible, the transform is one-way and new
363 * items cannot be stored in the returned list. The {@code add},
364 * {@code addAll} and {@code set} methods are unsupported in the returned
365 * list.
366 *
367 * <p>The function is applied lazily, invoked when needed. This is necessary
368 * for the returned list to be a view, but it means that the function will be
369 * applied many times for bulk operations like {@link List#contains} and
370 * {@link List#hashCode}. For this to perform well, {@code function} should be
371 * fast. To avoid lazy evaluation when the returned list doesn't need to be a
372 * view, copy the returned list into a new list of your choosing.
373 *
374 * <p>If {@code fromList} implements {@link RandomAccess}, so will the
375 * returned list. The returned list always implements {@link Serializable},
376 * but serialization will succeed only when {@code fromList} and
377 * {@code function} are serializable. The returned list is threadsafe if the
378 * supplied list and function are.
379 *
380 * <p>If only a {@code Collection} or {@code Iterable} input is available, use
381 * {@link Collections2#transform} or {@link Iterables#transform}.
382 */
383 public static <F, T> List<T> transform(
384 List<F> fromList, Function<? super F, ? extends T> function) {
385 return (fromList instanceof RandomAccess)
386 ? new TransformingRandomAccessList<F, T>(fromList, function)
387 : new TransformingSequentialList<F, T>(fromList, function);
388 }
389
390 /**
391 * Implementation of a sequential transforming list.
392 *
393 * @see Lists#transform
394 */
395 private static class TransformingSequentialList<F, T>
396 extends AbstractSequentialList<T> implements Serializable {
397 final List<F> fromList;
398 final Function<? super F, ? extends T> function;
399
400 TransformingSequentialList(
401 List<F> fromList, Function<? super F, ? extends T> function) {
402 this.fromList = checkNotNull(fromList);
403 this.function = checkNotNull(function);
404 }
405 /**
406 * The default implementation inherited is based on iteration and removal of
407 * each element which can be overkill. That's why we forward this call
408 * directly to the backing list.
409 */
410 @Override public void clear() {
411 fromList.clear();
412 }
413 @Override public int size() {
414 return fromList.size();
415 }
416 @Override public ListIterator<T> listIterator(final int index) {
417 final ListIterator<F> delegate = fromList.listIterator(index);
418 return new ListIterator<T>() {
419 @Override
420 public void add(T e) {
421 throw new UnsupportedOperationException();
422 }
423
424 @Override
425 public boolean hasNext() {
426 return delegate.hasNext();
427 }
428
429 @Override
430 public boolean hasPrevious() {
431 return delegate.hasPrevious();
432 }
433
434 @Override
435 public T next() {
436 return function.apply(delegate.next());
437 }
438
439 @Override
440 public int nextIndex() {
441 return delegate.nextIndex();
442 }
443
444 @Override
445 public T previous() {
446 return function.apply(delegate.previous());
447 }
448
449 @Override
450 public int previousIndex() {
451 return delegate.previousIndex();
452 }
453
454 @Override
455 public void remove() {
456 delegate.remove();
457 }
458
459 @Override
460 public void set(T e) {
461 throw new UnsupportedOperationException("not supported");
462 }
463 };
464 }
465
466 private static final long serialVersionUID = 0;
467 }
468
469 /**
470 * Implementation of a transforming random access list. We try to make as many
471 * of these methods pass-through to the source list as possible so that the
472 * performance characteristics of the source list and transformed list are
473 * similar.
474 *
475 * @see Lists#transform
476 */
477 private static class TransformingRandomAccessList<F, T>
478 extends AbstractList<T> implements RandomAccess, Serializable {
479 final List<F> fromList;
480 final Function<? super F, ? extends T> function;
481
482 TransformingRandomAccessList(
483 List<F> fromList, Function<? super F, ? extends T> function) {
484 this.fromList = checkNotNull(fromList);
485 this.function = checkNotNull(function);
486 }
487 @Override public void clear() {
488 fromList.clear();
489 }
490 @Override public T get(int index) {
491 return function.apply(fromList.get(index));
492 }
493 @Override public boolean isEmpty() {
494 return fromList.isEmpty();
495 }
496 @Override public T remove(int index) {
497 return function.apply(fromList.remove(index));
498 }
499 @Override public int size() {
500 return fromList.size();
501 }
502 private static final long serialVersionUID = 0;
503 }
504
505 /**
506 * Returns consecutive {@linkplain List#subList(int, int) sublists} of a list,
507 * each of the same size (the final list may be smaller). For example,
508 * partitioning a list containing {@code [a, b, c, d, e]} with a partition
509 * size of 3 yields {@code [[a, b, c], [d, e]]} -- an outer list containing
510 * two inner lists of three and two elements, all in the original order.
511 *
512 * <p>The outer list is unmodifiable, but reflects the latest state of the
513 * source list. The inner lists are sublist views of the original list,
514 * produced on demand using {@link List#subList(int, int)}, and are subject
515 * to all the usual caveats about modification as explained in that API.
516 *
517 * @param list the list to return consecutive sublists of
518 * @param size the desired size of each sublist (the last may be
519 * smaller)
520 * @return a list of consecutive sublists
521 * @throws IllegalArgumentException if {@code partitionSize} is nonpositive
522 */
523 public static <T> List<List<T>> partition(List<T> list, int size) {
524 checkNotNull(list);
525 checkArgument(size > 0);
526 return (list instanceof RandomAccess)
527 ? new RandomAccessPartition<T>(list, size)
528 : new Partition<T>(list, size);
529 }
530
531 private static class Partition<T> extends AbstractList<List<T>> {
532 final List<T> list;
533 final int size;
534
535 Partition(List<T> list, int size) {
536 this.list = list;
537 this.size = size;
538 }
539
540 @Override public List<T> get(int index) {
541 int listSize = size();
542 checkElementIndex(index, listSize);
543 int start = index * size;
544 int end = Math.min(start + size, list.size());
545 return list.subList(start, end);
546 }
547
548 @Override public int size() {
549 // TODO(user): refactor to common.math.IntMath.divide
550 int result = list.size() / size;
551 if (result * size != list.size()) {
552 result++;
553 }
554 return result;
555 }
556
557 @Override public boolean isEmpty() {
558 return list.isEmpty();
559 }
560 }
561
562 private static class RandomAccessPartition<T> extends Partition<T>
563 implements RandomAccess {
564 RandomAccessPartition(List<T> list, int size) {
565 super(list, size);
566 }
567 }
568
569 /**
570 * Returns a view of the specified string as an immutable list of {@code
571 * Character} values.
572 *
573 * @since 7.0
574 */
575 @Beta public static ImmutableList<Character> charactersOf(String string) {
576 return new StringAsImmutableList(checkNotNull(string));
577 }
578
579 @SuppressWarnings("serial") // serialized using ImmutableList serialization
580 private static final class StringAsImmutableList
581 extends ImmutableList<Character> {
582
583 private final String string;
584
585 StringAsImmutableList(String string) {
586 this.string = string;
587 }
588
589 @Override public int indexOf(@Nullable Object object) {
590 return (object instanceof Character)
591 ? string.indexOf((Character) object) : -1;
592 }
593
594 @Override public int lastIndexOf(@Nullable Object object) {
595 return (object instanceof Character)
596 ? string.lastIndexOf((Character) object) : -1;
597 }
598
599 @Override public ImmutableList<Character> subList(
600 int fromIndex, int toIndex) {
601 checkPositionIndexes(fromIndex, toIndex, size()); // for GWT
602 return charactersOf(string.substring(fromIndex, toIndex));
603 }
604
605 @Override boolean isPartialView() {
606 return false;
607 }
608
609 @Override public Character get(int index) {
610 checkElementIndex(index, size()); // for GWT
611 return string.charAt(index);
612 }
613
614 @Override public int size() {
615 return string.length();
616 }
617
618 @Override public boolean equals(@Nullable Object obj) {
619 if (!(obj instanceof List)) {
620 return false;
621 }
622 List<?> list = (List<?>) obj;
623 int n = string.length();
624 if (n != list.size()) {
625 return false;
626 }
627 Iterator<?> iterator = list.iterator();
628 for (int i = 0; i < n; i++) {
629 Object elem = iterator.next();
630 if (!(elem instanceof Character)
631 || ((Character) elem).charValue() != string.charAt(i)) {
632 return false;
633 }
634 }
635 return true;
636 }
637
638 int hash = 0;
639
640 @Override public int hashCode() {
641 int h = hash;
642 if (h == 0) {
643 h = 1;
644 for (int i = 0; i < string.length(); i++) {
645 h = h * 31 + string.charAt(i);
646 }
647 hash = h;
648 }
649 return h;
650 }
651 }
652
653 /**
654 * Returns a view of the specified {@code CharSequence} as a {@code
655 * List<Character>}, viewing {@code sequence} as a sequence of Unicode code
656 * units. The view does not support any modification operations, but reflects
657 * any changes to the underlying character sequence.
658 *
659 * @param sequence the character sequence to view as a {@code List} of
660 * characters
661 * @return an {@code List<Character>} view of the character sequence
662 * @since 7.0
663 */
664 @Beta public static List<Character> charactersOf(CharSequence sequence) {
665 return new CharSequenceAsList(checkNotNull(sequence));
666 }
667
668 private static final class CharSequenceAsList
669 extends AbstractList<Character> {
670 private final CharSequence sequence;
671
672 CharSequenceAsList(CharSequence sequence) {
673 this.sequence = sequence;
674 }
675
676 @Override public Character get(int index) {
677 checkElementIndex(index, size()); // for GWT
678 return sequence.charAt(index);
679 }
680
681 @Override public boolean contains(@Nullable Object o) {
682 return indexOf(o) >= 0;
683 }
684
685 @Override public int indexOf(@Nullable Object o) {
686 if (o instanceof Character) {
687 char c = (Character) o;
688 for (int i = 0; i < sequence.length(); i++) {
689 if (sequence.charAt(i) == c) {
690 return i;
691 }
692 }
693 }
694 return -1;
695 }
696
697 @Override public int lastIndexOf(@Nullable Object o) {
698 if (o instanceof Character) {
699 char c = ((Character) o).charValue();
700 for (int i = sequence.length() - 1; i >= 0; i--) {
701 if (sequence.charAt(i) == c) {
702 return i;
703 }
704 }
705 }
706 return -1;
707 }
708
709 @Override public int size() {
710 return sequence.length();
711 }
712
713 @Override public List<Character> subList(int fromIndex, int toIndex) {
714 checkPositionIndexes(fromIndex, toIndex, size()); // for GWT
715 return charactersOf(sequence.subSequence(fromIndex, toIndex));
716 }
717
718 @Override public int hashCode() {
719 int hash = 1;
720 for (int i = 0; i < sequence.length(); i++) {
721 hash = hash * 31 + sequence.charAt(i);
722 }
723 return hash;
724 }
725
726 @Override public boolean equals(@Nullable Object o) {
727 if (!(o instanceof List)) {
728 return false;
729 }
730 List<?> list = (List<?>) o;
731 int n = sequence.length();
732 if (n != list.size()) {
733 return false;
734 }
735 Iterator<?> iterator = list.iterator();
736 for (int i = 0; i < n; i++) {
737 Object elem = iterator.next();
738 if (!(elem instanceof Character)
739 || ((Character) elem).charValue() != sequence.charAt(i)) {
740 return false;
741 }
742 }
743 return true;
744 }
745 }
746
747 /**
748 * Returns a reversed view of the specified list. For example, {@code
749 * Lists.reverse(Arrays.asList(1, 2, 3))} returns a list containing {@code 3,
750 * 2, 1}. The returned list is backed by this list, so changes in the returned
751 * list are reflected in this list, and vice-versa. The returned list supports
752 * all of the optional list operations supported by this list.
753 *
754 * <p>The returned list is random-access if the specified list is random
755 * access.
756 *
757 * @since 7.0
758 */
759 public static <T> List<T> reverse(List<T> list) {
760 if (list instanceof ReverseList) {
761 return ((ReverseList<T>) list).getForwardList();
762 } else if (list instanceof RandomAccess) {
763 return new RandomAccessReverseList<T>(list);
764 } else {
765 return new ReverseList<T>(list);
766 }
767 }
768
769 private static class ReverseList<T> extends AbstractList<T> {
770 private final List<T> forwardList;
771
772 ReverseList(List<T> forwardList) {
773 this.forwardList = checkNotNull(forwardList);
774 }
775
776 List<T> getForwardList() {
777 return forwardList;
778 }
779
780 private int reverseIndex(int index) {
781 int size = size();
782 checkElementIndex(index, size);
783 return (size - 1) - index;
784 }
785
786 private int reversePosition(int index) {
787 int size = size();
788 checkPositionIndex(index, size);
789 return size - index;
790 }
791
792 @Override public void add(int index, @Nullable T element) {
793 forwardList.add(reversePosition(index), element);
794 }
795
796 @Override public void clear() {
797 forwardList.clear();
798 }
799
800 @Override public T remove(int index) {
801 return forwardList.remove(reverseIndex(index));
802 }
803
804 @Override protected void removeRange(int fromIndex, int toIndex) {
805 subList(fromIndex, toIndex).clear();
806 }
807
808 @Override public T set(int index, @Nullable T element) {
809 return forwardList.set(reverseIndex(index), element);
810 }
811
812 @Override public T get(int index) {
813 return forwardList.get(reverseIndex(index));
814 }
815
816 @Override public boolean isEmpty() {
817 return forwardList.isEmpty();
818 }
819
820 @Override public int size() {
821 return forwardList.size();
822 }
823
824 @Override public boolean contains(@Nullable Object o) {
825 return forwardList.contains(o);
826 }
827
828 @Override public boolean containsAll(Collection<?> c) {
829 return forwardList.containsAll(c);
830 }
831
832 @Override public List<T> subList(int fromIndex, int toIndex) {
833 checkPositionIndexes(fromIndex, toIndex, size());
834 return reverse(forwardList.subList(
835 reversePosition(toIndex), reversePosition(fromIndex)));
836 }
837
838 @Override public int indexOf(@Nullable Object o) {
839 int index = forwardList.lastIndexOf(o);
840 return (index >= 0) ? reverseIndex(index) : -1;
841 }
842
843 @Override public int lastIndexOf(@Nullable Object o) {
844 int index = forwardList.indexOf(o);
845 return (index >= 0) ? reverseIndex(index) : -1;
846 }
847
848 @Override public Iterator<T> iterator() {
849 return listIterator();
850 }
851
852 @Override public ListIterator<T> listIterator(int index) {
853 int start = reversePosition(index);
854 final ListIterator<T> forwardIterator = forwardList.listIterator(start);
855 return new ListIterator<T>() {
856
857 boolean canRemove;
858 boolean canSet;
859
860 @Override public void add(T e) {
861 forwardIterator.add(e);
862 forwardIterator.previous();
863 canSet = canRemove = false;
864 }
865
866 @Override public boolean hasNext() {
867 return forwardIterator.hasPrevious();
868 }
869
870 @Override public boolean hasPrevious() {
871 return forwardIterator.hasNext();
872 }
873
874 @Override public T next() {
875 if (!hasNext()) {
876 throw new NoSuchElementException();
877 }
878 canSet = canRemove = true;
879 return forwardIterator.previous();
880 }
881
882 @Override public int nextIndex() {
883 return reversePosition(forwardIterator.nextIndex());
884 }
885
886 @Override public T previous() {
887 if (!hasPrevious()) {
888 throw new NoSuchElementException();
889 }
890 canSet = canRemove = true;
891 return forwardIterator.next();
892 }
893
894 @Override public int previousIndex() {
895 return nextIndex() - 1;
896 }
897
898 @Override public void remove() {
899 checkState(canRemove);
900 forwardIterator.remove();
901 canRemove = canSet = false;
902 }
903
904 @Override public void set(T e) {
905 checkState(canSet);
906 forwardIterator.set(e);
907 }
908 };
909 }
910 }
911
912 private static class RandomAccessReverseList<T> extends ReverseList<T>
913 implements RandomAccess {
914 RandomAccessReverseList(List<T> forwardList) {
915 super(forwardList);
916 }
917 }
918
919 /**
920 * An implementation of {@link List#hashCode()}.
921 */
922 static int hashCodeImpl(List<?> list){
923 int hashCode = 1;
924 for (Object o : list) {
925 hashCode = 31 * hashCode + (o == null ? 0 : o.hashCode());
926 }
927 return hashCode;
928 }
929
930 /**
931 * An implementation of {@link List#equals(Object)}.
932 */
933 static boolean equalsImpl(List<?> list, @Nullable Object object) {
934 if (object == checkNotNull(list)) {
935 return true;
936 }
937 if (!(object instanceof List)) {
938 return false;
939 }
940
941 List<?> o = (List<?>) object;
942
943 return list.size() == o.size()
944 && Iterators.elementsEqual(list.iterator(), o.iterator());
945 }
946
947 /**
948 * An implementation of {@link List#addAll(int, Collection)}.
949 */
950 static <E> boolean addAllImpl(
951 List<E> list, int index, Iterable<? extends E> elements) {
952 boolean changed = false;
953 ListIterator<E> listIterator = list.listIterator(index);
954 for (E e : elements) {
955 listIterator.add(e);
956 changed = true;
957 }
958 return changed;
959 }
960
961 /**
962 * An implementation of {@link List#indexOf(Object)}.
963 */
964 static int indexOfImpl(List<?> list, @Nullable Object element){
965 ListIterator<?> listIterator = list.listIterator();
966 while (listIterator.hasNext()) {
967 if (Objects.equal(element, listIterator.next())) {
968 return listIterator.previousIndex();
969 }
970 }
971 return -1;
972 }
973
974 /**
975 * An implementation of {@link List#lastIndexOf(Object)}.
976 */
977 static int lastIndexOfImpl(List<?> list, @Nullable Object element){
978 ListIterator<?> listIterator = list.listIterator(list.size());
979 while (listIterator.hasPrevious()) {
980 if (Objects.equal(element, listIterator.previous())) {
981 return listIterator.nextIndex();
982 }
983 }
984 return -1;
985 }
986
987 /**
988 * Returns an implementation of {@link List#listIterator(int)}.
989 */
990 static <E> ListIterator<E> listIteratorImpl(List<E> list, int index) {
991 return new AbstractListWrapper<E>(list).listIterator(index);
992 }
993
994 /**
995 * An implementation of {@link List#subList(int, int)}.
996 */
997 static <E> List<E> subListImpl(
998 final List<E> list, int fromIndex, int toIndex) {
999 List<E> wrapper;
1000 if (list instanceof RandomAccess) {
1001 wrapper = new RandomAccessListWrapper<E>(list) {
1002 @Override public ListIterator<E> listIterator(int index) {
1003 return backingList.listIterator(index);
1004 }
1005
1006 private static final long serialVersionUID = 0;
1007 };
1008 } else {
1009 wrapper = new AbstractListWrapper<E>(list) {
1010 @Override public ListIterator<E> listIterator(int index) {
1011 return backingList.listIterator(index);
1012 }
1013
1014 private static final long serialVersionUID = 0;
1015 };
1016 }
1017 return wrapper.subList(fromIndex, toIndex);
1018 }
1019
1020 private static class AbstractListWrapper<E> extends AbstractList<E> {
1021 final List<E> backingList;
1022
1023 AbstractListWrapper(List<E> backingList) {
1024 this.backingList = checkNotNull(backingList);
1025 }
1026
1027 @Override public void add(int index, E element) {
1028 backingList.add(index, element);
1029 }
1030
1031 @Override public boolean addAll(int index, Collection<? extends E> c) {
1032 return backingList.addAll(index, c);
1033 }
1034
1035 @Override public E get(int index) {
1036 return backingList.get(index);
1037 }
1038
1039 @Override public E remove(int index) {
1040 return backingList.remove(index);
1041 }
1042
1043 @Override public E set(int index, E element) {
1044 return backingList.set(index, element);
1045 }
1046
1047 @Override public boolean contains(Object o) {
1048 return backingList.contains(o);
1049 }
1050
1051 @Override public int size() {
1052 return backingList.size();
1053 }
1054 }
1055
1056 private static class RandomAccessListWrapper<E>
1057 extends AbstractListWrapper<E> implements RandomAccess {
1058 RandomAccessListWrapper(List<E> backingList) {
1059 super(backingList);
1060 }
1061 }
1062
1063 /**
1064 * Used to avoid http://bugs.sun.com/view_bug.do?bug_id=6558557
1065 */
1066 static <T> List<T> cast(Iterable<T> iterable) {
1067 return (List<T>) iterable;
1068 }
1069 }