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
017 package com.google.common.collect;
018
019 import static com.google.common.base.Preconditions.checkArgument;
020 import static com.google.common.base.Preconditions.checkNotNull;
021
022 import com.google.common.annotations.Beta;
023 import com.google.common.annotations.GwtCompatible;
024 import com.google.common.annotations.GwtIncompatible;
025 import com.google.common.base.Predicate;
026 import com.google.common.base.Predicates;
027 import com.google.common.collect.Collections2.FilteredCollection;
028 import com.google.common.math.IntMath;
029
030 import java.io.IOException;
031 import java.io.ObjectInputStream;
032 import java.io.Serializable;
033 import java.util.AbstractSet;
034 import java.util.Arrays;
035 import java.util.Collection;
036 import java.util.Collections;
037 import java.util.Comparator;
038 import java.util.EnumSet;
039 import java.util.HashSet;
040 import java.util.Iterator;
041 import java.util.LinkedHashSet;
042 import java.util.List;
043 import java.util.Map;
044 import java.util.NavigableSet;
045 import java.util.NoSuchElementException;
046 import java.util.Set;
047 import java.util.SortedSet;
048 import java.util.TreeSet;
049 import java.util.concurrent.CopyOnWriteArraySet;
050
051 import javax.annotation.Nullable;
052
053 /**
054 * Static utility methods pertaining to {@link Set} instances. Also see this
055 * class's counterparts {@link Lists} and {@link Maps}.
056 *
057 * <p>See the Guava User Guide article on <a href=
058 * "http://code.google.com/p/guava-libraries/wiki/CollectionUtilitiesExplained#Sets">
059 * {@code Sets}</a>.
060 *
061 * @author Kevin Bourrillion
062 * @author Jared Levy
063 * @author Chris Povirk
064 * @since 2.0 (imported from Google Collections Library)
065 */
066 @GwtCompatible(emulated = true)
067 public final class Sets {
068 private Sets() {}
069
070 /**
071 * Returns an immutable set instance containing the given enum elements.
072 * Internally, the returned set will be backed by an {@link EnumSet}.
073 *
074 * <p>The iteration order of the returned set follows the enum's iteration
075 * order, not the order in which the elements are provided to the method.
076 *
077 * @param anElement one of the elements the set should contain
078 * @param otherElements the rest of the elements the set should contain
079 * @return an immutable set containing those elements, minus duplicates
080 */
081 // http://code.google.com/p/google-web-toolkit/issues/detail?id=3028
082 @GwtCompatible(serializable = true)
083 public static <E extends Enum<E>> ImmutableSet<E> immutableEnumSet(
084 E anElement, E... otherElements) {
085 return new ImmutableEnumSet<E>(EnumSet.of(anElement, otherElements));
086 }
087
088 /**
089 * Returns an immutable set instance containing the given enum elements.
090 * Internally, the returned set will be backed by an {@link EnumSet}.
091 *
092 * <p>The iteration order of the returned set follows the enum's iteration
093 * order, not the order in which the elements appear in the given collection.
094 *
095 * @param elements the elements, all of the same {@code enum} type, that the
096 * set should contain
097 * @return an immutable set containing those elements, minus duplicates
098 */
099 // 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 Iterable<E> elements) {
103 Iterator<E> iterator = elements.iterator();
104 if (!iterator.hasNext()) {
105 return ImmutableSet.of();
106 }
107 if (elements instanceof EnumSet) {
108 EnumSet<E> enumSetClone = EnumSet.copyOf((EnumSet<E>) elements);
109 return new ImmutableEnumSet<E>(enumSetClone);
110 }
111 E first = iterator.next();
112 EnumSet<E> set = EnumSet.of(first);
113 while (iterator.hasNext()) {
114 set.add(iterator.next());
115 }
116 return new ImmutableEnumSet<E>(set);
117 }
118
119 /**
120 * Returns a new {@code EnumSet} instance containing the given elements.
121 * Unlike {@link EnumSet#copyOf(Collection)}, this method does not produce an
122 * exception on an empty collection, and it may be called on any iterable, not
123 * just a {@code Collection}.
124 */
125 public static <E extends Enum<E>> EnumSet<E> newEnumSet(Iterable<E> iterable,
126 Class<E> elementType) {
127 /*
128 * TODO(cpovirk): noneOf() and addAll() will both throw
129 * NullPointerExceptions when appropriate. However, NullPointerTester will
130 * fail on this method because it passes in Class.class instead of an enum
131 * type. This means that, when iterable is null but elementType is not,
132 * noneOf() will throw a ClassCastException before addAll() has a chance to
133 * throw a NullPointerException. NullPointerTester considers this a failure.
134 * Ideally the test would be fixed, but it would require a special case for
135 * Class<E> where E extends Enum. Until that happens (if ever), leave
136 * checkNotNull() here. For now, contemplate the irony that checking
137 * elementType, the problem argument, is harmful, while checking iterable,
138 * the innocent bystander, is effective.
139 */
140 checkNotNull(iterable);
141 EnumSet<E> set = EnumSet.noneOf(elementType);
142 Iterables.addAll(set, iterable);
143 return set;
144 }
145
146 // HashSet
147
148 /**
149 * Creates a <i>mutable</i>, empty {@code HashSet} instance.
150 *
151 * <p><b>Note:</b> if mutability is not required, use {@link
152 * ImmutableSet#of()} instead.
153 *
154 * <p><b>Note:</b> if {@code E} is an {@link Enum} type, use {@link
155 * EnumSet#noneOf} instead.
156 *
157 * @return a new, empty {@code HashSet}
158 */
159 public static <E> HashSet<E> newHashSet() {
160 return new HashSet<E>();
161 }
162
163 /**
164 * Creates a <i>mutable</i> {@code HashSet} instance containing the given
165 * elements in unspecified order.
166 *
167 * <p><b>Note:</b> if mutability is not required and the elements are
168 * non-null, use an overload of {@link ImmutableSet#of()} (for varargs) or
169 * {@link ImmutableSet#copyOf(Object[])} (for an array) instead.
170 *
171 * <p><b>Note:</b> if {@code E} is an {@link Enum} type, use {@link
172 * EnumSet#of(Enum, Enum[])} instead.
173 *
174 * @param elements the elements that the set should contain
175 * @return a new {@code HashSet} containing those elements (minus duplicates)
176 */
177 public static <E> HashSet<E> newHashSet(E... elements) {
178 HashSet<E> set = newHashSetWithExpectedSize(elements.length);
179 Collections.addAll(set, elements);
180 return set;
181 }
182
183 /**
184 * Creates a {@code HashSet} instance, with a high enough "initial capacity"
185 * that it <i>should</i> hold {@code expectedSize} elements without growth.
186 * This behavior cannot be broadly guaranteed, but it is observed to be true
187 * for OpenJDK 1.6. It also can't be guaranteed that the method isn't
188 * inadvertently <i>oversizing</i> the returned set.
189 *
190 * @param expectedSize the number of elements you expect to add to the
191 * returned set
192 * @return a new, empty {@code HashSet} with enough capacity to hold {@code
193 * expectedSize} elements without resizing
194 * @throws IllegalArgumentException if {@code expectedSize} is negative
195 */
196 public static <E> HashSet<E> newHashSetWithExpectedSize(int expectedSize) {
197 return new HashSet<E>(Maps.capacity(expectedSize));
198 }
199
200 /**
201 * Creates a <i>mutable</i> {@code HashSet} instance containing the given
202 * elements in unspecified order.
203 *
204 * <p><b>Note:</b> if mutability is not required and the elements are
205 * non-null, use {@link ImmutableSet#copyOf(Iterable)} instead.
206 *
207 * <p><b>Note:</b> if {@code E} is an {@link Enum} type, use
208 * {@link #newEnumSet(Iterable, Class)} instead.
209 *
210 * @param elements the elements that the set should contain
211 * @return a new {@code HashSet} containing those elements (minus duplicates)
212 */
213 public static <E> HashSet<E> newHashSet(Iterable<? extends E> elements) {
214 return (elements instanceof Collection)
215 ? new HashSet<E>(Collections2.cast(elements))
216 : newHashSet(elements.iterator());
217 }
218
219 /**
220 * Creates a <i>mutable</i> {@code HashSet} instance containing the given
221 * elements in unspecified order.
222 *
223 * <p><b>Note:</b> if mutability is not required and the elements are
224 * non-null, use {@link ImmutableSet#copyOf(Iterable)} instead.
225 *
226 * <p><b>Note:</b> if {@code E} is an {@link Enum} type, you should create an
227 * {@link EnumSet} instead.
228 *
229 * @param elements the elements that the set should contain
230 * @return a new {@code HashSet} containing those elements (minus duplicates)
231 */
232 public static <E> HashSet<E> newHashSet(Iterator<? extends E> elements) {
233 HashSet<E> set = newHashSet();
234 while (elements.hasNext()) {
235 set.add(elements.next());
236 }
237 return set;
238 }
239
240 // LinkedHashSet
241
242 /**
243 * Creates a <i>mutable</i>, empty {@code LinkedHashSet} instance.
244 *
245 * <p><b>Note:</b> if mutability is not required, use {@link
246 * ImmutableSet#of()} instead.
247 *
248 * @return a new, empty {@code LinkedHashSet}
249 */
250 public static <E> LinkedHashSet<E> newLinkedHashSet() {
251 return new LinkedHashSet<E>();
252 }
253
254 /**
255 * Creates a {@code LinkedHashSet} instance, with a high enough "initial
256 * capacity" that it <i>should</i> hold {@code expectedSize} elements without
257 * growth. This behavior cannot be broadly guaranteed, but it is observed to
258 * be true for OpenJDK 1.6. It also can't be guaranteed that the method isn't
259 * inadvertently <i>oversizing</i> the returned set.
260 *
261 * @param expectedSize the number of elements you expect to add to the
262 * returned set
263 * @return a new, empty {@code LinkedHashSet} with enough capacity to hold
264 * {@code expectedSize} elements without resizing
265 * @throws IllegalArgumentException if {@code expectedSize} is negative
266 * @since 11.0
267 */
268 public static <E> LinkedHashSet<E> newLinkedHashSetWithExpectedSize(
269 int expectedSize) {
270 return new LinkedHashSet<E>(Maps.capacity(expectedSize));
271 }
272
273 /**
274 * Creates a <i>mutable</i> {@code LinkedHashSet} instance containing the
275 * given elements in order.
276 *
277 * <p><b>Note:</b> if mutability is not required and the elements are
278 * non-null, use {@link ImmutableSet#copyOf(Iterable)} instead.
279 *
280 * @param elements the elements that the set should contain, in order
281 * @return a new {@code LinkedHashSet} containing those elements (minus
282 * duplicates)
283 */
284 public static <E> LinkedHashSet<E> newLinkedHashSet(
285 Iterable<? extends E> elements) {
286 if (elements instanceof Collection) {
287 return new LinkedHashSet<E>(Collections2.cast(elements));
288 }
289 LinkedHashSet<E> set = newLinkedHashSet();
290 for (E element : elements) {
291 set.add(element);
292 }
293 return set;
294 }
295
296 // TreeSet
297
298 /**
299 * Creates a <i>mutable</i>, empty {@code TreeSet} instance sorted by the
300 * natural sort ordering of its elements.
301 *
302 * <p><b>Note:</b> if mutability is not required, use {@link
303 * ImmutableSortedSet#of()} instead.
304 *
305 * @return a new, empty {@code TreeSet}
306 */
307 public static <E extends Comparable> TreeSet<E> newTreeSet() {
308 return new TreeSet<E>();
309 }
310
311 /**
312 * Creates a <i>mutable</i> {@code TreeSet} instance containing the given
313 * elements sorted by their natural ordering.
314 *
315 * <p><b>Note:</b> if mutability is not required, use {@link
316 * ImmutableSortedSet#copyOf(Iterable)} instead.
317 *
318 * <p><b>Note:</b> If {@code elements} is a {@code SortedSet} with an explicit
319 * comparator, this method has different behavior than
320 * {@link TreeSet#TreeSet(SortedSet)}, which returns a {@code TreeSet} with
321 * that comparator.
322 *
323 * @param elements the elements that the set should contain
324 * @return a new {@code TreeSet} containing those elements (minus duplicates)
325 */
326 public static <E extends Comparable> TreeSet<E> newTreeSet(
327 Iterable<? extends E> elements) {
328 TreeSet<E> set = newTreeSet();
329 for (E element : elements) {
330 set.add(element);
331 }
332 return set;
333 }
334
335 /**
336 * Creates a <i>mutable</i>, empty {@code TreeSet} instance with the given
337 * comparator.
338 *
339 * <p><b>Note:</b> if mutability is not required, use {@code
340 * ImmutableSortedSet.orderedBy(comparator).build()} instead.
341 *
342 * @param comparator the comparator to use to sort the set
343 * @return a new, empty {@code TreeSet}
344 * @throws NullPointerException if {@code comparator} is null
345 */
346 public static <E> TreeSet<E> newTreeSet(Comparator<? super E> comparator) {
347 return new TreeSet<E>(checkNotNull(comparator));
348 }
349
350 /**
351 * Creates an empty {@code Set} that uses identity to determine equality. It
352 * compares object references, instead of calling {@code equals}, to
353 * determine whether a provided object matches an element in the set. For
354 * example, {@code contains} returns {@code false} when passed an object that
355 * equals a set member, but isn't the same instance. This behavior is similar
356 * to the way {@code IdentityHashMap} handles key lookups.
357 *
358 * @since 8.0
359 */
360 public static <E> Set<E> newIdentityHashSet() {
361 return Sets.newSetFromMap(Maps.<E, Boolean>newIdentityHashMap());
362 }
363
364 /**
365 * Creates an empty {@code CopyOnWriteArraySet} instance.
366 *
367 * <p><b>Note:</b> if you need an immutable empty {@link Set}, use
368 * {@link Collections#emptySet} instead.
369 *
370 * @return a new, empty {@code CopyOnWriteArraySet}
371 * @since 12.0
372 */
373 @Beta
374 @GwtIncompatible("CopyOnWriteArraySet")
375 public static <E> CopyOnWriteArraySet<E> newCopyOnWriteArraySet() {
376 return new CopyOnWriteArraySet<E>();
377 }
378
379 /**
380 * Creates a {@code CopyOnWriteArraySet} instance containing the given elements.
381 *
382 * @param elements the elements that the set should contain, in order
383 * @return a new {@code CopyOnWriteArraySet} containing those elements
384 * @since 12.0
385 */
386 @Beta
387 @GwtIncompatible("CopyOnWriteArraySet")
388 public static <E> CopyOnWriteArraySet<E> newCopyOnWriteArraySet(
389 Iterable<? extends E> elements) {
390 // We copy elements to an ArrayList first, rather than incurring the
391 // quadratic cost of adding them to the COWAS directly.
392 Collection<? extends E> elementsCollection = (elements instanceof Collection)
393 ? Collections2.cast(elements)
394 : Lists.newArrayList(elements);
395 return new CopyOnWriteArraySet<E>(elementsCollection);
396 }
397
398 /**
399 * Creates an {@code EnumSet} consisting of all enum values that are not in
400 * the specified collection. If the collection is an {@link EnumSet}, this
401 * method has the same behavior as {@link EnumSet#complementOf}. Otherwise,
402 * the specified collection must contain at least one element, in order to
403 * determine the element type. If the collection could be empty, use
404 * {@link #complementOf(Collection, Class)} instead of this method.
405 *
406 * @param collection the collection whose complement should be stored in the
407 * enum set
408 * @return a new, modifiable {@code EnumSet} containing all values of the enum
409 * that aren't present in the given collection
410 * @throws IllegalArgumentException if {@code collection} is not an
411 * {@code EnumSet} instance and contains no elements
412 */
413 public static <E extends Enum<E>> EnumSet<E> complementOf(
414 Collection<E> collection) {
415 if (collection instanceof EnumSet) {
416 return EnumSet.complementOf((EnumSet<E>) collection);
417 }
418 checkArgument(!collection.isEmpty(),
419 "collection is empty; use the other version of this method");
420 Class<E> type = collection.iterator().next().getDeclaringClass();
421 return makeComplementByHand(collection, type);
422 }
423
424 /**
425 * Creates an {@code EnumSet} consisting of all enum values that are not in
426 * the specified collection. This is equivalent to
427 * {@link EnumSet#complementOf}, but can act on any input collection, as long
428 * as the elements are of enum type.
429 *
430 * @param collection the collection whose complement should be stored in the
431 * {@code EnumSet}
432 * @param type the type of the elements in the set
433 * @return a new, modifiable {@code EnumSet} initially containing all the
434 * values of the enum not present in the given collection
435 */
436 public static <E extends Enum<E>> EnumSet<E> complementOf(
437 Collection<E> collection, Class<E> type) {
438 checkNotNull(collection);
439 return (collection instanceof EnumSet)
440 ? EnumSet.complementOf((EnumSet<E>) collection)
441 : makeComplementByHand(collection, type);
442 }
443
444 private static <E extends Enum<E>> EnumSet<E> makeComplementByHand(
445 Collection<E> collection, Class<E> type) {
446 EnumSet<E> result = EnumSet.allOf(type);
447 result.removeAll(collection);
448 return result;
449 }
450
451 /*
452 * Regarding newSetForMap() and SetFromMap:
453 *
454 * Written by Doug Lea with assistance from members of JCP JSR-166
455 * Expert Group and released to the public domain, as explained at
456 * http://creativecommons.org/licenses/publicdomain
457 */
458
459 /**
460 * Returns a set backed by the specified map. The resulting set displays
461 * the same ordering, concurrency, and performance characteristics as the
462 * backing map. In essence, this factory method provides a {@link Set}
463 * implementation corresponding to any {@link Map} implementation. There is no
464 * need to use this method on a {@link Map} implementation that already has a
465 * corresponding {@link Set} implementation (such as {@link java.util.HashMap}
466 * or {@link java.util.TreeMap}).
467 *
468 * <p>Each method invocation on the set returned by this method results in
469 * exactly one method invocation on the backing map or its {@code keySet}
470 * view, with one exception. The {@code addAll} method is implemented as a
471 * sequence of {@code put} invocations on the backing map.
472 *
473 * <p>The specified map must be empty at the time this method is invoked,
474 * and should not be accessed directly after this method returns. These
475 * conditions are ensured if the map is created empty, passed directly
476 * to this method, and no reference to the map is retained, as illustrated
477 * in the following code fragment: <pre> {@code
478 *
479 * Set<Object> identityHashSet = Sets.newSetFromMap(
480 * new IdentityHashMap<Object, Boolean>());}</pre>
481 *
482 * This method has the same behavior as the JDK 6 method
483 * {@code Collections.newSetFromMap()}. The returned set is serializable if
484 * the backing map is.
485 *
486 * @param map the backing map
487 * @return the set backed by the map
488 * @throws IllegalArgumentException if {@code map} is not empty
489 */
490 public static <E> Set<E> newSetFromMap(Map<E, Boolean> map) {
491 return new SetFromMap<E>(map);
492 }
493
494 private static class SetFromMap<E> extends AbstractSet<E>
495 implements Set<E>, Serializable {
496 private final Map<E, Boolean> m; // The backing map
497 private transient Set<E> s; // Its keySet
498
499 SetFromMap(Map<E, Boolean> map) {
500 checkArgument(map.isEmpty(), "Map is non-empty");
501 m = map;
502 s = map.keySet();
503 }
504
505 @Override public void clear() {
506 m.clear();
507 }
508 @Override public int size() {
509 return m.size();
510 }
511 @Override public boolean isEmpty() {
512 return m.isEmpty();
513 }
514 @Override public boolean contains(Object o) {
515 return m.containsKey(o);
516 }
517 @Override public boolean remove(Object o) {
518 return m.remove(o) != null;
519 }
520 @Override public boolean add(E e) {
521 return m.put(e, Boolean.TRUE) == null;
522 }
523 @Override public Iterator<E> iterator() {
524 return s.iterator();
525 }
526 @Override public Object[] toArray() {
527 return s.toArray();
528 }
529 @Override public <T> T[] toArray(T[] a) {
530 return s.toArray(a);
531 }
532 @Override public String toString() {
533 return s.toString();
534 }
535 @Override public int hashCode() {
536 return s.hashCode();
537 }
538 @Override public boolean equals(@Nullable Object object) {
539 return this == object || this.s.equals(object);
540 }
541 @Override public boolean containsAll(Collection<?> c) {
542 return s.containsAll(c);
543 }
544 @Override public boolean removeAll(Collection<?> c) {
545 return s.removeAll(c);
546 }
547 @Override public boolean retainAll(Collection<?> c) {
548 return s.retainAll(c);
549 }
550
551 // addAll is the only inherited implementation
552 @GwtIncompatible("not needed in emulated source")
553 private static final long serialVersionUID = 0;
554
555 @GwtIncompatible("java.io.ObjectInputStream")
556 private void readObject(ObjectInputStream stream)
557 throws IOException, ClassNotFoundException {
558 stream.defaultReadObject();
559 s = m.keySet();
560 }
561 }
562
563 /**
564 * An unmodifiable view of a set which may be backed by other sets; this view
565 * will change as the backing sets do. Contains methods to copy the data into
566 * a new set which will then remain stable. There is usually no reason to
567 * retain a reference of type {@code SetView}; typically, you either use it
568 * as a plain {@link Set}, or immediately invoke {@link #immutableCopy} or
569 * {@link #copyInto} and forget the {@code SetView} itself.
570 *
571 * @since 2.0 (imported from Google Collections Library)
572 */
573 public abstract static class SetView<E> extends AbstractSet<E> {
574 private SetView() {} // no subclasses but our own
575
576 /**
577 * Returns an immutable copy of the current contents of this set view.
578 * Does not support null elements.
579 *
580 * <p><b>Warning:</b> this may have unexpected results if a backing set of
581 * this view uses a nonstandard notion of equivalence, for example if it is
582 * a {@link TreeSet} using a comparator that is inconsistent with {@link
583 * Object#equals(Object)}.
584 */
585 public ImmutableSet<E> immutableCopy() {
586 return ImmutableSet.copyOf(this);
587 }
588
589 /**
590 * Copies the current contents of this set view into an existing set. This
591 * method has equivalent behavior to {@code set.addAll(this)}, assuming that
592 * all the sets involved are based on the same notion of equivalence.
593 *
594 * @return a reference to {@code set}, for convenience
595 */
596 // Note: S should logically extend Set<? super E> but can't due to either
597 // some javac bug or some weirdness in the spec, not sure which.
598 public <S extends Set<E>> S copyInto(S set) {
599 set.addAll(this);
600 return set;
601 }
602 }
603
604 /**
605 * Returns an unmodifiable <b>view</b> of the union of two sets. The returned
606 * set contains all elements that are contained in either backing set.
607 * Iterating over the returned set iterates first over all the elements of
608 * {@code set1}, then over each element of {@code set2}, in order, that is not
609 * contained in {@code set1}.
610 *
611 * <p>Results are undefined if {@code set1} and {@code set2} are sets based on
612 * different equivalence relations (as {@link HashSet}, {@link TreeSet}, and
613 * the {@link Map#keySet} of an {@code IdentityHashMap} all are).
614 *
615 * <p><b>Note:</b> The returned view performs better when {@code set1} is the
616 * smaller of the two sets. If you have reason to believe one of your sets
617 * will generally be smaller than the other, pass it first.
618 */
619 public static <E> SetView<E> union(
620 final Set<? extends E> set1, final Set<? extends E> set2) {
621 checkNotNull(set1, "set1");
622 checkNotNull(set2, "set2");
623
624 final Set<? extends E> set2minus1 = difference(set2, set1);
625
626 return new SetView<E>() {
627 @Override public int size() {
628 return set1.size() + set2minus1.size();
629 }
630 @Override public boolean isEmpty() {
631 return set1.isEmpty() && set2.isEmpty();
632 }
633 @Override public Iterator<E> iterator() {
634 return Iterators.unmodifiableIterator(
635 Iterators.concat(set1.iterator(), set2minus1.iterator()));
636 }
637 @Override public boolean contains(Object object) {
638 return set1.contains(object) || set2.contains(object);
639 }
640 @Override public <S extends Set<E>> S copyInto(S set) {
641 set.addAll(set1);
642 set.addAll(set2);
643 return set;
644 }
645 @Override public ImmutableSet<E> immutableCopy() {
646 return new ImmutableSet.Builder<E>()
647 .addAll(set1).addAll(set2).build();
648 }
649 };
650 }
651
652 /**
653 * Returns an unmodifiable <b>view</b> of the intersection of two sets. The
654 * returned set contains all elements that are contained by both backing sets.
655 * The iteration order of the returned set matches that of {@code set1}.
656 *
657 * <p>Results are undefined if {@code set1} and {@code set2} are sets based
658 * on different equivalence relations (as {@code HashSet}, {@code TreeSet},
659 * and the keySet of an {@code IdentityHashMap} all are).
660 *
661 * <p><b>Note:</b> The returned view performs slightly better when {@code
662 * set1} is the smaller of the two sets. If you have reason to believe one of
663 * your sets will generally be smaller than the other, pass it first.
664 * Unfortunately, since this method sets the generic type of the returned set
665 * based on the type of the first set passed, this could in rare cases force
666 * you to make a cast, for example: <pre> {@code
667 *
668 * Set<Object> aFewBadObjects = ...
669 * Set<String> manyBadStrings = ...
670 *
671 * // impossible for a non-String to be in the intersection
672 * SuppressWarnings("unchecked")
673 * Set<String> badStrings = (Set) Sets.intersection(
674 * aFewBadObjects, manyBadStrings);}</pre>
675 *
676 * This is unfortunate, but should come up only very rarely.
677 */
678 public static <E> SetView<E> intersection(
679 final Set<E> set1, final Set<?> set2) {
680 checkNotNull(set1, "set1");
681 checkNotNull(set2, "set2");
682
683 final Predicate<Object> inSet2 = Predicates.in(set2);
684 return new SetView<E>() {
685 @Override public Iterator<E> iterator() {
686 return Iterators.filter(set1.iterator(), inSet2);
687 }
688 @Override public int size() {
689 return Iterators.size(iterator());
690 }
691 @Override public boolean isEmpty() {
692 return !iterator().hasNext();
693 }
694 @Override public boolean contains(Object object) {
695 return set1.contains(object) && set2.contains(object);
696 }
697 @Override public boolean containsAll(Collection<?> collection) {
698 return set1.containsAll(collection)
699 && set2.containsAll(collection);
700 }
701 };
702 }
703
704 /**
705 * Returns an unmodifiable <b>view</b> of the difference of two sets. The
706 * returned set contains all elements that are contained by {@code set1} and
707 * not contained by {@code set2}. {@code set2} may also contain elements not
708 * present in {@code set1}; these are simply ignored. The iteration order of
709 * the returned set matches that of {@code set1}.
710 *
711 * <p>Results are undefined if {@code set1} and {@code set2} are sets based
712 * on different equivalence relations (as {@code HashSet}, {@code TreeSet},
713 * and the keySet of an {@code IdentityHashMap} all are).
714 */
715 public static <E> SetView<E> difference(
716 final Set<E> set1, final Set<?> set2) {
717 checkNotNull(set1, "set1");
718 checkNotNull(set2, "set2");
719
720 final Predicate<Object> notInSet2 = Predicates.not(Predicates.in(set2));
721 return new SetView<E>() {
722 @Override public Iterator<E> iterator() {
723 return Iterators.filter(set1.iterator(), notInSet2);
724 }
725 @Override public int size() {
726 return Iterators.size(iterator());
727 }
728 @Override public boolean isEmpty() {
729 return set2.containsAll(set1);
730 }
731 @Override public boolean contains(Object element) {
732 return set1.contains(element) && !set2.contains(element);
733 }
734 };
735 }
736
737 /**
738 * Returns an unmodifiable <b>view</b> of the symmetric difference of two
739 * sets. The returned set contains all elements that are contained in either
740 * {@code set1} or {@code set2} but not in both. The iteration order of the
741 * returned set is undefined.
742 *
743 * <p>Results are undefined if {@code set1} and {@code set2} are sets based
744 * on different equivalence relations (as {@code HashSet}, {@code TreeSet},
745 * and the keySet of an {@code IdentityHashMap} all are).
746 *
747 * @since 3.0
748 */
749 public static <E> SetView<E> symmetricDifference(
750 Set<? extends E> set1, Set<? extends E> set2) {
751 checkNotNull(set1, "set1");
752 checkNotNull(set2, "set2");
753
754 // TODO(kevinb): Replace this with a more efficient implementation
755 return difference(union(set1, set2), intersection(set1, set2));
756 }
757
758 /**
759 * Returns the elements of {@code unfiltered} that satisfy a predicate. The
760 * returned set is a live view of {@code unfiltered}; changes to one affect
761 * the other.
762 *
763 * <p>The resulting set's iterator does not support {@code remove()}, but all
764 * other set methods are supported. When given an element that doesn't satisfy
765 * the predicate, the set's {@code add()} and {@code addAll()} methods throw
766 * an {@link IllegalArgumentException}. When methods such as {@code
767 * removeAll()} and {@code clear()} are called on the filtered set, only
768 * elements that satisfy the filter will be removed from the underlying set.
769 *
770 * <p>The returned set isn't threadsafe or serializable, even if
771 * {@code unfiltered} is.
772 *
773 * <p>Many of the filtered set's methods, such as {@code size()}, iterate
774 * across every element in the underlying set and determine which elements
775 * satisfy the filter. When a live view is <i>not</i> needed, it may be faster
776 * to copy {@code Iterables.filter(unfiltered, predicate)} and use the copy.
777 *
778 * <p><b>Warning:</b> {@code predicate} must be <i>consistent with equals</i>,
779 * as documented at {@link Predicate#apply}. Do not provide a predicate such
780 * as {@code Predicates.instanceOf(ArrayList.class)}, which is inconsistent
781 * with equals. (See {@link Iterables#filter(Iterable, Class)} for related
782 * functionality.)
783 */
784 // TODO(kevinb): how to omit that last sentence when building GWT javadoc?
785 public static <E> Set<E> filter(
786 Set<E> unfiltered, Predicate<? super E> predicate) {
787 if (unfiltered instanceof SortedSet) {
788 return filter((SortedSet<E>) unfiltered, predicate);
789 }
790 if (unfiltered instanceof FilteredSet) {
791 // Support clear(), removeAll(), and retainAll() when filtering a filtered
792 // collection.
793 FilteredSet<E> filtered = (FilteredSet<E>) unfiltered;
794 Predicate<E> combinedPredicate
795 = Predicates.<E>and(filtered.predicate, predicate);
796 return new FilteredSet<E>(
797 (Set<E>) filtered.unfiltered, combinedPredicate);
798 }
799
800 return new FilteredSet<E>(
801 checkNotNull(unfiltered), checkNotNull(predicate));
802 }
803
804 private static class FilteredSet<E> extends FilteredCollection<E>
805 implements Set<E> {
806 FilteredSet(Set<E> unfiltered, Predicate<? super E> predicate) {
807 super(unfiltered, predicate);
808 }
809
810 @Override public boolean equals(@Nullable Object object) {
811 return equalsImpl(this, object);
812 }
813
814 @Override public int hashCode() {
815 return hashCodeImpl(this);
816 }
817 }
818
819 /**
820 * Returns the elements of a {@code SortedSet}, {@code unfiltered}, that
821 * satisfy a predicate. The returned set is a live view of {@code unfiltered};
822 * changes to one affect the other.
823 *
824 * <p>The resulting set's iterator does not support {@code remove()}, but all
825 * other set methods are supported. When given an element that doesn't satisfy
826 * the predicate, the set's {@code add()} and {@code addAll()} methods throw
827 * an {@link IllegalArgumentException}. When methods such as
828 * {@code removeAll()} and {@code clear()} are called on the filtered set,
829 * only elements that satisfy the filter will be removed from the underlying
830 * set.
831 *
832 * <p>The returned set isn't threadsafe or serializable, even if
833 * {@code unfiltered} is.
834 *
835 * <p>Many of the filtered set's methods, such as {@code size()}, iterate across
836 * every element in the underlying set and determine which elements satisfy
837 * the filter. When a live view is <i>not</i> needed, it may be faster to copy
838 * {@code Iterables.filter(unfiltered, predicate)} and use the copy.
839 *
840 * <p><b>Warning:</b> {@code predicate} must be <i>consistent with equals</i>,
841 * as documented at {@link Predicate#apply}. Do not provide a predicate such as
842 * {@code Predicates.instanceOf(ArrayList.class)}, which is inconsistent with
843 * equals. (See {@link Iterables#filter(Iterable, Class)} for related
844 * functionality.)
845 *
846 * @since 11.0
847 */
848 @Beta
849 @SuppressWarnings("unchecked")
850 public static <E> SortedSet<E> filter(
851 SortedSet<E> unfiltered, Predicate<? super E> predicate) {
852 if (unfiltered instanceof FilteredSet) {
853 // Support clear(), removeAll(), and retainAll() when filtering a filtered
854 // collection.
855 FilteredSet<E> filtered = (FilteredSet<E>) unfiltered;
856 Predicate<E> combinedPredicate
857 = Predicates.<E>and(filtered.predicate, predicate);
858 return new FilteredSortedSet<E>(
859 (SortedSet<E>) filtered.unfiltered, combinedPredicate);
860 }
861
862 return new FilteredSortedSet<E>(
863 checkNotNull(unfiltered), checkNotNull(predicate));
864 }
865
866 private static class FilteredSortedSet<E> extends FilteredCollection<E>
867 implements SortedSet<E> {
868
869 FilteredSortedSet(SortedSet<E> unfiltered, Predicate<? super E> predicate) {
870 super(unfiltered, predicate);
871 }
872
873 @Override public boolean equals(@Nullable Object object) {
874 return equalsImpl(this, object);
875 }
876
877 @Override public int hashCode() {
878 return hashCodeImpl(this);
879 }
880
881 @Override
882 public Comparator<? super E> comparator() {
883 return ((SortedSet<E>) unfiltered).comparator();
884 }
885
886 @Override
887 public SortedSet<E> subSet(E fromElement, E toElement) {
888 return new FilteredSortedSet<E>(((SortedSet<E>) unfiltered).subSet(fromElement, toElement),
889 predicate);
890 }
891
892 @Override
893 public SortedSet<E> headSet(E toElement) {
894 return new FilteredSortedSet<E>(((SortedSet<E>) unfiltered).headSet(toElement), predicate);
895 }
896
897 @Override
898 public SortedSet<E> tailSet(E fromElement) {
899 return new FilteredSortedSet<E>(((SortedSet<E>) unfiltered).tailSet(fromElement), predicate);
900 }
901
902 @Override
903 public E first() {
904 return iterator().next();
905 }
906
907 @Override
908 public E last() {
909 SortedSet<E> sortedUnfiltered = (SortedSet<E>) unfiltered;
910 while (true) {
911 E element = sortedUnfiltered.last();
912 if (predicate.apply(element)) {
913 return element;
914 }
915 sortedUnfiltered = sortedUnfiltered.headSet(element);
916 }
917 }
918 }
919
920 /**
921 * Returns every possible list that can be formed by choosing one element
922 * from each of the given sets in order; the "n-ary
923 * <a href="http://en.wikipedia.org/wiki/Cartesian_product">Cartesian
924 * product</a>" of the sets. For example: <pre> {@code
925 *
926 * Sets.cartesianProduct(ImmutableList.of(
927 * ImmutableSet.of(1, 2),
928 * ImmutableSet.of("A", "B", "C")))}</pre>
929 *
930 * returns a set containing six lists:
931 *
932 * <ul>
933 * <li>{@code ImmutableList.of(1, "A")}
934 * <li>{@code ImmutableList.of(1, "B")}
935 * <li>{@code ImmutableList.of(1, "C")}
936 * <li>{@code ImmutableList.of(2, "A")}
937 * <li>{@code ImmutableList.of(2, "B")}
938 * <li>{@code ImmutableList.of(2, "C")}
939 * </ul>
940 *
941 * The order in which these lists are returned is not guaranteed, however the
942 * position of an element inside a tuple always corresponds to the position of
943 * the set from which it came in the input list. Note that if any input set is
944 * empty, the Cartesian product will also be empty. If no sets at all are
945 * provided (an empty list), the resulting Cartesian product has one element,
946 * an empty list (counter-intuitive, but mathematically consistent).
947 *
948 * <p><i>Performance notes:</i> while the cartesian product of sets of size
949 * {@code m, n, p} is a set of size {@code m x n x p}, its actual memory
950 * consumption is much smaller. When the cartesian set is constructed, the
951 * input sets are merely copied. Only as the resulting set is iterated are the
952 * individual lists created, and these are not retained after iteration.
953 *
954 * @param sets the sets to choose elements from, in the order that
955 * the elements chosen from those sets should appear in the resulting
956 * lists
957 * @param <B> any common base class shared by all axes (often just {@link
958 * Object})
959 * @return the Cartesian product, as an immutable set containing immutable
960 * lists
961 * @throws NullPointerException if {@code sets}, any one of the {@code sets},
962 * or any element of a provided set is null
963 * @since 2.0
964 */
965 public static <B> Set<List<B>> cartesianProduct(
966 List<? extends Set<? extends B>> sets) {
967 for (Set<? extends B> set : sets) {
968 if (set.isEmpty()) {
969 return ImmutableSet.of();
970 }
971 }
972 CartesianSet<B> cartesianSet = new CartesianSet<B>(sets);
973 return cartesianSet;
974 }
975
976 /**
977 * Returns every possible list that can be formed by choosing one element
978 * from each of the given sets in order; the "n-ary
979 * <a href="http://en.wikipedia.org/wiki/Cartesian_product">Cartesian
980 * product</a>" of the sets. For example: <pre> {@code
981 *
982 * Sets.cartesianProduct(
983 * ImmutableSet.of(1, 2),
984 * ImmutableSet.of("A", "B", "C"))}</pre>
985 *
986 * returns a set containing six lists:
987 *
988 * <ul>
989 * <li>{@code ImmutableList.of(1, "A")}
990 * <li>{@code ImmutableList.of(1, "B")}
991 * <li>{@code ImmutableList.of(1, "C")}
992 * <li>{@code ImmutableList.of(2, "A")}
993 * <li>{@code ImmutableList.of(2, "B")}
994 * <li>{@code ImmutableList.of(2, "C")}
995 * </ul>
996 *
997 * The order in which these lists are returned is not guaranteed, however the
998 * position of an element inside a tuple always corresponds to the position of
999 * the set from which it came in the input list. Note that if any input set is
1000 * empty, the Cartesian product will also be empty. If no sets at all are
1001 * provided, the resulting Cartesian product has one element, an empty list
1002 * (counter-intuitive, but mathematically consistent).
1003 *
1004 * <p><i>Performance notes:</i> while the cartesian product of sets of size
1005 * {@code m, n, p} is a set of size {@code m x n x p}, its actual memory
1006 * consumption is much smaller. When the cartesian set is constructed, the
1007 * input sets are merely copied. Only as the resulting set is iterated are the
1008 * individual lists created, and these are not retained after iteration.
1009 *
1010 * @param sets the sets to choose elements from, in the order that
1011 * the elements chosen from those sets should appear in the resulting
1012 * lists
1013 * @param <B> any common base class shared by all axes (often just {@link
1014 * Object})
1015 * @return the Cartesian product, as an immutable set containing immutable
1016 * lists
1017 * @throws NullPointerException if {@code sets}, any one of the {@code sets},
1018 * or any element of a provided set is null
1019 * @since 2.0
1020 */
1021 public static <B> Set<List<B>> cartesianProduct(
1022 Set<? extends B>... sets) {
1023 return cartesianProduct(Arrays.asList(sets));
1024 }
1025
1026 private static class CartesianSet<B> extends AbstractSet<List<B>> {
1027 final ImmutableList<Axis> axes;
1028 final int size;
1029
1030 CartesianSet(List<? extends Set<? extends B>> sets) {
1031 int dividend = 1;
1032 ImmutableList.Builder<Axis> builder = ImmutableList.builder();
1033 try {
1034 for (Set<? extends B> set : sets) {
1035 Axis axis = new Axis(set, dividend);
1036 builder.add(axis);
1037 dividend = IntMath.checkedMultiply(dividend, axis.size());
1038 }
1039 } catch (ArithmeticException overflow) {
1040 throw new IllegalArgumentException("cartesian product too big");
1041 }
1042 this.axes = builder.build();
1043 size = dividend;
1044 }
1045
1046 @Override public int size() {
1047 return size;
1048 }
1049
1050 @Override public UnmodifiableIterator<List<B>> iterator() {
1051 return new AbstractIndexedListIterator<List<B>>(size) {
1052 @Override
1053 protected List<B> get(int index) {
1054 Object[] tuple = new Object[axes.size()];
1055 for (int i = 0 ; i < tuple.length; i++) {
1056 tuple[i] = axes.get(i).getForIndex(index);
1057 }
1058
1059 @SuppressWarnings("unchecked") // only B's are put in here
1060 List<B> result = (ImmutableList<B>) ImmutableList.copyOf(tuple);
1061 return result;
1062 }
1063 };
1064 }
1065
1066 @Override public boolean contains(Object element) {
1067 if (!(element instanceof List<?>)) {
1068 return false;
1069 }
1070 List<?> tuple = (List<?>) element;
1071 int dimensions = axes.size();
1072 if (tuple.size() != dimensions) {
1073 return false;
1074 }
1075 for (int i = 0; i < dimensions; i++) {
1076 if (!axes.get(i).contains(tuple.get(i))) {
1077 return false;
1078 }
1079 }
1080 return true;
1081 }
1082
1083 @Override public boolean equals(@Nullable Object object) {
1084 // Warning: this is broken if size() == 0, so it is critical that we
1085 // substitute an empty ImmutableSet to the user in place of this
1086 if (object instanceof CartesianSet) {
1087 CartesianSet<?> that = (CartesianSet<?>) object;
1088 return this.axes.equals(that.axes);
1089 }
1090 return super.equals(object);
1091 }
1092
1093 @Override public int hashCode() {
1094 // Warning: this is broken if size() == 0, so it is critical that we
1095 // substitute an empty ImmutableSet to the user in place of this
1096
1097 // It's a weird formula, but tests prove it works.
1098 int adjust = size - 1;
1099 for (int i = 0; i < axes.size(); i++) {
1100 adjust *= 31;
1101 }
1102 return axes.hashCode() + adjust;
1103 }
1104
1105 private class Axis {
1106 final ImmutableSet<? extends B> choices;
1107 final ImmutableList<? extends B> choicesList;
1108 final int dividend;
1109
1110 Axis(Set<? extends B> set, int dividend) {
1111 choices = ImmutableSet.copyOf(set);
1112 choicesList = choices.asList();
1113 this.dividend = dividend;
1114 }
1115
1116 int size() {
1117 return choices.size();
1118 }
1119
1120 B getForIndex(int index) {
1121 return choicesList.get(index / dividend % size());
1122 }
1123
1124 boolean contains(Object target) {
1125 return choices.contains(target);
1126 }
1127
1128 @Override public boolean equals(Object obj) {
1129 if (obj instanceof CartesianSet.Axis) {
1130 CartesianSet.Axis that = (CartesianSet.Axis) obj;
1131 return this.choices.equals(that.choices);
1132 // dividends must be equal or we wouldn't have gotten this far
1133 }
1134 return false;
1135 }
1136
1137 @Override public int hashCode() {
1138 // Because Axis instances are not exposed, we can
1139 // opportunistically choose whatever bizarre formula happens
1140 // to make CartesianSet.hashCode() as simple as possible.
1141 return size / choices.size() * choices.hashCode();
1142 }
1143 }
1144 }
1145
1146 /**
1147 * Returns the set of all possible subsets of {@code set}. For example,
1148 * {@code powerSet(ImmutableSet.of(1, 2))} returns the set {@code {{},
1149 * {1}, {2}, {1, 2}}}.
1150 *
1151 * <p>Elements appear in these subsets in the same iteration order as they
1152 * appeared in the input set. The order in which these subsets appear in the
1153 * outer set is undefined. Note that the power set of the empty set is not the
1154 * empty set, but a one-element set containing the empty set.
1155 *
1156 * <p>The returned set and its constituent sets use {@code equals} to decide
1157 * whether two elements are identical, even if the input set uses a different
1158 * concept of equivalence.
1159 *
1160 * <p><i>Performance notes:</i> while the power set of a set with size {@code
1161 * n} is of size {@code 2^n}, its memory usage is only {@code O(n)}. When the
1162 * power set is constructed, the input set is merely copied. Only as the
1163 * power set is iterated are the individual subsets created, and these subsets
1164 * themselves occupy only a few bytes of memory regardless of their size.
1165 *
1166 * @param set the set of elements to construct a power set from
1167 * @return the power set, as an immutable set of immutable sets
1168 * @throws IllegalArgumentException if {@code set} has more than 30 unique
1169 * elements (causing the power set size to exceed the {@code int} range)
1170 * @throws NullPointerException if {@code set} is or contains {@code null}
1171 * @see <a href="http://en.wikipedia.org/wiki/Power_set">Power set article at
1172 * Wikipedia</a>
1173 * @since 4.0
1174 */
1175 @GwtCompatible(serializable = false)
1176 public static <E> Set<Set<E>> powerSet(Set<E> set) {
1177 ImmutableSet<E> input = ImmutableSet.copyOf(set);
1178 checkArgument(input.size() <= 30,
1179 "Too many elements to create power set: %s > 30", input.size());
1180 return new PowerSet<E>(input);
1181 }
1182
1183 private static final class PowerSet<E> extends AbstractSet<Set<E>> {
1184 final ImmutableSet<E> inputSet;
1185 final ImmutableList<E> inputList;
1186 final int powerSetSize;
1187
1188 PowerSet(ImmutableSet<E> input) {
1189 this.inputSet = input;
1190 this.inputList = input.asList();
1191 this.powerSetSize = 1 << input.size();
1192 }
1193
1194 @Override public int size() {
1195 return powerSetSize;
1196 }
1197
1198 @Override public boolean isEmpty() {
1199 return false;
1200 }
1201
1202 @Override public Iterator<Set<E>> iterator() {
1203 return new AbstractIndexedListIterator<Set<E>>(powerSetSize) {
1204 @Override protected Set<E> get(final int setBits) {
1205 return new AbstractSet<E>() {
1206 @Override public int size() {
1207 return Integer.bitCount(setBits);
1208 }
1209 @Override public Iterator<E> iterator() {
1210 return new BitFilteredSetIterator<E>(inputList, setBits);
1211 }
1212 };
1213 }
1214 };
1215 }
1216
1217 private static final class BitFilteredSetIterator<E>
1218 extends UnmodifiableIterator<E> {
1219 final ImmutableList<E> input;
1220 int remainingSetBits;
1221
1222 BitFilteredSetIterator(ImmutableList<E> input, int allSetBits) {
1223 this.input = input;
1224 this.remainingSetBits = allSetBits;
1225 }
1226
1227 @Override public boolean hasNext() {
1228 return remainingSetBits != 0;
1229 }
1230
1231 @Override public E next() {
1232 int index = Integer.numberOfTrailingZeros(remainingSetBits);
1233 if (index == 32) {
1234 throw new NoSuchElementException();
1235 }
1236
1237 int currentElementMask = 1 << index;
1238 remainingSetBits &= ~currentElementMask;
1239 return input.get(index);
1240 }
1241 }
1242
1243 @Override public boolean contains(@Nullable Object obj) {
1244 if (obj instanceof Set) {
1245 Set<?> set = (Set<?>) obj;
1246 return inputSet.containsAll(set);
1247 }
1248 return false;
1249 }
1250
1251 @Override public boolean equals(@Nullable Object obj) {
1252 if (obj instanceof PowerSet) {
1253 PowerSet<?> that = (PowerSet<?>) obj;
1254 return inputSet.equals(that.inputSet);
1255 }
1256 return super.equals(obj);
1257 }
1258
1259 @Override public int hashCode() {
1260 /*
1261 * The sum of the sums of the hash codes in each subset is just the sum of
1262 * each input element's hash code times the number of sets that element
1263 * appears in. Each element appears in exactly half of the 2^n sets, so:
1264 */
1265 return inputSet.hashCode() << (inputSet.size() - 1);
1266 }
1267
1268 @Override public String toString() {
1269 return "powerSet(" + inputSet + ")";
1270 }
1271 }
1272
1273 /**
1274 * An implementation for {@link Set#hashCode()}.
1275 */
1276 static int hashCodeImpl(Set<?> s) {
1277 int hashCode = 0;
1278 for (Object o : s) {
1279 hashCode += o != null ? o.hashCode() : 0;
1280 }
1281 return hashCode;
1282 }
1283
1284 /**
1285 * An implementation for {@link Set#equals(Object)}.
1286 */
1287 static boolean equalsImpl(Set<?> s, @Nullable Object object){
1288 if (s == object) {
1289 return true;
1290 }
1291 if (object instanceof Set) {
1292 Set<?> o = (Set<?>) object;
1293
1294 try {
1295 return s.size() == o.size() && s.containsAll(o);
1296 } catch (NullPointerException ignored) {
1297 return false;
1298 } catch (ClassCastException ignored) {
1299 return false;
1300 }
1301 }
1302 return false;
1303 }
1304
1305 /**
1306 * Returns an unmodifiable view of the specified navigable set. This method
1307 * allows modules to provide users with "read-only" access to internal
1308 * navigable sets. Query operations on the returned set "read through" to the
1309 * specified set, and attempts to modify the returned set, whether direct or
1310 * via its collection views, result in an
1311 * {@code UnsupportedOperationException}.
1312 *
1313 * <p>The returned navigable set will be serializable if the specified
1314 * navigable set is serializable.
1315 *
1316 * @param set the navigable set for which an unmodifiable view is to be
1317 * returned
1318 * @return an unmodifiable view of the specified navigable set
1319 * @since 12.0
1320 */
1321 @GwtIncompatible("NavigableSet")
1322 public static <E> NavigableSet<E> unmodifiableNavigableSet(
1323 NavigableSet<E> set) {
1324 if (set instanceof ImmutableSortedSet
1325 || set instanceof UnmodifiableNavigableSet) {
1326 return set;
1327 }
1328 return new UnmodifiableNavigableSet<E>(set);
1329 }
1330
1331 @GwtIncompatible("NavigableSet")
1332 static final class UnmodifiableNavigableSet<E>
1333 extends ForwardingSortedSet<E> implements NavigableSet<E>, Serializable {
1334 private final NavigableSet<E> delegate;
1335
1336 UnmodifiableNavigableSet(NavigableSet<E> delegate) {
1337 this.delegate = checkNotNull(delegate);
1338 }
1339
1340 @Override
1341 protected SortedSet<E> delegate() {
1342 return Collections.unmodifiableSortedSet(delegate);
1343 }
1344
1345 @Override
1346 public E lower(E e) {
1347 return delegate.lower(e);
1348 }
1349
1350 @Override
1351 public E floor(E e) {
1352 return delegate.floor(e);
1353 }
1354
1355 @Override
1356 public E ceiling(E e) {
1357 return delegate.ceiling(e);
1358 }
1359
1360 @Override
1361 public E higher(E e) {
1362 return delegate.higher(e);
1363 }
1364
1365 @Override
1366 public E pollFirst() {
1367 throw new UnsupportedOperationException();
1368 }
1369
1370 @Override
1371 public E pollLast() {
1372 throw new UnsupportedOperationException();
1373 }
1374
1375 private transient UnmodifiableNavigableSet<E> descendingSet;
1376
1377 @Override
1378 public NavigableSet<E> descendingSet() {
1379 UnmodifiableNavigableSet<E> result = descendingSet;
1380 if (result == null) {
1381 result = descendingSet = new UnmodifiableNavigableSet<E>(
1382 delegate.descendingSet());
1383 result.descendingSet = this;
1384 }
1385 return result;
1386 }
1387
1388 @Override
1389 public Iterator<E> descendingIterator() {
1390 return Iterators.unmodifiableIterator(delegate.descendingIterator());
1391 }
1392
1393 @Override
1394 public NavigableSet<E> subSet(
1395 E fromElement,
1396 boolean fromInclusive,
1397 E toElement,
1398 boolean toInclusive) {
1399 return unmodifiableNavigableSet(delegate.subSet(
1400 fromElement,
1401 fromInclusive,
1402 toElement,
1403 toInclusive));
1404 }
1405
1406 @Override
1407 public NavigableSet<E> headSet(E toElement, boolean inclusive) {
1408 return unmodifiableNavigableSet(delegate.headSet(toElement, inclusive));
1409 }
1410
1411 @Override
1412 public NavigableSet<E> tailSet(E fromElement, boolean inclusive) {
1413 return unmodifiableNavigableSet(
1414 delegate.tailSet(fromElement, inclusive));
1415 }
1416
1417 private static final long serialVersionUID = 0;
1418 }
1419
1420 /**
1421 * Remove each element in an iterable from a set.
1422 */
1423 static boolean removeAllImpl(Set<?> set, Iterator<?> iterator) {
1424 boolean changed = false;
1425 while (iterator.hasNext()) {
1426 changed |= set.remove(iterator.next());
1427 }
1428 return changed;
1429 }
1430
1431 static boolean removeAllImpl(Set<?> set, Collection<?> collection) {
1432 if (collection instanceof Multiset) {
1433 collection = ((Multiset<?>) collection).elementSet();
1434 }
1435 if (collection.size() < set.size()) {
1436 return removeAllImpl(set, collection.iterator());
1437 } else {
1438 return Iterators.removeAll(set.iterator(), collection);
1439 }
1440 }
1441
1442 @GwtIncompatible("NavigableSet")
1443 static class DescendingSet<E> extends ForwardingNavigableSet<E> {
1444 private final NavigableSet<E> forward;
1445
1446 DescendingSet(NavigableSet<E> forward) {
1447 this.forward = forward;
1448 }
1449
1450 @Override
1451 protected NavigableSet<E> delegate() {
1452 return forward;
1453 }
1454
1455 @Override
1456 public E lower(E e) {
1457 return forward.higher(e);
1458 }
1459
1460 @Override
1461 public E floor(E e) {
1462 return forward.ceiling(e);
1463 }
1464
1465 @Override
1466 public E ceiling(E e) {
1467 return forward.floor(e);
1468 }
1469
1470 @Override
1471 public E higher(E e) {
1472 return forward.lower(e);
1473 }
1474
1475 @Override
1476 public E pollFirst() {
1477 return forward.pollLast();
1478 }
1479
1480 @Override
1481 public E pollLast() {
1482 return forward.pollFirst();
1483 }
1484
1485 @Override
1486 public NavigableSet<E> descendingSet() {
1487 return forward;
1488 }
1489
1490 @Override
1491 public Iterator<E> descendingIterator() {
1492 return forward.iterator();
1493 }
1494
1495 @Override
1496 public NavigableSet<E> subSet(
1497 E fromElement,
1498 boolean fromInclusive,
1499 E toElement,
1500 boolean toInclusive) {
1501 return forward.subSet(toElement, toInclusive, fromElement, fromInclusive).descendingSet();
1502 }
1503
1504 @Override
1505 public NavigableSet<E> headSet(E toElement, boolean inclusive) {
1506 return forward.tailSet(toElement, inclusive).descendingSet();
1507 }
1508
1509 @Override
1510 public NavigableSet<E> tailSet(E fromElement, boolean inclusive) {
1511 return forward.headSet(fromElement, inclusive).descendingSet();
1512 }
1513
1514 @SuppressWarnings("unchecked")
1515 @Override
1516 public Comparator<? super E> comparator() {
1517 Comparator<? super E> forwardComparator = forward.comparator();
1518 if (forwardComparator == null) {
1519 return (Comparator) Ordering.natural().reverse();
1520 } else {
1521 return reverse(forwardComparator);
1522 }
1523 }
1524
1525 // If we inline this, we get a javac error.
1526 private static <T> Ordering<T> reverse(Comparator<T> forward) {
1527 return Ordering.from(forward).reverse();
1528 }
1529
1530 @Override
1531 public E first() {
1532 return forward.last();
1533 }
1534
1535 @Override
1536 public SortedSet<E> headSet(E toElement) {
1537 return standardHeadSet(toElement);
1538 }
1539
1540 @Override
1541 public E last() {
1542 return forward.first();
1543 }
1544
1545 @Override
1546 public SortedSet<E> subSet(E fromElement, E toElement) {
1547 return standardSubSet(fromElement, toElement);
1548 }
1549
1550 @Override
1551 public SortedSet<E> tailSet(E fromElement) {
1552 return standardTailSet(fromElement);
1553 }
1554
1555 @Override
1556 public Iterator<E> iterator() {
1557 return forward.descendingIterator();
1558 }
1559
1560 @Override
1561 public Object[] toArray() {
1562 return standardToArray();
1563 }
1564
1565 @Override
1566 public <T> T[] toArray(T[] array) {
1567 return standardToArray(array);
1568 }
1569
1570 @Override
1571 public String toString() {
1572 return standardToString();
1573 }
1574 }
1575
1576 /**
1577 * Used to avoid http://bugs.sun.com/view_bug.do?bug_id=6558557
1578 */
1579 static <T> SortedSet<T> cast(Iterable<T> iterable) {
1580 return (SortedSet<T>) iterable;
1581 }
1582 }