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