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.GwtCompatible;
023 import com.google.common.annotations.GwtIncompatible;
024 import com.google.common.base.Function;
025 import com.google.common.base.Objects;
026 import com.google.common.base.Preconditions;
027 import com.google.common.base.Predicate;
028
029 import java.util.Arrays;
030 import java.util.Collection;
031 import java.util.Collections;
032 import java.util.HashSet;
033 import java.util.Iterator;
034 import java.util.List;
035 import java.util.NoSuchElementException;
036 import java.util.Queue;
037 import java.util.RandomAccess;
038 import java.util.Set;
039 import java.util.SortedSet;
040
041 import javax.annotation.Nullable;
042
043 /**
044 * This class contains static utility methods that operate on or return objects
045 * of type {@code Iterable}. Except as noted, each method has a corresponding
046 * {@link Iterator}-based method in the {@link Iterators} class.
047 *
048 * <p><i>Performance notes:</i> Unless otherwise noted, all of the iterables
049 * produced in this class are <i>lazy</i>, which means that their iterators
050 * only advance the backing iteration when absolutely necessary.
051 *
052 * @author Kevin Bourrillion
053 * @author Jared Levy
054 * @since 2.0 (imported from Google Collections Library)
055 */
056 @GwtCompatible(emulated = true)
057 public final class Iterables {
058 private Iterables() {}
059
060 /** Returns an unmodifiable view of {@code iterable}. */
061 public static <T> Iterable<T> unmodifiableIterable(
062 final Iterable<T> iterable) {
063 checkNotNull(iterable);
064 if (iterable instanceof UnmodifiableIterable ||
065 iterable instanceof ImmutableCollection) {
066 return iterable;
067 }
068 return new UnmodifiableIterable<T>(iterable);
069 }
070
071 /**
072 * Simply returns its argument.
073 *
074 * @deprecated no need to use this
075 * @since 10.0
076 */
077 @Deprecated public static <E> Iterable<E> unmodifiableIterable(
078 ImmutableCollection<E> iterable) {
079 return checkNotNull(iterable);
080 }
081
082 private static final class UnmodifiableIterable<T> implements Iterable<T> {
083 private final Iterable<T> iterable;
084
085 private UnmodifiableIterable(Iterable<T> iterable) {
086 this.iterable = iterable;
087 }
088
089 @Override
090 public Iterator<T> iterator() {
091 return Iterators.unmodifiableIterator(iterable.iterator());
092 }
093
094 @Override
095 public String toString() {
096 return iterable.toString();
097 }
098 // no equals and hashCode; it would break the contract!
099 }
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 * @param type the type of the elements
285 * @return a newly-allocated array into which all the elements of the iterable
286 * have been copied
287 */
288 @GwtIncompatible("Array.newInstance(Class, int)")
289 public static <T> T[] toArray(Iterable<? extends T> iterable, Class<T> type) {
290 Collection<? extends T> collection = toCollection(iterable);
291 T[] array = ObjectArrays.newArray(type, collection.size());
292 return collection.toArray(array);
293 }
294
295 /**
296 * Copies an iterable's elements into an array.
297 *
298 * @param iterable the iterable to copy
299 * @return a newly-allocated array into which all the elements of the iterable
300 * have been copied
301 */
302 static Object[] toArray(Iterable<?> iterable) {
303 return toCollection(iterable).toArray();
304 }
305
306 /**
307 * Converts an iterable into a collection. If the iterable is already a
308 * collection, it is returned. Otherwise, an {@link java.util.ArrayList} is
309 * created with the contents of the iterable in the same iteration order.
310 */
311 private static <E> Collection<E> toCollection(Iterable<E> iterable) {
312 return (iterable instanceof Collection)
313 ? (Collection<E>) iterable
314 : Lists.newArrayList(iterable.iterator());
315 }
316
317 /**
318 * Adds all elements in {@code iterable} to {@code collection}.
319 *
320 * @return {@code true} if {@code collection} was modified as a result of this
321 * operation.
322 */
323 public static <T> boolean addAll(
324 Collection<T> addTo, Iterable<? extends T> elementsToAdd) {
325 if (elementsToAdd instanceof Collection) {
326 Collection<? extends T> c = Collections2.cast(elementsToAdd);
327 return addTo.addAll(c);
328 }
329 return Iterators.addAll(addTo, elementsToAdd.iterator());
330 }
331
332 /**
333 * Returns the number of elements in the specified iterable that equal the
334 * specified object. This implementation avoids a full iteration when the
335 * iterable is a {@link Multiset} or {@link Set}.
336 *
337 * @see Collections#frequency
338 */
339 public static int frequency(Iterable<?> iterable, @Nullable Object element) {
340 if ((iterable instanceof Multiset)) {
341 return ((Multiset<?>) iterable).count(element);
342 }
343 if ((iterable instanceof Set)) {
344 return ((Set<?>) iterable).contains(element) ? 1 : 0;
345 }
346 return Iterators.frequency(iterable.iterator(), element);
347 }
348
349 /**
350 * Returns an iterable whose iterators cycle indefinitely over the elements of
351 * {@code iterable}.
352 *
353 * <p>That iterator supports {@code remove()} if {@code iterable.iterator()}
354 * does. After {@code remove()} is called, subsequent cycles omit the removed
355 * element, which is no longer in {@code iterable}. The iterator's
356 * {@code hasNext()} method returns {@code true} until {@code iterable} is
357 * empty.
358 *
359 * <p><b>Warning:</b> Typical uses of the resulting iterator may produce an
360 * infinite loop. You should use an explicit {@code break} or be certain that
361 * you will eventually remove all the elements.
362 *
363 * <p>To cycle over the iterable {@code n} times, use the following:
364 * {@code Iterables.concat(Collections.nCopies(n, iterable))}
365 */
366 public static <T> Iterable<T> cycle(final Iterable<T> iterable) {
367 checkNotNull(iterable);
368 return new Iterable<T>() {
369 @Override
370 public Iterator<T> iterator() {
371 return Iterators.cycle(iterable);
372 }
373 @Override public String toString() {
374 return iterable.toString() + " (cycled)";
375 }
376 };
377 }
378
379 /**
380 * Returns an iterable whose iterators cycle indefinitely over the provided
381 * elements.
382 *
383 * <p>After {@code remove} is invoked on a generated iterator, the removed
384 * element will no longer appear in either that iterator or any other iterator
385 * created from the same source iterable. That is, this method behaves exactly
386 * as {@code Iterables.cycle(Lists.newArrayList(elements))}. The iterator's
387 * {@code hasNext} method returns {@code true} until all of the original
388 * elements have been removed.
389 *
390 * <p><b>Warning:</b> Typical uses of the resulting iterator may produce an
391 * infinite loop. You should use an explicit {@code break} or be certain that
392 * you will eventually remove all the elements.
393 *
394 * <p>To cycle over the elements {@code n} times, use the following:
395 * {@code Iterables.concat(Collections.nCopies(n, Arrays.asList(elements)))}
396 */
397 public static <T> Iterable<T> cycle(T... elements) {
398 return cycle(Lists.newArrayList(elements));
399 }
400
401 /**
402 * Combines two iterables into a single iterable. The returned iterable has an
403 * iterator that traverses the elements in {@code a}, followed by the elements
404 * in {@code b}. The source iterators are not polled until necessary.
405 *
406 * <p>The returned iterable's iterator supports {@code remove()} when the
407 * corresponding input iterator supports it.
408 */
409 @SuppressWarnings("unchecked")
410 public static <T> Iterable<T> concat(
411 Iterable<? extends T> a, Iterable<? extends T> b) {
412 checkNotNull(a);
413 checkNotNull(b);
414 return concat(Arrays.asList(a, b));
415 }
416
417 /**
418 * Combines three iterables into a single iterable. The returned iterable has
419 * an iterator that traverses the elements in {@code a}, followed by the
420 * elements in {@code b}, followed by the elements in {@code c}. The source
421 * iterators are not polled until necessary.
422 *
423 * <p>The returned iterable's iterator supports {@code remove()} when the
424 * corresponding input iterator supports it.
425 */
426 @SuppressWarnings("unchecked")
427 public static <T> Iterable<T> concat(Iterable<? extends T> a,
428 Iterable<? extends T> b, Iterable<? extends T> c) {
429 checkNotNull(a);
430 checkNotNull(b);
431 checkNotNull(c);
432 return concat(Arrays.asList(a, b, c));
433 }
434
435 /**
436 * Combines four iterables into a single iterable. The returned iterable has
437 * an iterator that traverses the elements in {@code a}, followed by the
438 * elements in {@code b}, followed by the elements in {@code c}, followed by
439 * the elements in {@code d}. The source iterators are not polled until
440 * necessary.
441 *
442 * <p>The returned iterable's iterator supports {@code remove()} when the
443 * corresponding input iterator supports it.
444 */
445 @SuppressWarnings("unchecked")
446 public static <T> Iterable<T> concat(Iterable<? extends T> a,
447 Iterable<? extends T> b, Iterable<? extends T> c,
448 Iterable<? extends T> d) {
449 checkNotNull(a);
450 checkNotNull(b);
451 checkNotNull(c);
452 checkNotNull(d);
453 return concat(Arrays.asList(a, b, c, d));
454 }
455
456 /**
457 * Combines multiple iterables into a single iterable. The returned iterable
458 * has an iterator that traverses the elements of each iterable in
459 * {@code inputs}. The input iterators are not polled until necessary.
460 *
461 * <p>The returned iterable's iterator supports {@code remove()} when the
462 * corresponding input iterator supports it.
463 *
464 * @throws NullPointerException if any of the provided iterables is null
465 */
466 public static <T> Iterable<T> concat(Iterable<? extends T>... inputs) {
467 return concat(ImmutableList.copyOf(inputs));
468 }
469
470 /**
471 * Combines multiple iterables into a single iterable. The returned iterable
472 * has an iterator that traverses the elements of each iterable in
473 * {@code inputs}. The input iterators are not polled until necessary.
474 *
475 * <p>The returned iterable's iterator supports {@code remove()} when the
476 * corresponding input iterator supports it. The methods of the returned
477 * iterable may throw {@code NullPointerException} if any of the input
478 * iterators is null.
479 */
480 public static <T> Iterable<T> concat(
481 final Iterable<? extends Iterable<? extends T>> inputs) {
482 checkNotNull(inputs);
483 return new IterableWithToString<T>() {
484 @Override
485 public Iterator<T> iterator() {
486 return Iterators.concat(iterators(inputs));
487 }
488 };
489 }
490
491 /**
492 * Returns an iterator over the iterators of the given iterables.
493 */
494 private static <T> UnmodifiableIterator<Iterator<? extends T>> iterators(
495 Iterable<? extends Iterable<? extends T>> iterables) {
496 final Iterator<? extends Iterable<? extends T>> iterableIterator =
497 iterables.iterator();
498 return new UnmodifiableIterator<Iterator<? extends T>>() {
499 @Override
500 public boolean hasNext() {
501 return iterableIterator.hasNext();
502 }
503 @Override
504 public Iterator<? extends T> next() {
505 return iterableIterator.next().iterator();
506 }
507 };
508 }
509
510 /**
511 * Divides an iterable into unmodifiable sublists of the given size (the final
512 * iterable may be smaller). For example, partitioning an iterable containing
513 * {@code [a, b, c, d, e]} with a partition size of 3 yields {@code
514 * [[a, b, c], [d, e]]} -- an outer iterable containing two inner lists of
515 * three and two elements, all in the original order.
516 *
517 * <p>Iterators returned by the returned iterable do not support the {@link
518 * Iterator#remove()} method. The returned lists implement {@link
519 * RandomAccess}, whether or not the input list does.
520 *
521 * <p><b>Note:</b> if {@code iterable} is a {@link List}, use {@link
522 * Lists#partition(List, int)} instead.
523 *
524 * @param iterable the iterable to return a partitioned view of
525 * @param size the desired size of each partition (the last may be smaller)
526 * @return an iterable of unmodifiable lists containing the elements of {@code
527 * iterable} divided into partitions
528 * @throws IllegalArgumentException if {@code size} is nonpositive
529 */
530 public static <T> Iterable<List<T>> partition(
531 final Iterable<T> iterable, final int size) {
532 checkNotNull(iterable);
533 checkArgument(size > 0);
534 return new IterableWithToString<List<T>>() {
535 @Override
536 public Iterator<List<T>> iterator() {
537 return Iterators.partition(iterable.iterator(), size);
538 }
539 };
540 }
541
542 /**
543 * Divides an iterable into unmodifiable sublists of the given size, padding
544 * the final iterable with null values if necessary. For example, partitioning
545 * an iterable containing {@code [a, b, c, d, e]} with a partition size of 3
546 * yields {@code [[a, b, c], [d, e, null]]} -- an outer iterable containing
547 * two inner lists of three elements each, all in the original order.
548 *
549 * <p>Iterators returned by the returned iterable do not support the {@link
550 * Iterator#remove()} method.
551 *
552 * @param iterable the iterable to return a partitioned view of
553 * @param size the desired size of each partition
554 * @return an iterable of unmodifiable lists containing the elements of {@code
555 * iterable} divided into partitions (the final iterable may have
556 * trailing null elements)
557 * @throws IllegalArgumentException if {@code size} is nonpositive
558 */
559 public static <T> Iterable<List<T>> paddedPartition(
560 final Iterable<T> iterable, final int size) {
561 checkNotNull(iterable);
562 checkArgument(size > 0);
563 return new IterableWithToString<List<T>>() {
564 @Override
565 public Iterator<List<T>> iterator() {
566 return Iterators.paddedPartition(iterable.iterator(), size);
567 }
568 };
569 }
570
571 /**
572 * Returns the elements of {@code unfiltered} that satisfy a predicate. The
573 * resulting iterable's iterator does not support {@code remove()}.
574 */
575 public static <T> Iterable<T> filter(
576 final Iterable<T> unfiltered, final Predicate<? super T> predicate) {
577 checkNotNull(unfiltered);
578 checkNotNull(predicate);
579 return new IterableWithToString<T>() {
580 @Override
581 public Iterator<T> iterator() {
582 return Iterators.filter(unfiltered.iterator(), predicate);
583 }
584 };
585 }
586
587 /**
588 * Returns all instances of class {@code type} in {@code unfiltered}. The
589 * returned iterable has elements whose class is {@code type} or a subclass of
590 * {@code type}. The returned iterable's iterator does not support
591 * {@code remove()}.
592 *
593 * @param unfiltered an iterable containing objects of any type
594 * @param type the type of elements desired
595 * @return an unmodifiable iterable containing all elements of the original
596 * iterable that were of the requested type
597 */
598 @GwtIncompatible("Class.isInstance")
599 public static <T> Iterable<T> filter(
600 final Iterable<?> unfiltered, final Class<T> type) {
601 checkNotNull(unfiltered);
602 checkNotNull(type);
603 return new IterableWithToString<T>() {
604 @Override
605 public Iterator<T> iterator() {
606 return Iterators.filter(unfiltered.iterator(), type);
607 }
608 };
609 }
610
611 /**
612 * Returns {@code true} if one or more elements in {@code iterable} satisfy
613 * the predicate.
614 */
615 public static <T> boolean any(
616 Iterable<T> iterable, Predicate<? super T> predicate) {
617 return Iterators.any(iterable.iterator(), predicate);
618 }
619
620 /**
621 * Returns {@code true} if every element in {@code iterable} satisfies the
622 * predicate. If {@code iterable} is empty, {@code true} is returned.
623 */
624 public static <T> boolean all(
625 Iterable<T> iterable, Predicate<? super T> predicate) {
626 return Iterators.all(iterable.iterator(), predicate);
627 }
628
629 /**
630 * Returns the first element in {@code iterable} that satisfies the given
631 * predicate.
632 *
633 * @throws NoSuchElementException if no element in {@code iterable} matches
634 * the given predicate
635 */
636 public static <T> T find(Iterable<T> iterable,
637 Predicate<? super T> predicate) {
638 return Iterators.find(iterable.iterator(), predicate);
639 }
640
641 /**
642 * Returns the first element in {@code iterable} that satisfies the given
643 * predicate, or {@code defaultValue} if none found.
644 *
645 * @since 7.0
646 */
647 public static <T> T find(Iterable<T> iterable,
648 Predicate<? super T> predicate, @Nullable T defaultValue) {
649 return Iterators.find(iterable.iterator(), predicate, defaultValue);
650 }
651
652 /**
653 * Returns the index in {@code iterable} of the first element that satisfies
654 * the provided {@code predicate}, or {@code -1} if the Iterable has no such
655 * elements.
656 *
657 * <p>More formally, returns the lowest index {@code i} such that
658 * {@code predicate.apply(Iterables.get(iterable, i))} returns {@code true},
659 * or {@code -1} if there is no such index.
660 *
661 * @since 2.0
662 */
663 public static <T> int indexOf(
664 Iterable<T> iterable, Predicate<? super T> predicate) {
665 return Iterators.indexOf(iterable.iterator(), predicate);
666 }
667
668 /**
669 * Returns an iterable that applies {@code function} to each element of {@code
670 * fromIterable}.
671 *
672 * <p>The returned iterable's iterator supports {@code remove()} if the
673 * provided iterator does. After a successful {@code remove()} call,
674 * {@code fromIterable} no longer contains the corresponding element.
675 *
676 * <p>If the input {@code Iterable} is known to be a {@code List} or other
677 * {@code Collection}, consider {@link Lists#transform} and {@link
678 * Collections2#transform}.
679 */
680 public static <F, T> Iterable<T> transform(final Iterable<F> fromIterable,
681 final Function<? super F, ? extends T> function) {
682 checkNotNull(fromIterable);
683 checkNotNull(function);
684 return new IterableWithToString<T>() {
685 @Override
686 public Iterator<T> iterator() {
687 return Iterators.transform(fromIterable.iterator(), function);
688 }
689 };
690 }
691
692 /**
693 * Returns the element at the specified position in an iterable.
694 *
695 * @param position position of the element to return
696 * @return the element at the specified position in {@code iterable}
697 * @throws IndexOutOfBoundsException if {@code position} is negative or
698 * greater than or equal to the size of {@code iterable}
699 */
700 public static <T> T get(Iterable<T> iterable, int position) {
701 checkNotNull(iterable);
702 if (iterable instanceof List) {
703 return ((List<T>) iterable).get(position);
704 }
705
706 if (iterable instanceof Collection) {
707 // Can check both ends
708 Collection<T> collection = (Collection<T>) iterable;
709 Preconditions.checkElementIndex(position, collection.size());
710 } else {
711 // Can only check the lower end
712 checkNonnegativeIndex(position);
713 }
714 return Iterators.get(iterable.iterator(), position);
715 }
716
717 private static void checkNonnegativeIndex(int position) {
718 if (position < 0) {
719 throw new IndexOutOfBoundsException(
720 "position cannot be negative: " + position);
721 }
722 }
723
724 /**
725 * Returns the element at the specified position in an iterable or a default
726 * value otherwise.
727 *
728 * @param position position of the element to return
729 * @param defaultValue the default value to return if {@code position} is
730 * greater than or equal to the size of the iterable
731 * @return the element at the specified position in {@code iterable} or
732 * {@code defaultValue} if {@code iterable} contains fewer than
733 * {@code position + 1} elements.
734 * @throws IndexOutOfBoundsException if {@code position} is negative
735 * @since 4.0
736 */
737 public static <T> T get(Iterable<T> iterable, int position,
738 @Nullable T defaultValue) {
739 checkNotNull(iterable);
740 checkNonnegativeIndex(position);
741
742 try {
743 return get(iterable, position);
744 } catch (IndexOutOfBoundsException e) {
745 return defaultValue;
746 }
747 }
748
749 /**
750 * Returns the first element in {@code iterable} or {@code defaultValue} if
751 * the iterable is empty. The {@link Iterators} analog to this method is
752 * {@link Iterators#getNext}.
753 *
754 * @param defaultValue the default value to return if the iterable is empty
755 * @return the first element of {@code iterable} or the default value
756 * @since 7.0
757 */
758 public static <T> T getFirst(Iterable<T> iterable, @Nullable T defaultValue) {
759 return Iterators.getNext(iterable.iterator(), defaultValue);
760 }
761
762 /**
763 * Returns the last element of {@code iterable}.
764 *
765 * @return the last element of {@code iterable}
766 * @throws NoSuchElementException if the iterable is empty
767 */
768 public static <T> T getLast(Iterable<T> iterable) {
769 // TODO(kevinb): Support a concurrently modified collection?
770 if (iterable instanceof List) {
771 List<T> list = (List<T>) iterable;
772 if (list.isEmpty()) {
773 throw new NoSuchElementException();
774 }
775 return getLastInNonemptyList(list);
776 }
777
778 /*
779 * TODO(kevinb): consider whether this "optimization" is worthwhile. Users
780 * with SortedSets tend to know they are SortedSets and probably would not
781 * call this method.
782 */
783 if (iterable instanceof SortedSet) {
784 SortedSet<T> sortedSet = (SortedSet<T>) iterable;
785 return sortedSet.last();
786 }
787
788 return Iterators.getLast(iterable.iterator());
789 }
790
791 /**
792 * Returns the last element of {@code iterable} or {@code defaultValue} if
793 * the iterable is empty.
794 *
795 * @param defaultValue the value to return if {@code iterable} is empty
796 * @return the last element of {@code iterable} or the default value
797 * @since 3.0
798 */
799 public static <T> T getLast(Iterable<T> iterable, @Nullable T defaultValue) {
800 if (iterable instanceof Collection) {
801 Collection<T> collection = (Collection<T>) iterable;
802 if (collection.isEmpty()) {
803 return defaultValue;
804 }
805 }
806
807 if (iterable instanceof List) {
808 List<T> list = (List<T>) iterable;
809 return getLastInNonemptyList(list);
810 }
811
812 /*
813 * TODO(kevinb): consider whether this "optimization" is worthwhile. Users
814 * with SortedSets tend to know they are SortedSets and probably would not
815 * call this method.
816 */
817 if (iterable instanceof SortedSet) {
818 SortedSet<T> sortedSet = (SortedSet<T>) iterable;
819 return sortedSet.last();
820 }
821
822 return Iterators.getLast(iterable.iterator(), defaultValue);
823 }
824
825 private static <T> T getLastInNonemptyList(List<T> list) {
826 return list.get(list.size() - 1);
827 }
828
829 /**
830 * Returns a view of {@code iterable} that skips its first
831 * {@code numberToSkip} elements. If {@code iterable} contains fewer than
832 * {@code numberToSkip} elements, the returned iterable skips all of its
833 * elements.
834 *
835 * <p>Modifications to the underlying {@link Iterable} before a call to
836 * {@code iterator()} are reflected in the returned iterator. That is, the
837 * iterator skips the first {@code numberToSkip} elements that exist when the
838 * {@code Iterator} is created, not when {@code skip()} is called.
839 *
840 * <p>The returned iterable's iterator supports {@code remove()} if the
841 * iterator of the underlying iterable supports it. Note that it is
842 * <i>not</i> possible to delete the last skipped element by immediately
843 * calling {@code remove()} on that iterator, as the {@code Iterator}
844 * contract states that a call to {@code remove()} before a call to
845 * {@code next()} will throw an {@link IllegalStateException}.
846 *
847 * @since 3.0
848 */
849 public static <T> Iterable<T> skip(final Iterable<T> iterable,
850 final int numberToSkip) {
851 checkNotNull(iterable);
852 checkArgument(numberToSkip >= 0, "number to skip cannot be negative");
853
854 if (iterable instanceof List) {
855 final List<T> list = (List<T>) iterable;
856 return new IterableWithToString<T>() {
857 @Override
858 public Iterator<T> iterator() {
859 // TODO(kevinb): Support a concurrently modified collection?
860 return (numberToSkip >= list.size())
861 ? Iterators.<T>emptyIterator()
862 : list.subList(numberToSkip, list.size()).iterator();
863 }
864 };
865 }
866
867 return new IterableWithToString<T>() {
868 @Override
869 public Iterator<T> iterator() {
870 final Iterator<T> iterator = iterable.iterator();
871
872 Iterators.skip(iterator, numberToSkip);
873
874 /*
875 * We can't just return the iterator because an immediate call to its
876 * remove() method would remove one of the skipped elements instead of
877 * throwing an IllegalStateException.
878 */
879 return new Iterator<T>() {
880 boolean atStart = true;
881
882 @Override
883 public boolean hasNext() {
884 return iterator.hasNext();
885 }
886
887 @Override
888 public T next() {
889 if (!hasNext()) {
890 throw new NoSuchElementException();
891 }
892
893 try {
894 return iterator.next();
895 } finally {
896 atStart = false;
897 }
898 }
899
900 @Override
901 public void remove() {
902 if (atStart) {
903 throw new IllegalStateException();
904 }
905 iterator.remove();
906 }
907 };
908 }
909 };
910 }
911
912 /**
913 * Creates an iterable with the first {@code limitSize} elements of the given
914 * iterable. If the original iterable does not contain that many elements, the
915 * returned iterator will have the same behavior as the original iterable. The
916 * returned iterable's iterator supports {@code remove()} if the original
917 * iterator does.
918 *
919 * @param iterable the iterable to limit
920 * @param limitSize the maximum number of elements in the returned iterator
921 * @throws IllegalArgumentException if {@code limitSize} is negative
922 * @since 3.0
923 */
924 public static <T> Iterable<T> limit(
925 final Iterable<T> iterable, final int limitSize) {
926 checkNotNull(iterable);
927 checkArgument(limitSize >= 0, "limit is negative");
928 return new IterableWithToString<T>() {
929 @Override
930 public Iterator<T> iterator() {
931 return Iterators.limit(iterable.iterator(), limitSize);
932 }
933 };
934 }
935
936 /**
937 * Returns a view of the supplied iterable that wraps each generated
938 * {@link Iterator} through {@link Iterators#consumingIterator(Iterator)}.
939 *
940 * <p>Note: If {@code iterable} is a {@link Queue}, the returned iterable will
941 * get entries from {@link Queue#remove()} since {@link Queue}'s iteration
942 * order is undefined. Calling {@link Iterator#hasNext()} on a generated
943 * iterator from the returned iterable may cause an item to be immediately
944 * dequeued for return on a subsequent call to {@link Iterator#next()}.
945 *
946 * @param iterable the iterable to wrap
947 * @return a view of the supplied iterable that wraps each generated iterator
948 * through {@link Iterators#consumingIterator(Iterator)}; for queues,
949 * an iterable that generates iterators that return and consume the
950 * queue's elements in queue order
951 *
952 * @see Iterators#consumingIterator(Iterator)
953 * @since 2.0
954 */
955 public static <T> Iterable<T> consumingIterable(final Iterable<T> iterable) {
956 if (iterable instanceof Queue) {
957 return new Iterable<T>() {
958 @Override
959 public Iterator<T> iterator() {
960 return new ConsumingQueueIterator<T>((Queue<T>) iterable);
961 }
962 };
963 }
964
965 checkNotNull(iterable);
966
967 return new Iterable<T>() {
968 @Override
969 public Iterator<T> iterator() {
970 return Iterators.consumingIterator(iterable.iterator());
971 }
972 };
973 }
974
975 private static class ConsumingQueueIterator<T> extends AbstractIterator<T> {
976 private final Queue<T> queue;
977
978 private ConsumingQueueIterator(Queue<T> queue) {
979 this.queue = queue;
980 }
981
982 @Override public T computeNext() {
983 try {
984 return queue.remove();
985 } catch (NoSuchElementException e) {
986 return endOfData();
987 }
988 }
989 }
990
991 // Methods only in Iterables, not in Iterators
992
993 /**
994 * Adapts a list to an iterable with reversed iteration order. It is
995 * especially useful in foreach-style loops: <pre> {@code
996 *
997 * List<String> mylist = ...
998 * for (String str : Iterables.reverse(mylist)) {
999 * ...
1000 * }}</pre>
1001 *
1002 * There is no corresponding method in {@link Iterators}, since {@link
1003 * Iterable#iterator} can simply be invoked on the result of calling this
1004 * method.
1005 *
1006 * @return an iterable with the same elements as the list, in reverse
1007 *
1008 * @deprecated use {@link Lists#reverse(List)} or {@link
1009 * ImmutableList#reverse()}. <b>This method is scheduled for deletion in
1010 * July 2012.</b>
1011 */
1012 @Deprecated
1013 public static <T> Iterable<T> reverse(final List<T> list) {
1014 return Lists.reverse(list);
1015 }
1016
1017 /**
1018 * Determines if the given iterable contains no elements.
1019 *
1020 * <p>There is no precise {@link Iterator} equivalent to this method, since
1021 * one can only ask an iterator whether it has any elements <i>remaining</i>
1022 * (which one does using {@link Iterator#hasNext}).
1023 *
1024 * @return {@code true} if the iterable contains no elements
1025 */
1026 public static <T> boolean isEmpty(Iterable<T> iterable) {
1027 return !iterable.iterator().hasNext();
1028 }
1029
1030 // Non-public
1031
1032 /**
1033 * Removes the specified element from the specified iterable.
1034 *
1035 * <p>This method iterates over the iterable, checking each element returned
1036 * by the iterator in turn to see if it equals the object {@code o}. If they
1037 * are equal, it is removed from the iterable with the iterator's
1038 * {@code remove} method. At most one element is removed, even if the iterable
1039 * contains multiple members that equal {@code o}.
1040 *
1041 * <p><b>Warning:</b> Do not use this method for a collection, such as a
1042 * {@link HashSet}, that has a fast {@code remove} method.
1043 *
1044 * @param iterable the iterable from which to remove
1045 * @param o an element to remove from the collection
1046 * @return {@code true} if the iterable changed as a result
1047 * @throws UnsupportedOperationException if the iterator does not support the
1048 * {@code remove} method and the iterable contains the object
1049 */
1050 static boolean remove(Iterable<?> iterable, @Nullable Object o) {
1051 Iterator<?> i = iterable.iterator();
1052 while (i.hasNext()) {
1053 if (Objects.equal(i.next(), o)) {
1054 i.remove();
1055 return true;
1056 }
1057 }
1058 return false;
1059 }
1060
1061 abstract static class IterableWithToString<E> implements Iterable<E> {
1062 @Override public String toString() {
1063 return Iterables.toString(this);
1064 }
1065 }
1066 }