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