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