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