diff options
Diffstat (limited to 'guava/src/com/google/common/collect/Sets.java')
| -rw-r--r-- | guava/src/com/google/common/collect/Sets.java | 851 |
1 files changed, 237 insertions, 614 deletions
diff --git a/guava/src/com/google/common/collect/Sets.java b/guava/src/com/google/common/collect/Sets.java index 95298e7..14ad867 100644 --- a/guava/src/com/google/common/collect/Sets.java +++ b/guava/src/com/google/common/collect/Sets.java @@ -19,11 +19,16 @@ 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.annotations.GwtIncompatible; +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.IOException; import java.io.ObjectInputStream; @@ -39,22 +44,16 @@ import java.util.Iterator; import java.util.LinkedHashSet; import java.util.List; import java.util.Map; -import java.util.NavigableSet; import java.util.NoSuchElementException; import java.util.Set; import java.util.SortedSet; import java.util.TreeSet; -import java.util.concurrent.CopyOnWriteArraySet; import javax.annotation.Nullable; /** * Static utility methods pertaining to {@link Set} instances. Also see this - * class's counterparts {@link Lists}, {@link Maps} and {@link Queues}. - * - * <p>See the Guava User Guide article on <a href= - * "http://code.google.com/p/guava-libraries/wiki/CollectionUtilitiesExplained#Sets"> - * {@code Sets}</a>. + * class's counterparts {@link Lists} and {@link Maps}. * * @author Kevin Bourrillion * @author Jared Levy @@ -66,22 +65,6 @@ public final class Sets { private Sets() {} /** - * {@link AbstractSet} substitute without the potentially-quadratic - * {@code removeAll} implementation. - */ - abstract static class ImprovedAbstractSet<E> extends AbstractSet<E> { - @Override - public boolean removeAll(Collection<?> c) { - return removeAllImpl(this, c); - } - - @Override - public boolean retainAll(Collection<?> c) { - return super.retainAll(checkNotNull(c)); // GWT compatibility - } - } - - /** * Returns an immutable set instance containing the given enum elements. * Internally, the returned set will be backed by an {@link EnumSet}. * @@ -96,7 +79,7 @@ public final class Sets { @GwtCompatible(serializable = true) public static <E extends Enum<E>> ImmutableSet<E> immutableEnumSet( E anElement, E... otherElements) { - return ImmutableEnumSet.asImmutable(EnumSet.of(anElement, otherElements)); + return new ImmutableEnumSet<E>(EnumSet.of(anElement, otherElements)); } /** @@ -114,25 +97,20 @@ public final class Sets { @GwtCompatible(serializable = true) public static <E extends Enum<E>> ImmutableSet<E> immutableEnumSet( Iterable<E> elements) { - if (elements instanceof ImmutableEnumSet) { - return (ImmutableEnumSet<E>) elements; - } else if (elements instanceof Collection) { - Collection<E> collection = (Collection<E>) elements; - if (collection.isEmpty()) { - return ImmutableSet.of(); - } else { - return ImmutableEnumSet.asImmutable(EnumSet.copyOf(collection)); - } - } else { - Iterator<E> itr = elements.iterator(); - if (itr.hasNext()) { - EnumSet<E> enumSet = EnumSet.of(itr.next()); - Iterators.addAll(enumSet, itr); - return ImmutableEnumSet.asImmutable(enumSet); - } else { - return ImmutableSet.of(); - } + Iterator<E> iterator = elements.iterator(); + if (!iterator.hasNext()) { + return ImmutableSet.of(); + } + if (elements instanceof EnumSet) { + EnumSet<E> enumSetClone = EnumSet.copyOf((EnumSet<E>) elements); + return new ImmutableEnumSet<E>(enumSetClone); } + E first = iterator.next(); + EnumSet<E> set = EnumSet.of(first); + while (iterator.hasNext()) { + set.add(iterator.next()); + } + return new ImmutableEnumSet<E>(set); } /** @@ -143,6 +121,20 @@ public final class Sets { */ public static <E extends Enum<E>> EnumSet<E> newEnumSet(Iterable<E> iterable, Class<E> elementType) { + /* + * TODO(cpovirk): noneOf() and addAll() will both throw + * NullPointerExceptions when appropriate. However, NullPointerTester will + * fail on this method because it passes in Class.class instead of an enum + * type. This means that, when iterable is null but elementType is not, + * noneOf() will throw a ClassCastException before addAll() has a chance to + * throw a NullPointerException. NullPointerTester considers this a failure. + * Ideally the test would be fixed, but it would require a special case for + * Class<E> where E extends Enum. Until that happens (if ever), leave + * checkNotNull() here. For now, contemplate the irony that checking + * elementType, the problem argument, is harmful, while checking iterable, + * the innocent bystander, is effective. + */ + checkNotNull(iterable); EnumSet<E> set = EnumSet.noneOf(elementType); Iterables.addAll(set, iterable); return set; @@ -367,38 +359,6 @@ public final class Sets { } /** - * Creates an empty {@code CopyOnWriteArraySet} instance. - * - * <p><b>Note:</b> if you need an immutable empty {@link Set}, use - * {@link Collections#emptySet} instead. - * - * @return a new, empty {@code CopyOnWriteArraySet} - * @since 12.0 - */ - @GwtIncompatible("CopyOnWriteArraySet") - public static <E> CopyOnWriteArraySet<E> newCopyOnWriteArraySet() { - return new CopyOnWriteArraySet<E>(); - } - - /** - * Creates a {@code CopyOnWriteArraySet} instance containing the given elements. - * - * @param elements the elements that the set should contain, in order - * @return a new {@code CopyOnWriteArraySet} containing those elements - * @since 12.0 - */ - @GwtIncompatible("CopyOnWriteArraySet") - public static <E> CopyOnWriteArraySet<E> newCopyOnWriteArraySet( - Iterable<? extends E> elements) { - // We copy elements to an ArrayList first, rather than incurring the - // quadratic cost of adding them to the COWAS directly. - Collection<? extends E> elementsCollection = (elements instanceof Collection) - ? Collections2.cast(elements) - : Lists.newArrayList(elements); - return new CopyOnWriteArraySet<E>(elementsCollection); - } - - /** * Creates an {@code EnumSet} consisting of all enum values that are not in * the specified collection. If the collection is an {@link EnumSet}, this * method has the same behavior as {@link EnumSet#complementOf}. Otherwise, @@ -618,11 +578,6 @@ public final class Sets { * <p><b>Note:</b> 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. - * - * <p>Further, note that the current implementation is not suitable for nested - * {@code union} views, i.e. the following should be avoided when in a loop: - * {@code union = Sets.union(union, anotherSet);}, since iterating over the resulting - * set has a cubic complexity to the depth of the nesting. */ public static <E> SetView<E> union( final Set<? extends E> set1, final Set<? extends E> set2) { @@ -853,13 +808,10 @@ public final class Sets { * * @since 11.0 */ + @Beta + @SuppressWarnings("unchecked") public static <E> SortedSet<E> filter( SortedSet<E> unfiltered, Predicate<? super E> predicate) { - return Platform.setsFilterSortedSet(unfiltered, predicate); - } - - static <E> SortedSet<E> filterSortedIgnoreNavigable( - SortedSet<E> unfiltered, Predicate<? super E> predicate) { if (unfiltered instanceof FilteredSet) { // Support clear(), removeAll(), and retainAll() when filtering a filtered // collection. @@ -874,13 +826,21 @@ public final class Sets { checkNotNull(unfiltered), checkNotNull(predicate)); } - private static class FilteredSortedSet<E> extends FilteredSet<E> + private static class FilteredSortedSet<E> extends FilteredCollection<E> implements SortedSet<E> { FilteredSortedSet(SortedSet<E> unfiltered, Predicate<? super E> predicate) { super(unfiltered, predicate); } + @Override public boolean equals(@Nullable Object object) { + return equalsImpl(this, object); + } + + @Override public int hashCode() { + return hashCodeImpl(this); + } + @Override public Comparator<? super E> comparator() { return ((SortedSet<E>) unfiltered).comparator(); @@ -921,145 +881,6 @@ public final class Sets { } /** - * Returns the elements of a {@code NavigableSet}, {@code unfiltered}, that - * satisfy a predicate. The returned set is a live view of {@code unfiltered}; - * changes to one affect the other. - * - * <p>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. - * - * <p>The returned set isn't threadsafe or serializable, even if - * {@code unfiltered} is. - * - * <p>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 <i>not</i> needed, it may be faster to copy - * {@code Iterables.filter(unfiltered, predicate)} and use the copy. - * - * <p><b>Warning:</b> {@code predicate} must be <i>consistent with equals</i>, - * 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 14.0 - */ - @GwtIncompatible("NavigableSet") - @SuppressWarnings("unchecked") - public static <E> NavigableSet<E> filter( - NavigableSet<E> unfiltered, Predicate<? super E> predicate) { - if (unfiltered instanceof FilteredSet) { - // Support clear(), removeAll(), and retainAll() when filtering a filtered - // collection. - FilteredSet<E> filtered = (FilteredSet<E>) unfiltered; - Predicate<E> combinedPredicate - = Predicates.<E>and(filtered.predicate, predicate); - return new FilteredNavigableSet<E>( - (NavigableSet<E>) filtered.unfiltered, combinedPredicate); - } - - return new FilteredNavigableSet<E>( - checkNotNull(unfiltered), checkNotNull(predicate)); - } - - @GwtIncompatible("NavigableSet") - private static class FilteredNavigableSet<E> extends FilteredSortedSet<E> - implements NavigableSet<E> { - FilteredNavigableSet(NavigableSet<E> unfiltered, Predicate<? super E> predicate) { - super(unfiltered, predicate); - } - - NavigableSet<E> unfiltered() { - return (NavigableSet<E>) unfiltered; - } - - @Override - @Nullable - public E lower(E e) { - return Iterators.getNext(headSet(e, false).descendingIterator(), null); - } - - @Override - @Nullable - public E floor(E e) { - return Iterators.getNext(headSet(e, true).descendingIterator(), null); - } - - @Override - public E ceiling(E e) { - return Iterables.getFirst(tailSet(e, true), null); - } - - @Override - public E higher(E e) { - return Iterables.getFirst(tailSet(e, false), null); - } - - @Override - public E pollFirst() { - Iterator<E> unfilteredIterator = unfiltered().iterator(); - while (unfilteredIterator.hasNext()) { - E e = unfilteredIterator.next(); - if (predicate.apply(e)) { - unfilteredIterator.remove(); - return e; - } - } - return null; - } - - @Override - public E pollLast() { - Iterator<E> unfilteredIterator = unfiltered().descendingIterator(); - while (unfilteredIterator.hasNext()) { - E e = unfilteredIterator.next(); - if (predicate.apply(e)) { - unfilteredIterator.remove(); - return e; - } - } - return null; - } - - @Override - public NavigableSet<E> descendingSet() { - return Sets.filter(unfiltered().descendingSet(), predicate); - } - - @Override - public Iterator<E> descendingIterator() { - return Iterators.filter(unfiltered().descendingIterator(), predicate); - } - - @Override - public E last() { - return descendingIterator().next(); - } - - @Override - public NavigableSet<E> subSet( - E fromElement, boolean fromInclusive, E toElement, boolean toInclusive) { - return filter( - unfiltered().subSet(fromElement, fromInclusive, toElement, toInclusive), predicate); - } - - @Override - public NavigableSet<E> headSet(E toElement, boolean inclusive) { - return filter(unfiltered().headSet(toElement, inclusive), predicate); - } - - @Override - public NavigableSet<E> tailSet(E fromElement, boolean inclusive) { - return filter(unfiltered().tailSet(fromElement, inclusive), predicate); - } - } - - /** * Returns every possible list that can be formed by choosing one element * from each of the given sets in order; the "n-ary * <a href="http://en.wikipedia.org/wiki/Cartesian_product">Cartesian @@ -1080,22 +901,12 @@ public final class Sets { * <li>{@code ImmutableList.of(2, "C")} * </ul> * - * The result is guaranteed to be in the "traditional", lexicographical - * order for Cartesian products that you would get from nesting for loops: - * <pre> {@code - * - * for (B b0 : sets.get(0)) { - * for (B b1 : sets.get(1)) { - * ... - * ImmutableList<B> tuple = ImmutableList.of(b0, b1, ...); - * // operate on tuple - * } - * }}</pre> - * - * 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). + * 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). * * <p><i>Performance notes:</i> 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 @@ -1121,7 +932,8 @@ public final class Sets { return ImmutableSet.of(); } } - return CartesianSet.create(sets); + CartesianSet<B> cartesianSet = new CartesianSet<B>(sets); + return cartesianSet; } /** @@ -1145,22 +957,12 @@ public final class Sets { * <li>{@code ImmutableList.of(2, "C")} * </ul> * - * The result is guaranteed to be in the "traditional", lexicographical - * order for Cartesian products that you would get from nesting for loops: - * <pre> {@code - * - * for (B b0 : sets.get(0)) { - * for (B b1 : sets.get(1)) { - * ... - * ImmutableList<B> tuple = ImmutableList.of(b0, b1, ...); - * // operate on tuple - * } - * }}</pre> - * - * 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). + * 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). * * <p><i>Performance notes:</i> 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 @@ -1184,51 +986,73 @@ public final class Sets { return cartesianProduct(Arrays.asList(sets)); } - private static final class CartesianSet<E> - extends ForwardingCollection<List<E>> implements Set<List<E>> { - private transient final ImmutableList<ImmutableSet<E>> axes; - private transient final CartesianList<E> delegate; - - static <E> Set<List<E>> create(List<? extends Set<? extends E>> sets) { - ImmutableList.Builder<ImmutableSet<E>> axesBuilder = - new ImmutableList.Builder<ImmutableSet<E>>(sets.size()); - for (Set<? extends E> set : sets) { - ImmutableSet<E> copy = ImmutableSet.copyOf(set); - if (copy.isEmpty()) { - return ImmutableSet.of(); + private static class CartesianSet<B> extends AbstractSet<List<B>> { + final ImmutableList<Axis> axes; + final int size; + + CartesianSet(List<? extends Set<? extends B>> sets) { + int dividend = 1; + ImmutableList.Builder<Axis> builder = ImmutableList.builder(); + try { + for (Set<? extends B> set : sets) { + Axis axis = new Axis(set, dividend); + builder.add(axis); + dividend = IntMath.checkedMultiply(dividend, axis.size()); } - axesBuilder.add(copy); + } catch (ArithmeticException overflow) { + throw new IllegalArgumentException("cartesian product too big"); } - final ImmutableList<ImmutableSet<E>> axes = axesBuilder.build(); - ImmutableList<List<E>> listAxes = new ImmutableList<List<E>>() { + this.axes = builder.build(); + size = dividend; + } - @Override - public int size() { - return axes.size(); - } + @Override public int size() { + return size; + } + + @Override public UnmodifiableIterator<List<B>> iterator() { + return new UnmodifiableIterator<List<B>>() { + int index; @Override - public List<E> get(int index) { - return axes.get(index).asList(); + public boolean hasNext() { + return index < size; } @Override - boolean isPartialView() { - return true; + public List<B> 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<B> result = (ImmutableList<B>) ImmutableList.copyOf(tuple); + return result; } }; - return new CartesianSet<E>(axes, new CartesianList<E>(listAxes)); } - private CartesianSet( - ImmutableList<ImmutableSet<E>> axes, CartesianList<E> delegate) { - this.axes = axes; - this.delegate = delegate; - } - - @Override - protected Collection<List<E>> delegate() { - return delegate; + @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) { @@ -1241,26 +1065,56 @@ public final class Sets { return super.equals(object); } - @Override - public int hashCode() { + @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; + int adjust = size - 1; for (int i = 0; i < axes.size(); i++) { adjust *= 31; - adjust = ~~adjust; - // in GWT, we have to deal with integer overflow carefully } - int hash = 1; - for (Set<E> axis : axes) { - hash = 31 * hash + (size() / axis.size() * axis.hashCode()); + 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; + } - hash = ~~hash; + @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(); } - hash += adjust; - return ~~hash; } } @@ -1398,9 +1252,6 @@ public final class Sets { int hashCode = 0; for (Object o : s) { hashCode += o != null ? o.hashCode() : 0; - - hashCode = ~~hashCode; - // Needed to deal with unusual integer overflow in GWT. } return hashCode; } @@ -1427,345 +1278,117 @@ public final class Sets { } /** - * Returns an unmodifiable view of the specified navigable set. This method - * allows modules to provide users with "read-only" access to internal - * navigable sets. Query operations on the returned set "read through" to the - * specified set, and attempts to modify the returned set, whether direct or - * via its collection views, result in an - * {@code UnsupportedOperationException}. - * - * <p>The returned navigable set will be serializable if the specified - * navigable set is serializable. - * - * @param set the navigable set for which an unmodifiable view is to be - * returned - * @return an unmodifiable view of the specified navigable set - * @since 12.0 + * Creates a view of Set<B> for a Set<A>, given a bijection between A and B. + * (Modelled for now as InvertibleFunction<A, B>, can't be Converter<A, B> + * because that's not in Guava, though both designs are less than optimal). + * Note that the bijection is treated as undefined for values not in the + * given Set<A> - it doesn't have to define a true bijection for those. + * + * <p>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<A>. */ - @GwtIncompatible("NavigableSet") - public static <E> NavigableSet<E> unmodifiableNavigableSet( - NavigableSet<E> set) { - if (set instanceof ImmutableSortedSet - || set instanceof UnmodifiableNavigableSet) { - return set; - } - return new UnmodifiableNavigableSet<E>(set); + static <A, B> Set<B> transform( + Set<A> set, InvertibleFunction<A, B> bijection) { + return new TransformedSet<A, B>( + Preconditions.checkNotNull(set, "set"), + Preconditions.checkNotNull(bijection, "bijection") + ); } - @GwtIncompatible("NavigableSet") - static final class UnmodifiableNavigableSet<E> - extends ForwardingSortedSet<E> implements NavigableSet<E>, Serializable { - private final NavigableSet<E> delegate; - - UnmodifiableNavigableSet(NavigableSet<E> delegate) { - this.delegate = checkNotNull(delegate); - } - - @Override - protected SortedSet<E> delegate() { - return Collections.unmodifiableSortedSet(delegate); - } + /** + * Stop-gap measure since there is no bijection related type in Guava. + */ + abstract static class InvertibleFunction<A, B> implements Function<A, B> { + abstract A invert(B b); - @Override - public E lower(E e) { - return delegate.lower(e); - } + public InvertibleFunction<B, A> inverse() { + return new InvertibleFunction<B, A>() { + @Override public A apply(B b) { + return InvertibleFunction.this.invert(b); + } - @Override - public E floor(E e) { - return delegate.floor(e); - } + @Override B invert(A a) { + return InvertibleFunction.this.apply(a); + } - @Override - public E ceiling(E e) { - return delegate.ceiling(e); + // Not required per se, but just for good karma. + @Override public InvertibleFunction<A, B> inverse() { + return InvertibleFunction.this; + } + }; } + } - @Override - public E higher(E e) { - return delegate.higher(e); - } + private static class TransformedSet<A, B> extends AbstractSet<B> { + final Set<A> delegate; + final InvertibleFunction<A, B> bijection; - @Override - public E pollFirst() { - throw new UnsupportedOperationException(); + TransformedSet(Set<A> delegate, InvertibleFunction<A, B> bijection) { + this.delegate = delegate; + this.bijection = bijection; } - @Override - public E pollLast() { - throw new UnsupportedOperationException(); + @Override public Iterator<B> iterator() { + return Iterators.transform(delegate.iterator(), bijection); } - private transient UnmodifiableNavigableSet<E> descendingSet; - - @Override - public NavigableSet<E> descendingSet() { - UnmodifiableNavigableSet<E> result = descendingSet; - if (result == null) { - result = descendingSet = new UnmodifiableNavigableSet<E>( - delegate.descendingSet()); - result.descendingSet = this; - } - return result; + @Override public int size() { + return delegate.size(); } - @Override - public Iterator<E> descendingIterator() { - return Iterators.unmodifiableIterator(delegate.descendingIterator()); + @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<A, B> 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<A> 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<A> + * or B's not in this Set<B>. + * + * 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<A>. + * + * The first test is whether the inverse image of this B is indeed + * in Set<A>. But we don't know whether that B belongs in this Set<B> + * or not; if not, the converter is free to return + * anything it wants, even an element of Set<A> (and this relationship + * is not part of the Set<A> <--> Set<B> 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<A>. + */ + return delegate.contains(a) && Objects.equal(bijection.apply(a), o); } - @Override - public NavigableSet<E> subSet( - E fromElement, - boolean fromInclusive, - E toElement, - boolean toInclusive) { - return unmodifiableNavigableSet(delegate.subSet( - fromElement, - fromInclusive, - toElement, - toInclusive)); + @Override public boolean add(B b) { + return delegate.add(bijection.invert(b)); } - @Override - public NavigableSet<E> headSet(E toElement, boolean inclusive) { - return unmodifiableNavigableSet(delegate.headSet(toElement, inclusive)); + @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 NavigableSet<E> tailSet(E fromElement, boolean inclusive) { - return unmodifiableNavigableSet( - delegate.tailSet(fromElement, inclusive)); + @Override public void clear() { + delegate.clear(); } - - private static final long serialVersionUID = 0; - } - - /** - * Returns a synchronized (thread-safe) navigable set backed by the specified - * navigable set. In order to guarantee serial access, it is critical that - * <b>all</b> access to the backing navigable set is accomplished - * through the returned navigable set (or its views). - * - * <p>It is imperative that the user manually synchronize on the returned - * sorted set when iterating over it or any of its {@code descendingSet}, - * {@code subSet}, {@code headSet}, or {@code tailSet} views. <pre> {@code - * - * NavigableSet<E> set = synchronizedNavigableSet(new TreeSet<E>()); - * ... - * synchronized (set) { - * // Must be in the synchronized block - * Iterator<E> it = set.iterator(); - * while (it.hasNext()){ - * foo(it.next()); - * } - * }}</pre> - * - * or: <pre> {@code - * - * NavigableSet<E> set = synchronizedNavigableSet(new TreeSet<E>()); - * NavigableSet<E> set2 = set.descendingSet().headSet(foo); - * ... - * synchronized (set) { // Note: set, not set2!!! - * // Must be in the synchronized block - * Iterator<E> it = set2.descendingIterator(); - * while (it.hasNext()) - * foo(it.next()); - * } - * }}</pre> - * - * Failure to follow this advice may result in non-deterministic behavior. - * - * <p>The returned navigable set will be serializable if the specified - * navigable set is serializable. - * - * @param navigableSet the navigable set to be "wrapped" in a synchronized - * navigable set. - * @return a synchronized view of the specified navigable set. - * @since 13.0 - */ - @GwtIncompatible("NavigableSet") - public static <E> NavigableSet<E> synchronizedNavigableSet( - NavigableSet<E> navigableSet) { - return Synchronized.navigableSet(navigableSet); } /** * Remove each element in an iterable from a set. */ - static boolean removeAllImpl(Set<?> set, Iterator<?> iterator) { + static boolean removeAllImpl(Set<?> set, Iterable<?> iterable) { + // TODO(jlevy): Have ForwardingSet.standardRemoveAll() call this method. boolean changed = false; - while (iterator.hasNext()) { - changed |= set.remove(iterator.next()); + for (Object o : iterable) { + changed |= set.remove(o); } return changed; } - - static boolean removeAllImpl(Set<?> set, Collection<?> collection) { - checkNotNull(collection); // for GWT - if (collection instanceof Multiset) { - collection = ((Multiset<?>) collection).elementSet(); - } - /* - * AbstractSet.removeAll(List) has quadratic behavior if the list size - * is just less than the set's size. We augment the test by - * assuming that sets have fast contains() performance, and other - * collections don't. See - * http://code.google.com/p/guava-libraries/issues/detail?id=1013 - */ - if (collection instanceof Set && collection.size() > set.size()) { - Iterator<?> setIterator = set.iterator(); - boolean changed = false; - while (setIterator.hasNext()) { - if (collection.contains(setIterator.next())) { - changed = true; - setIterator.remove(); - } - } - return changed; - } else { - return removeAllImpl(set, collection.iterator()); - } - } - - @GwtIncompatible("NavigableSet") - static class DescendingSet<E> extends ForwardingNavigableSet<E> { - private final NavigableSet<E> forward; - - DescendingSet(NavigableSet<E> forward) { - this.forward = forward; - } - - @Override - protected NavigableSet<E> delegate() { - return forward; - } - - @Override - public E lower(E e) { - return forward.higher(e); - } - - @Override - public E floor(E e) { - return forward.ceiling(e); - } - - @Override - public E ceiling(E e) { - return forward.floor(e); - } - - @Override - public E higher(E e) { - return forward.lower(e); - } - - @Override - public E pollFirst() { - return forward.pollLast(); - } - - @Override - public E pollLast() { - return forward.pollFirst(); - } - - @Override - public NavigableSet<E> descendingSet() { - return forward; - } - - @Override - public Iterator<E> descendingIterator() { - return forward.iterator(); - } - - @Override - public NavigableSet<E> subSet( - E fromElement, - boolean fromInclusive, - E toElement, - boolean toInclusive) { - return forward.subSet(toElement, toInclusive, fromElement, fromInclusive).descendingSet(); - } - - @Override - public NavigableSet<E> headSet(E toElement, boolean inclusive) { - return forward.tailSet(toElement, inclusive).descendingSet(); - } - - @Override - public NavigableSet<E> tailSet(E fromElement, boolean inclusive) { - return forward.headSet(fromElement, inclusive).descendingSet(); - } - - @SuppressWarnings("unchecked") - @Override - public Comparator<? super E> comparator() { - Comparator<? super E> forwardComparator = forward.comparator(); - if (forwardComparator == null) { - return (Comparator) Ordering.natural().reverse(); - } else { - return reverse(forwardComparator); - } - } - - // If we inline this, we get a javac error. - private static <T> Ordering<T> reverse(Comparator<T> forward) { - return Ordering.from(forward).reverse(); - } - - @Override - public E first() { - return forward.last(); - } - - @Override - public SortedSet<E> headSet(E toElement) { - return standardHeadSet(toElement); - } - - @Override - public E last() { - return forward.first(); - } - - @Override - public SortedSet<E> subSet(E fromElement, E toElement) { - return standardSubSet(fromElement, toElement); - } - - @Override - public SortedSet<E> tailSet(E fromElement) { - return standardTailSet(fromElement); - } - - @Override - public Iterator<E> iterator() { - return forward.descendingIterator(); - } - - @Override - public Object[] toArray() { - return standardToArray(); - } - - @Override - public <T> T[] toArray(T[] array) { - return standardToArray(array); - } - - @Override - public String toString() { - return standardToString(); - } - } - - /** - * Used to avoid http://bugs.sun.com/view_bug.do?bug_id=6558557 - */ - static <T> SortedSet<T> cast(Iterable<T> iterable) { - return (SortedSet<T>) iterable; - } } |