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
017package com.google.common.collect;
018
019import static com.google.common.base.Preconditions.checkArgument;
020import static com.google.common.base.Preconditions.checkNotNull;
021import static com.google.common.base.Preconditions.checkState;
022
023import com.google.common.annotations.Beta;
024import com.google.common.annotations.GwtCompatible;
025import com.google.common.annotations.GwtIncompatible;
026import com.google.common.base.Function;
027import com.google.common.base.Objects;
028import com.google.common.base.Preconditions;
029import com.google.common.base.Predicate;
030import com.google.common.base.Predicates;
031
032import java.util.Arrays;
033import java.util.Collection;
034import java.util.Collections;
035import java.util.Enumeration;
036import java.util.Iterator;
037import java.util.List;
038import java.util.NoSuchElementException;
039
040import javax.annotation.Nullable;
041
042/**
043 * This class contains static utility methods that operate on or return objects
044 * of type {@link Iterator}. Except as noted, each method has a corresponding
045 * {@link Iterable}-based method in the {@link Iterables} class.
046 *
047 * <p><i>Performance notes:</i> Unless otherwise noted, all of the iterators
048 * produced in this class are <i>lazy</i>, which means that they only advance
049 * the backing iteration when absolutely necessary.
050 *
051 * @author Kevin Bourrillion
052 * @author Jared Levy
053 * @since 2 (imported from Google Collections Library)
054 */
055@GwtCompatible(emulated = true)
056public final class Iterators {
057  private Iterators() {}
058
059  static final UnmodifiableIterator<Object> EMPTY_ITERATOR
060      = new UnmodifiableIterator<Object>() {
061        @Override
062        public boolean hasNext() {
063          return false;
064        }
065        @Override
066        public Object next() {
067          throw new NoSuchElementException();
068        }
069      };
070
071  /**
072   * Returns the empty iterator.
073   *
074   * <p>The {@link Iterable} equivalent of this method is {@link
075   * Collections#emptySet}.
076   */
077  // Casting to any type is safe since there are no actual elements.
078  @SuppressWarnings("unchecked")
079  public static <T> UnmodifiableIterator<T> emptyIterator() {
080    return (UnmodifiableIterator<T>) EMPTY_ITERATOR;
081  }
082
083  private static final Iterator<Object> EMPTY_MODIFIABLE_ITERATOR =
084      new Iterator<Object>() {
085        @Override public boolean hasNext() {
086          return false;
087        }
088
089        @Override public Object next() {
090          throw new NoSuchElementException();
091        }
092
093        @Override public void remove() {
094          throw new IllegalStateException();
095        }
096      };
097
098  /**
099   * Returns the empty {@code Iterator} that throws
100   * {@link IllegalStateException} instead of
101   * {@link UnsupportedOperationException} on a call to
102   * {@link Iterator#remove()}.
103   */
104  // Casting to any type is safe since there are no actual elements.
105  @SuppressWarnings("unchecked")
106  static <T> Iterator<T> emptyModifiableIterator() {
107    return (Iterator<T>) EMPTY_MODIFIABLE_ITERATOR;
108  }
109
110  /** Returns an unmodifiable view of {@code iterator}. */
111  public static <T> UnmodifiableIterator<T> unmodifiableIterator(
112      final Iterator<T> iterator) {
113    checkNotNull(iterator);
114    return new UnmodifiableIterator<T>() {
115      @Override
116      public boolean hasNext() {
117        return iterator.hasNext();
118      }
119      @Override
120      public T next() {
121        return iterator.next();
122      }
123    };
124  }
125
126  /**
127   * Returns the number of elements remaining in {@code iterator}. The iterator
128   * will be left exhausted: its {@code hasNext()} method will return
129   * {@code false}.
130   */
131  public static int size(Iterator<?> iterator) {
132    int count = 0;
133    while (iterator.hasNext()) {
134      iterator.next();
135      count++;
136    }
137    return count;
138  }
139
140  /**
141   * Returns {@code true} if {@code iterator} contains {@code element}.
142   */
143  public static boolean contains(Iterator<?> iterator, @Nullable Object element)
144  {
145    if (element == null) {
146      while (iterator.hasNext()) {
147        if (iterator.next() == null) {
148          return true;
149        }
150      }
151    } else {
152      while (iterator.hasNext()) {
153        if (element.equals(iterator.next())) {
154          return true;
155        }
156      }
157    }
158    return false;
159  }
160
161  /**
162   * Traverses an iterator and removes every element that belongs to the
163   * provided collection. The iterator will be left exhausted: its
164   * {@code hasNext()} method will return {@code false}.
165   *
166   * @param removeFrom the iterator to (potentially) remove elements from
167   * @param elementsToRemove the elements to remove
168   * @return {@code true} if any elements are removed from {@code iterator}
169   */
170  public static boolean removeAll(
171      Iterator<?> removeFrom, Collection<?> elementsToRemove) {
172    checkNotNull(elementsToRemove);
173    boolean modified = false;
174    while (removeFrom.hasNext()) {
175      if (elementsToRemove.contains(removeFrom.next())) {
176        removeFrom.remove();
177        modified = true;
178      }
179    }
180    return modified;
181  }
182
183  /**
184   * Removes every element that satisfies the provided predicate from the
185   * iterator. The iterator will be left exhausted: its {@code hasNext()}
186   * method will return {@code false}.
187   *
188   * @param removeFrom the iterator to (potentially) remove elements from
189   * @param predicate a predicate that determines whether an element should
190   *     be removed
191   * @return {@code true} if any elements were removed from the iterator
192   * @since 2
193   */
194  public static <T> boolean removeIf(
195      Iterator<T> removeFrom, Predicate<? super T> predicate) {
196    checkNotNull(predicate);
197    boolean modified = false;
198    while (removeFrom.hasNext()) {
199      if (predicate.apply(removeFrom.next())) {
200        removeFrom.remove();
201        modified = true;
202      }
203    }
204    return modified;
205  }
206
207  /**
208   * Traverses an iterator and removes every element that does not belong to the
209   * provided collection. The iterator will be left exhausted: its
210   * {@code hasNext()} method will return {@code false}.
211   *
212   * @param removeFrom the iterator to (potentially) remove elements from
213   * @param elementsToRetain the elements to retain
214   * @return {@code true} if any elements are removed from {@code iterator}
215   */
216  public static boolean retainAll(
217      Iterator<?> removeFrom, Collection<?> elementsToRetain) {
218    checkNotNull(elementsToRetain);
219    boolean modified = false;
220    while (removeFrom.hasNext()) {
221      if (!elementsToRetain.contains(removeFrom.next())) {
222        removeFrom.remove();
223        modified = true;
224      }
225    }
226    return modified;
227  }
228
229  /**
230   * Determines whether two iterators contain equal elements in the same order.
231   * More specifically, this method returns {@code true} if {@code iterator1}
232   * and {@code iterator2} contain the same number of elements and every element
233   * of {@code iterator1} is equal to the corresponding element of
234   * {@code iterator2}.
235   *
236   * <p>Note that this will modify the supplied iterators, since they will have
237   * been advanced some number of elements forward.
238   */
239  public static boolean elementsEqual(
240      Iterator<?> iterator1, Iterator<?> iterator2) {
241    while (iterator1.hasNext()) {
242      if (!iterator2.hasNext()) {
243        return false;
244      }
245      Object o1 = iterator1.next();
246      Object o2 = iterator2.next();
247      if (!Objects.equal(o1, o2)) {
248        return false;
249      }
250    }
251    return !iterator2.hasNext();
252  }
253
254  /**
255   * Returns a string representation of {@code iterator}, with the format
256   * {@code [e1, e2, ..., en]}. The iterator will be left exhausted: its
257   * {@code hasNext()} method will return {@code false}.
258   */
259  public static String toString(Iterator<?> iterator) {
260    if (!iterator.hasNext()) {
261      return "[]";
262    }
263    StringBuilder builder = new StringBuilder();
264    builder.append('[').append(iterator.next());
265    while (iterator.hasNext()) {
266      builder.append(", ").append(iterator.next());
267    }
268    return builder.append(']').toString();
269  }
270
271  /**
272   * Returns the single element contained in {@code iterator}.
273   *
274   * @throws NoSuchElementException if the iterator is empty
275   * @throws IllegalArgumentException if the iterator contains multiple
276   *     elements.  The state of the iterator is unspecified.
277   */
278  public static <T> T getOnlyElement(Iterator<T> iterator) {
279    T first = iterator.next();
280    if (!iterator.hasNext()) {
281      return first;
282    }
283
284    StringBuilder sb = new StringBuilder();
285    sb.append("expected one element but was: <" + first);
286    for (int i = 0; i < 4 && iterator.hasNext(); i++) {
287      sb.append(", " + iterator.next());
288    }
289    if (iterator.hasNext()) {
290      sb.append(", ...");
291    }
292    sb.append('>');
293
294    throw new IllegalArgumentException(sb.toString());
295  }
296
297  /**
298   * Returns the single element contained in {@code iterator}, or {@code
299   * defaultValue} if the iterator is empty.
300   *
301   * @throws IllegalArgumentException if the iterator contains multiple
302   *     elements.  The state of the iterator is unspecified.
303   */
304  public static <T> T getOnlyElement(
305      Iterator<T> iterator, @Nullable T defaultValue) {
306    return iterator.hasNext() ? getOnlyElement(iterator) : defaultValue;
307  }
308
309  /**
310   * Copies an iterator's elements into an array. The iterator will be left
311   * exhausted: its {@code hasNext()} method will return {@code false}.
312   *
313   * @param iterator the iterator to copy
314   * @param type the type of the elements
315   * @return a newly-allocated array into which all the elements of the iterator
316   *         have been copied
317   */
318  @GwtIncompatible("Array.newInstance(Class, int)")
319  public static <T> T[] toArray(
320      Iterator<? extends T> iterator, Class<T> type) {
321    List<T> list = Lists.newArrayList(iterator);
322    return Iterables.toArray(list, type);
323  }
324
325  /**
326   * Adds all elements in {@code iterator} to {@code collection}. The iterator
327   * will be left exhausted: its {@code hasNext()} method will return
328   * {@code false}.
329   *
330   * @return {@code true} if {@code collection} was modified as a result of this
331   *         operation
332   */
333  public static <T> boolean addAll(
334      Collection<T> addTo, Iterator<? extends T> iterator) {
335    checkNotNull(addTo);
336    boolean wasModified = false;
337    while (iterator.hasNext()) {
338      wasModified |= addTo.add(iterator.next());
339    }
340    return wasModified;
341  }
342
343  /**
344   * Returns the number of elements in the specified iterator that equal the
345   * specified object. The iterator will be left exhausted: its
346   * {@code hasNext()} method will return {@code false}.
347   *
348   * @see Collections#frequency
349   */
350  public static int frequency(Iterator<?> iterator, @Nullable Object element) {
351    int result = 0;
352    if (element == null) {
353      while (iterator.hasNext()) {
354        if (iterator.next() == null) {
355          result++;
356        }
357      }
358    } else {
359      while (iterator.hasNext()) {
360        if (element.equals(iterator.next())) {
361          result++;
362        }
363      }
364    }
365    return result;
366  }
367
368  /**
369   * Returns an iterator that cycles indefinitely over the elements of {@code
370   * iterable}.
371   *
372   * <p>The returned iterator supports {@code remove()} if the provided iterator
373   * does. After {@code remove()} is called, subsequent cycles omit the removed
374   * element, which is no longer in {@code iterable}. The iterator's
375   * {@code hasNext()} method returns {@code true} until {@code iterable} is
376   * empty.
377   *
378   * <p><b>Warning:</b> Typical uses of the resulting iterator may produce an
379   * infinite loop. You should use an explicit {@code break} or be certain that
380   * you will eventually remove all the elements.
381   */
382  public static <T> Iterator<T> cycle(final Iterable<T> iterable) {
383    checkNotNull(iterable);
384    return new Iterator<T>() {
385      Iterator<T> iterator = emptyIterator();
386      Iterator<T> removeFrom;
387
388      @Override
389      public boolean hasNext() {
390        if (!iterator.hasNext()) {
391          iterator = iterable.iterator();
392        }
393        return iterator.hasNext();
394      }
395      @Override
396      public T next() {
397        if (!hasNext()) {
398          throw new NoSuchElementException();
399        }
400        removeFrom = iterator;
401        return iterator.next();
402      }
403      @Override
404      public void remove() {
405        checkState(removeFrom != null,
406            "no calls to next() since last call to remove()");
407        removeFrom.remove();
408        removeFrom = null;
409      }
410    };
411  }
412
413  /**
414   * Returns an iterator that cycles indefinitely over the provided elements.
415   *
416   * <p>The returned iterator supports {@code remove()} if the provided iterator
417   * does. After {@code remove()} is called, subsequent cycles omit the removed
418   * element, but {@code elements} does not change. The iterator's
419   * {@code hasNext()} method returns {@code true} until all of the original
420   * elements have been removed.
421   *
422   * <p><b>Warning:</b> Typical uses of the resulting iterator may produce an
423   * infinite loop. You should use an explicit {@code break} or be certain that
424   * you will eventually remove all the elements.
425   */
426  public static <T> Iterator<T> cycle(T... elements) {
427    return cycle(Lists.newArrayList(elements));
428  }
429
430  /**
431   * Combines two iterators into a single iterator. The returned iterator
432   * iterates across the elements in {@code a}, followed by the elements in
433   * {@code b}. The source iterators are not polled until necessary.
434   *
435   * <p>The returned iterator supports {@code remove()} when the corresponding
436   * input iterator supports it.
437   */
438  @SuppressWarnings("unchecked")
439  public static <T> Iterator<T> concat(Iterator<? extends T> a,
440      Iterator<? extends T> b) {
441    checkNotNull(a);
442    checkNotNull(b);
443    return concat(Arrays.asList(a, b).iterator());
444  }
445
446  /**
447   * Combines three iterators into a single iterator. The returned iterator
448   * iterates across the elements in {@code a}, followed by the elements in
449   * {@code b}, followed by the elements in {@code c}. The source iterators
450   * are not polled until necessary.
451   *
452   * <p>The returned iterator supports {@code remove()} when the corresponding
453   * input iterator supports it.
454   */
455  @SuppressWarnings("unchecked")
456  public static <T> Iterator<T> concat(Iterator<? extends T> a,
457      Iterator<? extends T> b, Iterator<? extends T> c) {
458    checkNotNull(a);
459    checkNotNull(b);
460    checkNotNull(c);
461    return concat(Arrays.asList(a, b, c).iterator());
462  }
463
464  /**
465   * Combines four iterators into a single iterator. The returned iterator
466   * iterates across the elements in {@code a}, followed by the elements in
467   * {@code b}, followed by the elements in {@code c}, followed by the elements
468   * in {@code d}. The source iterators are not polled until necessary.
469   *
470   * <p>The returned iterator supports {@code remove()} when the corresponding
471   * input iterator supports it.
472   */
473  @SuppressWarnings("unchecked")
474  public static <T> Iterator<T> concat(Iterator<? extends T> a,
475      Iterator<? extends T> b, Iterator<? extends T> c,
476      Iterator<? extends T> d) {
477    checkNotNull(a);
478    checkNotNull(b);
479    checkNotNull(c);
480    checkNotNull(d);
481    return concat(Arrays.asList(a, b, c, d).iterator());
482  }
483
484  /**
485   * Combines multiple iterators into a single iterator. The returned iterator
486   * iterates across the elements of each iterator in {@code inputs}. The input
487   * iterators are not polled until necessary.
488   *
489   * <p>The returned iterator supports {@code remove()} when the corresponding
490   * input iterator supports it.
491   *
492   * @throws NullPointerException if any of the provided iterators is null
493   */
494  public static <T> Iterator<T> concat(Iterator<? extends T>... inputs) {
495    return concat(ImmutableList.copyOf(inputs).iterator());
496  }
497
498  /**
499   * Combines multiple iterators into a single iterator. The returned iterator
500   * iterates across the elements of each iterator in {@code inputs}. The input
501   * iterators are not polled until necessary.
502   *
503   * <p>The returned iterator supports {@code remove()} when the corresponding
504   * input iterator supports it. The methods of the returned iterator may throw
505   * {@code NullPointerException} if any of the input iterators are null.
506   */
507  public static <T> Iterator<T> concat(
508      final Iterator<? extends Iterator<? extends T>> inputs) {
509    checkNotNull(inputs);
510    return new Iterator<T>() {
511      Iterator<? extends T> current = emptyIterator();
512      Iterator<? extends T> removeFrom;
513
514      @Override
515      public boolean hasNext() {
516        // http://code.google.com/p/google-collections/issues/detail?id=151
517        // current.hasNext() might be relatively expensive, worth minimizing.
518        boolean currentHasNext;
519        // checkNotNull eager for GWT
520        // note: it must be here & not where 'current' is assigned,
521        // because otherwise we'll have called inputs.next() before throwing
522        // the first NPE, and the next time around we'll call inputs.next()
523        // again, incorrectly moving beyond the error.
524        while (!(currentHasNext = checkNotNull(current).hasNext())
525            && inputs.hasNext()) {
526          current = inputs.next();
527        }
528        return currentHasNext;
529      }
530      @Override
531      public T next() {
532        if (!hasNext()) {
533          throw new NoSuchElementException();
534        }
535        removeFrom = current;
536        return current.next();
537      }
538      @Override
539      public void remove() {
540        checkState(removeFrom != null,
541            "no calls to next() since last call to remove()");
542        removeFrom.remove();
543        removeFrom = null;
544      }
545    };
546  }
547
548  /**
549   * Divides an iterator into unmodifiable sublists of the given size (the final
550   * list may be smaller). For example, partitioning an iterator containing
551   * {@code [a, b, c, d, e]} with a partition size of 3 yields {@code
552   * [[a, b, c], [d, e]]} -- an outer iterator containing two inner lists of
553   * three and two elements, all in the original order.
554   *
555   * <p>The returned lists implement {@link java.util.RandomAccess}.
556   *
557   * @param iterator the iterator to return a partitioned view of
558   * @param size the desired size of each partition (the last may be smaller)
559   * @return an iterator of immutable lists containing the elements of {@code
560   *     iterator} divided into partitions
561   * @throws IllegalArgumentException if {@code size} is nonpositive
562   */
563  public static <T> UnmodifiableIterator<List<T>> partition(
564      Iterator<T> iterator, int size) {
565    return partitionImpl(iterator, size, false);
566  }
567
568  /**
569   * Divides an iterator into unmodifiable sublists of the given size, padding
570   * the final iterator with null values if necessary. For example, partitioning
571   * an iterator containing {@code [a, b, c, d, e]} with a partition size of 3
572   * yields {@code [[a, b, c], [d, e, null]]} -- an outer iterator containing
573   * two inner lists of three elements each, all in the original order.
574   *
575   * <p>The returned lists implement {@link java.util.RandomAccess}.
576   *
577   * @param iterator the iterator to return a partitioned view of
578   * @param size the desired size of each partition
579   * @return an iterator of immutable lists containing the elements of {@code
580   *     iterator} divided into partitions (the final iterable may have
581   *     trailing null elements)
582   * @throws IllegalArgumentException if {@code size} is nonpositive
583   */
584  public static <T> UnmodifiableIterator<List<T>> paddedPartition(
585      Iterator<T> iterator, int size) {
586    return partitionImpl(iterator, size, true);
587  }
588
589  private static <T> UnmodifiableIterator<List<T>> partitionImpl(
590      final Iterator<T> iterator, final int size, final boolean pad) {
591    checkNotNull(iterator);
592    checkArgument(size > 0);
593    return new UnmodifiableIterator<List<T>>() {
594      @Override
595      public boolean hasNext() {
596        return iterator.hasNext();
597      }
598      @Override
599      public List<T> next() {
600        if (!hasNext()) {
601          throw new NoSuchElementException();
602        }
603        Object[] array = new Object[size];
604        int count = 0;
605        for (; count < size && iterator.hasNext(); count++) {
606          array[count] = iterator.next();
607        }
608
609        @SuppressWarnings("unchecked") // we only put Ts in it
610        List<T> list = Collections.unmodifiableList(
611            (List<T>) Arrays.asList(array));
612        return (pad || count == size) ? list : list.subList(0, count);
613      }
614    };
615  }
616
617  /**
618   * Returns the elements of {@code unfiltered} that satisfy a predicate.
619   */
620  public static <T> UnmodifiableIterator<T> filter(
621      final Iterator<T> unfiltered, final Predicate<? super T> predicate) {
622    checkNotNull(unfiltered);
623    checkNotNull(predicate);
624    return new AbstractIterator<T>() {
625      @Override protected T computeNext() {
626        while (unfiltered.hasNext()) {
627          T element = unfiltered.next();
628          if (predicate.apply(element)) {
629            return element;
630          }
631        }
632        return endOfData();
633      }
634    };
635  }
636
637  /**
638   * Returns all instances of class {@code type} in {@code unfiltered}. The
639   * returned iterator has elements whose class is {@code type} or a subclass of
640   * {@code type}.
641   *
642   * @param unfiltered an iterator containing objects of any type
643   * @param type the type of elements desired
644   * @return an unmodifiable iterator containing all elements of the original
645   *     iterator that were of the requested type
646   */
647  @SuppressWarnings("unchecked") // can cast to <T> because non-Ts are removed
648  @GwtIncompatible("Class.isInstance")
649  public static <T> UnmodifiableIterator<T> filter(
650      Iterator<?> unfiltered, Class<T> type) {
651    return (UnmodifiableIterator<T>)
652        filter(unfiltered, Predicates.instanceOf(type));
653  }
654
655  /**
656   * Returns {@code true} if one or more elements returned by {@code iterator}
657   * satisfy the given predicate.
658   */
659  public static <T> boolean any(
660      Iterator<T> iterator, Predicate<? super T> predicate) {
661    checkNotNull(predicate);
662    while (iterator.hasNext()) {
663      T element = iterator.next();
664      if (predicate.apply(element)) {
665        return true;
666      }
667    }
668    return false;
669  }
670
671  /**
672   * Returns {@code true} if every element returned by {@code iterator}
673   * satisfies the given predicate. If {@code iterator} is empty, {@code true}
674   * is returned.
675   */
676  public static <T> boolean all(
677      Iterator<T> iterator, Predicate<? super T> predicate) {
678    checkNotNull(predicate);
679    while (iterator.hasNext()) {
680      T element = iterator.next();
681      if (!predicate.apply(element)) {
682        return false;
683      }
684    }
685    return true;
686  }
687
688  /**
689   * Returns the first element in {@code iterator} that satisfies the given
690   * predicate.  If no such element is found, the iterator will be left
691   * exhausted: its {@code hasNext()} method will return {@code false}.
692   *
693   * @throws NoSuchElementException if no element in {@code iterator} matches
694   *     the given predicate
695   */
696  public static <T> T find(
697      Iterator<T> iterator, Predicate<? super T> predicate) {
698    return filter(iterator, predicate).next();
699  }
700
701  /**
702   * Returns the first element in {@code iterator} that satisfies the given
703   * predicate.  If no such element is found, {@code defaultValue} will be
704   * returned from this method and the iterator will be left exhausted: its
705   * {@code hasNext()} method will return {@code false}.
706   *
707   * @since 7
708   */
709  public static <T> T find(Iterator<T> iterator, Predicate<? super T> predicate,
710      @Nullable T defaultValue) {
711    UnmodifiableIterator<T> filteredIterator = filter(iterator, predicate);
712    return filteredIterator.hasNext() ? filteredIterator.next() : defaultValue;
713  }
714
715  /**
716   * Returns the index in {@code iterator} of the first element that satisfies
717   * the provided {@code predicate}, or {@code -1} if the Iterator has no such
718   * elements.
719   *
720   * <p>More formally, returns the lowest index {@code i} such that
721   * {@code predicate.apply(Iterators.get(iterator, i))} is {@code true}, or
722   * {@code -1} if there is no such index.
723   *
724   * <p>If -1 is returned, the iterator will be left exhausted: its
725   * {@code hasNext()} method will return {@code false}.  Otherwise,
726   * the iterator will be set to the element which satisfies the
727   * {@code predicate}.
728   *
729   * @since 2
730   */
731  public static <T> int indexOf(
732      Iterator<T> iterator, Predicate<? super T> predicate) {
733    checkNotNull(predicate, "predicate");
734    int i = 0;
735    while (iterator.hasNext()) {
736      T current = iterator.next();
737      if (predicate.apply(current)) {
738        return i;
739      }
740      i++;
741    }
742    return -1;
743  }
744
745  /**
746   * Returns an iterator that applies {@code function} to each element of {@code
747   * fromIterator}.
748   *
749   * <p>The returned iterator supports {@code remove()} if the provided iterator
750   * does. After a successful {@code remove()} call, {@code fromIterator} no
751   * longer contains the corresponding element.
752   */
753  public static <F, T> Iterator<T> transform(final Iterator<F> fromIterator,
754      final Function<? super F, ? extends T> function) {
755    checkNotNull(fromIterator);
756    checkNotNull(function);
757    return new Iterator<T>() {
758      @Override
759      public boolean hasNext() {
760        return fromIterator.hasNext();
761      }
762      @Override
763      public T next() {
764        F from = fromIterator.next();
765        return function.apply(from);
766      }
767      @Override
768      public void remove() {
769        fromIterator.remove();
770      }
771    };
772  }
773
774  /**
775   * Advances {@code iterator} {@code position + 1} times, returning the
776   * element at the {@code position}th position.
777   *
778   * @param position position of the element to return
779   * @return the element at the specified position in {@code iterator}
780   * @throws IndexOutOfBoundsException if {@code position} is negative or
781   *     greater than or equal to the number of elements remaining in
782   *     {@code iterator}
783   */
784  public static <T> T get(Iterator<T> iterator, int position) {
785    checkNonnegative(position);
786
787    int skipped = 0;
788    while (iterator.hasNext()) {
789      T t = iterator.next();
790      if (skipped++ == position) {
791        return t;
792      }
793    }
794
795    throw new IndexOutOfBoundsException("position (" + position
796        + ") must be less than the number of elements that remained ("
797        + skipped + ")");
798  }
799
800  private static void checkNonnegative(int position) {
801    if (position < 0) {
802      throw new IndexOutOfBoundsException("position (" + position
803          + ") must not be negative");
804    }
805  }
806
807  /**
808   * Advances {@code iterator} {@code position + 1} times, returning the
809   * element at the {@code position}th position or {@code defaultValue}
810   * otherwise.
811   *
812   * @param position position of the element to return
813   * @param defaultValue the default value to return if the iterator is empty
814   *     or if {@code position} is greater than the number of elements
815   *     remaining in {@code iterator}
816   * @return the element at the specified position in {@code iterator} or
817   *     {@code defaultValue} if {@code iterator} produces fewer than
818   *     {@code position + 1} elements.
819   * @throws IndexOutOfBoundsException if {@code position} is negative
820   * @since 4
821   */
822  public static <T> T get(Iterator<T> iterator, int position,
823      @Nullable T defaultValue) {
824    checkNonnegative(position);
825
826    try {
827      return get(iterator, position);
828    } catch (IndexOutOfBoundsException e) {
829      return defaultValue;
830    }
831  }
832
833  /**
834   * Returns the next element in {@code iterator} or {@code defaultValue} if
835   * the iterator is empty.  The {@link Iterables} analog to this method is
836   * {@link Iterables#getFirst}.
837   *
838   * @param defaultValue the default value to return if the iterator is empty
839   * @return the next element of {@code iterator} or the default value
840   * @since 7
841   */
842  public static <T> T getNext(Iterator<T> iterator, @Nullable T defaultValue) {
843    return iterator.hasNext() ? iterator.next() : defaultValue;
844  }
845
846  /**
847   * Advances {@code iterator} to the end, returning the last element.
848   *
849   * @return the last element of {@code iterator}
850   * @throws NoSuchElementException if the iterator is empty
851   */
852  public static <T> T getLast(Iterator<T> iterator) {
853    while (true) {
854      T current = iterator.next();
855      if (!iterator.hasNext()) {
856        return current;
857      }
858    }
859  }
860
861  /**
862   * Advances {@code iterator} to the end, returning the last element or
863   * {@code defaultValue} if the iterator is empty.
864   *
865   * @param defaultValue the default value to return if the iterator is empty
866   * @return the last element of {@code iterator}
867   * @since 3
868   */
869  public static <T> T getLast(Iterator<T> iterator, @Nullable T defaultValue) {
870    return iterator.hasNext() ? getLast(iterator) : defaultValue;
871  }
872
873  /**
874   * Calls {@code next()} on {@code iterator}, either {@code numberToSkip} times
875   * or until {@code hasNext()} returns {@code false}, whichever comes first.
876   *
877   * @return the number of elements skipped
878   * @since 3
879   */
880  @Beta
881  public static <T> int skip(Iterator<T> iterator, int numberToSkip) {
882    checkNotNull(iterator);
883    checkArgument(numberToSkip >= 0, "number to skip cannot be negative");
884
885    int i;
886    for (i = 0; i < numberToSkip && iterator.hasNext(); i++) {
887      iterator.next();
888    }
889    return i;
890  }
891
892  /**
893   * Creates an iterator returning the first {@code limitSize} elements of the
894   * given iterator. If the original iterator does not contain that many
895   * elements, the returned iterator will have the same behavior as the original
896   * iterator. The returned iterator supports {@code remove()} if the original
897   * iterator does.
898   *
899   * @param iterator the iterator to limit
900   * @param limitSize the maximum number of elements in the returned iterator
901   * @throws IllegalArgumentException if {@code limitSize} is negative
902   * @since 3
903   */
904  public static <T> Iterator<T> limit(
905      final Iterator<T> iterator, final int limitSize) {
906    checkNotNull(iterator);
907    checkArgument(limitSize >= 0, "limit is negative");
908    return new Iterator<T>() {
909      private int count;
910
911      @Override
912      public boolean hasNext() {
913        return count < limitSize && iterator.hasNext();
914      }
915
916      @Override
917      public T next() {
918        if (!hasNext()) {
919          throw new NoSuchElementException();
920        }
921        count++;
922        return iterator.next();
923      }
924
925      @Override
926      public void remove() {
927        iterator.remove();
928      }
929    };
930  }
931
932  /**
933   * Returns a view of the supplied {@code iterator} that removes each element
934   * from the supplied {@code iterator} as it is returned.
935   *
936   * <p>The provided iterator must support {@link Iterator#remove()} or
937   * else the returned iterator will fail on the first call to {@code
938   * next}.
939   *
940   * @param iterator the iterator to remove and return elements from
941   * @return an iterator that removes and returns elements from the
942   *     supplied iterator
943   * @since 2
944   */
945  public static <T> Iterator<T> consumingIterator(final Iterator<T> iterator) {
946    checkNotNull(iterator);
947    return new UnmodifiableIterator<T>() {
948      @Override
949      public boolean hasNext() {
950        return iterator.hasNext();
951      }
952
953      @Override
954      public T next() {
955        T next = iterator.next();
956        iterator.remove();
957        return next;
958      }
959    };
960  }
961
962  // Methods only in Iterators, not in Iterables
963
964  /**
965   * Returns an iterator containing the elements of {@code array} in order. The
966   * returned iterator is a view of the array; subsequent changes to the array
967   * will be reflected in the iterator.
968   *
969   * <p><b>Note:</b> It is often preferable to represent your data using a
970   * collection type, for example using {@link Arrays#asList(Object[])}, making
971   * this method unnecessary.
972   *
973   * <p>The {@code Iterable} equivalent of this method is either {@link
974   * Arrays#asList(Object[])}, {@link ImmutableList#copyOf(Object[])}},
975   * or {@link ImmutableList#of}.
976   */
977  public static <T> UnmodifiableIterator<T> forArray(final T... array) {
978    // TODO(kevinb): compare performance with Arrays.asList(array).iterator().
979    checkNotNull(array);  // eager for GWT.
980    return new AbstractIndexedListIterator<T>(array.length) {
981      @Override protected T get(int index) {
982        return array[index];
983      }
984    };
985  }
986
987  /**
988   * Returns an iterator containing the elements in the specified range of
989   * {@code array} in order. The returned iterator is a view of the array;
990   * subsequent changes to the array will be reflected in the iterator.
991   *
992   * <p>The {@code Iterable} equivalent of this method is {@code
993   * Arrays.asList(array).subList(offset, offset + length)}.
994   *
995   * @param array array to read elements out of
996   * @param offset index of first array element to retrieve
997   * @param length number of elements in iteration
998   * @throws IndexOutOfBoundsException if {@code offset} is negative, {@code
999   *     length} is negative, or {@code offset + length > array.length}
1000   */
1001  static <T> UnmodifiableIterator<T> forArray(
1002      final T[] array, final int offset, int length) {
1003    checkArgument(length >= 0);
1004    int end = offset + length;
1005
1006    // Technically we should give a slightly more descriptive error on overflow
1007    Preconditions.checkPositionIndexes(offset, end, array.length);
1008
1009    /*
1010     * We can't use call the two-arg constructor with arguments (offset, end)
1011     * because the returned Iterator is a ListIterator that may be moved back
1012     * past the beginning of the iteration.
1013     */
1014    return new AbstractIndexedListIterator<T>(length) {
1015      @Override protected T get(int index) {
1016        return array[offset + index];
1017      }
1018    };
1019  }
1020
1021  /**
1022   * Returns an iterator containing only {@code value}.
1023   *
1024   * <p>The {@link Iterable} equivalent of this method is {@link
1025   * Collections#singleton}.
1026   */
1027  public static <T> UnmodifiableIterator<T> singletonIterator(
1028      @Nullable final T value) {
1029    return new UnmodifiableIterator<T>() {
1030      boolean done;
1031      @Override
1032      public boolean hasNext() {
1033        return !done;
1034      }
1035      @Override
1036      public T next() {
1037        if (done) {
1038          throw new NoSuchElementException();
1039        }
1040        done = true;
1041        return value;
1042      }
1043    };
1044  }
1045
1046  /**
1047   * Adapts an {@code Enumeration} to the {@code Iterator} interface.
1048   *
1049   * <p>This method has no equivalent in {@link Iterables} because viewing an
1050   * {@code Enumeration} as an {@code Iterable} is impossible. However, the
1051   * contents can be <i>copied</i> into a collection using {@link
1052   * Collections#list}.
1053   */
1054  public static <T> UnmodifiableIterator<T> forEnumeration(
1055      final Enumeration<T> enumeration) {
1056    checkNotNull(enumeration);
1057    return new UnmodifiableIterator<T>() {
1058      @Override
1059      public boolean hasNext() {
1060        return enumeration.hasMoreElements();
1061      }
1062      @Override
1063      public T next() {
1064        return enumeration.nextElement();
1065      }
1066    };
1067  }
1068
1069  /**
1070   * Adapts an {@code Iterator} to the {@code Enumeration} interface.
1071   *
1072   * <p>The {@code Iterable} equivalent of this method is either {@link
1073   * Collections#enumeration} (if you have a {@link Collection}), or
1074   * {@code Iterators.asEnumeration(collection.iterator())}.
1075   */
1076  public static <T> Enumeration<T> asEnumeration(final Iterator<T> iterator) {
1077    checkNotNull(iterator);
1078    return new Enumeration<T>() {
1079      @Override
1080      public boolean hasMoreElements() {
1081        return iterator.hasNext();
1082      }
1083      @Override
1084      public T nextElement() {
1085        return iterator.next();
1086      }
1087    };
1088  }
1089
1090  /**
1091   * Implementation of PeekingIterator that avoids peeking unless necessary.
1092   */
1093  private static class PeekingImpl<E> implements PeekingIterator<E> {
1094
1095    private final Iterator<? extends E> iterator;
1096    private boolean hasPeeked;
1097    private E peekedElement;
1098
1099    public PeekingImpl(Iterator<? extends E> iterator) {
1100      this.iterator = checkNotNull(iterator);
1101    }
1102
1103    @Override
1104    public boolean hasNext() {
1105      return hasPeeked || iterator.hasNext();
1106    }
1107
1108    @Override
1109    public E next() {
1110      if (!hasPeeked) {
1111        return iterator.next();
1112      }
1113      E result = peekedElement;
1114      hasPeeked = false;
1115      peekedElement = null;
1116      return result;
1117    }
1118
1119    @Override
1120    public void remove() {
1121      checkState(!hasPeeked, "Can't remove after you've peeked at next");
1122      iterator.remove();
1123    }
1124
1125    @Override
1126    public E peek() {
1127      if (!hasPeeked) {
1128        peekedElement = iterator.next();
1129        hasPeeked = true;
1130      }
1131      return peekedElement;
1132    }
1133  }
1134
1135  /**
1136   * Returns a {@code PeekingIterator} backed by the given iterator.
1137   *
1138   * <p>Calls to the {@code peek} method with no intervening calls to {@code
1139   * next} do not affect the iteration, and hence return the same object each
1140   * time. A subsequent call to {@code next} is guaranteed to return the same
1141   * object again. For example: <pre>   {@code
1142   *
1143   *   PeekingIterator<String> peekingIterator =
1144   *       Iterators.peekingIterator(Iterators.forArray("a", "b"));
1145   *   String a1 = peekingIterator.peek(); // returns "a"
1146   *   String a2 = peekingIterator.peek(); // also returns "a"
1147   *   String a3 = peekingIterator.next(); // also returns "a"}</pre>
1148   *
1149   * Any structural changes to the underlying iteration (aside from those
1150   * performed by the iterator's own {@link PeekingIterator#remove()} method)
1151   * will leave the iterator in an undefined state.
1152   *
1153   * <p>The returned iterator does not support removal after peeking, as
1154   * explained by {@link PeekingIterator#remove()}.
1155   *
1156   * <p>Note: If the given iterator is already a {@code PeekingIterator},
1157   * it <i>might</i> be returned to the caller, although this is neither
1158   * guaranteed to occur nor required to be consistent.  For example, this
1159   * method <i>might</i> choose to pass through recognized implementations of
1160   * {@code PeekingIterator} when the behavior of the implementation is
1161   * known to meet the contract guaranteed by this method.
1162   *
1163   * <p>There is no {@link Iterable} equivalent to this method, so use this
1164   * method to wrap each individual iterator as it is generated.
1165   *
1166   * @param iterator the backing iterator. The {@link PeekingIterator} assumes
1167   *     ownership of this iterator, so users should cease making direct calls
1168   *     to it after calling this method.
1169   * @return a peeking iterator backed by that iterator. Apart from the
1170   *     additional {@link PeekingIterator#peek()} method, this iterator behaves
1171   *     exactly the same as {@code iterator}.
1172   */
1173  public static <T> PeekingIterator<T> peekingIterator(
1174      Iterator<? extends T> iterator) {
1175    if (iterator instanceof PeekingImpl) {
1176      // Safe to cast <? extends T> to <T> because PeekingImpl only uses T
1177      // covariantly (and cannot be subclassed to add non-covariant uses).
1178      @SuppressWarnings("unchecked")
1179      PeekingImpl<T> peeking = (PeekingImpl<T>) iterator;
1180      return peeking;
1181    }
1182    return new PeekingImpl<T>(iterator);
1183  }
1184}