001/*
002 * Licensed to the Apache Software Foundation (ASF) under one or more
003 * contributor license agreements.  See the NOTICE file distributed with
004 * this work for additional information regarding copyright ownership.
005 * The ASF licenses this file to You under the Apache License, Version 2.0
006 * (the "License"); you may not use this file except in compliance with
007 * the License.  You may obtain a copy of the License at
008 *
009 *      http://www.apache.org/licenses/LICENSE-2.0
010 *
011 * Unless required by applicable law or agreed to in writing, software
012 * distributed under the License is distributed on an "AS IS" BASIS,
013 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
014 * See the License for the specific language governing permissions and
015 * limitations under the License.
016 */
017package org.apache.commons.collections4;
018
019import java.util.ArrayList;
020import java.util.Collection;
021import java.util.Collections;
022import java.util.Comparator;
023import java.util.Iterator;
024import java.util.List;
025import java.util.Set;
026
027import org.apache.commons.collections4.functors.EqualPredicate;
028import org.apache.commons.collections4.iterators.LazyIteratorChain;
029import org.apache.commons.collections4.iterators.ReverseListIterator;
030import org.apache.commons.collections4.iterators.UniqueFilterIterator;
031
032/**
033 * Provides utility methods and decorators for {@link Iterable} instances.
034 * <p>
035 * <b>Note</b>: this util class has been designed for fail-fast argument checking.
036 * <ul>
037 * <li>
038 * all decorator methods are <b>NOT</b> null-safe wrt the provided Iterable argument, i.e.
039 * they will throw a {@link NullPointerException} if a null Iterable is passed as argument.
040 * <li>
041 * all other utility methods are null-safe wrt the provided Iterable argument, i.e. they will
042 * treat a null Iterable the same way as an empty one. Other arguments which are null,
043 * e.g. a {@link Predicate}, will result in a {@link NullPointerException}. Exception: passing
044 * a null {@link Comparator} is equivalent to a Comparator with natural ordering.
045 * </ul>
046 *
047 * @since 4.1
048 */
049public class IterableUtils {
050
051    /**
052     * An empty iterable.
053     */
054    @SuppressWarnings("rawtypes")
055    static final FluentIterable EMPTY_ITERABLE = new FluentIterable<Object>() {
056        @Override
057        public Iterator<Object> iterator() {
058            return IteratorUtils.emptyIterator();
059        }
060    };
061
062    // Empty
063    // ----------------------------------------------------------------------
064
065    /**
066     * Gets an empty iterable.
067     * <p>
068     * This iterable does not contain any elements.
069     *
070     * @param <E> the element type
071     * @return an empty iterable
072     */
073    @SuppressWarnings("unchecked") // OK, empty collection is compatible with any type
074    public static <E> Iterable<E> emptyIterable() {
075        return EMPTY_ITERABLE;
076    }
077
078    // Chained
079    // ----------------------------------------------------------------------
080
081    /**
082     * Combines two iterables into a single iterable.
083     * <p>
084     * The returned iterable has an iterator that traverses the elements in {@code a},
085     * followed by the elements in {@code b}. The source iterators are not polled until
086     * necessary.
087     * <p>
088     * The returned iterable's iterator supports {@code remove()} when the corresponding
089     * input iterator supports it.
090     *
091     * @param <E> the element type
092     * @param a  the first iterable, may not be null
093     * @param b  the second iterable, may not be null
094     * @return a new iterable, combining the provided iterables
095     * @throws NullPointerException if either a or b is null
096     */
097    @SuppressWarnings("unchecked")
098    public static <E> Iterable<E> chainedIterable(final Iterable<? extends E> a,
099                                                  final Iterable<? extends E> b) {
100        return chainedIterable(new Iterable[] {a, b});
101    }
102
103    /**
104     * Combines three iterables into a single iterable.
105     * <p>
106     * The returned iterable has an iterator that traverses the elements in {@code a},
107     * followed by the elements in {@code b} and {@code c}. The source iterators are
108     * not polled until necessary.
109     * <p>
110     * The returned iterable's iterator supports {@code remove()} when the corresponding
111     * input iterator supports it.
112     *
113     * @param <E> the element type
114     * @param a  the first iterable, may not be null
115     * @param b  the second iterable, may not be null
116     * @param c  the third iterable, may not be null
117     * @return a new iterable, combining the provided iterables
118     * @throws NullPointerException if either of the provided iterables is null
119     */
120    @SuppressWarnings("unchecked")
121    public static <E> Iterable<E> chainedIterable(final Iterable<? extends E> a,
122                                                  final Iterable<? extends E> b,
123                                                  final Iterable<? extends E> c) {
124        return chainedIterable(new Iterable[] {a, b, c});
125    }
126
127    /**
128     * Combines four iterables into a single iterable.
129     * <p>
130     * The returned iterable has an iterator that traverses the elements in {@code a},
131     * followed by the elements in {@code b}, {@code c} and {@code d}. The source
132     * iterators are not polled until necessary.
133     * <p>
134     * The returned iterable's iterator supports {@code remove()} when the corresponding
135     * input iterator supports it.
136     *
137     * @param <E> the element type
138     * @param a  the first iterable, may not be null
139     * @param b  the second iterable, may not be null
140     * @param c  the third iterable, may not be null
141     * @param d  the fourth iterable, may not be null
142     * @return a new iterable, combining the provided iterables
143     * @throws NullPointerException if either of the provided iterables is null
144     */
145    @SuppressWarnings("unchecked")
146    public static <E> Iterable<E> chainedIterable(final Iterable<? extends E> a,
147                                                  final Iterable<? extends E> b,
148                                                  final Iterable<? extends E> c,
149                                                  final Iterable<? extends E> d) {
150        return chainedIterable(new Iterable[] {a, b, c, d});
151    }
152
153    /**
154     * Combines the provided iterables into a single iterable.
155     * <p>
156     * The returned iterable has an iterator that traverses the elements in the order
157     * of the arguments, i.e. iterables[0], iterables[1], .... The source iterators
158     * are not polled until necessary.
159     * <p>
160     * The returned iterable's iterator supports {@code remove()} when the corresponding
161     * input iterator supports it.
162     *
163     * @param <E> the element type
164     * @param iterables  the iterables to combine, may not be null
165     * @return a new iterable, combining the provided iterables
166     * @throws NullPointerException if either of the provided iterables is null
167     */
168    public static <E> Iterable<E> chainedIterable(final Iterable<? extends E>... iterables) {
169        checkNotNull(iterables);
170        return new FluentIterable<E>() {
171            @Override
172            public Iterator<E> iterator() {
173                return new LazyIteratorChain<E>() {
174                    @Override
175                    protected Iterator<? extends E> nextIterator(final int count) {
176                        if (count > iterables.length) {
177                            return null;
178                        }
179                        return iterables[count - 1].iterator();
180                    }
181                };
182            }
183        };
184    }
185
186    // Collated
187    // ----------------------------------------------------------------------
188
189    /**
190     * Combines the two provided iterables into an ordered iterable using
191     * natural ordering.
192     * <p>
193     * The returned iterable's iterator supports {@code remove()} when the
194     * corresponding input iterator supports it.
195     *
196     * @param <E> the element type
197     * @param a  the first iterable, may not be null
198     * @param b  the second iterable, may not be null
199     * @return a filtered view on the specified iterable
200     * @throws NullPointerException if either of the provided iterables is null
201     */
202    public static <E> Iterable<E> collatedIterable(final Iterable<? extends E> a,
203                                                   final Iterable<? extends E> b) {
204        checkNotNull(a, b);
205        return new FluentIterable<E>() {
206            @Override
207            public Iterator<E> iterator() {
208                return IteratorUtils.collatedIterator(null, a.iterator(), b.iterator());
209            }
210        };
211    }
212
213    /**
214     * Combines the two provided iterables into an ordered iterable using the
215     * provided comparator. If the comparator is null, natural ordering will be
216     * used.
217     * <p>
218     * The returned iterable's iterator supports {@code remove()} when the
219     * corresponding input iterator supports it.
220     *
221     * @param <E> the element type
222     * @param comparator  the comparator defining an ordering over the elements,
223     *   may be null, in which case natural ordering will be used
224     * @param a  the first iterable, may not be null
225     * @param b  the second iterable, may not be null
226     * @return a filtered view on the specified iterable
227     * @throws NullPointerException if either of the provided iterables is null
228     */
229    public static <E> Iterable<E> collatedIterable(final Comparator<? super E> comparator,
230                                                   final Iterable<? extends E> a,
231                                                   final Iterable<? extends E> b) {
232        checkNotNull(a, b);
233        return new FluentIterable<E>() {
234            @Override
235            public Iterator<E> iterator() {
236                return IteratorUtils.collatedIterator(comparator, a.iterator(), b.iterator());
237            }
238        };
239    }
240
241    // Filtered
242    // ----------------------------------------------------------------------
243
244    /**
245     * Returns a view of the given iterable that only contains elements matching
246     * the provided predicate.
247     * <p>
248     * The returned iterable's iterator supports {@code remove()} when the
249     * corresponding input iterator supports it.
250     *
251     * @param <E> the element type
252     * @param iterable  the iterable to filter, may not be null
253     * @param predicate  the predicate used to filter elements, may not be null
254     * @return a filtered view on the specified iterable
255     * @throws NullPointerException if either iterable or predicate is null
256     */
257    public static <E> Iterable<E> filteredIterable(final Iterable<E> iterable,
258                                                   final Predicate<? super E> predicate) {
259        checkNotNull(iterable);
260        if (predicate == null) {
261            throw new NullPointerException("Predicate must not be null.");
262        }
263        return new FluentIterable<E>() {
264            @Override
265            public Iterator<E> iterator() {
266                return IteratorUtils.filteredIterator(emptyIteratorIfNull(iterable), predicate);
267            }
268        };
269    }
270
271    // Bounded
272    // ----------------------------------------------------------------------
273
274    /**
275     * Returns a view of the given iterable that contains at most the given number
276     * of elements.
277     * <p>
278     * The returned iterable's iterator supports {@code remove()} when the corresponding
279     * input iterator supports it.
280     *
281     * @param <E> the element type
282     * @param iterable  the iterable to limit, may not be null
283     * @param maxSize  the maximum number of elements, must not be negative
284     * @return a bounded view on the specified iterable
285     * @throws IllegalArgumentException if maxSize is negative
286     * @throws NullPointerException if iterable is null
287     */
288    public static <E> Iterable<E> boundedIterable(final Iterable<E> iterable, final long maxSize) {
289        checkNotNull(iterable);
290        if (maxSize < 0) {
291            throw new IllegalArgumentException("MaxSize parameter must not be negative.");
292        }
293
294        return new FluentIterable<E>() {
295            @Override
296            public Iterator<E> iterator() {
297                return IteratorUtils.boundedIterator(iterable.iterator(), maxSize);
298            }
299        };
300    }
301
302    // Looping
303    // ----------------------------------------------------------------------
304
305    /**
306     * Returns a view of the given iterable which will cycle infinitely over
307     * its elements.
308     * <p>
309     * The returned iterable's iterator supports {@code remove()} if
310     * {@code iterable.iterator()} does. After {@code remove()} is called, subsequent
311     * cycles omit the removed element, which is no longer in {@code iterable}. The
312     * iterator's {@code hasNext()} method returns {@code true} until {@code iterable}
313     * is empty.
314     *
315     * @param <E> the element type
316     * @param iterable  the iterable to loop, may not be null
317     * @return a view of the iterable, providing an infinite loop over its elements
318     * @throws NullPointerException if iterable is null
319     */
320    public static <E> Iterable<E> loopingIterable(final Iterable<E> iterable) {
321        checkNotNull(iterable);
322        return new FluentIterable<E>() {
323            @Override
324            public Iterator<E> iterator() {
325                return new LazyIteratorChain<E>() {
326                    @Override
327                    protected Iterator<? extends E> nextIterator(final int count) {
328                        if (IterableUtils.isEmpty(iterable)) {
329                            return null;
330                        }
331                        return iterable.iterator();
332                    }
333                };
334            }
335        };
336    }
337
338    // Reversed
339    // ----------------------------------------------------------------------
340
341    /**
342     * Returns a reversed view of the given iterable.
343     * <p>
344     * In case the provided iterable is a {@link List} instance, a
345     * {@link ReverseListIterator} will be used to reverse the traversal
346     * order, otherwise an intermediate {@link List} needs to be created.
347     * <p>
348     * The returned iterable's iterator supports {@code remove()} if the
349     * provided iterable is a {@link List} instance.
350     *
351     * @param <E> the element type
352     * @param iterable  the iterable to use, may not be null
353     * @return a reversed view of the specified iterable
354     * @throws NullPointerException if iterable is null
355     * @see ReverseListIterator
356     */
357    public static <E> Iterable<E> reversedIterable(final Iterable<E> iterable) {
358        checkNotNull(iterable);
359        return new FluentIterable<E>() {
360            @Override
361            public Iterator<E> iterator() {
362                final List<E> list = (iterable instanceof List<?>) ?
363                        (List<E>) iterable :
364                        IteratorUtils.toList(iterable.iterator());
365                return new ReverseListIterator<>(list);
366            }
367        };
368    }
369
370    // Skipping
371    // ----------------------------------------------------------------------
372
373    /**
374     * Returns a view of the given iterable that skips the first N elements.
375     * <p>
376     * The returned iterable's iterator supports {@code remove()} when the corresponding
377     * input iterator supports it.
378     *
379     * @param <E> the element type
380     * @param iterable  the iterable to use, may not be null
381     * @param elementsToSkip  the number of elements to skip from the start, must not be negative
382     * @return a view of the specified iterable, skipping the first N elements
383     * @throws IllegalArgumentException if elementsToSkip is negative
384     * @throws NullPointerException if iterable is null
385     */
386    public static <E> Iterable<E> skippingIterable(final Iterable<E> iterable, final long elementsToSkip) {
387        checkNotNull(iterable);
388        if (elementsToSkip < 0) {
389            throw new IllegalArgumentException("ElementsToSkip parameter must not be negative.");
390        }
391
392        return new FluentIterable<E>() {
393            @Override
394            public Iterator<E> iterator() {
395                return IteratorUtils.skippingIterator(iterable.iterator(), elementsToSkip);
396            }
397        };
398    }
399
400    // Transformed
401    // ----------------------------------------------------------------------
402
403    /**
404     * Returns a transformed view of the given iterable where all of its elements
405     * have been transformed by the provided transformer.
406     * <p>
407     * The returned iterable's iterator supports {@code remove()} when the corresponding
408     * input iterator supports it.
409     *
410     * @param <I>  the input element type
411     * @param <O>  the output element type
412     * @param iterable  the iterable to transform, may not be null
413     * @param transformer  the transformer, must not be null
414     * @return a transformed view of the specified iterable
415     * @throws NullPointerException if either iterable or transformer is null
416     */
417    public static <I, O> Iterable<O> transformedIterable(final Iterable<I> iterable,
418                                                         final Transformer<? super I, ? extends O> transformer) {
419        checkNotNull(iterable);
420        if (transformer == null) {
421            throw new NullPointerException("Transformer must not be null.");
422        }
423        return new FluentIterable<O>() {
424            @Override
425            public Iterator<O> iterator() {
426                return IteratorUtils.transformedIterator(iterable.iterator(), transformer);
427            }
428        };
429    }
430
431    // Unique
432    // ----------------------------------------------------------------------
433
434    /**
435     * Returns a unique view of the given iterable.
436     * <p>
437     * The returned iterable's iterator supports {@code remove()} when the
438     * corresponding input iterator supports it. Calling {@code remove()}
439     * will only remove a single element from the underlying iterator.
440     *
441     * @param <E> the element type
442     * @param iterable  the iterable to use, may not be null
443     * @return a unique view of the specified iterable
444     * @throws NullPointerException if iterable is null
445     */
446    public static <E> Iterable<E> uniqueIterable(final Iterable<E> iterable) {
447        checkNotNull(iterable);
448        return new FluentIterable<E>() {
449            @Override
450            public Iterator<E> iterator() {
451                return new UniqueFilterIterator<>(iterable.iterator());
452            }
453        };
454    }
455
456    // Unmodifiable
457    // ----------------------------------------------------------------------
458
459    /**
460     * Returns an unmodifiable view of the given iterable.
461     * <p>
462     * The returned iterable's iterator does not support {@code remove()}.
463     *
464     * @param <E> the element type
465     * @param iterable  the iterable to use, may not be null
466     * @return an unmodifiable view of the specified iterable
467     * @throws NullPointerException if iterable is null
468     */
469    public static <E> Iterable<E> unmodifiableIterable(final Iterable<E> iterable) {
470        checkNotNull(iterable);
471        if (iterable instanceof UnmodifiableIterable<?>) {
472            return iterable;
473        }
474        return new UnmodifiableIterable<>(iterable);
475    }
476
477    /**
478     * Inner class to distinguish unmodifiable instances.
479     */
480    private static final class UnmodifiableIterable<E> extends FluentIterable<E> {
481        private final Iterable<E> unmodifiable;
482
483        public UnmodifiableIterable(final Iterable<E> iterable) {
484            super();
485            this.unmodifiable = iterable;
486        }
487
488        @Override
489        public Iterator<E> iterator() {
490            return IteratorUtils.unmodifiableIterator(unmodifiable.iterator());
491        }
492    }
493
494    // Zipping
495    // ----------------------------------------------------------------------
496
497    /**
498     * Interleaves two iterables into a single iterable.
499     * <p>
500     * The returned iterable has an iterator that traverses the elements in {@code a}
501     * and {@code b} in alternating order. The source iterators are not polled until
502     * necessary.
503     * <p>
504     * The returned iterable's iterator supports {@code remove()} when the corresponding
505     * input iterator supports it.
506     *
507     * @param <E> the element type
508     * @param a  the first iterable, may not be null
509     * @param b  the second iterable, may not be null
510     * @return a new iterable, interleaving the provided iterables
511     * @throws NullPointerException if either a or b is null
512     */
513    public static <E> Iterable<E> zippingIterable(final Iterable<? extends E> a,
514                                                  final Iterable<? extends E> b) {
515        checkNotNull(a);
516        checkNotNull(b);
517        return new FluentIterable<E>() {
518            @Override
519            public Iterator<E> iterator() {
520                return IteratorUtils.zippingIterator(a.iterator(), b.iterator());
521            }
522        };
523    }
524
525    /**
526     * Interleaves two iterables into a single iterable.
527     * <p>
528     * The returned iterable has an iterator that traverses the elements in {@code a}
529     * and {@code b} in alternating order. The source iterators are not polled until
530     * necessary.
531     * <p>
532     * The returned iterable's iterator supports {@code remove()} when the corresponding
533     * input iterator supports it.
534     *
535     * @param <E> the element type
536     * @param first  the first iterable, may not be null
537     * @param others  the array of iterables to interleave, may not be null
538     * @return a new iterable, interleaving the provided iterables
539     * @throws NullPointerException if either of the provided iterables is null
540     */
541    public static <E> Iterable<E> zippingIterable(final Iterable<? extends E> first,
542                                                  final Iterable<? extends E>... others) {
543        checkNotNull(first);
544        checkNotNull(others);
545        return new FluentIterable<E>() {
546            @Override
547            public Iterator<E> iterator() {
548                @SuppressWarnings("unchecked") // safe
549                final
550                Iterator<? extends E>[] iterators = new Iterator[others.length + 1];
551                iterators[0] = first.iterator();
552                for (int i = 0; i < others.length; i++) {
553                    iterators[i + 1] = others[i].iterator();
554                }
555                return IteratorUtils.zippingIterator(iterators);
556            }
557        };
558    }
559
560    // Utility methods
561    // ----------------------------------------------------------------------
562
563    /**
564     * Returns an immutable empty iterable if the argument is null,
565     * or the argument itself otherwise.
566     *
567     * @param <E> the element type
568     * @param iterable  the iterable, may be null
569     * @return an empty iterable if the argument is null
570     */
571    public static <E> Iterable<E> emptyIfNull(final Iterable<E> iterable) {
572        return iterable == null ? IterableUtils.<E>emptyIterable() : iterable;
573    }
574
575    /**
576     * Applies the closure to each element of the provided iterable.
577     *
578     * @param <E> the element type
579     * @param iterable  the iterator to use, may be null
580     * @param closure  the closure to apply to each element, may not be null
581     * @throws NullPointerException if closure is null
582     */
583    public static <E> void forEach(final Iterable<E> iterable, final Closure<? super E> closure) {
584        IteratorUtils.forEach(emptyIteratorIfNull(iterable), closure);
585    }
586
587    /**
588     * Executes the given closure on each but the last element in the iterable.
589     * <p>
590     * If the input iterable is null no change is made.
591     *
592     * @param <E> the type of object the {@link Iterable} contains
593     * @param iterable  the iterable to get the input from, may be null
594     * @param closure  the closure to perform, may not be null
595     * @return the last element in the iterable, or null if iterable is null or empty
596     */
597    public static <E> E forEachButLast(final Iterable<E> iterable, final Closure<? super E> closure) {
598        return IteratorUtils.forEachButLast(emptyIteratorIfNull(iterable), closure);
599    }
600
601    /**
602     * Finds the first element in the given iterable which matches the given predicate.
603     * <p>
604     * A <code>null</code> or empty iterator returns null.
605     *
606     * @param <E> the element type
607     * @param iterable  the iterable to search, may be null
608     * @param predicate  the predicate to use, may not be null
609     * @return the first element of the iterable which matches the predicate or null if none could be found
610     * @throws NullPointerException if predicate is null
611     */
612    public static <E> E find(final Iterable<E> iterable, final Predicate<? super E> predicate) {
613        return IteratorUtils.find(emptyIteratorIfNull(iterable), predicate);
614    }
615
616    /**
617     * Returns the index of the first element in the specified iterable that
618     * matches the given predicate.
619     * <p>
620     * A <code>null</code> or empty iterable returns -1.
621     *
622     * @param <E> the element type
623     * @param iterable  the iterable to search, may be null
624     * @param predicate  the predicate to use, may not be null
625     * @return the index of the first element which matches the predicate or -1 if none matches
626     * @throws NullPointerException if predicate is null
627     */
628    public static <E> int indexOf(final Iterable<E> iterable, final Predicate<? super E> predicate) {
629        return IteratorUtils.indexOf(emptyIteratorIfNull(iterable), predicate);
630    }
631
632    /**
633     * Answers true if a predicate is true for every element of an iterable.
634     * <p>
635     * A <code>null</code> or empty iterable returns true.
636     *
637     * @param <E> the type of object the {@link Iterable} contains
638     * @param iterable  the {@link Iterable} to use, may be null
639     * @param predicate  the predicate to use, may not be null
640     * @return true if every element of the collection matches the predicate or if the
641     *   collection is empty, false otherwise
642     * @throws NullPointerException if predicate is null
643     */
644    public static <E> boolean matchesAll(final Iterable<E> iterable, final Predicate<? super E> predicate) {
645        return IteratorUtils.matchesAll(emptyIteratorIfNull(iterable), predicate);
646    }
647
648    /**
649     * Answers true if a predicate is true for any element of the iterable.
650     * <p>
651     * A <code>null</code> or empty iterable returns false.
652     *
653     * @param <E> the type of object the {@link Iterable} contains
654     * @param iterable  the {@link Iterable} to use, may be null
655     * @param predicate  the predicate to use, may not be null
656     * @return true if any element of the collection matches the predicate, false otherwise
657     * @throws NullPointerException if predicate is null
658     */
659    public static <E> boolean matchesAny(final Iterable<E> iterable, final Predicate<? super E> predicate) {
660        return IteratorUtils.matchesAny(emptyIteratorIfNull(iterable), predicate);
661    }
662
663    /**
664     * Counts the number of elements in the input iterable that match the predicate.
665     * <p>
666     * A <code>null</code> iterable matches no elements.
667     *
668     * @param <E> the type of object the {@link Iterable} contains
669     * @param input  the {@link Iterable} to get the input from, may be null
670     * @param predicate  the predicate to use, may not be null
671     * @return the number of matches for the predicate in the collection
672     * @throws NullPointerException if predicate is null
673     */
674    public static <E> long countMatches(final Iterable<E> input, final Predicate<? super E> predicate) {
675        if (predicate == null) {
676            throw new NullPointerException("Predicate must not be null.");
677        }
678        return size(filteredIterable(emptyIfNull(input), predicate));
679    }
680
681    /**
682     * Answers true if the provided iterable is empty.
683     * <p>
684     * A <code>null</code> iterable returns true.
685     *
686     * @param iterable  the {@link Iterable to use}, may be null
687     * @return true if the iterable is null or empty, false otherwise
688     */
689    public static boolean isEmpty(final Iterable<?> iterable) {
690        if (iterable instanceof Collection<?>) {
691            return ((Collection<?>) iterable).isEmpty();
692        }
693        return IteratorUtils.isEmpty(emptyIteratorIfNull(iterable));
694    }
695
696    /**
697     * Checks if the object is contained in the given iterable.
698     * <p>
699     * A <code>null</code> or empty iterable returns false.
700     *
701     * @param <E> the type of object the {@link Iterable} contains
702     * @param iterable  the iterable to check, may be null
703     * @param object  the object to check
704     * @return true if the object is contained in the iterable, false otherwise
705     */
706    public static <E> boolean contains(final Iterable<E> iterable, final Object object) {
707        if (iterable instanceof Collection<?>) {
708            return ((Collection<E>) iterable).contains(object);
709        }
710        return IteratorUtils.contains(emptyIteratorIfNull(iterable), object);
711    }
712
713    /**
714     * Checks if the object is contained in the given iterable. Object equality
715     * is tested with an {@code equator} unlike {@link #contains(Iterable, Object)}
716     * which uses {@link Object#equals(Object)}.
717     * <p>
718     * A <code>null</code> or empty iterable returns false.
719     * A <code>null</code> object will not be passed to the equator, instead a
720     * {@link org.apache.commons.collections4.functors.NullPredicate NullPredicate}
721     * will be used.
722     *
723     * @param <E> the type of object the {@link Iterable} contains
724     * @param iterable  the iterable to check, may be null
725     * @param object  the object to check
726     * @param equator  the equator to use to check, may not be null
727     * @return true if the object is contained in the iterable, false otherwise
728     * @throws NullPointerException if equator is null
729     */
730    public static <E> boolean contains(final Iterable<? extends E> iterable, final E object,
731                                       final Equator<? super E> equator) {
732        if (equator == null) {
733            throw new NullPointerException("Equator must not be null.");
734        }
735        return matchesAny(iterable, EqualPredicate.equalPredicate(object, equator));
736    }
737
738    /**
739     * Returns the number of occurrences of the provided object in the iterable.
740     *
741     * @param <E> the element type that the {@link Iterable} may contain
742     * @param <T> the element type of the object to find
743     * @param iterable  the {@link Iterable} to search
744     * @param obj  the object to find the cardinality of
745     * @return the number of occurrences of obj in iterable
746     */
747    public static <E, T extends E> int frequency(final Iterable<E> iterable, final T obj) {
748        if (iterable instanceof Set<?>) {
749            return ((Set<E>) iterable).contains(obj) ? 1 : 0;
750        }
751        if (iterable instanceof Bag<?>) {
752            return ((Bag<E>) iterable).getCount(obj);
753        }
754        return size(filteredIterable(emptyIfNull(iterable), EqualPredicate.<E>equalPredicate(obj)));
755    }
756
757    /**
758     * Returns the <code>index</code>-th value in the <code>iterable</code>'s {@link Iterator}, throwing
759     * <code>IndexOutOfBoundsException</code> if there is no such element.
760     * <p>
761     * If the {@link Iterable} is a {@link List}, then it will use {@link List#get(int)}.
762     *
763     * @param <T> the type of object in the {@link Iterable}.
764     * @param iterable  the {@link Iterable} to get a value from, may be null
765     * @param index  the index to get
766     * @return the object at the specified index
767     * @throws IndexOutOfBoundsException if the index is invalid
768     */
769    public static <T> T get(final Iterable<T> iterable, final int index) {
770        CollectionUtils.checkIndexBounds(index);
771        if (iterable instanceof List<?>) {
772            return ((List<T>) iterable).get(index);
773        }
774        return IteratorUtils.get(emptyIteratorIfNull(iterable), index);
775    }
776
777    /**
778     * Shortcut for {@code get(iterator, 0)}.
779     * <p>
780     * Returns the <code>first</code> value in the <code>iterable</code>'s {@link Iterator}, throwing
781     * <code>IndexOutOfBoundsException</code> if there is no such element.
782     * </p>
783     * <p>
784     * If the {@link Iterable} is a {@link List}, then it will use {@link List#get(int)}.
785     * </p>
786     *
787     * @param <T> the type of object in the {@link Iterable}.
788     * @param iterable  the {@link Iterable} to get a value from, may be null
789     * @return the first object
790     * @throws IndexOutOfBoundsException if the request  is invalid
791     * @since 4.2
792     */
793    public static <T> T first(final Iterable<T> iterable) {
794        return get(iterable, 0);
795    }
796
797    /**
798     * Returns the number of elements contained in the given iterator.
799     * <p>
800     * A <code>null</code> or empty iterator returns {@code 0}.
801     *
802     * @param iterable  the iterable to check, may be null
803     * @return the number of elements contained in the iterable
804     */
805    public static int size(final Iterable<?> iterable) {
806        if (iterable instanceof Collection<?>) {
807            return ((Collection<?>) iterable).size();
808        }
809        return IteratorUtils.size(emptyIteratorIfNull(iterable));
810    }
811
812    /**
813     * Partitions all elements from iterable into separate output collections,
814     * based on the evaluation of the given predicate.
815     * <p>
816     * For each predicate, the result will contain a list holding all elements of the
817     * input iterable matching the predicate. The last list will hold all elements
818     * which didn't match any predicate:
819     * <pre>
820     *  [C1, R] = partition(I, P1) with
821     *  I = input
822     *  P1 = first predicate
823     *  C1 = collection of elements matching P1
824     *  R = collection of elements rejected by all predicates
825     * </pre>
826     * <p>
827     * If the input iterable is <code>null</code>, the same is returned as for an
828     * empty iterable.
829     * <p>
830     * Example: for an input list [1, 2, 3, 4, 5] calling partition with a predicate [x &lt; 3]
831     * will result in the following output: [[1, 2], [3, 4, 5]].
832     *
833     * @param <O>  the type of object the {@link Iterable} contains
834     * @param iterable  the iterable to partition, may be null
835     * @param predicate  the predicate to use, may not be null
836     * @return a list containing the output collections
837     * @throws NullPointerException if predicate is null
838     */
839    public static <O> List<List<O>> partition(final Iterable<? extends O> iterable,
840                                              final Predicate<? super O> predicate) {
841        if (predicate == null) {
842            throw new NullPointerException("Predicate must not be null.");
843        }
844        @SuppressWarnings({ "unchecked", "rawtypes" }) // safe
845        final Factory<List<O>> factory = FactoryUtils.instantiateFactory((Class) ArrayList.class);
846        @SuppressWarnings("unchecked") // safe
847        final Predicate<? super O>[] predicates = new Predicate[] { predicate };
848        return partition(iterable, factory, predicates);
849    }
850
851    /**
852     * Partitions all elements from iterable into separate output collections,
853     * based on the evaluation of the given predicates.
854     * <p>
855     * For each predicate, the result will contain a list holding all elements of the
856     * input iterable matching the predicate. The last list will hold all elements
857     * which didn't match any predicate:
858     * <pre>
859     *  [C1, C2, R] = partition(I, P1, P2) with
860     *  I = input
861     *  P1 = first predicate
862     *  P2 = second predicate
863     *  C1 = collection of elements matching P1
864     *  C2 = collection of elements matching P2
865     *  R = collection of elements rejected by all predicates
866     * </pre>
867     * <p>
868     * <b>Note</b>: elements are only added to the output collection of the first matching
869     * predicate, determined by the order of arguments.
870     * <p>
871     * If the input iterable is <code>null</code>, the same is returned as for an
872     * empty iterable.
873     * <p>
874     * Example: for an input list [1, 2, 3, 4, 5] calling partition with predicates [x &lt; 3]
875     * and [x &lt; 5] will result in the following output: [[1, 2], [3, 4], [5]].
876     *
877     * @param <O>  the type of object the {@link Iterable} contains
878     * @param iterable  the collection to get the input from, may be null
879     * @param predicates  the predicates to use, may not be null
880     * @return a list containing the output collections
881     * @throws NullPointerException if any predicate is null
882     */
883    public static <O> List<List<O>> partition(final Iterable<? extends O> iterable,
884                                              final Predicate<? super O>... predicates) {
885
886        @SuppressWarnings({ "unchecked", "rawtypes" }) // safe
887        final Factory<List<O>> factory = FactoryUtils.instantiateFactory((Class) ArrayList.class);
888        return partition(iterable, factory, predicates);
889    }
890
891    /**
892     * Partitions all elements from iterable into separate output collections,
893     * based on the evaluation of the given predicates.
894     * <p>
895     * For each predicate, the returned list will contain a collection holding
896     * all elements of the input iterable matching the predicate. The last collection
897     * contained in the list will hold all elements which didn't match any predicate:
898     * <pre>
899     *  [C1, C2, R] = partition(I, P1, P2) with
900     *  I = input
901     *  P1 = first predicate
902     *  P2 = second predicate
903     *  C1 = collection of elements matching P1
904     *  C2 = collection of elements matching P2
905     *  R = collection of elements rejected by all predicates
906     * </pre>
907     * <p>
908     * <b>Note</b>: elements are only added to the output collection of the first matching
909     * predicate, determined by the order of arguments.
910     * <p>
911     * If the input iterable is <code>null</code>, the same is returned as for an
912     * empty iterable.
913     * If no predicates have been provided, all elements of the input collection
914     * will be added to the rejected collection.
915     * <p>
916     * Example: for an input list [1, 2, 3, 4, 5] calling partition with predicates [x &lt; 3]
917     * and [x &lt; 5] will result in the following output: [[1, 2], [3, 4], [5]].
918     *
919     * @param <O>  the type of object the {@link Iterable} contains
920     * @param <R>  the type of the output {@link Collection}
921     * @param iterable  the collection to get the input from, may be null
922     * @param partitionFactory  the factory used to create the output collections
923     * @param predicates  the predicates to use, may not be null
924     * @return a list containing the output collections
925     * @throws NullPointerException if any predicate is null
926     */
927    public static <O, R extends Collection<O>> List<R> partition(final Iterable<? extends O> iterable,
928            final Factory<R> partitionFactory, final Predicate<? super O>... predicates) {
929
930        if (iterable == null) {
931            final Iterable<O> empty = emptyIterable();
932            return partition(empty, partitionFactory, predicates);
933        }
934
935        if (predicates == null) {
936            throw new NullPointerException("Predicates must not be null.");
937        }
938
939        for (final Predicate<?> p : predicates) {
940            if (p == null) {
941                throw new NullPointerException("Predicate must not be null.");
942            }
943        }
944
945        if (predicates.length < 1) {
946            // return the entire input collection as a single partition
947            final R singlePartition = partitionFactory.create();
948            CollectionUtils.addAll(singlePartition, iterable);
949            return Collections.singletonList(singlePartition);
950        }
951
952        // create the empty partitions
953        final int numberOfPredicates = predicates.length;
954        final int numberOfPartitions = numberOfPredicates + 1;
955        final List<R> partitions = new ArrayList<>(numberOfPartitions);
956        for (int i = 0; i < numberOfPartitions; ++i) {
957            partitions.add(partitionFactory.create());
958        }
959
960        // for each element in inputCollection:
961        // find the first predicate that evaluates to true.
962        // if there is a predicate, add the element to the corresponding partition.
963        // if there is no predicate, add it to the last, catch-all partition.
964        for (final O element : iterable) {
965            boolean elementAssigned = false;
966            for (int i = 0; i < numberOfPredicates; ++i) {
967                if (predicates[i].evaluate(element)) {
968                    partitions.get(i).add(element);
969                    elementAssigned = true;
970                    break;
971                }
972            }
973
974            if (!elementAssigned) {
975                // no predicates evaluated to true
976                // add element to last partition
977                partitions.get(numberOfPredicates).add(element);
978            }
979        }
980
981        return partitions;
982    }
983
984    /**
985     * Gets a new list with the contents of the provided iterable.
986     *
987     * @param <E> the element type
988     * @param iterable  the iterable to use, may be null
989     * @return a list of the iterator contents
990     */
991    public static <E> List<E> toList(final Iterable<E> iterable) {
992        return IteratorUtils.toList(emptyIteratorIfNull(iterable));
993    }
994
995    /**
996     * Returns a string representation of the elements of the specified iterable.
997     * <p>
998     * The string representation consists of a list of the iterable's elements,
999     * enclosed in square brackets ({@code "[]"}). Adjacent elements are separated
1000     * by the characters {@code ", "} (a comma followed by a space). Elements are
1001     * converted to strings as by {@code String.valueOf(Object)}.
1002     *
1003     * @param <E> the element type
1004     * @param iterable  the iterable to convert to a string, may be null
1005     * @return a string representation of {@code iterable}
1006     */
1007    public static <E> String toString(final Iterable<E> iterable) {
1008        return IteratorUtils.toString(emptyIteratorIfNull(iterable));
1009    }
1010
1011    /**
1012     * Returns a string representation of the elements of the specified iterable.
1013     * <p>
1014     * The string representation consists of a list of the iterable's elements,
1015     * enclosed in square brackets ({@code "[]"}). Adjacent elements are separated
1016     * by the characters {@code ", "} (a comma followed by a space). Elements are
1017     * converted to strings as by using the provided {@code transformer}.
1018     *
1019     * @param <E> the element type
1020     * @param iterable  the iterable to convert to a string, may be null
1021     * @param transformer  the transformer used to get a string representation of an element
1022     * @return a string representation of {@code iterable}
1023     * @throws NullPointerException if {@code transformer} is null
1024     */
1025    public static <E> String toString(final Iterable<E> iterable,
1026                                      final Transformer<? super E, String> transformer) {
1027        if (transformer == null) {
1028            throw new NullPointerException("Transformer must not be null.");
1029        }
1030        return IteratorUtils.toString(emptyIteratorIfNull(iterable), transformer);
1031    }
1032
1033    /**
1034     * Returns a string representation of the elements of the specified iterable.
1035     * <p>
1036     * The string representation consists of a list of the iterable's elements,
1037     * enclosed by the provided {@code prefix} and {@code suffix}. Adjacent elements
1038     * are separated by the provided {@code delimiter}. Elements are converted to
1039     * strings as by using the provided {@code transformer}.
1040     *
1041     * @param <E> the element type
1042     * @param iterable  the iterable to convert to a string, may be null
1043     * @param transformer  the transformer used to get a string representation of an element
1044     * @param delimiter  the string to delimit elements
1045     * @param prefix  the prefix, prepended to the string representation
1046     * @param suffix  the suffix, appended to the string representation
1047     * @return a string representation of {@code iterable}
1048     * @throws NullPointerException if either transformer, delimiter, prefix or suffix is null
1049     */
1050    public static <E> String toString(final Iterable<E> iterable,
1051                                      final Transformer<? super E, String> transformer,
1052                                      final String delimiter,
1053                                      final String prefix,
1054                                      final String suffix) {
1055        return IteratorUtils.toString(emptyIteratorIfNull(iterable),
1056                                      transformer, delimiter, prefix, suffix);
1057    }
1058
1059    // Helper methods
1060    // ----------------------------------------------------------------------
1061
1062    /**
1063     * Fail-fast check for null arguments.
1064     *
1065     * @param iterable  the iterable to check
1066     * @throws NullPointerException if iterable is null
1067     */
1068    static void checkNotNull(final Iterable<?> iterable) {
1069        if (iterable == null) {
1070            throw new NullPointerException("Iterable must not be null.");
1071        }
1072    }
1073
1074    /**
1075     * Fail-fast check for null arguments.
1076     *
1077     * @param iterables  the iterables to check
1078     * @throws NullPointerException if the argument or any of its contents is null
1079     */
1080    static void checkNotNull(final Iterable<?>... iterables) {
1081        if (iterables == null) {
1082            throw new NullPointerException("Iterables must not be null.");
1083        }
1084        for (final Iterable<?> iterable : iterables) {
1085            checkNotNull(iterable);
1086        }
1087    }
1088
1089    /**
1090     * Returns an empty iterator if the argument is <code>null</code>,
1091     * or {@code iterable.iterator()} otherwise.
1092     *
1093     * @param <E> the element type
1094     * @param iterable  the iterable, possibly <code>null</code>
1095     * @return an empty iterator if the argument is <code>null</code>
1096     */
1097    private static <E> Iterator<E> emptyIteratorIfNull(final Iterable<E> iterable) {
1098        return iterable != null ? iterable.iterator() : IteratorUtils.<E>emptyIterator();
1099    }
1100
1101}