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