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