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