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