    001/*
    002 * Licensed to the Apache Software Foundation (ASF) under one or more
    003 * contributor license agreements.  See the NOTICE file distributed with
    004 * this work for additional information regarding copyright ownership.
    005 * The ASF licenses this file to You under the Apache License, Version 2.0
    006 * (the "License"); you may not use this file except in compliance with
    007 * the License.  You may obtain a copy of the License at
    008 *
    009 *      http://www.apache.org/licenses/LICENSE-2.0
    010 *
    011 * Unless required by applicable law or agreed to in writing, software
    012 * distributed under the License is distributed on an "AS IS" BASIS,
    013 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
    014 * See the License for the specific language governing permissions and
    015 * limitations under the License.
    016 */
    017package org.apache.commons.collections4;
    018
    019import java.util.AbstractSet;
    020import java.util.Arrays;
    021import java.util.Collection;
    022import java.util.Collections;
    023import java.util.HashSet;
    024import java.util.IdentityHashMap;
    025import java.util.Iterator;
    026import java.util.NavigableSet;
    027import java.util.Objects;
    028import java.util.Set;
    029import java.util.SortedSet;
    030import java.util.TreeSet;
    031
    032import org.apache.commons.collections4.set.ListOrderedSet;
    033import org.apache.commons.collections4.set.PredicatedNavigableSet;
    034import org.apache.commons.collections4.set.PredicatedSet;
    035import org.apache.commons.collections4.set.PredicatedSortedSet;
    036import org.apache.commons.collections4.set.TransformedNavigableSet;
    037import org.apache.commons.collections4.set.TransformedSet;
    038import org.apache.commons.collections4.set.TransformedSortedSet;
    039import org.apache.commons.collections4.set.UnmodifiableNavigableSet;
    040import org.apache.commons.collections4.set.UnmodifiableSet;
    041import org.apache.commons.collections4.set.UnmodifiableSortedSet;
    042
    043/**
    044 * Provides utility methods and decorators for
    045 * {@link Set} and {@link SortedSet} instances.
    046 *
    047 * @since 2.1
    048 */
    049public class SetUtils {
    050
    051    /**
    052     * An unmodifiable <strong>view</strong> of a set that may be backed by other sets.
    053     * <p>
    054     * If the decorated sets change, this view will change as well. The contents
    055     * of this view can be transferred to another instance via the {@link #copyInto(Set)}
    056     * and {@link #toSet()} methods.
    057     * </p>
    058     *
    059     * @param <E> the element type
    060     * @since 4.1
    061     */
    062    public abstract static class SetView<E> extends AbstractSet<E> {
    063
    064        /**
    065         * Copies the contents of this view into the provided set.
    066         *
    067         * @param <S> the set type
    068         * @param set  the set for copying the contents
    069         */
    070        public <S extends Set<E>> void copyInto(final S set) {
    071            CollectionUtils.addAll(set, this);
    072        }
    073
    074        /**
    075         * Return an iterator for this view; the returned iterator is
    076         * not required to be unmodifiable.
    077         * @return a new iterator for this view
    078         */
    079        protected abstract Iterator<E> createIterator();
    080
    081        @Override
    082        public Iterator<E> iterator() {
    083            return IteratorUtils.unmodifiableIterator(createIterator());
    084        }
    085
    086        @Override
    087        public int size() {
    088            return IteratorUtils.size(iterator());
    089        }
    090
    091        /**
    092         * Returns a new set containing the contents of this view.
    093         *
    094         * @return a new set containing all elements of this view
    095         */
    096        public Set<E> toSet() {
    097            final Set<E> set = new HashSet<>(size());
    098            copyInto(set);
    099            return set;
    100        }
    101    }
    102
    103    /**
    104     * An empty unmodifiable sorted set.
    105     * This is not provided in the JDK.
    106     */
    107    @SuppressWarnings("rawtypes")
    108    public static final SortedSet EMPTY_SORTED_SET =
    109            UnmodifiableSortedSet.unmodifiableSortedSet(new TreeSet<>());
    110
    111    /**
    112     * Returns an unmodifiable <strong>view</strong> containing the difference of the given
    113     * {@link Set}s, denoted by {@code a \ b} (or {@code a - b}).
    114     * <p>
    115     * The returned view contains all elements of {@code a} that are not a member
    116     * of {@code b}.
    117     *
    118     * @param <E> the generic type that is able to represent the types contained
    119     *   in both input sets.
    120     * @param setA  the set to subtract from, must not be null
    121     * @param setB  the set to subtract, must not be null
    122     * @return a view of the relative complement of the two sets
    123     * @since 4.1
    124     */
    125    public static <E> SetView<E> difference(final Set<? extends E> setA, final Set<? extends E> setB) {
    126        Objects.requireNonNull(setA, "setA");
    127        Objects.requireNonNull(setB, "setB");
    128
    129        final Predicate<E> notContainedInB = object -> !setB.contains(object);
    130
    131        return new SetView<E>() {
    132            @Override
    133            public boolean contains(final Object o) {
    134                return setA.contains(o) && !setB.contains(o);
    135            }
    136
    137            @Override
    138            public Iterator<E> createIterator() {
    139                return IteratorUtils.filteredIterator(setA.iterator(), notContainedInB);
    140            }
    141        };
    142    }
    143
    144    /**
    145     * Returns an unmodifiable <strong>view</strong> of the symmetric difference of the given
    146     * {@link Set}s.
    147     * <p>
    148     * The returned view contains all elements of {@code a} and {@code b} that are
    149     * not a member of the other set.
    150     * <p>
    151     * This is equivalent to {@code union(difference(a, b), difference(b, a))}.
    152     *
    153     * @param <E> the generic type that is able to represent the types contained
    154     *   in both input sets.
    155     * @param setA  the first set, must not be null
    156     * @param setB  the second set, must not be null
    157     * @return a view of the symmetric difference of the two sets
    158     * @since 4.1
    159     */
    160    public static <E> SetView<E> disjunction(final Set<? extends E> setA, final Set<? extends E> setB) {
    161        Objects.requireNonNull(setA, "setA");
    162        Objects.requireNonNull(setB, "setB");
    163
    164        final SetView<E> aMinusB = difference(setA, setB);
    165        final SetView<E> bMinusA = difference(setB, setA);
    166
    167        return new SetView<E>() {
    168            @Override
    169            public boolean contains(final Object o) {
    170                return setA.contains(o) ^ setB.contains(o);
    171            }
    172
    173            @Override
    174            public Iterator<E> createIterator() {
    175                return IteratorUtils.chainedIterator(aMinusB.iterator(), bMinusA.iterator());
    176            }
    177
    178            @Override
    179            public boolean isEmpty() {
    180                return aMinusB.isEmpty() && bMinusA.isEmpty();
    181            }
    182
    183            @Override
    184            public int size() {
    185                return aMinusB.size() + bMinusA.size();
    186            }
    187        };
    188    }
    189
    190    /**
    191     * Returns an immutable empty set if the argument is {@code null},
    192     * or the argument itself otherwise.
    193     *
    194     * @param <T> the element type
    195     * @param set the set, possibly {@code null}
    196     * @return an empty set if the argument is {@code null}
    197     */
    198    public static <T> Set<T> emptyIfNull(final Set<T> set) {
    199        return set == null ? Collections.<T>emptySet() : set;
    200    }
    201
    202    /**
    203     * Gets a typed empty unmodifiable Set.
    204     * @param <E> the element type
    205     * @return an empty Set
    206     */
    207    public static <E> Set<E> emptySet() {
    208        return Collections.<E>emptySet();
    209    }
    210
    211    /**
    212     * Gets a typed empty unmodifiable sorted set.
    213     * @param <E> the element type
    214     * @return an empty sorted Set
    215     */
    216    @SuppressWarnings("unchecked") // empty set is OK for any type
    217    public static <E> SortedSet<E> emptySortedSet() {
    218        return EMPTY_SORTED_SET;
    219    }
    220
    221    /**
    222     * Generates a hash code using the algorithm specified in
    223     * {@link java.util.Set#hashCode()}.
    224     * <p>
    225     * This method is useful for implementing {@code Set} when you cannot
    226     * extend AbstractSet. The method takes Collection instances to enable other
    227     * collection types to use the Set implementation algorithm.
    228     *
    229     * @param <T> the element type
    230     * @see java.util.Set#hashCode()
    231     * @param set  the set to calculate the hash code for, may be null
    232     * @return the hash code
    233     */
    234    public static <T> int hashCodeForSet(final Collection<T> set) {
    235        if (set == null) {
    236            return 0;
    237        }
    238
    239        int hashCode = 0;
    240        for (final T obj : set) {
    241            if (obj != null) {
    242                hashCode += obj.hashCode();
    243            }
    244        }
    245        return hashCode;
    246    }
    247
    248    /**
    249     * Creates a set from the given items. If the passed var-args argument is {@code
    250     * null}, then the method returns {@code null}.
    251     * @param <E> the element type
    252     * @param items the elements that make up the new set
    253     * @return a set
    254     * @since 4.3
    255     */
    256    public static <E> HashSet<E> hashSet(final E... items) {
    257        if (items == null) {
    258            return null;
    259        }
    260        return new HashSet<>(Arrays.asList(items));
    261    }
    262
    263    /**
    264     * Returns an unmodifiable <strong>view</strong> of the intersection of the given {@link Set}s.
    265     * <p>
    266     * The returned view contains all elements that are members of both input sets
    267     * ({@code a} and {@code b}).
    268     *
    269     * @param <E> the generic type that is able to represent the types contained
    270     *   in both input sets.
    271     * @param setA  the first set, must not be null
    272     * @param setB  the second set, must not be null
    273     * @return a view of the intersection of the two sets
    274     * @since 4.1
    275     */
    276    public static <E> SetView<E> intersection(final Set<? extends E> setA, final Set<? extends E> setB) {
    277        Objects.requireNonNull(setA, "setA");
    278        Objects.requireNonNull(setB, "setB");
    279
    280        return new SetView<E>() {
    281            @Override
    282            public boolean contains(final Object o) {
    283                return setA.contains(o) && setB.contains(o);
    284            }
    285
    286            @Override
    287            public Iterator<E> createIterator() {
    288                return IteratorUtils.filteredIterator(setA.iterator(), setB::contains);
    289            }
    290        };
    291    }
    292
    293    /**
    294     * Tests two sets for equality as per the {@code equals()} contract
    295     * in {@link java.util.Set#equals(Object)}.
    296     * <p>
    297     * This method is useful for implementing {@code Set} when you cannot
    298     * extend AbstractSet. The method takes Collection instances to enable other
    299     * collection types to use the Set implementation algorithm.
    300     * <p>
    301     * The relevant text (slightly paraphrased as this is a static method) is:
    302     * <blockquote>
    303     * <p>Two sets are considered equal if they have
    304     * the same size, and every member of the first set is contained in
    305     * the second. This ensures that the {@code equals} method works
    306     * properly across different implementations of the {@code Set}
    307     * interface.</p>
    308     *
    309     * <p>
    310     * This implementation first checks if the two sets are the same object:
    311     * if so it returns {@code true}.  Then, it checks if the two sets are
    312     * identical in size; if not, it returns false. If so, it returns
    313     * {@code a.containsAll((Collection) b)}.</p>
    314     * </blockquote>
    315     *
    316     * @see java.util.Set
    317     * @param set1  the first set, may be null
    318     * @param set2  the second set, may be null
    319     * @return whether the sets are equal by value comparison
    320     */
    321    public static boolean isEqualSet(final Collection<?> set1, final Collection<?> set2) {
    322        if (set1 == set2) {
    323            return true;
    324        }
    325        if (set1 == null || set2 == null || set1.size() != set2.size()) {
    326            return false;
    327        }
    328
    329        return set1.containsAll(set2);
    330    }
    331
    332    /**
    333     * Returns a new hash set that matches elements based on {@code ==} not
    334     * {@code equals()}.
    335     * <p>
    336     * <strong>This set will violate the detail of various Set contracts.</strong>
    337     * As a general rule, don't compare this set to other sets. In particular, you can't
    338     * use decorators like {@link ListOrderedSet} on it, which silently assume that these
    339     * contracts are fulfilled.
    340     * <p>
    341     * <strong>Note that the returned set is not synchronized and is not thread-safe.</strong>
    342     * If you wish to use this set from multiple threads concurrently, you must use
    343     * appropriate synchronization. The simplest approach is to wrap this map
    344     * using {@link java.util.Collections#synchronizedSet(Set)}. This class may throw
    345     * exceptions when accessed by concurrent threads without synchronization.
    346     *
    347     * @param <E>  the element type
    348     * @return a new identity hash set
    349     * @since 4.1
    350     */
    351    public static <E> Set<E> newIdentityHashSet() {
    352        return Collections.newSetFromMap(new IdentityHashMap<>());
    353    }
    354
    355    /**
    356     * Returns a set that maintains the order of elements that are added
    357     * backed by the given set.
    358     * <p>
    359     * If an element is added twice, the order is determined by the first add.
    360     * The order is observed through the iterator or toArray.
    361     *
    362     * @param <E> the element type
    363     * @param set  the set to order, must not be null
    364     * @return an ordered set backed by the given set
    365     * @throws NullPointerException if the set is null
    366     */
    367    public static <E> Set<E> orderedSet(final Set<E> set) {
    368        return ListOrderedSet.listOrderedSet(set);
    369    }
    370
    371    /**
    372     * Returns a predicated (validating) navigable set backed by the given navigable set.
    373     * <p>
    374     * Only objects that pass the test in the given predicate can be added to the set.
    375     * Trying to add an invalid object results in an IllegalArgumentException.
    376     * It is important not to use the original set after invoking this method,
    377     * as it is a backdoor for adding invalid objects.
    378     *
    379     * @param <E> the element type
    380     * @param set  the navigable set to predicate, must not be null
    381     * @param predicate  the predicate for the navigable set, must not be null
    382     * @return a predicated navigable set backed by the given navigable set
    383     * @throws NullPointerException if the set or predicate is null
    384     * @since 4.1
    385     */
    386    public static <E> SortedSet<E> predicatedNavigableSet(final NavigableSet<E> set,
    387                                                          final Predicate<? super E> predicate) {
    388        return PredicatedNavigableSet.predicatedNavigableSet(set, predicate);
    389    }
    390
    391    /**
    392     * Returns a predicated (validating) set backed by the given set.
    393     * <p>
    394     * Only objects that pass the test in the given predicate can be added to the set.
    395     * Trying to add an invalid object results in an IllegalArgumentException.
    396     * It is important not to use the original set after invoking this method,
    397     * as it is a backdoor for adding invalid objects.
    398     *
    399     * @param <E> the element type
    400     * @param set  the set to predicate, must not be null
    401     * @param predicate  the predicate for the set, must not be null
    402     * @return a predicated set backed by the given set
    403     * @throws NullPointerException if the set or predicate is null
    404     */
    405    public static <E> Set<E> predicatedSet(final Set<E> set, final Predicate<? super E> predicate) {
    406        return PredicatedSet.predicatedSet(set, predicate);
    407    }
    408
    409    /**
    410     * Returns a predicated (validating) sorted set backed by the given sorted set.
    411     * <p>
    412     * Only objects that pass the test in the given predicate can be added to the set.
    413     * Trying to add an invalid object results in an IllegalArgumentException.
    414     * It is important not to use the original set after invoking this method,
    415     * as it is a backdoor for adding invalid objects.
    416     *
    417     * @param <E> the element type
    418     * @param set  the sorted set to predicate, must not be null
    419     * @param predicate  the predicate for the sorted set, must not be null
    420     * @return a predicated sorted set backed by the given sorted set
    421     * @throws NullPointerException if the set or predicate is null
    422     */
    423    public static <E> SortedSet<E> predicatedSortedSet(final SortedSet<E> set,
    424                                                       final Predicate<? super E> predicate) {
    425        return PredicatedSortedSet.predicatedSortedSet(set, predicate);
    426    }
    427
    428    // Set
    429    /**
    430     * Returns a synchronized set backed by the given set.
    431     * <p>
    432     * You must manually synchronize on the returned set's iterator to
    433     * avoid non-deterministic behavior:
    434     *
    435     * <pre>
    436     * Sets s = SetUtils.synchronizedSet(mySet);
    437     * synchronized (s) {
    438     *     Iterator i = s.iterator();
    439     *     while (i.hasNext()) {
    440     *         process (i.next());
    441     *     }
    442     * }
    443     * </pre>
    444     *
    445     * This method is just a wrapper for {@link Collections#synchronizedSet(Set)}.
    446     *
    447     * @param <E> the element type
    448     * @param set  the set to synchronize, must not be null
    449     * @return a synchronized set backed by the given set
    450     * @throws NullPointerException if the set is null
    451     */
    452    public static <E> Set<E> synchronizedSet(final Set<E> set) {
    453        return Collections.synchronizedSet(set);
    454    }
    455
    456    // SortedSet
    457    /**
    458     * Returns a synchronized sorted set backed by the given sorted set.
    459     * <p>
    460     * You must manually synchronize on the returned set's iterator to
    461     * avoid non-deterministic behavior:
    462     *
    463     * <pre>
    464     * Set s = SetUtils.synchronizedSortedSet(mySet);
    465     * synchronized (s) {
    466     *     Iterator i = s.iterator();
    467     *     while (i.hasNext()) {
    468     *         process (i.next());
    469     *     }
    470     * }
    471     * </pre>
    472     *
    473     * This method is just a wrapper for {@link Collections#synchronizedSortedSet(SortedSet)}.
    474     *
    475     * @param <E> the element type
    476     * @param set  the sorted set to synchronize, must not be null
    477     * @return a synchronized set backed by the given set
    478     * @throws NullPointerException if the set is null
    479     */
    480    public static <E> SortedSet<E> synchronizedSortedSet(final SortedSet<E> set) {
    481        return Collections.synchronizedSortedSet(set);
    482    }
    483
    484    /**
    485     * Returns a transformed navigable set backed by the given navigable set.
    486     * <p>
    487     * Each object is passed through the transformer as it is added to the
    488     * Set. It is important not to use the original set after invoking this
    489     * method, as it is a backdoor for adding untransformed objects.
    490     * <p>
    491     * Existing entries in the specified set will not be transformed.
    492     * If you want that behavior, see {@link TransformedNavigableSet#transformedNavigableSet}.
    493     *
    494     * @param <E> the element type
    495     * @param set  the navigable set to transform, must not be null
    496     * @param transformer  the transformer for the set, must not be null
    497     * @return a transformed set backed by the given set
    498     * @throws NullPointerException if the set or transformer is null
    499     * @since 4.1
    500     */
    501    public static <E> SortedSet<E> transformedNavigableSet(final NavigableSet<E> set,
    502                                                           final Transformer<? super E, ? extends E> transformer) {
    503        return TransformedNavigableSet.transformingNavigableSet(set, transformer);
    504    }
    505
    506    /**
    507     * Returns a transformed set backed by the given set.
    508     * <p>
    509     * Each object is passed through the transformer as it is added to the
    510     * Set. It is important not to use the original set after invoking this
    511     * method, as it is a backdoor for adding untransformed objects.
    512     * <p>
    513     * Existing entries in the specified set will not be transformed.
    514     * If you want that behavior, see {@link TransformedSet#transformedSet}.
    515     *
    516     * @param <E> the element type
    517     * @param set  the set to transform, must not be null
    518     * @param transformer  the transformer for the set, must not be null
    519     * @return a transformed set backed by the given set
    520     * @throws NullPointerException if the set or transformer is null
    521     */
    522    public static <E> Set<E> transformedSet(final Set<E> set,
    523                                            final Transformer<? super E, ? extends E> transformer) {
    524        return TransformedSet.transformingSet(set, transformer);
    525    }
    526
    527    /**
    528     * Returns a transformed sorted set backed by the given set.
    529     * <p>
    530     * Each object is passed through the transformer as it is added to the
    531     * Set. It is important not to use the original set after invoking this
    532     * method, as it is a backdoor for adding untransformed objects.
    533     * <p>
    534     * Existing entries in the specified set will not be transformed.
    535     * If you want that behavior, see {@link TransformedSortedSet#transformedSortedSet}.
    536     *
    537     * @param <E> the element type
    538     * @param set  the set to transform, must not be null
    539     * @param transformer  the transformer for the set, must not be null
    540     * @return a transformed set backed by the given set
    541     * @throws NullPointerException if the set or transformer is null
    542     */
    543    public static <E> SortedSet<E> transformedSortedSet(final SortedSet<E> set,
    544                                                        final Transformer<? super E, ? extends E> transformer) {
    545        return TransformedSortedSet.transformingSortedSet(set, transformer);
    546    }
    547
    548    // Set operations
    549
    550    /**
    551     * Returns an unmodifiable <strong>view</strong> of the union of the given {@link Set}s.
    552     * <p>
    553     * The returned view contains all elements of {@code a} and {@code b}.
    554     *
    555     * @param <E> the generic type that is able to represent the types contained
    556     *   in both input sets.
    557     * @param setA  the first set, must not be null
    558     * @param setB  the second set, must not be null
    559     * @return a view of the union of the two set
    560     * @throws NullPointerException if either input set is null
    561     * @since 4.1
    562     */
    563    public static <E> SetView<E> union(final Set<? extends E> setA, final Set<? extends E> setB) {
    564        Objects.requireNonNull(setA, "setA");
    565        Objects.requireNonNull(setB, "setB");
    566
    567        final SetView<E> bMinusA = difference(setB, setA);
    568
    569        return new SetView<E>() {
    570            @Override
    571            public boolean contains(final Object o) {
    572                return setA.contains(o) || setB.contains(o);
    573            }
    574
    575            @Override
    576            public Iterator<E> createIterator() {
    577                return IteratorUtils.chainedIterator(setA.iterator(), bMinusA.iterator());
    578            }
    579
    580            @Override
    581            public boolean isEmpty() {
    582                return setA.isEmpty() && setB.isEmpty();
    583            }
    584
    585            @Override
    586            public int size() {
    587                return setA.size() + bMinusA.size();
    588            }
    589        };
    590    }
    591
    592    // NavigableSet
    593    /**
    594     * Returns an unmodifiable navigable set backed by the given navigable set.
    595     * <p>
    596     * This method uses the implementation in the decorators subpackage.
    597     *
    598     * @param <E> the element type
    599     * @param set  the navigable set to make unmodifiable, must not be null
    600     * @return an unmodifiable set backed by the given set
    601     * @throws NullPointerException if the set is null
    602     * @since 4.1
    603     */
    604    public static <E> SortedSet<E> unmodifiableNavigableSet(final NavigableSet<E> set) {
    605        return UnmodifiableNavigableSet.unmodifiableNavigableSet(set);
    606    }
    607
    608    /**
    609     * Creates an unmodifiable set from the given items. If the passed var-args argument is {@code
    610     * null}, then the method returns {@code null}.
    611     * @param <E> the element type
    612     * @param items the elements that make up the new set
    613     * @return a set
    614     * @since 4.3
    615     */
    616    public static <E> Set<E> unmodifiableSet(final E... items) {
    617        if (items == null) {
    618            return null;
    619        }
    620        return UnmodifiableSet.unmodifiableSet(hashSet(items));
    621    }
    622
    623    /**
    624     * Returns an unmodifiable set backed by the given set.
    625     * <p>
    626     * This method uses the implementation in the decorators subpackage.
    627     *
    628     * @param <E> the element type
    629     * @param set  the set to make unmodifiable, must not be null
    630     * @return an unmodifiable set backed by the given set
    631     * @throws NullPointerException if the set is null
    632     */
    633    public static <E> Set<E> unmodifiableSet(final Set<? extends E> set) {
    634        return UnmodifiableSet.unmodifiableSet(set);
    635    }
    636
    637    /**
    638     * Returns an unmodifiable sorted set backed by the given sorted set.
    639     * <p>
    640     * This method uses the implementation in the decorators subpackage.
    641     *
    642     * @param <E> the element type
    643     * @param set  the sorted set to make unmodifiable, must not be null
    644     * @return an unmodifiable set backed by the given set
    645     * @throws NullPointerException if the set is null
    646     */
    647    public static <E> SortedSet<E> unmodifiableSortedSet(final SortedSet<E> set) {
    648        return UnmodifiableSortedSet.unmodifiableSortedSet(set);
    649    }
    650
    651    /**
    652     * Don't allow instances.
    653     */
    654    private SetUtils() {
    655        // empty
    656    }
    657
    658}