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