| /* |
| * Copyright (C) 2011 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.GwtIncompatible; |
| |
| import java.io.Serializable; |
| import java.util.Arrays; |
| import java.util.Collection; |
| import java.util.Collections; |
| import java.util.Comparator; |
| import java.util.Iterator; |
| import java.util.List; |
| |
| /** |
| * An immutable {@code SortedMultiset} that stores its elements in a sorted array. Some instances |
| * are ordered by an explicit comparator, while others follow the natural sort ordering of their |
| * elements. Either way, null elements are not supported. |
| * |
| * <p>Unlike {@link Multisets#unmodifiableSortedMultiset}, which is a <i>view</i> of a separate |
| * collection that can still change, an instance of {@code ImmutableSortedMultiset} contains its |
| * own private data and will <i>never</i> change. This class is convenient for {@code public static |
| * final} multisets ("constant multisets") and also lets you easily make a "defensive copy" of a |
| * set provided to your class by a caller. |
| * |
| * <p>The multisets returned by the {@link #headMultiset}, {@link #tailMultiset}, and |
| * {@link #subMultiset} methods share the same array as the original multiset, preventing that |
| * array from being garbage collected. If this is a concern, the data may be copied into a |
| * correctly-sized array by calling {@link #copyOfSorted}. |
| * |
| * <p><b>Note on element equivalence:</b> The {@link #contains(Object)}, |
| * {@link #containsAll(Collection)}, and {@link #equals(Object)} implementations must check whether |
| * a provided object is equivalent to an element in the collection. Unlike most collections, an |
| * {@code ImmutableSortedMultiset} doesn't use {@link Object#equals} to determine if two elements |
| * are equivalent. Instead, with an explicit comparator, the following relation determines whether |
| * elements {@code x} and {@code y} are equivalent: |
| * |
| * <pre> {@code |
| * |
| * {(x, y) | comparator.compare(x, y) == 0}}</pre> |
| * |
| * <p>With natural ordering of elements, the following relation determines whether two elements are |
| * equivalent: |
| * |
| * <pre> {@code |
| * |
| * {(x, y) | x.compareTo(y) == 0}}</pre> |
| * |
| * <b>Warning:</b> Like most multisets, an {@code ImmutableSortedMultiset} will not function |
| * correctly if an element is modified after being placed in the multiset. For this reason, and to |
| * avoid general confusion, it is strongly recommended to place only immutable objects into this |
| * collection. |
| * |
| * <p><b>Note:</b> Although this class is not final, it cannot be subclassed as it has no public or |
| * protected constructors. Thus, instances of this type are guaranteed to be immutable. |
| * |
| * <p>See the Guava User Guide article on <a href= |
| * "http://code.google.com/p/guava-libraries/wiki/ImmutableCollectionsExplained"> |
| * immutable collections</a>. |
| * |
| * @author Louis Wasserman |
| * @since 12.0 |
| */ |
| @Beta |
| @GwtIncompatible("hasn't been tested yet") |
| public abstract class ImmutableSortedMultiset<E> extends ImmutableSortedMultisetFauxverideShim<E> |
| implements SortedMultiset<E> { |
| // TODO(user): GWT compatibility |
| |
| private static final Comparator<Comparable> NATURAL_ORDER = Ordering.natural(); |
| |
| private static final ImmutableSortedMultiset<Comparable> NATURAL_EMPTY_MULTISET = |
| new EmptyImmutableSortedMultiset<Comparable>(NATURAL_ORDER); |
| |
| /** |
| * Returns the empty immutable sorted multiset. |
| */ |
| @SuppressWarnings("unchecked") |
| public static <E> ImmutableSortedMultiset<E> of() { |
| return (ImmutableSortedMultiset) NATURAL_EMPTY_MULTISET; |
| } |
| |
| /** |
| * Returns an immutable sorted multiset containing a single element. |
| */ |
| public static <E extends Comparable<? super E>> ImmutableSortedMultiset<E> of(E element) { |
| RegularImmutableSortedSet<E> elementSet = |
| (RegularImmutableSortedSet<E>) ImmutableSortedSet.of(element); |
| int[] counts = {1}; |
| long[] cumulativeCounts = {0, 1}; |
| return new RegularImmutableSortedMultiset<E>(elementSet, counts, cumulativeCounts, 0, 1); |
| } |
| |
| /** |
| * Returns an immutable sorted multiset containing the given elements sorted by their natural |
| * ordering. |
| * |
| * @throws NullPointerException if any element is null |
| */ |
| @SuppressWarnings("unchecked") |
| public static <E extends Comparable<? super E>> ImmutableSortedMultiset<E> of(E e1, E e2) { |
| return copyOf(Ordering.natural(), Arrays.asList(e1, e2)); |
| } |
| |
| /** |
| * Returns an immutable sorted multiset containing the given elements sorted by their natural |
| * ordering. |
| * |
| * @throws NullPointerException if any element is null |
| */ |
| @SuppressWarnings("unchecked") |
| public static <E extends Comparable<? super E>> ImmutableSortedMultiset<E> of(E e1, E e2, E e3) { |
| return copyOf(Ordering.natural(), Arrays.asList(e1, e2, e3)); |
| } |
| |
| /** |
| * Returns an immutable sorted multiset containing the given elements sorted by their natural |
| * ordering. |
| * |
| * @throws NullPointerException if any element is null |
| */ |
| @SuppressWarnings("unchecked") |
| public static <E extends Comparable<? super E>> ImmutableSortedMultiset<E> of( |
| E e1, E e2, E e3, E e4) { |
| return copyOf(Ordering.natural(), Arrays.asList(e1, e2, e3, e4)); |
| } |
| |
| /** |
| * Returns an immutable sorted multiset containing the given elements sorted by their natural |
| * ordering. |
| * |
| * @throws NullPointerException if any element is null |
| */ |
| @SuppressWarnings("unchecked") |
| public static <E extends Comparable<? super E>> ImmutableSortedMultiset<E> of( |
| E e1, E e2, E e3, E e4, E e5) { |
| return copyOf(Ordering.natural(), Arrays.asList(e1, e2, e3, e4, e5)); |
| } |
| |
| /** |
| * Returns an immutable sorted multiset containing the given elements sorted by their natural |
| * ordering. |
| * |
| * @throws NullPointerException if any element is null |
| */ |
| @SuppressWarnings("unchecked") |
| public static <E extends Comparable<? super E>> ImmutableSortedMultiset<E> of( |
| E e1, E e2, E e3, E e4, E e5, E e6, E... remaining) { |
| int size = remaining.length + 6; |
| List<E> all = Lists.newArrayListWithCapacity(size); |
| Collections.addAll(all, e1, e2, e3, e4, e5, e6); |
| Collections.addAll(all, remaining); |
| return copyOf(Ordering.natural(), all); |
| } |
| |
| /** |
| * Returns an immutable sorted multiset containing the given elements sorted by their natural |
| * ordering. |
| * |
| * @throws NullPointerException if any of {@code elements} is null |
| */ |
| public static <E extends Comparable<? super E>> ImmutableSortedMultiset<E> copyOf(E[] elements) { |
| return copyOf(Ordering.natural(), Arrays.asList(elements)); |
| } |
| |
| /** |
| * Returns an immutable sorted multiset containing the given elements sorted by their natural |
| * ordering. To create a copy of a {@code SortedMultiset} that preserves the |
| * comparator, call {@link #copyOfSorted} instead. This method iterates over {@code elements} at |
| * most once. |
| * |
| * <p>Note that if {@code s} is a {@code multiset<String>}, then {@code |
| * ImmutableSortedMultiset.copyOf(s)} returns an {@code ImmutableSortedMultiset<String>} |
| * containing each of the strings in {@code s}, while {@code ImmutableSortedMultiset.of(s)} |
| * returns an {@code ImmutableSortedMultiset<multiset<String>>} containing one element (the given |
| * multiset itself). |
| * |
| * <p>Despite the method name, this method attempts to avoid actually copying the data when it is |
| * safe to do so. The exact circumstances under which a copy will or will not be performed are |
| * undocumented and subject to change. |
| * |
| * <p>This method is not type-safe, as it may be called on elements that are not mutually |
| * comparable. |
| * |
| * @throws ClassCastException if the elements are not mutually comparable |
| * @throws NullPointerException if any of {@code elements} is null |
| */ |
| public static <E> ImmutableSortedMultiset<E> copyOf(Iterable<? extends E> elements) { |
| // Hack around E not being a subtype of Comparable. |
| // Unsafe, see ImmutableSortedMultisetFauxverideShim. |
| @SuppressWarnings("unchecked") |
| Ordering<E> naturalOrder = (Ordering<E>) Ordering.<Comparable>natural(); |
| return copyOf(naturalOrder, elements); |
| } |
| |
| /** |
| * Returns an immutable sorted multiset containing the given elements sorted by their natural |
| * ordering. |
| * |
| * <p>This method is not type-safe, as it may be called on elements that are not mutually |
| * comparable. |
| * |
| * @throws ClassCastException if the elements are not mutually comparable |
| * @throws NullPointerException if any of {@code elements} is null |
| */ |
| public static <E> ImmutableSortedMultiset<E> copyOf(Iterator<? extends E> elements) { |
| // Hack around E not being a subtype of Comparable. |
| // Unsafe, see ImmutableSortedMultisetFauxverideShim. |
| @SuppressWarnings("unchecked") |
| Ordering<E> naturalOrder = (Ordering<E>) Ordering.<Comparable>natural(); |
| return copyOf(naturalOrder, elements); |
| } |
| |
| /** |
| * Returns an immutable sorted multiset containing the given elements sorted by the given {@code |
| * Comparator}. |
| * |
| * @throws NullPointerException if {@code comparator} or any of {@code elements} is null |
| */ |
| public static <E> ImmutableSortedMultiset<E> copyOf( |
| Comparator<? super E> comparator, Iterator<? extends E> elements) { |
| checkNotNull(comparator); |
| return new Builder<E>(comparator).addAll(elements).build(); |
| } |
| |
| /** |
| * Returns an immutable sorted multiset containing the given elements sorted by the given {@code |
| * Comparator}. This method iterates over {@code elements} at most once. |
| * |
| * <p>Despite the method name, this method attempts to avoid actually copying the data when it is |
| * safe to do so. The exact circumstances under which a copy will or will not be performed are |
| * undocumented and subject to change. |
| * |
| * @throws NullPointerException if {@code comparator} or any of {@code elements} is null |
| */ |
| public static <E> ImmutableSortedMultiset<E> copyOf( |
| Comparator<? super E> comparator, Iterable<? extends E> elements) { |
| if (elements instanceof ImmutableSortedMultiset) { |
| @SuppressWarnings("unchecked") // immutable collections are always safe for covariant casts |
| ImmutableSortedMultiset<E> multiset = (ImmutableSortedMultiset<E>) elements; |
| if (comparator.equals(multiset.comparator())) { |
| if (multiset.isPartialView()) { |
| return copyOfSortedEntries(comparator, multiset.entrySet().asList()); |
| } else { |
| return multiset; |
| } |
| } |
| } |
| elements = Lists.newArrayList(elements); // defensive copy |
| TreeMultiset<E> sortedCopy = TreeMultiset.create(checkNotNull(comparator)); |
| Iterables.addAll(sortedCopy, elements); |
| return copyOfSortedEntries(comparator, sortedCopy.entrySet()); |
| } |
| |
| /** |
| * Returns an immutable sorted multiset containing the elements of a sorted multiset, sorted by |
| * the same {@code Comparator}. That behavior differs from {@link #copyOf(Iterable)}, which |
| * always uses the natural ordering of the elements. |
| * |
| * <p>Despite the method name, this method attempts to avoid actually copying the data when it is |
| * safe to do so. The exact circumstances under which a copy will or will not be performed are |
| * undocumented and subject to change. |
| * |
| * <p>This method is safe to use even when {@code sortedMultiset} is a synchronized or concurrent |
| * collection that is currently being modified by another thread. |
| * |
| * @throws NullPointerException if {@code sortedMultiset} or any of its elements is null |
| */ |
| public static <E> ImmutableSortedMultiset<E> copyOfSorted(SortedMultiset<E> sortedMultiset) { |
| return copyOfSortedEntries(sortedMultiset.comparator(), |
| Lists.newArrayList(sortedMultiset.entrySet())); |
| } |
| |
| private static <E> ImmutableSortedMultiset<E> copyOfSortedEntries( |
| Comparator<? super E> comparator, Collection<Entry<E>> entries) { |
| if (entries.isEmpty()) { |
| return emptyMultiset(comparator); |
| } |
| ImmutableList.Builder<E> elementsBuilder = new ImmutableList.Builder<E>(entries.size()); |
| int[] counts = new int[entries.size()]; |
| long[] cumulativeCounts = new long[entries.size() + 1]; |
| int i = 0; |
| for (Entry<E> entry : entries) { |
| elementsBuilder.add(entry.getElement()); |
| counts[i] = entry.getCount(); |
| cumulativeCounts[i + 1] = cumulativeCounts[i] + counts[i]; |
| i++; |
| } |
| return new RegularImmutableSortedMultiset<E>( |
| new RegularImmutableSortedSet<E>(elementsBuilder.build(), comparator), |
| counts, cumulativeCounts, 0, entries.size()); |
| } |
| |
| @SuppressWarnings("unchecked") |
| static <E> ImmutableSortedMultiset<E> emptyMultiset(Comparator<? super E> comparator) { |
| if (NATURAL_ORDER.equals(comparator)) { |
| return (ImmutableSortedMultiset) NATURAL_EMPTY_MULTISET; |
| } |
| return new EmptyImmutableSortedMultiset<E>(comparator); |
| } |
| |
| ImmutableSortedMultiset() {} |
| |
| @Override |
| public final Comparator<? super E> comparator() { |
| return elementSet().comparator(); |
| } |
| |
| @Override |
| public abstract ImmutableSortedSet<E> elementSet(); |
| |
| transient ImmutableSortedMultiset<E> descendingMultiset; |
| |
| @Override |
| public ImmutableSortedMultiset<E> descendingMultiset() { |
| ImmutableSortedMultiset<E> result = descendingMultiset; |
| if (result == null) { |
| return descendingMultiset = new DescendingImmutableSortedMultiset<E>(this); |
| } |
| return result; |
| } |
| |
| /** |
| * {@inheritDoc} |
| * |
| * <p>This implementation is guaranteed to throw an {@link UnsupportedOperationException}. |
| * |
| * @throws UnsupportedOperationException always |
| * @deprecated Unsupported operation. |
| */ |
| @Deprecated |
| @Override |
| public final Entry<E> pollFirstEntry() { |
| throw new UnsupportedOperationException(); |
| } |
| |
| /** |
| * {@inheritDoc} |
| * |
| * <p>This implementation is guaranteed to throw an {@link UnsupportedOperationException}. |
| * |
| * @throws UnsupportedOperationException always |
| * @deprecated Unsupported operation. |
| */ |
| @Deprecated |
| @Override |
| public final Entry<E> pollLastEntry() { |
| throw new UnsupportedOperationException(); |
| } |
| |
| @Override |
| public abstract ImmutableSortedMultiset<E> headMultiset(E upperBound, BoundType boundType); |
| |
| @Override |
| public ImmutableSortedMultiset<E> subMultiset( |
| E lowerBound, BoundType lowerBoundType, E upperBound, BoundType upperBoundType) { |
| checkArgument(comparator().compare(lowerBound, upperBound) <= 0, |
| "Expected lowerBound <= upperBound but %s > %s", lowerBound, upperBound); |
| return tailMultiset(lowerBound, lowerBoundType).headMultiset(upperBound, upperBoundType); |
| } |
| |
| @Override |
| public abstract ImmutableSortedMultiset<E> tailMultiset(E lowerBound, BoundType boundType); |
| |
| /** |
| * Returns a builder that creates immutable sorted multisets with an explicit comparator. If the |
| * comparator has a more general type than the set being generated, such as creating a {@code |
| * SortedMultiset<Integer>} with a {@code Comparator<Number>}, use the {@link Builder} |
| * constructor instead. |
| * |
| * @throws NullPointerException if {@code comparator} is null |
| */ |
| public static <E> Builder<E> orderedBy(Comparator<E> comparator) { |
| return new Builder<E>(comparator); |
| } |
| |
| /** |
| * Returns a builder that creates immutable sorted multisets whose elements are ordered by the |
| * reverse of their natural ordering. |
| * |
| * <p>Note: the type parameter {@code E} extends {@code Comparable<E>} rather than {@code |
| * Comparable<? super E>} as a workaround for javac <a |
| * href="http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=6468354">bug 6468354</a>. |
| */ |
| public static <E extends Comparable<E>> Builder<E> reverseOrder() { |
| return new Builder<E>(Ordering.natural().reverse()); |
| } |
| |
| /** |
| * Returns a builder that creates immutable sorted multisets whose elements are ordered by their |
| * natural ordering. The sorted multisets use {@link Ordering#natural()} as the comparator. This |
| * method provides more type-safety than {@link #builder}, as it can be called only for classes |
| * that implement {@link Comparable}. |
| * |
| * <p>Note: the type parameter {@code E} extends {@code Comparable<E>} rather than {@code |
| * Comparable<? super E>} as a workaround for javac <a |
| * href="http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=6468354">bug 6468354</a>. |
| */ |
| public static <E extends Comparable<E>> Builder<E> naturalOrder() { |
| return new Builder<E>(Ordering.natural()); |
| } |
| |
| /** |
| * A builder for creating immutable multiset instances, especially {@code public static final} |
| * multisets ("constant multisets"). Example: |
| * |
| * <pre> {@code |
| * |
| * public static final ImmutableSortedMultiset<Bean> BEANS = |
| * new ImmutableSortedMultiset.Builder<Bean>() |
| * .addCopies(Bean.COCOA, 4) |
| * .addCopies(Bean.GARDEN, 6) |
| * .addCopies(Bean.RED, 8) |
| * .addCopies(Bean.BLACK_EYED, 10) |
| * .build();}</pre> |
| * |
| * <p>Builder instances can be reused; it is safe to call {@link #build} multiple times to build |
| * multiple multisets in series. |
| * |
| * @since 12.0 |
| */ |
| public static class Builder<E> extends ImmutableMultiset.Builder<E> { |
| /** |
| * Creates a new builder. The returned builder is equivalent to the builder generated by |
| * {@link ImmutableSortedMultiset#orderedBy(Comparator)}. |
| */ |
| public Builder(Comparator<? super E> comparator) { |
| super(TreeMultiset.<E>create(checkNotNull(comparator))); |
| } |
| |
| /** |
| * Adds {@code element} to the {@code ImmutableSortedMultiset}. |
| * |
| * @param element the element to add |
| * @return this {@code Builder} object |
| * @throws NullPointerException if {@code element} is null |
| */ |
| @Override |
| public Builder<E> add(E element) { |
| super.add(element); |
| return this; |
| } |
| |
| /** |
| * Adds a number of occurrences of an element to this {@code ImmutableSortedMultiset}. |
| * |
| * @param element the element to add |
| * @param occurrences the number of occurrences of the element to add. May be zero, in which |
| * case no change will be made. |
| * @return this {@code Builder} object |
| * @throws NullPointerException if {@code element} is null |
| * @throws IllegalArgumentException if {@code occurrences} is negative, or if this operation |
| * would result in more than {@link Integer#MAX_VALUE} occurrences of the element |
| */ |
| @Override |
| public Builder<E> addCopies(E element, int occurrences) { |
| super.addCopies(element, occurrences); |
| return this; |
| } |
| |
| /** |
| * Adds or removes the necessary occurrences of an element such that the element attains the |
| * desired count. |
| * |
| * @param element the element to add or remove occurrences of |
| * @param count the desired count of the element in this multiset |
| * @return this {@code Builder} object |
| * @throws NullPointerException if {@code element} is null |
| * @throws IllegalArgumentException if {@code count} is negative |
| */ |
| @Override |
| public Builder<E> setCount(E element, int count) { |
| super.setCount(element, count); |
| return this; |
| } |
| |
| /** |
| * Adds each element of {@code elements} to the {@code ImmutableSortedMultiset}. |
| * |
| * @param elements the elements to add |
| * @return this {@code Builder} object |
| * @throws NullPointerException if {@code elements} is null or contains a null element |
| */ |
| @Override |
| public Builder<E> add(E... elements) { |
| super.add(elements); |
| return this; |
| } |
| |
| /** |
| * Adds each element of {@code elements} to the {@code ImmutableSortedMultiset}. |
| * |
| * @param elements the {@code Iterable} to add to the {@code ImmutableSortedMultiset} |
| * @return this {@code Builder} object |
| * @throws NullPointerException if {@code elements} is null or contains a null element |
| */ |
| @Override |
| public Builder<E> addAll(Iterable<? extends E> elements) { |
| super.addAll(elements); |
| return this; |
| } |
| |
| /** |
| * Adds each element of {@code elements} to the {@code ImmutableSortedMultiset}. |
| * |
| * @param elements the elements to add to the {@code ImmutableSortedMultiset} |
| * @return this {@code Builder} object |
| * @throws NullPointerException if {@code elements} is null or contains a null element |
| */ |
| @Override |
| public Builder<E> addAll(Iterator<? extends E> elements) { |
| super.addAll(elements); |
| return this; |
| } |
| |
| /** |
| * Returns a newly-created {@code ImmutableSortedMultiset} based on the contents of the {@code |
| * Builder}. |
| */ |
| @Override |
| public ImmutableSortedMultiset<E> build() { |
| return copyOfSorted((SortedMultiset<E>) contents); |
| } |
| } |
| |
| private static final class SerializedForm<E> implements Serializable { |
| Comparator<? super E> comparator; |
| E[] elements; |
| int[] counts; |
| |
| @SuppressWarnings("unchecked") |
| SerializedForm(SortedMultiset<E> multiset) { |
| this.comparator = multiset.comparator(); |
| int n = multiset.entrySet().size(); |
| elements = (E[]) new Object[n]; |
| counts = new int[n]; |
| int i = 0; |
| for (Entry<E> entry : multiset.entrySet()) { |
| elements[i] = entry.getElement(); |
| counts[i] = entry.getCount(); |
| i++; |
| } |
| } |
| |
| Object readResolve() { |
| int n = elements.length; |
| Builder<E> builder = new Builder<E>(comparator); |
| for (int i = 0; i < n; i++) { |
| builder.addCopies(elements[i], counts[i]); |
| } |
| return builder.build(); |
| } |
| } |
| |
| @Override |
| Object writeReplace() { |
| return new SerializedForm<E>(this); |
| } |
| } |