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}