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