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