/* * Copyright (C) 2007 The Guava Authors * * Licensed under the Apache License, Version 2.0 (the "License"); * you may not use this file except in compliance with the License. * You may obtain a copy of the License at * * http://www.apache.org/licenses/LICENSE-2.0 * * Unless required by applicable law or agreed to in writing, software * distributed under the License is distributed on an "AS IS" BASIS, * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. * See the License for the specific language governing permissions and * limitations under the License. */ package com.google.common.collect; import static com.google.common.base.Preconditions.checkArgument; import static com.google.common.base.Preconditions.checkNotNull; import com.google.common.annotations.Beta; import com.google.common.annotations.GwtCompatible; import com.google.common.base.Function; import com.google.common.base.Objects; import com.google.common.base.Preconditions; import com.google.common.base.Predicate; import com.google.common.base.Predicates; import com.google.common.collect.Collections2.FilteredCollection; import com.google.common.math.IntMath; import java.io.Serializable; import java.util.AbstractSet; import java.util.Arrays; import java.util.Collection; import java.util.Collections; import java.util.Comparator; import java.util.EnumSet; import java.util.HashSet; import java.util.Iterator; import java.util.LinkedHashSet; import java.util.List; import java.util.Map; import java.util.NoSuchElementException; import java.util.Set; import java.util.SortedSet; import java.util.TreeSet; import javax.annotation.Nullable; /** * Static utility methods pertaining to {@link Set} instances. Also see this * class's counterparts {@link Lists} and {@link Maps}. * * @author Kevin Bourrillion * @author Jared Levy * @author Chris Povirk * @since 2.0 (imported from Google Collections Library) */ @GwtCompatible(emulated = true) public final class Sets { private Sets() {} /** * Returns an immutable set instance containing the given enum elements. * Internally, the returned set will be backed by an {@link EnumSet}. * *
The iteration order of the returned set follows the enum's iteration
* order, not the order in which the elements are provided to the method.
*
* @param anElement one of the elements the set should contain
* @param otherElements the rest of the elements the set should contain
* @return an immutable set containing those elements, minus duplicates
*/
// http://code.google.com/p/google-web-toolkit/issues/detail?id=3028
@GwtCompatible(serializable = true)
public static The iteration order of the returned set follows the enum's iteration
* order, not the order in which the elements appear in the given collection.
*
* @param elements the elements, all of the same {@code enum} type, that the
* set should contain
* @return an immutable set containing those elements, minus duplicates
*/
// http://code.google.com/p/google-web-toolkit/issues/detail?id=3028
@GwtCompatible(serializable = true)
public static Note: if mutability is not required, use {@link
* ImmutableSet#of()} instead.
*
* Note: if {@code E} is an {@link Enum} type, use {@link
* EnumSet#noneOf} instead.
*
* @return a new, empty {@code HashSet}
*/
public static Note: if mutability is not required and the elements are
* non-null, use an overload of {@link ImmutableSet#of()} (for varargs) or
* {@link ImmutableSet#copyOf(Object[])} (for an array) instead.
*
* Note: if {@code E} is an {@link Enum} type, use {@link
* EnumSet#of(Enum, Enum[])} instead.
*
* @param elements the elements that the set should contain
* @return a new {@code HashSet} containing those elements (minus duplicates)
*/
public static Note: if mutability is not required and the elements are
* non-null, use {@link ImmutableSet#copyOf(Iterable)} instead.
*
* Note: if {@code E} is an {@link Enum} type, use
* {@link #newEnumSet(Iterable, Class)} instead.
*
* @param elements the elements that the set should contain
* @return a new {@code HashSet} containing those elements (minus duplicates)
*/
public static Note: if mutability is not required and the elements are
* non-null, use {@link ImmutableSet#copyOf(Iterable)} instead.
*
* Note: if {@code E} is an {@link Enum} type, you should create an
* {@link EnumSet} instead.
*
* @param elements the elements that the set should contain
* @return a new {@code HashSet} containing those elements (minus duplicates)
*/
public static Note: if mutability is not required, use {@link
* ImmutableSet#of()} instead.
*
* @return a new, empty {@code LinkedHashSet}
*/
public static Note: if mutability is not required and the elements are
* non-null, use {@link ImmutableSet#copyOf(Iterable)} instead.
*
* @param elements the elements that the set should contain, in order
* @return a new {@code LinkedHashSet} containing those elements (minus
* duplicates)
*/
public static Note: if mutability is not required, use {@link
* ImmutableSortedSet#of()} instead.
*
* @return a new, empty {@code TreeSet}
*/
public static Note: if mutability is not required, use {@link
* ImmutableSortedSet#copyOf(Iterable)} instead.
*
* Note: If {@code elements} is a {@code SortedSet} with an explicit
* comparator, this method has different behavior than
* {@link TreeSet#TreeSet(SortedSet)}, which returns a {@code TreeSet} with
* that comparator.
*
* @param elements the elements that the set should contain
* @return a new {@code TreeSet} containing those elements (minus duplicates)
*/
public static Note: if mutability is not required, use {@code
* ImmutableSortedSet.orderedBy(comparator).build()} instead.
*
* @param comparator the comparator to use to sort the set
* @return a new, empty {@code TreeSet}
* @throws NullPointerException if {@code comparator} is null
*/
public static Each method invocation on the set returned by this method results in
* exactly one method invocation on the backing map or its {@code keySet}
* view, with one exception. The {@code addAll} method is implemented as a
* sequence of {@code put} invocations on the backing map.
*
* The specified map must be empty at the time this method is invoked,
* and should not be accessed directly after this method returns. These
* conditions are ensured if the map is created empty, passed directly
* to this method, and no reference to the map is retained, as illustrated
* in the following code fragment: Warning: this may have unexpected results if a backing set of
* this view uses a nonstandard notion of equivalence, for example if it is
* a {@link TreeSet} using a comparator that is inconsistent with {@link
* Object#equals(Object)}.
*/
public ImmutableSet Results are undefined if {@code set1} and {@code set2} are sets based on
* different equivalence relations (as {@link HashSet}, {@link TreeSet}, and
* the {@link Map#keySet} of an {@code IdentityHashMap} all are).
*
* Note: The returned view performs better when {@code set1} is the
* smaller of the two sets. If you have reason to believe one of your sets
* will generally be smaller than the other, pass it first.
*/
public static Results are undefined if {@code set1} and {@code set2} are sets based
* on different equivalence relations (as {@code HashSet}, {@code TreeSet},
* and the keySet of an {@code IdentityHashMap} all are).
*
* Note: The returned view performs slightly better when {@code
* set1} is the smaller of the two sets. If you have reason to believe one of
* your sets will generally be smaller than the other, pass it first.
* Unfortunately, since this method sets the generic type of the returned set
* based on the type of the first set passed, this could in rare cases force
* you to make a cast, for example: Results are undefined if {@code set1} and {@code set2} are sets based
* on different equivalence relations (as {@code HashSet}, {@code TreeSet},
* and the keySet of an {@code IdentityHashMap} all are).
*/
public static Results are undefined if {@code set1} and {@code set2} are sets based
* on different equivalence relations (as {@code HashSet}, {@code TreeSet},
* and the keySet of an {@code IdentityHashMap} all are).
*
* @since 3.0
*/
public static The resulting set's iterator does not support {@code remove()}, but all
* other set methods are supported. When given an element that doesn't satisfy
* the predicate, the set's {@code add()} and {@code addAll()} methods throw
* an {@link IllegalArgumentException}. When methods such as {@code
* removeAll()} and {@code clear()} are called on the filtered set, only
* elements that satisfy the filter will be removed from the underlying set.
*
* The returned set isn't threadsafe or serializable, even if
* {@code unfiltered} is.
*
* Many of the filtered set's methods, such as {@code size()}, iterate
* across every element in the underlying set and determine which elements
* satisfy the filter. When a live view is not needed, it may be faster
* to copy {@code Iterables.filter(unfiltered, predicate)} and use the copy.
*
* Warning: {@code predicate} must be consistent with equals,
* as documented at {@link Predicate#apply}. Do not provide a predicate such
* as {@code Predicates.instanceOf(ArrayList.class)}, which is inconsistent
* with equals. (See {@link Iterables#filter(Iterable, Class)} for related
* functionality.)
*/
// TODO(kevinb): how to omit that last sentence when building GWT javadoc?
public static The resulting set's iterator does not support {@code remove()}, but all
* other set methods are supported. When given an element that doesn't satisfy
* the predicate, the set's {@code add()} and {@code addAll()} methods throw
* an {@link IllegalArgumentException}. When methods such as
* {@code removeAll()} and {@code clear()} are called on the filtered set,
* only elements that satisfy the filter will be removed from the underlying
* set.
*
* The returned set isn't threadsafe or serializable, even if
* {@code unfiltered} is.
*
* Many of the filtered set's methods, such as {@code size()}, iterate across
* every element in the underlying set and determine which elements satisfy
* the filter. When a live view is not needed, it may be faster to copy
* {@code Iterables.filter(unfiltered, predicate)} and use the copy.
*
* Warning: {@code predicate} must be consistent with equals,
* as documented at {@link Predicate#apply}. Do not provide a predicate such as
* {@code Predicates.instanceOf(ArrayList.class)}, which is inconsistent with
* equals. (See {@link Iterables#filter(Iterable, Class)} for related
* functionality.)
*
* @since 11.0
*/
@Beta
@SuppressWarnings("unchecked")
public static Performance notes: while the cartesian product of sets of size
* {@code m, n, p} is a set of size {@code m x n x p}, its actual memory
* consumption is much smaller. When the cartesian set is constructed, the
* input sets are merely copied. Only as the resulting set is iterated are the
* individual lists created, and these are not retained after iteration.
*
* @param sets the sets to choose elements from, in the order that
* the elements chosen from those sets should appear in the resulting
* lists
* @param any common base class shared by all axes (often just {@link
* Object})
* @return the Cartesian product, as an immutable set containing immutable
* lists
* @throws NullPointerException if {@code sets}, any one of the {@code sets},
* or any element of a provided set is null
* @since 2.0
*/
public static Set Performance notes: while the cartesian product of sets of size
* {@code m, n, p} is a set of size {@code m x n x p}, its actual memory
* consumption is much smaller. When the cartesian set is constructed, the
* input sets are merely copied. Only as the resulting set is iterated are the
* individual lists created, and these are not retained after iteration.
*
* @param sets the sets to choose elements from, in the order that
* the elements chosen from those sets should appear in the resulting
* lists
* @param any common base class shared by all axes (often just {@link
* Object})
* @return the Cartesian product, as an immutable set containing immutable
* lists
* @throws NullPointerException if {@code sets}, any one of the {@code sets},
* or any element of a provided set is null
* @since 2.0
*/
public static Set Elements appear in these subsets in the same iteration order as they
* appeared in the input set. The order in which these subsets appear in the
* outer set is undefined. Note that the power set of the empty set is not the
* empty set, but a one-element set containing the empty set.
*
* The returned set and its constituent sets use {@code equals} to decide
* whether two elements are identical, even if the input set uses a different
* concept of equivalence.
*
* Performance notes: while the power set of a set with size {@code
* n} is of size {@code 2^n}, its memory usage is only {@code O(n)}. When the
* power set is constructed, the input set is merely copied. Only as the
* power set is iterated are the individual subsets created, and these subsets
* themselves occupy only a few bytes of memory regardless of their size.
*
* @param set the set of elements to construct a power set from
* @return the power set, as an immutable set of immutable sets
* @throws IllegalArgumentException if {@code set} has more than 30 unique
* elements (causing the power set size to exceed the {@code int} range)
* @throws NullPointerException if {@code set} is or contains {@code null}
* @see Power set article at
* Wikipedia
* @since 4.0
*/
@GwtCompatible(serializable = false)
public static Note that the returned Set's contains method is unsafe -
* you *must* pass an instance of B to it, since the bijection
* can only invert B's (not any Object) back to A, so we can
* then delegate the call to the original Set.
*/
static Set transform(
Set set, InvertibleFunction bijection) {
return new TransformedSet(
Preconditions.checkNotNull(set, "set"),
Preconditions.checkNotNull(bijection, "bijection")
);
}
/**
* Stop-gap measure since there is no bijection related type in Guava.
*/
abstract static class InvertibleFunction implements Function {
abstract A invert(B b);
public InvertibleFunction inverse() {
return new InvertibleFunction() {
@Override public A apply(B b) {
return InvertibleFunction.this.invert(b);
}
@Override B invert(A a) {
return InvertibleFunction.this.apply(a);
}
// Not required per se, but just for good karma.
@Override public InvertibleFunction inverse() {
return InvertibleFunction.this;
}
};
}
}
private static class TransformedSet extends AbstractSet {
final Set delegate;
final InvertibleFunction bijection;
TransformedSet(Set delegate, InvertibleFunction bijection) {
this.delegate = delegate;
this.bijection = bijection;
}
@Override public Iterator iterator() {
return Iterators.transform(delegate.iterator(), bijection);
}
@Override public int size() {
return delegate.size();
}
@SuppressWarnings("unchecked") // unsafe, passed object *must* be B
@Override public boolean contains(Object o) {
B b = (B) o;
A a = bijection.invert(b);
/*
* Mathematically, Converter defines a bijection between ALL A's
* on ALL B's. Here we concern ourselves with a subset
* of this relation: we only want the part that is defined by a *subset*
* of all A's (defined by that Set delegate), and the image
* of *that* on B (which is this set). We don't care whether
* the converter is *not* a bijection for A's that are not in Set
* or B's not in this Set.
*
* We only want to return true if and only f the user passes a B instance
* that is contained in precisely in the image of Set.
*
* The first test is whether the inverse image of this B is indeed
* in Set. But we don't know whether that B belongs in this Set
* or not; if not, the converter is free to return
* anything it wants, even an element of Set (and this relationship
* is not part of the Set <--> Set bijection), and we must not
* be confused by that. So we have to do a final check to see if the
* image of that A is really equivalent to the passed B, which proves
* that the given B belongs indeed in the image of Set.
*/
return delegate.contains(a) && Objects.equal(bijection.apply(a), o);
}
@Override public boolean add(B b) {
return delegate.add(bijection.invert(b));
}
@SuppressWarnings("unchecked") // unsafe, passed object *must* be B
@Override public boolean remove(Object o) {
return contains(o) && delegate.remove(bijection.invert((B) o));
}
@Override public void clear() {
delegate.clear();
}
}
/**
* Remove each element in an iterable from a set.
*/
static boolean removeAllImpl(Set> set, Iterable> iterable) {
// TODO(jlevy): Have ForwardingSet.standardRemoveAll() call this method.
boolean changed = false;
for (Object o : iterable) {
changed |= set.remove(o);
}
return changed;
}
}
{@code
*
* Set
*
* This method has the same behavior as the JDK 6 method
* {@code Collections.newSetFromMap()}. The returned set is serializable if
* the backing map is.
*
* @param map the backing map
* @return the set backed by the map
* @throws IllegalArgumentException if {@code map} is not empty
*/
public static > S copyInto(S set) {
set.addAll(this);
return set;
}
}
/**
* Returns an unmodifiable view of the union of two sets. The returned
* set contains all elements that are contained in either backing set.
* Iterating over the returned set iterates first over all the elements of
* {@code set1}, then over each element of {@code set2}, in order, that is not
* contained in {@code set1}.
*
* > S copyInto(S set) {
set.addAll(set1);
set.addAll(set2);
return set;
}
@Override public ImmutableSet {@code
*
* Set
*
* This is unfortunate, but should come up only very rarely.
*/
public static {@code
*
* Sets.cartesianProduct(ImmutableList.of(
* ImmutableSet.of(1, 2),
* ImmutableSet.of("A", "B", "C")))}
*
* returns a set containing six lists:
*
*
*
*
* The order in which these lists are returned is not guaranteed, however the
* position of an element inside a tuple always corresponds to the position of
* the set from which it came in the input list. Note that if any input set is
* empty, the Cartesian product will also be empty. If no sets at all are
* provided (an empty list), the resulting Cartesian product has one element,
* an empty list (counter-intuitive, but mathematically consistent).
*
* > cartesianProduct(
List extends Set extends B>> sets) {
for (Set extends B> set : sets) {
if (set.isEmpty()) {
return ImmutableSet.of();
}
}
CartesianSet cartesianSet = new CartesianSet(sets);
return cartesianSet;
}
/**
* Returns every possible list that can be formed by choosing one element
* from each of the given sets in order; the "n-ary
* Cartesian
* product" of the sets. For example:
{@code
*
* Sets.cartesianProduct(
* ImmutableSet.of(1, 2),
* ImmutableSet.of("A", "B", "C"))}
*
* returns a set containing six lists:
*
*
*
*
* The order in which these lists are returned is not guaranteed, however the
* position of an element inside a tuple always corresponds to the position of
* the set from which it came in the input list. Note that if any input set is
* empty, the Cartesian product will also be empty. If no sets at all are
* provided, the resulting Cartesian product has one element, an empty list
* (counter-intuitive, but mathematically consistent).
*
* > cartesianProduct(
Set extends B>... sets) {
return cartesianProduct(Arrays.asList(sets));
}
private static class CartesianSet extends AbstractSet
> {
final ImmutableList
> iterator() {
return new UnmodifiableIterator
>() {
int index;
@Override
public boolean hasNext() {
return index < size;
}
@Override
public List next() {
if (!hasNext()) {
throw new NoSuchElementException();
}
Object[] tuple = new Object[axes.size()];
for (int i = 0 ; i < tuple.length; i++) {
tuple[i] = axes.get(i).getForIndex(index);
}
index++;
@SuppressWarnings("unchecked") // only B's are put in here
List result = (ImmutableList) ImmutableList.copyOf(tuple);
return result;
}
};
}
@Override public boolean contains(Object element) {
if (!(element instanceof List>)) {
return false;
}
List> tuple = (List>) element;
int dimensions = axes.size();
if (tuple.size() != dimensions) {
return false;
}
for (int i = 0; i < dimensions; i++) {
if (!axes.get(i).contains(tuple.get(i))) {
return false;
}
}
return true;
}
@Override public boolean equals(@Nullable Object object) {
// Warning: this is broken if size() == 0, so it is critical that we
// substitute an empty ImmutableSet to the user in place of this
if (object instanceof CartesianSet) {
CartesianSet> that = (CartesianSet>) object;
return this.axes.equals(that.axes);
}
return super.equals(object);
}
@Override public int hashCode() {
// Warning: this is broken if size() == 0, so it is critical that we
// substitute an empty ImmutableSet to the user in place of this
// It's a weird formula, but tests prove it works.
int adjust = size - 1;
for (int i = 0; i < axes.size(); i++) {
adjust *= 31;
}
return axes.hashCode() + adjust;
}
private class Axis {
final ImmutableSet extends B> choices;
final ImmutableList extends B> choicesList;
final int dividend;
Axis(Set extends B> set, int dividend) {
choices = ImmutableSet.copyOf(set);
choicesList = choices.asList();
this.dividend = dividend;
}
int size() {
return choices.size();
}
B getForIndex(int index) {
return choicesList.get(index / dividend % size());
}
boolean contains(Object target) {
return choices.contains(target);
}
@Override public boolean equals(Object obj) {
if (obj instanceof CartesianSet.Axis) {
CartesianSet.Axis that = (CartesianSet.Axis) obj;
return this.choices.equals(that.choices);
// dividends must be equal or we wouldn't have gotten this far
}
return false;
}
@Override public int hashCode() {
// Because Axis instances are not exposed, we can
// opportunistically choose whatever bizarre formula happens
// to make CartesianSet.hashCode() as simple as possible.
return size / choices.size() * choices.hashCode();
}
}
}
/**
* Returns the set of all possible subsets of {@code set}. For example,
* {@code powerSet(ImmutableSet.of(1, 2))} returns the set {@code {{},
* {1}, {2}, {1, 2}}}.
*
*