1/* 2 * Copyright (C) 2007 The Guava Authors 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 17package com.google.common.collect; 18 19import static com.google.common.base.Preconditions.checkArgument; 20import static com.google.common.base.Preconditions.checkNotNull; 21 22import com.google.common.annotations.Beta; 23import com.google.common.annotations.GwtCompatible; 24import com.google.common.base.Function; 25import com.google.common.base.Objects; 26import com.google.common.base.Optional; 27import com.google.common.base.Preconditions; 28import com.google.common.base.Predicate; 29 30import java.util.Arrays; 31import java.util.Collection; 32import java.util.Comparator; 33import java.util.Iterator; 34import java.util.List; 35import java.util.NoSuchElementException; 36import java.util.Queue; 37import java.util.RandomAccess; 38import java.util.Set; 39import java.util.SortedSet; 40 41import javax.annotation.Nullable; 42 43/** 44 * This class contains static utility methods that operate on or return objects 45 * of type {@code Iterable}. Except as noted, each method has a corresponding 46 * {@link Iterator}-based method in the {@link Iterators} class. 47 * 48 * <p><i>Performance notes:</i> Unless otherwise noted, all of the iterables 49 * produced in this class are <i>lazy</i>, which means that their iterators 50 * only advance the backing iteration when absolutely necessary. 51 * 52 * @author Kevin Bourrillion 53 * @author Jared Levy 54 * @since 2.0 (imported from Google Collections Library) 55 */ 56@GwtCompatible(emulated = true) 57public final class Iterables { 58 private Iterables() {} 59 60 /** Returns an unmodifiable view of {@code iterable}. */ 61 public static <T> Iterable<T> unmodifiableIterable( 62 final Iterable<T> iterable) { 63 checkNotNull(iterable); 64 if (iterable instanceof UnmodifiableIterable || 65 iterable instanceof ImmutableCollection) { 66 return iterable; 67 } 68 return new UnmodifiableIterable<T>(iterable); 69 } 70 71 /** 72 * Simply returns its argument. 73 * 74 * @deprecated no need to use this 75 * @since 10.0 76 */ 77 @Deprecated public static <E> Iterable<E> unmodifiableIterable( 78 ImmutableCollection<E> iterable) { 79 return checkNotNull(iterable); 80 } 81 82 private static final class UnmodifiableIterable<T> implements Iterable<T> { 83 private final Iterable<T> iterable; 84 85 private UnmodifiableIterable(Iterable<T> iterable) { 86 this.iterable = iterable; 87 } 88 89 @Override 90 public Iterator<T> iterator() { 91 return Iterators.unmodifiableIterator(iterable.iterator()); 92 } 93 94 @Override 95 public String toString() { 96 return iterable.toString(); 97 } 98 // no equals and hashCode; it would break the contract! 99 } 100 101 /** 102 * Returns the number of elements in {@code iterable}. 103 */ 104 public static int size(Iterable<?> iterable) { 105 return (iterable instanceof Collection) 106 ? ((Collection<?>) iterable).size() 107 : Iterators.size(iterable.iterator()); 108 } 109 110 /** 111 * Returns {@code true} if {@code iterable} contains {@code element}; that is, 112 * any object for which {@code equals(element)} is true. 113 */ 114 public static boolean contains(Iterable<?> iterable, @Nullable Object element) 115 { 116 if (iterable instanceof Collection) { 117 Collection<?> collection = (Collection<?>) iterable; 118 try { 119 return collection.contains(element); 120 } catch (NullPointerException e) { 121 return false; 122 } catch (ClassCastException e) { 123 return false; 124 } 125 } 126 return Iterators.contains(iterable.iterator(), element); 127 } 128 129 /** 130 * Removes, from an iterable, every element that belongs to the provided 131 * collection. 132 * 133 * <p>This method calls {@link Collection#removeAll} if {@code iterable} is a 134 * collection, and {@link Iterators#removeAll} otherwise. 135 * 136 * @param removeFrom the iterable to (potentially) remove elements from 137 * @param elementsToRemove the elements to remove 138 * @return {@code true} if any element was removed from {@code iterable} 139 */ 140 public static boolean removeAll( 141 Iterable<?> removeFrom, Collection<?> elementsToRemove) { 142 return (removeFrom instanceof Collection) 143 ? ((Collection<?>) removeFrom).removeAll(checkNotNull(elementsToRemove)) 144 : Iterators.removeAll(removeFrom.iterator(), elementsToRemove); 145 } 146 147 /** 148 * Removes, from an iterable, every element that does not belong to the 149 * provided collection. 150 * 151 * <p>This method calls {@link Collection#retainAll} if {@code iterable} is a 152 * collection, and {@link Iterators#retainAll} otherwise. 153 * 154 * @param removeFrom the iterable to (potentially) remove elements from 155 * @param elementsToRetain the elements to retain 156 * @return {@code true} if any element was removed from {@code iterable} 157 */ 158 public static boolean retainAll( 159 Iterable<?> removeFrom, Collection<?> elementsToRetain) { 160 return (removeFrom instanceof Collection) 161 ? ((Collection<?>) removeFrom).retainAll(checkNotNull(elementsToRetain)) 162 : Iterators.retainAll(removeFrom.iterator(), elementsToRetain); 163 } 164 165 /** 166 * Removes, from an iterable, every element that satisfies the provided 167 * predicate. 168 * 169 * @param removeFrom the iterable to (potentially) remove elements from 170 * @param predicate a predicate that determines whether an element should 171 * be removed 172 * @return {@code true} if any elements were removed from the iterable 173 * 174 * @throws UnsupportedOperationException if the iterable does not support 175 * {@code remove()}. 176 * @since 2.0 177 */ 178 public static <T> boolean removeIf( 179 Iterable<T> removeFrom, Predicate<? super T> predicate) { 180 if (removeFrom instanceof RandomAccess && removeFrom instanceof List) { 181 return removeIfFromRandomAccessList( 182 (List<T>) removeFrom, checkNotNull(predicate)); 183 } 184 return Iterators.removeIf(removeFrom.iterator(), predicate); 185 } 186 187 private static <T> boolean removeIfFromRandomAccessList( 188 List<T> list, Predicate<? super T> predicate) { 189 // Note: Not all random access lists support set() so we need to deal with 190 // those that don't and attempt the slower remove() based solution. 191 int from = 0; 192 int to = 0; 193 194 for (; from < list.size(); from++) { 195 T element = list.get(from); 196 if (!predicate.apply(element)) { 197 if (from > to) { 198 try { 199 list.set(to, element); 200 } catch (UnsupportedOperationException e) { 201 slowRemoveIfForRemainingElements(list, predicate, to, from); 202 return true; 203 } 204 } 205 to++; 206 } 207 } 208 209 // Clear the tail of any remaining items 210 list.subList(to, list.size()).clear(); 211 return from != to; 212 } 213 214 private static <T> void slowRemoveIfForRemainingElements(List<T> list, 215 Predicate<? super T> predicate, int to, int from) { 216 // Here we know that: 217 // * (to < from) and that both are valid indices. 218 // * Everything with (index < to) should be kept. 219 // * Everything with (to <= index < from) should be removed. 220 // * The element with (index == from) should be kept. 221 // * Everything with (index > from) has not been checked yet. 222 223 // Check from the end of the list backwards (minimize expected cost of 224 // moving elements when remove() is called). Stop before 'from' because 225 // we already know that should be kept. 226 for (int n = list.size() - 1; n > from; n--) { 227 if (predicate.apply(list.get(n))) { 228 list.remove(n); 229 } 230 } 231 // And now remove everything in the range [to, from) (going backwards). 232 for (int n = from - 1; n >= to; n--) { 233 list.remove(n); 234 } 235 } 236 237 /** 238 * Determines whether two iterables contain equal elements in the same order. 239 * More specifically, this method returns {@code true} if {@code iterable1} 240 * and {@code iterable2} contain the same number of elements and every element 241 * of {@code iterable1} is equal to the corresponding element of 242 * {@code iterable2}. 243 */ 244 public static boolean elementsEqual( 245 Iterable<?> iterable1, Iterable<?> iterable2) { 246 return Iterators.elementsEqual(iterable1.iterator(), iterable2.iterator()); 247 } 248 249 /** 250 * Returns a string representation of {@code iterable}, with the format 251 * {@code [e1, e2, ..., en]}. 252 */ 253 public static String toString(Iterable<?> iterable) { 254 return Iterators.toString(iterable.iterator()); 255 } 256 257 /** 258 * Returns the single element contained in {@code iterable}. 259 * 260 * @throws NoSuchElementException if the iterable is empty 261 * @throws IllegalArgumentException if the iterable contains multiple 262 * elements 263 */ 264 public static <T> T getOnlyElement(Iterable<T> iterable) { 265 return Iterators.getOnlyElement(iterable.iterator()); 266 } 267 268 /** 269 * Returns the single element contained in {@code iterable}, or {@code 270 * defaultValue} if the iterable is empty. 271 * 272 * @throws IllegalArgumentException if the iterator contains multiple 273 * elements 274 */ 275 public static <T> T getOnlyElement( 276 Iterable<T> iterable, @Nullable T defaultValue) { 277 return Iterators.getOnlyElement(iterable.iterator(), defaultValue); 278 } 279 280 /** 281 * Copies an iterable's elements into an array. 282 * 283 * @param iterable the iterable to copy 284 * @return a newly-allocated array into which all the elements of the iterable 285 * have been copied 286 */ 287 static Object[] toArray(Iterable<?> iterable) { 288 return toCollection(iterable).toArray(); 289 } 290 291 /** 292 * Converts an iterable into a collection. If the iterable is already a 293 * collection, it is returned. Otherwise, an {@link java.util.ArrayList} is 294 * created with the contents of the iterable in the same iteration order. 295 */ 296 private static <E> Collection<E> toCollection(Iterable<E> iterable) { 297 return (iterable instanceof Collection) 298 ? (Collection<E>) iterable 299 : Lists.newArrayList(iterable.iterator()); 300 } 301 302 /** 303 * Adds all elements in {@code iterable} to {@code collection}. 304 * 305 * @return {@code true} if {@code collection} was modified as a result of this 306 * operation. 307 */ 308 public static <T> boolean addAll( 309 Collection<T> addTo, Iterable<? extends T> elementsToAdd) { 310 if (elementsToAdd instanceof Collection) { 311 Collection<? extends T> c = Collections2.cast(elementsToAdd); 312 return addTo.addAll(c); 313 } 314 return Iterators.addAll(addTo, elementsToAdd.iterator()); 315 } 316 317 /** 318 * Returns the number of elements in the specified iterable that equal the 319 * specified object. This implementation avoids a full iteration when the 320 * iterable is a {@link Multiset} or {@link Set}. 321 * 322 * @see Collections#frequency 323 */ 324 public static int frequency(Iterable<?> iterable, @Nullable Object element) { 325 if ((iterable instanceof Multiset)) { 326 return ((Multiset<?>) iterable).count(element); 327 } 328 if ((iterable instanceof Set)) { 329 return ((Set<?>) iterable).contains(element) ? 1 : 0; 330 } 331 return Iterators.frequency(iterable.iterator(), element); 332 } 333 334 /** 335 * Returns an iterable whose iterators cycle indefinitely over the elements of 336 * {@code iterable}. 337 * 338 * <p>That iterator supports {@code remove()} if {@code iterable.iterator()} 339 * does. After {@code remove()} is called, subsequent cycles omit the removed 340 * element, which is no longer in {@code iterable}. The iterator's 341 * {@code hasNext()} method returns {@code true} until {@code iterable} is 342 * empty. 343 * 344 * <p><b>Warning:</b> Typical uses of the resulting iterator may produce an 345 * infinite loop. You should use an explicit {@code break} or be certain that 346 * you will eventually remove all the elements. 347 * 348 * <p>To cycle over the iterable {@code n} times, use the following: 349 * {@code Iterables.concat(Collections.nCopies(n, iterable))} 350 */ 351 public static <T> Iterable<T> cycle(final Iterable<T> iterable) { 352 checkNotNull(iterable); 353 return new Iterable<T>() { 354 @Override 355 public Iterator<T> iterator() { 356 return Iterators.cycle(iterable); 357 } 358 @Override public String toString() { 359 return iterable.toString() + " (cycled)"; 360 } 361 }; 362 } 363 364 /** 365 * Returns an iterable whose iterators cycle indefinitely over the provided 366 * elements. 367 * 368 * <p>After {@code remove} is invoked on a generated iterator, the removed 369 * element will no longer appear in either that iterator or any other iterator 370 * created from the same source iterable. That is, this method behaves exactly 371 * as {@code Iterables.cycle(Lists.newArrayList(elements))}. The iterator's 372 * {@code hasNext} method returns {@code true} until all of the original 373 * elements have been removed. 374 * 375 * <p><b>Warning:</b> Typical uses of the resulting iterator may produce an 376 * infinite loop. You should use an explicit {@code break} or be certain that 377 * you will eventually remove all the elements. 378 * 379 * <p>To cycle over the elements {@code n} times, use the following: 380 * {@code Iterables.concat(Collections.nCopies(n, Arrays.asList(elements)))} 381 */ 382 public static <T> Iterable<T> cycle(T... elements) { 383 return cycle(Lists.newArrayList(elements)); 384 } 385 386 /** 387 * Combines two iterables into a single iterable. The returned iterable has an 388 * iterator that traverses the elements in {@code a}, followed by the elements 389 * in {@code b}. The source iterators are not polled until necessary. 390 * 391 * <p>The returned iterable's iterator supports {@code remove()} when the 392 * corresponding input iterator supports it. 393 */ 394 @SuppressWarnings("unchecked") 395 public static <T> Iterable<T> concat( 396 Iterable<? extends T> a, Iterable<? extends T> b) { 397 checkNotNull(a); 398 checkNotNull(b); 399 return concat(Arrays.asList(a, b)); 400 } 401 402 /** 403 * Combines three iterables into a single iterable. The returned iterable has 404 * an iterator that traverses the elements in {@code a}, followed by the 405 * elements in {@code b}, followed by the elements in {@code c}. The source 406 * iterators are not polled until necessary. 407 * 408 * <p>The returned iterable's iterator supports {@code remove()} when the 409 * corresponding input iterator supports it. 410 */ 411 @SuppressWarnings("unchecked") 412 public static <T> Iterable<T> concat(Iterable<? extends T> a, 413 Iterable<? extends T> b, Iterable<? extends T> c) { 414 checkNotNull(a); 415 checkNotNull(b); 416 checkNotNull(c); 417 return concat(Arrays.asList(a, b, c)); 418 } 419 420 /** 421 * Combines four iterables into a single iterable. The returned iterable has 422 * an iterator that traverses the elements in {@code a}, followed by the 423 * elements in {@code b}, followed by the elements in {@code c}, followed by 424 * the elements in {@code d}. The source iterators are not polled until 425 * necessary. 426 * 427 * <p>The returned iterable's iterator supports {@code remove()} when the 428 * corresponding input iterator supports it. 429 */ 430 @SuppressWarnings("unchecked") 431 public static <T> Iterable<T> concat(Iterable<? extends T> a, 432 Iterable<? extends T> b, Iterable<? extends T> c, 433 Iterable<? extends T> d) { 434 checkNotNull(a); 435 checkNotNull(b); 436 checkNotNull(c); 437 checkNotNull(d); 438 return concat(Arrays.asList(a, b, c, d)); 439 } 440 441 /** 442 * Combines multiple iterables into a single iterable. The returned iterable 443 * has an iterator that traverses the elements of each iterable in 444 * {@code inputs}. The input iterators are not polled until necessary. 445 * 446 * <p>The returned iterable's iterator supports {@code remove()} when the 447 * corresponding input iterator supports it. 448 * 449 * @throws NullPointerException if any of the provided iterables is null 450 */ 451 public static <T> Iterable<T> concat(Iterable<? extends T>... inputs) { 452 return concat(ImmutableList.copyOf(inputs)); 453 } 454 455 /** 456 * Combines multiple iterables into a single iterable. The returned iterable 457 * has an iterator that traverses the elements of each iterable in 458 * {@code inputs}. The input iterators are not polled until necessary. 459 * 460 * <p>The returned iterable's iterator supports {@code remove()} when the 461 * corresponding input iterator supports it. The methods of the returned 462 * iterable may throw {@code NullPointerException} if any of the input 463 * iterators is null. 464 */ 465 public static <T> Iterable<T> concat( 466 final Iterable<? extends Iterable<? extends T>> inputs) { 467 checkNotNull(inputs); 468 return new IterableWithToString<T>() { 469 @Override 470 public Iterator<T> iterator() { 471 return Iterators.concat(iterators(inputs)); 472 } 473 }; 474 } 475 476 /** 477 * Returns an iterator over the iterators of the given iterables. 478 */ 479 private static <T> UnmodifiableIterator<Iterator<? extends T>> iterators( 480 Iterable<? extends Iterable<? extends T>> iterables) { 481 final Iterator<? extends Iterable<? extends T>> iterableIterator = 482 iterables.iterator(); 483 return new UnmodifiableIterator<Iterator<? extends T>>() { 484 @Override 485 public boolean hasNext() { 486 return iterableIterator.hasNext(); 487 } 488 @Override 489 public Iterator<? extends T> next() { 490 return iterableIterator.next().iterator(); 491 } 492 }; 493 } 494 495 /** 496 * Divides an iterable into unmodifiable sublists of the given size (the final 497 * iterable may be smaller). For example, partitioning an iterable containing 498 * {@code [a, b, c, d, e]} with a partition size of 3 yields {@code 499 * [[a, b, c], [d, e]]} -- an outer iterable containing two inner lists of 500 * three and two elements, all in the original order. 501 * 502 * <p>Iterators returned by the returned iterable do not support the {@link 503 * Iterator#remove()} method. The returned lists implement {@link 504 * RandomAccess}, whether or not the input list does. 505 * 506 * <p><b>Note:</b> if {@code iterable} is a {@link List}, use {@link 507 * Lists#partition(List, int)} instead. 508 * 509 * @param iterable the iterable to return a partitioned view of 510 * @param size the desired size of each partition (the last may be smaller) 511 * @return an iterable of unmodifiable lists containing the elements of {@code 512 * iterable} divided into partitions 513 * @throws IllegalArgumentException if {@code size} is nonpositive 514 */ 515 public static <T> Iterable<List<T>> partition( 516 final Iterable<T> iterable, final int size) { 517 checkNotNull(iterable); 518 checkArgument(size > 0); 519 return new IterableWithToString<List<T>>() { 520 @Override 521 public Iterator<List<T>> iterator() { 522 return Iterators.partition(iterable.iterator(), size); 523 } 524 }; 525 } 526 527 /** 528 * Divides an iterable into unmodifiable sublists of the given size, padding 529 * the final iterable with null values if necessary. For example, partitioning 530 * an iterable containing {@code [a, b, c, d, e]} with a partition size of 3 531 * yields {@code [[a, b, c], [d, e, null]]} -- an outer iterable containing 532 * two inner lists of three elements each, all in the original order. 533 * 534 * <p>Iterators returned by the returned iterable do not support the {@link 535 * Iterator#remove()} method. 536 * 537 * @param iterable the iterable to return a partitioned view of 538 * @param size the desired size of each partition 539 * @return an iterable of unmodifiable lists containing the elements of {@code 540 * iterable} divided into partitions (the final iterable may have 541 * trailing null elements) 542 * @throws IllegalArgumentException if {@code size} is nonpositive 543 */ 544 public static <T> Iterable<List<T>> paddedPartition( 545 final Iterable<T> iterable, final int size) { 546 checkNotNull(iterable); 547 checkArgument(size > 0); 548 return new IterableWithToString<List<T>>() { 549 @Override 550 public Iterator<List<T>> iterator() { 551 return Iterators.paddedPartition(iterable.iterator(), size); 552 } 553 }; 554 } 555 556 /** 557 * Returns the elements of {@code unfiltered} that satisfy a predicate. The 558 * resulting iterable's iterator does not support {@code remove()}. 559 */ 560 public static <T> Iterable<T> filter( 561 final Iterable<T> unfiltered, final Predicate<? super T> predicate) { 562 checkNotNull(unfiltered); 563 checkNotNull(predicate); 564 return new IterableWithToString<T>() { 565 @Override 566 public Iterator<T> iterator() { 567 return Iterators.filter(unfiltered.iterator(), predicate); 568 } 569 }; 570 } 571 572 /** 573 * Returns {@code true} if one or more elements in {@code iterable} satisfy 574 * the predicate. 575 */ 576 public static <T> boolean any( 577 Iterable<T> iterable, Predicate<? super T> predicate) { 578 return Iterators.any(iterable.iterator(), predicate); 579 } 580 581 /** 582 * Returns {@code true} if every element in {@code iterable} satisfies the 583 * predicate. If {@code iterable} is empty, {@code true} is returned. 584 */ 585 public static <T> boolean all( 586 Iterable<T> iterable, Predicate<? super T> predicate) { 587 return Iterators.all(iterable.iterator(), predicate); 588 } 589 590 /** 591 * Returns the first element in {@code iterable} that satisfies the given 592 * predicate; use this method only when such an element is known to exist. If 593 * it is possible that <i>no</i> element will match, use {@link 594 * #tryFind)} or {@link #find(Iterable, Predicate, T)} instead. 595 * 596 * @throws NoSuchElementException if no element in {@code iterable} matches 597 * the given predicate 598 */ 599 public static <T> T find(Iterable<T> iterable, 600 Predicate<? super T> predicate) { 601 return Iterators.find(iterable.iterator(), predicate); 602 } 603 604 /** 605 * Returns the first element in {@code iterable} that satisfies the given 606 * predicate, or {@code defaultValue} if none found. Note that this can 607 * usually be handled more naturally using {@code 608 * tryFind(iterable, predicate).or(defaultValue)}. 609 * 610 * @since 7.0 611 */ 612 public static <T> T find(Iterable<T> iterable, 613 Predicate<? super T> predicate, @Nullable T defaultValue) { 614 return Iterators.find(iterable.iterator(), predicate, defaultValue); 615 } 616 617 /** 618 * Returns an {@link Optional} containing the first element in {@code 619 * iterable} that satisfies the given predicate, if such an element exists. 620 * 621 * <p><b>Warning:</b> avoid using a {@code predicate} that matches {@code 622 * null}. If {@code null} is matched in {@code iterable}, a 623 * NullPointerException will be thrown. 624 * 625 * @since 11.0 626 */ 627 public static <T> Optional<T> tryFind(Iterable<T> iterable, 628 Predicate<? super T> predicate) { 629 return Iterators.tryFind(iterable.iterator(), predicate); 630 } 631 632 /** 633 * Returns the index in {@code iterable} of the first element that satisfies 634 * the provided {@code predicate}, or {@code -1} if the Iterable has no such 635 * elements. 636 * 637 * <p>More formally, returns the lowest index {@code i} such that 638 * {@code predicate.apply(Iterables.get(iterable, i))} returns {@code true}, 639 * or {@code -1} if there is no such index. 640 * 641 * @since 2.0 642 */ 643 public static <T> int indexOf( 644 Iterable<T> iterable, Predicate<? super T> predicate) { 645 return Iterators.indexOf(iterable.iterator(), predicate); 646 } 647 648 /** 649 * Returns an iterable that applies {@code function} to each element of {@code 650 * fromIterable}. 651 * 652 * <p>The returned iterable's iterator supports {@code remove()} if the 653 * provided iterator does. After a successful {@code remove()} call, 654 * {@code fromIterable} no longer contains the corresponding element. 655 * 656 * <p>If the input {@code Iterable} is known to be a {@code List} or other 657 * {@code Collection}, consider {@link Lists#transform} and {@link 658 * Collections2#transform}. 659 */ 660 public static <F, T> Iterable<T> transform(final Iterable<F> fromIterable, 661 final Function<? super F, ? extends T> function) { 662 checkNotNull(fromIterable); 663 checkNotNull(function); 664 return new IterableWithToString<T>() { 665 @Override 666 public Iterator<T> iterator() { 667 return Iterators.transform(fromIterable.iterator(), function); 668 } 669 }; 670 } 671 672 /** 673 * Returns the element at the specified position in an iterable. 674 * 675 * @param position position of the element to return 676 * @return the element at the specified position in {@code iterable} 677 * @throws IndexOutOfBoundsException if {@code position} is negative or 678 * greater than or equal to the size of {@code iterable} 679 */ 680 public static <T> T get(Iterable<T> iterable, int position) { 681 checkNotNull(iterable); 682 if (iterable instanceof List) { 683 return ((List<T>) iterable).get(position); 684 } 685 686 if (iterable instanceof Collection) { 687 // Can check both ends 688 Collection<T> collection = (Collection<T>) iterable; 689 Preconditions.checkElementIndex(position, collection.size()); 690 } else { 691 // Can only check the lower end 692 checkNonnegativeIndex(position); 693 } 694 return Iterators.get(iterable.iterator(), position); 695 } 696 697 private static void checkNonnegativeIndex(int position) { 698 if (position < 0) { 699 throw new IndexOutOfBoundsException( 700 "position cannot be negative: " + position); 701 } 702 } 703 704 /** 705 * Returns the element at the specified position in an iterable or a default 706 * value otherwise. 707 * 708 * @param position position of the element to return 709 * @param defaultValue the default value to return if {@code position} is 710 * greater than or equal to the size of the iterable 711 * @return the element at the specified position in {@code iterable} or 712 * {@code defaultValue} if {@code iterable} contains fewer than 713 * {@code position + 1} elements. 714 * @throws IndexOutOfBoundsException if {@code position} is negative 715 * @since 4.0 716 */ 717 public static <T> T get(Iterable<T> iterable, int position, 718 @Nullable T defaultValue) { 719 checkNotNull(iterable); 720 checkNonnegativeIndex(position); 721 722 try { 723 return get(iterable, position); 724 } catch (IndexOutOfBoundsException e) { 725 return defaultValue; 726 } 727 } 728 729 /** 730 * Returns the first element in {@code iterable} or {@code defaultValue} if 731 * the iterable is empty. The {@link Iterators} analog to this method is 732 * {@link Iterators#getNext}. 733 * 734 * @param defaultValue the default value to return if the iterable is empty 735 * @return the first element of {@code iterable} or the default value 736 * @since 7.0 737 */ 738 public static <T> T getFirst(Iterable<T> iterable, @Nullable T defaultValue) { 739 return Iterators.getNext(iterable.iterator(), defaultValue); 740 } 741 742 /** 743 * Returns the last element of {@code iterable}. 744 * 745 * @return the last element of {@code iterable} 746 * @throws NoSuchElementException if the iterable is empty 747 */ 748 public static <T> T getLast(Iterable<T> iterable) { 749 // TODO(kevinb): Support a concurrently modified collection? 750 if (iterable instanceof List) { 751 List<T> list = (List<T>) iterable; 752 if (list.isEmpty()) { 753 throw new NoSuchElementException(); 754 } 755 return getLastInNonemptyList(list); 756 } 757 758 /* 759 * TODO(kevinb): consider whether this "optimization" is worthwhile. Users 760 * with SortedSets tend to know they are SortedSets and probably would not 761 * call this method. 762 */ 763 if (iterable instanceof SortedSet) { 764 SortedSet<T> sortedSet = (SortedSet<T>) iterable; 765 return sortedSet.last(); 766 } 767 768 return Iterators.getLast(iterable.iterator()); 769 } 770 771 /** 772 * Returns the last element of {@code iterable} or {@code defaultValue} if 773 * the iterable is empty. 774 * 775 * @param defaultValue the value to return if {@code iterable} is empty 776 * @return the last element of {@code iterable} or the default value 777 * @since 3.0 778 */ 779 public static <T> T getLast(Iterable<T> iterable, @Nullable T defaultValue) { 780 if (iterable instanceof Collection) { 781 Collection<T> collection = (Collection<T>) iterable; 782 if (collection.isEmpty()) { 783 return defaultValue; 784 } 785 } 786 787 if (iterable instanceof List) { 788 List<T> list = (List<T>) iterable; 789 return getLastInNonemptyList(list); 790 } 791 792 /* 793 * TODO(kevinb): consider whether this "optimization" is worthwhile. Users 794 * with SortedSets tend to know they are SortedSets and probably would not 795 * call this method. 796 */ 797 if (iterable instanceof SortedSet) { 798 SortedSet<T> sortedSet = (SortedSet<T>) iterable; 799 return sortedSet.last(); 800 } 801 802 return Iterators.getLast(iterable.iterator(), defaultValue); 803 } 804 805 private static <T> T getLastInNonemptyList(List<T> list) { 806 return list.get(list.size() - 1); 807 } 808 809 /** 810 * Returns a view of {@code iterable} that skips its first 811 * {@code numberToSkip} elements. If {@code iterable} contains fewer than 812 * {@code numberToSkip} elements, the returned iterable skips all of its 813 * elements. 814 * 815 * <p>Modifications to the underlying {@link Iterable} before a call to 816 * {@code iterator()} are reflected in the returned iterator. That is, the 817 * iterator skips the first {@code numberToSkip} elements that exist when the 818 * {@code Iterator} is created, not when {@code skip()} is called. 819 * 820 * <p>The returned iterable's iterator supports {@code remove()} if the 821 * iterator of the underlying iterable supports it. Note that it is 822 * <i>not</i> possible to delete the last skipped element by immediately 823 * calling {@code remove()} on that iterator, as the {@code Iterator} 824 * contract states that a call to {@code remove()} before a call to 825 * {@code next()} will throw an {@link IllegalStateException}. 826 * 827 * @since 3.0 828 */ 829 public static <T> Iterable<T> skip(final Iterable<T> iterable, 830 final int numberToSkip) { 831 checkNotNull(iterable); 832 checkArgument(numberToSkip >= 0, "number to skip cannot be negative"); 833 834 if (iterable instanceof List) { 835 final List<T> list = (List<T>) iterable; 836 return new IterableWithToString<T>() { 837 @Override 838 public Iterator<T> iterator() { 839 // TODO(kevinb): Support a concurrently modified collection? 840 return (numberToSkip >= list.size()) 841 ? Iterators.<T>emptyIterator() 842 : list.subList(numberToSkip, list.size()).iterator(); 843 } 844 }; 845 } 846 847 return new IterableWithToString<T>() { 848 @Override 849 public Iterator<T> iterator() { 850 final Iterator<T> iterator = iterable.iterator(); 851 852 Iterators.skip(iterator, numberToSkip); 853 854 /* 855 * We can't just return the iterator because an immediate call to its 856 * remove() method would remove one of the skipped elements instead of 857 * throwing an IllegalStateException. 858 */ 859 return new Iterator<T>() { 860 boolean atStart = true; 861 862 @Override 863 public boolean hasNext() { 864 return iterator.hasNext(); 865 } 866 867 @Override 868 public T next() { 869 if (!hasNext()) { 870 throw new NoSuchElementException(); 871 } 872 873 try { 874 return iterator.next(); 875 } finally { 876 atStart = false; 877 } 878 } 879 880 @Override 881 public void remove() { 882 if (atStart) { 883 throw new IllegalStateException(); 884 } 885 iterator.remove(); 886 } 887 }; 888 } 889 }; 890 } 891 892 /** 893 * Creates an iterable with the first {@code limitSize} elements of the given 894 * iterable. If the original iterable does not contain that many elements, the 895 * returned iterator will have the same behavior as the original iterable. The 896 * returned iterable's iterator supports {@code remove()} if the original 897 * iterator does. 898 * 899 * @param iterable the iterable to limit 900 * @param limitSize the maximum number of elements in the returned iterator 901 * @throws IllegalArgumentException if {@code limitSize} is negative 902 * @since 3.0 903 */ 904 public static <T> Iterable<T> limit( 905 final Iterable<T> iterable, final int limitSize) { 906 checkNotNull(iterable); 907 checkArgument(limitSize >= 0, "limit is negative"); 908 return new IterableWithToString<T>() { 909 @Override 910 public Iterator<T> iterator() { 911 return Iterators.limit(iterable.iterator(), limitSize); 912 } 913 }; 914 } 915 916 /** 917 * Returns a view of the supplied iterable that wraps each generated 918 * {@link Iterator} through {@link Iterators#consumingIterator(Iterator)}. 919 * 920 * <p>Note: If {@code iterable} is a {@link Queue}, the returned iterable will 921 * get entries from {@link Queue#remove()} since {@link Queue}'s iteration 922 * order is undefined. Calling {@link Iterator#hasNext()} on a generated 923 * iterator from the returned iterable may cause an item to be immediately 924 * dequeued for return on a subsequent call to {@link Iterator#next()}. 925 * 926 * @param iterable the iterable to wrap 927 * @return a view of the supplied iterable that wraps each generated iterator 928 * through {@link Iterators#consumingIterator(Iterator)}; for queues, 929 * an iterable that generates iterators that return and consume the 930 * queue's elements in queue order 931 * 932 * @see Iterators#consumingIterator(Iterator) 933 * @since 2.0 934 */ 935 public static <T> Iterable<T> consumingIterable(final Iterable<T> iterable) { 936 if (iterable instanceof Queue) { 937 return new Iterable<T>() { 938 @Override 939 public Iterator<T> iterator() { 940 return new ConsumingQueueIterator<T>((Queue<T>) iterable); 941 } 942 }; 943 } 944 945 checkNotNull(iterable); 946 947 return new Iterable<T>() { 948 @Override 949 public Iterator<T> iterator() { 950 return Iterators.consumingIterator(iterable.iterator()); 951 } 952 }; 953 } 954 955 private static class ConsumingQueueIterator<T> extends AbstractIterator<T> { 956 private final Queue<T> queue; 957 958 private ConsumingQueueIterator(Queue<T> queue) { 959 this.queue = queue; 960 } 961 962 @Override public T computeNext() { 963 try { 964 return queue.remove(); 965 } catch (NoSuchElementException e) { 966 return endOfData(); 967 } 968 } 969 } 970 971 // Methods only in Iterables, not in Iterators 972 973 /** 974 * Adapts a list to an iterable with reversed iteration order. It is 975 * especially useful in foreach-style loops: <pre> {@code 976 * 977 * List<String> mylist = ... 978 * for (String str : Iterables.reverse(mylist)) { 979 * ... 980 * }}</pre> 981 * 982 * There is no corresponding method in {@link Iterators}, since {@link 983 * Iterable#iterator} can simply be invoked on the result of calling this 984 * method. 985 * 986 * @return an iterable with the same elements as the list, in reverse 987 * 988 * @deprecated use {@link Lists#reverse(List)} or {@link 989 * ImmutableList#reverse()}. <b>This method is scheduled for deletion in 990 * July 2012.</b> 991 */ 992 @Deprecated 993 public static <T> Iterable<T> reverse(final List<T> list) { 994 return Lists.reverse(list); 995 } 996 997 /** 998 * Determines if the given iterable contains no elements. 999 * 1000 * <p>There is no precise {@link Iterator} equivalent to this method, since 1001 * one can only ask an iterator whether it has any elements <i>remaining</i> 1002 * (which one does using {@link Iterator#hasNext}). 1003 * 1004 * @return {@code true} if the iterable contains no elements 1005 */ 1006 public static boolean isEmpty(Iterable<?> iterable) { 1007 if (iterable instanceof Collection) { 1008 return ((Collection<?>) iterable).isEmpty(); 1009 } 1010 return !iterable.iterator().hasNext(); 1011 } 1012 1013 // Non-public 1014 1015 /** 1016 * Removes the specified element from the specified iterable. 1017 * 1018 * <p>This method iterates over the iterable, checking each element returned 1019 * by the iterator in turn to see if it equals the object {@code o}. If they 1020 * are equal, it is removed from the iterable with the iterator's 1021 * {@code remove} method. At most one element is removed, even if the iterable 1022 * contains multiple members that equal {@code o}. 1023 * 1024 * <p><b>Warning:</b> Do not use this method for a collection, such as a 1025 * {@link HashSet}, that has a fast {@code remove} method. 1026 * 1027 * @param iterable the iterable from which to remove 1028 * @param o an element to remove from the collection 1029 * @return {@code true} if the iterable changed as a result 1030 * @throws UnsupportedOperationException if the iterator does not support the 1031 * {@code remove} method and the iterable contains the object 1032 */ 1033 static boolean remove(Iterable<?> iterable, @Nullable Object o) { 1034 Iterator<?> i = iterable.iterator(); 1035 while (i.hasNext()) { 1036 if (Objects.equal(i.next(), o)) { 1037 i.remove(); 1038 return true; 1039 } 1040 } 1041 return false; 1042 } 1043 1044 abstract static class IterableWithToString<E> implements Iterable<E> { 1045 @Override public String toString() { 1046 return Iterables.toString(this); 1047 } 1048 } 1049 1050 /** 1051 * Returns an iterable over the merged contents of all given 1052 * {@code iterables}. Equivalent entries will not be de-duplicated. 1053 * 1054 * <p>Callers must ensure that the source {@code iterables} are in 1055 * non-descending order as this method does not sort its input. 1056 * 1057 * <p>For any equivalent elements across all {@code iterables}, it is 1058 * undefined which element is returned first. 1059 * 1060 * @since 11.0 1061 */ 1062 @Beta 1063 public static <T> Iterable<T> mergeSorted( 1064 final Iterable<? extends Iterable<? extends T>> iterables, 1065 final Comparator<? super T> comparator) { 1066 checkNotNull(iterables, "iterables"); 1067 checkNotNull(comparator, "comparator"); 1068 Iterable<T> iterable = new Iterable<T>() { 1069 @Override 1070 public Iterator<T> iterator() { 1071 return Iterators.mergeSorted( 1072 Iterables.transform(iterables, Iterables.<T>toIterator()), 1073 comparator); 1074 } 1075 }; 1076 return new UnmodifiableIterable<T>(iterable); 1077 } 1078 1079 // TODO(user): Is this the best place for this? Move to fluent functions? 1080 // Useful as a public method? 1081 private static <T> Function<Iterable<? extends T>, Iterator<? extends T>> 1082 toIterator() { 1083 return new Function<Iterable<? extends T>, Iterator<? extends T>>() { 1084 @Override 1085 public Iterator<? extends T> apply(Iterable<? extends T> iterable) { 1086 return iterable.iterator(); 1087 } 1088 }; 1089 } 1090} 1091