Class TreeMultiset<E>
- java.lang.Object
-
- java.util.AbstractCollection<E>
-
- com.google.common.collect.AbstractMultiset<E>
-
- com.google.common.collect.AbstractSortedMultiset<E>
-
- com.google.common.collect.TreeMultiset<E>
-
- All Implemented Interfaces:
Multiset<E>
,SortedIterable<E>
,SortedMultiset<E>
,SortedMultisetBridge<E>
,java.io.Serializable
,java.lang.Iterable<E>
,java.util.Collection<E>
public final class TreeMultiset<E> extends AbstractSortedMultiset<E> implements java.io.Serializable
A multiset which maintains the ordering of its elements, according to either their natural order or an explicitComparator
. In all cases, this implementation usesComparable.compareTo(T)
orComparator.compare(T, T)
instead ofObject.equals(java.lang.Object)
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 theCollection
contract, which is specified in terms ofObject.equals(java.lang.Object)
.See the Guava User Guide article on
Multiset
.- Since:
- 2.0
- See Also:
- Serialized Form
-
-
Nested Class Summary
Nested Classes Modifier and Type Class Description private static class
TreeMultiset.Aggregate
A function which can be summed across a subtree.private static class
TreeMultiset.AvlNode<E>
private static class
TreeMultiset.Reference<T>
-
Nested classes/interfaces inherited from class com.google.common.collect.AbstractMultiset
AbstractMultiset.ElementSet, AbstractMultiset.EntrySet
-
Nested classes/interfaces inherited from interface com.google.common.collect.Multiset
Multiset.Entry<E>
-
-
Field Summary
Fields Modifier and Type Field Description private TreeMultiset.AvlNode<E>
header
private GeneralRange<E>
range
private TreeMultiset.Reference<TreeMultiset.AvlNode<E>>
rootReference
private static long
serialVersionUID
-
Fields inherited from class com.google.common.collect.AbstractSortedMultiset
comparator
-
-
Constructor Summary
Constructors Constructor Description TreeMultiset(TreeMultiset.Reference<TreeMultiset.AvlNode<E>> rootReference, GeneralRange<E> range, TreeMultiset.AvlNode<E> endLink)
TreeMultiset(java.util.Comparator<? super E> comparator)
-
Method Summary
All Methods Static Methods Instance Methods Concrete Methods Modifier and Type Method Description int
add(E element, int occurrences)
Adds a number of occurrences of an element to this multiset.private long
aggregateAboveRange(TreeMultiset.Aggregate aggr, TreeMultiset.AvlNode<E> node)
private long
aggregateBelowRange(TreeMultiset.Aggregate aggr, TreeMultiset.AvlNode<E> node)
private long
aggregateForEntries(TreeMultiset.Aggregate aggr)
void
clear()
int
count(java.lang.Object element)
Returns the number of occurrences of an element in this multiset (the count of the element).static <E extends java.lang.Comparable>
TreeMultiset<E>create()
Creates a new, empty multiset, sorted according to the elements' natural order.static <E extends java.lang.Comparable>
TreeMultiset<E>create(java.lang.Iterable<? extends E> elements)
Creates an empty multiset containing the given initial elements, sorted according to the elements' natural order.static <E> TreeMultiset<E>
create(java.util.Comparator<? super E> comparator)
Creates a new, empty multiset, sorted according to the specified comparator.(package private) java.util.Iterator<Multiset.Entry<E>>
descendingEntryIterator()
(package private) int
distinctElements()
(package private) static int
distinctElements(TreeMultiset.AvlNode<?> node)
(package private) java.util.Iterator<E>
elementIterator()
(package private) java.util.Iterator<Multiset.Entry<E>>
entryIterator()
private TreeMultiset.AvlNode<E>
firstNode()
Returns the first node in the tree that is in range.void
forEachEntry(java.util.function.ObjIntConsumer<? super E> action)
Runs the specified action for each distinct element in this multiset, and the number of occurrences of that element.SortedMultiset<E>
headMultiset(E upperBound, BoundType boundType)
Returns a view of this multiset restricted to the elements less thanupperBound
, optionally includingupperBound
itself.java.util.Iterator<E>
iterator()
private TreeMultiset.AvlNode<E>
lastNode()
private void
readObject(java.io.ObjectInputStream stream)
int
remove(java.lang.Object element, int occurrences)
Removes a number of occurrences of the specified element from this multiset.int
setCount(E element, int count)
Adds or removes the necessary occurrences of an element such that the element attains the desired count.boolean
setCount(E element, int oldCount, int newCount)
Conditionally sets the count of an element to a new value, as described inMultiset.setCount(Object, int)
, provided that the element has the expected current count.int
size()
Returns the total number of all occurrences of all elements in this multiset.private static <T> void
successor(TreeMultiset.AvlNode<T> a, TreeMultiset.AvlNode<T> b)
private static <T> void
successor(TreeMultiset.AvlNode<T> a, TreeMultiset.AvlNode<T> b, TreeMultiset.AvlNode<T> c)
SortedMultiset<E>
tailMultiset(E lowerBound, BoundType boundType)
Returns a view of this multiset restricted to the elements greater thanlowerBound
, optionally includinglowerBound
itself.private Multiset.Entry<E>
wrapEntry(TreeMultiset.AvlNode<E> baseEntry)
private void
writeObject(java.io.ObjectOutputStream stream)
-
Methods inherited from class com.google.common.collect.AbstractSortedMultiset
comparator, createDescendingMultiset, createElementSet, descendingIterator, descendingMultiset, elementSet, firstEntry, lastEntry, pollFirstEntry, pollLastEntry, subMultiset
-
Methods inherited from class com.google.common.collect.AbstractMultiset
add, addAll, contains, createEntrySet, entrySet, equals, hashCode, isEmpty, remove, removeAll, retainAll, toString
-
Methods inherited from class java.lang.Object
clone, finalize, getClass, notify, notifyAll, wait, wait, wait
-
Methods inherited from interface java.util.Collection
addAll, isEmpty, parallelStream, removeIf, stream, toArray, toArray, toArray
-
Methods inherited from interface com.google.common.collect.Multiset
add, contains, containsAll, equals, forEach, hashCode, remove, removeAll, retainAll, spliterator, toString
-
Methods inherited from interface com.google.common.collect.SortedMultiset
entrySet
-
-
-
-
Field Detail
-
rootReference
private final transient TreeMultiset.Reference<TreeMultiset.AvlNode<E>> rootReference
-
range
private final transient GeneralRange<E> range
-
header
private final transient TreeMultiset.AvlNode<E> header
-
serialVersionUID
private static final long serialVersionUID
- See Also:
- Constant Field Values
-
-
Constructor Detail
-
TreeMultiset
TreeMultiset(TreeMultiset.Reference<TreeMultiset.AvlNode<E>> rootReference, GeneralRange<E> range, TreeMultiset.AvlNode<E> endLink)
-
TreeMultiset
TreeMultiset(java.util.Comparator<? super E> comparator)
-
-
Method Detail
-
create
public static <E extends java.lang.Comparable> TreeMultiset<E> create()
Creates a new, empty multiset, sorted according to the elements' natural order. All elements inserted into the multiset must implement theComparable
interface. Furthermore, all such elements must be mutually comparable:e1.compareTo(e2)
must not throw aClassCastException
for any elementse1
ande2
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), theadd(Object)
call will throw aClassCastException
.The type specification is
<E extends Comparable>
, instead of the more specific<E extends Comparable<? super E>>
, to support classes defined without generics.
-
create
public static <E> TreeMultiset<E> create(@CheckForNull java.util.Comparator<? super E> comparator)
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 aClassCastException
for any elementse1
ande2
in the multiset. If the user attempts to add an element to the multiset that violates this constraint, theadd(Object)
call will throw aClassCastException
.- Parameters:
comparator
- the comparator that will be used to sort this multiset. A null value indicates that the elements' natural ordering should be used.
-
create
public static <E extends java.lang.Comparable> TreeMultiset<E> create(java.lang.Iterable<? extends E> elements)
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 aMultiset
.The type specification is
<E extends Comparable>
, instead of the more specific<E extends Comparable<? super E>>
, to support classes defined without generics.
-
aggregateForEntries
private long aggregateForEntries(TreeMultiset.Aggregate aggr)
-
aggregateBelowRange
private long aggregateBelowRange(TreeMultiset.Aggregate aggr, @CheckForNull TreeMultiset.AvlNode<E> node)
-
aggregateAboveRange
private long aggregateAboveRange(TreeMultiset.Aggregate aggr, @CheckForNull TreeMultiset.AvlNode<E> node)
-
size
public int size()
Description copied from interface:Multiset
Returns the total number of all occurrences of all elements in this multiset.Note: this method does not return the number of distinct elements in the multiset, which is given by
entrySet().size()
.
-
distinctElements
int distinctElements()
- Specified by:
distinctElements
in classAbstractMultiset<E>
-
distinctElements
static int distinctElements(@CheckForNull TreeMultiset.AvlNode<?> node)
-
count
public int count(@CheckForNull java.lang.Object element)
Description copied from interface:Multiset
Returns the number of occurrences of an element in this multiset (the count of the element). Note that for anObject.equals(java.lang.Object)
-based multiset, this gives the same result asCollections.frequency(java.util.Collection<?>, java.lang.Object)
(which would presumably perform more poorly).Note: the utility method
Iterables.frequency(java.lang.Iterable<?>, java.lang.Object)
generalizes this operation; it correctly delegates to this method when dealing with a multiset, but it can also accept any other iterable type.
-
add
public int add(E element, int occurrences)
Description copied from interface:Multiset
Adds a number of occurrences of an element to this multiset. Note that ifoccurrences == 1
, this method has the identical effect toMultiset.add(Object)
. This method is functionally equivalent (except in the case of overflow) to the calladdAll(Collections.nCopies(element, occurrences))
, which would presumably perform much more poorly.- Specified by:
add
in interfaceMultiset<E>
- Overrides:
add
in classAbstractMultiset<E>
- Parameters:
element
- the element to add occurrences of; may be null only if explicitly allowed by the implementationoccurrences
- the number of occurrences of the element to add. May be zero, in which case no change will be made.- Returns:
- the count of the element before the operation; possibly zero
-
remove
public int remove(@CheckForNull java.lang.Object element, int occurrences)
Description copied from interface:Multiset
Removes a number of occurrences of the specified element from this multiset. If the multiset contains fewer than this number of occurrences to begin with, all occurrences will be removed. Note that ifoccurrences == 1
, this is functionally equivalent to the callremove(element)
.- Specified by:
remove
in interfaceMultiset<E>
- Overrides:
remove
in classAbstractMultiset<E>
- Parameters:
element
- the element to conditionally remove occurrences ofoccurrences
- the number of occurrences of the element to remove. May be zero, in which case no change will be made.- Returns:
- the count of the element before the operation; possibly zero
-
setCount
public int setCount(E element, int count)
Description copied from interface:Multiset
Adds or removes the necessary occurrences of an element such that the element attains the desired count.- Specified by:
setCount
in interfaceMultiset<E>
- Overrides:
setCount
in classAbstractMultiset<E>
- Parameters:
element
- the element to add or remove occurrences of; may be null only if explicitly allowed by the implementationcount
- the desired count of the element in this multiset- Returns:
- the count of the element before the operation; possibly zero
-
setCount
public boolean setCount(E element, int oldCount, int newCount)
Description copied from interface:Multiset
Conditionally sets the count of an element to a new value, as described inMultiset.setCount(Object, int)
, provided that the element has the expected current count. If the current count is notoldCount
, no change is made.- Specified by:
setCount
in interfaceMultiset<E>
- Overrides:
setCount
in classAbstractMultiset<E>
- Parameters:
element
- the element to conditionally set the count of; may be null only if explicitly allowed by the implementationoldCount
- the expected present count of the element in this multisetnewCount
- the desired count of the element in this multiset- Returns:
true
if the condition for modification was met. This implies that the multiset was indeed modified, unlessoldCount == newCount
.
-
clear
public void clear()
- Specified by:
clear
in interfacejava.util.Collection<E>
- Specified by:
clear
in classAbstractMultiset<E>
-
wrapEntry
private Multiset.Entry<E> wrapEntry(TreeMultiset.AvlNode<E> baseEntry)
-
firstNode
@CheckForNull private TreeMultiset.AvlNode<E> firstNode()
Returns the first node in the tree that is in range.
-
lastNode
@CheckForNull private TreeMultiset.AvlNode<E> lastNode()
-
elementIterator
java.util.Iterator<E> elementIterator()
- Specified by:
elementIterator
in classAbstractMultiset<E>
-
entryIterator
java.util.Iterator<Multiset.Entry<E>> entryIterator()
- Specified by:
entryIterator
in classAbstractMultiset<E>
-
descendingEntryIterator
java.util.Iterator<Multiset.Entry<E>> descendingEntryIterator()
- Specified by:
descendingEntryIterator
in classAbstractSortedMultiset<E>
-
forEachEntry
public void forEachEntry(java.util.function.ObjIntConsumer<? super E> action)
Description copied from interface:Multiset
Runs the specified action for each distinct element in this multiset, and the number of occurrences of that element. For someMultiset
implementations, this may be more efficient than iterating over theMultiset.entrySet()
either explicitly or withentrySet().forEach(action)
.- Specified by:
forEachEntry
in interfaceMultiset<E>
-
iterator
public java.util.Iterator<E> iterator()
Description copied from interface:SortedMultiset
Elements that occur multiple times in the multiset will appear multiple times in this iterator, though not necessarily sequentially.
The iterator returns the elements in ascending order according to this multiset's comparator.
- Specified by:
iterator
in interfacejava.util.Collection<E>
- Specified by:
iterator
in interfacejava.lang.Iterable<E>
- Specified by:
iterator
in interfaceMultiset<E>
- Specified by:
iterator
in interfaceSortedIterable<E>
- Specified by:
iterator
in interfaceSortedMultiset<E>
- Specified by:
iterator
in classjava.util.AbstractCollection<E>
-
headMultiset
public SortedMultiset<E> headMultiset(E upperBound, BoundType boundType)
Description copied from interface:SortedMultiset
Returns a view of this multiset restricted to the elements less thanupperBound
, optionally includingupperBound
itself. The returned multiset is a view of this multiset, so changes to one will be reflected in the other. The returned multiset supports all operations that this multiset supports.The returned multiset will throw an
IllegalArgumentException
on attempts to add elements outside its range.- Specified by:
headMultiset
in interfaceSortedMultiset<E>
-
tailMultiset
public SortedMultiset<E> tailMultiset(E lowerBound, BoundType boundType)
Description copied from interface:SortedMultiset
Returns a view of this multiset restricted to the elements greater thanlowerBound
, optionally includinglowerBound
itself. The returned multiset is a view of this multiset, so changes to one will be reflected in the other. The returned multiset supports all operations that this multiset supports.The returned multiset will throw an
IllegalArgumentException
on attempts to add elements outside its range.- Specified by:
tailMultiset
in interfaceSortedMultiset<E>
-
successor
private static <T> void successor(TreeMultiset.AvlNode<T> a, TreeMultiset.AvlNode<T> b)
-
successor
private static <T> void successor(TreeMultiset.AvlNode<T> a, TreeMultiset.AvlNode<T> b, TreeMultiset.AvlNode<T> c)
-
writeObject
private void writeObject(java.io.ObjectOutputStream stream) throws java.io.IOException
- Throws:
java.io.IOException
-
readObject
private void readObject(java.io.ObjectInputStream stream) throws java.io.IOException, java.lang.ClassNotFoundException
- Throws:
java.io.IOException
java.lang.ClassNotFoundException
-
-