Package one.microstream.collections

Class XSort

java.lang.Object

one.microstream.collections.XSort

public final class XSort
extends Object

Constructor Summary

Constructors

Constructor	Description
XSort()

Method Summary

Modifier and Type	Method	Description
static void	bufferDistinctsort(int[] values, int[] buffer)
static <E> void	bufferDistinctsort(E[] values, E[] buffer, Comparator<? super E> comparator)
static <E> E[]	bufferedAdaptiveMergesort(E[] elements, E[] buffer, int start, int bound, Comparator<? super E> comparator)	Subranged version of bufferedAdaptiveMergesort(Object[],Object[],Comparator).
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.
static <E> E[]	bufferMergesort(E[] values, E[] buffer, int start, int bound, Comparator<? super E> comparator)
static <E> E[]	bufferMergesort(E[] values, E[] buffer, Comparator<? super E> comparator)
static <E> Comparator<? super E>	chain(Comparator<? super E>... comparators)
static int	compare(Boolean o1, Boolean o2)
static int	compare(Byte o1, Byte o2)
static int	compare(Double o1, Double o2)
static int	compare(Float o1, Float o2)
static int	compare(Integer o1, Integer o2)
static int	compare(Long o1, Long o2)
static int	compare(Short o1, Short o2)
static int	compare(String o1, String o2)
static int	compareIdentityHash(Object o1, Object o2)
static int	compareLength(String o1, String o2)
static void	copyDistinctsort(int[] values, int[] target)
static void	distinctsort(int[] values)
static <E> void	distinctsort(E[] values, Comparator<? super E> comparator)
static <E> void	distinctsortInto(E[] values, E[] target, Comparator<? super E> comparator)
static void	insertionsort(boolean[] values)
static void	insertionsort(byte[] values)
static void	insertionsort(char[] values)
static void	insertionsort(double[] values)
static void	insertionsort(float[] values)
static void	insertionsort(int[] values)
static void	insertionsort(long[] values)
static void	insertionsort(short[] values)
static <E> void	insertionsort(E[] values, Comparator<? super E> comparator)
static boolean	isDecreasing(int[] values)
static boolean	isDecreasing(int[] values, int startIndex, int endIndex)
static boolean	isIncreasing(int[] values)
static boolean	isIncreasing(int[] values, int startIndex, int endIndex)
static <E> boolean	isReverseSorted(E[] values, int startIndex, int endIndex, Comparator<? super E> comparator)
static <E> boolean	isSorted(E[] values, Comparator<? super E> comparator)
static boolean	isStrictlyDecreasing(int[] values)
static boolean	isStrictlyDecreasing(int[] values, int startIndex, int endIndex)
static boolean	isStrictlyIncreasing(int[] values)
static boolean	isStrictlyIncreasing(int[] values, int startIndex, int endIndex)
static <E> boolean	isStrictlyReverseSorted(E[] values, int startIndex, int endIndex, Comparator<? super E> comparator)
static <E> boolean	isStrictlySorted(E[] values, Comparator<? super E> comparator)
static <E> void	mergesort(E[] values, int start, int bound, Comparator<? super E> comparator)
static <E> void	mergesort(E[] values, Comparator<? super E> comparator)
static <E> void	parallelSort(E[] elements, Comparator<? super E> comparator)	Experimental parallel sorting that splits the sorting work up into two parts.
static <E> void	quicksort(E[] values, int start, int bound, Comparator<? super E> comparator)
static <E> void	quicksort(E[] values, Comparator<? super E> comparator)
static void	quicksortDualPivot(int[] values)
static <E> void	quicksortDualPivot(E[] values, Comparator<? super E> comparator)
static <E> Comparator<E>	reverse(Comparator<E> comparator)
static void	sort(int[] values)	Sorts the passed values array.
static void	sort(int[] values, int start, int bound)	Subranged version of sort(int[]).
static void	sort(long[] values)
static <E> void	sort(E[] elements, int start, int bound, Comparator<? super E> comparator)	Subranged version of sort(Object[],Comparator).
static <E> void	sort(E[] elements, Comparator<? super E> comparator)	Sorts the passed array as true instances (i.e.
static <T> void	sortAll(Comparator<? super T> sortation, Sortable<T>... sortables)
static double	uniformity(int... values)
static int	uniformitySimple(int... values)	Returns the number of subsequent equal values.
static <V> void	valueSort(XSortableSequence<V> values, Comparator<? super V> comparator)
static <V> void	valueSort(V[] values, int start, int bound, Comparator<? super V> comparator)	Subranged version of valueSort(Object[],Comparator).
static <V> void	valueSort(V[] values, Comparator<? super V> comparator)	Sorts the passed array as values (i.e.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

XSort

public XSort()

Method Detail

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 orginal 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 arraymyElements (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 orginal 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 arraymyElements (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 programmatical 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 arraymyElements (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.

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 -

Parameters:

elements -

comparator -

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 arraymyElements (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)