Class FrequencySortedSet<E>
- Type Parameters:
E
- the type of elements in the set.
- All Implemented Interfaces:
Serializable
,Iterable<E>
,Collection<E>
,Comparator<E>
,Set<E>
,SortedSet<E>
An optional boolean argument in the constructor allows the construction of set in reversed order
(most frequently added elements first, less frequently added last). This is similar but not identical
to creating a default FrequencySortedSet
and iterating through it in reverse order.
The difference is that elements added the same amount of time will still be traversed in their insertion order.
This class is not thread-safe. Synchronizations (if wanted) are caller responsibility.
- Since:
- 0.8
- Version:
- 0.8
- See Also:
-
Nested Class Summary
Nested ClassesModifier and TypeClassDescriptionprivate final class
Iterator over sorted elements.private final class
A view over a subset ofFrequencySortedSet
. -
Field Summary
FieldsModifier and TypeFieldDescriptionprivate static final Comparator<Map.Entry<?,
Integer>> The comparator used for sorting map entries.The frequency of occurrence for each element.private int[]
The frequency for each sorted element.private final int
0
if the element should be sorted in the usual order, or-1
if the elements should be sorted in reverse order (most frequent element first).private static final long
For cross-version compatibility.private E[]
Elements in sorted order, ornull
if not yet computed. -
Constructor Summary
ConstructorsConstructorDescriptionCreates an initially empty set with less frequent elements first.FrequencySortedSet
(boolean reversed) Creates an initially empty set with the default initial capacity.FrequencySortedSet
(int initialCapacity, boolean reversed) Creates an initially empty set with the specified initial capacity. -
Method Summary
Modifier and TypeMethodDescriptionboolean
Adds the specified element to this set.boolean
Repetitively adds the specified element to this set.void
clear()
Removes all elements from this set.final Comparator<E>
Returns the comparator used to order the elements in this set.final int
Compares the specified elements for frequency.boolean
Returnstrue
if this set contains the specified element.private void
Sorts the elements in frequency order, if not already done.first()
Returns the first element in this set.int[]
Returns the frequency of all elements in this set, in iteration order.int
Returns the frequency of the specified element in this set.Returns a view of the portion of this set whose elements occur with a frequency strictly less thantoElement
frequency.boolean
isEmpty()
Returnstrue
if this set is empty.iterator()
Returns an iterator over the elements in this set in frequency order.last()
Returns the last element in this set.boolean
Removes the specified element from this set, no matter how many time it has been added.private int
signedFrequency
(E element) Returns the frequency of the specified element in this set.int
size()
Returns the number of elements in this set.Returns a view of the portion of this set whose elements occur with a frequency in the range offromElement
frequency inclusive totoElement
frequency exclusive.Returns a view of the portion of this set whose elements occur with a frequency equal or greater thanfromElement
frequency.Object[]
toArray()
Returns the content of this set as an array.<T> T[]
toArray
(T[] array) Returns the content of this set as an array.Methods inherited from class java.util.AbstractSet
equals, hashCode, removeAll
Methods inherited from class java.util.AbstractCollection
addAll, containsAll, retainAll, toString
Methods inherited from class java.lang.Object
clone, finalize, getClass, notify, notifyAll, wait, wait, wait
Methods inherited from interface java.util.Collection
parallelStream, removeIf, stream, toArray
Methods inherited from interface java.util.Comparator
equals, reversed, thenComparing, thenComparing, thenComparing, thenComparingDouble, thenComparingInt, thenComparingLong
Methods inherited from interface java.util.Set
addAll, containsAll, equals, hashCode, removeAll, retainAll
Methods inherited from interface java.util.SortedSet
spliterator
-
Field Details
-
serialVersionUID
private static final long serialVersionUIDFor cross-version compatibility.- See Also:
-
count
The frequency of occurrence for each element. We must use a linked hash map instead of an ordinary hash map because we want to preserve insertion order for elements that occur at the same frequency. Values are positives if this set sorts by increasing frequencies, or negatives if this set sorts by decreasing frequencies. -
order
private final int order0
if the element should be sorted in the usual order, or-1
if the elements should be sorted in reverse order (most frequent element first). This value is XORed with the number of times n that an element is added:n ^ order
. The intent is to store negative numbers in thecount
map if thisFrequencySortedSet
has been created for reverse order.Implementation note: we could have used+1
and-1
for the usual and reverse order respectively, and store the multiplication resultn * order
in thecount
map. We rather use XOR for two reasons: first, XOR is a simpler operation for the CPU than multiplication. Second, XOR guarantees us that all negative numbers can be made positive infrequencies()
, by applying againn ^ order
. By contrast, the multiplication approach (or just the-n
negation) would fail to convertInteger.MIN_VALUE
. -
sorted
Elements in sorted order, ornull
if not yet computed. -
frequencies
private transient int[] frequencies -
COMPARATOR
The comparator used for sorting map entries. Must be consistent withcompare(Object, Object)
implementation.
-
-
Constructor Details
-
FrequencySortedSet
public FrequencySortedSet()Creates an initially empty set with less frequent elements first. -
FrequencySortedSet
public FrequencySortedSet(boolean reversed) Creates an initially empty set with the default initial capacity.- Parameters:
reversed
-true
if the elements should be sorted in reverse order (most frequent element first, less frequent element last).
-
FrequencySortedSet
public FrequencySortedSet(int initialCapacity, boolean reversed) Creates an initially empty set with the specified initial capacity.- Parameters:
initialCapacity
- the initial capacity.reversed
-true
if the elements should be sorted in reverse order (most frequent element first, less frequent element last).
-
-
Method Details
-
size
public int size()Returns the number of elements in this set.- Specified by:
size
in interfaceCollection<E>
- Specified by:
size
in interfaceSet<E>
- Specified by:
size
in classAbstractCollection<E>
-
isEmpty
public boolean isEmpty()Returnstrue
if this set is empty.- Specified by:
isEmpty
in interfaceCollection<E>
- Specified by:
isEmpty
in interfaceSet<E>
- Overrides:
isEmpty
in classAbstractCollection<E>
-
add
Repetitively adds the specified element to this set. Returnstrue
if this set changed as a result of this operation. Changes in element order are not notified by the returned value.- Parameters:
element
- the element to add (may benull
).occurrence
- the number of time to add the given element. The default value is 1.- Returns:
true
if this set changed as a result of this operation.- Throws:
IllegalArgumentException
- ifoccurrence
is negative.
-
add
Adds the specified element to this set. Returnstrue
if this set changed as a result of this operation. Changes in element order are not notified by the returned value.The default implementation delegates to
add(element, 1)
.- Specified by:
add
in interfaceCollection<E>
- Specified by:
add
in interfaceSet<E>
- Overrides:
add
in classAbstractCollection<E>
- Parameters:
element
- the element to add (may benull
).- Returns:
true
if this set changed as a result of this operation.
-
contains
Returnstrue
if this set contains the specified element.- Specified by:
contains
in interfaceCollection<E>
- Specified by:
contains
in interfaceSet<E>
- Overrides:
contains
in classAbstractCollection<E>
- Parameters:
element
- the element whose presence in this set is to be tested.- Returns:
true
if this set contains the specified element.
-
remove
Removes the specified element from this set, no matter how many time it has been added. Returnstrue
if this set changed as a result of this operation.- Specified by:
remove
in interfaceCollection<E>
- Specified by:
remove
in interfaceSet<E>
- Overrides:
remove
in classAbstractCollection<E>
- Parameters:
element
- the element to remove.- Returns:
true
if this set changed as a result of this operation.
-
clear
public void clear()Removes all elements from this set.- Specified by:
clear
in interfaceCollection<E>
- Specified by:
clear
in interfaceSet<E>
- Overrides:
clear
in classAbstractCollection<E>
-
iterator
Returns an iterator over the elements in this set in frequency order. -
headSet
Returns a view of the portion of this set whose elements occur with a frequency strictly less thantoElement
frequency. -
tailSet
Returns a view of the portion of this set whose elements occur with a frequency equal or greater thanfromElement
frequency. -
subSet
Returns a view of the portion of this set whose elements occur with a frequency in the range offromElement
frequency inclusive totoElement
frequency exclusive. -
first
Returns the first element in this set.- For sets created with the default order, this is the less frequently added element. If more than one element were added with the same frequency, this is the first one that has been added to this set at this frequency.
- For sets created with the reverse order, this is the most frequently added element. If more than one element were added with the same frequency, this is the first one that has been added to this set at this frequency.
- Specified by:
first
in interfaceSortedSet<E>
- Throws:
NoSuchElementException
- if this set is empty.
-
last
Returns the last element in this set.- For sets created with the default order, this is the most frequently added element. If more than one element were added with the same frequency, this is the last one that has been added to this set at this frequency.
- For sets created with the reverse order, this is the less frequently added element. If more than one element were added with the same frequency, this is the last one that has been added to this set at this frequency.
- Specified by:
last
in interfaceSortedSet<E>
- Throws:
NoSuchElementException
- if this set is empty.
-
ensureSorted
private void ensureSorted()Sorts the elements in frequency order, if not already done. The sorted array will contain all elements without duplicated values, with the less frequent element first and the most frequent element last (or the converse if this set has been created for reverse order). If some elements appear at the same frequency, then their ordering will be preserved. -
comparator
Returns the comparator used to order the elements in this set. For aFrequencySortedSet
, the comparator is alwaysthis
.This method is final because the
FrequencySortedSet
implementation makes assumptions on the comparator that would not hold if this method were overridden.- Specified by:
comparator
in interfaceSortedSet<E>
-
compare
Compares the specified elements for frequency. ForFrequencySortedSet
with default ordering, this method returns a positive number ifo1
has been added more frequently to this set thano2
, a negative number ifo1
has been added less frequently thano2
, and 0 otherwise. ForFrequencySortedSet
with reverse ordering, this is the converse.This method is final because the
FrequencySortedSet
implementation makes assumptions on the comparator that would not hold if this method were overridden.- Specified by:
compare
in interfaceComparator<E>
-
signedFrequency
Returns the frequency of the specified element in this set. Returns a negative number if this set has been created for reversed order. -
frequency
Returns the frequency of the specified element in this set.- Parameters:
element
- the element whose frequency is to be obtained.- Returns:
- the frequency of the given element, or
0
if it does not occur in this set.
-
frequencies
public int[] frequencies()Returns the frequency of all elements in this set, in iteration order.- Returns:
- the frequency of all elements in this set.
-
toArray
Returns the content of this set as an array.- Specified by:
toArray
in interfaceCollection<E>
- Specified by:
toArray
in interfaceSet<E>
- Overrides:
toArray
in classAbstractCollection<E>
-
toArray
public <T> T[] toArray(T[] array) Returns the content of this set as an array.- Specified by:
toArray
in interfaceCollection<E>
- Specified by:
toArray
in interfaceSet<E>
- Overrides:
toArray
in classAbstractCollection<E>
- Type Parameters:
T
- the type of the array elements.- Parameters:
array
- the array where to copy the elements.- Returns:
- the elements in the given array, or in a new array if the given array does not have a sufficient capacity.
-