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.Predicate;
025import com.google.common.base.Predicates;
026import com.google.common.collect.Collections2.FilteredCollection;
027
028import java.io.Serializable;
029import java.util.AbstractSet;
030import java.util.Arrays;
031import java.util.Collection;
032import java.util.Collections;
033import java.util.Comparator;
034import java.util.EnumSet;
035import java.util.HashSet;
036import java.util.Iterator;
037import java.util.LinkedHashSet;
038import java.util.List;
039import java.util.Map;
040import java.util.NavigableSet;
041import java.util.NoSuchElementException;
042import java.util.Set;
043import java.util.SortedSet;
044import java.util.TreeSet;
045import java.util.concurrent.ConcurrentHashMap;
046import java.util.concurrent.CopyOnWriteArraySet;
047
048import javax.annotation.CheckReturnValue;
049import javax.annotation.Nullable;
050
051/**
052 * Static utility methods pertaining to {@link Set} instances. Also see this
053 * class's counterparts {@link Lists}, {@link Maps} and {@link Queues}.
054 *
055 * <p>See the Guava User Guide article on <a href=
056 * "https://github.com/google/guava/wiki/CollectionUtilitiesExplained#sets">
057 * {@code Sets}</a>.
058 *
059 * @author Kevin Bourrillion
060 * @author Jared Levy
061 * @author Chris Povirk
062 * @since 2.0
063 */
064@GwtCompatible(emulated = true)
065public final class Sets {
066  private Sets() {}
067
068  /**
069   * {@link AbstractSet} substitute without the potentially-quadratic
070   * {@code removeAll} implementation.
071   */
072  abstract static class ImprovedAbstractSet<E> extends AbstractSet<E> {
073    @Override
074    public boolean removeAll(Collection<?> c) {
075      return removeAllImpl(this, c);
076    }
077
078    @Override
079    public boolean retainAll(Collection<?> c) {
080      return super.retainAll(checkNotNull(c)); // GWT compatibility
081    }
082  }
083
084  /**
085   * Returns an immutable set instance containing the given enum elements.
086   * Internally, the returned set will be backed by an {@link EnumSet}.
087   *
088   * <p>The iteration order of the returned set follows the enum's iteration
089   * order, not the order in which the elements are provided to the method.
090   *
091   * @param anElement one of the elements the set should contain
092   * @param otherElements the rest of the elements the set should contain
093   * @return an immutable set containing those elements, minus duplicates
094   */
095  // http://code.google.com/p/google-web-toolkit/issues/detail?id=3028
096  @GwtCompatible(serializable = true)
097  public static <E extends Enum<E>> ImmutableSet<E> immutableEnumSet(
098      E anElement, E... otherElements) {
099    return ImmutableEnumSet.asImmutable(EnumSet.of(anElement, otherElements));
100  }
101
102  /**
103   * Returns an immutable set instance containing the given enum elements.
104   * Internally, the returned set will be backed by an {@link EnumSet}.
105   *
106   * <p>The iteration order of the returned set follows the enum's iteration
107   * order, not the order in which the elements appear in the given collection.
108   *
109   * @param elements the elements, all of the same {@code enum} type, that the
110   *     set should contain
111   * @return an immutable set containing those elements, minus duplicates
112   */
113  // http://code.google.com/p/google-web-toolkit/issues/detail?id=3028
114  @GwtCompatible(serializable = true)
115  public static <E extends Enum<E>> ImmutableSet<E> immutableEnumSet(Iterable<E> elements) {
116    if (elements instanceof ImmutableEnumSet) {
117      return (ImmutableEnumSet<E>) elements;
118    } else if (elements instanceof Collection) {
119      Collection<E> collection = (Collection<E>) elements;
120      if (collection.isEmpty()) {
121        return ImmutableSet.of();
122      } else {
123        return ImmutableEnumSet.asImmutable(EnumSet.copyOf(collection));
124      }
125    } else {
126      Iterator<E> itr = elements.iterator();
127      if (itr.hasNext()) {
128        EnumSet<E> enumSet = EnumSet.of(itr.next());
129        Iterators.addAll(enumSet, itr);
130        return ImmutableEnumSet.asImmutable(enumSet);
131      } else {
132        return ImmutableSet.of();
133      }
134    }
135  }
136
137  /**
138   * Returns a new, <i>mutable</i> {@code EnumSet} instance containing the given elements in their
139   * natural order. This method behaves identically to {@link EnumSet#copyOf(Collection)}, but also
140   * accepts non-{@code Collection} iterables and empty iterables.
141   */
142  public static <E extends Enum<E>> EnumSet<E> newEnumSet(
143      Iterable<E> iterable, Class<E> elementType) {
144    EnumSet<E> set = EnumSet.noneOf(elementType);
145    Iterables.addAll(set, iterable);
146    return set;
147  }
148
149  // HashSet
150
151  /**
152   * Creates a <i>mutable</i>, initially empty {@code HashSet} instance.
153   *
154   * <p><b>Note:</b> if mutability is not required, use {@link ImmutableSet#of()} instead. If
155   * {@code E} is an {@link Enum} type, use {@link EnumSet#noneOf} instead. Otherwise, strongly
156   * consider using a {@code LinkedHashSet} instead, at the cost of increased memory footprint, to
157   * get deterministic iteration behavior.
158   *
159   * <p><b>Note for Java 7 and later:</b> this method is now unnecessary and should be treated as
160   * deprecated. Instead, use the {@code HashSet} constructor directly, taking advantage of the new
161   * <a href="http://goo.gl/iz2Wi">"diamond" syntax</a>.
162   */
163  public static <E> HashSet<E> newHashSet() {
164    return new HashSet<E>();
165  }
166
167  /**
168   * Creates a <i>mutable</i> {@code HashSet} instance initially containing the given elements.
169   *
170   * <p><b>Note:</b> if elements are non-null and won't be added or removed after this point, use
171   * {@link ImmutableSet#of()} or {@link ImmutableSet#copyOf(Object[])} instead. If {@code E} is an
172   * {@link Enum} type, use {@link EnumSet#of(Enum, Enum[])} instead. Otherwise, strongly consider
173   * using a {@code LinkedHashSet} instead, at the cost of increased memory footprint, to get
174   * deterministic iteration behavior.
175   *
176   * <p>This method is just a small convenience, either for {@code newHashSet(}{@link Arrays#asList
177   * asList}{@code (...))}, or for creating an empty set then calling {@link Collections#addAll}.
178   * This method is not actually very useful and will likely be deprecated in the future.
179   */
180  public static <E> HashSet<E> newHashSet(E... elements) {
181    HashSet<E> set = newHashSetWithExpectedSize(elements.length);
182    Collections.addAll(set, elements);
183    return set;
184  }
185
186  /**
187   * Creates a {@code HashSet} instance, with a high enough initial table size that it <i>should</i>
188   * hold {@code expectedSize} elements without resizing. This behavior cannot be broadly
189   * guaranteed, but it is observed to be true for OpenJDK 1.7. It also can't be guaranteed that the
190   * method isn't inadvertently <i>oversizing</i> the returned set.
191   *
192   * @param expectedSize the number of elements you expect to add to the
193   *        returned set
194   * @return a new, empty {@code HashSet} with enough capacity to hold {@code
195   *         expectedSize} elements without resizing
196   * @throws IllegalArgumentException if {@code expectedSize} is negative
197   */
198  public static <E> HashSet<E> newHashSetWithExpectedSize(int expectedSize) {
199    return new HashSet<E>(Maps.capacity(expectedSize));
200  }
201
202  /**
203   * Creates a <i>mutable</i> {@code HashSet} instance containing the given elements. A very thin
204   * convenience for creating an empty set then calling {@link Collection#addAll} or {@link
205   * Iterables#addAll}.
206   *
207   * <p><b>Note:</b> if mutability is not required and the elements are non-null, use {@link
208   * ImmutableSet#copyOf(Iterable)} instead. (Or, change {@code elements} to be a {@link
209   * FluentIterable} and call {@code elements.toSet()}.)
210   *
211   * <p><b>Note:</b> if {@code E} is an {@link Enum} type, use {@link #newEnumSet(Iterable, Class)}
212   * instead.
213   *
214   * <p><b>Note for Java 7 and later:</b> if {@code elements} is a {@link Collection}, you don't
215   * need this method. Instead, use the {@code HashSet} constructor directly, taking advantage of
216   * the new <a href="http://goo.gl/iz2Wi">"diamond" syntax</a>.
217   *
218   * <p>Overall, this method is not very useful and will likely be deprecated in the future.
219   */
220  public static <E> HashSet<E> newHashSet(Iterable<? extends E> elements) {
221    return (elements instanceof Collection)
222        ? new HashSet<E>(Collections2.cast(elements))
223        : newHashSet(elements.iterator());
224  }
225
226  /**
227   * Creates a <i>mutable</i> {@code HashSet} instance containing the given elements. A very thin
228   * convenience for creating an empty set and then calling {@link Iterators#addAll}.
229   *
230   * <p><b>Note:</b> if mutability is not required and the elements are non-null, use {@link
231   * ImmutableSet#copyOf(Iterator)} instead.
232   *
233   * <p><b>Note:</b> if {@code E} is an {@link Enum} type, you should create an {@link EnumSet}
234   * instead.
235   *
236   * <p>Overall, this method is not very useful and will likely be deprecated in the future.
237   */
238  public static <E> HashSet<E> newHashSet(Iterator<? extends E> elements) {
239    HashSet<E> set = newHashSet();
240    Iterators.addAll(set, elements);
241    return set;
242  }
243
244  /**
245   * Creates a thread-safe set backed by a hash map. The set is backed by a
246   * {@link ConcurrentHashMap} instance, and thus carries the same concurrency
247   * guarantees.
248   *
249   * <p>Unlike {@code HashSet}, this class does NOT allow {@code null} to be
250   * used as an element. The set is serializable.
251   *
252   * @return a new, empty thread-safe {@code Set}
253   * @since 15.0
254   */
255  public static <E> Set<E> newConcurrentHashSet() {
256    return newSetFromMap(new ConcurrentHashMap<E, Boolean>());
257  }
258
259  /**
260   * Creates a thread-safe set backed by a hash map and containing the given
261   * elements. The set is backed by a {@link ConcurrentHashMap} instance, and
262   * thus carries the same concurrency guarantees.
263   *
264   * <p>Unlike {@code HashSet}, this class does NOT allow {@code null} to be
265   * used as an element. The set is serializable.
266   *
267   * @param elements the elements that the set should contain
268   * @return a new thread-safe set containing those elements (minus duplicates)
269   * @throws NullPointerException if {@code elements} or any of its contents is
270   *      null
271   * @since 15.0
272   */
273  public static <E> Set<E> newConcurrentHashSet(Iterable<? extends E> elements) {
274    Set<E> set = newConcurrentHashSet();
275    Iterables.addAll(set, elements);
276    return set;
277  }
278
279  // LinkedHashSet
280
281  /**
282   * Creates a <i>mutable</i>, empty {@code LinkedHashSet} instance.
283   *
284   * <p><b>Note:</b> if mutability is not required, use {@link
285   * ImmutableSet#of()} instead.
286   *
287   * @return a new, empty {@code LinkedHashSet}
288   */
289  public static <E> LinkedHashSet<E> newLinkedHashSet() {
290    return new LinkedHashSet<E>();
291  }
292
293  /**
294   * Creates a {@code LinkedHashSet} instance, with a high enough "initial
295   * capacity" that it <i>should</i> hold {@code expectedSize} elements without
296   * growth. This behavior cannot be broadly guaranteed, but it is observed to
297   * be true for OpenJDK 1.6. It also can't be guaranteed that the method isn't
298   * inadvertently <i>oversizing</i> the returned set.
299   *
300   * @param expectedSize the number of elements you expect to add to the
301   *        returned set
302   * @return a new, empty {@code LinkedHashSet} with enough capacity to hold
303   *         {@code expectedSize} elements without resizing
304   * @throws IllegalArgumentException if {@code expectedSize} is negative
305   * @since 11.0
306   */
307  public static <E> LinkedHashSet<E> newLinkedHashSetWithExpectedSize(int expectedSize) {
308    return new LinkedHashSet<E>(Maps.capacity(expectedSize));
309  }
310
311  /**
312   * Creates a <i>mutable</i> {@code LinkedHashSet} instance containing the
313   * given elements in order.
314   *
315   * <p><b>Note:</b> if mutability is not required and the elements are
316   * non-null, use {@link ImmutableSet#copyOf(Iterable)} instead.
317   *
318   * @param elements the elements that the set should contain, in order
319   * @return a new {@code LinkedHashSet} containing those elements (minus
320   *     duplicates)
321   */
322  public static <E> LinkedHashSet<E> newLinkedHashSet(Iterable<? extends E> elements) {
323    if (elements instanceof Collection) {
324      return new LinkedHashSet<E>(Collections2.cast(elements));
325    }
326    LinkedHashSet<E> set = newLinkedHashSet();
327    Iterables.addAll(set, elements);
328    return set;
329  }
330
331  // TreeSet
332
333  /**
334   * Creates a <i>mutable</i>, empty {@code TreeSet} instance sorted by the
335   * natural sort ordering of its elements.
336   *
337   * <p><b>Note:</b> if mutability is not required, use {@link
338   * ImmutableSortedSet#of()} instead.
339   *
340   * @return a new, empty {@code TreeSet}
341   */
342  public static <E extends Comparable> TreeSet<E> newTreeSet() {
343    return new TreeSet<E>();
344  }
345
346  /**
347   * Creates a <i>mutable</i> {@code TreeSet} instance containing the given
348   * elements sorted by their natural ordering.
349   *
350   * <p><b>Note:</b> if mutability is not required, use {@link
351   * ImmutableSortedSet#copyOf(Iterable)} instead.
352   *
353   * <p><b>Note:</b> If {@code elements} is a {@code SortedSet} with an explicit
354   * comparator, this method has different behavior than
355   * {@link TreeSet#TreeSet(SortedSet)}, which returns a {@code TreeSet} with
356   * that comparator.
357   *
358   * @param elements the elements that the set should contain
359   * @return a new {@code TreeSet} containing those elements (minus duplicates)
360   */
361  public static <E extends Comparable> TreeSet<E> newTreeSet(Iterable<? extends E> elements) {
362    TreeSet<E> set = newTreeSet();
363    Iterables.addAll(set, elements);
364    return set;
365  }
366
367  /**
368   * Creates a <i>mutable</i>, empty {@code TreeSet} instance with the given
369   * comparator.
370   *
371   * <p><b>Note:</b> if mutability is not required, use {@code
372   * ImmutableSortedSet.orderedBy(comparator).build()} instead.
373   *
374   * @param comparator the comparator to use to sort the set
375   * @return a new, empty {@code TreeSet}
376   * @throws NullPointerException if {@code comparator} is null
377   */
378  public static <E> TreeSet<E> newTreeSet(Comparator<? super E> comparator) {
379    return new TreeSet<E>(checkNotNull(comparator));
380  }
381
382  /**
383   * Creates an empty {@code Set} that uses identity to determine equality. It
384   * compares object references, instead of calling {@code equals}, to
385   * determine whether a provided object matches an element in the set. For
386   * example, {@code contains} returns {@code false} when passed an object that
387   * equals a set member, but isn't the same instance. This behavior is similar
388   * to the way {@code IdentityHashMap} handles key lookups.
389   *
390   * @since 8.0
391   */
392  public static <E> Set<E> newIdentityHashSet() {
393    return Sets.newSetFromMap(Maps.<E, Boolean>newIdentityHashMap());
394  }
395
396  /**
397   * Creates an empty {@code CopyOnWriteArraySet} instance.
398   *
399   * <p><b>Note:</b> if you need an immutable empty {@link Set}, use
400   * {@link Collections#emptySet} instead.
401   *
402   * @return a new, empty {@code CopyOnWriteArraySet}
403   * @since 12.0
404   */
405  @GwtIncompatible("CopyOnWriteArraySet")
406  public static <E> CopyOnWriteArraySet<E> newCopyOnWriteArraySet() {
407    return new CopyOnWriteArraySet<E>();
408  }
409
410  /**
411   * Creates a {@code CopyOnWriteArraySet} instance containing the given elements.
412   *
413   * @param elements the elements that the set should contain, in order
414   * @return a new {@code CopyOnWriteArraySet} containing those elements
415   * @since 12.0
416   */
417  @GwtIncompatible("CopyOnWriteArraySet")
418  public static <E> CopyOnWriteArraySet<E> newCopyOnWriteArraySet(Iterable<? extends E> elements) {
419    // We copy elements to an ArrayList first, rather than incurring the
420    // quadratic cost of adding them to the COWAS directly.
421    Collection<? extends E> elementsCollection =
422        (elements instanceof Collection)
423            ? Collections2.cast(elements)
424            : Lists.newArrayList(elements);
425    return new CopyOnWriteArraySet<E>(elementsCollection);
426  }
427
428  /**
429   * Creates an {@code EnumSet} consisting of all enum values that are not in
430   * the specified collection. If the collection is an {@link EnumSet}, this
431   * method has the same behavior as {@link EnumSet#complementOf}. Otherwise,
432   * the specified collection must contain at least one element, in order to
433   * determine the element type. If the collection could be empty, use
434   * {@link #complementOf(Collection, Class)} instead of this method.
435   *
436   * @param collection the collection whose complement should be stored in the
437   *     enum set
438   * @return a new, modifiable {@code EnumSet} containing all values of the enum
439   *     that aren't present in the given collection
440   * @throws IllegalArgumentException if {@code collection} is not an
441   *     {@code EnumSet} instance and contains no elements
442   */
443  public static <E extends Enum<E>> EnumSet<E> complementOf(Collection<E> collection) {
444    if (collection instanceof EnumSet) {
445      return EnumSet.complementOf((EnumSet<E>) collection);
446    }
447    checkArgument(
448        !collection.isEmpty(), "collection is empty; use the other version of this method");
449    Class<E> type = collection.iterator().next().getDeclaringClass();
450    return makeComplementByHand(collection, type);
451  }
452
453  /**
454   * Creates an {@code EnumSet} consisting of all enum values that are not in
455   * the specified collection. This is equivalent to
456   * {@link EnumSet#complementOf}, but can act on any input collection, as long
457   * as the elements are of enum type.
458   *
459   * @param collection the collection whose complement should be stored in the
460   *     {@code EnumSet}
461   * @param type the type of the elements in the set
462   * @return a new, modifiable {@code EnumSet} initially containing all the
463   *     values of the enum not present in the given collection
464   */
465  public static <E extends Enum<E>> EnumSet<E> complementOf(
466      Collection<E> collection, Class<E> type) {
467    checkNotNull(collection);
468    return (collection instanceof EnumSet)
469        ? EnumSet.complementOf((EnumSet<E>) collection)
470        : makeComplementByHand(collection, type);
471  }
472
473  private static <E extends Enum<E>> EnumSet<E> makeComplementByHand(
474      Collection<E> collection, Class<E> type) {
475    EnumSet<E> result = EnumSet.allOf(type);
476    result.removeAll(collection);
477    return result;
478  }
479
480  /**
481   * Returns a set backed by the specified map. The resulting set displays
482   * the same ordering, concurrency, and performance characteristics as the
483   * backing map. In essence, this factory method provides a {@link Set}
484   * implementation corresponding to any {@link Map} implementation. There is no
485   * need to use this method on a {@link Map} implementation that already has a
486   * corresponding {@link Set} implementation (such as {@link java.util.HashMap}
487   * or {@link java.util.TreeMap}).
488   *
489   * <p>Each method invocation on the set returned by this method results in
490   * exactly one method invocation on the backing map or its {@code keySet}
491   * view, with one exception. The {@code addAll} method is implemented as a
492   * sequence of {@code put} invocations on the backing map.
493   *
494   * <p>The specified map must be empty at the time this method is invoked,
495   * and should not be accessed directly after this method returns. These
496   * conditions are ensured if the map is created empty, passed directly
497   * to this method, and no reference to the map is retained, as illustrated
498   * in the following code fragment: <pre>  {@code
499   *
500   *   Set<Object> identityHashSet = Sets.newSetFromMap(
501   *       new IdentityHashMap<Object, Boolean>());}</pre>
502   *
503   * <p>The returned set is serializable if the backing map is.
504   *
505   * @param map the backing map
506   * @return the set backed by the map
507   * @throws IllegalArgumentException if {@code map} is not empty
508   * @deprecated Use {@link Collections#newSetFromMap} instead. This method
509   *     will be removed in August 2017.
510   */
511  @Deprecated
512  public static <E> Set<E> newSetFromMap(Map<E, Boolean> map) {
513    return Platform.newSetFromMap(map);
514  }
515
516  /**
517   * An unmodifiable view of a set which may be backed by other sets; this view
518   * will change as the backing sets do. Contains methods to copy the data into
519   * a new set which will then remain stable. There is usually no reason to
520   * retain a reference of type {@code SetView}; typically, you either use it
521   * as a plain {@link Set}, or immediately invoke {@link #immutableCopy} or
522   * {@link #copyInto} and forget the {@code SetView} itself.
523   *
524   * @since 2.0
525   */
526  public abstract static class SetView<E> extends AbstractSet<E> {
527    private SetView() {} // no subclasses but our own
528
529    /**
530     * Returns an immutable copy of the current contents of this set view.
531     * Does not support null elements.
532     *
533     * <p><b>Warning:</b> this may have unexpected results if a backing set of
534     * this view uses a nonstandard notion of equivalence, for example if it is
535     * a {@link TreeSet} using a comparator that is inconsistent with {@link
536     * Object#equals(Object)}.
537     */
538    public ImmutableSet<E> immutableCopy() {
539      return ImmutableSet.copyOf(this);
540    }
541
542    /**
543     * Copies the current contents of this set view into an existing set. This
544     * method has equivalent behavior to {@code set.addAll(this)}, assuming that
545     * all the sets involved are based on the same notion of equivalence.
546     *
547     * @return a reference to {@code set}, for convenience
548     */
549    // Note: S should logically extend Set<? super E> but can't due to either
550    // some javac bug or some weirdness in the spec, not sure which.
551    public <S extends Set<E>> S copyInto(S set) {
552      set.addAll(this);
553      return set;
554    }
555  }
556
557  /**
558   * Returns an unmodifiable <b>view</b> of the union of two sets. The returned
559   * set contains all elements that are contained in either backing set.
560   * Iterating over the returned set iterates first over all the elements of
561   * {@code set1}, then over each element of {@code set2}, in order, that is not
562   * contained in {@code set1}.
563   *
564   * <p>Results are undefined if {@code set1} and {@code set2} are sets based on
565   * different equivalence relations (as {@link HashSet}, {@link TreeSet}, and
566   * the {@link Map#keySet} of an {@code IdentityHashMap} all are).
567   *
568   * <p><b>Note:</b> The returned view performs better when {@code set1} is the
569   * smaller of the two sets. If you have reason to believe one of your sets
570   * will generally be smaller than the other, pass it first.
571   *
572   * <p>Further, note that the current implementation is not suitable for nested
573   * {@code union} views, i.e. the following should be avoided when in a loop:
574   * {@code union = Sets.union(union, anotherSet);}, since iterating over the resulting
575   * set has a cubic complexity to the depth of the nesting.
576   */
577  public static <E> SetView<E> union(final Set<? extends E> set1, final Set<? extends E> set2) {
578    checkNotNull(set1, "set1");
579    checkNotNull(set2, "set2");
580
581    final Set<? extends E> set2minus1 = difference(set2, set1);
582
583    return new SetView<E>() {
584      @Override
585      public int size() {
586        return set1.size() + set2minus1.size();
587      }
588
589      @Override
590      public boolean isEmpty() {
591        return set1.isEmpty() && set2.isEmpty();
592      }
593
594      @Override
595      public Iterator<E> iterator() {
596        return Iterators.unmodifiableIterator(
597            Iterators.concat(set1.iterator(), set2minus1.iterator()));
598      }
599
600      @Override
601      public boolean contains(Object object) {
602        return set1.contains(object) || set2.contains(object);
603      }
604
605      @Override
606      public <S extends Set<E>> S copyInto(S set) {
607        set.addAll(set1);
608        set.addAll(set2);
609        return set;
610      }
611
612      @Override
613      public ImmutableSet<E> immutableCopy() {
614        return new ImmutableSet.Builder<E>().addAll(set1).addAll(set2).build();
615      }
616    };
617  }
618
619  /**
620   * Returns an unmodifiable <b>view</b> of the intersection of two sets. The
621   * returned set contains all elements that are contained by both backing sets.
622   * The iteration order of the returned set matches that of {@code set1}.
623   *
624   * <p>Results are undefined if {@code set1} and {@code set2} are sets based
625   * on different equivalence relations (as {@code HashSet}, {@code TreeSet},
626   * and the keySet of an {@code IdentityHashMap} all are).
627   *
628   * <p><b>Note:</b> The returned view performs slightly better when {@code
629   * set1} is the smaller of the two sets. If you have reason to believe one of
630   * your sets will generally be smaller than the other, pass it first.
631   * Unfortunately, since this method sets the generic type of the returned set
632   * based on the type of the first set passed, this could in rare cases force
633   * you to make a cast, for example: <pre>   {@code
634   *
635   *   Set<Object> aFewBadObjects = ...
636   *   Set<String> manyBadStrings = ...
637   *
638   *   // impossible for a non-String to be in the intersection
639   *   SuppressWarnings("unchecked")
640   *   Set<String> badStrings = (Set) Sets.intersection(
641   *       aFewBadObjects, manyBadStrings);}</pre>
642   *
643   * <p>This is unfortunate, but should come up only very rarely.
644   */
645  public static <E> SetView<E> intersection(final Set<E> set1, final Set<?> set2) {
646    checkNotNull(set1, "set1");
647    checkNotNull(set2, "set2");
648
649    final Predicate<Object> inSet2 = Predicates.in(set2);
650    return new SetView<E>() {
651      @Override
652      public Iterator<E> iterator() {
653        return Iterators.filter(set1.iterator(), inSet2);
654      }
655
656      @Override
657      public int size() {
658        return Iterators.size(iterator());
659      }
660
661      @Override
662      public boolean isEmpty() {
663        return !iterator().hasNext();
664      }
665
666      @Override
667      public boolean contains(Object object) {
668        return set1.contains(object) && set2.contains(object);
669      }
670
671      @Override
672      public boolean containsAll(Collection<?> collection) {
673        return set1.containsAll(collection) && set2.containsAll(collection);
674      }
675    };
676  }
677
678  /**
679   * Returns an unmodifiable <b>view</b> of the difference of two sets. The
680   * returned set contains all elements that are contained by {@code set1} and
681   * not contained by {@code set2}. {@code set2} may also contain elements not
682   * present in {@code set1}; these are simply ignored. The iteration order of
683   * the returned set matches that of {@code set1}.
684   *
685   * <p>Results are undefined if {@code set1} and {@code set2} are sets based
686   * on different equivalence relations (as {@code HashSet}, {@code TreeSet},
687   * and the keySet of an {@code IdentityHashMap} all are).
688   */
689  public static <E> SetView<E> difference(final Set<E> set1, final Set<?> set2) {
690    checkNotNull(set1, "set1");
691    checkNotNull(set2, "set2");
692
693    final Predicate<Object> notInSet2 = Predicates.not(Predicates.in(set2));
694    return new SetView<E>() {
695      @Override
696      public Iterator<E> iterator() {
697        return Iterators.filter(set1.iterator(), notInSet2);
698      }
699
700      @Override
701      public int size() {
702        return Iterators.size(iterator());
703      }
704
705      @Override
706      public boolean isEmpty() {
707        return set2.containsAll(set1);
708      }
709
710      @Override
711      public boolean contains(Object element) {
712        return set1.contains(element) && !set2.contains(element);
713      }
714    };
715  }
716
717  /**
718   * Returns an unmodifiable <b>view</b> of the symmetric difference of two
719   * sets. The returned set contains all elements that are contained in either
720   * {@code set1} or {@code set2} but not in both. The iteration order of the
721   * returned set is undefined.
722   *
723   * <p>Results are undefined if {@code set1} and {@code set2} are sets based
724   * on different equivalence relations (as {@code HashSet}, {@code TreeSet},
725   * and the keySet of an {@code IdentityHashMap} all are).
726   *
727   * @since 3.0
728   */
729  public static <E> SetView<E> symmetricDifference(
730      final Set<? extends E> set1, final Set<? extends E> set2) {
731    checkNotNull(set1, "set1");
732    checkNotNull(set2, "set2");
733
734    return new SetView<E>() {
735      @Override
736      public Iterator<E> iterator() {
737        final Iterator<? extends E> itr1 = set1.iterator();
738        final Iterator<? extends E> itr2 = set2.iterator();
739        return new AbstractIterator<E>() {
740          @Override
741          public E computeNext() {
742            while (itr1.hasNext()) {
743              E elem1 = itr1.next();
744              if (!set2.contains(elem1)) {
745                return elem1;
746              }
747            }
748            while (itr2.hasNext()) {
749              E elem2 = itr2.next();
750              if (!set1.contains(elem2)) {
751                return elem2;
752              }
753            }
754            return endOfData();
755          }
756        };
757      }
758
759      @Override
760      public int size() {
761        return Iterators.size(iterator());
762      }
763
764      @Override
765      public boolean isEmpty() {
766        return set1.equals(set2);
767      }
768
769      @Override
770      public boolean contains(Object element) {
771        return set1.contains(element) ^ set2.contains(element);
772      }
773    };
774  }
775
776  /**
777   * Returns the elements of {@code unfiltered} that satisfy a predicate. The
778   * returned set is a live view of {@code unfiltered}; changes to one affect
779   * the other.
780   *
781   * <p>The resulting set's iterator does not support {@code remove()}, but all
782   * other set methods are supported. When given an element that doesn't satisfy
783   * the predicate, the set's {@code add()} and {@code addAll()} methods throw
784   * an {@link IllegalArgumentException}. When methods such as {@code
785   * removeAll()} and {@code clear()} are called on the filtered set, only
786   * elements that satisfy the filter will be removed from the underlying set.
787   *
788   * <p>The returned set isn't threadsafe or serializable, even if
789   * {@code unfiltered} is.
790   *
791   * <p>Many of the filtered set's methods, such as {@code size()}, iterate
792   * across every element in the underlying set and determine which elements
793   * satisfy the filter. When a live view is <i>not</i> needed, it may be faster
794   * to copy {@code Iterables.filter(unfiltered, predicate)} and use the copy.
795   *
796   * <p><b>Warning:</b> {@code predicate} must be <i>consistent with equals</i>,
797   * as documented at {@link Predicate#apply}. Do not provide a predicate such
798   * as {@code Predicates.instanceOf(ArrayList.class)}, which is inconsistent
799   * with equals. (See {@link Iterables#filter(Iterable, Class)} for related
800   * functionality.)
801   */
802  // TODO(kevinb): how to omit that last sentence when building GWT javadoc?
803  @CheckReturnValue
804  public static <E> Set<E> filter(Set<E> unfiltered, Predicate<? super E> predicate) {
805    if (unfiltered instanceof SortedSet) {
806      return filter((SortedSet<E>) unfiltered, predicate);
807    }
808    if (unfiltered instanceof FilteredSet) {
809      // Support clear(), removeAll(), and retainAll() when filtering a filtered
810      // collection.
811      FilteredSet<E> filtered = (FilteredSet<E>) unfiltered;
812      Predicate<E> combinedPredicate = Predicates.<E>and(filtered.predicate, predicate);
813      return new FilteredSet<E>((Set<E>) filtered.unfiltered, combinedPredicate);
814    }
815
816    return new FilteredSet<E>(checkNotNull(unfiltered), checkNotNull(predicate));
817  }
818
819  private static class FilteredSet<E> extends FilteredCollection<E> implements Set<E> {
820    FilteredSet(Set<E> unfiltered, Predicate<? super E> predicate) {
821      super(unfiltered, predicate);
822    }
823
824    @Override
825    public boolean equals(@Nullable Object object) {
826      return equalsImpl(this, object);
827    }
828
829    @Override
830    public int hashCode() {
831      return hashCodeImpl(this);
832    }
833  }
834
835  /**
836   * Returns the elements of a {@code SortedSet}, {@code unfiltered}, that
837   * satisfy a predicate. The returned set is a live view of {@code unfiltered};
838   * changes to one affect the other.
839   *
840   * <p>The resulting set's iterator does not support {@code remove()}, but all
841   * other set methods are supported. When given an element that doesn't satisfy
842   * the predicate, the set's {@code add()} and {@code addAll()} methods throw
843   * an {@link IllegalArgumentException}. When methods such as
844   * {@code removeAll()} and {@code clear()} are called on the filtered set,
845   * only elements that satisfy the filter will be removed from the underlying
846   * set.
847   *
848   * <p>The returned set isn't threadsafe or serializable, even if
849   * {@code unfiltered} is.
850   *
851   * <p>Many of the filtered set's methods, such as {@code size()}, iterate across
852   * every element in the underlying set and determine which elements satisfy
853   * the filter. When a live view is <i>not</i> needed, it may be faster to copy
854   * {@code Iterables.filter(unfiltered, predicate)} and use the copy.
855   *
856   * <p><b>Warning:</b> {@code predicate} must be <i>consistent with equals</i>,
857   * as documented at {@link Predicate#apply}. Do not provide a predicate such as
858   * {@code Predicates.instanceOf(ArrayList.class)}, which is inconsistent with
859   * equals. (See {@link Iterables#filter(Iterable, Class)} for related
860   * functionality.)
861   *
862   * @since 11.0
863   */
864  @CheckReturnValue
865  public static <E> SortedSet<E> filter(SortedSet<E> unfiltered, Predicate<? super E> predicate) {
866    return Platform.setsFilterSortedSet(unfiltered, predicate);
867  }
868
869  static <E> SortedSet<E> filterSortedIgnoreNavigable(
870      SortedSet<E> unfiltered, Predicate<? super E> predicate) {
871    if (unfiltered instanceof FilteredSet) {
872      // Support clear(), removeAll(), and retainAll() when filtering a filtered
873      // collection.
874      FilteredSet<E> filtered = (FilteredSet<E>) unfiltered;
875      Predicate<E> combinedPredicate = Predicates.<E>and(filtered.predicate, predicate);
876      return new FilteredSortedSet<E>((SortedSet<E>) filtered.unfiltered, combinedPredicate);
877    }
878
879    return new FilteredSortedSet<E>(checkNotNull(unfiltered), checkNotNull(predicate));
880  }
881
882  private static class FilteredSortedSet<E> extends FilteredSet<E> implements SortedSet<E> {
883
884    FilteredSortedSet(SortedSet<E> unfiltered, Predicate<? super E> predicate) {
885      super(unfiltered, predicate);
886    }
887
888    @Override
889    public Comparator<? super E> comparator() {
890      return ((SortedSet<E>) unfiltered).comparator();
891    }
892
893    @Override
894    public SortedSet<E> subSet(E fromElement, E toElement) {
895      return new FilteredSortedSet<E>(
896          ((SortedSet<E>) unfiltered).subSet(fromElement, toElement), predicate);
897    }
898
899    @Override
900    public SortedSet<E> headSet(E toElement) {
901      return new FilteredSortedSet<E>(((SortedSet<E>) unfiltered).headSet(toElement), predicate);
902    }
903
904    @Override
905    public SortedSet<E> tailSet(E fromElement) {
906      return new FilteredSortedSet<E>(((SortedSet<E>) unfiltered).tailSet(fromElement), predicate);
907    }
908
909    @Override
910    public E first() {
911      return iterator().next();
912    }
913
914    @Override
915    public E last() {
916      SortedSet<E> sortedUnfiltered = (SortedSet<E>) unfiltered;
917      while (true) {
918        E element = sortedUnfiltered.last();
919        if (predicate.apply(element)) {
920          return element;
921        }
922        sortedUnfiltered = sortedUnfiltered.headSet(element);
923      }
924    }
925  }
926
927  /**
928   * Returns the elements of a {@code NavigableSet}, {@code unfiltered}, that
929   * satisfy a predicate. The returned set is a live view of {@code unfiltered};
930   * changes to one affect the other.
931   *
932   * <p>The resulting set's iterator does not support {@code remove()}, but all
933   * other set methods are supported. When given an element that doesn't satisfy
934   * the predicate, the set's {@code add()} and {@code addAll()} methods throw
935   * an {@link IllegalArgumentException}. When methods such as
936   * {@code removeAll()} and {@code clear()} are called on the filtered set,
937   * only elements that satisfy the filter will be removed from the underlying
938   * set.
939   *
940   * <p>The returned set isn't threadsafe or serializable, even if
941   * {@code unfiltered} is.
942   *
943   * <p>Many of the filtered set's methods, such as {@code size()}, iterate across
944   * every element in the underlying set and determine which elements satisfy
945   * the filter. When a live view is <i>not</i> needed, it may be faster to copy
946   * {@code Iterables.filter(unfiltered, predicate)} and use the copy.
947   *
948   * <p><b>Warning:</b> {@code predicate} must be <i>consistent with equals</i>,
949   * as documented at {@link Predicate#apply}. Do not provide a predicate such as
950   * {@code Predicates.instanceOf(ArrayList.class)}, which is inconsistent with
951   * equals. (See {@link Iterables#filter(Iterable, Class)} for related
952   * functionality.)
953   *
954   * @since 14.0
955   */
956  @GwtIncompatible("NavigableSet")
957  @SuppressWarnings("unchecked")
958  @CheckReturnValue
959  public static <E> NavigableSet<E> filter(
960      NavigableSet<E> unfiltered, Predicate<? super E> predicate) {
961    if (unfiltered instanceof FilteredSet) {
962      // Support clear(), removeAll(), and retainAll() when filtering a filtered
963      // collection.
964      FilteredSet<E> filtered = (FilteredSet<E>) unfiltered;
965      Predicate<E> combinedPredicate = Predicates.<E>and(filtered.predicate, predicate);
966      return new FilteredNavigableSet<E>((NavigableSet<E>) filtered.unfiltered, combinedPredicate);
967    }
968
969    return new FilteredNavigableSet<E>(checkNotNull(unfiltered), checkNotNull(predicate));
970  }
971
972  @GwtIncompatible("NavigableSet")
973  private static class FilteredNavigableSet<E> extends FilteredSortedSet<E>
974      implements NavigableSet<E> {
975    FilteredNavigableSet(NavigableSet<E> unfiltered, Predicate<? super E> predicate) {
976      super(unfiltered, predicate);
977    }
978
979    NavigableSet<E> unfiltered() {
980      return (NavigableSet<E>) unfiltered;
981    }
982
983    @Override
984    @Nullable
985    public E lower(E e) {
986      return Iterators.getNext(headSet(e, false).descendingIterator(), null);
987    }
988
989    @Override
990    @Nullable
991    public E floor(E e) {
992      return Iterators.getNext(headSet(e, true).descendingIterator(), null);
993    }
994
995    @Override
996    public E ceiling(E e) {
997      return Iterables.getFirst(tailSet(e, true), null);
998    }
999
1000    @Override
1001    public E higher(E e) {
1002      return Iterables.getFirst(tailSet(e, false), null);
1003    }
1004
1005    @Override
1006    public E pollFirst() {
1007      return Iterables.removeFirstMatching(unfiltered(), predicate);
1008    }
1009
1010    @Override
1011    public E pollLast() {
1012      return Iterables.removeFirstMatching(unfiltered().descendingSet(), predicate);
1013    }
1014
1015    @Override
1016    public NavigableSet<E> descendingSet() {
1017      return Sets.filter(unfiltered().descendingSet(), predicate);
1018    }
1019
1020    @Override
1021    public Iterator<E> descendingIterator() {
1022      return Iterators.filter(unfiltered().descendingIterator(), predicate);
1023    }
1024
1025    @Override
1026    public E last() {
1027      return descendingIterator().next();
1028    }
1029
1030    @Override
1031    public NavigableSet<E> subSet(
1032        E fromElement, boolean fromInclusive, E toElement, boolean toInclusive) {
1033      return filter(
1034          unfiltered().subSet(fromElement, fromInclusive, toElement, toInclusive), predicate);
1035    }
1036
1037    @Override
1038    public NavigableSet<E> headSet(E toElement, boolean inclusive) {
1039      return filter(unfiltered().headSet(toElement, inclusive), predicate);
1040    }
1041
1042    @Override
1043    public NavigableSet<E> tailSet(E fromElement, boolean inclusive) {
1044      return filter(unfiltered().tailSet(fromElement, inclusive), predicate);
1045    }
1046  }
1047
1048  /**
1049   * Returns every possible list that can be formed by choosing one element
1050   * from each of the given sets in order; the "n-ary
1051   * <a href="http://en.wikipedia.org/wiki/Cartesian_product">Cartesian
1052   * product</a>" of the sets. For example: <pre>   {@code
1053   *
1054   *   Sets.cartesianProduct(ImmutableList.of(
1055   *       ImmutableSet.of(1, 2),
1056   *       ImmutableSet.of("A", "B", "C")))}</pre>
1057   *
1058   * <p>returns a set containing six lists:
1059   *
1060   * <ul>
1061   * <li>{@code ImmutableList.of(1, "A")}
1062   * <li>{@code ImmutableList.of(1, "B")}
1063   * <li>{@code ImmutableList.of(1, "C")}
1064   * <li>{@code ImmutableList.of(2, "A")}
1065   * <li>{@code ImmutableList.of(2, "B")}
1066   * <li>{@code ImmutableList.of(2, "C")}
1067   * </ul>
1068   *
1069   * <p>The result is guaranteed to be in the "traditional", lexicographical
1070   * order for Cartesian products that you would get from nesting for loops:
1071   * <pre>   {@code
1072   *
1073   *   for (B b0 : sets.get(0)) {
1074   *     for (B b1 : sets.get(1)) {
1075   *       ...
1076   *       ImmutableList<B> tuple = ImmutableList.of(b0, b1, ...);
1077   *       // operate on tuple
1078   *     }
1079   *   }}</pre>
1080   *
1081   * <p>Note that if any input set is empty, the Cartesian product will also be
1082   * empty. If no sets at all are provided (an empty list), the resulting
1083   * Cartesian product has one element, an empty list (counter-intuitive, but
1084   * mathematically consistent).
1085   *
1086   * <p><i>Performance notes:</i> while the cartesian product of sets of size
1087   * {@code m, n, p} is a set of size {@code m x n x p}, its actual memory
1088   * consumption is much smaller. When the cartesian set is constructed, the
1089   * input sets are merely copied. Only as the resulting set is iterated are the
1090   * individual lists created, and these are not retained after iteration.
1091   *
1092   * @param sets the sets to choose elements from, in the order that
1093   *     the elements chosen from those sets should appear in the resulting
1094   *     lists
1095   * @param <B> any common base class shared by all axes (often just {@link
1096   *     Object})
1097   * @return the Cartesian product, as an immutable set containing immutable
1098   *     lists
1099   * @throws NullPointerException if {@code sets}, any one of the {@code sets},
1100   *     or any element of a provided set is null
1101   * @since 2.0
1102   */
1103  public static <B> Set<List<B>> cartesianProduct(List<? extends Set<? extends B>> sets) {
1104    return CartesianSet.create(sets);
1105  }
1106
1107  /**
1108   * Returns every possible list that can be formed by choosing one element
1109   * from each of the given sets in order; the "n-ary
1110   * <a href="http://en.wikipedia.org/wiki/Cartesian_product">Cartesian
1111   * product</a>" of the sets. For example: <pre>   {@code
1112   *
1113   *   Sets.cartesianProduct(
1114   *       ImmutableSet.of(1, 2),
1115   *       ImmutableSet.of("A", "B", "C"))}</pre>
1116   *
1117   * <p>returns a set containing six lists:
1118   *
1119   * <ul>
1120   * <li>{@code ImmutableList.of(1, "A")}
1121   * <li>{@code ImmutableList.of(1, "B")}
1122   * <li>{@code ImmutableList.of(1, "C")}
1123   * <li>{@code ImmutableList.of(2, "A")}
1124   * <li>{@code ImmutableList.of(2, "B")}
1125   * <li>{@code ImmutableList.of(2, "C")}
1126   * </ul>
1127   *
1128   * <p>The result is guaranteed to be in the "traditional", lexicographical
1129   * order for Cartesian products that you would get from nesting for loops:
1130   * <pre>   {@code
1131   *
1132   *   for (B b0 : sets.get(0)) {
1133   *     for (B b1 : sets.get(1)) {
1134   *       ...
1135   *       ImmutableList<B> tuple = ImmutableList.of(b0, b1, ...);
1136   *       // operate on tuple
1137   *     }
1138   *   }}</pre>
1139   *
1140   * <p>Note that if any input set is empty, the Cartesian product will also be
1141   * empty. If no sets at all are provided (an empty list), the resulting
1142   * Cartesian product has one element, an empty list (counter-intuitive, but
1143   * mathematically consistent).
1144   *
1145   * <p><i>Performance notes:</i> while the cartesian product of sets of size
1146   * {@code m, n, p} is a set of size {@code m x n x p}, its actual memory
1147   * consumption is much smaller. When the cartesian set is constructed, the
1148   * input sets are merely copied. Only as the resulting set is iterated are the
1149   * individual lists created, and these are not retained after iteration.
1150   *
1151   * @param sets the sets to choose elements from, in the order that
1152   *     the elements chosen from those sets should appear in the resulting
1153   *     lists
1154   * @param <B> any common base class shared by all axes (often just {@link
1155   *     Object})
1156   * @return the Cartesian product, as an immutable set containing immutable
1157   *     lists
1158   * @throws NullPointerException if {@code sets}, any one of the {@code sets},
1159   *     or any element of a provided set is null
1160   * @since 2.0
1161   */
1162  public static <B> Set<List<B>> cartesianProduct(Set<? extends B>... sets) {
1163    return cartesianProduct(Arrays.asList(sets));
1164  }
1165
1166  private static final class CartesianSet<E> extends ForwardingCollection<List<E>>
1167      implements Set<List<E>> {
1168    private transient final ImmutableList<ImmutableSet<E>> axes;
1169    private transient final CartesianList<E> delegate;
1170
1171    static <E> Set<List<E>> create(List<? extends Set<? extends E>> sets) {
1172      ImmutableList.Builder<ImmutableSet<E>> axesBuilder =
1173          new ImmutableList.Builder<ImmutableSet<E>>(sets.size());
1174      for (Set<? extends E> set : sets) {
1175        ImmutableSet<E> copy = ImmutableSet.copyOf(set);
1176        if (copy.isEmpty()) {
1177          return ImmutableSet.of();
1178        }
1179        axesBuilder.add(copy);
1180      }
1181      final ImmutableList<ImmutableSet<E>> axes = axesBuilder.build();
1182      ImmutableList<List<E>> listAxes =
1183          new ImmutableList<List<E>>() {
1184            @Override
1185            public int size() {
1186              return axes.size();
1187            }
1188
1189            @Override
1190            public List<E> get(int index) {
1191              return axes.get(index).asList();
1192            }
1193
1194            @Override
1195            boolean isPartialView() {
1196              return true;
1197            }
1198          };
1199      return new CartesianSet<E>(axes, new CartesianList<E>(listAxes));
1200    }
1201
1202    private CartesianSet(ImmutableList<ImmutableSet<E>> axes, CartesianList<E> delegate) {
1203      this.axes = axes;
1204      this.delegate = delegate;
1205    }
1206
1207    @Override
1208    protected Collection<List<E>> delegate() {
1209      return delegate;
1210    }
1211
1212    @Override
1213    public boolean equals(@Nullable Object object) {
1214      // Warning: this is broken if size() == 0, so it is critical that we
1215      // substitute an empty ImmutableSet to the user in place of this
1216      if (object instanceof CartesianSet) {
1217        CartesianSet<?> that = (CartesianSet<?>) object;
1218        return this.axes.equals(that.axes);
1219      }
1220      return super.equals(object);
1221    }
1222
1223    @Override
1224    public int hashCode() {
1225      // Warning: this is broken if size() == 0, so it is critical that we
1226      // substitute an empty ImmutableSet to the user in place of this
1227
1228      // It's a weird formula, but tests prove it works.
1229      int adjust = size() - 1;
1230      for (int i = 0; i < axes.size(); i++) {
1231        adjust *= 31;
1232        adjust = ~~adjust;
1233        // in GWT, we have to deal with integer overflow carefully
1234      }
1235      int hash = 1;
1236      for (Set<E> axis : axes) {
1237        hash = 31 * hash + (size() / axis.size() * axis.hashCode());
1238
1239        hash = ~~hash;
1240      }
1241      hash += adjust;
1242      return ~~hash;
1243    }
1244  }
1245
1246  /**
1247   * Returns the set of all possible subsets of {@code set}. For example,
1248   * {@code powerSet(ImmutableSet.of(1, 2))} returns the set {@code {{},
1249   * {1}, {2}, {1, 2}}}.
1250   *
1251   * <p>Elements appear in these subsets in the same iteration order as they
1252   * appeared in the input set. The order in which these subsets appear in the
1253   * outer set is undefined. Note that the power set of the empty set is not the
1254   * empty set, but a one-element set containing the empty set.
1255   *
1256   * <p>The returned set and its constituent sets use {@code equals} to decide
1257   * whether two elements are identical, even if the input set uses a different
1258   * concept of equivalence.
1259   *
1260   * <p><i>Performance notes:</i> while the power set of a set with size {@code
1261   * n} is of size {@code 2^n}, its memory usage is only {@code O(n)}. When the
1262   * power set is constructed, the input set is merely copied. Only as the
1263   * power set is iterated are the individual subsets created, and these subsets
1264   * themselves occupy only a small constant amount of memory.
1265   *
1266   * @param set the set of elements to construct a power set from
1267   * @return the power set, as an immutable set of immutable sets
1268   * @throws IllegalArgumentException if {@code set} has more than 30 unique
1269   *     elements (causing the power set size to exceed the {@code int} range)
1270   * @throws NullPointerException if {@code set} is or contains {@code null}
1271   * @see <a href="http://en.wikipedia.org/wiki/Power_set">Power set article at
1272   *      Wikipedia</a>
1273   * @since 4.0
1274   */
1275  @GwtCompatible(serializable = false)
1276  public static <E> Set<Set<E>> powerSet(Set<E> set) {
1277    return new PowerSet<E>(set);
1278  }
1279
1280  private static final class SubSet<E> extends AbstractSet<E> {
1281    private final ImmutableMap<E, Integer> inputSet;
1282    private final int mask;
1283
1284    SubSet(ImmutableMap<E, Integer> inputSet, int mask) {
1285      this.inputSet = inputSet;
1286      this.mask = mask;
1287    }
1288
1289    @Override
1290    public Iterator<E> iterator() {
1291      return new UnmodifiableIterator<E>() {
1292        final ImmutableList<E> elements = inputSet.keySet().asList();
1293        int remainingSetBits = mask;
1294
1295        @Override
1296        public boolean hasNext() {
1297          return remainingSetBits != 0;
1298        }
1299
1300        @Override
1301        public E next() {
1302          int index = Integer.numberOfTrailingZeros(remainingSetBits);
1303          if (index == 32) {
1304            throw new NoSuchElementException();
1305          }
1306          remainingSetBits &= ~(1 << index);
1307          return elements.get(index);
1308        }
1309      };
1310    }
1311
1312    @Override
1313    public int size() {
1314      return Integer.bitCount(mask);
1315    }
1316
1317    @Override
1318    public boolean contains(@Nullable Object o) {
1319      Integer index = inputSet.get(o);
1320      return index != null && (mask & (1 << index)) != 0;
1321    }
1322  }
1323
1324  private static final class PowerSet<E> extends AbstractSet<Set<E>> {
1325    final ImmutableMap<E, Integer> inputSet;
1326
1327    PowerSet(Set<E> input) {
1328      this.inputSet = Maps.indexMap(input);
1329      checkArgument(
1330          inputSet.size() <= 30, "Too many elements to create power set: %s > 30", inputSet.size());
1331    }
1332
1333    @Override
1334    public int size() {
1335      return 1 << inputSet.size();
1336    }
1337
1338    @Override
1339    public boolean isEmpty() {
1340      return false;
1341    }
1342
1343    @Override
1344    public Iterator<Set<E>> iterator() {
1345      return new AbstractIndexedListIterator<Set<E>>(size()) {
1346        @Override
1347        protected Set<E> get(final int setBits) {
1348          return new SubSet<E>(inputSet, setBits);
1349        }
1350      };
1351    }
1352
1353    @Override
1354    public boolean contains(@Nullable Object obj) {
1355      if (obj instanceof Set) {
1356        Set<?> set = (Set<?>) obj;
1357        return inputSet.keySet().containsAll(set);
1358      }
1359      return false;
1360    }
1361
1362    @Override
1363    public boolean equals(@Nullable Object obj) {
1364      if (obj instanceof PowerSet) {
1365        PowerSet<?> that = (PowerSet<?>) obj;
1366        return inputSet.equals(that.inputSet);
1367      }
1368      return super.equals(obj);
1369    }
1370
1371    @Override
1372    public int hashCode() {
1373      /*
1374       * The sum of the sums of the hash codes in each subset is just the sum of
1375       * each input element's hash code times the number of sets that element
1376       * appears in. Each element appears in exactly half of the 2^n sets, so:
1377       */
1378      return inputSet.keySet().hashCode() << (inputSet.size() - 1);
1379    }
1380
1381    @Override
1382    public String toString() {
1383      return "powerSet(" + inputSet + ")";
1384    }
1385  }
1386
1387  /**
1388   * An implementation for {@link Set#hashCode()}.
1389   */
1390  static int hashCodeImpl(Set<?> s) {
1391    int hashCode = 0;
1392    for (Object o : s) {
1393      hashCode += o != null ? o.hashCode() : 0;
1394
1395      hashCode = ~~hashCode;
1396      // Needed to deal with unusual integer overflow in GWT.
1397    }
1398    return hashCode;
1399  }
1400
1401  /**
1402   * An implementation for {@link Set#equals(Object)}.
1403   */
1404  static boolean equalsImpl(Set<?> s, @Nullable Object object) {
1405    if (s == object) {
1406      return true;
1407    }
1408    if (object instanceof Set) {
1409      Set<?> o = (Set<?>) object;
1410
1411      try {
1412        return s.size() == o.size() && s.containsAll(o);
1413      } catch (NullPointerException ignored) {
1414        return false;
1415      } catch (ClassCastException ignored) {
1416        return false;
1417      }
1418    }
1419    return false;
1420  }
1421
1422  /**
1423   * Returns an unmodifiable view of the specified navigable set. This method
1424   * allows modules to provide users with "read-only" access to internal
1425   * navigable sets. Query operations on the returned set "read through" to the
1426   * specified set, and attempts to modify the returned set, whether direct or
1427   * via its collection views, result in an
1428   * {@code UnsupportedOperationException}.
1429   *
1430   * <p>The returned navigable set will be serializable if the specified
1431   * navigable set is serializable.
1432   *
1433   * @param set the navigable set for which an unmodifiable view is to be
1434   *        returned
1435   * @return an unmodifiable view of the specified navigable set
1436   * @since 12.0
1437   */
1438  @GwtIncompatible("NavigableSet")
1439  public static <E> NavigableSet<E> unmodifiableNavigableSet(NavigableSet<E> set) {
1440    if (set instanceof ImmutableSortedSet || set instanceof UnmodifiableNavigableSet) {
1441      return set;
1442    }
1443    return new UnmodifiableNavigableSet<E>(set);
1444  }
1445
1446  @GwtIncompatible("NavigableSet")
1447  static final class UnmodifiableNavigableSet<E> extends ForwardingSortedSet<E>
1448      implements NavigableSet<E>, Serializable {
1449    private final NavigableSet<E> delegate;
1450
1451    UnmodifiableNavigableSet(NavigableSet<E> delegate) {
1452      this.delegate = checkNotNull(delegate);
1453    }
1454
1455    @Override
1456    protected SortedSet<E> delegate() {
1457      return Collections.unmodifiableSortedSet(delegate);
1458    }
1459
1460    @Override
1461    public E lower(E e) {
1462      return delegate.lower(e);
1463    }
1464
1465    @Override
1466    public E floor(E e) {
1467      return delegate.floor(e);
1468    }
1469
1470    @Override
1471    public E ceiling(E e) {
1472      return delegate.ceiling(e);
1473    }
1474
1475    @Override
1476    public E higher(E e) {
1477      return delegate.higher(e);
1478    }
1479
1480    @Override
1481    public E pollFirst() {
1482      throw new UnsupportedOperationException();
1483    }
1484
1485    @Override
1486    public E pollLast() {
1487      throw new UnsupportedOperationException();
1488    }
1489
1490    private transient UnmodifiableNavigableSet<E> descendingSet;
1491
1492    @Override
1493    public NavigableSet<E> descendingSet() {
1494      UnmodifiableNavigableSet<E> result = descendingSet;
1495      if (result == null) {
1496        result = descendingSet = new UnmodifiableNavigableSet<E>(delegate.descendingSet());
1497        result.descendingSet = this;
1498      }
1499      return result;
1500    }
1501
1502    @Override
1503    public Iterator<E> descendingIterator() {
1504      return Iterators.unmodifiableIterator(delegate.descendingIterator());
1505    }
1506
1507    @Override
1508    public NavigableSet<E> subSet(
1509        E fromElement, boolean fromInclusive, E toElement, boolean toInclusive) {
1510      return unmodifiableNavigableSet(
1511          delegate.subSet(fromElement, fromInclusive, toElement, toInclusive));
1512    }
1513
1514    @Override
1515    public NavigableSet<E> headSet(E toElement, boolean inclusive) {
1516      return unmodifiableNavigableSet(delegate.headSet(toElement, inclusive));
1517    }
1518
1519    @Override
1520    public NavigableSet<E> tailSet(E fromElement, boolean inclusive) {
1521      return unmodifiableNavigableSet(delegate.tailSet(fromElement, inclusive));
1522    }
1523
1524    private static final long serialVersionUID = 0;
1525  }
1526
1527  /**
1528   * Returns a synchronized (thread-safe) navigable set backed by the specified
1529   * navigable set.  In order to guarantee serial access, it is critical that
1530   * <b>all</b> access to the backing navigable set is accomplished
1531   * through the returned navigable set (or its views).
1532   *
1533   * <p>It is imperative that the user manually synchronize on the returned
1534   * sorted set when iterating over it or any of its {@code descendingSet},
1535   * {@code subSet}, {@code headSet}, or {@code tailSet} views. <pre>   {@code
1536   *
1537   *   NavigableSet<E> set = synchronizedNavigableSet(new TreeSet<E>());
1538   *    ...
1539   *   synchronized (set) {
1540   *     // Must be in the synchronized block
1541   *     Iterator<E> it = set.iterator();
1542   *     while (it.hasNext()) {
1543   *       foo(it.next());
1544   *     }
1545   *   }}</pre>
1546   *
1547   * <p>or: <pre>   {@code
1548   *
1549   *   NavigableSet<E> set = synchronizedNavigableSet(new TreeSet<E>());
1550   *   NavigableSet<E> set2 = set.descendingSet().headSet(foo);
1551   *    ...
1552   *   synchronized (set) { // Note: set, not set2!!!
1553   *     // Must be in the synchronized block
1554   *     Iterator<E> it = set2.descendingIterator();
1555   *     while (it.hasNext())
1556   *       foo(it.next());
1557   *     }
1558   *   }}</pre>
1559   *
1560   * <p>Failure to follow this advice may result in non-deterministic behavior.
1561   *
1562   * <p>The returned navigable set will be serializable if the specified
1563   * navigable set is serializable.
1564   *
1565   * @param navigableSet the navigable set to be "wrapped" in a synchronized
1566   *    navigable set.
1567   * @return a synchronized view of the specified navigable set.
1568   * @since 13.0
1569   */
1570  @GwtIncompatible("NavigableSet")
1571  public static <E> NavigableSet<E> synchronizedNavigableSet(NavigableSet<E> navigableSet) {
1572    return Synchronized.navigableSet(navigableSet);
1573  }
1574
1575  /**
1576   * Remove each element in an iterable from a set.
1577   */
1578  static boolean removeAllImpl(Set<?> set, Iterator<?> iterator) {
1579    boolean changed = false;
1580    while (iterator.hasNext()) {
1581      changed |= set.remove(iterator.next());
1582    }
1583    return changed;
1584  }
1585
1586  static boolean removeAllImpl(Set<?> set, Collection<?> collection) {
1587    checkNotNull(collection); // for GWT
1588    if (collection instanceof Multiset) {
1589      collection = ((Multiset<?>) collection).elementSet();
1590    }
1591    /*
1592     * AbstractSet.removeAll(List) has quadratic behavior if the list size
1593     * is just less than the set's size.  We augment the test by
1594     * assuming that sets have fast contains() performance, and other
1595     * collections don't.  See
1596     * http://code.google.com/p/guava-libraries/issues/detail?id=1013
1597     */
1598    if (collection instanceof Set && collection.size() > set.size()) {
1599      return Iterators.removeAll(set.iterator(), collection);
1600    } else {
1601      return removeAllImpl(set, collection.iterator());
1602    }
1603  }
1604
1605  @GwtIncompatible("NavigableSet")
1606  static class DescendingSet<E> extends ForwardingNavigableSet<E> {
1607    private final NavigableSet<E> forward;
1608
1609    DescendingSet(NavigableSet<E> forward) {
1610      this.forward = forward;
1611    }
1612
1613    @Override
1614    protected NavigableSet<E> delegate() {
1615      return forward;
1616    }
1617
1618    @Override
1619    public E lower(E e) {
1620      return forward.higher(e);
1621    }
1622
1623    @Override
1624    public E floor(E e) {
1625      return forward.ceiling(e);
1626    }
1627
1628    @Override
1629    public E ceiling(E e) {
1630      return forward.floor(e);
1631    }
1632
1633    @Override
1634    public E higher(E e) {
1635      return forward.lower(e);
1636    }
1637
1638    @Override
1639    public E pollFirst() {
1640      return forward.pollLast();
1641    }
1642
1643    @Override
1644    public E pollLast() {
1645      return forward.pollFirst();
1646    }
1647
1648    @Override
1649    public NavigableSet<E> descendingSet() {
1650      return forward;
1651    }
1652
1653    @Override
1654    public Iterator<E> descendingIterator() {
1655      return forward.iterator();
1656    }
1657
1658    @Override
1659    public NavigableSet<E> subSet(
1660        E fromElement, boolean fromInclusive, E toElement, boolean toInclusive) {
1661      return forward.subSet(toElement, toInclusive, fromElement, fromInclusive).descendingSet();
1662    }
1663
1664    @Override
1665    public NavigableSet<E> headSet(E toElement, boolean inclusive) {
1666      return forward.tailSet(toElement, inclusive).descendingSet();
1667    }
1668
1669    @Override
1670    public NavigableSet<E> tailSet(E fromElement, boolean inclusive) {
1671      return forward.headSet(fromElement, inclusive).descendingSet();
1672    }
1673
1674    @SuppressWarnings("unchecked")
1675    @Override
1676    public Comparator<? super E> comparator() {
1677      Comparator<? super E> forwardComparator = forward.comparator();
1678      if (forwardComparator == null) {
1679        return (Comparator) Ordering.natural().reverse();
1680      } else {
1681        return reverse(forwardComparator);
1682      }
1683    }
1684
1685    // If we inline this, we get a javac error.
1686    private static <T> Ordering<T> reverse(Comparator<T> forward) {
1687      return Ordering.from(forward).reverse();
1688    }
1689
1690    @Override
1691    public E first() {
1692      return forward.last();
1693    }
1694
1695    @Override
1696    public SortedSet<E> headSet(E toElement) {
1697      return standardHeadSet(toElement);
1698    }
1699
1700    @Override
1701    public E last() {
1702      return forward.first();
1703    }
1704
1705    @Override
1706    public SortedSet<E> subSet(E fromElement, E toElement) {
1707      return standardSubSet(fromElement, toElement);
1708    }
1709
1710    @Override
1711    public SortedSet<E> tailSet(E fromElement) {
1712      return standardTailSet(fromElement);
1713    }
1714
1715    @Override
1716    public Iterator<E> iterator() {
1717      return forward.descendingIterator();
1718    }
1719
1720    @Override
1721    public Object[] toArray() {
1722      return standardToArray();
1723    }
1724
1725    @Override
1726    public <T> T[] toArray(T[] array) {
1727      return standardToArray(array);
1728    }
1729
1730    @Override
1731    public String toString() {
1732      return standardToString();
1733    }
1734  }
1735}