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
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.GwtCompatible;
023 import com.google.common.annotations.GwtIncompatible;
024 import com.google.common.base.Function;
025 import com.google.common.base.Objects;
026 import com.google.common.base.Preconditions;
027 import com.google.common.base.Predicate;
028 import com.google.common.base.Predicates;
029 import com.google.common.collect.Collections2.FilteredCollection;
030 import com.google.common.primitives.Ints;
031
032 import java.io.IOException;
033 import java.io.ObjectInputStream;
034 import java.io.Serializable;
035 import java.util.AbstractSet;
036 import java.util.Arrays;
037 import java.util.Collection;
038 import java.util.Collections;
039 import java.util.Comparator;
040 import java.util.EnumSet;
041 import java.util.HashMap;
042 import java.util.HashSet;
043 import java.util.IdentityHashMap;
044 import java.util.Iterator;
045 import java.util.LinkedHashSet;
046 import java.util.List;
047 import java.util.Map;
048 import java.util.NoSuchElementException;
049 import java.util.Set;
050 import java.util.SortedSet;
051 import java.util.TreeMap;
052 import java.util.TreeSet;
053
054 import javax.annotation.Nullable;
055
056 /**
057 * Static utility methods pertaining to {@link Set} instances. Also see this
058 * class's counterparts {@link Lists} and {@link Maps}.
059 *
060 * @author Kevin Bourrillion
061 * @author Jared Levy
062 * @author Chris Povirk
063 * @since 2 (imported from Google Collections Library)
064 */
065 @GwtCompatible(emulated = true)
066 public final class Sets {
067 private Sets() {}
068
069 /**
070 * Returns an immutable set instance containing the given enum elements.
071 * Internally, the returned set will be backed by an {@link EnumSet}.
072 *
073 * <p>The iteration order of the returned set follows the enum's iteration
074 * order, not the order in which the elements are provided to the method.
075 *
076 * @param anElement one of the elements the set should contain
077 * @param otherElements the rest of the elements the set should contain
078 * @return an immutable set containing those elements, minus duplicates
079 */
080 // http://code.google.com/p/google-web-toolkit/issues/detail?id=3028
081 @GwtCompatible(serializable = true)
082 public static <E extends Enum<E>> ImmutableSet<E> immutableEnumSet(
083 E anElement, E... otherElements) {
084 return new ImmutableEnumSet<E>(EnumSet.of(anElement, otherElements));
085 }
086
087 /**
088 * Returns an immutable set instance containing the given enum elements.
089 * Internally, the returned set will be backed by an {@link EnumSet}.
090 *
091 * <p>The iteration order of the returned set follows the enum's iteration
092 * order, not the order in which the elements appear in the given collection.
093 *
094 * @param elements the elements, all of the same {@code enum} type, that the
095 * set should contain
096 * @return an immutable set containing those elements, minus duplicates
097 */
098 // http://code.google.com/p/google-web-toolkit/issues/detail?id=3028
099 @GwtCompatible(serializable = true)
100 public static <E extends Enum<E>> ImmutableSet<E> immutableEnumSet(
101 Iterable<E> elements) {
102 Iterator<E> iterator = elements.iterator();
103 if (!iterator.hasNext()) {
104 return ImmutableSet.of();
105 }
106 if (elements instanceof EnumSet) {
107 EnumSet<E> enumSetClone = EnumSet.copyOf((EnumSet<E>) elements);
108 return new ImmutableEnumSet<E>(enumSetClone);
109 }
110 E first = iterator.next();
111 EnumSet<E> set = EnumSet.of(first);
112 while (iterator.hasNext()) {
113 set.add(iterator.next());
114 }
115 return new ImmutableEnumSet<E>(set);
116 }
117
118 /**
119 * Returns a new {@code EnumSet} instance containing the given elements.
120 * Unlike {@link EnumSet#copyOf(Collection)}, this method does not produce an
121 * exception on an empty collection, and it may be called on any iterable, not
122 * just a {@code Collection}.
123 */
124 public static <E extends Enum<E>> EnumSet<E> newEnumSet(Iterable<E> iterable,
125 Class<E> elementType) {
126 /*
127 * TODO(cpovirk): noneOf() and addAll() will both throw
128 * NullPointerExceptions when appropriate. However, NullPointerTester will
129 * fail on this method because it passes in Class.class instead of an enum
130 * type. This means that, when iterable is null but elementType is not,
131 * noneOf() will throw a ClassCastException before addAll() has a chance to
132 * throw a NullPointerException. NullPointerTester considers this a failure.
133 * Ideally the test would be fixed, but it would require a special case for
134 * Class<E> where E extends Enum. Until that happens (if ever), leave
135 * checkNotNull() here. For now, contemplate the irony that checking
136 * elementType, the problem argument, is harmful, while checking iterable,
137 * the innocent bystander, is effective.
138 */
139 checkNotNull(iterable);
140 EnumSet<E> set = EnumSet.noneOf(elementType);
141 Iterables.addAll(set, iterable);
142 return set;
143 }
144
145 // HashSet
146
147 /**
148 * Creates a <i>mutable</i>, empty {@code HashSet} instance.
149 *
150 * <p><b>Note:</b> if mutability is not required, use {@link
151 * ImmutableSet#of()} instead.
152 *
153 * <p><b>Note:</b> if {@code E} is an {@link Enum} type, use {@link
154 * EnumSet#noneOf} instead.
155 *
156 * @return a new, empty {@code HashSet}
157 */
158 public static <E> HashSet<E> newHashSet() {
159 return new HashSet<E>();
160 }
161
162 /**
163 * Creates a <i>mutable</i> {@code HashSet} instance containing the given
164 * elements in unspecified order.
165 *
166 * <p><b>Note:</b> if mutability is not required and the elements are
167 * non-null, use an overload of {@link ImmutableSet#of()} (for varargs) or
168 * {@link ImmutableSet#copyOf(Object[])} (for an array) instead.
169 *
170 * <p><b>Note:</b> if {@code E} is an {@link Enum} type, use {@link
171 * EnumSet#of(Enum, Enum[])} instead.
172 *
173 * @param elements the elements that the set should contain
174 * @return a new {@code HashSet} containing those elements (minus duplicates)
175 */
176 public static <E> HashSet<E> newHashSet(E... elements) {
177 int capacity = Maps.capacity(elements.length);
178 HashSet<E> set = new HashSet<E>(capacity);
179 Collections.addAll(set, elements);
180 return set;
181 }
182
183 /**
184 * Creates an empty {@code HashSet} instance with enough capacity to hold the
185 * specified number of elements without rehashing.
186 *
187 * @param expectedSize the expected size
188 * @return a new, empty {@code HashSet} with enough capacity to hold {@code
189 * expectedSize} elements without rehashing
190 * @throws IllegalArgumentException if {@code expectedSize} is negative
191 */
192 public static <E> HashSet<E> newHashSetWithExpectedSize(int expectedSize) {
193 return new HashSet<E>(Maps.capacity(expectedSize));
194 }
195
196 /**
197 * Creates a <i>mutable</i> {@code HashSet} instance containing the given
198 * elements in unspecified order.
199 *
200 * <p><b>Note:</b> if mutability is not required and the elements are
201 * non-null, use {@link ImmutableSet#copyOf(Iterable)} instead.
202 *
203 * <p><b>Note:</b> if {@code E} is an {@link Enum} type, use
204 * {@link #newEnumSet(Iterable, Class)} instead.
205 *
206 * @param elements the elements that the set should contain
207 * @return a new {@code HashSet} containing those elements (minus duplicates)
208 */
209 public static <E> HashSet<E> newHashSet(Iterable<? extends E> elements) {
210 return (elements instanceof Collection)
211 ? new HashSet<E>(Collections2.cast(elements))
212 : newHashSet(elements.iterator());
213 }
214
215 /**
216 * Creates a <i>mutable</i> {@code HashSet} instance containing the given
217 * elements in unspecified order.
218 *
219 * <p><b>Note:</b> if mutability is not required and the elements are
220 * non-null, use {@link ImmutableSet#copyOf(Iterable)} instead.
221 *
222 * <p><b>Note:</b> if {@code E} is an {@link Enum} type, you should create an
223 * {@link EnumSet} instead.
224 *
225 * @param elements the elements that the set should contain
226 * @return a new {@code HashSet} containing those elements (minus duplicates)
227 */
228 public static <E> HashSet<E> newHashSet(Iterator<? extends E> elements) {
229 HashSet<E> set = newHashSet();
230 while (elements.hasNext()) {
231 set.add(elements.next());
232 }
233 return set;
234 }
235
236 // LinkedHashSet
237
238 /**
239 * Creates a <i>mutable</i>, empty {@code LinkedHashSet} instance.
240 *
241 * <p><b>Note:</b> if mutability is not required, use {@link
242 * ImmutableSet#of()} instead.
243 *
244 * @return a new, empty {@code LinkedHashSet}
245 */
246 public static <E> LinkedHashSet<E> newLinkedHashSet() {
247 return new LinkedHashSet<E>();
248 }
249
250 /**
251 * Creates a <i>mutable</i> {@code LinkedHashSet} instance containing the
252 * given elements in order.
253 *
254 * <p><b>Note:</b> if mutability is not required and the elements are
255 * non-null, use {@link ImmutableSet#copyOf(Iterable)} instead.
256 *
257 * @param elements the elements that the set should contain, in order
258 * @return a new {@code LinkedHashSet} containing those elements (minus
259 * duplicates)
260 */
261 public static <E> LinkedHashSet<E> newLinkedHashSet(
262 Iterable<? extends E> elements) {
263 if (elements instanceof Collection) {
264 return new LinkedHashSet<E>(Collections2.cast(elements));
265 }
266 LinkedHashSet<E> set = newLinkedHashSet();
267 for (E element : elements) {
268 set.add(element);
269 }
270 return set;
271 }
272
273 // TreeSet
274
275 /**
276 * Creates a <i>mutable</i>, empty {@code TreeSet} instance sorted by the
277 * natural sort ordering of its elements.
278 *
279 * <p><b>Note:</b> if mutability is not required, use {@link
280 * ImmutableSortedSet#of()} instead.
281 *
282 * @return a new, empty {@code TreeSet}
283 */
284 @SuppressWarnings("unchecked") // allow ungenerified Comparable types
285 public static <E extends Comparable> TreeSet<E> newTreeSet() {
286 return new TreeSet<E>();
287 }
288
289 /**
290 * Creates a <i>mutable</i> {@code TreeSet} instance containing the given
291 * elements sorted by their natural ordering.
292 *
293 * <p><b>Note:</b> if mutability is not required, use {@link
294 * ImmutableSortedSet#copyOf(Iterable)} instead.
295 *
296 * <p><b>Note:</b> If {@code elements} is a {@code SortedSet} with an explicit
297 * comparator, this method has different behavior than
298 * {@link TreeSet#TreeSet(SortedSet)}, which returns a {@code TreeSet} with
299 * that comparator.
300 *
301 * @param elements the elements that the set should contain
302 * @return a new {@code TreeSet} containing those elements (minus duplicates)
303 */
304 @SuppressWarnings("unchecked") // allow ungenerified Comparable types
305 public static <E extends Comparable> TreeSet<E> newTreeSet(
306 Iterable<? extends E> elements) {
307 TreeSet<E> set = newTreeSet();
308 for (E element : elements) {
309 set.add(element);
310 }
311 return set;
312 }
313
314 /**
315 * Creates a <i>mutable</i>, empty {@code TreeSet} instance with the given
316 * comparator.
317 *
318 * <p><b>Note:</b> if mutability is not required, use {@code
319 * ImmutableSortedSet.orderedBy(comparator).build()} instead.
320 *
321 * @param comparator the comparator to use to sort the set
322 * @return a new, empty {@code TreeSet}
323 * @throws NullPointerException if {@code comparator} is null
324 */
325 public static <E> TreeSet<E> newTreeSet(Comparator<? super E> comparator) {
326 return new TreeSet<E>(checkNotNull(comparator));
327 }
328
329 /**
330 * Creates an empty {@code Set} that uses identity to determine equality. It
331 * compares object references, instead of calling {@code equals}, to
332 * determine whether a provided object matches an element in the set. For
333 * example, {@code contains} returns {@code false} when passed an object that
334 * equals a set member, but isn't the same instance. This behavior is similar
335 * to the way {@link IdentityHashMap} handles key lookups.
336 *
337 * @since 8
338 */
339 public static <E> Set<E> newIdentityHashSet() {
340 return Sets.newSetFromMap(Maps.<E, Boolean>newIdentityHashMap());
341 }
342
343 /**
344 * Creates an {@code EnumSet} consisting of all enum values that are not in
345 * the specified collection. If the collection is an {@link EnumSet}, this
346 * method has the same behavior as {@link EnumSet#complementOf}. Otherwise,
347 * the specified collection must contain at least one element, in order to
348 * determine the element type. If the collection could be empty, use
349 * {@link #complementOf(Collection, Class)} instead of this method.
350 *
351 * @param collection the collection whose complement should be stored in the
352 * enum set
353 * @return a new, modifiable {@code EnumSet} containing all values of the enum
354 * that aren't present in the given collection
355 * @throws IllegalArgumentException if {@code collection} is not an
356 * {@code EnumSet} instance and contains no elements
357 */
358 public static <E extends Enum<E>> EnumSet<E> complementOf(
359 Collection<E> collection) {
360 if (collection instanceof EnumSet) {
361 return EnumSet.complementOf((EnumSet<E>) collection);
362 }
363 checkArgument(!collection.isEmpty(),
364 "collection is empty; use the other version of this method");
365 Class<E> type = collection.iterator().next().getDeclaringClass();
366 return makeComplementByHand(collection, type);
367 }
368
369 /**
370 * Creates an {@code EnumSet} consisting of all enum values that are not in
371 * the specified collection. This is equivalent to
372 * {@link EnumSet#complementOf}, but can act on any input collection, as long
373 * as the elements are of enum type.
374 *
375 * @param collection the collection whose complement should be stored in the
376 * {@code EnumSet}
377 * @param type the type of the elements in the set
378 * @return a new, modifiable {@code EnumSet} initially containing all the
379 * values of the enum not present in the given collection
380 */
381 public static <E extends Enum<E>> EnumSet<E> complementOf(
382 Collection<E> collection, Class<E> type) {
383 checkNotNull(collection);
384 return (collection instanceof EnumSet)
385 ? EnumSet.complementOf((EnumSet<E>) collection)
386 : makeComplementByHand(collection, type);
387 }
388
389 private static <E extends Enum<E>> EnumSet<E> makeComplementByHand(
390 Collection<E> collection, Class<E> type) {
391 EnumSet<E> result = EnumSet.allOf(type);
392 result.removeAll(collection);
393 return result;
394 }
395
396 /*
397 * Regarding newSetForMap() and SetFromMap:
398 *
399 * Written by Doug Lea with assistance from members of JCP JSR-166
400 * Expert Group and released to the public domain, as explained at
401 * http://creativecommons.org/licenses/publicdomain
402 */
403
404 /**
405 * Returns a set backed by the specified map. The resulting set displays
406 * the same ordering, concurrency, and performance characteristics as the
407 * backing map. In essence, this factory method provides a {@link Set}
408 * implementation corresponding to any {@link Map} implementation. There is no
409 * need to use this method on a {@link Map} implementation that already has a
410 * corresponding {@link Set} implementation (such as {@link HashMap} or
411 * {@link TreeMap}).
412 *
413 * <p>Each method invocation on the set returned by this method results in
414 * exactly one method invocation on the backing map or its <tt>keySet</tt>
415 * view, with one exception. The <tt>addAll</tt> method is implemented as a
416 * sequence of <tt>put</tt> invocations on the backing map.
417 *
418 * <p>The specified map must be empty at the time this method is invoked,
419 * and should not be accessed directly after this method returns. These
420 * conditions are ensured if the map is created empty, passed directly
421 * to this method, and no reference to the map is retained, as illustrated
422 * in the following code fragment: <pre> {@code
423 *
424 * Set<Object> identityHashSet = Sets.newSetFromMap(
425 * new IdentityHashMap<Object, Boolean>());}</pre>
426 *
427 * This method has the same behavior as the JDK 6 method
428 * {@code Collections.newSetFromMap()}. The returned set is serializable if
429 * the backing map is.
430 *
431 * @param map the backing map
432 * @return the set backed by the map
433 * @throws IllegalArgumentException if <tt>map</tt> is not empty
434 */
435 public static <E> Set<E> newSetFromMap(Map<E, Boolean> map) {
436 return new SetFromMap<E>(map);
437 }
438
439 private static class SetFromMap<E> extends AbstractSet<E>
440 implements Set<E>, Serializable {
441 private final Map<E, Boolean> m; // The backing map
442 private transient Set<E> s; // Its keySet
443
444 SetFromMap(Map<E, Boolean> map) {
445 checkArgument(map.isEmpty(), "Map is non-empty");
446 m = map;
447 s = map.keySet();
448 }
449
450 @Override public void clear() {
451 m.clear();
452 }
453 @Override public int size() {
454 return m.size();
455 }
456 @Override public boolean isEmpty() {
457 return m.isEmpty();
458 }
459 @Override public boolean contains(Object o) {
460 return m.containsKey(o);
461 }
462 @Override public boolean remove(Object o) {
463 return m.remove(o) != null;
464 }
465 @Override public boolean add(E e) {
466 return m.put(e, Boolean.TRUE) == null;
467 }
468 @Override public Iterator<E> iterator() {
469 return s.iterator();
470 }
471 @Override public Object[] toArray() {
472 return s.toArray();
473 }
474 @Override public <T> T[] toArray(T[] a) {
475 return s.toArray(a);
476 }
477 @Override public String toString() {
478 return s.toString();
479 }
480 @Override public int hashCode() {
481 return s.hashCode();
482 }
483 @Override public boolean equals(@Nullable Object object) {
484 return this == object || this.s.equals(object);
485 }
486 @Override public boolean containsAll(Collection<?> c) {
487 return s.containsAll(c);
488 }
489 @Override public boolean removeAll(Collection<?> c) {
490 return s.removeAll(c);
491 }
492 @Override public boolean retainAll(Collection<?> c) {
493 return s.retainAll(c);
494 }
495
496 // addAll is the only inherited implementation
497 @GwtIncompatible("not needed in emulated source")
498 private static final long serialVersionUID = 0;
499
500 @GwtIncompatible("java.io.ObjectInputStream")
501 private void readObject(ObjectInputStream stream)
502 throws IOException, ClassNotFoundException {
503 stream.defaultReadObject();
504 s = m.keySet();
505 }
506 }
507
508 /**
509 * An unmodifiable view of a set which may be backed by other sets; this view
510 * will change as the backing sets do. Contains methods to copy the data into
511 * a new set which will then remain stable. There is usually no reason to
512 * retain a reference of type {@code SetView}; typically, you either use it
513 * as a plain {@link Set}, or immediately invoke {@link #immutableCopy} or
514 * {@link #copyInto} and forget the {@code SetView} itself.
515 *
516 * @since 2 (imported from Google Collections Library)
517 */
518 public abstract static class SetView<E> extends AbstractSet<E> {
519 private SetView() {} // no subclasses but our own
520
521 /**
522 * Returns an immutable copy of the current contents of this set view.
523 * Does not support null elements.
524 *
525 * <p><b>Warning:</b> this may have unexpected results if a backing set of
526 * this view uses a nonstandard notion of equivalence, for example if it is
527 * a {@link TreeSet} using a comparator that is inconsistent with {@link
528 * Object#equals(Object)}.
529 */
530 public ImmutableSet<E> immutableCopy() {
531 return ImmutableSet.copyOf(this);
532 }
533
534 /**
535 * Copies the current contents of this set view into an existing set. This
536 * method has equivalent behavior to {@code set.addAll(this)}, assuming that
537 * all the sets involved are based on the same notion of equivalence.
538 *
539 * @return a reference to {@code set}, for convenience
540 */
541 // Note: S should logically extend Set<? super E> but can't due to either
542 // some javac bug or some weirdness in the spec, not sure which.
543 public <S extends Set<E>> S copyInto(S set) {
544 set.addAll(this);
545 return set;
546 }
547 }
548
549 /**
550 * Returns an unmodifiable <b>view</b> of the union of two sets. The returned
551 * set contains all elements that are contained in either backing set.
552 * Iterating over the returned set iterates first over all the elements of
553 * {@code set1}, then over each element of {@code set2}, in order, that is not
554 * contained in {@code set1}.
555 *
556 * <p>Results are undefined if {@code set1} and {@code set2} are sets based on
557 * different equivalence relations (as {@link HashSet}, {@link TreeSet}, and
558 * the {@link Map#keySet} of an {@link IdentityHashMap} all are).
559 *
560 * <p><b>Note:</b> The returned view performs better when {@code set1} is the
561 * smaller of the two sets. If you have reason to believe one of your sets
562 * will generally be smaller than the other, pass it first.
563 */
564 public static <E> SetView<E> union(
565 final Set<? extends E> set1, final Set<? extends E> set2) {
566 checkNotNull(set1, "set1");
567 checkNotNull(set2, "set2");
568
569 final Set<? extends E> set2minus1 = difference(set2, set1);
570
571 return new SetView<E>() {
572 @Override public int size() {
573 return set1.size() + set2minus1.size();
574 }
575 @Override public boolean isEmpty() {
576 return set1.isEmpty() && set2.isEmpty();
577 }
578 @Override public Iterator<E> iterator() {
579 return Iterators.unmodifiableIterator(
580 Iterators.concat(set1.iterator(), set2minus1.iterator()));
581 }
582 @Override public boolean contains(Object object) {
583 return set1.contains(object) || set2.contains(object);
584 }
585 @Override public <S extends Set<E>> S copyInto(S set) {
586 set.addAll(set1);
587 set.addAll(set2);
588 return set;
589 }
590 @Override public ImmutableSet<E> immutableCopy() {
591 return new ImmutableSet.Builder<E>()
592 .addAll(set1).addAll(set2).build();
593 }
594 };
595 }
596
597 /**
598 * Returns an unmodifiable <b>view</b> of the intersection of two sets. The
599 * returned set contains all elements that are contained by both backing sets.
600 * The iteration order of the returned set matches that of {@code set1}.
601 *
602 * <p>Results are undefined if {@code set1} and {@code set2} are sets based
603 * on different equivalence relations (as {@code HashSet}, {@code TreeSet},
604 * and the keySet of an {@code IdentityHashMap} all are).
605 *
606 * <p><b>Note:</b> The returned view performs slightly better when {@code
607 * set1} is the smaller of the two sets. If you have reason to believe one of
608 * your sets will generally be smaller than the other, pass it first.
609 * Unfortunately, since this method sets the generic type of the returned set
610 * based on the type of the first set passed, this could in rare cases force
611 * you to make a cast, for example: <pre> {@code
612 *
613 * Set<Object> aFewBadObjects = ...
614 * Set<String> manyBadStrings = ...
615 *
616 * // impossible for a non-String to be in the intersection
617 * SuppressWarnings("unchecked")
618 * Set<String> badStrings = (Set) Sets.intersection(
619 * aFewBadObjects, manyBadStrings);}</pre>
620 *
621 * This is unfortunate, but should come up only very rarely.
622 */
623 public static <E> SetView<E> intersection(
624 final Set<E> set1, final Set<?> set2) {
625 checkNotNull(set1, "set1");
626 checkNotNull(set2, "set2");
627
628 final Predicate<Object> inSet2 = Predicates.in(set2);
629 return new SetView<E>() {
630 @Override public Iterator<E> iterator() {
631 return Iterators.filter(set1.iterator(), inSet2);
632 }
633 @Override public int size() {
634 return Iterators.size(iterator());
635 }
636 @Override public boolean isEmpty() {
637 return !iterator().hasNext();
638 }
639 @Override public boolean contains(Object object) {
640 return set1.contains(object) && set2.contains(object);
641 }
642 @Override public boolean containsAll(Collection<?> collection) {
643 return set1.containsAll(collection)
644 && set2.containsAll(collection);
645 }
646 };
647 }
648
649 /**
650 * Returns an unmodifiable <b>view</b> of the difference of two sets. The
651 * returned set contains all elements that are contained by {@code set1} and
652 * not contained by {@code set2}. {@code set2} may also contain elements not
653 * present in {@code set1}; these are simply ignored. The iteration order of
654 * the returned set matches that of {@code set1}.
655 *
656 * <p>Results are undefined if {@code set1} and {@code set2} are sets based
657 * on different equivalence relations (as {@code HashSet}, {@code TreeSet},
658 * and the keySet of an {@code IdentityHashMap} all are).
659 */
660 public static <E> SetView<E> difference(
661 final Set<E> set1, final Set<?> set2) {
662 checkNotNull(set1, "set1");
663 checkNotNull(set2, "set2");
664
665 final Predicate<Object> notInSet2 = Predicates.not(Predicates.in(set2));
666 return new SetView<E>() {
667 @Override public Iterator<E> iterator() {
668 return Iterators.filter(set1.iterator(), notInSet2);
669 }
670 @Override public int size() {
671 return Iterators.size(iterator());
672 }
673 @Override public boolean isEmpty() {
674 return set2.containsAll(set1);
675 }
676 @Override public boolean contains(Object element) {
677 return set1.contains(element) && !set2.contains(element);
678 }
679 };
680 }
681
682 /**
683 * Returns an unmodifiable <b>view</b> of the symmetric difference of two
684 * sets. The returned set contains all elements that are contained in either
685 * {@code set1} or {@code set2} but not in both. The iteration order of the
686 * returned set is undefined.
687 *
688 * <p>Results are undefined if {@code set1} and {@code set2} are sets based
689 * on different equivalence relations (as {@code HashSet}, {@code TreeSet},
690 * and the keySet of an {@code IdentityHashMap} all are).
691 *
692 * @since 3
693 */
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 @Override
886 public boolean hasNext() {
887 return index < size;
888 }
889
890 @Override
891 public List<B> next() {
892 if (!hasNext()) {
893 throw new NoSuchElementException();
894 }
895
896 Object[] tuple = new Object[axes.size()];
897 for (int i = 0 ; i < tuple.length; i++) {
898 tuple[i] = axes.get(i).getForIndex(index);
899 }
900 index++;
901
902 @SuppressWarnings("unchecked") // only B's are put in here
903 List<B> result = (ImmutableList<B>) ImmutableList.copyOf(tuple);
904 return result;
905 }
906 };
907 }
908
909 @Override public boolean contains(Object element) {
910 if (!(element instanceof List<?>)) {
911 return false;
912 }
913 List<?> tuple = (List<?>) element;
914 int dimensions = axes.size();
915 if (tuple.size() != dimensions) {
916 return false;
917 }
918 for (int i = 0; i < dimensions; i++) {
919 if (!axes.get(i).contains(tuple.get(i))) {
920 return false;
921 }
922 }
923 return true;
924 }
925
926 @Override public boolean equals(@Nullable Object object) {
927 // Warning: this is broken if size() == 0, so it is critical that we
928 // substitute an empty ImmutableSet to the user in place of this
929 if (object instanceof CartesianSet) {
930 CartesianSet<?> that = (CartesianSet<?>) object;
931 return this.axes.equals(that.axes);
932 }
933 return super.equals(object);
934 }
935
936 @Override public int hashCode() {
937 // Warning: this is broken if size() == 0, so it is critical that we
938 // substitute an empty ImmutableSet to the user in place of this
939
940 // It's a weird formula, but tests prove it works.
941 int adjust = size - 1;
942 for (int i = 0; i < axes.size(); i++) {
943 adjust *= 31;
944 }
945 return axes.hashCode() + adjust;
946 }
947
948 private class Axis {
949 final ImmutableSet<? extends B> choices;
950 final ImmutableList<? extends B> choicesList;
951 final int dividend;
952
953 Axis(Set<? extends B> set, int dividend) {
954 choices = ImmutableSet.copyOf(set);
955 choicesList = choices.asList();
956 this.dividend = dividend;
957 }
958
959 int size() {
960 return choices.size();
961 }
962
963 B getForIndex(int index) {
964 return choicesList.get(index / dividend % size());
965 }
966
967 boolean contains(Object target) {
968 return choices.contains(target);
969 }
970
971 @SuppressWarnings("unchecked") // javac rejects "CartesianSet<?>.Axis"
972 @Override public boolean equals(Object obj) {
973 if (obj instanceof CartesianSet.Axis) {
974 CartesianSet.Axis that = (CartesianSet.Axis) obj;
975 return this.choices.equals(that.choices);
976 // dividends must be equal or we wouldn't have gotten this far
977 }
978 return false;
979 }
980
981 @Override public int hashCode() {
982 // Because Axis instances are not exposed, we can
983 // opportunistically choose whatever bizarre formula happens
984 // to make CartesianSet.hashCode() as simple as possible.
985 return size / choices.size() * choices.hashCode();
986 }
987 }
988 }
989
990 /**
991 * Returns the set of all possible subsets of {@code set}. For example,
992 * {@code powerSet(ImmutableSet.of(1, 2))} returns the set {@code {{},
993 * {1}, {2}, {1, 2}}}.
994 *
995 * <p>Elements appear in these subsets in the same iteration order as they
996 * appeared in the input set. The order in which these subsets appear in the
997 * outer set is undefined. Note that the power set of the empty set is not the
998 * empty set, but a one-element set containing the empty set.
999 *
1000 * <p>The returned set and its constituent sets use {@code equals} to decide
1001 * whether two elements are identical, even if the input set uses a different
1002 * concept of equivalence.
1003 *
1004 * <p><i>Performance notes:</i> while the power set of a set with size {@code
1005 * n} is of size {@code 2^n}, its memory usage is only {@code O(n)}. When the
1006 * power set is constructed, the input set is merely copied. Only as the
1007 * power set is iterated are the individual subsets created, and these subsets
1008 * themselves occupy only a few bytes of memory regardless of their size.
1009 *
1010 * @param set the set of elements to construct a power set from
1011 * @return the power set, as an immutable set of immutable sets
1012 * @throws IllegalArgumentException if {@code set} has more than 30 unique
1013 * elements (causing the power set size to exceed the {@code int} range)
1014 * @throws NullPointerException if {@code set} or any of its elements is
1015 * null
1016 * @see <a href="http://en.wikipedia.org/wiki/Power_set">Power set article at
1017 * Wikipedia</a>
1018 * @since 4
1019 */
1020 @GwtCompatible(serializable = false)
1021 public static <E> Set<Set<E>> powerSet(Set<E> set) {
1022 ImmutableSet<E> input = ImmutableSet.copyOf(set);
1023 checkArgument(input.size() <= 30,
1024 "Too many elements to create power set: %s > 30", input.size());
1025 return new PowerSet<E>(input);
1026 }
1027
1028 private static final class PowerSet<E> extends AbstractSet<Set<E>> {
1029 final ImmutableSet<E> inputSet;
1030 final ImmutableList<E> inputList;
1031 final int powerSetSize;
1032
1033 PowerSet(ImmutableSet<E> input) {
1034 this.inputSet = input;
1035 this.inputList = input.asList();
1036 this.powerSetSize = 1 << input.size();
1037 }
1038
1039 @Override public int size() {
1040 return powerSetSize;
1041 }
1042
1043 @Override public boolean isEmpty() {
1044 return false;
1045 }
1046
1047 @Override public Iterator<Set<E>> iterator() {
1048 return new AbstractIndexedListIterator<Set<E>>(powerSetSize) {
1049 @Override protected Set<E> get(final int setBits) {
1050 return new AbstractSet<E>() {
1051 @Override public int size() {
1052 return Integer.bitCount(setBits);
1053 }
1054 @Override public Iterator<E> iterator() {
1055 return new BitFilteredSetIterator<E>(inputList, setBits);
1056 }
1057 };
1058 }
1059 };
1060 }
1061
1062 private static final class BitFilteredSetIterator<E>
1063 extends UnmodifiableIterator<E> {
1064 final ImmutableList<E> input;
1065 int remainingSetBits;
1066
1067 BitFilteredSetIterator(ImmutableList<E> input, int allSetBits) {
1068 this.input = input;
1069 this.remainingSetBits = allSetBits;
1070 }
1071
1072 @Override public boolean hasNext() {
1073 return remainingSetBits != 0;
1074 }
1075
1076 @Override public E next() {
1077 int index = Integer.numberOfTrailingZeros(remainingSetBits);
1078 if (index == 32) {
1079 throw new NoSuchElementException();
1080 }
1081
1082 int currentElementMask = 1 << index;
1083 remainingSetBits &= ~currentElementMask;
1084 return input.get(index);
1085 }
1086 }
1087
1088 @Override public boolean contains(@Nullable Object obj) {
1089 if (obj instanceof Set) {
1090 Set<?> set = (Set<?>) obj;
1091 return inputSet.containsAll(set);
1092 }
1093 return false;
1094 }
1095
1096 @Override public boolean equals(@Nullable Object obj) {
1097 if (obj instanceof PowerSet) {
1098 PowerSet<?> that = (PowerSet<?>) obj;
1099 return inputSet.equals(that.inputSet);
1100 }
1101 return super.equals(obj);
1102 }
1103
1104 @Override public int hashCode() {
1105 /*
1106 * The sum of the sums of the hash codes in each subset is just the sum of
1107 * each input element's hash code times the number of sets that element
1108 * appears in. Each element appears in exactly half of the 2^n sets, so:
1109 */
1110 return inputSet.hashCode() << (inputSet.size() - 1);
1111 }
1112
1113 @Override public String toString() {
1114 return "powerSet(" + inputSet + ")";
1115 }
1116 }
1117
1118 /**
1119 * An implementation for {@link Set#hashCode()}.
1120 */
1121 static int hashCodeImpl(Set<?> s) {
1122 int hashCode = 0;
1123 for (Object o : s) {
1124 hashCode += o != null ? o.hashCode() : 0;
1125 }
1126 return hashCode;
1127 }
1128
1129 /**
1130 * An implementation for {@link Set#equals(Object)}.
1131 */
1132 static boolean equalsImpl(Set<?> s, @Nullable Object object){
1133 if (s == object) {
1134 return true;
1135 }
1136 if (object instanceof Set) {
1137 Set<?> o = (Set<?>) object;
1138
1139 try {
1140 return s.size() == o.size() && s.containsAll(o);
1141 } catch (NullPointerException ignored) {
1142 return false;
1143 } catch (ClassCastException ignored) {
1144 return false;
1145 }
1146 }
1147 return false;
1148 }
1149
1150 /**
1151 * Creates a view of Set<B> for a Set<A>, given a bijection between A and B.
1152 * (Modelled for now as InvertibleFunction<A, B>, can't be Converter<A, B>
1153 * because that's not in Guava, though both designs are less than optimal).
1154 * Note that the bijection is treated as undefined for values not in the
1155 * given Set<A> - it doesn't have to define a true bijection for those.
1156 *
1157 * <p>Note that the returned Set's contains method is unsafe -
1158 * you *must* pass an instance of B to it, since the bijection
1159 * can only invert B's (not any Object) back to A, so we can
1160 * then delegate the call to the original Set<A>.
1161 */
1162 static <A, B> Set<B> transform(Set<A> set, InvertibleFunction<A, B> bijection) {
1163 return new TransformedSet<A, B>(
1164 Preconditions.checkNotNull(set, "set"),
1165 Preconditions.checkNotNull(bijection, "bijection")
1166 );
1167 }
1168
1169 /**
1170 * Stop-gap measure since there is no bijection related type in Guava.
1171 */
1172 abstract static class InvertibleFunction<A, B> implements Function<A, B> {
1173 abstract A invert(B b);
1174
1175 public InvertibleFunction<B, A> inverse() {
1176 return new InvertibleFunction<B, A>() {
1177 @Override public A apply(B b) {
1178 return InvertibleFunction.this.invert(b);
1179 }
1180
1181 @Override B invert(A a) {
1182 return InvertibleFunction.this.apply(a);
1183 }
1184
1185 // Not required per se, but just for good karma.
1186 @Override public InvertibleFunction<A, B> inverse() {
1187 return InvertibleFunction.this;
1188 }
1189 };
1190 }
1191 }
1192
1193 private static class TransformedSet<A, B> extends AbstractSet<B> {
1194 final Set<A> delegate;
1195 final InvertibleFunction<A, B> bijection;
1196
1197 TransformedSet(Set<A> delegate, InvertibleFunction<A, B> bijection) {
1198 this.delegate = delegate;
1199 this.bijection = bijection;
1200 }
1201
1202 @Override public Iterator<B> iterator() {
1203 return Iterators.transform(delegate.iterator(), bijection);
1204 }
1205
1206 @Override public int size() {
1207 return delegate.size();
1208 }
1209
1210 @SuppressWarnings("unchecked") // unsafe, passed object *must* be B
1211 @Override public boolean contains(Object o) {
1212 B b = (B) o;
1213 A a = bijection.invert(b);
1214 /*
1215 * Mathematically, Converter<A, B> defines a bijection between ALL A's
1216 * on ALL B's. Here we concern ourselves with a subset
1217 * of this relation: we only want the part that is defined by a *subset*
1218 * of all A's (defined by that Set<A> delegate), and the image
1219 * of *that* on B (which is this set). We don't care whether
1220 * the converter is *not* a bijection for A's that are not in Set<A>
1221 * or B's not in this Set<B>.
1222 *
1223 * We only want to return true if and only f the user passes a B instance
1224 * that is contained in precisely in the image of Set<A>.
1225 *
1226 * The first test is whether the inverse image of this B is indeed
1227 * in Set<A>. But we don't know whether that B belongs in this Set<B>
1228 * or not; if not, the converter is free to return
1229 * anything it wants, even an element of Set<A> (and this relationship
1230 * is not part of the Set<A> <--> Set<B> bijection), and we must not
1231 * be confused by that. So we have to do a final check to see if the
1232 * image of that A is really equivalent to the passed B, which proves
1233 * that the given B belongs indeed in the image of Set<A>.
1234 */
1235 return delegate.contains(a) && Objects.equal(bijection.apply(a), o);
1236 }
1237
1238 @Override public boolean add(B b) {
1239 return delegate.add(bijection.invert(b));
1240 }
1241
1242 @SuppressWarnings("unchecked") // unsafe, passed object *must* be B
1243 @Override public boolean remove(Object o) {
1244 return contains(o) ? delegate.remove(bijection.invert((B) o)) : false;
1245 }
1246
1247 @Override public void clear() {
1248 delegate.clear();
1249 }
1250 }
1251 }