View Javadoc
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.checkNotNull;
21  import static com.google.common.base.Preconditions.checkState;
22  import static com.google.common.base.Predicates.instanceOf;
23  import static com.google.common.collect.CollectPreconditions.checkRemove;
24  
25  import com.google.common.annotations.Beta;
26  import com.google.common.annotations.GwtCompatible;
27  import com.google.common.annotations.GwtIncompatible;
28  import com.google.common.base.Function;
29  import com.google.common.base.Objects;
30  import com.google.common.base.Optional;
31  import com.google.common.base.Preconditions;
32  import com.google.common.base.Predicate;
33  import com.google.common.primitives.Ints;
34  import com.google.errorprone.annotations.CanIgnoreReturnValue;
35  import java.util.ArrayDeque;
36  import java.util.Arrays;
37  import java.util.Collection;
38  import java.util.Collections;
39  import java.util.Comparator;
40  import java.util.Deque;
41  import java.util.Enumeration;
42  import java.util.Iterator;
43  import java.util.List;
44  import java.util.ListIterator;
45  import java.util.NoSuchElementException;
46  import java.util.PriorityQueue;
47  import java.util.Queue;
48  import javax.annotation.Nullable;
49  
50  /**
51   * This class contains static utility methods that operate on or return objects
52   * of type {@link Iterator}. Except as noted, each method has a corresponding
53   * {@link Iterable}-based method in the {@link Iterables} class.
54   *
55   * <p><i>Performance notes:</i> Unless otherwise noted, all of the iterators
56   * produced in this class are <i>lazy</i>, which means that they only advance
57   * the backing iteration when absolutely necessary.
58   *
59   * <p>See the Guava User Guide section on <a href=
60   * "https://github.com/google/guava/wiki/CollectionUtilitiesExplained#iterables">
61   * {@code Iterators}</a>.
62   *
63   * @author Kevin Bourrillion
64   * @author Jared Levy
65   * @since 2.0
66   */
67  @GwtCompatible(emulated = true)
68  public final class Iterators {
69    private Iterators() {}
70  
71    /**
72     * Returns the empty iterator.
73     *
74     * <p>The {@link Iterable} equivalent of this method is {@link
75     * ImmutableSet#of()}.
76     */
77    static <T> UnmodifiableIterator<T> emptyIterator() {
78      return emptyListIterator();
79    }
80  
81    /**
82     * Returns the empty iterator.
83     *
84     * <p>The {@link Iterable} equivalent of this method is {@link
85     * ImmutableSet#of()}.
86     */
87    // Casting to any type is safe since there are no actual elements.
88    @SuppressWarnings("unchecked")
89    static <T> UnmodifiableListIterator<T> emptyListIterator() {
90      return (UnmodifiableListIterator<T>) ArrayItr.EMPTY;
91    }
92  
93    /**
94     * This is an enum singleton rather than an anonymous class so ProGuard can figure out it's only
95     * referenced by emptyModifiableIterator().
96     */
97    private enum EmptyModifiableIterator implements Iterator<Object> {
98      INSTANCE;
99  
100     @Override
101     public boolean hasNext() {
102       return false;
103     }
104 
105     @Override
106     public Object next() {
107       throw new NoSuchElementException();
108     }
109 
110     @Override
111     public void remove() {
112       checkRemove(false);
113     }
114   }
115 
116   /**
117    * Returns the empty {@code Iterator} that throws
118    * {@link IllegalStateException} instead of
119    * {@link UnsupportedOperationException} on a call to
120    * {@link Iterator#remove()}.
121    */
122   // Casting to any type is safe since there are no actual elements.
123   @SuppressWarnings("unchecked")
124   static <T> Iterator<T> emptyModifiableIterator() {
125     return (Iterator<T>) EmptyModifiableIterator.INSTANCE;
126   }
127 
128   /** Returns an unmodifiable view of {@code iterator}. */
129   public static <T> UnmodifiableIterator<T> unmodifiableIterator(
130       final Iterator<? extends T> iterator) {
131     checkNotNull(iterator);
132     if (iterator instanceof UnmodifiableIterator) {
133       @SuppressWarnings("unchecked") // Since it's unmodifiable, the covariant cast is safe
134       UnmodifiableIterator<T> result = (UnmodifiableIterator<T>) iterator;
135       return result;
136     }
137     return new UnmodifiableIterator<T>() {
138       @Override
139       public boolean hasNext() {
140         return iterator.hasNext();
141       }
142 
143       @Override
144       public T next() {
145         return iterator.next();
146       }
147     };
148   }
149 
150   /**
151    * Simply returns its argument.
152    *
153    * @deprecated no need to use this
154    * @since 10.0
155    */
156   @Deprecated
157   public static <T> UnmodifiableIterator<T> unmodifiableIterator(UnmodifiableIterator<T> iterator) {
158     return checkNotNull(iterator);
159   }
160 
161   /**
162    * Returns the number of elements remaining in {@code iterator}. The iterator
163    * will be left exhausted: its {@code hasNext()} method will return
164    * {@code false}.
165    */
166   public static int size(Iterator<?> iterator) {
167     long count = 0L;
168     while (iterator.hasNext()) {
169       iterator.next();
170       count++;
171     }
172     return Ints.saturatedCast(count);
173   }
174 
175   /**
176    * Returns {@code true} if {@code iterator} contains {@code element}.
177    */
178   public static boolean contains(Iterator<?> iterator, @Nullable Object element) {
179     if (element == null) {
180       while (iterator.hasNext()) {
181         if (iterator.next() == null) {
182           return true;
183         }
184       }
185     } else {
186       while (iterator.hasNext()) {
187         if (element.equals(iterator.next())) {
188           return true;
189         }
190       }
191     }
192     return false;
193   }
194 
195   /**
196    * Traverses an iterator and removes every element that belongs to the
197    * provided collection. The iterator will be left exhausted: its
198    * {@code hasNext()} method will return {@code false}.
199    *
200    * @param removeFrom the iterator to (potentially) remove elements from
201    * @param elementsToRemove the elements to remove
202    * @return {@code true} if any element was removed from {@code iterator}
203    */
204   @CanIgnoreReturnValue
205   public static boolean removeAll(Iterator<?> removeFrom, Collection<?> elementsToRemove) {
206     checkNotNull(elementsToRemove);
207     boolean result = false;
208     while (removeFrom.hasNext()) {
209       if (elementsToRemove.contains(removeFrom.next())) {
210         removeFrom.remove();
211         result = true;
212       }
213     }
214     return result;
215   }
216 
217   /**
218    * Removes every element that satisfies the provided predicate from the
219    * iterator. The iterator will be left exhausted: its {@code hasNext()}
220    * method will return {@code false}.
221    *
222    * @param removeFrom the iterator to (potentially) remove elements from
223    * @param predicate a predicate that determines whether an element should
224    *     be removed
225    * @return {@code true} if any elements were removed from the iterator
226    * @since 2.0
227    */
228   @CanIgnoreReturnValue
229   public static <T> boolean removeIf(Iterator<T> removeFrom, Predicate<? super T> predicate) {
230     checkNotNull(predicate);
231     boolean modified = false;
232     while (removeFrom.hasNext()) {
233       if (predicate.apply(removeFrom.next())) {
234         removeFrom.remove();
235         modified = true;
236       }
237     }
238     return modified;
239   }
240 
241   /**
242    * Traverses an iterator and removes every element that does not belong to the
243    * provided collection. The iterator will be left exhausted: its
244    * {@code hasNext()} method will return {@code false}.
245    *
246    * @param removeFrom the iterator to (potentially) remove elements from
247    * @param elementsToRetain the elements to retain
248    * @return {@code true} if any element was removed from {@code iterator}
249    */
250   @CanIgnoreReturnValue
251   public static boolean retainAll(Iterator<?> removeFrom, Collection<?> elementsToRetain) {
252     checkNotNull(elementsToRetain);
253     boolean result = false;
254     while (removeFrom.hasNext()) {
255       if (!elementsToRetain.contains(removeFrom.next())) {
256         removeFrom.remove();
257         result = true;
258       }
259     }
260     return result;
261   }
262 
263   /**
264    * Determines whether two iterators contain equal elements in the same order.
265    * More specifically, this method returns {@code true} if {@code iterator1}
266    * and {@code iterator2} contain the same number of elements and every element
267    * of {@code iterator1} is equal to the corresponding element of
268    * {@code iterator2}.
269    *
270    * <p>Note that this will modify the supplied iterators, since they will have
271    * been advanced some number of elements forward.
272    */
273   public static boolean elementsEqual(Iterator<?> iterator1, Iterator<?> iterator2) {
274     while (iterator1.hasNext()) {
275       if (!iterator2.hasNext()) {
276         return false;
277       }
278       Object o1 = iterator1.next();
279       Object o2 = iterator2.next();
280       if (!Objects.equal(o1, o2)) {
281         return false;
282       }
283     }
284     return !iterator2.hasNext();
285   }
286 
287   /**
288    * Returns a string representation of {@code iterator}, with the format
289    * {@code [e1, e2, ..., en]}. The iterator will be left exhausted: its
290    * {@code hasNext()} method will return {@code false}.
291    */
292   public static String toString(Iterator<?> iterator) {
293     StringBuilder sb = new StringBuilder().append('[');
294     boolean first = true;
295     while (iterator.hasNext()) {
296       if (!first) {
297         sb.append(", ");
298       }
299       first = false;
300       sb.append(iterator.next());
301     }
302     return sb.append(']').toString();
303   }
304 
305   /**
306    * Returns the single element contained in {@code iterator}.
307    *
308    * @throws NoSuchElementException if the iterator is empty
309    * @throws IllegalArgumentException if the iterator contains multiple
310    *     elements.  The state of the iterator is unspecified.
311    */
312   @CanIgnoreReturnValue // TODO(kak): Consider removing this?
313   public static <T> T getOnlyElement(Iterator<T> iterator) {
314     T first = iterator.next();
315     if (!iterator.hasNext()) {
316       return first;
317     }
318 
319     StringBuilder sb = new StringBuilder().append("expected one element but was: <").append(first);
320     for (int i = 0; i < 4 && iterator.hasNext(); i++) {
321       sb.append(", ").append(iterator.next());
322     }
323     if (iterator.hasNext()) {
324       sb.append(", ...");
325     }
326     sb.append('>');
327 
328     throw new IllegalArgumentException(sb.toString());
329   }
330 
331   /**
332    * Returns the single element contained in {@code iterator}, or {@code
333    * defaultValue} if the iterator is empty.
334    *
335    * @throws IllegalArgumentException if the iterator contains multiple
336    *     elements.  The state of the iterator is unspecified.
337    */
338   @CanIgnoreReturnValue // TODO(kak): Consider removing this?
339   @Nullable
340   public static <T> T getOnlyElement(Iterator<? extends T> iterator, @Nullable T defaultValue) {
341     return iterator.hasNext() ? getOnlyElement(iterator) : defaultValue;
342   }
343 
344   /**
345    * Copies an iterator's elements into an array. The iterator will be left
346    * exhausted: its {@code hasNext()} method will return {@code false}.
347    *
348    * @param iterator the iterator to copy
349    * @param type the type of the elements
350    * @return a newly-allocated array into which all the elements of the iterator
351    *         have been copied
352    */
353   @GwtIncompatible // Array.newInstance(Class, int)
354   public static <T> T[] toArray(Iterator<? extends T> iterator, Class<T> type) {
355     List<T> list = Lists.newArrayList(iterator);
356     return Iterables.toArray(list, type);
357   }
358 
359   /**
360    * Adds all elements in {@code iterator} to {@code collection}. The iterator
361    * will be left exhausted: its {@code hasNext()} method will return
362    * {@code false}.
363    *
364    * @return {@code true} if {@code collection} was modified as a result of this
365    *         operation
366    */
367   @CanIgnoreReturnValue
368   public static <T> boolean addAll(Collection<T> addTo, Iterator<? extends T> iterator) {
369     checkNotNull(addTo);
370     checkNotNull(iterator);
371     boolean wasModified = false;
372     while (iterator.hasNext()) {
373       wasModified |= addTo.add(iterator.next());
374     }
375     return wasModified;
376   }
377 
378   /**
379    * Returns the number of elements in the specified iterator that equal the
380    * specified object. The iterator will be left exhausted: its
381    * {@code hasNext()} method will return {@code false}.
382    *
383    * @see Collections#frequency
384    */
385   public static int frequency(Iterator<?> iterator, @Nullable Object element) {
386     int count = 0;
387     while (contains(iterator, element)) {
388       // Since it lives in the same class, we know contains gets to the element and then stops,
389       // though that isn't currently publicly documented.
390       count++;
391     }
392     return count;
393   }
394 
395   /**
396    * Returns an iterator that cycles indefinitely over the elements of {@code
397    * iterable}.
398    *
399    * <p>The returned iterator supports {@code remove()} if the provided iterator
400    * does. After {@code remove()} is called, subsequent cycles omit the removed
401    * element, which is no longer in {@code iterable}. The iterator's
402    * {@code hasNext()} method returns {@code true} until {@code iterable} is
403    * empty.
404    *
405    * <p><b>Warning:</b> Typical uses of the resulting iterator may produce an
406    * infinite loop. You should use an explicit {@code break} or be certain that
407    * you will eventually remove all the elements.
408    */
409   public static <T> Iterator<T> cycle(final Iterable<T> iterable) {
410     checkNotNull(iterable);
411     return new Iterator<T>() {
412       Iterator<T> iterator = emptyModifiableIterator();
413 
414       @Override
415       public boolean hasNext() {
416         /*
417          * Don't store a new Iterator until we know the user can't remove() the last returned
418          * element anymore. Otherwise, when we remove from the old iterator, we may be invalidating
419          * the new one. The result is a ConcurrentModificationException or other bad behavior.
420          *
421          * (If we decide that we really, really hate allocating two Iterators per cycle instead of
422          * one, we can optimistically store the new Iterator and then be willing to throw it out if
423          * the user calls remove().)
424          */
425         return iterator.hasNext() || iterable.iterator().hasNext();
426       }
427 
428       @Override
429       public T next() {
430         if (!iterator.hasNext()) {
431           iterator = iterable.iterator();
432           if (!iterator.hasNext()) {
433             throw new NoSuchElementException();
434           }
435         }
436         return iterator.next();
437       }
438 
439       @Override
440       public void remove() {
441         iterator.remove();
442       }
443     };
444   }
445 
446   /**
447    * Returns an iterator that cycles indefinitely over the provided elements.
448    *
449    * <p>The returned iterator supports {@code remove()}. After {@code remove()}
450    * is called, subsequent cycles omit the removed
451    * element, but {@code elements} does not change. The iterator's
452    * {@code hasNext()} method returns {@code true} until all of the original
453    * elements have been removed.
454    *
455    * <p><b>Warning:</b> Typical uses of the resulting iterator may produce an
456    * infinite loop. You should use an explicit {@code break} or be certain that
457    * you will eventually remove all the elements.
458    */
459   @SafeVarargs
460   public static <T> Iterator<T> cycle(T... elements) {
461     return cycle(Lists.newArrayList(elements));
462   }
463 
464   /**
465    * Returns an Iterator that walks the specified array, nulling out elements behind it.
466    * This can avoid memory leaks when an element is no longer necessary.
467    *
468    * This is mainly just to avoid the intermediate ArrayDeque in ConsumingQueueIterator.
469    */
470   private static <T> Iterator<T> consumingForArray(final T... elements) {
471     return new UnmodifiableIterator<T>() {
472       int index = 0;
473 
474       @Override
475       public boolean hasNext() {
476         return index < elements.length;
477       }
478 
479       @Override
480       public T next() {
481         if (!hasNext()) {
482           throw new NoSuchElementException();
483         }
484         T result = elements[index];
485         elements[index] = null;
486         index++;
487         return result;
488       }
489     };
490   }
491 
492   /**
493    * Combines two iterators into a single iterator. The returned iterator
494    * iterates across the elements in {@code a}, followed by the elements in
495    * {@code b}. The source iterators are not polled until necessary.
496    *
497    * <p>The returned iterator supports {@code remove()} when the corresponding
498    * input iterator supports it.
499    */
500   public static <T> Iterator<T> concat(Iterator<? extends T> a, Iterator<? extends T> b) {
501     checkNotNull(a);
502     checkNotNull(b);
503     return concat(consumingForArray(a, b));
504   }
505 
506   /**
507    * Combines three iterators into a single iterator. The returned iterator
508    * iterates across the elements in {@code a}, followed by the elements in
509    * {@code b}, followed by the elements in {@code c}. The source iterators
510    * are not polled until necessary.
511    *
512    * <p>The returned iterator supports {@code remove()} when the corresponding
513    * input iterator supports it.
514    */
515   public static <T> Iterator<T> concat(
516       Iterator<? extends T> a, Iterator<? extends T> b, Iterator<? extends T> c) {
517     checkNotNull(a);
518     checkNotNull(b);
519     checkNotNull(c);
520     return concat(consumingForArray(a, b, c));
521   }
522 
523   /**
524    * Combines four iterators into a single iterator. The returned iterator
525    * iterates across the elements in {@code a}, followed by the elements in
526    * {@code b}, followed by the elements in {@code c}, followed by the elements
527    * in {@code d}. The source iterators are not polled until necessary.
528    *
529    * <p>The returned iterator supports {@code remove()} when the corresponding
530    * input iterator supports it.
531    */
532   public static <T> Iterator<T> concat(
533       Iterator<? extends T> a,
534       Iterator<? extends T> b,
535       Iterator<? extends T> c,
536       Iterator<? extends T> d) {
537     checkNotNull(a);
538     checkNotNull(b);
539     checkNotNull(c);
540     checkNotNull(d);
541     return concat(consumingForArray(a, b, c, d));
542   }
543 
544   /**
545    * Combines multiple iterators into a single iterator. The returned iterator
546    * iterates across the elements of each iterator in {@code inputs}. The input
547    * iterators are not polled until necessary.
548    *
549    * <p>The returned iterator supports {@code remove()} when the corresponding
550    * input iterator supports it.
551    *
552    * @throws NullPointerException if any of the provided iterators is null
553    */
554   public static <T> Iterator<T> concat(Iterator<? extends T>... inputs) {
555     return concatNoDefensiveCopy(Arrays.copyOf(inputs, inputs.length));
556   }
557 
558   /**
559    * Concats a varargs array of iterators without making a defensive copy of the array.
560    */
561   static <T> Iterator<T> concatNoDefensiveCopy(Iterator<? extends T>... inputs) {
562     for (Iterator<? extends T> input : checkNotNull(inputs)) {
563       checkNotNull(input);
564     }
565     return concat(consumingForArray(inputs));
566   }
567 
568   /**
569    * Combines multiple iterators into a single iterator. The returned iterator
570    * iterates across the elements of each iterator in {@code inputs}. The input
571    * iterators are not polled until necessary.
572    *
573    * <p>The returned iterator supports {@code remove()} when the corresponding
574    * input iterator supports it. The methods of the returned iterator may throw
575    * {@code NullPointerException} if any of the input iterators is null.
576    */
577   public static <T> Iterator<T> concat(Iterator<? extends Iterator<? extends T>> inputs) {
578     return new ConcatenatedIterator<T>(inputs);
579   }
580 
581   /**
582    * Divides an iterator into unmodifiable sublists of the given size (the final
583    * list may be smaller). For example, partitioning an iterator containing
584    * {@code [a, b, c, d, e]} with a partition size of 3 yields {@code
585    * [[a, b, c], [d, e]]} -- an outer iterator containing two inner lists of
586    * three and two elements, all in the original order.
587    *
588    * <p>The returned lists implement {@link java.util.RandomAccess}.
589    *
590    * @param iterator the iterator to return a partitioned view of
591    * @param size the desired size of each partition (the last may be smaller)
592    * @return an iterator of immutable lists containing the elements of {@code
593    *     iterator} divided into partitions
594    * @throws IllegalArgumentException if {@code size} is nonpositive
595    */
596   public static <T> UnmodifiableIterator<List<T>> partition(Iterator<T> iterator, int size) {
597     return partitionImpl(iterator, size, false);
598   }
599 
600   /**
601    * Divides an iterator into unmodifiable sublists of the given size, padding
602    * the final iterator with null values if necessary. For example, partitioning
603    * an iterator containing {@code [a, b, c, d, e]} with a partition size of 3
604    * yields {@code [[a, b, c], [d, e, null]]} -- an outer iterator containing
605    * two inner lists of three elements each, all in the original order.
606    *
607    * <p>The returned lists implement {@link java.util.RandomAccess}.
608    *
609    * @param iterator the iterator to return a partitioned view of
610    * @param size the desired size of each partition
611    * @return an iterator of immutable lists containing the elements of {@code
612    *     iterator} divided into partitions (the final iterable may have
613    *     trailing null elements)
614    * @throws IllegalArgumentException if {@code size} is nonpositive
615    */
616   public static <T> UnmodifiableIterator<List<T>> paddedPartition(Iterator<T> iterator, int size) {
617     return partitionImpl(iterator, size, true);
618   }
619 
620   private static <T> UnmodifiableIterator<List<T>> partitionImpl(
621       final Iterator<T> iterator, final int size, final boolean pad) {
622     checkNotNull(iterator);
623     checkArgument(size > 0);
624     return new UnmodifiableIterator<List<T>>() {
625       @Override
626       public boolean hasNext() {
627         return iterator.hasNext();
628       }
629 
630       @Override
631       public List<T> next() {
632         if (!hasNext()) {
633           throw new NoSuchElementException();
634         }
635         Object[] array = new Object[size];
636         int count = 0;
637         for (; count < size && iterator.hasNext(); count++) {
638           array[count] = iterator.next();
639         }
640         for (int i = count; i < size; i++) {
641           array[i] = null; // for GWT
642         }
643 
644         @SuppressWarnings("unchecked") // we only put Ts in it
645         List<T> list = Collections.unmodifiableList((List<T>) Arrays.asList(array));
646         return (pad || count == size) ? list : list.subList(0, count);
647       }
648     };
649   }
650 
651   /**
652    * Returns a view of {@code unfiltered} containing all elements that satisfy
653    * the input predicate {@code retainIfTrue}.
654    */
655   public static <T> UnmodifiableIterator<T> filter(
656       final Iterator<T> unfiltered, final Predicate<? super T> retainIfTrue) {
657     checkNotNull(unfiltered);
658     checkNotNull(retainIfTrue);
659     return new AbstractIterator<T>() {
660       @Override
661       protected T computeNext() {
662         while (unfiltered.hasNext()) {
663           T element = unfiltered.next();
664           if (retainIfTrue.apply(element)) {
665             return element;
666           }
667         }
668         return endOfData();
669       }
670     };
671   }
672 
673   /**
674    * Returns a view of {@code unfiltered} containing all elements that are of
675    * the type {@code desiredType}.
676    */
677   @SuppressWarnings("unchecked") // can cast to <T> because non-Ts are removed
678   @GwtIncompatible // Class.isInstance
679   public static <T> UnmodifiableIterator<T> filter(Iterator<?> unfiltered, Class<T> desiredType) {
680     return (UnmodifiableIterator<T>) filter(unfiltered, instanceOf(desiredType));
681   }
682 
683   /**
684    * Returns {@code true} if one or more elements returned by {@code iterator}
685    * satisfy the given predicate.
686    */
687   public static <T> boolean any(Iterator<T> iterator, Predicate<? super T> predicate) {
688     return indexOf(iterator, predicate) != -1;
689   }
690 
691   /**
692    * Returns {@code true} if every element returned by {@code iterator}
693    * satisfies the given predicate. If {@code iterator} is empty, {@code true}
694    * is returned.
695    */
696   public static <T> boolean all(Iterator<T> iterator, Predicate<? super T> predicate) {
697     checkNotNull(predicate);
698     while (iterator.hasNext()) {
699       T element = iterator.next();
700       if (!predicate.apply(element)) {
701         return false;
702       }
703     }
704     return true;
705   }
706 
707   /**
708    * Returns the first element in {@code iterator} that satisfies the given
709    * predicate; use this method only when such an element is known to exist. If
710    * no such element is found, the iterator will be left exhausted: its {@code
711    * hasNext()} method will return {@code false}. If it is possible that
712    * <i>no</i> element will match, use {@link #tryFind} or {@link
713    * #find(Iterator, Predicate, Object)} instead.
714    *
715    * @throws NoSuchElementException if no element in {@code iterator} matches
716    *     the given predicate
717    */
718   public static <T> T find(Iterator<T> iterator, Predicate<? super T> predicate) {
719     checkNotNull(iterator);
720     checkNotNull(predicate);
721     while (iterator.hasNext()) {
722       T t = iterator.next();
723       if (predicate.apply(t)) {
724         return t;
725       }
726     }
727     throw new NoSuchElementException();
728   }
729 
730   /**
731    * Returns the first element in {@code iterator} that satisfies the given
732    * predicate. If no such element is found, {@code defaultValue} will be
733    * returned from this method and the iterator will be left exhausted: its
734    * {@code hasNext()} method will return {@code false}. Note that this can
735    * usually be handled more naturally using {@code
736    * tryFind(iterator, predicate).or(defaultValue)}.
737    *
738    * @since 7.0
739    */
740   @Nullable
741   public static <T> T find(
742       Iterator<? extends T> iterator, Predicate<? super T> predicate, @Nullable T defaultValue) {
743     checkNotNull(iterator);
744     checkNotNull(predicate);
745     while (iterator.hasNext()) {
746       T t = iterator.next();
747       if (predicate.apply(t)) {
748         return t;
749       }
750     }
751     return defaultValue;
752   }
753 
754   /**
755    * Returns an {@link Optional} containing the first element in {@code
756    * iterator} that satisfies the given predicate, if such an element exists. If
757    * no such element is found, an empty {@link Optional} will be returned from
758    * this method and the iterator will be left exhausted: its {@code
759    * hasNext()} method will return {@code false}.
760    *
761    * <p><b>Warning:</b> avoid using a {@code predicate} that matches {@code
762    * null}. If {@code null} is matched in {@code iterator}, a
763    * NullPointerException will be thrown.
764    *
765    * @since 11.0
766    */
767   public static <T> Optional<T> tryFind(Iterator<T> iterator, Predicate<? super T> predicate) {
768     checkNotNull(iterator);
769     checkNotNull(predicate);
770     while (iterator.hasNext()) {
771       T t = iterator.next();
772       if (predicate.apply(t)) {
773         return Optional.of(t);
774       }
775     }
776     return Optional.absent();
777   }
778 
779   /**
780    * Returns the index in {@code iterator} of the first element that satisfies
781    * the provided {@code predicate}, or {@code -1} if the Iterator has no such
782    * elements.
783    *
784    * <p>More formally, returns the lowest index {@code i} such that
785    * {@code predicate.apply(Iterators.get(iterator, i))} returns {@code true},
786    * or {@code -1} if there is no such index.
787    *
788    * <p>If -1 is returned, the iterator will be left exhausted: its
789    * {@code hasNext()} method will return {@code false}.  Otherwise,
790    * the iterator will be set to the element which satisfies the
791    * {@code predicate}.
792    *
793    * @since 2.0
794    */
795   public static <T> int indexOf(Iterator<T> iterator, Predicate<? super T> predicate) {
796     checkNotNull(predicate, "predicate");
797     for (int i = 0; iterator.hasNext(); i++) {
798       T current = iterator.next();
799       if (predicate.apply(current)) {
800         return i;
801       }
802     }
803     return -1;
804   }
805 
806   /**
807    * Returns a view containing the result of applying {@code function} to each
808    * element of {@code fromIterator}.
809    *
810    * <p>The returned iterator supports {@code remove()} if {@code fromIterator}
811    * does. After a successful {@code remove()} call, {@code fromIterator} no
812    * longer contains the corresponding element.
813    */
814   public static <F, T> Iterator<T> transform(
815       final Iterator<F> fromIterator, final Function<? super F, ? extends T> function) {
816     checkNotNull(function);
817     return new TransformedIterator<F, T>(fromIterator) {
818       @Override
819       T transform(F from) {
820         return function.apply(from);
821       }
822     };
823   }
824 
825   /**
826    * Advances {@code iterator} {@code position + 1} times, returning the
827    * element at the {@code position}th position.
828    *
829    * @param position position of the element to return
830    * @return the element at the specified position in {@code iterator}
831    * @throws IndexOutOfBoundsException if {@code position} is negative or
832    *     greater than or equal to the number of elements remaining in
833    *     {@code iterator}
834    */
835   public static <T> T get(Iterator<T> iterator, int position) {
836     checkNonnegative(position);
837     int skipped = advance(iterator, position);
838     if (!iterator.hasNext()) {
839       throw new IndexOutOfBoundsException(
840           "position ("
841               + position
842               + ") must be less than the number of elements that remained ("
843               + skipped
844               + ")");
845     }
846     return iterator.next();
847   }
848 
849   static void checkNonnegative(int position) {
850     if (position < 0) {
851       throw new IndexOutOfBoundsException("position (" + position + ") must not be negative");
852     }
853   }
854 
855   /**
856    * Advances {@code iterator} {@code position + 1} times, returning the
857    * element at the {@code position}th position or {@code defaultValue}
858    * otherwise.
859    *
860    * @param position position of the element to return
861    * @param defaultValue the default value to return if the iterator is empty
862    *     or if {@code position} is greater than the number of elements
863    *     remaining in {@code iterator}
864    * @return the element at the specified position in {@code iterator} or
865    *     {@code defaultValue} if {@code iterator} produces fewer than
866    *     {@code position + 1} elements.
867    * @throws IndexOutOfBoundsException if {@code position} is negative
868    * @since 4.0
869    */
870   @Nullable
871   public static <T> T get(Iterator<? extends T> iterator, int position, @Nullable T defaultValue) {
872     checkNonnegative(position);
873     advance(iterator, position);
874     return getNext(iterator, defaultValue);
875   }
876 
877   /**
878    * Returns the next element in {@code iterator} or {@code defaultValue} if
879    * the iterator is empty.  The {@link Iterables} analog to this method is
880    * {@link Iterables#getFirst}.
881    *
882    * @param defaultValue the default value to return if the iterator is empty
883    * @return the next element of {@code iterator} or the default value
884    * @since 7.0
885    */
886   @Nullable
887   public static <T> T getNext(Iterator<? extends T> iterator, @Nullable T defaultValue) {
888     return iterator.hasNext() ? iterator.next() : defaultValue;
889   }
890 
891   /**
892    * Advances {@code iterator} to the end, returning the last element.
893    *
894    * @return the last element of {@code iterator}
895    * @throws NoSuchElementException if the iterator is empty
896    */
897   public static <T> T getLast(Iterator<T> iterator) {
898     while (true) {
899       T current = iterator.next();
900       if (!iterator.hasNext()) {
901         return current;
902       }
903     }
904   }
905 
906   /**
907    * Advances {@code iterator} to the end, returning the last element or
908    * {@code defaultValue} if the iterator is empty.
909    *
910    * @param defaultValue the default value to return if the iterator is empty
911    * @return the last element of {@code iterator}
912    * @since 3.0
913    */
914   @Nullable
915   public static <T> T getLast(Iterator<? extends T> iterator, @Nullable T defaultValue) {
916     return iterator.hasNext() ? getLast(iterator) : defaultValue;
917   }
918 
919   /**
920    * Calls {@code next()} on {@code iterator}, either {@code numberToAdvance} times
921    * or until {@code hasNext()} returns {@code false}, whichever comes first.
922    *
923    * @return the number of elements the iterator was advanced
924    * @since 13.0 (since 3.0 as {@code Iterators.skip})
925    */
926   @CanIgnoreReturnValue
927   public static int advance(Iterator<?> iterator, int numberToAdvance) {
928     checkNotNull(iterator);
929     checkArgument(numberToAdvance >= 0, "numberToAdvance must be nonnegative");
930 
931     int i;
932     for (i = 0; i < numberToAdvance && iterator.hasNext(); i++) {
933       iterator.next();
934     }
935     return i;
936   }
937 
938   /**
939    * Returns a view containing the first {@code limitSize} elements of {@code
940    * iterator}. If {@code iterator} contains fewer than {@code limitSize}
941    * elements, the returned view contains all of its elements. The returned
942    * iterator supports {@code remove()} if {@code iterator} does.
943    *
944    * @param iterator the iterator to limit
945    * @param limitSize the maximum number of elements in the returned iterator
946    * @throws IllegalArgumentException if {@code limitSize} is negative
947    * @since 3.0
948    */
949   public static <T> Iterator<T> limit(final Iterator<T> iterator, final int limitSize) {
950     checkNotNull(iterator);
951     checkArgument(limitSize >= 0, "limit is negative");
952     return new Iterator<T>() {
953       private int count;
954 
955       @Override
956       public boolean hasNext() {
957         return count < limitSize && iterator.hasNext();
958       }
959 
960       @Override
961       public T next() {
962         if (!hasNext()) {
963           throw new NoSuchElementException();
964         }
965         count++;
966         return iterator.next();
967       }
968 
969       @Override
970       public void remove() {
971         iterator.remove();
972       }
973     };
974   }
975 
976   /**
977    * Returns a view of the supplied {@code iterator} that removes each element
978    * from the supplied {@code iterator} as it is returned.
979    *
980    * <p>The provided iterator must support {@link Iterator#remove()} or
981    * else the returned iterator will fail on the first call to {@code
982    * next}.
983    *
984    * @param iterator the iterator to remove and return elements from
985    * @return an iterator that removes and returns elements from the
986    *     supplied iterator
987    * @since 2.0
988    */
989   public static <T> Iterator<T> consumingIterator(final Iterator<T> iterator) {
990     checkNotNull(iterator);
991     return new UnmodifiableIterator<T>() {
992       @Override
993       public boolean hasNext() {
994         return iterator.hasNext();
995       }
996 
997       @Override
998       public T next() {
999         T next = iterator.next();
1000         iterator.remove();
1001         return next;
1002       }
1003 
1004       @Override
1005       public String toString() {
1006         return "Iterators.consumingIterator(...)";
1007       }
1008     };
1009   }
1010 
1011   /**
1012    * Deletes and returns the next value from the iterator, or returns
1013    * {@code null} if there is no such value.
1014    */
1015   @Nullable
1016   static <T> T pollNext(Iterator<T> iterator) {
1017     if (iterator.hasNext()) {
1018       T result = iterator.next();
1019       iterator.remove();
1020       return result;
1021     } else {
1022       return null;
1023     }
1024   }
1025 
1026   // Methods only in Iterators, not in Iterables
1027 
1028   /**
1029    * Clears the iterator using its remove method.
1030    */
1031   static void clear(Iterator<?> iterator) {
1032     checkNotNull(iterator);
1033     while (iterator.hasNext()) {
1034       iterator.next();
1035       iterator.remove();
1036     }
1037   }
1038 
1039   /**
1040    * Returns an iterator containing the elements of {@code array} in order. The
1041    * returned iterator is a view of the array; subsequent changes to the array
1042    * will be reflected in the iterator.
1043    *
1044    * <p><b>Note:</b> It is often preferable to represent your data using a
1045    * collection type, for example using {@link Arrays#asList(Object[])}, making
1046    * this method unnecessary.
1047    *
1048    * <p>The {@code Iterable} equivalent of this method is either {@link
1049    * Arrays#asList(Object[])}, {@link ImmutableList#copyOf(Object[])}},
1050    * or {@link ImmutableList#of}.
1051    */
1052   @SafeVarargs
1053   public static <T> UnmodifiableIterator<T> forArray(final T... array) {
1054     return forArray(array, 0, array.length, 0);
1055   }
1056 
1057   private static final class ArrayItr<T> extends AbstractIndexedListIterator<T> {
1058     static final UnmodifiableListIterator<Object> EMPTY = new ArrayItr<>(new Object[0], 0, 0, 0);
1059 
1060     private final T[] array;
1061     private final int offset;
1062 
1063     ArrayItr(T[] array, int offset, int length, int index) {
1064       super(length, index);
1065       this.array = array;
1066       this.offset = offset;
1067     }
1068 
1069     @Override
1070     protected T get(int index) {
1071       return array[offset + index];
1072     }
1073   }
1074 
1075   /**
1076    * Returns a list iterator containing the elements in the specified range of
1077    * {@code array} in order, starting at the specified index.
1078    *
1079    * <p>The {@code Iterable} equivalent of this method is {@code
1080    * Arrays.asList(array).subList(offset, offset + length).listIterator(index)}.
1081    */
1082   static <T> UnmodifiableListIterator<T> forArray(
1083       final T[] array, final int offset, int length, int index) {
1084     checkArgument(length >= 0);
1085     int end = offset + length;
1086 
1087     // Technically we should give a slightly more descriptive error on overflow
1088     Preconditions.checkPositionIndexes(offset, end, array.length);
1089     Preconditions.checkPositionIndex(index, length);
1090     if (length == 0) {
1091       return emptyListIterator();
1092     }
1093     return new ArrayItr<T>(array, offset, length, index);
1094   }
1095 
1096   /**
1097    * Returns an iterator containing only {@code value}.
1098    *
1099    * <p>The {@link Iterable} equivalent of this method is {@link
1100    * Collections#singleton}.
1101    */
1102   public static <T> UnmodifiableIterator<T> singletonIterator(@Nullable final T value) {
1103     return new UnmodifiableIterator<T>() {
1104       boolean done;
1105 
1106       @Override
1107       public boolean hasNext() {
1108         return !done;
1109       }
1110 
1111       @Override
1112       public T next() {
1113         if (done) {
1114           throw new NoSuchElementException();
1115         }
1116         done = true;
1117         return value;
1118       }
1119     };
1120   }
1121 
1122   /**
1123    * Adapts an {@code Enumeration} to the {@code Iterator} interface.
1124    *
1125    * <p>This method has no equivalent in {@link Iterables} because viewing an
1126    * {@code Enumeration} as an {@code Iterable} is impossible. However, the
1127    * contents can be <i>copied</i> into a collection using {@link
1128    * Collections#list}.
1129    */
1130   public static <T> UnmodifiableIterator<T> forEnumeration(final Enumeration<T> enumeration) {
1131     checkNotNull(enumeration);
1132     return new UnmodifiableIterator<T>() {
1133       @Override
1134       public boolean hasNext() {
1135         return enumeration.hasMoreElements();
1136       }
1137 
1138       @Override
1139       public T next() {
1140         return enumeration.nextElement();
1141       }
1142     };
1143   }
1144 
1145   /**
1146    * Adapts an {@code Iterator} to the {@code Enumeration} interface.
1147    *
1148    * <p>The {@code Iterable} equivalent of this method is either {@link
1149    * Collections#enumeration} (if you have a {@link Collection}), or
1150    * {@code Iterators.asEnumeration(collection.iterator())}.
1151    */
1152   public static <T> Enumeration<T> asEnumeration(final Iterator<T> iterator) {
1153     checkNotNull(iterator);
1154     return new Enumeration<T>() {
1155       @Override
1156       public boolean hasMoreElements() {
1157         return iterator.hasNext();
1158       }
1159 
1160       @Override
1161       public T nextElement() {
1162         return iterator.next();
1163       }
1164     };
1165   }
1166 
1167   /**
1168    * Implementation of PeekingIterator that avoids peeking unless necessary.
1169    */
1170   private static class PeekingImpl<E> implements PeekingIterator<E> {
1171 
1172     private final Iterator<? extends E> iterator;
1173     private boolean hasPeeked;
1174     private E peekedElement;
1175 
1176     public PeekingImpl(Iterator<? extends E> iterator) {
1177       this.iterator = checkNotNull(iterator);
1178     }
1179 
1180     @Override
1181     public boolean hasNext() {
1182       return hasPeeked || iterator.hasNext();
1183     }
1184 
1185     @Override
1186     public E next() {
1187       if (!hasPeeked) {
1188         return iterator.next();
1189       }
1190       E result = peekedElement;
1191       hasPeeked = false;
1192       peekedElement = null;
1193       return result;
1194     }
1195 
1196     @Override
1197     public void remove() {
1198       checkState(!hasPeeked, "Can't remove after you've peeked at next");
1199       iterator.remove();
1200     }
1201 
1202     @Override
1203     public E peek() {
1204       if (!hasPeeked) {
1205         peekedElement = iterator.next();
1206         hasPeeked = true;
1207       }
1208       return peekedElement;
1209     }
1210   }
1211 
1212   /**
1213    * Returns a {@code PeekingIterator} backed by the given iterator.
1214    *
1215    * <p>Calls to the {@code peek} method with no intervening calls to {@code
1216    * next} do not affect the iteration, and hence return the same object each
1217    * time. A subsequent call to {@code next} is guaranteed to return the same
1218    * object again. For example: <pre>   {@code
1219    *
1220    *   PeekingIterator<String> peekingIterator =
1221    *       Iterators.peekingIterator(Iterators.forArray("a", "b"));
1222    *   String a1 = peekingIterator.peek(); // returns "a"
1223    *   String a2 = peekingIterator.peek(); // also returns "a"
1224    *   String a3 = peekingIterator.next(); // also returns "a"}</pre>
1225    *
1226    * <p>Any structural changes to the underlying iteration (aside from those
1227    * performed by the iterator's own {@link PeekingIterator#remove()} method)
1228    * will leave the iterator in an undefined state.
1229    *
1230    * <p>The returned iterator does not support removal after peeking, as
1231    * explained by {@link PeekingIterator#remove()}.
1232    *
1233    * <p>Note: If the given iterator is already a {@code PeekingIterator},
1234    * it <i>might</i> be returned to the caller, although this is neither
1235    * guaranteed to occur nor required to be consistent.  For example, this
1236    * method <i>might</i> choose to pass through recognized implementations of
1237    * {@code PeekingIterator} when the behavior of the implementation is
1238    * known to meet the contract guaranteed by this method.
1239    *
1240    * <p>There is no {@link Iterable} equivalent to this method, so use this
1241    * method to wrap each individual iterator as it is generated.
1242    *
1243    * @param iterator the backing iterator. The {@link PeekingIterator} assumes
1244    *     ownership of this iterator, so users should cease making direct calls
1245    *     to it after calling this method.
1246    * @return a peeking iterator backed by that iterator. Apart from the
1247    *     additional {@link PeekingIterator#peek()} method, this iterator behaves
1248    *     exactly the same as {@code iterator}.
1249    */
1250   public static <T> PeekingIterator<T> peekingIterator(Iterator<? extends T> iterator) {
1251     if (iterator instanceof PeekingImpl) {
1252       // Safe to cast <? extends T> to <T> because PeekingImpl only uses T
1253       // covariantly (and cannot be subclassed to add non-covariant uses).
1254       @SuppressWarnings("unchecked")
1255       PeekingImpl<T> peeking = (PeekingImpl<T>) iterator;
1256       return peeking;
1257     }
1258     return new PeekingImpl<T>(iterator);
1259   }
1260 
1261   /**
1262    * Simply returns its argument.
1263    *
1264    * @deprecated no need to use this
1265    * @since 10.0
1266    */
1267   @Deprecated
1268   public static <T> PeekingIterator<T> peekingIterator(PeekingIterator<T> iterator) {
1269     return checkNotNull(iterator);
1270   }
1271 
1272   /**
1273    * Returns an iterator over the merged contents of all given
1274    * {@code iterators}, traversing every element of the input iterators.
1275    * Equivalent entries will not be de-duplicated.
1276    *
1277    * <p>Callers must ensure that the source {@code iterators} are in
1278    * non-descending order as this method does not sort its input.
1279    *
1280    * <p>For any equivalent elements across all {@code iterators}, it is
1281    * undefined which element is returned first.
1282    *
1283    * @since 11.0
1284    */
1285   @Beta
1286   public static <T> UnmodifiableIterator<T> mergeSorted(
1287       Iterable<? extends Iterator<? extends T>> iterators, Comparator<? super T> comparator) {
1288     checkNotNull(iterators, "iterators");
1289     checkNotNull(comparator, "comparator");
1290 
1291     return new MergingIterator<T>(iterators, comparator);
1292   }
1293 
1294   /**
1295    * An iterator that performs a lazy N-way merge, calculating the next value
1296    * each time the iterator is polled. This amortizes the sorting cost over the
1297    * iteration and requires less memory than sorting all elements at once.
1298    *
1299    * <p>Retrieving a single element takes approximately O(log(M)) time, where M
1300    * is the number of iterators. (Retrieving all elements takes approximately
1301    * O(N*log(M)) time, where N is the total number of elements.)
1302    */
1303   private static class MergingIterator<T> extends UnmodifiableIterator<T> {
1304     final Queue<PeekingIterator<T>> queue;
1305 
1306     public MergingIterator(
1307         Iterable<? extends Iterator<? extends T>> iterators,
1308         final Comparator<? super T> itemComparator) {
1309       // A comparator that's used by the heap, allowing the heap
1310       // to be sorted based on the top of each iterator.
1311       Comparator<PeekingIterator<T>> heapComparator =
1312           new Comparator<PeekingIterator<T>>() {
1313             @Override
1314             public int compare(PeekingIterator<T> o1, PeekingIterator<T> o2) {
1315               return itemComparator.compare(o1.peek(), o2.peek());
1316             }
1317           };
1318 
1319       queue = new PriorityQueue<>(2, heapComparator);
1320 
1321       for (Iterator<? extends T> iterator : iterators) {
1322         if (iterator.hasNext()) {
1323           queue.add(Iterators.peekingIterator(iterator));
1324         }
1325       }
1326     }
1327 
1328     @Override
1329     public boolean hasNext() {
1330       return !queue.isEmpty();
1331     }
1332 
1333     @Override
1334     public T next() {
1335       PeekingIterator<T> nextIter = queue.remove();
1336       T next = nextIter.next();
1337       if (nextIter.hasNext()) {
1338         queue.add(nextIter);
1339       }
1340       return next;
1341     }
1342   }
1343 
1344   private static class ConcatenatedIterator<T> implements Iterator<T> {
1345     /* The last iterator to return an element.  Calls to remove() go to this iterator. */
1346     private Iterator<? extends T> toRemove;
1347 
1348     /* The iterator currently returning elements. */
1349     private Iterator<? extends T> iterator;
1350 
1351     /*
1352      * We track the "meta iterators," the iterators-of-iterators, below.  Usually, topMetaIterator
1353      * is the only one in use, but if we encounter nested concatenations, we start a deque of
1354      * meta-iterators rather than letting the nesting get arbitrarily deep.  This keeps each
1355      * operation O(1).
1356      */
1357 
1358     private Iterator<? extends Iterator<? extends T>> topMetaIterator;
1359 
1360     // Only becomes nonnull if we encounter nested concatenations.
1361     @Nullable
1362     private Deque<Iterator<? extends Iterator<? extends T>>> metaIterators;
1363 
1364     ConcatenatedIterator(Iterator<? extends Iterator<? extends T>> metaIterator) {
1365       iterator = emptyIterator();
1366       topMetaIterator = checkNotNull(metaIterator);
1367     }
1368 
1369     // Returns a nonempty meta-iterator or, if all meta-iterators are empty, null.
1370     @Nullable
1371     private Iterator<? extends Iterator<? extends T>> getTopMetaIterator() {
1372       while (topMetaIterator == null || !topMetaIterator.hasNext()) {
1373         if (metaIterators != null && !metaIterators.isEmpty()) {
1374           topMetaIterator = metaIterators.removeFirst();
1375         } else {
1376           return null;
1377         }
1378       }
1379       return topMetaIterator;
1380     }
1381 
1382     @Override
1383     public boolean hasNext() {
1384       while (!checkNotNull(iterator).hasNext()) {
1385         // this weird checkNotNull positioning appears required by our tests, which expect
1386         // both hasNext and next to throw NPE if an input iterator is null.
1387 
1388         topMetaIterator = getTopMetaIterator();
1389         if (topMetaIterator == null) {
1390           return false;
1391         }
1392 
1393         iterator = topMetaIterator.next();
1394 
1395         if (iterator instanceof ConcatenatedIterator) {
1396           // Instead of taking linear time in the number of nested concatenations, unpack
1397           // them into the queue
1398           @SuppressWarnings("unchecked")
1399           ConcatenatedIterator<T> topConcat = (ConcatenatedIterator<T>) iterator;
1400           iterator = topConcat.iterator;
1401 
1402           // topConcat.topMetaIterator, then topConcat.metaIterators, then this.topMetaIterator,
1403           // then this.metaIterators
1404 
1405           if (this.metaIterators == null) {
1406             this.metaIterators = new ArrayDeque<>();
1407           }
1408           this.metaIterators.addFirst(this.topMetaIterator);
1409           if (topConcat.metaIterators != null) {
1410             while (!topConcat.metaIterators.isEmpty()) {
1411               this.metaIterators.addFirst(topConcat.metaIterators.removeLast());
1412             }
1413           }
1414           this.topMetaIterator = topConcat.topMetaIterator;
1415         }
1416       }
1417       return true;
1418     }
1419 
1420     @Override
1421     public T next() {
1422       if (hasNext()) {
1423         toRemove = iterator;
1424         return iterator.next();
1425       } else {
1426         throw new NoSuchElementException();
1427       }
1428     }
1429 
1430     @Override
1431     public void remove() {
1432       CollectPreconditions.checkRemove(toRemove != null);
1433       toRemove.remove();
1434       toRemove = null;
1435     }
1436   }
1437 
1438   /**
1439    * Used to avoid http://bugs.sun.com/view_bug.do?bug_id=6558557
1440    */
1441   static <T> ListIterator<T> cast(Iterator<T> iterator) {
1442     return (ListIterator<T>) iterator;
1443   }
1444 }