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 @GwtIncompatible("Array.newInstance(Class, int)")
315 public static <T> T[] toArray(
316 Iterator<? extends T> iterator, Class<T> type) {
317 List<T> list = Lists.newArrayList(iterator);
318 return Iterables.toArray(list, type);
319 }
320
321 /**
322 * Adds all elements in {@code iterator} to {@code collection}. The iterator
323 * will be left exhausted: its {@code hasNext()} method will return
324 * {@code false}.
325 *
326 * @return {@code true} if {@code collection} was modified as a result of this
327 * operation
328 */
329 public static <T> boolean addAll(
330 Collection<T> addTo, Iterator<? extends T> iterator) {
331 checkNotNull(addTo);
332 boolean wasModified = false;
333 while (iterator.hasNext()) {
334 wasModified |= addTo.add(iterator.next());
335 }
336 return wasModified;
337 }
338
339 /**
340 * Returns the number of elements in the specified iterator that equal the
341 * specified object. The iterator will be left exhausted: its
342 * {@code hasNext()} method will return {@code false}.
343 *
344 * @see Collections#frequency
345 */
346 public static int frequency(Iterator<?> iterator, @Nullable Object element) {
347 int result = 0;
348 if (element == null) {
349 while (iterator.hasNext()) {
350 if (iterator.next() == null) {
351 result++;
352 }
353 }
354 } else {
355 while (iterator.hasNext()) {
356 if (element.equals(iterator.next())) {
357 result++;
358 }
359 }
360 }
361 return result;
362 }
363
364 /**
365 * Returns an iterator that cycles indefinitely over the elements of {@code
366 * iterable}.
367 *
368 * <p>The returned iterator supports {@code remove()} if the provided iterator
369 * does. After {@code remove()} is called, subsequent cycles omit the removed
370 * element, which is no longer in {@code iterable}. The iterator's
371 * {@code hasNext()} method returns {@code true} until {@code iterable} is
372 * empty.
373 *
374 * <p><b>Warning:</b> Typical uses of the resulting iterator may produce an
375 * infinite loop. You should use an explicit {@code break} or be certain that
376 * you will eventually remove all the elements.
377 */
378 public static <T> Iterator<T> cycle(final Iterable<T> iterable) {
379 checkNotNull(iterable);
380 return new Iterator<T>() {
381 Iterator<T> iterator = emptyIterator();
382 Iterator<T> removeFrom;
383
384 public boolean hasNext() {
385 if (!iterator.hasNext()) {
386 iterator = iterable.iterator();
387 }
388 return iterator.hasNext();
389 }
390 public T next() {
391 if (!hasNext()) {
392 throw new NoSuchElementException();
393 }
394 removeFrom = iterator;
395 return iterator.next();
396 }
397 public void remove() {
398 checkState(removeFrom != null,
399 "no calls to next() since last call to remove()");
400 removeFrom.remove();
401 removeFrom = null;
402 }
403 };
404 }
405
406 /**
407 * Returns an iterator that cycles indefinitely over the provided elements.
408 *
409 * <p>The returned iterator supports {@code remove()} if the provided iterator
410 * does. After {@code remove()} is called, subsequent cycles omit the removed
411 * element, but {@code elements} does not change. The iterator's
412 * {@code hasNext()} method returns {@code true} until all of the original
413 * elements have been removed.
414 *
415 * <p><b>Warning:</b> Typical uses of the resulting iterator may produce an
416 * infinite loop. You should use an explicit {@code break} or be certain that
417 * you will eventually remove all the elements.
418 */
419 public static <T> Iterator<T> cycle(T... elements) {
420 return cycle(Lists.newArrayList(elements));
421 }
422
423 /**
424 * Combines two iterators into a single iterator. The returned iterator
425 * iterates across the elements in {@code a}, followed by the elements in
426 * {@code b}. The source iterators are not polled until necessary.
427 *
428 * <p>The returned iterator supports {@code remove()} when the corresponding
429 * input iterator supports it.
430 */
431 @SuppressWarnings("unchecked")
432 public static <T> Iterator<T> concat(Iterator<? extends T> a,
433 Iterator<? extends T> b) {
434 checkNotNull(a);
435 checkNotNull(b);
436 return concat(Arrays.asList(a, b).iterator());
437 }
438
439 /**
440 * Combines three iterators into a single iterator. The returned iterator
441 * iterates across the elements in {@code a}, followed by the elements in
442 * {@code b}, followed by the elements in {@code c}. The source iterators
443 * are not polled until necessary.
444 *
445 * <p>The returned iterator supports {@code remove()} when the corresponding
446 * input iterator supports it.
447 */
448 @SuppressWarnings("unchecked")
449 public static <T> Iterator<T> concat(Iterator<? extends T> a,
450 Iterator<? extends T> b, Iterator<? extends T> c) {
451 checkNotNull(a);
452 checkNotNull(b);
453 checkNotNull(c);
454 return concat(Arrays.asList(a, b, c).iterator());
455 }
456
457 /**
458 * Combines four iterators into a single iterator. The returned iterator
459 * iterates across the elements in {@code a}, followed by the elements in
460 * {@code b}, followed by the elements in {@code c}, followed by the elements
461 * in {@code d}. The source iterators are not polled until necessary.
462 *
463 * <p>The returned iterator supports {@code remove()} when the corresponding
464 * input iterator supports it.
465 */
466 @SuppressWarnings("unchecked")
467 public static <T> Iterator<T> concat(Iterator<? extends T> a,
468 Iterator<? extends T> b, Iterator<? extends T> c,
469 Iterator<? extends T> d) {
470 checkNotNull(a);
471 checkNotNull(b);
472 checkNotNull(c);
473 checkNotNull(d);
474 return concat(Arrays.asList(a, b, c, d).iterator());
475 }
476
477 /**
478 * Combines multiple iterators into a single iterator. The returned iterator
479 * iterates across the elements of each iterator in {@code inputs}. The input
480 * iterators are not polled until necessary.
481 *
482 * <p>The returned iterator supports {@code remove()} when the corresponding
483 * input iterator supports it.
484 *
485 * @throws NullPointerException if any of the provided iterators is null
486 */
487 public static <T> Iterator<T> concat(Iterator<? extends T>... inputs) {
488 return concat(ImmutableList.copyOf(inputs).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. The methods of the returned iterator may throw
498 * {@code NullPointerException} if any of the input iterators are null.
499 */
500 public static <T> Iterator<T> concat(
501 final Iterator<? extends Iterator<? extends T>> inputs) {
502 checkNotNull(inputs);
503 return new Iterator<T>() {
504 Iterator<? extends T> current = emptyIterator();
505 Iterator<? extends T> removeFrom;
506
507 public boolean hasNext() {
508 // http://code.google.com/p/google-collections/issues/detail?id=151
509 // current.hasNext() might be relatively expensive, worth minimizing.
510 boolean currentHasNext;
511 // checkNotNull eager for GWT
512 // note: it must be here & not where 'current' is assigned,
513 // because otherwise we'll have called inputs.next() before throwing
514 // the first NPE, and the next time around we'll call inputs.next()
515 // again, incorrectly moving beyond the error.
516 while (!(currentHasNext = checkNotNull(current).hasNext())
517 && inputs.hasNext()) {
518 current = inputs.next();
519 }
520 return currentHasNext;
521 }
522 public T next() {
523 if (!hasNext()) {
524 throw new NoSuchElementException();
525 }
526 removeFrom = current;
527 return current.next();
528 }
529 public void remove() {
530 checkState(removeFrom != null,
531 "no calls to next() since last call to remove()");
532 removeFrom.remove();
533 removeFrom = null;
534 }
535 };
536 }
537
538 /**
539 * Divides an iterator into unmodifiable sublists of the given size (the final
540 * list may be smaller). For example, partitioning an iterator containing
541 * {@code [a, b, c, d, e]} with a partition size of 3 yields {@code
542 * [[a, b, c], [d, e]]} -- an outer iterator containing two inner lists of
543 * three and two elements, all in the original order.
544 *
545 * <p>The returned lists implement {@link java.util.RandomAccess}.
546 *
547 * @param iterator the iterator to return a partitioned view of
548 * @param size the desired size of each partition (the last may be smaller)
549 * @return an iterator of immutable lists containing the elements of {@code
550 * iterator} divided into partitions
551 * @throws IllegalArgumentException if {@code size} is nonpositive
552 */
553 public static <T> UnmodifiableIterator<List<T>> partition(
554 Iterator<T> iterator, int size) {
555 return partitionImpl(iterator, size, false);
556 }
557
558 /**
559 * Divides an iterator into unmodifiable sublists of the given size, padding
560 * the final iterator with null values if necessary. For example, partitioning
561 * an iterator containing {@code [a, b, c, d, e]} with a partition size of 3
562 * yields {@code [[a, b, c], [d, e, null]]} -- an outer iterator containing
563 * two inner lists of three elements each, all in the original order.
564 *
565 * <p>The returned lists implement {@link java.util.RandomAccess}.
566 *
567 * @param iterator the iterator to return a partitioned view of
568 * @param size the desired size of each partition
569 * @return an iterator of immutable lists containing the elements of {@code
570 * iterator} divided into partitions (the final iterable may have
571 * trailing null elements)
572 * @throws IllegalArgumentException if {@code size} is nonpositive
573 */
574 public static <T> UnmodifiableIterator<List<T>> paddedPartition(
575 Iterator<T> iterator, int size) {
576 return partitionImpl(iterator, size, true);
577 }
578
579 private static <T> UnmodifiableIterator<List<T>> partitionImpl(
580 final Iterator<T> iterator, final int size, final boolean pad) {
581 checkNotNull(iterator);
582 checkArgument(size > 0);
583 return new UnmodifiableIterator<List<T>>() {
584 public boolean hasNext() {
585 return iterator.hasNext();
586 }
587 public List<T> next() {
588 if (!hasNext()) {
589 throw new NoSuchElementException();
590 }
591 Object[] array = new Object[size];
592 int count = 0;
593 for (; count < size && iterator.hasNext(); count++) {
594 array[count] = iterator.next();
595 }
596
597 @SuppressWarnings("unchecked") // we only put Ts in it
598 List<T> list = Collections.unmodifiableList(
599 (List<T>) Arrays.asList(array));
600 return (pad || count == size) ? list : list.subList(0, count);
601 }
602 };
603 }
604
605 /**
606 * Returns the elements of {@code unfiltered} that satisfy a predicate.
607 */
608 public static <T> UnmodifiableIterator<T> filter(
609 final Iterator<T> unfiltered, final Predicate<? super T> predicate) {
610 checkNotNull(unfiltered);
611 checkNotNull(predicate);
612 return new AbstractIterator<T>() {
613 @Override protected T computeNext() {
614 while (unfiltered.hasNext()) {
615 T element = unfiltered.next();
616 if (predicate.apply(element)) {
617 return element;
618 }
619 }
620 return endOfData();
621 }
622 };
623 }
624
625 /**
626 * Returns all instances of class {@code type} in {@code unfiltered}. The
627 * returned iterator has elements whose class is {@code type} or a subclass of
628 * {@code type}.
629 *
630 * @param unfiltered an iterator containing objects of any type
631 * @param type the type of elements desired
632 * @return an unmodifiable iterator containing all elements of the original
633 * iterator that were of the requested type
634 */
635 @SuppressWarnings("unchecked") // can cast to <T> because non-Ts are removed
636 @GwtIncompatible("Class.isInstance")
637 public static <T> UnmodifiableIterator<T> filter(
638 Iterator<?> unfiltered, Class<T> type) {
639 return (UnmodifiableIterator<T>)
640 filter(unfiltered, Predicates.instanceOf(type));
641 }
642
643 /**
644 * Returns {@code true} if one or more elements returned by {@code iterator}
645 * satisfy the given predicate.
646 */
647 public static <T> boolean any(
648 Iterator<T> iterator, Predicate<? super T> predicate) {
649 checkNotNull(predicate);
650 while (iterator.hasNext()) {
651 T element = iterator.next();
652 if (predicate.apply(element)) {
653 return true;
654 }
655 }
656 return false;
657 }
658
659 /**
660 * Returns {@code true} if every element returned by {@code iterator}
661 * satisfies the given predicate. If {@code iterator} is empty, {@code true}
662 * is returned.
663 */
664 public static <T> boolean all(
665 Iterator<T> iterator, Predicate<? super T> predicate) {
666 checkNotNull(predicate);
667 while (iterator.hasNext()) {
668 T element = iterator.next();
669 if (!predicate.apply(element)) {
670 return false;
671 }
672 }
673 return true;
674 }
675
676 /**
677 * Returns the first element in {@code iterator} that satisfies the given
678 * predicate. If no such element is found, the iterator will be left
679 * exhausted: its {@code hasNext()} method will return {@code false}.
680 *
681 * @throws NoSuchElementException if no element in {@code iterator} matches
682 * the given predicate
683 */
684 public static <T> T find(
685 Iterator<T> iterator, Predicate<? super T> predicate) {
686 return filter(iterator, predicate).next();
687 }
688
689 /**
690 * Returns the first element in {@code iterator} that satisfies the given
691 * predicate. If no such element is found, {@code defaultValue} will be
692 * returned from this method and the iterator will be left exhausted: its
693 * {@code hasNext()} method will return {@code false}.
694 *
695 * @since 7
696 */
697 public static <T> T find(Iterator<T> iterator, Predicate<? super T> predicate,
698 @Nullable T defaultValue) {
699 UnmodifiableIterator<T> filteredIterator = filter(iterator, predicate);
700 return filteredIterator.hasNext() ? filteredIterator.next() : defaultValue;
701 }
702
703 /**
704 * Returns the index in {@code iterator} of the first element that satisfies
705 * the provided {@code predicate}, or {@code -1} if the Iterator has no such
706 * elements.
707 *
708 * <p>More formally, returns the lowest index {@code i} such that
709 * {@code predicate.apply(Iterators.get(iterator, i))} is {@code true}, or
710 * {@code -1} if there is no such index.
711 *
712 * <p>If -1 is returned, the iterator will be left exhausted: its
713 * {@code hasNext()} method will return {@code false}. Otherwise,
714 * the iterator will be set to the element which satisfies the
715 * {@code predicate}.
716 *
717 * @since 2
718 */
719 public static <T> int indexOf(
720 Iterator<T> iterator, Predicate<? super T> predicate) {
721 checkNotNull(predicate, "predicate");
722 int i = 0;
723 while (iterator.hasNext()) {
724 T current = iterator.next();
725 if (predicate.apply(current)) {
726 return i;
727 }
728 i++;
729 }
730 return -1;
731 }
732
733 /**
734 * Returns an iterator that applies {@code function} to each element of {@code
735 * fromIterator}.
736 *
737 * <p>The returned iterator supports {@code remove()} if the provided iterator
738 * does. After a successful {@code remove()} call, {@code fromIterator} no
739 * longer contains the corresponding element.
740 */
741 public static <F, T> Iterator<T> transform(final Iterator<F> fromIterator,
742 final Function<? super F, ? extends T> function) {
743 checkNotNull(fromIterator);
744 checkNotNull(function);
745 return new Iterator<T>() {
746 public boolean hasNext() {
747 return fromIterator.hasNext();
748 }
749 public T next() {
750 F from = fromIterator.next();
751 return function.apply(from);
752 }
753 public void remove() {
754 fromIterator.remove();
755 }
756 };
757 }
758
759 /**
760 * Advances {@code iterator} {@code position + 1} times, returning the
761 * element at the {@code position}th position.
762 *
763 * @param position position of the element to return
764 * @return the element at the specified position in {@code iterator}
765 * @throws IndexOutOfBoundsException if {@code position} is negative or
766 * greater than or equal to the number of elements remaining in
767 * {@code iterator}
768 */
769 public static <T> T get(Iterator<T> iterator, int position) {
770 checkNonnegative(position);
771
772 int skipped = 0;
773 while (iterator.hasNext()) {
774 T t = iterator.next();
775 if (skipped++ == position) {
776 return t;
777 }
778 }
779
780 throw new IndexOutOfBoundsException("position (" + position
781 + ") must be less than the number of elements that remained ("
782 + skipped + ")");
783 }
784
785 private static void checkNonnegative(int position) {
786 if (position < 0) {
787 throw new IndexOutOfBoundsException("position (" + position
788 + ") must not be negative");
789 }
790 }
791
792 /**
793 * Advances {@code iterator} {@code position + 1} times, returning the
794 * element at the {@code position}th position or {@code defaultValue}
795 * otherwise.
796 *
797 * @param position position of the element to return
798 * @param defaultValue the default value to return if the iterator is empty
799 * or if {@code position} is greater than the number of elements
800 * remaining in {@code iterator}
801 * @return the element at the specified position in {@code iterator} or
802 * {@code defaultValue} if {@code iterator} produces fewer than
803 * {@code position + 1} elements.
804 * @throws IndexOutOfBoundsException if {@code position} is negative
805 * @since 4
806 */
807 public static <T> T get(Iterator<T> iterator, int position,
808 @Nullable T defaultValue) {
809 checkNonnegative(position);
810
811 try {
812 return get(iterator, position);
813 } catch (IndexOutOfBoundsException e) {
814 return defaultValue;
815 }
816 }
817
818 /**
819 * Returns the next element in {@code iterator} or {@code defaultValue} if
820 * the iterator is empty. The {@link Iterables} analog to this method is
821 * {@link Iterables#getFirst}.
822 *
823 * @param defaultValue the default value to return if the iterator is empty
824 * @return the next element of {@code iterator} or the default value
825 * @since 7
826 */
827 public static <T> T getNext(Iterator<T> iterator, @Nullable T defaultValue) {
828 return iterator.hasNext() ? iterator.next() : defaultValue;
829 }
830
831 /**
832 * Advances {@code iterator} to the end, returning the last element.
833 *
834 * @return the last element of {@code iterator}
835 * @throws NoSuchElementException if the iterator is empty
836 */
837 public static <T> T getLast(Iterator<T> iterator) {
838 while (true) {
839 T current = iterator.next();
840 if (!iterator.hasNext()) {
841 return current;
842 }
843 }
844 }
845
846 /**
847 * Advances {@code iterator} to the end, returning the last element or
848 * {@code defaultValue} if the iterator is empty.
849 *
850 * @param defaultValue the default value to return if the iterator is empty
851 * @return the last element of {@code iterator}
852 * @since 3
853 */
854 public static <T> T getLast(Iterator<T> iterator, @Nullable T defaultValue) {
855 return iterator.hasNext() ? getLast(iterator) : defaultValue;
856 }
857
858 /**
859 * Calls {@code next()} on {@code iterator}, either {@code numberToSkip} times
860 * or until {@code hasNext()} returns {@code false}, whichever comes first.
861 *
862 * @return the number of elements skipped
863 * @since 3
864 */
865 @Beta // naming issue, unclear user demand
866 public static <T> int skip(Iterator<T> iterator, int numberToSkip) {
867 checkNotNull(iterator);
868 checkArgument(numberToSkip >= 0, "number to skip cannot be negative");
869
870 int i;
871 for (i = 0; i < numberToSkip && iterator.hasNext(); i++) {
872 iterator.next();
873 }
874 return i;
875 }
876
877 /**
878 * Creates an iterator returning the first {@code limitSize} elements of the
879 * given iterator. If the original iterator does not contain that many
880 * elements, the returned iterator will have the same behavior as the original
881 * iterator. The returned iterator supports {@code remove()} if the original
882 * iterator does.
883 *
884 * @param iterator the iterator to limit
885 * @param limitSize the maximum number of elements in the returned iterator
886 * @throws IllegalArgumentException if {@code limitSize} is negative
887 * @since 3
888 */
889 @Beta // naming issue
890 public static <T> Iterator<T> limit(
891 final Iterator<T> iterator, final int limitSize) {
892 checkNotNull(iterator);
893 checkArgument(limitSize >= 0, "limit is negative");
894 return new Iterator<T>() {
895 private int count;
896
897 public boolean hasNext() {
898 return count < limitSize && iterator.hasNext();
899 }
900
901 public T next() {
902 if (!hasNext()) {
903 throw new NoSuchElementException();
904 }
905 count++;
906 return iterator.next();
907 }
908
909 public void remove() {
910 iterator.remove();
911 }
912 };
913 }
914
915 /**
916 * Returns a view of the supplied {@code iterator} that removes each element
917 * from the supplied {@code iterator} as it is returned.
918 *
919 * <p>The provided iterator must support {@link Iterator#remove()} or
920 * else the returned iterator will fail on the first call to {@code
921 * next}.
922 *
923 * @param iterator the iterator to remove and return elements from
924 * @return an iterator that removes and returns elements from the
925 * supplied iterator
926 * @since 2
927 */
928 @Beta
929 public static <T> Iterator<T> consumingIterator(final Iterator<T> iterator) {
930 checkNotNull(iterator);
931 return new UnmodifiableIterator<T>() {
932 public boolean hasNext() {
933 return iterator.hasNext();
934 }
935
936 public T next() {
937 T next = iterator.next();
938 iterator.remove();
939 return next;
940 }
941 };
942 }
943
944 // Methods only in Iterators, not in Iterables
945
946 /**
947 * Returns an iterator containing the elements of {@code array} in order. The
948 * returned iterator is a view of the array; subsequent changes to the array
949 * will be reflected in the iterator.
950 *
951 * <p><b>Note:</b> It is often preferable to represent your data using a
952 * collection type, for example using {@link Arrays#asList(Object[])}, making
953 * this method unnecessary.
954 *
955 * <p>The {@code Iterable} equivalent of this method is either {@link
956 * Arrays#asList(Object[])}, {@link ImmutableList#copyOf(Object[])}},
957 * or {@link ImmutableList#of}.
958 */
959 public static <T> UnmodifiableIterator<T> forArray(final T... array) {
960 // TODO(kevinb): compare performance with Arrays.asList(array).iterator().
961 checkNotNull(array); // eager for GWT.
962 return new AbstractIndexedListIterator<T>(array.length) {
963 @Override protected T get(int index) {
964 return array[index];
965 }
966 };
967 }
968
969 /**
970 * Returns an iterator containing the elements in the specified range of
971 * {@code array} in order. The returned iterator is a view of the array;
972 * subsequent changes to the array will be reflected in the iterator.
973 *
974 * <p>The {@code Iterable} equivalent of this method is {@code
975 * Arrays.asList(array).subList(offset, offset + length)}.
976 *
977 * @param array array to read elements out of
978 * @param offset index of first array element to retrieve
979 * @param length number of elements in iteration
980 * @throws IndexOutOfBoundsException if {@code offset} is negative, {@code
981 * length} is negative, or {@code offset + length > array.length}
982 */
983 static <T> UnmodifiableIterator<T> forArray(
984 final T[] array, final int offset, int length) {
985 checkArgument(length >= 0);
986 int end = offset + length;
987
988 // Technically we should give a slightly more descriptive error on overflow
989 Preconditions.checkPositionIndexes(offset, end, array.length);
990
991 /*
992 * We can't use call the two-arg constructor with arguments (offset, end)
993 * because the returned Iterator is a ListIterator that may be moved back
994 * past the beginning of the iteration.
995 */
996 return new AbstractIndexedListIterator<T>(length) {
997 @Override protected T get(int index) {
998 return array[offset + index];
999 }
1000 };
1001 }
1002
1003 /**
1004 * Returns an iterator containing only {@code value}.
1005 *
1006 * <p>The {@link Iterable} equivalent of this method is {@link
1007 * Collections#singleton}.
1008 */
1009 public static <T> UnmodifiableIterator<T> singletonIterator(
1010 @Nullable final T value) {
1011 return new UnmodifiableIterator<T>() {
1012 boolean done;
1013 public boolean hasNext() {
1014 return !done;
1015 }
1016 public T next() {
1017 if (done) {
1018 throw new NoSuchElementException();
1019 }
1020 done = true;
1021 return value;
1022 }
1023 };
1024 }
1025
1026 /**
1027 * Adapts an {@code Enumeration} to the {@code Iterator} interface.
1028 *
1029 * <p>This method has no equivalent in {@link Iterables} because viewing an
1030 * {@code Enumeration} as an {@code Iterable} is impossible. However, the
1031 * contents can be <i>copied</i> into a collection using {@link
1032 * Collections#list}.
1033 */
1034 public static <T> UnmodifiableIterator<T> forEnumeration(
1035 final Enumeration<T> enumeration) {
1036 checkNotNull(enumeration);
1037 return new UnmodifiableIterator<T>() {
1038 public boolean hasNext() {
1039 return enumeration.hasMoreElements();
1040 }
1041 public T next() {
1042 return enumeration.nextElement();
1043 }
1044 };
1045 }
1046
1047 /**
1048 * Adapts an {@code Iterator} to the {@code Enumeration} interface.
1049 *
1050 * <p>The {@code Iterable} equivalent of this method is either {@link
1051 * Collections#enumeration} (if you have a {@link Collection}), or
1052 * {@code Iterators.asEnumeration(collection.iterator())}.
1053 */
1054 public static <T> Enumeration<T> asEnumeration(final Iterator<T> iterator) {
1055 checkNotNull(iterator);
1056 return new Enumeration<T>() {
1057 public boolean hasMoreElements() {
1058 return iterator.hasNext();
1059 }
1060 public T nextElement() {
1061 return iterator.next();
1062 }
1063 };
1064 }
1065
1066 /**
1067 * Implementation of PeekingIterator that avoids peeking unless necessary.
1068 */
1069 private static class PeekingImpl<E> implements PeekingIterator<E> {
1070
1071 private final Iterator<? extends E> iterator;
1072 private boolean hasPeeked;
1073 private E peekedElement;
1074
1075 public PeekingImpl(Iterator<? extends E> iterator) {
1076 this.iterator = checkNotNull(iterator);
1077 }
1078
1079 public boolean hasNext() {
1080 return hasPeeked || iterator.hasNext();
1081 }
1082
1083 public E next() {
1084 if (!hasPeeked) {
1085 return iterator.next();
1086 }
1087 E result = peekedElement;
1088 hasPeeked = false;
1089 peekedElement = null;
1090 return result;
1091 }
1092
1093 public void remove() {
1094 checkState(!hasPeeked, "Can't remove after you've peeked at next");
1095 iterator.remove();
1096 }
1097
1098 public E peek() {
1099 if (!hasPeeked) {
1100 peekedElement = iterator.next();
1101 hasPeeked = true;
1102 }
1103 return peekedElement;
1104 }
1105 }
1106
1107 /**
1108 * Returns a {@code PeekingIterator} backed by the given iterator.
1109 *
1110 * <p>Calls to the {@code peek} method with no intervening calls to {@code
1111 * next} do not affect the iteration, and hence return the same object each
1112 * time. A subsequent call to {@code next} is guaranteed to return the same
1113 * object again. For example: <pre> {@code
1114 *
1115 * PeekingIterator<String> peekingIterator =
1116 * Iterators.peekingIterator(Iterators.forArray("a", "b"));
1117 * String a1 = peekingIterator.peek(); // returns "a"
1118 * String a2 = peekingIterator.peek(); // also returns "a"
1119 * String a3 = peekingIterator.next(); // also returns "a"}</pre>
1120 *
1121 * Any structural changes to the underlying iteration (aside from those
1122 * performed by the iterator's own {@link PeekingIterator#remove()} method)
1123 * will leave the iterator in an undefined state.
1124 *
1125 * <p>The returned iterator does not support removal after peeking, as
1126 * explained by {@link PeekingIterator#remove()}.
1127 *
1128 * <p>Note: If the given iterator is already a {@code PeekingIterator},
1129 * it <i>might</i> be returned to the caller, although this is neither
1130 * guaranteed to occur nor required to be consistent. For example, this
1131 * method <i>might</i> choose to pass through recognized implementations of
1132 * {@code PeekingIterator} when the behavior of the implementation is
1133 * known to meet the contract guaranteed by this method.
1134 *
1135 * <p>There is no {@link Iterable} equivalent to this method, so use this
1136 * method to wrap each individual iterator as it is generated.
1137 *
1138 * @param iterator the backing iterator. The {@link PeekingIterator} assumes
1139 * ownership of this iterator, so users should cease making direct calls
1140 * to it after calling this method.
1141 * @return a peeking iterator backed by that iterator. Apart from the
1142 * additional {@link PeekingIterator#peek()} method, this iterator behaves
1143 * exactly the same as {@code iterator}.
1144 */
1145 public static <T> PeekingIterator<T> peekingIterator(
1146 Iterator<? extends T> iterator) {
1147 if (iterator instanceof PeekingImpl) {
1148 // Safe to cast <? extends T> to <T> because PeekingImpl only uses T
1149 // covariantly (and cannot be subclassed to add non-covariant uses).
1150 @SuppressWarnings("unchecked")
1151 PeekingImpl<T> peeking = (PeekingImpl<T>) iterator;
1152 return peeking;
1153 }
1154 return new PeekingImpl<T>(iterator);
1155 }
1156 }