Package one.microstream.collections

Class XSort

java.lang.Object
one.microstream.collections.XSort
public final class XSort
extends Object

  • Method Details

    • compare

      public static final int compare​(Boolean o1, Boolean o2)

    • compare

      public static final int compare​(Byte o1, Byte o2)

    • compare

      public static final int compare​(Short o1, Short o2)

    • compare

      public static final int compare​(Integer o1, Integer o2)

    • compare

      public static final int compare​(Float o1, Float o2)

    • compare

      public static final int compare​(Long o1, Long o2)

    • compare

      public static final int compare​(Double o1, Double o2)

    • compare

      public static final int compare​(String o1, String o2)

    • compareLength

      public static final int compareLength​(String o1, String o2)

    • compareIdentityHash

      public static final int compareIdentityHash​(Object o1, Object o2)

    • reverse

      public static final <E> Comparator<E> reverse​(Comparator<E> comparator)

    • chain

      @SafeVarargs public static final <E> Comparator<? super E> chain​(Comparator<? super E>... comparators)

    • sortAll

      @SafeVarargs public static final <T> void sortAll​(Comparator<? super T> sortation, Sortable<T>... sortables)

    • insertionsort

      public static void insertionsort​(boolean[] values)

    • insertionsort

      public static void insertionsort​(byte[] values)

    • insertionsort

      public static void insertionsort​(short[] values)

    • insertionsort

      public static void insertionsort​(int[] values)

    • insertionsort

      public static void insertionsort​(long[] values)

    • insertionsort

      public static void insertionsort​(float[] values)

    • insertionsort

      public static void insertionsort​(double[] values)

    • insertionsort

      public static void insertionsort​(char[] values)

    • insertionsort

      public static <E> void insertionsort​(E[] values, Comparator<? super E> comparator)

    • sort

      public static <E> void sort​(E[] elements, Comparator<? super E> comparator)
      Sorts the passed array as true instances (i.e. with a stable sorting algorithm) that adapts to already sorted or nearly sorted order.

      This method is best used as a general purpose sort.

      For a subranged version, see sort(Object[], int, int, Comparator).

      Due to sorting the passed array in a stable and fast (O(n log(n)) fashion, each call of this method instantiates an internal buffer array with the same size as the passed array. If the repeated creation of buffer arrays shall be prevented, use bufferedAdaptiveMergesort(Object[], Object[], Comparator) to explicitly provide a reusable buffer.

      If maintaining the original order of equal elements (stability) is not required, valueSort(Object[], Comparator) usually yields better performance and also does not require additional storage space by using an unstable sorting algorithm.
      Note that unstable sorting algorithms can achieve stable results, too, if the passed array contains only distinct elements (e.g. the content of a set) or if all equal elements are just references to the same instance.

      Type Parameters:
      E - the type of the elements to be sorted.
      Parameters:
      elements - the elements to be sorted.
      comparator - the Comparator defining the sortation order of the elements.
      See Also:
      valueSort(Object[], Comparator), bufferedAdaptiveMergesort(Object[], Object[], Comparator), sort(Object[], int, int, Comparator)

    • sort

      public static <E> void sort​(E[] elements, int start, int bound, Comparator<? super E> comparator)
      Subranged version of sort(Object[], Comparator).

      Example: sort(myElements, 0, 5, myElementComparator sorts the first 5 elements of array myElements (indices 0 to 4).

      For further information, see sort(Object[], Comparator).

      Type Parameters:
      E - the type of the elements to be sorted.
      Parameters:
      elements - the elements to be sorted.
      start - the starting index (inclusive) of the subrange to be sorted.
      bound - the bounding index (exclusive) of the subrange to be sorted.
      comparator - the Comparator defining the sortation order of the elements.

    • valueSort

      public static <V> void valueSort​(XSortableSequence<V> values, Comparator<? super V> comparator)

    • valueSort

      public static <V> void valueSort​(V[] values, Comparator<? super V> comparator)
      Sorts the passed array as values (i.e. with an unstable sorting algorithm).

      This method is best used for sorting arrays where stability is not important of that consist only of distinct values of equal values that actually are just duplicate references to the same instance.

      For a subranged version, see valueSort(Object[], int, int, Comparator).

      The used algorithm works inplace, i.e. does not instantiate any additional instances.

      If maintaining the original order of equal elements (stability) is required, sort(Object[], Comparator) has to be used instead, which maintains stability at the cost of performance and the need of additional temporary storage.

      Type Parameters:
      V - the type of the values to be sorted.
      Parameters:
      values - the values to be sorted.
      comparator - the Comparator defining the sortation order of the values.

    • valueSort

      public static <V> void valueSort​(V[] values, int start, int bound, Comparator<? super V> comparator)
      Subranged version of valueSort(Object[], Comparator).

      Example: valueSort(myValues, 0, 5, myvalueComparator sorts the first 5 values of array myElements (indices 0 to 4).

      For further information, see sort(Object[], Comparator).

      Type Parameters:
      V - the type of the values to be sorted.
      Parameters:
      values - the values to be sorted.
      start - the starting index (inclusive) of the subrange to be sorted.
      bound - the bounding index (exclusive) of the subrange to be sorted.
      comparator - the Comparator defining the sortation order of the elements.

    • bufferedAdaptiveMergesort

      public static <E> E[] bufferedAdaptiveMergesort​(E[] elements, E[] buffer, Comparator<? super E> comparator)
      Variation of sort(Object[], Comparator) that allows to pass an additional array to be used as the sorting algorithm's internal buffer.

      Use this method if the repeated buffer array instantiation of sort(Object[], Comparator) causes problems.

      If the passed buffer array is too small, a new buffer array of appropriate size is instantiated. The buffer (NOT the sorted array!) is returned.

      The buffer array is NOT cleared after the sorting is completed and may contain partial and inconsistent intermediate results. It is the external buffer array provider's responsibility to ensure programmatically correctness and memory leak avoidance for any content that might remain in the buffer array.

      Type Parameters:
      E - the type of the elements to be sorted.
      Parameters:
      elements - the array containing the elements to be sorted.
      buffer - the array to be used as a buffer by the sorting algorithm.
      comparator - the comparator defining the sortation order of the elements.
      Returns:
      the passed buffer array or the newly created buffer array if the passed buffer array was too small.
      See Also:
      sort(Object[], Comparator), bufferedAdaptiveMergesort(Object[], Object[], int, int, Comparator)

    • bufferedAdaptiveMergesort

      public static <E> E[] bufferedAdaptiveMergesort​(E[] elements, E[] buffer, int start, int bound, Comparator<? super E> comparator)
      Subranged version of bufferedAdaptiveMergesort(Object[], Object[], Comparator).

      Example: bufferSort(myElements, 0, 5, myElementComparator sorts the first 5 elements of array myElements (indices 0 to 4).

      For further information, see sort(Object[], Comparator).

      Type Parameters:
      E - the type of the elements to be sorted.
      Parameters:
      elements - the elements to be sorted.
      buffer - the array to be used as a buffer by the sorting algorithm.
      start - the starting index (inclusive) of the subrange to be sorted.
      bound - the bounding index (exclusive) of the subrange to be sorted.
      comparator - the Comparator defining the sortation order of the elements.
      Returns:
      the passed buffer array or the newly created buffer array if the passed buffer array was too small.

    • parallelSort

      public static <E> void parallelSort​(E[] elements, Comparator<? super E> comparator)
      Experimental parallel sorting that splits the sorting work up into two parts.

      As the work to do has to be big enough to pay off, the algorithm is capped at a certain minimum length (hardcoded 8192 at the moment) under which a normal singlethreaded sorting is executed. Really notable performance gain is achieved for lengths above 10.000. Length above 1 million yields performance boosts around 40% to 100%.

      Type Parameters:
      E - the type of the elements to be sorted.
      Parameters:
      elements - the elements to be sorted.
      comparator - the Comparator defining the sortation order of the elements.

    • sort

      public static final void sort​(int[] values) throws NullPointerException
      Sorts the passed values array.

      For a subranged version, see sort(int[], int, int).

      The used algorithm works inplace, i.e. does not instantiate any additional instances.

      Parameters:
      values - the values to be sorted.
      Throws:
      NullPointerException

    • sort

      public static final void sort​(long[] values) throws NullPointerException
      Throws:
      NullPointerException

    • sort

      public static final void sort​(int[] values, int start, int bound) throws NullPointerException, ArrayIndexOutOfBoundsException
      Subranged version of sort(int[]).

      Example: sort(myValues, 0, 5 sorts the first 5 values of array myElements (indices 0 to 4).

      For further information, see sort(int[]).

      Parameters:
      values - the values to be sorted.
      start - the starting index (inclusive) of the subrange to be sorted.
      bound - the bounding index (exclusive) of the subrange to be sorted.
      Throws:
      NullPointerException
      ArrayIndexOutOfBoundsException

    • quicksort

      public static final <E> void quicksort​(E[] values, Comparator<? super E> comparator) throws NullPointerException
      Throws:
      NullPointerException

    • quicksort

      public static final <E> void quicksort​(E[] values, int start, int bound, Comparator<? super E> comparator) throws NullPointerException
      Throws:
      NullPointerException

    • mergesort

      public static <E> void mergesort​(E[] values, Comparator<? super E> comparator)

    • mergesort

      public static <E> void mergesort​(E[] values, int start, int bound, Comparator<? super E> comparator)

    • bufferMergesort

      public static <E> E[] bufferMergesort​(E[] values, E[] buffer, Comparator<? super E> comparator)

    • bufferMergesort

      public static <E> E[] bufferMergesort​(E[] values, E[] buffer, int start, int bound, Comparator<? super E> comparator)

    • distinctsort

      public static void distinctsort​(int[] values)

    • copyDistinctsort

      public static void copyDistinctsort​(int[] values, int[] target)

    • bufferDistinctsort

      public static void bufferDistinctsort​(int[] values, int[] buffer)

    • distinctsort

      public static <E> void distinctsort​(E[] values, Comparator<? super E> comparator)

    • bufferDistinctsort

      public static <E> void bufferDistinctsort​(E[] values, E[] buffer, Comparator<? super E> comparator)

    • distinctsortInto

      public static <E> void distinctsortInto​(E[] values, E[] target, Comparator<? super E> comparator)

    • quicksortDualPivot

      public static void quicksortDualPivot​(int[] values)

    • quicksortDualPivot

      public static <E> void quicksortDualPivot​(E[] values, Comparator<? super E> comparator)

    • isIncreasing

      public static boolean isIncreasing​(int[] values)

    • isStrictlyIncreasing

      public static boolean isStrictlyIncreasing​(int[] values)

    • isDecreasing

      public static boolean isDecreasing​(int[] values)

    • isStrictlyDecreasing

      public static boolean isStrictlyDecreasing​(int[] values)

    • isIncreasing

      public static boolean isIncreasing​(int[] values, int startIndex, int endIndex)

    • isStrictlyIncreasing

      public static boolean isStrictlyIncreasing​(int[] values, int startIndex, int endIndex)

    • isDecreasing

      public static boolean isDecreasing​(int[] values, int startIndex, int endIndex)

    • isStrictlyDecreasing

      public static boolean isStrictlyDecreasing​(int[] values, int startIndex, int endIndex)

    • isSorted

      public static <E> boolean isSorted​(E[] values, Comparator<? super E> comparator)

    • isStrictlySorted

      public static <E> boolean isStrictlySorted​(E[] values, Comparator<? super E> comparator)

    • isReverseSorted

      public static <E> boolean isReverseSorted​(E[] values, int startIndex, int endIndex, Comparator<? super E> comparator)

    • isStrictlyReverseSorted

      public static <E> boolean isStrictlyReverseSorted​(E[] values, int startIndex, int endIndex, Comparator<? super E> comparator)

    • uniformitySimple

      public static int uniformitySimple​(int... values)
      Returns the number of subsequent equal values.

      Examples:
      uniformity(1,2,3,4,5) == 0
      uniformity(1,1,1,1,1) == 5
      uniformity(1,1,1,2,2) == 3
      uniformity(1,1,3,2,2) == 2

      Parameters:
      values - the values whose uniformity shall be calculated
      Returns:
      the uniformity count.

    • uniformity

      public static double uniformity​(int... values)