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 ImmutableList#of()} 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 }