Class Arrays
- java.lang.Object
-
- it.unimi.dsi.fastutil.Arrays
-
public class Arrays extends java.lang.Object
A class providing static methods and objects that do useful things with arrays.In addition to commodity methods, this class contains
Swapper
-based implementations of quicksort and of a stable, in-place mergesort. These generic sorting methods can be used to sort any kind of list, but they find their natural usage, for instance, in sorting arrays in parallel.- See Also:
Arrays
-
-
Field Summary
Fields Modifier and Type Field Description static int
MAX_ARRAY_SIZE
This is a safe value used byArrayList
(as of Java 7) to avoid throwingOutOfMemoryError
on some JVMs.
-
Method Summary
All Methods Static Methods Concrete Methods Modifier and Type Method Description static void
ensureFromTo(int arrayLength, int from, int to)
Ensures that a range given by its first (inclusive) and last (exclusive) elements fits an array of given length.static void
ensureOffsetLength(int arrayLength, int offset, int length)
Ensures that a range given by an offset and a length fits an array of given length.static void
mergeSort(int from, int to, IntComparator c, Swapper swapper)
Sorts the specified range of elements using the specified swapper and according to the order induced by the specified comparator using mergesort.static void
parallelQuickSort(int from, int to, IntComparator comp, Swapper swapper)
Sorts the specified range of elements using the specified swapper and according to the order induced by the specified comparator using a parallel quicksort.static void
quickSort(int from, int to, IntComparator comp, Swapper swapper)
Sorts the specified range of elements using the specified swapper and according to the order induced by the specified comparator using parallel quicksort.
-
-
-
Field Detail
-
MAX_ARRAY_SIZE
public static final int MAX_ARRAY_SIZE
This is a safe value used byArrayList
(as of Java 7) to avoid throwingOutOfMemoryError
on some JVMs. We adopt the same value.- See Also:
- Constant Field Values
-
-
Method Detail
-
ensureFromTo
public static void ensureFromTo(int arrayLength, int from, int to)
Ensures that a range given by its first (inclusive) and last (exclusive) elements fits an array of given length.This method may be used whenever an array range check is needed.
- Parameters:
arrayLength
- an array length.from
- a start index (inclusive).to
- an end index (inclusive).- Throws:
java.lang.IllegalArgumentException
- iffrom
is greater thanto
.java.lang.ArrayIndexOutOfBoundsException
- iffrom
orto
are greater thanarrayLength
or negative.
-
ensureOffsetLength
public static void ensureOffsetLength(int arrayLength, int offset, int length)
Ensures that a range given by an offset and a length fits an array of given length.This method may be used whenever an array range check is needed.
- Parameters:
arrayLength
- an array length.offset
- a start index for the fragmentlength
- a length (the number of elements in the fragment).- Throws:
java.lang.IllegalArgumentException
- iflength
is negative.java.lang.ArrayIndexOutOfBoundsException
- ifoffset
is negative oroffset
+length
is greater thanarrayLength
.
-
mergeSort
public static void mergeSort(int from, int to, IntComparator c, Swapper swapper)
Sorts the specified range of elements using the specified swapper and according to the order induced by the specified comparator using mergesort.This sort is guaranteed to be stable: equal elements will not be reordered as a result of the sort. The sorting algorithm is an in-place mergesort that is significantly slower than a standard mergesort, as its running time is O(n (log n)2), but it does not allocate additional memory; as a result, it can be used as a generic sorting algorithm.
- Parameters:
from
- the index of the first element (inclusive) to be sorted.to
- the index of the last element (exclusive) to be sorted.c
- the comparator to determine the order of the generic data (arguments are positions).swapper
- an object that knows how to swap the elements at any two positions.
-
parallelQuickSort
public static void parallelQuickSort(int from, int to, IntComparator comp, Swapper swapper)
Sorts the specified range of elements using the specified swapper and according to the order induced by the specified comparator using a parallel quicksort.The sorting algorithm is a tuned quicksort adapted from Jon L. Bentley and M. Douglas McIlroy, “Engineering a Sort Function”, Software: Practice and Experience, 23(11), pages 1249−1265, 1993.
This implementation uses a
ForkJoinPool
executor service withRuntime.availableProcessors()
parallel threads.- Parameters:
from
- the index of the first element (inclusive) to be sorted.to
- the index of the last element (exclusive) to be sorted.comp
- the comparator to determine the order of the generic data.swapper
- an object that knows how to swap the elements at any two positions.
-
quickSort
public static void quickSort(int from, int to, IntComparator comp, Swapper swapper)
Sorts the specified range of elements using the specified swapper and according to the order induced by the specified comparator using parallel quicksort.The sorting algorithm is a tuned quicksort adapted from Jon L. Bentley and M. Douglas McIlroy, “Engineering a Sort Function”, Software: Practice and Experience, 23(11), pages 1249−1265, 1993.
This implementation uses a
ForkJoinPool
executor service withRuntime.availableProcessors()
parallel threads.- Parameters:
from
- the index of the first element (inclusive) to be sorted.to
- the index of the last element (exclusive) to be sorted.comp
- the comparator to determine the order of the generic data.swapper
- an object that knows how to swap the elements at any two positions.
-
-