/*
* 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.annotations.
GwtIncompatible;
import com.google.common.collect.
Multiset.
Entry;
import com.google.common.primitives.
Ints;
import java.io.
Serializable;
import java.util.
Arrays;
import java.util.
Collection;
import java.util.
Iterator;
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.
*
* <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);
}
}
}