package com.google.common.collect;
import static com.google.common.base.Preconditions.checkArgument;
import static com.google.common.base.Preconditions.checkState;
import javax.annotation.Nullable;
A multiset which maintains the ordering of its elements, according to either their natural order
or an explicit
Comparator
. In all cases, this implementation uses
Comparable.compareTo
or
Comparator.compare
instead of
Object.equals
to
determine equivalence of instances.
Warning: The comparison must be consistent with equals as explained by the
Comparable
class specification. Otherwise, the resulting multiset will violate the
java.util.Collection
contract, which is specified in terms of Object.equals
.
See the Guava User Guide article on
Multiset
.
- Author(s):
- Louis Wasserman
- Jared Levy
- Since:
- 2.0 (imported from Google Collections Library)
Creates a new, empty multiset, sorted according to the elements' natural order. All elements
inserted into the multiset must implement the
Comparable
interface. Furthermore, all
such elements must be
mutually comparable:
e1.compareTo(e2)
must not throw a
ClassCastException
for any elements
e1
and
e2
in the multiset. If the
user attempts to add an element to the multiset that violates this constraint (for example,
the user attempts to add a string element to a set whose elements are integers), the
add(Object)
call will throw a
ClassCastException
.
The type specification is <E extends Comparable>
, instead of the more specific
<E extends Comparable<? super E>>
, to support classes defined without generics.
Creates a new, empty multiset, sorted according to the specified comparator. All elements
inserted into the multiset must be
mutually comparable by the specified comparator:
comparator.compare(e1,
e2)
must not throw a
ClassCastException
for any elements
e1
and
e2
in
the multiset. If the user attempts to add an element to the multiset that violates this
constraint, the
add(Object)
call will throw a
ClassCastException
.
- Parameters:
comparator
the comparator that will be used to sort this multiset. A null value indicates that
the elements' natural ordering should be used.
return (comparator == null)
Creates an empty multiset containing the given initial elements, sorted according to the
elements' natural order.
This implementation is highly efficient when elements
is itself a Multiset
.
The type specification is <E extends Comparable>
, instead of the more specific
<E extends Comparable<? super E>>
, to support classes defined without generics.
Iterables.addAll(multiset, elements);
this.range = GeneralRange.all(comparator);
A function which can be summed across a subtree.
return (root == null) ? 0 : root.totalCount;
return (root == null) ? 0 : root.distinctElements;
public int add(@Nullable E element, int occurrences) {
checkArgument(occurrences >= 0, "occurrences must be >= 0 but was %s", occurrences);
int[] result = new int[1];
public int remove(@Nullable Object element, int occurrences) {
checkArgument(occurrences >= 0, "occurrences must be >= 0 but was %s", occurrences);
int[] result = new int[1];
public int setCount(@Nullable E element, int count) {
int[] result = new int[1];
public boolean setCount(@Nullable E element, int oldCount, int newCount) {
int[] result = new int[1];
return result[0] == oldCount;
Returns the first node in the tree that is in range.
return (node == null) ? 0 : node.distinctElements;
@Nullable private T value;
@Nullable public T get() {
public void checkAndSet(@Nullable T expected, T newValue) {
@Nullable private final E elem;
AvlNode(@Nullable E elem, int elemCount) {
int initHeight = initLeft.height;
left = initLeft.add(comparator, e, count, result);
int initHeight = initRight.height;
right = initRight.add(comparator, e, count, result);
left = initLeft.remove(comparator, e, count, result);
if (count >= result[0]) {
return (result[0] == 0) ? this : rebalance();
right = initRight.remove(comparator, e, count, result);
if (count >= result[0]) {
if (count == 0 && result[0] != 0) {
} else if (count > 0 && result[0] == 0) {
if (count == 0 && result[0] != 0) {
} else if (count > 0 && result[0] == 0) {
if (expectedCount == 0 && newCount > 0) {
left = initLeft.setCount(comparator, e, expectedCount, newCount, result);
if (result[0] == expectedCount) {
if (newCount == 0 && result[0] != 0) {
} else if (newCount > 0 && result[0] == 0) {
if (expectedCount == 0 && newCount > 0) {
right = initRight.setCount(comparator, e, expectedCount, newCount, result);
if (result[0] == expectedCount) {
if (newCount == 0 && result[0] != 0) {
} else if (newCount > 0 && result[0] == 0) {
} else if (right == null) {
this.right = newTop.left;
this.left = newTop.right;
return (node == null) ? 0 : node.totalCount;
return (node == null) ? 0 : node.height;
- SerialData:
- the comparator, the number of distinct elements, the first element, its count, the
second element, its count, and so on
GeneralRange.all(comparator));