1 /* Arrays.java -- Utility class with methods to operate on arrays
2 Copyright (C) 1998, 1999, 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007,
3 Free Software Foundation, Inc.
5 This file is part of GNU Classpath.
7 GNU Classpath is free software; you can redistribute it and/or modify
8 it under the terms of the GNU General Public License as published by
9 the Free Software Foundation; either version 2, or (at your option)
12 GNU Classpath is distributed in the hope that it will be useful, but
13 WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
15 General Public License for more details.
17 You should have received a copy of the GNU General Public License
18 along with GNU Classpath; see the file COPYING. If not, write to the
19 Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
22 Linking this library statically or dynamically with other modules is
23 making a combined work based on this library. Thus, the terms and
24 conditions of the GNU General Public License cover the whole
27 As a special exception, the copyright holders of this library give you
28 permission to link this library with independent modules to produce an
29 executable, regardless of the license terms of these independent
30 modules, and to copy and distribute the resulting executable under
31 terms of your choice, provided that you also meet, for each linked
32 independent module, the terms and conditions of the license of that
33 module. An independent module is a module which is not derived from
34 or based on this library. If you modify this library, you may extend
35 this exception to your version of the library, but you are not
36 obligated to do so. If you do not wish to do so, delete this
37 exception statement from your version. */
42 import java
.io
.Serializable
;
43 import java
.lang
.reflect
.Array
;
46 * This class contains various static utility methods performing operations on
47 * arrays, and a method to provide a List "view" of an array to facilitate
48 * using arrays with Collection-based APIs. All methods throw a
49 * {@link NullPointerException} if the parameter array is null.
52 * Implementations may use their own algorithms, but must obey the general
53 * properties; for example, the sort must be stable and n*log(n) complexity.
54 * Sun's implementation of sort, and therefore ours, is a tuned quicksort,
55 * adapted from Jon L. Bentley and M. Douglas McIlroy's "Engineering a Sort
56 * Function", Software-Practice and Experience, Vol. 23(11) P. 1249-1265
57 * (November 1993). This algorithm offers n*log(n) performance on many data
58 * sets that cause other quicksorts to degrade to quadratic performance.
60 * @author Original author unknown
61 * @author Bryce McKinlay
62 * @author Eric Blake (ebb9@email.byu.edu)
66 * @status updated to 1.4
71 * This class is non-instantiable.
80 * Perform a binary search of a byte array for a key. The array must be
81 * sorted (as by the sort() method) - if it is not, the behaviour of this
82 * method is undefined, and may be an infinite loop. If the array contains
83 * the key more than once, any one of them may be found. Note: although the
84 * specification allows for an infinite loop if the array is unsorted, it
85 * will not happen in this implementation.
87 * @param a the array to search (must be sorted)
88 * @param key the value to search for
89 * @return the index at which the key was found, or -n-1 if it was not
90 * found, where n is the index of the first value higher than key or
91 * a.length if there is no such value.
93 public static int binarySearch(byte[] a
, byte key
)
97 return binarySearch(a
, 0, a
.length
- 1, key
);
101 * Perform a binary search of a range of a byte array for a key. The range
102 * must be sorted (as by the <code>sort(byte[], int, int)</code> method) -
103 * if it is not, the behaviour of this method is undefined, and may be an
104 * infinite loop. If the array contains the key more than once, any one of
105 * them may be found. Note: although the specification allows for an infinite
106 * loop if the array is unsorted, it will not happen in this implementation.
108 * @param a the array to search (must be sorted)
109 * @param low the lowest index to search from.
110 * @param hi the highest index to search to.
111 * @param key the value to search for
112 * @return the index at which the key was found, or -n-1 if it was not
113 * found, where n is the index of the first value higher than key or
114 * a.length if there is no such value.
115 * @throws IllegalArgumentException if <code>low > hi</code>
116 * @throws ArrayIndexOutOfBoundsException if <code>low < 0</code> or
117 * <code>hi > a.length</code>.
119 public static int binarySearch(byte[] a
, int low
, int hi
, byte key
)
122 throw new IllegalArgumentException("The start index is higher than " +
123 "the finish index.");
124 if (low
< 0 || hi
> a
.length
)
125 throw new ArrayIndexOutOfBoundsException("One of the indices is out " +
130 mid
= (low
+ hi
) >>> 1;
131 final byte d
= a
[mid
];
137 // This gets the insertion point right on the last loop.
144 * Perform a binary search of a char array for a key. The array must be
145 * sorted (as by the sort() method) - if it is not, the behaviour of this
146 * method is undefined, and may be an infinite loop. If the array contains
147 * the key more than once, any one of them may be found. Note: although the
148 * specification allows for an infinite loop if the array is unsorted, it
149 * will not happen in this implementation.
151 * @param a the array to search (must be sorted)
152 * @param key the value to search for
153 * @return the index at which the key was found, or -n-1 if it was not
154 * found, where n is the index of the first value higher than key or
155 * a.length if there is no such value.
157 public static int binarySearch(char[] a
, char key
)
161 return binarySearch(a
, 0, a
.length
- 1, key
);
165 * Perform a binary search of a range of a char array for a key. The range
166 * must be sorted (as by the <code>sort(char[], int, int)</code> method) -
167 * if it is not, the behaviour of this method is undefined, and may be an
168 * infinite loop. If the array contains the key more than once, any one of
169 * them may be found. Note: although the specification allows for an infinite
170 * loop if the array is unsorted, it will not happen in this implementation.
172 * @param a the array to search (must be sorted)
173 * @param low the lowest index to search from.
174 * @param hi the highest index to search to.
175 * @param key the value to search for
176 * @return the index at which the key was found, or -n-1 if it was not
177 * found, where n is the index of the first value higher than key or
178 * a.length if there is no such value.
179 * @throws IllegalArgumentException if <code>low > hi</code>
180 * @throws ArrayIndexOutOfBoundsException if <code>low < 0</code> or
181 * <code>hi > a.length</code>.
183 public static int binarySearch(char[] a
, int low
, int hi
, char key
)
186 throw new IllegalArgumentException("The start index is higher than " +
187 "the finish index.");
188 if (low
< 0 || hi
> a
.length
)
189 throw new ArrayIndexOutOfBoundsException("One of the indices is out " +
194 mid
= (low
+ hi
) >>> 1;
195 final char d
= a
[mid
];
201 // This gets the insertion point right on the last loop.
208 * Perform a binary search of a short array for a key. The array must be
209 * sorted (as by the sort() method) - if it is not, the behaviour of this
210 * method is undefined, and may be an infinite loop. If the array contains
211 * the key more than once, any one of them may be found. Note: although the
212 * specification allows for an infinite loop if the array is unsorted, it
213 * will not happen in this implementation.
215 * @param a the array to search (must be sorted)
216 * @param key the value to search for
217 * @return the index at which the key was found, or -n-1 if it was not
218 * found, where n is the index of the first value higher than key or
219 * a.length if there is no such value.
221 public static int binarySearch(short[] a
, short key
)
225 return binarySearch(a
, 0, a
.length
- 1, key
);
229 * Perform a binary search of a range of a short array for a key. The range
230 * must be sorted (as by the <code>sort(short[], int, int)</code> method) -
231 * if it is not, the behaviour of this method is undefined, and may be an
232 * infinite loop. If the array contains the key more than once, any one of
233 * them may be found. Note: although the specification allows for an infinite
234 * loop if the array is unsorted, it will not happen in this implementation.
236 * @param a the array to search (must be sorted)
237 * @param low the lowest index to search from.
238 * @param hi the highest index to search to.
239 * @param key the value to search for
240 * @return the index at which the key was found, or -n-1 if it was not
241 * found, where n is the index of the first value higher than key or
242 * a.length if there is no such value.
243 * @throws IllegalArgumentException if <code>low > hi</code>
244 * @throws ArrayIndexOutOfBoundsException if <code>low < 0</code> or
245 * <code>hi > a.length</code>.
247 public static int binarySearch(short[] a
, int low
, int hi
, short key
)
250 throw new IllegalArgumentException("The start index is higher than " +
251 "the finish index.");
252 if (low
< 0 || hi
> a
.length
)
253 throw new ArrayIndexOutOfBoundsException("One of the indices is out " +
258 mid
= (low
+ hi
) >>> 1;
259 final short d
= a
[mid
];
265 // This gets the insertion point right on the last loop.
272 * Perform a binary search of an int array for a key. The array must be
273 * sorted (as by the sort() method) - if it is not, the behaviour of this
274 * method is undefined, and may be an infinite loop. If the array contains
275 * the key more than once, any one of them may be found. Note: although the
276 * specification allows for an infinite loop if the array is unsorted, it
277 * will not happen in this implementation.
279 * @param a the array to search (must be sorted)
280 * @param key the value to search for
281 * @return the index at which the key was found, or -n-1 if it was not
282 * found, where n is the index of the first value higher than key or
283 * a.length if there is no such value.
285 public static int binarySearch(int[] a
, int key
)
289 return binarySearch(a
, 0, a
.length
- 1, key
);
293 * Perform a binary search of a range of an integer array for a key. The range
294 * must be sorted (as by the <code>sort(int[], int, int)</code> method) -
295 * if it is not, the behaviour of this method is undefined, and may be an
296 * infinite loop. If the array contains the key more than once, any one of
297 * them may be found. Note: although the specification allows for an infinite
298 * loop if the array is unsorted, it will not happen in this implementation.
300 * @param a the array to search (must be sorted)
301 * @param low the lowest index to search from.
302 * @param hi the highest index to search to.
303 * @param key the value to search for
304 * @return the index at which the key was found, or -n-1 if it was not
305 * found, where n is the index of the first value higher than key or
306 * a.length if there is no such value.
307 * @throws IllegalArgumentException if <code>low > hi</code>
308 * @throws ArrayIndexOutOfBoundsException if <code>low < 0</code> or
309 * <code>hi > a.length</code>.
311 public static int binarySearch(int[] a
, int low
, int hi
, int key
)
314 throw new IllegalArgumentException("The start index is higher than " +
315 "the finish index.");
316 if (low
< 0 || hi
> a
.length
)
317 throw new ArrayIndexOutOfBoundsException("One of the indices is out " +
322 mid
= (low
+ hi
) >>> 1;
323 final int d
= a
[mid
];
329 // This gets the insertion point right on the last loop.
336 * Perform a binary search of a long array for a key. The array must be
337 * sorted (as by the sort() method) - if it is not, the behaviour of this
338 * method is undefined, and may be an infinite loop. If the array contains
339 * the key more than once, any one of them may be found. Note: although the
340 * specification allows for an infinite loop if the array is unsorted, it
341 * will not happen in this implementation.
343 * @param a the array to search (must be sorted)
344 * @param key the value to search for
345 * @return the index at which the key was found, or -n-1 if it was not
346 * found, where n is the index of the first value higher than key or
347 * a.length if there is no such value.
349 public static int binarySearch(long[] a
, long key
)
353 return binarySearch(a
, 0, a
.length
- 1, key
);
357 * Perform a binary search of a range of a long array for a key. The range
358 * must be sorted (as by the <code>sort(long[], int, int)</code> method) -
359 * if it is not, the behaviour of this method is undefined, and may be an
360 * infinite loop. If the array contains the key more than once, any one of
361 * them may be found. Note: although the specification allows for an infinite
362 * loop if the array is unsorted, it will not happen in this implementation.
364 * @param a the array to search (must be sorted)
365 * @param low the lowest index to search from.
366 * @param hi the highest index to search to.
367 * @param key the value to search for
368 * @return the index at which the key was found, or -n-1 if it was not
369 * found, where n is the index of the first value higher than key or
370 * a.length if there is no such value.
371 * @throws IllegalArgumentException if <code>low > hi</code>
372 * @throws ArrayIndexOutOfBoundsException if <code>low < 0</code> or
373 * <code>hi > a.length</code>.
375 public static int binarySearch(long[] a
, int low
, int hi
, long key
)
378 throw new IllegalArgumentException("The start index is higher than " +
379 "the finish index.");
380 if (low
< 0 || hi
> a
.length
)
381 throw new ArrayIndexOutOfBoundsException("One of the indices is out " +
386 mid
= (low
+ hi
) >>> 1;
387 final long d
= a
[mid
];
393 // This gets the insertion point right on the last loop.
400 * Perform a binary search of a float array for a key. The array must be
401 * sorted (as by the sort() method) - if it is not, the behaviour of this
402 * method is undefined, and may be an infinite loop. If the array contains
403 * the key more than once, any one of them may be found. Note: although the
404 * specification allows for an infinite loop if the array is unsorted, it
405 * will not happen in this implementation.
407 * @param a the array to search (must be sorted)
408 * @param key the value to search for
409 * @return the index at which the key was found, or -n-1 if it was not
410 * found, where n is the index of the first value higher than key or
411 * a.length if there is no such value.
413 public static int binarySearch(float[] a
, float key
)
417 return binarySearch(a
, 0, a
.length
- 1, key
);
421 * Perform a binary search of a range of a float array for a key. The range
422 * must be sorted (as by the <code>sort(float[], int, int)</code> method) -
423 * if it is not, the behaviour of this method is undefined, and may be an
424 * infinite loop. If the array contains the key more than once, any one of
425 * them may be found. Note: although the specification allows for an infinite
426 * loop if the array is unsorted, it will not happen in this implementation.
428 * @param a the array to search (must be sorted)
429 * @param low the lowest index to search from.
430 * @param hi the highest index to search to.
431 * @param key the value to search for
432 * @return the index at which the key was found, or -n-1 if it was not
433 * found, where n is the index of the first value higher than key or
434 * a.length if there is no such value.
435 * @throws IllegalArgumentException if <code>low > hi</code>
436 * @throws ArrayIndexOutOfBoundsException if <code>low < 0</code> or
437 * <code>hi > a.length</code>.
439 public static int binarySearch(float[] a
, int low
, int hi
, float key
)
442 throw new IllegalArgumentException("The start index is higher than " +
443 "the finish index.");
444 if (low
< 0 || hi
> a
.length
)
445 throw new ArrayIndexOutOfBoundsException("One of the indices is out " +
447 // Must use Float.compare to take into account NaN, +-0.
451 mid
= (low
+ hi
) >>> 1;
452 final int r
= Float
.compare(a
[mid
], key
);
458 // This gets the insertion point right on the last loop
465 * Perform a binary search of a double array for a key. The array must be
466 * sorted (as by the sort() method) - if it is not, the behaviour of this
467 * method is undefined, and may be an infinite loop. If the array contains
468 * the key more than once, any one of them may be found. Note: although the
469 * specification allows for an infinite loop if the array is unsorted, it
470 * will not happen in this implementation.
472 * @param a the array to search (must be sorted)
473 * @param key the value to search for
474 * @return the index at which the key was found, or -n-1 if it was not
475 * found, where n is the index of the first value higher than key or
476 * a.length if there is no such value.
478 public static int binarySearch(double[] a
, double key
)
482 return binarySearch(a
, 0, a
.length
- 1, key
);
486 * Perform a binary search of a range of a double array for a key. The range
487 * must be sorted (as by the <code>sort(double[], int, int)</code> method) -
488 * if it is not, the behaviour of this method is undefined, and may be an
489 * infinite loop. If the array contains the key more than once, any one of
490 * them may be found. Note: although the specification allows for an infinite
491 * loop if the array is unsorted, it will not happen in this implementation.
493 * @param a the array to search (must be sorted)
494 * @param low the lowest index to search from.
495 * @param hi the highest index to search to.
496 * @param key the value to search for
497 * @return the index at which the key was found, or -n-1 if it was not
498 * found, where n is the index of the first value higher than key or
499 * a.length if there is no such value.
500 * @throws IllegalArgumentException if <code>low > hi</code>
501 * @throws ArrayIndexOutOfBoundsException if <code>low < 0</code> or
502 * <code>hi > a.length</code>.
504 public static int binarySearch(double[] a
, int low
, int hi
, double key
)
507 throw new IllegalArgumentException("The start index is higher than " +
508 "the finish index.");
509 if (low
< 0 || hi
> a
.length
)
510 throw new ArrayIndexOutOfBoundsException("One of the indices is out " +
512 // Must use Double.compare to take into account NaN, +-0.
516 mid
= (low
+ hi
) >>> 1;
517 final int r
= Double
.compare(a
[mid
], key
);
523 // This gets the insertion point right on the last loop
530 * Perform a binary search of an Object array for a key, using the natural
531 * ordering of the elements. The array must be sorted (as by the sort()
532 * method) - if it is not, the behaviour of this method is undefined, and may
533 * be an infinite loop. Further, the key must be comparable with every item
534 * in the array. If the array contains the key more than once, any one of
535 * them may be found. Note: although the specification allows for an infinite
536 * loop if the array is unsorted, it will not happen in this (JCL)
539 * @param a the array to search (must be sorted)
540 * @param key the value to search for
541 * @return the index at which the key was found, or -n-1 if it was not
542 * found, where n is the index of the first value higher than key or
543 * a.length if there is no such value.
544 * @throws ClassCastException if key could not be compared with one of the
546 * @throws NullPointerException if a null element in a is compared
548 public static int binarySearch(Object
[] a
, Object key
)
552 return binarySearch(a
, key
, null);
556 * Perform a binary search of a range of an Object array for a key. The range
557 * must be sorted (as by the <code>sort(Object[], int, int)</code> method) -
558 * if it is not, the behaviour of this method is undefined, and may be an
559 * infinite loop. If the array contains the key more than once, any one of
560 * them may be found. Note: although the specification allows for an infinite
561 * loop if the array is unsorted, it will not happen in this implementation.
563 * @param a the array to search (must be sorted)
564 * @param low the lowest index to search from.
565 * @param hi the highest index to search to.
566 * @param key the value to search for
567 * @return the index at which the key was found, or -n-1 if it was not
568 * found, where n is the index of the first value higher than key or
569 * a.length if there is no such value.
571 public static int binarySearch(Object
[] a
, int low
, int hi
, Object key
)
573 return binarySearch(a
, low
, hi
, key
, null);
577 * Perform a binary search of an Object array for a key, using a supplied
578 * Comparator. The array must be sorted (as by the sort() method with the
579 * same Comparator) - if it is not, the behaviour of this method is
580 * undefined, and may be an infinite loop. Further, the key must be
581 * comparable with every item in the array. If the array contains the key
582 * more than once, any one of them may be found. Note: although the
583 * specification allows for an infinite loop if the array is unsorted, it
584 * will not happen in this (JCL) implementation.
586 * @param a the array to search (must be sorted)
587 * @param key the value to search for
588 * @param c the comparator by which the array is sorted; or null to
589 * use the elements' natural order
590 * @return the index at which the key was found, or -n-1 if it was not
591 * found, where n is the index of the first value higher than key or
592 * a.length if there is no such value.
593 * @throws ClassCastException if key could not be compared with one of the
595 * @throws NullPointerException if a null element is compared with natural
596 * ordering (only possible when c is null)
598 public static <T
> int binarySearch(T
[] a
, T key
, Comparator
<?
super T
> c
)
602 return binarySearch(a
, 0, a
.length
- 1, key
, c
);
606 * Perform a binary search of a range of an Object array for a key using
607 * a {@link Comparator}. The range must be sorted (as by the
608 * <code>sort(Object[], int, int)</code> method) - if it is not, the
609 * behaviour of this method is undefined, and may be an infinite loop. If
610 * the array contains the key more than once, any one of them may be found.
611 * Note: although the specification allows for an infinite loop if the array
612 * is unsorted, it will not happen in this implementation.
614 * @param a the array to search (must be sorted)
615 * @param low the lowest index to search from.
616 * @param hi the highest index to search to.
617 * @param key the value to search for
618 * @param c the comparator by which the array is sorted; or null to
619 * use the elements' natural order
620 * @return the index at which the key was found, or -n-1 if it was not
621 * found, where n is the index of the first value higher than key or
622 * a.length if there is no such value.
623 * @throws ClassCastException if key could not be compared with one of the
625 * @throws IllegalArgumentException if <code>low > hi</code>
626 * @throws ArrayIndexOutOfBoundsException if <code>low < 0</code> or
627 * <code>hi > a.length</code>.
629 public static <T
> int binarySearch(T
[] a
, int low
, int hi
, T key
,
630 Comparator
<?
super T
> c
)
633 throw new IllegalArgumentException("The start index is higher than " +
634 "the finish index.");
635 if (low
< 0 || hi
> a
.length
)
636 throw new ArrayIndexOutOfBoundsException("One of the indices is out " +
641 mid
= (low
+ hi
) >>> 1;
642 // NOTE: Please keep the order of a[mid] and key. Although
643 // not required by the specs, the RI has it in this order as
644 // well, and real programs (erroneously) depend on it.
645 final int d
= Collections
.compare(a
[mid
], key
, c
);
651 // This gets the insertion point right on the last loop
660 * Compare two boolean arrays for equality.
662 * @param a1 the first array to compare
663 * @param a2 the second array to compare
664 * @return true if a1 and a2 are both null, or if a2 is of the same length
665 * as a1, and for each 0 <= i < a1.length, a1[i] == a2[i]
667 public static boolean equals(boolean[] a1
, boolean[] a2
)
669 // Quick test which saves comparing elements of the same array, and also
670 // catches the case that both are null.
674 if (null == a1
|| null == a2
)
677 // If they're the same length, test each element
678 if (a1
.length
== a2
.length
)
690 * Compare two byte arrays for equality.
692 * @param a1 the first array to compare
693 * @param a2 the second array to compare
694 * @return true if a1 and a2 are both null, or if a2 is of the same length
695 * as a1, and for each 0 <= i < a1.length, a1[i] == a2[i]
697 public static boolean equals(byte[] a1
, byte[] a2
)
699 // Quick test which saves comparing elements of the same array, and also
700 // catches the case that both are null.
704 if (null == a1
|| null == a2
)
707 // If they're the same length, test each element
708 if (a1
.length
== a2
.length
)
720 * Compare two char arrays for equality.
722 * @param a1 the first array to compare
723 * @param a2 the second array to compare
724 * @return true if a1 and a2 are both null, or if a2 is of the same length
725 * as a1, and for each 0 <= i < a1.length, a1[i] == a2[i]
727 public static boolean equals(char[] a1
, char[] a2
)
729 // Quick test which saves comparing elements of the same array, and also
730 // catches the case that both are null.
734 if (null == a1
|| null == a2
)
737 // If they're the same length, test each element
738 if (a1
.length
== a2
.length
)
750 * Compare two short arrays for equality.
752 * @param a1 the first array to compare
753 * @param a2 the second array to compare
754 * @return true if a1 and a2 are both null, or if a2 is of the same length
755 * as a1, and for each 0 <= i < a1.length, a1[i] == a2[i]
757 public static boolean equals(short[] a1
, short[] a2
)
759 // Quick test which saves comparing elements of the same array, and also
760 // catches the case that both are null.
764 if (null == a1
|| null == a2
)
767 // If they're the same length, test each element
768 if (a1
.length
== a2
.length
)
780 * Compare two int arrays for equality.
782 * @param a1 the first array to compare
783 * @param a2 the second array to compare
784 * @return true if a1 and a2 are both null, or if a2 is of the same length
785 * as a1, and for each 0 <= i < a1.length, a1[i] == a2[i]
787 public static boolean equals(int[] a1
, int[] a2
)
789 // Quick test which saves comparing elements of the same array, and also
790 // catches the case that both are null.
794 if (null == a1
|| null == a2
)
797 // If they're the same length, test each element
798 if (a1
.length
== a2
.length
)
810 * Compare two long arrays for equality.
812 * @param a1 the first array to compare
813 * @param a2 the second array to compare
814 * @return true if a1 and a2 are both null, or if a2 is of the same length
815 * as a1, and for each 0 <= i < a1.length, a1[i] == a2[i]
817 public static boolean equals(long[] a1
, long[] a2
)
819 // Quick test which saves comparing elements of the same array, and also
820 // catches the case that both are null.
824 if (null == a1
|| null == a2
)
827 // If they're the same length, test each element
828 if (a1
.length
== a2
.length
)
840 * Compare two float arrays for equality.
842 * @param a1 the first array to compare
843 * @param a2 the second array to compare
844 * @return true if a1 and a2 are both null, or if a2 is of the same length
845 * as a1, and for each 0 <= i < a1.length, a1[i] == a2[i]
847 public static boolean equals(float[] a1
, float[] a2
)
849 // Quick test which saves comparing elements of the same array, and also
850 // catches the case that both are null.
854 if (null == a1
|| null == a2
)
857 // Must use Float.compare to take into account NaN, +-0.
858 // If they're the same length, test each element
859 if (a1
.length
== a2
.length
)
863 if (Float
.compare(a1
[i
], a2
[i
]) != 0)
871 * Compare two double arrays for equality.
873 * @param a1 the first array to compare
874 * @param a2 the second array to compare
875 * @return true if a1 and a2 are both null, or if a2 is of the same length
876 * as a1, and for each 0 <= i < a1.length, a1[i] == a2[i]
878 public static boolean equals(double[] a1
, double[] a2
)
880 // Quick test which saves comparing elements of the same array, and also
881 // catches the case that both are null.
885 if (null == a1
|| null == a2
)
888 // Must use Double.compare to take into account NaN, +-0.
889 // If they're the same length, test each element
890 if (a1
.length
== a2
.length
)
894 if (Double
.compare(a1
[i
], a2
[i
]) != 0)
902 * Compare two Object arrays for equality.
904 * @param a1 the first array to compare
905 * @param a2 the second array to compare
906 * @return true if a1 and a2 are both null, or if a1 is of the same length
907 * as a2, and for each 0 <= i < a.length, a1[i] == null ?
908 * a2[i] == null : a1[i].equals(a2[i]).
910 public static boolean equals(Object
[] a1
, Object
[] a2
)
912 // Quick test which saves comparing elements of the same array, and also
913 // catches the case that both are null.
917 if (null == a1
|| null == a2
)
920 // If they're the same length, test each element
921 if (a1
.length
== a2
.length
)
925 if (! AbstractCollection
.equals(a1
[i
], a2
[i
]))
935 * Fill an array with a boolean value.
937 * @param a the array to fill
938 * @param val the value to fill it with
940 public static void fill(boolean[] a
, boolean val
)
942 fill(a
, 0, a
.length
, val
);
946 * Fill a range of an array with a boolean value.
948 * @param a the array to fill
949 * @param fromIndex the index to fill from, inclusive
950 * @param toIndex the index to fill to, exclusive
951 * @param val the value to fill with
952 * @throws IllegalArgumentException if fromIndex > toIndex
953 * @throws ArrayIndexOutOfBoundsException if fromIndex < 0
954 * || toIndex > a.length
956 public static void fill(boolean[] a
, int fromIndex
, int toIndex
, boolean val
)
958 if (fromIndex
> toIndex
)
959 throw new IllegalArgumentException();
960 for (int i
= fromIndex
; i
< toIndex
; i
++)
965 * Fill an array with a byte value.
967 * @param a the array to fill
968 * @param val the value to fill it with
970 public static void fill(byte[] a
, byte val
)
972 fill(a
, 0, a
.length
, val
);
976 * Fill a range of an array with a byte value.
978 * @param a the array to fill
979 * @param fromIndex the index to fill from, inclusive
980 * @param toIndex the index to fill to, exclusive
981 * @param val the value to fill with
982 * @throws IllegalArgumentException if fromIndex > toIndex
983 * @throws ArrayIndexOutOfBoundsException if fromIndex < 0
984 * || toIndex > a.length
986 public static void fill(byte[] a
, int fromIndex
, int toIndex
, byte val
)
988 if (fromIndex
> toIndex
)
989 throw new IllegalArgumentException();
990 for (int i
= fromIndex
; i
< toIndex
; i
++)
995 * Fill an array with a char value.
997 * @param a the array to fill
998 * @param val the value to fill it with
1000 public static void fill(char[] a
, char val
)
1002 fill(a
, 0, a
.length
, val
);
1006 * Fill a range of an array with a char value.
1008 * @param a the array to fill
1009 * @param fromIndex the index to fill from, inclusive
1010 * @param toIndex the index to fill to, exclusive
1011 * @param val the value to fill with
1012 * @throws IllegalArgumentException if fromIndex > toIndex
1013 * @throws ArrayIndexOutOfBoundsException if fromIndex < 0
1014 * || toIndex > a.length
1016 public static void fill(char[] a
, int fromIndex
, int toIndex
, char val
)
1018 if (fromIndex
> toIndex
)
1019 throw new IllegalArgumentException();
1020 for (int i
= fromIndex
; i
< toIndex
; i
++)
1025 * Fill an array with a short value.
1027 * @param a the array to fill
1028 * @param val the value to fill it with
1030 public static void fill(short[] a
, short val
)
1032 fill(a
, 0, a
.length
, val
);
1036 * Fill a range of an array with a short value.
1038 * @param a the array to fill
1039 * @param fromIndex the index to fill from, inclusive
1040 * @param toIndex the index to fill to, exclusive
1041 * @param val the value to fill with
1042 * @throws IllegalArgumentException if fromIndex > toIndex
1043 * @throws ArrayIndexOutOfBoundsException if fromIndex < 0
1044 * || toIndex > a.length
1046 public static void fill(short[] a
, int fromIndex
, int toIndex
, short val
)
1048 if (fromIndex
> toIndex
)
1049 throw new IllegalArgumentException();
1050 for (int i
= fromIndex
; i
< toIndex
; i
++)
1055 * Fill an array with an int value.
1057 * @param a the array to fill
1058 * @param val the value to fill it with
1060 public static void fill(int[] a
, int val
)
1062 fill(a
, 0, a
.length
, val
);
1066 * Fill a range of an array with an int value.
1068 * @param a the array to fill
1069 * @param fromIndex the index to fill from, inclusive
1070 * @param toIndex the index to fill to, exclusive
1071 * @param val the value to fill with
1072 * @throws IllegalArgumentException if fromIndex > toIndex
1073 * @throws ArrayIndexOutOfBoundsException if fromIndex < 0
1074 * || toIndex > a.length
1076 public static void fill(int[] a
, int fromIndex
, int toIndex
, int val
)
1078 if (fromIndex
> toIndex
)
1079 throw new IllegalArgumentException();
1080 for (int i
= fromIndex
; i
< toIndex
; i
++)
1085 * Fill an array with a long value.
1087 * @param a the array to fill
1088 * @param val the value to fill it with
1090 public static void fill(long[] a
, long val
)
1092 fill(a
, 0, a
.length
, val
);
1096 * Fill a range of an array with a long value.
1098 * @param a the array to fill
1099 * @param fromIndex the index to fill from, inclusive
1100 * @param toIndex the index to fill to, exclusive
1101 * @param val the value to fill with
1102 * @throws IllegalArgumentException if fromIndex > toIndex
1103 * @throws ArrayIndexOutOfBoundsException if fromIndex < 0
1104 * || toIndex > a.length
1106 public static void fill(long[] a
, int fromIndex
, int toIndex
, long val
)
1108 if (fromIndex
> toIndex
)
1109 throw new IllegalArgumentException();
1110 for (int i
= fromIndex
; i
< toIndex
; i
++)
1115 * Fill an array with a float value.
1117 * @param a the array to fill
1118 * @param val the value to fill it with
1120 public static void fill(float[] a
, float val
)
1122 fill(a
, 0, a
.length
, val
);
1126 * Fill a range of an array with a float value.
1128 * @param a the array to fill
1129 * @param fromIndex the index to fill from, inclusive
1130 * @param toIndex the index to fill to, exclusive
1131 * @param val the value to fill with
1132 * @throws IllegalArgumentException if fromIndex > toIndex
1133 * @throws ArrayIndexOutOfBoundsException if fromIndex < 0
1134 * || toIndex > a.length
1136 public static void fill(float[] a
, int fromIndex
, int toIndex
, float val
)
1138 if (fromIndex
> toIndex
)
1139 throw new IllegalArgumentException();
1140 for (int i
= fromIndex
; i
< toIndex
; i
++)
1145 * Fill an array with a double value.
1147 * @param a the array to fill
1148 * @param val the value to fill it with
1150 public static void fill(double[] a
, double val
)
1152 fill(a
, 0, a
.length
, val
);
1156 * Fill a range of an array with a double value.
1158 * @param a the array to fill
1159 * @param fromIndex the index to fill from, inclusive
1160 * @param toIndex the index to fill to, exclusive
1161 * @param val the value to fill with
1162 * @throws IllegalArgumentException if fromIndex > toIndex
1163 * @throws ArrayIndexOutOfBoundsException if fromIndex < 0
1164 * || toIndex > a.length
1166 public static void fill(double[] a
, int fromIndex
, int toIndex
, double val
)
1168 if (fromIndex
> toIndex
)
1169 throw new IllegalArgumentException();
1170 for (int i
= fromIndex
; i
< toIndex
; i
++)
1175 * Fill an array with an Object value.
1177 * @param a the array to fill
1178 * @param val the value to fill it with
1179 * @throws ClassCastException if val is not an instance of the element
1182 public static void fill(Object
[] a
, Object val
)
1184 fill(a
, 0, a
.length
, val
);
1188 * Fill a range of an array with an Object value.
1190 * @param a the array to fill
1191 * @param fromIndex the index to fill from, inclusive
1192 * @param toIndex the index to fill to, exclusive
1193 * @param val the value to fill with
1194 * @throws ClassCastException if val is not an instance of the element
1196 * @throws IllegalArgumentException if fromIndex > toIndex
1197 * @throws ArrayIndexOutOfBoundsException if fromIndex < 0
1198 * || toIndex > a.length
1200 public static void fill(Object
[] a
, int fromIndex
, int toIndex
, Object val
)
1202 if (fromIndex
> toIndex
)
1203 throw new IllegalArgumentException();
1204 for (int i
= fromIndex
; i
< toIndex
; i
++)
1210 // Thanks to Paul Fisher (rao@gnu.org) for finding this quicksort algorithm
1211 // as specified by Sun and porting it to Java. The algorithm is an optimised
1212 // quicksort, as described in Jon L. Bentley and M. Douglas McIlroy's
1213 // "Engineering a Sort Function", Software-Practice and Experience, Vol.
1214 // 23(11) P. 1249-1265 (November 1993). This algorithm gives n*log(n)
1215 // performance on many arrays that would take quadratic time with a standard
1219 * Performs a stable sort on the elements, arranging them according to their
1222 * @param a the byte array to sort
1224 public static void sort(byte[] a
)
1226 qsort(a
, 0, a
.length
);
1230 * Performs a stable sort on the elements, arranging them according to their
1233 * @param a the byte array to sort
1234 * @param fromIndex the first index to sort (inclusive)
1235 * @param toIndex the last index to sort (exclusive)
1236 * @throws IllegalArgumentException if fromIndex > toIndex
1237 * @throws ArrayIndexOutOfBoundsException if fromIndex < 0
1238 * || toIndex > a.length
1240 public static void sort(byte[] a
, int fromIndex
, int toIndex
)
1242 if (fromIndex
> toIndex
)
1243 throw new IllegalArgumentException();
1245 throw new ArrayIndexOutOfBoundsException();
1246 qsort(a
, fromIndex
, toIndex
- fromIndex
);
1250 * Finds the index of the median of three array elements.
1252 * @param a the first index
1253 * @param b the second index
1254 * @param c the third index
1255 * @param d the array
1256 * @return the index (a, b, or c) which has the middle value of the three
1258 private static int med3(int a
, int b
, int c
, byte[] d
)
1261 ?
(d
[b
] < d
[c
] ? b
: d
[a
] < d
[c
] ? c
: a
)
1262 : (d
[b
] > d
[c
] ? b
: d
[a
] > d
[c
] ? c
: a
));
1266 * Swaps the elements at two locations of an array
1268 * @param i the first index
1269 * @param j the second index
1270 * @param a the array
1272 private static void swap(int i
, int j
, byte[] a
)
1280 * Swaps two ranges of an array.
1282 * @param i the first range start
1283 * @param j the second range start
1284 * @param n the element count
1285 * @param a the array
1287 private static void vecswap(int i
, int j
, int n
, byte[] a
)
1289 for ( ; n
> 0; i
++, j
++, n
--)
1294 * Performs a recursive modified quicksort.
1296 * @param array the array to sort
1297 * @param from the start index (inclusive)
1298 * @param count the number of elements to sort
1300 private static void qsort(byte[] array
, int from
, int count
)
1302 // Use an insertion sort on small arrays.
1305 for (int i
= from
+ 1; i
< from
+ count
; i
++)
1306 for (int j
= i
; j
> from
&& array
[j
- 1] > array
[j
]; j
--)
1307 swap(j
, j
- 1, array
);
1311 // Determine a good median element.
1312 int mid
= from
+ count
/ 2;
1314 int hi
= from
+ count
- 1;
1317 { // big arrays, pseudomedian of 9
1319 lo
= med3(lo
, lo
+ s
, lo
+ 2 * s
, array
);
1320 mid
= med3(mid
- s
, mid
, mid
+ s
, array
);
1321 hi
= med3(hi
- 2 * s
, hi
- s
, hi
, array
);
1323 mid
= med3(lo
, mid
, hi
, array
);
1328 // Pull the median element out of the fray, and use it as a pivot.
1329 swap(from
, mid
, array
);
1331 c
= d
= from
+ count
- 1;
1333 // Repeatedly move b and c to each other, swapping elements so
1334 // that all elements before index b are less than the pivot, and all
1335 // elements after index c are greater than the pivot. a and b track
1336 // the elements equal to the pivot.
1339 while (b
<= c
&& (comp
= array
[b
] - array
[from
]) <= 0)
1348 while (c
>= b
&& (comp
= array
[c
] - array
[from
]) >= 0)
1364 // Swap pivot(s) back in place, the recurse on left and right sections.
1367 span
= Math
.min(a
- from
, b
- a
);
1368 vecswap(from
, b
- span
, span
, array
);
1370 span
= Math
.min(d
- c
, hi
- d
- 1);
1371 vecswap(b
, hi
- span
, span
, array
);
1375 qsort(array
, from
, span
);
1379 qsort(array
, hi
- span
, span
);
1383 * Performs a stable sort on the elements, arranging them according to their
1386 * @param a the char array to sort
1388 public static void sort(char[] a
)
1390 qsort(a
, 0, a
.length
);
1394 * Performs a stable sort on the elements, arranging them according to their
1397 * @param a the char array to sort
1398 * @param fromIndex the first index to sort (inclusive)
1399 * @param toIndex the last index to sort (exclusive)
1400 * @throws IllegalArgumentException if fromIndex > toIndex
1401 * @throws ArrayIndexOutOfBoundsException if fromIndex < 0
1402 * || toIndex > a.length
1404 public static void sort(char[] a
, int fromIndex
, int toIndex
)
1406 if (fromIndex
> toIndex
)
1407 throw new IllegalArgumentException();
1409 throw new ArrayIndexOutOfBoundsException();
1410 qsort(a
, fromIndex
, toIndex
- fromIndex
);
1414 * Finds the index of the median of three array elements.
1416 * @param a the first index
1417 * @param b the second index
1418 * @param c the third index
1419 * @param d the array
1420 * @return the index (a, b, or c) which has the middle value of the three
1422 private static int med3(int a
, int b
, int c
, char[] d
)
1425 ?
(d
[b
] < d
[c
] ? b
: d
[a
] < d
[c
] ? c
: a
)
1426 : (d
[b
] > d
[c
] ? b
: d
[a
] > d
[c
] ? c
: a
));
1430 * Swaps the elements at two locations of an array
1432 * @param i the first index
1433 * @param j the second index
1434 * @param a the array
1436 private static void swap(int i
, int j
, char[] a
)
1444 * Swaps two ranges of an array.
1446 * @param i the first range start
1447 * @param j the second range start
1448 * @param n the element count
1449 * @param a the array
1451 private static void vecswap(int i
, int j
, int n
, char[] a
)
1453 for ( ; n
> 0; i
++, j
++, n
--)
1458 * Performs a recursive modified quicksort.
1460 * @param array the array to sort
1461 * @param from the start index (inclusive)
1462 * @param count the number of elements to sort
1464 private static void qsort(char[] array
, int from
, int count
)
1466 // Use an insertion sort on small arrays.
1469 for (int i
= from
+ 1; i
< from
+ count
; i
++)
1470 for (int j
= i
; j
> from
&& array
[j
- 1] > array
[j
]; j
--)
1471 swap(j
, j
- 1, array
);
1475 // Determine a good median element.
1476 int mid
= from
+ count
/ 2;
1478 int hi
= from
+ count
- 1;
1481 { // big arrays, pseudomedian of 9
1483 lo
= med3(lo
, lo
+ s
, lo
+ 2 * s
, array
);
1484 mid
= med3(mid
- s
, mid
, mid
+ s
, array
);
1485 hi
= med3(hi
- 2 * s
, hi
- s
, hi
, array
);
1487 mid
= med3(lo
, mid
, hi
, array
);
1492 // Pull the median element out of the fray, and use it as a pivot.
1493 swap(from
, mid
, array
);
1495 c
= d
= from
+ count
- 1;
1497 // Repeatedly move b and c to each other, swapping elements so
1498 // that all elements before index b are less than the pivot, and all
1499 // elements after index c are greater than the pivot. a and b track
1500 // the elements equal to the pivot.
1503 while (b
<= c
&& (comp
= array
[b
] - array
[from
]) <= 0)
1512 while (c
>= b
&& (comp
= array
[c
] - array
[from
]) >= 0)
1528 // Swap pivot(s) back in place, the recurse on left and right sections.
1531 span
= Math
.min(a
- from
, b
- a
);
1532 vecswap(from
, b
- span
, span
, array
);
1534 span
= Math
.min(d
- c
, hi
- d
- 1);
1535 vecswap(b
, hi
- span
, span
, array
);
1539 qsort(array
, from
, span
);
1543 qsort(array
, hi
- span
, span
);
1547 * Performs a stable sort on the elements, arranging them according to their
1550 * @param a the short array to sort
1552 public static void sort(short[] a
)
1554 qsort(a
, 0, a
.length
);
1558 * Performs a stable sort on the elements, arranging them according to their
1561 * @param a the short array to sort
1562 * @param fromIndex the first index to sort (inclusive)
1563 * @param toIndex the last index to sort (exclusive)
1564 * @throws IllegalArgumentException if fromIndex > toIndex
1565 * @throws ArrayIndexOutOfBoundsException if fromIndex < 0
1566 * || toIndex > a.length
1568 public static void sort(short[] a
, int fromIndex
, int toIndex
)
1570 if (fromIndex
> toIndex
)
1571 throw new IllegalArgumentException();
1573 throw new ArrayIndexOutOfBoundsException();
1574 qsort(a
, fromIndex
, toIndex
- fromIndex
);
1578 * Finds the index of the median of three array elements.
1580 * @param a the first index
1581 * @param b the second index
1582 * @param c the third index
1583 * @param d the array
1584 * @return the index (a, b, or c) which has the middle value of the three
1586 private static int med3(int a
, int b
, int c
, short[] d
)
1589 ?
(d
[b
] < d
[c
] ? b
: d
[a
] < d
[c
] ? c
: a
)
1590 : (d
[b
] > d
[c
] ? b
: d
[a
] > d
[c
] ? c
: a
));
1594 * Swaps the elements at two locations of an array
1596 * @param i the first index
1597 * @param j the second index
1598 * @param a the array
1600 private static void swap(int i
, int j
, short[] a
)
1608 * Swaps two ranges of an array.
1610 * @param i the first range start
1611 * @param j the second range start
1612 * @param n the element count
1613 * @param a the array
1615 private static void vecswap(int i
, int j
, int n
, short[] a
)
1617 for ( ; n
> 0; i
++, j
++, n
--)
1622 * Performs a recursive modified quicksort.
1624 * @param array the array to sort
1625 * @param from the start index (inclusive)
1626 * @param count the number of elements to sort
1628 private static void qsort(short[] array
, int from
, int count
)
1630 // Use an insertion sort on small arrays.
1633 for (int i
= from
+ 1; i
< from
+ count
; i
++)
1634 for (int j
= i
; j
> from
&& array
[j
- 1] > array
[j
]; j
--)
1635 swap(j
, j
- 1, array
);
1639 // Determine a good median element.
1640 int mid
= from
+ count
/ 2;
1642 int hi
= from
+ count
- 1;
1645 { // big arrays, pseudomedian of 9
1647 lo
= med3(lo
, lo
+ s
, lo
+ 2 * s
, array
);
1648 mid
= med3(mid
- s
, mid
, mid
+ s
, array
);
1649 hi
= med3(hi
- 2 * s
, hi
- s
, hi
, array
);
1651 mid
= med3(lo
, mid
, hi
, array
);
1656 // Pull the median element out of the fray, and use it as a pivot.
1657 swap(from
, mid
, array
);
1659 c
= d
= from
+ count
- 1;
1661 // Repeatedly move b and c to each other, swapping elements so
1662 // that all elements before index b are less than the pivot, and all
1663 // elements after index c are greater than the pivot. a and b track
1664 // the elements equal to the pivot.
1667 while (b
<= c
&& (comp
= array
[b
] - array
[from
]) <= 0)
1676 while (c
>= b
&& (comp
= array
[c
] - array
[from
]) >= 0)
1692 // Swap pivot(s) back in place, the recurse on left and right sections.
1695 span
= Math
.min(a
- from
, b
- a
);
1696 vecswap(from
, b
- span
, span
, array
);
1698 span
= Math
.min(d
- c
, hi
- d
- 1);
1699 vecswap(b
, hi
- span
, span
, array
);
1703 qsort(array
, from
, span
);
1707 qsort(array
, hi
- span
, span
);
1711 * Performs a stable sort on the elements, arranging them according to their
1714 * @param a the int array to sort
1716 public static void sort(int[] a
)
1718 qsort(a
, 0, a
.length
);
1722 * Performs a stable sort on the elements, arranging them according to their
1725 * @param a the int array to sort
1726 * @param fromIndex the first index to sort (inclusive)
1727 * @param toIndex the last index to sort (exclusive)
1728 * @throws IllegalArgumentException if fromIndex > toIndex
1729 * @throws ArrayIndexOutOfBoundsException if fromIndex < 0
1730 * || toIndex > a.length
1732 public static void sort(int[] a
, int fromIndex
, int toIndex
)
1734 if (fromIndex
> toIndex
)
1735 throw new IllegalArgumentException();
1737 throw new ArrayIndexOutOfBoundsException();
1738 qsort(a
, fromIndex
, toIndex
- fromIndex
);
1742 * Finds the index of the median of three array elements.
1744 * @param a the first index
1745 * @param b the second index
1746 * @param c the third index
1747 * @param d the array
1748 * @return the index (a, b, or c) which has the middle value of the three
1750 private static int med3(int a
, int b
, int c
, int[] d
)
1753 ?
(d
[b
] < d
[c
] ? b
: d
[a
] < d
[c
] ? c
: a
)
1754 : (d
[b
] > d
[c
] ? b
: d
[a
] > d
[c
] ? c
: a
));
1758 * Swaps the elements at two locations of an array
1760 * @param i the first index
1761 * @param j the second index
1762 * @param a the array
1764 private static void swap(int i
, int j
, int[] a
)
1772 * Swaps two ranges of an array.
1774 * @param i the first range start
1775 * @param j the second range start
1776 * @param n the element count
1777 * @param a the array
1779 private static void vecswap(int i
, int j
, int n
, int[] a
)
1781 for ( ; n
> 0; i
++, j
++, n
--)
1786 * Compares two integers in natural order, since a - b is inadequate.
1788 * @param a the first int
1789 * @param b the second int
1790 * @return < 0, 0, or > 0 accorting to the comparison
1792 private static int compare(int a
, int b
)
1794 return a
< b ?
-1 : a
== b ?
0 : 1;
1798 * Performs a recursive modified quicksort.
1800 * @param array the array to sort
1801 * @param from the start index (inclusive)
1802 * @param count the number of elements to sort
1804 private static void qsort(int[] array
, int from
, int count
)
1806 // Use an insertion sort on small arrays.
1809 for (int i
= from
+ 1; i
< from
+ count
; i
++)
1810 for (int j
= i
; j
> from
&& array
[j
- 1] > array
[j
]; j
--)
1811 swap(j
, j
- 1, array
);
1815 // Determine a good median element.
1816 int mid
= from
+ count
/ 2;
1818 int hi
= from
+ count
- 1;
1821 { // big arrays, pseudomedian of 9
1823 lo
= med3(lo
, lo
+ s
, lo
+ 2 * s
, array
);
1824 mid
= med3(mid
- s
, mid
, mid
+ s
, array
);
1825 hi
= med3(hi
- 2 * s
, hi
- s
, hi
, array
);
1827 mid
= med3(lo
, mid
, hi
, array
);
1832 // Pull the median element out of the fray, and use it as a pivot.
1833 swap(from
, mid
, array
);
1835 c
= d
= from
+ count
- 1;
1837 // Repeatedly move b and c to each other, swapping elements so
1838 // that all elements before index b are less than the pivot, and all
1839 // elements after index c are greater than the pivot. a and b track
1840 // the elements equal to the pivot.
1843 while (b
<= c
&& (comp
= compare(array
[b
], array
[from
])) <= 0)
1852 while (c
>= b
&& (comp
= compare(array
[c
], array
[from
])) >= 0)
1868 // Swap pivot(s) back in place, the recurse on left and right sections.
1871 span
= Math
.min(a
- from
, b
- a
);
1872 vecswap(from
, b
- span
, span
, array
);
1874 span
= Math
.min(d
- c
, hi
- d
- 1);
1875 vecswap(b
, hi
- span
, span
, array
);
1879 qsort(array
, from
, span
);
1883 qsort(array
, hi
- span
, span
);
1887 * Performs a stable sort on the elements, arranging them according to their
1890 * @param a the long array to sort
1892 public static void sort(long[] a
)
1894 qsort(a
, 0, a
.length
);
1898 * Performs a stable sort on the elements, arranging them according to their
1901 * @param a the long array to sort
1902 * @param fromIndex the first index to sort (inclusive)
1903 * @param toIndex the last index to sort (exclusive)
1904 * @throws IllegalArgumentException if fromIndex > toIndex
1905 * @throws ArrayIndexOutOfBoundsException if fromIndex < 0
1906 * || toIndex > a.length
1908 public static void sort(long[] a
, int fromIndex
, int toIndex
)
1910 if (fromIndex
> toIndex
)
1911 throw new IllegalArgumentException();
1913 throw new ArrayIndexOutOfBoundsException();
1914 qsort(a
, fromIndex
, toIndex
- fromIndex
);
1918 * Finds the index of the median of three array elements.
1920 * @param a the first index
1921 * @param b the second index
1922 * @param c the third index
1923 * @param d the array
1924 * @return the index (a, b, or c) which has the middle value of the three
1926 private static int med3(int a
, int b
, int c
, long[] d
)
1929 ?
(d
[b
] < d
[c
] ? b
: d
[a
] < d
[c
] ? c
: a
)
1930 : (d
[b
] > d
[c
] ? b
: d
[a
] > d
[c
] ? c
: a
));
1934 * Swaps the elements at two locations of an array
1936 * @param i the first index
1937 * @param j the second index
1938 * @param a the array
1940 private static void swap(int i
, int j
, long[] a
)
1948 * Swaps two ranges of an array.
1950 * @param i the first range start
1951 * @param j the second range start
1952 * @param n the element count
1953 * @param a the array
1955 private static void vecswap(int i
, int j
, int n
, long[] a
)
1957 for ( ; n
> 0; i
++, j
++, n
--)
1962 * Compares two longs in natural order, since a - b is inadequate.
1964 * @param a the first long
1965 * @param b the second long
1966 * @return < 0, 0, or > 0 accorting to the comparison
1968 private static int compare(long a
, long b
)
1970 return a
< b ?
-1 : a
== b ?
0 : 1;
1974 * Performs a recursive modified quicksort.
1976 * @param array the array to sort
1977 * @param from the start index (inclusive)
1978 * @param count the number of elements to sort
1980 private static void qsort(long[] array
, int from
, int count
)
1982 // Use an insertion sort on small arrays.
1985 for (int i
= from
+ 1; i
< from
+ count
; i
++)
1986 for (int j
= i
; j
> from
&& array
[j
- 1] > array
[j
]; j
--)
1987 swap(j
, j
- 1, array
);
1991 // Determine a good median element.
1992 int mid
= from
+ count
/ 2;
1994 int hi
= from
+ count
- 1;
1997 { // big arrays, pseudomedian of 9
1999 lo
= med3(lo
, lo
+ s
, lo
+ 2 * s
, array
);
2000 mid
= med3(mid
- s
, mid
, mid
+ s
, array
);
2001 hi
= med3(hi
- 2 * s
, hi
- s
, hi
, array
);
2003 mid
= med3(lo
, mid
, hi
, array
);
2008 // Pull the median element out of the fray, and use it as a pivot.
2009 swap(from
, mid
, array
);
2011 c
= d
= from
+ count
- 1;
2013 // Repeatedly move b and c to each other, swapping elements so
2014 // that all elements before index b are less than the pivot, and all
2015 // elements after index c are greater than the pivot. a and b track
2016 // the elements equal to the pivot.
2019 while (b
<= c
&& (comp
= compare(array
[b
], array
[from
])) <= 0)
2028 while (c
>= b
&& (comp
= compare(array
[c
], array
[from
])) >= 0)
2044 // Swap pivot(s) back in place, the recurse on left and right sections.
2047 span
= Math
.min(a
- from
, b
- a
);
2048 vecswap(from
, b
- span
, span
, array
);
2050 span
= Math
.min(d
- c
, hi
- d
- 1);
2051 vecswap(b
, hi
- span
, span
, array
);
2055 qsort(array
, from
, span
);
2059 qsort(array
, hi
- span
, span
);
2063 * Performs a stable sort on the elements, arranging them according to their
2066 * @param a the float array to sort
2068 public static void sort(float[] a
)
2070 qsort(a
, 0, a
.length
);
2074 * Performs a stable sort on the elements, arranging them according to their
2077 * @param a the float array to sort
2078 * @param fromIndex the first index to sort (inclusive)
2079 * @param toIndex the last index to sort (exclusive)
2080 * @throws IllegalArgumentException if fromIndex > toIndex
2081 * @throws ArrayIndexOutOfBoundsException if fromIndex < 0
2082 * || toIndex > a.length
2084 public static void sort(float[] a
, int fromIndex
, int toIndex
)
2086 if (fromIndex
> toIndex
)
2087 throw new IllegalArgumentException();
2089 throw new ArrayIndexOutOfBoundsException();
2090 qsort(a
, fromIndex
, toIndex
- fromIndex
);
2094 * Finds the index of the median of three array elements.
2096 * @param a the first index
2097 * @param b the second index
2098 * @param c the third index
2099 * @param d the array
2100 * @return the index (a, b, or c) which has the middle value of the three
2102 private static int med3(int a
, int b
, int c
, float[] d
)
2104 return (Float
.compare(d
[a
], d
[b
]) < 0
2105 ?
(Float
.compare(d
[b
], d
[c
]) < 0 ? b
2106 : Float
.compare(d
[a
], d
[c
]) < 0 ? c
: a
)
2107 : (Float
.compare(d
[b
], d
[c
]) > 0 ? b
2108 : Float
.compare(d
[a
], d
[c
]) > 0 ? c
: a
));
2112 * Swaps the elements at two locations of an array
2114 * @param i the first index
2115 * @param j the second index
2116 * @param a the array
2118 private static void swap(int i
, int j
, float[] a
)
2126 * Swaps two ranges of an array.
2128 * @param i the first range start
2129 * @param j the second range start
2130 * @param n the element count
2131 * @param a the array
2133 private static void vecswap(int i
, int j
, int n
, float[] a
)
2135 for ( ; n
> 0; i
++, j
++, n
--)
2140 * Performs a recursive modified quicksort.
2142 * @param array the array to sort
2143 * @param from the start index (inclusive)
2144 * @param count the number of elements to sort
2146 private static void qsort(float[] array
, int from
, int count
)
2148 // Use an insertion sort on small arrays.
2151 for (int i
= from
+ 1; i
< from
+ count
; i
++)
2153 j
> from
&& Float
.compare(array
[j
- 1], array
[j
]) > 0;
2156 swap(j
, j
- 1, array
);
2161 // Determine a good median element.
2162 int mid
= from
+ count
/ 2;
2164 int hi
= from
+ count
- 1;
2167 { // big arrays, pseudomedian of 9
2169 lo
= med3(lo
, lo
+ s
, lo
+ 2 * s
, array
);
2170 mid
= med3(mid
- s
, mid
, mid
+ s
, array
);
2171 hi
= med3(hi
- 2 * s
, hi
- s
, hi
, array
);
2173 mid
= med3(lo
, mid
, hi
, array
);
2178 // Pull the median element out of the fray, and use it as a pivot.
2179 swap(from
, mid
, array
);
2181 c
= d
= from
+ count
- 1;
2183 // Repeatedly move b and c to each other, swapping elements so
2184 // that all elements before index b are less than the pivot, and all
2185 // elements after index c are greater than the pivot. a and b track
2186 // the elements equal to the pivot.
2189 while (b
<= c
&& (comp
= Float
.compare(array
[b
], array
[from
])) <= 0)
2198 while (c
>= b
&& (comp
= Float
.compare(array
[c
], array
[from
])) >= 0)
2214 // Swap pivot(s) back in place, the recurse on left and right sections.
2217 span
= Math
.min(a
- from
, b
- a
);
2218 vecswap(from
, b
- span
, span
, array
);
2220 span
= Math
.min(d
- c
, hi
- d
- 1);
2221 vecswap(b
, hi
- span
, span
, array
);
2225 qsort(array
, from
, span
);
2229 qsort(array
, hi
- span
, span
);
2233 * Performs a stable sort on the elements, arranging them according to their
2236 * @param a the double array to sort
2238 public static void sort(double[] a
)
2240 qsort(a
, 0, a
.length
);
2244 * Performs a stable sort on the elements, arranging them according to their
2247 * @param a the double array to sort
2248 * @param fromIndex the first index to sort (inclusive)
2249 * @param toIndex the last index to sort (exclusive)
2250 * @throws IllegalArgumentException if fromIndex > toIndex
2251 * @throws ArrayIndexOutOfBoundsException if fromIndex < 0
2252 * || toIndex > a.length
2254 public static void sort(double[] a
, int fromIndex
, int toIndex
)
2256 if (fromIndex
> toIndex
)
2257 throw new IllegalArgumentException();
2259 throw new ArrayIndexOutOfBoundsException();
2260 qsort(a
, fromIndex
, toIndex
- fromIndex
);
2264 * Finds the index of the median of three array elements.
2266 * @param a the first index
2267 * @param b the second index
2268 * @param c the third index
2269 * @param d the array
2270 * @return the index (a, b, or c) which has the middle value of the three
2272 private static int med3(int a
, int b
, int c
, double[] d
)
2274 return (Double
.compare(d
[a
], d
[b
]) < 0
2275 ?
(Double
.compare(d
[b
], d
[c
]) < 0 ? b
2276 : Double
.compare(d
[a
], d
[c
]) < 0 ? c
: a
)
2277 : (Double
.compare(d
[b
], d
[c
]) > 0 ? b
2278 : Double
.compare(d
[a
], d
[c
]) > 0 ? c
: a
));
2282 * Swaps the elements at two locations of an array
2284 * @param i the first index
2285 * @param j the second index
2286 * @param a the array
2288 private static void swap(int i
, int j
, double[] a
)
2296 * Swaps two ranges of an array.
2298 * @param i the first range start
2299 * @param j the second range start
2300 * @param n the element count
2301 * @param a the array
2303 private static void vecswap(int i
, int j
, int n
, double[] a
)
2305 for ( ; n
> 0; i
++, j
++, n
--)
2310 * Performs a recursive modified quicksort.
2312 * @param array the array to sort
2313 * @param from the start index (inclusive)
2314 * @param count the number of elements to sort
2316 private static void qsort(double[] array
, int from
, int count
)
2318 // Use an insertion sort on small arrays.
2321 for (int i
= from
+ 1; i
< from
+ count
; i
++)
2323 j
> from
&& Double
.compare(array
[j
- 1], array
[j
]) > 0;
2326 swap(j
, j
- 1, array
);
2331 // Determine a good median element.
2332 int mid
= from
+ count
/ 2;
2334 int hi
= from
+ count
- 1;
2337 { // big arrays, pseudomedian of 9
2339 lo
= med3(lo
, lo
+ s
, lo
+ 2 * s
, array
);
2340 mid
= med3(mid
- s
, mid
, mid
+ s
, array
);
2341 hi
= med3(hi
- 2 * s
, hi
- s
, hi
, array
);
2343 mid
= med3(lo
, mid
, hi
, array
);
2348 // Pull the median element out of the fray, and use it as a pivot.
2349 swap(from
, mid
, array
);
2351 c
= d
= from
+ count
- 1;
2353 // Repeatedly move b and c to each other, swapping elements so
2354 // that all elements before index b are less than the pivot, and all
2355 // elements after index c are greater than the pivot. a and b track
2356 // the elements equal to the pivot.
2359 while (b
<= c
&& (comp
= Double
.compare(array
[b
], array
[from
])) <= 0)
2368 while (c
>= b
&& (comp
= Double
.compare(array
[c
], array
[from
])) >= 0)
2384 // Swap pivot(s) back in place, the recurse on left and right sections.
2387 span
= Math
.min(a
- from
, b
- a
);
2388 vecswap(from
, b
- span
, span
, array
);
2390 span
= Math
.min(d
- c
, hi
- d
- 1);
2391 vecswap(b
, hi
- span
, span
, array
);
2395 qsort(array
, from
, span
);
2399 qsort(array
, hi
- span
, span
);
2403 * Sort an array of Objects according to their natural ordering. The sort is
2404 * guaranteed to be stable, that is, equal elements will not be reordered.
2405 * The sort algorithm is a mergesort with the merge omitted if the last
2406 * element of one half comes before the first element of the other half. This
2407 * algorithm gives guaranteed O(n*log(n)) time, at the expense of making a
2408 * copy of the array.
2410 * @param a the array to be sorted
2411 * @throws ClassCastException if any two elements are not mutually
2413 * @throws NullPointerException if an element is null (since
2414 * null.compareTo cannot work)
2417 public static void sort(Object
[] a
)
2419 sort(a
, 0, a
.length
, null);
2423 * Sort an array of Objects according to a Comparator. The sort is
2424 * guaranteed to be stable, that is, equal elements will not be reordered.
2425 * The sort algorithm is a mergesort with the merge omitted if the last
2426 * element of one half comes before the first element of the other half. This
2427 * algorithm gives guaranteed O(n*log(n)) time, at the expense of making a
2428 * copy of the array.
2430 * @param a the array to be sorted
2431 * @param c a Comparator to use in sorting the array; or null to indicate
2432 * the elements' natural order
2433 * @throws ClassCastException if any two elements are not mutually
2434 * comparable by the Comparator provided
2435 * @throws NullPointerException if a null element is compared with natural
2436 * ordering (only possible when c is null)
2438 public static <T
> void sort(T
[] a
, Comparator
<?
super T
> c
)
2440 sort(a
, 0, a
.length
, c
);
2444 * Sort an array of Objects according to their natural ordering. The sort is
2445 * guaranteed to be stable, that is, equal elements will not be reordered.
2446 * The sort algorithm is a mergesort with the merge omitted if the last
2447 * element of one half comes before the first element of the other half. This
2448 * algorithm gives guaranteed O(n*log(n)) time, at the expense of making a
2449 * copy of the array.
2451 * @param a the array to be sorted
2452 * @param fromIndex the index of the first element to be sorted
2453 * @param toIndex the index of the last element to be sorted plus one
2454 * @throws ClassCastException if any two elements are not mutually
2456 * @throws NullPointerException if an element is null (since
2457 * null.compareTo cannot work)
2458 * @throws ArrayIndexOutOfBoundsException if fromIndex and toIndex
2460 * @throws IllegalArgumentException if fromIndex > toIndex
2462 public static void sort(Object
[] a
, int fromIndex
, int toIndex
)
2464 sort(a
, fromIndex
, toIndex
, null);
2468 * Sort an array of Objects according to a Comparator. The sort is
2469 * guaranteed to be stable, that is, equal elements will not be reordered.
2470 * The sort algorithm is a mergesort with the merge omitted if the last
2471 * element of one half comes before the first element of the other half. This
2472 * algorithm gives guaranteed O(n*log(n)) time, at the expense of making a
2473 * copy of the array.
2475 * @param a the array to be sorted
2476 * @param fromIndex the index of the first element to be sorted
2477 * @param toIndex the index of the last element to be sorted plus one
2478 * @param c a Comparator to use in sorting the array; or null to indicate
2479 * the elements' natural order
2480 * @throws ClassCastException if any two elements are not mutually
2481 * comparable by the Comparator provided
2482 * @throws ArrayIndexOutOfBoundsException if fromIndex and toIndex
2484 * @throws IllegalArgumentException if fromIndex > toIndex
2485 * @throws NullPointerException if a null element is compared with natural
2486 * ordering (only possible when c is null)
2488 public static <T
> void sort(T
[] a
, int fromIndex
, int toIndex
,
2489 Comparator
<?
super T
> c
)
2491 if (fromIndex
> toIndex
)
2492 throw new IllegalArgumentException("fromIndex " + fromIndex
2493 + " > toIndex " + toIndex
);
2495 throw new ArrayIndexOutOfBoundsException();
2497 // In general, the code attempts to be simple rather than fast, the
2498 // idea being that a good optimising JIT will be able to optimise it
2499 // better than I can, and if I try it will make it more confusing for
2500 // the JIT. First presort the array in chunks of length 6 with insertion
2501 // sort. A mergesort would give too much overhead for this length.
2502 for (int chunk
= fromIndex
; chunk
< toIndex
; chunk
+= 6)
2504 int end
= Math
.min(chunk
+ 6, toIndex
);
2505 for (int i
= chunk
+ 1; i
< end
; i
++)
2507 if (Collections
.compare(a
[i
- 1], a
[i
], c
) > 0)
2509 // not already sorted
2518 && Collections
.compare(a
[j
- 1], elem
, c
) > 0);
2524 int len
= toIndex
- fromIndex
;
2525 // If length is smaller or equal 6 we are done.
2530 T
[] dest
= (T
[]) new Object
[len
];
2531 T
[] t
= null; // t is used for swapping src and dest
2533 // The difference of the fromIndex of the src and dest array.
2534 int srcDestDiff
= -fromIndex
;
2536 // The merges are done in this loop
2537 for (int size
= 6; size
< len
; size
<<= 1)
2539 for (int start
= fromIndex
; start
< toIndex
; start
+= size
<< 1)
2541 // mid is the start of the second sublist;
2542 // end the start of the next sublist (or end of array).
2543 int mid
= start
+ size
;
2544 int end
= Math
.min(toIndex
, mid
+ size
);
2546 // The second list is empty or the elements are already in
2547 // order - no need to merge
2549 || Collections
.compare(src
[mid
- 1], src
[mid
], c
) <= 0)
2551 System
.arraycopy(src
, start
,
2552 dest
, start
+ srcDestDiff
, end
- start
);
2554 // The two halves just need swapping - no need to merge
2556 else if (Collections
.compare(src
[start
], src
[end
- 1], c
) > 0)
2558 System
.arraycopy(src
, start
,
2559 dest
, end
- size
+ srcDestDiff
, size
);
2560 System
.arraycopy(src
, mid
,
2561 dest
, start
+ srcDestDiff
, end
- mid
);
2566 // Declare a lot of variables to save repeating
2567 // calculations. Hopefully a decent JIT will put these
2568 // in registers and make this fast
2571 int i
= start
+ srcDestDiff
;
2573 // The main merge loop; terminates as soon as either
2575 while (p1
< mid
&& p2
< end
)
2578 src
[(Collections
.compare(src
[p1
], src
[p2
], c
) <= 0
2582 // Finish up by copying the remainder of whichever half
2585 System
.arraycopy(src
, p1
, dest
, i
, mid
- p1
);
2587 System
.arraycopy(src
, p2
, dest
, i
, end
- p2
);
2590 // swap src and dest ready for the next merge
2594 fromIndex
+= srcDestDiff
;
2595 toIndex
+= srcDestDiff
;
2596 srcDestDiff
= -srcDestDiff
;
2599 // make sure the result ends up back in the right place. Note
2600 // that src and dest may have been swapped above, so src
2601 // contains the sorted array.
2604 // Note that fromIndex == 0.
2605 System
.arraycopy(src
, 0, a
, srcDestDiff
, toIndex
);
2610 * Returns a list "view" of the specified array. This method is intended to
2611 * make it easy to use the Collections API with existing array-based APIs and
2612 * programs. Changes in the list or the array show up in both places. The
2613 * list does not support element addition or removal, but does permit
2614 * value modification. The returned list implements both Serializable and
2617 * @param a the array to return a view of (<code>null</code> not permitted)
2618 * @return a fixed-size list, changes to which "write through" to the array
2620 * @throws NullPointerException if <code>a</code> is <code>null</code>.
2623 * @see Arrays.ArrayList
2625 public static <T
> List
<T
> asList(final T
... a
)
2627 return new Arrays
.ArrayList(a
);
2631 * Returns the hashcode of an array of long numbers. If two arrays
2632 * are equal, according to <code>equals()</code>, they should have the
2633 * same hashcode. The hashcode returned by the method is equal to that
2634 * obtained by the corresponding <code>List</code> object. This has the same
2635 * data, but represents longs in their wrapper class, <code>Long</code>.
2636 * For <code>null</code>, 0 is returned.
2638 * @param v an array of long numbers for which the hash code should be
2640 * @return the hash code of the array, or 0 if null was given.
2643 public static int hashCode(long[] v
)
2648 for (int i
= 0; i
< v
.length
; ++i
)
2650 int elt
= (int) (v
[i
] ^
(v
[i
] >>> 32));
2651 result
= 31 * result
+ elt
;
2657 * Returns the hashcode of an array of integer numbers. If two arrays
2658 * are equal, according to <code>equals()</code>, they should have the
2659 * same hashcode. The hashcode returned by the method is equal to that
2660 * obtained by the corresponding <code>List</code> object. This has the same
2661 * data, but represents ints in their wrapper class, <code>Integer</code>.
2662 * For <code>null</code>, 0 is returned.
2664 * @param v an array of integer numbers for which the hash code should be
2666 * @return the hash code of the array, or 0 if null was given.
2669 public static int hashCode(int[] v
)
2674 for (int i
= 0; i
< v
.length
; ++i
)
2675 result
= 31 * result
+ v
[i
];
2680 * Returns the hashcode of an array of short numbers. If two arrays
2681 * are equal, according to <code>equals()</code>, they should have the
2682 * same hashcode. The hashcode returned by the method is equal to that
2683 * obtained by the corresponding <code>List</code> object. This has the same
2684 * data, but represents shorts in their wrapper class, <code>Short</code>.
2685 * For <code>null</code>, 0 is returned.
2687 * @param v an array of short numbers for which the hash code should be
2689 * @return the hash code of the array, or 0 if null was given.
2692 public static int hashCode(short[] v
)
2697 for (int i
= 0; i
< v
.length
; ++i
)
2698 result
= 31 * result
+ v
[i
];
2703 * Returns the hashcode of an array of characters. If two arrays
2704 * are equal, according to <code>equals()</code>, they should have the
2705 * same hashcode. The hashcode returned by the method is equal to that
2706 * obtained by the corresponding <code>List</code> object. This has the same
2707 * data, but represents chars in their wrapper class, <code>Character</code>.
2708 * For <code>null</code>, 0 is returned.
2710 * @param v an array of characters for which the hash code should be
2712 * @return the hash code of the array, or 0 if null was given.
2715 public static int hashCode(char[] v
)
2720 for (int i
= 0; i
< v
.length
; ++i
)
2721 result
= 31 * result
+ v
[i
];
2726 * Returns the hashcode of an array of bytes. If two arrays
2727 * are equal, according to <code>equals()</code>, they should have the
2728 * same hashcode. The hashcode returned by the method is equal to that
2729 * obtained by the corresponding <code>List</code> object. This has the same
2730 * data, but represents bytes in their wrapper class, <code>Byte</code>.
2731 * For <code>null</code>, 0 is returned.
2733 * @param v an array of bytes for which the hash code should be
2735 * @return the hash code of the array, or 0 if null was given.
2738 public static int hashCode(byte[] v
)
2743 for (int i
= 0; i
< v
.length
; ++i
)
2744 result
= 31 * result
+ v
[i
];
2749 * Returns the hashcode of an array of booleans. If two arrays
2750 * are equal, according to <code>equals()</code>, they should have the
2751 * same hashcode. The hashcode returned by the method is equal to that
2752 * obtained by the corresponding <code>List</code> object. This has the same
2753 * data, but represents booleans in their wrapper class,
2754 * <code>Boolean</code>. For <code>null</code>, 0 is returned.
2756 * @param v an array of booleans for which the hash code should be
2758 * @return the hash code of the array, or 0 if null was given.
2761 public static int hashCode(boolean[] v
)
2766 for (int i
= 0; i
< v
.length
; ++i
)
2767 result
= 31 * result
+ (v
[i
] ?
1231 : 1237);
2772 * Returns the hashcode of an array of floats. If two arrays
2773 * are equal, according to <code>equals()</code>, they should have the
2774 * same hashcode. The hashcode returned by the method is equal to that
2775 * obtained by the corresponding <code>List</code> object. This has the same
2776 * data, but represents floats in their wrapper class, <code>Float</code>.
2777 * For <code>null</code>, 0 is returned.
2779 * @param v an array of floats for which the hash code should be
2781 * @return the hash code of the array, or 0 if null was given.
2784 public static int hashCode(float[] v
)
2789 for (int i
= 0; i
< v
.length
; ++i
)
2790 result
= 31 * result
+ Float
.floatToIntBits(v
[i
]);
2795 * Returns the hashcode of an array of doubles. If two arrays
2796 * are equal, according to <code>equals()</code>, they should have the
2797 * same hashcode. The hashcode returned by the method is equal to that
2798 * obtained by the corresponding <code>List</code> object. This has the same
2799 * data, but represents doubles in their wrapper class, <code>Double</code>.
2800 * For <code>null</code>, 0 is returned.
2802 * @param v an array of doubles for which the hash code should be
2804 * @return the hash code of the array, or 0 if null was given.
2807 public static int hashCode(double[] v
)
2812 for (int i
= 0; i
< v
.length
; ++i
)
2814 long l
= Double
.doubleToLongBits(v
[i
]);
2815 int elt
= (int) (l ^
(l
>>> 32));
2816 result
= 31 * result
+ elt
;
2822 * Returns the hashcode of an array of objects. If two arrays
2823 * are equal, according to <code>equals()</code>, they should have the
2824 * same hashcode. The hashcode returned by the method is equal to that
2825 * obtained by the corresponding <code>List</code> object.
2826 * For <code>null</code>, 0 is returned.
2828 * @param v an array of integer numbers for which the hash code should be
2830 * @return the hash code of the array, or 0 if null was given.
2833 public static int hashCode(Object
[] v
)
2838 for (int i
= 0; i
< v
.length
; ++i
)
2840 int elt
= v
[i
] == null ?
0 : v
[i
].hashCode();
2841 result
= 31 * result
+ elt
;
2846 public static int deepHashCode(Object
[] v
)
2851 for (int i
= 0; i
< v
.length
; ++i
)
2856 else if (v
[i
] instanceof boolean[])
2857 elt
= hashCode((boolean[]) v
[i
]);
2858 else if (v
[i
] instanceof byte[])
2859 elt
= hashCode((byte[]) v
[i
]);
2860 else if (v
[i
] instanceof char[])
2861 elt
= hashCode((char[]) v
[i
]);
2862 else if (v
[i
] instanceof short[])
2863 elt
= hashCode((short[]) v
[i
]);
2864 else if (v
[i
] instanceof int[])
2865 elt
= hashCode((int[]) v
[i
]);
2866 else if (v
[i
] instanceof long[])
2867 elt
= hashCode((long[]) v
[i
]);
2868 else if (v
[i
] instanceof float[])
2869 elt
= hashCode((float[]) v
[i
]);
2870 else if (v
[i
] instanceof double[])
2871 elt
= hashCode((double[]) v
[i
]);
2872 else if (v
[i
] instanceof Object
[])
2873 elt
= hashCode((Object
[]) v
[i
]);
2875 elt
= v
[i
].hashCode();
2876 result
= 31 * result
+ elt
;
2882 public static boolean deepEquals(Object
[] v1
, Object
[] v2
)
2886 if (v2
== null || v1
.length
!= v2
.length
)
2889 for (int i
= 0; i
< v1
.length
; ++i
)
2896 if (e1
== null || e2
== null)
2900 if (e1
instanceof boolean[] && e2
instanceof boolean[])
2901 check
= equals((boolean[]) e1
, (boolean[]) e2
);
2902 else if (e1
instanceof byte[] && e2
instanceof byte[])
2903 check
= equals((byte[]) e1
, (byte[]) e2
);
2904 else if (e1
instanceof char[] && e2
instanceof char[])
2905 check
= equals((char[]) e1
, (char[]) e2
);
2906 else if (e1
instanceof short[] && e2
instanceof short[])
2907 check
= equals((short[]) e1
, (short[]) e2
);
2908 else if (e1
instanceof int[] && e2
instanceof int[])
2909 check
= equals((int[]) e1
, (int[]) e2
);
2910 else if (e1
instanceof long[] && e2
instanceof long[])
2911 check
= equals((long[]) e1
, (long[]) e2
);
2912 else if (e1
instanceof float[] && e2
instanceof float[])
2913 check
= equals((float[]) e1
, (float[]) e2
);
2914 else if (e1
instanceof double[] && e2
instanceof double[])
2915 check
= equals((double[]) e1
, (double[]) e2
);
2916 else if (e1
instanceof Object
[] && e2
instanceof Object
[])
2917 check
= equals((Object
[]) e1
, (Object
[]) e2
);
2919 check
= e1
.equals(e2
);
2928 * Returns a String representation of the argument array. Returns "null"
2929 * if <code>a</code> is null.
2930 * @param v the array to represent
2931 * @return a String representing this array
2934 public static String
toString(boolean[] v
)
2938 StringBuilder b
= new StringBuilder("[");
2939 for (int i
= 0; i
< v
.length
; ++i
)
2946 return b
.toString();
2950 * Returns a String representation of the argument array. Returns "null"
2951 * if <code>a</code> is null.
2952 * @param v the array to represent
2953 * @return a String representing this array
2956 public static String
toString(byte[] v
)
2960 StringBuilder b
= new StringBuilder("[");
2961 for (int i
= 0; i
< v
.length
; ++i
)
2968 return b
.toString();
2972 * Returns a String representation of the argument array. Returns "null"
2973 * if <code>a</code> is null.
2974 * @param v the array to represent
2975 * @return a String representing this array
2978 public static String
toString(char[] v
)
2982 StringBuilder b
= new StringBuilder("[");
2983 for (int i
= 0; i
< v
.length
; ++i
)
2990 return b
.toString();
2994 * Returns a String representation of the argument array. Returns "null"
2995 * if <code>a</code> is null.
2996 * @param v the array to represent
2997 * @return a String representing this array
3000 public static String
toString(short[] v
)
3004 StringBuilder b
= new StringBuilder("[");
3005 for (int i
= 0; i
< v
.length
; ++i
)
3012 return b
.toString();
3016 * Returns a String representation of the argument array. Returns "null"
3017 * if <code>a</code> is null.
3018 * @param v the array to represent
3019 * @return a String representing this array
3022 public static String
toString(int[] v
)
3026 StringBuilder b
= new StringBuilder("[");
3027 for (int i
= 0; i
< v
.length
; ++i
)
3034 return b
.toString();
3038 * Returns a String representation of the argument array. Returns "null"
3039 * if <code>a</code> is null.
3040 * @param v the array to represent
3041 * @return a String representing this array
3044 public static String
toString(long[] v
)
3048 StringBuilder b
= new StringBuilder("[");
3049 for (int i
= 0; i
< v
.length
; ++i
)
3056 return b
.toString();
3060 * Returns a String representation of the argument array. Returns "null"
3061 * if <code>a</code> is null.
3062 * @param v the array to represent
3063 * @return a String representing this array
3066 public static String
toString(float[] v
)
3070 StringBuilder b
= new StringBuilder("[");
3071 for (int i
= 0; i
< v
.length
; ++i
)
3078 return b
.toString();
3082 * Returns a String representation of the argument array. Returns "null"
3083 * if <code>a</code> is null.
3084 * @param v the array to represent
3085 * @return a String representing this array
3088 public static String
toString(double[] v
)
3092 StringBuilder b
= new StringBuilder("[");
3093 for (int i
= 0; i
< v
.length
; ++i
)
3100 return b
.toString();
3104 * Returns a String representation of the argument array. Returns "null"
3105 * if <code>a</code> is null.
3106 * @param v the array to represent
3107 * @return a String representing this array
3110 public static String
toString(Object
[] v
)
3114 StringBuilder b
= new StringBuilder("[");
3115 for (int i
= 0; i
< v
.length
; ++i
)
3122 return b
.toString();
3125 private static void deepToString(Object
[] v
, StringBuilder b
, HashSet seen
)
3128 for (int i
= 0; i
< v
.length
; ++i
)
3135 else if (elt
instanceof boolean[])
3136 b
.append(toString((boolean[]) elt
));
3137 else if (elt
instanceof byte[])
3138 b
.append(toString((byte[]) elt
));
3139 else if (elt
instanceof char[])
3140 b
.append(toString((char[]) elt
));
3141 else if (elt
instanceof short[])
3142 b
.append(toString((short[]) elt
));
3143 else if (elt
instanceof int[])
3144 b
.append(toString((int[]) elt
));
3145 else if (elt
instanceof long[])
3146 b
.append(toString((long[]) elt
));
3147 else if (elt
instanceof float[])
3148 b
.append(toString((float[]) elt
));
3149 else if (elt
instanceof double[])
3150 b
.append(toString((double[]) elt
));
3151 else if (elt
instanceof Object
[])
3153 Object
[] os
= (Object
[]) elt
;
3154 if (seen
.contains(os
))
3159 deepToString(os
, b
, seen
);
3169 public static String
deepToString(Object
[] v
)
3173 HashSet seen
= new HashSet();
3174 StringBuilder b
= new StringBuilder();
3175 deepToString(v
, b
, seen
);
3176 return b
.toString();
3180 * Inner class used by {@link #asList(Object[])} to provide a list interface
3181 * to an array. The name, though it clashes with java.util.ArrayList, is
3182 * Sun's choice for Serialization purposes. Element addition and removal
3183 * is prohibited, but values can be modified.
3185 * @author Eric Blake (ebb9@email.byu.edu)
3186 * @status updated to 1.4
3188 private static final class ArrayList
<E
> extends AbstractList
<E
>
3189 implements Serializable
, RandomAccess
3191 // We override the necessary methods, plus others which will be much
3192 // more efficient with direct iteration rather than relying on iterator().
3195 * Compatible with JDK 1.4.
3197 private static final long serialVersionUID
= -2764017481108945198L;
3200 * The array we are viewing.
3203 private final E
[] a
;
3206 * Construct a list view of the array.
3207 * @param a the array to view
3208 * @throws NullPointerException if a is null
3212 // We have to explicitly check.
3214 throw new NullPointerException();
3219 * Returns the object at the specified index in
3222 * @param index The index to retrieve an object from.
3223 * @return The object at the array index specified.
3225 public E
get(int index
)
3231 * Returns the size of the array.
3241 * Replaces the object at the specified index
3242 * with the supplied element.
3244 * @param index The index at which to place the new object.
3245 * @param element The new object.
3246 * @return The object replaced by this operation.
3248 public E
set(int index
, E element
)
3256 * Returns true if the array contains the
3259 * @param o The object to look for.
3260 * @return True if the object was found.
3262 public boolean contains(Object o
)
3264 return lastIndexOf(o
) >= 0;
3268 * Returns the first index at which the
3269 * object, o, occurs in the array.
3271 * @param o The object to search for.
3272 * @return The first relevant index.
3274 public int indexOf(Object o
)
3276 int size
= a
.length
;
3277 for (int i
= 0; i
< size
; i
++)
3278 if (ArrayList
.equals(o
, a
[i
]))
3284 * Returns the last index at which the
3285 * object, o, occurs in the array.
3287 * @param o The object to search for.
3288 * @return The last relevant index.
3290 public int lastIndexOf(Object o
)
3294 if (ArrayList
.equals(o
, a
[i
]))
3300 * Transforms the list into an array of
3301 * objects, by simplying cloning the array
3302 * wrapped by this list.
3304 * @return A clone of the internal array.
3306 public Object
[] toArray()
3308 return (Object
[]) a
.clone();
3312 * Copies the objects from this list into
3313 * the supplied array. The supplied array
3314 * is shrunk or enlarged to the size of the
3315 * internal array, and filled with its objects.
3317 * @param array The array to fill with the objects in this list.
3318 * @return The array containing the objects in this list,
3319 * which may or may not be == to array.
3321 public <T
> T
[] toArray(T
[] array
)
3323 int size
= a
.length
;
3324 if (array
.length
< size
)
3325 array
= (T
[]) Array
.newInstance(array
.getClass().getComponentType(),
3327 else if (array
.length
> size
)
3330 System
.arraycopy(a
, 0, array
, 0, size
);
3336 * Returns a copy of the supplied array, truncating or padding as
3337 * necessary with <code>false</code> to obtain the specified length.
3338 * Indices that are valid for both arrays will return the same value.
3339 * Indices that only exist in the returned array (due to the new length
3340 * being greater than the original length) will return <code>false</code>.
3341 * This is equivalent to calling
3342 * <code>copyOfRange(original, 0, newLength)</code>.
3344 * @param original the original array to be copied.
3345 * @param newLength the length of the returned array.
3346 * @return a copy of the original array, truncated or padded with
3347 * <code>false</code> to obtain the required length.
3348 * @throws NegativeArraySizeException if <code>newLength</code> is negative.
3349 * @throws NullPointerException if <code>original</code> is <code>null</code>.
3351 * @see #copyOfRange(boolean[],int,int)
3353 public static boolean[] copyOf(boolean[] original
, int newLength
)
3356 throw new NegativeArraySizeException("The array size is negative.");
3357 return copyOfRange(original
, 0, newLength
);
3361 * Copies the specified range of the supplied array to a new
3362 * array, padding as necessary with <code>false</code>
3363 * if <code>to</code> is greater than the length of the original
3364 * array. <code>from</code> must be in the range zero to
3365 * <code>original.length</code> and can not be greater than
3366 * <code>to</code>. The initial element of the
3367 * returned array will be equal to <code>original[from]</code>,
3368 * except where <code>from</code> is equal to <code>to</code>
3369 * (where a zero-length array will be returned) or <code>
3370 * <code>from</code> is equal to <code>original.length</code>
3371 * (where an array padded with <code>false</code> will be
3372 * returned). The returned array is always of length
3373 * <code>to - from</code>.
3375 * @param original the array from which to copy.
3376 * @param from the initial index of the range, inclusive.
3377 * @param to the final index of the range, exclusive.
3378 * @return a copy of the specified range, with padding to
3379 * obtain the required length.
3380 * @throws ArrayIndexOutOfBoundsException if <code>from < 0</code>
3381 * or <code>from > original.length</code>
3382 * @throws IllegalArgumentException if <code>from > to</code>
3383 * @throws NullPointerException if <code>original</code> is <code>null</code>.
3385 * @see #copyOf(boolean[],int)
3387 public static boolean[] copyOfRange(boolean[] original
, int from
, int to
)
3390 throw new IllegalArgumentException("The initial index is after " +
3391 "the final index.");
3392 boolean[] newArray
= new boolean[to
- from
];
3393 if (to
> original
.length
)
3395 System
.arraycopy(original
, from
, newArray
, 0,
3396 original
.length
- from
);
3397 fill(newArray
, original
.length
, newArray
.length
, false);
3400 System
.arraycopy(original
, from
, newArray
, 0, to
- from
);
3405 * Returns a copy of the supplied array, truncating or padding as
3406 * necessary with <code>(byte)0</code> to obtain the specified length.
3407 * Indices that are valid for both arrays will return the same value.
3408 * Indices that only exist in the returned array (due to the new length
3409 * being greater than the original length) will return <code>(byte)0</code>.
3410 * This is equivalent to calling
3411 * <code>copyOfRange(original, 0, newLength)</code>.
3413 * @param original the original array to be copied.
3414 * @param newLength the length of the returned array.
3415 * @return a copy of the original array, truncated or padded with
3416 * <code>(byte)0</code> to obtain the required length.
3417 * @throws NegativeArraySizeException if <code>newLength</code> is negative.
3418 * @throws NullPointerException if <code>original</code> is <code>null</code>.
3420 * @see #copyOfRange(byte[],int,int)
3422 public static byte[] copyOf(byte[] original
, int newLength
)
3425 throw new NegativeArraySizeException("The array size is negative.");
3426 return copyOfRange(original
, 0, newLength
);
3430 * Copies the specified range of the supplied array to a new
3431 * array, padding as necessary with <code>(byte)0</code>
3432 * if <code>to</code> is greater than the length of the original
3433 * array. <code>from</code> must be in the range zero to
3434 * <code>original.length</code> and can not be greater than
3435 * <code>to</code>. The initial element of the
3436 * returned array will be equal to <code>original[from]</code>,
3437 * except where <code>from</code> is equal to <code>to</code>
3438 * (where a zero-length array will be returned) or <code>
3439 * <code>from</code> is equal to <code>original.length</code>
3440 * (where an array padded with <code>(byte)0</code> will be
3441 * returned). The returned array is always of length
3442 * <code>to - from</code>.
3444 * @param original the array from which to copy.
3445 * @param from the initial index of the range, inclusive.
3446 * @param to the final index of the range, exclusive.
3447 * @return a copy of the specified range, with padding to
3448 * obtain the required length.
3449 * @throws ArrayIndexOutOfBoundsException if <code>from < 0</code>
3450 * or <code>from > original.length</code>
3451 * @throws IllegalArgumentException if <code>from > to</code>
3452 * @throws NullPointerException if <code>original</code> is <code>null</code>.
3454 * @see #copyOf(byte[],int)
3456 public static byte[] copyOfRange(byte[] original
, int from
, int to
)
3459 throw new IllegalArgumentException("The initial index is after " +
3460 "the final index.");
3461 byte[] newArray
= new byte[to
- from
];
3462 if (to
> original
.length
)
3464 System
.arraycopy(original
, from
, newArray
, 0,
3465 original
.length
- from
);
3466 fill(newArray
, original
.length
, newArray
.length
, (byte)0);
3469 System
.arraycopy(original
, from
, newArray
, 0, to
- from
);
3474 * Returns a copy of the supplied array, truncating or padding as
3475 * necessary with <code>'\0'</code> to obtain the specified length.
3476 * Indices that are valid for both arrays will return the same value.
3477 * Indices that only exist in the returned array (due to the new length
3478 * being greater than the original length) will return <code>'\0'</code>.
3479 * This is equivalent to calling
3480 * <code>copyOfRange(original, 0, newLength)</code>.
3482 * @param original the original array to be copied.
3483 * @param newLength the length of the returned array.
3484 * @return a copy of the original array, truncated or padded with
3485 * <code>'\0'</code> to obtain the required length.
3486 * @throws NegativeArraySizeException if <code>newLength</code> is negative.
3487 * @throws NullPointerException if <code>original</code> is <code>null</code>.
3489 * @see #copyOfRange(char[],int,int)
3491 public static char[] copyOf(char[] original
, int newLength
)
3494 throw new NegativeArraySizeException("The array size is negative.");
3495 return copyOfRange(original
, 0, newLength
);
3499 * Copies the specified range of the supplied array to a new
3500 * array, padding as necessary with <code>'\0'</code>
3501 * if <code>to</code> is greater than the length of the original
3502 * array. <code>from</code> must be in the range zero to
3503 * <code>original.length</code> and can not be greater than
3504 * <code>to</code>. The initial element of the
3505 * returned array will be equal to <code>original[from]</code>,
3506 * except where <code>from</code> is equal to <code>to</code>
3507 * (where a zero-length array will be returned) or <code>
3508 * <code>from</code> is equal to <code>original.length</code>
3509 * (where an array padded with <code>'\0'</code> will be
3510 * returned). The returned array is always of length
3511 * <code>to - from</code>.
3513 * @param original the array from which to copy.
3514 * @param from the initial index of the range, inclusive.
3515 * @param to the final index of the range, exclusive.
3516 * @return a copy of the specified range, with padding to
3517 * obtain the required length.
3518 * @throws ArrayIndexOutOfBoundsException if <code>from < 0</code>
3519 * or <code>from > original.length</code>
3520 * @throws IllegalArgumentException if <code>from > to</code>
3521 * @throws NullPointerException if <code>original</code> is <code>null</code>.
3523 * @see #copyOf(char[],int)
3525 public static char[] copyOfRange(char[] original
, int from
, int to
)
3528 throw new IllegalArgumentException("The initial index is after " +
3529 "the final index.");
3530 char[] newArray
= new char[to
- from
];
3531 if (to
> original
.length
)
3533 System
.arraycopy(original
, from
, newArray
, 0,
3534 original
.length
- from
);
3535 fill(newArray
, original
.length
, newArray
.length
, '\0');
3538 System
.arraycopy(original
, from
, newArray
, 0, to
- from
);
3543 * Returns a copy of the supplied array, truncating or padding as
3544 * necessary with <code>0d</code> to obtain the specified length.
3545 * Indices that are valid for both arrays will return the same value.
3546 * Indices that only exist in the returned array (due to the new length
3547 * being greater than the original length) will return <code>0d</code>.
3548 * This is equivalent to calling
3549 * <code>copyOfRange(original, 0, newLength)</code>.
3551 * @param original the original array to be copied.
3552 * @param newLength the length of the returned array.
3553 * @return a copy of the original array, truncated or padded with
3554 * <code>0d</code> to obtain the required length.
3555 * @throws NegativeArraySizeException if <code>newLength</code> is negative.
3556 * @throws NullPointerException if <code>original</code> is <code>null</code>.
3558 * @see #copyOfRange(double[],int,int)
3560 public static double[] copyOf(double[] original
, int newLength
)
3563 throw new NegativeArraySizeException("The array size is negative.");
3564 return copyOfRange(original
, 0, newLength
);
3568 * Copies the specified range of the supplied array to a new
3569 * array, padding as necessary with <code>0d</code>
3570 * if <code>to</code> is greater than the length of the original
3571 * array. <code>from</code> must be in the range zero to
3572 * <code>original.length</code> and can not be greater than
3573 * <code>to</code>. The initial element of the
3574 * returned array will be equal to <code>original[from]</code>,
3575 * except where <code>from</code> is equal to <code>to</code>
3576 * (where a zero-length array will be returned) or <code>
3577 * <code>from</code> is equal to <code>original.length</code>
3578 * (where an array padded with <code>0d</code> will be
3579 * returned). The returned array is always of length
3580 * <code>to - from</code>.
3582 * @param original the array from which to copy.
3583 * @param from the initial index of the range, inclusive.
3584 * @param to the final index of the range, exclusive.
3585 * @return a copy of the specified range, with padding to
3586 * obtain the required length.
3587 * @throws ArrayIndexOutOfBoundsException if <code>from < 0</code>
3588 * or <code>from > original.length</code>
3589 * @throws IllegalArgumentException if <code>from > to</code>
3590 * @throws NullPointerException if <code>original</code> is <code>null</code>.
3592 * @see #copyOf(double[],int)
3594 public static double[] copyOfRange(double[] original
, int from
, int to
)
3597 throw new IllegalArgumentException("The initial index is after " +
3598 "the final index.");
3599 double[] newArray
= new double[to
- from
];
3600 if (to
> original
.length
)
3602 System
.arraycopy(original
, from
, newArray
, 0,
3603 original
.length
- from
);
3604 fill(newArray
, original
.length
, newArray
.length
, 0d
);
3607 System
.arraycopy(original
, from
, newArray
, 0, to
- from
);
3612 * Returns a copy of the supplied array, truncating or padding as
3613 * necessary with <code>0f</code> to obtain the specified length.
3614 * Indices that are valid for both arrays will return the same value.
3615 * Indices that only exist in the returned array (due to the new length
3616 * being greater than the original length) will return <code>0f</code>.
3617 * This is equivalent to calling
3618 * <code>copyOfRange(original, 0, newLength)</code>.
3620 * @param original the original array to be copied.
3621 * @param newLength the length of the returned array.
3622 * @return a copy of the original array, truncated or padded with
3623 * <code>0f</code> to obtain the required length.
3624 * @throws NegativeArraySizeException if <code>newLength</code> is negative.
3625 * @throws NullPointerException if <code>original</code> is <code>null</code>.
3627 * @see #copyOfRange(float[],int,int)
3629 public static float[] copyOf(float[] original
, int newLength
)
3632 throw new NegativeArraySizeException("The array size is negative.");
3633 return copyOfRange(original
, 0, newLength
);
3637 * Copies the specified range of the supplied array to a new
3638 * array, padding as necessary with <code>0f</code>
3639 * if <code>to</code> is greater than the length of the original
3640 * array. <code>from</code> must be in the range zero to
3641 * <code>original.length</code> and can not be greater than
3642 * <code>to</code>. The initial element of the
3643 * returned array will be equal to <code>original[from]</code>,
3644 * except where <code>from</code> is equal to <code>to</code>
3645 * (where a zero-length array will be returned) or <code>
3646 * <code>from</code> is equal to <code>original.length</code>
3647 * (where an array padded with <code>0f</code> will be
3648 * returned). The returned array is always of length
3649 * <code>to - from</code>.
3651 * @param original the array from which to copy.
3652 * @param from the initial index of the range, inclusive.
3653 * @param to the final index of the range, exclusive.
3654 * @return a copy of the specified range, with padding to
3655 * obtain the required length.
3656 * @throws ArrayIndexOutOfBoundsException if <code>from < 0</code>
3657 * or <code>from > original.length</code>
3658 * @throws IllegalArgumentException if <code>from > to</code>
3659 * @throws NullPointerException if <code>original</code> is <code>null</code>.
3661 * @see #copyOf(float[],int)
3663 public static float[] copyOfRange(float[] original
, int from
, int to
)
3666 throw new IllegalArgumentException("The initial index is after " +
3667 "the final index.");
3668 float[] newArray
= new float[to
- from
];
3669 if (to
> original
.length
)
3671 System
.arraycopy(original
, from
, newArray
, 0,
3672 original
.length
- from
);
3673 fill(newArray
, original
.length
, newArray
.length
, 0f
);
3676 System
.arraycopy(original
, from
, newArray
, 0, to
- from
);
3681 * Returns a copy of the supplied array, truncating or padding as
3682 * necessary with <code>0</code> to obtain the specified length.
3683 * Indices that are valid for both arrays will return the same value.
3684 * Indices that only exist in the returned array (due to the new length
3685 * being greater than the original length) will return <code>0</code>.
3686 * This is equivalent to calling
3687 * <code>copyOfRange(original, 0, newLength)</code>.
3689 * @param original the original array to be copied.
3690 * @param newLength the length of the returned array.
3691 * @return a copy of the original array, truncated or padded with
3692 * <code>0</code> to obtain the required length.
3693 * @throws NegativeArraySizeException if <code>newLength</code> is negative.
3694 * @throws NullPointerException if <code>original</code> is <code>null</code>.
3696 * @see #copyOfRange(int[],int,int)
3698 public static int[] copyOf(int[] original
, int newLength
)
3701 throw new NegativeArraySizeException("The array size is negative.");
3702 return copyOfRange(original
, 0, newLength
);
3706 * Copies the specified range of the supplied array to a new
3707 * array, padding as necessary with <code>0</code>
3708 * if <code>to</code> is greater than the length of the original
3709 * array. <code>from</code> must be in the range zero to
3710 * <code>original.length</code> and can not be greater than
3711 * <code>to</code>. The initial element of the
3712 * returned array will be equal to <code>original[from]</code>,
3713 * except where <code>from</code> is equal to <code>to</code>
3714 * (where a zero-length array will be returned) or <code>
3715 * <code>from</code> is equal to <code>original.length</code>
3716 * (where an array padded with <code>0</code> will be
3717 * returned). The returned array is always of length
3718 * <code>to - from</code>.
3720 * @param original the array from which to copy.
3721 * @param from the initial index of the range, inclusive.
3722 * @param to the final index of the range, exclusive.
3723 * @return a copy of the specified range, with padding to
3724 * obtain the required length.
3725 * @throws ArrayIndexOutOfBoundsException if <code>from < 0</code>
3726 * or <code>from > original.length</code>
3727 * @throws IllegalArgumentException if <code>from > to</code>
3728 * @throws NullPointerException if <code>original</code> is <code>null</code>.
3730 * @see #copyOf(int[],int)
3732 public static int[] copyOfRange(int[] original
, int from
, int to
)
3735 throw new IllegalArgumentException("The initial index is after " +
3736 "the final index.");
3737 int[] newArray
= new int[to
- from
];
3738 if (to
> original
.length
)
3740 System
.arraycopy(original
, from
, newArray
, 0,
3741 original
.length
- from
);
3742 fill(newArray
, original
.length
, newArray
.length
, 0);
3745 System
.arraycopy(original
, from
, newArray
, 0, to
- from
);
3750 * Returns a copy of the supplied array, truncating or padding as
3751 * necessary with <code>0L</code> to obtain the specified length.
3752 * Indices that are valid for both arrays will return the same value.
3753 * Indices that only exist in the returned array (due to the new length
3754 * being greater than the original length) will return <code>0L</code>.
3755 * This is equivalent to calling
3756 * <code>copyOfRange(original, 0, newLength)</code>.
3758 * @param original the original array to be copied.
3759 * @param newLength the length of the returned array.
3760 * @return a copy of the original array, truncated or padded with
3761 * <code>0L</code> to obtain the required length.
3762 * @throws NegativeArraySizeException if <code>newLength</code> is negative.
3763 * @throws NullPointerException if <code>original</code> is <code>null</code>.
3765 * @see #copyOfRange(long[],int,int)
3767 public static long[] copyOf(long[] original
, int newLength
)
3770 throw new NegativeArraySizeException("The array size is negative.");
3771 return copyOfRange(original
, 0, newLength
);
3775 * Copies the specified range of the supplied array to a new
3776 * array, padding as necessary with <code>0L</code>
3777 * if <code>to</code> is greater than the length of the original
3778 * array. <code>from</code> must be in the range zero to
3779 * <code>original.length</code> and can not be greater than
3780 * <code>to</code>. The initial element of the
3781 * returned array will be equal to <code>original[from]</code>,
3782 * except where <code>from</code> is equal to <code>to</code>
3783 * (where a zero-length array will be returned) or <code>
3784 * <code>from</code> is equal to <code>original.length</code>
3785 * (where an array padded with <code>0L</code> will be
3786 * returned). The returned array is always of length
3787 * <code>to - from</code>.
3789 * @param original the array from which to copy.
3790 * @param from the initial index of the range, inclusive.
3791 * @param to the final index of the range, exclusive.
3792 * @return a copy of the specified range, with padding to
3793 * obtain the required length.
3794 * @throws ArrayIndexOutOfBoundsException if <code>from < 0</code>
3795 * or <code>from > original.length</code>
3796 * @throws IllegalArgumentException if <code>from > to</code>
3797 * @throws NullPointerException if <code>original</code> is <code>null</code>.
3799 * @see #copyOf(long[],int)
3801 public static long[] copyOfRange(long[] original
, int from
, int to
)
3804 throw new IllegalArgumentException("The initial index is after " +
3805 "the final index.");
3806 long[] newArray
= new long[to
- from
];
3807 if (to
> original
.length
)
3809 System
.arraycopy(original
, from
, newArray
, 0,
3810 original
.length
- from
);
3811 fill(newArray
, original
.length
, newArray
.length
, 0L);
3814 System
.arraycopy(original
, from
, newArray
, 0, to
- from
);
3819 * Returns a copy of the supplied array, truncating or padding as
3820 * necessary with <code>(short)0</code> to obtain the specified length.
3821 * Indices that are valid for both arrays will return the same value.
3822 * Indices that only exist in the returned array (due to the new length
3823 * being greater than the original length) will return <code>(short)0</code>.
3824 * This is equivalent to calling
3825 * <code>copyOfRange(original, 0, newLength)</code>.
3827 * @param original the original array to be copied.
3828 * @param newLength the length of the returned array.
3829 * @return a copy of the original array, truncated or padded with
3830 * <code>(short)0</code> to obtain the required length.
3831 * @throws NegativeArraySizeException if <code>newLength</code> is negative.
3832 * @throws NullPointerException if <code>original</code> is <code>null</code>.
3834 * @see #copyOfRange(short[],int,int)
3836 public static short[] copyOf(short[] original
, int newLength
)
3839 throw new NegativeArraySizeException("The array size is negative.");
3840 return copyOfRange(original
, 0, newLength
);
3844 * Copies the specified range of the supplied array to a new
3845 * array, padding as necessary with <code>(short)0</code>
3846 * if <code>to</code> is greater than the length of the original
3847 * array. <code>from</code> must be in the range zero to
3848 * <code>original.length</code> and can not be greater than
3849 * <code>to</code>. The initial element of the
3850 * returned array will be equal to <code>original[from]</code>,
3851 * except where <code>from</code> is equal to <code>to</code>
3852 * (where a zero-length array will be returned) or <code>
3853 * <code>from</code> is equal to <code>original.length</code>
3854 * (where an array padded with <code>(short)0</code> will be
3855 * returned). The returned array is always of length
3856 * <code>to - from</code>.
3858 * @param original the array from which to copy.
3859 * @param from the initial index of the range, inclusive.
3860 * @param to the final index of the range, exclusive.
3861 * @return a copy of the specified range, with padding to
3862 * obtain the required length.
3863 * @throws ArrayIndexOutOfBoundsException if <code>from < 0</code>
3864 * or <code>from > original.length</code>
3865 * @throws IllegalArgumentException if <code>from > to</code>
3866 * @throws NullPointerException if <code>original</code> is <code>null</code>.
3868 * @see #copyOf(short[],int)
3870 public static short[] copyOfRange(short[] original
, int from
, int to
)
3873 throw new IllegalArgumentException("The initial index is after " +
3874 "the final index.");
3875 short[] newArray
= new short[to
- from
];
3876 if (to
> original
.length
)
3878 System
.arraycopy(original
, from
, newArray
, 0,
3879 original
.length
- from
);
3880 fill(newArray
, original
.length
, newArray
.length
, (short)0);
3883 System
.arraycopy(original
, from
, newArray
, 0, to
- from
);
3888 * Returns a copy of the supplied array, truncating or padding as
3889 * necessary with <code>null</code> to obtain the specified length.
3890 * Indices that are valid for both arrays will return the same value.
3891 * Indices that only exist in the returned array (due to the new length
3892 * being greater than the original length) will return <code>null</code>.
3893 * This is equivalent to calling
3894 * <code>copyOfRange(original, 0, newLength)</code>.
3896 * @param original the original array to be copied.
3897 * @param newLength the length of the returned array.
3898 * @return a copy of the original array, truncated or padded with
3899 * <code>null</code> to obtain the required length.
3900 * @throws NegativeArraySizeException if <code>newLength</code> is negative.
3901 * @throws NullPointerException if <code>original</code> is <code>null</code>.
3903 * @see #copyOfRange(T[],int,int)
3905 public static <T
> T
[] copyOf(T
[] original
, int newLength
)
3908 throw new NegativeArraySizeException("The array size is negative.");
3909 return copyOfRange(original
, 0, newLength
);
3913 * Copies the specified range of the supplied array to a new
3914 * array, padding as necessary with <code>null</code>
3915 * if <code>to</code> is greater than the length of the original
3916 * array. <code>from</code> must be in the range zero to
3917 * <code>original.length</code> and can not be greater than
3918 * <code>to</code>. The initial element of the
3919 * returned array will be equal to <code>original[from]</code>,
3920 * except where <code>from</code> is equal to <code>to</code>
3921 * (where a zero-length array will be returned) or <code>
3922 * <code>from</code> is equal to <code>original.length</code>
3923 * (where an array padded with <code>null</code> will be
3924 * returned). The returned array is always of length
3925 * <code>to - from</code>.
3927 * @param original the array from which to copy.
3928 * @param from the initial index of the range, inclusive.
3929 * @param to the final index of the range, exclusive.
3930 * @return a copy of the specified range, with padding to
3931 * obtain the required length.
3932 * @throws ArrayIndexOutOfBoundsException if <code>from < 0</code>
3933 * or <code>from > original.length</code>
3934 * @throws IllegalArgumentException if <code>from > to</code>
3935 * @throws NullPointerException if <code>original</code> is <code>null</code>.
3937 * @see #copyOf(T[],int)
3939 public static <T
> T
[] copyOfRange(T
[] original
, int from
, int to
)
3942 throw new IllegalArgumentException("The initial index is after " +
3943 "the final index.");
3944 Class elemType
= original
.getClass().getComponentType();
3945 T
[] newArray
= (T
[]) Array
.newInstance(elemType
, to
- from
);
3946 if (to
> original
.length
)
3948 System
.arraycopy(original
, from
, newArray
, 0,
3949 original
.length
- from
);
3950 fill(newArray
, original
.length
, newArray
.length
, null);
3953 System
.arraycopy(original
, from
, newArray
, 0, to
- from
);
3958 * Returns a copy of the supplied array, truncating or padding as
3959 * necessary with <code>null</code> to obtain the specified length.
3960 * Indices that are valid for both arrays will return the same value.
3961 * Indices that only exist in the returned array (due to the new length
3962 * being greater than the original length) will return <code>null</code>.
3963 * This is equivalent to calling
3964 * <code>copyOfRange(original, 0, newLength, newType)</code>. The returned
3965 * array will be of the specified type, <code>newType</code>.
3967 * @param original the original array to be copied.
3968 * @param newLength the length of the returned array.
3969 * @param newType the type of the returned array.
3970 * @return a copy of the original array, truncated or padded with
3971 * <code>null</code> to obtain the required length.
3972 * @throws NegativeArraySizeException if <code>newLength</code> is negative.
3973 * @throws NullPointerException if <code>original</code> is <code>null</code>.
3975 * @see #copyOfRange(U[],int,int,Class)
3977 public static <T
,U
> T
[] copyOf(U
[] original
, int newLength
,
3978 Class
<?
extends T
[]> newType
)
3981 throw new NegativeArraySizeException("The array size is negative.");
3982 return copyOfRange(original
, 0, newLength
, newType
);
3986 * Copies the specified range of the supplied array to a new
3987 * array, padding as necessary with <code>null</code>
3988 * if <code>to</code> is greater than the length of the original
3989 * array. <code>from</code> must be in the range zero to
3990 * <code>original.length</code> and can not be greater than
3991 * <code>to</code>. The initial element of the
3992 * returned array will be equal to <code>original[from]</code>,
3993 * except where <code>from</code> is equal to <code>to</code>
3994 * (where a zero-length array will be returned) or <code>
3995 * <code>from</code> is equal to <code>original.length</code>
3996 * (where an array padded with <code>null</code> will be
3997 * returned). The returned array is always of length
3998 * <code>to - from</code> and will be of the specified type,
3999 * <code>newType</code>.
4001 * @param original the array from which to copy.
4002 * @param from the initial index of the range, inclusive.
4003 * @param to the final index of the range, exclusive.
4004 * @param newType the type of the returned array.
4005 * @return a copy of the specified range, with padding to
4006 * obtain the required length.
4007 * @throws ArrayIndexOutOfBoundsException if <code>from < 0</code>
4008 * or <code>from > original.length</code>
4009 * @throws IllegalArgumentException if <code>from > to</code>
4010 * @throws NullPointerException if <code>original</code> is <code>null</code>.
4012 * @see #copyOf(T[],int)
4014 public static <T
,U
> T
[] copyOfRange(U
[] original
, int from
, int to
,
4015 Class
<?
extends T
[]> newType
)
4018 throw new IllegalArgumentException("The initial index is after " +
4019 "the final index.");
4020 T
[] newArray
= (T
[]) Array
.newInstance(newType
.getComponentType(),
4022 if (to
> original
.length
)
4024 System
.arraycopy(original
, from
, newArray
, 0,
4025 original
.length
- from
);
4026 fill(newArray
, original
.length
, newArray
.length
, null);
4029 System
.arraycopy(original
, from
, newArray
, 0, to
- from
);