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.compatqual.MonotonicNonNullDecl;
055import org.checkerframework.checker.nullness.compatqual.NullableDecl;
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    @MonotonicNonNullDecl 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(@NullableDecl 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    @NullableDecl
1212    public E lower(E e) {
1213      return Iterators.find(unfiltered().headSet(e, false).descendingIterator(), predicate, null);
1214    }
1215
1216    @Override
1217    @NullableDecl
1218    public E floor(E e) {
1219      return Iterators.find(unfiltered().headSet(e, true).descendingIterator(), predicate, null);
1220    }
1221
1222    @Override
1223    public E ceiling(E e) {
1224      return Iterables.find(unfiltered().tailSet(e, true), predicate, null);
1225    }
1226
1227    @Override
1228    public E higher(E e) {
1229      return Iterables.find(unfiltered().tailSet(e, false), predicate, null);
1230    }
1231
1232    @Override
1233    public E pollFirst() {
1234      return Iterables.removeFirstMatching(unfiltered(), predicate);
1235    }
1236
1237    @Override
1238    public E pollLast() {
1239      return Iterables.removeFirstMatching(unfiltered().descendingSet(), predicate);
1240    }
1241
1242    @Override
1243    public NavigableSet<E> descendingSet() {
1244      return Sets.filter(unfiltered().descendingSet(), predicate);
1245    }
1246
1247    @Override
1248    public Iterator<E> descendingIterator() {
1249      return Iterators.filter(unfiltered().descendingIterator(), predicate);
1250    }
1251
1252    @Override
1253    public E last() {
1254      return Iterators.find(unfiltered().descendingIterator(), predicate);
1255    }
1256
1257    @Override
1258    public NavigableSet<E> subSet(
1259        E fromElement, boolean fromInclusive, E toElement, boolean toInclusive) {
1260      return filter(
1261          unfiltered().subSet(fromElement, fromInclusive, toElement, toInclusive), predicate);
1262    }
1263
1264    @Override
1265    public NavigableSet<E> headSet(E toElement, boolean inclusive) {
1266      return filter(unfiltered().headSet(toElement, inclusive), predicate);
1267    }
1268
1269    @Override
1270    public NavigableSet<E> tailSet(E fromElement, boolean inclusive) {
1271      return filter(unfiltered().tailSet(fromElement, inclusive), predicate);
1272    }
1273  }
1274
1275  /**
1276   * Returns every possible list that can be formed by choosing one element from each of the given
1277   * sets in order; the "n-ary <a href="http://en.wikipedia.org/wiki/Cartesian_product">Cartesian
1278   * product</a>" of the sets. For example:
1279   *
1280   * <pre>{@code
1281   * Sets.cartesianProduct(ImmutableList.of(
1282   *     ImmutableSet.of(1, 2),
1283   *     ImmutableSet.of("A", "B", "C")))
1284   * }</pre>
1285   *
1286   * <p>returns a set containing six lists:
1287   *
1288   * <ul>
1289   *   <li>{@code ImmutableList.of(1, "A")}
1290   *   <li>{@code ImmutableList.of(1, "B")}
1291   *   <li>{@code ImmutableList.of(1, "C")}
1292   *   <li>{@code ImmutableList.of(2, "A")}
1293   *   <li>{@code ImmutableList.of(2, "B")}
1294   *   <li>{@code ImmutableList.of(2, "C")}
1295   * </ul>
1296   *
1297   * <p>The result is guaranteed to be in the "traditional", lexicographical order for Cartesian
1298   * products that you would get from nesting for loops:
1299   *
1300   * <pre>{@code
1301   * for (B b0 : sets.get(0)) {
1302   *   for (B b1 : sets.get(1)) {
1303   *     ...
1304   *     ImmutableList<B> tuple = ImmutableList.of(b0, b1, ...);
1305   *     // operate on tuple
1306   *   }
1307   * }
1308   * }</pre>
1309   *
1310   * <p>Note that if any input set is empty, the Cartesian product will also be empty. If no sets at
1311   * all are provided (an empty list), the resulting Cartesian product has one element, an empty
1312   * list (counter-intuitive, but mathematically consistent).
1313   *
1314   * <p><i>Performance notes:</i> while the cartesian product of sets of size {@code m, n, p} is a
1315   * set of size {@code m x n x p}, its actual memory consumption is much smaller. When the
1316   * cartesian set is constructed, the input sets are merely copied. Only as the resulting set is
1317   * iterated are the individual lists created, and these are not retained after iteration.
1318   *
1319   * @param sets the sets to choose elements from, in the order that the elements chosen from those
1320   *     sets should appear in the resulting lists
1321   * @param <B> any common base class shared by all axes (often just {@link Object})
1322   * @return the Cartesian product, as an immutable set containing immutable lists
1323   * @throws NullPointerException if {@code sets}, any one of the {@code sets}, or any element of a
1324   *     provided set is null
1325   * @since 2.0
1326   */
1327  public static <B> Set<List<B>> cartesianProduct(List<? extends Set<? extends B>> sets) {
1328    return CartesianSet.create(sets);
1329  }
1330
1331  /**
1332   * Returns every possible list that can be formed by choosing one element from each of the given
1333   * sets in order; the "n-ary <a href="http://en.wikipedia.org/wiki/Cartesian_product">Cartesian
1334   * product</a>" of the sets. For example:
1335   *
1336   * <pre>{@code
1337   * Sets.cartesianProduct(
1338   *     ImmutableSet.of(1, 2),
1339   *     ImmutableSet.of("A", "B", "C"))
1340   * }</pre>
1341   *
1342   * <p>returns a set containing six lists:
1343   *
1344   * <ul>
1345   *   <li>{@code ImmutableList.of(1, "A")}
1346   *   <li>{@code ImmutableList.of(1, "B")}
1347   *   <li>{@code ImmutableList.of(1, "C")}
1348   *   <li>{@code ImmutableList.of(2, "A")}
1349   *   <li>{@code ImmutableList.of(2, "B")}
1350   *   <li>{@code ImmutableList.of(2, "C")}
1351   * </ul>
1352   *
1353   * <p>The result is guaranteed to be in the "traditional", lexicographical order for Cartesian
1354   * products that you would get from nesting for loops:
1355   *
1356   * <pre>{@code
1357   * for (B b0 : sets.get(0)) {
1358   *   for (B b1 : sets.get(1)) {
1359   *     ...
1360   *     ImmutableList<B> tuple = ImmutableList.of(b0, b1, ...);
1361   *     // operate on tuple
1362   *   }
1363   * }
1364   * }</pre>
1365   *
1366   * <p>Note that if any input set is empty, the Cartesian product will also be empty. If no sets at
1367   * all are provided (an empty list), the resulting Cartesian product has one element, an empty
1368   * list (counter-intuitive, but mathematically consistent).
1369   *
1370   * <p><i>Performance notes:</i> while the cartesian product of sets of size {@code m, n, p} is a
1371   * set of size {@code m x n x p}, its actual memory consumption is much smaller. When the
1372   * cartesian set is constructed, the input sets are merely copied. Only as the resulting set is
1373   * iterated are the individual lists created, and these are not retained after iteration.
1374   *
1375   * @param sets the sets to choose elements from, in the order that the elements chosen from those
1376   *     sets should appear in the resulting lists
1377   * @param <B> any common base class shared by all axes (often just {@link Object})
1378   * @return the Cartesian product, as an immutable set containing immutable lists
1379   * @throws NullPointerException if {@code sets}, any one of the {@code sets}, or any element of a
1380   *     provided set is null
1381   * @since 2.0
1382   */
1383  public static <B> Set<List<B>> cartesianProduct(Set<? extends B>... sets) {
1384    return cartesianProduct(Arrays.asList(sets));
1385  }
1386
1387  private static final class CartesianSet<E> extends ForwardingCollection<List<E>>
1388      implements Set<List<E>> {
1389    private final transient ImmutableList<ImmutableSet<E>> axes;
1390    private final transient CartesianList<E> delegate;
1391
1392    static <E> Set<List<E>> create(List<? extends Set<? extends E>> sets) {
1393      ImmutableList.Builder<ImmutableSet<E>> axesBuilder = new ImmutableList.Builder<>(sets.size());
1394      for (Set<? extends E> set : sets) {
1395        ImmutableSet<E> copy = ImmutableSet.copyOf(set);
1396        if (copy.isEmpty()) {
1397          return ImmutableSet.of();
1398        }
1399        axesBuilder.add(copy);
1400      }
1401      final ImmutableList<ImmutableSet<E>> axes = axesBuilder.build();
1402      ImmutableList<List<E>> listAxes =
1403          new ImmutableList<List<E>>() {
1404            @Override
1405            public int size() {
1406              return axes.size();
1407            }
1408
1409            @Override
1410            public List<E> get(int index) {
1411              return axes.get(index).asList();
1412            }
1413
1414            @Override
1415            boolean isPartialView() {
1416              return true;
1417            }
1418          };
1419      return new CartesianSet<E>(axes, new CartesianList<E>(listAxes));
1420    }
1421
1422    private CartesianSet(ImmutableList<ImmutableSet<E>> axes, CartesianList<E> delegate) {
1423      this.axes = axes;
1424      this.delegate = delegate;
1425    }
1426
1427    @Override
1428    protected Collection<List<E>> delegate() {
1429      return delegate;
1430    }
1431
1432    @Override
1433    public boolean equals(@NullableDecl Object object) {
1434      // Warning: this is broken if size() == 0, so it is critical that we
1435      // substitute an empty ImmutableSet to the user in place of this
1436      if (object instanceof CartesianSet) {
1437        CartesianSet<?> that = (CartesianSet<?>) object;
1438        return this.axes.equals(that.axes);
1439      }
1440      return super.equals(object);
1441    }
1442
1443    @Override
1444    public int hashCode() {
1445      // Warning: this is broken if size() == 0, so it is critical that we
1446      // substitute an empty ImmutableSet to the user in place of this
1447
1448      // It's a weird formula, but tests prove it works.
1449      int adjust = size() - 1;
1450      for (int i = 0; i < axes.size(); i++) {
1451        adjust *= 31;
1452        adjust = ~~adjust;
1453        // in GWT, we have to deal with integer overflow carefully
1454      }
1455      int hash = 1;
1456      for (Set<E> axis : axes) {
1457        hash = 31 * hash + (size() / axis.size() * axis.hashCode());
1458
1459        hash = ~~hash;
1460      }
1461      hash += adjust;
1462      return ~~hash;
1463    }
1464  }
1465
1466  /**
1467   * Returns the set of all possible subsets of {@code set}. For example, {@code
1468   * powerSet(ImmutableSet.of(1, 2))} returns the set {@code {{}, {1}, {2}, {1, 2}}}.
1469   *
1470   * <p>Elements appear in these subsets in the same iteration order as they appeared in the input
1471   * set. The order in which these subsets appear in the outer set is undefined. Note that the power
1472   * set of the empty set is not the empty set, but a one-element set containing the empty set.
1473   *
1474   * <p>The returned set and its constituent sets use {@code equals} to decide whether two elements
1475   * are identical, even if the input set uses a different concept of equivalence.
1476   *
1477   * <p><i>Performance notes:</i> while the power set of a set with size {@code n} is of size {@code
1478   * 2^n}, its memory usage is only {@code O(n)}. When the power set is constructed, the input set
1479   * is merely copied. Only as the power set is iterated are the individual subsets created, and
1480   * these subsets themselves occupy only a small constant amount of memory.
1481   *
1482   * @param set the set of elements to construct a power set from
1483   * @return the power set, as an immutable set of immutable sets
1484   * @throws IllegalArgumentException if {@code set} has more than 30 unique elements (causing the
1485   *     power set size to exceed the {@code int} range)
1486   * @throws NullPointerException if {@code set} is or contains {@code null}
1487   * @see <a href="http://en.wikipedia.org/wiki/Power_set">Power set article at Wikipedia</a>
1488   * @since 4.0
1489   */
1490  @GwtCompatible(serializable = false)
1491  public static <E> Set<Set<E>> powerSet(Set<E> set) {
1492    return new PowerSet<E>(set);
1493  }
1494
1495  private static final class SubSet<E> extends AbstractSet<E> {
1496    private final ImmutableMap<E, Integer> inputSet;
1497    private final int mask;
1498
1499    SubSet(ImmutableMap<E, Integer> inputSet, int mask) {
1500      this.inputSet = inputSet;
1501      this.mask = mask;
1502    }
1503
1504    @Override
1505    public Iterator<E> iterator() {
1506      return new UnmodifiableIterator<E>() {
1507        final ImmutableList<E> elements = inputSet.keySet().asList();
1508        int remainingSetBits = mask;
1509
1510        @Override
1511        public boolean hasNext() {
1512          return remainingSetBits != 0;
1513        }
1514
1515        @Override
1516        public E next() {
1517          int index = Integer.numberOfTrailingZeros(remainingSetBits);
1518          if (index == 32) {
1519            throw new NoSuchElementException();
1520          }
1521          remainingSetBits &= ~(1 << index);
1522          return elements.get(index);
1523        }
1524      };
1525    }
1526
1527    @Override
1528    public int size() {
1529      return Integer.bitCount(mask);
1530    }
1531
1532    @Override
1533    public boolean contains(@NullableDecl Object o) {
1534      Integer index = inputSet.get(o);
1535      return index != null && (mask & (1 << index)) != 0;
1536    }
1537  }
1538
1539  private static final class PowerSet<E> extends AbstractSet<Set<E>> {
1540    final ImmutableMap<E, Integer> inputSet;
1541
1542    PowerSet(Set<E> input) {
1543      this.inputSet = Maps.indexMap(input);
1544      checkArgument(
1545          inputSet.size() <= 30, "Too many elements to create power set: %s > 30", inputSet.size());
1546    }
1547
1548    @Override
1549    public int size() {
1550      return 1 << inputSet.size();
1551    }
1552
1553    @Override
1554    public boolean isEmpty() {
1555      return false;
1556    }
1557
1558    @Override
1559    public Iterator<Set<E>> iterator() {
1560      return new AbstractIndexedListIterator<Set<E>>(size()) {
1561        @Override
1562        protected Set<E> get(final int setBits) {
1563          return new SubSet<E>(inputSet, setBits);
1564        }
1565      };
1566    }
1567
1568    @Override
1569    public boolean contains(@NullableDecl Object obj) {
1570      if (obj instanceof Set) {
1571        Set<?> set = (Set<?>) obj;
1572        return inputSet.keySet().containsAll(set);
1573      }
1574      return false;
1575    }
1576
1577    @Override
1578    public boolean equals(@NullableDecl Object obj) {
1579      if (obj instanceof PowerSet) {
1580        PowerSet<?> that = (PowerSet<?>) obj;
1581        return inputSet.equals(that.inputSet);
1582      }
1583      return super.equals(obj);
1584    }
1585
1586    @Override
1587    public int hashCode() {
1588      /*
1589       * The sum of the sums of the hash codes in each subset is just the sum of
1590       * each input element's hash code times the number of sets that element
1591       * appears in. Each element appears in exactly half of the 2^n sets, so:
1592       */
1593      return inputSet.keySet().hashCode() << (inputSet.size() - 1);
1594    }
1595
1596    @Override
1597    public String toString() {
1598      return "powerSet(" + inputSet + ")";
1599    }
1600  }
1601
1602  /**
1603   * Returns the set of all subsets of {@code set} of size {@code size}. For example, {@code
1604   * combinations(ImmutableSet.of(1, 2, 3), 2)} returns the set {@code {{1, 2}, {1, 3}, {2, 3}}}.
1605   *
1606   * <p>Elements appear in these subsets in the same iteration order as they appeared in the input
1607   * set. The order in which these subsets appear in the outer set is undefined.
1608   *
1609   * <p>The returned set and its constituent sets use {@code equals} to decide whether two elements
1610   * are identical, even if the input set uses a different concept of equivalence.
1611   *
1612   * <p><i>Performance notes:</i> the memory usage of the returned set is only {@code O(n)}. When
1613   * the result set is constructed, the input set is merely copied. Only as the result set is
1614   * iterated are the individual subsets created. Each of these subsets occupies an additional O(n)
1615   * memory but only for as long as the user retains a reference to it. That is, the set returned by
1616   * {@code combinations} does not retain the individual subsets.
1617   *
1618   * @param set the set of elements to take combinations of
1619   * @param size the number of elements per combination
1620   * @return the set of all combinations of {@code size} elements from {@code set}
1621   * @throws IllegalArgumentException if {@code size} is not between 0 and {@code set.size()}
1622   *     inclusive
1623   * @throws NullPointerException if {@code set} is or contains {@code null}
1624   * @since 23.0
1625   */
1626  @Beta
1627  public static <E> Set<Set<E>> combinations(Set<E> set, final int size) {
1628    final ImmutableMap<E, Integer> index = Maps.indexMap(set);
1629    checkNonnegative(size, "size");
1630    checkArgument(size <= index.size(), "size (%s) must be <= set.size() (%s)", size, index.size());
1631    if (size == 0) {
1632      return ImmutableSet.<Set<E>>of(ImmutableSet.<E>of());
1633    } else if (size == index.size()) {
1634      return ImmutableSet.<Set<E>>of(index.keySet());
1635    }
1636    return new AbstractSet<Set<E>>() {
1637      @Override
1638      public boolean contains(@NullableDecl Object o) {
1639        if (o instanceof Set) {
1640          Set<?> s = (Set<?>) o;
1641          return s.size() == size && index.keySet().containsAll(s);
1642        }
1643        return false;
1644      }
1645
1646      @Override
1647      public Iterator<Set<E>> iterator() {
1648        return new AbstractIterator<Set<E>>() {
1649          final BitSet bits = new BitSet(index.size());
1650
1651          @Override
1652          protected Set<E> computeNext() {
1653            if (bits.isEmpty()) {
1654              bits.set(0, size);
1655            } else {
1656              int firstSetBit = bits.nextSetBit(0);
1657              int bitToFlip = bits.nextClearBit(firstSetBit);
1658
1659              if (bitToFlip == index.size()) {
1660                return endOfData();
1661              }
1662
1663              /*
1664               * The current set in sorted order looks like
1665               * {firstSetBit, firstSetBit + 1, ..., bitToFlip - 1, ...}
1666               * where it does *not* contain bitToFlip.
1667               *
1668               * The next combination is
1669               *
1670               * {0, 1, ..., bitToFlip - firstSetBit - 2, bitToFlip, ...}
1671               *
1672               * This is lexicographically next if you look at the combinations in descending order
1673               * e.g. {2, 1, 0}, {3, 1, 0}, {3, 2, 0}, {3, 2, 1}, {4, 1, 0}...
1674               */
1675
1676              bits.set(0, bitToFlip - firstSetBit - 1);
1677              bits.clear(bitToFlip - firstSetBit - 1, bitToFlip);
1678              bits.set(bitToFlip);
1679            }
1680            final BitSet copy = (BitSet) bits.clone();
1681            return new AbstractSet<E>() {
1682              @Override
1683              public boolean contains(@NullableDecl Object o) {
1684                Integer i = index.get(o);
1685                return i != null && copy.get(i);
1686              }
1687
1688              @Override
1689              public Iterator<E> iterator() {
1690                return new AbstractIterator<E>() {
1691                  int i = -1;
1692
1693                  @Override
1694                  protected E computeNext() {
1695                    i = copy.nextSetBit(i + 1);
1696                    if (i == -1) {
1697                      return endOfData();
1698                    }
1699                    return index.keySet().asList().get(i);
1700                  }
1701                };
1702              }
1703
1704              @Override
1705              public int size() {
1706                return size;
1707              }
1708            };
1709          }
1710        };
1711      }
1712
1713      @Override
1714      public int size() {
1715        return IntMath.binomial(index.size(), size);
1716      }
1717
1718      @Override
1719      public String toString() {
1720        return "Sets.combinations(" + index.keySet() + ", " + size + ")";
1721      }
1722    };
1723  }
1724
1725  /** An implementation for {@link Set#hashCode()}. */
1726  static int hashCodeImpl(Set<?> s) {
1727    int hashCode = 0;
1728    for (Object o : s) {
1729      hashCode += o != null ? o.hashCode() : 0;
1730
1731      hashCode = ~~hashCode;
1732      // Needed to deal with unusual integer overflow in GWT.
1733    }
1734    return hashCode;
1735  }
1736
1737  /** An implementation for {@link Set#equals(Object)}. */
1738  static boolean equalsImpl(Set<?> s, @NullableDecl Object object) {
1739    if (s == object) {
1740      return true;
1741    }
1742    if (object instanceof Set) {
1743      Set<?> o = (Set<?>) object;
1744
1745      try {
1746        return s.size() == o.size() && s.containsAll(o);
1747      } catch (NullPointerException | ClassCastException ignored) {
1748        return false;
1749      }
1750    }
1751    return false;
1752  }
1753
1754  /**
1755   * Returns an unmodifiable view of the specified navigable set. This method allows modules to
1756   * provide users with "read-only" access to internal navigable sets. Query operations on the
1757   * returned set "read through" to the specified set, and attempts to modify the returned set,
1758   * whether direct or via its collection views, result in an {@code UnsupportedOperationException}.
1759   *
1760   * <p>The returned navigable set will be serializable if the specified navigable set is
1761   * serializable.
1762   *
1763   * @param set the navigable set for which an unmodifiable view is to be returned
1764   * @return an unmodifiable view of the specified navigable set
1765   * @since 12.0
1766   */
1767  public static <E> NavigableSet<E> unmodifiableNavigableSet(NavigableSet<E> set) {
1768    if (set instanceof ImmutableCollection || set instanceof UnmodifiableNavigableSet) {
1769      return set;
1770    }
1771    return new UnmodifiableNavigableSet<E>(set);
1772  }
1773
1774  static final class UnmodifiableNavigableSet<E> extends ForwardingSortedSet<E>
1775      implements NavigableSet<E>, Serializable {
1776    private final NavigableSet<E> delegate;
1777    private final SortedSet<E> unmodifiableDelegate;
1778
1779    UnmodifiableNavigableSet(NavigableSet<E> delegate) {
1780      this.delegate = checkNotNull(delegate);
1781      this.unmodifiableDelegate = Collections.unmodifiableSortedSet(delegate);
1782    }
1783
1784    @Override
1785    protected SortedSet<E> delegate() {
1786      return unmodifiableDelegate;
1787    }
1788
1789    // default methods not forwarded by ForwardingSortedSet
1790
1791    @Override
1792    public boolean removeIf(java.util.function.Predicate<? super E> filter) {
1793      throw new UnsupportedOperationException();
1794    }
1795
1796    @Override
1797    public Stream<E> stream() {
1798      return delegate.stream();
1799    }
1800
1801    @Override
1802    public Stream<E> parallelStream() {
1803      return delegate.parallelStream();
1804    }
1805
1806    @Override
1807    public void forEach(Consumer<? super E> action) {
1808      delegate.forEach(action);
1809    }
1810
1811    @Override
1812    public E lower(E e) {
1813      return delegate.lower(e);
1814    }
1815
1816    @Override
1817    public E floor(E e) {
1818      return delegate.floor(e);
1819    }
1820
1821    @Override
1822    public E ceiling(E e) {
1823      return delegate.ceiling(e);
1824    }
1825
1826    @Override
1827    public E higher(E e) {
1828      return delegate.higher(e);
1829    }
1830
1831    @Override
1832    public E pollFirst() {
1833      throw new UnsupportedOperationException();
1834    }
1835
1836    @Override
1837    public E pollLast() {
1838      throw new UnsupportedOperationException();
1839    }
1840
1841    @MonotonicNonNullDecl private transient UnmodifiableNavigableSet<E> descendingSet;
1842
1843    @Override
1844    public NavigableSet<E> descendingSet() {
1845      UnmodifiableNavigableSet<E> result = descendingSet;
1846      if (result == null) {
1847        result = descendingSet = new UnmodifiableNavigableSet<E>(delegate.descendingSet());
1848        result.descendingSet = this;
1849      }
1850      return result;
1851    }
1852
1853    @Override
1854    public Iterator<E> descendingIterator() {
1855      return Iterators.unmodifiableIterator(delegate.descendingIterator());
1856    }
1857
1858    @Override
1859    public NavigableSet<E> subSet(
1860        E fromElement, boolean fromInclusive, E toElement, boolean toInclusive) {
1861      return unmodifiableNavigableSet(
1862          delegate.subSet(fromElement, fromInclusive, toElement, toInclusive));
1863    }
1864
1865    @Override
1866    public NavigableSet<E> headSet(E toElement, boolean inclusive) {
1867      return unmodifiableNavigableSet(delegate.headSet(toElement, inclusive));
1868    }
1869
1870    @Override
1871    public NavigableSet<E> tailSet(E fromElement, boolean inclusive) {
1872      return unmodifiableNavigableSet(delegate.tailSet(fromElement, inclusive));
1873    }
1874
1875    private static final long serialVersionUID = 0;
1876  }
1877
1878  /**
1879   * Returns a synchronized (thread-safe) navigable set backed by the specified navigable set. In
1880   * order to guarantee serial access, it is critical that <b>all</b> access to the backing
1881   * navigable set is accomplished through the returned navigable set (or its views).
1882   *
1883   * <p>It is imperative that the user manually synchronize on the returned sorted set when
1884   * iterating over it or any of its {@code descendingSet}, {@code subSet}, {@code headSet}, or
1885   * {@code tailSet} views.
1886   *
1887   * <pre>{@code
1888   * NavigableSet<E> set = synchronizedNavigableSet(new TreeSet<E>());
1889   *  ...
1890   * synchronized (set) {
1891   *   // Must be in the synchronized block
1892   *   Iterator<E> it = set.iterator();
1893   *   while (it.hasNext()) {
1894   *     foo(it.next());
1895   *   }
1896   * }
1897   * }</pre>
1898   *
1899   * <p>or:
1900   *
1901   * <pre>{@code
1902   * NavigableSet<E> set = synchronizedNavigableSet(new TreeSet<E>());
1903   * NavigableSet<E> set2 = set.descendingSet().headSet(foo);
1904   *  ...
1905   * synchronized (set) { // Note: set, not set2!!!
1906   *   // Must be in the synchronized block
1907   *   Iterator<E> it = set2.descendingIterator();
1908   *   while (it.hasNext())
1909   *     foo(it.next());
1910   *   }
1911   * }
1912   * }</pre>
1913   *
1914   * <p>Failure to follow this advice may result in non-deterministic behavior.
1915   *
1916   * <p>The returned navigable set will be serializable if the specified navigable set is
1917   * serializable.
1918   *
1919   * @param navigableSet the navigable set to be "wrapped" in a synchronized navigable set.
1920   * @return a synchronized view of the specified navigable set.
1921   * @since 13.0
1922   */
1923  @GwtIncompatible // NavigableSet
1924  public static <E> NavigableSet<E> synchronizedNavigableSet(NavigableSet<E> navigableSet) {
1925    return Synchronized.navigableSet(navigableSet);
1926  }
1927
1928  /** Remove each element in an iterable from a set. */
1929  static boolean removeAllImpl(Set<?> set, Iterator<?> iterator) {
1930    boolean changed = false;
1931    while (iterator.hasNext()) {
1932      changed |= set.remove(iterator.next());
1933    }
1934    return changed;
1935  }
1936
1937  static boolean removeAllImpl(Set<?> set, Collection<?> collection) {
1938    checkNotNull(collection); // for GWT
1939    if (collection instanceof Multiset) {
1940      collection = ((Multiset<?>) collection).elementSet();
1941    }
1942    /*
1943     * AbstractSet.removeAll(List) has quadratic behavior if the list size
1944     * is just more than the set's size.  We augment the test by
1945     * assuming that sets have fast contains() performance, and other
1946     * collections don't.  See
1947     * http://code.google.com/p/guava-libraries/issues/detail?id=1013
1948     */
1949    if (collection instanceof Set && collection.size() > set.size()) {
1950      return Iterators.removeAll(set.iterator(), collection);
1951    } else {
1952      return removeAllImpl(set, collection.iterator());
1953    }
1954  }
1955
1956  @GwtIncompatible // NavigableSet
1957  static class DescendingSet<E> extends ForwardingNavigableSet<E> {
1958    private final NavigableSet<E> forward;
1959
1960    DescendingSet(NavigableSet<E> forward) {
1961      this.forward = forward;
1962    }
1963
1964    @Override
1965    protected NavigableSet<E> delegate() {
1966      return forward;
1967    }
1968
1969    @Override
1970    public E lower(E e) {
1971      return forward.higher(e);
1972    }
1973
1974    @Override
1975    public E floor(E e) {
1976      return forward.ceiling(e);
1977    }
1978
1979    @Override
1980    public E ceiling(E e) {
1981      return forward.floor(e);
1982    }
1983
1984    @Override
1985    public E higher(E e) {
1986      return forward.lower(e);
1987    }
1988
1989    @Override
1990    public E pollFirst() {
1991      return forward.pollLast();
1992    }
1993
1994    @Override
1995    public E pollLast() {
1996      return forward.pollFirst();
1997    }
1998
1999    @Override
2000    public NavigableSet<E> descendingSet() {
2001      return forward;
2002    }
2003
2004    @Override
2005    public Iterator<E> descendingIterator() {
2006      return forward.iterator();
2007    }
2008
2009    @Override
2010    public NavigableSet<E> subSet(
2011        E fromElement, boolean fromInclusive, E toElement, boolean toInclusive) {
2012      return forward.subSet(toElement, toInclusive, fromElement, fromInclusive).descendingSet();
2013    }
2014
2015    @Override
2016    public SortedSet<E> subSet(E fromElement, E toElement) {
2017      return standardSubSet(fromElement, toElement);
2018    }
2019
2020    @Override
2021    public NavigableSet<E> headSet(E toElement, boolean inclusive) {
2022      return forward.tailSet(toElement, inclusive).descendingSet();
2023    }
2024
2025    @Override
2026    public SortedSet<E> headSet(E toElement) {
2027      return standardHeadSet(toElement);
2028    }
2029
2030    @Override
2031    public NavigableSet<E> tailSet(E fromElement, boolean inclusive) {
2032      return forward.headSet(fromElement, inclusive).descendingSet();
2033    }
2034
2035    @Override
2036    public SortedSet<E> tailSet(E fromElement) {
2037      return standardTailSet(fromElement);
2038    }
2039
2040    @SuppressWarnings("unchecked")
2041    @Override
2042    public Comparator<? super E> comparator() {
2043      Comparator<? super E> forwardComparator = forward.comparator();
2044      if (forwardComparator == null) {
2045        return (Comparator) Ordering.natural().reverse();
2046      } else {
2047        return reverse(forwardComparator);
2048      }
2049    }
2050
2051    // If we inline this, we get a javac error.
2052    private static <T> Ordering<T> reverse(Comparator<T> forward) {
2053      return Ordering.from(forward).reverse();
2054    }
2055
2056    @Override
2057    public E first() {
2058      return forward.last();
2059    }
2060
2061    @Override
2062    public E last() {
2063      return forward.first();
2064    }
2065
2066    @Override
2067    public Iterator<E> iterator() {
2068      return forward.descendingIterator();
2069    }
2070
2071    @Override
2072    public Object[] toArray() {
2073      return standardToArray();
2074    }
2075
2076    @Override
2077    public <T> T[] toArray(T[] array) {
2078      return standardToArray(array);
2079    }
2080
2081    @Override
2082    public String toString() {
2083      return standardToString();
2084    }
2085  }
2086
2087  /**
2088   * Returns a view of the portion of {@code set} whose elements are contained by {@code range}.
2089   *
2090   * <p>This method delegates to the appropriate methods of {@link NavigableSet} (namely {@link
2091   * NavigableSet#subSet(Object, boolean, Object, boolean) subSet()}, {@link
2092   * NavigableSet#tailSet(Object, boolean) tailSet()}, and {@link NavigableSet#headSet(Object,
2093   * boolean) headSet()}) to actually construct the view. Consult these methods for a full
2094   * description of the returned view's behavior.
2095   *
2096   * <p><b>Warning:</b> {@code Range}s always represent a range of values using the values' natural
2097   * ordering. {@code NavigableSet} on the other hand can specify a custom ordering via a {@link
2098   * Comparator}, which can violate the natural ordering. Using this method (or in general using
2099   * {@code Range}) with unnaturally-ordered sets can lead to unexpected and undefined behavior.
2100   *
2101   * @since 20.0
2102   */
2103  @Beta
2104  @GwtIncompatible // NavigableSet
2105  public static <K extends Comparable<? super K>> NavigableSet<K> subSet(
2106      NavigableSet<K> set, Range<K> range) {
2107    if (set.comparator() != null
2108        && set.comparator() != Ordering.natural()
2109        && range.hasLowerBound()
2110        && range.hasUpperBound()) {
2111      checkArgument(
2112          set.comparator().compare(range.lowerEndpoint(), range.upperEndpoint()) <= 0,
2113          "set is using a custom comparator which is inconsistent with the natural ordering.");
2114    }
2115    if (range.hasLowerBound() && range.hasUpperBound()) {
2116      return set.subSet(
2117          range.lowerEndpoint(),
2118          range.lowerBoundType() == BoundType.CLOSED,
2119          range.upperEndpoint(),
2120          range.upperBoundType() == BoundType.CLOSED);
2121    } else if (range.hasLowerBound()) {
2122      return set.tailSet(range.lowerEndpoint(), range.lowerBoundType() == BoundType.CLOSED);
2123    } else if (range.hasUpperBound()) {
2124      return set.headSet(range.upperEndpoint(), range.upperBoundType() == BoundType.CLOSED);
2125    }
2126    return checkNotNull(set);
2127  }
2128}