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