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