< prev index next >
src/java.base/share/classes/java/util/TimSort.java
Print this page
@@ -22,11 +22,11 @@
* Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
* or visit www.oracle.com if you need additional information or have any
* questions.
*/
-package java.util;
+package javany.util;
/**
* A stable, adaptive, iterative mergesort that requires far fewer than
* n lg(n) comparisons when running on partially sorted arrays, while
* offering performance comparable to a traditional mergesort when run
@@ -57,11 +57,11 @@
* sort, assuming the input array is large enough to warrant the full-blown
* TimSort. Small arrays are sorted in place, using a binary insertion sort.
*
* @author Josh Bloch
*/
-class TimSort<T> {
+class TimSort<any T> {
/**
* This is the minimum sized sequence that will be merged. Shorter
* sequences will be lengthened by calling binarySort. If the entire
* array is less than this length, no merges will be performed.
*
@@ -151,12 +151,11 @@
int len = a.length;
int tlen = (len < 2 * INITIAL_TMP_STORAGE_LENGTH) ?
len >>> 1 : INITIAL_TMP_STORAGE_LENGTH;
if (work == null || workLen < tlen || workBase + tlen > work.length) {
@SuppressWarnings({"unchecked", "UnnecessaryLocalVariable"})
- T[] newArray = (T[])java.lang.reflect.Array.newInstance
- (a.getClass().getComponentType(), tlen);
+ T[] newArray = new T[tlen];
tmp = newArray;
tmpBase = 0;
tmpLen = tlen;
}
else {
@@ -201,11 +200,11 @@
* @param work a workspace array (slice)
* @param workBase origin of usable space in work array
* @param workLen usable size of work array
* @since 1.8
*/
- static <T> void sort(T[] a, int lo, int hi, Comparator<? super T> c,
+ static <any T> void sort(T[] a, int lo, int hi, Comparator<? super T> c,
T[] work, int workBase, int workLen) {
assert c != null && a != null && lo >= 0 && lo <= hi && hi <= a.length;
int nRemaining = hi - lo;
if (nRemaining < 2)
@@ -268,11 +267,11 @@
* @param start the index of the first element in the range that is
* not already known to be sorted ({@code lo <= start <= hi})
* @param c comparator to used for the sort
*/
@SuppressWarnings("fallthrough")
- private static <T> void binarySort(T[] a, int lo, int hi, int start,
+ private static <any T> void binarySort(T[] a, int lo, int hi, int start,
Comparator<? super T> c) {
assert lo <= start && start <= hi;
if (start == lo)
start++;
for ( ; start < hi; start++) {
@@ -307,11 +306,11 @@
// Switch is just an optimization for arraycopy in default case
switch (n) {
case 2: a[left + 2] = a[left + 1];
case 1: a[left + 1] = a[left];
break;
- default: System.arraycopy(a, left, a, left + 1, n);
+ default: Any.arraycopy(a, left, a, left + 1, n);
}
a[left] = pivot;
}
}
@@ -338,11 +337,11 @@
It is required that {@code lo < hi}.
* @param c the comparator to used for the sort
* @return the length of the run beginning at the specified position in
* the specified array
*/
- private static <T> int countRunAndMakeAscending(T[] a, int lo, int hi,
+ private static <any T> int countRunAndMakeAscending(T[] a, int lo, int hi,
Comparator<? super T> c) {
assert lo < hi;
int runHi = lo + 1;
if (runHi == hi)
return 1;
@@ -365,14 +364,14 @@
*
* @param a the array in which a range is to be reversed
* @param lo the index of the first element in the range to be reversed
* @param hi the index after the last element in the range to be reversed
*/
- private static void reverseRange(Object[] a, int lo, int hi) {
+ private static <any T> void reverseRange(T[] a, int lo, int hi) {
hi--;
while (lo < hi) {
- Object t = a[lo];
+ T t = a[lo];
a[lo++] = a[hi];
a[hi--] = t;
}
}
@@ -528,11 +527,11 @@
* pretending that a[b - 1] is minus infinity and a[b + n] is infinity.
* In other words, key belongs at index b + k; or in other words,
* the first k elements of a should precede key, and the last n - k
* should follow it.
*/
- private static <T> int gallopLeft(T key, T[] a, int base, int len, int hint,
+ private static <any T> int gallopLeft(T key, T[] a, int base, int len, int hint,
Comparator<? super T> c) {
assert len > 0 && hint >= 0 && hint < len;
int lastOfs = 0;
int ofs = 1;
if (c.compare(key, a[base + hint]) > 0) {
@@ -598,11 +597,11 @@
* @param hint the index at which to begin the search, 0 <= hint < n.
* The closer hint is to the result, the faster this method will run.
* @param c the comparator used to order the range, and to search
* @return the int k, 0 <= k <= n such that a[b + k - 1] <= key < a[b + k]
*/
- private static <T> int gallopRight(T key, T[] a, int base, int len,
+ private static <any T> int gallopRight(T key, T[] a, int base, int len,
int hint, Comparator<? super T> c) {
assert len > 0 && hint >= 0 && hint < len;
int ofs = 1;
int lastOfs = 0;
@@ -681,20 +680,20 @@
T[] a = this.a; // For performance
T[] tmp = ensureCapacity(len1);
int cursor1 = tmpBase; // Indexes into tmp array
int cursor2 = base2; // Indexes int a
int dest = base1; // Indexes int a
- System.arraycopy(a, base1, tmp, cursor1, len1);
+ Any.arraycopy(a, base1, tmp, cursor1, len1);
// Move first element of second run and deal with degenerate cases
a[dest++] = a[cursor2++];
if (--len2 == 0) {
- System.arraycopy(tmp, cursor1, a, dest, len1);
+ Any.arraycopy(tmp, cursor1, a, dest, len1);
return;
}
if (len1 == 1) {
- System.arraycopy(a, cursor2, a, dest, len2);
+ Any.arraycopy(a, cursor2, a, dest, len2);
a[dest + len2] = tmp[cursor1]; // Last elt of run 1 to end of merge
return;
}
Comparator<? super T> c = this.c; // Use local variable for performance
@@ -732,11 +731,11 @@
*/
do {
assert len1 > 1 && len2 > 0;
count1 = gallopRight(a[cursor2], tmp, cursor1, len1, 0, c);
if (count1 != 0) {
- System.arraycopy(tmp, cursor1, a, dest, count1);
+ Any.arraycopy(tmp, cursor1, a, dest, count1);
dest += count1;
cursor1 += count1;
len1 -= count1;
if (len1 <= 1) // len1 == 1 || len1 == 0
break outer;
@@ -745,11 +744,11 @@
if (--len2 == 0)
break outer;
count2 = gallopLeft(tmp[cursor1], a, cursor2, len2, 0, c);
if (count2 != 0) {
- System.arraycopy(a, cursor2, a, dest, count2);
+ Any.arraycopy(a, cursor2, a, dest, count2);
dest += count2;
cursor2 += count2;
len2 -= count2;
if (len2 == 0)
break outer;
@@ -765,19 +764,19 @@
} // End of "outer" loop
this.minGallop = minGallop < 1 ? 1 : minGallop; // Write back to field
if (len1 == 1) {
assert len2 > 0;
- System.arraycopy(a, cursor2, a, dest, len2);
+ Any.arraycopy(a, cursor2, a, dest, len2);
a[dest + len2] = tmp[cursor1]; // Last elt of run 1 to end of merge
} else if (len1 == 0) {
throw new IllegalArgumentException(
"Comparison method violates its general contract!");
} else {
assert len2 == 0;
assert len1 > 1;
- System.arraycopy(tmp, cursor1, a, dest, len1);
+ Any.arraycopy(tmp, cursor1, a, dest, len1);
}
}
/**
* Like mergeLo, except that this method should be called only if
@@ -795,26 +794,26 @@
// Copy second run into temp array
T[] a = this.a; // For performance
T[] tmp = ensureCapacity(len2);
int tmpBase = this.tmpBase;
- System.arraycopy(a, base2, tmp, tmpBase, len2);
+ Any.arraycopy(a, base2, tmp, tmpBase, len2);
int cursor1 = base1 + len1 - 1; // Indexes into a
int cursor2 = tmpBase + len2 - 1; // Indexes into tmp array
int dest = base2 + len2 - 1; // Indexes into a
// Move last element of first run and deal with degenerate cases
a[dest--] = a[cursor1--];
if (--len1 == 0) {
- System.arraycopy(tmp, tmpBase, a, dest - (len2 - 1), len2);
+ Any.arraycopy(tmp, tmpBase, a, dest - (len2 - 1), len2);
return;
}
if (len2 == 1) {
dest -= len1;
cursor1 -= len1;
- System.arraycopy(a, cursor1 + 1, a, dest + 1, len1);
+ Any.arraycopy(a, cursor1 + 1, a, dest + 1, len1);
a[dest] = tmp[cursor2];
return;
}
Comparator<? super T> c = this.c; // Use local variable for performance
@@ -855,11 +854,11 @@
count1 = len1 - gallopRight(tmp[cursor2], a, base1, len1, len1 - 1, c);
if (count1 != 0) {
dest -= count1;
cursor1 -= count1;
len1 -= count1;
- System.arraycopy(a, cursor1 + 1, a, dest + 1, count1);
+ Any.arraycopy(a, cursor1 + 1, a, dest + 1, count1);
if (len1 == 0)
break outer;
}
a[dest--] = tmp[cursor2--];
if (--len2 == 1)
@@ -868,11 +867,11 @@
count2 = len2 - gallopLeft(a[cursor1], tmp, tmpBase, len2, len2 - 1, c);
if (count2 != 0) {
dest -= count2;
cursor2 -= count2;
len2 -= count2;
- System.arraycopy(tmp, cursor2 + 1, a, dest + 1, count2);
+ Any.arraycopy(tmp, cursor2 + 1, a, dest + 1, count2);
if (len2 <= 1) // len2 == 1 || len2 == 0
break outer;
}
a[dest--] = a[cursor1--];
if (--len1 == 0)
@@ -887,19 +886,19 @@
if (len2 == 1) {
assert len1 > 0;
dest -= len1;
cursor1 -= len1;
- System.arraycopy(a, cursor1 + 1, a, dest + 1, len1);
+ Any.arraycopy(a, cursor1 + 1, a, dest + 1, len1);
a[dest] = tmp[cursor2]; // Move first elt of run2 to front of merge
} else if (len2 == 0) {
throw new IllegalArgumentException(
"Comparison method violates its general contract!");
} else {
assert len1 == 0;
assert len2 > 0;
- System.arraycopy(tmp, tmpBase, a, dest - (len2 - 1), len2);
+ Any.arraycopy(tmp, tmpBase, a, dest - (len2 - 1), len2);
}
}
/**
* Ensures that the external array tmp has at least the specified
@@ -924,12 +923,11 @@
newSize = minCapacity;
else
newSize = Math.min(newSize, a.length >>> 1);
@SuppressWarnings({"unchecked", "UnnecessaryLocalVariable"})
- T[] newArray = (T[])java.lang.reflect.Array.newInstance
- (a.getClass().getComponentType(), newSize);
+ T[] newArray = new T[newSize];
tmp = newArray;
tmpLen = newSize;
tmpBase = 0;
}
return tmp;
< prev index next >