package java.util;
import java.lang.reflect.Array;
import java.util.concurrent.ForkJoinPool;
import java.util.function.BinaryOperator;
import java.util.function.Consumer;
import java.util.function.DoubleBinaryOperator;
import java.util.function.IntBinaryOperator;
import java.util.function.IntFunction;
import java.util.function.IntToDoubleFunction;
import java.util.function.IntToLongFunction;
import java.util.function.IntUnaryOperator;
import java.util.function.LongBinaryOperator;
import java.util.function.UnaryOperator;
import java.util.stream.DoubleStream;
import java.util.stream.IntStream;
import java.util.stream.LongStream;
import java.util.stream.Stream;
import java.util.stream.StreamSupport;
////提供排序，并行排序，流，并行流的工具方法，并行执行函数接口的静态方法
// Sort ,
//去除了重载函数(意义相同，只是类型不同)
public class Arrays {
/**
* The minimum array length below which a parallel sorting
* algorithm will not further partition the sorting task. Using
* smaller sizes typically results in memory contention across
* tasks that makes parallel speedups unlikely.
*/
private static final int MIN_ARRAY_SORT_GRAN = 1 << 13;
// Suppresses default constructor, ensuring non-instantiability.
private Arrays(){}
//用于排序的内部类，自然顺序
static final class NaturalOrder implements Comparator<Object> {
@SuppressWarnings("unchecked")
public int compare(Object first, Object second){
return ((Comparable<Object>) first).compareTo(second);
}
static final NaturalOrder INSTANCE = new NaturalOrder();
}
//检查数组越界
private static void rangeCheck(int arrayLength, int fromIndex, int toIndex){
if(fromIndex > toIndex){
throw new IllegalArgumentException(
"fromIndex(" + fromIndex + ") > toIndex(" + toIndex + ")");
}
if(fromIndex < 0){
throw new ArrayIndexOutOfBoundsException(fromIndex);
}
if(toIndex > arrayLength){
throw new ArrayIndexOutOfBoundsException(toIndex);
}
}
// 使用DualPivotQuicksort 快排排序，去除了其他类型的重载 **********************//
public static void sort(int[] a){
DualPivotQuicksort.sort(a, 0, a.length - 1, null, 0, 0);
}
public static void sort(int[] a, int fromIndex, int toIndex){
rangeCheck(a.length, fromIndex, toIndex);
DualPivotQuicksort.sort(a, fromIndex, toIndex - 1, null, 0, 0);
}
//并行排序，通过ForkJoinPool实现并行排序
public static void parallelSort(long[] a){
int n = a.length, p, g;
if(n <= MIN_ARRAY_SORT_GRAN ||
(p = ForkJoinPool.getCommonPoolParallelism()) == 1)
DualPivotQuicksort.sort(a, 0, n - 1, null, 0, 0);
else
new ArraysParallelSortHelpers.FJLong.Sorter
(null, a, new long[n], 0, n, 0,
((g = n / (p << 2)) <= MIN_ARRAY_SORT_GRAN) ?
MIN_ARRAY_SORT_GRAN : g).invoke();
}
public static void parallelSort(long[] a, int fromIndex, int toIndex){
rangeCheck(a.length, fromIndex, toIndex);
int n = toIndex - fromIndex, p, g;
if(n <= MIN_ARRAY_SORT_GRAN ||
(p = ForkJoinPool.getCommonPoolParallelism()) == 1)
DualPivotQuicksort.sort(a, fromIndex, toIndex - 1, null, 0, 0);
else
new ArraysParallelSortHelpers.FJLong.Sorter
(null, a, new long[n], fromIndex, n, 0,
((g = n / (p << 2)) <= MIN_ARRAY_SORT_GRAN) ?
MIN_ARRAY_SORT_GRAN : g).invoke();
}
@SuppressWarnings("unchecked")
public static <T extends Comparable<? super T>> void parallelSort(T[] a){
int n = a.length, p, g;
if(n <= MIN_ARRAY_SORT_GRAN ||
(p = ForkJoinPool.getCommonPoolParallelism()) == 1)
TimSort.sort(a, 0, n, NaturalOrder.INSTANCE, null, 0, 0);
else
new ArraysParallelSortHelpers.FJObject.Sorter<T>
(null, a,
(T[]) Array.newInstance(a.getClass().getComponentType(), n),
0, n, 0, ((g = n / (p << 2)) <= MIN_ARRAY_SORT_GRAN) ?
MIN_ARRAY_SORT_GRAN : g, NaturalOrder.INSTANCE).invoke();
}
@SuppressWarnings("unchecked")
public static <T extends Comparable<? super T>>
void parallelSort(T[] a, int fromIndex, int toIndex){
rangeCheck(a.length, fromIndex, toIndex);
int n = toIndex - fromIndex, p, g;
if(n <= MIN_ARRAY_SORT_GRAN ||
(p = ForkJoinPool.getCommonPoolParallelism()) == 1)
TimSort.sort(a, fromIndex, toIndex, NaturalOrder.INSTANCE, null, 0, 0);
else
new ArraysParallelSortHelpers.FJObject.Sorter<T>
(null, a,
(T[]) Array.newInstance(a.getClass().getComponentType(), n),
fromIndex, n, 0, ((g = n / (p << 2)) <= MIN_ARRAY_SORT_GRAN) ?
MIN_ARRAY_SORT_GRAN : g, NaturalOrder.INSTANCE).invoke();
}
@SuppressWarnings("unchecked")
public static <T> void parallelSort(T[] a, Comparator<? super T> cmp){
if(cmp == null)
cmp = NaturalOrder.INSTANCE;
int n = a.length, p, g;
if(n <= MIN_ARRAY_SORT_GRAN ||
(p = ForkJoinPool.getCommonPoolParallelism()) == 1)
TimSort.sort(a, 0, n, cmp, null, 0, 0);
else
new ArraysParallelSortHelpers.FJObject.Sorter<T>
(null, a,
(T[]) Array.newInstance(a.getClass().getComponentType(), n),
0, n, 0, ((g = n / (p << 2)) <= MIN_ARRAY_SORT_GRAN) ?
MIN_ARRAY_SORT_GRAN : g, cmp).invoke();
}
@SuppressWarnings("unchecked")
public static <T> void parallelSort(T[] a, int fromIndex, int toIndex,
Comparator<? super T> cmp){
rangeCheck(a.length, fromIndex, toIndex);
if(cmp == null)
cmp = NaturalOrder.INSTANCE;
int n = toIndex - fromIndex, p, g;
if(n <= MIN_ARRAY_SORT_GRAN ||
(p = ForkJoinPool.getCommonPoolParallelism()) == 1)
TimSort.sort(a, fromIndex, toIndex, cmp, null, 0, 0);
else
new ArraysParallelSortHelpers.FJObject.Sorter<T>
(null, a,
(T[]) Array.newInstance(a.getClass().getComponentType(), n),
fromIndex, n, 0, ((g = n / (p << 2)) <= MIN_ARRAY_SORT_GRAN) ?
MIN_ARRAY_SORT_GRAN : g, cmp).invoke();
}
//归并排序
static final class LegacyMergeSort {
private static final boolean userRequested =
java.security.AccessController.doPrivileged(
new sun.security.action.GetBooleanAction(
"java.util.Arrays.useLegacyMergeSort")).booleanValue();
}
//根据需要旋转归并排序还是TimSort
public static void sort(Object[] a){
if(LegacyMergeSort.userRequested)
legacyMergeSort(a);
el***parableTimSort.sort(a, 0, a.length, null, 0, 0);
}
private static void legacyMergeSort(Object[] a){
Object[] aux = a.clone();
mergeSort(aux, a, 0, a.length, 0);
}
public static void sort(Object[] a, int fromIndex, int toIndex){
rangeCheck(a.length, fromIndex, toIndex);
if(LegacyMergeSort.userRequested)
legacyMergeSort(a, fromIndex, toIndex);
el***parableTimSort.sort(a, fromIndex, toIndex, null, 0, 0);
}
private static void legacyMergeSort(Object[] a,
int fromIndex, int toIndex){
Object[] aux = copyOfRange(a, fromIndex, toIndex);
mergeSort(aux, a, fromIndex, toIndex, -fromIndex);
}
private static final int INSERTIONSORT_THRESHOLD = 7;
private static void mergeSort(Object[] src,
Object[] dest,
int low,
int high,
int off){
int length = high - low;
// Insertion sort on smallest arrays
if(length < INSERTIONSORT_THRESHOLD){
for(int i = low; i < high; i++){
for(int j = i; j > low &&
((Comparable) dest[j - 1]).compareTo(dest[j]) > 0; j--){ swap(dest, j, j - 1); }
}
return;
}
// Recursively sort halves of dest into src
int destLow = low;
int destHigh = high;
low += off;
high += off;
int mid = (low + high) >>> 1;
mergeSort(dest, src, low, mid, -off);
mergeSort(dest, src, mid, high, -off);
// If list is already sorted, just copy from src to dest. This is an
// optimization that results in faster sorts for nearly ordered lists.
if(((Comparable) src[mid - 1]).compareTo(src[mid]) <= 0){
System.arraycopy(src, low, dest, destLow, length);
return;
}
// Merge sorted halves (now in src) into dest
for(int i = destLow, p = low, q = mid; i < destHigh; i++){
if(q >= high || p < mid && ((Comparable) src[p]).compareTo(src[q]) <= 0)
dest[i] = src[p++];
else
dest[i] = src[q++];
}
}
private static void swap(Object[] x, int a, int b){
Object t = x[a];
x[a] = x[b];
x[b] = t;
}
public static <T> void sort(T[] a, Comparator<? super T> c){
if(c == null){
sort(a);
}else{
if(LegacyMergeSort.userRequested)
legacyMergeSort(a, c);
else
TimSort.sort(a, 0, a.length, c, null, 0, 0);
}
}
private static <T> void legacyMergeSort(T[] a, Comparator<? super T> c){
T[] aux = a.clone();
if(c == null)
mergeSort(aux, a, 0, a.length, 0);
else
mergeSort(aux, a, 0, a.length, 0, c);
}
public static <T> void sort(T[] a, int fromIndex, int toIndex,
Comparator<? super T> c){
if(c == null){
sort(a, fromIndex, toIndex);
}else{
rangeCheck(a.length, fromIndex, toIndex);
if(LegacyMergeSort.userRequested)
legacyMergeSort(a, fromIndex, toIndex, c);
else
TimSort.sort(a, fromIndex, toIndex, c, null, 0, 0);
}
}
private static <T> void legacyMergeSort(T[] a, int fromIndex, int toIndex,
Comparator<? super T> c){
T[] aux = copyOfRange(a, fromIndex, toIndex);
if(c == null)
mergeSort(aux, a, fromIndex, toIndex, -fromIndex);
else
mergeSort(aux, a, fromIndex, toIndex, -fromIndex, c);
}
private static void mergeSort(Object[] src,
Object[] dest,
int low, int high, int off,
Comparator c){
int length = high - low;
// Insertion sort on smallest arrays
if(length < INSERTIONSORT_THRESHOLD){
for(int i = low; i < high; i++){
for(int j = i; j > low && c.compare(dest[j - 1], dest[j]) > 0; j--){ swap(dest, j, j - 1); }
}
return;
}
// Recursively sort halves of dest into src
int destLow = low;
int destHigh = high;
low += off;
high += off;
int mid = (low + high) >>> 1;
mergeSort(dest, src, low, mid, -off, c);
mergeSort(dest, src, mid, high, -off, c);
// If list is already sorted, just copy from src to dest. This is an
// optimization that results in faster sorts for nearly ordered lists.
if(c.compare(src[mid - 1], src[mid]) <= 0){
System.arraycopy(src, low, dest, destLow, length);
return;
}
// Merge sorted halves (now in src) into dest
for(int i = destLow, p = low, q = mid; i < destHigh; i++){
if(q >= high || p < mid && c.compare(src[p], src[q]) <= 0)
dest[i] = src[p++];
else
dest[i] = src[q++];
}
}
// Parallel prefix
public static <T> void parallelPrefix(T[] array, BinaryOperator<T> op){
Objects.requireNonNull(op);
if(array.length > 0)
new ArrayPrefixHelpers.CumulateTask<>
(null, op, array, 0, array.length).invoke();
}
public static <T> void parallelPrefix(T[] array, int fromIndex,
int toIndex, BinaryOperator<T> op){
Objects.requireNonNull(op);
rangeCheck(array.length, fromIndex, toIndex);
if(fromIndex < toIndex)
new ArrayPrefixHelpers.CumulateTask<>
(null, op, array, fromIndex, toIndex).invoke();
}
// Searching
public static int binarySearch(Object[] a, Object key){
return binarySearch0(a, 0, a.length, key);
}
public static int binarySearch(Object[] a, int fromIndex, int toIndex,
Object key){
rangeCheck(a.length, fromIndex, toIndex);
return binarySearch0(a, fromIndex, toIndex, key);
}
// Like public version, but without range checks.
private static int binarySearch0(Object[] a, int fromIndex, int toIndex,
Object key){
int low = fromIndex;
int high = toIndex - 1;
while (low <= high) {
int mid = (low + high) >>> 1;
@SuppressWarnings("rawtypes")
Comparable midVal = (Comparable) a[mid];
@SuppressWarnings("unchecked")
int cmp = midVal.compareTo(key);
if(cmp < 0)
low = mid + 1;
else if(cmp > 0)
high = mid - 1;
else
return mid; // key found
}
return -(low + 1); // key not found.
}
public static <T> int binarySearch(T[] a, T key, Comparator<? super T> c){
return binarySearch0(a, 0, a.length, key, c);
}
public static <T> int binarySearch(T[] a, int fromIndex, int toIndex,
T key, Comparator<? super T> c){
rangeCheck(a.length, fromIndex, toIndex);
return binarySearch0(a, fromIndex, toIndex, key, c);
}
// Like public version, but without range checks.
private static <T> int binarySearch0(T[] a, int fromIndex, int toIndex,
T key, Comparator<? super T> c){
if(c == null){
return binarySearch0(a, fromIndex, toIndex, key);
}
int low = fromIndex;
int high = toIndex - 1;
while (low <= high) {
int mid = (low + high) >>> 1;
T midVal = a[mid];
int cmp = c.compare(midVal, key);
if(cmp < 0)
low = mid + 1;
else if(cmp > 0)
high = mid - 1;
else
return mid; // key found
}
return -(low + 1); // key not found.
}
// Equality Testing
public static boolean equals(Object[] a, Object[] a2){
if(a == a2)
return true;
if(a == null || a2 == null)
return false;
int length = a.length;
if(a2.length != length)
return false;
for(int i = 0; i < length; i++){
Object o1 = a[i];
Object o2 = a2[i];
if(!(o1 == null ? o2 == null : o1.equals(o2)))
return false;
}
return true;
}
// Filling
public static void fill(Object[] a, Object val){
for(int i = 0, len = a.length; i < len; i++){ a[i] = val; }
}
public static void fill(Object[] a, int fromIndex, int toIndex, Object val){
rangeCheck(a.length, fromIndex, toIndex);
for(int i = fromIndex; i < toIndex; i++){ a[i] = val; }
}
// Cloning
public static <T> T[] copyOf(T[] original, int newLength){
return (T[]) copyOf(original, newLength, original.getClass());
}
public static <T, U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType){
@SuppressWarnings("unchecked")
T[] copy = ((Object) newType == (Object) Object[].class)
? (T[]) new Object[newLength]
: (T[]) Array.newInstance(newType.getComponentType(), newLength);
System.arraycopy(original, 0, copy, 0,
Math.min(original.length, newLength));
return copy;
}
@SuppressWarnings("unchecked")
public static <T> T[] copyOfRange(T[] original, int from, int to){
return copyOfRange(original, from, to, (Class<? extends T[]>) original.getClass());
}
public static <T, U> T[] copyOfRange(U[] original, int from, int to, Class<? extends T[]> newType){
int newLength = to - from;
if(newLength < 0)
throw new IllegalArgumentException(from + " > " + to);
@SuppressWarnings("unchecked")
T[] copy = ((Object) newType == (Object) Object[].class)
? (T[]) new Object[newLength]
: (T[]) Array.newInstance(newType.getComponentType(), newLength);
System.arraycopy(original, from, copy, 0,
Math.min(original.length - from, newLength));
return copy;
}
// Misc
@SafeVarargs
@SuppressWarnings("varargs")
public static <T> List<T> asList(T... a){
return new ArrayList<>(a);
}
private static class ArrayList<E> extends AbstractList<E>
implements RandomAccess, java.io.Serializable {
private static final long serialVersionUID = -2764017481108945198L;
private final E[] a;
ArrayList(E[] array){
a = Objects.requireNonNull(array);
}
@Override
public int size(){
return a.length;
}
@Override
public Object[] toArray(){
return a.clone();
}
@Override
@SuppressWarnings("unchecked")
public <T> T[] toArray(T[] a){
int size = size();
if(a.length < size)
return Arrays.copyOf(this.a, size,
(Class<? extends T[]>) a.getClass());
System.arraycopy(this.a, 0, a, 0, size);
if(a.length > size)
a[size] = null;
return a;
}
@Override
public E get(int index){
return a[index];
}
@Override
public E set(int index, E element){
E oldValue = a[index];
a[index] = element;
return oldValue;
}
@Override
public int indexOf(Object o){
E[] a = this.a;
if(o == null){
for(int i = 0; i < a.length; i++){
if(a[i] == null)
return i;
}
}else{
for(int i = 0; i < a.length; i++){
if(o.equals(a[i]))
return i;
}
}
return -1;
}
@Override
public boolean contains(Object o){
return indexOf(o) != -1;
}
@Override
public Spliterator<E> spliterator(){
return Spliterators.spliterator(a, Spliterator.ORDERED);
}
@Override
public void forEach(Consumer<? super E> action){
Objects.requireNonNull(action);
for(E e : a){
action.accept(e);
}
}
@Override
public void replaceAll(UnaryOperator<E> operator){
Objects.requireNonNull(operator);
E[] a = this.a;
for(int i = 0; i < a.length; i++){
a[i] = operator.apply(a[i]);
}
}
@Override
public void sort(Comparator<? super E> c){
Arrays.sort(a, c);
}
}
public static int hashCode(long a[]){
if(a == null)
return 0;
int result = 1;
for(long element : a){
int elementHash = (int) (element ^ (element >>> 32));
result = 31 * result + elementHash;
}
return result;
}
public static int hashCode(double a[]){
if(a == null)
return 0;
int result = 1;
for(double element : a){
long bits = Double.doubleToLongBits(element);
result = 31 * result + (int) (bits ^ (bits >>> 32));
}
return result;
}
public static int hashCode(Object a[]){
if(a == null)
return 0;
int result = 1;
for(Object element : a){ result = 31 * result + (element == null ? 0 : element.hashCode()); }
return result;
}
//把所有ele加起来
public static int deepHashCode(Object a[]){
if(a == null)
return 0;
int result = 1;
for(Object element : a){
int elementHash = 0;
if(element instanceof Object[])
elementHash = deepHashCode((Object[]) element);
else if(element instanceof byte[])
elementHash = hashCode((byte[]) element);
else if(element instanceof short[])
elementHash = hashCode((short[]) element);
else if(element instanceof int[])
elementHash = hashCode((int[]) element);
else if(element instanceof long[])
elementHash = hashCode((long[]) element);
else if(element instanceof char[])
elementHash = hashCode((char[]) element);
else if(element instanceof float[])
elementHash = hashCode((float[]) element);
else if(element instanceof double[])
elementHash = hashCode((double[]) element);
else if(element instanceof boolean[])
elementHash = hashCode((boolean[]) element);
else if(element != null)
elementHash = element.hashCode();
result = 31 * result + elementHash;
}
return result;
}
public static boolean deepEquals(Object[] a1, Object[] a2){
if(a1 == a2)
return true;
if(a1 == null || a2 == null)
return false;
int length = a1.length;
if(a2.length != length)
return false;
for(int i = 0; i < length; i++){
Object e1 = a1[i];
Object e2 = a2[i];
if(e1 == e2)
continue;
if(e1 == null)
return false;
// Figure out whether the two elements are equal
boolean eq = deepEquals0(e1, e2);
if(!eq)
return false;
}
return true;
}
static boolean deepEquals0(Object e1, Object e2){
assert e1 != null;
boolean eq;
if(e1 instanceof Object[] && e2 instanceof Object[])
eq = deepEquals((Object[]) e1, (Object[]) e2);
else if(e1 instanceof byte[] && e2 instanceof byte[])
eq = equals((byte[]) e1, (byte[]) e2);
else if(e1 instanceof short[] && e2 instanceof short[])
eq = equals((short[]) e1, (short[]) e2);
else if(e1 instanceof int[] && e2 instanceof int[])
eq = equals((int[]) e1, (int[]) e2);
else if(e1 instanceof long[] && e2 instanceof long[])
eq = equals((long[]) e1, (long[]) e2);
else if(e1 instanceof char[] && e2 instanceof char[])
eq = equals((char[]) e1, (char[]) e2);
else if(e1 instanceof float[] && e2 instanceof float[])
eq = equals((float[]) e1, (float[]) e2);
else if(e1 instanceof double[] && e2 instanceof double[])
eq = equals((double[]) e1, (double[]) e2);
else if(e1 instanceof boolean[] && e2 instanceof boolean[])
eq = equals((boolean[]) e1, (boolean[]) e2);
else
eq = e1.equals(e2);
return eq;
}
public static String toString(long[] a){
if(a == null)
return "null";
int iMax = a.length - 1;
if(iMax == -1)
return "[]";
StringBuilder b = new StringBuilder();
b.append('[');
for(int i = 0; ; i++){
b.append(a[i]);
if(i == iMax)
return b.append(']').toString();
b.append(", ");
}
}
public static String toString(Object[] a){
if(a == null)
return "null";
int iMax = a.length - 1;
if(iMax == -1)
return "[]";
StringBuilder b = new StringBuilder();
b.append('[');
for(int i = 0; ; i++){
b.append(String.valueOf(a[i]));
if(i == iMax)
return b.append(']').toString();
b.append(", ");
}
}
public static String deepToString(Object[] a){
if(a == null)
return "null";
int bufLen = 20 * a.length;
if(a.length != 0 && bufLen <= 0)
bufLen = Integer.MAX_VALUE;
StringBuilder buf = new StringBuilder(bufLen);
deepToString(a, buf, new HashSet<Object[]>());
return buf.toString();
}
private static void deepToString(Object[] a, StringBuilder buf,
Set<Object[]> dejaVu){
if(a == null){
buf.append("null");
return;
}
int iMax = a.length - 1;
if(iMax == -1){
buf.append("[]");
return;
}
dejaVu.add(a);
buf.append('[');
for(int i = 0; ; i++){
Object element = a[i];
if(element == null){
buf.append("null");
}else{
Class<?> eClass = element.getClass();
if(eClass.isArray()){
if(eClass == byte[].class)
buf.append(toString((byte[]) element));
else if(eClass == short[].class)
buf.append(toString((short[]) element));
else if(eClass == int[].class)
buf.append(toString((int[]) element));
else if(eClass == long[].class)
buf.append(toString((long[]) element));
else if(eClass == char[].class)
buf.append(toString((char[]) element));
else if(eClass == float[].class)
buf.append(toString((float[]) element));
else if(eClass == double[].class)
buf.append(toString((double[]) element));
else if(eClass == boolean[].class)
buf.append(toString((boolean[]) element));
else{ // element is an array of object references
if(dejaVu.contains(element))
buf.append("[...]");
else
deepToString((Object[]) element, buf, dejaVu);
}
}else{ // element is non-null and not an array
buf.append(element.toString());
}
}
if(i == iMax)
break;
buf.append(", ");
}
buf.append(']');
dejaVu.remove(a);
}
public static <T> void setAll(T[] array, IntFunction<? extends T> generator){
Objects.requireNonNull(generator);
for(int i = 0; i < array.length; i++){ array[i] = generator.apply(i); }
}
public static <T> void parallelSetAll(T[] array, IntFunction<? extends T> generator){
Objects.requireNonNull(generator);
IntStream.range(0, array.length).parallel().forEach(i -> { array[i] = generator.apply(i); });
}
public static <T> Spliterator<T> spliterator(T[] array){
return Spliterators.spliterator(array,
Spliterator.ORDERED | Spliterator.IMMUTABLE);
}
public static <T> Spliterator<T> spliterator(T[] array, int startInclusive, int endExclusive){
return Spliterators.spliterator(array, startInclusive, endExclusive,
Spliterator.ORDERED | Spliterator.IMMUTABLE);
}
public static <T> Stream<T> stream(T[] array){
return stream(array, 0, array.length);
}
public static <T> Stream<T> stream(T[] array, int startInclusive, int endExclusive){
return StreamSupport.stream(spliterator(array, startInclusive, endExclusive), false);
}
}
京公网安备 11010502036488号