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