    001    /*
    002     * Copyright (C) 2007 The Guava Authors
    003     *
    004     * Licensed under the Apache License, Version 2.0 (the "License");
    005     * you may not use this file except in compliance with the License.
    006     * You may obtain a copy of the License at
    007     *
    008     * http://www.apache.org/licenses/LICENSE-2.0
    009     *
    010     * Unless required by applicable law or agreed to in writing, software
    011     * distributed under the License is distributed on an "AS IS" BASIS,
    012     * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
    013     * See the License for the specific language governing permissions and
    014     * limitations under the License.
    015     */
    016
    017    package com.google.common.collect;
    018
    019    import static com.google.common.base.Preconditions.checkArgument;
    020    import static com.google.common.base.Preconditions.checkNotNull;
    021
    022    import com.google.common.annotations.GwtCompatible;
    023    import com.google.common.annotations.GwtIncompatible;
    024    import com.google.common.base.Function;
    025    import com.google.common.base.Objects;
    026    import com.google.common.base.Preconditions;
    027    import com.google.common.base.Predicate;
    028    import com.google.common.base.Predicates;
    029    import com.google.common.collect.Collections2.FilteredCollection;
    030    import com.google.common.primitives.Ints;
    031
    032    import java.io.IOException;
    033    import java.io.ObjectInputStream;
    034    import java.io.Serializable;
    035    import java.util.AbstractSet;
    036    import java.util.Arrays;
    037    import java.util.Collection;
    038    import java.util.Collections;
    039    import java.util.Comparator;
    040    import java.util.EnumSet;
    041    import java.util.HashSet;
    042    import java.util.Iterator;
    043    import java.util.LinkedHashSet;
    044    import java.util.List;
    045    import java.util.Map;
    046    import java.util.NoSuchElementException;
    047    import java.util.Set;
    048    import java.util.SortedSet;
    049    import java.util.TreeSet;
    050
    051    import javax.annotation.Nullable;
    052
    053    /**
    054     * Static utility methods pertaining to {@link Set} instances. Also see this
    055     * class's counterparts {@link Lists} and {@link Maps}.
    056     *
    057     * @author Kevin Bourrillion
    058     * @author Jared Levy
    059     * @author Chris Povirk
    060     * @since 2.0 (imported from Google Collections Library)
    061     */
    062    @GwtCompatible(emulated = true)
    063    public final class Sets {
    064      private Sets() {}
    065
    066      /**
    067       * Returns an immutable set instance containing the given enum elements.
    068       * Internally, the returned set will be backed by an {@link EnumSet}.
    069       *
    070       * <p>The iteration order of the returned set follows the enum's iteration
    071       * order, not the order in which the elements are provided to the method.
    072       *
    073       * @param anElement one of the elements the set should contain
    074       * @param otherElements the rest of the elements the set should contain
    075       * @return an immutable set containing those elements, minus duplicates
    076       */
    077      // http://code.google.com/p/google-web-toolkit/issues/detail?id=3028
    078      @GwtCompatible(serializable = true)
    079      public static <E extends Enum<E>> ImmutableSet<E> immutableEnumSet(
    080          E anElement, E... otherElements) {
    081        return new ImmutableEnumSet<E>(EnumSet.of(anElement, otherElements));
    082      }
    083
    084      /**
    085       * Returns an immutable set instance containing the given enum elements.
    086       * Internally, the returned set will be backed by an {@link EnumSet}.
    087       *
    088       * <p>The iteration order of the returned set follows the enum's iteration
    089       * order, not the order in which the elements appear in the given collection.
    090       *
    091       * @param elements the elements, all of the same {@code enum} type, that the
    092       *     set should contain
    093       * @return an immutable set containing those elements, minus duplicates
    094       */
    095      // http://code.google.com/p/google-web-toolkit/issues/detail?id=3028
    096      @GwtCompatible(serializable = true)
    097      public static <E extends Enum<E>> ImmutableSet<E> immutableEnumSet(
    098          Iterable<E> elements) {
    099        Iterator<E> iterator = elements.iterator();
    100        if (!iterator.hasNext()) {
    101          return ImmutableSet.of();
    102        }
    103        if (elements instanceof EnumSet) {
    104          EnumSet<E> enumSetClone = EnumSet.copyOf((EnumSet<E>) elements);
    105          return new ImmutableEnumSet<E>(enumSetClone);
    106        }
    107        E first = iterator.next();
    108        EnumSet<E> set = EnumSet.of(first);
    109        while (iterator.hasNext()) {
    110          set.add(iterator.next());
    111        }
    112        return new ImmutableEnumSet<E>(set);
    113      }
    114
    115      /**
    116       * Returns a new {@code EnumSet} instance containing the given elements.
    117       * Unlike {@link EnumSet#copyOf(Collection)}, this method does not produce an
    118       * exception on an empty collection, and it may be called on any iterable, not
    119       * just a {@code Collection}.
    120       */
    121      public static <E extends Enum<E>> EnumSet<E> newEnumSet(Iterable<E> iterable,
    122          Class<E> elementType) {
    123        /*
    124         * TODO(cpovirk): noneOf() and addAll() will both throw
    125         * NullPointerExceptions when appropriate. However, NullPointerTester will
    126         * fail on this method because it passes in Class.class instead of an enum
    127         * type. This means that, when iterable is null but elementType is not,
    128         * noneOf() will throw a ClassCastException before addAll() has a chance to
    129         * throw a NullPointerException. NullPointerTester considers this a failure.
    130         * Ideally the test would be fixed, but it would require a special case for
    131         * Class<E> where E extends Enum. Until that happens (if ever), leave
    132         * checkNotNull() here. For now, contemplate the irony that checking
    133         * elementType, the problem argument, is harmful, while checking iterable,
    134         * the innocent bystander, is effective.
    135         */
    136        checkNotNull(iterable);
    137        EnumSet<E> set = EnumSet.noneOf(elementType);
    138        Iterables.addAll(set, iterable);
    139        return set;
    140      }
    141
    142      // HashSet
    143
    144      /**
    145       * Creates a <i>mutable</i>, empty {@code HashSet} instance.
    146       *
    147       * <p><b>Note:</b> if mutability is not required, use {@link
    148       * ImmutableSet#of()} instead.
    149       *
    150       * <p><b>Note:</b> if {@code E} is an {@link Enum} type, use {@link
    151       * EnumSet#noneOf} instead.
    152       *
    153       * @return a new, empty {@code HashSet}
    154       */
    155      public static <E> HashSet<E> newHashSet() {
    156        return new HashSet<E>();
    157      }
    158
    159      /**
    160       * Creates a <i>mutable</i> {@code HashSet} instance containing the given
    161       * elements in unspecified order.
    162       *
    163       * <p><b>Note:</b> if mutability is not required and the elements are
    164       * non-null, use an overload of {@link ImmutableSet#of()} (for varargs) or
    165       * {@link ImmutableSet#copyOf(Object[])} (for an array) instead.
    166       *
    167       * <p><b>Note:</b> if {@code E} is an {@link Enum} type, use {@link
    168       * EnumSet#of(Enum, Enum[])} instead.
    169       *
    170       * @param elements the elements that the set should contain
    171       * @return a new {@code HashSet} containing those elements (minus duplicates)
    172       */
    173      public static <E> HashSet<E> newHashSet(E... elements) {
    174        HashSet<E> set = newHashSetWithExpectedSize(elements.length);
    175        Collections.addAll(set, elements);
    176        return set;
    177      }
    178
    179      /**
    180       * Creates a {@code HashSet} instance, with a high enough "initial capacity"
    181       * that it <i>should</i> hold {@code expectedSize} elements without growth.
    182       * This behavior cannot be broadly guaranteed, but it is observed to be true
    183       * for OpenJDK 1.6. It also can't be guaranteed that the method isn't
    184       * inadvertently <i>oversizing</i> the returned set.
    185       *
    186       * @param expectedSize the number of elements you expect to add to the
    187       *        returned set
    188       * @return a new, empty {@code HashSet} with enough capacity to hold {@code
    189       *         expectedSize} elements without resizing
    190       * @throws IllegalArgumentException if {@code expectedSize} is negative
    191       */
    192      public static <E> HashSet<E> newHashSetWithExpectedSize(int expectedSize) {
    193        return new HashSet<E>(Maps.capacity(expectedSize));
    194      }
    195
    196      /**
    197       * Creates a <i>mutable</i> {@code HashSet} instance containing the given
    198       * elements in unspecified order.
    199       *
    200       * <p><b>Note:</b> if mutability is not required and the elements are
    201       * non-null, use {@link ImmutableSet#copyOf(Iterable)} instead.
    202       *
    203       * <p><b>Note:</b> if {@code E} is an {@link Enum} type, use
    204       * {@link #newEnumSet(Iterable, Class)} instead.
    205       *
    206       * @param elements the elements that the set should contain
    207       * @return a new {@code HashSet} containing those elements (minus duplicates)
    208       */
    209      public static <E> HashSet<E> newHashSet(Iterable<? extends E> elements) {
    210        return (elements instanceof Collection)
    211            ? new HashSet<E>(Collections2.cast(elements))
    212            : newHashSet(elements.iterator());
    213      }
    214
    215      /**
    216       * Creates a <i>mutable</i> {@code HashSet} instance containing the given
    217       * elements in unspecified order.
    218       *
    219       * <p><b>Note:</b> if mutability is not required and the elements are
    220       * non-null, use {@link ImmutableSet#copyOf(Iterable)} instead.
    221       *
    222       * <p><b>Note:</b> if {@code E} is an {@link Enum} type, you should create an
    223       * {@link EnumSet} instead.
    224       *
    225       * @param elements the elements that the set should contain
    226       * @return a new {@code HashSet} containing those elements (minus duplicates)
    227       */
    228      public static <E> HashSet<E> newHashSet(Iterator<? extends E> elements) {
    229        HashSet<E> set = newHashSet();
    230        while (elements.hasNext()) {
    231          set.add(elements.next());
    232        }
    233        return set;
    234      }
    235
    236      // LinkedHashSet
    237
    238      /**
    239       * Creates a <i>mutable</i>, empty {@code LinkedHashSet} instance.
    240       *
    241       * <p><b>Note:</b> if mutability is not required, use {@link
    242       * ImmutableSet#of()} instead.
    243       *
    244       * @return a new, empty {@code LinkedHashSet}
    245       */
    246      public static <E> LinkedHashSet<E> newLinkedHashSet() {
    247        return new LinkedHashSet<E>();
    248      }
    249
    250      /**
    251       * Creates a <i>mutable</i> {@code LinkedHashSet} instance containing the
    252       * given elements in order.
    253       *
    254       * <p><b>Note:</b> if mutability is not required and the elements are
    255       * non-null, use {@link ImmutableSet#copyOf(Iterable)} instead.
    256       *
    257       * @param elements the elements that the set should contain, in order
    258       * @return a new {@code LinkedHashSet} containing those elements (minus
    259       *     duplicates)
    260       */
    261      public static <E> LinkedHashSet<E> newLinkedHashSet(
    262          Iterable<? extends E> elements) {
    263        if (elements instanceof Collection) {
    264          return new LinkedHashSet<E>(Collections2.cast(elements));
    265        }
    266        LinkedHashSet<E> set = newLinkedHashSet();
    267        for (E element : elements) {
    268          set.add(element);
    269        }
    270        return set;
    271      }
    272
    273      // TreeSet
    274
    275      /**
    276       * Creates a <i>mutable</i>, empty {@code TreeSet} instance sorted by the
    277       * natural sort ordering of its elements.
    278       *
    279       * <p><b>Note:</b> if mutability is not required, use {@link
    280       * ImmutableSortedSet#of()} instead.
    281       *
    282       * @return a new, empty {@code TreeSet}
    283       */
    284      public static <E extends Comparable> TreeSet<E> newTreeSet() {
    285        return new TreeSet<E>();
    286      }
    287
    288      /**
    289       * Creates a <i>mutable</i> {@code TreeSet} instance containing the given
    290       * elements sorted by their natural ordering.
    291       *
    292       * <p><b>Note:</b> if mutability is not required, use {@link
    293       * ImmutableSortedSet#copyOf(Iterable)} instead.
    294       *
    295       * <p><b>Note:</b> If {@code elements} is a {@code SortedSet} with an explicit
    296       * comparator, this method has different behavior than
    297       * {@link TreeSet#TreeSet(SortedSet)}, which returns a {@code TreeSet} with
    298       * that comparator.
    299       *
    300       * @param elements the elements that the set should contain
    301       * @return a new {@code TreeSet} containing those elements (minus duplicates)
    302       */
    303      public static <E extends Comparable> TreeSet<E> newTreeSet(
    304          Iterable<? extends E> elements) {
    305        TreeSet<E> set = newTreeSet();
    306        for (E element : elements) {
    307          set.add(element);
    308        }
    309        return set;
    310      }
    311
    312      /**
    313       * Creates a <i>mutable</i>, empty {@code TreeSet} instance with the given
    314       * comparator.
    315       *
    316       * <p><b>Note:</b> if mutability is not required, use {@code
    317       * ImmutableSortedSet.orderedBy(comparator).build()} instead.
    318       *
    319       * @param comparator the comparator to use to sort the set
    320       * @return a new, empty {@code TreeSet}
    321       * @throws NullPointerException if {@code comparator} is null
    322       */
    323      public static <E> TreeSet<E> newTreeSet(Comparator<? super E> comparator) {
    324        return new TreeSet<E>(checkNotNull(comparator));
    325      }
    326
    327      /**
    328       * Creates an empty {@code Set} that uses identity to determine equality. It
    329       * compares object references, instead of calling {@code equals}, to
    330       * determine whether a provided object matches an element in the set. For
    331       * example, {@code contains} returns {@code false} when passed an object that
    332       * equals a set member, but isn't the same instance. This behavior is similar
    333       * to the way {@code IdentityHashMap} handles key lookups.
    334       *
    335       * @since 8.0
    336       */
    337      public static <E> Set<E> newIdentityHashSet() {
    338        return Sets.newSetFromMap(Maps.<E, Boolean>newIdentityHashMap());
    339      }
    340
    341      /**
    342       * Creates an {@code EnumSet} consisting of all enum values that are not in
    343       * the specified collection. If the collection is an {@link EnumSet}, this
    344       * method has the same behavior as {@link EnumSet#complementOf}. Otherwise,
    345       * the specified collection must contain at least one element, in order to
    346       * determine the element type. If the collection could be empty, use
    347       * {@link #complementOf(Collection, Class)} instead of this method.
    348       *
    349       * @param collection the collection whose complement should be stored in the
    350       *     enum set
    351       * @return a new, modifiable {@code EnumSet} containing all values of the enum
    352       *     that aren't present in the given collection
    353       * @throws IllegalArgumentException if {@code collection} is not an
    354       *     {@code EnumSet} instance and contains no elements
    355       */
    356      public static <E extends Enum<E>> EnumSet<E> complementOf(
    357          Collection<E> collection) {
    358        if (collection instanceof EnumSet) {
    359          return EnumSet.complementOf((EnumSet<E>) collection);
    360        }
    361        checkArgument(!collection.isEmpty(),
    362            "collection is empty; use the other version of this method");
    363        Class<E> type = collection.iterator().next().getDeclaringClass();
    364        return makeComplementByHand(collection, type);
    365      }
    366
    367      /**
    368       * Creates an {@code EnumSet} consisting of all enum values that are not in
    369       * the specified collection. This is equivalent to
    370       * {@link EnumSet#complementOf}, but can act on any input collection, as long
    371       * as the elements are of enum type.
    372       *
    373       * @param collection the collection whose complement should be stored in the
    374       *     {@code EnumSet}
    375       * @param type the type of the elements in the set
    376       * @return a new, modifiable {@code EnumSet} initially containing all the
    377       *     values of the enum not present in the given collection
    378       */
    379      public static <E extends Enum<E>> EnumSet<E> complementOf(
    380          Collection<E> collection, Class<E> type) {
    381        checkNotNull(collection);
    382        return (collection instanceof EnumSet)
    383            ? EnumSet.complementOf((EnumSet<E>) collection)
    384            : makeComplementByHand(collection, type);
    385      }
    386
    387      private static <E extends Enum<E>> EnumSet<E> makeComplementByHand(
    388          Collection<E> collection, Class<E> type) {
    389        EnumSet<E> result = EnumSet.allOf(type);
    390        result.removeAll(collection);
    391        return result;
    392      }
    393
    394      /*
    395       * Regarding newSetForMap() and SetFromMap:
    396       *
    397       * Written by Doug Lea with assistance from members of JCP JSR-166
    398       * Expert Group and released to the public domain, as explained at
    399       * http://creativecommons.org/licenses/publicdomain
    400       */
    401
    402      /**
    403       * Returns a set backed by the specified map. The resulting set displays
    404       * the same ordering, concurrency, and performance characteristics as the
    405       * backing map. In essence, this factory method provides a {@link Set}
    406       * implementation corresponding to any {@link Map} implementation. There is no
    407       * need to use this method on a {@link Map} implementation that already has a
    408       * corresponding {@link Set} implementation (such as {@link java.util.HashMap}
    409       * or {@link java.util.TreeMap}).
    410       *
    411       * <p>Each method invocation on the set returned by this method results in
    412       * exactly one method invocation on the backing map or its {@code keySet}
    413       * view, with one exception. The {@code addAll} method is implemented as a
    414       * sequence of {@code put} invocations on the backing map.
    415       *
    416       * <p>The specified map must be empty at the time this method is invoked,
    417       * and should not be accessed directly after this method returns. These
    418       * conditions are ensured if the map is created empty, passed directly
    419       * to this method, and no reference to the map is retained, as illustrated
    420       * in the following code fragment: <pre>  {@code
    421       *
    422       *   Set<Object> identityHashSet = Sets.newSetFromMap(
    423       *       new IdentityHashMap<Object, Boolean>());}</pre>
    424       *
    425       * This method has the same behavior as the JDK 6 method
    426       * {@code Collections.newSetFromMap()}. The returned set is serializable if
    427       * the backing map is.
    428       *
    429       * @param map the backing map
    430       * @return the set backed by the map
    431       * @throws IllegalArgumentException if {@code map} is not empty
    432       */
    433      public static <E> Set<E> newSetFromMap(Map<E, Boolean> map) {
    434        return new SetFromMap<E>(map);
    435      }
    436
    437      private static class SetFromMap<E> extends AbstractSet<E>
    438          implements Set<E>, Serializable {
    439        private final Map<E, Boolean> m; // The backing map
    440        private transient Set<E> s; // Its keySet
    441
    442        SetFromMap(Map<E, Boolean> map) {
    443          checkArgument(map.isEmpty(), "Map is non-empty");
    444          m = map;
    445          s = map.keySet();
    446        }
    447
    448        @Override public void clear() {
    449          m.clear();
    450        }
    451        @Override public int size() {
    452          return m.size();
    453        }
    454        @Override public boolean isEmpty() {
    455          return m.isEmpty();
    456        }
    457        @Override public boolean contains(Object o) {
    458          return m.containsKey(o);
    459        }
    460        @Override public boolean remove(Object o) {
    461          return m.remove(o) != null;
    462        }
    463        @Override public boolean add(E e) {
    464          return m.put(e, Boolean.TRUE) == null;
    465        }
    466        @Override public Iterator<E> iterator() {
    467          return s.iterator();
    468        }
    469        @Override public Object[] toArray() {
    470          return s.toArray();
    471        }
    472        @Override public <T> T[] toArray(T[] a) {
    473          return s.toArray(a);
    474        }
    475        @Override public String toString() {
    476          return s.toString();
    477        }
    478        @Override public int hashCode() {
    479          return s.hashCode();
    480        }
    481        @Override public boolean equals(@Nullable Object object) {
    482          return this == object || this.s.equals(object);
    483        }
    484        @Override public boolean containsAll(Collection<?> c) {
    485          return s.containsAll(c);
    486        }
    487        @Override public boolean removeAll(Collection<?> c) {
    488          return s.removeAll(c);
    489        }
    490        @Override public boolean retainAll(Collection<?> c) {
    491          return s.retainAll(c);
    492        }
    493
    494        // addAll is the only inherited implementation
    495        @GwtIncompatible("not needed in emulated source")
    496        private static final long serialVersionUID = 0;
    497
    498        @GwtIncompatible("java.io.ObjectInputStream")
    499        private void readObject(ObjectInputStream stream)
    500            throws IOException, ClassNotFoundException {
    501          stream.defaultReadObject();
    502          s = m.keySet();
    503        }
    504      }
    505
    506      /**
    507       * An unmodifiable view of a set which may be backed by other sets; this view
    508       * will change as the backing sets do. Contains methods to copy the data into
    509       * a new set which will then remain stable. There is usually no reason to
    510       * retain a reference of type {@code SetView}; typically, you either use it
    511       * as a plain {@link Set}, or immediately invoke {@link #immutableCopy} or
    512       * {@link #copyInto} and forget the {@code SetView} itself.
    513       *
    514       * @since 2.0 (imported from Google Collections Library)
    515       */
    516      public abstract static class SetView<E> extends AbstractSet<E> {
    517        private SetView() {} // no subclasses but our own
    518
    519        /**
    520         * Returns an immutable copy of the current contents of this set view.
    521         * Does not support null elements.
    522         *
    523         * <p><b>Warning:</b> this may have unexpected results if a backing set of
    524         * this view uses a nonstandard notion of equivalence, for example if it is
    525         * a {@link TreeSet} using a comparator that is inconsistent with {@link
    526         * Object#equals(Object)}.
    527         */
    528        public ImmutableSet<E> immutableCopy() {
    529          return ImmutableSet.copyOf(this);
    530        }
    531
    532        /**
    533         * Copies the current contents of this set view into an existing set. This
    534         * method has equivalent behavior to {@code set.addAll(this)}, assuming that
    535         * all the sets involved are based on the same notion of equivalence.
    536         *
    537         * @return a reference to {@code set}, for convenience
    538         */
    539        // Note: S should logically extend Set<? super E> but can't due to either
    540        // some javac bug or some weirdness in the spec, not sure which.
    541        public <S extends Set<E>> S copyInto(S set) {
    542          set.addAll(this);
    543          return set;
    544        }
    545      }
    546
    547      /**
    548       * Returns an unmodifiable <b>view</b> of the union of two sets. The returned
    549       * set contains all elements that are contained in either backing set.
    550       * Iterating over the returned set iterates first over all the elements of
    551       * {@code set1}, then over each element of {@code set2}, in order, that is not
    552       * contained in {@code set1}.
    553       *
    554       * <p>Results are undefined if {@code set1} and {@code set2} are sets based on
    555       * different equivalence relations (as {@link HashSet}, {@link TreeSet}, and
    556       * the {@link Map#keySet} of an {@code IdentityHashMap} all are).
    557       *
    558       * <p><b>Note:</b> The returned view performs better when {@code set1} is the
    559       * smaller of the two sets. If you have reason to believe one of your sets
    560       * will generally be smaller than the other, pass it first.
    561       */
    562      public static <E> SetView<E> union(
    563          final Set<? extends E> set1, final Set<? extends E> set2) {
    564        checkNotNull(set1, "set1");
    565        checkNotNull(set2, "set2");
    566
    567        final Set<? extends E> set2minus1 = difference(set2, set1);
    568
    569        return new SetView<E>() {
    570          @Override public int size() {
    571            return set1.size() + set2minus1.size();
    572          }
    573          @Override public boolean isEmpty() {
    574            return set1.isEmpty() && set2.isEmpty();
    575          }
    576          @Override public Iterator<E> iterator() {
    577            return Iterators.unmodifiableIterator(
    578                Iterators.concat(set1.iterator(), set2minus1.iterator()));
    579          }
    580          @Override public boolean contains(Object object) {
    581            return set1.contains(object) || set2.contains(object);
    582          }
    583          @Override public <S extends Set<E>> S copyInto(S set) {
    584            set.addAll(set1);
    585            set.addAll(set2);
    586            return set;
    587          }
    588          @Override public ImmutableSet<E> immutableCopy() {
    589            return new ImmutableSet.Builder<E>()
    590                .addAll(set1).addAll(set2).build();
    591          }
    592        };
    593      }
    594
    595      /**
    596       * Returns an unmodifiable <b>view</b> of the intersection of two sets. The
    597       * returned set contains all elements that are contained by both backing sets.
    598       * The iteration order of the returned set matches that of {@code set1}.
    599       *
    600       * <p>Results are undefined if {@code set1} and {@code set2} are sets based
    601       * on different equivalence relations (as {@code HashSet}, {@code TreeSet},
    602       * and the keySet of an {@code IdentityHashMap} all are).
    603       *
    604       * <p><b>Note:</b> The returned view performs slightly better when {@code
    605       * set1} is the smaller of the two sets. If you have reason to believe one of
    606       * your sets will generally be smaller than the other, pass it first.
    607       * Unfortunately, since this method sets the generic type of the returned set
    608       * based on the type of the first set passed, this could in rare cases force
    609       * you to make a cast, for example: <pre>   {@code
    610       *
    611       *   Set<Object> aFewBadObjects = ...
    612       *   Set<String> manyBadStrings = ...
    613       *
    614       *   // impossible for a non-String to be in the intersection
    615       *   SuppressWarnings("unchecked")
    616       *   Set<String> badStrings = (Set) Sets.intersection(
    617       *       aFewBadObjects, manyBadStrings);}</pre>
    618       *
    619       * This is unfortunate, but should come up only very rarely.
    620       */
    621      public static <E> SetView<E> intersection(
    622          final Set<E> set1, final Set<?> set2) {
    623        checkNotNull(set1, "set1");
    624        checkNotNull(set2, "set2");
    625
    626        final Predicate<Object> inSet2 = Predicates.in(set2);
    627        return new SetView<E>() {
    628          @Override public Iterator<E> iterator() {
    629            return Iterators.filter(set1.iterator(), inSet2);
    630          }
    631          @Override public int size() {
    632            return Iterators.size(iterator());
    633          }
    634          @Override public boolean isEmpty() {
    635            return !iterator().hasNext();
    636          }
    637          @Override public boolean contains(Object object) {
    638            return set1.contains(object) && set2.contains(object);
    639          }
    640          @Override public boolean containsAll(Collection<?> collection) {
    641            return set1.containsAll(collection)
    642                && set2.containsAll(collection);
    643          }
    644        };
    645      }
    646
    647      /**
    648       * Returns an unmodifiable <b>view</b> of the difference of two sets. The
    649       * returned set contains all elements that are contained by {@code set1} and
    650       * not contained by {@code set2}. {@code set2} may also contain elements not
    651       * present in {@code set1}; these are simply ignored. The iteration order of
    652       * the returned set matches that of {@code set1}.
    653       *
    654       * <p>Results are undefined if {@code set1} and {@code set2} are sets based
    655       * on different equivalence relations (as {@code HashSet}, {@code TreeSet},
    656       * and the keySet of an {@code IdentityHashMap} all are).
    657       */
    658      public static <E> SetView<E> difference(
    659          final Set<E> set1, final Set<?> set2) {
    660        checkNotNull(set1, "set1");
    661        checkNotNull(set2, "set2");
    662
    663        final Predicate<Object> notInSet2 = Predicates.not(Predicates.in(set2));
    664        return new SetView<E>() {
    665          @Override public Iterator<E> iterator() {
    666            return Iterators.filter(set1.iterator(), notInSet2);
    667          }
    668          @Override public int size() {
    669            return Iterators.size(iterator());
    670          }
    671          @Override public boolean isEmpty() {
    672            return set2.containsAll(set1);
    673          }
    674          @Override public boolean contains(Object element) {
    675            return set1.contains(element) && !set2.contains(element);
    676          }
    677        };
    678      }
    679
    680      /**
    681       * Returns an unmodifiable <b>view</b> of the symmetric difference of two
    682       * sets. The returned set contains all elements that are contained in either
    683       * {@code set1} or {@code set2} but not in both. The iteration order of the
    684       * returned set is undefined.
    685       *
    686       * <p>Results are undefined if {@code set1} and {@code set2} are sets based
    687       * on different equivalence relations (as {@code HashSet}, {@code TreeSet},
    688       * and the keySet of an {@code IdentityHashMap} all are).
    689       *
    690       * @since 3.0
    691       */
    692      public static <E> SetView<E> symmetricDifference(
    693          Set<? extends E> set1, Set<? extends E> set2) {
    694        checkNotNull(set1, "set1");
    695        checkNotNull(set2, "set2");
    696
    697        // TODO(kevinb): Replace this with a more efficient implementation
    698        return difference(union(set1, set2), intersection(set1, set2));
    699      }
    700
    701      /**
    702       * Returns the elements of {@code unfiltered} that satisfy a predicate. The
    703       * returned set is a live view of {@code unfiltered}; changes to one affect
    704       * the other.
    705       *
    706       * <p>The resulting set's iterator does not support {@code remove()}, but all
    707       * other set methods are supported. When given an element that doesn't satisfy
    708       * the predicate, the set's {@code add()} and {@code addAll()} methods throw
    709       * an {@link IllegalArgumentException}. When methods such as {@code
    710       * removeAll()} and {@code clear()} are called on the filtered set, only
    711       * elements that satisfy the filter will be removed from the underlying set.
    712       *
    713       * <p>The returned set isn't threadsafe or serializable, even if
    714       * {@code unfiltered} is.
    715       *
    716       * <p>Many of the filtered set's methods, such as {@code size()}, iterate
    717       * across every element in the underlying set and determine which elements
    718       * satisfy the filter. When a live view is <i>not</i> needed, it may be faster
    719       * to copy {@code Iterables.filter(unfiltered, predicate)} and use the copy.
    720       *
    721       * <p><b>Warning:</b> {@code predicate} must be <i>consistent with equals</i>,
    722       * as documented at {@link Predicate#apply}. Do not provide a predicate such
    723       * as {@code Predicates.instanceOf(ArrayList.class)}, which is inconsistent
    724       * with equals. (See {@link Iterables#filter(Iterable, Class)} for related
    725       * functionality.)
    726       */
    727      // TODO(kevinb): how to omit that last sentence when building GWT javadoc?
    728      public static <E> Set<E> filter(
    729          Set<E> unfiltered, Predicate<? super E> predicate) {
    730        if (unfiltered instanceof FilteredSet) {
    731          // Support clear(), removeAll(), and retainAll() when filtering a filtered
    732          // collection.
    733          FilteredSet<E> filtered = (FilteredSet<E>) unfiltered;
    734          Predicate<E> combinedPredicate
    735              = Predicates.<E>and(filtered.predicate, predicate);
    736          return new FilteredSet<E>(
    737              (Set<E>) filtered.unfiltered, combinedPredicate);
    738        }
    739
    740        return new FilteredSet<E>(
    741            checkNotNull(unfiltered), checkNotNull(predicate));
    742      }
    743
    744      private static class FilteredSet<E> extends FilteredCollection<E>
    745          implements Set<E> {
    746        FilteredSet(Set<E> unfiltered, Predicate<? super E> predicate) {
    747          super(unfiltered, predicate);
    748        }
    749
    750        @Override public boolean equals(@Nullable Object object) {
    751          return equalsImpl(this, object);
    752        }
    753
    754        @Override public int hashCode() {
    755          return hashCodeImpl(this);
    756        }
    757      }
    758
    759      /**
    760       * Returns every possible list that can be formed by choosing one element
    761       * from each of the given sets in order; the "n-ary
    762       * <a href="http://en.wikipedia.org/wiki/Cartesian_product">Cartesian
    763       * product</a>" of the sets. For example: <pre>   {@code
    764       *
    765       *   Sets.cartesianProduct(ImmutableList.of(
    766       *       ImmutableSet.of(1, 2),
    767       *       ImmutableSet.of("A", "B", "C")))}</pre>
    768       *
    769       * returns a set containing six lists:
    770       *
    771       * <ul>
    772       * <li>{@code ImmutableList.of(1, "A")}
    773       * <li>{@code ImmutableList.of(1, "B")}
    774       * <li>{@code ImmutableList.of(1, "C")}
    775       * <li>{@code ImmutableList.of(2, "A")}
    776       * <li>{@code ImmutableList.of(2, "B")}
    777       * <li>{@code ImmutableList.of(2, "C")}
    778       * </ul>
    779       *
    780       * The order in which these lists are returned is not guaranteed, however the
    781       * position of an element inside a tuple always corresponds to the position of
    782       * the set from which it came in the input list. Note that if any input set is
    783       * empty, the Cartesian product will also be empty. If no sets at all are
    784       * provided (an empty list), the resulting Cartesian product has one element,
    785       * an empty list (counter-intuitive, but mathematically consistent).
    786       *
    787       * <p><i>Performance notes:</i> while the cartesian product of sets of size
    788       * {@code m, n, p} is a set of size {@code m x n x p}, its actual memory
    789       * consumption is much smaller. When the cartesian set is constructed, the
    790       * input sets are merely copied. Only as the resulting set is iterated are the
    791       * individual lists created, and these are not retained after iteration.
    792       *
    793       * @param sets the sets to choose elements from, in the order that
    794       *     the elements chosen from those sets should appear in the resulting
    795       *     lists
    796       * @param <B> any common base class shared by all axes (often just {@link
    797       *     Object})
    798       * @return the Cartesian product, as an immutable set containing immutable
    799       *     lists
    800       * @throws NullPointerException if {@code sets}, any one of the {@code sets},
    801       *     or any element of a provided set is null
    802       * @since 2.0
    803       */
    804      public static <B> Set<List<B>> cartesianProduct(
    805          List<? extends Set<? extends B>> sets) {
    806        for (Set<? extends B> set : sets) {
    807          if (set.isEmpty()) {
    808            return ImmutableSet.of();
    809          }
    810        }
    811        CartesianSet<B> cartesianSet = new CartesianSet<B>(sets);
    812        return cartesianSet;
    813      }
    814
    815      /**
    816       * Returns every possible list that can be formed by choosing one element
    817       * from each of the given sets in order; the "n-ary
    818       * <a href="http://en.wikipedia.org/wiki/Cartesian_product">Cartesian
    819       * product</a>" of the sets. For example: <pre>   {@code
    820       *
    821       *   Sets.cartesianProduct(
    822       *       ImmutableSet.of(1, 2),
    823       *       ImmutableSet.of("A", "B", "C"))}</pre>
    824       *
    825       * returns a set containing six lists:
    826       *
    827       * <ul>
    828       * <li>{@code ImmutableList.of(1, "A")}
    829       * <li>{@code ImmutableList.of(1, "B")}
    830       * <li>{@code ImmutableList.of(1, "C")}
    831       * <li>{@code ImmutableList.of(2, "A")}
    832       * <li>{@code ImmutableList.of(2, "B")}
    833       * <li>{@code ImmutableList.of(2, "C")}
    834       * </ul>
    835       *
    836       * The order in which these lists are returned is not guaranteed, however the
    837       * position of an element inside a tuple always corresponds to the position of
    838       * the set from which it came in the input list. Note that if any input set is
    839       * empty, the Cartesian product will also be empty. If no sets at all are
    840       * provided, the resulting Cartesian product has one element, an empty list
    841       * (counter-intuitive, but mathematically consistent).
    842       *
    843       * <p><i>Performance notes:</i> while the cartesian product of sets of size
    844       * {@code m, n, p} is a set of size {@code m x n x p}, its actual memory
    845       * consumption is much smaller. When the cartesian set is constructed, the
    846       * input sets are merely copied. Only as the resulting set is iterated are the
    847       * individual lists created, and these are not retained after iteration.
    848       *
    849       * @param sets the sets to choose elements from, in the order that
    850       *     the elements chosen from those sets should appear in the resulting
    851       *     lists
    852       * @param <B> any common base class shared by all axes (often just {@link
    853       *     Object})
    854       * @return the Cartesian product, as an immutable set containing immutable
    855       *     lists
    856       * @throws NullPointerException if {@code sets}, any one of the {@code sets},
    857       *     or any element of a provided set is null
    858       * @since 2.0
    859       */
    860      public static <B> Set<List<B>> cartesianProduct(
    861          Set<? extends B>... sets) {
    862        return cartesianProduct(Arrays.asList(sets));
    863      }
    864
    865      private static class CartesianSet<B> extends AbstractSet<List<B>> {
    866        final ImmutableList<Axis> axes;
    867        final int size;
    868
    869        CartesianSet(List<? extends Set<? extends B>> sets) {
    870          long dividend = 1;
    871          ImmutableList.Builder<Axis> builder = ImmutableList.builder();
    872          for (Set<? extends B> set : sets) {
    873            Axis axis = new Axis(set, (int) dividend); // check overflow at end
    874            builder.add(axis);
    875            dividend *= axis.size();
    876            checkArgument(dividend <= Integer.MAX_VALUE,
    877                "cartesian product is too big");
    878          }
    879          this.axes = builder.build();
    880          size = Ints.checkedCast(dividend);
    881        }
    882
    883        @Override public int size() {
    884          return size;
    885        }
    886
    887        @Override public UnmodifiableIterator<List<B>> iterator() {
    888          return new UnmodifiableIterator<List<B>>() {
    889            int index;
    890
    891            @Override
    892            public boolean hasNext() {
    893              return index < size;
    894            }
    895
    896            @Override
    897            public List<B> next() {
    898              if (!hasNext()) {
    899                throw new NoSuchElementException();
    900              }
    901
    902              Object[] tuple = new Object[axes.size()];
    903              for (int i = 0 ; i < tuple.length; i++) {
    904                tuple[i] = axes.get(i).getForIndex(index);
    905              }
    906              index++;
    907
    908              @SuppressWarnings("unchecked") // only B's are put in here
    909              List<B> result = (ImmutableList<B>) ImmutableList.copyOf(tuple);
    910              return result;
    911            }
    912          };
    913        }
    914
    915        @Override public boolean contains(Object element) {
    916          if (!(element instanceof List<?>)) {
    917            return false;
    918          }
    919          List<?> tuple = (List<?>) element;
    920          int dimensions = axes.size();
    921          if (tuple.size() != dimensions) {
    922            return false;
    923          }
    924          for (int i = 0; i < dimensions; i++) {
    925            if (!axes.get(i).contains(tuple.get(i))) {
    926              return false;
    927            }
    928          }
    929          return true;
    930        }
    931
    932        @Override public boolean equals(@Nullable Object object) {
    933          // Warning: this is broken if size() == 0, so it is critical that we
    934          // substitute an empty ImmutableSet to the user in place of this
    935          if (object instanceof CartesianSet) {
    936            CartesianSet<?> that = (CartesianSet<?>) object;
    937            return this.axes.equals(that.axes);
    938          }
    939          return super.equals(object);
    940        }
    941
    942        @Override public int hashCode() {
    943          // Warning: this is broken if size() == 0, so it is critical that we
    944          // substitute an empty ImmutableSet to the user in place of this
    945
    946          // It's a weird formula, but tests prove it works.
    947          int adjust = size - 1;
    948          for (int i = 0; i < axes.size(); i++) {
    949            adjust *= 31;
    950          }
    951          return axes.hashCode() + adjust;
    952        }
    953
    954        private class Axis {
    955          final ImmutableSet<? extends B> choices;
    956          final ImmutableList<? extends B> choicesList;
    957          final int dividend;
    958
    959          Axis(Set<? extends B> set, int dividend) {
    960            choices = ImmutableSet.copyOf(set);
    961            choicesList = choices.asList();
    962            this.dividend = dividend;
    963          }
    964
    965          int size() {
    966            return choices.size();
    967          }
    968
    969          B getForIndex(int index) {
    970            return choicesList.get(index / dividend % size());
    971          }
    972
    973          boolean contains(Object target) {
    974            return choices.contains(target);
    975          }
    976
    977          @Override public boolean equals(Object obj) {
    978            if (obj instanceof CartesianSet.Axis) {
    979              CartesianSet.Axis that = (CartesianSet.Axis) obj;
    980              return this.choices.equals(that.choices);
    981              // dividends must be equal or we wouldn't have gotten this far
    982            }
    983            return false;
    984          }
    985
    986          @Override public int hashCode() {
    987            // Because Axis instances are not exposed, we can
    988            // opportunistically choose whatever bizarre formula happens
    989            // to make CartesianSet.hashCode() as simple as possible.
    990            return size / choices.size() * choices.hashCode();
    991          }
    992        }
    993      }
    994
    995      /**
    996       * Returns the set of all possible subsets of {@code set}. For example,
    997       * {@code powerSet(ImmutableSet.of(1, 2))} returns the set {@code {{},
    998       * {1}, {2}, {1, 2}}}.
    999       *
    1000       * <p>Elements appear in these subsets in the same iteration order as they
    1001       * appeared in the input set. The order in which these subsets appear in the
    1002       * outer set is undefined. Note that the power set of the empty set is not the
    1003       * empty set, but a one-element set containing the empty set.
    1004       *
    1005       * <p>The returned set and its constituent sets use {@code equals} to decide
    1006       * whether two elements are identical, even if the input set uses a different
    1007       * concept of equivalence.
    1008       *
    1009       * <p><i>Performance notes:</i> while the power set of a set with size {@code
    1010       * n} is of size {@code 2^n}, its memory usage is only {@code O(n)}. When the
    1011       * power set is constructed, the input set is merely copied. Only as the
    1012       * power set is iterated are the individual subsets created, and these subsets
    1013       * themselves occupy only a few bytes of memory regardless of their size.
    1014       *
    1015       * @param set the set of elements to construct a power set from
    1016       * @return the power set, as an immutable set of immutable sets
    1017       * @throws IllegalArgumentException if {@code set} has more than 30 unique
    1018       *     elements (causing the power set size to exceed the {@code int} range)
    1019       * @throws NullPointerException if {@code set} is or contains {@code null}
    1020       * @see <a href="http://en.wikipedia.org/wiki/Power_set">Power set article at
    1021       *      Wikipedia</a>
    1022       * @since 4.0
    1023       */
    1024      @GwtCompatible(serializable = false)
    1025      public static <E> Set<Set<E>> powerSet(Set<E> set) {
    1026        ImmutableSet<E> input = ImmutableSet.copyOf(set);
    1027        checkArgument(input.size() <= 30,
    1028            "Too many elements to create power set: %s > 30", input.size());
    1029        return new PowerSet<E>(input);
    1030      }
    1031
    1032      private static final class PowerSet<E> extends AbstractSet<Set<E>> {
    1033        final ImmutableSet<E> inputSet;
    1034        final ImmutableList<E> inputList;
    1035        final int powerSetSize;
    1036
    1037        PowerSet(ImmutableSet<E> input) {
    1038          this.inputSet = input;
    1039          this.inputList = input.asList();
    1040          this.powerSetSize = 1 << input.size();
    1041        }
    1042
    1043        @Override public int size() {
    1044          return powerSetSize;
    1045        }
    1046
    1047        @Override public boolean isEmpty() {
    1048          return false;
    1049        }
    1050
    1051        @Override public Iterator<Set<E>> iterator() {
    1052          return new AbstractIndexedListIterator<Set<E>>(powerSetSize) {
    1053            @Override protected Set<E> get(final int setBits) {
    1054              return new AbstractSet<E>() {
    1055                @Override public int size() {
    1056                  return Integer.bitCount(setBits);
    1057                }
    1058                @Override public Iterator<E> iterator() {
    1059                  return new BitFilteredSetIterator<E>(inputList, setBits);
    1060                }
    1061              };
    1062            }
    1063          };
    1064        }
    1065
    1066        private static final class BitFilteredSetIterator<E>
    1067            extends UnmodifiableIterator<E> {
    1068          final ImmutableList<E> input;
    1069          int remainingSetBits;
    1070
    1071          BitFilteredSetIterator(ImmutableList<E> input, int allSetBits) {
    1072            this.input = input;
    1073            this.remainingSetBits = allSetBits;
    1074          }
    1075
    1076          @Override public boolean hasNext() {
    1077            return remainingSetBits != 0;
    1078          }
    1079
    1080          @Override public E next() {
    1081            int index = Integer.numberOfTrailingZeros(remainingSetBits);
    1082            if (index == 32) {
    1083              throw new NoSuchElementException();
    1084            }
    1085
    1086            int currentElementMask = 1 << index;
    1087            remainingSetBits &= ~currentElementMask;
    1088            return input.get(index);
    1089          }
    1090        }
    1091
    1092        @Override public boolean contains(@Nullable Object obj) {
    1093          if (obj instanceof Set) {
    1094            Set<?> set = (Set<?>) obj;
    1095            return inputSet.containsAll(set);
    1096          }
    1097          return false;
    1098        }
    1099
    1100        @Override public boolean equals(@Nullable Object obj) {
    1101          if (obj instanceof PowerSet) {
    1102            PowerSet<?> that = (PowerSet<?>) obj;
    1103            return inputSet.equals(that.inputSet);
    1104          }
    1105          return super.equals(obj);
    1106        }
    1107
    1108        @Override public int hashCode() {
    1109          /*
    1110           * The sum of the sums of the hash codes in each subset is just the sum of
    1111           * each input element's hash code times the number of sets that element
    1112           * appears in. Each element appears in exactly half of the 2^n sets, so:
    1113           */
    1114          return inputSet.hashCode() << (inputSet.size() - 1);
    1115        }
    1116
    1117        @Override public String toString() {
    1118          return "powerSet(" + inputSet + ")";
    1119        }
    1120      }
    1121
    1122      /**
    1123       * An implementation for {@link Set#hashCode()}.
    1124       */
    1125      static int hashCodeImpl(Set<?> s) {
    1126        int hashCode = 0;
    1127        for (Object o : s) {
    1128          hashCode += o != null ? o.hashCode() : 0;
    1129        }
    1130        return hashCode;
    1131      }
    1132
    1133      /**
    1134       * An implementation for {@link Set#equals(Object)}.
    1135       */
    1136      static boolean equalsImpl(Set<?> s, @Nullable Object object){
    1137        if (s == object) {
    1138          return true;
    1139        }
    1140        if (object instanceof Set) {
    1141          Set<?> o = (Set<?>) object;
    1142
    1143          try {
    1144            return s.size() == o.size() && s.containsAll(o);
    1145          } catch (NullPointerException ignored) {
    1146            return false;
    1147          } catch (ClassCastException ignored) {
    1148            return false;
    1149          }
    1150        }
    1151        return false;
    1152      }
    1153
    1154      /**
    1155       * Creates a view of Set<B> for a Set<A>, given a bijection between A and B.
    1156       * (Modelled for now as InvertibleFunction<A, B>, can't be Converter<A, B>
    1157       * because that's not in Guava, though both designs are less than optimal).
    1158       * Note that the bijection is treated as undefined for values not in the
    1159       * given Set<A> - it doesn't have to define a true bijection for those.
    1160       *
    1161       * <p>Note that the returned Set's contains method is unsafe -
    1162       * you *must* pass an instance of B to it, since the bijection
    1163       * can only invert B's (not any Object) back to A, so we can
    1164       * then delegate the call to the original Set<A>.
    1165       */
    1166      static <A, B> Set<B> transform(
    1167          Set<A> set, InvertibleFunction<A, B> bijection) {
    1168        return new TransformedSet<A, B>(
    1169            Preconditions.checkNotNull(set, "set"),
    1170            Preconditions.checkNotNull(bijection, "bijection")
    1171        );
    1172      }
    1173
    1174      /**
    1175       * Stop-gap measure since there is no bijection related type in Guava.
    1176       */
    1177      abstract static class InvertibleFunction<A, B> implements Function<A, B> {
    1178        abstract A invert(B b);
    1179
    1180        public InvertibleFunction<B, A> inverse() {
    1181          return new InvertibleFunction<B, A>() {
    1182            @Override public A apply(B b) {
    1183              return InvertibleFunction.this.invert(b);
    1184            }
    1185
    1186            @Override B invert(A a) {
    1187              return InvertibleFunction.this.apply(a);
    1188            }
    1189
    1190            // Not required per se, but just for good karma.
    1191            @Override public InvertibleFunction<A, B> inverse() {
    1192              return InvertibleFunction.this;
    1193            }
    1194          };
    1195        }
    1196      }
    1197
    1198      private static class TransformedSet<A, B> extends AbstractSet<B> {
    1199        final Set<A> delegate;
    1200        final InvertibleFunction<A, B> bijection;
    1201
    1202        TransformedSet(Set<A> delegate, InvertibleFunction<A, B> bijection) {
    1203          this.delegate = delegate;
    1204          this.bijection = bijection;
    1205        }
    1206
    1207        @Override public Iterator<B> iterator() {
    1208          return Iterators.transform(delegate.iterator(), bijection);
    1209        }
    1210
    1211        @Override public int size() {
    1212          return delegate.size();
    1213        }
    1214
    1215        @SuppressWarnings("unchecked") // unsafe, passed object *must* be B
    1216        @Override public boolean contains(Object o) {
    1217          B b = (B) o;
    1218          A a = bijection.invert(b);
    1219          /*
    1220           * Mathematically, Converter<A, B> defines a bijection between ALL A's
    1221           * on ALL B's. Here we concern ourselves with a subset
    1222           * of this relation: we only want the part that is defined by a *subset*
    1223           * of all A's (defined by that Set<A> delegate), and the image
    1224           * of *that* on B (which is this set). We don't care whether
    1225           * the converter is *not* a bijection for A's that are not in Set<A>
    1226           * or B's not in this Set<B>.
    1227           *
    1228           * We only want to return true if and only f the user passes a B instance
    1229           * that is contained in precisely in the image of Set<A>.
    1230           *
    1231           * The first test is whether the inverse image of this B is indeed
    1232           * in Set<A>. But we don't know whether that B belongs in this Set<B>
    1233           * or not; if not, the converter is free to return
    1234           * anything it wants, even an element of Set<A> (and this relationship
    1235           * is not part of the Set<A> <--> Set<B> bijection), and we must not
    1236           * be confused by that. So we have to do a final check to see if the
    1237           * image of that A is really equivalent to the passed B, which proves
    1238           * that the given B belongs indeed in the image of Set<A>.
    1239           */
    1240          return delegate.contains(a) && Objects.equal(bijection.apply(a), o);
    1241        }
    1242
    1243        @Override public boolean add(B b) {
    1244          return delegate.add(bijection.invert(b));
    1245        }
    1246
    1247        @SuppressWarnings("unchecked") // unsafe, passed object *must* be B
    1248        @Override public boolean remove(Object o) {
    1249          return contains(o) && delegate.remove(bijection.invert((B) o));
    1250        }
    1251
    1252        @Override public void clear() {
    1253          delegate.clear();
    1254        }
    1255      }
    1256    }