Class FrequencySortedSet<E>

java.lang.Object
java.util.AbstractCollection<E>
java.util.AbstractSet<E>
org.apache.sis.util.collection.FrequencySortedSet<E>
Type Parameters:
E - the type of elements in the set.
All Implemented Interfaces:
Serializable, Iterable<E>, Collection<E>, Comparator<E>, SequencedCollection<E>, SequencedSet<E>, Set<E>, SortedSet<E>

public class FrequencySortedSet<E> extends AbstractSet<E> implements SortedSet<E>, Comparator<E>, Serializable
A set with elements ordered by the amount of time they were added. By default, less frequently added elements are first and most frequently added elements are last. If some elements were added the same amount of time, then the iterator will traverse them in their insertion order.

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:
  • Field Details

    • serialVersionUID

      private static final long serialVersionUID
      For cross-version compatibility.
      See Also:
    • count

      private final Map<E,Integer> 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 order
      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). 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 the count map if this FrequencySortedSet 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 result n * order in the count 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 in frequencies(), by applying again n ^ order. By contrast, the multiplication approach (or just the -n negation) would fail to convert Integer.MIN_VALUE.
    • sorted

      private transient E[] sorted
      Elements in sorted order, or null if not yet computed.
    • frequencies

      private transient int[] frequencies
      The frequency for each sorted element. This array is invalid if sorted is null.
    • COMPARATOR

      private static final Comparator<Map.Entry<?,Integer>> COMPARATOR
      The comparator used for sorting map entries. Must be consistent with compare(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 interface Collection<E>
      Specified by:
      size in interface Set<E>
      Specified by:
      size in class AbstractCollection<E>
    • isEmpty

      public boolean isEmpty()
      Returns true if this set is empty.
      Specified by:
      isEmpty in interface Collection<E>
      Specified by:
      isEmpty in interface Set<E>
      Overrides:
      isEmpty in class AbstractCollection<E>
    • add

      public boolean add(E element, int occurrence) throws IllegalArgumentException
      Repetitively adds the specified element to this set. Returns true 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 be null).
      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 - if occurrence is negative.
    • add

      public boolean add(E element)
      Adds the specified element to this set. Returns true 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 interface Collection<E>
      Specified by:
      add in interface Set<E>
      Overrides:
      add in class AbstractCollection<E>
      Parameters:
      element - the element to add (may be null).
      Returns:
      true if this set changed as a result of this operation.
    • contains

      public boolean contains(Object element)
      Returns true if this set contains the specified element.
      Specified by:
      contains in interface Collection<E>
      Specified by:
      contains in interface Set<E>
      Overrides:
      contains in class AbstractCollection<E>
      Parameters:
      element - the element whose presence in this set is to be tested.
      Returns:
      true if this set contains the specified element.
    • remove

      public boolean remove(Object element)
      Removes the specified element from this set, no matter how many time it has been added. Returns true if this set changed as a result of this operation.
      Specified by:
      remove in interface Collection<E>
      Specified by:
      remove in interface Set<E>
      Overrides:
      remove in class AbstractCollection<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 interface Collection<E>
      Specified by:
      clear in interface Set<E>
      Overrides:
      clear in class AbstractCollection<E>
    • iterator

      public Iterator<E> iterator()
      Returns an iterator over the elements in this set in frequency order.
      Specified by:
      iterator in interface Collection<E>
      Specified by:
      iterator in interface Iterable<E>
      Specified by:
      iterator in interface Set<E>
      Specified by:
      iterator in class AbstractCollection<E>
    • headSet

      public SortedSet<E> headSet(E toElement)
      Returns a view of the portion of this set whose elements occur with a frequency strictly less than toElement frequency.
      Specified by:
      headSet in interface SortedSet<E>
      Parameters:
      toElement - high endpoint (exclusive) of the returned set. May be null.
      Returns:
      a view of the portion of this set delimited by the given endpoint.
    • tailSet

      public SortedSet<E> tailSet(E fromElement)
      Returns a view of the portion of this set whose elements occur with a frequency equal or greater than fromElement frequency.
      Specified by:
      tailSet in interface SortedSet<E>
      Parameters:
      fromElement - low endpoint (inclusive) of the returned set. May be null.
      Returns:
      a view of the portion of this set delimited by the given endpoint.
    • subSet

      public SortedSet<E> subSet(E fromElement, E toElement)
      Returns a view of the portion of this set whose elements occur with a frequency in the range of fromElement frequency inclusive to toElement frequency exclusive.
      Specified by:
      subSet in interface SortedSet<E>
      Parameters:
      fromElement - low endpoint (inclusive) of the returned set. May be null.
      toElement - high endpoint (exclusive) of the returned set. May be null.
      Returns:
      a view of the portion of this set delimited by the given endpoints.
    • first

      public E first() throws NoSuchElementException
      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 interface SortedSet<E>
      Throws:
      NoSuchElementException - if this set is empty.
    • last

      public E last() throws NoSuchElementException
      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 interface SortedSet<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

      public final Comparator<E> comparator()
      Returns the comparator used to order the elements in this set. For a FrequencySortedSet, the comparator is always this.

      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 interface SortedSet<E>
    • compare

      public final int compare(E o1, E o2)
      Compares the specified elements for frequency. For FrequencySortedSet with default ordering, this method returns a positive number if o1 has been added more frequently to this set than o2, a negative number if o1 has been added less frequently than o2, and 0 otherwise. For FrequencySortedSet 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 interface Comparator<E>
    • signedFrequency

      private int signedFrequency(E element)
      Returns the frequency of the specified element in this set. Returns a negative number if this set has been created for reversed order.
    • frequency

      public int frequency(E element)
      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

      public Object[] toArray()
      Returns the content of this set as an array.
      Specified by:
      toArray in interface Collection<E>
      Specified by:
      toArray in interface Set<E>
      Overrides:
      toArray in class AbstractCollection<E>
    • toArray

      public <T> T[] toArray(T[] array)
      Returns the content of this set as an array.
      Specified by:
      toArray in interface Collection<E>
      Specified by:
      toArray in interface Set<E>
      Overrides:
      toArray in class AbstractCollection<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.