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