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