001 /*
002 * Copyright (C) 2007 Google Inc.
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
017 package com.google.common.collect;
018
019 import static com.google.common.base.Preconditions.checkArgument;
020 import static com.google.common.base.Preconditions.checkNotNull;
021
022 import com.google.common.annotations.Beta;
023 import com.google.common.annotations.GwtCompatible;
024 import com.google.common.annotations.GwtIncompatible;
025 import com.google.common.base.Predicate;
026 import com.google.common.base.Predicates;
027 import com.google.common.collect.Collections2.FilteredCollection;
028 import com.google.common.primitives.Ints;
029
030 import java.io.IOException;
031 import java.io.ObjectInputStream;
032 import java.io.Serializable;
033 import java.util.AbstractSet;
034 import java.util.Arrays;
035 import java.util.Collection;
036 import java.util.Collections;
037 import java.util.Comparator;
038 import java.util.EnumSet;
039 import java.util.HashMap;
040 import java.util.HashSet;
041 import java.util.IdentityHashMap;
042 import java.util.Iterator;
043 import java.util.LinkedHashSet;
044 import java.util.List;
045 import java.util.Map;
046 import java.util.NoSuchElementException;
047 import java.util.Set;
048 import java.util.SortedSet;
049 import java.util.TreeMap;
050 import java.util.TreeSet;
051
052 import javax.annotation.Nullable;
053
054 /**
055 * Static utility methods pertaining to {@link Set} instances. Also see this
056 * class's counterparts {@link Lists} and {@link Maps}.
057 *
058 * @author Kevin Bourrillion
059 * @author Jared Levy
060 * @author Chris Povirk
061 * @since 2 (imported from Google Collections Library)
062 */
063 @GwtCompatible(emulated = true)
064 public final class Sets {
065 private Sets() {}
066
067 /**
068 * Returns an immutable set instance containing the given enum elements.
069 * Internally, the returned set will be backed by an {@link EnumSet}.
070 *
071 * <p>The iteration order of the returned set follows the enum's iteration
072 * order, not the order in which the elements are provided to the method.
073 *
074 * @param anElement one of the elements the set should contain
075 * @param otherElements the rest of the elements the set should contain
076 * @return an immutable set containing those elements, minus duplicates
077 */
078 // http://code.google.com/p/google-web-toolkit/issues/detail?id=3028
079 @GwtCompatible(serializable = true)
080 public static <E extends Enum<E>> ImmutableSet<E> immutableEnumSet(
081 E anElement, E... otherElements) {
082 return new ImmutableEnumSet<E>(EnumSet.of(anElement, otherElements));
083 }
084
085 /**
086 * Returns an immutable set instance containing the given enum elements.
087 * Internally, the returned set will be backed by an {@link EnumSet}.
088 *
089 * <p>The iteration order of the returned set follows the enum's iteration
090 * order, not the order in which the elements appear in the given collection.
091 *
092 * @param elements the elements, all of the same {@code enum} type, that the
093 * set should contain
094 * @return an immutable set containing those elements, minus duplicates
095 */
096 // http://code.google.com/p/google-web-toolkit/issues/detail?id=3028
097 @GwtCompatible(serializable = true)
098 public static <E extends Enum<E>> ImmutableSet<E> immutableEnumSet(
099 Iterable<E> elements) {
100 Iterator<E> iterator = elements.iterator();
101 if (!iterator.hasNext()) {
102 return ImmutableSet.of();
103 }
104 if (elements instanceof EnumSet) {
105 EnumSet<E> enumSetClone = EnumSet.copyOf((EnumSet<E>) elements);
106 return new ImmutableEnumSet<E>(enumSetClone);
107 }
108 E first = iterator.next();
109 EnumSet<E> set = EnumSet.of(first);
110 while (iterator.hasNext()) {
111 set.add(iterator.next());
112 }
113 return new ImmutableEnumSet<E>(set);
114 }
115
116 /**
117 * Returns a new {@code EnumSet} instance containing the given elements.
118 * Unlike {@link EnumSet#copyOf(Collection)}, this method does not produce an
119 * exception on an empty collection, and it may be called on any iterable, not
120 * just a {@code Collection}.
121 */
122 public static <E extends Enum<E>> EnumSet<E> newEnumSet(Iterable<E> iterable,
123 Class<E> elementType) {
124 /*
125 * TODO: noneOf() and addAll() will both throw NullPointerExceptions when
126 * appropriate. However, NullPointerTester will fail on this method because
127 * it passes in Class.class instead of an enum type. This means that, when
128 * iterable is null but elementType is not, noneOf() will throw a
129 * ClassCastException before addAll() has a chance to throw a
130 * NullPointerException. NullPointerTester considers this a failure.
131 * Ideally the test would be fixed, but it would require a special case for
132 * Class<E> where E extends Enum. Until that happens (if ever), leave
133 * checkNotNull() here. For now, contemplate the irony that checking
134 * elementType, the problem argument, is harmful, while checking iterable,
135 * the innocent bystander, is effective.
136 */
137 checkNotNull(iterable);
138 EnumSet<E> set = EnumSet.noneOf(elementType);
139 Iterables.addAll(set, iterable);
140 return set;
141 }
142
143 // HashSet
144
145 /**
146 * Creates a <i>mutable</i>, empty {@code HashSet} instance.
147 *
148 * <p><b>Note:</b> if mutability is not required, use {@link
149 * ImmutableSet#of()} instead.
150 *
151 * <p><b>Note:</b> if {@code E} is an {@link Enum} type, use {@link
152 * EnumSet#noneOf} instead.
153 *
154 * @return a new, empty {@code HashSet}
155 */
156 public static <E> HashSet<E> newHashSet() {
157 return new HashSet<E>();
158 }
159
160 /**
161 * Creates a <i>mutable</i> {@code HashSet} instance containing the given
162 * elements in unspecified order.
163 *
164 * <p><b>Note:</b> if mutability is not required and the elements are
165 * non-null, use an overload of {@link ImmutableSet#of()} (for varargs) or
166 * {@link ImmutableSet#copyOf(Object[])} (for an array) instead.
167 *
168 * <p><b>Note:</b> if {@code E} is an {@link Enum} type, use {@link
169 * EnumSet#of(Enum, Enum[])} instead.
170 *
171 * @param elements the elements that the set should contain
172 * @return a new {@code HashSet} containing those elements (minus duplicates)
173 */
174 public static <E> HashSet<E> newHashSet(E... elements) {
175 int capacity = Maps.capacity(elements.length);
176 HashSet<E> set = new HashSet<E>(capacity);
177 Collections.addAll(set, elements);
178 return set;
179 }
180
181 /**
182 * Creates an empty {@code HashSet} instance with enough capacity to hold the
183 * specified number of elements without rehashing.
184 *
185 * @param expectedSize the expected size
186 * @return a new, empty {@code HashSet} with enough capacity to hold {@code
187 * expectedSize} elements without rehashing
188 * @throws IllegalArgumentException if {@code expectedSize} is negative
189 */
190 public static <E> HashSet<E> newHashSetWithExpectedSize(int expectedSize) {
191 return new HashSet<E>(Maps.capacity(expectedSize));
192 }
193
194 /**
195 * Creates a <i>mutable</i> {@code HashSet} instance containing the given
196 * elements in unspecified order.
197 *
198 * <p><b>Note:</b> if mutability is not required and the elements are
199 * non-null, use {@link ImmutableSet#copyOf(Iterable)} instead.
200 *
201 * <p><b>Note:</b> if {@code E} is an {@link Enum} type, use
202 * {@link #newEnumSet(Iterable, Class)} instead.
203 *
204 * @param elements the elements that the set should contain
205 * @return a new {@code HashSet} containing those elements (minus duplicates)
206 */
207 public static <E> HashSet<E> newHashSet(Iterable<? extends E> elements) {
208 if (elements instanceof Collection) {
209 @SuppressWarnings("unchecked")
210 Collection<? extends E> collection = (Collection<? extends E>) elements;
211 return new HashSet<E>(collection);
212 } else {
213 return newHashSet(elements.iterator());
214 }
215 }
216
217 /**
218 * Creates a <i>mutable</i> {@code HashSet} instance containing the given
219 * elements in unspecified order.
220 *
221 * <p><b>Note:</b> if mutability is not required and the elements are
222 * non-null, use {@link ImmutableSet#copyOf(Iterable)} instead.
223 *
224 * <p><b>Note:</b> if {@code E} is an {@link Enum} type, you should create an
225 * {@link EnumSet} instead.
226 *
227 * @param elements the elements that the set should contain
228 * @return a new {@code HashSet} containing those elements (minus duplicates)
229 */
230 public static <E> HashSet<E> newHashSet(Iterator<? extends E> elements) {
231 HashSet<E> set = newHashSet();
232 while (elements.hasNext()) {
233 set.add(elements.next());
234 }
235 return set;
236 }
237
238 // LinkedHashSet
239
240 /**
241 * Creates a <i>mutable</i>, empty {@code LinkedHashSet} instance.
242 *
243 * <p><b>Note:</b> if mutability is not required, use {@link
244 * ImmutableSet#of()} instead.
245 *
246 * @return a new, empty {@code LinkedHashSet}
247 */
248 public static <E> LinkedHashSet<E> newLinkedHashSet() {
249 return new LinkedHashSet<E>();
250 }
251
252 /**
253 * Creates a <i>mutable</i> {@code LinkedHashSet} instance containing the
254 * given elements in order.
255 *
256 * <p><b>Note:</b> if mutability is not required and the elements are
257 * non-null, use {@link ImmutableSet#copyOf(Iterable)} instead.
258 *
259 * @param elements the elements that the set should contain, in order
260 * @return a new {@code LinkedHashSet} containing those elements (minus
261 * duplicates)
262 */
263 public static <E> LinkedHashSet<E> newLinkedHashSet(
264 Iterable<? extends E> elements) {
265 if (elements instanceof Collection) {
266 @SuppressWarnings("unchecked")
267 Collection<? extends E> collection = (Collection<? extends E>) elements;
268 return new LinkedHashSet<E>(collection);
269 }
270 LinkedHashSet<E> set = newLinkedHashSet();
271 for (E element : elements) {
272 set.add(element);
273 }
274 return set;
275 }
276
277 // TreeSet
278
279 /**
280 * Creates a <i>mutable</i>, empty {@code TreeSet} instance sorted by the
281 * natural sort ordering of its elements.
282 *
283 * <p><b>Note:</b> if mutability is not required, use {@link
284 * ImmutableSortedSet#of()} instead.
285 *
286 * @return a new, empty {@code TreeSet}
287 */
288 @SuppressWarnings("unchecked") // allow ungenerified Comparable types
289 public static <E extends Comparable> TreeSet<E> newTreeSet() {
290 return new TreeSet<E>();
291 }
292
293 /**
294 * Creates a <i>mutable</i> {@code TreeSet} instance containing the given
295 * elements sorted by their natural ordering.
296 *
297 * <p><b>Note:</b> if mutability is not required, use {@link
298 * ImmutableSortedSet#copyOf(Iterable)} instead.
299 *
300 * <p><b>Note:</b> If {@code elements} is a {@code SortedSet} with an explicit
301 * comparator, this method has different behavior than
302 * {@link TreeSet#TreeSet(SortedSet)}, which returns a {@code TreeSet} with
303 * that comparator.
304 *
305 * @param elements the elements that the set should contain
306 * @return a new {@code TreeSet} containing those elements (minus duplicates)
307 */
308 @SuppressWarnings("unchecked") // allow ungenerified Comparable types
309 public static <E extends Comparable> TreeSet<E> newTreeSet(
310 Iterable<? extends E> elements) {
311 TreeSet<E> set = newTreeSet();
312 for (E element : elements) {
313 set.add(element);
314 }
315 return set;
316 }
317
318 /**
319 * Creates a <i>mutable</i>, empty {@code TreeSet} instance with the given
320 * comparator.
321 *
322 * <p><b>Note:</b> if mutability is not required, use {@code
323 * ImmutableSortedSet.orderedBy(comparator).build()} instead.
324 *
325 * @param comparator the comparator to use to sort the set
326 * @return a new, empty {@code TreeSet}
327 * @throws NullPointerException if {@code comparator} is null
328 */
329 public static <E> TreeSet<E> newTreeSet(Comparator<? super E> comparator) {
330 return new TreeSet<E>(checkNotNull(comparator));
331 }
332
333 /**
334 * Creates an {@code EnumSet} consisting of all enum values that are not in
335 * the specified collection. If the collection is an {@link EnumSet}, this
336 * method has the same behavior as {@link EnumSet#complementOf}. Otherwise,
337 * the specified collection must contain at least one element, in order to
338 * determine the element type. If the collection could be empty, use
339 * {@link #complementOf(Collection, Class)} instead of this method.
340 *
341 * @param collection the collection whose complement should be stored in the
342 * enum set
343 * @return a new, modifiable {@code EnumSet} containing all values of the enum
344 * that aren't present in the given collection
345 * @throws IllegalArgumentException if {@code collection} is not an
346 * {@code EnumSet} instance and contains no elements
347 */
348 public static <E extends Enum<E>> EnumSet<E> complementOf(
349 Collection<E> collection) {
350 if (collection instanceof EnumSet) {
351 return EnumSet.complementOf((EnumSet<E>) collection);
352 }
353 checkArgument(!collection.isEmpty(),
354 "collection is empty; use the other version of this method");
355 Class<E> type = collection.iterator().next().getDeclaringClass();
356 return makeComplementByHand(collection, type);
357 }
358
359 /**
360 * Creates an {@code EnumSet} consisting of all enum values that are not in
361 * the specified collection. This is equivalent to
362 * {@link EnumSet#complementOf}, but can act on any input collection, as long
363 * as the elements are of enum type.
364 *
365 * @param collection the collection whose complement should be stored in the
366 * {@code EnumSet}
367 * @param type the type of the elements in the set
368 * @return a new, modifiable {@code EnumSet} initially containing all the
369 * values of the enum not present in the given collection
370 */
371 public static <E extends Enum<E>> EnumSet<E> complementOf(
372 Collection<E> collection, Class<E> type) {
373 checkNotNull(collection);
374 return (collection instanceof EnumSet)
375 ? EnumSet.complementOf((EnumSet<E>) collection)
376 : makeComplementByHand(collection, type);
377 }
378
379 private static <E extends Enum<E>> EnumSet<E> makeComplementByHand(
380 Collection<E> collection, Class<E> type) {
381 EnumSet<E> result = EnumSet.allOf(type);
382 result.removeAll(collection);
383 return result;
384 }
385
386 /*
387 * Regarding newSetForMap() and SetFromMap:
388 *
389 * Written by Doug Lea with assistance from members of JCP JSR-166
390 * Expert Group and released to the public domain, as explained at
391 * http://creativecommons.org/licenses/publicdomain
392 */
393
394 /**
395 * Returns a set backed by the specified map. The resulting set displays
396 * the same ordering, concurrency, and performance characteristics as the
397 * backing map. In essence, this factory method provides a {@link Set}
398 * implementation corresponding to any {@link Map} implementation. There is no
399 * need to use this method on a {@link Map} implementation that already has a
400 * corresponding {@link Set} implementation (such as {@link HashMap} or
401 * {@link TreeMap}).
402 *
403 * <p>Each method invocation on the set returned by this method results in
404 * exactly one method invocation on the backing map or its <tt>keySet</tt>
405 * view, with one exception. The <tt>addAll</tt> method is implemented as a
406 * sequence of <tt>put</tt> invocations on the backing map.
407 *
408 * <p>The specified map must be empty at the time this method is invoked,
409 * and should not be accessed directly after this method returns. These
410 * conditions are ensured if the map is created empty, passed directly
411 * to this method, and no reference to the map is retained, as illustrated
412 * in the following code fragment: <pre> {@code
413 *
414 * Set<Object> identityHashSet = Sets.newSetFromMap(
415 * new IdentityHashMap<Object, Boolean>());}</pre>
416 *
417 * This method has the same behavior as the JDK 6 method
418 * {@code Collections.newSetFromMap()}. The returned set is serializable if
419 * the backing map is.
420 *
421 * @param map the backing map
422 * @return the set backed by the map
423 * @throws IllegalArgumentException if <tt>map</tt> is not empty
424 */
425 public static <E> Set<E> newSetFromMap(Map<E, Boolean> map) {
426 return new SetFromMap<E>(map);
427 }
428
429 private static class SetFromMap<E> extends AbstractSet<E>
430 implements Set<E>, Serializable {
431 private final Map<E, Boolean> m; // The backing map
432 private transient Set<E> s; // Its keySet
433
434 SetFromMap(Map<E, Boolean> map) {
435 checkArgument(map.isEmpty(), "Map is non-empty");
436 m = map;
437 s = map.keySet();
438 }
439
440 @Override public void clear() {
441 m.clear();
442 }
443 @Override public int size() {
444 return m.size();
445 }
446 @Override public boolean isEmpty() {
447 return m.isEmpty();
448 }
449 @Override public boolean contains(Object o) {
450 return m.containsKey(o);
451 }
452 @Override public boolean remove(Object o) {
453 return m.remove(o) != null;
454 }
455 @Override public boolean add(E e) {
456 return m.put(e, Boolean.TRUE) == null;
457 }
458 @Override public Iterator<E> iterator() {
459 return s.iterator();
460 }
461 @Override public Object[] toArray() {
462 return s.toArray();
463 }
464 @Override public <T> T[] toArray(T[] a) {
465 return s.toArray(a);
466 }
467 @Override public String toString() {
468 return s.toString();
469 }
470 @Override public int hashCode() {
471 return s.hashCode();
472 }
473 @Override public boolean equals(@Nullable Object object) {
474 return this == object || this.s.equals(object);
475 }
476 @Override public boolean containsAll(Collection<?> c) {
477 return s.containsAll(c);
478 }
479 @Override public boolean removeAll(Collection<?> c) {
480 return s.removeAll(c);
481 }
482 @Override public boolean retainAll(Collection<?> c) {
483 return s.retainAll(c);
484 }
485
486 // addAll is the only inherited implementation
487 @GwtIncompatible("not needed in emulated source")
488 private static final long serialVersionUID = 0;
489
490 @GwtIncompatible("java.io.ObjectInputStream")
491 private void readObject(ObjectInputStream stream)
492 throws IOException, ClassNotFoundException {
493 stream.defaultReadObject();
494 s = m.keySet();
495 }
496 }
497
498 /**
499 * An unmodifiable view of a set which may be backed by other sets; this view
500 * will change as the backing sets do. Contains methods to copy the data into
501 * a new set which will then remain stable. There is usually no reason to
502 * retain a reference of type {@code SetView}; typically, you either use it
503 * as a plain {@link Set}, or immediately invoke {@link #immutableCopy} or
504 * {@link #copyInto} and forget the {@code SetView} itself.
505 */
506 public abstract static class SetView<E> extends AbstractSet<E> {
507 private SetView() {} // no subclasses but our own
508
509 /**
510 * Returns an immutable copy of the current contents of this set view.
511 * Does not support null elements.
512 *
513 * <p><b>Warning:</b> this may have unexpected results if a backing set of
514 * this view uses a nonstandard notion of equivalence, for example if it is
515 * a {@link TreeSet} using a comparator that is inconsistent with {@link
516 * Object#equals(Object)}.
517 */
518 public ImmutableSet<E> immutableCopy() {
519 return ImmutableSet.copyOf(this);
520 }
521
522 /**
523 * Copies the current contents of this set view into an existing set. This
524 * method has equivalent behavior to {@code set.addAll(this)}, assuming that
525 * all the sets involved are based on the same notion of equivalence.
526 *
527 * @return a reference to {@code set}, for convenience
528 */
529 // Note: S should logically extend Set<? super E> but can't due to either
530 // some javac bug or some weirdness in the spec, not sure which.
531 public <S extends Set<E>> S copyInto(S set) {
532 set.addAll(this);
533 return set;
534 }
535 }
536
537 /**
538 * Returns an unmodifiable <b>view</b> of the union of two sets. The returned
539 * set contains all elements that are contained in either backing set.
540 * Iterating over the returned set iterates first over all the elements of
541 * {@code set1}, then over each element of {@code set2}, in order, that is not
542 * contained in {@code set1}.
543 *
544 * <p>Results are undefined if {@code set1} and {@code set2} are sets based on
545 * different equivalence relations (as {@link HashSet}, {@link TreeSet}, and
546 * the {@link Map#keySet} of an {@link IdentityHashMap} all are).
547 *
548 * <p><b>Note:</b> The returned view performs better when {@code set1} is the
549 * smaller of the two sets. If you have reason to believe one of your sets
550 * will generally be smaller than the other, pass it first.
551 */
552 public static <E> SetView<E> union(
553 final Set<? extends E> set1, final Set<? extends E> set2) {
554 checkNotNull(set1, "set1");
555 checkNotNull(set2, "set2");
556
557 // TODO: once we have OrderedIterators, check if these are compatible
558 // sorted sets and use that instead if so
559
560 final Set<? extends E> set2minus1 = difference(set2, set1);
561
562 return new SetView<E>() {
563 @Override public int size() {
564 return set1.size() + set2minus1.size();
565 }
566 @Override public boolean isEmpty() {
567 return set1.isEmpty() && set2.isEmpty();
568 }
569 @Override public Iterator<E> iterator() {
570 return Iterators.unmodifiableIterator(
571 Iterators.concat(set1.iterator(), set2minus1.iterator()));
572 }
573 @Override public boolean contains(Object object) {
574 return set1.contains(object) || set2.contains(object);
575 }
576 @Override public <S extends Set<E>> S copyInto(S set) {
577 set.addAll(set1);
578 set.addAll(set2);
579 return set;
580 }
581 @Override public ImmutableSet<E> immutableCopy() {
582 return new ImmutableSet.Builder<E>()
583 .addAll(set1).addAll(set2).build();
584 }
585 };
586 }
587
588 /**
589 * Returns an unmodifiable <b>view</b> of the intersection of two sets. The
590 * returned set contains all elements that are contained by both backing sets.
591 * The iteration order of the returned set matches that of {@code set1}.
592 *
593 * <p>Results are undefined if {@code set1} and {@code set2} are sets based
594 * on different equivalence relations (as {@code HashSet}, {@code TreeSet},
595 * and the keySet of an {@code IdentityHashMap} all are).
596 *
597 * <p><b>Note:</b> The returned view performs slightly better when {@code
598 * set1} is the smaller of the two sets. If you have reason to believe one of
599 * your sets will generally be smaller than the other, pass it first.
600 * Unfortunately, since this method sets the generic type of the returned set
601 * based on the type of the first set passed, this could in rare cases force
602 * you to make a cast, for example: <pre> {@code
603 *
604 * Set<Object> aFewBadObjects = ...
605 * Set<String> manyBadStrings = ...
606 *
607 * // impossible for a non-String to be in the intersection
608 * SuppressWarnings("unchecked")
609 * Set<String> badStrings = (Set) Sets.intersection(
610 * aFewBadObjects, manyBadStrings);}</pre>
611 *
612 * This is unfortunate, but should come up only very rarely.
613 */
614 public static <E> SetView<E> intersection(
615 final Set<E> set1, final Set<?> set2) {
616 checkNotNull(set1, "set1");
617 checkNotNull(set2, "set2");
618
619 // TODO: once we have OrderedIterators, check if these are compatible
620 // sorted sets and use that instead if so
621
622 final Predicate<Object> inSet2 = Predicates.in(set2);
623 return new SetView<E>() {
624 @Override public Iterator<E> iterator() {
625 return Iterators.filter(set1.iterator(), inSet2);
626 }
627 @Override public int size() {
628 return Iterators.size(iterator());
629 }
630 @Override public boolean isEmpty() {
631 return !iterator().hasNext();
632 }
633 @Override public boolean contains(Object object) {
634 return set1.contains(object) && set2.contains(object);
635 }
636 @Override public boolean containsAll(Collection<?> collection) {
637 return set1.containsAll(collection)
638 && set2.containsAll(collection);
639 }
640 };
641 }
642
643 /**
644 * Returns an unmodifiable <b>view</b> of the difference of two sets. The
645 * returned set contains all elements that are contained by {@code set1} and
646 * not contained by {@code set2}. {@code set2} may also contain elements not
647 * present in {@code set1}; these are simply ignored. The iteration order of
648 * the returned set matches that of {@code set1}.
649 *
650 * <p>Results are undefined if {@code set1} and {@code set2} are sets based
651 * on different equivalence relations (as {@code HashSet}, {@code TreeSet},
652 * and the keySet of an {@code IdentityHashMap} all are).
653 */
654 public static <E> SetView<E> difference(
655 final Set<E> set1, final Set<?> set2) {
656 checkNotNull(set1, "set1");
657 checkNotNull(set2, "set2");
658
659 // TODO: once we have OrderedIterators, check if these are compatible
660 // sorted sets and use that instead if so
661
662 final Predicate<Object> notInSet2 = Predicates.not(Predicates.in(set2));
663 return new SetView<E>() {
664 @Override public Iterator<E> iterator() {
665 return Iterators.filter(set1.iterator(), notInSet2);
666 }
667 @Override public int size() {
668 return Iterators.size(iterator());
669 }
670 @Override public boolean isEmpty() {
671 return set2.containsAll(set1);
672 }
673 @Override public boolean contains(Object element) {
674 return set1.contains(element) && !set2.contains(element);
675 }
676 };
677 }
678
679 /**
680 * Returns an unmodifiable <b>view</b> of the symmetric difference of two
681 * sets. The returned set contains all elements that are contained in either
682 * {@code set1} or {@code set2} but not in both. The iteration order of the
683 * returned set is undefined.
684 *
685 * <p>Results are undefined if {@code set1} and {@code set2} are sets based
686 * on different equivalence relations (as {@code HashSet}, {@code TreeSet},
687 * and the keySet of an {@code IdentityHashMap} all are).
688 *
689 * @since 3
690 */
691 @Beta
692 public static <E> SetView<E> symmetricDifference(
693 Set<? extends E> set1, Set<? extends E> set2) {
694 checkNotNull(set1, "set1");
695 checkNotNull(set2, "set2");
696
697 // TODO: Replace this with a more efficient implementation
698 return difference(union(set1, set2), intersection(set1, set2));
699 }
700
701 /**
702 * Returns the elements of {@code unfiltered} that satisfy a predicate. The
703 * returned set is a live view of {@code unfiltered}; changes to one affect
704 * the other.
705 *
706 * <p>The resulting set's iterator does not support {@code remove()}, but all
707 * other set methods are supported. The set's {@code add()} and
708 * {@code addAll()} methods throw an {@link IllegalArgumentException} if an
709 * element that doesn't satisfy the predicate is provided. When methods such
710 * as {@code removeAll()} and {@code clear()} are called on the filtered set,
711 * only elements that satisfy the filter will be removed from the underlying
712 * collection.
713 *
714 * <p>The returned set isn't threadsafe or serializable, even if
715 * {@code unfiltered} is.
716 *
717 * <p>Many of the filtered set's methods, such as {@code size()}, iterate
718 * across every element in the underlying set and determine which elements
719 * satisfy the filter. When a live view is <i>not</i> needed, it may be faster
720 * to copy {@code Iterables.filter(unfiltered, predicate)} and use the copy.
721 */
722 public static <E> Set<E> filter(
723 Set<E> unfiltered, Predicate<? super E> predicate) {
724 if (unfiltered instanceof FilteredSet) {
725 // Support clear(), removeAll(), and retainAll() when filtering a filtered
726 // collection.
727 FilteredSet<E> filtered = (FilteredSet<E>) unfiltered;
728 Predicate<E> combinedPredicate
729 = Predicates.<E>and(filtered.predicate, predicate);
730 return new FilteredSet<E>(
731 (Set<E>) filtered.unfiltered, combinedPredicate);
732 }
733
734 return new FilteredSet<E>(
735 checkNotNull(unfiltered), checkNotNull(predicate));
736 }
737
738 private static class FilteredSet<E> extends FilteredCollection<E>
739 implements Set<E> {
740 FilteredSet(Set<E> unfiltered, Predicate<? super E> predicate) {
741 super(unfiltered, predicate);
742 }
743
744 @Override public boolean equals(@Nullable Object object) {
745 return Collections2.setEquals(this, object);
746 }
747
748 @Override public int hashCode() {
749 return hashCodeImpl(this);
750 }
751 }
752
753 /**
754 * Returns every possible list that can be formed by choosing one element
755 * from each of the given sets in order; the "n-ary
756 * <a href="http://en.wikipedia.org/wiki/Cartesian_product">Cartesian
757 * product</a>" of the sets. For example: <pre class="code"> {@code
758 *
759 * Sets.cartesianProduct(ImmutableList.of(
760 * ImmutableSet.of(1, 2),
761 * ImmutableSet.of("A", "B", "C")))}</pre>
762 *
763 * returns a set containing six lists:
764 *
765 * <ul>
766 * <li>{@code ImmutableList.of(1, "A")}
767 * <li>{@code ImmutableList.of(1, "B")}
768 * <li>{@code ImmutableList.of(1, "C")}
769 * <li>{@code ImmutableList.of(2, "A")}
770 * <li>{@code ImmutableList.of(2, "B")}
771 * <li>{@code ImmutableList.of(2, "C")}
772 * </ul>
773 *
774 * The order in which these lists are returned is not guaranteed, however the
775 * position of an element inside a tuple always corresponds to the position of
776 * the set from which it came in the input list. Note that if any input set is
777 * empty, the Cartesian product will also be empty. If no sets at all are
778 * provided (an empty list), the resulting Cartesian product has one element,
779 * an empty list (counter-intuitive, but mathematically consistent).
780 *
781 * <p><i>Performance notes:</i> while the cartesian product of sets of size
782 * {@code m, n, p} is a set of size {@code m x n x p}, its actual memory
783 * consumption is much smaller. When the cartesian set is constructed, the
784 * input sets are merely copied. Only as the resulting set is iterated are the
785 * individual lists created, and these are not retained after iteration.
786 *
787 * @param sets the sets to choose elements from, in the order that
788 * the elements chosen from those sets should appear in the resulting
789 * lists
790 * @param <B> any common base class shared by all axes (often just {@link
791 * Object})
792 * @return the Cartesian product, as an immutable set containing immutable
793 * lists
794 * @throws NullPointerException if {@code sets}, any one of the {@code sets},
795 * or any element of a provided set is null
796 * @since 2
797 */
798 public static <B> Set<List<B>> cartesianProduct(
799 List<? extends Set<? extends B>> sets) {
800 CartesianSet<B> cartesianSet = new CartesianSet<B>(sets);
801 return cartesianSet.isEmpty() ? ImmutableSet.<List<B>>of() : cartesianSet;
802 }
803
804 /**
805 * Returns every possible list that can be formed by choosing one element
806 * from each of the given sets in order; the "n-ary
807 * <a href="http://en.wikipedia.org/wiki/Cartesian_product">Cartesian
808 * product</a>" of the sets. For example: <pre class="code"> {@code
809 *
810 * Sets.cartesianProduct(
811 * ImmutableSet.of(1, 2),
812 * ImmutableSet.of("A", "B", "C"))}</pre>
813 *
814 * returns a set containing six lists:
815 *
816 * <ul>
817 * <li>{@code ImmutableList.of(1, "A")}
818 * <li>{@code ImmutableList.of(1, "B")}
819 * <li>{@code ImmutableList.of(1, "C")}
820 * <li>{@code ImmutableList.of(2, "A")}
821 * <li>{@code ImmutableList.of(2, "B")}
822 * <li>{@code ImmutableList.of(2, "C")}
823 * </ul>
824 *
825 * The order in which these lists are returned is not guaranteed, however the
826 * position of an element inside a tuple always corresponds to the position of
827 * the set from which it came in the input list. Note that if any input set is
828 * empty, the Cartesian product will also be empty. If no sets at all are
829 * provided, the resulting Cartesian product has one element, an empty list
830 * (counter-intuitive, but mathematically consistent).
831 *
832 * <p><i>Performance notes:</i> while the cartesian product of sets of size
833 * {@code m, n, p} is a set of size {@code m x n x p}, its actual memory
834 * consumption is much smaller. When the cartesian set is constructed, the
835 * input sets are merely copied. Only as the resulting set is iterated are the
836 * individual lists created, and these are not retained after iteration.
837 *
838 * @param sets the sets to choose elements from, in the order that
839 * the elements chosen from those sets should appear in the resulting
840 * lists
841 * @param <B> any common base class shared by all axes (often just {@link
842 * Object})
843 * @return the Cartesian product, as an immutable set containing immutable
844 * lists
845 * @throws NullPointerException if {@code sets}, any one of the {@code sets},
846 * or any element of a provided set is null
847 * @since 2
848 */
849 public static <B> Set<List<B>> cartesianProduct(
850 Set<? extends B>... sets) {
851 return cartesianProduct(Arrays.asList(sets));
852 }
853
854 private static class CartesianSet<B> extends AbstractSet<List<B>> {
855 final ImmutableList<Axis> axes;
856 final int size;
857
858 CartesianSet(List<? extends Set<? extends B>> sets) {
859 long dividend = 1;
860 ImmutableList.Builder<Axis> builder = ImmutableList.builder();
861 for (Set<? extends B> set : sets) {
862 Axis axis = new Axis(set, (int) dividend); // check overflow at end
863 builder.add(axis);
864 dividend *= axis.size();
865 }
866 this.axes = builder.build();
867 size = Ints.checkedCast(dividend);
868 }
869
870 @Override public int size() {
871 return size;
872 }
873
874 @Override public UnmodifiableIterator<List<B>> iterator() {
875 return new UnmodifiableIterator<List<B>>() {
876 int index;
877
878 public boolean hasNext() {
879 return index < size;
880 }
881
882 public List<B> next() {
883 if (!hasNext()) {
884 throw new NoSuchElementException();
885 }
886
887 Object[] tuple = new Object[axes.size()];
888 for (int i = 0 ; i < tuple.length; i++) {
889 tuple[i] = axes.get(i).getForIndex(index);
890 }
891 index++;
892
893 @SuppressWarnings("unchecked") // only B's are put in here
894 List<B> result = (ImmutableList<B>) ImmutableList.copyOf(tuple);
895 return result;
896 }
897 };
898 }
899
900 @Override public boolean contains(Object element) {
901 if (!(element instanceof List<?>)) {
902 return false;
903 }
904 List<?> tuple = (List<?>) element;
905 int dimensions = axes.size();
906 if (tuple.size() != dimensions) {
907 return false;
908 }
909 for (int i = 0; i < dimensions; i++) {
910 if (!axes.get(i).contains(tuple.get(i))) {
911 return false;
912 }
913 }
914 return true;
915 }
916
917 @Override public boolean equals(@Nullable Object object) {
918 // Warning: this is broken if size() == 0, so it is critical that we
919 // substitute an empty ImmutableSet to the user in place of this
920 if (object instanceof CartesianSet) {
921 CartesianSet<?> that = (CartesianSet<?>) object;
922 return this.axes.equals(that.axes);
923 }
924 return super.equals(object);
925 }
926
927 @Override public int hashCode() {
928 // Warning: this is broken if size() == 0, so it is critical that we
929 // substitute an empty ImmutableSet to the user in place of this
930
931 // It's a weird formula, but tests prove it works.
932 int adjust = size - 1;
933 for (int i = 0; i < axes.size(); i++) {
934 adjust *= 31;
935 }
936 return axes.hashCode() + adjust;
937 }
938
939 private class Axis {
940 final ImmutableSet<? extends B> choices;
941 final ImmutableList<? extends B> choicesList;
942 final int dividend;
943
944 Axis(Set<? extends B> set, int dividend) {
945 choices = ImmutableSet.copyOf(set);
946 choicesList = choices.asList();
947 this.dividend = dividend;
948 }
949
950 int size() {
951 return choices.size();
952 }
953
954 B getForIndex(int index) {
955 return choicesList.get(index / dividend % size());
956 }
957
958 boolean contains(Object target) {
959 return choices.contains(target);
960 }
961
962 @SuppressWarnings("unchecked") // javac rejects "CartesianSet<?>.Axis"
963 @Override public boolean equals(Object obj) {
964 if (obj instanceof CartesianSet.Axis) {
965 CartesianSet.Axis that = (CartesianSet.Axis) obj;
966 return this.choices.equals(that.choices);
967 // dividends must be equal or we wouldn't have gotten this far
968 }
969 return false;
970 }
971
972 @Override public int hashCode() {
973 // Because Axis instances are not exposed, we can
974 // opportunistically choose whatever bizarre formula happens
975 // to make CartesianSet.hashCode() as simple as possible.
976 return size / choices.size() * choices.hashCode();
977 }
978 }
979 }
980
981 /**
982 * Returns the set of all possible subsets of {@code set}. For example,
983 * {@code powerSet(ImmutableSet.of(1, 2))} returns the set {@code {{},
984 * {1}, {2}, {1, 2}}}.
985 *
986 * <p>Elements appear in these subsets in the same iteration order as they
987 * appeared in the input set. The order in which these subsets appear in the
988 * outer set is undefined. Note that the power set of the empty set is not the
989 * empty set, but a one-element set containing the empty set.
990 *
991 * <p>The returned set and its constituent sets use {@code equals} to decide
992 * whether two elements are identical, even if the input set uses a different
993 * concept of equivalence.
994 *
995 * <p><i>Performance notes:</i> while the power set of a set with size {@code
996 * n} is of size {@code 2^n}, its memory usage is only {@code O(n)}. When the
997 * power set is constructed, the input set is merely copied. Only as the
998 * power set is iterated are the individual subsets created, and these subsets
999 * themselves occupy only a few bytes of memory regardless of their size.
1000 *
1001 * @param set the set of elements to construct a power set from
1002 * @return the power set, as an immutable set of immutable sets
1003 * @throws IllegalArgumentException if {@code set} has more than 30 unique
1004 * elements (causing the power set size to exceed the {@code int} range)
1005 * @throws NullPointerException if {@code set} or any of its elements is
1006 * null
1007 * @see <a href="http://en.wikipedia.org/wiki/Power_set">Power set article at
1008 * Wikipedia</a>
1009 * @since 4
1010 */
1011 @GwtCompatible(serializable = false)
1012 public static <E> Set<Set<E>> powerSet(Set<E> set) {
1013 ImmutableSet<E> input = ImmutableSet.copyOf(set);
1014 checkArgument(input.size() <= 30,
1015 "Too many elements to create power set: %s > 30", input.size());
1016 return new PowerSet<E>(input);
1017 }
1018
1019 private static final class PowerSet<E> extends AbstractSet<Set<E>> {
1020 final ImmutableSet<E> inputSet;
1021 final ImmutableList<E> inputList;
1022 final int powerSetSize;
1023
1024 PowerSet(ImmutableSet<E> input) {
1025 this.inputSet = input;
1026 this.inputList = input.asList();
1027 this.powerSetSize = 1 << input.size();
1028 }
1029
1030 @Override public int size() {
1031 return powerSetSize;
1032 }
1033
1034 @Override public boolean isEmpty() {
1035 return false;
1036 }
1037
1038 @Override public Iterator<Set<E>> iterator() {
1039 return new AbstractIndexedIterator<Set<E>>(powerSetSize) {
1040 @Override protected Set<E> get(final int setBits) {
1041 return new AbstractSet<E>() {
1042 @Override public int size() {
1043 return Integer.bitCount(setBits);
1044 }
1045 @Override public Iterator<E> iterator() {
1046 return new BitFilteredSetIterator<E>(inputList, setBits);
1047 }
1048 };
1049 }
1050 };
1051 }
1052
1053 private static final class BitFilteredSetIterator<E>
1054 extends UnmodifiableIterator<E> {
1055 final ImmutableList<E> input;
1056 int remainingSetBits;
1057
1058 BitFilteredSetIterator(ImmutableList<E> input, int allSetBits) {
1059 this.input = input;
1060 this.remainingSetBits = allSetBits;
1061 }
1062
1063 @Override public boolean hasNext() {
1064 return remainingSetBits != 0;
1065 }
1066
1067 @Override public E next() {
1068 int index = Integer.numberOfTrailingZeros(remainingSetBits);
1069 if (index == 32) {
1070 throw new NoSuchElementException();
1071 }
1072
1073 int currentElementMask = 1 << index;
1074 remainingSetBits &= ~currentElementMask;
1075 return input.get(index);
1076 }
1077 }
1078
1079 @Override public boolean contains(@Nullable Object obj) {
1080 if (obj instanceof Set) {
1081 Set<?> set = (Set<?>) obj;
1082 return inputSet.containsAll(set);
1083 }
1084 return false;
1085 }
1086
1087 @Override public boolean equals(@Nullable Object obj) {
1088 if (obj instanceof PowerSet) {
1089 PowerSet<?> that = (PowerSet<?>) obj;
1090 return inputSet.equals(that.inputSet);
1091 }
1092 return super.equals(obj);
1093 }
1094
1095 @Override public int hashCode() {
1096 /*
1097 * The sum of the sums of the hash codes in each subset is just the sum of
1098 * each input element's hash code times the number of sets that element
1099 * appears in. Each element appears in exactly half of the 2^n sets, so:
1100 */
1101 return inputSet.hashCode() << (inputSet.size() - 1);
1102 }
1103
1104 @Override public String toString() {
1105 return "powerSet(" + inputSet + ")";
1106 }
1107 }
1108
1109 /**
1110 * Calculates and returns the hash code of {@code s}.
1111 */
1112 static int hashCodeImpl(Set<?> s) {
1113 int hashCode = 0;
1114 for (Object o : s) {
1115 hashCode += o != null ? o.hashCode() : 0;
1116 }
1117 return hashCode;
1118 }
1119 }