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