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