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