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 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 public void add(T e) {
377 throw new UnsupportedOperationException();
378 }
379
380 public boolean hasNext() {
381 return delegate.hasNext();
382 }
383
384 public boolean hasPrevious() {
385 return delegate.hasPrevious();
386 }
387
388 public T next() {
389 return function.apply(delegate.next());
390 }
391
392 public int nextIndex() {
393 return delegate.nextIndex();
394 }
395
396 public T previous() {
397 return function.apply(delegate.previous());
398 }
399
400 public int previousIndex() {
401 return delegate.previousIndex();
402 }
403
404 public void remove() {
405 delegate.remove();
406 }
407
408 public void set(T e) {
409 throw new UnsupportedOperationException("not supported");
410 }
411 };
412 }
413
414 private static final long serialVersionUID = 0;
415 }
416
417 /**
418 * Implementation of a transforming random access list. We try to make as many
419 * of these methods pass-through to the source list as possible so that the
420 * performance characteristics of the source list and transformed list are
421 * similar.
422 *
423 * @see Lists#transform
424 */
425 private static class TransformingRandomAccessList<F, T>
426 extends AbstractList<T> implements RandomAccess, Serializable {
427 final List<F> fromList;
428 final Function<? super F, ? extends T> function;
429
430 TransformingRandomAccessList(
431 List<F> fromList, Function<? super F, ? extends T> function) {
432 this.fromList = checkNotNull(fromList);
433 this.function = checkNotNull(function);
434 }
435 @Override public void clear() {
436 fromList.clear();
437 }
438 @Override public T get(int index) {
439 return function.apply(fromList.get(index));
440 }
441 @Override public boolean isEmpty() {
442 return fromList.isEmpty();
443 }
444 @Override public T remove(int index) {
445 return function.apply(fromList.remove(index));
446 }
447 @Override public int size() {
448 return fromList.size();
449 }
450 private static final long serialVersionUID = 0;
451 }
452
453 /**
454 * Returns consecutive {@linkplain List#subList(int, int) sublists} of a list,
455 * each of the same size (the final list may be smaller). For example,
456 * partitioning a list containing {@code [a, b, c, d, e]} with a partition
457 * size of 3 yields {@code [[a, b, c], [d, e]]} -- an outer list containing
458 * two inner lists of three and two elements, all in the original order.
459 *
460 * <p>The outer list is unmodifiable, but reflects the latest state of the
461 * source list. The inner lists are sublist views of the original list,
462 * produced on demand using {@link List#subList(int, int)}, and are subject
463 * to all the usual caveats about modification as explained in that API.
464 *
465 * @param list the list to return consecutive sublists of
466 * @param size the desired size of each sublist (the last may be
467 * smaller)
468 * @return a list of consecutive sublists
469 * @throws IllegalArgumentException if {@code partitionSize} is nonpositive
470 */
471 public static <T> List<List<T>> partition(List<T> list, int size) {
472 checkNotNull(list);
473 checkArgument(size > 0);
474 return (list instanceof RandomAccess)
475 ? new RandomAccessPartition<T>(list, size)
476 : new Partition<T>(list, size);
477 }
478
479 private static class Partition<T> extends AbstractList<List<T>> {
480 final List<T> list;
481 final int size;
482
483 Partition(List<T> list, int size) {
484 this.list = list;
485 this.size = size;
486 }
487
488 @Override public List<T> get(int index) {
489 int listSize = size();
490 checkElementIndex(index, listSize);
491 int start = index * size;
492 int end = Math.min(start + size, list.size());
493 return list.subList(start, end);
494 }
495
496 @Override public int size() {
497 return (list.size() + size - 1) / size;
498 }
499
500 @Override public boolean isEmpty() {
501 return list.isEmpty();
502 }
503 }
504
505 private static class RandomAccessPartition<T> extends Partition<T>
506 implements RandomAccess {
507 RandomAccessPartition(List<T> list, int size) {
508 super(list, size);
509 }
510 }
511
512 /**
513 * Returns a view of the specified string as an immutable list of {@code
514 * Character} values.
515 *
516 * @since 7
517 */
518 @Beta public static ImmutableList<Character> charactersOf(String string) {
519 return new StringAsImmutableList(checkNotNull(string));
520 }
521
522 @SuppressWarnings("serial") // serialized using ImmutableList serialization
523 private static final class StringAsImmutableList
524 extends ImmutableList<Character> {
525
526 private final String string;
527
528 StringAsImmutableList(String string) {
529 this.string = string;
530 }
531
532 @Override public boolean contains(@Nullable Object object) {
533 return indexOf(object) >= 0;
534 }
535
536 @Override public int indexOf(@Nullable Object object) {
537 return (object instanceof Character)
538 ? string.indexOf((Character) object) : -1;
539 }
540
541 @Override public int lastIndexOf(@Nullable Object object) {
542 return (object instanceof Character)
543 ? string.lastIndexOf((Character) object) : -1;
544 }
545
546 @Override public UnmodifiableListIterator<Character> listIterator(
547 int index) {
548 return new AbstractIndexedListIterator<Character>(size(), index) {
549 @Override protected Character get(int index) {
550 return string.charAt(index);
551 }
552 };
553 }
554
555 @Override public ImmutableList<Character> subList(
556 int fromIndex, int toIndex) {
557 return charactersOf(string.substring(fromIndex, toIndex));
558 }
559
560 @Override boolean isPartialView() {
561 return false;
562 }
563
564 @Override public Character get(int index) {
565 return string.charAt(index);
566 }
567
568 @Override public int size() {
569 return string.length();
570 }
571
572 @Override public boolean equals(@Nullable Object obj) {
573 if (!(obj instanceof List)) {
574 return false;
575 }
576 List<?> list = (List<?>) obj;
577 int n = string.length();
578 if (n != list.size()) {
579 return false;
580 }
581 Iterator<?> iterator = list.iterator();
582 for (int i = 0; i < n; i++) {
583 Object elem = iterator.next();
584 if (!(elem instanceof Character)
585 || ((Character) elem).charValue() != string.charAt(i)) {
586 return false;
587 }
588 }
589 return true;
590 }
591
592 int hash = 0;
593
594 @Override public int hashCode() {
595 int h = hash;
596 if (h == 0) {
597 h = 1;
598 for (int i = 0; i < string.length(); i++) {
599 h = h * 31 + string.charAt(i);
600 }
601 hash = h;
602 }
603 return h;
604 }
605 }
606
607 /**
608 * Returns a view of the specified {@code CharSequence} as a {@code
609 * List<Character>}, viewing {@code sequence} as a sequence of Unicode code
610 * units. The view does not support any modification operations, but reflects
611 * any changes to the underlying character sequence.
612 *
613 * @param sequence the character sequence to view as a {@code List} of
614 * characters
615 * @return an {@code List<Character>} view of the character sequence
616 * @since 7
617 */
618 @Beta public static List<Character> charactersOf(CharSequence sequence) {
619 return new CharSequenceAsList(checkNotNull(sequence));
620 }
621
622 private static final class CharSequenceAsList
623 extends AbstractList<Character> {
624 private final CharSequence sequence;
625
626 CharSequenceAsList(CharSequence sequence) {
627 this.sequence = sequence;
628 }
629
630 @Override public Character get(int index) {
631 return sequence.charAt(index);
632 }
633
634 @Override public boolean contains(@Nullable Object o) {
635 return indexOf(o) >= 0;
636 }
637
638 @Override public int indexOf(@Nullable Object o) {
639 if (o instanceof Character) {
640 char c = (Character) o;
641 for (int i = 0; i < sequence.length(); i++) {
642 if (sequence.charAt(i) == c) {
643 return i;
644 }
645 }
646 }
647 return -1;
648 }
649
650 @Override public int lastIndexOf(@Nullable Object o) {
651 if (o instanceof Character) {
652 char c = ((Character) o).charValue();
653 for (int i = sequence.length() - 1; i >= 0; i--) {
654 if (sequence.charAt(i) == c) {
655 return i;
656 }
657 }
658 }
659 return -1;
660 }
661
662 @Override public int size() {
663 return sequence.length();
664 }
665
666 @Override public List<Character> subList(int fromIndex, int toIndex) {
667 return charactersOf(sequence.subSequence(fromIndex, toIndex));
668 }
669
670 @Override public int hashCode() {
671 int hash = 1;
672 for (int i = 0; i < sequence.length(); i++) {
673 hash = hash * 31 + sequence.charAt(i);
674 }
675 return hash;
676 }
677
678 @Override public boolean equals(@Nullable Object o) {
679 if (!(o instanceof List)) {
680 return false;
681 }
682 List<?> list = (List<?>) o;
683 int n = sequence.length();
684 if (n != list.size()) {
685 return false;
686 }
687 Iterator<?> iterator = list.iterator();
688 for (int i = 0; i < n; i++) {
689 Object elem = iterator.next();
690 if (!(elem instanceof Character)
691 || ((Character) elem).charValue() != sequence.charAt(i)) {
692 return false;
693 }
694 }
695 return true;
696 }
697 }
698
699 /**
700 * Returns a reversed view of the specified list. For example, {@code
701 * Lists.reverse(Arrays.asList(1, 2, 3))} returns a list containing {@code 3,
702 * 2, 1}. The returned list is backed by this list, so changes in the returned
703 * list are reflected in this list, and vice-versa. The returned list supports
704 * all of the optional list operations supported by this list.
705 *
706 * <p>The returned list is random-access if the specified list is random
707 * access.
708 *
709 * @since 7
710 */
711 public static <T> List<T> reverse(List<T> list) {
712 if (list instanceof ReverseList) {
713 return ((ReverseList<T>) list).getForwardList();
714 } else if (list instanceof RandomAccess) {
715 return new RandomAccessReverseList<T>(list);
716 } else {
717 return new ReverseList<T>(list);
718 }
719 }
720
721 private static class ReverseList<T> extends AbstractList<T> {
722 private final List<T> forwardList;
723
724 ReverseList(List<T> forwardList) {
725 this.forwardList = checkNotNull(forwardList);
726 }
727
728 List<T> getForwardList() {
729 return forwardList;
730 }
731
732 private int reverseIndex(int index) {
733 int size = size();
734 checkElementIndex(index, size);
735 return (size - 1) - index;
736 }
737
738 private int reversePosition(int index) {
739 int size = size();
740 checkPositionIndex(index, size);
741 return size - index;
742 }
743
744 @Override public void add(int index, @Nullable T element) {
745 forwardList.add(reversePosition(index), element);
746 }
747
748 @Override public void clear() {
749 forwardList.clear();
750 }
751
752 @Override public T remove(int index) {
753 return forwardList.remove(reverseIndex(index));
754 }
755
756 @Override protected void removeRange(int fromIndex, int toIndex) {
757 subList(fromIndex, toIndex).clear();
758 }
759
760 @Override public T set(int index, @Nullable T element) {
761 return forwardList.set(reverseIndex(index), element);
762 }
763
764 @Override public T get(int index) {
765 return forwardList.get(reverseIndex(index));
766 }
767
768 @Override public boolean isEmpty() {
769 return forwardList.isEmpty();
770 }
771
772 @Override public int size() {
773 return forwardList.size();
774 }
775
776 @Override public boolean contains(@Nullable Object o) {
777 return forwardList.contains(o);
778 }
779
780 @Override public boolean containsAll(Collection<?> c) {
781 return forwardList.containsAll(c);
782 }
783
784 @Override public List<T> subList(int fromIndex, int toIndex) {
785 checkPositionIndexes(fromIndex, toIndex, size());
786 return reverse(forwardList.subList(
787 reversePosition(toIndex), reversePosition(fromIndex)));
788 }
789
790 @Override public int indexOf(@Nullable Object o) {
791 int index = forwardList.lastIndexOf(o);
792 return (index >= 0) ? reverseIndex(index) : -1;
793 }
794
795 @Override public int lastIndexOf(@Nullable Object o) {
796 int index = forwardList.indexOf(o);
797 return (index >= 0) ? reverseIndex(index) : -1;
798 }
799
800 @Override public Iterator<T> iterator() {
801 return listIterator();
802 }
803
804 @Override public ListIterator<T> listIterator(int index) {
805 int start = reversePosition(index);
806 final ListIterator<T> forwardIterator = forwardList.listIterator(start);
807 return new ListIterator<T>() {
808
809 boolean canRemove;
810 boolean canSet;
811
812 @Override public void add(T e) {
813 forwardIterator.add(e);
814 forwardIterator.previous();
815 canSet = canRemove = false;
816 }
817
818 @Override public boolean hasNext() {
819 return forwardIterator.hasPrevious();
820 }
821
822 @Override public boolean hasPrevious() {
823 return forwardIterator.hasNext();
824 }
825
826 @Override public T next() {
827 if (!hasNext()) {
828 throw new NoSuchElementException();
829 }
830 canSet = canRemove = true;
831 return forwardIterator.previous();
832 }
833
834 @Override public int nextIndex() {
835 return reversePosition(forwardIterator.nextIndex());
836 }
837
838 @Override public T previous() {
839 if (!hasPrevious()) {
840 throw new NoSuchElementException();
841 }
842 canSet = canRemove = true;
843 return forwardIterator.next();
844 }
845
846 @Override public int previousIndex() {
847 return nextIndex() - 1;
848 }
849
850 @Override public void remove() {
851 checkState(canRemove);
852 forwardIterator.remove();
853 canRemove = canSet = false;
854 }
855
856 @Override public void set(T e) {
857 checkState(canSet);
858 forwardIterator.set(e);
859 }
860 };
861 }
862 }
863
864 private static class RandomAccessReverseList<T> extends ReverseList<T>
865 implements RandomAccess {
866 RandomAccessReverseList(List<T> forwardList) {
867 super(forwardList);
868 }
869 }
870
871 /**
872 * An implementation of {@link List#hashCode()}.
873 */
874 static int hashCodeImpl(List<?> list){
875 int hashCode = 1;
876 for (Object o : list) {
877 hashCode = 31 * hashCode + (o == null ? 0 : o.hashCode());
878 }
879 return hashCode;
880 }
881
882 /**
883 * An implementation of {@link List#equals(Object)}.
884 */
885 static boolean equalsImpl(List<?> list, @Nullable Object object) {
886 if (object == checkNotNull(list)) {
887 return true;
888 }
889 if (!(object instanceof List)) {
890 return false;
891 }
892
893 List<?> o = (List<?>) object;
894
895 return list.size() == o.size()
896 && Iterators.elementsEqual(list.iterator(), o.iterator());
897 }
898
899 /**
900 * An implementation of {@link List#addAll(int, Collection)}.
901 */
902 static <E> boolean addAllImpl(
903 List<E> list, int index, Iterable<? extends E> elements) {
904 boolean changed = false;
905 ListIterator<E> listIterator = list.listIterator(index);
906 for (E e : elements) {
907 listIterator.add(e);
908 changed = true;
909 }
910 return changed;
911 }
912
913 /**
914 * An implementation of {@link List#indexOf(Object)}.
915 */
916 static int indexOfImpl(List<?> list, @Nullable Object element){
917 ListIterator<?> listIterator = list.listIterator();
918 while (listIterator.hasNext()) {
919 if (Objects.equal(element, listIterator.next())) {
920 return listIterator.previousIndex();
921 }
922 }
923 return -1;
924 }
925
926 /**
927 * An implementation of {@link List#lastIndexOf(Object)}.
928 */
929 static int lastIndexOfImpl(List<?> list, @Nullable Object element){
930 ListIterator<?> listIterator = list.listIterator(list.size());
931 while (listIterator.hasPrevious()) {
932 if (Objects.equal(element, listIterator.previous())) {
933 return listIterator.nextIndex();
934 }
935 }
936 return -1;
937 }
938
939 /**
940 * Returns an implementation of {@link List#listIterator(int)}.
941 */
942 static <E> ListIterator<E> listIteratorImpl(List<E> list, int index) {
943 return new AbstractListWrapper<E>(list).listIterator(index);
944 }
945
946 /**
947 * An implementation of {@link List#subList(int, int)}.
948 */
949 static <E> List<E> subListImpl(
950 final List<E> list, int fromIndex, int toIndex) {
951 List<E> wrapper;
952 if (list instanceof RandomAccess) {
953 wrapper = new RandomAccessListWrapper<E>(list) {
954 @Override public ListIterator<E> listIterator(int index) {
955 return backingList.listIterator(index);
956 }
957
958 private static final long serialVersionUID = 0;
959 };
960 } else {
961 wrapper = new AbstractListWrapper<E>(list) {
962 @Override public ListIterator<E> listIterator(int index) {
963 return backingList.listIterator(index);
964 }
965
966 private static final long serialVersionUID = 0;
967 };
968 }
969 return wrapper.subList(fromIndex, toIndex);
970 }
971
972 private static class AbstractListWrapper<E> extends AbstractList<E> {
973 final List<E> backingList;
974
975 AbstractListWrapper(List<E> backingList) {
976 this.backingList = checkNotNull(backingList);
977 }
978
979 @Override public void add(int index, E element) {
980 backingList.add(index, element);
981 }
982
983 @Override public boolean addAll(int index, Collection<? extends E> c) {
984 return backingList.addAll(index, c);
985 }
986
987 @Override public E get(int index) {
988 return backingList.get(index);
989 }
990
991 @Override public E remove(int index) {
992 return backingList.remove(index);
993 }
994
995 @Override public E set(int index, E element) {
996 return backingList.set(index, element);
997 }
998
999 @Override public boolean contains(Object o) {
1000 return backingList.contains(o);
1001 }
1002
1003 @Override public int size() {
1004 return backingList.size();
1005 }
1006 }
1007
1008 private static class RandomAccessListWrapper<E>
1009 extends AbstractListWrapper<E> implements RandomAccess {
1010 RandomAccessListWrapper(List<E> backingList) {
1011 super(backingList);
1012 }
1013 }
1014 }