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