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