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