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