604 lines
17 KiB
Java
604 lines
17 KiB
Java
/*
|
|
* Copyright (C) 2008 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.checkNotNull;
|
|
|
|
import java.io.Serializable;
|
|
import java.util.Arrays;
|
|
import java.util.Collection;
|
|
import java.util.Iterator;
|
|
|
|
import javax.annotation.Nullable;
|
|
|
|
import com.google.common.annotations.GwtCompatible;
|
|
import com.google.common.annotations.GwtIncompatible;
|
|
import com.google.common.primitives.Ints;
|
|
|
|
/**
|
|
* An immutable hash-based multiset. Does not permit null elements.
|
|
*
|
|
* <p>
|
|
* Its iterator orders elements according to the first appearance of the element
|
|
* among the items passed to the factory method or builder. When the multiset
|
|
* contains multiple instances of an element, those instances are consecutive in
|
|
* the iteration order.
|
|
*
|
|
* <p>
|
|
* See the Guava User Guide article on <a href=
|
|
* "http://code.google.com/p/guava-libraries/wiki/ImmutableCollectionsExplained">
|
|
* immutable collections</a>.
|
|
*
|
|
* @author Jared Levy
|
|
* @author Louis Wasserman
|
|
* @since 2.0 (imported from Google Collections Library)
|
|
*/
|
|
@GwtCompatible(serializable = true, emulated = true)
|
|
@SuppressWarnings("serial") // we're overriding default serialization
|
|
// TODO(user): write an efficient asList() implementation
|
|
public abstract class ImmutableMultiset<E> extends ImmutableCollection<E> implements Multiset<E> {
|
|
|
|
private static final ImmutableMultiset<Object> EMPTY = new RegularImmutableMultiset<Object>(
|
|
ImmutableMap.<Object, Integer>of(), 0);
|
|
|
|
/**
|
|
* Returns the empty immutable multiset.
|
|
*/
|
|
@SuppressWarnings("unchecked") // all supported methods are covariant
|
|
public static <E> ImmutableMultiset<E> of() {
|
|
return (ImmutableMultiset<E>) EMPTY;
|
|
}
|
|
|
|
/**
|
|
* Returns an immutable multiset containing a single element.
|
|
*
|
|
* @throws NullPointerException if {@code element} is null
|
|
* @since 6.0 (source-compatible since 2.0)
|
|
*/
|
|
@SuppressWarnings("unchecked") // generic array created but never written
|
|
public static <E> ImmutableMultiset<E> of(E element) {
|
|
return copyOfInternal(element);
|
|
}
|
|
|
|
/**
|
|
* Returns an immutable multiset containing the given elements, in order.
|
|
*
|
|
* @throws NullPointerException if any element is null
|
|
* @since 6.0 (source-compatible since 2.0)
|
|
*/
|
|
@SuppressWarnings("unchecked") //
|
|
public static <E> ImmutableMultiset<E> of(E e1, E e2) {
|
|
return copyOfInternal(e1, e2);
|
|
}
|
|
|
|
/**
|
|
* Returns an immutable multiset containing the given elements, in order.
|
|
*
|
|
* @throws NullPointerException if any element is null
|
|
* @since 6.0 (source-compatible since 2.0)
|
|
*/
|
|
@SuppressWarnings("unchecked") //
|
|
public static <E> ImmutableMultiset<E> of(E e1, E e2, E e3) {
|
|
return copyOfInternal(e1, e2, e3);
|
|
}
|
|
|
|
/**
|
|
* Returns an immutable multiset containing the given elements, in order.
|
|
*
|
|
* @throws NullPointerException if any element is null
|
|
* @since 6.0 (source-compatible since 2.0)
|
|
*/
|
|
@SuppressWarnings("unchecked") //
|
|
public static <E> ImmutableMultiset<E> of(E e1, E e2, E e3, E e4) {
|
|
return copyOfInternal(e1, e2, e3, e4);
|
|
}
|
|
|
|
/**
|
|
* Returns an immutable multiset containing the given elements, in order.
|
|
*
|
|
* @throws NullPointerException if any element is null
|
|
* @since 6.0 (source-compatible since 2.0)
|
|
*/
|
|
@SuppressWarnings("unchecked") //
|
|
public static <E> ImmutableMultiset<E> of(E e1, E e2, E e3, E e4, E e5) {
|
|
return copyOfInternal(e1, e2, e3, e4, e5);
|
|
}
|
|
|
|
/**
|
|
* Returns an immutable multiset containing the given elements, in order.
|
|
*
|
|
* @throws NullPointerException if any element is null
|
|
* @since 6.0 (source-compatible since 2.0)
|
|
*/
|
|
@SuppressWarnings("unchecked") //
|
|
public static <E> ImmutableMultiset<E> of(E e1, E e2, E e3, E e4, E e5, E e6, E... others) {
|
|
return new Builder<E>().add(e1).add(e2).add(e3).add(e4).add(e5).add(e6).add(others).build();
|
|
}
|
|
|
|
/**
|
|
* Returns an immutable multiset containing the given elements.
|
|
*
|
|
* <p>
|
|
* The multiset is ordered by the first occurrence of each element. For example,
|
|
* {@code ImmutableMultiset.copyOf([2, 3, 1, 3])} yields a multiset with
|
|
* elements in the order {@code 2, 3, 3, 1}.
|
|
*
|
|
* @throws NullPointerException if any of {@code elements} is null
|
|
* @since 6.0
|
|
*/
|
|
public static <E> ImmutableMultiset<E> copyOf(E[] elements) {
|
|
return copyOf(Arrays.asList(elements));
|
|
}
|
|
|
|
/**
|
|
* Returns an immutable multiset containing the given elements.
|
|
*
|
|
* <p>
|
|
* The multiset is ordered by the first occurrence of each element. For example,
|
|
* {@code ImmutableMultiset.copyOf(Arrays.asList(2, 3, 1, 3))} yields a multiset
|
|
* with elements in the order {@code 2, 3, 3, 1}.
|
|
*
|
|
* <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>
|
|
* <b>Note:</b> Despite what the method name suggests, if {@code elements} is an
|
|
* {@code ImmutableMultiset}, no copy will actually be performed, and the given
|
|
* multiset itself will be returned.
|
|
*
|
|
* @throws NullPointerException if any of {@code elements} is null
|
|
*/
|
|
public static <E> ImmutableMultiset<E> copyOf(Iterable<? extends E> elements) {
|
|
if (elements instanceof ImmutableMultiset) {
|
|
@SuppressWarnings("unchecked") // all supported methods are covariant
|
|
ImmutableMultiset<E> result = (ImmutableMultiset<E>) elements;
|
|
if (!result.isPartialView()) {
|
|
return result;
|
|
}
|
|
}
|
|
|
|
Multiset<? extends E> multiset = (elements instanceof Multiset) ? Multisets.cast(elements)
|
|
: LinkedHashMultiset.create(elements);
|
|
|
|
return copyOfInternal(multiset);
|
|
}
|
|
|
|
private static <E> ImmutableMultiset<E> copyOfInternal(E... elements) {
|
|
return copyOf(Arrays.asList(elements));
|
|
}
|
|
|
|
private static <E> ImmutableMultiset<E> copyOfInternal(Multiset<? extends E> multiset) {
|
|
return copyFromEntries(multiset.entrySet());
|
|
}
|
|
|
|
static <E> ImmutableMultiset<E> copyFromEntries(Collection<? extends Entry<? extends E>> entries) {
|
|
long size = 0;
|
|
ImmutableMap.Builder<E, Integer> builder = ImmutableMap.builder();
|
|
for (Entry<? extends E> entry : entries) {
|
|
int count = entry.getCount();
|
|
if (count > 0) {
|
|
// Since ImmutableMap.Builder throws an NPE if an element is null, no
|
|
// other null checks are needed.
|
|
builder.put(entry.getElement(), count);
|
|
size += count;
|
|
}
|
|
}
|
|
|
|
if (size == 0) {
|
|
return of();
|
|
}
|
|
return new RegularImmutableMultiset<E>(builder.build(), Ints.saturatedCast(size));
|
|
}
|
|
|
|
/**
|
|
* Returns an immutable multiset containing the given elements.
|
|
*
|
|
* <p>
|
|
* The multiset is ordered by the first occurrence of each element. For example,
|
|
* {@code ImmutableMultiset.copyOf(Arrays.asList(2, 3, 1, 3).iterator())} yields
|
|
* a multiset with elements in the order {@code 2, 3, 3, 1}.
|
|
*
|
|
* @throws NullPointerException if any of {@code elements} is null
|
|
*/
|
|
public static <E> ImmutableMultiset<E> copyOf(Iterator<? extends E> elements) {
|
|
Multiset<E> multiset = LinkedHashMultiset.create();
|
|
Iterators.addAll(multiset, elements);
|
|
return copyOfInternal(multiset);
|
|
}
|
|
|
|
ImmutableMultiset() {
|
|
}
|
|
|
|
@Override
|
|
public UnmodifiableIterator<E> iterator() {
|
|
final Iterator<Entry<E>> entryIterator = entrySet().iterator();
|
|
return new UnmodifiableIterator<E>() {
|
|
int remaining;
|
|
E element;
|
|
|
|
@Override
|
|
public boolean hasNext() {
|
|
return (remaining > 0) || entryIterator.hasNext();
|
|
}
|
|
|
|
@Override
|
|
public E next() {
|
|
if (remaining <= 0) {
|
|
Entry<E> entry = entryIterator.next();
|
|
element = entry.getElement();
|
|
remaining = entry.getCount();
|
|
}
|
|
remaining--;
|
|
return element;
|
|
}
|
|
};
|
|
}
|
|
|
|
@Override
|
|
public boolean contains(@Nullable Object object) {
|
|
return count(object) > 0;
|
|
}
|
|
|
|
@Override
|
|
public boolean containsAll(Collection<?> targets) {
|
|
return elementSet().containsAll(targets);
|
|
}
|
|
|
|
/**
|
|
* Guaranteed to throw an exception and leave the collection unmodified.
|
|
*
|
|
* @throws UnsupportedOperationException always
|
|
* @deprecated Unsupported operation.
|
|
*/
|
|
@Deprecated
|
|
@Override
|
|
public final int add(E element, int occurrences) {
|
|
throw new UnsupportedOperationException();
|
|
}
|
|
|
|
/**
|
|
* Guaranteed to throw an exception and leave the collection unmodified.
|
|
*
|
|
* @throws UnsupportedOperationException always
|
|
* @deprecated Unsupported operation.
|
|
*/
|
|
@Deprecated
|
|
@Override
|
|
public final int remove(Object element, int occurrences) {
|
|
throw new UnsupportedOperationException();
|
|
}
|
|
|
|
/**
|
|
* Guaranteed to throw an exception and leave the collection unmodified.
|
|
*
|
|
* @throws UnsupportedOperationException always
|
|
* @deprecated Unsupported operation.
|
|
*/
|
|
@Deprecated
|
|
@Override
|
|
public final int setCount(E element, int count) {
|
|
throw new UnsupportedOperationException();
|
|
}
|
|
|
|
/**
|
|
* Guaranteed to throw an exception and leave the collection unmodified.
|
|
*
|
|
* @throws UnsupportedOperationException always
|
|
* @deprecated Unsupported operation.
|
|
*/
|
|
@Deprecated
|
|
@Override
|
|
public final boolean setCount(E element, int oldCount, int newCount) {
|
|
throw new UnsupportedOperationException();
|
|
}
|
|
|
|
@GwtIncompatible("not present in emulated superclass")
|
|
@Override
|
|
int copyIntoArray(Object[] dst, int offset) {
|
|
for (Multiset.Entry<E> entry : entrySet()) {
|
|
Arrays.fill(dst, offset, offset + entry.getCount(), entry.getElement());
|
|
offset += entry.getCount();
|
|
}
|
|
return offset;
|
|
}
|
|
|
|
@Override
|
|
public boolean equals(@Nullable Object object) {
|
|
return Multisets.equalsImpl(this, object);
|
|
}
|
|
|
|
@Override
|
|
public int hashCode() {
|
|
return Sets.hashCodeImpl(entrySet());
|
|
}
|
|
|
|
@Override
|
|
public String toString() {
|
|
return entrySet().toString();
|
|
}
|
|
|
|
private transient ImmutableSet<Entry<E>> entrySet;
|
|
|
|
@Override
|
|
public ImmutableSet<Entry<E>> entrySet() {
|
|
ImmutableSet<Entry<E>> es = entrySet;
|
|
return (es == null) ? (entrySet = createEntrySet()) : es;
|
|
}
|
|
|
|
private final ImmutableSet<Entry<E>> createEntrySet() {
|
|
return isEmpty() ? ImmutableSet.<Entry<E>>of() : new EntrySet();
|
|
}
|
|
|
|
abstract Entry<E> getEntry(int index);
|
|
|
|
private final class EntrySet extends ImmutableSet<Entry<E>> {
|
|
@Override
|
|
boolean isPartialView() {
|
|
return ImmutableMultiset.this.isPartialView();
|
|
}
|
|
|
|
@Override
|
|
public UnmodifiableIterator<Entry<E>> iterator() {
|
|
return asList().iterator();
|
|
}
|
|
|
|
@Override
|
|
ImmutableList<Entry<E>> createAsList() {
|
|
return new ImmutableAsList<Entry<E>>() {
|
|
@Override
|
|
public Entry<E> get(int index) {
|
|
return getEntry(index);
|
|
}
|
|
|
|
@Override
|
|
ImmutableCollection<Entry<E>> delegateCollection() {
|
|
return EntrySet.this;
|
|
}
|
|
};
|
|
}
|
|
|
|
@Override
|
|
public int size() {
|
|
return elementSet().size();
|
|
}
|
|
|
|
@Override
|
|
public boolean contains(Object o) {
|
|
if (o instanceof Entry) {
|
|
Entry<?> entry = (Entry<?>) o;
|
|
if (entry.getCount() <= 0) {
|
|
return false;
|
|
}
|
|
int count = count(entry.getElement());
|
|
return count == entry.getCount();
|
|
}
|
|
return false;
|
|
}
|
|
|
|
@Override
|
|
public int hashCode() {
|
|
return ImmutableMultiset.this.hashCode();
|
|
}
|
|
|
|
// We can't label this with @Override, because it doesn't override anything
|
|
// in the GWT emulated version.
|
|
// TODO(cpovirk): try making all copies of this method @GwtIncompatible instead
|
|
Object writeReplace() {
|
|
return new EntrySetSerializedForm<E>(ImmutableMultiset.this);
|
|
}
|
|
|
|
private static final long serialVersionUID = 0;
|
|
}
|
|
|
|
static class EntrySetSerializedForm<E> implements Serializable {
|
|
final ImmutableMultiset<E> multiset;
|
|
|
|
EntrySetSerializedForm(ImmutableMultiset<E> multiset) {
|
|
this.multiset = multiset;
|
|
}
|
|
|
|
Object readResolve() {
|
|
return multiset.entrySet();
|
|
}
|
|
}
|
|
|
|
private static class SerializedForm implements Serializable {
|
|
final Object[] elements;
|
|
final int[] counts;
|
|
|
|
SerializedForm(Multiset<?> multiset) {
|
|
int distinct = multiset.entrySet().size();
|
|
elements = new Object[distinct];
|
|
counts = new int[distinct];
|
|
int i = 0;
|
|
for (Entry<?> entry : multiset.entrySet()) {
|
|
elements[i] = entry.getElement();
|
|
counts[i] = entry.getCount();
|
|
i++;
|
|
}
|
|
}
|
|
|
|
Object readResolve() {
|
|
LinkedHashMultiset<Object> multiset = LinkedHashMultiset.create(elements.length);
|
|
for (int i = 0; i < elements.length; i++) {
|
|
multiset.add(elements[i], counts[i]);
|
|
}
|
|
return ImmutableMultiset.copyOf(multiset);
|
|
}
|
|
|
|
private static final long serialVersionUID = 0;
|
|
}
|
|
|
|
// We can't label this with @Override, because it doesn't override anything
|
|
// in the GWT emulated version.
|
|
Object writeReplace() {
|
|
return new SerializedForm(this);
|
|
}
|
|
|
|
/**
|
|
* Returns a new builder. The generated builder is equivalent to the builder
|
|
* created by the {@link Builder} constructor.
|
|
*/
|
|
public static <E> Builder<E> builder() {
|
|
return new Builder<E>();
|
|
}
|
|
|
|
/**
|
|
* A builder for creating immutable multiset instances, especially {@code
|
|
* public static final} multisets ("constant multisets"). Example:
|
|
*
|
|
* <pre>
|
|
* {
|
|
* @code
|
|
*
|
|
* public static final ImmutableMultiset<Bean> BEANS = new ImmutableMultiset.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 2.0 (imported from Google Collections Library)
|
|
*/
|
|
public static class Builder<E> extends ImmutableCollection.Builder<E> {
|
|
final Multiset<E> contents;
|
|
|
|
/**
|
|
* Creates a new builder. The returned builder is equivalent to the builder
|
|
* generated by {@link ImmutableMultiset#builder}.
|
|
*/
|
|
public Builder() {
|
|
this(LinkedHashMultiset.<E>create());
|
|
}
|
|
|
|
Builder(Multiset<E> contents) {
|
|
this.contents = contents;
|
|
}
|
|
|
|
/**
|
|
* Adds {@code element} to the {@code ImmutableMultiset}.
|
|
*
|
|
* @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) {
|
|
contents.add(checkNotNull(element));
|
|
return this;
|
|
}
|
|
|
|
/**
|
|
* Adds a number of occurrences of an element to this {@code
|
|
* ImmutableMultiset}.
|
|
*
|
|
* @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
|
|
*/
|
|
public Builder<E> addCopies(E element, int occurrences) {
|
|
contents.add(checkNotNull(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
|
|
*/
|
|
public Builder<E> setCount(E element, int count) {
|
|
contents.setCount(checkNotNull(element), count);
|
|
return this;
|
|
}
|
|
|
|
/**
|
|
* Adds each element of {@code elements} to the {@code ImmutableMultiset}.
|
|
*
|
|
* @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 ImmutableMultiset}.
|
|
*
|
|
* @param elements the {@code Iterable} to add to the {@code
|
|
* ImmutableMultiset}
|
|
* @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) {
|
|
if (elements instanceof Multiset) {
|
|
Multiset<? extends E> multiset = Multisets.cast(elements);
|
|
for (Entry<? extends E> entry : multiset.entrySet()) {
|
|
addCopies(entry.getElement(), entry.getCount());
|
|
}
|
|
} else {
|
|
super.addAll(elements);
|
|
}
|
|
return this;
|
|
}
|
|
|
|
/**
|
|
* Adds each element of {@code elements} to the {@code ImmutableMultiset}.
|
|
*
|
|
* @param elements the elements to add to the {@code ImmutableMultiset}
|
|
* @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 ImmutableMultiset} based on the contents of
|
|
* the {@code Builder}.
|
|
*/
|
|
@Override
|
|
public ImmutableMultiset<E> build() {
|
|
return copyOf(contents);
|
|
}
|
|
}
|
|
}
|