1 /*
2 * Copyright (c) 1997, 2018, Oracle and/or its affiliates. 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. Oracle designates this
8 * particular file as subject to the "Classpath" exception as provided
9 * by Oracle in the LICENSE file that accompanied this code.
10 *
11 * This code is distributed in the hope that it will be useful, but WITHOUT
12 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
14 * version 2 for more details (a copy is included in the LICENSE file that
15 * accompanied this code).
16 *
17 * You should have received a copy of the GNU General Public License version
18 * 2 along with this work; if not, write to the Free Software Foundation,
19 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
20 *
21 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
22 * or visit www.oracle.com if you need additional information or have any
57 *
58 * <p>The documentation for the methods contained in this class includes
59 * brief descriptions of the <i>implementations</i>. Such descriptions should
60 * be regarded as <i>implementation notes</i>, rather than parts of the
61 * <i>specification</i>. Implementors should feel free to substitute other
62 * algorithms, so long as the specification itself is adhered to. (For
63 * example, the algorithm used by {@code sort(Object[])} does not have to be
64 * a MergeSort, but it does have to be <i>stable</i>.)
65 *
66 * <p>This class is a member of the
67 * <a href="{@docRoot}/java.base/java/util/package-summary.html#CollectionsFramework">
68 * Java Collections Framework</a>.
69 *
70 * @author Josh Bloch
71 * @author Neal Gafter
72 * @author John Rose
73 * @since 1.2
74 */
75 public class Arrays {
76
77 /**
78 * The minimum array length below which a parallel sorting
79 * algorithm will not further partition the sorting task. Using
80 * smaller sizes typically results in memory contention across
81 * tasks that makes parallel speedups unlikely.
82 */
83 private static final int MIN_ARRAY_SORT_GRAN = 1 << 13;
84
85 // Suppresses default constructor, ensuring non-instantiability.
86 private Arrays() {}
87
88 /**
89 * A comparator that implements the natural ordering of a group of
90 * mutually comparable elements. May be used when a supplied
91 * comparator is null. To simplify code-sharing within underlying
92 * implementations, the compare method only declares type Object
93 * for its second argument.
94 *
95 * Arrays class implementor's note: It is an empirical matter
96 * whether ComparableTimSort offers any performance benefit over
97 * TimSort used with this comparator. If not, you are better off
98 * deleting or bypassing ComparableTimSort. There is currently no
99 * empirical case for separating them for parallel sorting, so all
100 * public Object parallelSort methods use the same comparator
101 * based implementation.
102 */
103 static final class NaturalOrder implements Comparator<Object> {
104 @SuppressWarnings("unchecked")
105 public int compare(Object first, Object second) {
106 return ((Comparable<Object>)first).compareTo(second);
107 }
108 static final NaturalOrder INSTANCE = new NaturalOrder();
109 }
110
111 /**
112 * Checks that {@code fromIndex} and {@code toIndex} are in
113 * the range and throws an exception if they aren't.
114 */
115 static void rangeCheck(int arrayLength, int fromIndex, int toIndex) {
116 if (fromIndex > toIndex) {
117 throw new IllegalArgumentException(
118 "fromIndex(" + fromIndex + ") > toIndex(" + toIndex + ")");
119 }
120 if (fromIndex < 0) {
121 throw new ArrayIndexOutOfBoundsException(fromIndex);
122 }
123 if (toIndex > arrayLength) {
124 throw new ArrayIndexOutOfBoundsException(toIndex);
125 }
126 }
127
128 /*
129 * Sorting methods. Note that all public "sort" methods take the
130 * same form: Performing argument checks if necessary, and then
131 * expanding arguments into those required for the internal
132 * implementation methods residing in other package-private
133 * classes (except for legacyMergeSort, included in this class).
134 */
135
136 /**
137 * Sorts the specified array into ascending numerical order.
138 *
139 * <p>Implementation note: The sorting algorithm is a Dual-Pivot Quicksort
140 * by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithm
141 * offers O(n log(n)) performance on many data sets that cause other
142 * quicksorts to degrade to quadratic performance, and is typically
143 * faster than traditional (one-pivot) Quicksort implementations.
144 *
145 * @param a the array to be sorted
146 */
147 public static void sort(int[] a) {
148 DualPivotQuicksort.sort(a, 0, a.length - 1, null, 0, 0);
149 }
150
151 /**
152 * Sorts the specified range of the array into ascending order. The range
153 * to be sorted extends from the index {@code fromIndex}, inclusive, to
154 * the index {@code toIndex}, exclusive. If {@code fromIndex == toIndex},
155 * the range to be sorted is empty.
156 *
157 * <p>Implementation note: The sorting algorithm is a Dual-Pivot Quicksort
158 * by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithm
159 * offers O(n log(n)) performance on many data sets that cause other
160 * quicksorts to degrade to quadratic performance, and is typically
161 * faster than traditional (one-pivot) Quicksort implementations.
162 *
163 * @param a the array to be sorted
164 * @param fromIndex the index of the first element, inclusive, to be sorted
165 * @param toIndex the index of the last element, exclusive, to be sorted
166 *
167 * @throws IllegalArgumentException if {@code fromIndex > toIndex}
168 * @throws ArrayIndexOutOfBoundsException
169 * if {@code fromIndex < 0} or {@code toIndex > a.length}
170 */
171 public static void sort(int[] a, int fromIndex, int toIndex) {
172 rangeCheck(a.length, fromIndex, toIndex);
173 DualPivotQuicksort.sort(a, fromIndex, toIndex - 1, null, 0, 0);
174 }
175
176 /**
177 * Sorts the specified array into ascending numerical order.
178 *
179 * <p>Implementation note: The sorting algorithm is a Dual-Pivot Quicksort
180 * by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithm
181 * offers O(n log(n)) performance on many data sets that cause other
182 * quicksorts to degrade to quadratic performance, and is typically
183 * faster than traditional (one-pivot) Quicksort implementations.
184 *
185 * @param a the array to be sorted
186 */
187 public static void sort(long[] a) {
188 DualPivotQuicksort.sort(a, 0, a.length - 1, null, 0, 0);
189 }
190
191 /**
192 * Sorts the specified range of the array into ascending order. The range
193 * to be sorted extends from the index {@code fromIndex}, inclusive, to
194 * the index {@code toIndex}, exclusive. If {@code fromIndex == toIndex},
195 * the range to be sorted is empty.
196 *
197 * <p>Implementation note: The sorting algorithm is a Dual-Pivot Quicksort
198 * by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithm
199 * offers O(n log(n)) performance on many data sets that cause other
200 * quicksorts to degrade to quadratic performance, and is typically
201 * faster than traditional (one-pivot) Quicksort implementations.
202 *
203 * @param a the array to be sorted
204 * @param fromIndex the index of the first element, inclusive, to be sorted
205 * @param toIndex the index of the last element, exclusive, to be sorted
206 *
207 * @throws IllegalArgumentException if {@code fromIndex > toIndex}
208 * @throws ArrayIndexOutOfBoundsException
209 * if {@code fromIndex < 0} or {@code toIndex > a.length}
210 */
211 public static void sort(long[] a, int fromIndex, int toIndex) {
212 rangeCheck(a.length, fromIndex, toIndex);
213 DualPivotQuicksort.sort(a, fromIndex, toIndex - 1, null, 0, 0);
214 }
215
216 /**
217 * Sorts the specified array into ascending numerical order.
218 *
219 * <p>Implementation note: The sorting algorithm is a Dual-Pivot Quicksort
220 * by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithm
221 * offers O(n log(n)) performance on many data sets that cause other
222 * quicksorts to degrade to quadratic performance, and is typically
223 * faster than traditional (one-pivot) Quicksort implementations.
224 *
225 * @param a the array to be sorted
226 */
227 public static void sort(short[] a) {
228 DualPivotQuicksort.sort(a, 0, a.length - 1, null, 0, 0);
229 }
230
231 /**
232 * Sorts the specified range of the array into ascending order. The range
233 * to be sorted extends from the index {@code fromIndex}, inclusive, to
234 * the index {@code toIndex}, exclusive. If {@code fromIndex == toIndex},
235 * the range to be sorted is empty.
236 *
237 * <p>Implementation note: The sorting algorithm is a Dual-Pivot Quicksort
238 * by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithm
239 * offers O(n log(n)) performance on many data sets that cause other
240 * quicksorts to degrade to quadratic performance, and is typically
241 * faster than traditional (one-pivot) Quicksort implementations.
242 *
243 * @param a the array to be sorted
244 * @param fromIndex the index of the first element, inclusive, to be sorted
245 * @param toIndex the index of the last element, exclusive, to be sorted
246 *
247 * @throws IllegalArgumentException if {@code fromIndex > toIndex}
248 * @throws ArrayIndexOutOfBoundsException
249 * if {@code fromIndex < 0} or {@code toIndex > a.length}
250 */
251 public static void sort(short[] a, int fromIndex, int toIndex) {
252 rangeCheck(a.length, fromIndex, toIndex);
253 DualPivotQuicksort.sort(a, fromIndex, toIndex - 1, null, 0, 0);
254 }
255
256 /**
257 * Sorts the specified array into ascending numerical order.
258 *
259 * <p>Implementation note: The sorting algorithm is a Dual-Pivot Quicksort
260 * by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithm
261 * offers O(n log(n)) performance on many data sets that cause other
262 * quicksorts to degrade to quadratic performance, and is typically
263 * faster than traditional (one-pivot) Quicksort implementations.
264 *
265 * @param a the array to be sorted
266 */
267 public static void sort(char[] a) {
268 DualPivotQuicksort.sort(a, 0, a.length - 1, null, 0, 0);
269 }
270
271 /**
272 * Sorts the specified range of the array into ascending order. The range
273 * to be sorted extends from the index {@code fromIndex}, inclusive, to
274 * the index {@code toIndex}, exclusive. If {@code fromIndex == toIndex},
275 * the range to be sorted is empty.
276 *
277 * <p>Implementation note: The sorting algorithm is a Dual-Pivot Quicksort
278 * by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithm
279 * offers O(n log(n)) performance on many data sets that cause other
280 * quicksorts to degrade to quadratic performance, and is typically
281 * faster than traditional (one-pivot) Quicksort implementations.
282 *
283 * @param a the array to be sorted
284 * @param fromIndex the index of the first element, inclusive, to be sorted
285 * @param toIndex the index of the last element, exclusive, to be sorted
286 *
287 * @throws IllegalArgumentException if {@code fromIndex > toIndex}
288 * @throws ArrayIndexOutOfBoundsException
289 * if {@code fromIndex < 0} or {@code toIndex > a.length}
290 */
291 public static void sort(char[] a, int fromIndex, int toIndex) {
292 rangeCheck(a.length, fromIndex, toIndex);
293 DualPivotQuicksort.sort(a, fromIndex, toIndex - 1, null, 0, 0);
294 }
295
296 /**
297 * Sorts the specified array into ascending numerical order.
298 *
299 * <p>Implementation note: The sorting algorithm is a Dual-Pivot Quicksort
300 * by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithm
301 * offers O(n log(n)) performance on many data sets that cause other
302 * quicksorts to degrade to quadratic performance, and is typically
303 * faster than traditional (one-pivot) Quicksort implementations.
304 *
305 * @param a the array to be sorted
306 */
307 public static void sort(byte[] a) {
308 DualPivotQuicksort.sort(a, 0, a.length - 1);
309 }
310
311 /**
312 * Sorts the specified range of the array into ascending order. The range
313 * to be sorted extends from the index {@code fromIndex}, inclusive, to
314 * the index {@code toIndex}, exclusive. If {@code fromIndex == toIndex},
315 * the range to be sorted is empty.
316 *
317 * <p>Implementation note: The sorting algorithm is a Dual-Pivot Quicksort
318 * by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithm
319 * offers O(n log(n)) performance on many data sets that cause other
320 * quicksorts to degrade to quadratic performance, and is typically
321 * faster than traditional (one-pivot) Quicksort implementations.
322 *
323 * @param a the array to be sorted
324 * @param fromIndex the index of the first element, inclusive, to be sorted
325 * @param toIndex the index of the last element, exclusive, to be sorted
326 *
327 * @throws IllegalArgumentException if {@code fromIndex > toIndex}
328 * @throws ArrayIndexOutOfBoundsException
329 * if {@code fromIndex < 0} or {@code toIndex > a.length}
330 */
331 public static void sort(byte[] a, int fromIndex, int toIndex) {
332 rangeCheck(a.length, fromIndex, toIndex);
333 DualPivotQuicksort.sort(a, fromIndex, toIndex - 1);
334 }
335
336 /**
337 * Sorts the specified array into ascending numerical order.
338 *
339 * <p>The {@code <} relation does not provide a total order on all float
340 * values: {@code -0.0f == 0.0f} is {@code true} and a {@code Float.NaN}
341 * value compares neither less than, greater than, nor equal to any value,
342 * even itself. This method uses the total order imposed by the method
343 * {@link Float#compareTo}: {@code -0.0f} is treated as less than value
344 * {@code 0.0f} and {@code Float.NaN} is considered greater than any
345 * other value and all {@code Float.NaN} values are considered equal.
346 *
347 * <p>Implementation note: The sorting algorithm is a Dual-Pivot Quicksort
348 * by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithm
349 * offers O(n log(n)) performance on many data sets that cause other
350 * quicksorts to degrade to quadratic performance, and is typically
351 * faster than traditional (one-pivot) Quicksort implementations.
352 *
353 * @param a the array to be sorted
354 */
355 public static void sort(float[] a) {
356 DualPivotQuicksort.sort(a, 0, a.length - 1, null, 0, 0);
357 }
358
359 /**
360 * Sorts the specified range of the array into ascending order. The range
361 * to be sorted extends from the index {@code fromIndex}, inclusive, to
362 * the index {@code toIndex}, exclusive. If {@code fromIndex == toIndex},
363 * the range to be sorted is empty.
364 *
365 * <p>The {@code <} relation does not provide a total order on all float
366 * values: {@code -0.0f == 0.0f} is {@code true} and a {@code Float.NaN}
367 * value compares neither less than, greater than, nor equal to any value,
368 * even itself. This method uses the total order imposed by the method
369 * {@link Float#compareTo}: {@code -0.0f} is treated as less than value
370 * {@code 0.0f} and {@code Float.NaN} is considered greater than any
371 * other value and all {@code Float.NaN} values are considered equal.
372 *
373 * <p>Implementation note: The sorting algorithm is a Dual-Pivot Quicksort
374 * by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithm
375 * offers O(n log(n)) performance on many data sets that cause other
376 * quicksorts to degrade to quadratic performance, and is typically
377 * faster than traditional (one-pivot) Quicksort implementations.
378 *
379 * @param a the array to be sorted
380 * @param fromIndex the index of the first element, inclusive, to be sorted
381 * @param toIndex the index of the last element, exclusive, to be sorted
382 *
383 * @throws IllegalArgumentException if {@code fromIndex > toIndex}
384 * @throws ArrayIndexOutOfBoundsException
385 * if {@code fromIndex < 0} or {@code toIndex > a.length}
386 */
387 public static void sort(float[] a, int fromIndex, int toIndex) {
388 rangeCheck(a.length, fromIndex, toIndex);
389 DualPivotQuicksort.sort(a, fromIndex, toIndex - 1, null, 0, 0);
390 }
391
392 /**
393 * Sorts the specified array into ascending numerical order.
394 *
395 * <p>The {@code <} relation does not provide a total order on all double
396 * values: {@code -0.0d == 0.0d} is {@code true} and a {@code Double.NaN}
397 * value compares neither less than, greater than, nor equal to any value,
398 * even itself. This method uses the total order imposed by the method
399 * {@link Double#compareTo}: {@code -0.0d} is treated as less than value
400 * {@code 0.0d} and {@code Double.NaN} is considered greater than any
401 * other value and all {@code Double.NaN} values are considered equal.
402 *
403 * <p>Implementation note: The sorting algorithm is a Dual-Pivot Quicksort
404 * by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithm
405 * offers O(n log(n)) performance on many data sets that cause other
406 * quicksorts to degrade to quadratic performance, and is typically
407 * faster than traditional (one-pivot) Quicksort implementations.
408 *
409 * @param a the array to be sorted
410 */
411 public static void sort(double[] a) {
412 DualPivotQuicksort.sort(a, 0, a.length - 1, null, 0, 0);
413 }
414
415 /**
416 * Sorts the specified range of the array into ascending order. The range
417 * to be sorted extends from the index {@code fromIndex}, inclusive, to
418 * the index {@code toIndex}, exclusive. If {@code fromIndex == toIndex},
419 * the range to be sorted is empty.
420 *
421 * <p>The {@code <} relation does not provide a total order on all double
422 * values: {@code -0.0d == 0.0d} is {@code true} and a {@code Double.NaN}
423 * value compares neither less than, greater than, nor equal to any value,
424 * even itself. This method uses the total order imposed by the method
425 * {@link Double#compareTo}: {@code -0.0d} is treated as less than value
426 * {@code 0.0d} and {@code Double.NaN} is considered greater than any
427 * other value and all {@code Double.NaN} values are considered equal.
428 *
429 * <p>Implementation note: The sorting algorithm is a Dual-Pivot Quicksort
430 * by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithm
431 * offers O(n log(n)) performance on many data sets that cause other
432 * quicksorts to degrade to quadratic performance, and is typically
433 * faster than traditional (one-pivot) Quicksort implementations.
434 *
435 * @param a the array to be sorted
436 * @param fromIndex the index of the first element, inclusive, to be sorted
437 * @param toIndex the index of the last element, exclusive, to be sorted
438 *
439 * @throws IllegalArgumentException if {@code fromIndex > toIndex}
440 * @throws ArrayIndexOutOfBoundsException
441 * if {@code fromIndex < 0} or {@code toIndex > a.length}
442 */
443 public static void sort(double[] a, int fromIndex, int toIndex) {
444 rangeCheck(a.length, fromIndex, toIndex);
445 DualPivotQuicksort.sort(a, fromIndex, toIndex - 1, null, 0, 0);
446 }
447
448 /**
449 * Sorts the specified array into ascending numerical order.
450 *
451 * @implNote The sorting algorithm is a parallel sort-merge that breaks the
452 * array into sub-arrays that are themselves sorted and then merged. When
453 * the sub-array length reaches a minimum granularity, the sub-array is
454 * sorted using the appropriate {@link Arrays#sort(byte[]) Arrays.sort}
455 * method. If the length of the specified array is less than the minimum
456 * granularity, then it is sorted using the appropriate {@link
457 * Arrays#sort(byte[]) Arrays.sort} method. The algorithm requires a
458 * working space no greater than the size of the original array. The
459 * {@link ForkJoinPool#commonPool() ForkJoin common pool} is used to
460 * execute any parallel tasks.
461 *
462 * @param a the array to be sorted
463 *
464 * @since 1.8
465 */
466 public static void parallelSort(byte[] a) {
467 int n = a.length, p, g;
468 if (n <= MIN_ARRAY_SORT_GRAN ||
469 (p = ForkJoinPool.getCommonPoolParallelism()) == 1)
470 DualPivotQuicksort.sort(a, 0, n - 1);
471 else
472 new ArraysParallelSortHelpers.FJByte.Sorter
473 (null, a, new byte[n], 0, n, 0,
474 ((g = n / (p << 2)) <= MIN_ARRAY_SORT_GRAN) ?
475 MIN_ARRAY_SORT_GRAN : g).invoke();
476 }
477
478 /**
479 * Sorts the specified range of the array into ascending numerical order.
480 * The range to be sorted extends from the index {@code fromIndex},
481 * inclusive, to the index {@code toIndex}, exclusive. If
482 * {@code fromIndex == toIndex}, the range to be sorted is empty.
483 *
484 * @implNote The sorting algorithm is a parallel sort-merge that breaks the
485 * array into sub-arrays that are themselves sorted and then merged. When
486 * the sub-array length reaches a minimum granularity, the sub-array is
487 * sorted using the appropriate {@link Arrays#sort(byte[]) Arrays.sort}
488 * method. If the length of the specified array is less than the minimum
489 * granularity, then it is sorted using the appropriate {@link
490 * Arrays#sort(byte[]) Arrays.sort} method. The algorithm requires a working
491 * space no greater than the size of the specified range of the original
492 * array. The {@link ForkJoinPool#commonPool() ForkJoin common pool} is
493 * used to execute any parallel tasks.
494 *
495 * @param a the array to be sorted
496 * @param fromIndex the index of the first element, inclusive, to be sorted
497 * @param toIndex the index of the last element, exclusive, to be sorted
498 *
499 * @throws IllegalArgumentException if {@code fromIndex > toIndex}
500 * @throws ArrayIndexOutOfBoundsException
501 * if {@code fromIndex < 0} or {@code toIndex > a.length}
502 *
503 * @since 1.8
504 */
505 public static void parallelSort(byte[] a, int fromIndex, int toIndex) {
506 rangeCheck(a.length, fromIndex, toIndex);
507 int n = toIndex - fromIndex, p, g;
508 if (n <= MIN_ARRAY_SORT_GRAN ||
509 (p = ForkJoinPool.getCommonPoolParallelism()) == 1)
510 DualPivotQuicksort.sort(a, fromIndex, toIndex - 1);
511 else
512 new ArraysParallelSortHelpers.FJByte.Sorter
513 (null, a, new byte[n], fromIndex, n, 0,
514 ((g = n / (p << 2)) <= MIN_ARRAY_SORT_GRAN) ?
515 MIN_ARRAY_SORT_GRAN : g).invoke();
516 }
517
518 /**
519 * Sorts the specified array into ascending numerical order.
520 *
521 * @implNote The sorting algorithm is a parallel sort-merge that breaks the
522 * array into sub-arrays that are themselves sorted and then merged. When
523 * the sub-array length reaches a minimum granularity, the sub-array is
524 * sorted using the appropriate {@link Arrays#sort(char[]) Arrays.sort}
525 * method. If the length of the specified array is less than the minimum
526 * granularity, then it is sorted using the appropriate {@link
527 * Arrays#sort(char[]) Arrays.sort} method. The algorithm requires a
528 * working space no greater than the size of the original array. The
529 * {@link ForkJoinPool#commonPool() ForkJoin common pool} is used to
530 * execute any parallel tasks.
531 *
532 * @param a the array to be sorted
533 *
534 * @since 1.8
535 */
536 public static void parallelSort(char[] a) {
537 int n = a.length, p, g;
538 if (n <= MIN_ARRAY_SORT_GRAN ||
539 (p = ForkJoinPool.getCommonPoolParallelism()) == 1)
540 DualPivotQuicksort.sort(a, 0, n - 1, null, 0, 0);
541 else
542 new ArraysParallelSortHelpers.FJChar.Sorter
543 (null, a, new char[n], 0, n, 0,
544 ((g = n / (p << 2)) <= MIN_ARRAY_SORT_GRAN) ?
545 MIN_ARRAY_SORT_GRAN : g).invoke();
546 }
547
548 /**
549 * Sorts the specified range of the array into ascending numerical order.
550 * The range to be sorted extends from the index {@code fromIndex},
551 * inclusive, to the index {@code toIndex}, exclusive. If
552 * {@code fromIndex == toIndex}, the range to be sorted is empty.
553 *
554 @implNote The sorting algorithm is a parallel sort-merge that breaks the
555 * array into sub-arrays that are themselves sorted and then merged. When
556 * the sub-array length reaches a minimum granularity, the sub-array is
557 * sorted using the appropriate {@link Arrays#sort(char[]) Arrays.sort}
558 * method. If the length of the specified array is less than the minimum
559 * granularity, then it is sorted using the appropriate {@link
560 * Arrays#sort(char[]) Arrays.sort} method. The algorithm requires a working
561 * space no greater than the size of the specified range of the original
562 * array. The {@link ForkJoinPool#commonPool() ForkJoin common pool} is
563 * used to execute any parallel tasks.
564 *
565 * @param a the array to be sorted
566 * @param fromIndex the index of the first element, inclusive, to be sorted
567 * @param toIndex the index of the last element, exclusive, to be sorted
568 *
569 * @throws IllegalArgumentException if {@code fromIndex > toIndex}
570 * @throws ArrayIndexOutOfBoundsException
571 * if {@code fromIndex < 0} or {@code toIndex > a.length}
572 *
573 * @since 1.8
574 */
575 public static void parallelSort(char[] a, int fromIndex, int toIndex) {
576 rangeCheck(a.length, fromIndex, toIndex);
577 int n = toIndex - fromIndex, p, g;
578 if (n <= MIN_ARRAY_SORT_GRAN ||
579 (p = ForkJoinPool.getCommonPoolParallelism()) == 1)
580 DualPivotQuicksort.sort(a, fromIndex, toIndex - 1, null, 0, 0);
581 else
582 new ArraysParallelSortHelpers.FJChar.Sorter
583 (null, a, new char[n], fromIndex, n, 0,
584 ((g = n / (p << 2)) <= MIN_ARRAY_SORT_GRAN) ?
585 MIN_ARRAY_SORT_GRAN : g).invoke();
586 }
587
588 /**
589 * Sorts the specified array into ascending numerical order.
590 *
591 * @implNote The sorting algorithm is a parallel sort-merge that breaks the
592 * array into sub-arrays that are themselves sorted and then merged. When
593 * the sub-array length reaches a minimum granularity, the sub-array is
594 * sorted using the appropriate {@link Arrays#sort(short[]) Arrays.sort}
595 * method. If the length of the specified array is less than the minimum
596 * granularity, then it is sorted using the appropriate {@link
597 * Arrays#sort(short[]) Arrays.sort} method. The algorithm requires a
598 * working space no greater than the size of the original array. The
599 * {@link ForkJoinPool#commonPool() ForkJoin common pool} is used to
600 * execute any parallel tasks.
601 *
602 * @param a the array to be sorted
603 *
604 * @since 1.8
605 */
606 public static void parallelSort(short[] a) {
607 int n = a.length, p, g;
608 if (n <= MIN_ARRAY_SORT_GRAN ||
609 (p = ForkJoinPool.getCommonPoolParallelism()) == 1)
610 DualPivotQuicksort.sort(a, 0, n - 1, null, 0, 0);
611 else
612 new ArraysParallelSortHelpers.FJShort.Sorter
613 (null, a, new short[n], 0, n, 0,
614 ((g = n / (p << 2)) <= MIN_ARRAY_SORT_GRAN) ?
615 MIN_ARRAY_SORT_GRAN : g).invoke();
616 }
617
618 /**
619 * Sorts the specified range of the array into ascending numerical order.
620 * The range to be sorted extends from the index {@code fromIndex},
621 * inclusive, to the index {@code toIndex}, exclusive. If
622 * {@code fromIndex == toIndex}, the range to be sorted is empty.
623 *
624 * @implNote The sorting algorithm is a parallel sort-merge that breaks the
625 * array into sub-arrays that are themselves sorted and then merged. When
626 * the sub-array length reaches a minimum granularity, the sub-array is
627 * sorted using the appropriate {@link Arrays#sort(short[]) Arrays.sort}
628 * method. If the length of the specified array is less than the minimum
629 * granularity, then it is sorted using the appropriate {@link
630 * Arrays#sort(short[]) Arrays.sort} method. The algorithm requires a working
631 * space no greater than the size of the specified range of the original
632 * array. The {@link ForkJoinPool#commonPool() ForkJoin common pool} is
633 * used to execute any parallel tasks.
634 *
635 * @param a the array to be sorted
636 * @param fromIndex the index of the first element, inclusive, to be sorted
637 * @param toIndex the index of the last element, exclusive, to be sorted
638 *
639 * @throws IllegalArgumentException if {@code fromIndex > toIndex}
640 * @throws ArrayIndexOutOfBoundsException
641 * if {@code fromIndex < 0} or {@code toIndex > a.length}
642 *
643 * @since 1.8
644 */
645 public static void parallelSort(short[] a, int fromIndex, int toIndex) {
646 rangeCheck(a.length, fromIndex, toIndex);
647 int n = toIndex - fromIndex, p, g;
648 if (n <= MIN_ARRAY_SORT_GRAN ||
649 (p = ForkJoinPool.getCommonPoolParallelism()) == 1)
650 DualPivotQuicksort.sort(a, fromIndex, toIndex - 1, null, 0, 0);
651 else
652 new ArraysParallelSortHelpers.FJShort.Sorter
653 (null, a, new short[n], fromIndex, n, 0,
654 ((g = n / (p << 2)) <= MIN_ARRAY_SORT_GRAN) ?
655 MIN_ARRAY_SORT_GRAN : g).invoke();
656 }
657
658 /**
659 * Sorts the specified array into ascending numerical order.
660 *
661 * @implNote The sorting algorithm is a parallel sort-merge that breaks the
662 * array into sub-arrays that are themselves sorted and then merged. When
663 * the sub-array length reaches a minimum granularity, the sub-array is
664 * sorted using the appropriate {@link Arrays#sort(int[]) Arrays.sort}
665 * method. If the length of the specified array is less than the minimum
666 * granularity, then it is sorted using the appropriate {@link
667 * Arrays#sort(int[]) Arrays.sort} method. The algorithm requires a
668 * working space no greater than the size of the original array. The
669 * {@link ForkJoinPool#commonPool() ForkJoin common pool} is used to
670 * execute any parallel tasks.
671 *
672 * @param a the array to be sorted
673 *
674 * @since 1.8
675 */
676 public static void parallelSort(int[] a) {
677 int n = a.length, p, g;
678 if (n <= MIN_ARRAY_SORT_GRAN ||
679 (p = ForkJoinPool.getCommonPoolParallelism()) == 1)
680 DualPivotQuicksort.sort(a, 0, n - 1, null, 0, 0);
681 else
682 new ArraysParallelSortHelpers.FJInt.Sorter
683 (null, a, new int[n], 0, n, 0,
684 ((g = n / (p << 2)) <= MIN_ARRAY_SORT_GRAN) ?
685 MIN_ARRAY_SORT_GRAN : g).invoke();
686 }
687
688 /**
689 * Sorts the specified range of the array into ascending numerical order.
690 * The range to be sorted extends from the index {@code fromIndex},
691 * inclusive, to the index {@code toIndex}, exclusive. If
692 * {@code fromIndex == toIndex}, the range to be sorted is empty.
693 *
694 * @implNote The sorting algorithm is a parallel sort-merge that breaks the
695 * array into sub-arrays that are themselves sorted and then merged. When
696 * the sub-array length reaches a minimum granularity, the sub-array is
697 * sorted using the appropriate {@link Arrays#sort(int[]) Arrays.sort}
698 * method. If the length of the specified array is less than the minimum
699 * granularity, then it is sorted using the appropriate {@link
700 * Arrays#sort(int[]) Arrays.sort} method. The algorithm requires a working
701 * space no greater than the size of the specified range of the original
702 * array. The {@link ForkJoinPool#commonPool() ForkJoin common pool} is
703 * used to execute any parallel tasks.
704 *
705 * @param a the array to be sorted
706 * @param fromIndex the index of the first element, inclusive, to be sorted
707 * @param toIndex the index of the last element, exclusive, to be sorted
708 *
709 * @throws IllegalArgumentException if {@code fromIndex > toIndex}
710 * @throws ArrayIndexOutOfBoundsException
711 * if {@code fromIndex < 0} or {@code toIndex > a.length}
712 *
713 * @since 1.8
714 */
715 public static void parallelSort(int[] a, int fromIndex, int toIndex) {
716 rangeCheck(a.length, fromIndex, toIndex);
717 int n = toIndex - fromIndex, p, g;
718 if (n <= MIN_ARRAY_SORT_GRAN ||
719 (p = ForkJoinPool.getCommonPoolParallelism()) == 1)
720 DualPivotQuicksort.sort(a, fromIndex, toIndex - 1, null, 0, 0);
721 else
722 new ArraysParallelSortHelpers.FJInt.Sorter
723 (null, a, new int[n], fromIndex, n, 0,
724 ((g = n / (p << 2)) <= MIN_ARRAY_SORT_GRAN) ?
725 MIN_ARRAY_SORT_GRAN : g).invoke();
726 }
727
728 /**
729 * Sorts the specified array into ascending numerical order.
730 *
731 * @implNote The sorting algorithm is a parallel sort-merge that breaks the
732 * array into sub-arrays that are themselves sorted and then merged. When
733 * the sub-array length reaches a minimum granularity, the sub-array is
734 * sorted using the appropriate {@link Arrays#sort(long[]) Arrays.sort}
735 * method. If the length of the specified array is less than the minimum
736 * granularity, then it is sorted using the appropriate {@link
737 * Arrays#sort(long[]) Arrays.sort} method. The algorithm requires a
738 * working space no greater than the size of the original array. The
739 * {@link ForkJoinPool#commonPool() ForkJoin common pool} is used to
740 * execute any parallel tasks.
741 *
742 * @param a the array to be sorted
743 *
744 * @since 1.8
745 */
746 public static void parallelSort(long[] a) {
747 int n = a.length, p, g;
748 if (n <= MIN_ARRAY_SORT_GRAN ||
749 (p = ForkJoinPool.getCommonPoolParallelism()) == 1)
750 DualPivotQuicksort.sort(a, 0, n - 1, null, 0, 0);
751 else
752 new ArraysParallelSortHelpers.FJLong.Sorter
753 (null, a, new long[n], 0, n, 0,
754 ((g = n / (p << 2)) <= MIN_ARRAY_SORT_GRAN) ?
755 MIN_ARRAY_SORT_GRAN : g).invoke();
756 }
757
758 /**
759 * Sorts the specified range of the array into ascending numerical order.
760 * The range to be sorted extends from the index {@code fromIndex},
761 * inclusive, to the index {@code toIndex}, exclusive. If
762 * {@code fromIndex == toIndex}, the range to be sorted is empty.
763 *
764 * @implNote The sorting algorithm is a parallel sort-merge that breaks the
765 * array into sub-arrays that are themselves sorted and then merged. When
766 * the sub-array length reaches a minimum granularity, the sub-array is
767 * sorted using the appropriate {@link Arrays#sort(long[]) Arrays.sort}
768 * method. If the length of the specified array is less than the minimum
769 * granularity, then it is sorted using the appropriate {@link
770 * Arrays#sort(long[]) Arrays.sort} method. The algorithm requires a working
771 * space no greater than the size of the specified range of the original
772 * array. The {@link ForkJoinPool#commonPool() ForkJoin common pool} is
773 * used to execute any parallel tasks.
774 *
775 * @param a the array to be sorted
776 * @param fromIndex the index of the first element, inclusive, to be sorted
777 * @param toIndex the index of the last element, exclusive, to be sorted
778 *
779 * @throws IllegalArgumentException if {@code fromIndex > toIndex}
780 * @throws ArrayIndexOutOfBoundsException
781 * if {@code fromIndex < 0} or {@code toIndex > a.length}
782 *
783 * @since 1.8
784 */
785 public static void parallelSort(long[] a, int fromIndex, int toIndex) {
786 rangeCheck(a.length, fromIndex, toIndex);
787 int n = toIndex - fromIndex, p, g;
788 if (n <= MIN_ARRAY_SORT_GRAN ||
789 (p = ForkJoinPool.getCommonPoolParallelism()) == 1)
790 DualPivotQuicksort.sort(a, fromIndex, toIndex - 1, null, 0, 0);
791 else
792 new ArraysParallelSortHelpers.FJLong.Sorter
793 (null, a, new long[n], fromIndex, n, 0,
794 ((g = n / (p << 2)) <= MIN_ARRAY_SORT_GRAN) ?
795 MIN_ARRAY_SORT_GRAN : g).invoke();
796 }
797
798 /**
799 * Sorts the specified array into ascending numerical order.
800 *
801 * <p>The {@code <} relation does not provide a total order on all float
802 * values: {@code -0.0f == 0.0f} is {@code true} and a {@code Float.NaN}
803 * value compares neither less than, greater than, nor equal to any value,
804 * even itself. This method uses the total order imposed by the method
805 * {@link Float#compareTo}: {@code -0.0f} is treated as less than value
806 * {@code 0.0f} and {@code Float.NaN} is considered greater than any
807 * other value and all {@code Float.NaN} values are considered equal.
808 *
809 * @implNote The sorting algorithm is a parallel sort-merge that breaks the
810 * array into sub-arrays that are themselves sorted and then merged. When
811 * the sub-array length reaches a minimum granularity, the sub-array is
812 * sorted using the appropriate {@link Arrays#sort(float[]) Arrays.sort}
813 * method. If the length of the specified array is less than the minimum
814 * granularity, then it is sorted using the appropriate {@link
815 * Arrays#sort(float[]) Arrays.sort} method. The algorithm requires a
816 * working space no greater than the size of the original array. The
817 * {@link ForkJoinPool#commonPool() ForkJoin common pool} is used to
818 * execute any parallel tasks.
819 *
820 * @param a the array to be sorted
821 *
822 * @since 1.8
823 */
824 public static void parallelSort(float[] a) {
825 int n = a.length, p, g;
826 if (n <= MIN_ARRAY_SORT_GRAN ||
827 (p = ForkJoinPool.getCommonPoolParallelism()) == 1)
828 DualPivotQuicksort.sort(a, 0, n - 1, null, 0, 0);
829 else
830 new ArraysParallelSortHelpers.FJFloat.Sorter
831 (null, a, new float[n], 0, n, 0,
832 ((g = n / (p << 2)) <= MIN_ARRAY_SORT_GRAN) ?
833 MIN_ARRAY_SORT_GRAN : g).invoke();
834 }
835
836 /**
837 * Sorts the specified range of the array into ascending numerical order.
838 * The range to be sorted extends from the index {@code fromIndex},
839 * inclusive, to the index {@code toIndex}, exclusive. If
840 * {@code fromIndex == toIndex}, the range to be sorted is empty.
841 *
842 * <p>The {@code <} relation does not provide a total order on all float
843 * values: {@code -0.0f == 0.0f} is {@code true} and a {@code Float.NaN}
844 * value compares neither less than, greater than, nor equal to any value,
845 * even itself. This method uses the total order imposed by the method
846 * {@link Float#compareTo}: {@code -0.0f} is treated as less than value
847 * {@code 0.0f} and {@code Float.NaN} is considered greater than any
848 * other value and all {@code Float.NaN} values are considered equal.
849 *
850 * @implNote The sorting algorithm is a parallel sort-merge that breaks the
851 * array into sub-arrays that are themselves sorted and then merged. When
852 * the sub-array length reaches a minimum granularity, the sub-array is
853 * sorted using the appropriate {@link Arrays#sort(float[]) Arrays.sort}
854 * method. If the length of the specified array is less than the minimum
855 * granularity, then it is sorted using the appropriate {@link
856 * Arrays#sort(float[]) Arrays.sort} method. The algorithm requires a working
857 * space no greater than the size of the specified range of the original
858 * array. The {@link ForkJoinPool#commonPool() ForkJoin common pool} is
859 * used to execute any parallel tasks.
860 *
861 * @param a the array to be sorted
862 * @param fromIndex the index of the first element, inclusive, to be sorted
863 * @param toIndex the index of the last element, exclusive, to be sorted
864 *
865 * @throws IllegalArgumentException if {@code fromIndex > toIndex}
866 * @throws ArrayIndexOutOfBoundsException
867 * if {@code fromIndex < 0} or {@code toIndex > a.length}
868 *
869 * @since 1.8
870 */
871 public static void parallelSort(float[] a, int fromIndex, int toIndex) {
872 rangeCheck(a.length, fromIndex, toIndex);
873 int n = toIndex - fromIndex, p, g;
874 if (n <= MIN_ARRAY_SORT_GRAN ||
875 (p = ForkJoinPool.getCommonPoolParallelism()) == 1)
876 DualPivotQuicksort.sort(a, fromIndex, toIndex - 1, null, 0, 0);
877 else
878 new ArraysParallelSortHelpers.FJFloat.Sorter
879 (null, a, new float[n], fromIndex, n, 0,
880 ((g = n / (p << 2)) <= MIN_ARRAY_SORT_GRAN) ?
881 MIN_ARRAY_SORT_GRAN : g).invoke();
882 }
883
884 /**
885 * Sorts the specified array into ascending numerical order.
886 *
887 * <p>The {@code <} relation does not provide a total order on all double
888 * values: {@code -0.0d == 0.0d} is {@code true} and a {@code Double.NaN}
889 * value compares neither less than, greater than, nor equal to any value,
890 * even itself. This method uses the total order imposed by the method
891 * {@link Double#compareTo}: {@code -0.0d} is treated as less than value
892 * {@code 0.0d} and {@code Double.NaN} is considered greater than any
893 * other value and all {@code Double.NaN} values are considered equal.
894 *
895 * @implNote The sorting algorithm is a parallel sort-merge that breaks the
896 * array into sub-arrays that are themselves sorted and then merged. When
897 * the sub-array length reaches a minimum granularity, the sub-array is
898 * sorted using the appropriate {@link Arrays#sort(double[]) Arrays.sort}
899 * method. If the length of the specified array is less than the minimum
900 * granularity, then it is sorted using the appropriate {@link
901 * Arrays#sort(double[]) Arrays.sort} method. The algorithm requires a
902 * working space no greater than the size of the original array. The
903 * {@link ForkJoinPool#commonPool() ForkJoin common pool} is used to
904 * execute any parallel tasks.
905 *
906 * @param a the array to be sorted
907 *
908 * @since 1.8
909 */
910 public static void parallelSort(double[] a) {
911 int n = a.length, p, g;
912 if (n <= MIN_ARRAY_SORT_GRAN ||
913 (p = ForkJoinPool.getCommonPoolParallelism()) == 1)
914 DualPivotQuicksort.sort(a, 0, n - 1, null, 0, 0);
915 else
916 new ArraysParallelSortHelpers.FJDouble.Sorter
917 (null, a, new double[n], 0, n, 0,
918 ((g = n / (p << 2)) <= MIN_ARRAY_SORT_GRAN) ?
919 MIN_ARRAY_SORT_GRAN : g).invoke();
920 }
921
922 /**
923 * Sorts the specified range of the array into ascending numerical order.
924 * The range to be sorted extends from the index {@code fromIndex},
925 * inclusive, to the index {@code toIndex}, exclusive. If
926 * {@code fromIndex == toIndex}, the range to be sorted is empty.
927 *
928 * <p>The {@code <} relation does not provide a total order on all double
929 * values: {@code -0.0d == 0.0d} is {@code true} and a {@code Double.NaN}
930 * value compares neither less than, greater than, nor equal to any value,
931 * even itself. This method uses the total order imposed by the method
932 * {@link Double#compareTo}: {@code -0.0d} is treated as less than value
933 * {@code 0.0d} and {@code Double.NaN} is considered greater than any
934 * other value and all {@code Double.NaN} values are considered equal.
935 *
936 * @implNote The sorting algorithm is a parallel sort-merge that breaks the
937 * array into sub-arrays that are themselves sorted and then merged. When
938 * the sub-array length reaches a minimum granularity, the sub-array is
939 * sorted using the appropriate {@link Arrays#sort(double[]) Arrays.sort}
940 * method. If the length of the specified array is less than the minimum
941 * granularity, then it is sorted using the appropriate {@link
942 * Arrays#sort(double[]) Arrays.sort} method. The algorithm requires a working
943 * space no greater than the size of the specified range of the original
944 * array. The {@link ForkJoinPool#commonPool() ForkJoin common pool} is
945 * used to execute any parallel tasks.
946 *
947 * @param a the array to be sorted
948 * @param fromIndex the index of the first element, inclusive, to be sorted
949 * @param toIndex the index of the last element, exclusive, to be sorted
950 *
951 * @throws IllegalArgumentException if {@code fromIndex > toIndex}
952 * @throws ArrayIndexOutOfBoundsException
953 * if {@code fromIndex < 0} or {@code toIndex > a.length}
954 *
955 * @since 1.8
956 */
957 public static void parallelSort(double[] a, int fromIndex, int toIndex) {
958 rangeCheck(a.length, fromIndex, toIndex);
959 int n = toIndex - fromIndex, p, g;
960 if (n <= MIN_ARRAY_SORT_GRAN ||
961 (p = ForkJoinPool.getCommonPoolParallelism()) == 1)
962 DualPivotQuicksort.sort(a, fromIndex, toIndex - 1, null, 0, 0);
963 else
964 new ArraysParallelSortHelpers.FJDouble.Sorter
965 (null, a, new double[n], fromIndex, n, 0,
966 ((g = n / (p << 2)) <= MIN_ARRAY_SORT_GRAN) ?
967 MIN_ARRAY_SORT_GRAN : g).invoke();
968 }
969
970 /**
971 * Sorts the specified array of objects into ascending order, according
972 * to the {@linkplain Comparable natural ordering} of its elements.
973 * All elements in the array must implement the {@link Comparable}
974 * interface. Furthermore, all elements in the array must be
975 * <i>mutually comparable</i> (that is, {@code e1.compareTo(e2)} must
976 * not throw a {@code ClassCastException} for any elements {@code e1}
977 * and {@code e2} in the array).
978 *
979 * <p>This sort is guaranteed to be <i>stable</i>: equal elements will
980 * not be reordered as a result of the sort.
981 *
982 * @implNote The sorting algorithm is a parallel sort-merge that breaks the
983 * array into sub-arrays that are themselves sorted and then merged. When
984 * the sub-array length reaches a minimum granularity, the sub-array is
985 * sorted using the appropriate {@link Arrays#sort(Object[]) Arrays.sort}
986 * method. If the length of the specified array is less than the minimum
987 * granularity, then it is sorted using the appropriate {@link
988 * Arrays#sort(Object[]) Arrays.sort} method. The algorithm requires a
989 * working space no greater than the size of the original array. The
990 * {@link ForkJoinPool#commonPool() ForkJoin common pool} is used to
2985
2986 int aLength = aToIndex - aFromIndex;
2987 int bLength = bToIndex - bFromIndex;
2988 if (aLength != bLength)
2989 return false;
2990
2991 return ArraysSupport.mismatch(a, aFromIndex,
2992 b, bFromIndex,
2993 aLength) < 0;
2994 }
2995
2996 /**
2997 * Returns {@code true} if the two specified arrays of doubles are
2998 * <i>equal</i> to one another. Two arrays are considered equal if both
2999 * arrays contain the same number of elements, and all corresponding pairs
3000 * of elements in the two arrays are equal. In other words, two arrays
3001 * are equal if they contain the same elements in the same order. Also,
3002 * two array references are considered equal if both are {@code null}.
3003 *
3004 * Two doubles {@code d1} and {@code d2} are considered equal if:
3005 * <pre> {@code new Double(d1).equals(new Double(d2))}</pre>
3006 * (Unlike the {@code ==} operator, this method considers
3007 * {@code NaN} equals to itself, and 0.0d unequal to -0.0d.)
3008 *
3009 * @param a one array to be tested for equality
3010 * @param a2 the other array to be tested for equality
3011 * @return {@code true} if the two arrays are equal
3012 * @see Double#equals(Object)
3013 */
3014 public static boolean equals(double[] a, double[] a2) {
3015 if (a==a2)
3016 return true;
3017 if (a==null || a2==null)
3018 return false;
3019
3020 int length = a.length;
3021 if (a2.length != length)
3022 return false;
3023
3024 return ArraysSupport.mismatch(a, a2, length) < 0;
3025 }
3026
3027 /**
3028 * Returns true if the two specified arrays of doubles, over the specified
3029 * ranges, are <i>equal</i> to one another.
3030 *
3031 * <p>Two arrays are considered equal if the number of elements covered by
3032 * each range is the same, and all corresponding pairs of elements over the
3033 * specified ranges in the two arrays are equal. In other words, two arrays
3034 * are equal if they contain, over the specified ranges, the same elements
3035 * in the same order.
3036 *
3037 * <p>Two doubles {@code d1} and {@code d2} are considered equal if:
3038 * <pre> {@code new Double(d1).equals(new Double(d2))}</pre>
3039 * (Unlike the {@code ==} operator, this method considers
3040 * {@code NaN} equals to itself, and 0.0d unequal to -0.0d.)
3041 *
3042 * @param a the first array to be tested for equality
3043 * @param aFromIndex the index (inclusive) of the first element in the
3044 * first array to be tested
3045 * @param aToIndex the index (exclusive) of the last element in the
3046 * first array to be tested
3047 * @param b the second array to be tested fro equality
3048 * @param bFromIndex the index (inclusive) of the first element in the
3049 * second array to be tested
3050 * @param bToIndex the index (exclusive) of the last element in the
3051 * second array to be tested
3052 * @return {@code true} if the two arrays, over the specified ranges, are
3053 * equal
3054 * @throws IllegalArgumentException
3055 * if {@code aFromIndex > aToIndex} or
3056 * if {@code bFromIndex > bToIndex}
3057 * @throws ArrayIndexOutOfBoundsException
3058 * if {@code aFromIndex < 0 or aToIndex > a.length} or
3068 rangeCheck(b.length, bFromIndex, bToIndex);
3069
3070 int aLength = aToIndex - aFromIndex;
3071 int bLength = bToIndex - bFromIndex;
3072 if (aLength != bLength)
3073 return false;
3074
3075 return ArraysSupport.mismatch(a, aFromIndex,
3076 b, bFromIndex, aLength) < 0;
3077 }
3078
3079 /**
3080 * Returns {@code true} if the two specified arrays of floats are
3081 * <i>equal</i> to one another. Two arrays are considered equal if both
3082 * arrays contain the same number of elements, and all corresponding pairs
3083 * of elements in the two arrays are equal. In other words, two arrays
3084 * are equal if they contain the same elements in the same order. Also,
3085 * two array references are considered equal if both are {@code null}.
3086 *
3087 * Two floats {@code f1} and {@code f2} are considered equal if:
3088 * <pre> {@code new Float(f1).equals(new Float(f2))}</pre>
3089 * (Unlike the {@code ==} operator, this method considers
3090 * {@code NaN} equals to itself, and 0.0f unequal to -0.0f.)
3091 *
3092 * @param a one array to be tested for equality
3093 * @param a2 the other array to be tested for equality
3094 * @return {@code true} if the two arrays are equal
3095 * @see Float#equals(Object)
3096 */
3097 public static boolean equals(float[] a, float[] a2) {
3098 if (a==a2)
3099 return true;
3100 if (a==null || a2==null)
3101 return false;
3102
3103 int length = a.length;
3104 if (a2.length != length)
3105 return false;
3106
3107 return ArraysSupport.mismatch(a, a2, length) < 0;
3108 }
3109
3110 /**
3111 * Returns true if the two specified arrays of floats, over the specified
3112 * ranges, are <i>equal</i> to one another.
3113 *
3114 * <p>Two arrays are considered equal if the number of elements covered by
3115 * each range is the same, and all corresponding pairs of elements over the
3116 * specified ranges in the two arrays are equal. In other words, two arrays
3117 * are equal if they contain, over the specified ranges, the same elements
3118 * in the same order.
3119 *
3120 * <p>Two floats {@code f1} and {@code f2} are considered equal if:
3121 * <pre> {@code new Float(f1).equals(new Float(f2))}</pre>
3122 * (Unlike the {@code ==} operator, this method considers
3123 * {@code NaN} equals to itself, and 0.0f unequal to -0.0f.)
3124 *
3125 * @param a the first array to be tested for equality
3126 * @param aFromIndex the index (inclusive) of the first element in the
3127 * first array to be tested
3128 * @param aToIndex the index (exclusive) of the last element in the
3129 * first array to be tested
3130 * @param b the second array to be tested fro equality
3131 * @param bFromIndex the index (inclusive) of the first element in the
3132 * second array to be tested
3133 * @param bToIndex the index (exclusive) of the last element in the
3134 * second array to be tested
3135 * @return {@code true} if the two arrays, over the specified ranges, are
3136 * equal
3137 * @throws IllegalArgumentException
3138 * if {@code aFromIndex > aToIndex} or
3139 * if {@code bFromIndex > bToIndex}
3140 * @throws ArrayIndexOutOfBoundsException
3141 * if {@code aFromIndex < 0 or aToIndex > a.length} or
8904 T[] b, int bFromIndex, int bToIndex,
8905 Comparator<? super T> cmp) {
8906 Objects.requireNonNull(cmp);
8907 rangeCheck(a.length, aFromIndex, aToIndex);
8908 rangeCheck(b.length, bFromIndex, bToIndex);
8909
8910 int aLength = aToIndex - aFromIndex;
8911 int bLength = bToIndex - bFromIndex;
8912 int length = Math.min(aLength, bLength);
8913 for (int i = 0; i < length; i++) {
8914 T oa = a[aFromIndex++];
8915 T ob = b[bFromIndex++];
8916 if (oa != ob) {
8917 // Null-value comparison is deferred to the comparator
8918 int v = cmp.compare(oa, ob);
8919 if (v != 0) {
8920 return i;
8921 }
8922 }
8923 }
8924
8925 return aLength != bLength ? length : -1;
8926 }
8927 }
|
1 /*
2 * Copyright (c) 1997, 2019, Oracle and/or its affiliates. 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. Oracle designates this
8 * particular file as subject to the "Classpath" exception as provided
9 * by Oracle in the LICENSE file that accompanied this code.
10 *
11 * This code is distributed in the hope that it will be useful, but WITHOUT
12 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
14 * version 2 for more details (a copy is included in the LICENSE file that
15 * accompanied this code).
16 *
17 * You should have received a copy of the GNU General Public License version
18 * 2 along with this work; if not, write to the Free Software Foundation,
19 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
20 *
21 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
22 * or visit www.oracle.com if you need additional information or have any
57 *
58 * <p>The documentation for the methods contained in this class includes
59 * brief descriptions of the <i>implementations</i>. Such descriptions should
60 * be regarded as <i>implementation notes</i>, rather than parts of the
61 * <i>specification</i>. Implementors should feel free to substitute other
62 * algorithms, so long as the specification itself is adhered to. (For
63 * example, the algorithm used by {@code sort(Object[])} does not have to be
64 * a MergeSort, but it does have to be <i>stable</i>.)
65 *
66 * <p>This class is a member of the
67 * <a href="{@docRoot}/java.base/java/util/package-summary.html#CollectionsFramework">
68 * Java Collections Framework</a>.
69 *
70 * @author Josh Bloch
71 * @author Neal Gafter
72 * @author John Rose
73 * @since 1.2
74 */
75 public class Arrays {
76
77 // Suppresses default constructor, ensuring non-instantiability.
78 private Arrays() {}
79
80 /*
81 * Sorting methods. Note that all public "sort" methods take the
82 * same form: performing argument checks if necessary, and then
83 * expanding arguments into those required for the internal
84 * implementation methods residing in other package-private
85 * classes (except for legacyMergeSort, included in this class).
86 */
87
88 /**
89 * Sorts the specified array into ascending numerical order.
90 *
91 * @implNote The sorting algorithm is a Dual-Pivot Quicksort
92 * by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithm
93 * offers O(n log(n)) performance on all data sets, and is typically
94 * faster than traditional (one-pivot) Quicksort implementations.
95 *
96 * @param a the array to be sorted
97 */
98 public static void sort(int[] a) {
99 DualPivotQuicksort.sort(a, 0, 0, a.length);
100 }
101
102 /**
103 * Sorts the specified range of the array into ascending order. The range
104 * to be sorted extends from the index {@code fromIndex}, inclusive, to
105 * the index {@code toIndex}, exclusive. If {@code fromIndex == toIndex},
106 * the range to be sorted is empty.
107 *
108 * @implNote The sorting algorithm is a Dual-Pivot Quicksort
109 * by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithm
110 * offers O(n log(n)) performance on all data sets, and is typically
111 * faster than traditional (one-pivot) Quicksort implementations.
112 *
113 * @param a the array to be sorted
114 * @param fromIndex the index of the first element, inclusive, to be sorted
115 * @param toIndex the index of the last element, exclusive, to be sorted
116 *
117 * @throws IllegalArgumentException if {@code fromIndex > toIndex}
118 * @throws ArrayIndexOutOfBoundsException
119 * if {@code fromIndex < 0} or {@code toIndex > a.length}
120 */
121 public static void sort(int[] a, int fromIndex, int toIndex) {
122 rangeCheck(a.length, fromIndex, toIndex);
123 DualPivotQuicksort.sort(a, 0, fromIndex, toIndex);
124 }
125
126 /**
127 * Sorts the specified array into ascending numerical order.
128 *
129 * @implNote The sorting algorithm is a Dual-Pivot Quicksort
130 * by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithm
131 * offers O(n log(n)) performance on all data sets, and is typically
132 * faster than traditional (one-pivot) Quicksort implementations.
133 *
134 * @param a the array to be sorted
135 */
136 public static void sort(long[] a) {
137 DualPivotQuicksort.sort(a, 0, 0, a.length);
138 }
139
140 /**
141 * Sorts the specified range of the array into ascending order. The range
142 * to be sorted extends from the index {@code fromIndex}, inclusive, to
143 * the index {@code toIndex}, exclusive. If {@code fromIndex == toIndex},
144 * the range to be sorted is empty.
145 *
146 * @implNote The sorting algorithm is a Dual-Pivot Quicksort
147 * by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithm
148 * offers O(n log(n)) performance on all data sets, and is typically
149 * faster than traditional (one-pivot) Quicksort implementations.
150 *
151 * @param a the array to be sorted
152 * @param fromIndex the index of the first element, inclusive, to be sorted
153 * @param toIndex the index of the last element, exclusive, to be sorted
154 *
155 * @throws IllegalArgumentException if {@code fromIndex > toIndex}
156 * @throws ArrayIndexOutOfBoundsException
157 * if {@code fromIndex < 0} or {@code toIndex > a.length}
158 */
159 public static void sort(long[] a, int fromIndex, int toIndex) {
160 rangeCheck(a.length, fromIndex, toIndex);
161 DualPivotQuicksort.sort(a, 0, fromIndex, toIndex);
162 }
163
164 /**
165 * Sorts the specified array into ascending numerical order.
166 *
167 * @implNote The sorting algorithm is a Dual-Pivot Quicksort
168 * by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithm
169 * offers O(n log(n)) performance on all data sets, and is typically
170 * faster than traditional (one-pivot) Quicksort implementations.
171 *
172 * @param a the array to be sorted
173 */
174 public static void sort(short[] a) {
175 DualPivotQuicksort.sort(a, 0, a.length);
176 }
177
178 /**
179 * Sorts the specified range of the array into ascending order. The range
180 * to be sorted extends from the index {@code fromIndex}, inclusive, to
181 * the index {@code toIndex}, exclusive. If {@code fromIndex == toIndex},
182 * the range to be sorted is empty.
183 *
184 * @implNote The sorting algorithm is a Dual-Pivot Quicksort
185 * by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithm
186 * offers O(n log(n)) performance on all data sets, and is typically
187 * faster than traditional (one-pivot) Quicksort implementations.
188 *
189 * @param a the array to be sorted
190 * @param fromIndex the index of the first element, inclusive, to be sorted
191 * @param toIndex the index of the last element, exclusive, to be sorted
192 *
193 * @throws IllegalArgumentException if {@code fromIndex > toIndex}
194 * @throws ArrayIndexOutOfBoundsException
195 * if {@code fromIndex < 0} or {@code toIndex > a.length}
196 */
197 public static void sort(short[] a, int fromIndex, int toIndex) {
198 rangeCheck(a.length, fromIndex, toIndex);
199 DualPivotQuicksort.sort(a, fromIndex, toIndex);
200 }
201
202 /**
203 * Sorts the specified array into ascending numerical order.
204 *
205 * @implNote The sorting algorithm is a Dual-Pivot Quicksort
206 * by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithm
207 * offers O(n log(n)) performance on all data sets, and is typically
208 * faster than traditional (one-pivot) Quicksort implementations.
209 *
210 * @param a the array to be sorted
211 */
212 public static void sort(char[] a) {
213 DualPivotQuicksort.sort(a, 0, a.length);
214 }
215
216 /**
217 * Sorts the specified range of the array into ascending order. The range
218 * to be sorted extends from the index {@code fromIndex}, inclusive, to
219 * the index {@code toIndex}, exclusive. If {@code fromIndex == toIndex},
220 * the range to be sorted is empty.
221 *
222 * @implNote The sorting algorithm is a Dual-Pivot Quicksort
223 * by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithm
224 * offers O(n log(n)) performance on all data sets, and is typically
225 * faster than traditional (one-pivot) Quicksort implementations.
226 *
227 * @param a the array to be sorted
228 * @param fromIndex the index of the first element, inclusive, to be sorted
229 * @param toIndex the index of the last element, exclusive, to be sorted
230 *
231 * @throws IllegalArgumentException if {@code fromIndex > toIndex}
232 * @throws ArrayIndexOutOfBoundsException
233 * if {@code fromIndex < 0} or {@code toIndex > a.length}
234 */
235 public static void sort(char[] a, int fromIndex, int toIndex) {
236 rangeCheck(a.length, fromIndex, toIndex);
237 DualPivotQuicksort.sort(a, fromIndex, toIndex);
238 }
239
240 /**
241 * Sorts the specified array into ascending numerical order.
242 *
243 * @implNote The sorting algorithm is a Dual-Pivot Quicksort
244 * by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithm
245 * offers O(n log(n)) performance on all data sets, and is typically
246 * faster than traditional (one-pivot) Quicksort implementations.
247 *
248 * @param a the array to be sorted
249 */
250 public static void sort(byte[] a) {
251 DualPivotQuicksort.sort(a, 0, a.length);
252 }
253
254 /**
255 * Sorts the specified range of the array into ascending order. The range
256 * to be sorted extends from the index {@code fromIndex}, inclusive, to
257 * the index {@code toIndex}, exclusive. If {@code fromIndex == toIndex},
258 * the range to be sorted is empty.
259 *
260 * @implNote The sorting algorithm is a Dual-Pivot Quicksort
261 * by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithm
262 * offers O(n log(n)) performance on all data sets, and is typically
263 * faster than traditional (one-pivot) Quicksort implementations.
264 *
265 * @param a the array to be sorted
266 * @param fromIndex the index of the first element, inclusive, to be sorted
267 * @param toIndex the index of the last element, exclusive, to be sorted
268 *
269 * @throws IllegalArgumentException if {@code fromIndex > toIndex}
270 * @throws ArrayIndexOutOfBoundsException
271 * if {@code fromIndex < 0} or {@code toIndex > a.length}
272 */
273 public static void sort(byte[] a, int fromIndex, int toIndex) {
274 rangeCheck(a.length, fromIndex, toIndex);
275 DualPivotQuicksort.sort(a, fromIndex, toIndex);
276 }
277
278 /**
279 * Sorts the specified array into ascending numerical order.
280 *
281 * <p>The {@code <} relation does not provide a total order on all float
282 * values: {@code -0.0f == 0.0f} is {@code true} and a {@code Float.NaN}
283 * value compares neither less than, greater than, nor equal to any value,
284 * even itself. This method uses the total order imposed by the method
285 * {@link Float#compareTo}: {@code -0.0f} is treated as less than value
286 * {@code 0.0f} and {@code Float.NaN} is considered greater than any
287 * other value and all {@code Float.NaN} values are considered equal.
288 *
289 * @implNote The sorting algorithm is a Dual-Pivot Quicksort
290 * by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithm
291 * offers O(n log(n)) performance on all data sets, and is typically
292 * faster than traditional (one-pivot) Quicksort implementations.
293 *
294 * @param a the array to be sorted
295 */
296 public static void sort(float[] a) {
297 DualPivotQuicksort.sort(a, 0, 0, a.length);
298 }
299
300 /**
301 * Sorts the specified range of the array into ascending order. The range
302 * to be sorted extends from the index {@code fromIndex}, inclusive, to
303 * the index {@code toIndex}, exclusive. If {@code fromIndex == toIndex},
304 * the range to be sorted is empty.
305 *
306 * <p>The {@code <} relation does not provide a total order on all float
307 * values: {@code -0.0f == 0.0f} is {@code true} and a {@code Float.NaN}
308 * value compares neither less than, greater than, nor equal to any value,
309 * even itself. This method uses the total order imposed by the method
310 * {@link Float#compareTo}: {@code -0.0f} is treated as less than value
311 * {@code 0.0f} and {@code Float.NaN} is considered greater than any
312 * other value and all {@code Float.NaN} values are considered equal.
313 *
314 * @implNote The sorting algorithm is a Dual-Pivot Quicksort
315 * by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithm
316 * offers O(n log(n)) performance on all data sets, and is typically
317 * faster than traditional (one-pivot) Quicksort implementations.
318 *
319 * @param a the array to be sorted
320 * @param fromIndex the index of the first element, inclusive, to be sorted
321 * @param toIndex the index of the last element, exclusive, to be sorted
322 *
323 * @throws IllegalArgumentException if {@code fromIndex > toIndex}
324 * @throws ArrayIndexOutOfBoundsException
325 * if {@code fromIndex < 0} or {@code toIndex > a.length}
326 */
327 public static void sort(float[] a, int fromIndex, int toIndex) {
328 rangeCheck(a.length, fromIndex, toIndex);
329 DualPivotQuicksort.sort(a, 0, fromIndex, toIndex);
330 }
331
332 /**
333 * Sorts the specified array into ascending numerical order.
334 *
335 * <p>The {@code <} relation does not provide a total order on all double
336 * values: {@code -0.0d == 0.0d} is {@code true} and a {@code Double.NaN}
337 * value compares neither less than, greater than, nor equal to any value,
338 * even itself. This method uses the total order imposed by the method
339 * {@link Double#compareTo}: {@code -0.0d} is treated as less than value
340 * {@code 0.0d} and {@code Double.NaN} is considered greater than any
341 * other value and all {@code Double.NaN} values are considered equal.
342 *
343 * @implNote The sorting algorithm is a Dual-Pivot Quicksort
344 * by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithm
345 * offers O(n log(n)) performance on all data sets, and is typically
346 * faster than traditional (one-pivot) Quicksort implementations.
347 *
348 * @param a the array to be sorted
349 */
350 public static void sort(double[] a) {
351 DualPivotQuicksort.sort(a, 0, 0, a.length);
352 }
353
354 /**
355 * Sorts the specified range of the array into ascending order. The range
356 * to be sorted extends from the index {@code fromIndex}, inclusive, to
357 * the index {@code toIndex}, exclusive. If {@code fromIndex == toIndex},
358 * the range to be sorted is empty.
359 *
360 * <p>The {@code <} relation does not provide a total order on all double
361 * values: {@code -0.0d == 0.0d} is {@code true} and a {@code Double.NaN}
362 * value compares neither less than, greater than, nor equal to any value,
363 * even itself. This method uses the total order imposed by the method
364 * {@link Double#compareTo}: {@code -0.0d} is treated as less than value
365 * {@code 0.0d} and {@code Double.NaN} is considered greater than any
366 * other value and all {@code Double.NaN} values are considered equal.
367 *
368 * @implNote The sorting algorithm is a Dual-Pivot Quicksort
369 * by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithm
370 * offers O(n log(n)) performance on all data sets, and is typically
371 * faster than traditional (one-pivot) Quicksort implementations.
372 *
373 * @param a the array to be sorted
374 * @param fromIndex the index of the first element, inclusive, to be sorted
375 * @param toIndex the index of the last element, exclusive, to be sorted
376 *
377 * @throws IllegalArgumentException if {@code fromIndex > toIndex}
378 * @throws ArrayIndexOutOfBoundsException
379 * if {@code fromIndex < 0} or {@code toIndex > a.length}
380 */
381 public static void sort(double[] a, int fromIndex, int toIndex) {
382 rangeCheck(a.length, fromIndex, toIndex);
383 DualPivotQuicksort.sort(a, 0, fromIndex, toIndex);
384 }
385
386 /**
387 * Sorts the specified array into ascending numerical order.
388 *
389 * @implNote The sorting algorithm is a Dual-Pivot Quicksort by
390 * Vladimir Yaroslavskiy, Jon Bentley and Josh Bloch. This algorithm
391 * offers O(n log(n)) performance on all data sets, and is typically
392 * faster than traditional (one-pivot) Quicksort implementations.
393 *
394 * @param a the array to be sorted
395 *
396 * @since 1.8
397 */
398 public static void parallelSort(byte[] a) {
399 DualPivotQuicksort.sort(a, 0, a.length);
400 }
401
402 /**
403 * Sorts the specified range of the array into ascending numerical order.
404 * The range to be sorted extends from the index {@code fromIndex},
405 * inclusive, to the index {@code toIndex}, exclusive. If
406 * {@code fromIndex == toIndex}, the range to be sorted is empty.
407 *
408 * @implNote The sorting algorithm is a Dual-Pivot Quicksort by
409 * Vladimir Yaroslavskiy, Jon Bentley and Josh Bloch. This algorithm
410 * offers O(n log(n)) performance on all data sets, and is typically
411 * faster than traditional (one-pivot) Quicksort implementations.
412 *
413 * @param a the array to be sorted
414 * @param fromIndex the index of the first element, inclusive, to be sorted
415 * @param toIndex the index of the last element, exclusive, to be sorted
416 *
417 * @throws IllegalArgumentException if {@code fromIndex > toIndex}
418 * @throws ArrayIndexOutOfBoundsException
419 * if {@code fromIndex < 0} or {@code toIndex > a.length}
420 *
421 * @since 1.8
422 */
423 public static void parallelSort(byte[] a, int fromIndex, int toIndex) {
424 rangeCheck(a.length, fromIndex, toIndex);
425 DualPivotQuicksort.sort(a, fromIndex, toIndex);
426 }
427
428 /**
429 * Sorts the specified array into ascending numerical order.
430 *
431 * @implNote The sorting algorithm is a Dual-Pivot Quicksort by
432 * Vladimir Yaroslavskiy, Jon Bentley and Josh Bloch. This algorithm
433 * offers O(n log(n)) performance on all data sets, and is typically
434 * faster than traditional (one-pivot) Quicksort implementations.
435 *
436 * @param a the array to be sorted
437 *
438 * @since 1.8
439 */
440 public static void parallelSort(char[] a) {
441 DualPivotQuicksort.sort(a, 0, a.length);
442 }
443
444 /**
445 * Sorts the specified range of the array into ascending numerical order.
446 * The range to be sorted extends from the index {@code fromIndex},
447 * inclusive, to the index {@code toIndex}, exclusive. If
448 * {@code fromIndex == toIndex}, the range to be sorted is empty.
449 *
450 * @implNote The sorting algorithm is a Dual-Pivot Quicksort by
451 * Vladimir Yaroslavskiy, Jon Bentley and Josh Bloch. This algorithm
452 * offers O(n log(n)) performance on all data sets, and is typically
453 * faster than traditional (one-pivot) Quicksort implementations.
454 *
455 * @param a the array to be sorted
456 * @param fromIndex the index of the first element, inclusive, to be sorted
457 * @param toIndex the index of the last element, exclusive, to be sorted
458 *
459 * @throws IllegalArgumentException if {@code fromIndex > toIndex}
460 * @throws ArrayIndexOutOfBoundsException
461 * if {@code fromIndex < 0} or {@code toIndex > a.length}
462 *
463 * @since 1.8
464 */
465 public static void parallelSort(char[] a, int fromIndex, int toIndex) {
466 rangeCheck(a.length, fromIndex, toIndex);
467 DualPivotQuicksort.sort(a, fromIndex, toIndex);
468 }
469
470 /**
471 * Sorts the specified array into ascending numerical order.
472 *
473 * @implNote The sorting algorithm is a Dual-Pivot Quicksort by
474 * Vladimir Yaroslavskiy, Jon Bentley and Josh Bloch. This algorithm
475 * offers O(n log(n)) performance on all data sets, and is typically
476 * faster than traditional (one-pivot) Quicksort implementations.
477 *
478 * @param a the array to be sorted
479 *
480 * @since 1.8
481 */
482 public static void parallelSort(short[] a) {
483 DualPivotQuicksort.sort(a, 0, a.length);
484 }
485
486 /**
487 * Sorts the specified range of the array into ascending numerical order.
488 * The range to be sorted extends from the index {@code fromIndex},
489 * inclusive, to the index {@code toIndex}, exclusive. If
490 * {@code fromIndex == toIndex}, the range to be sorted is empty.
491 *
492 * @implNote The sorting algorithm is a Dual-Pivot Quicksort by
493 * Vladimir Yaroslavskiy, Jon Bentley and Josh Bloch. This algorithm
494 * offers O(n log(n)) performance on all data sets, and is typically
495 * faster than traditional (one-pivot) Quicksort implementations.
496 *
497 * @param a the array to be sorted
498 * @param fromIndex the index of the first element, inclusive, to be sorted
499 * @param toIndex the index of the last element, exclusive, to be sorted
500 *
501 * @throws IllegalArgumentException if {@code fromIndex > toIndex}
502 * @throws ArrayIndexOutOfBoundsException
503 * if {@code fromIndex < 0} or {@code toIndex > a.length}
504 *
505 * @since 1.8
506 */
507 public static void parallelSort(short[] a, int fromIndex, int toIndex) {
508 rangeCheck(a.length, fromIndex, toIndex);
509 DualPivotQuicksort.sort(a, fromIndex, toIndex);
510 }
511
512 /**
513 * Sorts the specified array into ascending numerical order.
514 *
515 * @implNote The sorting algorithm is a Dual-Pivot Quicksort by
516 * Vladimir Yaroslavskiy, Jon Bentley and Josh Bloch. This algorithm
517 * offers O(n log(n)) performance on all data sets, and is typically
518 * faster than traditional (one-pivot) Quicksort implementations.
519 *
520 * @param a the array to be sorted
521 *
522 * @since 1.8
523 */
524 public static void parallelSort(int[] a) {
525 DualPivotQuicksort.sort(a, ForkJoinPool.getCommonPoolParallelism(), 0, a.length);
526 }
527
528 /**
529 * Sorts the specified range of the array into ascending numerical order.
530 * The range to be sorted extends from the index {@code fromIndex},
531 * inclusive, to the index {@code toIndex}, exclusive. If
532 * {@code fromIndex == toIndex}, the range to be sorted is empty.
533 *
534 * @implNote The sorting algorithm is a Dual-Pivot Quicksort by
535 * Vladimir Yaroslavskiy, Jon Bentley and Josh Bloch. This algorithm
536 * offers O(n log(n)) performance on all data sets, and is typically
537 * faster than traditional (one-pivot) Quicksort implementations.
538 *
539 * @param a the array to be sorted
540 * @param fromIndex the index of the first element, inclusive, to be sorted
541 * @param toIndex the index of the last element, exclusive, to be sorted
542 *
543 * @throws IllegalArgumentException if {@code fromIndex > toIndex}
544 * @throws ArrayIndexOutOfBoundsException
545 * if {@code fromIndex < 0} or {@code toIndex > a.length}
546 *
547 * @since 1.8
548 */
549 public static void parallelSort(int[] a, int fromIndex, int toIndex) {
550 rangeCheck(a.length, fromIndex, toIndex);
551 DualPivotQuicksort.sort(a, ForkJoinPool.getCommonPoolParallelism(), fromIndex, toIndex);
552 }
553
554 /**
555 * Sorts the specified array into ascending numerical order.
556 *
557 * @implNote The sorting algorithm is a Dual-Pivot Quicksort by
558 * Vladimir Yaroslavskiy, Jon Bentley and Josh Bloch. This algorithm
559 * offers O(n log(n)) performance on all data sets, and is typically
560 * faster than traditional (one-pivot) Quicksort implementations.
561 *
562 * @param a the array to be sorted
563 *
564 * @since 1.8
565 */
566 public static void parallelSort(long[] a) {
567 DualPivotQuicksort.sort(a, ForkJoinPool.getCommonPoolParallelism(), 0, a.length);
568 }
569
570 /**
571 * Sorts the specified range of the array into ascending numerical order.
572 * The range to be sorted extends from the index {@code fromIndex},
573 * inclusive, to the index {@code toIndex}, exclusive. If
574 * {@code fromIndex == toIndex}, the range to be sorted is empty.
575 *
576 * @implNote The sorting algorithm is a Dual-Pivot Quicksort by
577 * Vladimir Yaroslavskiy, Jon Bentley and Josh Bloch. This algorithm
578 * offers O(n log(n)) performance on all data sets, and is typically
579 * faster than traditional (one-pivot) Quicksort implementations.
580 *
581 * @param a the array to be sorted
582 * @param fromIndex the index of the first element, inclusive, to be sorted
583 * @param toIndex the index of the last element, exclusive, to be sorted
584 *
585 * @throws IllegalArgumentException if {@code fromIndex > toIndex}
586 * @throws ArrayIndexOutOfBoundsException
587 * if {@code fromIndex < 0} or {@code toIndex > a.length}
588 *
589 * @since 1.8
590 */
591 public static void parallelSort(long[] a, int fromIndex, int toIndex) {
592 rangeCheck(a.length, fromIndex, toIndex);
593 DualPivotQuicksort.sort(a, ForkJoinPool.getCommonPoolParallelism(), fromIndex, toIndex);
594 }
595
596 /**
597 * Sorts the specified array into ascending numerical order.
598 *
599 * <p>The {@code <} relation does not provide a total order on all float
600 * values: {@code -0.0f == 0.0f} is {@code true} and a {@code Float.NaN}
601 * value compares neither less than, greater than, nor equal to any value,
602 * even itself. This method uses the total order imposed by the method
603 * {@link Float#compareTo}: {@code -0.0f} is treated as less than value
604 * {@code 0.0f} and {@code Float.NaN} is considered greater than any
605 * other value and all {@code Float.NaN} values are considered equal.
606 *
607 * @implNote The sorting algorithm is a Dual-Pivot Quicksort by
608 * Vladimir Yaroslavskiy, Jon Bentley and Josh Bloch. This algorithm
609 * offers O(n log(n)) performance on all data sets, and is typically
610 * faster than traditional (one-pivot) Quicksort implementations.
611 *
612 * @param a the array to be sorted
613 *
614 * @since 1.8
615 */
616 public static void parallelSort(float[] a) {
617 DualPivotQuicksort.sort(a, ForkJoinPool.getCommonPoolParallelism(), 0, a.length);
618 }
619
620 /**
621 * Sorts the specified range of the array into ascending numerical order.
622 * The range to be sorted extends from the index {@code fromIndex},
623 * inclusive, to the index {@code toIndex}, exclusive. If
624 * {@code fromIndex == toIndex}, the range to be sorted is empty.
625 *
626 * <p>The {@code <} relation does not provide a total order on all float
627 * values: {@code -0.0f == 0.0f} is {@code true} and a {@code Float.NaN}
628 * value compares neither less than, greater than, nor equal to any value,
629 * even itself. This method uses the total order imposed by the method
630 * {@link Float#compareTo}: {@code -0.0f} is treated as less than value
631 * {@code 0.0f} and {@code Float.NaN} is considered greater than any
632 * other value and all {@code Float.NaN} values are considered equal.
633 *
634 * @implNote The sorting algorithm is a Dual-Pivot Quicksort by
635 * Vladimir Yaroslavskiy, Jon Bentley and Josh Bloch. This algorithm
636 * offers O(n log(n)) performance on all data sets, and is typically
637 * faster than traditional (one-pivot) Quicksort implementations.
638 *
639 * @param a the array to be sorted
640 * @param fromIndex the index of the first element, inclusive, to be sorted
641 * @param toIndex the index of the last element, exclusive, to be sorted
642 *
643 * @throws IllegalArgumentException if {@code fromIndex > toIndex}
644 * @throws ArrayIndexOutOfBoundsException
645 * if {@code fromIndex < 0} or {@code toIndex > a.length}
646 *
647 * @since 1.8
648 */
649 public static void parallelSort(float[] a, int fromIndex, int toIndex) {
650 rangeCheck(a.length, fromIndex, toIndex);
651 DualPivotQuicksort.sort(a, ForkJoinPool.getCommonPoolParallelism(), fromIndex, toIndex);
652 }
653
654 /**
655 * Sorts the specified array into ascending numerical order.
656 *
657 * <p>The {@code <} relation does not provide a total order on all double
658 * values: {@code -0.0d == 0.0d} is {@code true} and a {@code Double.NaN}
659 * value compares neither less than, greater than, nor equal to any value,
660 * even itself. This method uses the total order imposed by the method
661 * {@link Double#compareTo}: {@code -0.0d} is treated as less than value
662 * {@code 0.0d} and {@code Double.NaN} is considered greater than any
663 * other value and all {@code Double.NaN} values are considered equal.
664 *
665 * @implNote The sorting algorithm is a Dual-Pivot Quicksort by
666 * Vladimir Yaroslavskiy, Jon Bentley and Josh Bloch. This algorithm
667 * offers O(n log(n)) performance on all data sets, and is typically
668 * faster than traditional (one-pivot) Quicksort implementations.
669 *
670 * @param a the array to be sorted
671 *
672 * @since 1.8
673 */
674 public static void parallelSort(double[] a) {
675 DualPivotQuicksort.sort(a, ForkJoinPool.getCommonPoolParallelism(), 0, a.length);
676 }
677
678 /**
679 * Sorts the specified range of the array into ascending numerical order.
680 * The range to be sorted extends from the index {@code fromIndex},
681 * inclusive, to the index {@code toIndex}, exclusive. If
682 * {@code fromIndex == toIndex}, the range to be sorted is empty.
683 *
684 * <p>The {@code <} relation does not provide a total order on all double
685 * values: {@code -0.0d == 0.0d} is {@code true} and a {@code Double.NaN}
686 * value compares neither less than, greater than, nor equal to any value,
687 * even itself. This method uses the total order imposed by the method
688 * {@link Double#compareTo}: {@code -0.0d} is treated as less than value
689 * {@code 0.0d} and {@code Double.NaN} is considered greater than any
690 * other value and all {@code Double.NaN} values are considered equal.
691 *
692 * @implNote The sorting algorithm is a Dual-Pivot Quicksort by
693 * Vladimir Yaroslavskiy, Jon Bentley and Josh Bloch. This algorithm
694 * offers O(n log(n)) performance on all data sets, and is typically
695 * faster than traditional (one-pivot) Quicksort implementations.
696 *
697 * @param a the array to be sorted
698 * @param fromIndex the index of the first element, inclusive, to be sorted
699 * @param toIndex the index of the last element, exclusive, to be sorted
700 *
701 * @throws IllegalArgumentException if {@code fromIndex > toIndex}
702 * @throws ArrayIndexOutOfBoundsException
703 * if {@code fromIndex < 0} or {@code toIndex > a.length}
704 *
705 * @since 1.8
706 */
707 public static void parallelSort(double[] a, int fromIndex, int toIndex) {
708 rangeCheck(a.length, fromIndex, toIndex);
709 DualPivotQuicksort.sort(a, ForkJoinPool.getCommonPoolParallelism(), fromIndex, toIndex);
710 }
711
712 /**
713 * Checks that {@code fromIndex} and {@code toIndex} are in
714 * the range and throws an exception if they aren't.
715 */
716 static void rangeCheck(int arrayLength, int fromIndex, int toIndex) {
717 if (fromIndex > toIndex) {
718 throw new IllegalArgumentException(
719 "fromIndex(" + fromIndex + ") > toIndex(" + toIndex + ")");
720 }
721 if (fromIndex < 0) {
722 throw new ArrayIndexOutOfBoundsException(fromIndex);
723 }
724 if (toIndex > arrayLength) {
725 throw new ArrayIndexOutOfBoundsException(toIndex);
726 }
727 }
728
729 /**
730 * A comparator that implements the natural ordering of a group of
731 * mutually comparable elements. May be used when a supplied
732 * comparator is null. To simplify code-sharing within underlying
733 * implementations, the compare method only declares type Object
734 * for its second argument.
735 *
736 * Arrays class implementor's note: It is an empirical matter
737 * whether ComparableTimSort offers any performance benefit over
738 * TimSort used with this comparator. If not, you are better off
739 * deleting or bypassing ComparableTimSort. There is currently no
740 * empirical case for separating them for parallel sorting, so all
741 * public Object parallelSort methods use the same comparator
742 * based implementation.
743 */
744 static final class NaturalOrder implements Comparator<Object> {
745 @SuppressWarnings("unchecked")
746 public int compare(Object first, Object second) {
747 return ((Comparable<Object>)first).compareTo(second);
748 }
749 static final NaturalOrder INSTANCE = new NaturalOrder();
750 }
751
752 /**
753 * The minimum array length below which a parallel sorting
754 * algorithm will not further partition the sorting task. Using
755 * smaller sizes typically results in memory contention across
756 * tasks that makes parallel speedups unlikely.
757 */
758 private static final int MIN_ARRAY_SORT_GRAN = 1 << 13;
759
760 /**
761 * Sorts the specified array of objects into ascending order, according
762 * to the {@linkplain Comparable natural ordering} of its elements.
763 * All elements in the array must implement the {@link Comparable}
764 * interface. Furthermore, all elements in the array must be
765 * <i>mutually comparable</i> (that is, {@code e1.compareTo(e2)} must
766 * not throw a {@code ClassCastException} for any elements {@code e1}
767 * and {@code e2} in the array).
768 *
769 * <p>This sort is guaranteed to be <i>stable</i>: equal elements will
770 * not be reordered as a result of the sort.
771 *
772 * @implNote The sorting algorithm is a parallel sort-merge that breaks the
773 * array into sub-arrays that are themselves sorted and then merged. When
774 * the sub-array length reaches a minimum granularity, the sub-array is
775 * sorted using the appropriate {@link Arrays#sort(Object[]) Arrays.sort}
776 * method. If the length of the specified array is less than the minimum
777 * granularity, then it is sorted using the appropriate {@link
778 * Arrays#sort(Object[]) Arrays.sort} method. The algorithm requires a
779 * working space no greater than the size of the original array. The
780 * {@link ForkJoinPool#commonPool() ForkJoin common pool} is used to
2775
2776 int aLength = aToIndex - aFromIndex;
2777 int bLength = bToIndex - bFromIndex;
2778 if (aLength != bLength)
2779 return false;
2780
2781 return ArraysSupport.mismatch(a, aFromIndex,
2782 b, bFromIndex,
2783 aLength) < 0;
2784 }
2785
2786 /**
2787 * Returns {@code true} if the two specified arrays of doubles are
2788 * <i>equal</i> to one another. Two arrays are considered equal if both
2789 * arrays contain the same number of elements, and all corresponding pairs
2790 * of elements in the two arrays are equal. In other words, two arrays
2791 * are equal if they contain the same elements in the same order. Also,
2792 * two array references are considered equal if both are {@code null}.
2793 *
2794 * Two doubles {@code d1} and {@code d2} are considered equal if:
2795 * <pre>{@code new Double(d1).equals(new Double(d2))}</pre>
2796 * (Unlike the {@code ==} operator, this method considers
2797 * {@code NaN} equals to itself, and 0.0d unequal to -0.0d.)
2798 *
2799 * @param a one array to be tested for equality
2800 * @param a2 the other array to be tested for equality
2801 * @return {@code true} if the two arrays are equal
2802 * @see Double#equals(Object)
2803 */
2804 public static boolean equals(double[] a, double[] a2) {
2805 if (a==a2)
2806 return true;
2807 if (a==null || a2==null)
2808 return false;
2809
2810 int length = a.length;
2811 if (a2.length != length)
2812 return false;
2813
2814 return ArraysSupport.mismatch(a, a2, length) < 0;
2815 }
2816
2817 /**
2818 * Returns true if the two specified arrays of doubles, over the specified
2819 * ranges, are <i>equal</i> to one another.
2820 *
2821 * <p>Two arrays are considered equal if the number of elements covered by
2822 * each range is the same, and all corresponding pairs of elements over the
2823 * specified ranges in the two arrays are equal. In other words, two arrays
2824 * are equal if they contain, over the specified ranges, the same elements
2825 * in the same order.
2826 *
2827 * <p>Two doubles {@code d1} and {@code d2} are considered equal if:
2828 * <pre>{@code new Double(d1).equals(new Double(d2))}</pre>
2829 * (Unlike the {@code ==} operator, this method considers
2830 * {@code NaN} equals to itself, and 0.0d unequal to -0.0d.)
2831 *
2832 * @param a the first array to be tested for equality
2833 * @param aFromIndex the index (inclusive) of the first element in the
2834 * first array to be tested
2835 * @param aToIndex the index (exclusive) of the last element in the
2836 * first array to be tested
2837 * @param b the second array to be tested fro equality
2838 * @param bFromIndex the index (inclusive) of the first element in the
2839 * second array to be tested
2840 * @param bToIndex the index (exclusive) of the last element in the
2841 * second array to be tested
2842 * @return {@code true} if the two arrays, over the specified ranges, are
2843 * equal
2844 * @throws IllegalArgumentException
2845 * if {@code aFromIndex > aToIndex} or
2846 * if {@code bFromIndex > bToIndex}
2847 * @throws ArrayIndexOutOfBoundsException
2848 * if {@code aFromIndex < 0 or aToIndex > a.length} or
2858 rangeCheck(b.length, bFromIndex, bToIndex);
2859
2860 int aLength = aToIndex - aFromIndex;
2861 int bLength = bToIndex - bFromIndex;
2862 if (aLength != bLength)
2863 return false;
2864
2865 return ArraysSupport.mismatch(a, aFromIndex,
2866 b, bFromIndex, aLength) < 0;
2867 }
2868
2869 /**
2870 * Returns {@code true} if the two specified arrays of floats are
2871 * <i>equal</i> to one another. Two arrays are considered equal if both
2872 * arrays contain the same number of elements, and all corresponding pairs
2873 * of elements in the two arrays are equal. In other words, two arrays
2874 * are equal if they contain the same elements in the same order. Also,
2875 * two array references are considered equal if both are {@code null}.
2876 *
2877 * Two floats {@code f1} and {@code f2} are considered equal if:
2878 * <pre>{@code new Float(f1).equals(new Float(f2))}</pre>
2879 * (Unlike the {@code ==} operator, this method considers
2880 * {@code NaN} equals to itself, and 0.0f unequal to -0.0f.)
2881 *
2882 * @param a one array to be tested for equality
2883 * @param a2 the other array to be tested for equality
2884 * @return {@code true} if the two arrays are equal
2885 * @see Float#equals(Object)
2886 */
2887 public static boolean equals(float[] a, float[] a2) {
2888 if (a==a2)
2889 return true;
2890 if (a==null || a2==null)
2891 return false;
2892
2893 int length = a.length;
2894 if (a2.length != length)
2895 return false;
2896
2897 return ArraysSupport.mismatch(a, a2, length) < 0;
2898 }
2899
2900 /**
2901 * Returns true if the two specified arrays of floats, over the specified
2902 * ranges, are <i>equal</i> to one another.
2903 *
2904 * <p>Two arrays are considered equal if the number of elements covered by
2905 * each range is the same, and all corresponding pairs of elements over the
2906 * specified ranges in the two arrays are equal. In other words, two arrays
2907 * are equal if they contain, over the specified ranges, the same elements
2908 * in the same order.
2909 *
2910 * <p>Two floats {@code f1} and {@code f2} are considered equal if:
2911 * <pre>{@code new Float(f1).equals(new Float(f2))}</pre>
2912 * (Unlike the {@code ==} operator, this method considers
2913 * {@code NaN} equals to itself, and 0.0f unequal to -0.0f.)
2914 *
2915 * @param a the first array to be tested for equality
2916 * @param aFromIndex the index (inclusive) of the first element in the
2917 * first array to be tested
2918 * @param aToIndex the index (exclusive) of the last element in the
2919 * first array to be tested
2920 * @param b the second array to be tested fro equality
2921 * @param bFromIndex the index (inclusive) of the first element in the
2922 * second array to be tested
2923 * @param bToIndex the index (exclusive) of the last element in the
2924 * second array to be tested
2925 * @return {@code true} if the two arrays, over the specified ranges, are
2926 * equal
2927 * @throws IllegalArgumentException
2928 * if {@code aFromIndex > aToIndex} or
2929 * if {@code bFromIndex > bToIndex}
2930 * @throws ArrayIndexOutOfBoundsException
2931 * if {@code aFromIndex < 0 or aToIndex > a.length} or
8694 T[] b, int bFromIndex, int bToIndex,
8695 Comparator<? super T> cmp) {
8696 Objects.requireNonNull(cmp);
8697 rangeCheck(a.length, aFromIndex, aToIndex);
8698 rangeCheck(b.length, bFromIndex, bToIndex);
8699
8700 int aLength = aToIndex - aFromIndex;
8701 int bLength = bToIndex - bFromIndex;
8702 int length = Math.min(aLength, bLength);
8703 for (int i = 0; i < length; i++) {
8704 T oa = a[aFromIndex++];
8705 T ob = b[bFromIndex++];
8706 if (oa != ob) {
8707 // Null-value comparison is deferred to the comparator
8708 int v = cmp.compare(oa, ob);
8709 if (v != 0) {
8710 return i;
8711 }
8712 }
8713 }
8714 return aLength != bLength ? length : -1;
8715 }
8716 }
|