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.HashSet;
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.TreeSet;
050
051 import javax.annotation.Nullable;
052
053 /**
054 * Static utility methods pertaining to {@link Set} instances. Also see this
055 * class's counterparts {@link Lists} and {@link Maps}.
056 *
057 * @author Kevin Bourrillion
058 * @author Jared Levy
059 * @author Chris Povirk
060 * @since 2.0 (imported from Google Collections Library)
061 */
062 @GwtCompatible(emulated = true)
063 public final class Sets {
064 private Sets() {}
065
066 /**
067 * Returns an immutable set instance containing the given enum elements.
068 * Internally, the returned set will be backed by an {@link EnumSet}.
069 *
070 * <p>The iteration order of the returned set follows the enum's iteration
071 * order, not the order in which the elements are provided to the method.
072 *
073 * @param anElement one of the elements the set should contain
074 * @param otherElements the rest of the elements the set should contain
075 * @return an immutable set containing those elements, minus duplicates
076 */
077 // http://code.google.com/p/google-web-toolkit/issues/detail?id=3028
078 @GwtCompatible(serializable = true)
079 public static <E extends Enum<E>> ImmutableSet<E> immutableEnumSet(
080 E anElement, E... otherElements) {
081 return new ImmutableEnumSet<E>(EnumSet.of(anElement, otherElements));
082 }
083
084 /**
085 * Returns an immutable set instance containing the given enum elements.
086 * Internally, the returned set will be backed by an {@link EnumSet}.
087 *
088 * <p>The iteration order of the returned set follows the enum's iteration
089 * order, not the order in which the elements appear in the given collection.
090 *
091 * @param elements the elements, all of the same {@code enum} type, that the
092 * set should contain
093 * @return an immutable set containing those elements, minus duplicates
094 */
095 // http://code.google.com/p/google-web-toolkit/issues/detail?id=3028
096 @GwtCompatible(serializable = true)
097 public static <E extends Enum<E>> ImmutableSet<E> immutableEnumSet(
098 Iterable<E> elements) {
099 Iterator<E> iterator = elements.iterator();
100 if (!iterator.hasNext()) {
101 return ImmutableSet.of();
102 }
103 if (elements instanceof EnumSet) {
104 EnumSet<E> enumSetClone = EnumSet.copyOf((EnumSet<E>) elements);
105 return new ImmutableEnumSet<E>(enumSetClone);
106 }
107 E first = iterator.next();
108 EnumSet<E> set = EnumSet.of(first);
109 while (iterator.hasNext()) {
110 set.add(iterator.next());
111 }
112 return new ImmutableEnumSet<E>(set);
113 }
114
115 /**
116 * Returns a new {@code EnumSet} instance containing the given elements.
117 * Unlike {@link EnumSet#copyOf(Collection)}, this method does not produce an
118 * exception on an empty collection, and it may be called on any iterable, not
119 * just a {@code Collection}.
120 */
121 public static <E extends Enum<E>> EnumSet<E> newEnumSet(Iterable<E> iterable,
122 Class<E> elementType) {
123 /*
124 * TODO(cpovirk): noneOf() and addAll() will both throw
125 * NullPointerExceptions when appropriate. However, NullPointerTester will
126 * fail on this method because it passes in Class.class instead of an enum
127 * type. This means that, when iterable is null but elementType is not,
128 * noneOf() will throw a ClassCastException before addAll() has a chance to
129 * throw a NullPointerException. NullPointerTester considers this a failure.
130 * Ideally the test would be fixed, but it would require a special case for
131 * Class<E> where E extends Enum. Until that happens (if ever), leave
132 * checkNotNull() here. For now, contemplate the irony that checking
133 * elementType, the problem argument, is harmful, while checking iterable,
134 * the innocent bystander, is effective.
135 */
136 checkNotNull(iterable);
137 EnumSet<E> set = EnumSet.noneOf(elementType);
138 Iterables.addAll(set, iterable);
139 return set;
140 }
141
142 // HashSet
143
144 /**
145 * Creates a <i>mutable</i>, empty {@code HashSet} instance.
146 *
147 * <p><b>Note:</b> if mutability is not required, use {@link
148 * ImmutableSet#of()} instead.
149 *
150 * <p><b>Note:</b> if {@code E} is an {@link Enum} type, use {@link
151 * EnumSet#noneOf} instead.
152 *
153 * @return a new, empty {@code HashSet}
154 */
155 public static <E> HashSet<E> newHashSet() {
156 return new HashSet<E>();
157 }
158
159 /**
160 * Creates a <i>mutable</i> {@code HashSet} instance containing the given
161 * elements in unspecified order.
162 *
163 * <p><b>Note:</b> if mutability is not required and the elements are
164 * non-null, use an overload of {@link ImmutableSet#of()} (for varargs) or
165 * {@link ImmutableSet#copyOf(Object[])} (for an array) instead.
166 *
167 * <p><b>Note:</b> if {@code E} is an {@link Enum} type, use {@link
168 * EnumSet#of(Enum, Enum[])} instead.
169 *
170 * @param elements the elements that the set should contain
171 * @return a new {@code HashSet} containing those elements (minus duplicates)
172 */
173 public static <E> HashSet<E> newHashSet(E... elements) {
174 HashSet<E> set = newHashSetWithExpectedSize(elements.length);
175 Collections.addAll(set, elements);
176 return set;
177 }
178
179 /**
180 * Creates a {@code HashSet} instance, with a high enough "initial capacity"
181 * that it <i>should</i> hold {@code expectedSize} elements without growth.
182 * This behavior cannot be broadly guaranteed, but it is observed to be true
183 * for OpenJDK 1.6. It also can't be guaranteed that the method isn't
184 * inadvertently <i>oversizing</i> the returned set.
185 *
186 * @param expectedSize the number of elements you expect to add to the
187 * returned set
188 * @return a new, empty {@code HashSet} with enough capacity to hold {@code
189 * expectedSize} elements without resizing
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 public static <E extends Comparable> TreeSet<E> newTreeSet() {
285 return new TreeSet<E>();
286 }
287
288 /**
289 * Creates a <i>mutable</i> {@code TreeSet} instance containing the given
290 * elements sorted by their natural ordering.
291 *
292 * <p><b>Note:</b> if mutability is not required, use {@link
293 * ImmutableSortedSet#copyOf(Iterable)} instead.
294 *
295 * <p><b>Note:</b> If {@code elements} is a {@code SortedSet} with an explicit
296 * comparator, this method has different behavior than
297 * {@link TreeSet#TreeSet(SortedSet)}, which returns a {@code TreeSet} with
298 * that comparator.
299 *
300 * @param elements the elements that the set should contain
301 * @return a new {@code TreeSet} containing those elements (minus duplicates)
302 */
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 {@code IdentityHashMap} handles key lookups.
334 *
335 * @since 8.0
336 */
337 public static <E> Set<E> newIdentityHashSet() {
338 return Sets.newSetFromMap(Maps.<E, Boolean>newIdentityHashMap());
339 }
340
341 /**
342 * Creates an {@code EnumSet} consisting of all enum values that are not in
343 * the specified collection. If the collection is an {@link EnumSet}, this
344 * method has the same behavior as {@link EnumSet#complementOf}. Otherwise,
345 * the specified collection must contain at least one element, in order to
346 * determine the element type. If the collection could be empty, use
347 * {@link #complementOf(Collection, Class)} instead of this method.
348 *
349 * @param collection the collection whose complement should be stored in the
350 * enum set
351 * @return a new, modifiable {@code EnumSet} containing all values of the enum
352 * that aren't present in the given collection
353 * @throws IllegalArgumentException if {@code collection} is not an
354 * {@code EnumSet} instance and contains no elements
355 */
356 public static <E extends Enum<E>> EnumSet<E> complementOf(
357 Collection<E> collection) {
358 if (collection instanceof EnumSet) {
359 return EnumSet.complementOf((EnumSet<E>) collection);
360 }
361 checkArgument(!collection.isEmpty(),
362 "collection is empty; use the other version of this method");
363 Class<E> type = collection.iterator().next().getDeclaringClass();
364 return makeComplementByHand(collection, type);
365 }
366
367 /**
368 * Creates an {@code EnumSet} consisting of all enum values that are not in
369 * the specified collection. This is equivalent to
370 * {@link EnumSet#complementOf}, but can act on any input collection, as long
371 * as the elements are of enum type.
372 *
373 * @param collection the collection whose complement should be stored in the
374 * {@code EnumSet}
375 * @param type the type of the elements in the set
376 * @return a new, modifiable {@code EnumSet} initially containing all the
377 * values of the enum not present in the given collection
378 */
379 public static <E extends Enum<E>> EnumSet<E> complementOf(
380 Collection<E> collection, Class<E> type) {
381 checkNotNull(collection);
382 return (collection instanceof EnumSet)
383 ? EnumSet.complementOf((EnumSet<E>) collection)
384 : makeComplementByHand(collection, type);
385 }
386
387 private static <E extends Enum<E>> EnumSet<E> makeComplementByHand(
388 Collection<E> collection, Class<E> type) {
389 EnumSet<E> result = EnumSet.allOf(type);
390 result.removeAll(collection);
391 return result;
392 }
393
394 /*
395 * Regarding newSetForMap() and SetFromMap:
396 *
397 * Written by Doug Lea with assistance from members of JCP JSR-166
398 * Expert Group and released to the public domain, as explained at
399 * http://creativecommons.org/licenses/publicdomain
400 */
401
402 /**
403 * Returns a set backed by the specified map. The resulting set displays
404 * the same ordering, concurrency, and performance characteristics as the
405 * backing map. In essence, this factory method provides a {@link Set}
406 * implementation corresponding to any {@link Map} implementation. There is no
407 * need to use this method on a {@link Map} implementation that already has a
408 * corresponding {@link Set} implementation (such as {@link java.util.HashMap}
409 * or {@link java.util.TreeMap}).
410 *
411 * <p>Each method invocation on the set returned by this method results in
412 * exactly one method invocation on the backing map or its {@code keySet}
413 * view, with one exception. The {@code addAll} method is implemented as a
414 * sequence of {@code put} invocations on the backing map.
415 *
416 * <p>The specified map must be empty at the time this method is invoked,
417 * and should not be accessed directly after this method returns. These
418 * conditions are ensured if the map is created empty, passed directly
419 * to this method, and no reference to the map is retained, as illustrated
420 * in the following code fragment: <pre> {@code
421 *
422 * Set<Object> identityHashSet = Sets.newSetFromMap(
423 * new IdentityHashMap<Object, Boolean>());}</pre>
424 *
425 * This method has the same behavior as the JDK 6 method
426 * {@code Collections.newSetFromMap()}. The returned set is serializable if
427 * the backing map is.
428 *
429 * @param map the backing map
430 * @return the set backed by the map
431 * @throws IllegalArgumentException if {@code map} is not empty
432 */
433 public static <E> Set<E> newSetFromMap(Map<E, Boolean> map) {
434 return new SetFromMap<E>(map);
435 }
436
437 private static class SetFromMap<E> extends AbstractSet<E>
438 implements Set<E>, Serializable {
439 private final Map<E, Boolean> m; // The backing map
440 private transient Set<E> s; // Its keySet
441
442 SetFromMap(Map<E, Boolean> map) {
443 checkArgument(map.isEmpty(), "Map is non-empty");
444 m = map;
445 s = map.keySet();
446 }
447
448 @Override public void clear() {
449 m.clear();
450 }
451 @Override public int size() {
452 return m.size();
453 }
454 @Override public boolean isEmpty() {
455 return m.isEmpty();
456 }
457 @Override public boolean contains(Object o) {
458 return m.containsKey(o);
459 }
460 @Override public boolean remove(Object o) {
461 return m.remove(o) != null;
462 }
463 @Override public boolean add(E e) {
464 return m.put(e, Boolean.TRUE) == null;
465 }
466 @Override public Iterator<E> iterator() {
467 return s.iterator();
468 }
469 @Override public Object[] toArray() {
470 return s.toArray();
471 }
472 @Override public <T> T[] toArray(T[] a) {
473 return s.toArray(a);
474 }
475 @Override public String toString() {
476 return s.toString();
477 }
478 @Override public int hashCode() {
479 return s.hashCode();
480 }
481 @Override public boolean equals(@Nullable Object object) {
482 return this == object || this.s.equals(object);
483 }
484 @Override public boolean containsAll(Collection<?> c) {
485 return s.containsAll(c);
486 }
487 @Override public boolean removeAll(Collection<?> c) {
488 return s.removeAll(c);
489 }
490 @Override public boolean retainAll(Collection<?> c) {
491 return s.retainAll(c);
492 }
493
494 // addAll is the only inherited implementation
495 @GwtIncompatible("not needed in emulated source")
496 private static final long serialVersionUID = 0;
497
498 @GwtIncompatible("java.io.ObjectInputStream")
499 private void readObject(ObjectInputStream stream)
500 throws IOException, ClassNotFoundException {
501 stream.defaultReadObject();
502 s = m.keySet();
503 }
504 }
505
506 /**
507 * An unmodifiable view of a set which may be backed by other sets; this view
508 * will change as the backing sets do. Contains methods to copy the data into
509 * a new set which will then remain stable. There is usually no reason to
510 * retain a reference of type {@code SetView}; typically, you either use it
511 * as a plain {@link Set}, or immediately invoke {@link #immutableCopy} or
512 * {@link #copyInto} and forget the {@code SetView} itself.
513 *
514 * @since 2.0 (imported from Google Collections Library)
515 */
516 public abstract static class SetView<E> extends AbstractSet<E> {
517 private SetView() {} // no subclasses but our own
518
519 /**
520 * Returns an immutable copy of the current contents of this set view.
521 * Does not support null elements.
522 *
523 * <p><b>Warning:</b> this may have unexpected results if a backing set of
524 * this view uses a nonstandard notion of equivalence, for example if it is
525 * a {@link TreeSet} using a comparator that is inconsistent with {@link
526 * Object#equals(Object)}.
527 */
528 public ImmutableSet<E> immutableCopy() {
529 return ImmutableSet.copyOf(this);
530 }
531
532 /**
533 * Copies the current contents of this set view into an existing set. This
534 * method has equivalent behavior to {@code set.addAll(this)}, assuming that
535 * all the sets involved are based on the same notion of equivalence.
536 *
537 * @return a reference to {@code set}, for convenience
538 */
539 // Note: S should logically extend Set<? super E> but can't due to either
540 // some javac bug or some weirdness in the spec, not sure which.
541 public <S extends Set<E>> S copyInto(S set) {
542 set.addAll(this);
543 return set;
544 }
545 }
546
547 /**
548 * Returns an unmodifiable <b>view</b> of the union of two sets. The returned
549 * set contains all elements that are contained in either backing set.
550 * Iterating over the returned set iterates first over all the elements of
551 * {@code set1}, then over each element of {@code set2}, in order, that is not
552 * contained in {@code set1}.
553 *
554 * <p>Results are undefined if {@code set1} and {@code set2} are sets based on
555 * different equivalence relations (as {@link HashSet}, {@link TreeSet}, and
556 * the {@link Map#keySet} of an {@code IdentityHashMap} all are).
557 *
558 * <p><b>Note:</b> The returned view performs better when {@code set1} is the
559 * smaller of the two sets. If you have reason to believe one of your sets
560 * will generally be smaller than the other, pass it first.
561 */
562 public static <E> SetView<E> union(
563 final Set<? extends E> set1, final Set<? extends E> set2) {
564 checkNotNull(set1, "set1");
565 checkNotNull(set2, "set2");
566
567 final Set<? extends E> set2minus1 = difference(set2, set1);
568
569 return new SetView<E>() {
570 @Override public int size() {
571 return set1.size() + set2minus1.size();
572 }
573 @Override public boolean isEmpty() {
574 return set1.isEmpty() && set2.isEmpty();
575 }
576 @Override public Iterator<E> iterator() {
577 return Iterators.unmodifiableIterator(
578 Iterators.concat(set1.iterator(), set2minus1.iterator()));
579 }
580 @Override public boolean contains(Object object) {
581 return set1.contains(object) || set2.contains(object);
582 }
583 @Override public <S extends Set<E>> S copyInto(S set) {
584 set.addAll(set1);
585 set.addAll(set2);
586 return set;
587 }
588 @Override public ImmutableSet<E> immutableCopy() {
589 return new ImmutableSet.Builder<E>()
590 .addAll(set1).addAll(set2).build();
591 }
592 };
593 }
594
595 /**
596 * Returns an unmodifiable <b>view</b> of the intersection of two sets. The
597 * returned set contains all elements that are contained by both backing sets.
598 * The iteration order of the returned set matches that of {@code set1}.
599 *
600 * <p>Results are undefined if {@code set1} and {@code set2} are sets based
601 * on different equivalence relations (as {@code HashSet}, {@code TreeSet},
602 * and the keySet of an {@code IdentityHashMap} all are).
603 *
604 * <p><b>Note:</b> The returned view performs slightly better when {@code
605 * set1} is the smaller of the two sets. If you have reason to believe one of
606 * your sets will generally be smaller than the other, pass it first.
607 * Unfortunately, since this method sets the generic type of the returned set
608 * based on the type of the first set passed, this could in rare cases force
609 * you to make a cast, for example: <pre> {@code
610 *
611 * Set<Object> aFewBadObjects = ...
612 * Set<String> manyBadStrings = ...
613 *
614 * // impossible for a non-String to be in the intersection
615 * SuppressWarnings("unchecked")
616 * Set<String> badStrings = (Set) Sets.intersection(
617 * aFewBadObjects, manyBadStrings);}</pre>
618 *
619 * This is unfortunate, but should come up only very rarely.
620 */
621 public static <E> SetView<E> intersection(
622 final Set<E> set1, final Set<?> set2) {
623 checkNotNull(set1, "set1");
624 checkNotNull(set2, "set2");
625
626 final Predicate<Object> inSet2 = Predicates.in(set2);
627 return new SetView<E>() {
628 @Override public Iterator<E> iterator() {
629 return Iterators.filter(set1.iterator(), inSet2);
630 }
631 @Override public int size() {
632 return Iterators.size(iterator());
633 }
634 @Override public boolean isEmpty() {
635 return !iterator().hasNext();
636 }
637 @Override public boolean contains(Object object) {
638 return set1.contains(object) && set2.contains(object);
639 }
640 @Override public boolean containsAll(Collection<?> collection) {
641 return set1.containsAll(collection)
642 && set2.containsAll(collection);
643 }
644 };
645 }
646
647 /**
648 * Returns an unmodifiable <b>view</b> of the difference of two sets. The
649 * returned set contains all elements that are contained by {@code set1} and
650 * not contained by {@code set2}. {@code set2} may also contain elements not
651 * present in {@code set1}; these are simply ignored. The iteration order of
652 * the returned set matches that of {@code set1}.
653 *
654 * <p>Results are undefined if {@code set1} and {@code set2} are sets based
655 * on different equivalence relations (as {@code HashSet}, {@code TreeSet},
656 * and the keySet of an {@code IdentityHashMap} all are).
657 */
658 public static <E> SetView<E> difference(
659 final Set<E> set1, final Set<?> set2) {
660 checkNotNull(set1, "set1");
661 checkNotNull(set2, "set2");
662
663 final Predicate<Object> notInSet2 = Predicates.not(Predicates.in(set2));
664 return new SetView<E>() {
665 @Override public Iterator<E> iterator() {
666 return Iterators.filter(set1.iterator(), notInSet2);
667 }
668 @Override public int size() {
669 return Iterators.size(iterator());
670 }
671 @Override public boolean isEmpty() {
672 return set2.containsAll(set1);
673 }
674 @Override public boolean contains(Object element) {
675 return set1.contains(element) && !set2.contains(element);
676 }
677 };
678 }
679
680 /**
681 * Returns an unmodifiable <b>view</b> of the symmetric difference of two
682 * sets. The returned set contains all elements that are contained in either
683 * {@code set1} or {@code set2} but not in both. The iteration order of the
684 * returned set is undefined.
685 *
686 * <p>Results are undefined if {@code set1} and {@code set2} are sets based
687 * on different equivalence relations (as {@code HashSet}, {@code TreeSet},
688 * and the keySet of an {@code IdentityHashMap} all are).
689 *
690 * @since 3.0
691 */
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(kevinb): 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. When given an element that doesn't satisfy
708 * the predicate, the set's {@code add()} and {@code addAll()} methods throw
709 * an {@link IllegalArgumentException}. When methods such as {@code
710 * removeAll()} and {@code clear()} are called on the filtered set, only
711 * elements that satisfy the filter will be removed from the underlying set.
712 *
713 * <p>The returned set isn't threadsafe or serializable, even if
714 * {@code unfiltered} is.
715 *
716 * <p>Many of the filtered set's methods, such as {@code size()}, iterate
717 * across every element in the underlying set and determine which elements
718 * satisfy the filter. When a live view is <i>not</i> needed, it may be faster
719 * to copy {@code Iterables.filter(unfiltered, predicate)} and use the copy.
720 *
721 * <p><b>Warning:</b> {@code predicate} must be <i>consistent with equals</i>,
722 * as documented at {@link Predicate#apply}. Do not provide a predicate such
723 * as {@code Predicates.instanceOf(ArrayList.class)}, which is inconsistent
724 * with equals. (See {@link Iterables#filter(Iterable, Class)} for related
725 * functionality.)
726 */
727 // TODO(kevinb): how to omit that last sentence when building GWT javadoc?
728 public static <E> Set<E> filter(
729 Set<E> unfiltered, Predicate<? super E> predicate) {
730 if (unfiltered instanceof FilteredSet) {
731 // Support clear(), removeAll(), and retainAll() when filtering a filtered
732 // collection.
733 FilteredSet<E> filtered = (FilteredSet<E>) unfiltered;
734 Predicate<E> combinedPredicate
735 = Predicates.<E>and(filtered.predicate, predicate);
736 return new FilteredSet<E>(
737 (Set<E>) filtered.unfiltered, combinedPredicate);
738 }
739
740 return new FilteredSet<E>(
741 checkNotNull(unfiltered), checkNotNull(predicate));
742 }
743
744 private static class FilteredSet<E> extends FilteredCollection<E>
745 implements Set<E> {
746 FilteredSet(Set<E> unfiltered, Predicate<? super E> predicate) {
747 super(unfiltered, predicate);
748 }
749
750 @Override public boolean equals(@Nullable Object object) {
751 return equalsImpl(this, object);
752 }
753
754 @Override public int hashCode() {
755 return hashCodeImpl(this);
756 }
757 }
758
759 /**
760 * Returns every possible list that can be formed by choosing one element
761 * from each of the given sets in order; the "n-ary
762 * <a href="http://en.wikipedia.org/wiki/Cartesian_product">Cartesian
763 * product</a>" of the sets. For example: <pre> {@code
764 *
765 * Sets.cartesianProduct(ImmutableList.of(
766 * ImmutableSet.of(1, 2),
767 * ImmutableSet.of("A", "B", "C")))}</pre>
768 *
769 * returns a set containing six lists:
770 *
771 * <ul>
772 * <li>{@code ImmutableList.of(1, "A")}
773 * <li>{@code ImmutableList.of(1, "B")}
774 * <li>{@code ImmutableList.of(1, "C")}
775 * <li>{@code ImmutableList.of(2, "A")}
776 * <li>{@code ImmutableList.of(2, "B")}
777 * <li>{@code ImmutableList.of(2, "C")}
778 * </ul>
779 *
780 * The order in which these lists are returned is not guaranteed, however the
781 * position of an element inside a tuple always corresponds to the position of
782 * the set from which it came in the input list. Note that if any input set is
783 * empty, the Cartesian product will also be empty. If no sets at all are
784 * provided (an empty list), the resulting Cartesian product has one element,
785 * an empty list (counter-intuitive, but mathematically consistent).
786 *
787 * <p><i>Performance notes:</i> while the cartesian product of sets of size
788 * {@code m, n, p} is a set of size {@code m x n x p}, its actual memory
789 * consumption is much smaller. When the cartesian set is constructed, the
790 * input sets are merely copied. Only as the resulting set is iterated are the
791 * individual lists created, and these are not retained after iteration.
792 *
793 * @param sets the sets to choose elements from, in the order that
794 * the elements chosen from those sets should appear in the resulting
795 * lists
796 * @param <B> any common base class shared by all axes (often just {@link
797 * Object})
798 * @return the Cartesian product, as an immutable set containing immutable
799 * lists
800 * @throws NullPointerException if {@code sets}, any one of the {@code sets},
801 * or any element of a provided set is null
802 * @since 2.0
803 */
804 public static <B> Set<List<B>> cartesianProduct(
805 List<? extends Set<? extends B>> sets) {
806 for (Set<? extends B> set : sets) {
807 if (set.isEmpty()) {
808 return ImmutableSet.of();
809 }
810 }
811 CartesianSet<B> cartesianSet = new CartesianSet<B>(sets);
812 return cartesianSet;
813 }
814
815 /**
816 * Returns every possible list that can be formed by choosing one element
817 * from each of the given sets in order; the "n-ary
818 * <a href="http://en.wikipedia.org/wiki/Cartesian_product">Cartesian
819 * product</a>" of the sets. For example: <pre> {@code
820 *
821 * Sets.cartesianProduct(
822 * ImmutableSet.of(1, 2),
823 * ImmutableSet.of("A", "B", "C"))}</pre>
824 *
825 * returns a set containing six lists:
826 *
827 * <ul>
828 * <li>{@code ImmutableList.of(1, "A")}
829 * <li>{@code ImmutableList.of(1, "B")}
830 * <li>{@code ImmutableList.of(1, "C")}
831 * <li>{@code ImmutableList.of(2, "A")}
832 * <li>{@code ImmutableList.of(2, "B")}
833 * <li>{@code ImmutableList.of(2, "C")}
834 * </ul>
835 *
836 * The order in which these lists are returned is not guaranteed, however the
837 * position of an element inside a tuple always corresponds to the position of
838 * the set from which it came in the input list. Note that if any input set is
839 * empty, the Cartesian product will also be empty. If no sets at all are
840 * provided, the resulting Cartesian product has one element, an empty list
841 * (counter-intuitive, but mathematically consistent).
842 *
843 * <p><i>Performance notes:</i> while the cartesian product of sets of size
844 * {@code m, n, p} is a set of size {@code m x n x p}, its actual memory
845 * consumption is much smaller. When the cartesian set is constructed, the
846 * input sets are merely copied. Only as the resulting set is iterated are the
847 * individual lists created, and these are not retained after iteration.
848 *
849 * @param sets the sets to choose elements from, in the order that
850 * the elements chosen from those sets should appear in the resulting
851 * lists
852 * @param <B> any common base class shared by all axes (often just {@link
853 * Object})
854 * @return the Cartesian product, as an immutable set containing immutable
855 * lists
856 * @throws NullPointerException if {@code sets}, any one of the {@code sets},
857 * or any element of a provided set is null
858 * @since 2.0
859 */
860 public static <B> Set<List<B>> cartesianProduct(
861 Set<? extends B>... sets) {
862 return cartesianProduct(Arrays.asList(sets));
863 }
864
865 private static class CartesianSet<B> extends AbstractSet<List<B>> {
866 final ImmutableList<Axis> axes;
867 final int size;
868
869 CartesianSet(List<? extends Set<? extends B>> sets) {
870 long dividend = 1;
871 ImmutableList.Builder<Axis> builder = ImmutableList.builder();
872 for (Set<? extends B> set : sets) {
873 Axis axis = new Axis(set, (int) dividend); // check overflow at end
874 builder.add(axis);
875 dividend *= axis.size();
876 checkArgument(dividend <= Integer.MAX_VALUE,
877 "cartesian product is too big");
878 }
879 this.axes = builder.build();
880 size = Ints.checkedCast(dividend);
881 }
882
883 @Override public int size() {
884 return size;
885 }
886
887 @Override public UnmodifiableIterator<List<B>> iterator() {
888 return new UnmodifiableIterator<List<B>>() {
889 int index;
890
891 @Override
892 public boolean hasNext() {
893 return index < size;
894 }
895
896 @Override
897 public List<B> next() {
898 if (!hasNext()) {
899 throw new NoSuchElementException();
900 }
901
902 Object[] tuple = new Object[axes.size()];
903 for (int i = 0 ; i < tuple.length; i++) {
904 tuple[i] = axes.get(i).getForIndex(index);
905 }
906 index++;
907
908 @SuppressWarnings("unchecked") // only B's are put in here
909 List<B> result = (ImmutableList<B>) ImmutableList.copyOf(tuple);
910 return result;
911 }
912 };
913 }
914
915 @Override public boolean contains(Object element) {
916 if (!(element instanceof List<?>)) {
917 return false;
918 }
919 List<?> tuple = (List<?>) element;
920 int dimensions = axes.size();
921 if (tuple.size() != dimensions) {
922 return false;
923 }
924 for (int i = 0; i < dimensions; i++) {
925 if (!axes.get(i).contains(tuple.get(i))) {
926 return false;
927 }
928 }
929 return true;
930 }
931
932 @Override public boolean equals(@Nullable Object object) {
933 // Warning: this is broken if size() == 0, so it is critical that we
934 // substitute an empty ImmutableSet to the user in place of this
935 if (object instanceof CartesianSet) {
936 CartesianSet<?> that = (CartesianSet<?>) object;
937 return this.axes.equals(that.axes);
938 }
939 return super.equals(object);
940 }
941
942 @Override public int hashCode() {
943 // Warning: this is broken if size() == 0, so it is critical that we
944 // substitute an empty ImmutableSet to the user in place of this
945
946 // It's a weird formula, but tests prove it works.
947 int adjust = size - 1;
948 for (int i = 0; i < axes.size(); i++) {
949 adjust *= 31;
950 }
951 return axes.hashCode() + adjust;
952 }
953
954 private class Axis {
955 final ImmutableSet<? extends B> choices;
956 final ImmutableList<? extends B> choicesList;
957 final int dividend;
958
959 Axis(Set<? extends B> set, int dividend) {
960 choices = ImmutableSet.copyOf(set);
961 choicesList = choices.asList();
962 this.dividend = dividend;
963 }
964
965 int size() {
966 return choices.size();
967 }
968
969 B getForIndex(int index) {
970 return choicesList.get(index / dividend % size());
971 }
972
973 boolean contains(Object target) {
974 return choices.contains(target);
975 }
976
977 @Override public boolean equals(Object obj) {
978 if (obj instanceof CartesianSet.Axis) {
979 CartesianSet.Axis that = (CartesianSet.Axis) obj;
980 return this.choices.equals(that.choices);
981 // dividends must be equal or we wouldn't have gotten this far
982 }
983 return false;
984 }
985
986 @Override public int hashCode() {
987 // Because Axis instances are not exposed, we can
988 // opportunistically choose whatever bizarre formula happens
989 // to make CartesianSet.hashCode() as simple as possible.
990 return size / choices.size() * choices.hashCode();
991 }
992 }
993 }
994
995 /**
996 * Returns the set of all possible subsets of {@code set}. For example,
997 * {@code powerSet(ImmutableSet.of(1, 2))} returns the set {@code {{},
998 * {1}, {2}, {1, 2}}}.
999 *
1000 * <p>Elements appear in these subsets in the same iteration order as they
1001 * appeared in the input set. The order in which these subsets appear in the
1002 * outer set is undefined. Note that the power set of the empty set is not the
1003 * empty set, but a one-element set containing the empty set.
1004 *
1005 * <p>The returned set and its constituent sets use {@code equals} to decide
1006 * whether two elements are identical, even if the input set uses a different
1007 * concept of equivalence.
1008 *
1009 * <p><i>Performance notes:</i> while the power set of a set with size {@code
1010 * n} is of size {@code 2^n}, its memory usage is only {@code O(n)}. When the
1011 * power set is constructed, the input set is merely copied. Only as the
1012 * power set is iterated are the individual subsets created, and these subsets
1013 * themselves occupy only a few bytes of memory regardless of their size.
1014 *
1015 * @param set the set of elements to construct a power set from
1016 * @return the power set, as an immutable set of immutable sets
1017 * @throws IllegalArgumentException if {@code set} has more than 30 unique
1018 * elements (causing the power set size to exceed the {@code int} range)
1019 * @throws NullPointerException if {@code set} is or contains {@code null}
1020 * @see <a href="http://en.wikipedia.org/wiki/Power_set">Power set article at
1021 * Wikipedia</a>
1022 * @since 4.0
1023 */
1024 @GwtCompatible(serializable = false)
1025 public static <E> Set<Set<E>> powerSet(Set<E> set) {
1026 ImmutableSet<E> input = ImmutableSet.copyOf(set);
1027 checkArgument(input.size() <= 30,
1028 "Too many elements to create power set: %s > 30", input.size());
1029 return new PowerSet<E>(input);
1030 }
1031
1032 private static final class PowerSet<E> extends AbstractSet<Set<E>> {
1033 final ImmutableSet<E> inputSet;
1034 final ImmutableList<E> inputList;
1035 final int powerSetSize;
1036
1037 PowerSet(ImmutableSet<E> input) {
1038 this.inputSet = input;
1039 this.inputList = input.asList();
1040 this.powerSetSize = 1 << input.size();
1041 }
1042
1043 @Override public int size() {
1044 return powerSetSize;
1045 }
1046
1047 @Override public boolean isEmpty() {
1048 return false;
1049 }
1050
1051 @Override public Iterator<Set<E>> iterator() {
1052 return new AbstractIndexedListIterator<Set<E>>(powerSetSize) {
1053 @Override protected Set<E> get(final int setBits) {
1054 return new AbstractSet<E>() {
1055 @Override public int size() {
1056 return Integer.bitCount(setBits);
1057 }
1058 @Override public Iterator<E> iterator() {
1059 return new BitFilteredSetIterator<E>(inputList, setBits);
1060 }
1061 };
1062 }
1063 };
1064 }
1065
1066 private static final class BitFilteredSetIterator<E>
1067 extends UnmodifiableIterator<E> {
1068 final ImmutableList<E> input;
1069 int remainingSetBits;
1070
1071 BitFilteredSetIterator(ImmutableList<E> input, int allSetBits) {
1072 this.input = input;
1073 this.remainingSetBits = allSetBits;
1074 }
1075
1076 @Override public boolean hasNext() {
1077 return remainingSetBits != 0;
1078 }
1079
1080 @Override public E next() {
1081 int index = Integer.numberOfTrailingZeros(remainingSetBits);
1082 if (index == 32) {
1083 throw new NoSuchElementException();
1084 }
1085
1086 int currentElementMask = 1 << index;
1087 remainingSetBits &= ~currentElementMask;
1088 return input.get(index);
1089 }
1090 }
1091
1092 @Override public boolean contains(@Nullable Object obj) {
1093 if (obj instanceof Set) {
1094 Set<?> set = (Set<?>) obj;
1095 return inputSet.containsAll(set);
1096 }
1097 return false;
1098 }
1099
1100 @Override public boolean equals(@Nullable Object obj) {
1101 if (obj instanceof PowerSet) {
1102 PowerSet<?> that = (PowerSet<?>) obj;
1103 return inputSet.equals(that.inputSet);
1104 }
1105 return super.equals(obj);
1106 }
1107
1108 @Override public int hashCode() {
1109 /*
1110 * The sum of the sums of the hash codes in each subset is just the sum of
1111 * each input element's hash code times the number of sets that element
1112 * appears in. Each element appears in exactly half of the 2^n sets, so:
1113 */
1114 return inputSet.hashCode() << (inputSet.size() - 1);
1115 }
1116
1117 @Override public String toString() {
1118 return "powerSet(" + inputSet + ")";
1119 }
1120 }
1121
1122 /**
1123 * An implementation for {@link Set#hashCode()}.
1124 */
1125 static int hashCodeImpl(Set<?> s) {
1126 int hashCode = 0;
1127 for (Object o : s) {
1128 hashCode += o != null ? o.hashCode() : 0;
1129 }
1130 return hashCode;
1131 }
1132
1133 /**
1134 * An implementation for {@link Set#equals(Object)}.
1135 */
1136 static boolean equalsImpl(Set<?> s, @Nullable Object object){
1137 if (s == object) {
1138 return true;
1139 }
1140 if (object instanceof Set) {
1141 Set<?> o = (Set<?>) object;
1142
1143 try {
1144 return s.size() == o.size() && s.containsAll(o);
1145 } catch (NullPointerException ignored) {
1146 return false;
1147 } catch (ClassCastException ignored) {
1148 return false;
1149 }
1150 }
1151 return false;
1152 }
1153
1154 /**
1155 * Creates a view of Set<B> for a Set<A>, given a bijection between A and B.
1156 * (Modelled for now as InvertibleFunction<A, B>, can't be Converter<A, B>
1157 * because that's not in Guava, though both designs are less than optimal).
1158 * Note that the bijection is treated as undefined for values not in the
1159 * given Set<A> - it doesn't have to define a true bijection for those.
1160 *
1161 * <p>Note that the returned Set's contains method is unsafe -
1162 * you *must* pass an instance of B to it, since the bijection
1163 * can only invert B's (not any Object) back to A, so we can
1164 * then delegate the call to the original Set<A>.
1165 */
1166 static <A, B> Set<B> transform(
1167 Set<A> set, InvertibleFunction<A, B> bijection) {
1168 return new TransformedSet<A, B>(
1169 Preconditions.checkNotNull(set, "set"),
1170 Preconditions.checkNotNull(bijection, "bijection")
1171 );
1172 }
1173
1174 /**
1175 * Stop-gap measure since there is no bijection related type in Guava.
1176 */
1177 abstract static class InvertibleFunction<A, B> implements Function<A, B> {
1178 abstract A invert(B b);
1179
1180 public InvertibleFunction<B, A> inverse() {
1181 return new InvertibleFunction<B, A>() {
1182 @Override public A apply(B b) {
1183 return InvertibleFunction.this.invert(b);
1184 }
1185
1186 @Override B invert(A a) {
1187 return InvertibleFunction.this.apply(a);
1188 }
1189
1190 // Not required per se, but just for good karma.
1191 @Override public InvertibleFunction<A, B> inverse() {
1192 return InvertibleFunction.this;
1193 }
1194 };
1195 }
1196 }
1197
1198 private static class TransformedSet<A, B> extends AbstractSet<B> {
1199 final Set<A> delegate;
1200 final InvertibleFunction<A, B> bijection;
1201
1202 TransformedSet(Set<A> delegate, InvertibleFunction<A, B> bijection) {
1203 this.delegate = delegate;
1204 this.bijection = bijection;
1205 }
1206
1207 @Override public Iterator<B> iterator() {
1208 return Iterators.transform(delegate.iterator(), bijection);
1209 }
1210
1211 @Override public int size() {
1212 return delegate.size();
1213 }
1214
1215 @SuppressWarnings("unchecked") // unsafe, passed object *must* be B
1216 @Override public boolean contains(Object o) {
1217 B b = (B) o;
1218 A a = bijection.invert(b);
1219 /*
1220 * Mathematically, Converter<A, B> defines a bijection between ALL A's
1221 * on ALL B's. Here we concern ourselves with a subset
1222 * of this relation: we only want the part that is defined by a *subset*
1223 * of all A's (defined by that Set<A> delegate), and the image
1224 * of *that* on B (which is this set). We don't care whether
1225 * the converter is *not* a bijection for A's that are not in Set<A>
1226 * or B's not in this Set<B>.
1227 *
1228 * We only want to return true if and only f the user passes a B instance
1229 * that is contained in precisely in the image of Set<A>.
1230 *
1231 * The first test is whether the inverse image of this B is indeed
1232 * in Set<A>. But we don't know whether that B belongs in this Set<B>
1233 * or not; if not, the converter is free to return
1234 * anything it wants, even an element of Set<A> (and this relationship
1235 * is not part of the Set<A> <--> Set<B> bijection), and we must not
1236 * be confused by that. So we have to do a final check to see if the
1237 * image of that A is really equivalent to the passed B, which proves
1238 * that the given B belongs indeed in the image of Set<A>.
1239 */
1240 return delegate.contains(a) && Objects.equal(bijection.apply(a), o);
1241 }
1242
1243 @Override public boolean add(B b) {
1244 return delegate.add(bijection.invert(b));
1245 }
1246
1247 @SuppressWarnings("unchecked") // unsafe, passed object *must* be B
1248 @Override public boolean remove(Object o) {
1249 return contains(o) && delegate.remove(bijection.invert((B) o));
1250 }
1251
1252 @Override public void clear() {
1253 delegate.clear();
1254 }
1255 }
1256 }