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