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