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