author | alanb |
Wed, 09 Feb 2011 15:59:27 +0000 | |
changeset 8193 | 626b859aabb2 |
parent 8188 | b90884cf34f5 |
child 9035 | 1255eb81cc2f |
permissions | -rw-r--r-- |
4177
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
1 |
/* |
5995
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
2 |
* Copyright (c) 2009, 2010, Oracle and/or its affiliates. All rights reserved. |
4177
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
3 |
* DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. |
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
4 |
* |
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
5 |
* This code is free software; you can redistribute it and/or modify it |
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
6 |
* under the terms of the GNU General Public License version 2 only, as |
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
7 |
* published by the Free Software Foundation. |
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
8 |
* |
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
9 |
* This code is distributed in the hope that it will be useful, but WITHOUT |
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
10 |
* ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or |
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
11 |
* FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License |
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
12 |
* version 2 for more details (a copy is included in the LICENSE file that |
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
13 |
* accompanied this code). |
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
14 |
* |
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
15 |
* You should have received a copy of the GNU General Public License version |
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
16 |
* 2 along with this work; if not, write to the Free Software Foundation, |
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
17 |
* Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. |
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
18 |
* |
5506 | 19 |
* Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA |
20 |
* or visit www.oracle.com if you need additional information or have any |
|
21 |
* questions. |
|
4177
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
22 |
*/ |
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
23 |
|
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
24 |
/* |
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
25 |
* @test |
8193
626b859aabb2
7018258: Dual-pivot updates in 7013585 can fail with ArrayIndexOutOfBoundsException
alanb
parents:
8188
diff
changeset
|
26 |
* @bug 6880672 6896573 6899694 6976036 7013585 7018258 |
4177
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
27 |
* @summary Exercise Arrays.sort |
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
28 |
* @build Sorting |
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
29 |
* @run main Sorting -shortrun |
4233 | 30 |
* |
31 |
* @author Vladimir Yaroslavskiy |
|
32 |
* @author Jon Bentley |
|
33 |
* @author Josh Bloch |
|
4177
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
34 |
*/ |
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
35 |
|
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
36 |
import java.util.Arrays; |
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
37 |
import java.util.Random; |
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
38 |
import java.io.PrintStream; |
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
39 |
|
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
40 |
public class Sorting { |
4233 | 41 |
private static final PrintStream out = System.out; |
42 |
private static final PrintStream err = System.err; |
|
43 |
||
44 |
// Array lengths used in a long run (default) |
|
45 |
private static final int[] LONG_RUN_LENGTHS = { |
|
5995
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
46 |
1, 2, 3, 5, 8, 13, 21, 34, 55, 100, 1000, 10000, 100000, 1000000 }; |
4177
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
47 |
|
4233 | 48 |
// Array lengths used in a short run |
5995
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
49 |
private static final int[] SHORT_RUN_LENGTHS = { |
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
50 |
1, 2, 3, 21, 55, 1000, 10000 }; |
4177
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
51 |
|
4233 | 52 |
// Random initial values used in a long run (default) |
6896
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
53 |
private static final long[] LONG_RUN_RANDOMS = { 666, 0xC0FFEE, 999 }; |
4233 | 54 |
|
55 |
// Random initial values used in a short run |
|
6896
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
56 |
private static final long[] SHORT_RUN_RANDOMS = { 666 }; |
4177
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
57 |
|
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
58 |
public static void main(String[] args) { |
4233 | 59 |
boolean shortRun = args.length > 0 && args[0].equals("-shortrun"); |
60 |
long start = System.currentTimeMillis(); |
|
61 |
||
62 |
if (shortRun) { |
|
63 |
testAndCheck(SHORT_RUN_LENGTHS, SHORT_RUN_RANDOMS); |
|
64 |
} else { |
|
65 |
testAndCheck(LONG_RUN_LENGTHS, LONG_RUN_RANDOMS); |
|
66 |
} |
|
67 |
long end = System.currentTimeMillis(); |
|
68 |
||
8193
626b859aabb2
7018258: Dual-pivot updates in 7013585 can fail with ArrayIndexOutOfBoundsException
alanb
parents:
8188
diff
changeset
|
69 |
out.format("PASSED in %d sec.\n", Math.round((end - start) / 1E3)); |
4233 | 70 |
} |
4177
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
71 |
|
4233 | 72 |
private static void testAndCheck(int[] lengths, long[] randoms) { |
5995
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
73 |
testEmptyAndNullIntArray(); |
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
74 |
testEmptyAndNullLongArray(); |
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
75 |
testEmptyAndNullShortArray(); |
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
76 |
testEmptyAndNullCharArray(); |
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
77 |
testEmptyAndNullByteArray(); |
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
78 |
testEmptyAndNullFloatArray(); |
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
79 |
testEmptyAndNullDoubleArray(); |
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
80 |
|
8193
626b859aabb2
7018258: Dual-pivot updates in 7013585 can fail with ArrayIndexOutOfBoundsException
alanb
parents:
8188
diff
changeset
|
81 |
for (int length : lengths) { |
626b859aabb2
7018258: Dual-pivot updates in 7013585 can fail with ArrayIndexOutOfBoundsException
alanb
parents:
8188
diff
changeset
|
82 |
testMergeSort(length); |
626b859aabb2
7018258: Dual-pivot updates in 7013585 can fail with ArrayIndexOutOfBoundsException
alanb
parents:
8188
diff
changeset
|
83 |
testAndCheckRange(length); |
626b859aabb2
7018258: Dual-pivot updates in 7013585 can fail with ArrayIndexOutOfBoundsException
alanb
parents:
8188
diff
changeset
|
84 |
testAndCheckSubArray(length); |
626b859aabb2
7018258: Dual-pivot updates in 7013585 can fail with ArrayIndexOutOfBoundsException
alanb
parents:
8188
diff
changeset
|
85 |
} |
626b859aabb2
7018258: Dual-pivot updates in 7013585 can fail with ArrayIndexOutOfBoundsException
alanb
parents:
8188
diff
changeset
|
86 |
for (long seed : randoms) { |
5995
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
87 |
for (int length : lengths) { |
8193
626b859aabb2
7018258: Dual-pivot updates in 7013585 can fail with ArrayIndexOutOfBoundsException
alanb
parents:
8188
diff
changeset
|
88 |
testAndCheckWithInsertionSort(length, new MyRandom(seed)); |
626b859aabb2
7018258: Dual-pivot updates in 7013585 can fail with ArrayIndexOutOfBoundsException
alanb
parents:
8188
diff
changeset
|
89 |
testAndCheckWithCheckSum(length, new MyRandom(seed)); |
626b859aabb2
7018258: Dual-pivot updates in 7013585 can fail with ArrayIndexOutOfBoundsException
alanb
parents:
8188
diff
changeset
|
90 |
testAndCheckWithScrambling(length, new MyRandom(seed)); |
626b859aabb2
7018258: Dual-pivot updates in 7013585 can fail with ArrayIndexOutOfBoundsException
alanb
parents:
8188
diff
changeset
|
91 |
testAndCheckFloat(length, new MyRandom(seed)); |
626b859aabb2
7018258: Dual-pivot updates in 7013585 can fail with ArrayIndexOutOfBoundsException
alanb
parents:
8188
diff
changeset
|
92 |
testAndCheckDouble(length, new MyRandom(seed)); |
626b859aabb2
7018258: Dual-pivot updates in 7013585 can fail with ArrayIndexOutOfBoundsException
alanb
parents:
8188
diff
changeset
|
93 |
testStable(length, new MyRandom(seed)); |
4233 | 94 |
} |
95 |
} |
|
96 |
} |
|
97 |
||
5995
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
98 |
private static void testEmptyAndNullIntArray() { |
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
99 |
ourDescription = "Check empty and null array"; |
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
100 |
Arrays.sort(new int[] {}); |
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
101 |
Arrays.sort(new int[] {}, 0, 0); |
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
102 |
|
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
103 |
try { |
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
104 |
Arrays.sort((int[]) null); |
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
105 |
} catch (NullPointerException expected) { |
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
106 |
try { |
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
107 |
Arrays.sort((int[]) null, 0, 0); |
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
108 |
} catch (NullPointerException expected2) { |
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
109 |
return; |
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
110 |
} |
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
111 |
failed("Arrays.sort(int[],fromIndex,toIndex) shouldn't " + |
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
112 |
"catch null array"); |
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
113 |
} |
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
114 |
failed("Arrays.sort(int[]) shouldn't catch null array"); |
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
115 |
} |
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
116 |
|
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
117 |
private static void testEmptyAndNullLongArray() { |
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
118 |
ourDescription = "Check empty and null array"; |
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
119 |
Arrays.sort(new long[] {}); |
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
120 |
Arrays.sort(new long[] {}, 0, 0); |
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
121 |
|
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
122 |
try { |
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
123 |
Arrays.sort((long[]) null); |
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
124 |
} catch (NullPointerException expected) { |
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
125 |
try { |
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
126 |
Arrays.sort((long[]) null, 0, 0); |
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
127 |
} catch (NullPointerException expected2) { |
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
128 |
return; |
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
129 |
} |
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
130 |
failed("Arrays.sort(long[],fromIndex,toIndex) shouldn't " + |
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
131 |
"catch null array"); |
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
132 |
} |
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
133 |
failed("Arrays.sort(long[]) shouldn't catch null array"); |
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
134 |
} |
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
135 |
|
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
136 |
private static void testEmptyAndNullShortArray() { |
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
137 |
ourDescription = "Check empty and null array"; |
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
138 |
Arrays.sort(new short[] {}); |
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
139 |
Arrays.sort(new short[] {}, 0, 0); |
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
140 |
|
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
141 |
try { |
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
142 |
Arrays.sort((short[]) null); |
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
143 |
} catch (NullPointerException expected) { |
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
144 |
try { |
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
145 |
Arrays.sort((short[]) null, 0, 0); |
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
146 |
} catch (NullPointerException expected2) { |
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
147 |
return; |
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
148 |
} |
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
149 |
failed("Arrays.sort(short[],fromIndex,toIndex) shouldn't " + |
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
150 |
"catch null array"); |
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
151 |
} |
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
152 |
failed("Arrays.sort(short[]) shouldn't catch null array"); |
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
153 |
} |
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
154 |
|
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
155 |
private static void testEmptyAndNullCharArray() { |
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
156 |
ourDescription = "Check empty and null array"; |
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
157 |
Arrays.sort(new char[] {}); |
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
158 |
Arrays.sort(new char[] {}, 0, 0); |
4177
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
159 |
|
5995
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
160 |
try { |
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
161 |
Arrays.sort((char[]) null); |
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
162 |
} catch (NullPointerException expected) { |
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
163 |
try { |
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
164 |
Arrays.sort((char[]) null, 0, 0); |
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
165 |
} catch (NullPointerException expected2) { |
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
166 |
return; |
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
167 |
} |
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
168 |
failed("Arrays.sort(char[],fromIndex,toIndex) shouldn't " + |
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
169 |
"catch null array"); |
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
170 |
} |
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
171 |
failed("Arrays.sort(char[]) shouldn't catch null array"); |
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
172 |
} |
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
173 |
|
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
174 |
private static void testEmptyAndNullByteArray() { |
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
175 |
ourDescription = "Check empty and null array"; |
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
176 |
Arrays.sort(new byte[] {}); |
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
177 |
Arrays.sort(new byte[] {}, 0, 0); |
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
178 |
|
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
179 |
try { |
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
180 |
Arrays.sort((byte[]) null); |
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
181 |
} catch (NullPointerException expected) { |
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
182 |
try { |
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
183 |
Arrays.sort((byte[]) null, 0, 0); |
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
184 |
} catch (NullPointerException expected2) { |
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
185 |
return; |
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
186 |
} |
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
187 |
failed("Arrays.sort(byte[],fromIndex,toIndex) shouldn't " + |
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
188 |
"catch null array"); |
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
189 |
} |
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
190 |
failed("Arrays.sort(byte[]) shouldn't catch null array"); |
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
191 |
} |
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
192 |
|
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
193 |
private static void testEmptyAndNullFloatArray() { |
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
194 |
ourDescription = "Check empty and null array"; |
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
195 |
Arrays.sort(new float[] {}); |
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
196 |
Arrays.sort(new float[] {}, 0, 0); |
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
197 |
|
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
198 |
try { |
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
199 |
Arrays.sort((float[]) null); |
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
200 |
} catch (NullPointerException expected) { |
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
201 |
try { |
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
202 |
Arrays.sort((float[]) null, 0, 0); |
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
203 |
} catch (NullPointerException expected2) { |
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
204 |
return; |
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
205 |
} |
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
206 |
failed("Arrays.sort(float[],fromIndex,toIndex) shouldn't " + |
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
207 |
"catch null array"); |
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
208 |
} |
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
209 |
failed("Arrays.sort(float[]) shouldn't catch null array"); |
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
210 |
} |
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
211 |
|
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
212 |
private static void testEmptyAndNullDoubleArray() { |
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
213 |
ourDescription = "Check empty and null array"; |
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
214 |
Arrays.sort(new double[] {}); |
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
215 |
Arrays.sort(new double[] {}, 0, 0); |
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
216 |
|
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
217 |
try { |
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
218 |
Arrays.sort((double[]) null); |
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
219 |
} catch (NullPointerException expected) { |
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
220 |
try { |
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
221 |
Arrays.sort((double[]) null, 0, 0); |
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
222 |
} catch (NullPointerException expected2) { |
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
223 |
return; |
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
224 |
} |
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
225 |
failed("Arrays.sort(double[],fromIndex,toIndex) shouldn't " + |
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
226 |
"catch null array"); |
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
227 |
} |
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
228 |
failed("Arrays.sort(double[]) shouldn't catch null array"); |
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
229 |
} |
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
230 |
|
8193
626b859aabb2
7018258: Dual-pivot updates in 7013585 can fail with ArrayIndexOutOfBoundsException
alanb
parents:
8188
diff
changeset
|
231 |
private static void testAndCheckSubArray(int length) { |
5995
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
232 |
ourDescription = "Check sorting of subarray"; |
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
233 |
int[] golden = new int[length]; |
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
234 |
boolean newLine = false; |
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
235 |
|
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
236 |
for (int m = 1; m < length / 2; m *= 2) { |
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
237 |
newLine = true; |
4233 | 238 |
int fromIndex = m; |
5995
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
239 |
int toIndex = length - m; |
4233 | 240 |
|
241 |
prepareSubArray(golden, fromIndex, toIndex, m); |
|
242 |
int[] test = golden.clone(); |
|
4177
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
243 |
|
4233 | 244 |
for (TypeConverter converter : TypeConverter.values()) { |
5995
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
245 |
out.println("Test 'subarray': " + converter + |
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
246 |
" length = " + length + ", m = " + m); |
4233 | 247 |
Object convertedGolden = converter.convert(golden); |
248 |
Object convertedTest = converter.convert(test); |
|
249 |
sortSubArray(convertedTest, fromIndex, toIndex); |
|
250 |
checkSubArray(convertedTest, fromIndex, toIndex, m); |
|
251 |
} |
|
252 |
} |
|
5995
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
253 |
if (newLine) { |
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
254 |
out.println(); |
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
255 |
} |
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
256 |
} |
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
257 |
|
8193
626b859aabb2
7018258: Dual-pivot updates in 7013585 can fail with ArrayIndexOutOfBoundsException
alanb
parents:
8188
diff
changeset
|
258 |
private static void testAndCheckRange(int length) { |
5995
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
259 |
ourDescription = "Check range check"; |
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
260 |
int[] golden = new int[length]; |
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
261 |
|
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
262 |
for (int m = 1; m < 2 * length; m *= 2) { |
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
263 |
for (int i = 1; i <= length; i++) { |
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
264 |
golden[i - 1] = i % m + m % i; |
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
265 |
} |
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
266 |
for (TypeConverter converter : TypeConverter.values()) { |
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
267 |
out.println("Test 'range': " + converter + |
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
268 |
", length = " + length + ", m = " + m); |
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
269 |
Object convertedGolden = converter.convert(golden); |
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
270 |
checkRange(convertedGolden, m); |
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
271 |
} |
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
272 |
} |
4177
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
273 |
out.println(); |
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
274 |
} |
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
275 |
|
8193
626b859aabb2
7018258: Dual-pivot updates in 7013585 can fail with ArrayIndexOutOfBoundsException
alanb
parents:
8188
diff
changeset
|
276 |
private static void testStable(int length, MyRandom random) { |
5995
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
277 |
ourDescription = "Check if sorting is stable"; |
8193
626b859aabb2
7018258: Dual-pivot updates in 7013585 can fail with ArrayIndexOutOfBoundsException
alanb
parents:
8188
diff
changeset
|
278 |
Pair[] a = build(length, random); |
4233 | 279 |
|
8193
626b859aabb2
7018258: Dual-pivot updates in 7013585 can fail with ArrayIndexOutOfBoundsException
alanb
parents:
8188
diff
changeset
|
280 |
out.println("Test 'stable': " + "random = " + random.getSeed() + |
5995
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
281 |
", length = " + length); |
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
282 |
Arrays.sort(a); |
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
283 |
checkSorted(a); |
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
284 |
checkStable(a); |
8193
626b859aabb2
7018258: Dual-pivot updates in 7013585 can fail with ArrayIndexOutOfBoundsException
alanb
parents:
8188
diff
changeset
|
285 |
out.println(); |
5995
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
286 |
} |
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
287 |
|
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
288 |
private static void checkSorted(Pair[] a) { |
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
289 |
for (int i = 0; i < a.length - 1; i++) { |
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
290 |
if (a[i].getKey() > a[i + 1].getKey()) { |
6896
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
291 |
failedSort(i, "" + a[i].getKey(), "" + a[i + 1].getKey()); |
4233 | 292 |
} |
5995
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
293 |
} |
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
294 |
} |
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
295 |
|
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
296 |
private static void checkStable(Pair[] a) { |
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
297 |
for (int i = 0; i < a.length / 4; ) { |
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
298 |
int key1 = a[i].getKey(); |
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
299 |
int value1 = a[i++].getValue(); |
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
300 |
int key2 = a[i].getKey(); |
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
301 |
int value2 = a[i++].getValue(); |
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
302 |
int key3 = a[i].getKey(); |
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
303 |
int value3 = a[i++].getValue(); |
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
304 |
int key4 = a[i].getKey(); |
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
305 |
int value4 = a[i++].getValue(); |
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
306 |
|
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
307 |
if (!(key1 == key2 && key2 == key3 && key3 == key4)) { |
6896
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
308 |
failed("On position " + i + " keys are different " + |
5995
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
309 |
key1 + ", " + key2 + ", " + key3 + ", " + key4); |
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
310 |
} |
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
311 |
if (!(value1 < value2 && value2 < value3 && value3 < value4)) { |
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
312 |
failed("Sorting is not stable at position " + i + |
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
313 |
". Second values have been changed: " + value1 + ", " + |
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
314 |
value2 + ", " + value3 + ", " + value4); |
4233 | 315 |
} |
316 |
} |
|
5995
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
317 |
} |
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
318 |
|
8193
626b859aabb2
7018258: Dual-pivot updates in 7013585 can fail with ArrayIndexOutOfBoundsException
alanb
parents:
8188
diff
changeset
|
319 |
private static Pair[] build(int length, Random random) { |
5995
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
320 |
Pair[] a = new Pair[length * 4]; |
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
321 |
|
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
322 |
for (int i = 0; i < a.length; ) { |
8193
626b859aabb2
7018258: Dual-pivot updates in 7013585 can fail with ArrayIndexOutOfBoundsException
alanb
parents:
8188
diff
changeset
|
323 |
int key = random.nextInt(); |
5995
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
324 |
a[i++] = new Pair(key, 1); |
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
325 |
a[i++] = new Pair(key, 2); |
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
326 |
a[i++] = new Pair(key, 3); |
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
327 |
a[i++] = new Pair(key, 4); |
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
328 |
} |
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
329 |
return a; |
4233 | 330 |
} |
331 |
||
5995
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
332 |
private static final class Pair implements Comparable<Pair> { |
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
333 |
Pair(int key, int value) { |
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
334 |
myKey = key; |
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
335 |
myValue = value; |
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
336 |
} |
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
337 |
|
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
338 |
int getKey() { |
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
339 |
return myKey; |
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
340 |
} |
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
341 |
|
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
342 |
int getValue() { |
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
343 |
return myValue; |
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
344 |
} |
4233 | 345 |
|
5995
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
346 |
public int compareTo(Pair pair) { |
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
347 |
if (myKey < pair.myKey) { |
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
348 |
return -1; |
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
349 |
} |
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
350 |
if (myKey > pair.myKey) { |
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
351 |
return 1; |
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
352 |
} |
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
353 |
return 0; |
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
354 |
} |
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
355 |
|
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
356 |
@Override |
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
357 |
public String toString() { |
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
358 |
return "(" + myKey + ", " + myValue + ")"; |
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
359 |
} |
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
360 |
|
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
361 |
private int myKey; |
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
362 |
private int myValue; |
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
363 |
} |
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
364 |
|
6896
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
365 |
|
8193
626b859aabb2
7018258: Dual-pivot updates in 7013585 can fail with ArrayIndexOutOfBoundsException
alanb
parents:
8188
diff
changeset
|
366 |
private static void testAndCheckWithInsertionSort(int length, MyRandom random) { |
6896
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
367 |
if (length > 1000) { |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
368 |
return; |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
369 |
} |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
370 |
ourDescription = "Check sorting with insertion sort"; |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
371 |
int[] golden = new int[length]; |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
372 |
|
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
373 |
for (int m = 1; m < 2 * length; m *= 2) { |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
374 |
for (UnsortedBuilder builder : UnsortedBuilder.values()) { |
8193
626b859aabb2
7018258: Dual-pivot updates in 7013585 can fail with ArrayIndexOutOfBoundsException
alanb
parents:
8188
diff
changeset
|
375 |
builder.build(golden, m, random); |
6896
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
376 |
int[] test = golden.clone(); |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
377 |
|
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
378 |
for (TypeConverter converter : TypeConverter.values()) { |
8193
626b859aabb2
7018258: Dual-pivot updates in 7013585 can fail with ArrayIndexOutOfBoundsException
alanb
parents:
8188
diff
changeset
|
379 |
out.println("Test 'insertion sort': " + converter + |
626b859aabb2
7018258: Dual-pivot updates in 7013585 can fail with ArrayIndexOutOfBoundsException
alanb
parents:
8188
diff
changeset
|
380 |
" " + builder + "random = " + random.getSeed() + |
626b859aabb2
7018258: Dual-pivot updates in 7013585 can fail with ArrayIndexOutOfBoundsException
alanb
parents:
8188
diff
changeset
|
381 |
", length = " + length + ", m = " + m); |
6896
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
382 |
Object convertedGolden = converter.convert(golden); |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
383 |
Object convertedTest1 = converter.convert(test); |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
384 |
Object convertedTest2 = converter.convert(test); |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
385 |
sort(convertedTest1); |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
386 |
sortByInsertionSort(convertedTest2); |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
387 |
compare(convertedTest1, convertedTest2); |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
388 |
} |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
389 |
} |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
390 |
} |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
391 |
out.println(); |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
392 |
} |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
393 |
|
8193
626b859aabb2
7018258: Dual-pivot updates in 7013585 can fail with ArrayIndexOutOfBoundsException
alanb
parents:
8188
diff
changeset
|
394 |
private static void testMergeSort(int length) { |
626b859aabb2
7018258: Dual-pivot updates in 7013585 can fail with ArrayIndexOutOfBoundsException
alanb
parents:
8188
diff
changeset
|
395 |
if (length < 1000) { |
626b859aabb2
7018258: Dual-pivot updates in 7013585 can fail with ArrayIndexOutOfBoundsException
alanb
parents:
8188
diff
changeset
|
396 |
return; |
626b859aabb2
7018258: Dual-pivot updates in 7013585 can fail with ArrayIndexOutOfBoundsException
alanb
parents:
8188
diff
changeset
|
397 |
} |
626b859aabb2
7018258: Dual-pivot updates in 7013585 can fail with ArrayIndexOutOfBoundsException
alanb
parents:
8188
diff
changeset
|
398 |
ourDescription = "Check merge sorting"; |
626b859aabb2
7018258: Dual-pivot updates in 7013585 can fail with ArrayIndexOutOfBoundsException
alanb
parents:
8188
diff
changeset
|
399 |
int[] golden = new int[length]; |
626b859aabb2
7018258: Dual-pivot updates in 7013585 can fail with ArrayIndexOutOfBoundsException
alanb
parents:
8188
diff
changeset
|
400 |
int period = 67; // java.util.DualPivotQuicksort.MAX_RUN_COUNT |
626b859aabb2
7018258: Dual-pivot updates in 7013585 can fail with ArrayIndexOutOfBoundsException
alanb
parents:
8188
diff
changeset
|
401 |
|
626b859aabb2
7018258: Dual-pivot updates in 7013585 can fail with ArrayIndexOutOfBoundsException
alanb
parents:
8188
diff
changeset
|
402 |
for (int m = period - 2; m <= period + 2; m++) { |
626b859aabb2
7018258: Dual-pivot updates in 7013585 can fail with ArrayIndexOutOfBoundsException
alanb
parents:
8188
diff
changeset
|
403 |
for (MergeBuilder builder : MergeBuilder.values()) { |
626b859aabb2
7018258: Dual-pivot updates in 7013585 can fail with ArrayIndexOutOfBoundsException
alanb
parents:
8188
diff
changeset
|
404 |
builder.build(golden, m); |
626b859aabb2
7018258: Dual-pivot updates in 7013585 can fail with ArrayIndexOutOfBoundsException
alanb
parents:
8188
diff
changeset
|
405 |
int[] test = golden.clone(); |
626b859aabb2
7018258: Dual-pivot updates in 7013585 can fail with ArrayIndexOutOfBoundsException
alanb
parents:
8188
diff
changeset
|
406 |
|
626b859aabb2
7018258: Dual-pivot updates in 7013585 can fail with ArrayIndexOutOfBoundsException
alanb
parents:
8188
diff
changeset
|
407 |
for (TypeConverter converter : TypeConverter.values()) { |
626b859aabb2
7018258: Dual-pivot updates in 7013585 can fail with ArrayIndexOutOfBoundsException
alanb
parents:
8188
diff
changeset
|
408 |
out.println("Test 'merge sort': " + converter + " " + |
626b859aabb2
7018258: Dual-pivot updates in 7013585 can fail with ArrayIndexOutOfBoundsException
alanb
parents:
8188
diff
changeset
|
409 |
builder + "length = " + length + ", m = " + m); |
626b859aabb2
7018258: Dual-pivot updates in 7013585 can fail with ArrayIndexOutOfBoundsException
alanb
parents:
8188
diff
changeset
|
410 |
Object convertedGolden = converter.convert(golden); |
626b859aabb2
7018258: Dual-pivot updates in 7013585 can fail with ArrayIndexOutOfBoundsException
alanb
parents:
8188
diff
changeset
|
411 |
sort(convertedGolden); |
626b859aabb2
7018258: Dual-pivot updates in 7013585 can fail with ArrayIndexOutOfBoundsException
alanb
parents:
8188
diff
changeset
|
412 |
checkSorted(convertedGolden); |
626b859aabb2
7018258: Dual-pivot updates in 7013585 can fail with ArrayIndexOutOfBoundsException
alanb
parents:
8188
diff
changeset
|
413 |
} |
626b859aabb2
7018258: Dual-pivot updates in 7013585 can fail with ArrayIndexOutOfBoundsException
alanb
parents:
8188
diff
changeset
|
414 |
} |
626b859aabb2
7018258: Dual-pivot updates in 7013585 can fail with ArrayIndexOutOfBoundsException
alanb
parents:
8188
diff
changeset
|
415 |
} |
626b859aabb2
7018258: Dual-pivot updates in 7013585 can fail with ArrayIndexOutOfBoundsException
alanb
parents:
8188
diff
changeset
|
416 |
out.println(); |
626b859aabb2
7018258: Dual-pivot updates in 7013585 can fail with ArrayIndexOutOfBoundsException
alanb
parents:
8188
diff
changeset
|
417 |
} |
626b859aabb2
7018258: Dual-pivot updates in 7013585 can fail with ArrayIndexOutOfBoundsException
alanb
parents:
8188
diff
changeset
|
418 |
|
626b859aabb2
7018258: Dual-pivot updates in 7013585 can fail with ArrayIndexOutOfBoundsException
alanb
parents:
8188
diff
changeset
|
419 |
private static void testAndCheckWithCheckSum(int length, MyRandom random) { |
5995
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
420 |
ourDescription = "Check sorting with check sum"; |
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
421 |
int[] golden = new int[length]; |
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
422 |
|
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
423 |
for (int m = 1; m < 2 * length; m *= 2) { |
4233 | 424 |
for (UnsortedBuilder builder : UnsortedBuilder.values()) { |
8193
626b859aabb2
7018258: Dual-pivot updates in 7013585 can fail with ArrayIndexOutOfBoundsException
alanb
parents:
8188
diff
changeset
|
425 |
builder.build(golden, m, random); |
4233 | 426 |
int[] test = golden.clone(); |
427 |
||
428 |
for (TypeConverter converter : TypeConverter.values()) { |
|
8193
626b859aabb2
7018258: Dual-pivot updates in 7013585 can fail with ArrayIndexOutOfBoundsException
alanb
parents:
8188
diff
changeset
|
429 |
out.println("Test 'check sum': " + converter + |
626b859aabb2
7018258: Dual-pivot updates in 7013585 can fail with ArrayIndexOutOfBoundsException
alanb
parents:
8188
diff
changeset
|
430 |
" " + builder + "random = " + random.getSeed() + |
626b859aabb2
7018258: Dual-pivot updates in 7013585 can fail with ArrayIndexOutOfBoundsException
alanb
parents:
8188
diff
changeset
|
431 |
", length = " + length + ", m = " + m); |
4233 | 432 |
Object convertedGolden = converter.convert(golden); |
433 |
Object convertedTest = converter.convert(test); |
|
434 |
sort(convertedTest); |
|
435 |
checkWithCheckSum(convertedTest, convertedGolden); |
|
436 |
} |
|
437 |
} |
|
438 |
} |
|
439 |
out.println(); |
|
440 |
} |
|
441 |
||
8193
626b859aabb2
7018258: Dual-pivot updates in 7013585 can fail with ArrayIndexOutOfBoundsException
alanb
parents:
8188
diff
changeset
|
442 |
private static void testAndCheckWithScrambling(int length, MyRandom random) { |
5995
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
443 |
ourDescription = "Check sorting with scrambling"; |
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
444 |
int[] golden = new int[length]; |
4177
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
445 |
|
4233 | 446 |
for (int m = 1; m <= 7; m++) { |
5995
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
447 |
if (m > length) { |
4233 | 448 |
break; |
449 |
} |
|
450 |
for (SortedBuilder builder : SortedBuilder.values()) { |
|
451 |
builder.build(golden, m); |
|
452 |
int[] test = golden.clone(); |
|
8193
626b859aabb2
7018258: Dual-pivot updates in 7013585 can fail with ArrayIndexOutOfBoundsException
alanb
parents:
8188
diff
changeset
|
453 |
scramble(test, random); |
4233 | 454 |
|
455 |
for (TypeConverter converter : TypeConverter.values()) { |
|
8193
626b859aabb2
7018258: Dual-pivot updates in 7013585 can fail with ArrayIndexOutOfBoundsException
alanb
parents:
8188
diff
changeset
|
456 |
out.println("Test 'scrambling': " + converter + |
626b859aabb2
7018258: Dual-pivot updates in 7013585 can fail with ArrayIndexOutOfBoundsException
alanb
parents:
8188
diff
changeset
|
457 |
" " + builder + "random = " + random.getSeed() + |
626b859aabb2
7018258: Dual-pivot updates in 7013585 can fail with ArrayIndexOutOfBoundsException
alanb
parents:
8188
diff
changeset
|
458 |
", length = " + length + ", m = " + m); |
4233 | 459 |
Object convertedGolden = converter.convert(golden); |
460 |
Object convertedTest = converter.convert(test); |
|
461 |
sort(convertedTest); |
|
462 |
compare(convertedTest, convertedGolden); |
|
463 |
} |
|
464 |
} |
|
465 |
} |
|
466 |
out.println(); |
|
467 |
} |
|
4177
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
468 |
|
8193
626b859aabb2
7018258: Dual-pivot updates in 7013585 can fail with ArrayIndexOutOfBoundsException
alanb
parents:
8188
diff
changeset
|
469 |
private static void testAndCheckFloat(int length, MyRandom random) { |
5995
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
470 |
ourDescription = "Check float sorting"; |
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
471 |
float[] golden = new float[length]; |
4233 | 472 |
final int MAX = 10; |
473 |
boolean newLine = false; |
|
474 |
||
475 |
for (int a = 0; a <= MAX; a++) { |
|
476 |
for (int g = 0; g <= MAX; g++) { |
|
477 |
for (int z = 0; z <= MAX; z++) { |
|
478 |
for (int n = 0; n <= MAX; n++) { |
|
479 |
for (int p = 0; p <= MAX; p++) { |
|
5995
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
480 |
if (a + g + z + n + p > length) { |
4233 | 481 |
continue; |
482 |
} |
|
5995
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
483 |
if (a + g + z + n + p < length) { |
4233 | 484 |
continue; |
485 |
} |
|
486 |
for (FloatBuilder builder : FloatBuilder.values()) { |
|
8193
626b859aabb2
7018258: Dual-pivot updates in 7013585 can fail with ArrayIndexOutOfBoundsException
alanb
parents:
8188
diff
changeset
|
487 |
out.println("Test 'float': random = " + random.getSeed() + |
626b859aabb2
7018258: Dual-pivot updates in 7013585 can fail with ArrayIndexOutOfBoundsException
alanb
parents:
8188
diff
changeset
|
488 |
", length = " + length + ", a = " + a + ", g = " + |
626b859aabb2
7018258: Dual-pivot updates in 7013585 can fail with ArrayIndexOutOfBoundsException
alanb
parents:
8188
diff
changeset
|
489 |
g + ", z = " + z + ", n = " + n + ", p = " + p); |
626b859aabb2
7018258: Dual-pivot updates in 7013585 can fail with ArrayIndexOutOfBoundsException
alanb
parents:
8188
diff
changeset
|
490 |
builder.build(golden, a, g, z, n, p, random); |
4233 | 491 |
float[] test = golden.clone(); |
8193
626b859aabb2
7018258: Dual-pivot updates in 7013585 can fail with ArrayIndexOutOfBoundsException
alanb
parents:
8188
diff
changeset
|
492 |
scramble(test, random); |
4233 | 493 |
sort(test); |
494 |
compare(test, golden, a, n, g); |
|
495 |
} |
|
496 |
newLine = true; |
|
497 |
} |
|
4177
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
498 |
} |
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
499 |
} |
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
500 |
} |
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
501 |
} |
4233 | 502 |
if (newLine) { |
503 |
out.println(); |
|
504 |
} |
|
505 |
} |
|
506 |
||
8193
626b859aabb2
7018258: Dual-pivot updates in 7013585 can fail with ArrayIndexOutOfBoundsException
alanb
parents:
8188
diff
changeset
|
507 |
private static void testAndCheckDouble(int length, MyRandom random) { |
5995
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
508 |
ourDescription = "Check double sorting"; |
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
509 |
double[] golden = new double[length]; |
4233 | 510 |
final int MAX = 10; |
511 |
boolean newLine = false; |
|
512 |
||
513 |
for (int a = 0; a <= MAX; a++) { |
|
514 |
for (int g = 0; g <= MAX; g++) { |
|
515 |
for (int z = 0; z <= MAX; z++) { |
|
516 |
for (int n = 0; n <= MAX; n++) { |
|
517 |
for (int p = 0; p <= MAX; p++) { |
|
5995
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
518 |
if (a + g + z + n + p > length) { |
4233 | 519 |
continue; |
520 |
} |
|
5995
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
521 |
if (a + g + z + n + p < length) { |
4233 | 522 |
continue; |
523 |
} |
|
524 |
for (DoubleBuilder builder : DoubleBuilder.values()) { |
|
8193
626b859aabb2
7018258: Dual-pivot updates in 7013585 can fail with ArrayIndexOutOfBoundsException
alanb
parents:
8188
diff
changeset
|
525 |
out.println("Test 'double': random = " + random.getSeed() + |
5995
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
526 |
", length = " + length + ", a = " + a + ", g = " + |
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
527 |
g + ", z = " + z + ", n = " + n + ", p = " + p); |
8193
626b859aabb2
7018258: Dual-pivot updates in 7013585 can fail with ArrayIndexOutOfBoundsException
alanb
parents:
8188
diff
changeset
|
528 |
builder.build(golden, a, g, z, n, p, random); |
4233 | 529 |
double[] test = golden.clone(); |
8193
626b859aabb2
7018258: Dual-pivot updates in 7013585 can fail with ArrayIndexOutOfBoundsException
alanb
parents:
8188
diff
changeset
|
530 |
scramble(test, random); |
4233 | 531 |
sort(test); |
532 |
compare(test, golden, a, n, g); |
|
533 |
} |
|
534 |
newLine = true; |
|
535 |
} |
|
536 |
} |
|
537 |
} |
|
538 |
} |
|
539 |
} |
|
540 |
if (newLine) { |
|
541 |
out.println(); |
|
542 |
} |
|
4177
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
543 |
} |
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
544 |
|
4233 | 545 |
private static void prepareSubArray(int[] a, int fromIndex, int toIndex, int m) { |
546 |
for (int i = 0; i < fromIndex; i++) { |
|
8188
b90884cf34f5
7013585: Dual-pivot quicksort improvements for highly structured (nearly sorted) and data with small periods
alanb
parents:
6896
diff
changeset
|
547 |
a[i] = 0xDEDA; |
4233 | 548 |
} |
8188
b90884cf34f5
7013585: Dual-pivot quicksort improvements for highly structured (nearly sorted) and data with small periods
alanb
parents:
6896
diff
changeset
|
549 |
int middle = (fromIndex + toIndex) >>> 1; |
b90884cf34f5
7013585: Dual-pivot quicksort improvements for highly structured (nearly sorted) and data with small periods
alanb
parents:
6896
diff
changeset
|
550 |
int k = 0; |
b90884cf34f5
7013585: Dual-pivot quicksort improvements for highly structured (nearly sorted) and data with small periods
alanb
parents:
6896
diff
changeset
|
551 |
|
b90884cf34f5
7013585: Dual-pivot quicksort improvements for highly structured (nearly sorted) and data with small periods
alanb
parents:
6896
diff
changeset
|
552 |
for (int i = fromIndex; i < middle; i++) { |
b90884cf34f5
7013585: Dual-pivot quicksort improvements for highly structured (nearly sorted) and data with small periods
alanb
parents:
6896
diff
changeset
|
553 |
a[i] = k++; |
b90884cf34f5
7013585: Dual-pivot quicksort improvements for highly structured (nearly sorted) and data with small periods
alanb
parents:
6896
diff
changeset
|
554 |
} |
b90884cf34f5
7013585: Dual-pivot quicksort improvements for highly structured (nearly sorted) and data with small periods
alanb
parents:
6896
diff
changeset
|
555 |
for (int i = middle; i < toIndex; i++) { |
b90884cf34f5
7013585: Dual-pivot quicksort improvements for highly structured (nearly sorted) and data with small periods
alanb
parents:
6896
diff
changeset
|
556 |
a[i] = k--; |
4233 | 557 |
} |
558 |
for (int i = toIndex; i < a.length; i++) { |
|
8188
b90884cf34f5
7013585: Dual-pivot quicksort improvements for highly structured (nearly sorted) and data with small periods
alanb
parents:
6896
diff
changeset
|
559 |
a[i] = 0xBABA; |
4233 | 560 |
} |
561 |
} |
|
562 |
||
8193
626b859aabb2
7018258: Dual-pivot updates in 7013585 can fail with ArrayIndexOutOfBoundsException
alanb
parents:
8188
diff
changeset
|
563 |
private static void scramble(int[] a, Random random) { |
5995
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
564 |
for (int i = 0; i < a.length * 7; i++) { |
8193
626b859aabb2
7018258: Dual-pivot updates in 7013585 can fail with ArrayIndexOutOfBoundsException
alanb
parents:
8188
diff
changeset
|
565 |
swap(a, random.nextInt(a.length), random.nextInt(a.length)); |
4233 | 566 |
} |
567 |
} |
|
568 |
||
8193
626b859aabb2
7018258: Dual-pivot updates in 7013585 can fail with ArrayIndexOutOfBoundsException
alanb
parents:
8188
diff
changeset
|
569 |
private static void scramble(float[] a, Random random) { |
5995
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
570 |
for (int i = 0; i < a.length * 7; i++) { |
8193
626b859aabb2
7018258: Dual-pivot updates in 7013585 can fail with ArrayIndexOutOfBoundsException
alanb
parents:
8188
diff
changeset
|
571 |
swap(a, random.nextInt(a.length), random.nextInt(a.length)); |
4233 | 572 |
} |
573 |
} |
|
574 |
||
8193
626b859aabb2
7018258: Dual-pivot updates in 7013585 can fail with ArrayIndexOutOfBoundsException
alanb
parents:
8188
diff
changeset
|
575 |
private static void scramble(double[] a, Random random) { |
5995
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
576 |
for (int i = 0; i < a.length * 7; i++) { |
8193
626b859aabb2
7018258: Dual-pivot updates in 7013585 can fail with ArrayIndexOutOfBoundsException
alanb
parents:
8188
diff
changeset
|
577 |
swap(a, random.nextInt(a.length), random.nextInt(a.length)); |
4233 | 578 |
} |
579 |
} |
|
580 |
||
581 |
private static void swap(int[] a, int i, int j) { |
|
582 |
int t = a[i]; |
|
583 |
a[i] = a[j]; |
|
584 |
a[j] = t; |
|
585 |
} |
|
586 |
||
587 |
private static void swap(float[] a, int i, int j) { |
|
588 |
float t = a[i]; |
|
589 |
a[i] = a[j]; |
|
590 |
a[j] = t; |
|
591 |
} |
|
592 |
||
593 |
private static void swap(double[] a, int i, int j) { |
|
594 |
double t = a[i]; |
|
595 |
a[i] = a[j]; |
|
596 |
a[j] = t; |
|
597 |
} |
|
598 |
||
599 |
private static enum TypeConverter { |
|
4177
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
600 |
INT { |
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
601 |
Object convert(int[] a) { |
4233 | 602 |
return a.clone(); |
4177
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
603 |
} |
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
604 |
}, |
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
605 |
LONG { |
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
606 |
Object convert(int[] a) { |
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
607 |
long[] b = new long[a.length]; |
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
608 |
|
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
609 |
for (int i = 0; i < a.length; i++) { |
4233 | 610 |
b[i] = (long) a[i]; |
4177
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
611 |
} |
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
612 |
return b; |
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
613 |
} |
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
614 |
}, |
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
615 |
BYTE { |
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
616 |
Object convert(int[] a) { |
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
617 |
byte[] b = new byte[a.length]; |
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
618 |
|
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
619 |
for (int i = 0; i < a.length; i++) { |
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
620 |
b[i] = (byte) a[i]; |
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
621 |
} |
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
622 |
return b; |
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
623 |
} |
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
624 |
}, |
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
625 |
SHORT { |
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
626 |
Object convert(int[] a) { |
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
627 |
short[] b = new short[a.length]; |
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
628 |
|
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
629 |
for (int i = 0; i < a.length; i++) { |
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
630 |
b[i] = (short) a[i]; |
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
631 |
} |
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
632 |
return b; |
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
633 |
} |
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
634 |
}, |
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
635 |
CHAR { |
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
636 |
Object convert(int[] a) { |
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
637 |
char[] b = new char[a.length]; |
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
638 |
|
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
639 |
for (int i = 0; i < a.length; i++) { |
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
640 |
b[i] = (char) a[i]; |
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
641 |
} |
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
642 |
return b; |
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
643 |
} |
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
644 |
}, |
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
645 |
FLOAT { |
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
646 |
Object convert(int[] a) { |
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
647 |
float[] b = new float[a.length]; |
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
648 |
|
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
649 |
for (int i = 0; i < a.length; i++) { |
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
650 |
b[i] = (float) a[i]; |
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
651 |
} |
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
652 |
return b; |
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
653 |
} |
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
654 |
}, |
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
655 |
DOUBLE { |
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
656 |
Object convert(int[] a) { |
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
657 |
double[] b = new double[a.length]; |
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
658 |
|
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
659 |
for (int i = 0; i < a.length; i++) { |
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
660 |
b[i] = (double) a[i]; |
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
661 |
} |
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
662 |
return b; |
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
663 |
} |
5995
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
664 |
}, |
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
665 |
INTEGER { |
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
666 |
Object convert(int[] a) { |
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
667 |
Integer[] b = new Integer[a.length]; |
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
668 |
|
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
669 |
for (int i = 0; i < a.length; i++) { |
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
670 |
b[i] = new Integer(a[i]); |
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
671 |
} |
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
672 |
return b; |
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
673 |
} |
4177
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
674 |
}; |
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
675 |
|
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
676 |
abstract Object convert(int[] a); |
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
677 |
|
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
678 |
@Override public String toString() { |
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
679 |
String name = name(); |
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
680 |
|
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
681 |
for (int i = name.length(); i < 9; i++) { |
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
682 |
name += " "; |
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
683 |
} |
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
684 |
return name; |
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
685 |
} |
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
686 |
} |
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
687 |
|
4233 | 688 |
private static enum FloatBuilder { |
689 |
SIMPLE { |
|
8193
626b859aabb2
7018258: Dual-pivot updates in 7013585 can fail with ArrayIndexOutOfBoundsException
alanb
parents:
8188
diff
changeset
|
690 |
void build(float[] x, int a, int g, int z, int n, int p, Random random) { |
4233 | 691 |
int fromIndex = 0; |
8193
626b859aabb2
7018258: Dual-pivot updates in 7013585 can fail with ArrayIndexOutOfBoundsException
alanb
parents:
8188
diff
changeset
|
692 |
float negativeValue = -random.nextFloat(); |
626b859aabb2
7018258: Dual-pivot updates in 7013585 can fail with ArrayIndexOutOfBoundsException
alanb
parents:
8188
diff
changeset
|
693 |
float positiveValue = random.nextFloat(); |
4233 | 694 |
|
695 |
writeValue(x, negativeValue, fromIndex, n); |
|
696 |
fromIndex += n; |
|
697 |
||
698 |
writeValue(x, -0.0f, fromIndex, g); |
|
699 |
fromIndex += g; |
|
700 |
||
701 |
writeValue(x, 0.0f, fromIndex, z); |
|
702 |
fromIndex += z; |
|
703 |
||
704 |
writeValue(x, positiveValue, fromIndex, p); |
|
705 |
fromIndex += p; |
|
706 |
||
707 |
writeValue(x, Float.NaN, fromIndex, a); |
|
708 |
} |
|
709 |
}; |
|
710 |
||
8193
626b859aabb2
7018258: Dual-pivot updates in 7013585 can fail with ArrayIndexOutOfBoundsException
alanb
parents:
8188
diff
changeset
|
711 |
abstract void build(float[] x, int a, int g, int z, int n, int p, Random random); |
4233 | 712 |
} |
713 |
||
714 |
private static enum DoubleBuilder { |
|
715 |
SIMPLE { |
|
8193
626b859aabb2
7018258: Dual-pivot updates in 7013585 can fail with ArrayIndexOutOfBoundsException
alanb
parents:
8188
diff
changeset
|
716 |
void build(double[] x, int a, int g, int z, int n, int p, Random random) { |
4233 | 717 |
int fromIndex = 0; |
8193
626b859aabb2
7018258: Dual-pivot updates in 7013585 can fail with ArrayIndexOutOfBoundsException
alanb
parents:
8188
diff
changeset
|
718 |
double negativeValue = -random.nextFloat(); |
626b859aabb2
7018258: Dual-pivot updates in 7013585 can fail with ArrayIndexOutOfBoundsException
alanb
parents:
8188
diff
changeset
|
719 |
double positiveValue = random.nextFloat(); |
4233 | 720 |
|
721 |
writeValue(x, negativeValue, fromIndex, n); |
|
722 |
fromIndex += n; |
|
723 |
||
724 |
writeValue(x, -0.0d, fromIndex, g); |
|
725 |
fromIndex += g; |
|
726 |
||
727 |
writeValue(x, 0.0d, fromIndex, z); |
|
728 |
fromIndex += z; |
|
729 |
||
730 |
writeValue(x, positiveValue, fromIndex, p); |
|
731 |
fromIndex += p; |
|
732 |
||
733 |
writeValue(x, Double.NaN, fromIndex, a); |
|
734 |
} |
|
735 |
}; |
|
736 |
||
8193
626b859aabb2
7018258: Dual-pivot updates in 7013585 can fail with ArrayIndexOutOfBoundsException
alanb
parents:
8188
diff
changeset
|
737 |
abstract void build(double[] x, int a, int g, int z, int n, int p, Random random); |
4233 | 738 |
} |
739 |
||
740 |
private static void writeValue(float[] a, float value, int fromIndex, int count) { |
|
741 |
for (int i = fromIndex; i < fromIndex + count; i++) { |
|
742 |
a[i] = value; |
|
743 |
} |
|
744 |
} |
|
745 |
||
746 |
private static void compare(float[] a, float[] b, int numNaN, int numNeg, int numNegZero) { |
|
747 |
for (int i = a.length - numNaN; i < a.length; i++) { |
|
748 |
if (a[i] == a[i]) { |
|
749 |
failed("On position " + i + " must be NaN instead of " + a[i]); |
|
750 |
} |
|
751 |
} |
|
752 |
final int NEGATIVE_ZERO = Float.floatToIntBits(-0.0f); |
|
753 |
||
754 |
for (int i = numNeg; i < numNeg + numNegZero; i++) { |
|
755 |
if (NEGATIVE_ZERO != Float.floatToIntBits(a[i])) { |
|
6896
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
756 |
failed("On position " + i + " must be -0.0 instead of " + a[i]); |
4233 | 757 |
} |
758 |
} |
|
759 |
for (int i = 0; i < a.length - numNaN; i++) { |
|
760 |
if (a[i] != b[i]) { |
|
6896
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
761 |
failedCompare(i, "" + a[i], "" + b[i]); |
4233 | 762 |
} |
763 |
} |
|
764 |
} |
|
765 |
||
766 |
private static void writeValue(double[] a, double value, int fromIndex, int count) { |
|
767 |
for (int i = fromIndex; i < fromIndex + count; i++) { |
|
768 |
a[i] = value; |
|
769 |
} |
|
770 |
} |
|
771 |
||
772 |
private static void compare(double[] a, double[] b, int numNaN, int numNeg, int numNegZero) { |
|
773 |
for (int i = a.length - numNaN; i < a.length; i++) { |
|
774 |
if (a[i] == a[i]) { |
|
775 |
failed("On position " + i + " must be NaN instead of " + a[i]); |
|
776 |
} |
|
777 |
} |
|
778 |
final long NEGATIVE_ZERO = Double.doubleToLongBits(-0.0d); |
|
779 |
||
780 |
for (int i = numNeg; i < numNeg + numNegZero; i++) { |
|
781 |
if (NEGATIVE_ZERO != Double.doubleToLongBits(a[i])) { |
|
6896
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
782 |
failed("On position " + i + " must be -0.0 instead of " + a[i]); |
4233 | 783 |
} |
784 |
} |
|
785 |
for (int i = 0; i < a.length - numNaN; i++) { |
|
786 |
if (a[i] != b[i]) { |
|
6896
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
787 |
failedCompare(i, "" + a[i], "" + b[i]); |
4233 | 788 |
} |
789 |
} |
|
790 |
} |
|
791 |
||
792 |
private static enum SortedBuilder { |
|
793 |
REPEATED { |
|
794 |
void build(int[] a, int m) { |
|
795 |
int period = a.length / m; |
|
796 |
int i = 0; |
|
797 |
int k = 0; |
|
798 |
||
799 |
while (true) { |
|
800 |
for (int t = 1; t <= period; t++) { |
|
801 |
if (i >= a.length) { |
|
802 |
return; |
|
803 |
} |
|
804 |
a[i++] = k; |
|
805 |
} |
|
806 |
if (i >= a.length) { |
|
807 |
return; |
|
808 |
} |
|
809 |
k++; |
|
810 |
} |
|
811 |
} |
|
812 |
}, |
|
813 |
ORGAN_PIPES { |
|
814 |
void build(int[] a, int m) { |
|
815 |
int i = 0; |
|
816 |
int k = m; |
|
817 |
||
818 |
while (true) { |
|
819 |
for (int t = 1; t <= m; t++) { |
|
820 |
if (i >= a.length) { |
|
821 |
return; |
|
822 |
} |
|
823 |
a[i++] = k; |
|
824 |
} |
|
825 |
} |
|
826 |
} |
|
827 |
}; |
|
828 |
||
829 |
abstract void build(int[] a, int m); |
|
830 |
||
831 |
@Override public String toString() { |
|
832 |
String name = name(); |
|
833 |
||
834 |
for (int i = name.length(); i < 12; i++) { |
|
835 |
name += " "; |
|
836 |
} |
|
837 |
return name; |
|
838 |
} |
|
839 |
} |
|
840 |
||
8193
626b859aabb2
7018258: Dual-pivot updates in 7013585 can fail with ArrayIndexOutOfBoundsException
alanb
parents:
8188
diff
changeset
|
841 |
private static enum MergeBuilder { |
626b859aabb2
7018258: Dual-pivot updates in 7013585 can fail with ArrayIndexOutOfBoundsException
alanb
parents:
8188
diff
changeset
|
842 |
ASCENDING { |
626b859aabb2
7018258: Dual-pivot updates in 7013585 can fail with ArrayIndexOutOfBoundsException
alanb
parents:
8188
diff
changeset
|
843 |
void build(int[] a, int m) { |
626b859aabb2
7018258: Dual-pivot updates in 7013585 can fail with ArrayIndexOutOfBoundsException
alanb
parents:
8188
diff
changeset
|
844 |
int period = a.length / m; |
626b859aabb2
7018258: Dual-pivot updates in 7013585 can fail with ArrayIndexOutOfBoundsException
alanb
parents:
8188
diff
changeset
|
845 |
int v = 1, i = 0; |
626b859aabb2
7018258: Dual-pivot updates in 7013585 can fail with ArrayIndexOutOfBoundsException
alanb
parents:
8188
diff
changeset
|
846 |
|
626b859aabb2
7018258: Dual-pivot updates in 7013585 can fail with ArrayIndexOutOfBoundsException
alanb
parents:
8188
diff
changeset
|
847 |
for (int k = 0; k < m; k++) { |
626b859aabb2
7018258: Dual-pivot updates in 7013585 can fail with ArrayIndexOutOfBoundsException
alanb
parents:
8188
diff
changeset
|
848 |
v = 1; |
626b859aabb2
7018258: Dual-pivot updates in 7013585 can fail with ArrayIndexOutOfBoundsException
alanb
parents:
8188
diff
changeset
|
849 |
for (int p = 0; p < period; p++) { |
626b859aabb2
7018258: Dual-pivot updates in 7013585 can fail with ArrayIndexOutOfBoundsException
alanb
parents:
8188
diff
changeset
|
850 |
a[i++] = v++; |
626b859aabb2
7018258: Dual-pivot updates in 7013585 can fail with ArrayIndexOutOfBoundsException
alanb
parents:
8188
diff
changeset
|
851 |
} |
626b859aabb2
7018258: Dual-pivot updates in 7013585 can fail with ArrayIndexOutOfBoundsException
alanb
parents:
8188
diff
changeset
|
852 |
} |
626b859aabb2
7018258: Dual-pivot updates in 7013585 can fail with ArrayIndexOutOfBoundsException
alanb
parents:
8188
diff
changeset
|
853 |
for (int j = i; j < a.length - 1; j++) { |
626b859aabb2
7018258: Dual-pivot updates in 7013585 can fail with ArrayIndexOutOfBoundsException
alanb
parents:
8188
diff
changeset
|
854 |
a[j] = v++; |
626b859aabb2
7018258: Dual-pivot updates in 7013585 can fail with ArrayIndexOutOfBoundsException
alanb
parents:
8188
diff
changeset
|
855 |
} |
626b859aabb2
7018258: Dual-pivot updates in 7013585 can fail with ArrayIndexOutOfBoundsException
alanb
parents:
8188
diff
changeset
|
856 |
a[a.length - 1] = 0; |
626b859aabb2
7018258: Dual-pivot updates in 7013585 can fail with ArrayIndexOutOfBoundsException
alanb
parents:
8188
diff
changeset
|
857 |
} |
626b859aabb2
7018258: Dual-pivot updates in 7013585 can fail with ArrayIndexOutOfBoundsException
alanb
parents:
8188
diff
changeset
|
858 |
}, |
626b859aabb2
7018258: Dual-pivot updates in 7013585 can fail with ArrayIndexOutOfBoundsException
alanb
parents:
8188
diff
changeset
|
859 |
DESCENDING { |
626b859aabb2
7018258: Dual-pivot updates in 7013585 can fail with ArrayIndexOutOfBoundsException
alanb
parents:
8188
diff
changeset
|
860 |
void build(int[] a, int m) { |
626b859aabb2
7018258: Dual-pivot updates in 7013585 can fail with ArrayIndexOutOfBoundsException
alanb
parents:
8188
diff
changeset
|
861 |
int period = a.length / m; |
626b859aabb2
7018258: Dual-pivot updates in 7013585 can fail with ArrayIndexOutOfBoundsException
alanb
parents:
8188
diff
changeset
|
862 |
int v = -1, i = 0; |
626b859aabb2
7018258: Dual-pivot updates in 7013585 can fail with ArrayIndexOutOfBoundsException
alanb
parents:
8188
diff
changeset
|
863 |
|
626b859aabb2
7018258: Dual-pivot updates in 7013585 can fail with ArrayIndexOutOfBoundsException
alanb
parents:
8188
diff
changeset
|
864 |
for (int k = 0; k < m; k++) { |
626b859aabb2
7018258: Dual-pivot updates in 7013585 can fail with ArrayIndexOutOfBoundsException
alanb
parents:
8188
diff
changeset
|
865 |
v = -1; |
626b859aabb2
7018258: Dual-pivot updates in 7013585 can fail with ArrayIndexOutOfBoundsException
alanb
parents:
8188
diff
changeset
|
866 |
for (int p = 0; p < period; p++) { |
626b859aabb2
7018258: Dual-pivot updates in 7013585 can fail with ArrayIndexOutOfBoundsException
alanb
parents:
8188
diff
changeset
|
867 |
a[i++] = v--; |
626b859aabb2
7018258: Dual-pivot updates in 7013585 can fail with ArrayIndexOutOfBoundsException
alanb
parents:
8188
diff
changeset
|
868 |
} |
626b859aabb2
7018258: Dual-pivot updates in 7013585 can fail with ArrayIndexOutOfBoundsException
alanb
parents:
8188
diff
changeset
|
869 |
} |
626b859aabb2
7018258: Dual-pivot updates in 7013585 can fail with ArrayIndexOutOfBoundsException
alanb
parents:
8188
diff
changeset
|
870 |
for (int j = i; j < a.length - 1; j++) { |
626b859aabb2
7018258: Dual-pivot updates in 7013585 can fail with ArrayIndexOutOfBoundsException
alanb
parents:
8188
diff
changeset
|
871 |
a[j] = v--; |
626b859aabb2
7018258: Dual-pivot updates in 7013585 can fail with ArrayIndexOutOfBoundsException
alanb
parents:
8188
diff
changeset
|
872 |
} |
626b859aabb2
7018258: Dual-pivot updates in 7013585 can fail with ArrayIndexOutOfBoundsException
alanb
parents:
8188
diff
changeset
|
873 |
a[a.length - 1] = 0; |
626b859aabb2
7018258: Dual-pivot updates in 7013585 can fail with ArrayIndexOutOfBoundsException
alanb
parents:
8188
diff
changeset
|
874 |
} |
626b859aabb2
7018258: Dual-pivot updates in 7013585 can fail with ArrayIndexOutOfBoundsException
alanb
parents:
8188
diff
changeset
|
875 |
}; |
626b859aabb2
7018258: Dual-pivot updates in 7013585 can fail with ArrayIndexOutOfBoundsException
alanb
parents:
8188
diff
changeset
|
876 |
|
626b859aabb2
7018258: Dual-pivot updates in 7013585 can fail with ArrayIndexOutOfBoundsException
alanb
parents:
8188
diff
changeset
|
877 |
abstract void build(int[] a, int m); |
626b859aabb2
7018258: Dual-pivot updates in 7013585 can fail with ArrayIndexOutOfBoundsException
alanb
parents:
8188
diff
changeset
|
878 |
|
626b859aabb2
7018258: Dual-pivot updates in 7013585 can fail with ArrayIndexOutOfBoundsException
alanb
parents:
8188
diff
changeset
|
879 |
@Override public String toString() { |
626b859aabb2
7018258: Dual-pivot updates in 7013585 can fail with ArrayIndexOutOfBoundsException
alanb
parents:
8188
diff
changeset
|
880 |
String name = name(); |
626b859aabb2
7018258: Dual-pivot updates in 7013585 can fail with ArrayIndexOutOfBoundsException
alanb
parents:
8188
diff
changeset
|
881 |
|
626b859aabb2
7018258: Dual-pivot updates in 7013585 can fail with ArrayIndexOutOfBoundsException
alanb
parents:
8188
diff
changeset
|
882 |
for (int i = name.length(); i < 12; i++) { |
626b859aabb2
7018258: Dual-pivot updates in 7013585 can fail with ArrayIndexOutOfBoundsException
alanb
parents:
8188
diff
changeset
|
883 |
name += " "; |
626b859aabb2
7018258: Dual-pivot updates in 7013585 can fail with ArrayIndexOutOfBoundsException
alanb
parents:
8188
diff
changeset
|
884 |
} |
626b859aabb2
7018258: Dual-pivot updates in 7013585 can fail with ArrayIndexOutOfBoundsException
alanb
parents:
8188
diff
changeset
|
885 |
return name; |
626b859aabb2
7018258: Dual-pivot updates in 7013585 can fail with ArrayIndexOutOfBoundsException
alanb
parents:
8188
diff
changeset
|
886 |
} |
626b859aabb2
7018258: Dual-pivot updates in 7013585 can fail with ArrayIndexOutOfBoundsException
alanb
parents:
8188
diff
changeset
|
887 |
} |
626b859aabb2
7018258: Dual-pivot updates in 7013585 can fail with ArrayIndexOutOfBoundsException
alanb
parents:
8188
diff
changeset
|
888 |
|
4233 | 889 |
private static enum UnsortedBuilder { |
4177
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
890 |
RANDOM { |
8193
626b859aabb2
7018258: Dual-pivot updates in 7013585 can fail with ArrayIndexOutOfBoundsException
alanb
parents:
8188
diff
changeset
|
891 |
void build(int[] a, int m, Random random) { |
4177
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
892 |
for (int i = 0; i < a.length; i++) { |
8193
626b859aabb2
7018258: Dual-pivot updates in 7013585 can fail with ArrayIndexOutOfBoundsException
alanb
parents:
8188
diff
changeset
|
893 |
a[i] = random.nextInt(); |
4177
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
894 |
} |
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
895 |
} |
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
896 |
}, |
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
897 |
ASCENDING { |
8193
626b859aabb2
7018258: Dual-pivot updates in 7013585 can fail with ArrayIndexOutOfBoundsException
alanb
parents:
8188
diff
changeset
|
898 |
void build(int[] a, int m, Random random) { |
4177
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
899 |
for (int i = 0; i < a.length; i++) { |
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
900 |
a[i] = m + i; |
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
901 |
} |
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
902 |
} |
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
903 |
}, |
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
904 |
DESCENDING { |
8193
626b859aabb2
7018258: Dual-pivot updates in 7013585 can fail with ArrayIndexOutOfBoundsException
alanb
parents:
8188
diff
changeset
|
905 |
void build(int[] a, int m, Random random) { |
4177
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
906 |
for (int i = 0; i < a.length; i++) { |
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
907 |
a[i] = a.length - m - i; |
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
908 |
} |
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
909 |
} |
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
910 |
}, |
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
911 |
ALL_EQUAL { |
8193
626b859aabb2
7018258: Dual-pivot updates in 7013585 can fail with ArrayIndexOutOfBoundsException
alanb
parents:
8188
diff
changeset
|
912 |
void build(int[] a, int m, Random random) { |
4177
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
913 |
for (int i = 0; i < a.length; i++) { |
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
914 |
a[i] = m; |
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
915 |
} |
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
916 |
} |
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
917 |
}, |
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
918 |
SAW { |
8193
626b859aabb2
7018258: Dual-pivot updates in 7013585 can fail with ArrayIndexOutOfBoundsException
alanb
parents:
8188
diff
changeset
|
919 |
void build(int[] a, int m, Random random) { |
4177
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
920 |
int incCount = 1; |
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
921 |
int decCount = a.length; |
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
922 |
int i = 0; |
6896
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
923 |
int period = m--; |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
924 |
|
4177
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
925 |
while (true) { |
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
926 |
for (int k = 1; k <= period; k++) { |
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
927 |
if (i >= a.length) { |
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
928 |
return; |
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
929 |
} |
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
930 |
a[i++] = incCount++; |
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
931 |
} |
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
932 |
period += m; |
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
933 |
|
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
934 |
for (int k = 1; k <= period; k++) { |
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
935 |
if (i >= a.length) { |
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
936 |
return; |
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
937 |
} |
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
938 |
a[i++] = decCount--; |
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
939 |
} |
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
940 |
period += m; |
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
941 |
} |
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
942 |
} |
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
943 |
}, |
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
944 |
REPEATED { |
8193
626b859aabb2
7018258: Dual-pivot updates in 7013585 can fail with ArrayIndexOutOfBoundsException
alanb
parents:
8188
diff
changeset
|
945 |
void build(int[] a, int m, Random random) { |
4177
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
946 |
for (int i = 0; i < a.length; i++) { |
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
947 |
a[i] = i % m; |
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
948 |
} |
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
949 |
} |
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
950 |
}, |
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
951 |
DUPLICATED { |
8193
626b859aabb2
7018258: Dual-pivot updates in 7013585 can fail with ArrayIndexOutOfBoundsException
alanb
parents:
8188
diff
changeset
|
952 |
void build(int[] a, int m, Random random) { |
4177
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
953 |
for (int i = 0; i < a.length; i++) { |
8193
626b859aabb2
7018258: Dual-pivot updates in 7013585 can fail with ArrayIndexOutOfBoundsException
alanb
parents:
8188
diff
changeset
|
954 |
a[i] = random.nextInt(m); |
4177
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
955 |
} |
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
956 |
} |
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
957 |
}, |
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
958 |
ORGAN_PIPES { |
8193
626b859aabb2
7018258: Dual-pivot updates in 7013585 can fail with ArrayIndexOutOfBoundsException
alanb
parents:
8188
diff
changeset
|
959 |
void build(int[] a, int m, Random random) { |
4177
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
960 |
int middle = a.length / (m + 1); |
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
961 |
|
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
962 |
for (int i = 0; i < middle; i++) { |
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
963 |
a[i] = i; |
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
964 |
} |
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
965 |
for (int i = middle; i < a.length; i++) { |
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
966 |
a[i] = a.length - i - 1; |
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
967 |
} |
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
968 |
} |
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
969 |
}, |
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
970 |
STAGGER { |
8193
626b859aabb2
7018258: Dual-pivot updates in 7013585 can fail with ArrayIndexOutOfBoundsException
alanb
parents:
8188
diff
changeset
|
971 |
void build(int[] a, int m, Random random) { |
4177
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
972 |
for (int i = 0; i < a.length; i++) { |
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
973 |
a[i] = (i * m + i) % a.length; |
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
974 |
} |
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
975 |
} |
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
976 |
}, |
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
977 |
PLATEAU { |
8193
626b859aabb2
7018258: Dual-pivot updates in 7013585 can fail with ArrayIndexOutOfBoundsException
alanb
parents:
8188
diff
changeset
|
978 |
void build(int[] a, int m, Random random) { |
4177
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
979 |
for (int i = 0; i < a.length; i++) { |
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
980 |
a[i] = Math.min(i, m); |
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
981 |
} |
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
982 |
} |
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
983 |
}, |
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
984 |
SHUFFLE { |
8193
626b859aabb2
7018258: Dual-pivot updates in 7013585 can fail with ArrayIndexOutOfBoundsException
alanb
parents:
8188
diff
changeset
|
985 |
void build(int[] a, int m, Random random) { |
626b859aabb2
7018258: Dual-pivot updates in 7013585 can fail with ArrayIndexOutOfBoundsException
alanb
parents:
8188
diff
changeset
|
986 |
int x = 0, y = 0; |
4177
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
987 |
for (int i = 0; i < a.length; i++) { |
8193
626b859aabb2
7018258: Dual-pivot updates in 7013585 can fail with ArrayIndexOutOfBoundsException
alanb
parents:
8188
diff
changeset
|
988 |
a[i] = random.nextBoolean() ? (x += 2) : (y += 2); |
4177
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
989 |
} |
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
990 |
} |
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
991 |
}; |
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
992 |
|
8193
626b859aabb2
7018258: Dual-pivot updates in 7013585 can fail with ArrayIndexOutOfBoundsException
alanb
parents:
8188
diff
changeset
|
993 |
abstract void build(int[] a, int m, Random random); |
4177
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
994 |
|
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
995 |
@Override public String toString() { |
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
996 |
String name = name(); |
4233 | 997 |
|
4177
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
998 |
for (int i = name.length(); i < 12; i++) { |
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
999 |
name += " "; |
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
1000 |
} |
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
1001 |
return name; |
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
1002 |
} |
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
1003 |
} |
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
1004 |
|
6896
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1005 |
private static void checkWithCheckSum(Object test, Object golden) { |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1006 |
checkSorted(test); |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1007 |
checkCheckSum(test, golden); |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1008 |
} |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1009 |
|
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1010 |
private static void failed(String message) { |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1011 |
err.format("\n*** TEST FAILED - %s.\n\n%s.\n\n", ourDescription, message); |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1012 |
throw new RuntimeException("Test failed - see log file for details"); |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1013 |
} |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1014 |
|
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1015 |
private static void failedSort(int index, String value1, String value2) { |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1016 |
failed("Array is not sorted at " + index + "-th position: " + |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1017 |
value1 + " and " + value2); |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1018 |
} |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1019 |
|
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1020 |
private static void failedCompare(int index, String value1, String value2) { |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1021 |
failed("On position " + index + " must be " + value2 + " instead of " + value1); |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1022 |
} |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1023 |
|
4233 | 1024 |
private static void compare(Object test, Object golden) { |
1025 |
if (test instanceof int[]) { |
|
1026 |
compare((int[]) test, (int[]) golden); |
|
1027 |
} else if (test instanceof long[]) { |
|
1028 |
compare((long[]) test, (long[]) golden); |
|
1029 |
} else if (test instanceof short[]) { |
|
1030 |
compare((short[]) test, (short[]) golden); |
|
1031 |
} else if (test instanceof byte[]) { |
|
1032 |
compare((byte[]) test, (byte[]) golden); |
|
1033 |
} else if (test instanceof char[]) { |
|
1034 |
compare((char[]) test, (char[]) golden); |
|
1035 |
} else if (test instanceof float[]) { |
|
1036 |
compare((float[]) test, (float[]) golden); |
|
1037 |
} else if (test instanceof double[]) { |
|
1038 |
compare((double[]) test, (double[]) golden); |
|
5995
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
1039 |
} else if (test instanceof Integer[]) { |
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
1040 |
compare((Integer[]) test, (Integer[]) golden); |
4233 | 1041 |
} else { |
1042 |
failed("Unknow type of array: " + test + " of class " + |
|
1043 |
test.getClass().getName()); |
|
1044 |
} |
|
1045 |
} |
|
1046 |
||
6896
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1047 |
private static void compare(int[] a, int[] b) { |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1048 |
for (int i = 0; i < a.length; i++) { |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1049 |
if (a[i] != b[i]) { |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1050 |
failedCompare(i, "" + a[i], "" + b[i]); |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1051 |
} |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1052 |
} |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1053 |
} |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1054 |
|
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1055 |
private static void compare(long[] a, long[] b) { |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1056 |
for (int i = 0; i < a.length; i++) { |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1057 |
if (a[i] != b[i]) { |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1058 |
failedCompare(i, "" + a[i], "" + b[i]); |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1059 |
} |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1060 |
} |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1061 |
} |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1062 |
|
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1063 |
private static void compare(short[] a, short[] b) { |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1064 |
for (int i = 0; i < a.length; i++) { |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1065 |
if (a[i] != b[i]) { |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1066 |
failedCompare(i, "" + a[i], "" + b[i]); |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1067 |
} |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1068 |
} |
4177
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
1069 |
} |
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
1070 |
|
6896
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1071 |
private static void compare(byte[] a, byte[] b) { |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1072 |
for (int i = 0; i < a.length; i++) { |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1073 |
if (a[i] != b[i]) { |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1074 |
failedCompare(i, "" + a[i], "" + b[i]); |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1075 |
} |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1076 |
} |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1077 |
} |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1078 |
|
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1079 |
private static void compare(char[] a, char[] b) { |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1080 |
for (int i = 0; i < a.length; i++) { |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1081 |
if (a[i] != b[i]) { |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1082 |
failedCompare(i, "" + a[i], "" + b[i]); |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1083 |
} |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1084 |
} |
4177
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
1085 |
} |
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
1086 |
|
6896
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1087 |
private static void compare(float[] a, float[] b) { |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1088 |
for (int i = 0; i < a.length; i++) { |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1089 |
if (a[i] != b[i]) { |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1090 |
failedCompare(i, "" + a[i], "" + b[i]); |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1091 |
} |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1092 |
} |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1093 |
} |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1094 |
|
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1095 |
private static void compare(double[] a, double[] b) { |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1096 |
for (int i = 0; i < a.length; i++) { |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1097 |
if (a[i] != b[i]) { |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1098 |
failedCompare(i, "" + a[i], "" + b[i]); |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1099 |
} |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1100 |
} |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1101 |
} |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1102 |
|
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1103 |
private static void compare(Integer[] a, Integer[] b) { |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1104 |
for (int i = 0; i < a.length; i++) { |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1105 |
if (a[i].compareTo(b[i]) != 0) { |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1106 |
failedCompare(i, "" + a[i], "" + b[i]); |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1107 |
} |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1108 |
} |
4177
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
1109 |
} |
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
1110 |
|
4233 | 1111 |
private static void checkSorted(Object object) { |
4177
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
1112 |
if (object instanceof int[]) { |
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
1113 |
checkSorted((int[]) object); |
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
1114 |
} else if (object instanceof long[]) { |
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
1115 |
checkSorted((long[]) object); |
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
1116 |
} else if (object instanceof short[]) { |
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
1117 |
checkSorted((short[]) object); |
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
1118 |
} else if (object instanceof byte[]) { |
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
1119 |
checkSorted((byte[]) object); |
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
1120 |
} else if (object instanceof char[]) { |
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
1121 |
checkSorted((char[]) object); |
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
1122 |
} else if (object instanceof float[]) { |
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
1123 |
checkSorted((float[]) object); |
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
1124 |
} else if (object instanceof double[]) { |
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
1125 |
checkSorted((double[]) object); |
5995
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
1126 |
} else if (object instanceof Integer[]) { |
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
1127 |
checkSorted((Integer[]) object); |
4177
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
1128 |
} else { |
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
1129 |
failed("Unknow type of array: " + object + " of class " + |
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
1130 |
object.getClass().getName()); |
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
1131 |
} |
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
1132 |
} |
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
1133 |
|
4233 | 1134 |
private static void checkSorted(int[] a) { |
4177
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
1135 |
for (int i = 0; i < a.length - 1; i++) { |
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
1136 |
if (a[i] > a[i + 1]) { |
6896
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1137 |
failedSort(i, "" + a[i], "" + a[i + 1]); |
4177
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
1138 |
} |
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
1139 |
} |
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
1140 |
} |
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
1141 |
|
4233 | 1142 |
private static void checkSorted(long[] a) { |
4177
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
1143 |
for (int i = 0; i < a.length - 1; i++) { |
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
1144 |
if (a[i] > a[i + 1]) { |
6896
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1145 |
failedSort(i, "" + a[i], "" + a[i + 1]); |
4177
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
1146 |
} |
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
1147 |
} |
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
1148 |
} |
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
1149 |
|
4233 | 1150 |
private static void checkSorted(short[] a) { |
1151 |
for (int i = 0; i < a.length - 1; i++) { |
|
1152 |
if (a[i] > a[i + 1]) { |
|
6896
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1153 |
failedSort(i, "" + a[i], "" + a[i + 1]); |
4233 | 1154 |
} |
1155 |
} |
|
1156 |
} |
|
1157 |
||
1158 |
private static void checkSorted(byte[] a) { |
|
4177
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
1159 |
for (int i = 0; i < a.length - 1; i++) { |
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
1160 |
if (a[i] > a[i + 1]) { |
6896
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1161 |
failedSort(i, "" + a[i], "" + a[i + 1]); |
4177
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
1162 |
} |
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
1163 |
} |
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
1164 |
} |
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
1165 |
|
4233 | 1166 |
private static void checkSorted(char[] a) { |
1167 |
for (int i = 0; i < a.length - 1; i++) { |
|
1168 |
if (a[i] > a[i + 1]) { |
|
6896
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1169 |
failedSort(i, "" + a[i], "" + a[i + 1]); |
4233 | 1170 |
} |
1171 |
} |
|
1172 |
} |
|
1173 |
||
1174 |
private static void checkSorted(float[] a) { |
|
4177
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
1175 |
for (int i = 0; i < a.length - 1; i++) { |
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
1176 |
if (a[i] > a[i + 1]) { |
6896
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1177 |
failedSort(i, "" + a[i], "" + a[i + 1]); |
4177
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
1178 |
} |
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
1179 |
} |
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
1180 |
} |
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
1181 |
|
4233 | 1182 |
private static void checkSorted(double[] a) { |
1183 |
for (int i = 0; i < a.length - 1; i++) { |
|
1184 |
if (a[i] > a[i + 1]) { |
|
6896
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1185 |
failedSort(i, "" + a[i], "" + a[i + 1]); |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1186 |
} |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1187 |
} |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1188 |
} |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1189 |
|
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1190 |
private static void checkSorted(Integer[] a) { |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1191 |
for (int i = 0; i < a.length - 1; i++) { |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1192 |
if (a[i].intValue() > a[i + 1].intValue()) { |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1193 |
failedSort(i, "" + a[i], "" + a[i + 1]); |
4233 | 1194 |
} |
1195 |
} |
|
1196 |
} |
|
1197 |
||
1198 |
private static void checkCheckSum(Object test, Object golden) { |
|
6896
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1199 |
if (checkSumXor(test) != checkSumXor(golden)) { |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1200 |
failed("Original and sorted arrays are not identical [xor]"); |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1201 |
} |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1202 |
if (checkSumPlus(test) != checkSumPlus(golden)) { |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1203 |
failed("Original and sorted arrays are not identical [plus]"); |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1204 |
} |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1205 |
} |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1206 |
|
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1207 |
private static int checkSumXor(Object object) { |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1208 |
if (object instanceof int[]) { |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1209 |
return checkSumXor((int[]) object); |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1210 |
} else if (object instanceof long[]) { |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1211 |
return checkSumXor((long[]) object); |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1212 |
} else if (object instanceof short[]) { |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1213 |
return checkSumXor((short[]) object); |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1214 |
} else if (object instanceof byte[]) { |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1215 |
return checkSumXor((byte[]) object); |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1216 |
} else if (object instanceof char[]) { |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1217 |
return checkSumXor((char[]) object); |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1218 |
} else if (object instanceof float[]) { |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1219 |
return checkSumXor((float[]) object); |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1220 |
} else if (object instanceof double[]) { |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1221 |
return checkSumXor((double[]) object); |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1222 |
} else if (object instanceof Integer[]) { |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1223 |
return checkSumXor((Integer[]) object); |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1224 |
} else { |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1225 |
failed("Unknow type of array: " + object + " of class " + |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1226 |
object.getClass().getName()); |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1227 |
return -1; |
4177
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
1228 |
} |
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
1229 |
} |
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
1230 |
|
6896
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1231 |
private static int checkSumXor(Integer[] a) { |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1232 |
int checkSum = 0; |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1233 |
|
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1234 |
for (Integer e : a) { |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1235 |
checkSum ^= e.intValue(); |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1236 |
} |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1237 |
return checkSum; |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1238 |
} |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1239 |
|
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1240 |
private static int checkSumXor(int[] a) { |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1241 |
int checkSum = 0; |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1242 |
|
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1243 |
for (int e : a) { |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1244 |
checkSum ^= e; |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1245 |
} |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1246 |
return checkSum; |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1247 |
} |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1248 |
|
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1249 |
private static int checkSumXor(long[] a) { |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1250 |
long checkSum = 0; |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1251 |
|
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1252 |
for (long e : a) { |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1253 |
checkSum ^= e; |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1254 |
} |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1255 |
return (int) checkSum; |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1256 |
} |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1257 |
|
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1258 |
private static int checkSumXor(short[] a) { |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1259 |
short checkSum = 0; |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1260 |
|
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1261 |
for (short e : a) { |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1262 |
checkSum ^= e; |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1263 |
} |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1264 |
return (int) checkSum; |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1265 |
} |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1266 |
|
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1267 |
private static int checkSumXor(byte[] a) { |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1268 |
byte checkSum = 0; |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1269 |
|
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1270 |
for (byte e : a) { |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1271 |
checkSum ^= e; |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1272 |
} |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1273 |
return (int) checkSum; |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1274 |
} |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1275 |
|
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1276 |
private static int checkSumXor(char[] a) { |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1277 |
char checkSum = 0; |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1278 |
|
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1279 |
for (char e : a) { |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1280 |
checkSum ^= e; |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1281 |
} |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1282 |
return (int) checkSum; |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1283 |
} |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1284 |
|
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1285 |
private static int checkSumXor(float[] a) { |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1286 |
int checkSum = 0; |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1287 |
|
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1288 |
for (float e : a) { |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1289 |
checkSum ^= (int) e; |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1290 |
} |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1291 |
return checkSum; |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1292 |
} |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1293 |
|
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1294 |
private static int checkSumXor(double[] a) { |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1295 |
int checkSum = 0; |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1296 |
|
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1297 |
for (double e : a) { |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1298 |
checkSum ^= (int) e; |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1299 |
} |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1300 |
return checkSum; |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1301 |
} |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1302 |
|
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1303 |
private static int checkSumPlus(Object object) { |
4177
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
1304 |
if (object instanceof int[]) { |
6896
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1305 |
return checkSumPlus((int[]) object); |
4177
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
1306 |
} else if (object instanceof long[]) { |
6896
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1307 |
return checkSumPlus((long[]) object); |
4177
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
1308 |
} else if (object instanceof short[]) { |
6896
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1309 |
return checkSumPlus((short[]) object); |
4177
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
1310 |
} else if (object instanceof byte[]) { |
6896
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1311 |
return checkSumPlus((byte[]) object); |
4177
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
1312 |
} else if (object instanceof char[]) { |
6896
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1313 |
return checkSumPlus((char[]) object); |
4177
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
1314 |
} else if (object instanceof float[]) { |
6896
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1315 |
return checkSumPlus((float[]) object); |
4177
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
1316 |
} else if (object instanceof double[]) { |
6896
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1317 |
return checkSumPlus((double[]) object); |
5995
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
1318 |
} else if (object instanceof Integer[]) { |
6896
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1319 |
return checkSumPlus((Integer[]) object); |
4177
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
1320 |
} else { |
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
1321 |
failed("Unknow type of array: " + object + " of class " + |
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
1322 |
object.getClass().getName()); |
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
1323 |
return -1; |
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
1324 |
} |
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
1325 |
} |
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
1326 |
|
6896
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1327 |
private static int checkSumPlus(int[] a) { |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1328 |
int checkSum = 0; |
4177
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
1329 |
|
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
1330 |
for (int e : a) { |
6896
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1331 |
checkSum += e; |
4177
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
1332 |
} |
6896
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1333 |
return checkSum; |
4177
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
1334 |
} |
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
1335 |
|
6896
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1336 |
private static int checkSumPlus(long[] a) { |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1337 |
long checkSum = 0; |
4177
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
1338 |
|
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
1339 |
for (long e : a) { |
6896
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1340 |
checkSum += e; |
4177
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
1341 |
} |
6896
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1342 |
return (int) checkSum; |
4177
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
1343 |
} |
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
1344 |
|
6896
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1345 |
private static int checkSumPlus(short[] a) { |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1346 |
short checkSum = 0; |
4177
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
1347 |
|
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
1348 |
for (short e : a) { |
6896
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1349 |
checkSum += e; |
4177
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
1350 |
} |
6896
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1351 |
return (int) checkSum; |
4177
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
1352 |
} |
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
1353 |
|
6896
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1354 |
private static int checkSumPlus(byte[] a) { |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1355 |
byte checkSum = 0; |
4177
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
1356 |
|
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
1357 |
for (byte e : a) { |
6896
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1358 |
checkSum += e; |
4177
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
1359 |
} |
6896
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1360 |
return (int) checkSum; |
4177
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
1361 |
} |
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
1362 |
|
6896
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1363 |
private static int checkSumPlus(char[] a) { |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1364 |
char checkSum = 0; |
4177
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
1365 |
|
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
1366 |
for (char e : a) { |
6896
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1367 |
checkSum += e; |
4177
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
1368 |
} |
6896
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1369 |
return (int) checkSum; |
4177
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
1370 |
} |
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
1371 |
|
6896
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1372 |
private static int checkSumPlus(float[] a) { |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1373 |
int checkSum = 0; |
4177
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
1374 |
|
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
1375 |
for (float e : a) { |
6896
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1376 |
checkSum += (int) e; |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1377 |
} |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1378 |
return checkSum; |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1379 |
} |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1380 |
|
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1381 |
private static int checkSumPlus(double[] a) { |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1382 |
int checkSum = 0; |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1383 |
|
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1384 |
for (double e : a) { |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1385 |
checkSum += (int) e; |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1386 |
} |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1387 |
return checkSum; |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1388 |
} |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1389 |
|
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1390 |
private static int checkSumPlus(Integer[] a) { |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1391 |
int checkSum = 0; |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1392 |
|
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1393 |
for (Integer e : a) { |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1394 |
checkSum += e.intValue(); |
4177
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
1395 |
} |
6896
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1396 |
return checkSum; |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1397 |
} |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1398 |
|
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1399 |
private static void sortByInsertionSort(Object object) { |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1400 |
if (object instanceof int[]) { |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1401 |
sortByInsertionSort((int[]) object); |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1402 |
} else if (object instanceof long[]) { |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1403 |
sortByInsertionSort((long[]) object); |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1404 |
} else if (object instanceof short[]) { |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1405 |
sortByInsertionSort((short[]) object); |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1406 |
} else if (object instanceof byte[]) { |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1407 |
sortByInsertionSort((byte[]) object); |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1408 |
} else if (object instanceof char[]) { |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1409 |
sortByInsertionSort((char[]) object); |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1410 |
} else if (object instanceof float[]) { |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1411 |
sortByInsertionSort((float[]) object); |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1412 |
} else if (object instanceof double[]) { |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1413 |
sortByInsertionSort((double[]) object); |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1414 |
} else if (object instanceof Integer[]) { |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1415 |
sortByInsertionSort((Integer[]) object); |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1416 |
} else { |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1417 |
failed("Unknow type of array: " + object + " of class " + |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1418 |
object.getClass().getName()); |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1419 |
} |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1420 |
} |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1421 |
|
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1422 |
private static void sortByInsertionSort(int[] a) { |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1423 |
for (int j, i = 1; i < a.length; i++) { |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1424 |
int ai = a[i]; |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1425 |
for (j = i - 1; j >= 0 && ai < a[j]; j--) { |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1426 |
a[j + 1] = a[j]; |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1427 |
} |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1428 |
a[j + 1] = ai; |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1429 |
} |
4177
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
1430 |
} |
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
1431 |
|
6896
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1432 |
private static void sortByInsertionSort(long[] a) { |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1433 |
for (int j, i = 1; i < a.length; i++) { |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1434 |
long ai = a[i]; |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1435 |
for (j = i - 1; j >= 0 && ai < a[j]; j--) { |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1436 |
a[j + 1] = a[j]; |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1437 |
} |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1438 |
a[j + 1] = ai; |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1439 |
} |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1440 |
} |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1441 |
|
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1442 |
private static void sortByInsertionSort(short[] a) { |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1443 |
for (int j, i = 1; i < a.length; i++) { |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1444 |
short ai = a[i]; |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1445 |
for (j = i - 1; j >= 0 && ai < a[j]; j--) { |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1446 |
a[j + 1] = a[j]; |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1447 |
} |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1448 |
a[j + 1] = ai; |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1449 |
} |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1450 |
} |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1451 |
|
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1452 |
private static void sortByInsertionSort(byte[] a) { |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1453 |
for (int j, i = 1; i < a.length; i++) { |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1454 |
byte ai = a[i]; |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1455 |
for (j = i - 1; j >= 0 && ai < a[j]; j--) { |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1456 |
a[j + 1] = a[j]; |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1457 |
} |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1458 |
a[j + 1] = ai; |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1459 |
} |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1460 |
} |
4177
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
1461 |
|
6896
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1462 |
private static void sortByInsertionSort(char[] a) { |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1463 |
for (int j, i = 1; i < a.length; i++) { |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1464 |
char ai = a[i]; |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1465 |
for (j = i - 1; j >= 0 && ai < a[j]; j--) { |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1466 |
a[j + 1] = a[j]; |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1467 |
} |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1468 |
a[j + 1] = ai; |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1469 |
} |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1470 |
} |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1471 |
|
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1472 |
private static void sortByInsertionSort(float[] a) { |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1473 |
for (int j, i = 1; i < a.length; i++) { |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1474 |
float ai = a[i]; |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1475 |
for (j = i - 1; j >= 0 && ai < a[j]; j--) { |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1476 |
a[j + 1] = a[j]; |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1477 |
} |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1478 |
a[j + 1] = ai; |
4177
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
1479 |
} |
6896
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1480 |
} |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1481 |
|
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1482 |
private static void sortByInsertionSort(double[] a) { |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1483 |
for (int j, i = 1; i < a.length; i++) { |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1484 |
double ai = a[i]; |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1485 |
for (j = i - 1; j >= 0 && ai < a[j]; j--) { |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1486 |
a[j + 1] = a[j]; |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1487 |
} |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1488 |
a[j + 1] = ai; |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1489 |
} |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1490 |
} |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1491 |
|
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1492 |
private static void sortByInsertionSort(Integer[] a) { |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1493 |
for (int j, i = 1; i < a.length; i++) { |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1494 |
Integer ai = a[i]; |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1495 |
for (j = i - 1; j >= 0 && ai < a[j]; j--) { |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1496 |
a[j + 1] = a[j]; |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1497 |
} |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1498 |
a[j + 1] = ai; |
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1499 |
} |
4177
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
1500 |
} |
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
1501 |
|
4233 | 1502 |
private static void sort(Object object) { |
4177
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
1503 |
if (object instanceof int[]) { |
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
1504 |
Arrays.sort((int[]) object); |
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
1505 |
} else if (object instanceof long[]) { |
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
1506 |
Arrays.sort((long[]) object); |
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
1507 |
} else if (object instanceof short[]) { |
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
1508 |
Arrays.sort((short[]) object); |
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
1509 |
} else if (object instanceof byte[]) { |
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
1510 |
Arrays.sort((byte[]) object); |
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
1511 |
} else if (object instanceof char[]) { |
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
1512 |
Arrays.sort((char[]) object); |
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
1513 |
} else if (object instanceof float[]) { |
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
1514 |
Arrays.sort((float[]) object); |
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
1515 |
} else if (object instanceof double[]) { |
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
1516 |
Arrays.sort((double[]) object); |
5995
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
1517 |
} else if (object instanceof Integer[]) { |
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
1518 |
Arrays.sort((Integer[]) object); |
4177
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
1519 |
} else { |
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
1520 |
failed("Unknow type of array: " + object + " of class " + |
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
1521 |
object.getClass().getName()); |
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
1522 |
} |
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
1523 |
} |
4233 | 1524 |
|
1525 |
private static void sortSubArray(Object object, int fromIndex, int toIndex) { |
|
1526 |
if (object instanceof int[]) { |
|
1527 |
Arrays.sort((int[]) object, fromIndex, toIndex); |
|
1528 |
} else if (object instanceof long[]) { |
|
1529 |
Arrays.sort((long[]) object, fromIndex, toIndex); |
|
1530 |
} else if (object instanceof short[]) { |
|
1531 |
Arrays.sort((short[]) object, fromIndex, toIndex); |
|
1532 |
} else if (object instanceof byte[]) { |
|
1533 |
Arrays.sort((byte[]) object, fromIndex, toIndex); |
|
1534 |
} else if (object instanceof char[]) { |
|
1535 |
Arrays.sort((char[]) object, fromIndex, toIndex); |
|
1536 |
} else if (object instanceof float[]) { |
|
1537 |
Arrays.sort((float[]) object, fromIndex, toIndex); |
|
1538 |
} else if (object instanceof double[]) { |
|
1539 |
Arrays.sort((double[]) object, fromIndex, toIndex); |
|
5995
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
1540 |
} else if (object instanceof Integer[]) { |
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
1541 |
Arrays.sort((Integer[]) object, fromIndex, toIndex); |
4233 | 1542 |
} else { |
1543 |
failed("Unknow type of array: " + object + " of class " + |
|
1544 |
object.getClass().getName()); |
|
1545 |
} |
|
1546 |
} |
|
1547 |
||
1548 |
private static void checkSubArray(Object object, int fromIndex, int toIndex, int m) { |
|
1549 |
if (object instanceof int[]) { |
|
1550 |
checkSubArray((int[]) object, fromIndex, toIndex, m); |
|
1551 |
} else if (object instanceof long[]) { |
|
1552 |
checkSubArray((long[]) object, fromIndex, toIndex, m); |
|
1553 |
} else if (object instanceof short[]) { |
|
1554 |
checkSubArray((short[]) object, fromIndex, toIndex, m); |
|
1555 |
} else if (object instanceof byte[]) { |
|
1556 |
checkSubArray((byte[]) object, fromIndex, toIndex, m); |
|
1557 |
} else if (object instanceof char[]) { |
|
1558 |
checkSubArray((char[]) object, fromIndex, toIndex, m); |
|
1559 |
} else if (object instanceof float[]) { |
|
1560 |
checkSubArray((float[]) object, fromIndex, toIndex, m); |
|
1561 |
} else if (object instanceof double[]) { |
|
1562 |
checkSubArray((double[]) object, fromIndex, toIndex, m); |
|
5995
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
1563 |
} else if (object instanceof Integer[]) { |
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
1564 |
checkSubArray((Integer[]) object, fromIndex, toIndex, m); |
4233 | 1565 |
} else { |
1566 |
failed("Unknow type of array: " + object + " of class " + |
|
1567 |
object.getClass().getName()); |
|
1568 |
} |
|
1569 |
} |
|
1570 |
||
5995
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
1571 |
private static void checkSubArray(Integer[] a, int fromIndex, int toIndex, int m) { |
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
1572 |
for (int i = 0; i < fromIndex; i++) { |
8188
b90884cf34f5
7013585: Dual-pivot quicksort improvements for highly structured (nearly sorted) and data with small periods
alanb
parents:
6896
diff
changeset
|
1573 |
if (a[i].intValue() != 0xDEDA) { |
5995
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
1574 |
failed("Range sort changes left element on position " + i + |
8188
b90884cf34f5
7013585: Dual-pivot quicksort improvements for highly structured (nearly sorted) and data with small periods
alanb
parents:
6896
diff
changeset
|
1575 |
": " + a[i] + ", must be " + 0xDEDA); |
5995
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
1576 |
} |
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
1577 |
} |
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
1578 |
|
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
1579 |
for (int i = fromIndex; i < toIndex - 1; i++) { |
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
1580 |
if (a[i].intValue() > a[i + 1].intValue()) { |
6896
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1581 |
failedSort(i, "" + a[i], "" + a[i + 1]); |
5995
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
1582 |
} |
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
1583 |
} |
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
1584 |
|
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
1585 |
for (int i = toIndex; i < a.length; i++) { |
8188
b90884cf34f5
7013585: Dual-pivot quicksort improvements for highly structured (nearly sorted) and data with small periods
alanb
parents:
6896
diff
changeset
|
1586 |
if (a[i].intValue() != 0xBABA) { |
5995
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
1587 |
failed("Range sort changes right element on position " + i + |
8188
b90884cf34f5
7013585: Dual-pivot quicksort improvements for highly structured (nearly sorted) and data with small periods
alanb
parents:
6896
diff
changeset
|
1588 |
": " + a[i] + ", must be " + 0xBABA); |
5995
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
1589 |
} |
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
1590 |
} |
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
1591 |
} |
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
1592 |
|
4233 | 1593 |
private static void checkSubArray(int[] a, int fromIndex, int toIndex, int m) { |
1594 |
for (int i = 0; i < fromIndex; i++) { |
|
8188
b90884cf34f5
7013585: Dual-pivot quicksort improvements for highly structured (nearly sorted) and data with small periods
alanb
parents:
6896
diff
changeset
|
1595 |
if (a[i] != 0xDEDA) { |
4233 | 1596 |
failed("Range sort changes left element on position " + i + |
8188
b90884cf34f5
7013585: Dual-pivot quicksort improvements for highly structured (nearly sorted) and data with small periods
alanb
parents:
6896
diff
changeset
|
1597 |
": " + a[i] + ", must be " + 0xDEDA); |
4233 | 1598 |
} |
1599 |
} |
|
1600 |
||
1601 |
for (int i = fromIndex; i < toIndex - 1; i++) { |
|
1602 |
if (a[i] > a[i + 1]) { |
|
6896
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1603 |
failedSort(i, "" + a[i], "" + a[i + 1]); |
4233 | 1604 |
} |
1605 |
} |
|
1606 |
||
1607 |
for (int i = toIndex; i < a.length; i++) { |
|
8188
b90884cf34f5
7013585: Dual-pivot quicksort improvements for highly structured (nearly sorted) and data with small periods
alanb
parents:
6896
diff
changeset
|
1608 |
if (a[i] != 0xBABA) { |
4233 | 1609 |
failed("Range sort changes right element on position " + i + |
8188
b90884cf34f5
7013585: Dual-pivot quicksort improvements for highly structured (nearly sorted) and data with small periods
alanb
parents:
6896
diff
changeset
|
1610 |
": " + a[i] + ", must be " + 0xBABA); |
4233 | 1611 |
} |
1612 |
} |
|
1613 |
} |
|
1614 |
||
1615 |
private static void checkSubArray(byte[] a, int fromIndex, int toIndex, int m) { |
|
1616 |
for (int i = 0; i < fromIndex; i++) { |
|
8188
b90884cf34f5
7013585: Dual-pivot quicksort improvements for highly structured (nearly sorted) and data with small periods
alanb
parents:
6896
diff
changeset
|
1617 |
if (a[i] != (byte) 0xDEDA) { |
4233 | 1618 |
failed("Range sort changes left element on position " + i + |
8188
b90884cf34f5
7013585: Dual-pivot quicksort improvements for highly structured (nearly sorted) and data with small periods
alanb
parents:
6896
diff
changeset
|
1619 |
": " + a[i] + ", must be " + 0xDEDA); |
4233 | 1620 |
} |
1621 |
} |
|
1622 |
||
1623 |
for (int i = fromIndex; i < toIndex - 1; i++) { |
|
1624 |
if (a[i] > a[i + 1]) { |
|
6896
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1625 |
failedSort(i, "" + a[i], "" + a[i + 1]); |
4233 | 1626 |
} |
1627 |
} |
|
1628 |
||
1629 |
for (int i = toIndex; i < a.length; i++) { |
|
8188
b90884cf34f5
7013585: Dual-pivot quicksort improvements for highly structured (nearly sorted) and data with small periods
alanb
parents:
6896
diff
changeset
|
1630 |
if (a[i] != (byte) 0xBABA) { |
4233 | 1631 |
failed("Range sort changes right element on position " + i + |
8188
b90884cf34f5
7013585: Dual-pivot quicksort improvements for highly structured (nearly sorted) and data with small periods
alanb
parents:
6896
diff
changeset
|
1632 |
": " + a[i] + ", must be " + 0xBABA); |
4233 | 1633 |
} |
1634 |
} |
|
1635 |
} |
|
1636 |
||
1637 |
private static void checkSubArray(long[] a, int fromIndex, int toIndex, int m) { |
|
1638 |
for (int i = 0; i < fromIndex; i++) { |
|
8188
b90884cf34f5
7013585: Dual-pivot quicksort improvements for highly structured (nearly sorted) and data with small periods
alanb
parents:
6896
diff
changeset
|
1639 |
if (a[i] != (long) 0xDEDA) { |
4233 | 1640 |
failed("Range sort changes left element on position " + i + |
8188
b90884cf34f5
7013585: Dual-pivot quicksort improvements for highly structured (nearly sorted) and data with small periods
alanb
parents:
6896
diff
changeset
|
1641 |
": " + a[i] + ", must be " + 0xDEDA); |
4233 | 1642 |
} |
1643 |
} |
|
1644 |
||
1645 |
for (int i = fromIndex; i < toIndex - 1; i++) { |
|
1646 |
if (a[i] > a[i + 1]) { |
|
6896
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1647 |
failedSort(i, "" + a[i], "" + a[i + 1]); |
4233 | 1648 |
} |
1649 |
} |
|
1650 |
||
1651 |
for (int i = toIndex; i < a.length; i++) { |
|
8188
b90884cf34f5
7013585: Dual-pivot quicksort improvements for highly structured (nearly sorted) and data with small periods
alanb
parents:
6896
diff
changeset
|
1652 |
if (a[i] != (long) 0xBABA) { |
4233 | 1653 |
failed("Range sort changes right element on position " + i + |
8188
b90884cf34f5
7013585: Dual-pivot quicksort improvements for highly structured (nearly sorted) and data with small periods
alanb
parents:
6896
diff
changeset
|
1654 |
": " + a[i] + ", must be " + 0xBABA); |
4233 | 1655 |
} |
1656 |
} |
|
1657 |
} |
|
1658 |
||
1659 |
private static void checkSubArray(char[] a, int fromIndex, int toIndex, int m) { |
|
1660 |
for (int i = 0; i < fromIndex; i++) { |
|
8188
b90884cf34f5
7013585: Dual-pivot quicksort improvements for highly structured (nearly sorted) and data with small periods
alanb
parents:
6896
diff
changeset
|
1661 |
if (a[i] != (char) 0xDEDA) { |
4233 | 1662 |
failed("Range sort changes left element on position " + i + |
8188
b90884cf34f5
7013585: Dual-pivot quicksort improvements for highly structured (nearly sorted) and data with small periods
alanb
parents:
6896
diff
changeset
|
1663 |
": " + a[i] + ", must be " + 0xDEDA); |
4233 | 1664 |
} |
1665 |
} |
|
1666 |
||
1667 |
for (int i = fromIndex; i < toIndex - 1; i++) { |
|
1668 |
if (a[i] > a[i + 1]) { |
|
6896
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1669 |
failedSort(i, "" + a[i], "" + a[i + 1]); |
4233 | 1670 |
} |
1671 |
} |
|
1672 |
||
1673 |
for (int i = toIndex; i < a.length; i++) { |
|
8188
b90884cf34f5
7013585: Dual-pivot quicksort improvements for highly structured (nearly sorted) and data with small periods
alanb
parents:
6896
diff
changeset
|
1674 |
if (a[i] != (char) 0xBABA) { |
4233 | 1675 |
failed("Range sort changes right element on position " + i + |
8188
b90884cf34f5
7013585: Dual-pivot quicksort improvements for highly structured (nearly sorted) and data with small periods
alanb
parents:
6896
diff
changeset
|
1676 |
": " + a[i] + ", must be " + 0xBABA); |
4233 | 1677 |
} |
1678 |
} |
|
1679 |
} |
|
1680 |
||
1681 |
private static void checkSubArray(short[] a, int fromIndex, int toIndex, int m) { |
|
1682 |
for (int i = 0; i < fromIndex; i++) { |
|
8188
b90884cf34f5
7013585: Dual-pivot quicksort improvements for highly structured (nearly sorted) and data with small periods
alanb
parents:
6896
diff
changeset
|
1683 |
if (a[i] != (short) 0xDEDA) { |
4233 | 1684 |
failed("Range sort changes left element on position " + i + |
8188
b90884cf34f5
7013585: Dual-pivot quicksort improvements for highly structured (nearly sorted) and data with small periods
alanb
parents:
6896
diff
changeset
|
1685 |
": " + a[i] + ", must be " + 0xDEDA); |
4233 | 1686 |
} |
1687 |
} |
|
1688 |
||
1689 |
for (int i = fromIndex; i < toIndex - 1; i++) { |
|
1690 |
if (a[i] > a[i + 1]) { |
|
6896
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1691 |
failedSort(i, "" + a[i], "" + a[i + 1]); |
4233 | 1692 |
} |
1693 |
} |
|
1694 |
||
1695 |
for (int i = toIndex; i < a.length; i++) { |
|
8188
b90884cf34f5
7013585: Dual-pivot quicksort improvements for highly structured (nearly sorted) and data with small periods
alanb
parents:
6896
diff
changeset
|
1696 |
if (a[i] != (short) 0xBABA) { |
4233 | 1697 |
failed("Range sort changes right element on position " + i + |
8188
b90884cf34f5
7013585: Dual-pivot quicksort improvements for highly structured (nearly sorted) and data with small periods
alanb
parents:
6896
diff
changeset
|
1698 |
": " + a[i] + ", must be " + 0xBABA); |
4233 | 1699 |
} |
1700 |
} |
|
1701 |
} |
|
1702 |
||
1703 |
private static void checkSubArray(float[] a, int fromIndex, int toIndex, int m) { |
|
1704 |
for (int i = 0; i < fromIndex; i++) { |
|
8188
b90884cf34f5
7013585: Dual-pivot quicksort improvements for highly structured (nearly sorted) and data with small periods
alanb
parents:
6896
diff
changeset
|
1705 |
if (a[i] != (float) 0xDEDA) { |
4233 | 1706 |
failed("Range sort changes left element on position " + i + |
8188
b90884cf34f5
7013585: Dual-pivot quicksort improvements for highly structured (nearly sorted) and data with small periods
alanb
parents:
6896
diff
changeset
|
1707 |
": " + a[i] + ", must be " + 0xDEDA); |
4233 | 1708 |
} |
1709 |
} |
|
1710 |
||
1711 |
for (int i = fromIndex; i < toIndex - 1; i++) { |
|
1712 |
if (a[i] > a[i + 1]) { |
|
6896
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1713 |
failedSort(i, "" + a[i], "" + a[i + 1]); |
4233 | 1714 |
} |
1715 |
} |
|
1716 |
||
1717 |
for (int i = toIndex; i < a.length; i++) { |
|
8188
b90884cf34f5
7013585: Dual-pivot quicksort improvements for highly structured (nearly sorted) and data with small periods
alanb
parents:
6896
diff
changeset
|
1718 |
if (a[i] != (float) 0xBABA) { |
4233 | 1719 |
failed("Range sort changes right element on position " + i + |
8188
b90884cf34f5
7013585: Dual-pivot quicksort improvements for highly structured (nearly sorted) and data with small periods
alanb
parents:
6896
diff
changeset
|
1720 |
": " + a[i] + ", must be " + 0xBABA); |
4233 | 1721 |
} |
1722 |
} |
|
1723 |
} |
|
1724 |
||
1725 |
private static void checkSubArray(double[] a, int fromIndex, int toIndex, int m) { |
|
1726 |
for (int i = 0; i < fromIndex; i++) { |
|
8188
b90884cf34f5
7013585: Dual-pivot quicksort improvements for highly structured (nearly sorted) and data with small periods
alanb
parents:
6896
diff
changeset
|
1727 |
if (a[i] != (double) 0xDEDA) { |
4233 | 1728 |
failed("Range sort changes left element on position " + i + |
8188
b90884cf34f5
7013585: Dual-pivot quicksort improvements for highly structured (nearly sorted) and data with small periods
alanb
parents:
6896
diff
changeset
|
1729 |
": " + a[i] + ", must be " + 0xDEDA); |
4233 | 1730 |
} |
1731 |
} |
|
1732 |
||
1733 |
for (int i = fromIndex; i < toIndex - 1; i++) { |
|
1734 |
if (a[i] > a[i + 1]) { |
|
6896
d229d56fd918
6976036: Dual-pivot quicksort update (10/2010 tune-up)
alanb
parents:
5995
diff
changeset
|
1735 |
failedSort(i, "" + a[i], "" + a[i + 1]); |
4233 | 1736 |
} |
1737 |
} |
|
1738 |
||
1739 |
for (int i = toIndex; i < a.length; i++) { |
|
8188
b90884cf34f5
7013585: Dual-pivot quicksort improvements for highly structured (nearly sorted) and data with small periods
alanb
parents:
6896
diff
changeset
|
1740 |
if (a[i] != (double) 0xBABA) { |
4233 | 1741 |
failed("Range sort changes right element on position " + i + |
8188
b90884cf34f5
7013585: Dual-pivot quicksort improvements for highly structured (nearly sorted) and data with small periods
alanb
parents:
6896
diff
changeset
|
1742 |
": " + a[i] + ", must be " + 0xBABA); |
4233 | 1743 |
} |
1744 |
} |
|
1745 |
} |
|
1746 |
||
5995
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
1747 |
private static void checkRange(Object object, int m) { |
4233 | 1748 |
if (object instanceof int[]) { |
5995
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
1749 |
checkRange((int[]) object, m); |
4233 | 1750 |
} else if (object instanceof long[]) { |
5995
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
1751 |
checkRange((long[]) object, m); |
4233 | 1752 |
} else if (object instanceof short[]) { |
5995
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
1753 |
checkRange((short[]) object, m); |
4233 | 1754 |
} else if (object instanceof byte[]) { |
5995
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
1755 |
checkRange((byte[]) object, m); |
4233 | 1756 |
} else if (object instanceof char[]) { |
5995
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
1757 |
checkRange((char[]) object, m); |
4233 | 1758 |
} else if (object instanceof float[]) { |
5995
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
1759 |
checkRange((float[]) object, m); |
4233 | 1760 |
} else if (object instanceof double[]) { |
5995
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
1761 |
checkRange((double[]) object, m); |
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
1762 |
} else if (object instanceof Integer[]) { |
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
1763 |
checkRange((Integer[]) object, m); |
4233 | 1764 |
} else { |
1765 |
failed("Unknow type of array: " + object + " of class " + |
|
1766 |
object.getClass().getName()); |
|
1767 |
} |
|
1768 |
} |
|
1769 |
||
5995
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
1770 |
private static void checkRange(Integer[] a, int m) { |
4233 | 1771 |
try { |
1772 |
Arrays.sort(a, m + 1, m); |
|
1773 |
||
1774 |
failed("Sort does not throw IllegalArgumentException " + |
|
1775 |
" as expected: fromIndex = " + (m + 1) + |
|
1776 |
" toIndex = " + m); |
|
1777 |
} |
|
1778 |
catch (IllegalArgumentException iae) { |
|
1779 |
try { |
|
1780 |
Arrays.sort(a, -m, a.length); |
|
1781 |
||
1782 |
failed("Sort does not throw ArrayIndexOutOfBoundsException " + |
|
1783 |
" as expected: fromIndex = " + (-m)); |
|
1784 |
} |
|
1785 |
catch (ArrayIndexOutOfBoundsException aoe) { |
|
1786 |
try { |
|
1787 |
Arrays.sort(a, 0, a.length + m); |
|
1788 |
||
1789 |
failed("Sort does not throw ArrayIndexOutOfBoundsException " + |
|
1790 |
" as expected: toIndex = " + (a.length + m)); |
|
1791 |
} |
|
1792 |
catch (ArrayIndexOutOfBoundsException aie) { |
|
1793 |
return; |
|
1794 |
} |
|
1795 |
} |
|
1796 |
} |
|
1797 |
} |
|
1798 |
||
5995
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
1799 |
private static void checkRange(int[] a, int m) { |
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
1800 |
try { |
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
1801 |
Arrays.sort(a, m + 1, m); |
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
1802 |
|
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
1803 |
failed("Sort does not throw IllegalArgumentException " + |
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
1804 |
" as expected: fromIndex = " + (m + 1) + |
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
1805 |
" toIndex = " + m); |
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
1806 |
} |
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
1807 |
catch (IllegalArgumentException iae) { |
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
1808 |
try { |
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
1809 |
Arrays.sort(a, -m, a.length); |
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
1810 |
|
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
1811 |
failed("Sort does not throw ArrayIndexOutOfBoundsException " + |
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
1812 |
" as expected: fromIndex = " + (-m)); |
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
1813 |
} |
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
1814 |
catch (ArrayIndexOutOfBoundsException aoe) { |
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
1815 |
try { |
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
1816 |
Arrays.sort(a, 0, a.length + m); |
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
1817 |
|
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
1818 |
failed("Sort does not throw ArrayIndexOutOfBoundsException " + |
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
1819 |
" as expected: toIndex = " + (a.length + m)); |
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
1820 |
} |
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
1821 |
catch (ArrayIndexOutOfBoundsException aie) { |
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
1822 |
return; |
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
1823 |
} |
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
1824 |
} |
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
1825 |
} |
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
1826 |
} |
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
1827 |
|
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
1828 |
private static void checkRange(long[] a, int m) { |
4233 | 1829 |
try { |
1830 |
Arrays.sort(a, m + 1, m); |
|
1831 |
||
1832 |
failed("Sort does not throw IllegalArgumentException " + |
|
1833 |
" as expected: fromIndex = " + (m + 1) + |
|
1834 |
" toIndex = " + m); |
|
1835 |
} |
|
1836 |
catch (IllegalArgumentException iae) { |
|
1837 |
try { |
|
1838 |
Arrays.sort(a, -m, a.length); |
|
1839 |
||
1840 |
failed("Sort does not throw ArrayIndexOutOfBoundsException " + |
|
1841 |
" as expected: fromIndex = " + (-m)); |
|
1842 |
} |
|
1843 |
catch (ArrayIndexOutOfBoundsException aoe) { |
|
1844 |
try { |
|
1845 |
Arrays.sort(a, 0, a.length + m); |
|
1846 |
||
1847 |
failed("Sort does not throw ArrayIndexOutOfBoundsException " + |
|
1848 |
" as expected: toIndex = " + (a.length + m)); |
|
1849 |
} |
|
1850 |
catch (ArrayIndexOutOfBoundsException aie) { |
|
1851 |
return; |
|
1852 |
} |
|
1853 |
} |
|
1854 |
} |
|
1855 |
} |
|
1856 |
||
5995
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
1857 |
private static void checkRange(byte[] a, int m) { |
4233 | 1858 |
try { |
1859 |
Arrays.sort(a, m + 1, m); |
|
1860 |
||
1861 |
failed("Sort does not throw IllegalArgumentException " + |
|
1862 |
" as expected: fromIndex = " + (m + 1) + |
|
1863 |
" toIndex = " + m); |
|
1864 |
} |
|
1865 |
catch (IllegalArgumentException iae) { |
|
1866 |
try { |
|
1867 |
Arrays.sort(a, -m, a.length); |
|
1868 |
||
1869 |
failed("Sort does not throw ArrayIndexOutOfBoundsException " + |
|
1870 |
" as expected: fromIndex = " + (-m)); |
|
1871 |
} |
|
1872 |
catch (ArrayIndexOutOfBoundsException aoe) { |
|
1873 |
try { |
|
1874 |
Arrays.sort(a, 0, a.length + m); |
|
1875 |
||
1876 |
failed("Sort does not throw ArrayIndexOutOfBoundsException " + |
|
1877 |
" as expected: toIndex = " + (a.length + m)); |
|
1878 |
} |
|
1879 |
catch (ArrayIndexOutOfBoundsException aie) { |
|
1880 |
return; |
|
1881 |
} |
|
1882 |
} |
|
1883 |
} |
|
1884 |
} |
|
1885 |
||
5995
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
1886 |
private static void checkRange(short[] a, int m) { |
4233 | 1887 |
try { |
1888 |
Arrays.sort(a, m + 1, m); |
|
1889 |
||
1890 |
failed("Sort does not throw IllegalArgumentException " + |
|
1891 |
" as expected: fromIndex = " + (m + 1) + |
|
1892 |
" toIndex = " + m); |
|
1893 |
} |
|
1894 |
catch (IllegalArgumentException iae) { |
|
1895 |
try { |
|
1896 |
Arrays.sort(a, -m, a.length); |
|
1897 |
||
1898 |
failed("Sort does not throw ArrayIndexOutOfBoundsException " + |
|
1899 |
" as expected: fromIndex = " + (-m)); |
|
1900 |
} |
|
1901 |
catch (ArrayIndexOutOfBoundsException aoe) { |
|
1902 |
try { |
|
1903 |
Arrays.sort(a, 0, a.length + m); |
|
1904 |
||
1905 |
failed("Sort does not throw ArrayIndexOutOfBoundsException " + |
|
1906 |
" as expected: toIndex = " + (a.length + m)); |
|
1907 |
} |
|
1908 |
catch (ArrayIndexOutOfBoundsException aie) { |
|
1909 |
return; |
|
1910 |
} |
|
1911 |
} |
|
1912 |
} |
|
1913 |
} |
|
1914 |
||
5995
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
1915 |
private static void checkRange(char[] a, int m) { |
4233 | 1916 |
try { |
1917 |
Arrays.sort(a, m + 1, m); |
|
1918 |
||
1919 |
failed("Sort does not throw IllegalArgumentException " + |
|
1920 |
" as expected: fromIndex = " + (m + 1) + |
|
1921 |
" toIndex = " + m); |
|
1922 |
} |
|
1923 |
catch (IllegalArgumentException iae) { |
|
1924 |
try { |
|
1925 |
Arrays.sort(a, -m, a.length); |
|
1926 |
||
1927 |
failed("Sort does not throw ArrayIndexOutOfBoundsException " + |
|
1928 |
" as expected: fromIndex = " + (-m)); |
|
1929 |
} |
|
1930 |
catch (ArrayIndexOutOfBoundsException aoe) { |
|
1931 |
try { |
|
1932 |
Arrays.sort(a, 0, a.length + m); |
|
1933 |
||
1934 |
failed("Sort does not throw ArrayIndexOutOfBoundsException " + |
|
1935 |
" as expected: toIndex = " + (a.length + m)); |
|
1936 |
} |
|
1937 |
catch (ArrayIndexOutOfBoundsException aie) { |
|
1938 |
return; |
|
1939 |
} |
|
1940 |
} |
|
1941 |
} |
|
1942 |
} |
|
1943 |
||
5995
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
1944 |
private static void checkRange(float[] a, int m) { |
4233 | 1945 |
try { |
1946 |
Arrays.sort(a, m + 1, m); |
|
1947 |
||
1948 |
failed("Sort does not throw IllegalArgumentException " + |
|
1949 |
" as expected: fromIndex = " + (m + 1) + |
|
1950 |
" toIndex = " + m); |
|
1951 |
} |
|
1952 |
catch (IllegalArgumentException iae) { |
|
1953 |
try { |
|
1954 |
Arrays.sort(a, -m, a.length); |
|
1955 |
||
1956 |
failed("Sort does not throw ArrayIndexOutOfBoundsException " + |
|
1957 |
" as expected: fromIndex = " + (-m)); |
|
1958 |
} |
|
1959 |
catch (ArrayIndexOutOfBoundsException aoe) { |
|
1960 |
try { |
|
1961 |
Arrays.sort(a, 0, a.length + m); |
|
1962 |
||
1963 |
failed("Sort does not throw ArrayIndexOutOfBoundsException " + |
|
1964 |
" as expected: toIndex = " + (a.length + m)); |
|
1965 |
} |
|
1966 |
catch (ArrayIndexOutOfBoundsException aie) { |
|
1967 |
return; |
|
1968 |
} |
|
1969 |
} |
|
1970 |
} |
|
1971 |
} |
|
1972 |
||
5995
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
1973 |
private static void checkRange(double[] a, int m) { |
4233 | 1974 |
try { |
1975 |
Arrays.sort(a, m + 1, m); |
|
1976 |
||
1977 |
failed("Sort does not throw IllegalArgumentException " + |
|
1978 |
" as expected: fromIndex = " + (m + 1) + |
|
1979 |
" toIndex = " + m); |
|
1980 |
} |
|
1981 |
catch (IllegalArgumentException iae) { |
|
1982 |
try { |
|
1983 |
Arrays.sort(a, -m, a.length); |
|
1984 |
||
1985 |
failed("Sort does not throw ArrayIndexOutOfBoundsException " + |
|
1986 |
" as expected: fromIndex = " + (-m)); |
|
1987 |
} |
|
1988 |
catch (ArrayIndexOutOfBoundsException aoe) { |
|
1989 |
try { |
|
1990 |
Arrays.sort(a, 0, a.length + m); |
|
1991 |
||
1992 |
failed("Sort does not throw ArrayIndexOutOfBoundsException " + |
|
1993 |
" as expected: toIndex = " + (a.length + m)); |
|
1994 |
} |
|
1995 |
catch (ArrayIndexOutOfBoundsException aie) { |
|
1996 |
return; |
|
1997 |
} |
|
1998 |
} |
|
1999 |
} |
|
2000 |
} |
|
2001 |
||
5995
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
2002 |
private static void outArray(Object[] a) { |
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
2003 |
for (int i = 0; i < a.length; i++) { |
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
2004 |
out.print(a[i] + " "); |
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
2005 |
} |
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
2006 |
out.println(); |
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
2007 |
} |
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
2008 |
|
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
2009 |
private static void outArray(int[] a) { |
4233 | 2010 |
for (int i = 0; i < a.length; i++) { |
2011 |
out.print(a[i] + " "); |
|
2012 |
} |
|
2013 |
out.println(); |
|
2014 |
} |
|
2015 |
||
5995
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
2016 |
private static void outArray(float[] a) { |
4233 | 2017 |
for (int i = 0; i < a.length; i++) { |
2018 |
out.print(a[i] + " "); |
|
2019 |
} |
|
2020 |
out.println(); |
|
2021 |
} |
|
2022 |
||
5995
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
2023 |
private static void outArray(double[] a) { |
4233 | 2024 |
for (int i = 0; i < a.length; i++) { |
2025 |
out.print(a[i] + " "); |
|
2026 |
} |
|
2027 |
out.println(); |
|
2028 |
} |
|
2029 |
||
8193
626b859aabb2
7018258: Dual-pivot updates in 7013585 can fail with ArrayIndexOutOfBoundsException
alanb
parents:
8188
diff
changeset
|
2030 |
private static class MyRandom extends Random { |
626b859aabb2
7018258: Dual-pivot updates in 7013585 can fail with ArrayIndexOutOfBoundsException
alanb
parents:
8188
diff
changeset
|
2031 |
MyRandom(long seed) { |
626b859aabb2
7018258: Dual-pivot updates in 7013585 can fail with ArrayIndexOutOfBoundsException
alanb
parents:
8188
diff
changeset
|
2032 |
super(seed); |
626b859aabb2
7018258: Dual-pivot updates in 7013585 can fail with ArrayIndexOutOfBoundsException
alanb
parents:
8188
diff
changeset
|
2033 |
mySeed = seed; |
626b859aabb2
7018258: Dual-pivot updates in 7013585 can fail with ArrayIndexOutOfBoundsException
alanb
parents:
8188
diff
changeset
|
2034 |
} |
626b859aabb2
7018258: Dual-pivot updates in 7013585 can fail with ArrayIndexOutOfBoundsException
alanb
parents:
8188
diff
changeset
|
2035 |
|
626b859aabb2
7018258: Dual-pivot updates in 7013585 can fail with ArrayIndexOutOfBoundsException
alanb
parents:
8188
diff
changeset
|
2036 |
long getSeed() { |
626b859aabb2
7018258: Dual-pivot updates in 7013585 can fail with ArrayIndexOutOfBoundsException
alanb
parents:
8188
diff
changeset
|
2037 |
return mySeed; |
626b859aabb2
7018258: Dual-pivot updates in 7013585 can fail with ArrayIndexOutOfBoundsException
alanb
parents:
8188
diff
changeset
|
2038 |
} |
626b859aabb2
7018258: Dual-pivot updates in 7013585 can fail with ArrayIndexOutOfBoundsException
alanb
parents:
8188
diff
changeset
|
2039 |
|
626b859aabb2
7018258: Dual-pivot updates in 7013585 can fail with ArrayIndexOutOfBoundsException
alanb
parents:
8188
diff
changeset
|
2040 |
private long mySeed; |
626b859aabb2
7018258: Dual-pivot updates in 7013585 can fail with ArrayIndexOutOfBoundsException
alanb
parents:
8188
diff
changeset
|
2041 |
} |
626b859aabb2
7018258: Dual-pivot updates in 7013585 can fail with ArrayIndexOutOfBoundsException
alanb
parents:
8188
diff
changeset
|
2042 |
|
5995
0b76e67c2054
6947216: Even more Dual-pivot quicksort improvements
alanb
parents:
5506
diff
changeset
|
2043 |
private static String ourDescription; |
4177
208f8c11e7ba
6896573: Arrays.sort(long[]) fails with StackOverflowError
alanb
parents:
diff
changeset
|
2044 |
} |