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