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.