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