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