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