|
1 /* |
|
2 * Copyright 2009 Sun Microsystems, Inc. All Rights Reserved. |
|
3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. |
|
4 * |
|
5 * This code is free software; you can redistribute it and/or modify it |
|
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 Sun Microsystems, Inc., 4150 Network Circle, Santa Clara, |
|
20 * CA 95054 USA or visit www.sun.com if you need additional information or |
|
21 * have any questions. |
|
22 */ |
|
23 |
|
24 /* |
|
25 * @test |
|
26 * @bug 6880672 6896573 |
|
27 * @summary Exercise Arrays.sort |
|
28 * @build Sorting |
|
29 * @run main Sorting -shortrun |
|
30 * @author Vladimir Yaroslavskiy, Josh Bloch, Jon Bentley |
|
31 */ |
|
32 |
|
33 import java.util.Arrays; |
|
34 import java.util.Random; |
|
35 import java.io.PrintStream; |
|
36 |
|
37 public class Sorting { |
|
38 static final PrintStream out = System.out; |
|
39 static final PrintStream err = System.err; |
|
40 |
|
41 // array lengths used in a long run (default) |
|
42 static final int[] LONG_RUN = { |
|
43 0, 1, 2, 3, 5, 8, 13, 21, 34, 55, 100, 1000, 10000, 100000, 1000000}; |
|
44 |
|
45 // array lengths used in a short run |
|
46 static final int[] SHORT_RUN = {0, 1, 2, 3, 21, 55, 1000, 10000, 500000}; |
|
47 |
|
48 public static void main(String[] args) { |
|
49 boolean shortRun = false; |
|
50 if (args.length > 0 && args[0].equals("-shortrun")) |
|
51 shortRun = true; |
|
52 |
|
53 long start = System.nanoTime(); |
|
54 |
|
55 testAndCheck((shortRun) ? SHORT_RUN : LONG_RUN); |
|
56 |
|
57 long end = System.nanoTime(); |
|
58 |
|
59 out.println(); |
|
60 out.format("PASS in %ds%n", Math.round((end - start) / 1e9)); |
|
61 } |
|
62 |
|
63 static void testAndCheck(int[] lengths) { |
|
64 for (int len : lengths) { |
|
65 out.println(); |
|
66 ArrayBuilder.reset(); |
|
67 int[] golden = new int[len]; |
|
68 |
|
69 for (int m = 1; m < 2 * len; m *= 2) { |
|
70 for (ArrayBuilder builder : ArrayBuilder.values()) { |
|
71 builder.build(golden, m); |
|
72 int[] test = golden.clone(); |
|
73 |
|
74 for (Converter converter : Converter.values()) { |
|
75 out.println("Test: " + converter + " " + builder + |
|
76 "len = " + len + ", m = " + m); |
|
77 Object convertedGolden = converter.convert(golden); |
|
78 Object convertedTest = converter.convert(test); |
|
79 sort(convertedTest); |
|
80 checkWithCheckSum(convertedTest, convertedGolden); |
|
81 } |
|
82 } |
|
83 } |
|
84 } |
|
85 } |
|
86 |
|
87 static enum Converter { |
|
88 INT { |
|
89 Object convert(int[] a) { |
|
90 return a; |
|
91 } |
|
92 }, |
|
93 LONG { |
|
94 Object convert(int[] a) { |
|
95 long[] b = new long[a.length]; |
|
96 |
|
97 for (int i = 0; i < a.length; i++) { |
|
98 b[i] = (int) a[i]; |
|
99 } |
|
100 return b; |
|
101 } |
|
102 }, |
|
103 BYTE { |
|
104 Object convert(int[] a) { |
|
105 byte[] b = new byte[a.length]; |
|
106 |
|
107 for (int i = 0; i < a.length; i++) { |
|
108 b[i] = (byte) a[i]; |
|
109 } |
|
110 return b; |
|
111 } |
|
112 }, |
|
113 SHORT { |
|
114 Object convert(int[] a) { |
|
115 short[] b = new short[a.length]; |
|
116 |
|
117 for (int i = 0; i < a.length; i++) { |
|
118 b[i] = (short) a[i]; |
|
119 } |
|
120 return b; |
|
121 } |
|
122 }, |
|
123 CHAR { |
|
124 Object convert(int[] a) { |
|
125 char[] b = new char[a.length]; |
|
126 |
|
127 for (int i = 0; i < a.length; i++) { |
|
128 b[i] = (char) a[i]; |
|
129 } |
|
130 return b; |
|
131 } |
|
132 }, |
|
133 FLOAT { |
|
134 Object convert(int[] a) { |
|
135 float[] b = new float[a.length]; |
|
136 |
|
137 for (int i = 0; i < a.length; i++) { |
|
138 b[i] = (float) a[i]; |
|
139 } |
|
140 return b; |
|
141 } |
|
142 }, |
|
143 DOUBLE { |
|
144 Object convert(int[] a) { |
|
145 double[] b = new double[a.length]; |
|
146 |
|
147 for (int i = 0; i < a.length; i++) { |
|
148 b[i] = (double) a[i]; |
|
149 } |
|
150 return b; |
|
151 } |
|
152 }; |
|
153 |
|
154 abstract Object convert(int[] a); |
|
155 |
|
156 @Override public String toString() { |
|
157 String name = name(); |
|
158 |
|
159 for (int i = name.length(); i < 9; i++) { |
|
160 name += " "; |
|
161 } |
|
162 return name; |
|
163 } |
|
164 } |
|
165 |
|
166 static enum ArrayBuilder { |
|
167 RANDOM { |
|
168 void build(int[] a, int m) { |
|
169 for (int i = 0; i < a.length; i++) { |
|
170 a[i] = ourRandom.nextInt(); |
|
171 } |
|
172 } |
|
173 }, |
|
174 ASCENDING { |
|
175 void build(int[] a, int m) { |
|
176 for (int i = 0; i < a.length; i++) { |
|
177 a[i] = m + i; |
|
178 } |
|
179 } |
|
180 }, |
|
181 DESCENDING { |
|
182 void build(int[] a, int m) { |
|
183 for (int i = 0; i < a.length; i++) { |
|
184 a[i] = a.length - m - i; |
|
185 } |
|
186 } |
|
187 }, |
|
188 ALL_EQUAL { |
|
189 void build(int[] a, int m) { |
|
190 for (int i = 0; i < a.length; i++) { |
|
191 a[i] = m; |
|
192 } |
|
193 } |
|
194 }, |
|
195 SAW { |
|
196 void build(int[] a, int m) { |
|
197 int incCount = 1; |
|
198 int decCount = a.length; |
|
199 int i = 0; |
|
200 int period = m; |
|
201 m--; |
|
202 while (true) { |
|
203 for (int k = 1; k <= period; k++) { |
|
204 if (i >= a.length) { |
|
205 return; |
|
206 } |
|
207 a[i++] = incCount++; |
|
208 } |
|
209 period += m; |
|
210 |
|
211 for (int k = 1; k <= period; k++) { |
|
212 if (i >= a.length) { |
|
213 return; |
|
214 } |
|
215 a[i++] = decCount--; |
|
216 } |
|
217 period += m; |
|
218 } |
|
219 } |
|
220 }, |
|
221 REPEATED { |
|
222 void build(int[] a, int m) { |
|
223 for (int i = 0; i < a.length; i++) { |
|
224 a[i] = i % m; |
|
225 } |
|
226 } |
|
227 }, |
|
228 DUPLICATED { |
|
229 void build(int[] a, int m) { |
|
230 for (int i = 0; i < a.length; i++) { |
|
231 a[i] = ourRandom.nextInt(m); |
|
232 } |
|
233 } |
|
234 }, |
|
235 ORGAN_PIPES { |
|
236 void build(int[] a, int m) { |
|
237 int middle = a.length / (m + 1); |
|
238 |
|
239 for (int i = 0; i < middle; i++) { |
|
240 a[i] = i; |
|
241 } |
|
242 for (int i = middle; i < a.length; i++) { |
|
243 a[i] = a.length - i - 1; |
|
244 } |
|
245 } |
|
246 }, |
|
247 STAGGER { |
|
248 void build(int[] a, int m) { |
|
249 for (int i = 0; i < a.length; i++) { |
|
250 a[i] = (i * m + i) % a.length; |
|
251 } |
|
252 } |
|
253 }, |
|
254 PLATEAU { |
|
255 void build(int[] a, int m) { |
|
256 for (int i = 0; i < a.length; i++) { |
|
257 a[i] = Math.min(i, m); |
|
258 } |
|
259 } |
|
260 }, |
|
261 SHUFFLE { |
|
262 void build(int[] a, int m) { |
|
263 for (int i = 0; i < a.length; i++) { |
|
264 a[i] = ourRandom.nextBoolean() ? (ourFirst += 2) : (ourSecond += 2); |
|
265 } |
|
266 } |
|
267 }; |
|
268 |
|
269 abstract void build(int[] a, int m); |
|
270 |
|
271 static void reset() { |
|
272 ourRandom = new Random(666); |
|
273 ourFirst = 0; |
|
274 ourSecond = 0; |
|
275 } |
|
276 |
|
277 @Override public String toString() { |
|
278 String name = name(); |
|
279 for (int i = name.length(); i < 12; i++) { |
|
280 name += " "; |
|
281 } |
|
282 return name; |
|
283 } |
|
284 |
|
285 private static int ourFirst; |
|
286 private static int ourSecond; |
|
287 private static Random ourRandom = new Random(666); |
|
288 } |
|
289 |
|
290 static void checkWithCheckSum(Object test, Object golden) { |
|
291 checkSorted(test); |
|
292 checkCheckSum(test, golden); |
|
293 } |
|
294 |
|
295 static void failed(String message) { |
|
296 err.format("***FAILED: %s%%n", message); |
|
297 throw new RuntimeException("Test failed - see log file for details"); |
|
298 } |
|
299 |
|
300 static void failed(int index, String value1, String value2) { |
|
301 failed("Array is not sorted at " + index + "-th position: " + value1 + |
|
302 " and " + value2); |
|
303 } |
|
304 |
|
305 static void checkSorted(Object object) { |
|
306 if (object instanceof int[]) { |
|
307 checkSorted((int[]) object); |
|
308 } else if (object instanceof long[]) { |
|
309 checkSorted((long[]) object); |
|
310 } else if (object instanceof short[]) { |
|
311 checkSorted((short[]) object); |
|
312 } else if (object instanceof byte[]) { |
|
313 checkSorted((byte[]) object); |
|
314 } else if (object instanceof char[]) { |
|
315 checkSorted((char[]) object); |
|
316 } else if (object instanceof float[]) { |
|
317 checkSorted((float[]) object); |
|
318 } else if (object instanceof double[]) { |
|
319 checkSorted((double[]) object); |
|
320 } else { |
|
321 failed("Unknow type of array: " + object + " of class " + |
|
322 object.getClass().getName()); |
|
323 } |
|
324 } |
|
325 |
|
326 static void checkSorted(int[] a) { |
|
327 for (int i = 0; i < a.length - 1; i++) { |
|
328 if (a[i] > a[i + 1]) { |
|
329 failed(i, "" + a[i], "" + a[i + 1]); |
|
330 } |
|
331 } |
|
332 } |
|
333 |
|
334 static void checkSorted(long[] a) { |
|
335 for (int i = 0; i < a.length - 1; i++) { |
|
336 if (a[i] > a[i + 1]) { |
|
337 failed(i, "" + a[i], "" + a[i + 1]); |
|
338 } |
|
339 } |
|
340 } |
|
341 |
|
342 static void checkSorted(short[] a) { |
|
343 for (int i = 0; i < a.length - 1; i++) { |
|
344 if (a[i] > a[i + 1]) { |
|
345 failed(i, "" + a[i], "" + a[i + 1]); |
|
346 } |
|
347 } |
|
348 } |
|
349 |
|
350 static void checkSorted(byte[] a) { |
|
351 for (int i = 0; i < a.length - 1; i++) { |
|
352 if (a[i] > a[i + 1]) { |
|
353 failed(i, "" + a[i], "" + a[i + 1]); |
|
354 } |
|
355 } |
|
356 } |
|
357 |
|
358 static void checkSorted(char[] a) { |
|
359 for (int i = 0; i < a.length - 1; i++) { |
|
360 if (a[i] > a[i + 1]) { |
|
361 failed(i, "" + a[i], "" + a[i + 1]); |
|
362 } |
|
363 } |
|
364 } |
|
365 |
|
366 static void checkSorted(float[] a) { |
|
367 for (int i = 0; i < a.length - 1; i++) { |
|
368 if (a[i] > a[i + 1]) { |
|
369 failed(i, "" + a[i], "" + a[i + 1]); |
|
370 } |
|
371 } |
|
372 } |
|
373 |
|
374 static void checkSorted(double[] a) { |
|
375 for (int i = 0; i < a.length - 1; i++) { |
|
376 if (a[i] > a[i + 1]) { |
|
377 failed(i, "" + a[i], "" + a[i + 1]); |
|
378 } |
|
379 } |
|
380 } |
|
381 |
|
382 static void checkCheckSum(Object test, Object golden) { |
|
383 if (checkSum(test) != checkSum(golden)) { |
|
384 failed("Original and sorted arrays seems not identical"); |
|
385 } |
|
386 } |
|
387 |
|
388 static int checkSum(Object object) { |
|
389 if (object instanceof int[]) { |
|
390 return checkSum((int[]) object); |
|
391 } else if (object instanceof long[]) { |
|
392 return checkSum((long[]) object); |
|
393 } else if (object instanceof short[]) { |
|
394 return checkSum((short[]) object); |
|
395 } else if (object instanceof byte[]) { |
|
396 return checkSum((byte[]) object); |
|
397 } else if (object instanceof char[]) { |
|
398 return checkSum((char[]) object); |
|
399 } else if (object instanceof float[]) { |
|
400 return checkSum((float[]) object); |
|
401 } else if (object instanceof double[]) { |
|
402 return checkSum((double[]) object); |
|
403 } else { |
|
404 failed("Unknow type of array: " + object + " of class " + |
|
405 object.getClass().getName()); |
|
406 return -1; |
|
407 } |
|
408 } |
|
409 |
|
410 static int checkSum(int[] a) { |
|
411 int checkSum = 0; |
|
412 |
|
413 for (int e : a) { |
|
414 checkSum ^= e; // xor |
|
415 } |
|
416 return checkSum; |
|
417 } |
|
418 |
|
419 static int checkSum(long[] a) { |
|
420 long checkSum = 0; |
|
421 |
|
422 for (long e : a) { |
|
423 checkSum ^= e; // xor |
|
424 } |
|
425 return (int) checkSum; |
|
426 } |
|
427 |
|
428 static int checkSum(short[] a) { |
|
429 short checkSum = 0; |
|
430 |
|
431 for (short e : a) { |
|
432 checkSum ^= e; // xor |
|
433 } |
|
434 return (int) checkSum; |
|
435 } |
|
436 |
|
437 static int checkSum(byte[] a) { |
|
438 byte checkSum = 0; |
|
439 |
|
440 for (byte e : a) { |
|
441 checkSum ^= e; // xor |
|
442 } |
|
443 return (int) checkSum; |
|
444 } |
|
445 |
|
446 static int checkSum(char[] a) { |
|
447 char checkSum = 0; |
|
448 |
|
449 for (char e : a) { |
|
450 checkSum ^= e; // xor |
|
451 } |
|
452 return (int) checkSum; |
|
453 } |
|
454 |
|
455 static int checkSum(float[] a) { |
|
456 int checkSum = 0; |
|
457 |
|
458 for (float e : a) { |
|
459 checkSum ^= (int) e; // xor |
|
460 } |
|
461 return checkSum; |
|
462 } |
|
463 |
|
464 static int checkSum(double[] a) { |
|
465 int checkSum = 0; |
|
466 |
|
467 for (double e : a) { |
|
468 checkSum ^= (int) e; // xor |
|
469 } |
|
470 return checkSum; |
|
471 } |
|
472 |
|
473 static void sort(Object object) { |
|
474 if (object instanceof int[]) { |
|
475 Arrays.sort((int[]) object); |
|
476 } else if (object instanceof long[]) { |
|
477 Arrays.sort((long[]) object); |
|
478 } else if (object instanceof short[]) { |
|
479 Arrays.sort((short[]) object); |
|
480 } else if (object instanceof byte[]) { |
|
481 Arrays.sort((byte[]) object); |
|
482 } else if (object instanceof char[]) { |
|
483 Arrays.sort((char[]) object); |
|
484 } else if (object instanceof float[]) { |
|
485 Arrays.sort((float[]) object); |
|
486 } else if (object instanceof double[]) { |
|
487 Arrays.sort((double[]) object); |
|
488 } else { |
|
489 failed("Unknow type of array: " + object + " of class " + |
|
490 object.getClass().getName()); |
|
491 } |
|
492 } |
|
493 } |