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