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