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 017package com.google.common.collect; 018 019import static com.google.common.base.Preconditions.checkArgument; 020import static com.google.common.base.Preconditions.checkNotNull; 021import static com.google.common.collect.CollectPreconditions.checkNonnegative; 022 023import com.google.common.annotations.Beta; 024import com.google.common.annotations.GwtCompatible; 025import com.google.common.annotations.GwtIncompatible; 026import com.google.common.base.Predicate; 027import com.google.common.base.Predicates; 028import com.google.common.collect.Collections2.FilteredCollection; 029import com.google.common.math.IntMath; 030import com.google.errorprone.annotations.CanIgnoreReturnValue; 031import com.google.errorprone.annotations.DoNotCall; 032import java.io.Serializable; 033import java.util.AbstractSet; 034import java.util.Arrays; 035import java.util.BitSet; 036import java.util.Collection; 037import java.util.Collections; 038import java.util.Comparator; 039import java.util.EnumSet; 040import java.util.HashSet; 041import java.util.Iterator; 042import java.util.LinkedHashSet; 043import java.util.List; 044import java.util.Map; 045import java.util.NavigableSet; 046import java.util.NoSuchElementException; 047import java.util.Set; 048import java.util.SortedSet; 049import java.util.TreeSet; 050import java.util.concurrent.ConcurrentHashMap; 051import java.util.concurrent.CopyOnWriteArraySet; 052import javax.annotation.CheckForNull; 053import org.checkerframework.checker.nullness.qual.Nullable; 054 055/** 056 * Static utility methods pertaining to {@link Set} instances. Also see this class's counterparts 057 * {@link Lists}, {@link Maps} and {@link Queues}. 058 * 059 * <p>See the Guava User Guide article on <a href= 060 * "https://github.com/google/guava/wiki/CollectionUtilitiesExplained#sets"> {@code Sets}</a>. 061 * 062 * @author Kevin Bourrillion 063 * @author Jared Levy 064 * @author Chris Povirk 065 * @since 2.0 066 */ 067@GwtCompatible(emulated = true) 068@ElementTypesAreNonnullByDefault 069public final class Sets { 070 private Sets() {} 071 072 /** 073 * {@link AbstractSet} substitute without the potentially-quadratic {@code removeAll} 074 * implementation. 075 */ 076 abstract static class ImprovedAbstractSet<E extends @Nullable Object> extends AbstractSet<E> { 077 @Override 078 public boolean removeAll(Collection<?> c) { 079 return removeAllImpl(this, c); 080 } 081 082 @Override 083 public boolean retainAll(Collection<?> c) { 084 return super.retainAll(checkNotNull(c)); // GWT compatibility 085 } 086 } 087 088 /** 089 * Returns an immutable set instance containing the given enum elements. Internally, the returned 090 * set will be backed by an {@link EnumSet}. 091 * 092 * <p>The iteration order of the returned set follows the enum's iteration order, not the order in 093 * which the elements are provided to the method. 094 * 095 * @param anElement one of the elements the set should contain 096 * @param otherElements the rest of the elements the set should contain 097 * @return an immutable set containing those elements, minus duplicates 098 */ 099 // http://code.google.com/p/google-web-toolkit/issues/detail?id=3028 100 @GwtCompatible(serializable = true) 101 public static <E extends Enum<E>> ImmutableSet<E> immutableEnumSet( 102 E anElement, E... otherElements) { 103 return ImmutableEnumSet.asImmutable(EnumSet.of(anElement, otherElements)); 104 } 105 106 /** 107 * Returns an immutable set instance containing the given enum elements. Internally, the returned 108 * set will be backed by an {@link EnumSet}. 109 * 110 * <p>The iteration order of the returned set follows the enum's iteration order, not the order in 111 * which the elements appear in the given collection. 112 * 113 * @param elements the elements, all of the same {@code enum} type, that the set should contain 114 * @return an immutable set containing those elements, minus duplicates 115 */ 116 // http://code.google.com/p/google-web-toolkit/issues/detail?id=3028 117 @GwtCompatible(serializable = true) 118 public static <E extends Enum<E>> ImmutableSet<E> immutableEnumSet(Iterable<E> elements) { 119 if (elements instanceof ImmutableEnumSet) { 120 return (ImmutableEnumSet<E>) elements; 121 } else if (elements instanceof Collection) { 122 Collection<E> collection = (Collection<E>) elements; 123 if (collection.isEmpty()) { 124 return ImmutableSet.of(); 125 } else { 126 return ImmutableEnumSet.asImmutable(EnumSet.copyOf(collection)); 127 } 128 } else { 129 Iterator<E> itr = elements.iterator(); 130 if (itr.hasNext()) { 131 EnumSet<E> enumSet = EnumSet.of(itr.next()); 132 Iterators.addAll(enumSet, itr); 133 return ImmutableEnumSet.asImmutable(enumSet); 134 } else { 135 return ImmutableSet.of(); 136 } 137 } 138 } 139 140 /** 141 * Returns a new, <i>mutable</i> {@code EnumSet} instance containing the given elements in their 142 * natural order. This method behaves identically to {@link EnumSet#copyOf(Collection)}, but also 143 * accepts non-{@code Collection} iterables and empty iterables. 144 */ 145 public static <E extends Enum<E>> EnumSet<E> newEnumSet( 146 Iterable<E> iterable, Class<E> elementType) { 147 EnumSet<E> set = EnumSet.noneOf(elementType); 148 Iterables.addAll(set, iterable); 149 return set; 150 } 151 152 // HashSet 153 154 /** 155 * Creates a <i>mutable</i>, initially empty {@code HashSet} instance. 156 * 157 * <p><b>Note:</b> if mutability is not required, use {@link ImmutableSet#of()} instead. If {@code 158 * E} is an {@link Enum} type, use {@link EnumSet#noneOf} instead. Otherwise, strongly consider 159 * using a {@code LinkedHashSet} instead, at the cost of increased memory footprint, to get 160 * deterministic iteration behavior. 161 * 162 * <p><b>Note for Java 7 and later:</b> this method is now unnecessary and should be treated as 163 * deprecated. Instead, use the {@code HashSet} constructor directly, taking advantage of the new 164 * <a href="http://goo.gl/iz2Wi">"diamond" syntax</a>. 165 */ 166 public static <E extends @Nullable Object> HashSet<E> newHashSet() { 167 return new HashSet<E>(); 168 } 169 170 /** 171 * Creates a <i>mutable</i> {@code HashSet} instance initially containing the given elements. 172 * 173 * <p><b>Note:</b> if elements are non-null and won't be added or removed after this point, use 174 * {@link ImmutableSet#of()} or {@link ImmutableSet#copyOf(Object[])} instead. If {@code E} is an 175 * {@link Enum} type, use {@link EnumSet#of(Enum, Enum[])} instead. Otherwise, strongly consider 176 * using a {@code LinkedHashSet} instead, at the cost of increased memory footprint, to get 177 * deterministic iteration behavior. 178 * 179 * <p>This method is just a small convenience, either for {@code newHashSet(}{@link Arrays#asList 180 * asList}{@code (...))}, or for creating an empty set then calling {@link Collections#addAll}. 181 * This method is not actually very useful and will likely be deprecated in the future. 182 */ 183 public static <E extends @Nullable Object> HashSet<E> newHashSet(E... elements) { 184 HashSet<E> set = newHashSetWithExpectedSize(elements.length); 185 Collections.addAll(set, elements); 186 return set; 187 } 188 189 /** 190 * Creates a <i>mutable</i> {@code HashSet} instance containing the given elements. A very thin 191 * convenience for creating an empty set then calling {@link Collection#addAll} or {@link 192 * Iterables#addAll}. 193 * 194 * <p><b>Note:</b> if mutability is not required and the elements are non-null, use {@link 195 * ImmutableSet#copyOf(Iterable)} instead. (Or, change {@code elements} to be a {@link 196 * FluentIterable} and call {@code elements.toSet()}.) 197 * 198 * <p><b>Note:</b> if {@code E} is an {@link Enum} type, use {@link #newEnumSet(Iterable, Class)} 199 * instead. 200 * 201 * <p><b>Note for Java 7 and later:</b> if {@code elements} is a {@link Collection}, you don't 202 * need this method. Instead, use the {@code HashSet} constructor directly, taking advantage of 203 * the new <a href="http://goo.gl/iz2Wi">"diamond" syntax</a>. 204 * 205 * <p>Overall, this method is not very useful and will likely be deprecated in the future. 206 */ 207 public static <E extends @Nullable Object> HashSet<E> newHashSet(Iterable<? extends E> elements) { 208 return (elements instanceof Collection) 209 ? new HashSet<E>((Collection<? extends E>) elements) 210 : newHashSet(elements.iterator()); 211 } 212 213 /** 214 * Creates a <i>mutable</i> {@code HashSet} instance containing the given elements. A very thin 215 * convenience for creating an empty set and then calling {@link Iterators#addAll}. 216 * 217 * <p><b>Note:</b> if mutability is not required and the elements are non-null, use {@link 218 * ImmutableSet#copyOf(Iterator)} instead. 219 * 220 * <p><b>Note:</b> if {@code E} is an {@link Enum} type, you should create an {@link EnumSet} 221 * instead. 222 * 223 * <p>Overall, this method is not very useful and will likely be deprecated in the future. 224 */ 225 public static <E extends @Nullable Object> HashSet<E> newHashSet(Iterator<? extends E> elements) { 226 HashSet<E> set = newHashSet(); 227 Iterators.addAll(set, elements); 228 return set; 229 } 230 231 /** 232 * Returns a new hash set using the smallest initial table size that can hold {@code expectedSize} 233 * elements without resizing. Note that this is not what {@link HashSet#HashSet(int)} does, but it 234 * is what most users want and expect it to do. 235 * 236 * <p>This behavior can't be broadly guaranteed, but has been tested with OpenJDK 1.7 and 1.8. 237 * 238 * @param expectedSize the number of elements you expect to add to the returned set 239 * @return a new, empty hash set with enough capacity to hold {@code expectedSize} elements 240 * without resizing 241 * @throws IllegalArgumentException if {@code expectedSize} is negative 242 */ 243 public static <E extends @Nullable Object> HashSet<E> newHashSetWithExpectedSize( 244 int expectedSize) { 245 return new HashSet<E>(Maps.capacity(expectedSize)); 246 } 247 248 /** 249 * Creates a thread-safe set backed by a hash map. The set is backed by a {@link 250 * ConcurrentHashMap} instance, and thus carries the same concurrency guarantees. 251 * 252 * <p>Unlike {@code HashSet}, this class does NOT allow {@code null} to be used as an element. The 253 * set is serializable. 254 * 255 * @return a new, empty thread-safe {@code Set} 256 * @since 15.0 257 */ 258 public static <E> Set<E> newConcurrentHashSet() { 259 return Collections.newSetFromMap(new ConcurrentHashMap<E, Boolean>()); 260 } 261 262 /** 263 * Creates a thread-safe set backed by a hash map and containing the given elements. The set is 264 * backed by a {@link ConcurrentHashMap} instance, and thus carries the same concurrency 265 * guarantees. 266 * 267 * <p>Unlike {@code HashSet}, this class does NOT allow {@code null} to be used as an element. The 268 * set is serializable. 269 * 270 * @param elements the elements that the set should contain 271 * @return a new thread-safe set containing those elements (minus duplicates) 272 * @throws NullPointerException if {@code elements} or any of its contents is null 273 * @since 15.0 274 */ 275 public static <E> Set<E> newConcurrentHashSet(Iterable<? extends E> elements) { 276 Set<E> set = newConcurrentHashSet(); 277 Iterables.addAll(set, elements); 278 return set; 279 } 280 281 // LinkedHashSet 282 283 /** 284 * Creates a <i>mutable</i>, empty {@code LinkedHashSet} instance. 285 * 286 * <p><b>Note:</b> if mutability is not required, use {@link ImmutableSet#of()} instead. 287 * 288 * <p><b>Note for Java 7 and later:</b> this method is now unnecessary and should be treated as 289 * deprecated. Instead, use the {@code LinkedHashSet} constructor directly, taking advantage of 290 * the new <a href="http://goo.gl/iz2Wi">"diamond" syntax</a>. 291 * 292 * @return a new, empty {@code LinkedHashSet} 293 */ 294 public static <E extends @Nullable Object> LinkedHashSet<E> newLinkedHashSet() { 295 return new LinkedHashSet<E>(); 296 } 297 298 /** 299 * Creates a <i>mutable</i> {@code LinkedHashSet} instance containing the given elements in order. 300 * 301 * <p><b>Note:</b> if mutability is not required and the elements are non-null, use {@link 302 * ImmutableSet#copyOf(Iterable)} instead. 303 * 304 * <p><b>Note for Java 7 and later:</b> if {@code elements} is a {@link Collection}, you don't 305 * need this method. Instead, use the {@code LinkedHashSet} constructor directly, taking advantage 306 * of the new <a href="http://goo.gl/iz2Wi">"diamond" syntax</a>. 307 * 308 * <p>Overall, this method is not very useful and will likely be deprecated in the future. 309 * 310 * @param elements the elements that the set should contain, in order 311 * @return a new {@code LinkedHashSet} containing those elements (minus duplicates) 312 */ 313 public static <E extends @Nullable Object> LinkedHashSet<E> newLinkedHashSet( 314 Iterable<? extends E> elements) { 315 if (elements instanceof Collection) { 316 return new LinkedHashSet<E>((Collection<? extends E>) elements); 317 } 318 LinkedHashSet<E> set = newLinkedHashSet(); 319 Iterables.addAll(set, elements); 320 return set; 321 } 322 323 /** 324 * Creates a {@code LinkedHashSet} instance, with a high enough "initial capacity" that it 325 * <i>should</i> hold {@code expectedSize} elements without growth. This behavior cannot be 326 * broadly guaranteed, but it is observed to be true for OpenJDK 1.7. It also can't be guaranteed 327 * that the method isn't inadvertently <i>oversizing</i> the returned set. 328 * 329 * @param expectedSize the number of elements you expect to add to the returned set 330 * @return a new, empty {@code LinkedHashSet} with enough capacity to hold {@code expectedSize} 331 * elements without resizing 332 * @throws IllegalArgumentException if {@code expectedSize} is negative 333 * @since 11.0 334 */ 335 public static <E extends @Nullable Object> LinkedHashSet<E> newLinkedHashSetWithExpectedSize( 336 int expectedSize) { 337 return new LinkedHashSet<E>(Maps.capacity(expectedSize)); 338 } 339 340 // TreeSet 341 342 /** 343 * Creates a <i>mutable</i>, empty {@code TreeSet} instance sorted by the natural sort ordering of 344 * its elements. 345 * 346 * <p><b>Note:</b> if mutability is not required, use {@link ImmutableSortedSet#of()} instead. 347 * 348 * <p><b>Note for Java 7 and later:</b> this method is now unnecessary and should be treated as 349 * deprecated. Instead, use the {@code TreeSet} constructor directly, taking advantage of the new 350 * <a href="http://goo.gl/iz2Wi">"diamond" syntax</a>. 351 * 352 * @return a new, empty {@code TreeSet} 353 */ 354 public static <E extends Comparable> TreeSet<E> newTreeSet() { 355 return new TreeSet<E>(); 356 } 357 358 /** 359 * Creates a <i>mutable</i> {@code TreeSet} instance containing the given elements sorted by their 360 * natural ordering. 361 * 362 * <p><b>Note:</b> if mutability is not required, use {@link ImmutableSortedSet#copyOf(Iterable)} 363 * instead. 364 * 365 * <p><b>Note:</b> If {@code elements} is a {@code SortedSet} with an explicit comparator, this 366 * method has different behavior than {@link TreeSet#TreeSet(SortedSet)}, which returns a {@code 367 * TreeSet} with that comparator. 368 * 369 * <p><b>Note for Java 7 and later:</b> this method is now unnecessary and should be treated as 370 * deprecated. Instead, use the {@code TreeSet} constructor directly, taking advantage of the new 371 * <a href="http://goo.gl/iz2Wi">"diamond" syntax</a>. 372 * 373 * <p>This method is just a small convenience for creating an empty set and then calling {@link 374 * Iterables#addAll}. This method is not very useful and will likely be deprecated in the future. 375 * 376 * @param elements the elements that the set should contain 377 * @return a new {@code TreeSet} containing those elements (minus duplicates) 378 */ 379 public static <E extends Comparable> TreeSet<E> newTreeSet(Iterable<? extends E> elements) { 380 TreeSet<E> set = newTreeSet(); 381 Iterables.addAll(set, elements); 382 return set; 383 } 384 385 /** 386 * Creates a <i>mutable</i>, empty {@code TreeSet} instance with the given comparator. 387 * 388 * <p><b>Note:</b> if mutability is not required, use {@code 389 * ImmutableSortedSet.orderedBy(comparator).build()} instead. 390 * 391 * <p><b>Note for Java 7 and later:</b> this method is now unnecessary and should be treated as 392 * deprecated. Instead, use the {@code TreeSet} constructor directly, taking advantage of the new 393 * <a href="http://goo.gl/iz2Wi">"diamond" syntax</a>. One caveat to this is that the {@code 394 * TreeSet} constructor uses a null {@code Comparator} to mean "natural ordering," whereas this 395 * factory rejects null. Clean your code accordingly. 396 * 397 * @param comparator the comparator to use to sort the set 398 * @return a new, empty {@code TreeSet} 399 * @throws NullPointerException if {@code comparator} is null 400 */ 401 public static <E extends @Nullable Object> TreeSet<E> newTreeSet( 402 Comparator<? super E> comparator) { 403 return new TreeSet<E>(checkNotNull(comparator)); 404 } 405 406 /** 407 * Creates an empty {@code Set} that uses identity to determine equality. It compares object 408 * references, instead of calling {@code equals}, to determine whether a provided object matches 409 * an element in the set. For example, {@code contains} returns {@code false} when passed an 410 * object that equals a set member, but isn't the same instance. This behavior is similar to the 411 * way {@code IdentityHashMap} handles key lookups. 412 * 413 * @since 8.0 414 */ 415 public static <E extends @Nullable Object> Set<E> newIdentityHashSet() { 416 return Collections.newSetFromMap(Maps.<E, Boolean>newIdentityHashMap()); 417 } 418 419 /** 420 * Creates an empty {@code CopyOnWriteArraySet} instance. 421 * 422 * <p><b>Note:</b> if you need an immutable empty {@link Set}, use {@link Collections#emptySet} 423 * instead. 424 * 425 * @return a new, empty {@code CopyOnWriteArraySet} 426 * @since 12.0 427 */ 428 @GwtIncompatible // CopyOnWriteArraySet 429 public static <E extends @Nullable Object> CopyOnWriteArraySet<E> newCopyOnWriteArraySet() { 430 return new CopyOnWriteArraySet<E>(); 431 } 432 433 /** 434 * Creates a {@code CopyOnWriteArraySet} instance containing the given elements. 435 * 436 * @param elements the elements that the set should contain, in order 437 * @return a new {@code CopyOnWriteArraySet} containing those elements 438 * @since 12.0 439 */ 440 @GwtIncompatible // CopyOnWriteArraySet 441 public static <E extends @Nullable Object> CopyOnWriteArraySet<E> newCopyOnWriteArraySet( 442 Iterable<? extends E> elements) { 443 // We copy elements to an ArrayList first, rather than incurring the 444 // quadratic cost of adding them to the COWAS directly. 445 Collection<? extends E> elementsCollection = 446 (elements instanceof Collection) 447 ? (Collection<? extends E>) elements 448 : Lists.newArrayList(elements); 449 return new CopyOnWriteArraySet<E>(elementsCollection); 450 } 451 452 /** 453 * Creates an {@code EnumSet} consisting of all enum values that are not in the specified 454 * collection. If the collection is an {@link EnumSet}, this method has the same behavior as 455 * {@link EnumSet#complementOf}. Otherwise, the specified collection must contain at least one 456 * element, in order to determine the element type. If the collection could be empty, use {@link 457 * #complementOf(Collection, Class)} instead of this method. 458 * 459 * @param collection the collection whose complement should be stored in the enum set 460 * @return a new, modifiable {@code EnumSet} containing all values of the enum that aren't present 461 * in the given collection 462 * @throws IllegalArgumentException if {@code collection} is not an {@code EnumSet} instance and 463 * contains no elements 464 */ 465 public static <E extends Enum<E>> EnumSet<E> complementOf(Collection<E> collection) { 466 if (collection instanceof EnumSet) { 467 return EnumSet.complementOf((EnumSet<E>) collection); 468 } 469 checkArgument( 470 !collection.isEmpty(), "collection is empty; use the other version of this method"); 471 Class<E> type = collection.iterator().next().getDeclaringClass(); 472 return makeComplementByHand(collection, type); 473 } 474 475 /** 476 * Creates an {@code EnumSet} consisting of all enum values that are not in the specified 477 * collection. This is equivalent to {@link EnumSet#complementOf}, but can act on any input 478 * collection, as long as the elements are of enum type. 479 * 480 * @param collection the collection whose complement should be stored in the {@code EnumSet} 481 * @param type the type of the elements in the set 482 * @return a new, modifiable {@code EnumSet} initially containing all the values of the enum not 483 * present in the given collection 484 */ 485 public static <E extends Enum<E>> EnumSet<E> complementOf( 486 Collection<E> collection, Class<E> type) { 487 checkNotNull(collection); 488 return (collection instanceof EnumSet) 489 ? EnumSet.complementOf((EnumSet<E>) collection) 490 : makeComplementByHand(collection, type); 491 } 492 493 private static <E extends Enum<E>> EnumSet<E> makeComplementByHand( 494 Collection<E> collection, Class<E> type) { 495 EnumSet<E> result = EnumSet.allOf(type); 496 result.removeAll(collection); 497 return result; 498 } 499 500 /** 501 * Returns a set backed by the specified map. The resulting set displays the same ordering, 502 * concurrency, and performance characteristics as the backing map. In essence, this factory 503 * method provides a {@link Set} implementation corresponding to any {@link Map} implementation. 504 * There is no need to use this method on a {@link Map} implementation that already has a 505 * corresponding {@link Set} implementation (such as {@link java.util.HashMap} or {@link 506 * java.util.TreeMap}). 507 * 508 * <p>Each method invocation on the set returned by this method results in exactly one method 509 * invocation on the backing map or its {@code keySet} view, with one exception. The {@code 510 * addAll} method is implemented as a sequence of {@code put} invocations on the backing map. 511 * 512 * <p>The specified map must be empty at the time this method is invoked, and should not be 513 * accessed directly after this method returns. These conditions are ensured if the map is created 514 * empty, passed directly to this method, and no reference to the map is retained, as illustrated 515 * in the following code fragment: 516 * 517 * <pre>{@code 518 * Set<Object> identityHashSet = Sets.newSetFromMap( 519 * new IdentityHashMap<Object, Boolean>()); 520 * }</pre> 521 * 522 * <p>The returned set is serializable if the backing map is. 523 * 524 * @param map the backing map 525 * @return the set backed by the map 526 * @throws IllegalArgumentException if {@code map} is not empty 527 * @deprecated Use {@link Collections#newSetFromMap} instead. 528 */ 529 @Deprecated 530 public static <E extends @Nullable Object> Set<E> newSetFromMap( 531 Map<E, Boolean> map) { 532 return Collections.newSetFromMap(map); 533 } 534 535 /** 536 * An unmodifiable view of a set which may be backed by other sets; this view will change as the 537 * backing sets do. Contains methods to copy the data into a new set which will then remain 538 * stable. There is usually no reason to retain a reference of type {@code SetView}; typically, 539 * you either use it as a plain {@link Set}, or immediately invoke {@link #immutableCopy} or 540 * {@link #copyInto} and forget the {@code SetView} itself. 541 * 542 * @since 2.0 543 */ 544 public abstract static class SetView<E extends @Nullable Object> extends AbstractSet<E> { 545 private SetView() {} // no subclasses but our own 546 547 /** 548 * Returns an immutable copy of the current contents of this set view. Does not support null 549 * elements. 550 * 551 * <p><b>Warning:</b> this may have unexpected results if a backing set of this view uses a 552 * nonstandard notion of equivalence, for example if it is a {@link TreeSet} using a comparator 553 * that is inconsistent with {@link Object#equals(Object)}. 554 */ 555 @SuppressWarnings("nullness") // Unsafe, but we can't fix it now. 556 public ImmutableSet<E> immutableCopy() { 557 return ImmutableSet.copyOf(this); 558 } 559 560 /** 561 * Copies the current contents of this set view into an existing set. This method has equivalent 562 * behavior to {@code set.addAll(this)}, assuming that all the sets involved are based on the 563 * same notion of equivalence. 564 * 565 * @return a reference to {@code set}, for convenience 566 */ 567 // Note: S should logically extend Set<? super E> but can't due to either 568 // some javac bug or some weirdness in the spec, not sure which. 569 @CanIgnoreReturnValue 570 public <S extends Set<E>> S copyInto(S set) { 571 set.addAll(this); 572 return set; 573 } 574 575 /** 576 * Guaranteed to throw an exception and leave the collection unmodified. 577 * 578 * @throws UnsupportedOperationException always 579 * @deprecated Unsupported operation. 580 */ 581 @CanIgnoreReturnValue 582 @Deprecated 583 @Override 584 @DoNotCall("Always throws UnsupportedOperationException") 585 public final boolean add(@ParametricNullness E e) { 586 throw new UnsupportedOperationException(); 587 } 588 589 /** 590 * Guaranteed to throw an exception and leave the collection unmodified. 591 * 592 * @throws UnsupportedOperationException always 593 * @deprecated Unsupported operation. 594 */ 595 @CanIgnoreReturnValue 596 @Deprecated 597 @Override 598 @DoNotCall("Always throws UnsupportedOperationException") 599 public final boolean remove(@CheckForNull Object object) { 600 throw new UnsupportedOperationException(); 601 } 602 603 /** 604 * Guaranteed to throw an exception and leave the collection unmodified. 605 * 606 * @throws UnsupportedOperationException always 607 * @deprecated Unsupported operation. 608 */ 609 @CanIgnoreReturnValue 610 @Deprecated 611 @Override 612 @DoNotCall("Always throws UnsupportedOperationException") 613 public final boolean addAll(Collection<? extends E> newElements) { 614 throw new UnsupportedOperationException(); 615 } 616 617 /** 618 * Guaranteed to throw an exception and leave the collection unmodified. 619 * 620 * @throws UnsupportedOperationException always 621 * @deprecated Unsupported operation. 622 */ 623 @CanIgnoreReturnValue 624 @Deprecated 625 @Override 626 @DoNotCall("Always throws UnsupportedOperationException") 627 public final boolean removeAll(Collection<?> oldElements) { 628 throw new UnsupportedOperationException(); 629 } 630 631 /** 632 * Guaranteed to throw an exception and leave the collection unmodified. 633 * 634 * @throws UnsupportedOperationException always 635 * @deprecated Unsupported operation. 636 */ 637 @CanIgnoreReturnValue 638 @Deprecated 639 @Override 640 @DoNotCall("Always throws UnsupportedOperationException") 641 public final boolean retainAll(Collection<?> elementsToKeep) { 642 throw new UnsupportedOperationException(); 643 } 644 645 /** 646 * Guaranteed to throw an exception and leave the collection unmodified. 647 * 648 * @throws UnsupportedOperationException always 649 * @deprecated Unsupported operation. 650 */ 651 @Deprecated 652 @Override 653 @DoNotCall("Always throws UnsupportedOperationException") 654 public final void clear() { 655 throw new UnsupportedOperationException(); 656 } 657 658 /** 659 * Scope the return type to {@link UnmodifiableIterator} to ensure this is an unmodifiable view. 660 * 661 * @since 20.0 (present with return type {@link Iterator} since 2.0) 662 */ 663 @Override 664 public abstract UnmodifiableIterator<E> iterator(); 665 } 666 667 /** 668 * Returns an unmodifiable <b>view</b> of the union of two sets. The returned set contains all 669 * elements that are contained in either backing set. Iterating over the returned set iterates 670 * first over all the elements of {@code set1}, then over each element of {@code set2}, in order, 671 * that is not contained in {@code set1}. 672 * 673 * <p>Results are undefined if {@code set1} and {@code set2} are sets based on different 674 * equivalence relations, for example if {@code set1} is a {@link HashSet} and {@code set2} is a 675 * {@link TreeSet} or the {@link Map#keySet} of an {@code IdentityHashMap}. 676 */ 677 public static <E extends @Nullable Object> SetView<E> union( 678 final Set<? extends E> set1, final Set<? extends E> set2) { 679 checkNotNull(set1, "set1"); 680 checkNotNull(set2, "set2"); 681 682 return new SetView<E>() { 683 @Override 684 public int size() { 685 int size = set1.size(); 686 for (E e : set2) { 687 if (!set1.contains(e)) { 688 size++; 689 } 690 } 691 return size; 692 } 693 694 @Override 695 public boolean isEmpty() { 696 return set1.isEmpty() && set2.isEmpty(); 697 } 698 699 @Override 700 public UnmodifiableIterator<E> iterator() { 701 return new AbstractIterator<E>() { 702 final Iterator<? extends E> itr1 = set1.iterator(); 703 final Iterator<? extends E> itr2 = set2.iterator(); 704 705 @Override 706 @CheckForNull 707 protected E computeNext() { 708 if (itr1.hasNext()) { 709 return itr1.next(); 710 } 711 while (itr2.hasNext()) { 712 E e = itr2.next(); 713 if (!set1.contains(e)) { 714 return e; 715 } 716 } 717 return endOfData(); 718 } 719 }; 720 } 721 722 @Override 723 public boolean contains(@CheckForNull Object object) { 724 return set1.contains(object) || set2.contains(object); 725 } 726 727 @Override 728 public <S extends Set<E>> S copyInto(S set) { 729 set.addAll(set1); 730 set.addAll(set2); 731 return set; 732 } 733 734 @Override 735 @SuppressWarnings("nullness") // see supertype 736 public ImmutableSet<E> immutableCopy() { 737 return new ImmutableSet.Builder<E>().addAll(set1).addAll(set2).build(); 738 } 739 }; 740 } 741 742 /** 743 * Returns an unmodifiable <b>view</b> of the intersection of two sets. The returned set contains 744 * all elements that are contained by both backing sets. The iteration order of the returned set 745 * matches that of {@code set1}. 746 * 747 * <p>Results are undefined if {@code set1} and {@code set2} are sets based on different 748 * equivalence relations, for example if {@code set1} is a {@link HashSet} and {@code set2} is a 749 * {@link TreeSet} or the {@link Map#keySet} of an {@code IdentityHashMap}. 750 * 751 * <p><b>Note:</b> The returned view performs slightly better when {@code set1} is the smaller of 752 * the two sets. If you have reason to believe one of your sets will generally be smaller than the 753 * other, pass it first. Unfortunately, since this method sets the generic type of the returned 754 * set based on the type of the first set passed, this could in rare cases force you to make a 755 * cast, for example: 756 * 757 * <pre>{@code 758 * Set<Object> aFewBadObjects = ... 759 * Set<String> manyBadStrings = ... 760 * 761 * // impossible for a non-String to be in the intersection 762 * SuppressWarnings("unchecked") 763 * Set<String> badStrings = (Set) Sets.intersection( 764 * aFewBadObjects, manyBadStrings); 765 * }</pre> 766 * 767 * <p>This is unfortunate, but should come up only very rarely. 768 */ 769 public static <E extends @Nullable Object> SetView<E> intersection( 770 final Set<E> set1, final Set<?> set2) { 771 checkNotNull(set1, "set1"); 772 checkNotNull(set2, "set2"); 773 774 return new SetView<E>() { 775 @Override 776 public UnmodifiableIterator<E> iterator() { 777 return new AbstractIterator<E>() { 778 final Iterator<E> itr = set1.iterator(); 779 780 @Override 781 @CheckForNull 782 protected E computeNext() { 783 while (itr.hasNext()) { 784 E e = itr.next(); 785 if (set2.contains(e)) { 786 return e; 787 } 788 } 789 return endOfData(); 790 } 791 }; 792 } 793 794 @Override 795 public int size() { 796 int size = 0; 797 for (E e : set1) { 798 if (set2.contains(e)) { 799 size++; 800 } 801 } 802 return size; 803 } 804 805 @Override 806 public boolean isEmpty() { 807 return Collections.disjoint(set2, set1); 808 } 809 810 @Override 811 public boolean contains(@CheckForNull Object object) { 812 return set1.contains(object) && set2.contains(object); 813 } 814 815 @Override 816 public boolean containsAll(Collection<?> collection) { 817 return set1.containsAll(collection) && set2.containsAll(collection); 818 } 819 }; 820 } 821 822 /** 823 * Returns an unmodifiable <b>view</b> of the difference of two sets. The returned set contains 824 * all elements that are contained by {@code set1} and not contained by {@code set2}. {@code set2} 825 * may also contain elements not present in {@code set1}; these are simply ignored. The iteration 826 * order of the returned set matches that of {@code set1}. 827 * 828 * <p>Results are undefined if {@code set1} and {@code set2} are sets based on different 829 * equivalence relations, for example if {@code set1} is a {@link HashSet} and {@code set2} is a 830 * {@link TreeSet} or the {@link Map#keySet} of an {@code IdentityHashMap}. 831 */ 832 public static <E extends @Nullable Object> SetView<E> difference( 833 final Set<E> set1, final Set<?> set2) { 834 checkNotNull(set1, "set1"); 835 checkNotNull(set2, "set2"); 836 837 return new SetView<E>() { 838 @Override 839 public UnmodifiableIterator<E> iterator() { 840 return new AbstractIterator<E>() { 841 final Iterator<E> itr = set1.iterator(); 842 843 @Override 844 @CheckForNull 845 protected E computeNext() { 846 while (itr.hasNext()) { 847 E e = itr.next(); 848 if (!set2.contains(e)) { 849 return e; 850 } 851 } 852 return endOfData(); 853 } 854 }; 855 } 856 857 @Override 858 public int size() { 859 int size = 0; 860 for (E e : set1) { 861 if (!set2.contains(e)) { 862 size++; 863 } 864 } 865 return size; 866 } 867 868 @Override 869 public boolean isEmpty() { 870 return set2.containsAll(set1); 871 } 872 873 @Override 874 public boolean contains(@CheckForNull Object element) { 875 return set1.contains(element) && !set2.contains(element); 876 } 877 }; 878 } 879 880 /** 881 * Returns an unmodifiable <b>view</b> of the symmetric difference of two sets. The returned set 882 * contains all elements that are contained in either {@code set1} or {@code set2} but not in 883 * both. The iteration order of the returned set is undefined. 884 * 885 * <p>Results are undefined if {@code set1} and {@code set2} are sets based on different 886 * equivalence relations, for example if {@code set1} is a {@link HashSet} and {@code set2} is a 887 * {@link TreeSet} or the {@link Map#keySet} of an {@code IdentityHashMap}. 888 * 889 * @since 3.0 890 */ 891 public static <E extends @Nullable Object> SetView<E> symmetricDifference( 892 final Set<? extends E> set1, final Set<? extends E> set2) { 893 checkNotNull(set1, "set1"); 894 checkNotNull(set2, "set2"); 895 896 return new SetView<E>() { 897 @Override 898 public UnmodifiableIterator<E> iterator() { 899 final Iterator<? extends E> itr1 = set1.iterator(); 900 final Iterator<? extends E> itr2 = set2.iterator(); 901 return new AbstractIterator<E>() { 902 @Override 903 @CheckForNull 904 public E computeNext() { 905 while (itr1.hasNext()) { 906 E elem1 = itr1.next(); 907 if (!set2.contains(elem1)) { 908 return elem1; 909 } 910 } 911 while (itr2.hasNext()) { 912 E elem2 = itr2.next(); 913 if (!set1.contains(elem2)) { 914 return elem2; 915 } 916 } 917 return endOfData(); 918 } 919 }; 920 } 921 922 @Override 923 public int size() { 924 int size = 0; 925 for (E e : set1) { 926 if (!set2.contains(e)) { 927 size++; 928 } 929 } 930 for (E e : set2) { 931 if (!set1.contains(e)) { 932 size++; 933 } 934 } 935 return size; 936 } 937 938 @Override 939 public boolean isEmpty() { 940 return set1.equals(set2); 941 } 942 943 @Override 944 public boolean contains(@CheckForNull Object element) { 945 return set1.contains(element) ^ set2.contains(element); 946 } 947 }; 948 } 949 950 /** 951 * Returns the elements of {@code unfiltered} that satisfy a predicate. The returned set is a live 952 * view of {@code unfiltered}; changes to one affect the other. 953 * 954 * <p>The resulting set's iterator does not support {@code remove()}, but all other set methods 955 * are supported. When given an element that doesn't satisfy the predicate, the set's {@code 956 * add()} and {@code addAll()} methods throw an {@link IllegalArgumentException}. When methods 957 * such as {@code removeAll()} and {@code clear()} are called on the filtered set, only elements 958 * that satisfy the filter will be removed from the underlying set. 959 * 960 * <p>The returned set isn't threadsafe or serializable, even if {@code unfiltered} is. 961 * 962 * <p>Many of the filtered set's methods, such as {@code size()}, iterate across every element in 963 * the underlying set and determine which elements satisfy the filter. When a live view is 964 * <i>not</i> needed, it may be faster to copy {@code Iterables.filter(unfiltered, predicate)} and 965 * use the copy. 966 * 967 * <p><b>Warning:</b> {@code predicate} must be <i>consistent with equals</i>, as documented at 968 * {@link Predicate#apply}. Do not provide a predicate such as {@code 969 * Predicates.instanceOf(ArrayList.class)}, which is inconsistent with equals. (See {@link 970 * Iterables#filter(Iterable, Class)} for related functionality.) 971 * 972 * <p><b>Java 8 users:</b> many use cases for this method are better addressed by {@link 973 * java.util.stream.Stream#filter}. This method is not being deprecated, but we gently encourage 974 * you to migrate to streams. 975 */ 976 // TODO(kevinb): how to omit that last sentence when building GWT javadoc? 977 public static <E extends @Nullable Object> Set<E> filter( 978 Set<E> unfiltered, Predicate<? super E> predicate) { 979 if (unfiltered instanceof SortedSet) { 980 return filter((SortedSet<E>) unfiltered, predicate); 981 } 982 if (unfiltered instanceof FilteredSet) { 983 // Support clear(), removeAll(), and retainAll() when filtering a filtered 984 // collection. 985 FilteredSet<E> filtered = (FilteredSet<E>) unfiltered; 986 Predicate<E> combinedPredicate = Predicates.<E>and(filtered.predicate, predicate); 987 return new FilteredSet<E>((Set<E>) filtered.unfiltered, combinedPredicate); 988 } 989 990 return new FilteredSet<E>(checkNotNull(unfiltered), checkNotNull(predicate)); 991 } 992 993 /** 994 * Returns the elements of a {@code SortedSet}, {@code unfiltered}, that satisfy a predicate. The 995 * returned set is a live view of {@code unfiltered}; changes to one affect the other. 996 * 997 * <p>The resulting set's iterator does not support {@code remove()}, but all other set methods 998 * are supported. When given an element that doesn't satisfy the predicate, the set's {@code 999 * add()} and {@code addAll()} methods throw an {@link IllegalArgumentException}. When methods 1000 * such as {@code removeAll()} and {@code clear()} are called on the filtered set, only elements 1001 * that satisfy the filter will be removed from the underlying set. 1002 * 1003 * <p>The returned set isn't threadsafe or serializable, even if {@code unfiltered} is. 1004 * 1005 * <p>Many of the filtered set's methods, such as {@code size()}, iterate across every element in 1006 * the underlying set and determine which elements satisfy the filter. When a live view is 1007 * <i>not</i> needed, it may be faster to copy {@code Iterables.filter(unfiltered, predicate)} and 1008 * use the copy. 1009 * 1010 * <p><b>Warning:</b> {@code predicate} must be <i>consistent with equals</i>, as documented at 1011 * {@link Predicate#apply}. Do not provide a predicate such as {@code 1012 * Predicates.instanceOf(ArrayList.class)}, which is inconsistent with equals. (See {@link 1013 * Iterables#filter(Iterable, Class)} for related functionality.) 1014 * 1015 * @since 11.0 1016 */ 1017 public static <E extends @Nullable Object> SortedSet<E> filter( 1018 SortedSet<E> unfiltered, Predicate<? super E> predicate) { 1019 if (unfiltered instanceof FilteredSet) { 1020 // Support clear(), removeAll(), and retainAll() when filtering a filtered 1021 // collection. 1022 FilteredSet<E> filtered = (FilteredSet<E>) unfiltered; 1023 Predicate<E> combinedPredicate = Predicates.<E>and(filtered.predicate, predicate); 1024 return new FilteredSortedSet<E>((SortedSet<E>) filtered.unfiltered, combinedPredicate); 1025 } 1026 1027 return new FilteredSortedSet<E>(checkNotNull(unfiltered), checkNotNull(predicate)); 1028 } 1029 1030 /** 1031 * Returns the elements of a {@code NavigableSet}, {@code unfiltered}, that satisfy a predicate. 1032 * The returned set is a live view of {@code unfiltered}; changes to one affect the other. 1033 * 1034 * <p>The resulting set's iterator does not support {@code remove()}, but all other set methods 1035 * are supported. When given an element that doesn't satisfy the predicate, the set's {@code 1036 * add()} and {@code addAll()} methods throw an {@link IllegalArgumentException}. When methods 1037 * such as {@code removeAll()} and {@code clear()} are called on the filtered set, only elements 1038 * that satisfy the filter will be removed from the underlying set. 1039 * 1040 * <p>The returned set isn't threadsafe or serializable, even if {@code unfiltered} is. 1041 * 1042 * <p>Many of the filtered set's methods, such as {@code size()}, iterate across every element in 1043 * the underlying set and determine which elements satisfy the filter. When a live view is 1044 * <i>not</i> needed, it may be faster to copy {@code Iterables.filter(unfiltered, predicate)} and 1045 * use the copy. 1046 * 1047 * <p><b>Warning:</b> {@code predicate} must be <i>consistent with equals</i>, as documented at 1048 * {@link Predicate#apply}. Do not provide a predicate such as {@code 1049 * Predicates.instanceOf(ArrayList.class)}, which is inconsistent with equals. (See {@link 1050 * Iterables#filter(Iterable, Class)} for related functionality.) 1051 * 1052 * @since 14.0 1053 */ 1054 @GwtIncompatible // NavigableSet 1055 @SuppressWarnings("unchecked") 1056 public static <E extends @Nullable Object> NavigableSet<E> filter( 1057 NavigableSet<E> unfiltered, Predicate<? super E> predicate) { 1058 if (unfiltered instanceof FilteredSet) { 1059 // Support clear(), removeAll(), and retainAll() when filtering a filtered 1060 // collection. 1061 FilteredSet<E> filtered = (FilteredSet<E>) unfiltered; 1062 Predicate<E> combinedPredicate = Predicates.<E>and(filtered.predicate, predicate); 1063 return new FilteredNavigableSet<E>((NavigableSet<E>) filtered.unfiltered, combinedPredicate); 1064 } 1065 1066 return new FilteredNavigableSet<E>(checkNotNull(unfiltered), checkNotNull(predicate)); 1067 } 1068 1069 private static class FilteredSet<E extends @Nullable Object> extends FilteredCollection<E> 1070 implements Set<E> { 1071 FilteredSet(Set<E> unfiltered, Predicate<? super E> predicate) { 1072 super(unfiltered, predicate); 1073 } 1074 1075 @Override 1076 public boolean equals(@CheckForNull Object object) { 1077 return equalsImpl(this, object); 1078 } 1079 1080 @Override 1081 public int hashCode() { 1082 return hashCodeImpl(this); 1083 } 1084 } 1085 1086 private static class FilteredSortedSet<E extends @Nullable Object> extends FilteredSet<E> 1087 implements SortedSet<E> { 1088 1089 FilteredSortedSet(SortedSet<E> unfiltered, Predicate<? super E> predicate) { 1090 super(unfiltered, predicate); 1091 } 1092 1093 @Override 1094 @CheckForNull 1095 public Comparator<? super E> comparator() { 1096 return ((SortedSet<E>) unfiltered).comparator(); 1097 } 1098 1099 @Override 1100 public SortedSet<E> subSet(@ParametricNullness E fromElement, @ParametricNullness E toElement) { 1101 return new FilteredSortedSet<E>( 1102 ((SortedSet<E>) unfiltered).subSet(fromElement, toElement), predicate); 1103 } 1104 1105 @Override 1106 public SortedSet<E> headSet(@ParametricNullness E toElement) { 1107 return new FilteredSortedSet<E>(((SortedSet<E>) unfiltered).headSet(toElement), predicate); 1108 } 1109 1110 @Override 1111 public SortedSet<E> tailSet(@ParametricNullness E fromElement) { 1112 return new FilteredSortedSet<E>(((SortedSet<E>) unfiltered).tailSet(fromElement), predicate); 1113 } 1114 1115 @Override 1116 @ParametricNullness 1117 public E first() { 1118 return Iterators.find(unfiltered.iterator(), predicate); 1119 } 1120 1121 @Override 1122 @ParametricNullness 1123 public E last() { 1124 SortedSet<E> sortedUnfiltered = (SortedSet<E>) unfiltered; 1125 while (true) { 1126 E element = sortedUnfiltered.last(); 1127 if (predicate.apply(element)) { 1128 return element; 1129 } 1130 sortedUnfiltered = sortedUnfiltered.headSet(element); 1131 } 1132 } 1133 } 1134 1135 @GwtIncompatible // NavigableSet 1136 private static class FilteredNavigableSet<E extends @Nullable Object> extends FilteredSortedSet<E> 1137 implements NavigableSet<E> { 1138 FilteredNavigableSet(NavigableSet<E> unfiltered, Predicate<? super E> predicate) { 1139 super(unfiltered, predicate); 1140 } 1141 1142 NavigableSet<E> unfiltered() { 1143 return (NavigableSet<E>) unfiltered; 1144 } 1145 1146 @Override 1147 @CheckForNull 1148 public E lower(@ParametricNullness E e) { 1149 return Iterators.find(unfiltered().headSet(e, false).descendingIterator(), predicate, null); 1150 } 1151 1152 @Override 1153 @CheckForNull 1154 public E floor(@ParametricNullness E e) { 1155 return Iterators.find(unfiltered().headSet(e, true).descendingIterator(), predicate, null); 1156 } 1157 1158 @Override 1159 @CheckForNull 1160 public E ceiling(@ParametricNullness E e) { 1161 return Iterables.find(unfiltered().tailSet(e, true), predicate, null); 1162 } 1163 1164 @Override 1165 @CheckForNull 1166 public E higher(@ParametricNullness E e) { 1167 return Iterables.find(unfiltered().tailSet(e, false), predicate, null); 1168 } 1169 1170 @Override 1171 @CheckForNull 1172 public E pollFirst() { 1173 return Iterables.removeFirstMatching(unfiltered(), predicate); 1174 } 1175 1176 @Override 1177 @CheckForNull 1178 public E pollLast() { 1179 return Iterables.removeFirstMatching(unfiltered().descendingSet(), predicate); 1180 } 1181 1182 @Override 1183 public NavigableSet<E> descendingSet() { 1184 return Sets.filter(unfiltered().descendingSet(), predicate); 1185 } 1186 1187 @Override 1188 public Iterator<E> descendingIterator() { 1189 return Iterators.filter(unfiltered().descendingIterator(), predicate); 1190 } 1191 1192 @Override 1193 @ParametricNullness 1194 public E last() { 1195 return Iterators.find(unfiltered().descendingIterator(), predicate); 1196 } 1197 1198 @Override 1199 public NavigableSet<E> subSet( 1200 @ParametricNullness E fromElement, 1201 boolean fromInclusive, 1202 @ParametricNullness E toElement, 1203 boolean toInclusive) { 1204 return filter( 1205 unfiltered().subSet(fromElement, fromInclusive, toElement, toInclusive), predicate); 1206 } 1207 1208 @Override 1209 public NavigableSet<E> headSet(@ParametricNullness E toElement, boolean inclusive) { 1210 return filter(unfiltered().headSet(toElement, inclusive), predicate); 1211 } 1212 1213 @Override 1214 public NavigableSet<E> tailSet(@ParametricNullness E fromElement, boolean inclusive) { 1215 return filter(unfiltered().tailSet(fromElement, inclusive), predicate); 1216 } 1217 } 1218 1219 /** 1220 * Returns every possible list that can be formed by choosing one element from each of the given 1221 * sets in order; the "n-ary <a href="http://en.wikipedia.org/wiki/Cartesian_product">Cartesian 1222 * product</a>" of the sets. For example: 1223 * 1224 * <pre>{@code 1225 * Sets.cartesianProduct(ImmutableList.of( 1226 * ImmutableSet.of(1, 2), 1227 * ImmutableSet.of("A", "B", "C"))) 1228 * }</pre> 1229 * 1230 * <p>returns a set containing six lists: 1231 * 1232 * <ul> 1233 * <li>{@code ImmutableList.of(1, "A")} 1234 * <li>{@code ImmutableList.of(1, "B")} 1235 * <li>{@code ImmutableList.of(1, "C")} 1236 * <li>{@code ImmutableList.of(2, "A")} 1237 * <li>{@code ImmutableList.of(2, "B")} 1238 * <li>{@code ImmutableList.of(2, "C")} 1239 * </ul> 1240 * 1241 * <p>The result is guaranteed to be in the "traditional", lexicographical order for Cartesian 1242 * products that you would get from nesting for loops: 1243 * 1244 * <pre>{@code 1245 * for (B b0 : sets.get(0)) { 1246 * for (B b1 : sets.get(1)) { 1247 * ... 1248 * ImmutableList<B> tuple = ImmutableList.of(b0, b1, ...); 1249 * // operate on tuple 1250 * } 1251 * } 1252 * }</pre> 1253 * 1254 * <p>Note that if any input set is empty, the Cartesian product will also be empty. If no sets at 1255 * all are provided (an empty list), the resulting Cartesian product has one element, an empty 1256 * list (counter-intuitive, but mathematically consistent). 1257 * 1258 * <p><i>Performance notes:</i> while the cartesian product of sets of size {@code m, n, p} is a 1259 * set of size {@code m x n x p}, its actual memory consumption is much smaller. When the 1260 * cartesian set is constructed, the input sets are merely copied. Only as the resulting set is 1261 * iterated are the individual lists created, and these are not retained after iteration. 1262 * 1263 * @param sets the sets to choose elements from, in the order that the elements chosen from those 1264 * sets should appear in the resulting lists 1265 * @param <B> any common base class shared by all axes (often just {@link Object}) 1266 * @return the Cartesian product, as an immutable set containing immutable lists 1267 * @throws NullPointerException if {@code sets}, any one of the {@code sets}, or any element of a 1268 * provided set is null 1269 * @throws IllegalArgumentException if the cartesian product size exceeds the {@code int} range 1270 * @since 2.0 1271 */ 1272 public static <B> Set<List<B>> cartesianProduct(List<? extends Set<? extends B>> sets) { 1273 return CartesianSet.create(sets); 1274 } 1275 1276 /** 1277 * Returns every possible list that can be formed by choosing one element from each of the given 1278 * sets in order; the "n-ary <a href="http://en.wikipedia.org/wiki/Cartesian_product">Cartesian 1279 * product</a>" of the sets. For example: 1280 * 1281 * <pre>{@code 1282 * Sets.cartesianProduct( 1283 * ImmutableSet.of(1, 2), 1284 * ImmutableSet.of("A", "B", "C")) 1285 * }</pre> 1286 * 1287 * <p>returns a set containing six lists: 1288 * 1289 * <ul> 1290 * <li>{@code ImmutableList.of(1, "A")} 1291 * <li>{@code ImmutableList.of(1, "B")} 1292 * <li>{@code ImmutableList.of(1, "C")} 1293 * <li>{@code ImmutableList.of(2, "A")} 1294 * <li>{@code ImmutableList.of(2, "B")} 1295 * <li>{@code ImmutableList.of(2, "C")} 1296 * </ul> 1297 * 1298 * <p>The result is guaranteed to be in the "traditional", lexicographical order for Cartesian 1299 * products that you would get from nesting for loops: 1300 * 1301 * <pre>{@code 1302 * for (B b0 : sets.get(0)) { 1303 * for (B b1 : sets.get(1)) { 1304 * ... 1305 * ImmutableList<B> tuple = ImmutableList.of(b0, b1, ...); 1306 * // operate on tuple 1307 * } 1308 * } 1309 * }</pre> 1310 * 1311 * <p>Note that if any input set is empty, the Cartesian product will also be empty. If no sets at 1312 * all are provided (an empty list), the resulting Cartesian product has one element, an empty 1313 * list (counter-intuitive, but mathematically consistent). 1314 * 1315 * <p><i>Performance notes:</i> while the cartesian product of sets of size {@code m, n, p} is a 1316 * set of size {@code m x n x p}, its actual memory consumption is much smaller. When the 1317 * cartesian set is constructed, the input sets are merely copied. Only as the resulting set is 1318 * iterated are the individual lists created, and these are not retained after iteration. 1319 * 1320 * @param sets the sets to choose elements from, in the order that the elements chosen from those 1321 * sets should appear in the resulting lists 1322 * @param <B> any common base class shared by all axes (often just {@link Object}) 1323 * @return the Cartesian product, as an immutable set containing immutable lists 1324 * @throws NullPointerException if {@code sets}, any one of the {@code sets}, or any element of a 1325 * provided set is null 1326 * @throws IllegalArgumentException if the cartesian product size exceeds the {@code int} range 1327 * @since 2.0 1328 */ 1329 @SafeVarargs 1330 public static <B> Set<List<B>> cartesianProduct(Set<? extends B>... sets) { 1331 return cartesianProduct(Arrays.asList(sets)); 1332 } 1333 1334 private static final class CartesianSet<E> extends ForwardingCollection<List<E>> 1335 implements Set<List<E>> { 1336 private final transient ImmutableList<ImmutableSet<E>> axes; 1337 private final transient CartesianList<E> delegate; 1338 1339 static <E> Set<List<E>> create(List<? extends Set<? extends E>> sets) { 1340 ImmutableList.Builder<ImmutableSet<E>> axesBuilder = new ImmutableList.Builder<>(sets.size()); 1341 for (Set<? extends E> set : sets) { 1342 ImmutableSet<E> copy = ImmutableSet.copyOf(set); 1343 if (copy.isEmpty()) { 1344 return ImmutableSet.of(); 1345 } 1346 axesBuilder.add(copy); 1347 } 1348 final ImmutableList<ImmutableSet<E>> axes = axesBuilder.build(); 1349 ImmutableList<List<E>> listAxes = 1350 new ImmutableList<List<E>>() { 1351 @Override 1352 public int size() { 1353 return axes.size(); 1354 } 1355 1356 @Override 1357 public List<E> get(int index) { 1358 return axes.get(index).asList(); 1359 } 1360 1361 @Override 1362 boolean isPartialView() { 1363 return true; 1364 } 1365 }; 1366 return new CartesianSet<E>(axes, new CartesianList<E>(listAxes)); 1367 } 1368 1369 private CartesianSet(ImmutableList<ImmutableSet<E>> axes, CartesianList<E> delegate) { 1370 this.axes = axes; 1371 this.delegate = delegate; 1372 } 1373 1374 @Override 1375 protected Collection<List<E>> delegate() { 1376 return delegate; 1377 } 1378 1379 @Override 1380 public boolean contains(@CheckForNull Object object) { 1381 if (!(object instanceof List)) { 1382 return false; 1383 } 1384 List<?> list = (List<?>) object; 1385 if (list.size() != axes.size()) { 1386 return false; 1387 } 1388 int i = 0; 1389 for (Object o : list) { 1390 if (!axes.get(i).contains(o)) { 1391 return false; 1392 } 1393 i++; 1394 } 1395 return true; 1396 } 1397 1398 @Override 1399 public boolean equals(@CheckForNull Object object) { 1400 // Warning: this is broken if size() == 0, so it is critical that we 1401 // substitute an empty ImmutableSet to the user in place of this 1402 if (object instanceof CartesianSet) { 1403 CartesianSet<?> that = (CartesianSet<?>) object; 1404 return this.axes.equals(that.axes); 1405 } 1406 return super.equals(object); 1407 } 1408 1409 @Override 1410 public int hashCode() { 1411 // Warning: this is broken if size() == 0, so it is critical that we 1412 // substitute an empty ImmutableSet to the user in place of this 1413 1414 // It's a weird formula, but tests prove it works. 1415 int adjust = size() - 1; 1416 for (int i = 0; i < axes.size(); i++) { 1417 adjust *= 31; 1418 adjust = ~~adjust; 1419 // in GWT, we have to deal with integer overflow carefully 1420 } 1421 int hash = 1; 1422 for (Set<E> axis : axes) { 1423 hash = 31 * hash + (size() / axis.size() * axis.hashCode()); 1424 1425 hash = ~~hash; 1426 } 1427 hash += adjust; 1428 return ~~hash; 1429 } 1430 } 1431 1432 /** 1433 * Returns the set of all possible subsets of {@code set}. For example, {@code 1434 * powerSet(ImmutableSet.of(1, 2))} returns the set {@code {{}, {1}, {2}, {1, 2}}}. 1435 * 1436 * <p>Elements appear in these subsets in the same iteration order as they appeared in the input 1437 * set. The order in which these subsets appear in the outer set is undefined. Note that the power 1438 * set of the empty set is not the empty set, but a one-element set containing the empty set. 1439 * 1440 * <p>The returned set and its constituent sets use {@code equals} to decide whether two elements 1441 * are identical, even if the input set uses a different concept of equivalence. 1442 * 1443 * <p><i>Performance notes:</i> while the power set of a set with size {@code n} is of size {@code 1444 * 2^n}, its memory usage is only {@code O(n)}. When the power set is constructed, the input set 1445 * is merely copied. Only as the power set is iterated are the individual subsets created, and 1446 * these subsets themselves occupy only a small constant amount of memory. 1447 * 1448 * @param set the set of elements to construct a power set from 1449 * @return the power set, as an immutable set of immutable sets 1450 * @throws IllegalArgumentException if {@code set} has more than 30 unique elements (causing the 1451 * power set size to exceed the {@code int} range) 1452 * @throws NullPointerException if {@code set} is or contains {@code null} 1453 * @see <a href="http://en.wikipedia.org/wiki/Power_set">Power set article at Wikipedia</a> 1454 * @since 4.0 1455 */ 1456 @GwtCompatible(serializable = false) 1457 public static <E> Set<Set<E>> powerSet(Set<E> set) { 1458 return new PowerSet<E>(set); 1459 } 1460 1461 private static final class SubSet<E> extends AbstractSet<E> { 1462 private final ImmutableMap<E, Integer> inputSet; 1463 private final int mask; 1464 1465 SubSet(ImmutableMap<E, Integer> inputSet, int mask) { 1466 this.inputSet = inputSet; 1467 this.mask = mask; 1468 } 1469 1470 @Override 1471 public Iterator<E> iterator() { 1472 return new UnmodifiableIterator<E>() { 1473 final ImmutableList<E> elements = inputSet.keySet().asList(); 1474 int remainingSetBits = mask; 1475 1476 @Override 1477 public boolean hasNext() { 1478 return remainingSetBits != 0; 1479 } 1480 1481 @Override 1482 public E next() { 1483 int index = Integer.numberOfTrailingZeros(remainingSetBits); 1484 if (index == 32) { 1485 throw new NoSuchElementException(); 1486 } 1487 remainingSetBits &= ~(1 << index); 1488 return elements.get(index); 1489 } 1490 }; 1491 } 1492 1493 @Override 1494 public int size() { 1495 return Integer.bitCount(mask); 1496 } 1497 1498 @Override 1499 public boolean contains(@CheckForNull Object o) { 1500 Integer index = inputSet.get(o); 1501 return index != null && (mask & (1 << index)) != 0; 1502 } 1503 } 1504 1505 private static final class PowerSet<E> extends AbstractSet<Set<E>> { 1506 final ImmutableMap<E, Integer> inputSet; 1507 1508 PowerSet(Set<E> input) { 1509 checkArgument( 1510 input.size() <= 30, "Too many elements to create power set: %s > 30", input.size()); 1511 this.inputSet = Maps.indexMap(input); 1512 } 1513 1514 @Override 1515 public int size() { 1516 return 1 << inputSet.size(); 1517 } 1518 1519 @Override 1520 public boolean isEmpty() { 1521 return false; 1522 } 1523 1524 @Override 1525 public Iterator<Set<E>> iterator() { 1526 return new AbstractIndexedListIterator<Set<E>>(size()) { 1527 @Override 1528 protected Set<E> get(final int setBits) { 1529 return new SubSet<E>(inputSet, setBits); 1530 } 1531 }; 1532 } 1533 1534 @Override 1535 public boolean contains(@CheckForNull Object obj) { 1536 if (obj instanceof Set) { 1537 Set<?> set = (Set<?>) obj; 1538 return inputSet.keySet().containsAll(set); 1539 } 1540 return false; 1541 } 1542 1543 @Override 1544 public boolean equals(@CheckForNull Object obj) { 1545 if (obj instanceof PowerSet) { 1546 PowerSet<?> that = (PowerSet<?>) obj; 1547 return inputSet.keySet().equals(that.inputSet.keySet()); 1548 } 1549 return super.equals(obj); 1550 } 1551 1552 @Override 1553 public int hashCode() { 1554 /* 1555 * The sum of the sums of the hash codes in each subset is just the sum of 1556 * each input element's hash code times the number of sets that element 1557 * appears in. Each element appears in exactly half of the 2^n sets, so: 1558 */ 1559 return inputSet.keySet().hashCode() << (inputSet.size() - 1); 1560 } 1561 1562 @Override 1563 public String toString() { 1564 return "powerSet(" + inputSet + ")"; 1565 } 1566 } 1567 1568 /** 1569 * Returns the set of all subsets of {@code set} of size {@code size}. For example, {@code 1570 * combinations(ImmutableSet.of(1, 2, 3), 2)} returns the set {@code {{1, 2}, {1, 3}, {2, 3}}}. 1571 * 1572 * <p>Elements appear in these subsets in the same iteration order as they appeared in the input 1573 * set. The order in which these subsets appear in the outer set is undefined. 1574 * 1575 * <p>The returned set and its constituent sets use {@code equals} to decide whether two elements 1576 * are identical, even if the input set uses a different concept of equivalence. 1577 * 1578 * <p><i>Performance notes:</i> the memory usage of the returned set is only {@code O(n)}. When 1579 * the result set is constructed, the input set is merely copied. Only as the result set is 1580 * iterated are the individual subsets created. Each of these subsets occupies an additional O(n) 1581 * memory but only for as long as the user retains a reference to it. That is, the set returned by 1582 * {@code combinations} does not retain the individual subsets. 1583 * 1584 * @param set the set of elements to take combinations of 1585 * @param size the number of elements per combination 1586 * @return the set of all combinations of {@code size} elements from {@code set} 1587 * @throws IllegalArgumentException if {@code size} is not between 0 and {@code set.size()} 1588 * inclusive 1589 * @throws NullPointerException if {@code set} is or contains {@code null} 1590 * @since 23.0 1591 */ 1592 @Beta 1593 public static <E> Set<Set<E>> combinations(Set<E> set, final int size) { 1594 final ImmutableMap<E, Integer> index = Maps.indexMap(set); 1595 checkNonnegative(size, "size"); 1596 checkArgument(size <= index.size(), "size (%s) must be <= set.size() (%s)", size, index.size()); 1597 if (size == 0) { 1598 return ImmutableSet.<Set<E>>of(ImmutableSet.<E>of()); 1599 } else if (size == index.size()) { 1600 return ImmutableSet.<Set<E>>of(index.keySet()); 1601 } 1602 return new AbstractSet<Set<E>>() { 1603 @Override 1604 public boolean contains(@CheckForNull Object o) { 1605 if (o instanceof Set) { 1606 Set<?> s = (Set<?>) o; 1607 return s.size() == size && index.keySet().containsAll(s); 1608 } 1609 return false; 1610 } 1611 1612 @Override 1613 public Iterator<Set<E>> iterator() { 1614 return new AbstractIterator<Set<E>>() { 1615 final BitSet bits = new BitSet(index.size()); 1616 1617 @Override 1618 @CheckForNull 1619 protected Set<E> computeNext() { 1620 if (bits.isEmpty()) { 1621 bits.set(0, size); 1622 } else { 1623 int firstSetBit = bits.nextSetBit(0); 1624 int bitToFlip = bits.nextClearBit(firstSetBit); 1625 1626 if (bitToFlip == index.size()) { 1627 return endOfData(); 1628 } 1629 /* 1630 * The current set in sorted order looks like 1631 * {firstSetBit, firstSetBit + 1, ..., bitToFlip - 1, ...} 1632 * where it does *not* contain bitToFlip. 1633 * 1634 * The next combination is 1635 * 1636 * {0, 1, ..., bitToFlip - firstSetBit - 2, bitToFlip, ...} 1637 * 1638 * This is lexicographically next if you look at the combinations in descending order 1639 * e.g. {2, 1, 0}, {3, 1, 0}, {3, 2, 0}, {3, 2, 1}, {4, 1, 0}... 1640 */ 1641 1642 bits.set(0, bitToFlip - firstSetBit - 1); 1643 bits.clear(bitToFlip - firstSetBit - 1, bitToFlip); 1644 bits.set(bitToFlip); 1645 } 1646 final BitSet copy = (BitSet) bits.clone(); 1647 return new AbstractSet<E>() { 1648 @Override 1649 public boolean contains(@CheckForNull Object o) { 1650 Integer i = index.get(o); 1651 return i != null && copy.get(i); 1652 } 1653 1654 @Override 1655 public Iterator<E> iterator() { 1656 return new AbstractIterator<E>() { 1657 int i = -1; 1658 1659 @Override 1660 @CheckForNull 1661 protected E computeNext() { 1662 i = copy.nextSetBit(i + 1); 1663 if (i == -1) { 1664 return endOfData(); 1665 } 1666 return index.keySet().asList().get(i); 1667 } 1668 }; 1669 } 1670 1671 @Override 1672 public int size() { 1673 return size; 1674 } 1675 }; 1676 } 1677 }; 1678 } 1679 1680 @Override 1681 public int size() { 1682 return IntMath.binomial(index.size(), size); 1683 } 1684 1685 @Override 1686 public String toString() { 1687 return "Sets.combinations(" + index.keySet() + ", " + size + ")"; 1688 } 1689 }; 1690 } 1691 1692 /** An implementation for {@link Set#hashCode()}. */ 1693 static int hashCodeImpl(Set<?> s) { 1694 int hashCode = 0; 1695 for (Object o : s) { 1696 hashCode += o != null ? o.hashCode() : 0; 1697 1698 hashCode = ~~hashCode; 1699 // Needed to deal with unusual integer overflow in GWT. 1700 } 1701 return hashCode; 1702 } 1703 1704 /** An implementation for {@link Set#equals(Object)}. */ 1705 static boolean equalsImpl(Set<?> s, @CheckForNull Object object) { 1706 if (s == object) { 1707 return true; 1708 } 1709 if (object instanceof Set) { 1710 Set<?> o = (Set<?>) object; 1711 1712 try { 1713 return s.size() == o.size() && s.containsAll(o); 1714 } catch (NullPointerException | ClassCastException ignored) { 1715 return false; 1716 } 1717 } 1718 return false; 1719 } 1720 1721 /** 1722 * Returns an unmodifiable view of the specified navigable set. This method allows modules to 1723 * provide users with "read-only" access to internal navigable sets. Query operations on the 1724 * returned set "read through" to the specified set, and attempts to modify the returned set, 1725 * whether direct or via its collection views, result in an {@code UnsupportedOperationException}. 1726 * 1727 * <p>The returned navigable set will be serializable if the specified navigable set is 1728 * serializable. 1729 * 1730 * @param set the navigable set for which an unmodifiable view is to be returned 1731 * @return an unmodifiable view of the specified navigable set 1732 * @since 12.0 1733 */ 1734 public static <E extends @Nullable Object> NavigableSet<E> unmodifiableNavigableSet( 1735 NavigableSet<E> set) { 1736 if (set instanceof ImmutableCollection || set instanceof UnmodifiableNavigableSet) { 1737 return set; 1738 } 1739 return new UnmodifiableNavigableSet<E>(set); 1740 } 1741 1742 static final class UnmodifiableNavigableSet<E extends @Nullable Object> 1743 extends ForwardingSortedSet<E> implements NavigableSet<E>, Serializable { 1744 private final NavigableSet<E> delegate; 1745 private final SortedSet<E> unmodifiableDelegate; 1746 1747 UnmodifiableNavigableSet(NavigableSet<E> delegate) { 1748 this.delegate = checkNotNull(delegate); 1749 this.unmodifiableDelegate = Collections.unmodifiableSortedSet(delegate); 1750 } 1751 1752 @Override 1753 protected SortedSet<E> delegate() { 1754 return unmodifiableDelegate; 1755 } 1756 1757 @Override 1758 @CheckForNull 1759 public E lower(@ParametricNullness E e) { 1760 return delegate.lower(e); 1761 } 1762 1763 @Override 1764 @CheckForNull 1765 public E floor(@ParametricNullness E e) { 1766 return delegate.floor(e); 1767 } 1768 1769 @Override 1770 @CheckForNull 1771 public E ceiling(@ParametricNullness E e) { 1772 return delegate.ceiling(e); 1773 } 1774 1775 @Override 1776 @CheckForNull 1777 public E higher(@ParametricNullness E e) { 1778 return delegate.higher(e); 1779 } 1780 1781 @Override 1782 @CheckForNull 1783 public E pollFirst() { 1784 throw new UnsupportedOperationException(); 1785 } 1786 1787 @Override 1788 @CheckForNull 1789 public E pollLast() { 1790 throw new UnsupportedOperationException(); 1791 } 1792 1793 @CheckForNull private transient UnmodifiableNavigableSet<E> descendingSet; 1794 1795 @Override 1796 public NavigableSet<E> descendingSet() { 1797 UnmodifiableNavigableSet<E> result = descendingSet; 1798 if (result == null) { 1799 result = descendingSet = new UnmodifiableNavigableSet<E>(delegate.descendingSet()); 1800 result.descendingSet = this; 1801 } 1802 return result; 1803 } 1804 1805 @Override 1806 public Iterator<E> descendingIterator() { 1807 return Iterators.unmodifiableIterator(delegate.descendingIterator()); 1808 } 1809 1810 @Override 1811 public NavigableSet<E> subSet( 1812 @ParametricNullness E fromElement, 1813 boolean fromInclusive, 1814 @ParametricNullness E toElement, 1815 boolean toInclusive) { 1816 return unmodifiableNavigableSet( 1817 delegate.subSet(fromElement, fromInclusive, toElement, toInclusive)); 1818 } 1819 1820 @Override 1821 public NavigableSet<E> headSet(@ParametricNullness E toElement, boolean inclusive) { 1822 return unmodifiableNavigableSet(delegate.headSet(toElement, inclusive)); 1823 } 1824 1825 @Override 1826 public NavigableSet<E> tailSet(@ParametricNullness E fromElement, boolean inclusive) { 1827 return unmodifiableNavigableSet(delegate.tailSet(fromElement, inclusive)); 1828 } 1829 1830 private static final long serialVersionUID = 0; 1831 } 1832 1833 /** 1834 * Returns a synchronized (thread-safe) navigable set backed by the specified navigable set. In 1835 * order to guarantee serial access, it is critical that <b>all</b> access to the backing 1836 * navigable set is accomplished through the returned navigable set (or its views). 1837 * 1838 * <p>It is imperative that the user manually synchronize on the returned sorted set when 1839 * iterating over it or any of its {@code descendingSet}, {@code subSet}, {@code headSet}, or 1840 * {@code tailSet} views. 1841 * 1842 * <pre>{@code 1843 * NavigableSet<E> set = synchronizedNavigableSet(new TreeSet<E>()); 1844 * ... 1845 * synchronized (set) { 1846 * // Must be in the synchronized block 1847 * Iterator<E> it = set.iterator(); 1848 * while (it.hasNext()) { 1849 * foo(it.next()); 1850 * } 1851 * } 1852 * }</pre> 1853 * 1854 * <p>or: 1855 * 1856 * <pre>{@code 1857 * NavigableSet<E> set = synchronizedNavigableSet(new TreeSet<E>()); 1858 * NavigableSet<E> set2 = set.descendingSet().headSet(foo); 1859 * ... 1860 * synchronized (set) { // Note: set, not set2!!! 1861 * // Must be in the synchronized block 1862 * Iterator<E> it = set2.descendingIterator(); 1863 * while (it.hasNext()) 1864 * foo(it.next()); 1865 * } 1866 * } 1867 * }</pre> 1868 * 1869 * <p>Failure to follow this advice may result in non-deterministic behavior. 1870 * 1871 * <p>The returned navigable set will be serializable if the specified navigable set is 1872 * serializable. 1873 * 1874 * @param navigableSet the navigable set to be "wrapped" in a synchronized navigable set. 1875 * @return a synchronized view of the specified navigable set. 1876 * @since 13.0 1877 */ 1878 @GwtIncompatible // NavigableSet 1879 public static <E extends @Nullable Object> NavigableSet<E> synchronizedNavigableSet( 1880 NavigableSet<E> navigableSet) { 1881 return Synchronized.navigableSet(navigableSet); 1882 } 1883 1884 /** Remove each element in an iterable from a set. */ 1885 static boolean removeAllImpl(Set<?> set, Iterator<?> iterator) { 1886 boolean changed = false; 1887 while (iterator.hasNext()) { 1888 changed |= set.remove(iterator.next()); 1889 } 1890 return changed; 1891 } 1892 1893 static boolean removeAllImpl(Set<?> set, Collection<?> collection) { 1894 checkNotNull(collection); // for GWT 1895 if (collection instanceof Multiset) { 1896 collection = ((Multiset<?>) collection).elementSet(); 1897 } 1898 /* 1899 * AbstractSet.removeAll(List) has quadratic behavior if the list size 1900 * is just more than the set's size. We augment the test by 1901 * assuming that sets have fast contains() performance, and other 1902 * collections don't. See 1903 * http://code.google.com/p/guava-libraries/issues/detail?id=1013 1904 */ 1905 if (collection instanceof Set && collection.size() > set.size()) { 1906 return Iterators.removeAll(set.iterator(), collection); 1907 } else { 1908 return removeAllImpl(set, collection.iterator()); 1909 } 1910 } 1911 1912 @GwtIncompatible // NavigableSet 1913 static class DescendingSet<E extends @Nullable Object> extends ForwardingNavigableSet<E> { 1914 private final NavigableSet<E> forward; 1915 1916 DescendingSet(NavigableSet<E> forward) { 1917 this.forward = forward; 1918 } 1919 1920 @Override 1921 protected NavigableSet<E> delegate() { 1922 return forward; 1923 } 1924 1925 @Override 1926 @CheckForNull 1927 public E lower(@ParametricNullness E e) { 1928 return forward.higher(e); 1929 } 1930 1931 @Override 1932 @CheckForNull 1933 public E floor(@ParametricNullness E e) { 1934 return forward.ceiling(e); 1935 } 1936 1937 @Override 1938 @CheckForNull 1939 public E ceiling(@ParametricNullness E e) { 1940 return forward.floor(e); 1941 } 1942 1943 @Override 1944 @CheckForNull 1945 public E higher(@ParametricNullness E e) { 1946 return forward.lower(e); 1947 } 1948 1949 @Override 1950 @CheckForNull 1951 public E pollFirst() { 1952 return forward.pollLast(); 1953 } 1954 1955 @Override 1956 @CheckForNull 1957 public E pollLast() { 1958 return forward.pollFirst(); 1959 } 1960 1961 @Override 1962 public NavigableSet<E> descendingSet() { 1963 return forward; 1964 } 1965 1966 @Override 1967 public Iterator<E> descendingIterator() { 1968 return forward.iterator(); 1969 } 1970 1971 @Override 1972 public NavigableSet<E> subSet( 1973 @ParametricNullness E fromElement, 1974 boolean fromInclusive, 1975 @ParametricNullness E toElement, 1976 boolean toInclusive) { 1977 return forward.subSet(toElement, toInclusive, fromElement, fromInclusive).descendingSet(); 1978 } 1979 1980 @Override 1981 public SortedSet<E> subSet(@ParametricNullness E fromElement, @ParametricNullness E toElement) { 1982 return standardSubSet(fromElement, toElement); 1983 } 1984 1985 @Override 1986 public NavigableSet<E> headSet(@ParametricNullness E toElement, boolean inclusive) { 1987 return forward.tailSet(toElement, inclusive).descendingSet(); 1988 } 1989 1990 @Override 1991 public SortedSet<E> headSet(@ParametricNullness E toElement) { 1992 return standardHeadSet(toElement); 1993 } 1994 1995 @Override 1996 public NavigableSet<E> tailSet(@ParametricNullness E fromElement, boolean inclusive) { 1997 return forward.headSet(fromElement, inclusive).descendingSet(); 1998 } 1999 2000 @Override 2001 public SortedSet<E> tailSet(@ParametricNullness E fromElement) { 2002 return standardTailSet(fromElement); 2003 } 2004 2005 @SuppressWarnings("unchecked") 2006 @Override 2007 public Comparator<? super E> comparator() { 2008 Comparator<? super E> forwardComparator = forward.comparator(); 2009 if (forwardComparator == null) { 2010 return (Comparator) Ordering.natural().reverse(); 2011 } else { 2012 return reverse(forwardComparator); 2013 } 2014 } 2015 2016 // If we inline this, we get a javac error. 2017 private static <T extends @Nullable Object> Ordering<T> reverse(Comparator<T> forward) { 2018 return Ordering.from(forward).reverse(); 2019 } 2020 2021 @Override 2022 @ParametricNullness 2023 public E first() { 2024 return forward.last(); 2025 } 2026 2027 @Override 2028 @ParametricNullness 2029 public E last() { 2030 return forward.first(); 2031 } 2032 2033 @Override 2034 public Iterator<E> iterator() { 2035 return forward.descendingIterator(); 2036 } 2037 2038 @Override 2039 public @Nullable Object[] toArray() { 2040 return standardToArray(); 2041 } 2042 2043 @Override 2044 @SuppressWarnings("nullness") // b/192354773 in our checker affects toArray declarations 2045 public <T extends @Nullable Object> T[] toArray(T[] array) { 2046 return standardToArray(array); 2047 } 2048 2049 @Override 2050 public String toString() { 2051 return standardToString(); 2052 } 2053 } 2054 2055 /** 2056 * Returns a view of the portion of {@code set} whose elements are contained by {@code range}. 2057 * 2058 * <p>This method delegates to the appropriate methods of {@link NavigableSet} (namely {@link 2059 * NavigableSet#subSet(Object, boolean, Object, boolean) subSet()}, {@link 2060 * NavigableSet#tailSet(Object, boolean) tailSet()}, and {@link NavigableSet#headSet(Object, 2061 * boolean) headSet()}) to actually construct the view. Consult these methods for a full 2062 * description of the returned view's behavior. 2063 * 2064 * <p><b>Warning:</b> {@code Range}s always represent a range of values using the values' natural 2065 * ordering. {@code NavigableSet} on the other hand can specify a custom ordering via a {@link 2066 * Comparator}, which can violate the natural ordering. Using this method (or in general using 2067 * {@code Range}) with unnaturally-ordered sets can lead to unexpected and undefined behavior. 2068 * 2069 * @since 20.0 2070 */ 2071 @Beta 2072 @GwtIncompatible // NavigableSet 2073 public static <K extends Comparable<? super K>> NavigableSet<K> subSet( 2074 NavigableSet<K> set, Range<K> range) { 2075 if (set.comparator() != null 2076 && set.comparator() != Ordering.natural() 2077 && range.hasLowerBound() 2078 && range.hasUpperBound()) { 2079 checkArgument( 2080 set.comparator().compare(range.lowerEndpoint(), range.upperEndpoint()) <= 0, 2081 "set is using a custom comparator which is inconsistent with the natural ordering."); 2082 } 2083 if (range.hasLowerBound() && range.hasUpperBound()) { 2084 return set.subSet( 2085 range.lowerEndpoint(), 2086 range.lowerBoundType() == BoundType.CLOSED, 2087 range.upperEndpoint(), 2088 range.upperBoundType() == BoundType.CLOSED); 2089 } else if (range.hasLowerBound()) { 2090 return set.tailSet(range.lowerEndpoint(), range.lowerBoundType() == BoundType.CLOSED); 2091 } else if (range.hasUpperBound()) { 2092 return set.headSet(range.upperEndpoint(), range.upperBoundType() == BoundType.CLOSED); 2093 } 2094 return checkNotNull(set); 2095 } 2096}