Class TreeMultiset<E>
- All Implemented Interfaces:
Multiset<E>
,SortedIterable<E>
,SortedMultiset<E>
,SortedMultisetBridge<E>
,Serializable
,Iterable<E>
,Collection<E>
Comparator
. In all cases, this implementation uses Comparable.compareTo(T)
or Comparator.compare(T, T)
instead of Object.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 the Collection
contract, which is specified in terms of Object.equals(java.lang.Object)
.
See the Guava User Guide article on Multiset
.
- Since:
- 2.0
- See Also:
-
Nested Class Summary
Nested ClassesModifier and TypeClassDescriptionprivate static enum
A function which can be summed across a subtree.private static final class
private static final class
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
FieldsModifier and TypeFieldDescriptionprivate final TreeMultiset.AvlNode
<E> private final GeneralRange
<E> private final TreeMultiset.Reference
<TreeMultiset.AvlNode<E>> private static final long
Fields inherited from class com.google.common.collect.AbstractSortedMultiset
comparator
-
Constructor Summary
ConstructorsConstructorDescriptionTreeMultiset
(TreeMultiset.Reference<TreeMultiset.AvlNode<E>> rootReference, GeneralRange<E> range, TreeMultiset.AvlNode<E> endLink) TreeMultiset
(Comparator<? super E> comparator) -
Method Summary
Modifier and TypeMethodDescriptionint
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
void
clear()
int
Returns the number of occurrences of an element in this multiset (the count of the element).static <E extends Comparable>
TreeMultiset<E> create()
Creates a new, empty multiset, sorted according to the elements' natural order.static <E extends Comparable>
TreeMultiset<E> Creates an empty multiset containing the given initial elements, sorted according to the elements' natural order.static <E> TreeMultiset
<E> create
(Comparator<? super E> comparator) Creates a new, empty multiset, sorted according to the specified comparator.(package private) Iterator
<Multiset.Entry<E>> (package private) int
(package private) static int
distinctElements
(TreeMultiset.AvlNode<?> node) (package private) Iterator
<Multiset.Entry<E>> private TreeMultiset.AvlNode
<E> Returns the first node in the tree that is in range.void
forEachEntry
(ObjIntConsumer<? super E> action) Runs the specified action for each distinct element in this multiset, and the number of occurrences of that element.headMultiset
(E upperBound, BoundType boundType) Returns a view of this multiset restricted to the elements less thanupperBound
, optionally includingupperBound
itself.iterator()
private TreeMultiset.AvlNode
<E> lastNode()
private void
readObject
(ObjectInputStream stream) int
Removes a number of occurrences of the specified element from this multiset.int
Adds or removes the necessary occurrences of an element such that the element attains the desired count.boolean
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) 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
(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.util.AbstractCollection
containsAll, toArray, toArray
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 Details
-
rootReference
-
range
-
header
-
serialVersionUID
private static final long serialVersionUID- See Also:
-
-
Constructor Details
-
TreeMultiset
TreeMultiset(TreeMultiset.Reference<TreeMultiset.AvlNode<E>> rootReference, GeneralRange<E> range, TreeMultiset.AvlNode<E> endLink) -
TreeMultiset
TreeMultiset(Comparator<? super E> comparator)
-
-
Method Details
-
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
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
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
-
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()
.- Specified by:
size
in interfaceCollection<E>
- Specified by:
size
in interfaceMultiset<E>
- Specified by:
size
in classAbstractCollection<E>
-
distinctElements
int distinctElements()- Specified by:
distinctElements
in classAbstractMultiset<E>
-
distinctElements
-
count
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
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
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
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
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 interfaceCollection<E>
- Specified by:
clear
in classAbstractMultiset<E>
-
wrapEntry
-
firstNode
Returns the first node in the tree that is in range. -
lastNode
-
elementIterator
- Specified by:
elementIterator
in classAbstractMultiset<E>
-
entryIterator
Iterator<Multiset.Entry<E>> entryIterator()- Specified by:
entryIterator
in classAbstractMultiset<E>
-
descendingEntryIterator
Iterator<Multiset.Entry<E>> descendingEntryIterator()- Specified by:
descendingEntryIterator
in classAbstractSortedMultiset<E>
-
forEachEntry
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
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 interfaceCollection<E>
- Specified by:
iterator
in interfaceIterable<E>
- Specified by:
iterator
in interfaceMultiset<E>
- Specified by:
iterator
in interfaceSortedIterable<E>
- Specified by:
iterator
in interfaceSortedMultiset<E>
- Specified by:
iterator
in classAbstractCollection<E>
-
headMultiset
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
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
-
successor
private static <T> void successor(TreeMultiset.AvlNode<T> a, TreeMultiset.AvlNode<T> b, TreeMultiset.AvlNode<T> c) -
writeObject
- Throws:
IOException
-
readObject
- Throws:
IOException
ClassNotFoundException
-