package java.util;
import java.lang.reflect.*;
public class Arrays {
// Suppresses default constructor, ensuring non-instantiability.
private Arrays() {
}
public static void sort(long[] a, int fromIndex, int toIndex) {
rangeCheck(a.length, fromIndex, toIndex);/*参数检查，不符合就会抛出IllegalArgumentException异常*/
sort1(a, fromIndex, toIndex-fromIndex);//排序
}
public static void sort(int[] a) {
sort1(a, 0, a.length);
}
/*
看起来很长的代码 其实是因为有七种基本类型的缘故
*/
/*
* The code for each of the seven primitive types is largely identical.
* C'est la vie.
*/
private static void sort1(long x[], int off, int len) {
// Insertion sort on smallest arrays
if (len < 7) {
for (int i=off; i<len+off; i++)
for (int j=i; j>off && x[j-1]>x[j]; j--)//这就是冒泡排序吧，，数量很少的时候 7是一个基准
swap(x, j, j-1);
return;
}
// Choose a partition element, v
int m = off + (len >> 1); // Small arrays, middle element
if (len > 7) {
int l = off;
int n = off + len - 1;
if (len > 40) { // Big arrays, pseudomedian of 9
int s = len/8;
l = med3(x, l, l+s, l+2*s);//取中间的数字啊
m = med3(x, m-s, m, m+s);
n = med3(x, n-2*s, n-s, n);
}
m = med3(x, l, m, n); // Mid-size, med of 3
}
long v = x[m];//为的是选择一个合适的数字做为基准，下面数据很多是排序就是快速排序了
// Establish Invariant: v* (<v)* (>v)* v*
int a = off, b = a, c = off + len - 1, d = c;
while(true) {
while (b <= c && x[b] <= v) {
if (x[b] == v)
swap(x, a++, b);
b++;
}
while (c >= b && x[c] >= v) {
if (x[c] == v)
swap(x, c, d--);
c--;
}
if (b > c)
break;
swap(x, b++, c--);
}
// Swap partition elements back to middle
int s, n = off + len;
s = Math.min(a-off, b-a ); vecswap(x, off, b-s, s);
s = Math.min(d-c, n-d-1); vecswap(x, b, n-s, s);
// Recursively sort non-partition-elements
if ((s = b-a) > 1)
sort1(x, off, s);
if ((s = d-c) > 1)
sort1(x, n-s, s);
}
/**
* Swaps x[a] with x[b].
*/
private static void swap(long x[], int a, int b) {
long t = x[a];
x[a] = x[b];
x[b] = t;
}
/**
* Swaps x[a .. (a+n-1)] with x[b .. (b+n-1)].
*/
private static void vecswap(long x[], int a, int b, int n) { //段与段进行交换
for (int i=0; i<n; i++, a++, b++)
swap(x, a, b);
}
/**
* Returns the index of the median of the three indexed longs.//三个数字为了得到中间数字的下标
*/
private static int med3(long x[], int a, int b, int c) {
return (x[a] < x[b] ?
(x[b] < x[c] ? b : x[a] < x[c] ? c : a) :
(x[b] > x[c] ? b : x[a] > x[c] ? c : a));
}
public static <T> void sort(T[] a, Comparator<? super T> c) { //引进了泛型方法 使用自己的比较器
T[] aux = (T[])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) {
rangeCheck(a.length, fromIndex, toIndex);
T[] aux = (T[])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++];
}
}
/**
* Check that fromIndex and toIndex are in range, and throw an
* appropriate exception if they aren't.
*/
private static void rangeCheck(int arrayLen, int fromIndex, int toIndex) {
if (fromIndex > toIndex)
throw new IllegalArgumentException("fromIndex(" + fromIndex +
") > toIndex(" + toIndex+")");
if (fromIndex < 0)
throw new ArrayIndexOutOfBoundsException(fromIndex);
if (toIndex > arrayLen)
throw new ArrayIndexOutOfBoundsException(toIndex);
}
// Searching 查询
public static int binarySearch(long[] a, int fromIndex, int toIndex,
long key) {
rangeCheck(a.length, fromIndex, toIndex);
return binarySearch0(a, fromIndex, toIndex, key);
}
// Like public version, but without range checks. 二分法查找啊
private static int binarySearch0(long[] a, int fromIndex, int toIndex,
long key) {
int low = fromIndex;
int high = toIndex - 1;
while (low <= high) {
int mid = (low + high) >>> 1;
long midVal = a[mid];
if (midVal < key)
low = mid + 1;
else if (midVal > key)
high = mid - 1;
else
return mid; // key found
}
return -(low + 1); // key not found.
}
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;
Comparable midVal = (Comparable)a[mid];
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.
}
public static boolean equals(long[] a, long[] 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++)
if (a[i] != a2[i])
return false;
return true;
}
public static boolean equals(int[] a, int[] a2) { //数组相当的判断 先比较 null 然后 长度 最后是各个值
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++)
if (a[i] != a2[i])
return false;
return true;
}
//填充就是放一些值。。
public static void fill(long[] a, long val) {
fill(a, 0, a.length, val);
}
public static void fill(long[] a, int fromIndex, int toIndex, long val) {
rangeCheck(a.length, fromIndex, toIndex);
for (int i=fromIndex; i<toIndex; i++)
a[i] = val;
}
public static void fill(Object[] a, Object val) {
fill(a, 0, a.length, 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 这个很常用的 调用了 System.arraycopy 方法 笔者不明白的是 这个和 System 有什么关系 自己实现不好么
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) {
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;
}
public static <T> T[] copyOfRange(T[] original, int from, int to) {
return copyOfRange(original, from, to, (Class<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);
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;
}
public static byte[] copyOfRange(byte[] original, int from, int to) {
int newLength = to - from;
if (newLength < 0)
throw new IllegalArgumentException(from + " > " + to);
byte[] copy = new byte[newLength];
System.arraycopy(original, from, copy, 0,
Math.min(original.length - from, newLength));
return copy;
}
public static <T> List<T> asList(T... a) {//返回一个受指定数组支持的固定大小的列表。
return new ArrayList<T>(a);
}
/**
* @serial include
*/
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) {
if (array==null)
throw new NullPointerException();
a = array;
}
public int size() {
return a.length;
}
public Object[] toArray() {
return a.clone();
}
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;
}
public E get(int index) {
return a[index];
}
public E set(int index, E element) {
E oldValue = a[index];
a[index] = element;
return oldValue;
}
public int indexOf(Object o) {
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;
}
public boolean contains(Object o) {
return indexOf(o) != -1;
}
}
//各种hashcode 不解释
public static int hashCode(int a[]) {
if (a == null)
return 0;
int result = 1;
for (int element : a)
result = 31 * result + element;
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;
}
/* 如果数组 a 的 e 元素本身是一个数组，则不能通过调用 e.hashCode() 计算其哈希码，但是，如果 e 是一个基本类型数组，则可以通过调用 Arrays.hashCode(e) 的适当重载来计算其哈希码，或者，如果 e 是一个引用类型数组，则可以通过递归调用 Arrays.deepHashCode(e) 来计算其哈希码。 */
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;
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);
if (!eq)
return false;
}
return true;
}
// 转换成字符串。。
public static String toString(int[] 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());
return buf.toString();
}
private static void deepToString(Object[] a, StringBuilder buf,
Set<Object[]> dejaVu) {
if (a == null) {
buf.append("null");
return;
}
dejaVu.add(a);
buf.append('[');
for (int i = 0; i < a.length; i++) {
if (i != 0)
buf.append(", ");
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());
}
}
}
buf.append(']');
dejaVu.remove(a);
}
}
刚开始看的时候真的觉得代码很长。。慢慢的，其实还好吧，很多都一样，我要好好学习java 不管怎么样 深入学习下源码总是有用的，可以避免犯错