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