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