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