1 /*
2 * Copyright 1997-2007 Sun Microsystems, Inc. All Rights Reserved.
3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
4 *
5 * This code is free software; you can redistribute it and/or modify it
6 * under the terms of the GNU General Public License version 2 only, as
7 * published by the Free Software Foundation. Sun designates this
8 * particular file as subject to the "Classpath" exception as provided
9 * by Sun 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 Sun Microsystems, Inc., 4150 Network Circle, Santa Clara,
22 * CA 95054 USA or visit www.sun.com if you need additional information or
23 * have any questions.
24 */
25
26 package java.util;
27
28 import java.lang.reflect;
29
30 /**
31 * This class contains various methods for manipulating arrays (such as
32 * sorting and searching). This class also contains a static factory
33 * that allows arrays to be viewed as lists.
34 *
35 * <p>The methods in this class all throw a <tt>NullPointerException</tt> if
36 * the specified array reference is null, except where noted.
37 *
38 * <p>The documentation for the methods contained in this class includes
39 * briefs description of the <i>implementations</i>. Such descriptions should
40 * be regarded as <i>implementation notes</i>, rather than parts of the
41 * <i>specification</i>. Implementors should feel free to substitute other
42 * algorithms, so long as the specification itself is adhered to. (For
43 * example, the algorithm used by <tt>sort(Object[])</tt> does not have to be
44 * a mergesort, but it does have to be <i>stable</i>.)
45 *
46 * <p>This class is a member of the
47 * <a href="{@docRoot}/../technotes/guides/collections/index.html">
48 * Java Collections Framework</a>.
49 *
50 * @author Josh Bloch
51 * @author Neal Gafter
52 * @author John Rose
53 * @since 1.2
54 */
55
56 public class Arrays {
57 // Suppresses default constructor, ensuring non-instantiability.
58 private Arrays() {
59 }
60
61 // Sorting
62
63 /**
64 * Sorts the specified array of longs into ascending numerical order.
65 * The sorting algorithm is a tuned quicksort, adapted from Jon
66 * L. Bentley and M. Douglas McIlroy's "Engineering a Sort Function",
67 * Software-Practice and Experience, Vol. 23(11) P. 1249-1265 (November
68 * 1993). This algorithm offers n*log(n) performance on many data sets
69 * that cause other quicksorts to degrade to quadratic performance.
70 *
71 * @param a the array to be sorted
72 */
73 public static void sort(long[] a) {
74 sort1(a, 0, a.length);
75 }
76
77 /**
78 * Sorts the specified range of the specified array of longs into
79 * ascending numerical order. The range to be sorted extends from index
80 * <tt>fromIndex</tt>, inclusive, to index <tt>toIndex</tt>, exclusive.
81 * (If <tt>fromIndex==toIndex</tt>, the range to be sorted is empty.)
82 *
83 * <p>The sorting algorithm is a tuned quicksort, adapted from Jon
84 * L. Bentley and M. Douglas McIlroy's "Engineering a Sort Function",
85 * Software-Practice and Experience, Vol. 23(11) P. 1249-1265 (November
86 * 1993). This algorithm offers n*log(n) performance on many data sets
87 * that cause other quicksorts to degrade to quadratic performance.
88 *
89 * @param a the array to be sorted
90 * @param fromIndex the index of the first element (inclusive) to be
91 * sorted
92 * @param toIndex the index of the last element (exclusive) to be sorted
93 * @throws IllegalArgumentException if <tt>fromIndex > toIndex</tt>
94 * @throws ArrayIndexOutOfBoundsException if <tt>fromIndex < 0</tt> or
95 * <tt>toIndex > a.length</tt>
96 */
97 public static void sort(long[] a, int fromIndex, int toIndex) {
98 rangeCheck(a.length, fromIndex, toIndex);
99 sort1(a, fromIndex, toIndex-fromIndex);
100 }
101
102 /**
103 * Sorts the specified array of ints into ascending numerical order.
104 * The sorting algorithm is a tuned quicksort, adapted from Jon
105 * L. Bentley and M. Douglas McIlroy's "Engineering a Sort Function",
106 * Software-Practice and Experience, Vol. 23(11) P. 1249-1265 (November
107 * 1993). This algorithm offers n*log(n) performance on many data sets
108 * that cause other quicksorts to degrade to quadratic performance.
109 *
110 * @param a the array to be sorted
111 */
112 public static void sort(int[] a) {
113 sort1(a, 0, a.length);
114 }
115
116 /**
117 * Sorts the specified range of the specified array of ints into
118 * ascending numerical order. The range to be sorted extends from index
119 * <tt>fromIndex</tt>, inclusive, to index <tt>toIndex</tt>, exclusive.
120 * (If <tt>fromIndex==toIndex</tt>, the range to be sorted is empty.)<p>
121 *
122 * The sorting algorithm is a tuned quicksort, adapted from Jon
123 * L. Bentley and M. Douglas McIlroy's "Engineering a Sort Function",
124 * Software-Practice and Experience, Vol. 23(11) P. 1249-1265 (November
125 * 1993). This algorithm offers n*log(n) performance on many data sets
126 * that cause other quicksorts to degrade to quadratic performance.
127 *
128 * @param a the array to be sorted
129 * @param fromIndex the index of the first element (inclusive) to be
130 * sorted
131 * @param toIndex the index of the last element (exclusive) to be sorted
132 * @throws IllegalArgumentException if <tt>fromIndex > toIndex</tt>
133 * @throws ArrayIndexOutOfBoundsException if <tt>fromIndex < 0</tt> or
134 * <tt>toIndex > a.length</tt>
135 */
136 public static void sort(int[] a, int fromIndex, int toIndex) {
137 rangeCheck(a.length, fromIndex, toIndex);
138 sort1(a, fromIndex, toIndex-fromIndex);
139 }
140
141 /**
142 * Sorts the specified array of shorts into ascending numerical order.
143 * The sorting algorithm is a tuned quicksort, adapted from Jon
144 * L. Bentley and M. Douglas McIlroy's "Engineering a Sort Function",
145 * Software-Practice and Experience, Vol. 23(11) P. 1249-1265 (November
146 * 1993). This algorithm offers n*log(n) performance on many data sets
147 * that cause other quicksorts to degrade to quadratic performance.
148 *
149 * @param a the array to be sorted
150 */
151 public static void sort(short[] a) {
152 sort1(a, 0, a.length);
153 }
154
155 /**
156 * Sorts the specified range of the specified array of shorts into
157 * ascending numerical order. The range to be sorted extends from index
158 * <tt>fromIndex</tt>, inclusive, to index <tt>toIndex</tt>, exclusive.
159 * (If <tt>fromIndex==toIndex</tt>, the range to be sorted is empty.)<p>
160 *
161 * The sorting algorithm is a tuned quicksort, adapted from Jon
162 * L. Bentley and M. Douglas McIlroy's "Engineering a Sort Function",
163 * Software-Practice and Experience, Vol. 23(11) P. 1249-1265 (November
164 * 1993). This algorithm offers n*log(n) performance on many data sets
165 * that cause other quicksorts to degrade to quadratic performance.
166 *
167 * @param a the array to be sorted
168 * @param fromIndex the index of the first element (inclusive) to be
169 * sorted
170 * @param toIndex the index of the last element (exclusive) to be sorted
171 * @throws IllegalArgumentException if <tt>fromIndex > toIndex</tt>
172 * @throws ArrayIndexOutOfBoundsException if <tt>fromIndex < 0</tt> or
173 * <tt>toIndex > a.length</tt>
174 */
175 public static void sort(short[] a, int fromIndex, int toIndex) {
176 rangeCheck(a.length, fromIndex, toIndex);
177 sort1(a, fromIndex, toIndex-fromIndex);
178 }
179
180 /**
181 * Sorts the specified array of chars into ascending numerical order.
182 * The sorting algorithm is a tuned quicksort, adapted from Jon
183 * L. Bentley and M. Douglas McIlroy's "Engineering a Sort Function",
184 * Software-Practice and Experience, Vol. 23(11) P. 1249-1265 (November
185 * 1993). This algorithm offers n*log(n) performance on many data sets
186 * that cause other quicksorts to degrade to quadratic performance.
187 *
188 * @param a the array to be sorted
189 */
190 public static void sort(char[] a) {
191 sort1(a, 0, a.length);
192 }
193
194 /**
195 * Sorts the specified range of the specified array of chars into
196 * ascending numerical order. The range to be sorted extends from index
197 * <tt>fromIndex</tt>, inclusive, to index <tt>toIndex</tt>, exclusive.
198 * (If <tt>fromIndex==toIndex</tt>, the range to be sorted is empty.)<p>
199 *
200 * The sorting algorithm is a tuned quicksort, adapted from Jon
201 * L. Bentley and M. Douglas McIlroy's "Engineering a Sort Function",
202 * Software-Practice and Experience, Vol. 23(11) P. 1249-1265 (November
203 * 1993). This algorithm offers n*log(n) performance on many data sets
204 * that cause other quicksorts to degrade to quadratic performance.
205 *
206 * @param a the array to be sorted
207 * @param fromIndex the index of the first element (inclusive) to be
208 * sorted
209 * @param toIndex the index of the last element (exclusive) to be sorted
210 * @throws IllegalArgumentException if <tt>fromIndex > toIndex</tt>
211 * @throws ArrayIndexOutOfBoundsException if <tt>fromIndex < 0</tt> or
212 * <tt>toIndex > a.length</tt>
213 */
214 public static void sort(char[] a, int fromIndex, int toIndex) {
215 rangeCheck(a.length, fromIndex, toIndex);
216 sort1(a, fromIndex, toIndex-fromIndex);
217 }
218
219 /**
220 * Sorts the specified array of bytes into ascending numerical order.
221 * The sorting algorithm is a tuned quicksort, adapted from Jon
222 * L. Bentley and M. Douglas McIlroy's "Engineering a Sort Function",
223 * Software-Practice and Experience, Vol. 23(11) P. 1249-1265 (November
224 * 1993). This algorithm offers n*log(n) performance on many data sets
225 * that cause other quicksorts to degrade to quadratic performance.
226 *
227 * @param a the array to be sorted
228 */
229 public static void sort(byte[] a) {
230 sort1(a, 0, a.length);
231 }
232
233 /**
234 * Sorts the specified range of the specified array of bytes into
235 * ascending numerical order. The range to be sorted extends from index
236 * <tt>fromIndex</tt>, inclusive, to index <tt>toIndex</tt>, exclusive.
237 * (If <tt>fromIndex==toIndex</tt>, the range to be sorted is empty.)<p>
238 *
239 * The sorting algorithm is a tuned quicksort, adapted from Jon
240 * L. Bentley and M. Douglas McIlroy's "Engineering a Sort Function",
241 * Software-Practice and Experience, Vol. 23(11) P. 1249-1265 (November
242 * 1993). This algorithm offers n*log(n) performance on many data sets
243 * that cause other quicksorts to degrade to quadratic performance.
244 *
245 * @param a the array to be sorted
246 * @param fromIndex the index of the first element (inclusive) to be
247 * sorted
248 * @param toIndex the index of the last element (exclusive) to be sorted
249 * @throws IllegalArgumentException if <tt>fromIndex > toIndex</tt>
250 * @throws ArrayIndexOutOfBoundsException if <tt>fromIndex < 0</tt> or
251 * <tt>toIndex > a.length</tt>
252 */
253 public static void sort(byte[] a, int fromIndex, int toIndex) {
254 rangeCheck(a.length, fromIndex, toIndex);
255 sort1(a, fromIndex, toIndex-fromIndex);
256 }
257
258 /**
259 * Sorts the specified array of doubles into ascending numerical order.
260 * <p>
261 * The <code><</code> relation does not provide a total order on
262 * all floating-point values; although they are distinct numbers
263 * <code>-0.0 == 0.0</code> is <code>true</code> and a NaN value
264 * compares neither less than, greater than, nor equal to any
265 * floating-point value, even itself. To allow the sort to
266 * proceed, instead of using the <code><</code> relation to
267 * determine ascending numerical order, this method uses the total
268 * order imposed by {@link Double#compareTo}. This ordering
269 * differs from the <code><</code> relation in that
270 * <code>-0.0</code> is treated as less than <code>0.0</code> and
271 * NaN is considered greater than any other floating-point value.
272 * For the purposes of sorting, all NaN values are considered
273 * equivalent and equal.
274 * <p>
275 * The sorting algorithm is a tuned quicksort, adapted from Jon
276 * L. Bentley and M. Douglas McIlroy's "Engineering a Sort Function",
277 * Software-Practice and Experience, Vol. 23(11) P. 1249-1265 (November
278 * 1993). This algorithm offers n*log(n) performance on many data sets
279 * that cause other quicksorts to degrade to quadratic performance.
280 *
281 * @param a the array to be sorted
282 */
283 public static void sort(double[] a) {
284 sort2(a, 0, a.length);
285 }
286
287 /**
288 * Sorts the specified range of the specified array of doubles into
289 * ascending numerical order. The range to be sorted extends from index
290 * <tt>fromIndex</tt>, inclusive, to index <tt>toIndex</tt>, exclusive.
291 * (If <tt>fromIndex==toIndex</tt>, the range to be sorted is empty.)
292 * <p>
293 * The <code><</code> relation does not provide a total order on
294 * all floating-point values; although they are distinct numbers
295 * <code>-0.0 == 0.0</code> is <code>true</code> and a NaN value
296 * compares neither less than, greater than, nor equal to any
297 * floating-point value, even itself. To allow the sort to
298 * proceed, instead of using the <code><</code> relation to
299 * determine ascending numerical order, this method uses the total
300 * order imposed by {@link Double#compareTo}. This ordering
301 * differs from the <code><</code> relation in that
302 * <code>-0.0</code> is treated as less than <code>0.0</code> and
303 * NaN is considered greater than any other floating-point value.
304 * For the purposes of sorting, all NaN values are considered
305 * equivalent and equal.
306 * <p>
307 * The sorting algorithm is a tuned quicksort, adapted from Jon
308 * L. Bentley and M. Douglas McIlroy's "Engineering a Sort Function",
309 * Software-Practice and Experience, Vol. 23(11) P. 1249-1265 (November
310 * 1993). This algorithm offers n*log(n) performance on many data sets
311 * that cause other quicksorts to degrade to quadratic performance.
312 *
313 * @param a the array to be sorted
314 * @param fromIndex the index of the first element (inclusive) to be
315 * sorted
316 * @param toIndex the index of the last element (exclusive) to be sorted
317 * @throws IllegalArgumentException if <tt>fromIndex > toIndex</tt>
318 * @throws ArrayIndexOutOfBoundsException if <tt>fromIndex < 0</tt> or
319 * <tt>toIndex > a.length</tt>
320 */
321 public static void sort(double[] a, int fromIndex, int toIndex) {
322 rangeCheck(a.length, fromIndex, toIndex);
323 sort2(a, fromIndex, toIndex);
324 }
325
326 /**
327 * Sorts the specified array of floats into ascending numerical order.
328 * <p>
329 * The <code><</code> relation does not provide a total order on
330 * all floating-point values; although they are distinct numbers
331 * <code>-0.0f == 0.0f</code> is <code>true</code> and a NaN value
332 * compares neither less than, greater than, nor equal to any
333 * floating-point value, even itself. To allow the sort to
334 * proceed, instead of using the <code><</code> relation to
335 * determine ascending numerical order, this method uses the total
336 * order imposed by {@link Float#compareTo}. This ordering
337 * differs from the <code><</code> relation in that
338 * <code>-0.0f</code> is treated as less than <code>0.0f</code> and
339 * NaN is considered greater than any other floating-point value.
340 * For the purposes of sorting, all NaN values are considered
341 * equivalent and equal.
342 * <p>
343 * The sorting algorithm is a tuned quicksort, adapted from Jon
344 * L. Bentley and M. Douglas McIlroy's "Engineering a Sort Function",
345 * Software-Practice and Experience, Vol. 23(11) P. 1249-1265 (November
346 * 1993). This algorithm offers n*log(n) performance on many data sets
347 * that cause other quicksorts to degrade to quadratic performance.
348 *
349 * @param a the array to be sorted
350 */
351 public static void sort(float[] a) {
352 sort2(a, 0, a.length);
353 }
354
355 /**
356 * Sorts the specified range of the specified array of floats into
357 * ascending numerical order. The range to be sorted extends from index
358 * <tt>fromIndex</tt>, inclusive, to index <tt>toIndex</tt>, exclusive.
359 * (If <tt>fromIndex==toIndex</tt>, the range to be sorted is empty.)
360 * <p>
361 * The <code><</code> relation does not provide a total order on
362 * all floating-point values; although they are distinct numbers
363 * <code>-0.0f == 0.0f</code> is <code>true</code> and a NaN value
364 * compares neither less than, greater than, nor equal to any
365 * floating-point value, even itself. To allow the sort to
366 * proceed, instead of using the <code><</code> relation to
367 * determine ascending numerical order, this method uses the total
368 * order imposed by {@link Float#compareTo}. This ordering
369 * differs from the <code><</code> relation in that
370 * <code>-0.0f</code> is treated as less than <code>0.0f</code> and
371 * NaN is considered greater than any other floating-point value.
372 * For the purposes of sorting, all NaN values are considered
373 * equivalent and equal.
374 * <p>
375 * The sorting algorithm is a tuned quicksort, adapted from Jon
376 * L. Bentley and M. Douglas McIlroy's "Engineering a Sort Function",
377 * Software-Practice and Experience, Vol. 23(11) P. 1249-1265 (November
378 * 1993). This algorithm offers n*log(n) performance on many data sets
379 * that cause other quicksorts to degrade to quadratic performance.
380 *
381 * @param a the array to be sorted
382 * @param fromIndex the index of the first element (inclusive) to be
383 * sorted
384 * @param toIndex the index of the last element (exclusive) to be sorted
385 * @throws IllegalArgumentException if <tt>fromIndex > toIndex</tt>
386 * @throws ArrayIndexOutOfBoundsException if <tt>fromIndex < 0</tt> or
387 * <tt>toIndex > a.length</tt>
388 */
389 public static void sort(float[] a, int fromIndex, int toIndex) {
390 rangeCheck(a.length, fromIndex, toIndex);
391 sort2(a, fromIndex, toIndex);
392 }
393
394 private static void sort2(double a[], int fromIndex, int toIndex) {
395 final long NEG_ZERO_BITS = Double.doubleToLongBits(-0.0d);
396 /*
397 * The sort is done in three phases to avoid the expense of using
398 * NaN and -0.0 aware comparisons during the main sort.
399 */
400
401 /*
402 * Preprocessing phase: Move any NaN's to end of array, count the
403 * number of -0.0's, and turn them into 0.0's.
404 */
405 int numNegZeros = 0;
406 int i = fromIndex, n = toIndex;
407 while(i < n) {
408 if (a[i] != a[i]) {
409 swap(a, i, --n);
410 } else {
411 if (a[i]==0 && Double.doubleToLongBits(a[i])==NEG_ZERO_BITS) {
412 a[i] = 0.0d;
413 numNegZeros++;
414 }
415 i++;
416 }
417 }
418
419 // Main sort phase: quicksort everything but the NaN's
420 sort1(a, fromIndex, n-fromIndex);
421
422 // Postprocessing phase: change 0.0's to -0.0's as required
423 if (numNegZeros != 0) {
424 int j = binarySearch0(a, fromIndex, n, 0.0d); // posn of ANY zero
425 do {
426 j--;
427 } while (j>=fromIndex && a[j]==0.0d);
428
429 // j is now one less than the index of the FIRST zero
430 for (int k=0; k<numNegZeros; k++)
431 a[++j] = -0.0d;
432 }
433 }
434
435
436 private static void sort2(float a[], int fromIndex, int toIndex) {
437 final int NEG_ZERO_BITS = Float.floatToIntBits(-0.0f);
438 /*
439 * The sort is done in three phases to avoid the expense of using
440 * NaN and -0.0 aware comparisons during the main sort.
441 */
442
443 /*
444 * Preprocessing phase: Move any NaN's to end of array, count the
445 * number of -0.0's, and turn them into 0.0's.
446 */
447 int numNegZeros = 0;
448 int i = fromIndex, n = toIndex;
449 while(i < n) {
450 if (a[i] != a[i]) {
451 swap(a, i, --n);
452 } else {
453 if (a[i]==0 && Float.floatToIntBits(a[i])==NEG_ZERO_BITS) {
454 a[i] = 0.0f;
455 numNegZeros++;
456 }
457 i++;
458 }
459 }
460
461 // Main sort phase: quicksort everything but the NaN's
462 sort1(a, fromIndex, n-fromIndex);
463
464 // Postprocessing phase: change 0.0's to -0.0's as required
465 if (numNegZeros != 0) {
466 int j = binarySearch0(a, fromIndex, n, 0.0f); // posn of ANY zero
467 do {
468 j--;
469 } while (j>=fromIndex && a[j]==0.0f);
470
471 // j is now one less than the index of the FIRST zero
472 for (int k=0; k<numNegZeros; k++)
473 a[++j] = -0.0f;
474 }
475 }
476
477
478 /*
479 * The code for each of the seven primitive types is largely identical.
480 * C'est la vie.
481 */
482
483 /**
484 * Sorts the specified sub-array of longs into ascending order.
485 */
486 private static void sort1(long x[], int off, int len) {
487 // Insertion sort on smallest arrays
488 if (len < 7) {
489 for (int i=off; i<len+off; i++)
490 for (int j=i; j>off && x[j-1]>x[j]; j--)
491 swap(x, j, j-1);
492 return;
493 }
494
495 // Choose a partition element, v
496 int m = off + (len >> 1); // Small arrays, middle element
497 if (len > 7) {
498 int l = off;
499 int n = off + len - 1;
500 if (len > 40) { // Big arrays, pseudomedian of 9
501 int s = len/8;
502 l = med3(x, l, l+s, l+2*s);
503 m = med3(x, m-s, m, m+s);
504 n = med3(x, n-2*s, n-s, n);
505 }
506 m = med3(x, l, m, n); // Mid-size, med of 3
507 }
508 long v = x[m];
509
510 // Establish Invariant: v* (<v)* (>v)* v*
511 int a = off, b = a, c = off + len - 1, d = c;
512 while(true) {
513 while (b <= c && x[b] <= v) {
514 if (x[b] == v)
515 swap(x, a++, b);
516 b++;
517 }
518 while (c >= b && x[c] >= v) {
519 if (x[c] == v)
520 swap(x, c, d--);
521 c--;
522 }
523 if (b > c)
524 break;
525 swap(x, b++, c--);
526 }
527
528 // Swap partition elements back to middle
529 int s, n = off + len;
530 s = Math.min(a-off, b-a ); vecswap(x, off, b-s, s);
531 s = Math.min(d-c, n-d-1); vecswap(x, b, n-s, s);
532
533 // Recursively sort non-partition-elements
534 if ((s = b-a) > 1)
535 sort1(x, off, s);
536 if ((s = d-c) > 1)
537 sort1(x, n-s, s);
538 }
539
540 /**
541 * Swaps x[a] with x[b].
542 */
543 private static void swap(long x[], int a, int b) {
544 long t = x[a];
545 x[a] = x[b];
546 x[b] = t;
547 }
548
549 /**
550 * Swaps x[a .. (a+n-1)] with x[b .. (b+n-1)].
551 */
552 private static void vecswap(long x[], int a, int b, int n) {
553 for (int i=0; i<n; i++, a++, b++)
554 swap(x, a, b);
555 }
556
557 /**
558 * Returns the index of the median of the three indexed longs.
559 */
560 private static int med3(long x[], int a, int b, int c) {
561 return (x[a] < x[b] ?
562 (x[b] < x[c] ? b : x[a] < x[c] ? c : a) :
563 (x[b] > x[c] ? b : x[a] > x[c] ? c : a));
564 }
565
566 /**
567 * Sorts the specified sub-array of integers into ascending order.
568 */
569 private static void sort1(int x[], int off, int len) {
570 // Insertion sort on smallest arrays
571 if (len < 7) {
572 for (int i=off; i<len+off; i++)
573 for (int j=i; j>off && x[j-1]>x[j]; j--)
574 swap(x, j, j-1);
575 return;
576 }
577
578 // Choose a partition element, v
579 int m = off + (len >> 1); // Small arrays, middle element
580 if (len > 7) {
581 int l = off;
582 int n = off + len - 1;
583 if (len > 40) { // Big arrays, pseudomedian of 9
584 int s = len/8;
585 l = med3(x, l, l+s, l+2*s);
586 m = med3(x, m-s, m, m+s);
587 n = med3(x, n-2*s, n-s, n);
588 }
589 m = med3(x, l, m, n); // Mid-size, med of 3
590 }
591 int v = x[m];
592
593 // Establish Invariant: v* (<v)* (>v)* v*
594 int a = off, b = a, c = off + len - 1, d = c;
595 while(true) {
596 while (b <= c && x[b] <= v) {
597 if (x[b] == v)
598 swap(x, a++, b);
599 b++;
600 }
601 while (c >= b && x[c] >= v) {
602 if (x[c] == v)
603 swap(x, c, d--);
604 c--;
605 }
606 if (b > c)
607 break;
608 swap(x, b++, c--);
609 }
610
611 // Swap partition elements back to middle
612 int s, n = off + len;
613 s = Math.min(a-off, b-a ); vecswap(x, off, b-s, s);
614 s = Math.min(d-c, n-d-1); vecswap(x, b, n-s, s);
615
616 // Recursively sort non-partition-elements
617 if ((s = b-a) > 1)
618 sort1(x, off, s);
619 if ((s = d-c) > 1)
620 sort1(x, n-s, s);
621 }
622
623 /**
624 * Swaps x[a] with x[b].
625 */
626 private static void swap(int x[], int a, int b) {
627 int t = x[a];
628 x[a] = x[b];
629 x[b] = t;
630 }
631
632 /**
633 * Swaps x[a .. (a+n-1)] with x[b .. (b+n-1)].
634 */
635 private static void vecswap(int x[], int a, int b, int n) {
636 for (int i=0; i<n; i++, a++, b++)
637 swap(x, a, b);
638 }
639
640 /**
641 * Returns the index of the median of the three indexed integers.
642 */
643 private static int med3(int x[], int a, int b, int c) {
644 return (x[a] < x[b] ?
645 (x[b] < x[c] ? b : x[a] < x[c] ? c : a) :
646 (x[b] > x[c] ? b : x[a] > x[c] ? c : a));
647 }
648
649 /**
650 * Sorts the specified sub-array of shorts into ascending order.
651 */
652 private static void sort1(short x[], int off, int len) {
653 // Insertion sort on smallest arrays
654 if (len < 7) {
655 for (int i=off; i<len+off; i++)
656 for (int j=i; j>off && x[j-1]>x[j]; j--)
657 swap(x, j, j-1);
658 return;
659 }
660
661 // Choose a partition element, v
662 int m = off + (len >> 1); // Small arrays, middle element
663 if (len > 7) {
664 int l = off;
665 int n = off + len - 1;
666 if (len > 40) { // Big arrays, pseudomedian of 9
667 int s = len/8;
668 l = med3(x, l, l+s, l+2*s);
669 m = med3(x, m-s, m, m+s);
670 n = med3(x, n-2*s, n-s, n);
671 }
672 m = med3(x, l, m, n); // Mid-size, med of 3
673 }
674 short v = x[m];
675
676 // Establish Invariant: v* (<v)* (>v)* v*
677 int a = off, b = a, c = off + len - 1, d = c;
678 while(true) {
679 while (b <= c && x[b] <= v) {
680 if (x[b] == v)
681 swap(x, a++, b);
682 b++;
683 }
684 while (c >= b && x[c] >= v) {
685 if (x[c] == v)
686 swap(x, c, d--);
687 c--;
688 }
689 if (b > c)
690 break;
691 swap(x, b++, c--);
692 }
693
694 // Swap partition elements back to middle
695 int s, n = off + len;
696 s = Math.min(a-off, b-a ); vecswap(x, off, b-s, s);
697 s = Math.min(d-c, n-d-1); vecswap(x, b, n-s, s);
698
699 // Recursively sort non-partition-elements
700 if ((s = b-a) > 1)
701 sort1(x, off, s);
702 if ((s = d-c) > 1)
703 sort1(x, n-s, s);
704 }
705
706 /**
707 * Swaps x[a] with x[b].
708 */
709 private static void swap(short x[], int a, int b) {
710 short t = x[a];
711 x[a] = x[b];
712 x[b] = t;
713 }
714
715 /**
716 * Swaps x[a .. (a+n-1)] with x[b .. (b+n-1)].
717 */
718 private static void vecswap(short x[], int a, int b, int n) {
719 for (int i=0; i<n; i++, a++, b++)
720 swap(x, a, b);
721 }
722
723 /**
724 * Returns the index of the median of the three indexed shorts.
725 */
726 private static int med3(short x[], int a, int b, int c) {
727 return (x[a] < x[b] ?
728 (x[b] < x[c] ? b : x[a] < x[c] ? c : a) :
729 (x[b] > x[c] ? b : x[a] > x[c] ? c : a));
730 }
731
732
733 /**
734 * Sorts the specified sub-array of chars into ascending order.
735 */
736 private static void sort1(char x[], int off, int len) {
737 // Insertion sort on smallest arrays
738 if (len < 7) {
739 for (int i=off; i<len+off; i++)
740 for (int j=i; j>off && x[j-1]>x[j]; j--)
741 swap(x, j, j-1);
742 return;
743 }
744
745 // Choose a partition element, v
746 int m = off + (len >> 1); // Small arrays, middle element
747 if (len > 7) {
748 int l = off;
749 int n = off + len - 1;
750 if (len > 40) { // Big arrays, pseudomedian of 9
751 int s = len/8;
752 l = med3(x, l, l+s, l+2*s);
753 m = med3(x, m-s, m, m+s);
754 n = med3(x, n-2*s, n-s, n);
755 }
756 m = med3(x, l, m, n); // Mid-size, med of 3
757 }
758 char v = x[m];
759
760 // Establish Invariant: v* (<v)* (>v)* v*
761 int a = off, b = a, c = off + len - 1, d = c;
762 while(true) {
763 while (b <= c && x[b] <= v) {
764 if (x[b] == v)
765 swap(x, a++, b);
766 b++;
767 }
768 while (c >= b && x[c] >= v) {
769 if (x[c] == v)
770 swap(x, c, d--);
771 c--;
772 }
773 if (b > c)
774 break;
775 swap(x, b++, c--);
776 }
777
778 // Swap partition elements back to middle
779 int s, n = off + len;
780 s = Math.min(a-off, b-a ); vecswap(x, off, b-s, s);
781 s = Math.min(d-c, n-d-1); vecswap(x, b, n-s, s);
782
783 // Recursively sort non-partition-elements
784 if ((s = b-a) > 1)
785 sort1(x, off, s);
786 if ((s = d-c) > 1)
787 sort1(x, n-s, s);
788 }
789
790 /**
791 * Swaps x[a] with x[b].
792 */
793 private static void swap(char x[], int a, int b) {
794 char t = x[a];
795 x[a] = x[b];
796 x[b] = t;
797 }
798
799 /**
800 * Swaps x[a .. (a+n-1)] with x[b .. (b+n-1)].
801 */
802 private static void vecswap(char x[], int a, int b, int n) {
803 for (int i=0; i<n; i++, a++, b++)
804 swap(x, a, b);
805 }
806
807 /**
808 * Returns the index of the median of the three indexed chars.
809 */
810 private static int med3(char x[], int a, int b, int c) {
811 return (x[a] < x[b] ?
812 (x[b] < x[c] ? b : x[a] < x[c] ? c : a) :
813 (x[b] > x[c] ? b : x[a] > x[c] ? c : a));
814 }
815
816
817 /**
818 * Sorts the specified sub-array of bytes into ascending order.
819 */
820 private static void sort1(byte x[], int off, int len) {
821 // Insertion sort on smallest arrays
822 if (len < 7) {
823 for (int i=off; i<len+off; i++)
824 for (int j=i; j>off && x[j-1]>x[j]; j--)
825 swap(x, j, j-1);
826 return;
827 }
828
829 // Choose a partition element, v
830 int m = off + (len >> 1); // Small arrays, middle element
831 if (len > 7) {
832 int l = off;
833 int n = off + len - 1;
834 if (len > 40) { // Big arrays, pseudomedian of 9
835 int s = len/8;
836 l = med3(x, l, l+s, l+2*s);
837 m = med3(x, m-s, m, m+s);
838 n = med3(x, n-2*s, n-s, n);
839 }
840 m = med3(x, l, m, n); // Mid-size, med of 3
841 }
842 byte v = x[m];
843
844 // Establish Invariant: v* (<v)* (>v)* v*
845 int a = off, b = a, c = off + len - 1, d = c;
846 while(true) {
847 while (b <= c && x[b] <= v) {
848 if (x[b] == v)
849 swap(x, a++, b);
850 b++;
851 }
852 while (c >= b && x[c] >= v) {
853 if (x[c] == v)
854 swap(x, c, d--);
855 c--;
856 }
857 if (b > c)
858 break;
859 swap(x, b++, c--);
860 }
861
862 // Swap partition elements back to middle
863 int s, n = off + len;
864 s = Math.min(a-off, b-a ); vecswap(x, off, b-s, s);
865 s = Math.min(d-c, n-d-1); vecswap(x, b, n-s, s);
866
867 // Recursively sort non-partition-elements
868 if ((s = b-a) > 1)
869 sort1(x, off, s);
870 if ((s = d-c) > 1)
871 sort1(x, n-s, s);
872 }
873
874 /**
875 * Swaps x[a] with x[b].
876 */
877 private static void swap(byte x[], int a, int b) {
878 byte t = x[a];
879 x[a] = x[b];
880 x[b] = t;
881 }
882
883 /**
884 * Swaps x[a .. (a+n-1)] with x[b .. (b+n-1)].
885 */
886 private static void vecswap(byte x[], int a, int b, int n) {
887 for (int i=0; i<n; i++, a++, b++)
888 swap(x, a, b);
889 }
890
891 /**
892 * Returns the index of the median of the three indexed bytes.
893 */
894 private static int med3(byte x[], int a, int b, int c) {
895 return (x[a] < x[b] ?
896 (x[b] < x[c] ? b : x[a] < x[c] ? c : a) :
897 (x[b] > x[c] ? b : x[a] > x[c] ? c : a));
898 }
899
900
901 /**
902 * Sorts the specified sub-array of doubles into ascending order.
903 */
904 private static void sort1(double x[], int off, int len) {
905 // Insertion sort on smallest arrays
906 if (len < 7) {
907 for (int i=off; i<len+off; i++)
908 for (int j=i; j>off && x[j-1]>x[j]; j--)
909 swap(x, j, j-1);
910 return;
911 }
912
913 // Choose a partition element, v
914 int m = off + (len >> 1); // Small arrays, middle element
915 if (len > 7) {
916 int l = off;
917 int n = off + len - 1;
918 if (len > 40) { // Big arrays, pseudomedian of 9
919 int s = len/8;
920 l = med3(x, l, l+s, l+2*s);
921 m = med3(x, m-s, m, m+s);
922 n = med3(x, n-2*s, n-s, n);
923 }
924 m = med3(x, l, m, n); // Mid-size, med of 3
925 }
926 double v = x[m];
927
928 // Establish Invariant: v* (<v)* (>v)* v*
929 int a = off, b = a, c = off + len - 1, d = c;
930 while(true) {
931 while (b <= c && x[b] <= v) {
932 if (x[b] == v)
933 swap(x, a++, b);
934 b++;
935 }
936 while (c >= b && x[c] >= v) {
937 if (x[c] == v)
938 swap(x, c, d--);
939 c--;
940 }
941 if (b > c)
942 break;
943 swap(x, b++, c--);
944 }
945
946 // Swap partition elements back to middle
947 int s, n = off + len;
948 s = Math.min(a-off, b-a ); vecswap(x, off, b-s, s);
949 s = Math.min(d-c, n-d-1); vecswap(x, b, n-s, s);
950
951 // Recursively sort non-partition-elements
952 if ((s = b-a) > 1)
953 sort1(x, off, s);
954 if ((s = d-c) > 1)
955 sort1(x, n-s, s);
956 }
957
958 /**
959 * Swaps x[a] with x[b].
960 */
961 private static void swap(double x[], int a, int b) {
962 double t = x[a];
963 x[a] = x[b];
964 x[b] = t;
965 }
966
967 /**
968 * Swaps x[a .. (a+n-1)] with x[b .. (b+n-1)].
969 */
970 private static void vecswap(double x[], int a, int b, int n) {
971 for (int i=0; i<n; i++, a++, b++)
972 swap(x, a, b);
973 }
974
975 /**
976 * Returns the index of the median of the three indexed doubles.
977 */
978 private static int med3(double x[], int a, int b, int c) {
979 return (x[a] < x[b] ?
980 (x[b] < x[c] ? b : x[a] < x[c] ? c : a) :
981 (x[b] > x[c] ? b : x[a] > x[c] ? c : a));
982 }
983
984
985 /**
986 * Sorts the specified sub-array of floats into ascending order.
987 */
988 private static void sort1(float x[], int off, int len) {
989 // Insertion sort on smallest arrays
990 if (len < 7) {
991 for (int i=off; i<len+off; i++)
992 for (int j=i; j>off && x[j-1]>x[j]; j--)
993 swap(x, j, j-1);
994 return;
995 }
996
997 // Choose a partition element, v
998 int m = off + (len >> 1); // Small arrays, middle element
999 if (len > 7) {
1000 int l = off;
1001 int n = off + len - 1;
1002 if (len > 40) { // Big arrays, pseudomedian of 9
1003 int s = len/8;
1004 l = med3(x, l, l+s, l+2*s);
1005 m = med3(x, m-s, m, m+s);
1006 n = med3(x, n-2*s, n-s, n);
1007 }
1008 m = med3(x, l, m, n); // Mid-size, med of 3
1009 }
1010 float v = x[m];
1011
1012 // Establish Invariant: v* (<v)* (>v)* v*
1013 int a = off, b = a, c = off + len - 1, d = c;
1014 while(true) {
1015 while (b <= c && x[b] <= v) {
1016 if (x[b] == v)
1017 swap(x, a++, b);
1018 b++;
1019 }
1020 while (c >= b && x[c] >= v) {
1021 if (x[c] == v)
1022 swap(x, c, d--);
1023 c--;
1024 }
1025 if (b > c)
1026 break;
1027 swap(x, b++, c--);
1028 }
1029
1030 // Swap partition elements back to middle
1031 int s, n = off + len;
1032 s = Math.min(a-off, b-a ); vecswap(x, off, b-s, s);
1033 s = Math.min(d-c, n-d-1); vecswap(x, b, n-s, s);
1034
1035 // Recursively sort non-partition-elements
1036 if ((s = b-a) > 1)
1037 sort1(x, off, s);
1038 if ((s = d-c) > 1)
1039 sort1(x, n-s, s);
1040 }
1041
1042 /**
1043 * Swaps x[a] with x[b].
1044 */
1045 private static void swap(float x[], int a, int b) {
1046 float t = x[a];
1047 x[a] = x[b];
1048 x[b] = t;
1049 }
1050
1051 /**
1052 * Swaps x[a .. (a+n-1)] with x[b .. (b+n-1)].
1053 */
1054 private static void vecswap(float x[], int a, int b, int n) {
1055 for (int i=0; i<n; i++, a++, b++)
1056 swap(x, a, b);
1057 }
1058
1059 /**
1060 * Returns the index of the median of the three indexed floats.
1061 */
1062 private static int med3(float x[], int a, int b, int c) {
1063 return (x[a] < x[b] ?
1064 (x[b] < x[c] ? b : x[a] < x[c] ? c : a) :
1065 (x[b] > x[c] ? b : x[a] > x[c] ? c : a));
1066 }
1067
1068
1069 /**
1070 * Sorts the specified array of objects into ascending order, according to
1071 * the {@linkplain Comparable natural ordering}
1072 * of its elements. All elements in the array
1073 * must implement the {@link Comparable} interface. Furthermore, all
1074 * elements in the array must be <i>mutually comparable</i> (that is,
1075 * <tt>e1.compareTo(e2)</tt> must not throw a <tt>ClassCastException</tt>
1076 * for any elements <tt>e1</tt> and <tt>e2</tt> in the array).<p>
1077 *
1078 * This sort is guaranteed to be <i>stable</i>: equal elements will
1079 * not be reordered as a result of the sort.<p>
1080 *
1081 * The sorting algorithm is a modified mergesort (in which the merge is
1082 * omitted if the highest element in the low sublist is less than the
1083 * lowest element in the high sublist). This algorithm offers guaranteed
1084 * n*log(n) performance.
1085 *
1086 * @param a the array to be sorted
1087 * @throws ClassCastException if the array contains elements that are not
1088 * <i>mutually comparable</i> (for example, strings and integers).
1089 */
1090 public static void sort(Object[] a) {
1091 Object[] aux = a.clone();
1092 mergeSort(aux, a, 0, a.length, 0);
1093 }
1094
1095 /**
1096 * Sorts the specified range of the specified array of objects into
1097 * ascending order, according to the
1098 * {@linkplain Comparable natural ordering} of its
1099 * elements. The range to be sorted extends from index
1100 * <tt>fromIndex</tt>, inclusive, to index <tt>toIndex</tt>, exclusive.
1101 * (If <tt>fromIndex==toIndex</tt>, the range to be sorted is empty.) All
1102 * elements in this range must implement the {@link Comparable}
1103 * interface. Furthermore, all elements in this range must be <i>mutually
1104 * comparable</i> (that is, <tt>e1.compareTo(e2)</tt> must not throw a
1105 * <tt>ClassCastException</tt> for any elements <tt>e1</tt> and
1106 * <tt>e2</tt> in the array).<p>
1107 *
1108 * This sort is guaranteed to be <i>stable</i>: equal elements will
1109 * not be reordered as a result of the sort.<p>
1110 *
1111 * The sorting algorithm is a modified mergesort (in which the merge is
1112 * omitted if the highest element in the low sublist is less than the
1113 * lowest element in the high sublist). This algorithm offers guaranteed
1114 * n*log(n) performance.
1115 *
1116 * @param a the array to be sorted
1117 * @param fromIndex the index of the first element (inclusive) to be
1118 * sorted
1119 * @param toIndex the index of the last element (exclusive) to be sorted
1120 * @throws IllegalArgumentException if <tt>fromIndex > toIndex</tt>
1121 * @throws ArrayIndexOutOfBoundsException if <tt>fromIndex < 0</tt> or
1122 * <tt>toIndex > a.length</tt>
1123 * @throws ClassCastException if the array contains elements that are
1124 * not <i>mutually comparable</i> (for example, strings and
1125 * integers).
1126 */
1127 public static void sort(Object[] a, int fromIndex, int toIndex) {
1128 rangeCheck(a.length, fromIndex, toIndex);
1129 Object[] aux = copyOfRange(a, fromIndex, toIndex);
1130 mergeSort(aux, a, fromIndex, toIndex, -fromIndex);
1131 }
1132
1133 /**
1134 * Tuning parameter: list size at or below which insertion sort will be
1135 * used in preference to mergesort or quicksort.
1136 */
1137 private static final int INSERTIONSORT_THRESHOLD = 7;
1138
1139 /**
1140 * Src is the source array that starts at index 0
1141 * Dest is the (possibly larger) array destination with a possible offset
1142 * low is the index in dest to start sorting
1143 * high is the end index in dest to end sorting
1144 * off is the offset to generate corresponding low, high in src
1145 */
1146 private static void mergeSort(Object[] src,
1147 Object[] dest,
1148 int low,
1149 int high,
1150 int off) {
1151 int length = high - low;
1152
1153 // Insertion sort on smallest arrays
1154 if (length < INSERTIONSORT_THRESHOLD) {
1155 for (int i=low; i<high; i++)
1156 for (int j=i; j>low &&
1157 ((Comparable) dest[j-1]).compareTo(dest[j])>0; j--)
1158 swap(dest, j, j-1);
1159 return;
1160 }
1161
1162 // Recursively sort halves of dest into src
1163 int destLow = low;
1164 int destHigh = high;
1165 low += off;
1166 high += off;
1167 int mid = (low + high) >>> 1;
1168 mergeSort(dest, src, low, mid, -off);
1169 mergeSort(dest, src, mid, high, -off);
1170
1171 // If list is already sorted, just copy from src to dest. This is an
1172 // optimization that results in faster sorts for nearly ordered lists.
1173 if (((Comparable)src[mid-1]).compareTo(src[mid]) <= 0) {
1174 System.arraycopy(src, low, dest, destLow, length);
1175 return;
1176 }
1177
1178 // Merge sorted halves (now in src) into dest
1179 for(int i = destLow, p = low, q = mid; i < destHigh; i++) {
1180 if (q >= high || p < mid && ((Comparable)src[p]).compareTo(src[q])<=0)
1181 dest[i] = src[p++];
1182 else
1183 dest[i] = src[q++];
1184 }
1185 }
1186
1187 /**
1188 * Swaps x[a] with x[b].
1189 */
1190 private static void swap(Object[] x, int a, int b) {
1191 Object t = x[a];
1192 x[a] = x[b];
1193 x[b] = t;
1194 }
1195
1196 /**
1197 * Sorts the specified array of objects according to the order induced by
1198 * the specified comparator. All elements in the array must be
1199 * <i>mutually comparable</i> by the specified comparator (that is,
1200 * <tt>c.compare(e1, e2)</tt> must not throw a <tt>ClassCastException</tt>
1201 * for any elements <tt>e1</tt> and <tt>e2</tt> in the array).<p>
1202 *
1203 * This sort is guaranteed to be <i>stable</i>: equal elements will
1204 * not be reordered as a result of the sort.<p>
1205 *
1206 * The sorting algorithm is a modified mergesort (in which the merge is
1207 * omitted if the highest element in the low sublist is less than the
1208 * lowest element in the high sublist). This algorithm offers guaranteed
1209 * n*log(n) performance.
1210 *
1211 * @param a the array to be sorted
1212 * @param c the comparator to determine the order of the array. A
1213 * <tt>null</tt> value indicates that the elements'
1214 * {@linkplain Comparable natural ordering} should be used.
1215 * @throws ClassCastException if the array contains elements that are
1216 * not <i>mutually comparable</i> using the specified comparator.
1217 */
1218 public static <T> void sort(T[] a, Comparator<? super T> c) {
1219 T[] aux = a.clone();
1220 if (c==null)
1221 mergeSort(aux, a, 0, a.length, 0);
1222 else
1223 mergeSort(aux, a, 0, a.length, 0, c);
1224 }
1225
1226 /**
1227 * Sorts the specified range of the specified array of objects according
1228 * to the order induced by the specified comparator. The range to be
1229 * sorted extends from index <tt>fromIndex</tt>, inclusive, to index
1230 * <tt>toIndex</tt>, exclusive. (If <tt>fromIndex==toIndex</tt>, the
1231 * range to be sorted is empty.) All elements in the range must be
1232 * <i>mutually comparable</i> by the specified comparator (that is,
1233 * <tt>c.compare(e1, e2)</tt> must not throw a <tt>ClassCastException</tt>
1234 * for any elements <tt>e1</tt> and <tt>e2</tt> in the range).<p>
1235 *
1236 * This sort is guaranteed to be <i>stable</i>: equal elements will
1237 * not be reordered as a result of the sort.<p>
1238 *
1239 * The sorting algorithm is a modified mergesort (in which the merge is
1240 * omitted if the highest element in the low sublist is less than the
1241 * lowest element in the high sublist). This algorithm offers guaranteed
1242 * n*log(n) performance.
1243 *
1244 * @param a the array to be sorted
1245 * @param fromIndex the index of the first element (inclusive) to be
1246 * sorted
1247 * @param toIndex the index of the last element (exclusive) to be sorted
1248 * @param c the comparator to determine the order of the array. A
1249 * <tt>null</tt> value indicates that the elements'
1250 * {@linkplain Comparable natural ordering} should be used.
1251 * @throws ClassCastException if the array contains elements that are not
1252 * <i>mutually comparable</i> using the specified comparator.
1253 * @throws IllegalArgumentException if <tt>fromIndex > toIndex</tt>
1254 * @throws ArrayIndexOutOfBoundsException if <tt>fromIndex < 0</tt> or
1255 * <tt>toIndex > a.length</tt>
1256 */
1257 public static <T> void sort(T[] a, int fromIndex, int toIndex,
1258 Comparator<? super T> c) {
1259 rangeCheck(a.length, fromIndex, toIndex);
1260 T[] aux = copyOfRange(a, fromIndex, toIndex);
1261 if (c==null)
1262 mergeSort(aux, a, fromIndex, toIndex, -fromIndex);
1263 else
1264 mergeSort(aux, a, fromIndex, toIndex, -fromIndex, c);
1265 }
1266
1267 /**
1268 * Src is the source array that starts at index 0
1269 * Dest is the (possibly larger) array destination with a possible offset
1270 * low is the index in dest to start sorting
1271 * high is the end index in dest to end sorting
1272 * off is the offset into src corresponding to low in dest
1273 */
1274 private static void mergeSort(Object[] src,
1275 Object[] dest,
1276 int low, int high, int off,
1277 Comparator c) {
1278 int length = high - low;
1279
1280 // Insertion sort on smallest arrays
1281 if (length < INSERTIONSORT_THRESHOLD) {
1282 for (int i=low; i<high; i++)
1283 for (int j=i; j>low && c.compare(dest[j-1], dest[j])>0; j--)
1284 swap(dest, j, j-1);
1285 return;
1286 }
1287
1288 // Recursively sort halves of dest into src
1289 int destLow = low;
1290 int destHigh = high;
1291 low += off;
1292 high += off;
1293 int mid = (low + high) >>> 1;
1294 mergeSort(dest, src, low, mid, -off, c);
1295 mergeSort(dest, src, mid, high, -off, c);
1296
1297 // If list is already sorted, just copy from src to dest. This is an
1298 // optimization that results in faster sorts for nearly ordered lists.
1299 if (c.compare(src[mid-1], src[mid]) <= 0) {
1300 System.arraycopy(src, low, dest, destLow, length);
1301 return;
1302 }
1303
1304 // Merge sorted halves (now in src) into dest
1305 for(int i = destLow, p = low, q = mid; i < destHigh; i++) {
1306 if (q >= high || p < mid && c.compare(src[p], src[q]) <= 0)
1307 dest[i] = src[p++];
1308 else
1309 dest[i] = src[q++];
1310 }
1311 }
1312
1313 /**
1314 * Check that fromIndex and toIndex are in range, and throw an
1315 * appropriate exception if they aren't.
1316 */
1317 private static void rangeCheck(int arrayLen, int fromIndex, int toIndex) {
1318 if (fromIndex > toIndex)
1319 throw new IllegalArgumentException("fromIndex(" + fromIndex +
1320 ") > toIndex(" + toIndex+")");
1321 if (fromIndex < 0)
1322 throw new ArrayIndexOutOfBoundsException(fromIndex);
1323 if (toIndex > arrayLen)
1324 throw new ArrayIndexOutOfBoundsException(toIndex);
1325 }
1326
1327 // Searching
1328
1329 /**
1330 * Searches the specified array of longs for the specified value using the
1331 * binary search algorithm. The array must be sorted (as
1332 * by the {@link #sort(long[])} method) prior to making this call. If it
1333 * is not sorted, the results are undefined. If the array contains
1334 * multiple elements with the specified value, there is no guarantee which
1335 * one will be found.
1336 *
1337 * @param a the array to be searched
1338 * @param key the value to be searched for
1339 * @return index of the search key, if it is contained in the array;
1340 * otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>. The
1341 * <i>insertion point</i> is defined as the point at which the
1342 * key would be inserted into the array: the index of the first
1343 * element greater than the key, or <tt>a.length</tt> if all
1344 * elements in the array are less than the specified key. Note
1345 * that this guarantees that the return value will be >= 0 if
1346 * and only if the key is found.
1347 */
1348 public static int binarySearch(long[] a, long key) {
1349 return binarySearch0(a, 0, a.length, key);
1350 }
1351
1352 /**
1353 * Searches a range of
1354 * the specified array of longs for the specified value using the
1355 * binary search algorithm.
1356 * The range must be sorted (as
1357 * by the {@link #sort(long[], int, int)} method)
1358 * prior to making this call. If it
1359 * is not sorted, the results are undefined. If the range contains
1360 * multiple elements with the specified value, there is no guarantee which
1361 * one will be found.
1362 *
1363 * @param a the array to be searched
1364 * @param fromIndex the index of the first element (inclusive) to be
1365 * searched
1366 * @param toIndex the index of the last element (exclusive) to be searched
1367 * @param key the value to be searched for
1368 * @return index of the search key, if it is contained in the array
1369 * within the specified range;
1370 * otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>. The
1371 * <i>insertion point</i> is defined as the point at which the
1372 * key would be inserted into the array: the index of the first
1373 * element in the range greater than the key,
1374 * or <tt>toIndex</tt> if all
1375 * elements in the range are less than the specified key. Note
1376 * that this guarantees that the return value will be >= 0 if
1377 * and only if the key is found.
1378 * @throws IllegalArgumentException
1379 * if {@code fromIndex > toIndex}
1380 * @throws ArrayIndexOutOfBoundsException
1381 * if {@code fromIndex < 0 or toIndex > a.length}
1382 * @since 1.6
1383 */
1384 public static int binarySearch(long[] a, int fromIndex, int toIndex,
1385 long key) {
1386 rangeCheck(a.length, fromIndex, toIndex);
1387 return binarySearch0(a, fromIndex, toIndex, key);
1388 }
1389
1390 // Like public version, but without range checks.
1391 private static int binarySearch0(long[] a, int fromIndex, int toIndex,
1392 long key) {
1393 int low = fromIndex;
1394 int high = toIndex - 1;
1395
1396 while (low <= high) {
1397 int mid = (low + high) >>> 1;
1398 long midVal = a[mid];
1399
1400 if (midVal < key)
1401 low = mid + 1;
1402 else if (midVal > key)
1403 high = mid - 1;
1404 else
1405 return mid; // key found
1406 }
1407 return -(low + 1); // key not found.
1408 }
1409
1410 /**
1411 * Searches the specified array of ints for the specified value using the
1412 * binary search algorithm. The array must be sorted (as
1413 * by the {@link #sort(int[])} method) prior to making this call. If it
1414 * is not sorted, the results are undefined. If the array contains
1415 * multiple elements with the specified value, there is no guarantee which
1416 * one will be found.
1417 *
1418 * @param a the array to be searched
1419 * @param key the value to be searched for
1420 * @return index of the search key, if it is contained in the array;
1421 * otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>. The
1422 * <i>insertion point</i> is defined as the point at which the
1423 * key would be inserted into the array: the index of the first
1424 * element greater than the key, or <tt>a.length</tt> if all
1425 * elements in the array are less than the specified key. Note
1426 * that this guarantees that the return value will be >= 0 if
1427 * and only if the key is found.
1428 */
1429 public static int binarySearch(int[] a, int key) {
1430 return binarySearch0(a, 0, a.length, key);
1431 }
1432
1433 /**
1434 * Searches a range of
1435 * the specified array of ints for the specified value using the
1436 * binary search algorithm.
1437 * The range must be sorted (as
1438 * by the {@link #sort(int[], int, int)} method)
1439 * prior to making this call. If it
1440 * is not sorted, the results are undefined. If the range contains
1441 * multiple elements with the specified value, there is no guarantee which
1442 * one will be found.
1443 *
1444 * @param a the array to be searched
1445 * @param fromIndex the index of the first element (inclusive) to be
1446 * searched
1447 * @param toIndex the index of the last element (exclusive) to be searched
1448 * @param key the value to be searched for
1449 * @return index of the search key, if it is contained in the array
1450 * within the specified range;
1451 * otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>. The
1452 * <i>insertion point</i> is defined as the point at which the
1453 * key would be inserted into the array: the index of the first
1454 * element in the range greater than the key,
1455 * or <tt>toIndex</tt> if all
1456 * elements in the range are less than the specified key. Note
1457 * that this guarantees that the return value will be >= 0 if
1458 * and only if the key is found.
1459 * @throws IllegalArgumentException
1460 * if {@code fromIndex > toIndex}
1461 * @throws ArrayIndexOutOfBoundsException
1462 * if {@code fromIndex < 0 or toIndex > a.length}
1463 * @since 1.6
1464 */
1465 public static int binarySearch(int[] a, int fromIndex, int toIndex,
1466 int key) {
1467 rangeCheck(a.length, fromIndex, toIndex);
1468 return binarySearch0(a, fromIndex, toIndex, key);
1469 }
1470
1471 // Like public version, but without range checks.
1472 private static int binarySearch0(int[] a, int fromIndex, int toIndex,
1473 int key) {
1474 int low = fromIndex;
1475 int high = toIndex - 1;
1476
1477 while (low <= high) {
1478 int mid = (low + high) >>> 1;
1479 int midVal = a[mid];
1480
1481 if (midVal < key)
1482 low = mid + 1;
1483 else if (midVal > key)
1484 high = mid - 1;
1485 else
1486 return mid; // key found
1487 }
1488 return -(low + 1); // key not found.
1489 }
1490
1491 /**
1492 * Searches the specified array of shorts for the specified value using
1493 * the binary search algorithm. The array must be sorted
1494 * (as by the {@link #sort(short[])} method) prior to making this call. If
1495 * it is not sorted, the results are undefined. If the array contains
1496 * multiple elements with the specified value, there is no guarantee which
1497 * one will be found.
1498 *
1499 * @param a the array to be searched
1500 * @param key the value to be searched for
1501 * @return index of the search key, if it is contained in the array;
1502 * otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>. The
1503 * <i>insertion point</i> is defined as the point at which the
1504 * key would be inserted into the array: the index of the first
1505 * element greater than the key, or <tt>a.length</tt> if all
1506 * elements in the array are less than the specified key. Note
1507 * that this guarantees that the return value will be >= 0 if
1508 * and only if the key is found.
1509 */
1510 public static int binarySearch(short[] a, short key) {
1511 return binarySearch0(a, 0, a.length, key);
1512 }
1513
1514 /**
1515 * Searches a range of
1516 * the specified array of shorts for the specified value using
1517 * the binary search algorithm.
1518 * The range must be sorted
1519 * (as by the {@link #sort(short[], int, int)} method)
1520 * prior to making this call. If
1521 * it is not sorted, the results are undefined. If the range contains
1522 * multiple elements with the specified value, there is no guarantee which
1523 * one will be found.
1524 *
1525 * @param a the array to be searched
1526 * @param fromIndex the index of the first element (inclusive) to be
1527 * searched
1528 * @param toIndex the index of the last element (exclusive) to be searched
1529 * @param key the value to be searched for
1530 * @return index of the search key, if it is contained in the array
1531 * within the specified range;
1532 * otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>. The
1533 * <i>insertion point</i> is defined as the point at which the
1534 * key would be inserted into the array: the index of the first
1535 * element in the range greater than the key,
1536 * or <tt>toIndex</tt> if all
1537 * elements in the range are less than the specified key. Note
1538 * that this guarantees that the return value will be >= 0 if
1539 * and only if the key is found.
1540 * @throws IllegalArgumentException
1541 * if {@code fromIndex > toIndex}
1542 * @throws ArrayIndexOutOfBoundsException
1543 * if {@code fromIndex < 0 or toIndex > a.length}
1544 * @since 1.6
1545 */
1546 public static int binarySearch(short[] a, int fromIndex, int toIndex,
1547 short key) {
1548 rangeCheck(a.length, fromIndex, toIndex);
1549 return binarySearch0(a, fromIndex, toIndex, key);
1550 }
1551
1552 // Like public version, but without range checks.
1553 private static int binarySearch0(short[] a, int fromIndex, int toIndex,
1554 short key) {
1555 int low = fromIndex;
1556 int high = toIndex - 1;
1557
1558 while (low <= high) {
1559 int mid = (low + high) >>> 1;
1560 short midVal = a[mid];
1561
1562 if (midVal < key)
1563 low = mid + 1;
1564 else if (midVal > key)
1565 high = mid - 1;
1566 else
1567 return mid; // key found
1568 }
1569 return -(low + 1); // key not found.
1570 }
1571
1572 /**
1573 * Searches the specified array of chars for the specified value using the
1574 * binary search algorithm. The array must be sorted (as
1575 * by the {@link #sort(char[])} method) prior to making this call. If it
1576 * is not sorted, the results are undefined. If the array contains
1577 * multiple elements with the specified value, there is no guarantee which
1578 * one will be found.
1579 *
1580 * @param a the array to be searched
1581 * @param key the value to be searched for
1582 * @return index of the search key, if it is contained in the array;
1583 * otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>. The
1584 * <i>insertion point</i> is defined as the point at which the
1585 * key would be inserted into the array: the index of the first
1586 * element greater than the key, or <tt>a.length</tt> if all
1587 * elements in the array are less than the specified key. Note
1588 * that this guarantees that the return value will be >= 0 if
1589 * and only if the key is found.
1590 */
1591 public static int binarySearch(char[] a, char key) {
1592 return binarySearch0(a, 0, a.length, key);
1593 }
1594
1595 /**
1596 * Searches a range of
1597 * the specified array of chars for the specified value using the
1598 * binary search algorithm.
1599 * The range must be sorted (as
1600 * by the {@link #sort(char[], int, int)} method)
1601 * prior to making this call. If it
1602 * is not sorted, the results are undefined. If the range contains
1603 * multiple elements with the specified value, there is no guarantee which
1604 * one will be found.
1605 *
1606 * @param a the array to be searched
1607 * @param fromIndex the index of the first element (inclusive) to be
1608 * searched
1609 * @param toIndex the index of the last element (exclusive) to be searched
1610 * @param key the value to be searched for
1611 * @return index of the search key, if it is contained in the array
1612 * within the specified range;
1613 * otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>. The
1614 * <i>insertion point</i> is defined as the point at which the
1615 * key would be inserted into the array: the index of the first
1616 * element in the range greater than the key,
1617 * or <tt>toIndex</tt> if all
1618 * elements in the range are less than the specified key. Note
1619 * that this guarantees that the return value will be >= 0 if
1620 * and only if the key is found.
1621 * @throws IllegalArgumentException
1622 * if {@code fromIndex > toIndex}
1623 * @throws ArrayIndexOutOfBoundsException
1624 * if {@code fromIndex < 0 or toIndex > a.length}
1625 * @since 1.6
1626 */
1627 public static int binarySearch(char[] a, int fromIndex, int toIndex,
1628 char key) {
1629 rangeCheck(a.length, fromIndex, toIndex);
1630 return binarySearch0(a, fromIndex, toIndex, key);
1631 }
1632
1633 // Like public version, but without range checks.
1634 private static int binarySearch0(char[] a, int fromIndex, int toIndex,
1635 char key) {
1636 int low = fromIndex;
1637 int high = toIndex - 1;
1638
1639 while (low <= high) {
1640 int mid = (low + high) >>> 1;
1641 char midVal = a[mid];
1642
1643 if (midVal < key)
1644 low = mid + 1;
1645 else if (midVal > key)
1646 high = mid - 1;
1647 else
1648 return mid; // key found
1649 }
1650 return -(low + 1); // key not found.
1651 }
1652
1653 /**
1654 * Searches the specified array of bytes for the specified value using the
1655 * binary search algorithm. The array must be sorted (as
1656 * by the {@link #sort(byte[])} method) prior to making this call. If it
1657 * is not sorted, the results are undefined. If the array contains
1658 * multiple elements with the specified value, there is no guarantee which
1659 * one will be found.
1660 *
1661 * @param a the array to be searched
1662 * @param key the value to be searched for
1663 * @return index of the search key, if it is contained in the array;
1664 * otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>. The
1665 * <i>insertion point</i> is defined as the point at which the
1666 * key would be inserted into the array: the index of the first
1667 * element greater than the key, or <tt>a.length</tt> if all
1668 * elements in the array are less than the specified key. Note
1669 * that this guarantees that the return value will be >= 0 if
1670 * and only if the key is found.
1671 */
1672 public static int binarySearch(byte[] a, byte key) {
1673 return binarySearch0(a, 0, a.length, key);
1674 }
1675
1676 /**
1677 * Searches a range of
1678 * the specified array of bytes for the specified value using the
1679 * binary search algorithm.
1680 * The range must be sorted (as
1681 * by the {@link #sort(byte[], int, int)} method)
1682 * prior to making this call. If it
1683 * is not sorted, the results are undefined. If the range contains
1684 * multiple elements with the specified value, there is no guarantee which
1685 * one will be found.
1686 *
1687 * @param a the array to be searched
1688 * @param fromIndex the index of the first element (inclusive) to be
1689 * searched
1690 * @param toIndex the index of the last element (exclusive) to be searched
1691 * @param key the value to be searched for
1692 * @return index of the search key, if it is contained in the array
1693 * within the specified range;
1694 * otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>. The
1695 * <i>insertion point</i> is defined as the point at which the
1696 * key would be inserted into the array: the index of the first
1697 * element in the range greater than the key,
1698 * or <tt>toIndex</tt> if all
1699 * elements in the range are less than the specified key. Note
1700 * that this guarantees that the return value will be >= 0 if
1701 * and only if the key is found.
1702 * @throws IllegalArgumentException
1703 * if {@code fromIndex > toIndex}
1704 * @throws ArrayIndexOutOfBoundsException
1705 * if {@code fromIndex < 0 or toIndex > a.length}
1706 * @since 1.6
1707 */
1708 public static int binarySearch(byte[] a, int fromIndex, int toIndex,
1709 byte key) {
1710 rangeCheck(a.length, fromIndex, toIndex);
1711 return binarySearch0(a, fromIndex, toIndex, key);
1712 }
1713
1714 // Like public version, but without range checks.
1715 private static int binarySearch0(byte[] a, int fromIndex, int toIndex,
1716 byte key) {
1717 int low = fromIndex;
1718 int high = toIndex - 1;
1719
1720 while (low <= high) {
1721 int mid = (low + high) >>> 1;
1722 byte midVal = a[mid];
1723
1724 if (midVal < key)
1725 low = mid + 1;
1726 else if (midVal > key)
1727 high = mid - 1;
1728 else
1729 return mid; // key found
1730 }
1731 return -(low + 1); // key not found.
1732 }
1733
1734 /**
1735 * Searches the specified array of doubles for the specified value using
1736 * the binary search algorithm. The array must be sorted
1737 * (as by the {@link #sort(double[])} method) prior to making this call.
1738 * If it is not sorted, the results are undefined. If the array contains
1739 * multiple elements with the specified value, there is no guarantee which
1740 * one will be found. This method considers all NaN values to be
1741 * equivalent and equal.
1742 *
1743 * @param a the array to be searched
1744 * @param key the value to be searched for
1745 * @return index of the search key, if it is contained in the array;
1746 * otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>. The
1747 * <i>insertion point</i> is defined as the point at which the
1748 * key would be inserted into the array: the index of the first
1749 * element greater than the key, or <tt>a.length</tt> if all
1750 * elements in the array are less than the specified key. Note
1751 * that this guarantees that the return value will be >= 0 if
1752 * and only if the key is found.
1753 */
1754 public static int binarySearch(double[] a, double key) {
1755 return binarySearch0(a, 0, a.length, key);
1756 }
1757
1758 /**
1759 * Searches a range of
1760 * the specified array of doubles for the specified value using
1761 * the binary search algorithm.
1762 * The range must be sorted
1763 * (as by the {@link #sort(double[], int, int)} method)
1764 * prior to making this call.
1765 * If it is not sorted, the results are undefined. If the range contains
1766 * multiple elements with the specified value, there is no guarantee which
1767 * one will be found. This method considers all NaN values to be
1768 * equivalent and equal.
1769 *
1770 * @param a the array to be searched
1771 * @param fromIndex the index of the first element (inclusive) to be
1772 * searched
1773 * @param toIndex the index of the last element (exclusive) to be searched
1774 * @param key the value to be searched for
1775 * @return index of the search key, if it is contained in the array
1776 * within the specified range;
1777 * otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>. The
1778 * <i>insertion point</i> is defined as the point at which the
1779 * key would be inserted into the array: the index of the first
1780 * element in the range greater than the key,
1781 * or <tt>toIndex</tt> if all
1782 * elements in the range are less than the specified key. Note
1783 * that this guarantees that the return value will be >= 0 if
1784 * and only if the key is found.
1785 * @throws IllegalArgumentException
1786 * if {@code fromIndex > toIndex}
1787 * @throws ArrayIndexOutOfBoundsException
1788 * if {@code fromIndex < 0 or toIndex > a.length}
1789 * @since 1.6
1790 */
1791 public static int binarySearch(double[] a, int fromIndex, int toIndex,
1792 double key) {
1793 rangeCheck(a.length, fromIndex, toIndex);
1794 return binarySearch0(a, fromIndex, toIndex, key);
1795 }
1796
1797 // Like public version, but without range checks.
1798 private static int binarySearch0(double[] a, int fromIndex, int toIndex,
1799 double key) {
1800 int low = fromIndex;
1801 int high = toIndex - 1;
1802
1803 while (low <= high) {
1804 int mid = (low + high) >>> 1;
1805 double midVal = a[mid];
1806
1807 if (midVal < key)
1808 low = mid + 1; // Neither val is NaN, thisVal is smaller
1809 else if (midVal > key)
1810 high = mid - 1; // Neither val is NaN, thisVal is larger
1811 else {
1812 long midBits = Double.doubleToLongBits(midVal);
1813 long keyBits = Double.doubleToLongBits(key);
1814 if (midBits == keyBits) // Values are equal
1815 return mid; // Key found
1816 else if (midBits < keyBits) // (-0.0, 0.0) or (!NaN, NaN)
1817 low = mid + 1;
1818 else // (0.0, -0.0) or (NaN, !NaN)
1819 high = mid - 1;
1820 }
1821 }
1822 return -(low + 1); // key not found.
1823 }
1824
1825 /**
1826 * Searches the specified array of floats for the specified value using
1827 * the binary search algorithm. The array must be sorted
1828 * (as by the {@link #sort(float[])} method) prior to making this call. If
1829 * it is not sorted, the results are undefined. If the array contains
1830 * multiple elements with the specified value, there is no guarantee which
1831 * one will be found. This method considers all NaN values to be
1832 * equivalent and equal.
1833 *
1834 * @param a the array to be searched
1835 * @param key the value to be searched for
1836 * @return index of the search key, if it is contained in the array;
1837 * otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>. The
1838 * <i>insertion point</i> is defined as the point at which the
1839 * key would be inserted into the array: the index of the first
1840 * element greater than the key, or <tt>a.length</tt> if all
1841 * elements in the array are less than the specified key. Note
1842 * that this guarantees that the return value will be >= 0 if
1843 * and only if the key is found.
1844 */
1845 public static int binarySearch(float[] a, float key) {
1846 return binarySearch0(a, 0, a.length, key);
1847 }
1848
1849 /**
1850 * Searches a range of
1851 * the specified array of floats for the specified value using
1852 * the binary search algorithm.
1853 * The range must be sorted
1854 * (as by the {@link #sort(float[], int, int)} method)
1855 * prior to making this call. If
1856 * it is not sorted, the results are undefined. If the range contains
1857 * multiple elements with the specified value, there is no guarantee which
1858 * one will be found. This method considers all NaN values to be
1859 * equivalent and equal.
1860 *
1861 * @param a the array to be searched
1862 * @param fromIndex the index of the first element (inclusive) to be
1863 * searched
1864 * @param toIndex the index of the last element (exclusive) to be searched
1865 * @param key the value to be searched for
1866 * @return index of the search key, if it is contained in the array
1867 * within the specified range;
1868 * otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>. The
1869 * <i>insertion point</i> is defined as the point at which the
1870 * key would be inserted into the array: the index of the first
1871 * element in the range greater than the key,
1872 * or <tt>toIndex</tt> if all
1873 * elements in the range are less than the specified key. Note
1874 * that this guarantees that the return value will be >= 0 if
1875 * and only if the key is found.
1876 * @throws IllegalArgumentException
1877 * if {@code fromIndex > toIndex}
1878 * @throws ArrayIndexOutOfBoundsException
1879 * if {@code fromIndex < 0 or toIndex > a.length}
1880 * @since 1.6
1881 */
1882 public static int binarySearch(float[] a, int fromIndex, int toIndex,
1883 float key) {
1884 rangeCheck(a.length, fromIndex, toIndex);
1885 return binarySearch0(a, fromIndex, toIndex, key);
1886 }
1887
1888 // Like public version, but without range checks.
1889 private static int binarySearch0(float[] a, int fromIndex, int toIndex,
1890 float key) {
1891 int low = fromIndex;
1892 int high = toIndex - 1;
1893
1894 while (low <= high) {
1895 int mid = (low + high) >>> 1;
1896 float midVal = a[mid];
1897
1898 if (midVal < key)
1899 low = mid + 1; // Neither val is NaN, thisVal is smaller
1900 else if (midVal > key)
1901 high = mid - 1; // Neither val is NaN, thisVal is larger
1902 else {
1903 int midBits = Float.floatToIntBits(midVal);
1904 int keyBits = Float.floatToIntBits(key);
1905 if (midBits == keyBits) // Values are equal
1906 return mid; // Key found
1907 else if (midBits < keyBits) // (-0.0, 0.0) or (!NaN, NaN)
1908 low = mid + 1;
1909 else // (0.0, -0.0) or (NaN, !NaN)
1910 high = mid - 1;
1911 }
1912 }
1913 return -(low + 1); // key not found.
1914 }
1915
1916
1917 /**
1918 * Searches the specified array for the specified object using the binary
1919 * search algorithm. The array must be sorted into ascending order
1920 * according to the
1921 * {@linkplain Comparable natural ordering}
1922 * of its elements (as by the
1923 * {@link #sort(Object[])} method) prior to making this call.
1924 * If it is not sorted, the results are undefined.
1925 * (If the array contains elements that are not mutually comparable (for
1926 * example, strings and integers), it <i>cannot</i> be sorted according
1927 * to the natural ordering of its elements, hence results are undefined.)
1928 * If the array contains multiple
1929 * elements equal to the specified object, there is no guarantee which
1930 * one will be found.
1931 *
1932 * @param a the array to be searched
1933 * @param key the value to be searched for
1934 * @return index of the search key, if it is contained in the array;
1935 * otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>. The
1936 * <i>insertion point</i> is defined as the point at which the
1937 * key would be inserted into the array: the index of the first
1938 * element greater than the key, or <tt>a.length</tt> if all
1939 * elements in the array are less than the specified key. Note
1940 * that this guarantees that the return value will be >= 0 if
1941 * and only if the key is found.
1942 * @throws ClassCastException if the search key is not comparable to the
1943 * elements of the array.
1944 */
1945 public static int binarySearch(Object[] a, Object key) {
1946 return binarySearch0(a, 0, a.length, key);
1947 }
1948
1949 /**
1950 * Searches a range of
1951 * the specified array for the specified object using the binary
1952 * search algorithm.
1953 * The range must be sorted into ascending order
1954 * according to the
1955 * {@linkplain Comparable natural ordering}
1956 * of its elements (as by the
1957 * {@link #sort(Object[], int, int)} method) prior to making this
1958 * call. If it is not sorted, the results are undefined.
1959 * (If the range contains elements that are not mutually comparable (for
1960 * example, strings and integers), it <i>cannot</i> be sorted according
1961 * to the natural ordering of its elements, hence results are undefined.)
1962 * If the range contains multiple
1963 * elements equal to the specified object, there is no guarantee which
1964 * one will be found.
1965 *
1966 * @param a the array to be searched
1967 * @param fromIndex the index of the first element (inclusive) to be
1968 * searched
1969 * @param toIndex the index of the last element (exclusive) to be searched
1970 * @param key the value to be searched for
1971 * @return index of the search key, if it is contained in the array
1972 * within the specified range;
1973 * otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>. The
1974 * <i>insertion point</i> is defined as the point at which the
1975 * key would be inserted into the array: the index of the first
1976 * element in the range greater than the key,
1977 * or <tt>toIndex</tt> if all
1978 * elements in the range are less than the specified key. Note
1979 * that this guarantees that the return value will be >= 0 if
1980 * and only if the key is found.
1981 * @throws ClassCastException if the search key is not comparable to the
1982 * elements of the array within the specified range.
1983 * @throws IllegalArgumentException
1984 * if {@code fromIndex > toIndex}
1985 * @throws ArrayIndexOutOfBoundsException
1986 * if {@code fromIndex < 0 or toIndex > a.length}
1987 * @since 1.6
1988 */
1989 public static int binarySearch(Object[] a, int fromIndex, int toIndex,
1990 Object key) {
1991 rangeCheck(a.length, fromIndex, toIndex);
1992 return binarySearch0(a, fromIndex, toIndex, key);
1993 }
1994
1995 // Like public version, but without range checks.
1996 private static int binarySearch0(Object[] a, int fromIndex, int toIndex,
1997 Object key) {
1998 int low = fromIndex;
1999 int high = toIndex - 1;
2000
2001 while (low <= high) {
2002 int mid = (low + high) >>> 1;
2003 Comparable midVal = (Comparable)a[mid];
2004 int cmp = midVal.compareTo(key);
2005
2006 if (cmp < 0)
2007 low = mid + 1;
2008 else if (cmp > 0)
2009 high = mid - 1;
2010 else
2011 return mid; // key found
2012 }
2013 return -(low + 1); // key not found.
2014 }
2015
2016 /**
2017 * Searches the specified array for the specified object using the binary
2018 * search algorithm. The array must be sorted into ascending order
2019 * according to the specified comparator (as by the
2020 * {@link #sort(Object[], Comparator) sort(T[], Comparator)}
2021 * method) prior to making this call. If it is
2022 * not sorted, the results are undefined.
2023 * If the array contains multiple
2024 * elements equal to the specified object, there is no guarantee which one
2025 * will be found.
2026 *
2027 * @param a the array to be searched
2028 * @param key the value to be searched for
2029 * @param c the comparator by which the array is ordered. A
2030 * <tt>null</tt> value indicates that the elements'
2031 * {@linkplain Comparable natural ordering} should be used.
2032 * @return index of the search key, if it is contained in the array;
2033 * otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>. The
2034 * <i>insertion point</i> is defined as the point at which the
2035 * key would be inserted into the array: the index of the first
2036 * element greater than the key, or <tt>a.length</tt> if all
2037 * elements in the array are less than the specified key. Note
2038 * that this guarantees that the return value will be >= 0 if
2039 * and only if the key is found.
2040 * @throws ClassCastException if the array contains elements that are not
2041 * <i>mutually comparable</i> using the specified comparator,
2042 * or the search key is not comparable to the
2043 * elements of the array using this comparator.
2044 */
2045 public static <T> int binarySearch(T[] a, T key, Comparator<? super T> c) {
2046 return binarySearch0(a, 0, a.length, key, c);
2047 }
2048
2049 /**
2050 * Searches a range of
2051 * the specified array for the specified object using the binary
2052 * search algorithm.
2053 * The range must be sorted into ascending order
2054 * according to the specified comparator (as by the
2055 * {@link #sort(Object[], int, int, Comparator)
2056 * sort(T[], int, int, Comparator)}
2057 * method) prior to making this call.
2058 * If it is not sorted, the results are undefined.
2059 * If the range contains multiple elements equal to the specified object,
2060 * there is no guarantee which one will be found.
2061 *
2062 * @param a the array to be searched
2063 * @param fromIndex the index of the first element (inclusive) to be
2064 * searched
2065 * @param toIndex the index of the last element (exclusive) to be searched
2066 * @param key the value to be searched for
2067 * @param c the comparator by which the array is ordered. A
2068 * <tt>null</tt> value indicates that the elements'
2069 * {@linkplain Comparable natural ordering} should be used.
2070 * @return index of the search key, if it is contained in the array
2071 * within the specified range;
2072 * otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>. The
2073 * <i>insertion point</i> is defined as the point at which the
2074 * key would be inserted into the array: the index of the first
2075 * element in the range greater than the key,
2076 * or <tt>toIndex</tt> if all
2077 * elements in the range are less than the specified key. Note
2078 * that this guarantees that the return value will be >= 0 if
2079 * and only if the key is found.
2080 * @throws ClassCastException if the range contains elements that are not
2081 * <i>mutually comparable</i> using the specified comparator,
2082 * or the search key is not comparable to the
2083 * elements in the range using this comparator.
2084 * @throws IllegalArgumentException
2085 * if {@code fromIndex > toIndex}
2086 * @throws ArrayIndexOutOfBoundsException
2087 * if {@code fromIndex < 0 or toIndex > a.length}
2088 * @since 1.6
2089 */
2090 public static <T> int binarySearch(T[] a, int fromIndex, int toIndex,
2091 T key, Comparator<? super T> c) {
2092 rangeCheck(a.length, fromIndex, toIndex);
2093 return binarySearch0(a, fromIndex, toIndex, key, c);
2094 }
2095
2096 // Like public version, but without range checks.
2097 private static <T> int binarySearch0(T[] a, int fromIndex, int toIndex,
2098 T key, Comparator<? super T> c) {
2099 if (c == null) {
2100 return binarySearch0(a, fromIndex, toIndex, key);
2101 }
2102 int low = fromIndex;
2103 int high = toIndex - 1;
2104
2105 while (low <= high) {
2106 int mid = (low + high) >>> 1;
2107 T midVal = a[mid];
2108 int cmp = c.compare(midVal, key);
2109
2110 if (cmp < 0)
2111 low = mid + 1;
2112 else if (cmp > 0)
2113 high = mid - 1;
2114 else
2115 return mid; // key found
2116 }
2117 return -(low + 1); // key not found.
2118 }
2119
2120
2121 // Equality Testing
2122
2123 /**
2124 * Returns <tt>true</tt> if the two specified arrays of longs are
2125 * <i>equal</i> to one another. Two arrays are considered equal if both
2126 * arrays contain the same number of elements, and all corresponding pairs
2127 * of elements in the two arrays are equal. In other words, two arrays
2128 * are equal if they contain the same elements in the same order. Also,
2129 * two array references are considered equal if both are <tt>null</tt>.<p>
2130 *
2131 * @param a one array to be tested for equality
2132 * @param a2 the other array to be tested for equality
2133 * @return <tt>true</tt> if the two arrays are equal
2134 */
2135 public static boolean equals(long[] a, long[] a2) {
2136 if (a==a2)
2137 return true;
2138 if (a==null || a2==null)
2139 return false;
2140
2141 int length = a.length;
2142 if (a2.length != length)
2143 return false;
2144
2145 for (int i=0; i<length; i++)
2146 if (a[i] != a2[i])
2147 return false;
2148
2149 return true;
2150 }
2151
2152 /**
2153 * Returns <tt>true</tt> if the two specified arrays of ints are
2154 * <i>equal</i> to one another. Two arrays are considered equal if both
2155 * arrays contain the same number of elements, and all corresponding pairs
2156 * of elements in the two arrays are equal. In other words, two arrays
2157 * are equal if they contain the same elements in the same order. Also,
2158 * two array references are considered equal if both are <tt>null</tt>.<p>
2159 *
2160 * @param a one array to be tested for equality
2161 * @param a2 the other array to be tested for equality
2162 * @return <tt>true</tt> if the two arrays are equal
2163 */
2164 public static boolean equals(int[] a, int[] a2) {
2165 if (a==a2)
2166 return true;
2167 if (a==null || a2==null)
2168 return false;
2169
2170 int length = a.length;
2171 if (a2.length != length)
2172 return false;
2173
2174 for (int i=0; i<length; i++)
2175 if (a[i] != a2[i])
2176 return false;
2177
2178 return true;
2179 }
2180
2181 /**
2182 * Returns <tt>true</tt> if the two specified arrays of shorts are
2183 * <i>equal</i> to one another. Two arrays are considered equal if both
2184 * arrays contain the same number of elements, and all corresponding pairs
2185 * of elements in the two arrays are equal. In other words, two arrays
2186 * are equal if they contain the same elements in the same order. Also,
2187 * two array references are considered equal if both are <tt>null</tt>.<p>
2188 *
2189 * @param a one array to be tested for equality
2190 * @param a2 the other array to be tested for equality
2191 * @return <tt>true</tt> if the two arrays are equal
2192 */
2193 public static boolean equals(short[] a, short a2[]) {
2194 if (a==a2)
2195 return true;
2196 if (a==null || a2==null)
2197 return false;
2198
2199 int length = a.length;
2200 if (a2.length != length)
2201 return false;
2202
2203 for (int i=0; i<length; i++)
2204 if (a[i] != a2[i])
2205 return false;
2206
2207 return true;
2208 }
2209
2210 /**
2211 * Returns <tt>true</tt> if the two specified arrays of chars are
2212 * <i>equal</i> to one another. Two arrays are considered equal if both
2213 * arrays contain the same number of elements, and all corresponding pairs
2214 * of elements in the two arrays are equal. In other words, two arrays
2215 * are equal if they contain the same elements in the same order. Also,
2216 * two array references are considered equal if both are <tt>null</tt>.<p>
2217 *
2218 * @param a one array to be tested for equality
2219 * @param a2 the other array to be tested for equality
2220 * @return <tt>true</tt> if the two arrays are equal
2221 */
2222 public static boolean equals(char[] a, char[] a2) {
2223 if (a==a2)
2224 return true;
2225 if (a==null || a2==null)
2226 return false;
2227
2228 int length = a.length;
2229 if (a2.length != length)
2230 return false;
2231
2232 for (int i=0; i<length; i++)
2233 if (a[i] != a2[i])
2234 return false;
2235
2236 return true;
2237 }
2238
2239 /**
2240 * Returns <tt>true</tt> if the two specified arrays of bytes are
2241 * <i>equal</i> to one another. Two arrays are considered equal if both
2242 * arrays contain t
Save This Page