/*
* 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 com.google.common.annotations.GwtCompatible;
import com.google.common.primitives.Ints;
import java.io.Serializable;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.Collections;
import java.util.Iterator;
import java.util.List;
import java.util.Set;
import javax.annotation.Nullable;
/**
* 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.
*
* @author Jared Levy
* @author Louis Wasserman
* @since 2.0 (imported from Google Collections Library)
*/
@GwtCompatible(serializable = 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> {
/**
* Returns the empty immutable multiset.
*/
@SuppressWarnings("unchecked") // all supported methods are covariant
public static <E> ImmutableMultiset<E> of() {
return (ImmutableMultiset<E>) EmptyImmutableMultiset.INSTANCE;
}
/**
* 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) {
int size = others.length + 6;
List<E> all = new ArrayList<E>(size);
Collections.addAll(all, e1, e2, e3, e4, e5, e6);
Collections.addAll(all, others);
return copyOf(all);
}
/**
* Returns an immutable multiset containing the given elements.
*
* <p>The multiset is ordered by the first occurrence of each element. For
* example, {@code ImmutableMultiset.of(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
* @deprecated use {@link #copyOf(Object[])}. <b>This method is scheduled for
* deletion in January 2012.</b>
* @since 2.0 (changed from varargs in 6.0)
*/
@Deprecated
public static <E> ImmutableMultiset<E> of(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([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) {
long size = 0;
ImmutableMap.Builder<E, Integer> builder = ImmutableMap.builder();
for (Entry<? extends E> entry : multiset.entrySet()) {
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 = entryIterator();
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
*/
@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
*/
@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
*/
@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
*/
@Override
public final boolean setCount(E element, int oldCount, int newCount) {
throw new UnsupportedOperationException();
}
@Override public boolean equals(@Nullable Object object) {
if (object == this) {
return true;
}
if (object instanceof Multiset) {
Multiset<?> that = (Multiset<?>) object;
if (this.size() != that.size()) {
return false;
}
for (Entry<?> entry : that.entrySet()) {
if (count(entry.getElement()) != entry.getCount()) {
return false;
}
}
return true;
}
return false;
}
@Override public int hashCode() {
return Sets.hashCodeImpl(entrySet());
}
@Override public String toString() {
return entrySet().toString();
}
private transient ImmutableSet<Entry<E>> entrySet;
@Override
public Set<Entry<E>> entrySet() {
ImmutableSet<Entry<E>> es = entrySet;
return (es == null) ? (entrySet = createEntrySet()) : es;
}
abstract UnmodifiableIterator<Entry<E>> entryIterator();
abstract int distinctElements();
ImmutableSet<Entry<E>> createEntrySet() {
return new EntrySet<E>(this);
}
static class EntrySet<E> extends ImmutableSet<Entry<E>> {
transient final ImmutableMultiset<E> multiset;
public EntrySet(ImmutableMultiset<E> multiset) {
this.multiset = multiset;
}
@Override
public UnmodifiableIterator<Entry<E>> iterator() {
return multiset.entryIterator();
}
@Override
public int size() {
return multiset.distinctElements();
}
@Override
boolean isPartialView() {
return multiset.isPartialView();
}
@Override
public boolean contains(Object o) {
if (o instanceof Entry) {
Entry<?> entry = (Entry<?>) o;
if (entry.getCount() <= 0) {
return false;
}
int count = multiset.count(entry.getElement());
return count == entry.getCount();
}
return false;
}
/*
* TODO(hhchan): Revert once we have a separate, manual emulation of this
* class.
*/
@Override
public Object[] toArray() {
Object[] newArray = new Object[size()];
return toArray(newArray);
}
/*
* TODO(hhchan): Revert once we have a separate, manual emulation of this
* class.
*/
@Override
public <T> T[] toArray(T[] other) {
int size = size();
if (other.length < size) {
other = ObjectArrays.newArray(other, size);
} else if (other.length > size) {
other[size] = null;
}
// Writes will produce ArrayStoreException when the toArray() doc requires
Object[] otherAsObjectArray = other;
int index = 0;
for (Entry<?> element : this) {
otherAsObjectArray[index++] = element;
}
return other;
}
@Override
public int hashCode() {
return multiset.hashCode();
}
// We can't label this with @Override, because it doesn't override anything
// in the GWT emulated version.
Object writeReplace() {
return new EntrySetSerializedForm<E>(multiset);
}
static class EntrySetSerializedForm<E> implements Serializable {
final ImmutableMultiset<E> multiset;
EntrySetSerializedForm(ImmutableMultiset<E> multiset) {
this.multiset = multiset;
}
Object readResolve() {
return multiset.entrySet();
}
}
private static final long serialVersionUID = 0;
}
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>
*
* 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);
}
}
}
|