Package icyllis.modernui.util

# Class AlgorithmUtils

java.lang.Object
icyllis.modernui.util.AlgorithmUtils

public final class AlgorithmUtils extends Object

- ## Method Summary

  Modifier and Type
  Method
  Description
  `static double`
  `averageStable(double[] a)`
  Calculate arithmetic mean without intermediate overflow or underflow.
  `static double`
  `averageStable(double[] a, int start, int limit)`
  Calculate arithmetic mean without intermediate overflow or underflow.
  `static int`
  `ceil(int[] a, int value)`
  Returns an index of the first element in the range `[0, a.length)` such that `a[index] >= value`, or `a.length` if no such element is found.
  `static int`
  `ceil(int[] a, int first, int last, int value)`
  Returns an index of the first element in the range `[first, last)` such that `a[index] >= value`, or `last` if no such element is found.
  `static int`
  `ceil(long[] a, int first, int last, long value)`
  Returns an index of the first element in the range `[first, last)` such that `a[index] >= value`, or `last` if no such element is found.
  `static int`
  `ceil(long[] a, long value)`
  Returns an index of the first element in the range `[0, a.length)` such that `a[index] >= value`, or `a.length` if no such element is found.
  `static <T> int`
  `ceil(T[] a, int first, int last, T value, Comparator<? super T> c)`
  Returns an index of the first element in the range `[first, last)` such that `a[index] >= value`, or `last` if no such element is found.
  `static <T> int`
  `ceil(T[] a, T value, Comparator<? super T> c)`
  Returns an index of the first element in the range `[0, a.length)` such that `a[index] >= value`, or `a.length` if no such element is found.
  `static int`
  `floor(int[] a, int value)`
  Returns an index of the last element in the range `[0, a.length)` such that `a[index] <= value`, or `-1` if no such element is found.
  `static int`
  `floor(int[] a, int first, int last, int value)`
  Returns an index of the last element in the range `[first, last)` such that `a[index] <= value`, or `first - 1` if no such element is found.
  `static int`
  `floor(long[] a, int first, int last, long value)`
  Returns an index of the last element in the range `[first, last)` such that `a[index] <= value`, or `first - 1` if no such element is found.
  `static int`
  `floor(long[] a, long value)`
  Returns an index of the last element in the range `[0, a.length)` such that `a[index] <= value`, or `-1` if no such element is found.
  `static <T> int`
  `floor(T[] a, int first, int last, T value, Comparator<? super T> c)`
  Returns an index of the last element in the range `[first, last)` such that `a[index] <= value`, or `first - 1` if no such element is found.
  `static <T> int`
  `floor(T[] a, T value, Comparator<? super T> c)`
  Returns an index of the last element in the range `[0, a.length)` such that `a[index] <= value`, or `-1` if no such element is found.
  `static int`
  `gcd(int a, int b)`
  Returns the greatest common divisor of `a, b`.
  `static long`
  `gcd(long a, long b)`
  Returns the greatest common divisor of `a, b`.
  `static int`
  `higher(int[] a, int value)`
  Returns an index of the first element in the range `[0, a.length)` such that `a[index] > value`, or `a.length` if no such element is found.
  `static int`
  `higher(int[] a, int first, int last, int value)`
  Returns an index of the first element in the range `[first, last)` such that `a[index] > value`, or `last` if no such element is found.
  `static int`
  `higher(long[] a, int first, int last, long value)`
  Returns an index of the first element in the range `[first, last)` such that `a[index] > value`, or `last` if no such element is found.
  `static int`
  `higher(long[] a, long value)`
  Returns an index of the first element in the range `[0, a.length)` such that `a[index] > value`, or `a.length` if no such element is found.
  `static <T> int`
  `higher(T[] a, int first, int last, T value, Comparator<? super T> c)`
  Returns an index of the first element in the range `[first, last)` such that `a[index] > value`, or `last` if no such element is found.
  `static <T> int`
  `higher(T[] a, T value, Comparator<? super T> c)`
  Returns an index of the first element in the range `[0, a.length)` such that `a[index] > value`, or `a.length` if no such element is found.
  `static int`
  `lengthOfLIS(int[] a, int n)`
  Returns the length of the longest increasing subsequence (non-strictly).
  `static int`
  `lengthOfLIS(int[] a, int n, boolean strict)`
  Returns the length of the longest increasing subsequence.
  `static int`
  `lengthOfLIS(long[] a, int n)`
  Returns the length of the longest increasing subsequence (non-strictly).
  `static int`
  `lengthOfLIS(long[] a, int n, boolean strict)`
  Returns the length of the longest increasing subsequence.
  `static int`
  `lower(int[] a, int value)`
  Returns an index of the last element in the range `[0, a.length)` such that `a[index] < value`, or `-1` if no such element is found.
  `static int`
  `lower(int[] a, int first, int last, int value)`
  Returns an index of the last element in the range `[0, a.length)` such that `a[index] < value`, or `first - 1` if no such element is found.
  `static int`
  `lower(long[] a, int first, int last, long value)`
  Returns an index of the last element in the range `[0, a.length)` such that `a[index] < value`, or `first - 1` if no such element is found.
  `static int`
  `lower(long[] a, long value)`
  Returns an index of the last element in the range `[0, a.length)` such that `a[index] < value`, or `-1` if no such element is found.
  `static <T> int`
  `lower(T[] a, int first, int last, T value, Comparator<? super T> c)`
  Returns an index of the last element in the range `[0, a.length)` such that `a[index] < value`, or `first - 1` if no such element is found.
  `static <T> int`
  `lower(T[] a, T value, Comparator<? super T> c)`
  Returns an index of the last element in the range `[0, a.length)` such that `a[index] < value`, or `-1` if no such element is found.
  `static int`
  `quickModPow(int a, int b, int m)`
  Returns `a^b mod m`, no overflow checks.
  `static long`
  `quickModPow(long a, long b, int m)`
  Returns `a^b mod m`, no overflow checks.
  `static int`
  `quickPow(int a, int b)`
  Returns `a^b`, no overflow checks.
  `static long`
  `quickPow(long a, long b)`
  Returns `a^b`, no overflow checks.

  ### Methods inherited from class java.lang.Object

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

- ## Method Details

  - ### gcd

    public static int gcd(int a, int b)
    Returns the greatest common divisor of `a, b`. Asserts `a >= 0 && b >= 0`.
    See Also:
      - IntMath

  - ### gcd

    public static long gcd(long a, long b)
    Returns the greatest common divisor of `a, b`. Asserts `a >= 0 && b >= 0`.
    See Also:
      - LongMath

  - ### quickPow

    public static int quickPow(int a, int b)
    Returns `a^b`, no overflow checks. Asserts `b >= 0`.
    Parameters:
      `a` - the base
      `b` - the exponent

  - ### quickPow

    public static long quickPow(long a, long b)
    Returns `a^b`, no overflow checks. Asserts `b >= 0`.
    Parameters:
      `a` - the base
      `b` - the exponent

  - ### quickModPow

    public static int quickModPow(int a, int b, int m)
    Returns `a^b mod m`, no overflow checks. Asserts `b >= 0 && m > 0`.

  - ### quickModPow

    public static long quickModPow(long a, long b, int m)
    Returns `a^b mod m`, no overflow checks. Asserts `b >= 0 && m > 0`.

  - ### lower

    public static int lower(@NonNull int[] a, int value)
    Returns an index of the last element in the range `[0, a.length)` such that `a[index] < value`, or `-1` if no such element is found. The elements in the range shall already be sorted or at least partitioned with respect to `value`.
    Parameters:
      `a` - the array to be searched
      `value` - the value to be searched for
    Returns:
      index of the search value, or `-1`
    See Also:
      - `Arrays.sort(int[])`

  - ### lower

    @Contract(pure=true) public static int lower(@NonNull int[] a, int first, int last, int value)
    Returns an index of the last element in the range `[0, a.length)` such that `a[index] < value`, or `first - 1` if no such element is found. The elements in the range shall already be sorted or at least partitioned with respect to `value`.
    Parameters:
      `a` - the array to be searched
      `first` - the index of the first element (inclusive) to be searched
      `last` - the index of the last element (exclusive) to be searched
      `value` - the value to be searched for
    Returns:
      index of the search value, or `first - 1`
    See Also:
      - `Arrays.sort(int[], int, int)`

  - ### lower

    @Contract(pure=true) public static int lower(@NonNull long[] a, long value)
    Returns an index of the last element in the range `[0, a.length)` such that `a[index] < value`, or `-1` if no such element is found. The elements in the range shall already be sorted or at least partitioned with respect to `value`.
    Parameters:
      `a` - the array to be searched
      `value` - the value to be searched for
    Returns:
      index of the search value, or `-1`
    See Also:
      - `Arrays.sort(long[])`

  - ### lower

    @Contract(pure=true) public static int lower(@NonNull long[] a, int first, int last, long value)
    Returns an index of the last element in the range `[0, a.length)` such that `a[index] < value`, or `first - 1` if no such element is found. The elements in the range shall already be sorted or at least partitioned with respect to `value`.
    Parameters:
      `a` - the array to be searched
      `first` - the index of the first element (inclusive) to be searched
      `last` - the index of the last element (exclusive) to be searched
      `value` - the value to be searched for
    Returns:
      index of the search value, or `first - 1`
    See Also:
      - `Arrays.sort(long[], int, int)`

  - ### lower

    public static <T> int lower(@NonNull T[] a, T value, @Nullable Comparator<? super T> c)
    Returns an index of the last element in the range `[0, a.length)` such that `a[index] < value`, or `-1` if no such element is found. The elements in the range shall already be sorted or at least partitioned with respect to `value`.
    Parameters:
      `a` - the array to be searched
      `value` - the value to be searched for
      `c` - the comparator by which the array is ordered. A `null` value indicates that the elements' natural ordering should be used.
    Returns:
      index of the search value, or `-1`
    See Also:
      - `Arrays.sort(Object[], Comparator)`

  - ### lower

    public static <T> int lower(@NonNull T[] a, int first, int last, T value, @Nullable Comparator<? super T> c)
    Returns an index of the last element in the range `[0, a.length)` such that `a[index] < value`, or `first - 1` if no such element is found. The elements in the range shall already be sorted or at least partitioned with respect to `value`.
    Parameters:
      `a` - the array to be searched
      `first` - the index of the first element (inclusive) to be searched
      `last` - the index of the last element (exclusive) to be searched
      `value` - the value to be searched for
      `c` - the comparator by which the array is ordered. A `null` value indicates that the elements' natural ordering should be used.
    Returns:
      index of the search value, or `first - 1`
    See Also:
      - `Arrays.sort(Object[], int, int, Comparator)`

  - ### floor

    public static int floor(@NonNull int[] a, int value)
    Returns an index of the last element in the range `[0, a.length)` such that `a[index] <= value`, or `-1` if no such element is found. The elements in the range shall already be sorted or at least partitioned with respect to `value`.
    Parameters:
      `a` - the array to be searched
      `value` - the value to be searched for
    Returns:
      index of the search value, or `-1`
    See Also:
      - `Arrays.sort(int[])`

  - ### floor

    @Contract(pure=true) public static int floor(@NonNull int[] a, int first, int last, int value)
    Returns an index of the last element in the range `[first, last)` such that `a[index] <= value`, or `first - 1` if no such element is found. The elements in the range shall already be sorted or at least partitioned with respect to `value`.
    Parameters:
      `a` - the array to be searched
      `first` - the index of the first element (inclusive) to be searched
      `last` - the index of the last element (exclusive) to be searched
      `value` - the value to be searched for
    Returns:
      index of the search value, or `first - 1`
    See Also:
      - `Arrays.sort(int[], int, int)`

  - ### floor

    @Contract(pure=true) public static int floor(@NonNull long[] a, long value)
    Returns an index of the last element in the range `[0, a.length)` such that `a[index] <= value`, or `-1` if no such element is found. The elements in the range shall already be sorted or at least partitioned with respect to `value`.
    Parameters:
      `a` - the array to be searched
      `value` - the value to be searched for
    Returns:
      index of the search value, or `-1`
    See Also:
      - `Arrays.sort(long[])`

  - ### floor

    @Contract(pure=true) public static int floor(@NonNull long[] a, int first, int last, long value)
    Returns an index of the last element in the range `[first, last)` such that `a[index] <= value`, or `first - 1` if no such element is found. The elements in the range shall already be sorted or at least partitioned with respect to `value`.
    Parameters:
      `a` - the array to be searched
      `first` - the index of the first element (inclusive) to be searched
      `last` - the index of the last element (exclusive) to be searched
      `value` - the value to be searched for
    Returns:
      index of the search value, or `first - 1`
    See Also:
      - `Arrays.sort(long[], int, int)`

  - ### floor

    public static <T> int floor(@NonNull T[] a, T value, @Nullable Comparator<? super T> c)
    Returns an index of the last element in the range `[0, a.length)` such that `a[index] <= value`, or `-1` if no such element is found. The elements in the range shall already be sorted or at least partitioned with respect to `value`.
    Parameters:
      `a` - the array to be searched
      `value` - the value to be searched for
      `c` - the comparator by which the array is ordered. A `null` value indicates that the elements' natural ordering should be used.
    Returns:
      index of the search value, or `-1`
    See Also:
      - `Arrays.sort(Object[], Comparator)`

  - ### floor

    public static <T> int floor(@NonNull T[] a, int first, int last, T value, @Nullable Comparator<? super T> c)
    Returns an index of the last element in the range `[first, last)` such that `a[index] <= value`, or `first - 1` if no such element is found. The elements in the range shall already be sorted or at least partitioned with respect to `value`.
    Parameters:
      `a` - the array to be searched
      `first` - the index of the first element (inclusive) to be searched
      `last` - the index of the last element (exclusive) to be searched
      `value` - the value to be searched for
      `c` - the comparator by which the array is ordered. A `null` value indicates that the elements' natural ordering should be used.
    Returns:
      index of the search value, or `first - 1`
    See Also:
      - `Arrays.sort(Object[], int, int, Comparator)`

  - ### ceil

    public static int ceil(@NonNull int[] a, int value)
    Returns an index of the first element in the range `[0, a.length)` such that `a[index] >= value`, or `a.length` if no such element is found. The elements in the range shall already be sorted or at least partitioned with respect to `value`.

    Equivalent to C++ `lower_bound`.

    Parameters:
      `a` - the array to be searched
      `value` - the value to be searched for
    Returns:
      index of the search value, or `a.length`
    See Also:
      - `Arrays.sort(int[])`

  - ### ceil

    @Contract(pure=true) public static int ceil(@NonNull int[] a, int first, int last, int value)
    Returns an index of the first element in the range `[first, last)` such that `a[index] >= value`, or `last` if no such element is found. The elements in the range shall already be sorted or at least partitioned with respect to `value`.

    Equivalent to C++ `lower_bound`.

    Parameters:
      `a` - the array to be searched
      `first` - the index of the first element (inclusive) to be searched
      `last` - the index of the last element (exclusive) to be searched
      `value` - the value to be searched for
    Returns:
      index of the search value, or `last`
    See Also:
      - `Arrays.sort(int[], int, int)`

  - ### ceil

    @Contract(pure=true) public static int ceil(@NonNull long[] a, long value)
    Returns an index of the first element in the range `[0, a.length)` such that `a[index] >= value`, or `a.length` if no such element is found. The elements in the range shall already be sorted or at least partitioned with respect to `value`.

    Equivalent to C++ `lower_bound`.

    Parameters:
      `a` - the array to be searched
      `value` - the value to be searched for
    Returns:
      index of the search value, or `a.length`
    See Also:
      - `Arrays.sort(long[])`

  - ### ceil

    @Contract(pure=true) public static int ceil(@NonNull long[] a, int first, int last, long value)
    Returns an index of the first element in the range `[first, last)` such that `a[index] >= value`, or `last` if no such element is found. The elements in the range shall already be sorted or at least partitioned with respect to `value`.

    Equivalent to C++ `lower_bound`.

    Parameters:
      `a` - the array to be searched
      `first` - the index of the first element (inclusive) to be searched
      `last` - the index of the last element (exclusive) to be searched
      `value` - the value to be searched for
    Returns:
      index of the search value, or `last`
    See Also:
      - `Arrays.sort(long[], int, int)`

  - ### ceil

    public static <T> int ceil(@NonNull T[] a, T value, @Nullable Comparator<? super T> c)
    Returns an index of the first element in the range `[0, a.length)` such that `a[index] >= value`, or `a.length` if no such element is found. The elements in the range shall already be sorted or at least partitioned with respect to `value`.

    Equivalent to C++ `lower_bound`.

    Parameters:
      `a` - the array to be searched
      `value` - the value to be searched for
      `c` - the comparator by which the array is ordered. A `null` value indicates that the elements' natural ordering should be used.
    Returns:
      index of the search value, or `a.length`
    See Also:
      - `Arrays.sort(Object[], Comparator)`

  - ### ceil

    public static <T> int ceil(@NonNull T[] a, int first, int last, T value, @Nullable Comparator<? super T> c)
    Returns an index of the first element in the range `[first, last)` such that `a[index] >= value`, or `last` if no such element is found. The elements in the range shall already be sorted or at least partitioned with respect to `value`.

    Equivalent to C++ `lower_bound`.

    Parameters:
      `a` - the array to be searched
      `first` - the index of the first element (inclusive) to be searched
      `last` - the index of the last element (exclusive) to be searched
      `value` - the value to be searched for
      `c` - the comparator by which the array is ordered. A `null` value indicates that the elements' natural ordering should be used.
    Returns:
      index of the search value, or `last`
    See Also:
      - `Arrays.sort(Object[], int, int, Comparator)`

  - ### higher

    public static int higher(@NonNull int[] a, int value)
    Returns an index of the first element in the range `[0, a.length)` such that `a[index] > value`, or `a.length` if no such element is found. The elements in the range shall already be sorted or at least partitioned with respect to `value`.

    Equivalent to C++ `upper_bound`.

    Parameters:
      `a` - the array to be searched
      `value` - the value to be searched for
    Returns:
      index of the search value, or `a.length`
    See Also:
      - `Arrays.sort(int[])`

  - ### higher

    @Contract(pure=true) public static int higher(@NonNull int[] a, int first, int last, int value)
    Returns an index of the first element in the range `[first, last)` such that `a[index] > value`, or `last` if no such element is found. The elements in the range shall already be sorted or at least partitioned with respect to `value`.

    Equivalent to C++ `upper_bound`.

    Parameters:
      `a` - the array to be searched
      `first` - the index of the first element (inclusive) to be searched
      `last` - the index of the last element (exclusive) to be searched
      `value` - the value to be searched for
    Returns:
      index of the search value, or `last`
    See Also:
      - `Arrays.sort(int[], int, int)`

  - ### higher

    public static int higher(@NonNull long[] a, long value)
    Returns an index of the first element in the range `[0, a.length)` such that `a[index] > value`, or `a.length` if no such element is found. The elements in the range shall already be sorted or at least partitioned with respect to `value`.

    Equivalent to C++ `upper_bound`.

    Parameters:
      `a` - the array to be searched
      `value` - the value to be searched for
    Returns:
      index of the search value, or `a.length`
    See Also:
      - `Arrays.sort(long[])`

  - ### higher

    public static int higher(@NonNull long[] a, int first, int last, long value)
    Returns an index of the first element in the range `[first, last)` such that `a[index] > value`, or `last` if no such element is found. The elements in the range shall already be sorted or at least partitioned with respect to `value`.

    Equivalent to C++ `upper_bound`.

    Parameters:
      `a` - the array to be searched
      `first` - the index of the first element (inclusive) to be searched
      `last` - the index of the last element (exclusive) to be searched
      `value` - the value to be searched for
    Returns:
      index of the search value, or `last`
    See Also:
      - `Arrays.sort(long[], int, int)`

  - ### higher

    public static <T> int higher(@NonNull T[] a, T value, @Nullable Comparator<? super T> c)
    Returns an index of the first element in the range `[0, a.length)` such that `a[index] > value`, or `a.length` if no such element is found. The elements in the range shall already be sorted or at least partitioned with respect to `value`.

    Equivalent to C++ `upper_bound`.

    Parameters:
      `a` - the array to be searched
      `value` - the value to be searched for
      `c` - the comparator by which the array is ordered. A `null` value indicates that the elements' natural ordering should be used.
    Returns:
      index of the search value, or `a.length`
    See Also:
      - `Arrays.sort(Object[], Comparator)`

  - ### higher

    public static <T> int higher(@NonNull T[] a, int first, int last, T value, @Nullable Comparator<? super T> c)
    Returns an index of the first element in the range `[first, last)` such that `a[index] > value`, or `last` if no such element is found. The elements in the range shall already be sorted or at least partitioned with respect to `value`.

    Equivalent to C++ `upper_bound`.

    Parameters:
      `a` - the array to be searched
      `first` - the index of the first element (inclusive) to be searched
      `last` - the index of the last element (exclusive) to be searched
      `value` - the value to be searched for
      `c` - the comparator by which the array is ordered. A `null` value indicates that the elements' natural ordering should be used.
    Returns:
      index of the search value, or `last`
    See Also:
      - `Arrays.sort(Object[], int, int, Comparator)`

  - ### lengthOfLIS

    @Contract(pure=true) public static int lengthOfLIS(@NonNull int[] a, int n)
    Returns the length of the longest increasing subsequence (non-strictly). This algorithm has a time complexity of O(n log(n)).

  - ### lengthOfLIS

    @Contract(pure=true) public static int lengthOfLIS(@NonNull int[] a, int n, boolean strict)
    Returns the length of the longest increasing subsequence. This algorithm has a time complexity of O(n log(n)).
    Parameters:
      `strict` - strictly increasing or not

  - ### lengthOfLIS

    @Contract(pure=true) public static int lengthOfLIS(@NonNull long[] a, int n)
    Returns the length of the longest increasing subsequence (non-strictly). This algorithm has a time complexity of O(n log(n)).

  - ### lengthOfLIS

    @Contract(pure=true) public static int lengthOfLIS(@NonNull long[] a, int n, boolean strict)
    Returns the length of the longest increasing subsequence. This algorithm has a time complexity of O(n log(n)).
    Parameters:
      `strict` - strictly increasing or not

  - ### averageStable

    public static double averageStable(@NonNull double[] a)
    Calculate arithmetic mean without intermediate overflow or underflow.

  - ### averageStable

    public static double averageStable(@NonNull double[] a, int start, int limit)
    Calculate arithmetic mean without intermediate overflow or underflow.