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