Class Arrays

java.lang.Object
it.unimi.dsi.fastutil.Arrays

public class Arrays extends 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.

Some algorithms provide a parallel version that will by default use the common pool, but this can be overridden by calling the function in a task already in the ForkJoinPool that the operation should run in. For example, something along the lines of "poolToParallelSortIn.invoke(() -> parallelQuickSort(arrayToSort))" will run the parallel sort in poolToParallelSortIn instead of the default pool.

See Also:
  • Nested Class Summary

    Nested Classes
    Modifier and Type
    Class
    Description
    protected static class 
     
  • Field Summary

    Fields
    Modifier and Type
    Field
    Description
    static final int
    This is a safe value used by ArrayList (as of Java 7) to avoid throwing OutOfMemoryError on some JVMs.
  • Method Summary

    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.
    protected static void
    swap(Swapper swapper, int a, int b, int n)
    Swaps two sequences of elements using a provided swapper.

    Methods inherited from class java.lang.Object

    clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
  • Field Details

  • Method Details

    • 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.

      In Java 9 and up, this method should be considered deprecated in favor of the Objects.checkFromToIndex(int, int, int) method, which may be intrinsified in recent JVMs.

      Parameters:
      arrayLength - an array length (must be nonnegative).
      from - a start index (inclusive).
      to - an end index (exclusive).
      Throws:
      IllegalArgumentException - if from is greater than to.
      ArrayIndexOutOfBoundsException - if from or to are greater than arrayLength 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.

      In Java 9 and up, this method should be considered deprecated in favor of the Objects.checkFromIndexSize(int, int, int) method, which may be intrinsified in recent JVMs.

      Parameters:
      arrayLength - an array length (must be nonnegative).
      offset - a start index for the fragment
      length - a length (the number of elements in the fragment).
      Throws:
      IllegalArgumentException - if length is negative.
      ArrayIndexOutOfBoundsException - if offset is negative or offset+length is greater than arrayLength.
    • 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.
    • swap

      protected static void swap(Swapper swapper, int a, int b, int n)
      Swaps two sequences of elements using a provided swapper.
      Parameters:
      swapper - the swapper.
      a - a position in x.
      b - another position in x.
      n - the number of elements to exchange starting at a and b.
    • 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.

      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.

      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.