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