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