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