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