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