6 * under the terms of the GNU General Public License version 2 only, as
7 * published by the Free Software Foundation.
8 *
9 * This code is distributed in the hope that it will be useful, but WITHOUT
10 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
11 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
12 * version 2 for more details (a copy is included in the LICENSE file that
13 * accompanied this code).
14 *
15 * You should have received a copy of the GNU General Public License version
16 * 2 along with this work; if not, write to the Free Software Foundation,
17 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
18 *
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.
22 */
23
24 /*
25 * @test
26 * @compile/module=java.base java/util/SortingHelper.java
27 * @bug 6880672 6896573 6899694 6976036 7013585 7018258 8003981 8226297
28 * @build Sorting
29 * @run main/othervm -XX:+UnlockDiagnosticVMOptions -XX:DisableIntrinsic=_arraySort,_arrayPartition Sorting -shortrun
30 * @run main/othervm -XX:-TieredCompilation -XX:CompileCommand=CompileThresholdScaling,java.util.DualPivotQuicksort::sort,0.0001 Sorting -shortrun
31 * @summary Exercise Arrays.sort, Arrays.parallelSort
32 *
33 * @author Vladimir Yaroslavskiy
34 * @author Jon Bentley
35 * @author Josh Bloch
36 */
37
38 import java.io.PrintStream;
39 import java.util.Comparator;
40 import java.util.Random;
41 import java.util.SortingHelper;
42
43 public class Sorting {
44
45 private static final PrintStream out = System.out;
46 private static final PrintStream err = System.err;
47
48 // Array lengths used in a long run (default)
49 private static final int[] LONG_RUN_LENGTHS = {
50 1, 3, 8, 21, 55, 100, 1_000, 10_000, 100_000 };
51
52 // Array lengths used in a short run
53 private static final int[] SHORT_RUN_LENGTHS = {
54 1, 8, 55, 100, 10_000 };
55
56 // Random initial values used in a long run (default)
57 private static final TestRandom[] LONG_RUN_RANDOMS = {
58 TestRandom.BABA, TestRandom.DEDA, TestRandom.C0FFEE };
59
60 // Random initial values used in a short run
61 private static final TestRandom[] SHORT_RUN_RANDOMS = {
62 TestRandom.C0FFEE };
63
64 // Constants used in subarray sorting
65 private static final int A380 = 0xA380;
66 private static final int B747 = 0xB747;
67
68 private final SortingHelper sortingHelper;
69 private final TestRandom[] randoms;
70 private final int[] lengths;
71 private Object[] gold;
72 private Object[] test;
73
74 public static void main(String[] args) {
75 long start = System.currentTimeMillis();
76 boolean shortRun = args.length > 0 && args[0].equals("-shortrun");
77
78 int[] lengths = shortRun ? SHORT_RUN_LENGTHS : LONG_RUN_LENGTHS;
79 TestRandom[] randoms = shortRun ? SHORT_RUN_RANDOMS : LONG_RUN_RANDOMS;
80
81 new Sorting(SortingHelper.DUAL_PIVOT_QUICKSORT, randoms, lengths).testCore();
82 new Sorting(SortingHelper.PARALLEL_SORT, randoms, lengths).testCore();
83 new Sorting(SortingHelper.HEAP_SORT, randoms, lengths).testBasic();
84 new Sorting(SortingHelper.ARRAYS_SORT, randoms, lengths).testAll();
85 new Sorting(SortingHelper.ARRAYS_PARALLEL_SORT, randoms, lengths).testAll();
86
87 long end = System.currentTimeMillis();
88 out.format("PASSED in %d sec.\n", (end - start) / 1000);
89 }
90
91 private Sorting(SortingHelper sortingHelper, TestRandom[] randoms, int[] lengths) {
92 this.sortingHelper = sortingHelper;
93 this.randoms = randoms;
125 testMergingSort(length, random);
126 testSubArray(length, random);
127 testNegativeZero(length, random);
128 testFloatingPointSorting(length, random);
129 }
130 }
131
132 private void testAll() {
133 for (int length : lengths) {
134 createData(length);
135 testAll(length);
136 }
137 }
138
139 private void testAll(int length) {
140 testCore(length);
141
142 for (TestRandom random : randoms) {
143 testRange(length, random);
144 testStability(length, random);
145 }
146 }
147
148 private void testEmptyArray() {
149 testEmptyAndNullIntArray();
150 testEmptyAndNullLongArray();
151 testEmptyAndNullByteArray();
152 testEmptyAndNullCharArray();
153 testEmptyAndNullShortArray();
154 testEmptyAndNullFloatArray();
155 testEmptyAndNullDoubleArray();
156 }
157
158 private void testStability(int length, TestRandom random) {
159 printTestName("Test stability", random, length);
160
161 Pair[] a = build(length, random);
162 sortingHelper.sort(a);
163 checkSorted(a);
164 checkStable(a);
165
166 a = build(length, random);
167 sortingHelper.sort(a, pairComparator);
329 convertData(length);
330
331 for (int i = 0; i < test.length; i++) {
332 printTestName("Test range check", random, length,
333 ", m = " + m + ", " + getType(i));
334 checkRange(test[i], m);
335 }
336 }
337 out.println();
338 }
339
340 private void checkSorted(Pair[] a) {
341 for (int i = 0; i < a.length - 1; i++) {
342 if (a[i].getKey() > a[i + 1].getKey()) {
343 fail("Array is not sorted at " + i + "-th position: " +
344 a[i].getKey() + " and " + a[i + 1].getKey());
345 }
346 }
347 }
348
349 private void checkStable(Pair[] a) {
350 for (int i = 0; i < a.length / 4; ) {
351 int key1 = a[i].getKey();
352 int value1 = a[i++].getValue();
353 int key2 = a[i].getKey();
354 int value2 = a[i++].getValue();
355 int key3 = a[i].getKey();
356 int value3 = a[i++].getValue();
357 int key4 = a[i].getKey();
358 int value4 = a[i++].getValue();
359
360 if (!(key1 == key2 && key2 == key3 && key3 == key4)) {
361 fail("Keys are different " + key1 + ", " + key2 + ", " +
362 key3 + ", " + key4 + " at position " + i);
363 }
364 if (!(value1 < value2 && value2 < value3 && value3 < value4)) {
365 fail("Sorting is not stable at position " + i +
366 ". Second values have been changed: " + value1 + ", " +
367 value2 + ", " + value3 + ", " + value4);
368 }
|
6 * under the terms of the GNU General Public License version 2 only, as
7 * published by the Free Software Foundation.
8 *
9 * This code is distributed in the hope that it will be useful, but WITHOUT
10 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
11 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
12 * version 2 for more details (a copy is included in the LICENSE file that
13 * accompanied this code).
14 *
15 * You should have received a copy of the GNU General Public License version
16 * 2 along with this work; if not, write to the Free Software Foundation,
17 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
18 *
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.
22 */
23
24 /*
25 * @test
26 * @bug 6880672 6896573 6899694 6976036 7013585 7018258 8003981 8226297
27 * @library /test/lib
28 * @compile/module=java.base java/util/SortingHelper.java
29 * @build Sorting
30 * @run main/othervm -XX:+UnlockDiagnosticVMOptions -XX:DisableIntrinsic=_arraySort,_arrayPartition Sorting -shortrun
31 * @run main/othervm -XX:-TieredCompilation -XX:CompileCommand=CompileThresholdScaling,java.util.DualPivotQuicksort::sort,0.0001 Sorting -shortrun
32 * @summary Exercise Arrays.sort, Arrays.parallelSort
33 *
34 * @author Vladimir Yaroslavskiy
35 * @author Jon Bentley
36 * @author Josh Bloch
37 */
38
39 import java.io.PrintStream;
40 import java.util.Comparator;
41 import java.util.Random;
42 import java.util.SortingHelper;
43
44 import jdk.test.lib.valueclass.AsValueClass;
45
46 public class Sorting {
47
48 private static final PrintStream out = System.out;
49 private static final PrintStream err = System.err;
50
51 // Array lengths used in a long run (default)
52 private static final int[] LONG_RUN_LENGTHS = {
53 1, 3, 8, 21, 55, 100, 1_000, 10_000, 100_000 };
54
55 // Array lengths used in a short run
56 private static final int[] SHORT_RUN_LENGTHS = {
57 1, 8, 55, 100, 10_000 };
58
59 // Random initial values used in a long run (default)
60 private static final TestRandom[] LONG_RUN_RANDOMS = {
61 TestRandom.BABA, TestRandom.DEDA, TestRandom.C0FFEE };
62
63 // Random initial values used in a short run
64 private static final TestRandom[] SHORT_RUN_RANDOMS = {
65 TestRandom.C0FFEE };
66
67 // Constants used in subarray sorting
68 private static final int A380 = 0xA380;
69 private static final int B747 = 0xB747;
70
71 private final SortingHelper sortingHelper;
72 private final TestRandom[] randoms;
73 private final int[] lengths;
74 private Object[] gold;
75 private Object[] test;
76
77 @AsValueClass
78 record Point(int x, int y) implements Comparable<Point> {
79 public int compareTo(Point p) {
80 return Integer.compare(x * x + y * y, p.x * p.x + p.y * p.y);
81 }
82 }
83
84 public static void main(String[] args) {
85 long start = System.currentTimeMillis();
86 boolean shortRun = args.length > 0 && args[0].equals("-shortrun");
87
88 int[] lengths = shortRun ? SHORT_RUN_LENGTHS : LONG_RUN_LENGTHS;
89 TestRandom[] randoms = shortRun ? SHORT_RUN_RANDOMS : LONG_RUN_RANDOMS;
90
91 new Sorting(SortingHelper.DUAL_PIVOT_QUICKSORT, randoms, lengths).testCore();
92 new Sorting(SortingHelper.PARALLEL_SORT, randoms, lengths).testCore();
93 new Sorting(SortingHelper.HEAP_SORT, randoms, lengths).testBasic();
94 new Sorting(SortingHelper.ARRAYS_SORT, randoms, lengths).testAll();
95 new Sorting(SortingHelper.ARRAYS_PARALLEL_SORT, randoms, lengths).testAll();
96
97 long end = System.currentTimeMillis();
98 out.format("PASSED in %d sec.\n", (end - start) / 1000);
99 }
100
101 private Sorting(SortingHelper sortingHelper, TestRandom[] randoms, int[] lengths) {
102 this.sortingHelper = sortingHelper;
103 this.randoms = randoms;
135 testMergingSort(length, random);
136 testSubArray(length, random);
137 testNegativeZero(length, random);
138 testFloatingPointSorting(length, random);
139 }
140 }
141
142 private void testAll() {
143 for (int length : lengths) {
144 createData(length);
145 testAll(length);
146 }
147 }
148
149 private void testAll(int length) {
150 testCore(length);
151
152 for (TestRandom random : randoms) {
153 testRange(length, random);
154 testStability(length, random);
155 testValueClass(length, random);
156 }
157 }
158
159 private void testValueClass(int length, TestRandom random) {
160 printTestName("Test value class (Point[])", random, length);
161
162 Point[] points = new Point[length];
163 for (int i = 0; i < length; i++) {
164 points[i] = new Point(random.nextInt(10) - 5, random.nextInt(10) - 5);
165 }
166
167 sortingHelper.sort(points);
168 checkSorted(points);
169
170 Comparator<Point> byXThenY = Comparator.comparingInt(Point::x).thenComparingInt(Point::y);
171 sortingHelper.sort(points, byXThenY);
172 checkSorted(points, byXThenY);
173
174 out.println();
175 }
176
177 private void testEmptyArray() {
178 testEmptyAndNullIntArray();
179 testEmptyAndNullLongArray();
180 testEmptyAndNullByteArray();
181 testEmptyAndNullCharArray();
182 testEmptyAndNullShortArray();
183 testEmptyAndNullFloatArray();
184 testEmptyAndNullDoubleArray();
185 }
186
187 private void testStability(int length, TestRandom random) {
188 printTestName("Test stability", random, length);
189
190 Pair[] a = build(length, random);
191 sortingHelper.sort(a);
192 checkSorted(a);
193 checkStable(a);
194
195 a = build(length, random);
196 sortingHelper.sort(a, pairComparator);
358 convertData(length);
359
360 for (int i = 0; i < test.length; i++) {
361 printTestName("Test range check", random, length,
362 ", m = " + m + ", " + getType(i));
363 checkRange(test[i], m);
364 }
365 }
366 out.println();
367 }
368
369 private void checkSorted(Pair[] a) {
370 for (int i = 0; i < a.length - 1; i++) {
371 if (a[i].getKey() > a[i + 1].getKey()) {
372 fail("Array is not sorted at " + i + "-th position: " +
373 a[i].getKey() + " and " + a[i + 1].getKey());
374 }
375 }
376 }
377
378 private void checkSorted(Point[] a) {
379 for (int i = 0; i < a.length - 1; i++) {
380 if (a[i].compareTo(a[i + 1]) > 0) {
381 fail("Point array is not sorted at " + i + "-th position: " + a[i] + " and " + a[i + 1]);
382 }
383 }
384 }
385
386 private void checkSorted(Point[] a, Comparator<Point> c) {
387 for (int i = 0; i < a.length - 1; i++) {
388 if (c.compare(a[i], a[i + 1]) > 0) {
389 fail("Point array is not sorted at " + i + "-th position: " + a[i] + " and " + a[i + 1]);
390 }
391 }
392 }
393
394 private void checkStable(Pair[] a) {
395 for (int i = 0; i < a.length / 4; ) {
396 int key1 = a[i].getKey();
397 int value1 = a[i++].getValue();
398 int key2 = a[i].getKey();
399 int value2 = a[i++].getValue();
400 int key3 = a[i].getKey();
401 int value3 = a[i++].getValue();
402 int key4 = a[i].getKey();
403 int value4 = a[i++].getValue();
404
405 if (!(key1 == key2 && key2 == key3 && key3 == key4)) {
406 fail("Keys are different " + key1 + ", " + key2 + ", " +
407 key3 + ", " + key4 + " at position " + i);
408 }
409 if (!(value1 < value2 && value2 < value3 && value3 < value4)) {
410 fail("Sorting is not stable at position " + i +
411 ". Second values have been changed: " + value1 + ", " +
412 value2 + ", " + value3 + ", " + value4);
413 }
|