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