    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.lang.reflect.Array;
    020import java.util.ArrayList;
    021import java.util.Collection;
    022import java.util.Collections;
    023import java.util.Comparator;
    024import java.util.Enumeration;
    025import java.util.HashMap;
    026import java.util.HashSet;
    027import java.util.Iterator;
    028import java.util.List;
    029import java.util.ListIterator;
    030import java.util.Map;
    031import java.util.Objects;
    032import java.util.Set;
    033
    034import org.apache.commons.collections4.bag.HashBag;
    035import org.apache.commons.collections4.collection.PredicatedCollection;
    036import org.apache.commons.collections4.collection.SynchronizedCollection;
    037import org.apache.commons.collections4.collection.TransformedCollection;
    038import org.apache.commons.collections4.collection.UnmodifiableBoundedCollection;
    039import org.apache.commons.collections4.collection.UnmodifiableCollection;
    040import org.apache.commons.collections4.functors.TruePredicate;
    041import org.apache.commons.collections4.iterators.CollatingIterator;
    042import org.apache.commons.collections4.iterators.PermutationIterator;
    043
    044/**
    045 * Provides utility methods and decorators for {@link Collection} instances.
    046 * <p>
    047 * Various utility methods might put the input objects into a Set/Map/Bag. In case
    048 * the input objects override {@link Object#equals(Object)}, it is mandatory that
    049 * the general contract of the {@link Object#hashCode()} method is maintained.
    050 * </p>
    051 * <p>
    052 * NOTE: From 4.0, method parameters will take {@link Iterable} objects when possible.
    053 * </p>
    054 *
    055 * @since 1.0
    056 */
    057public class CollectionUtils {
    058
    059    /**
    060     * Helper class to easily access cardinality properties of two collections.
    061     * @param <O>  the element type
    062     */
    063    private static class CardinalityHelper<O> {
    064
    065        static boolean equals(final Collection<?> a, final Collection<?> b) {
    066            return new HashBag<>(a).equals(new HashBag<>(b));
    067        }
    068
    069        /** Contains the cardinality for each object in collection A. */
    070        final Bag<O> cardinalityA;
    071
    072        /** Contains the cardinality for each object in collection B. */
    073        final Bag<O> cardinalityB;
    074
    075        /**
    076         * Creates a new CardinalityHelper for two collections.
    077         *
    078         * @param a  the first collection
    079         * @param b  the second collection
    080         */
    081        CardinalityHelper(final Iterable<? extends O> a, final Iterable<? extends O> b) {
    082            cardinalityA = new HashBag<>(a);
    083            cardinalityB = new HashBag<>(b);
    084        }
    085
    086        /**
    087         * Gets the frequency of this object in collection A.
    088         *
    089         * @param key the key whose associated frequency is to be returned.
    090         * @return the frequency of the object in collection A
    091         */
    092        public int freqA(final Object key) {
    093            return getFreq(key, cardinalityA);
    094        }
    095
    096        /**
    097         * Gets the frequency of this object in collection B.
    098         *
    099         * @param key the key whose associated frequency is to be returned.
    100         * @return the frequency of the object in collection B
    101         */
    102        public int freqB(final Object key) {
    103            return getFreq(key, cardinalityB);
    104        }
    105
    106        private int getFreq(final Object key, final Bag<?> freqMap) {
    107            return freqMap.getCount(key);
    108        }
    109
    110        /**
    111         * Gets the maximum frequency of an object.
    112         *
    113         * @param obj  the object
    114         * @return the maximum frequency of the object
    115         */
    116        public final int max(final Object obj) {
    117            return Math.max(freqA(obj), freqB(obj));
    118        }
    119
    120        /**
    121         * Gets the minimum frequency of an object.
    122         *
    123         * @param obj  the object
    124         * @return the minimum frequency of the object
    125         */
    126        public final int min(final Object obj) {
    127            return Math.min(freqA(obj), freqB(obj));
    128        }
    129    }
    130
    131    /**
    132     * Wraps another object and uses the provided Equator to implement
    133     * {@link #equals(Object)} and {@link #hashCode()}.
    134     * <p>
    135     * This class can be used to store objects into a Map.
    136     * </p>
    137     *
    138     * @param <O>  the element type
    139     * @since 4.0
    140     */
    141    private static final class EquatorWrapper<O> {
    142        private final Equator<? super O> equator;
    143        private final O object;
    144
    145        EquatorWrapper(final Equator<? super O> equator, final O object) {
    146            this.equator = equator;
    147            this.object = object;
    148        }
    149
    150        @Override
    151        public boolean equals(final Object obj) {
    152            if (!(obj instanceof EquatorWrapper)) {
    153                return false;
    154            }
    155            @SuppressWarnings("unchecked")
    156            final EquatorWrapper<O> otherObj = (EquatorWrapper<O>) obj;
    157            return equator.equate(object, otherObj.getObject());
    158        }
    159
    160        public O getObject() {
    161            return object;
    162        }
    163
    164        @Override
    165        public int hashCode() {
    166            return equator.hash(object);
    167        }
    168    }
    169
    170    /**
    171     * Helper class for set-related operations, e.g. union, subtract, intersection.
    172     * @param <O>  the element type
    173     */
    174    private static final class SetOperationCardinalityHelper<O> extends CardinalityHelper<O> implements Iterable<O> {
    175
    176        /** Contains the unique elements of the two collections. */
    177        private final Set<O> elements;
    178
    179        /** Output collection. */
    180        private final List<O> newList;
    181
    182        /**
    183         * Create a new set operation helper from the two collections.
    184         * @param a  the first collection
    185         * @param b  the second collection
    186         */
    187        SetOperationCardinalityHelper(final Iterable<? extends O> a, final Iterable<? extends O> b) {
    188            super(a, b);
    189            elements = new HashSet<>();
    190            addAll(elements, a);
    191            addAll(elements, b);
    192            // the resulting list must contain at least each unique element, but may grow
    193            newList = new ArrayList<>(elements.size());
    194        }
    195
    196        @Override
    197        public Iterator<O> iterator() {
    198            return elements.iterator();
    199        }
    200
    201        /**
    202         * Returns the resulting collection.
    203         * @return the result
    204         */
    205        public Collection<O> list() {
    206            return newList;
    207        }
    208
    209        /**
    210         * Add the object {@code count} times to the result collection.
    211         * @param obj  the object to add
    212         * @param count  the count
    213         */
    214        public void setCardinality(final O obj, final int count) {
    215            for (int i = 0; i < count; i++) {
    216                newList.add(obj);
    217            }
    218        }
    219
    220    }
    221
    222    /**
    223     * The index value when an element is not found in a collection or array: {@code -1}.
    224     *
    225     * @since 4.5.0-M1
    226     */
    227    public static final int INDEX_NOT_FOUND = -1;
    228
    229    /**
    230     * Default prefix used while converting an Iterator to its String representation.
    231     *
    232     * @since 4.5.0-M1
    233     */
    234    public static final String DEFAULT_TOSTRING_PREFIX = "[";
    235
    236    /**
    237     * Default suffix used while converting an Iterator to its String representation.
    238     *
    239     * @since 4.5.0-M1
    240     */
    241    public static final String DEFAULT_TOSTRING_SUFFIX = "]";
    242
    243    /**
    244     * A String for Colon  (":").
    245     *
    246     * @since 4.5.0-M1
    247     */
    248    public static final String COLON = ":";
    249
    250    /**
    251     * A String for Comma (",").
    252     *
    253     * @since 4.5.0-M1
    254     */
    255    public static final String COMMA = ",";
    256
    257    /**
    258     * An empty unmodifiable collection.
    259     * The JDK provides empty Set and List implementations which could be used for
    260     * this purpose. However they could be cast to Set or List which might be
    261     * undesirable. This implementation only implements Collection.
    262     */
    263    @SuppressWarnings("rawtypes") // we deliberately use the raw type here
    264    public static final Collection EMPTY_COLLECTION = Collections.emptyList();
    265
    266    /**
    267     * Adds all elements in the array to the given collection.
    268     *
    269     * @param <C>  the type of object the {@link Collection} contains
    270     * @param collection  the collection to add to, must not be null
    271     * @param elements  the array of elements to add, must not be null
    272     * @return {@code true} if the collection was changed, {@code false} otherwise
    273     * @throws NullPointerException if the collection or elements is null
    274     */
    275    public static <C> boolean addAll(final Collection<C> collection, final C... elements) {
    276        Objects.requireNonNull(collection, "collection");
    277        Objects.requireNonNull(elements, "elements");
    278        boolean changed = false;
    279        for (final C element : elements) {
    280            changed |= collection.add(element);
    281        }
    282        return changed;
    283    }
    284
    285    /**
    286     * Adds all elements in the enumeration to the given collection.
    287     *
    288     * @param <C>  the type of object the {@link Collection} contains
    289     * @param collection  the collection to add to, must not be null
    290     * @param enumeration  the enumeration of elements to add, must not be null
    291     * @return {@code true} if the collections was changed, {@code false} otherwise
    292     * @throws NullPointerException if the collection or enumeration is null
    293     */
    294    public static <C> boolean addAll(final Collection<C> collection, final Enumeration<? extends C> enumeration) {
    295        Objects.requireNonNull(collection, "collection");
    296        Objects.requireNonNull(enumeration, "enumeration");
    297        boolean changed = false;
    298        while (enumeration.hasMoreElements()) {
    299            changed |= collection.add(enumeration.nextElement());
    300        }
    301        return changed;
    302    }
    303
    304    /**
    305     * Adds all elements in the {@link Iterable} to the given collection. If the
    306     * {@link Iterable} is a {@link Collection} then it is cast and will be
    307     * added using {@link Collection#addAll(Collection)} instead of iterating.
    308     *
    309     * @param <C>  the type of object the {@link Collection} contains
    310     * @param collection  the collection to add to, must not be null
    311     * @param iterable  the iterable of elements to add, must not be null
    312     * @return a boolean indicating whether the collection has changed or not.
    313     * @throws NullPointerException if the collection or iterable is null
    314     */
    315    public static <C> boolean addAll(final Collection<C> collection, final Iterable<? extends C> iterable) {
    316        Objects.requireNonNull(collection, "collection");
    317        Objects.requireNonNull(iterable, "iterable");
    318        if (iterable instanceof Collection<?>) {
    319            return collection.addAll((Collection<? extends C>) iterable);
    320        }
    321        return addAll(collection, iterable.iterator());
    322    }
    323
    324    /**
    325     * Adds all elements in the iteration to the given collection.
    326     *
    327     * @param <C>  the type of object the {@link Collection} contains
    328     * @param collection  the collection to add to, must not be null
    329     * @param iterator  the iterator of elements to add, must not be null
    330     * @return a boolean indicating whether the collection has changed or not.
    331     * @throws NullPointerException if the collection or iterator is null
    332     */
    333    public static <C> boolean addAll(final Collection<C> collection, final Iterator<? extends C> iterator) {
    334        Objects.requireNonNull(collection, "collection");
    335        Objects.requireNonNull(iterator, "iterator");
    336        boolean changed = false;
    337        while (iterator.hasNext()) {
    338            changed |= collection.add(iterator.next());
    339        }
    340        return changed;
    341    }
    342
    343    /**
    344     * Adds an element to the collection unless the element is null.
    345     *
    346     * @param <T>  the type of object the {@link Collection} contains
    347     * @param collection  the collection to add to, must not be null
    348     * @param object  the object to add, if null it will not be added
    349     * @return true if the collection changed
    350     * @throws NullPointerException if the collection is null
    351     * @since 3.2
    352     */
    353    public static <T> boolean addIgnoreNull(final Collection<T> collection, final T object) {
    354        Objects.requireNonNull(collection, "collection");
    355        return object != null && collection.add(object);
    356    }
    357
    358    /**
    359     * Returns the number of occurrences of <em>obj</em> in <em>coll</em>.
    360     *
    361     * @param obj the object to find the cardinality of
    362     * @param collection the {@link Iterable} to search
    363     * @param <O> the type of object that the {@link Iterable} may contain.
    364     * @return the number of occurrences of obj in coll
    365     * @throws NullPointerException if collection is null
    366     * @deprecated since 4.1, use {@link IterableUtils#frequency(Iterable, Object)} instead.
    367     *   Be aware that the order of parameters has changed.
    368     */
    369    @Deprecated
    370    public static <O> int cardinality(final O obj, final Iterable<? super O> collection) {
    371        return IterableUtils.frequency(Objects.requireNonNull(collection, "collection"), obj);
    372    }
    373
    374    /**
    375     * Ensures an index is not negative.
    376     * @param index the index to check.
    377     * @throws IndexOutOfBoundsException if the index is negative.
    378     */
    379    static void checkIndexBounds(final int index) {
    380        if (index < 0) {
    381            throw new IndexOutOfBoundsException("Index cannot be negative: " + index);
    382        }
    383    }
    384
    385    /**
    386     * Merges two sorted Collections, a and b, into a single, sorted List
    387     * such that the natural ordering of the elements is retained.
    388     * <p>
    389     * Uses the standard O(n) merge algorithm for combining two sorted lists.
    390     * </p>
    391     *
    392     * @param <O>  the element type
    393     * @param a  the first collection, must not be null
    394     * @param b  the second collection, must not be null
    395     * @return a new sorted List, containing the elements of Collection a and b
    396     * @throws NullPointerException if either collection is null
    397     * @since 4.0
    398     */
    399    public static <O extends Comparable<? super O>> List<O> collate(final Iterable<? extends O> a,
    400                                                                    final Iterable<? extends O> b) {
    401        return collate(a, b, ComparatorUtils.<O>naturalComparator(), true);
    402    }
    403
    404    /**
    405     * Merges two sorted Collections, a and b, into a single, sorted List
    406     * such that the natural ordering of the elements is retained.
    407     * <p>
    408     * Uses the standard O(n) merge algorithm for combining two sorted lists.
    409     * </p>
    410     *
    411     * @param <O>  the element type
    412     * @param a  the first collection, must not be null
    413     * @param b  the second collection, must not be null
    414     * @param includeDuplicates  if {@code true} duplicate elements will be retained, otherwise
    415     *   they will be removed in the output collection
    416     * @return a new sorted List, containing the elements of Collection a and b
    417     * @throws NullPointerException if either collection is null
    418     * @since 4.0
    419     */
    420    public static <O extends Comparable<? super O>> List<O> collate(final Iterable<? extends O> a,
    421                                                                    final Iterable<? extends O> b,
    422                                                                    final boolean includeDuplicates) {
    423        return collate(a, b, ComparatorUtils.<O>naturalComparator(), includeDuplicates);
    424    }
    425
    426    /**
    427     * Merges two sorted Collections, a and b, into a single, sorted List
    428     * such that the ordering of the elements according to Comparator c is retained.
    429     * <p>
    430     * Uses the standard O(n) merge algorithm for combining two sorted lists.
    431     * </p>
    432     *
    433     * @param <O>  the element type
    434     * @param a  the first collection, must not be null
    435     * @param b  the second collection, must not be null
    436     * @param c  the comparator to use for the merge.
    437     * @return a new sorted List, containing the elements of Collection a and b
    438     * @throws NullPointerException if either collection or the comparator is null
    439     * @since 4.0
    440     */
    441    public static <O> List<O> collate(final Iterable<? extends O> a, final Iterable<? extends O> b,
    442                                      final Comparator<? super O> c) {
    443        return collate(a, b, c, true);
    444    }
    445
    446    /**
    447     * Merges two sorted Collections, a and b, into a single, sorted List
    448     * such that the ordering of the elements according to Comparator c is retained.
    449     * <p>
    450     * Uses the standard O(n) merge algorithm for combining two sorted lists.
    451     * </p>
    452     *
    453     * @param <O>  the element type
    454     * @param iterableA  the first collection, must not be null
    455     * @param iterableB  the second collection, must not be null
    456     * @param comparator  the comparator to use for the merge.
    457     * @param includeDuplicates  if {@code true} duplicate elements will be retained, otherwise
    458     *   they will be removed in the output collection
    459     * @return a new sorted List, containing the elements of Collection a and b
    460     * @throws NullPointerException if either collection or the comparator is null
    461     * @since 4.0
    462     */
    463    public static <O> List<O> collate(final Iterable<? extends O> iterableA, final Iterable<? extends O> iterableB,
    464                                      final Comparator<? super O> comparator, final boolean includeDuplicates) {
    465        Objects.requireNonNull(iterableA, "iterableA");
    466        Objects.requireNonNull(iterableB, "iterableB");
    467        Objects.requireNonNull(comparator, "comparator");
    468        // if both Iterables are a Collection, we can estimate the size
    469        final int totalSize = iterableA instanceof Collection<?> && iterableB instanceof Collection<?> ?
    470                Math.max(1, ((Collection<?>) iterableA).size() + ((Collection<?>) iterableB).size()) : 10;
    471
    472        final Iterator<O> iterator = new CollatingIterator<>(comparator, iterableA.iterator(), iterableB.iterator());
    473        if (includeDuplicates) {
    474            return IteratorUtils.toList(iterator, totalSize);
    475        }
    476        final ArrayList<O> mergedList = new ArrayList<>(totalSize);
    477        O lastItem = null;
    478        while (iterator.hasNext()) {
    479            final O item = iterator.next();
    480            if (lastItem == null || !lastItem.equals(item)) {
    481                mergedList.add(item);
    482            }
    483            lastItem = item;
    484        }
    485        mergedList.trimToSize();
    486        return mergedList;
    487    }
    488
    489    /**
    490     * Transforms all elements from input collection with the given transformer
    491     * and adds them to the output collection.
    492     * <p>
    493     * If the input collection or transformer is null, there is no change to the
    494     * output collection.
    495     * </p>
    496     *
    497     * @param <I>  the type of object in the input collection
    498     * @param <O>  the type of object in the output collection
    499     * @param <R>  the type of the output collection
    500     * @param inputCollection  the collection to get the input from, may be null
    501     * @param transformer  the transformer to use, may be null
    502     * @param outputCollection  the collection to output into, may not be null if inputCollection
    503     *   and transformer are not null
    504     * @return the output collection with the transformed input added
    505     * @throws NullPointerException if the outputCollection is null and both, inputCollection and
    506     *   transformer are not null
    507     */
    508    public static <I, O, R extends Collection<? super O>> R collect(final Iterable<? extends I> inputCollection,
    509            final Transformer<? super I, ? extends O> transformer, final R outputCollection) {
    510        if (inputCollection != null) {
    511            return collect(inputCollection.iterator(), transformer, outputCollection);
    512        }
    513        return outputCollection;
    514    }
    515
    516    /**
    517     * Returns a new Collection containing all elements of the input collection
    518     * transformed by the given transformer.
    519     * <p>
    520     * If the input collection or transformer is null, the result is an empty list.
    521     * </p>
    522     *
    523     * @param <I>  the type of object in the input collection
    524     * @param <O>  the type of object in the output collection
    525     * @param inputCollection  the collection to get the input from, may not be null
    526     * @param transformer  the transformer to use, may be null
    527     * @return the transformed result (new list)
    528     * @throws NullPointerException if the outputCollection is null and both, inputCollection and
    529     *   transformer are not null
    530     */
    531    public static <I, O> Collection<O> collect(final Iterable<I> inputCollection,
    532                                               final Transformer<? super I, ? extends O> transformer) {
    533        int size = 0;
    534        if (null != inputCollection) {
    535            size = inputCollection instanceof Collection<?> ? ((Collection<?>) inputCollection).size() : 0;
    536        }
    537        final Collection<O> answer = size == 0 ? new ArrayList<>() : new ArrayList<>(size);
    538        return collect(inputCollection, transformer, answer);
    539    }
    540
    541    /**
    542     * Transforms all elements from the input iterator with the given transformer
    543     * and adds them to the output collection.
    544     * <p>
    545     * If the input iterator or transformer is null, there is no change to the
    546     * output collection.
    547     * </p>
    548     *
    549     * @param <I>  the type of object in the input collection
    550     * @param <O>  the type of object in the output collection
    551     * @param <R>  the type of the output collection
    552     * @param inputIterator  the iterator to get the input from, may be null
    553     * @param transformer  the transformer to use, may be null
    554     * @param outputCollection  the collection to output into, may not be null if inputIterator
    555     *   and transformer are not null
    556     * @return the outputCollection with the transformed input added
    557     * @throws NullPointerException if the output collection is null and both, inputIterator and
    558     *   transformer are not null
    559     */
    560    public static <I, O, R extends Collection<? super O>> R collect(final Iterator<? extends I> inputIterator,
    561            final Transformer<? super I, ? extends O> transformer, final R outputCollection) {
    562        if (inputIterator != null && transformer != null) {
    563            while (inputIterator.hasNext()) {
    564                final I item = inputIterator.next();
    565                final O value = transformer.apply(item);
    566                outputCollection.add(value);
    567            }
    568        }
    569        return outputCollection;
    570    }
    571
    572    /**
    573     * Transforms all elements from the input iterator with the given transformer
    574     * and adds them to the output collection.
    575     * <p>
    576     * If the input iterator or transformer is null, the result is an empty list.
    577     * </p>
    578     *
    579     * @param <I>  the type of object in the input collection
    580     * @param <O>  the type of object in the output collection
    581     * @param inputIterator  the iterator to get the input from, may be null
    582     * @param transformer  the transformer to use, may be null
    583     * @return the transformed result (new list)
    584     */
    585    public static <I, O> Collection<O> collect(final Iterator<I> inputIterator,
    586                                               final Transformer<? super I, ? extends O> transformer) {
    587        return collect(inputIterator, transformer, new ArrayList<>());
    588    }
    589
    590    /**
    591     * Returns {@code true} iff all elements of {@code coll2} are also contained
    592     * in {@code coll1}. The cardinality of values in {@code coll2} is not taken into account,
    593     * which is the same behavior as {@link Collection#containsAll(Collection)}.
    594     * <p>
    595     * In other words, this method returns {@code true} iff the
    596     * {@link #intersection} of <em>coll1</em> and <em>coll2</em> has the same cardinality as
    597     * the set of unique values from {@code coll2}. In case {@code coll2} is empty, {@code true}
    598     * will be returned.
    599     * </p>
    600     * <p>
    601     * This method is intended as a replacement for {@link Collection#containsAll(Collection)}
    602     * with a guaranteed runtime complexity of {@code O(n + m)}. Depending on the type of
    603     * {@link Collection} provided, this method will be much faster than calling
    604     * {@link Collection#containsAll(Collection)} instead, though this will come at the
    605     * cost of an additional space complexity O(n).
    606     * </p>
    607     *
    608     * @param coll1  the first collection, must not be null
    609     * @param coll2  the second collection, must not be null
    610     * @return {@code true} iff the intersection of the collections has the same cardinality
    611     *   as the set of unique elements from the second collection
    612     * @throws NullPointerException if coll1 or coll2 is null
    613     * @since 4.0
    614     */
    615    public static boolean containsAll(final Collection<?> coll1, final Collection<?> coll2) {
    616        Objects.requireNonNull(coll1, "coll1");
    617        Objects.requireNonNull(coll2, "coll2");
    618        if (coll2.isEmpty()) {
    619            return true;
    620        }
    621        final Set<Object> elementsAlreadySeen = new HashSet<>();
    622        for (final Object nextElement : coll2) {
    623            if (elementsAlreadySeen.contains(nextElement)) {
    624                continue;
    625            }
    626
    627            boolean foundCurrentElement = false;
    628            for (final Object p : coll1) {
    629                elementsAlreadySeen.add(p);
    630                if (Objects.equals(nextElement, p)) {
    631                    foundCurrentElement = true;
    632                    break;
    633                }
    634            }
    635
    636            if (!foundCurrentElement) {
    637                return false;
    638            }
    639        }
    640        return true;
    641    }
    642
    643    /**
    644     * Returns {@code true} iff at least one element is in both collections.
    645     * <p>
    646     * In other words, this method returns {@code true} iff the
    647     * {@link #intersection} of <em>coll1</em> and <em>coll2</em> is not empty.
    648     * </p>
    649     *
    650     * @param coll1  the first collection, must not be null
    651     * @param coll2  the second collection, must not be null
    652     * @return {@code true} iff the intersection of the collections is non-empty
    653     * @throws NullPointerException if coll1 or coll2 is null
    654     * @since 2.1
    655     * @see #intersection
    656     */
    657    public static boolean containsAny(final Collection<?> coll1, final Collection<?> coll2) {
    658        Objects.requireNonNull(coll1, "coll1");
    659        Objects.requireNonNull(coll2, "coll2");
    660        if (coll1.size() < coll2.size()) {
    661            for (final Object aColl1 : coll1) {
    662                if (coll2.contains(aColl1)) {
    663                    return true;
    664                }
    665            }
    666        } else {
    667            for (final Object aColl2 : coll2) {
    668                if (coll1.contains(aColl2)) {
    669                    return true;
    670                }
    671            }
    672        }
    673        return false;
    674    }
    675
    676    /**
    677     * Returns {@code true} iff at least one element is in both collections.
    678     * <p>
    679     * In other words, this method returns {@code true} iff the
    680     * {@link #intersection} of <em>coll1</em> and <em>coll2</em> is not empty.
    681     * </p>
    682     *
    683     * @param <T> the type of object to lookup in {@code coll1}.
    684     * @param coll1  the first collection, must not be null
    685     * @param coll2  the second collection, must not be null
    686     * @return {@code true} iff the intersection of the collections is non-empty
    687     * @throws NullPointerException if coll1 or coll2 is null
    688     * @since 4.2
    689     * @see #intersection
    690     */
    691    public static <T> boolean containsAny(final Collection<?> coll1, @SuppressWarnings("unchecked") final T... coll2) {
    692        Objects.requireNonNull(coll1, "coll1");
    693        Objects.requireNonNull(coll2, "coll2");
    694        if (coll1.size() < coll2.length) {
    695            for (final Object aColl1 : coll1) {
    696                if (ArrayUtils.contains(coll2, aColl1)) {
    697                    return true;
    698                }
    699            }
    700        } else {
    701            for (final Object aColl2 : coll2) {
    702                if (coll1.contains(aColl2)) {
    703                    return true;
    704                }
    705            }
    706        }
    707        return false;
    708    }
    709
    710    /**
    711     * Counts the number of elements in the input collection that match the
    712     * predicate.
    713     * <p>
    714     * A {@code null} collection or predicate matches no elements.
    715     * </p>
    716     *
    717     * @param <C>  the type of object the {@link Iterable} contains
    718     * @param input  the {@link Iterable} to get the input from, may be null
    719     * @param predicate  the predicate to use, may be null
    720     * @return the number of matches for the predicate in the collection
    721     * @deprecated since 4.1, use {@link IterableUtils#countMatches(Iterable, Predicate)} instead
    722     */
    723    @Deprecated
    724    public static <C> int countMatches(final Iterable<C> input, final Predicate<? super C> predicate) {
    725        return predicate == null ? 0 : (int) IterableUtils.countMatches(input, predicate);
    726    }
    727
    728    /**
    729     * Returns a {@link Collection} containing the exclusive disjunction
    730     * (symmetric difference) of the given {@link Iterable}s.
    731     * <p>
    732     * The cardinality of each element <em>e</em> in the returned
    733     * {@link Collection} will be equal to
    734     * <code>max(cardinality(<em>e</em>,<em>a</em>),cardinality(<em>e</em>,<em>b</em>)) - min(cardinality(<em>e</em>,<em>a</em>),
    735     * cardinality(<em>e</em>,<em>b</em>))</code>.
    736     * </p>
    737     * <p>
    738     * This is equivalent to
    739     * {@code {@link #subtract subtract}({@link #union union(a,b)},{@link #intersection intersection(a,b)})}
    740     * or
    741     * {@code {@link #union union}({@link #subtract subtract(a,b)},{@link #subtract subtract(b,a)})}.
    742     * </p>
    743     *
    744     * @param a the first collection, must not be null
    745     * @param b the second collection, must not be null
    746     * @param <O> the generic type that is able to represent the types contained
    747     *        in both input collections.
    748     * @return the symmetric difference of the two collections
    749     * @throws NullPointerException if either collection is null
    750     */
    751    public static <O> Collection<O> disjunction(final Iterable<? extends O> a, final Iterable<? extends O> b) {
    752        Objects.requireNonNull(a, "a");
    753        Objects.requireNonNull(b, "b");
    754        final SetOperationCardinalityHelper<O> helper = new SetOperationCardinalityHelper<>(a, b);
    755        for (final O obj : helper) {
    756            helper.setCardinality(obj, helper.max(obj) - helper.min(obj));
    757        }
    758        return helper.list();
    759    }
    760
    761    /**
    762     * Returns the immutable EMPTY_COLLECTION with generic type safety.
    763     *
    764     * @see #EMPTY_COLLECTION
    765     * @since 4.0
    766     * @param <T> the element type
    767     * @return immutable empty collection
    768     */
    769    @SuppressWarnings("unchecked") // OK, empty collection is compatible with any type
    770    public static <T> Collection<T> emptyCollection() {
    771        return EMPTY_COLLECTION;
    772    }
    773
    774    /**
    775     * Returns an immutable empty collection if the argument is {@code null},
    776     * or the argument itself otherwise.
    777     *
    778     * @param <T> the element type
    779     * @param collection the collection, possibly {@code null}
    780     * @return an empty collection if the argument is {@code null}
    781     */
    782    public static <T> Collection<T> emptyIfNull(final Collection<T> collection) {
    783        return collection == null ? emptyCollection() : collection;
    784    }
    785
    786    /**
    787     * Answers true if a predicate is true for at least one element of a
    788     * collection.
    789     * <p>
    790     * A {@code null} collection or predicate returns false.
    791     * </p>
    792     *
    793     * @param <C>  the type of object the {@link Iterable} contains
    794     * @param input  the {@link Iterable} to get the input from, may be null
    795     * @param predicate  the predicate to use, may be null
    796     * @return true if at least one element of the collection matches the predicate
    797     * @deprecated since 4.1, use {@link IterableUtils#matchesAny(Iterable, Predicate)} instead
    798     */
    799    @Deprecated
    800    public static <C> boolean exists(final Iterable<C> input, final Predicate<? super C> predicate) {
    801        return predicate != null && IterableUtils.matchesAny(input, predicate);
    802    }
    803
    804    /**
    805     * Extract the lone element of the specified Collection.
    806     *
    807     * @param <E> collection type
    808     * @param collection to read
    809     * @return sole member of collection
    810     * @throws NullPointerException if collection is null
    811     * @throws IllegalArgumentException if collection is empty or contains more than one element
    812     * @since 4.0
    813     */
    814    public static <E> E extractSingleton(final Collection<E> collection) {
    815        Objects.requireNonNull(collection, "collection");
    816        if (collection.size() != 1) {
    817            throw new IllegalArgumentException("Can extract singleton only when collection size == 1");
    818        }
    819        return collection.iterator().next();
    820    }
    821
    822    /**
    823     * Filter the collection by applying a Predicate to each element. If the
    824     * predicate returns false, remove the element.
    825     * <p>
    826     * If the input collection or predicate is null, there is no change made.
    827     * </p>
    828     *
    829     * @param <T>  the type of object the {@link Iterable} contains
    830     * @param collection  the collection to get the input from, may be null
    831     * @param predicate  the predicate to use as a filter, may be null
    832     * @return true if the collection is modified by this call, false otherwise.
    833     */
    834    public static <T> boolean filter(final Iterable<T> collection, final Predicate<? super T> predicate) {
    835        boolean result = false;
    836        if (collection != null && predicate != null) {
    837            for (final Iterator<T> it = collection.iterator(); it.hasNext();) {
    838                if (!predicate.test(it.next())) {
    839                    it.remove();
    840                    result = true;
    841                }
    842            }
    843        }
    844        return result;
    845    }
    846
    847    /**
    848     * Filter the collection by applying a Predicate to each element. If the
    849     * predicate returns true, remove the element.
    850     * <p>
    851     * This is equivalent to {@code filter(collection, PredicateUtils.notPredicate(predicate))}
    852     * if predicate is != null.
    853     * </p>
    854     * <p>
    855     * If the input collection or predicate is null, there is no change made.
    856     * </p>
    857     *
    858     * @param <T>  the type of object the {@link Iterable} contains
    859     * @param collection  the collection to get the input from, may be null
    860     * @param predicate  the predicate to use as a filter, may be null
    861     * @return true if the collection is modified by this call, false otherwise.
    862     */
    863    public static <T> boolean filterInverse(final Iterable<T> collection, final Predicate<? super T> predicate) {
    864        return filter(collection, predicate == null ? null : PredicateUtils.notPredicate(predicate));
    865    }
    866
    867    /**
    868     * Finds the first element in the given collection which matches the given predicate.
    869     * <p>
    870     * If the input collection or predicate is null, or no element of the collection
    871     * matches the predicate, null is returned.
    872     * </p>
    873     *
    874     * @param <T>  the type of object the {@link Iterable} contains
    875     * @param collection  the collection to search, may be null
    876     * @param predicate  the predicate to use, may be null
    877     * @return the first element of the collection which matches the predicate or null if none could be found
    878     * @deprecated since 4.1, use {@link IterableUtils#find(Iterable, Predicate)} instead
    879     */
    880    @Deprecated
    881    public static <T> T find(final Iterable<T> collection, final Predicate<? super T> predicate) {
    882        return predicate != null ? IterableUtils.find(collection, predicate) : null;
    883    }
    884
    885    /**
    886     * Executes the given closure on each but the last element in the collection.
    887     * <p>
    888     * If the input collection or closure is null, there is no change made.
    889     * </p>
    890     *
    891     * @param <T>  the type of object the {@link Iterable} contains
    892     * @param <C>  the closure type
    893     * @param collection  the collection to get the input from, may be null
    894     * @param closure  the closure to perform, may be null
    895     * @return the last element in the collection, or null if either collection or closure is null
    896     * @since 4.0
    897     * @deprecated since 4.1, use {@link IterableUtils#forEachButLast(Iterable, Closure)} instead
    898     */
    899    @Deprecated
    900    public static <T, C extends Closure<? super T>> T forAllButLastDo(final Iterable<T> collection,
    901                                                                      final C closure) {
    902        return closure != null ? IterableUtils.forEachButLast(collection, closure) : null;
    903    }
    904
    905    /**
    906     * Executes the given closure on each but the last element in the collection.
    907     * <p>
    908     * If the input collection or closure is null, there is no change made.
    909     * </p>
    910     *
    911     * @param <T>  the type of object the {@link Collection} contains
    912     * @param <C>  the closure type
    913     * @param iterator  the iterator to get the input from, may be null
    914     * @param closure  the closure to perform, may be null
    915     * @return the last element in the collection, or null if either iterator or closure is null
    916     * @since 4.0
    917     * @deprecated since 4.1, use {@link IteratorUtils#forEachButLast(Iterator, Closure)} instead
    918     */
    919    @Deprecated
    920    public static <T, C extends Closure<? super T>> T forAllButLastDo(final Iterator<T> iterator, final C closure) {
    921        return closure != null ? IteratorUtils.forEachButLast(iterator, closure) : null;
    922    }
    923
    924    /**
    925     * Executes the given closure on each element in the collection.
    926     * <p>
    927     * If the input collection or closure is null, there is no change made.
    928     * </p>
    929     *
    930     * @param <T>  the type of object the {@link Iterable} contains
    931     * @param <C>  the closure type
    932     * @param collection  the collection to get the input from, may be null
    933     * @param closure  the closure to perform, may be null
    934     * @return closure
    935     * @deprecated since 4.1, use {@link IterableUtils#forEach(Iterable, Closure)} instead
    936     */
    937    @Deprecated
    938    public static <T, C extends Closure<? super T>> C forAllDo(final Iterable<T> collection, final C closure) {
    939        if (closure != null) {
    940            IterableUtils.forEach(collection, closure);
    941        }
    942        return closure;
    943    }
    944
    945    /**
    946     * Executes the given closure on each element in the collection.
    947     * <p>
    948     * If the input collection or closure is null, there is no change made.
    949     * </p>
    950     *
    951     * @param <T>  the type of object the {@link Iterator} contains
    952     * @param <C>  the closure type
    953     * @param iterator  the iterator to get the input from, may be null
    954     * @param closure  the closure to perform, may be null
    955     * @return closure
    956     * @since 4.0
    957     * @deprecated since 4.1, use {@link IteratorUtils#forEach(Iterator, Closure)} instead
    958     */
    959    @Deprecated
    960    public static <T, C extends Closure<? super T>> C forAllDo(final Iterator<T> iterator, final C closure) {
    961        if (closure != null) {
    962            IteratorUtils.forEach(iterator, closure);
    963        }
    964        return closure;
    965    }
    966
    967    /**
    968     * Returns the {@code index}-th value in the {@code iterable}'s {@link Iterator}, throwing
    969     * {@code IndexOutOfBoundsException} if there is no such element.
    970     * <p>
    971     * If the {@link Iterable} is a {@link List}, then it will use {@link List#get(int)}.
    972     * </p>
    973     *
    974     * @param iterable  the {@link Iterable} to get a value from
    975     * @param index  the index to get
    976     * @param <T> the type of object in the {@link Iterable}.
    977     * @return the object at the specified index
    978     * @throws IndexOutOfBoundsException if the index is invalid
    979     * @deprecated since 4.1, use {@code IterableUtils.get(Iterable, int)} instead
    980     */
    981    @Deprecated
    982    public static <T> T get(final Iterable<T> iterable, final int index) {
    983        Objects.requireNonNull(iterable, "iterable");
    984        return IterableUtils.get(iterable, index);
    985    }
    986
    987    /**
    988     * Returns the {@code index}-th value in {@link Iterator}, throwing
    989     * {@code IndexOutOfBoundsException} if there is no such element.
    990     * <p>
    991     * The Iterator is advanced to {@code index} (or to the end, if
    992     * {@code index} exceeds the number of entries) as a side effect of this method.
    993     * </p>
    994     *
    995     * @param iterator  the iterator to get a value from
    996     * @param index  the index to get
    997     * @param <T> the type of object in the {@link Iterator}
    998     * @return the object at the specified index
    999     * @throws IndexOutOfBoundsException if the index is invalid
    1000     * @throws IllegalArgumentException if the object type is invalid
    1001     * @throws NullPointerException if iterator is null
    1002     * @deprecated since 4.1, use {@code IteratorUtils.get(Iterator, int)} instead
    1003     */
    1004    @Deprecated
    1005    public static <T> T get(final Iterator<T> iterator, final int index) {
    1006        Objects.requireNonNull(iterator, "iterator");
    1007        return IteratorUtils.get(iterator, index);
    1008    }
    1009
    1010    /**
    1011     * Returns the {@code index}-th {@code Map.Entry} in the {@code map}'s {@code entrySet},
    1012     * throwing {@code IndexOutOfBoundsException} if there is no such element.
    1013     *
    1014     * @param <K>  the key type in the {@link Map}
    1015     * @param <V>  the value type in the {@link Map}
    1016     * @param map  the object to get a value from
    1017     * @param index  the index to get
    1018     * @return the object at the specified index
    1019     * @throws IndexOutOfBoundsException if the index is invalid
    1020     */
    1021    public static <K, V> Map.Entry<K, V> get(final Map<K, V> map, final int index) {
    1022        Objects.requireNonNull(map, "map");
    1023        checkIndexBounds(index);
    1024        return get(map.entrySet(), index);
    1025    }
    1026
    1027    /**
    1028     * Returns the {@code index}-th value in {@code object}, throwing
    1029     * {@code IndexOutOfBoundsException} if there is no such element or
    1030     * {@code IllegalArgumentException} if {@code object} is not an
    1031     * instance of one of the supported types.
    1032     * <p>
    1033     * The supported types, and associated semantics are:
    1034     * </p>
    1035     * <ul>
    1036     * <li> Map -- the value returned is the {@code Map.Entry} in position
    1037     *      {@code index} in the map's {@code entrySet} iterator,
    1038     *      if there is such an entry.</li>
    1039     * <li> List -- this method is equivalent to the list's get method.</li>
    1040     * <li> Array -- the {@code index}-th array entry is returned,
    1041     *      if there is such an entry; otherwise an {@code IndexOutOfBoundsException}
    1042     *      is thrown.</li>
    1043     * <li> Collection -- the value returned is the {@code index}-th object
    1044     *      returned by the collection's default iterator, if there is such an element.</li>
    1045     * <li> Iterator or Enumeration -- the value returned is the
    1046     *      {@code index}-th object in the Iterator/Enumeration, if there
    1047     *      is such an element.  The Iterator/Enumeration is advanced to
    1048     *      {@code index} (or to the end, if {@code index} exceeds the
    1049     *      number of entries) as a side effect of this method.</li>
    1050     * </ul>
    1051     *
    1052     * @param object  the object to get a value from
    1053     * @param index  the index to get
    1054     * @return the object at the specified index
    1055     * @throws IndexOutOfBoundsException if the index is invalid
    1056     * @throws IllegalArgumentException if the object type is invalid
    1057     */
    1058    public static Object get(final Object object, final int index) {
    1059        final int i = index;
    1060        if (i < 0) {
    1061            throw new IndexOutOfBoundsException("Index cannot be negative: " + i);
    1062        }
    1063        if (object instanceof Map<?, ?>) {
    1064            final Map<?, ?> map = (Map<?, ?>) object;
    1065            final Iterator<?> iterator = map.entrySet().iterator();
    1066            return IteratorUtils.get(iterator, i);
    1067        }
    1068        if (object instanceof Object[]) {
    1069            return ((Object[]) object)[i];
    1070        }
    1071        if (object instanceof Iterator<?>) {
    1072            final Iterator<?> it = (Iterator<?>) object;
    1073            return IteratorUtils.get(it, i);
    1074        }
    1075        if (object instanceof Iterable<?>) {
    1076            final Iterable<?> iterable = (Iterable<?>) object;
    1077            return IterableUtils.get(iterable, i);
    1078        }
    1079        if (object instanceof Enumeration<?>) {
    1080            final Enumeration<?> it = (Enumeration<?>) object;
    1081            return EnumerationUtils.get(it, i);
    1082        }
    1083        if (object == null) {
    1084            throw new IllegalArgumentException("Unsupported object type: null");
    1085        }
    1086        try {
    1087            return Array.get(object, i);
    1088        } catch (final IllegalArgumentException ex) {
    1089            throw new IllegalArgumentException("Unsupported object type: " + object.getClass().getName());
    1090        }
    1091    }
    1092
    1093    /**
    1094     * Returns a {@link Map} mapping each unique element in the given
    1095     * {@link Collection} to an {@link Integer} representing the number
    1096     * of occurrences of that element in the {@link Collection}.
    1097     * <p>
    1098     * Only those elements present in the collection will appear as
    1099     * keys in the map.
    1100     * </p>
    1101     *
    1102     * @param <O>  the type of object in the returned {@link Map}. This is a super type of &lt;I&gt;.
    1103     * @param coll  the collection to get the cardinality map for, must not be null
    1104     * @return the populated cardinality map
    1105     * @throws NullPointerException if coll is null
    1106     */
    1107    public static <O> Map<O, Integer> getCardinalityMap(final Iterable<? extends O> coll) {
    1108        Objects.requireNonNull(coll, "coll");
    1109        final Map<O, Integer> count = new HashMap<>();
    1110        for (final O obj : coll) {
    1111            final Integer c = count.get(obj);
    1112            if (c == null) {
    1113                count.put(obj, Integer.valueOf(1));
    1114            } else {
    1115                count.put(obj, Integer.valueOf(c.intValue() + 1));
    1116            }
    1117        }
    1118        return count;
    1119    }
    1120
    1121    /**
    1122     * Returns the hash code of the input collection using the hash method of an equator.
    1123     *
    1124     * <p>
    1125     * Returns 0 if the input collection is {@code null}.
    1126     * </p>
    1127     *
    1128     * @param <E>  the element type
    1129     * @param collection  the input collection
    1130     * @param equator  the equator used for generate hashCode
    1131     * @return the hash code of the input collection using the hash method of an equator
    1132     * @throws NullPointerException if the equator is {@code null}
    1133     * @since 4.5.0-M1
    1134     */
    1135    public static <E> int hashCode(final Collection<? extends E> collection,
    1136            final Equator<? super E> equator) {
    1137        Objects.requireNonNull(equator, "equator");
    1138        if (null == collection) {
    1139            return 0;
    1140        }
    1141        int hashCode = 1;
    1142        for (final E e : collection) {
    1143            hashCode = 31 * hashCode + equator.hash(e);
    1144        }
    1145        return hashCode;
    1146    }
    1147
    1148    /**
    1149     * Returns a {@link Collection} containing the intersection of the given
    1150     * {@link Iterable}s.
    1151     * <p>
    1152     * The cardinality of each element in the returned {@link Collection} will
    1153     * be equal to the minimum of the cardinality of that element in the two
    1154     * given {@link Iterable}s.
    1155     * </p>
    1156     *
    1157     * @param a the first collection, must not be null
    1158     * @param b the second collection, must not be null
    1159     * @param <O> the generic type that is able to represent the types contained
    1160     *        in both input collections.
    1161     * @return the intersection of the two collections
    1162     * @throws NullPointerException if either collection is null
    1163     * @see Collection#retainAll
    1164     * @see #containsAny
    1165     */
    1166    public static <O> Collection<O> intersection(final Iterable<? extends O> a, final Iterable<? extends O> b) {
    1167        Objects.requireNonNull(a, "a");
    1168        Objects.requireNonNull(b, "b");
    1169        final SetOperationCardinalityHelper<O> helper = new SetOperationCardinalityHelper<>(a, b);
    1170        for (final O obj : helper) {
    1171            helper.setCardinality(obj, helper.min(obj));
    1172        }
    1173        return helper.list();
    1174    }
    1175
    1176    /**
    1177     * Null-safe check if the specified collection is empty.
    1178     * <p>
    1179     * Null returns true.
    1180     * </p>
    1181     *
    1182     * @param coll  the collection to check, may be null
    1183     * @return true if empty or null
    1184     * @since 3.2
    1185     */
    1186    public static boolean isEmpty(final Collection<?> coll) {
    1187        return coll == null || coll.isEmpty();
    1188    }
    1189
    1190    /**
    1191     * Returns {@code true} iff the given {@link Collection}s contain
    1192     * exactly the same elements with exactly the same cardinalities.
    1193     * <p>
    1194     * That is, iff the cardinality of <em>e</em> in <em>a</em> is
    1195     * equal to the cardinality of <em>e</em> in <em>b</em>,
    1196     * for each element <em>e</em> in <em>a</em> or <em>b</em>.
    1197     * </p>
    1198     *
    1199     * @param a  the first collection, must not be null
    1200     * @param b  the second collection, must not be null
    1201     * @return {@code true} iff the collections contain the same elements with the same cardinalities.
    1202     * @throws NullPointerException if either collection is null
    1203     */
    1204    public static boolean isEqualCollection(final Collection<?> a, final Collection<?> b) {
    1205        return CardinalityHelper.equals(a, b);
    1206    }
    1207
    1208    /**
    1209     * Returns {@code true} iff the given {@link Collection}s contain
    1210     * exactly the same elements with exactly the same cardinalities.
    1211     * <p>
    1212     * That is, iff the cardinality of <em>e</em> in <em>a</em> is
    1213     * equal to the cardinality of <em>e</em> in <em>b</em>,
    1214     * for each element <em>e</em> in <em>a</em> or <em>b</em>.
    1215     * </p>
    1216     * <p>
    1217     * <strong>Note:</strong> from version 4.1 onwards this method requires the input
    1218     * collections and equator to be of compatible type (using bounded wildcards).
    1219     * Providing incompatible arguments (e.g. by casting to their rawtypes)
    1220     * will result in a {@code ClassCastException} thrown at runtime.
    1221     * </p>
    1222     *
    1223     * @param <E>  the element type
    1224     * @param a  the first collection, must not be null
    1225     * @param b  the second collection, must not be null
    1226     * @param equator  the Equator used for testing equality
    1227     * @return {@code true} iff the collections contain the same elements with the same cardinalities.
    1228     * @throws NullPointerException if either collection or equator is null
    1229     * @since 4.0
    1230     */
    1231    public static <E> boolean isEqualCollection(final Collection<? extends E> a,
    1232                                                final Collection<? extends E> b,
    1233                                                final Equator<? super E> equator) {
    1234        Objects.requireNonNull(a, "a");
    1235        Objects.requireNonNull(b, "b");
    1236        Objects.requireNonNull(equator, "equator");
    1237
    1238        if (a.size() != b.size()) {
    1239            return false;
    1240        }
    1241
    1242        @SuppressWarnings({ "unchecked", "rawtypes" })
    1243        final Transformer<E, ?> transformer = input -> new EquatorWrapper(equator, input);
    1244
    1245        return isEqualCollection(collect(a, transformer), collect(b, transformer));
    1246    }
    1247
    1248    /**
    1249     * Returns true if no more elements can be added to the Collection.
    1250     * <p>
    1251     * This method uses the {@link BoundedCollection} interface to determine the
    1252     * full status. If the collection does not implement this interface then
    1253     * false is returned.
    1254     * </p>
    1255     * <p>
    1256     * The collection does not have to implement this interface directly.
    1257     * If the collection has been decorated using the decorators subpackage
    1258     * then these will be removed to access the BoundedCollection.
    1259     * </p>
    1260     *
    1261     * @param collection  the collection to check
    1262     * @return true if the BoundedCollection is full
    1263     * @throws NullPointerException if the collection is null
    1264     */
    1265    public static boolean isFull(final Collection<? extends Object> collection) {
    1266        Objects.requireNonNull(collection, "collection");
    1267        if (collection instanceof BoundedCollection) {
    1268            return ((BoundedCollection<?>) collection).isFull();
    1269        }
    1270        try {
    1271            final BoundedCollection<?> bcoll =
    1272                    UnmodifiableBoundedCollection.unmodifiableBoundedCollection(collection);
    1273            return bcoll.isFull();
    1274        } catch (final IllegalArgumentException ex) {
    1275            return false;
    1276        }
    1277    }
    1278
    1279    /**
    1280     * Null-safe check if the specified collection is not empty.
    1281     * <p>
    1282     * Null returns false.
    1283     * </p>
    1284     *
    1285     * @param coll  the collection to check, may be null
    1286     * @return true if non-null and non-empty
    1287     * @since 3.2
    1288     */
    1289    public static boolean isNotEmpty(final Collection<?> coll) {
    1290        return !isEmpty(coll);
    1291    }
    1292
    1293    /**
    1294     * Returns {@code true} iff <em>a</em> is a <em>proper</em> sub-collection of <em>b</em>,
    1295     * that is, iff the cardinality of <em>e</em> in <em>a</em> is less
    1296     * than or equal to the cardinality of <em>e</em> in <em>b</em>,
    1297     * for each element <em>e</em> in <em>a</em>, and there is at least one
    1298     * element <em>f</em> such that the cardinality of <em>f</em> in <em>b</em>
    1299     * is strictly greater than the cardinality of <em>f</em> in <em>a</em>.
    1300     * <p>
    1301     * The implementation assumes
    1302     * </p>
    1303     * <ul>
    1304     *    <li>{@code a.size()} and {@code b.size()} represent the
    1305     *    total cardinality of <em>a</em> and <em>b</em>, resp. </li>
    1306     *    <li>{@code a.size() &lt; Integer.MAXVALUE}</li>
    1307     * </ul>
    1308     *
    1309     * @param a  the first (sub?) collection, must not be null
    1310     * @param b  the second (super?) collection, must not be null
    1311     * @return {@code true} iff <em>a</em> is a <em>proper</em> sub-collection of <em>b</em>
    1312     * @throws NullPointerException if either collection is null
    1313     * @see #isSubCollection
    1314     * @see Collection#containsAll
    1315     */
    1316    public static boolean isProperSubCollection(final Collection<?> a, final Collection<?> b) {
    1317        Objects.requireNonNull(a, "a");
    1318        Objects.requireNonNull(b, "b");
    1319        return a.size() < b.size() && isSubCollection(a, b);
    1320    }
    1321
    1322    /**
    1323     * Returns {@code true} iff <em>a</em> is a sub-collection of <em>b</em>,
    1324     * that is, iff the cardinality of <em>e</em> in <em>a</em> is less than or
    1325     * equal to the cardinality of <em>e</em> in <em>b</em>, for each element <em>e</em>
    1326     * in <em>a</em>.
    1327     *
    1328     * @param a the first (sub?) collection, must not be null
    1329     * @param b the second (super?) collection, must not be null
    1330     * @return {@code true} iff <em>a</em> is a sub-collection of <em>b</em>
    1331     * @throws NullPointerException if either collection is null
    1332     * @see #isProperSubCollection
    1333     * @see Collection#containsAll
    1334     */
    1335    public static boolean isSubCollection(final Collection<?> a, final Collection<?> b) {
    1336        Objects.requireNonNull(a, "a");
    1337        Objects.requireNonNull(b, "b");
    1338        final CardinalityHelper<Object> helper = new CardinalityHelper<>(a, b);
    1339        for (final Object obj : a) {
    1340            if (helper.freqA(obj) > helper.freqB(obj)) {
    1341                return false;
    1342            }
    1343        }
    1344        return true;
    1345    }
    1346
    1347    /**
    1348     * Answers true if a predicate is true for every element of a
    1349     * collection.
    1350     *
    1351     * <p>
    1352     * A {@code null} predicate returns false.
    1353     * </p>
    1354     * <p>
    1355     * A {@code null} or empty collection returns true.
    1356     * </p>
    1357     *
    1358     * @param <C>  the type of object the {@link Iterable} contains
    1359     * @param input  the {@link Iterable} to get the input from, may be null
    1360     * @param predicate  the predicate to use, may be null
    1361     * @return true if every element of the collection matches the predicate or if the
    1362     * collection is empty, false otherwise
    1363     * @since 4.0
    1364     * @deprecated since 4.1, use {@link IterableUtils#matchesAll(Iterable, Predicate)} instead
    1365     */
    1366    @Deprecated
    1367    public static <C> boolean matchesAll(final Iterable<C> input, final Predicate<? super C> predicate) {
    1368        return predicate != null && IterableUtils.matchesAll(input, predicate);
    1369    }
    1370
    1371    /**
    1372     * Gets the maximum number of elements that the Collection can contain.
    1373     * <p>
    1374     * This method uses the {@link BoundedCollection} interface to determine the
    1375     * maximum size. If the collection does not implement this interface then
    1376     * -1 is returned.
    1377     * </p>
    1378     * <p>
    1379     * The collection does not have to implement this interface directly.
    1380     * If the collection has been decorated using the decorators subpackage
    1381     * then these will be removed to access the BoundedCollection.
    1382     * </p>
    1383     *
    1384     * @param collection  the collection to check
    1385     * @return the maximum size of the BoundedCollection, -1 if no maximum size
    1386     * @throws NullPointerException if the collection is null
    1387     */
    1388    public static int maxSize(final Collection<? extends Object> collection) {
    1389        Objects.requireNonNull(collection, "collection");
    1390        if (collection instanceof BoundedCollection) {
    1391            return ((BoundedCollection<?>) collection).maxSize();
    1392        }
    1393        try {
    1394            final BoundedCollection<?> bcoll =
    1395                    UnmodifiableBoundedCollection.unmodifiableBoundedCollection(collection);
    1396            return bcoll.maxSize();
    1397        } catch (final IllegalArgumentException ex) {
    1398            return -1;
    1399        }
    1400    }
    1401
    1402    /**
    1403     * Returns a {@link Collection} of all the permutations of the input collection.
    1404     * <p>
    1405     * NOTE: the number of permutations of a given collection is equal to n!, where
    1406     * n is the size of the collection. Thus, the resulting collection will become
    1407     * <strong>very</strong> large for collections &gt; 10 (e.g. 10! = 3628800, 15! = 1307674368000).
    1408     * </p>
    1409     * <p>
    1410     * For larger collections it is advised to use a {@link PermutationIterator} to
    1411     * iterate over all permutations.
    1412     * </p>
    1413     *
    1414     * @see PermutationIterator
    1415     * @param <E>  the element type
    1416     * @param collection  the collection to create permutations for, must not be null
    1417     * @return an unordered collection of all permutations of the input collection
    1418     * @throws NullPointerException if collection is null
    1419     * @since 4.0
    1420     */
    1421    public static <E> Collection<List<E>> permutations(final Collection<E> collection) {
    1422        Objects.requireNonNull(collection, "collection");
    1423        final PermutationIterator<E> it = new PermutationIterator<>(collection);
    1424        final Collection<List<E>> result = new ArrayList<>();
    1425        while (it.hasNext()) {
    1426            result.add(it.next());
    1427        }
    1428        return result;
    1429    }
    1430
    1431    /**
    1432     * Returns a predicated (validating) collection backed by the given collection.
    1433     * <p>
    1434     * Only objects that pass the test in the given predicate can be added to the collection.
    1435     * Trying to add an invalid object results in an IllegalArgumentException.
    1436     * It is important not to use the original collection after invoking this method,
    1437     * as it is a backdoor for adding invalid objects.
    1438     * </p>
    1439     *
    1440     * @param <C> the type of objects in the Collection.
    1441     * @param collection  the collection to predicate, must not be null
    1442     * @param predicate  the predicate for the collection, must not be null
    1443     * @return a predicated collection backed by the given collection
    1444     * @throws NullPointerException if the collection or predicate is null
    1445     */
    1446    public static <C> Collection<C> predicatedCollection(final Collection<C> collection,
    1447                                                         final Predicate<? super C> predicate) {
    1448        Objects.requireNonNull(collection, "collection");
    1449        Objects.requireNonNull(predicate, "predicate");
    1450        return PredicatedCollection.predicatedCollection(collection, predicate);
    1451    }
    1452
    1453    /**
    1454     * Removes the elements in {@code remove} from {@code collection}. That is, this
    1455     * method returns a collection containing all the elements in {@code c}
    1456     * that are not in {@code remove}. The cardinality of an element {@code e}
    1457     * in the returned collection is the same as the cardinality of {@code e}
    1458     * in {@code collection} unless {@code remove} contains {@code e}, in which
    1459     * case the cardinality is zero. This method is useful if you do not wish to modify
    1460     * the collection {@code c} and thus cannot call {@code collection.removeAll(remove);}.
    1461     * <p>
    1462     * This implementation iterates over {@code collection}, checking each element in
    1463     * turn to see if it's contained in {@code remove}. If it's not contained, it's added
    1464     * to the returned list. As a consequence, it is advised to use a collection type for
    1465     * {@code remove} that provides a fast (e.g. O(1)) implementation of
    1466     * {@link Collection#contains(Object)}.
    1467     * </p>
    1468     *
    1469     * @param <E>  the type of object the {@link Collection} contains
    1470     * @param collection  the collection from which items are removed (in the returned collection)
    1471     * @param remove  the items to be removed from the returned {@code collection}
    1472     * @return a {@code Collection} containing all the elements of {@code collection} except
    1473     * any elements that also occur in {@code remove}.
    1474     * @throws NullPointerException if either parameter is null
    1475     * @since 4.0 (method existed in 3.2 but was completely broken)
    1476     */
    1477    public static <E> Collection<E> removeAll(final Collection<E> collection, final Collection<?> remove) {
    1478        return ListUtils.removeAll(collection, remove);
    1479    }
    1480
    1481    /**
    1482     * Removes all elements in {@code remove} from {@code collection}.
    1483     * That is, this method returns a collection containing all the elements in
    1484     * {@code collection} that are not in {@code remove}. The
    1485     * cardinality of an element {@code e} in the returned collection is
    1486     * the same as the cardinality of {@code e} in {@code collection}
    1487     * unless {@code remove} contains {@code e}, in which case the
    1488     * cardinality is zero. This method is useful if you do not wish to modify
    1489     * the collection {@code c} and thus cannot call
    1490     * {@code collection.removeAll(remove)}.
    1491     * <p>
    1492     * Moreover this method uses an {@link Equator} instead of
    1493     * {@link Object#equals(Object)} to determine the equality of the elements
    1494     * in {@code collection} and {@code remove}. Hence this method is
    1495     * useful in cases where the equals behavior of an object needs to be
    1496     * modified without changing the object itself.
    1497     * </p>
    1498     *
    1499     * @param <E> the type of object the {@link Collection} contains
    1500     * @param collection the collection from which items are removed (in the returned collection)
    1501     * @param remove the items to be removed from the returned collection
    1502     * @param equator the Equator used for testing equality
    1503     * @return a {@code Collection} containing all the elements of {@code collection}
    1504     * except any element that if equal according to the {@code equator}
    1505     * @throws NullPointerException if any of the parameters is null
    1506     * @since 4.1
    1507     */
    1508    public static <E> Collection<E> removeAll(final Iterable<E> collection,
    1509                                              final Iterable<? extends E> remove,
    1510                                              final Equator<? super E> equator) {
    1511        Objects.requireNonNull(collection, "collection");
    1512        Objects.requireNonNull(remove, "remove");
    1513        Objects.requireNonNull(equator, "equator");
    1514        final Transformer<E, EquatorWrapper<E>> transformer = input -> new EquatorWrapper<>(equator, input);
    1515
    1516        final Set<EquatorWrapper<E>> removeSet =
    1517                collect(remove, transformer, new HashSet<>());
    1518
    1519        final List<E> list = new ArrayList<>();
    1520        for (final E element : collection) {
    1521            if (!removeSet.contains(new EquatorWrapper<>(equator, element))) {
    1522                list.add(element);
    1523            }
    1524        }
    1525        return list;
    1526    }
    1527
    1528    /**
    1529     * Removes the specified number of elements from the start index in the collection and returns them.
    1530     * This method modifies the input collections.
    1531     *
    1532     * @param <E>  the type of object the {@link Collection} contains
    1533     * @param input  the collection will be operated, can't be null
    1534     * @param startIndex  the start index (inclusive) to remove element, can't be less than 0
    1535     * @param count  the specified number to remove, can't be less than 1
    1536     * @return collection of elements that removed from the input collection
    1537     * @throws NullPointerException if input is null
    1538     * @since 4.5.0-M1
    1539     */
    1540    public static <E> Collection<E> removeCount(final Collection<E> input, int startIndex, int count) {
    1541        Objects.requireNonNull(input, "input");
    1542        if (startIndex < 0) {
    1543            throw new IndexOutOfBoundsException("The start index can't be less than 0.");
    1544        }
    1545        if (count < 0) {
    1546            throw new IndexOutOfBoundsException("The count can't be less than 0.");
    1547        }
    1548        if (input.size() < startIndex + count) {
    1549            throw new IndexOutOfBoundsException(
    1550                    "The sum of start index and count can't be greater than the size of collection.");
    1551        }
    1552
    1553        final Collection<E> result = new ArrayList<>(count);
    1554        final Iterator<E> iterator = input.iterator();
    1555        while (count > 0) {
    1556            if (startIndex > 0) {
    1557                startIndex -= 1;
    1558                iterator.next();
    1559                continue;
    1560            }
    1561            count -= 1;
    1562            result.add(iterator.next());
    1563            iterator.remove();
    1564        }
    1565        return result;
    1566    }
    1567
    1568    /**
    1569     * Removes elements whose index are between startIndex, inclusive and endIndex,
    1570     * exclusive in the collection and returns them.
    1571     * This method modifies the input collections.
    1572     *
    1573     * @param <E>  the type of object the {@link Collection} contains
    1574     * @param input  the collection will be operated, must not be null
    1575     * @param startIndex  the start index (inclusive) to remove element, must not be less than 0
    1576     * @param endIndex  the end index (exclusive) to remove, must not be less than startIndex
    1577     * @return collection of elements that removed from the input collection
    1578     * @throws NullPointerException if input is null
    1579     * @since 4.5.0-M1
    1580     */
    1581    public static <E> Collection<E> removeRange(final Collection<E> input, final int startIndex, final int endIndex) {
    1582        Objects.requireNonNull(input, "input");
    1583        if (endIndex < startIndex) {
    1584            throw new IllegalArgumentException("The end index can't be less than the start index.");
    1585        }
    1586        if (input.size() < endIndex) {
    1587            throw new IndexOutOfBoundsException("The end index can't be greater than the size of collection.");
    1588        }
    1589        return removeCount(input, startIndex, endIndex - startIndex);
    1590    }
    1591
    1592    /**
    1593     * Returns a collection containing all the elements in {@code collection}
    1594     * that are also in {@code retain}. The cardinality of an element {@code e}
    1595     * in the returned collection is the same as the cardinality of {@code e}
    1596     * in {@code collection} unless {@code retain} does not contain {@code e}, in which
    1597     * case the cardinality is zero. This method is useful if you do not wish to modify
    1598     * the collection {@code c} and thus cannot call {@code c.retainAll(retain);}.
    1599     * <p>
    1600     * This implementation iterates over {@code collection}, checking each element in
    1601     * turn to see if it's contained in {@code retain}. If it's contained, it's added
    1602     * to the returned list. As a consequence, it is advised to use a collection type for
    1603     * {@code retain} that provides a fast (e.g. O(1)) implementation of
    1604     * {@link Collection#contains(Object)}.
    1605     * </p>
    1606     *
    1607     * @param <C>  the type of object the {@link Collection} contains
    1608     * @param collection  the collection whose contents are the target of the #retailAll operation
    1609     * @param retain  the collection containing the elements to be retained in the returned collection
    1610     * @return a {@code Collection} containing all the elements of {@code collection}
    1611     * that occur at least once in {@code retain}.
    1612     * @throws NullPointerException if either parameter is null
    1613     * @since 3.2
    1614     */
    1615    public static <C> Collection<C> retainAll(final Collection<C> collection, final Collection<?> retain) {
    1616        Objects.requireNonNull(collection, "collection");
    1617        Objects.requireNonNull(retain, "retain");
    1618        return ListUtils.retainAll(collection, retain);
    1619    }
    1620
    1621    /**
    1622     * Returns a collection containing all the elements in
    1623     * {@code collection} that are also in {@code retain}. The
    1624     * cardinality of an element {@code e} in the returned collection is
    1625     * the same as the cardinality of {@code e} in {@code collection}
    1626     * unless {@code retain} does not contain {@code e}, in which case
    1627     * the cardinality is zero. This method is useful if you do not wish to
    1628     * modify the collection {@code c} and thus cannot call
    1629     * {@code c.retainAll(retain);}.
    1630     * <p>
    1631     * Moreover this method uses an {@link Equator} instead of
    1632     * {@link Object#equals(Object)} to determine the equality of the elements
    1633     * in {@code collection} and {@code retain}. Hence this method is
    1634     * useful in cases where the equals behavior of an object needs to be
    1635     * modified without changing the object itself.
    1636     * </p>
    1637     *
    1638     * @param <E> the type of object the {@link Collection} contains
    1639     * @param collection the collection whose contents are the target of the {@code retainAll} operation
    1640     * @param retain the collection containing the elements to be retained in the returned collection
    1641     * @param equator the Equator used for testing equality
    1642     * @return a {@code Collection} containing all the elements of {@code collection}
    1643     * that occur at least once in {@code retain} according to the {@code equator}
    1644     * @throws NullPointerException if any of the parameters is null
    1645     * @since 4.1
    1646     */
    1647    public static <E> Collection<E> retainAll(final Iterable<E> collection,
    1648                                              final Iterable<? extends E> retain,
    1649                                              final Equator<? super E> equator) {
    1650        Objects.requireNonNull(collection, "collection");
    1651        Objects.requireNonNull(retain, "retain");
    1652        Objects.requireNonNull(equator, "equator");
    1653        final Transformer<E, EquatorWrapper<E>> transformer = input -> new EquatorWrapper<>(equator, input);
    1654
    1655        final Set<EquatorWrapper<E>> retainSet =
    1656                collect(retain, transformer, new HashSet<>());
    1657
    1658        final List<E> list = new ArrayList<>();
    1659        for (final E element : collection) {
    1660            if (retainSet.contains(new EquatorWrapper<>(equator, element))) {
    1661                list.add(element);
    1662            }
    1663        }
    1664        return list;
    1665    }
    1666
    1667    /**
    1668     * Reverses the order of the given array.
    1669     *
    1670     * @param array  the array to reverse
    1671     */
    1672    public static void reverseArray(final Object[] array) {
    1673        Objects.requireNonNull(array, "array");
    1674        int i = 0;
    1675        int j = array.length - 1;
    1676        Object tmp;
    1677
    1678        while (j > i) {
    1679            tmp = array[j];
    1680            array[j] = array[i];
    1681            array[i] = tmp;
    1682            j--;
    1683            i++;
    1684        }
    1685    }
    1686
    1687    /**
    1688     * Selects all elements from input collection which match the given
    1689     * predicate into an output collection.
    1690     * <p>
    1691     * A {@code null} predicate matches no elements.
    1692     * </p>
    1693     *
    1694     * @param <O>  the type of object the {@link Iterable} contains
    1695     * @param inputCollection  the collection to get the input from, may not be null
    1696     * @param predicate  the predicate to use, may be null
    1697     * @return the elements matching the predicate (new list)
    1698     */
    1699    public static <O> Collection<O> select(final Iterable<? extends O> inputCollection,
    1700                                           final Predicate<? super O> predicate) {
    1701        int size = 0;
    1702        if (null != inputCollection) {
    1703            size = inputCollection instanceof Collection<?> ? ((Collection<?>) inputCollection).size() : 0;
    1704        }
    1705        final Collection<O> answer = size == 0 ? new ArrayList<>() : new ArrayList<>(size);
    1706        return select(inputCollection, predicate, answer);
    1707    }
    1708
    1709    /**
    1710     * Selects all elements from input collection which match the given
    1711     * predicate and adds them to outputCollection.
    1712     * <p>
    1713     * If the input collection or predicate is null, there is no change to the
    1714     * output collection.
    1715     * </p>
    1716     *
    1717     * @param <O>  the type of object the {@link Iterable} contains
    1718     * @param <R>  the type of the output {@link Collection}
    1719     * @param inputCollection  the collection to get the input from, may be null
    1720     * @param predicate  the predicate to use, may be null
    1721     * @param outputCollection  the collection to output into, may not be null if the inputCollection
    1722     *   and predicate or not null
    1723     * @return the outputCollection
    1724     */
    1725    public static <O, R extends Collection<? super O>> R select(final Iterable<? extends O> inputCollection,
    1726            final Predicate<? super O> predicate, final R outputCollection) {
    1727
    1728        if (inputCollection != null && predicate != null) {
    1729            for (final O item : inputCollection) {
    1730                if (predicate.test(item)) {
    1731                    outputCollection.add(item);
    1732                }
    1733            }
    1734        }
    1735        return outputCollection;
    1736    }
    1737
    1738    /**
    1739     * Selects all elements from inputCollection into an output and rejected collection,
    1740     * based on the evaluation of the given predicate.
    1741     * <p>
    1742     * Elements matching the predicate are added to the {@code outputCollection},
    1743     * all other elements are added to the {@code rejectedCollection}.
    1744     * </p>
    1745     * <p>
    1746     * If the input predicate is {@code null}, no elements are added to
    1747     * {@code outputCollection} or {@code rejectedCollection}.
    1748     * </p>
    1749     * <p>
    1750     * Note: calling the method is equivalent to the following code snippet:
    1751     * </p>
    1752     * <pre>
    1753     *   select(inputCollection, predicate, outputCollection);
    1754     *   selectRejected(inputCollection, predicate, rejectedCollection);
    1755     * </pre>
    1756     *
    1757     * @param <O>  the type of object the {@link Iterable} contains
    1758     * @param <R>  the type of the output {@link Collection}
    1759     * @param inputCollection  the collection to get the input from, may be null
    1760     * @param predicate  the predicate to use, may be null
    1761     * @param outputCollection  the collection to output selected elements into, may not be null if the
    1762     *   inputCollection and predicate are not null
    1763     * @param rejectedCollection  the collection to output rejected elements into, may not be null if the
    1764     *   inputCollection or predicate are not null
    1765     * @return the outputCollection
    1766     * @since 4.1
    1767     */
    1768    public static <O, R extends Collection<? super O>> R select(final Iterable<? extends O> inputCollection,
    1769            final Predicate<? super O> predicate, final R outputCollection, final R rejectedCollection) {
    1770
    1771        if (inputCollection != null && predicate != null) {
    1772            for (final O element : inputCollection) {
    1773                if (predicate.test(element)) {
    1774                    outputCollection.add(element);
    1775                } else {
    1776                    rejectedCollection.add(element);
    1777                }
    1778            }
    1779        }
    1780        return outputCollection;
    1781    }
    1782
    1783    /**
    1784     * Selects all elements from inputCollection which don't match the given
    1785     * predicate into an output collection.
    1786     * <p>
    1787     * If the input predicate is {@code null}, the result is an empty
    1788     * list.
    1789     * </p>
    1790     *
    1791     * @param <O>  the type of object the {@link Iterable} contains
    1792     * @param inputCollection  the collection to get the input from, may not be null
    1793     * @param predicate  the predicate to use, may be null
    1794     * @return the elements <strong>not</strong> matching the predicate (new list)
    1795     */
    1796    public static <O> Collection<O> selectRejected(final Iterable<? extends O> inputCollection,
    1797                                                   final Predicate<? super O> predicate) {
    1798        int size = 0;
    1799        if (null != inputCollection) {
    1800            size = inputCollection instanceof Collection<?> ? ((Collection<?>) inputCollection).size() : 0;
    1801        }
    1802        final Collection<O> answer = size == 0 ? new ArrayList<>() : new ArrayList<>(size);
    1803        return selectRejected(inputCollection, predicate, answer);
    1804    }
    1805
    1806    /**
    1807     * Selects all elements from inputCollection which don't match the given
    1808     * predicate and adds them to outputCollection.
    1809     * <p>
    1810     * If the input predicate is {@code null}, no elements are added to
    1811     * {@code outputCollection}.
    1812     * </p>
    1813     *
    1814     * @param <O>  the type of object the {@link Iterable} contains
    1815     * @param <R>  the type of the output {@link Collection}
    1816     * @param inputCollection  the collection to get the input from, may be null
    1817     * @param predicate  the predicate to use, may be null
    1818     * @param outputCollection  the collection to output into, may not be null if the inputCollection
    1819     *   and predicate or not null
    1820     * @return outputCollection
    1821     */
    1822    public static <O, R extends Collection<? super O>> R selectRejected(final Iterable<? extends O> inputCollection,
    1823            final Predicate<? super O> predicate, final R outputCollection) {
    1824
    1825        if (inputCollection != null && predicate != null) {
    1826            for (final O item : inputCollection) {
    1827                if (!predicate.test(item)) {
    1828                    outputCollection.add(item);
    1829                }
    1830            }
    1831        }
    1832        return outputCollection;
    1833    }
    1834
    1835    /**
    1836     * Gets the size of the collection/iterator specified.
    1837     * <p>
    1838     * This method can handles objects as follows
    1839     * </p>
    1840     * <ul>
    1841     * <li>Collection - the collection size
    1842     * <li>Map - the map size
    1843     * <li>Array - the array size
    1844     * <li>Iterator - the number of elements remaining in the iterator
    1845     * <li>Enumeration - the number of elements remaining in the enumeration
    1846     * </ul>
    1847     *
    1848     * @param object  the object to get the size of, may be null
    1849     * @return the size of the specified collection or 0 if the object was null
    1850     * @throws IllegalArgumentException thrown if object is not recognized
    1851     * @since 3.1
    1852     */
    1853    public static int size(final Object object) {
    1854        if (object == null) {
    1855            return 0;
    1856        }
    1857        int total = 0;
    1858        if (object instanceof Map<?, ?>) {
    1859            total = ((Map<?, ?>) object).size();
    1860        } else if (object instanceof Collection<?>) {
    1861            total = ((Collection<?>) object).size();
    1862        } else if (object instanceof Iterable<?>) {
    1863            total = IterableUtils.size((Iterable<?>) object);
    1864        } else if (object instanceof Object[]) {
    1865            total = ((Object[]) object).length;
    1866        } else if (object instanceof Iterator<?>) {
    1867            total = IteratorUtils.size((Iterator<?>) object);
    1868        } else if (object instanceof Enumeration<?>) {
    1869            final Enumeration<?> it = (Enumeration<?>) object;
    1870            while (it.hasMoreElements()) {
    1871                total++;
    1872                it.nextElement();
    1873            }
    1874        } else {
    1875            try {
    1876                total = Array.getLength(object);
    1877            } catch (final IllegalArgumentException ex) {
    1878                throw new IllegalArgumentException("Unsupported object type: " + object.getClass().getName());
    1879            }
    1880        }
    1881        return total;
    1882    }
    1883
    1884    /**
    1885     * Checks if the specified collection/array/iterator is empty.
    1886     * <p>
    1887     * This method can handles objects as follows
    1888     * </p>
    1889     * <ul>
    1890     * <li>Collection - via collection isEmpty
    1891     * <li>Map - via map isEmpty
    1892     * <li>Array - using array size
    1893     * <li>Iterator - via hasNext
    1894     * <li>Enumeration - via hasMoreElements
    1895     * </ul>
    1896     * <p>
    1897     * Note: This method is named to avoid clashing with
    1898     * {@link #isEmpty(Collection)}.
    1899     * </p>
    1900     *
    1901     * @param object  the object to get the size of, may be null
    1902     * @return true if empty or null
    1903     * @throws IllegalArgumentException thrown if object is not recognized
    1904     * @since 3.2
    1905     */
    1906    public static boolean sizeIsEmpty(final Object object) {
    1907        if (object == null) {
    1908            return true;
    1909        }
    1910        if (object instanceof Collection<?>) {
    1911            return ((Collection<?>) object).isEmpty();
    1912        }
    1913        if (object instanceof Iterable<?>) {
    1914            return IterableUtils.isEmpty((Iterable<?>) object);
    1915        }
    1916        if (object instanceof Map<?, ?>) {
    1917            return ((Map<?, ?>) object).isEmpty();
    1918        }
    1919        if (object instanceof Object[]) {
    1920            return ((Object[]) object).length == 0;
    1921        }
    1922        if (object instanceof Iterator<?>) {
    1923            return !((Iterator<?>) object).hasNext();
    1924        }
    1925        if (object instanceof Enumeration<?>) {
    1926            return !((Enumeration<?>) object).hasMoreElements();
    1927        }
    1928        try {
    1929            return Array.getLength(object) == 0;
    1930        } catch (final IllegalArgumentException ex) {
    1931            throw new IllegalArgumentException("Unsupported object type: " + object.getClass().getName());
    1932        }
    1933    }
    1934
    1935    /**
    1936     * Returns a new {@link Collection} containing {@code <em>a</em> - <em>b</em>}.
    1937     * The cardinality of each element <em>e</em> in the returned {@link Collection}
    1938     * will be the cardinality of <em>e</em> in <em>a</em> minus the cardinality
    1939     * of <em>e</em> in <em>b</em>, or zero, whichever is greater.
    1940     *
    1941     * @param a  the collection to subtract from, must not be null
    1942     * @param b  the collection to subtract, must not be null
    1943     * @param <O> the generic type that is able to represent the types contained
    1944     *        in both input collections.
    1945     * @return a new collection with the results
    1946     * @see Collection#removeAll
    1947     */
    1948    public static <O> Collection<O> subtract(final Iterable<? extends O> a, final Iterable<? extends O> b) {
    1949        final Predicate<O> p = TruePredicate.truePredicate();
    1950        return subtract(a, b, p);
    1951    }
    1952
    1953    /**
    1954     * Returns a new {@link Collection} containing <em>a</em> minus a subset of
    1955     * <em>b</em>.  Only the elements of <em>b</em> that satisfy the predicate
    1956     * condition, <em>p</em> are subtracted from <em>a</em>.
    1957     *
    1958     * <p>
    1959     * The cardinality of each element <em>e</em> in the returned {@link Collection}
    1960     * that satisfies the predicate condition will be the cardinality of <em>e</em> in <em>a</em>
    1961     * minus the cardinality of <em>e</em> in <em>b</em>, or zero, whichever is greater.
    1962     * </p>
    1963     * <p>
    1964     * The cardinality of each element <em>e</em> in the returned {@link Collection} that does <strong>not</strong>
    1965     * satisfy the predicate condition will be equal to the cardinality of <em>e</em> in <em>a</em>.
    1966     * </p>
    1967     *
    1968     * @param a  the collection to subtract from, must not be null
    1969     * @param b  the collection to subtract, must not be null
    1970     * @param p  the condition used to determine which elements of <em>b</em> are
    1971     *        subtracted.
    1972     * @param <O> the generic type that is able to represent the types contained
    1973     *        in both input collections.
    1974     * @return a new collection with the results
    1975     * @throws NullPointerException if either collection or p is null
    1976     * @since 4.0
    1977     * @see Collection#removeAll
    1978     */
    1979    public static <O> Collection<O> subtract(final Iterable<? extends O> a,
    1980                                             final Iterable<? extends O> b,
    1981                                             final Predicate<O> p) {
    1982        Objects.requireNonNull(a, "a");
    1983        Objects.requireNonNull(b, "b");
    1984        Objects.requireNonNull(p, "p");
    1985        final ArrayList<O> list = new ArrayList<>();
    1986        final HashBag<O> bag = new HashBag<>();
    1987        for (final O element : b) {
    1988            if (p.test(element)) {
    1989                bag.add(element);
    1990            }
    1991        }
    1992        for (final O element : a) {
    1993            if (!bag.remove(element, 1)) {
    1994                list.add(element);
    1995            }
    1996        }
    1997        return list;
    1998    }
    1999
    2000    /**
    2001     * Returns a synchronized collection backed by the given collection.
    2002     * <p>
    2003     * You must manually synchronize on the returned buffer's iterator to
    2004     * avoid non-deterministic behavior:
    2005     * </p>
    2006     * <pre>
    2007     * Collection c = CollectionUtils.synchronizedCollection(myCollection);
    2008     * synchronized (c) {
    2009     *     Iterator i = c.iterator();
    2010     *     while (i.hasNext()) {
    2011     *         process (i.next());
    2012     *     }
    2013     * }
    2014     * </pre>
    2015     * <p>
    2016     * This method uses the implementation in the decorators subpackage.
    2017     * </p>
    2018     *
    2019     * @param <C>  the type of object the {@link Collection} contains
    2020     * @param collection  the collection to synchronize, must not be null
    2021     * @return a synchronized collection backed by the given collection
    2022     * @throws NullPointerException if the collection is null
    2023     * @deprecated since 4.1, use {@link java.util.Collections#synchronizedCollection(Collection)} instead
    2024     */
    2025    @Deprecated
    2026    public static <C> Collection<C> synchronizedCollection(final Collection<C> collection) {
    2027        Objects.requireNonNull(collection, "collection");
    2028        return SynchronizedCollection.synchronizedCollection(collection);
    2029    }
    2030
    2031    /**
    2032     * Transform the collection by applying a Transformer to each element.
    2033     * <p>
    2034     * If the input collection or transformer is null, there is no change made.
    2035     * </p>
    2036     * <p>
    2037     * This routine is best for Lists, for which set() is used to do the
    2038     * transformations "in place." For other Collections, clear() and addAll()
    2039     * are used to replace elements.
    2040     * </p>
    2041     * <p>
    2042     * If the input collection controls its input, such as a Set, and the
    2043     * Transformer creates duplicates (or are otherwise invalid), the collection
    2044     * may reduce in size due to calling this method.
    2045     * </p>
    2046     *
    2047     * @param <C>  the type of object the {@link Collection} contains
    2048     * @param collection  the {@link Collection} to get the input from, may be null
    2049     * @param transformer  the transformer to perform, may be null
    2050     */
    2051    public static <C> void transform(final Collection<C> collection,
    2052                                     final Transformer<? super C, ? extends C> transformer) {
    2053
    2054        if (collection != null && transformer != null) {
    2055            if (collection instanceof List<?>) {
    2056                final List<C> list = (List<C>) collection;
    2057                for (final ListIterator<C> it = list.listIterator(); it.hasNext();) {
    2058                    it.set(transformer.apply(it.next()));
    2059                }
    2060            } else {
    2061                final Collection<C> resultCollection = collect(collection, transformer);
    2062                collection.clear();
    2063                collection.addAll(resultCollection);
    2064            }
    2065        }
    2066    }
    2067
    2068    /**
    2069     * Returns a transformed bag backed by the given collection.
    2070     * <p>
    2071     * Each object is passed through the transformer as it is added to the
    2072     * Collection. It is important not to use the original collection after invoking this
    2073     * method, as it is a backdoor for adding untransformed objects.
    2074     * </p>
    2075     * <p>
    2076     * Existing entries in the specified collection will not be transformed.
    2077     * If you want that behavior, see {@link TransformedCollection#transformedCollection}.
    2078     * </p>
    2079     *
    2080     * @param <E> the type of object the {@link Collection} contains
    2081     * @param collection  the collection to predicate, must not be null
    2082     * @param transformer  the transformer for the collection, must not be null
    2083     * @return a transformed collection backed by the given collection
    2084     * @throws NullPointerException if the collection or transformer is null
    2085     */
    2086    public static <E> Collection<E> transformingCollection(final Collection<E> collection,
    2087            final Transformer<? super E, ? extends E> transformer) {
    2088        Objects.requireNonNull(collection, "collection");
    2089        Objects.requireNonNull(transformer, "transformer");
    2090        return TransformedCollection.transformingCollection(collection, transformer);
    2091    }
    2092
    2093    /**
    2094     * Returns a {@link Collection} containing the union of the given
    2095     * {@link Iterable}s.
    2096     * <p>
    2097     * The cardinality of each element in the returned {@link Collection} will
    2098     * be equal to the maximum of the cardinality of that element in the two
    2099     * given {@link Iterable}s.
    2100     * </p>
    2101     *
    2102     * @param a the first collection, must not be null
    2103     * @param b the second collection, must not be null
    2104     * @param <O> the generic type that is able to represent the types contained
    2105     *        in both input collections.
    2106     * @return the union of the two collections
    2107     * @throws NullPointerException if either collection is null
    2108     * @see Collection#addAll
    2109     */
    2110    public static <O> Collection<O> union(final Iterable<? extends O> a, final Iterable<? extends O> b) {
    2111        Objects.requireNonNull(a, "a");
    2112        Objects.requireNonNull(b, "b");
    2113        final SetOperationCardinalityHelper<O> helper = new SetOperationCardinalityHelper<>(a, b);
    2114        for (final O obj : helper) {
    2115            helper.setCardinality(obj, helper.max(obj));
    2116        }
    2117        return helper.list();
    2118    }
    2119
    2120    /**
    2121     * Returns an unmodifiable collection backed by the given collection.
    2122     * <p>
    2123     * This method uses the implementation in the decorators subpackage.
    2124     * </p>
    2125     *
    2126     * @param <C>  the type of object the {@link Collection} contains
    2127     * @param collection  the collection to make unmodifiable, must not be null
    2128     * @return an unmodifiable collection backed by the given collection
    2129     * @throws NullPointerException if the collection is null
    2130     * @deprecated since 4.1, use {@link java.util.Collections#unmodifiableCollection(Collection)} instead
    2131     */
    2132    @Deprecated
    2133    public static <C> Collection<C> unmodifiableCollection(final Collection<? extends C> collection) {
    2134        Objects.requireNonNull(collection, "collection");
    2135        return UnmodifiableCollection.unmodifiableCollection(collection);
    2136    }
    2137
    2138    /**
    2139     * Don't allow instances.
    2140     */
    2141    private CollectionUtils() {
    2142        // empty
    2143    }
    2144}