Find Usages Diff Raw Download HTML Widget
Start line:  
End line:  

Snippet Preview

Snippet HTML Code

Stack Overflow Questions 
1
   /*
2
    * Copyright (C) 2007 The Guava Authors
3
    *
4
    * Licensed under the Apache License, Version 2.0 (the "License");
5
    * you may not use this file except in compliance with the License.
6
    * You may obtain a copy of the License at
7
    *
8
    * http://www.apache.org/licenses/LICENSE-2.0
9
    *
10
   * Unless required by applicable law or agreed to in writing, software
11
   * distributed under the License is distributed on an "AS IS" BASIS,
12
   * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13
   * See the License for the specific language governing permissions and
14
   * limitations under the License.
15
   */
16
  
17
  package com.google.common.collect;
18
  
19
  import static com.google.common.base.Preconditions.checkArgument;
20
  import static com.google.common.base.Preconditions.checkElementIndex;
21
  import static com.google.common.base.Preconditions.checkNotNull;
22
  import static com.google.common.base.Preconditions.checkPositionIndex;
23
  import static com.google.common.base.Preconditions.checkPositionIndexes;
24
  import static com.google.common.base.Preconditions.checkState;
25
  import static com.google.common.collect.CollectPreconditions.checkNonnegative;
26
  import static com.google.common.collect.CollectPreconditions.checkRemove;
27
  
35
  
41
  import java.util.Arrays;
46
  import java.util.List;
50
  
Static utility methods pertaining to java.util.List instances. Also see this class's counterparts Sets, Maps and com.google.common.collect.Queues.

See the Guava User Guide article on Lists.

Author(s):
Kevin Bourrillion
Mike Bostock
Louis Wasserman
Since:
2.0 (imported from Google Collections Library)
65
  
66
  @GwtCompatible(emulated = true)
67
  public final class Lists {
68
    private Lists() {}
69
  
70
    // ArrayList
71
  
  
Creates a mutable, empty ArrayList instance.

Note: if mutability is not required, use ImmutableList.of() instead.

Returns:
a new, empty ArrayList
79
  
80
    @GwtCompatible(serializable = true)
81
    public static <E> ArrayList<E> newArrayList() {
82
      return new ArrayList<E>();
83
    }

  
Creates a mutable ArrayList instance containing the given elements.

Note: if mutability is not required and the elements are non-null, use an overload of ImmutableList.of() (for varargs) or ImmutableList.copyOf(java.lang.Object[]) (for an array) instead.

Parameters:
elements the elements that the list should contain, in order
Returns:
a new ArrayList containing those elements
95
  
96
    @GwtCompatible(serializable = true)
97
    public static <E> ArrayList<E> newArrayList(E... elements) {
98
      checkNotNull(elements); // for GWT
99
      // Avoid integer overflow when a large array is passed in
100
     int capacity = computeArrayListCapacity(elements.length);
101
     ArrayList<E> list = new ArrayList<E>(capacity);
102
     Collections.addAll(list, elements);
103
     return list;
104
   }
105
 
106
   @VisibleForTesting static int computeArrayListCapacity(int arraySize) {
107
     checkNonnegative(arraySize, "arraySize");
108
 
109
     // TODO(kevinb): Figure out the right behavior, and document it
110
     return Ints.saturatedCast(5L + arraySize + (arraySize / 10));
111
   }

  
Creates a mutable ArrayList instance containing the given elements.

Note: if mutability is not required and the elements are non-null, use ImmutableList.copyOf(java.util.Iterator) instead.

Parameters:
elements the elements that the list should contain, in order
Returns:
a new ArrayList containing those elements
122
 
123
   @GwtCompatible(serializable = true)
124
   public static <E> ArrayList<E> newArrayList(Iterable<? extends E> elements) {
125
     checkNotNull(elements); // for GWT
126
     // Let ArrayList's sizing logic work, if possible
127
     return (elements instanceof Collection)
128
         ? new ArrayList<E>(Collections2.cast(elements))
129
         : newArrayList(elements.iterator());
130
   }

  
Creates a mutable ArrayList instance containing the given elements.

Note: if mutability is not required and the elements are non-null, use ImmutableList.copyOf(java.util.Iterator) instead.

Parameters:
elements the elements that the list should contain, in order
Returns:
a new ArrayList containing those elements
141
 
142
   @GwtCompatible(serializable = true)
143
   public static <E> ArrayList<E> newArrayList(Iterator<? extends E> elements) {
144
     ArrayList<E> list = newArrayList();
145
     Iterators.addAll(list, elements);
146
     return list;
147
   }

  
Creates an ArrayList instance backed by an array of the exact size specified; equivalent to java.util.ArrayList.(int).

Note: if you know the exact size your list will be, consider using a fixed-size list (java.util.Arrays.asList(java.lang.Object[])) or an ImmutableList instead of a growable java.util.ArrayList.

Note: If you have only an estimate of the eventual size of the list, consider padding this estimate by a suitable amount, or simply use newArrayListWithExpectedSize(int) instead.

Parameters:
initialArraySize the exact size of the initial backing array for the returned array list (ArrayList documentation calls this value the "capacity")
Returns:
a new, empty ArrayList which is guaranteed not to resize itself unless its size reaches initialArraySize + 1
Throws:
java.lang.IllegalArgumentException if initialArraySize is negative
168
 
169
   @GwtCompatible(serializable = true)
170
   public static <E> ArrayList<E> newArrayListWithCapacity(
171
       int initialArraySize) {
172
     checkNonnegative(initialArraySize, "initialArraySize"); // for GWT.
173
     return new ArrayList<E>(initialArraySize);
174
   }

  
Creates an ArrayList instance sized appropriately to hold an estimated number of elements without resizing. A small amount of padding is added in case the estimate is low.

Note: If you know the exact number of elements the list will hold, or prefer to calculate your own amount of padding, refer to newArrayListWithCapacity(int).

Parameters:
estimatedSize an estimate of the eventual java.util.List.size() of the new list
Returns:
a new, empty ArrayList, sized appropriately to hold the estimated number of elements
Throws:
java.lang.IllegalArgumentException if estimatedSize is negative
190
 
191
   @GwtCompatible(serializable = true)
192
   public static <E> ArrayList<E> newArrayListWithExpectedSize(
193
       int estimatedSize) {
194
     return new ArrayList<E>(computeArrayListCapacity(estimatedSize));
195
   }
196
 
197
   // LinkedList
198
 
  
Creates an empty LinkedList instance.

Note: if you need an immutable empty java.util.List, use ImmutableList.of() instead.

Returns:
a new, empty LinkedList
206
 
207
   @GwtCompatible(serializable = true)
208
   public static <E> LinkedList<E> newLinkedList() {
209
     return new LinkedList<E>();
210
   }

  
Creates a LinkedList instance containing the given elements.

Parameters:
elements the elements that the list should contain, in order
Returns:
a new LinkedList containing those elements
217
 
218
   @GwtCompatible(serializable = true)
219
   public static <E> LinkedList<E> newLinkedList(
220
       Iterable<? extends E> elements) {
221
     LinkedList<E> list = newLinkedList();
222
     Iterables.addAll(list, elements);
223
     return list;
224
   }

  
Returns an unmodifiable list containing the specified first element and backed by the specified array of additional elements. Changes to the rest array will be reflected in the returned list. Unlike java.util.Arrays.asList(java.lang.Object[]), the returned list is unmodifiable.

This is useful when a varargs method needs to use a signature such as (Foo firstFoo, Foo... moreFoos), in order to avoid overload ambiguity or to enforce a minimum argument count.

The returned list is serializable and implements java.util.RandomAccess.

Parameters:
first the first element
rest an array of additional elements, possibly empty
Returns:
an unmodifiable list containing the specified elements
241
 
242
   public static <E> List<E> asList(@Nullable E first, E[] rest) {
243
     return new OnePlusArrayList<E>(first, rest);
244
   }

  

See also:
Lists.asList(java.lang.Object,java.lang.Object[])
246
 
247
   private static class OnePlusArrayList<E> extends AbstractList<E>
248
       implements Serializable, RandomAccess {
249
     final E first;
250
     final E[] rest;
251
 
252
     OnePlusArrayList(@Nullable E first, E[] rest) {
253
       this. = first;
254
       this. = checkNotNull(rest);
255
     }
256
     @Override public int size() {
257
       return . + 1;
258
     }
259
     @Override public E get(int index) {
260
       // check explicitly so the IOOBE will have the right message
261
       checkElementIndex(index, size());
262
       return (index == 0) ?  : [index - 1];
263
     }
264
     private static final long serialVersionUID = 0;
265
   }

  
Returns an unmodifiable list containing the specified first and second element, and backed by the specified array of additional elements. Changes to the rest array will be reflected in the returned list. Unlike java.util.Arrays.asList(java.lang.Object[]), the returned list is unmodifiable.

This is useful when a varargs method needs to use a signature such as (Foo firstFoo, Foo secondFoo, Foo... moreFoos), in order to avoid overload ambiguity or to enforce a minimum argument count.

The returned list is serializable and implements java.util.RandomAccess.

Parameters:
first the first element
second the second element
rest an array of additional elements, possibly empty
Returns:
an unmodifiable list containing the specified elements
283
 
284
   public static <E> List<E> asList(
285
       @Nullable E first, @Nullable E second, E[] rest) {
286
     return new TwoPlusArrayList<E>(first, second, rest);
287
   }

  

See also:
Lists.asList(java.lang.Object,java.lang.Object,java.lang.Object[])
289
 
290
   private static class TwoPlusArrayList<E> extends AbstractList<E>
291
       implements Serializable, RandomAccess {
292
     final E first;
293
     final E second;
294
     final E[] rest;
295
 
296
     TwoPlusArrayList(@Nullable E first, @Nullable E second, E[] rest) {
297
       this. = first;
298
       this. = second;
299
       this. = checkNotNull(rest);
300
     }
301
     @Override public int size() {
302
       return . + 2;
303
     }
304
     @Override public E get(int index) {
305
       switch (index) {
306
         case 0:
307
           return ;
308
         case 1:
309
           return ;
310
         default:
311
           // check explicitly so the IOOBE will have the right message
312
           checkElementIndex(index, size());
313
           return [index - 2];
314
       }
315
     }
316
     private static final long serialVersionUID = 0;
317
   }

  
Returns every possible list that can be formed by choosing one element from each of the given lists in order; the "n-ary Cartesian product" of the lists. For example: 
   Lists.cartesianProduct(ImmutableList.of(
       ImmutableList.of(1, 2),
       ImmutableList.of("A", "B", "C")))

returns a list containing six lists in the following order:

  • ImmutableList.of(1, "A")
  • ImmutableList.of(1, "B")
  • ImmutableList.of(1, "C")
  • ImmutableList.of(2, "A")
  • ImmutableList.of(2, "B")
  • ImmutableList.of(2, "C")

The result is guaranteed to be in the "traditional", lexicographical order for Cartesian products that you would get from nesting for loops: 

   for (B b0 : lists.get(0)) {
     for (B b1 : lists.get(1)) {
       ...
       ImmutableList<B> tuple = ImmutableList.of(b0, b1, ...);
       // operate on tuple
     
   }}

Note that if any input list is empty, the Cartesian product will also be empty. If no lists at all are provided (an empty list), the resulting Cartesian product has one element, an empty list (counter-intuitive, but mathematically consistent).

Performance notes: while the cartesian product of lists of size m, n, p is a list of size m x n x p, its actual memory consumption is much smaller. When the cartesian product is constructed, the input lists are merely copied. Only as the resulting list is iterated are the individual lists created, and these are not retained after iteration.

Parameters:
lists the lists to choose elements from, in the order that the elements chosen from those lists should appear in the resulting lists
<B> any common base class shared by all axes (often just java.lang.Object)
Returns:
the Cartesian product, as an immutable list containing immutable lists
Throws:
java.lang.IllegalArgumentException if the size of the cartesian product would be greater than java.lang.Integer.MAX_VALUE
java.lang.NullPointerException if lists, any one of the lists, or any element of a provided list is null
374
  static <B> List<List<B>>
375
       cartesianProduct(List<? extends List<? extends B>> lists) {
376
     return CartesianList.create(lists);
377
   }

  
Returns every possible list that can be formed by choosing one element from each of the given lists in order; the "n-ary Cartesian product" of the lists. For example: 
   Lists.cartesianProduct(ImmutableList.of(
       ImmutableList.of(1, 2),
       ImmutableList.of("A", "B", "C")))

returns a list containing six lists in the following order:

  • ImmutableList.of(1, "A")
  • ImmutableList.of(1, "B")
  • ImmutableList.of(1, "C")
  • ImmutableList.of(2, "A")
  • ImmutableList.of(2, "B")
  • ImmutableList.of(2, "C")

The result is guaranteed to be in the "traditional", lexicographical order for Cartesian products that you would get from nesting for loops: 

   for (B b0 : lists.get(0)) {
     for (B b1 : lists.get(1)) {
       ...
       ImmutableList<B> tuple = ImmutableList.of(b0, b1, ...);
       // operate on tuple
     
   }}

Note that if any input list is empty, the Cartesian product will also be empty. If no lists at all are provided (an empty list), the resulting Cartesian product has one element, an empty list (counter-intuitive, but mathematically consistent).

Performance notes: while the cartesian product of lists of size m, n, p is a list of size m x n x p, its actual memory consumption is much smaller. When the cartesian product is constructed, the input lists are merely copied. Only as the resulting list is iterated are the individual lists created, and these are not retained after iteration.

Parameters:
lists the lists to choose elements from, in the order that the elements chosen from those lists should appear in the resulting lists
<B> any common base class shared by all axes (often just java.lang.Object)
Returns:
the Cartesian product, as an immutable list containing immutable lists
Throws:
java.lang.IllegalArgumentException if the size of the cartesian product would be greater than java.lang.Integer.MAX_VALUE
java.lang.NullPointerException if lists, any one of the lists, or any element of a provided list is null
434
  static <B> List<List<B>>
435
       cartesianProduct(List<? extends B>... lists) {
436
     return cartesianProduct(Arrays.asList(lists));
437
   }

  
Returns a list that applies function to each element of fromList. The returned list is a transformed view of fromList; changes to fromList will be reflected in the returned list and vice versa.

Since functions are not reversible, the transform is one-way and new items cannot be stored in the returned list. The add, addAll and set methods are unsupported in the returned list.

The function is applied lazily, invoked when needed. This is necessary for the returned list to be a view, but it means that the function will be applied many times for bulk operations like java.util.List.contains(java.lang.Object) and java.util.List.hashCode(). For this to perform well, function should be fast. To avoid lazy evaluation when the returned list doesn't need to be a view, copy the returned list into a new list of your choosing.

If fromList implements java.util.RandomAccess, so will the returned list. The returned list is threadsafe if the supplied list and function are.

If only a Collection or Iterable input is available, use com.google.common.collect.Collections2.transform(java.util.Collection,com.google.common.base.Function) or Iterables.transform(java.lang.Iterable,com.google.common.base.Function).

Note: serializing the returned list is implemented by serializing fromList, its contents, and function -- not by serializing the transformed values. This can lead to surprising behavior, so serializing the returned list is not recommended. Instead, copy the list using ImmutableList.copyOf(java.util.Collection) (for example), then serialize the copy. Other methods similar to this do not implement serialization at all for this reason. 

471
 
472
   public static <F, T> List<T> transform(
473
       List<F> fromList, Function<? super F, ? extends T> function) {
474
     return (fromList instanceof RandomAccess)
475
         ? new TransformingRandomAccessList<F, T>(fromList, function)
476
         : new TransformingSequentialList<F, T>(fromList, function);
477
   }

  
Implementation of a sequential transforming list.

See also:
Lists.transform(java.util.List,com.google.common.base.Function)
483
 
484
   private static class TransformingSequentialList<F, T>
485
       extends AbstractSequentialList<T> implements Serializable {
486
     final List<F> fromList;
487
     final Function<? super F, ? extends T> function;
488
 
490
         List<F> fromList, Function<? super F, ? extends T> function) {
491
       this. = checkNotNull(fromList);
492
       this. = checkNotNull(function);
493
     }
    
The default implementation inherited is based on iteration and removal of each element which can be overkill. That's why we forward this call directly to the backing list. 
498
 
499
     @Override public void clear() {
500
       .clear();
501
     }
502
     @Override public int size() {
503
       return .size();
504
     }
505
     @Override public ListIterator<T> listIterator(final int index) {
506
       return new TransformedListIterator<F, T>(.listIterator(index)) {
507
         @Override
508
         T transform(F from) {
509
           return .apply(from);
510
         }
511
       };
512
     }
513
 
514
     private static final long serialVersionUID = 0;
515
   }

  
Implementation of a transforming random access list. We try to make as many of these methods pass-through to the source list as possible so that the performance characteristics of the source list and transformed list are similar.

See also:
Lists.transform(java.util.List,com.google.common.base.Function)
524
 
525
   private static class TransformingRandomAccessList<F, T>
526
       extends AbstractList<T> implements RandomAccess, Serializable {
527
     final List<F> fromList;
528
     final Function<? super F, ? extends T> function;
529
 
531
         List<F> fromList, Function<? super F, ? extends T> function) {
532
       this. = checkNotNull(fromList);
533
       this. = checkNotNull(function);
534
     }
535
     @Override public void clear() {
536
       .clear();
537
     }
538
     @Override public T get(int index) {
539
       return .apply(.get(index));
540
     }
541
     @Override public Iterator<T> iterator() {
542
       return listIterator();
543
     }
544
     @Override public ListIterator<T> listIterator(int index) {
545
       return new TransformedListIterator<F, T>(.listIterator(index)) {
546
         @Override
547
         T transform(F from) {
548
           return .apply(from);
549
         }
550
       };
551
     }
552
     @Override public boolean isEmpty() {
553
       return .isEmpty();
554
     }
555
     @Override public T remove(int index) {
556
       return .apply(.remove(index));
557
     }
558
     @Override public int size() {
559
       return .size();
560
     }
561
     private static final long serialVersionUID = 0;
562
   }

  
Returns consecutive sublists of a list, each of the same size (the final list may be smaller). For example, partitioning a list containing [a, b, c, d, e] with a partition size of 3 yields [[a, b, c], [d, e]] -- an outer list containing two inner lists of three and two elements, all in the original order.

The outer list is unmodifiable, but reflects the latest state of the source list. The inner lists are sublist views of the original list, produced on demand using java.util.List.subList(int,int), and are subject to all the usual caveats about modification as explained in that API.

Parameters:
list the list to return consecutive sublists of
size the desired size of each sublist (the last may be smaller)
Returns:
a list of consecutive sublists
Throws:
java.lang.IllegalArgumentException if partitionSize is nonpositive
581
 
582
   public static <T> List<List<T>> partition(List<T> list, int size) {
583
     checkNotNull(list);
584
     checkArgument(size > 0);
585
     return (list instanceof RandomAccess)
586
         ? new RandomAccessPartition<T>(list, size)
587
         : new Partition<T>(list, size);
588
   }
589
 
590
   private static class Partition<T> extends AbstractList<List<T>> {
591
     final List<T> list;
592
     final int size;
593
 
594
     Partition(List<T> list, int size) {
595
       this. = list;
596
       this. = size;
597
     }
598
 
599
     @Override public List<T> get(int index) {
600
       checkElementIndex(index, size());
601
       int start = index * ;
602
       int end = Math.min(start + , .size());
603
       return .subList(start, end);
604
     }
605
 
606
     @Override public int size() {
607
       return IntMath.divide(.size(), , .);
608
     }
609
 
610
     @Override public boolean isEmpty() {
611
       return .isEmpty();
612
     }
613
   }
614
 
615
   private static class RandomAccessPartition<T> extends Partition<T>
616
       implements RandomAccess {
617
     RandomAccessPartition(List<T> list, int size) {
618
       super(list, size);
619
     }
620
   }

  
Returns a view of the specified string as an immutable list of Character values.

Since:
7.0
627
 
628
   @Beta public static ImmutableList<Character> charactersOf(String string) {
629
     return new StringAsImmutableList(checkNotNull(string));
630
   }
631
 
632
   @SuppressWarnings("serial") // serialized using ImmutableList serialization
633
   private static final class StringAsImmutableList
634
       extends ImmutableList<Character> {
635
 
636
     private final String string;
637
 
638
     StringAsImmutableList(String string) {
639
       this. = string;
640
     }
641
 
642
     @Override public int indexOf(@Nullable Object object) {
643
       return (object instanceof Character)
644
           ? .indexOf((Character) object) : -1;
645
     }
646
 
647
     @Override public int lastIndexOf(@Nullable Object object) {
648
       return (object instanceof Character)
649
           ? .lastIndexOf((Character) object) : -1;
650
     }
651
 
653
         int fromIndex, int toIndex) {
654
       checkPositionIndexes(fromIndex, toIndex, size()); // for GWT
655
       return charactersOf(.substring(fromIndex, toIndex));
656
     }
657
 
658
     @Override boolean isPartialView() {
659
       return false;
660
     }
661
 
662
     @Override public Character get(int index) {
663
       checkElementIndex(index, size()); // for GWT
664
       return .charAt(index);
665
     }
666
 
667
     @Override public int size() {
668
       return .length();
669
     }
670
   }

  
Returns a view of the specified CharSequence as a List<Character>, viewing sequence as a sequence of Unicode code units. The view does not support any modification operations, but reflects any changes to the underlying character sequence.

Parameters:
sequence the character sequence to view as a List of characters
Returns:
an List<Character> view of the character sequence
Since:
7.0
682
 
683
   @Beta public static List<Character> charactersOf(CharSequence sequence) {
684
     return new CharSequenceAsList(checkNotNull(sequence));
685
   }
686
 
687
   private static final class CharSequenceAsList
688
       extends AbstractList<Character> {
689
     private final CharSequence sequence;
690
 
691
     CharSequenceAsList(CharSequence sequence) {
692
       this. = sequence;
693
     }
694
 
695
     @Override public Character get(int index) {
696
       checkElementIndex(index, size()); // for GWT
697
       return .charAt(index);
698
     }
699
 
700
     @Override public int size() {
701
       return .length();
702
     }
703
   }

  
Returns a reversed view of the specified list. For example, Lists.reverse(Arrays.asList(1, 2, 3)) returns a list containing 3, 2, 1. The returned list is backed by this list, so changes in the returned list are reflected in this list, and vice-versa. The returned list supports all of the optional list operations supported by this list.

The returned list is random-access if the specified list is random access.

Since:
7.0
716
 
717
   public static <T> List<T> reverse(List<T> list) {
718
     if (list instanceof ImmutableList) {
719
       return ((ImmutableList<T>) list).reverse();
720
     } else if (list instanceof ReverseList) {
721
       return ((ReverseList<T>) list).getForwardList();
722
     } else if (list instanceof RandomAccess) {
723
       return new RandomAccessReverseList<T>(list);
724
     } else {
725
       return new ReverseList<T>(list);
726
     }
727
   }
728
 
729
   private static class ReverseList<T> extends AbstractList<T> {
730
     private final List<T> forwardList;
731
 
732
     ReverseList(List<T> forwardList) {
733
       this. = checkNotNull(forwardList);
734
     }
735
 
736
     List<T> getForwardList() {
737
       return ;
738
     }
739
 
740
     private int reverseIndex(int index) {
741
       int size = size();
742
       checkElementIndex(index, size);
743
       return (size - 1) - index;
744
     }
745
 
746
     private int reversePosition(int index) {
747
       int size = size();
748
       checkPositionIndex(index, size);
749
       return size - index;
750
     }
751
 
752
     @Override public void add(int index, @Nullable T element) {
753
       .add(reversePosition(index), element);
754
     }
755
 
756
     @Override public void clear() {
757
       .clear();
758
     }
759
 
760
     @Override public T remove(int index) {
761
       return .remove(reverseIndex(index));
762
     }
763
 
764
     @Override protected void removeRange(int fromIndex, int toIndex) {
765
       subList(fromIndex, toIndex).clear();
766
     }
767
 
768
     @Override public T set(int index, @Nullable T element) {
769
       return .set(reverseIndex(index), element);
770
     }
771
 
772
     @Override public T get(int index) {
773
       return .get(reverseIndex(index));
774
     }
775
 
776
     @Override public int size() {
777
       return .size();
778
     }
779
 
780
     @Override public List<T> subList(int fromIndex, int toIndex) {
781
       checkPositionIndexes(fromIndex, toIndex, size());
782
       return reverse(.subList(
783
           reversePosition(toIndex), reversePosition(fromIndex)));
784
     }
785
 
786
     @Override public Iterator<T> iterator() {
787
       return listIterator();
788
     }
789
 
790
     @Override public ListIterator<T> listIterator(int index) {
791
       int start = reversePosition(index);
792
       final ListIterator<T> forwardIterator = .listIterator(start);
793
       return new ListIterator<T>() {
794
 
795
         boolean canRemoveOrSet;
796
 
797
         @Override public void add(T e) {
798
           forwardIterator.add(e);
799
           forwardIterator.previous();
800
            = false;
801
         }
802
 
803
         @Override public boolean hasNext() {
804
           return forwardIterator.hasPrevious();
805
         }
806
 
807
         @Override public boolean hasPrevious() {
808
           return forwardIterator.hasNext();
809
         }
810
 
811
         @Override public T next() {
812
           if (!hasNext()) {
813
             throw new NoSuchElementException();
814
           }
815
            = true;
816
           return forwardIterator.previous();
817
         }
818
 
819
         @Override public int nextIndex() {
820
           return reversePosition(forwardIterator.nextIndex());
821
         }
822
 
823
         @Override public T previous() {
824
           if (!hasPrevious()) {
825
             throw new NoSuchElementException();
826
           }
827
            = true;
828
           return forwardIterator.next();
829
         }
830
 
831
         @Override public int previousIndex() {
832
           return nextIndex() - 1;
833
         }
834
 
835
         @Override public void remove() {
836
           checkRemove();
837
           forwardIterator.remove();
838
            = false;
839
         }
840
 
841
         @Override public void set(T e) {
842
           checkState();
843
           forwardIterator.set(e);
844
         }
845
       };
846
     }
847
   }
848
 
849
   private static class RandomAccessReverseList<T> extends ReverseList<T>
850
       implements RandomAccess {
851
     RandomAccessReverseList(List<T> forwardList) {
852
       super(forwardList);
853
     }
854
   }

  
An implementation of java.util.List.hashCode(). 
858
 
859
   static int hashCodeImpl(List<?> list) {
860
     // TODO(user): worth optimizing for RandomAccess?
861
     int hashCode = 1;
862
     for (Object o : list) {
863
       hashCode = 31 * hashCode + (o == null ? 0 : o.hashCode());
864
 
865
       hashCode = ~~hashCode;
866
       // needed to deal with GWT integer overflow
867
     }
868
     return hashCode;
869
   }

  
An implementation of java.util.List.equals(java.lang.Object). 
873
 
874
   static boolean equalsImpl(List<?> list, @Nullable Object object) {
875
     if (object == checkNotNull(list)) {
876
       return true;
877
     }
878
     if (!(object instanceof List)) {
879
       return false;
880
     }
881
 
882
     List<?> o = (List<?>) object;
883
 
884
     return list.size() == o.size()
885
         && Iterators.elementsEqual(list.iterator(), o.iterator());
886
   }

  
An implementation of java.util.List.addAll(int,java.util.Collection). 
890
 
891
   static <E> boolean addAllImpl(
892
       List<E> list, int index, Iterable<? extends E> elements) {
893
     boolean changed = false;
894
     ListIterator<E> listIterator = list.listIterator(index);
895
     for (E e : elements) {
896
       listIterator.add(e);
897
       changed = true;
898
     }
899
     return changed;
900
   }

  
An implementation of java.util.List.indexOf(java.lang.Object). 
904
 
905
   static int indexOfImpl(List<?> list, @Nullable Object element) {
906
     ListIterator<?> listIterator = list.listIterator();
907
     while (listIterator.hasNext()) {
908
       if (Objects.equal(element, listIterator.next())) {
909
         return listIterator.previousIndex();
910
       }
911
     }
912
     return -1;
913
   }

  
An implementation of java.util.List.lastIndexOf(java.lang.Object). 
917
 
918
   static int lastIndexOfImpl(List<?> list, @Nullable Object element) {
919
     ListIterator<?> listIterator = list.listIterator(list.size());
920
     while (listIterator.hasPrevious()) {
921
       if (Objects.equal(element, listIterator.previous())) {
922
         return listIterator.nextIndex();
923
       }
924
     }
925
     return -1;
926
   }

  
Returns an implementation of java.util.List.listIterator(int). 
930
 
931
   static <E> ListIterator<E> listIteratorImpl(List<E> list, int index) {
932
     return new AbstractListWrapper<E>(list).listIterator(index);
933
   }

  
An implementation of java.util.List.subList(int,int). 
937
 
938
   static <E> List<E> subListImpl(
939
       final List<E> list, int fromIndex, int toIndex) {
940
     List<E> wrapper;
941
     if (list instanceof RandomAccess) {
942
       wrapper = new RandomAccessListWrapper<E>(list) {
943
         @Override public ListIterator<E> listIterator(int index) {
944
           return .listIterator(index);
945
         }
946
 
947
         private static final long serialVersionUID = 0;
948
       };
949
     } else {
950
       wrapper = new AbstractListWrapper<E>(list) {
951
         @Override public ListIterator<E> listIterator(int index) {
952
           return .listIterator(index);
953
         }
954
 
955
         private static final long serialVersionUID = 0;
956
       };
957
     }
958
     return wrapper.subList(fromIndex, toIndex);
959
   }
960
 
961
   private static class AbstractListWrapper<E> extends AbstractList<E> {
962
     final List<E> backingList;
963
 
964
     AbstractListWrapper(List<E> backingList) {
965
       this. = checkNotNull(backingList);
966
     }
967
 
968
     @Override public void add(int index, E element) {
969
       .add(index, element);
970
     }
971
 
972
     @Override public boolean addAll(int index, Collection<? extends E> c) {
973
       return .addAll(index, c);
974
     }
975
 
976
     @Override public E get(int index) {
977
       return .get(index);
978
     }
979
 
980
     @Override public E remove(int index) {
981
       return .remove(index);
982
     }
983
 
984
     @Override public E set(int index, E element) {
985
       return .set(index, element);
986
     }
987
 
988
     @Override public boolean contains(Object o) {
989
       return .contains(o);
990
     }
991
 
992
     @Override public int size() {
993
       return .size();
994
     }
995
   }
996
 
997
   private static class RandomAccessListWrapper<E>
998
       extends AbstractListWrapper<E> implements RandomAccess {
999
     RandomAccessListWrapper(List<E> backingList) {
1000
      super(backingList);
1001
    }
1002
  }

  
Used to avoid http://bugs.sun.com/view_bug.do?bug_id=6558557 
1007
  static <T> List<T> cast(Iterable<T> iterable) {
1008
    return (List<T>) iterable;
1009
  }