Package net.algart.arrays

Class ArraySelector

java.lang.Object
net.algart.arrays.ArraySelector
public class ArraySelector extends Object

Selecting algorithms. This class provides an implementation for QuickSelect algorithm.

The architecture of this class is similar to ArraySorter class.

Unlike standard Java sorting algorithms, this class has no restriction 231-1 for the length of arrays. This class allows to select among up to 263−1 elements.

Author:
Daniel Alievsky
See Also:

  • Method Details

    • getQuickSelector

      public static ArraySelector getQuickSelector()
      Returns an instance of this class that implements QuickSelect algorithm.
      Returns:
      implementation of QuickSelect algorithm.

    • select

      public void select(long numberOfElements, long[] percentileIndexes, ArrayComparator comparator, ArrayExchanger exchanger)
      Partially reorders elements of some array 0..numberOfElements-1 so, that every element, having index m=percentileIndexes[k] in increasing order, will be placed at the position array[m] (m=0..numberOfElements-1), all previous elements (in increasing order) will be placed before it, and all further elements will be placed after it.

      Аfter this reordering we have a guarantee, that for any m=percentileIndexes[...] and for any i, j, that 0 ≤ i < m, m < j < numberOfElements, the following checks will return false:

           comparator.less(j, m)
     comparator.less(m, i)

      Reordering is based on movement of elements of the array with help of exchanger object, which must provide necessary access to the data.

      Note: list of indexes percentileIndexes must be sorted in increasing order. You can provide this, for example, by simple call of standard Java sorting method Arrays.sort(percentileIndexes) before calling this method.

      Note: if some exception occurs while calling comparator or exchanger methods, the array stays shuffled ("partially" sorted). (The typical example is ClassCastException when the comparator tries to cast some objects to java.lang.Comparable type.) In other words, this method is non-atomic regarding this failure.

      Parameters:
      numberOfElements - number of elements in the array.
      percentileIndexes - list of indexes inside the array, that should be placed to correct place in increasing order.
      comparator - comparator for checking order of elements.
      exchanger - exchanger for exchanging reordered elements.
      Throws:
      NullPointerException - if percentileIndexes, comparator or exchanger argument is null.
      IllegalArgumentException - if numberOfElements≤0, or if percentileIndexes array is empty, or if it contains indexes outside 0..numberOfElements-1 range, or if it is not sorted in increasing order.
      ClassCastException - may be thrown while calling methods of comparator or exchanger during the sorting, if the types of the array elements are not appropriate (it is only a typical example of exception: those methods may throw another run-time exceptions).

    • select

      public void select(long numberOfElements, double[] percentileLevels, ArrayComparator comparator, ArrayExchanger exchanger)
      Equivalent of 
           select(numberOfElements, percentileIndexes, comparator, exchanger)
      call, where percentileIndexes[k]=percentileIndex(percentileLevels[k], numberOfElements) for every k=0,...,percentileLevels.length-1.

      For example, percentileLevels={0.0, 0.5, 1.0} requests to find the minimum, median and maximum and place them to positions 0, percentileIndex(0.5, numberOfElements) and numberOfElements-1.

      Note: list of levels percentileLevels must be sorted in increasing order. You can provide this, for example, but simple call of standard Java sorting method Arrays.sort(percentileLevels) before calling this method.

      Parameters:
      numberOfElements - number of elements in the array.
      percentileLevels - list of percentile levels: required indexes, divided by array length.
      comparator - comparator for checking order of elements.
      exchanger - exchanger for exchanging sorted elements.
      Throws:
      NullPointerException - if percentileLevels, comparator or exchanger argument is null.
      IllegalArgumentException - if numberOfElements≤0, or if percentileLevels array is empty, or if it contains elements outside 0..1 range or NaN, or if it is not sorted in increasing order.
      ClassCastException - may be thrown while calling methods of comparator or exchanger during the sorting, if the types of the array elements are not appropriate (it is only a typical example of exception: those methods may throw another run-time exceptions).

    • select

      public void select(long from, long to, long requiredIndex, ArrayComparator comparator, ArrayExchanger exchanger)
      The version of select(long, long[], ArrayComparator, ArrayExchanger) method for selecting the single element with the required index. Unlike the previous method, allows to select element in a part of the array from ≤ index < to.

      After this reordering we have a guarantee, that for any i, j, that from ≤ i < requiredIndex, requiredIndex < j < to, the following checks will return false:

           comparator.less(j, m)
     comparator.less(m, i)

      Elements with indexes <from and ≥to are not analysed.

      Parameters:
      from - index of the first analysed element of some data array, inclusive.
      to - index of the last analysed element of some data array, exclusive.
      requiredIndex - index inside the array, that should be placed to correct place in increasing order.
      comparator - comparator for checking order of elements.
      exchanger - exchanger for exchanging reordered elements.
      Throws:
      NullPointerException - if comparator or exchanger argument is null.
      IllegalArgumentException - if from > to or from < 0, or or if requiredIndex is outside from..to-1 range.
      ClassCastException - may be thrown while calling methods of comparator or exchanger during the sorting, if the types of the array elements are not appropriate (it is only a typical example of exception: those methods may throw another run-time exceptions).

    • select

      public void select(int[] percentileIndexes, byte[] array, int length)
      Optimized version of select(long, long[], ArrayComparator, ArrayExchanger) method for selecting the element from first length elements of byte[] array.

      Note: unlike select(long, long[], ArrayComparator, ArrayExchanger), this method does not check elements of percentileIndexes, that they are correct and correctly sorted. If they are incorrect, the results will be undefined. You can check them yourself by checkPercentileIndexes(int[], int) method.

      Note that the elements of this array are supposed to be unsigned: we always compare array[i] & 0xFF and array[j] & 0xFF instead of simple array[i] and array[j].

      Parameters:
      percentileIndexes - list of indexes inside the array, that should be placed to correct place in increasing order.
      array - data array.
      length - number of elements: only elements array[0..length-1 are analysed.
      Throws:
      NullPointerException - if percentileIndexes or array argument is null.
      IllegalArgumentException - if length≤0, or length>array.length.

    • select

      public void select(double[] percentileLevels, byte[] array, int length)
      Optimized version of select(long, double[], ArrayComparator, ArrayExchanger) method for selecting the element from first length elements of byte[] array.

      Note: unlike select(long, double[], ArrayComparator, ArrayExchanger), this method does not check elements of percentileLevels, that they are correct and correctly sorted. If they are incorrect, the results will be undefined. You can check them yourself by checkPercentileLevels(double[]) method.

      Note that the elements of this array are supposed to be unsigned: we always compare array[i] & 0xFF and array[j] & 0xFF instead of simple array[i] and array[j].

      Parameters:
      percentileLevels - list of percentile levels: required indexes, divided by array length.
      array - data array.
      length - number of elements: only elements array[0..length-1 are analysed.
      Throws:
      NullPointerException - if percentileLevels or array argument is null.
      IllegalArgumentException - if length≤0, or length>array.length.

    • select

      public byte select(int from, int to, int requiredIndex, byte[] array)
      Optimized version of select(long, long, long, ArrayComparator, ArrayExchanger) method for selecting the element from byte[] array.

      Note that the elements of this array are supposed to be unsigned: we always compare array[i] & 0xFF and array[j] & 0xFF instead of simple array[i] and array[j].

      Parameters:
      from - index of the first analysed element of some data array, inclusive.
      to - index of the last analysed element of some data array, exclusive.
      requiredIndex - index inside the array, that should be placed to correct place in increasing order.
      array - data array.
      Throws:
      NullPointerException - if array argument is null.
      IllegalArgumentException - if from > to or from < 0, or if requiredIndex is outside from..to-1 range.

    • select

      public void select(int[] percentileIndexes, char[] array, int length)
      Optimized version of select(long, long[], ArrayComparator, ArrayExchanger) method for selecting the element from first length elements of char[] array.

      Note: unlike select(long, long[], ArrayComparator, ArrayExchanger), this method does not check elements of percentileIndexes, that they are correct and correctly sorted. If they are incorrect, the results will be undefined. You can check them yourself by checkPercentileIndexes(int[], int) method.

      Parameters:
      percentileIndexes - list of indexes inside the array, that should be placed to correct place in increasing order.
      array - data array.
      length - number of elements: only elements array[0..length-1 are analysed.
      Throws:
      NullPointerException - if percentileIndexes or array argument is null.
      IllegalArgumentException - if length≤0, or length>array.length.

    • select

      public void select(double[] percentileLevels, char[] array, int length)
      Optimized version of select(long, double[], ArrayComparator, ArrayExchanger) method for selecting the element from first length elements of char[] array.

      Note: unlike select(long, double[], ArrayComparator, ArrayExchanger), this method does not check elements of percentileLevels, that they are correct and correctly sorted. If they are incorrect, the results will be undefined. You can check them yourself by checkPercentileLevels(double[]) method.

      Parameters:
      percentileLevels - list of percentile levels: required indexes, divided by array length.
      array - data array.
      length - number of elements: only elements array[0..length-1 are analysed.
      Throws:
      NullPointerException - if percentileLevels or array argument is null.
      IllegalArgumentException - if length≤0, or length>array.length.

    • select

      public char select(int from, int to, int requiredIndex, char[] array)
      Optimized version of select(long, long, long, ArrayComparator, ArrayExchanger) method for selecting the element from char[] array.

      Parameters:
      from - index of the first analysed element of some data array, inclusive.
      to - index of the last analysed element of some data array, exclusive.
      requiredIndex - index inside the array, that should be placed to correct place in increasing order.
      array - data array.
      Throws:
      NullPointerException - if array argument is null.
      IllegalArgumentException - if from > to or from < 0, or if requiredIndex is outside from..to-1 range.

    • select

      public void select(int[] percentileIndexes, short[] array, int length)
      Optimized version of select(long, long[], ArrayComparator, ArrayExchanger) method for selecting the element from first length elements of short[] array.

      Note: unlike select(long, long[], ArrayComparator, ArrayExchanger), this method does not check elements of percentileIndexes, that they are correct and correctly sorted. If they are incorrect, the results will be undefined. You can check them yourself by checkPercentileIndexes(int[], int) method.

      Note that the elements of this array are supposed to be unsigned: we always compare array[i] & 0xFFFF and array[j] & 0xFFFF instead of simple array[i] and array[j].

      Parameters:
      percentileIndexes - list of indexes inside the array, that should be placed to correct place in increasing order.
      array - data array.
      length - number of elements: only elements array[0..length-1 are analysed.
      Throws:
      NullPointerException - if percentileIndexes or array argument is null.
      IllegalArgumentException - if length≤0, or length>array.length.

    • select

      public void select(double[] percentileLevels, short[] array, int length)
      Optimized version of select(long, double[], ArrayComparator, ArrayExchanger) method for selecting the element from first length elements of short[] array.

      Note: unlike select(long, double[], ArrayComparator, ArrayExchanger), this method does not check elements of percentileLevels, that they are correct and correctly sorted. If they are incorrect, the results will be undefined. You can check them yourself by checkPercentileLevels(double[]) method.

      Note that the elements of this array are supposed to be unsigned: we always compare array[i] & 0xFFFF and array[j] & 0xFFFF instead of simple array[i] and array[j].

      Parameters:
      percentileLevels - list of percentile levels: required indexes, divided by array length.
      array - data array.
      length - number of elements: only elements array[0..length-1 are analysed.
      Throws:
      NullPointerException - if percentileLevels or array argument is null.
      IllegalArgumentException - if length≤0, or length>array.length.

    • select

      public short select(int from, int to, int requiredIndex, short[] array)
      Optimized version of select(long, long, long, ArrayComparator, ArrayExchanger) method for selecting the element from short[] array.

      Note that the elements of this array are supposed to be unsigned: we always compare array[i] & 0xFFFF and array[j] & 0xFFFF instead of simple array[i] and array[j].

      Parameters:
      from - index of the first analysed element of some data array, inclusive.
      to - index of the last analysed element of some data array, exclusive.
      requiredIndex - index inside the array, that should be placed to correct place in increasing order.
      array - data array.
      Throws:
      NullPointerException - if array argument is null.
      IllegalArgumentException - if from > to or from < 0, or if requiredIndex is outside from..to-1 range.

    • select

      public void select(int[] percentileIndexes, int[] array, int length)
      Optimized version of select(long, long[], ArrayComparator, ArrayExchanger) method for selecting the element from first length elements of int[] array.

      Note: unlike select(long, long[], ArrayComparator, ArrayExchanger), this method does not check elements of percentileIndexes, that they are correct and correctly sorted. If they are incorrect, the results will be undefined. You can check them yourself by checkPercentileIndexes(int[], int) method.

      Parameters:
      percentileIndexes - list of indexes inside the array, that should be placed to correct place in increasing order.
      array - data array.
      length - number of elements: only elements array[0..length-1 are analysed.
      Throws:
      NullPointerException - if percentileIndexes or array argument is null.
      IllegalArgumentException - if length≤0, or length>array.length.

    • select

      public void select(double[] percentileLevels, int[] array, int length)
      Optimized version of select(long, double[], ArrayComparator, ArrayExchanger) method for selecting the element from first length elements of int[] array.

      Note: unlike select(long, double[], ArrayComparator, ArrayExchanger), this method does not check elements of percentileLevels, that they are correct and correctly sorted. If they are incorrect, the results will be undefined. You can check them yourself by checkPercentileLevels(double[]) method.

      Parameters:
      percentileLevels - list of percentile levels: required indexes, divided by array length.
      array - data array.
      length - number of elements: only elements array[0..length-1 are analysed.
      Throws:
      NullPointerException - if percentileLevels or array argument is null.
      IllegalArgumentException - if length≤0, or length>array.length.

    • select

      public int select(int from, int to, int requiredIndex, int[] array)
      Optimized version of select(long, long, long, ArrayComparator, ArrayExchanger) method for selecting the element from int[] array.

      Parameters:
      from - index of the first analysed element of some data array, inclusive.
      to - index of the last analysed element of some data array, exclusive.
      requiredIndex - index inside the array, that should be placed to correct place in increasing order.
      array - data array.
      Throws:
      NullPointerException - if array argument is null.
      IllegalArgumentException - if from > to or from < 0, or if requiredIndex is outside from..to-1 range.

    • select

      public void select(int[] percentileIndexes, long[] array, int length)
      Optimized version of select(long, long[], ArrayComparator, ArrayExchanger) method for selecting the element from first length elements of long[] array.

      Note: unlike select(long, long[], ArrayComparator, ArrayExchanger), this method does not check elements of percentileIndexes, that they are correct and correctly sorted. If they are incorrect, the results will be undefined. You can check them yourself by checkPercentileIndexes(int[], int) method.

      Parameters:
      percentileIndexes - list of indexes inside the array, that should be placed to correct place in increasing order.
      array - data array.
      length - number of elements: only elements array[0..length-1 are analysed.
      Throws:
      NullPointerException - if percentileIndexes or array argument is null.
      IllegalArgumentException - if length≤0, or length>array.length.

    • select

      public void select(double[] percentileLevels, long[] array, int length)
      Optimized version of select(long, double[], ArrayComparator, ArrayExchanger) method for selecting the element from first length elements of long[] array.

      Note: unlike select(long, double[], ArrayComparator, ArrayExchanger), this method does not check elements of percentileLevels, that they are correct and correctly sorted. If they are incorrect, the results will be undefined. You can check them yourself by checkPercentileLevels(double[]) method.

      Parameters:
      percentileLevels - list of percentile levels: required indexes, divided by array length.
      array - data array.
      length - number of elements: only elements array[0..length-1 are analysed.
      Throws:
      NullPointerException - if percentileLevels or array argument is null.
      IllegalArgumentException - if length≤0, or length>array.length.

    • select

      public long select(int from, int to, int requiredIndex, long[] array)
      Optimized version of select(long, long, long, ArrayComparator, ArrayExchanger) method for selecting the element from long[] array.

      Parameters:
      from - index of the first analysed element of some data array, inclusive.
      to - index of the last analysed element of some data array, exclusive.
      requiredIndex - index inside the array, that should be placed to correct place in increasing order.
      array - data array.
      Throws:
      NullPointerException - if array argument is null.
      IllegalArgumentException - if from > to or from < 0, or if requiredIndex is outside from..to-1 range.

    • select

      public void select(int[] percentileIndexes, float[] array, int length)
      Optimized version of select(long, long[], ArrayComparator, ArrayExchanger) method for selecting the element from first length elements of float[] array.

      Note: unlike select(long, long[], ArrayComparator, ArrayExchanger), this method does not check elements of percentileIndexes, that they are correct and correctly sorted. If they are incorrect, the results will be undefined. You can check them yourself by checkPercentileIndexes(int[], int) method.

      Note that elements of float[] array are compared by Float.compare(float, float) method. So, NaN is considered to be equal to itself and greater than all other float values (including POSITIVE_INFINITY), and 0.0 is considered be greater than -0.0.

      Parameters:
      percentileIndexes - list of indexes inside the array, that should be placed to correct place in increasing order.
      array - data array.
      length - number of elements: only elements array[0..length-1 are analysed.
      Throws:
      NullPointerException - if percentileIndexes or array argument is null.
      IllegalArgumentException - if length≤0, or length>array.length.

    • select

      public void select(double[] percentileLevels, float[] array, int length)
      Optimized version of select(long, double[], ArrayComparator, ArrayExchanger) method for selecting the element from first length elements of float[] array.

      Note: unlike select(long, double[], ArrayComparator, ArrayExchanger), this method does not check elements of percentileLevels, that they are correct and correctly sorted. If they are incorrect, the results will be undefined. You can check them yourself by checkPercentileLevels(double[]) method.

      Note that elements of float[] array are compared by Float.compare(float, float) method. So, NaN is considered to be equal to itself and greater than all other float values (including POSITIVE_INFINITY), and 0.0 is considered be greater than -0.0.

      Parameters:
      percentileLevels - list of percentile levels: required indexes, divided by array length.
      array - data array.
      length - number of elements: only elements array[0..length-1 are analysed.
      Throws:
      NullPointerException - if percentileLevels or array argument is null.
      IllegalArgumentException - if length≤0, or length>array.length.

    • select

      public float select(int from, int to, int requiredIndex, float[] array)
      Optimized version of select(long, long, long, ArrayComparator, ArrayExchanger) method for selecting the element from float[] array.

      Note that elements of float[] array are compared by Float.compare(float, float) method. So, NaN is considered to be equal to itself and greater than all other float values (including POSITIVE_INFINITY), and 0.0 is considered be greater than -0.0.

      Parameters:
      from - index of the first analysed element of some data array, inclusive.
      to - index of the last analysed element of some data array, exclusive.
      requiredIndex - index inside the array, that should be placed to correct place in increasing order.
      array - data array.
      Throws:
      NullPointerException - if array argument is null.
      IllegalArgumentException - if from > to or from < 0, or if requiredIndex is outside from..to-1 range.

    • select

      public void select(int[] percentileIndexes, double[] array, int length)
      Optimized version of select(long, long[], ArrayComparator, ArrayExchanger) method for selecting the element from first length elements of double[] array.

      Note: unlike select(long, long[], ArrayComparator, ArrayExchanger), this method does not check elements of percentileIndexes, that they are correct and correctly sorted. If they are incorrect, the results will be undefined. You can check them yourself by checkPercentileIndexes(int[], int) method.

      Note that elements of double[] array are compared by Double.compare(double, double) method. So, NaN is considered to be equal to itself and greater than all other double alues (including POSITIVE_INFINITY), and 0.0 is considered be greater than -0.0.

      Parameters:
      percentileIndexes - list of indexes inside the array, that should be placed to correct place in increasing order.
      array - data array.
      length - number of elements: only elements array[0..length-1 are analysed.
      Throws:
      NullPointerException - if percentileIndexes or array argument is null.
      IllegalArgumentException - if length≤0, or length>array.length.

    • select

      public void select(double[] percentileLevels, double[] array, int length)
      Optimized version of select(long, double[], ArrayComparator, ArrayExchanger) method for selecting the element from first length elements of double[] array.

      Note: unlike select(long, double[], ArrayComparator, ArrayExchanger), this method does not check elements of percentileLevels, that they are correct and correctly sorted. If they are incorrect, the results will be undefined. You can check them yourself by checkPercentileLevels(double[]) method.

      Note that elements of double[] array are compared by Double.compare(double, double) method. So, NaN is considered to be equal to itself and greater than all other double alues (including POSITIVE_INFINITY), and 0.0 is considered be greater than -0.0.

      Parameters:
      percentileLevels - list of percentile levels: required indexes, divided by array length.
      array - data array.
      length - number of elements: only elements array[0..length-1 are analysed.
      Throws:
      NullPointerException - if percentileLevels or array argument is null.
      IllegalArgumentException - if length≤0, or length>array.length.

    • select

      public double select(int from, int to, int requiredIndex, double[] array)
      Optimized version of select(long, long, long, ArrayComparator, ArrayExchanger) method for selecting the element from double[] array.

      Note that elements of double[] array are compared by Double.compare(double, double) method. So, NaN is considered to be equal to itself and greater than all other double alues (including POSITIVE_INFINITY), and 0.0 is considered be greater than -0.0.

      Parameters:
      from - index of the first analysed element of some data array, inclusive.
      to - index of the last analysed element of some data array, exclusive.
      requiredIndex - index inside the array, that should be placed to correct place in increasing order.
      array - data array.
      Throws:
      NullPointerException - if array argument is null.
      IllegalArgumentException - if from > to or from < 0, or if requiredIndex is outside from..to-1 range.

    • percentileIndex

      public static long percentileIndex(double percentileLevel, long numberOfElements)
      Returns index of the percentile with the given level in the array with the given number of elements. The result of this method is 
           Math.round(percentileLevel * (numberOfElements - 1))
      Parameters:
      percentileLevel - percentile level.
      numberOfElements - number of elements in the array.
      Returns:
      corresponding index of the element in the increasing order.

    • percentileIndex

      public static int percentileIndex(double percentileLevel, int numberOfElements)
      Returns index of the percentile with the given level in the array with the given number of elements. The result of this method is 
           (int) Math.round(percentileLevel * (numberOfElements - 1))
      Parameters:
      percentileLevel - percentile level.
      numberOfElements - number of elements in the array.
      Returns:
      corresponding index of the element in the increasing order.

    • checkPercentileIndexes

      public static void checkPercentileIndexes(long[] percentileIndexes, long numberOfElements)
      Checks whether the given percentile indexes are correct for passing to select(long, long[], ArrayComparator, ArrayExchanger) method. Throws an exception if they are incorrect.
      Parameters:
      percentileIndexes - list of indexes inside the array, that should be placed to correct place in increasing order.
      numberOfElements - number of elements in the array.
      Throws:
      IllegalArgumentException - if numberOfElements≤0, or if percentileIndexes array is empty, or if it contains indexes outside 0..numberOfElements-1 range, or if it is not sorted in increasing order.

    • checkPercentileIndexes

      public static void checkPercentileIndexes(int[] percentileIndexes, int numberOfElements)
      Checks whether the given percentile indexes are correct for passing to select(int[], float[], int) and similar methods. Throws an exception if they are incorrect.
      Parameters:
      percentileIndexes - list of indexes inside the array, that should be placed to correct place in increasing order.
      numberOfElements - number of elements in the array.
      Throws:
      IllegalArgumentException - if numberOfElements≤0, or if percentileIndexes array is empty, or if it contains indexes outside 0..numberOfElements-1 range, or if it is not sorted in increasing order.

    • checkPercentileLevels

      public static void checkPercentileLevels(double[] percentileLevels)
      Checks whether the given percentile levels are correct for passing to select(long, double[], ArrayComparator, ArrayExchanger) method. Throws an exception if they are incorrect.
      Parameters:
      percentileLevels - list of percentile levels: required indexes, divided by array length.
      Throws:
      IllegalArgumentException - if percentileLevels array is empty, or if it contains elements outside 0..1 range or NaN, or if it is not sorted in increasing order.

    • toString

      public String toString()
      Overrides:
      toString in class Object