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