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