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