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