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