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 gnu.java.lang.CPStringBuilder;
44 import java.io.Serializable;
45 import java.lang.reflect.Array;
48 * This class contains various static utility methods performing operations on
49 * arrays, and a method to provide a List "view" of an array to facilitate
50 * using arrays with Collection-based APIs. All methods throw a
51 * {@link NullPointerException} if the parameter array is null.
54 * Implementations may use their own algorithms, but must obey the general
55 * properties; for example, the sort must be stable and n*log(n) complexity.
56 * Sun's implementation of sort, and therefore ours, is a tuned quicksort,
57 * adapted from Jon L. Bentley and M. Douglas McIlroy's "Engineering a Sort
58 * Function", Software-Practice and Experience, Vol. 23(11) P. 1249-1265
59 * (November 1993). This algorithm offers n*log(n) performance on many data
60 * sets that cause other quicksorts to degrade to quadratic performance.
62 * @author Original author unknown
63 * @author Bryce McKinlay
64 * @author Eric Blake (ebb9@email.byu.edu)
68 * @status updated to 1.4
73 * This class is non-instantiable.
82 * Perform a binary search of a byte array for a key. The array must be
83 * sorted (as by the sort() method) - if it is not, the behaviour of this
84 * method is undefined, and may be an infinite loop. If the array contains
85 * the key more than once, any one of them may be found. Note: although the
86 * specification allows for an infinite loop if the array is unsorted, it
87 * will not happen in this implementation.
89 * @param a the array to search (must be sorted)
90 * @param key the value to search for
91 * @return the index at which the key was found, or -n-1 if it was not
92 * found, where n is the index of the first value higher than key or
93 * a.length if there is no such value.
95 public static int binarySearch(byte[] a, byte key)
99 return binarySearch(a, 0, a.length - 1, key);
103 * Perform a binary search of a range of a byte array for a key. The range
104 * must be sorted (as by the <code>sort(byte[], int, int)</code> method) -
105 * if it is not, the behaviour of this method is undefined, and may be an
106 * infinite loop. If the array contains the key more than once, any one of
107 * them may be found. Note: although the specification allows for an infinite
108 * loop if the array is unsorted, it will not happen in this implementation.
110 * @param a the array to search (must be sorted)
111 * @param low the lowest index to search from.
112 * @param hi the highest index to search to.
113 * @param key the value to search for
114 * @return the index at which the key was found, or -n-1 if it was not
115 * found, where n is the index of the first value higher than key or
116 * a.length if there is no such value.
117 * @throws IllegalArgumentException if <code>low > hi</code>
118 * @throws ArrayIndexOutOfBoundsException if <code>low < 0</code> or
119 * <code>hi > a.length</code>.
121 public static int binarySearch(byte[] a, int low, int hi, byte key)
124 throw new IllegalArgumentException("The start index is higher than " +
125 "the finish index.");
126 if (low < 0 || hi > a.length)
127 throw new ArrayIndexOutOfBoundsException("One of the indices is out " +
132 mid = (low + hi) >>> 1;
133 final byte d = a[mid];
139 // This gets the insertion point right on the last loop.
146 * Perform a binary search of a char array for a key. The array must be
147 * sorted (as by the sort() method) - if it is not, the behaviour of this
148 * method is undefined, and may be an infinite loop. If the array contains
149 * the key more than once, any one of them may be found. Note: although the
150 * specification allows for an infinite loop if the array is unsorted, it
151 * will not happen in this implementation.
153 * @param a the array to search (must be sorted)
154 * @param key the value to search for
155 * @return the index at which the key was found, or -n-1 if it was not
156 * found, where n is the index of the first value higher than key or
157 * a.length if there is no such value.
159 public static int binarySearch(char[] a, char key)
163 return binarySearch(a, 0, a.length - 1, key);
167 * Perform a binary search of a range of a char array for a key. The range
168 * must be sorted (as by the <code>sort(char[], int, int)</code> method) -
169 * if it is not, the behaviour of this method is undefined, and may be an
170 * infinite loop. If the array contains the key more than once, any one of
171 * them may be found. Note: although the specification allows for an infinite
172 * loop if the array is unsorted, it will not happen in this implementation.
174 * @param a the array to search (must be sorted)
175 * @param low the lowest index to search from.
176 * @param hi the highest index to search to.
177 * @param key the value to search for
178 * @return the index at which the key was found, or -n-1 if it was not
179 * found, where n is the index of the first value higher than key or
180 * a.length if there is no such value.
181 * @throws IllegalArgumentException if <code>low > hi</code>
182 * @throws ArrayIndexOutOfBoundsException if <code>low < 0</code> or
183 * <code>hi > a.length</code>.
185 public static int binarySearch(char[] a, int low, int hi, char key)
188 throw new IllegalArgumentException("The start index is higher than " +
189 "the finish index.");
190 if (low < 0 || hi > a.length)
191 throw new ArrayIndexOutOfBoundsException("One of the indices is out " +
196 mid = (low + hi) >>> 1;
197 final char d = a[mid];
203 // This gets the insertion point right on the last loop.
210 * Perform a binary search of a short array for a key. The array must be
211 * sorted (as by the sort() method) - if it is not, the behaviour of this
212 * method is undefined, and may be an infinite loop. If the array contains
213 * the key more than once, any one of them may be found. Note: although the
214 * specification allows for an infinite loop if the array is unsorted, it
215 * will not happen in this implementation.
217 * @param a the array to search (must be sorted)
218 * @param key the value to search for
219 * @return the index at which the key was found, or -n-1 if it was not
220 * found, where n is the index of the first value higher than key or
221 * a.length if there is no such value.
223 public static int binarySearch(short[] a, short key)
227 return binarySearch(a, 0, a.length - 1, key);
231 * Perform a binary search of a range of a short array for a key. The range
232 * must be sorted (as by the <code>sort(short[], int, int)</code> method) -
233 * if it is not, the behaviour of this method is undefined, and may be an
234 * infinite loop. If the array contains the key more than once, any one of
235 * them may be found. Note: although the specification allows for an infinite
236 * loop if the array is unsorted, it will not happen in this implementation.
238 * @param a the array to search (must be sorted)
239 * @param low the lowest index to search from.
240 * @param hi the highest index to search to.
241 * @param key the value to search for
242 * @return the index at which the key was found, or -n-1 if it was not
243 * found, where n is the index of the first value higher than key or
244 * a.length if there is no such value.
245 * @throws IllegalArgumentException if <code>low > hi</code>
246 * @throws ArrayIndexOutOfBoundsException if <code>low < 0</code> or
247 * <code>hi > a.length</code>.
249 public static int binarySearch(short[] a, int low, int hi, short key)
252 throw new IllegalArgumentException("The start index is higher than " +
253 "the finish index.");
254 if (low < 0 || hi > a.length)
255 throw new ArrayIndexOutOfBoundsException("One of the indices is out " +
260 mid = (low + hi) >>> 1;
261 final short d = a[mid];
267 // This gets the insertion point right on the last loop.
274 * Perform a binary search of an int array for a key. The array must be
275 * sorted (as by the sort() method) - if it is not, the behaviour of this
276 * method is undefined, and may be an infinite loop. If the array contains
277 * the key more than once, any one of them may be found. Note: although the
278 * specification allows for an infinite loop if the array is unsorted, it
279 * will not happen in this implementation.
281 * @param a the array to search (must be sorted)
282 * @param key the value to search for
283 * @return the index at which the key was found, or -n-1 if it was not
284 * found, where n is the index of the first value higher than key or
285 * a.length if there is no such value.
287 public static int binarySearch(int[] a, int key)
291 return binarySearch(a, 0, a.length - 1, key);
295 * Perform a binary search of a range of an integer array for a key. The range
296 * must be sorted (as by the <code>sort(int[], int, int)</code> method) -
297 * if it is not, the behaviour of this method is undefined, and may be an
298 * infinite loop. If the array contains the key more than once, any one of
299 * them may be found. Note: although the specification allows for an infinite
300 * loop if the array is unsorted, it will not happen in this implementation.
302 * @param a the array to search (must be sorted)
303 * @param low the lowest index to search from.
304 * @param hi the highest index to search to.
305 * @param key the value to search for
306 * @return the index at which the key was found, or -n-1 if it was not
307 * found, where n is the index of the first value higher than key or
308 * a.length if there is no such value.
309 * @throws IllegalArgumentException if <code>low > hi</code>
310 * @throws ArrayIndexOutOfBoundsException if <code>low < 0</code> or
311 * <code>hi > a.length</code>.
313 public static int binarySearch(int[] a, int low, int hi, int key)
316 throw new IllegalArgumentException("The start index is higher than " +
317 "the finish index.");
318 if (low < 0 || hi > a.length)
319 throw new ArrayIndexOutOfBoundsException("One of the indices is out " +
324 mid = (low + hi) >>> 1;
325 final int d = a[mid];
331 // This gets the insertion point right on the last loop.
338 * Perform a binary search of a long array for a key. The array must be
339 * sorted (as by the sort() method) - if it is not, the behaviour of this
340 * method is undefined, and may be an infinite loop. If the array contains
341 * the key more than once, any one of them may be found. Note: although the
342 * specification allows for an infinite loop if the array is unsorted, it
343 * will not happen in this implementation.
345 * @param a the array to search (must be sorted)
346 * @param key the value to search for
347 * @return the index at which the key was found, or -n-1 if it was not
348 * found, where n is the index of the first value higher than key or
349 * a.length if there is no such value.
351 public static int binarySearch(long[] a, long key)
355 return binarySearch(a, 0, a.length - 1, key);
359 * Perform a binary search of a range of a long array for a key. The range
360 * must be sorted (as by the <code>sort(long[], int, int)</code> method) -
361 * if it is not, the behaviour of this method is undefined, and may be an
362 * infinite loop. If the array contains the key more than once, any one of
363 * them may be found. Note: although the specification allows for an infinite
364 * loop if the array is unsorted, it will not happen in this implementation.
366 * @param a the array to search (must be sorted)
367 * @param low the lowest index to search from.
368 * @param hi the highest index to search to.
369 * @param key the value to search for
370 * @return the index at which the key was found, or -n-1 if it was not
371 * found, where n is the index of the first value higher than key or
372 * a.length if there is no such value.
373 * @throws IllegalArgumentException if <code>low > hi</code>
374 * @throws ArrayIndexOutOfBoundsException if <code>low < 0</code> or
375 * <code>hi > a.length</code>.
377 public static int binarySearch(long[] a, int low, int hi, long key)
380 throw new IllegalArgumentException("The start index is higher than " +
381 "the finish index.");
382 if (low < 0 || hi > a.length)
383 throw new ArrayIndexOutOfBoundsException("One of the indices is out " +
388 mid = (low + hi) >>> 1;
389 final long d = a[mid];
395 // This gets the insertion point right on the last loop.
402 * Perform a binary search of a float array for a key. The array must be
403 * sorted (as by the sort() method) - if it is not, the behaviour of this
404 * method is undefined, and may be an infinite loop. If the array contains
405 * the key more than once, any one of them may be found. Note: although the
406 * specification allows for an infinite loop if the array is unsorted, it
407 * will not happen in this implementation.
409 * @param a the array to search (must be sorted)
410 * @param key the value to search for
411 * @return the index at which the key was found, or -n-1 if it was not
412 * found, where n is the index of the first value higher than key or
413 * a.length if there is no such value.
415 public static int binarySearch(float[] a, float key)
419 return binarySearch(a, 0, a.length - 1, key);
423 * Perform a binary search of a range of a float array for a key. The range
424 * must be sorted (as by the <code>sort(float[], int, int)</code> method) -
425 * if it is not, the behaviour of this method is undefined, and may be an
426 * infinite loop. If the array contains the key more than once, any one of
427 * them may be found. Note: although the specification allows for an infinite
428 * loop if the array is unsorted, it will not happen in this implementation.
430 * @param a the array to search (must be sorted)
431 * @param low the lowest index to search from.
432 * @param hi the highest index to search to.
433 * @param key the value to search for
434 * @return the index at which the key was found, or -n-1 if it was not
435 * found, where n is the index of the first value higher than key or
436 * a.length if there is no such value.
437 * @throws IllegalArgumentException if <code>low > hi</code>
438 * @throws ArrayIndexOutOfBoundsException if <code>low < 0</code> or
439 * <code>hi > a.length</code>.
441 public static int binarySearch(float[] a, int low, int hi, float key)
444 throw new IllegalArgumentException("The start index is higher than " +
445 "the finish index.");
446 if (low < 0 || hi > a.length)
447 throw new ArrayIndexOutOfBoundsException("One of the indices is out " +
449 // Must use Float.compare to take into account NaN, +-0.
453 mid = (low + hi) >>> 1;
454 final int r = Float.compare(a[mid], key);
460 // This gets the insertion point right on the last loop
467 * Perform a binary search of a double array for a key. The array must be
468 * sorted (as by the sort() method) - if it is not, the behaviour of this
469 * method is undefined, and may be an infinite loop. If the array contains
470 * the key more than once, any one of them may be found. Note: although the
471 * specification allows for an infinite loop if the array is unsorted, it
472 * will not happen in this implementation.
474 * @param a the array to search (must be sorted)
475 * @param key the value to search for
476 * @return the index at which the key was found, or -n-1 if it was not
477 * found, where n is the index of the first value higher than key or
478 * a.length if there is no such value.
480 public static int binarySearch(double[] a, double key)
484 return binarySearch(a, 0, a.length - 1, key);
488 * Perform a binary search of a range of a double array for a key. The range
489 * must be sorted (as by the <code>sort(double[], int, int)</code> method) -
490 * if it is not, the behaviour of this method is undefined, and may be an
491 * infinite loop. If the array contains the key more than once, any one of
492 * them may be found. Note: although the specification allows for an infinite
493 * loop if the array is unsorted, it will not happen in this implementation.
495 * @param a the array to search (must be sorted)
496 * @param low the lowest index to search from.
497 * @param hi the highest index to search to.
498 * @param key the value to search for
499 * @return the index at which the key was found, or -n-1 if it was not
500 * found, where n is the index of the first value higher than key or
501 * a.length if there is no such value.
502 * @throws IllegalArgumentException if <code>low > hi</code>
503 * @throws ArrayIndexOutOfBoundsException if <code>low < 0</code> or
504 * <code>hi > a.length</code>.
506 public static int binarySearch(double[] a, int low, int hi, double key)
509 throw new IllegalArgumentException("The start index is higher than " +
510 "the finish index.");
511 if (low < 0 || hi > a.length)
512 throw new ArrayIndexOutOfBoundsException("One of the indices is out " +
514 // Must use Double.compare to take into account NaN, +-0.
518 mid = (low + hi) >>> 1;
519 final int r = Double.compare(a[mid], key);
525 // This gets the insertion point right on the last loop
532 * Perform a binary search of an Object array for a key, using the natural
533 * ordering of the elements. The array must be sorted (as by the sort()
534 * method) - if it is not, the behaviour of this method is undefined, and may
535 * be an infinite loop. Further, the key must be comparable with every item
536 * in the array. If the array contains the key more than once, any one of
537 * them may be found. Note: although the specification allows for an infinite
538 * loop if the array is unsorted, it will not happen in this (JCL)
541 * @param a the array to search (must be sorted)
542 * @param key the value to search for
543 * @return the index at which the key was found, or -n-1 if it was not
544 * found, where n is the index of the first value higher than key or
545 * a.length if there is no such value.
546 * @throws ClassCastException if key could not be compared with one of the
548 * @throws NullPointerException if a null element in a is compared
550 public static int binarySearch(Object[] a, Object key)
554 return binarySearch(a, key, null);
558 * Perform a binary search of a range of an Object array for a key. The range
559 * must be sorted (as by the <code>sort(Object[], int, int)</code> method) -
560 * if it is not, the behaviour of this method is undefined, and may be an
561 * infinite loop. If the array contains the key more than once, any one of
562 * them may be found. Note: although the specification allows for an infinite
563 * loop if the array is unsorted, it will not happen in this implementation.
565 * @param a the array to search (must be sorted)
566 * @param low the lowest index to search from.
567 * @param hi the highest index to search to.
568 * @param key the value to search for
569 * @return the index at which the key was found, or -n-1 if it was not
570 * found, where n is the index of the first value higher than key or
571 * a.length if there is no such value.
573 public static int binarySearch(Object[] a, int low, int hi, Object key)
575 return binarySearch(a, low, hi, key, null);
579 * Perform a binary search of an Object array for a key, using a supplied
580 * Comparator. The array must be sorted (as by the sort() method with the
581 * same Comparator) - if it is not, the behaviour of this method is
582 * undefined, and may be an infinite loop. Further, the key must be
583 * comparable with every item in the array. If the array contains the key
584 * more than once, any one of them may be found. Note: although the
585 * specification allows for an infinite loop if the array is unsorted, it
586 * will not happen in this (JCL) implementation.
588 * @param a the array to search (must be sorted)
589 * @param key the value to search for
590 * @param c the comparator by which the array is sorted; or null to
591 * use the elements' natural order
592 * @return the index at which the key was found, or -n-1 if it was not
593 * found, where n is the index of the first value higher than key or
594 * a.length if there is no such value.
595 * @throws ClassCastException if key could not be compared with one of the
597 * @throws NullPointerException if a null element is compared with natural
598 * ordering (only possible when c is null)
600 public static <T> int binarySearch(T[] a, T key, Comparator<? super T> c)
604 return binarySearch(a, 0, a.length - 1, key, c);
608 * Perform a binary search of a range of an Object array for a key using
609 * a {@link Comparator}. The range must be sorted (as by the
610 * <code>sort(Object[], int, int)</code> method) - if it is not, the
611 * behaviour of this method is undefined, and may be an infinite loop. If
612 * the array contains the key more than once, any one of them may be found.
613 * Note: although the specification allows for an infinite loop if the array
614 * is unsorted, it will not happen in this implementation.
616 * @param a the array to search (must be sorted)
617 * @param low the lowest index to search from.
618 * @param hi the highest index to search to.
619 * @param key the value to search for
620 * @param c the comparator by which the array is sorted; or null to
621 * use the elements' natural order
622 * @return the index at which the key was found, or -n-1 if it was not
623 * found, where n is the index of the first value higher than key or
624 * a.length if there is no such value.
625 * @throws ClassCastException if key could not be compared with one of the
627 * @throws IllegalArgumentException if <code>low > hi</code>
628 * @throws ArrayIndexOutOfBoundsException if <code>low < 0</code> or
629 * <code>hi > a.length</code>.
631 public static <T> int binarySearch(T[] a, int low, int hi, T key,
632 Comparator<? super T> c)
635 throw new IllegalArgumentException("The start index is higher than " +
636 "the finish index.");
637 if (low < 0 || hi > a.length)
638 throw new ArrayIndexOutOfBoundsException("One of the indices is out " +
643 mid = (low + hi) >>> 1;
644 // NOTE: Please keep the order of a[mid] and key. Although
645 // not required by the specs, the RI has it in this order as
646 // well, and real programs (erroneously) depend on it.
647 final int d = Collections.compare(a[mid], key, c);
653 // This gets the insertion point right on the last loop
662 * Compare two boolean arrays for equality.
664 * @param a1 the first array to compare
665 * @param a2 the second array to compare
666 * @return true if a1 and a2 are both null, or if a2 is of the same length
667 * as a1, and for each 0 <= i < a1.length, a1[i] == a2[i]
669 public static boolean equals(boolean[] a1, boolean[] a2)
671 // Quick test which saves comparing elements of the same array, and also
672 // catches the case that both are null.
676 if (null == a1 || null == a2)
679 // If they're the same length, test each element
680 if (a1.length == a2.length)
692 * Compare two byte arrays for equality.
694 * @param a1 the first array to compare
695 * @param a2 the second array to compare
696 * @return true if a1 and a2 are both null, or if a2 is of the same length
697 * as a1, and for each 0 <= i < a1.length, a1[i] == a2[i]
699 public static boolean equals(byte[] a1, byte[] a2)
701 // Quick test which saves comparing elements of the same array, and also
702 // catches the case that both are null.
706 if (null == a1 || null == a2)
709 // If they're the same length, test each element
710 if (a1.length == a2.length)
722 * Compare two char arrays for equality.
724 * @param a1 the first array to compare
725 * @param a2 the second array to compare
726 * @return true if a1 and a2 are both null, or if a2 is of the same length
727 * as a1, and for each 0 <= i < a1.length, a1[i] == a2[i]
729 public static boolean equals(char[] a1, char[] a2)
731 // Quick test which saves comparing elements of the same array, and also
732 // catches the case that both are null.
736 if (null == a1 || null == a2)
739 // If they're the same length, test each element
740 if (a1.length == a2.length)
752 * Compare two short arrays for equality.
754 * @param a1 the first array to compare
755 * @param a2 the second array to compare
756 * @return true if a1 and a2 are both null, or if a2 is of the same length
757 * as a1, and for each 0 <= i < a1.length, a1[i] == a2[i]
759 public static boolean equals(short[] a1, short[] a2)
761 // Quick test which saves comparing elements of the same array, and also
762 // catches the case that both are null.
766 if (null == a1 || null == a2)
769 // If they're the same length, test each element
770 if (a1.length == a2.length)
782 * Compare two int arrays for equality.
784 * @param a1 the first array to compare
785 * @param a2 the second array to compare
786 * @return true if a1 and a2 are both null, or if a2 is of the same length
787 * as a1, and for each 0 <= i < a1.length, a1[i] == a2[i]
789 public static boolean equals(int[] a1, int[] a2)
791 // Quick test which saves comparing elements of the same array, and also
792 // catches the case that both are null.
796 if (null == a1 || null == a2)
799 // If they're the same length, test each element
800 if (a1.length == a2.length)
812 * Compare two long arrays for equality.
814 * @param a1 the first array to compare
815 * @param a2 the second array to compare
816 * @return true if a1 and a2 are both null, or if a2 is of the same length
817 * as a1, and for each 0 <= i < a1.length, a1[i] == a2[i]
819 public static boolean equals(long[] a1, long[] a2)
821 // Quick test which saves comparing elements of the same array, and also
822 // catches the case that both are null.
826 if (null == a1 || null == a2)
829 // If they're the same length, test each element
830 if (a1.length == a2.length)
842 * Compare two float arrays for equality.
844 * @param a1 the first array to compare
845 * @param a2 the second array to compare
846 * @return true if a1 and a2 are both null, or if a2 is of the same length
847 * as a1, and for each 0 <= i < a1.length, a1[i] == a2[i]
849 public static boolean equals(float[] a1, float[] a2)
851 // Quick test which saves comparing elements of the same array, and also
852 // catches the case that both are null.
856 if (null == a1 || null == a2)
859 // Must use Float.compare to take into account NaN, +-0.
860 // If they're the same length, test each element
861 if (a1.length == a2.length)
865 if (Float.compare(a1[i], a2[i]) != 0)
873 * Compare two double arrays for equality.
875 * @param a1 the first array to compare
876 * @param a2 the second array to compare
877 * @return true if a1 and a2 are both null, or if a2 is of the same length
878 * as a1, and for each 0 <= i < a1.length, a1[i] == a2[i]
880 public static boolean equals(double[] a1, double[] a2)
882 // Quick test which saves comparing elements of the same array, and also
883 // catches the case that both are null.
887 if (null == a1 || null == a2)
890 // Must use Double.compare to take into account NaN, +-0.
891 // If they're the same length, test each element
892 if (a1.length == a2.length)
896 if (Double.compare(a1[i], a2[i]) != 0)
904 * Compare two Object arrays for equality.
906 * @param a1 the first array to compare
907 * @param a2 the second array to compare
908 * @return true if a1 and a2 are both null, or if a1 is of the same length
909 * as a2, and for each 0 <= i < a.length, a1[i] == null ?
910 * a2[i] == null : a1[i].equals(a2[i]).
912 public static boolean equals(Object[] a1, Object[] a2)
914 // Quick test which saves comparing elements of the same array, and also
915 // catches the case that both are null.
919 if (null == a1 || null == a2)
922 // If they're the same length, test each element
923 if (a1.length == a2.length)
927 if (! AbstractCollection.equals(a1[i], a2[i]))
937 * Fill an array with a boolean value.
939 * @param a the array to fill
940 * @param val the value to fill it with
942 public static void fill(boolean[] a, boolean val)
944 fill(a, 0, a.length, val);
948 * Fill a range of an array with a boolean value.
950 * @param a the array to fill
951 * @param fromIndex the index to fill from, inclusive
952 * @param toIndex the index to fill to, exclusive
953 * @param val the value to fill with
954 * @throws IllegalArgumentException if fromIndex > toIndex
955 * @throws ArrayIndexOutOfBoundsException if fromIndex < 0
956 * || toIndex > a.length
958 public static void fill(boolean[] a, int fromIndex, int toIndex, boolean val)
960 if (fromIndex > toIndex)
961 throw new IllegalArgumentException();
962 for (int i = fromIndex; i < toIndex; i++)
967 * Fill an array with a byte value.
969 * @param a the array to fill
970 * @param val the value to fill it with
972 public static void fill(byte[] a, byte val)
974 fill(a, 0, a.length, val);
978 * Fill a range of an array with a byte value.
980 * @param a the array to fill
981 * @param fromIndex the index to fill from, inclusive
982 * @param toIndex the index to fill to, exclusive
983 * @param val the value to fill with
984 * @throws IllegalArgumentException if fromIndex > toIndex
985 * @throws ArrayIndexOutOfBoundsException if fromIndex < 0
986 * || toIndex > a.length
988 public static void fill(byte[] a, int fromIndex, int toIndex, byte val)
990 if (fromIndex > toIndex)
991 throw new IllegalArgumentException();
992 for (int i = fromIndex; i < toIndex; i++)
997 * Fill an array with a char value.
999 * @param a the array to fill
1000 * @param val the value to fill it with
1002 public static void fill(char[] a, char val)
1004 fill(a, 0, a.length, val);
1008 * Fill a range of an array with a char value.
1010 * @param a the array to fill
1011 * @param fromIndex the index to fill from, inclusive
1012 * @param toIndex the index to fill to, exclusive
1013 * @param val the value to fill with
1014 * @throws IllegalArgumentException if fromIndex > toIndex
1015 * @throws ArrayIndexOutOfBoundsException if fromIndex < 0
1016 * || toIndex > a.length
1018 public static void fill(char[] a, int fromIndex, int toIndex, char val)
1020 if (fromIndex > toIndex)
1021 throw new IllegalArgumentException();
1022 for (int i = fromIndex; i < toIndex; i++)
1027 * Fill an array with a short value.
1029 * @param a the array to fill
1030 * @param val the value to fill it with
1032 public static void fill(short[] a, short val)
1034 fill(a, 0, a.length, val);
1038 * Fill a range of an array with a short value.
1040 * @param a the array to fill
1041 * @param fromIndex the index to fill from, inclusive
1042 * @param toIndex the index to fill to, exclusive
1043 * @param val the value to fill with
1044 * @throws IllegalArgumentException if fromIndex > toIndex
1045 * @throws ArrayIndexOutOfBoundsException if fromIndex < 0
1046 * || toIndex > a.length
1048 public static void fill(short[] a, int fromIndex, int toIndex, short val)
1050 if (fromIndex > toIndex)
1051 throw new IllegalArgumentException();
1052 for (int i = fromIndex; i < toIndex; i++)
1057 * Fill an array with an int value.
1059 * @param a the array to fill
1060 * @param val the value to fill it with
1062 public static void fill(int[] a, int val)
1064 fill(a, 0, a.length, val);
1068 * Fill a range of an array with an int value.
1070 * @param a the array to fill
1071 * @param fromIndex the index to fill from, inclusive
1072 * @param toIndex the index to fill to, exclusive
1073 * @param val the value to fill with
1074 * @throws IllegalArgumentException if fromIndex > toIndex
1075 * @throws ArrayIndexOutOfBoundsException if fromIndex < 0
1076 * || toIndex > a.length
1078 public static void fill(int[] a, int fromIndex, int toIndex, int val)
1080 if (fromIndex > toIndex)
1081 throw new IllegalArgumentException();
1082 for (int i = fromIndex; i < toIndex; i++)
1087 * Fill an array with a long value.
1089 * @param a the array to fill
1090 * @param val the value to fill it with
1092 public static void fill(long[] a, long val)
1094 fill(a, 0, a.length, val);
1098 * Fill a range of an array with a long value.
1100 * @param a the array to fill
1101 * @param fromIndex the index to fill from, inclusive
1102 * @param toIndex the index to fill to, exclusive
1103 * @param val the value to fill with
1104 * @throws IllegalArgumentException if fromIndex > toIndex
1105 * @throws ArrayIndexOutOfBoundsException if fromIndex < 0
1106 * || toIndex > a.length
1108 public static void fill(long[] a, int fromIndex, int toIndex, long val)
1110 if (fromIndex > toIndex)
1111 throw new IllegalArgumentException();
1112 for (int i = fromIndex; i < toIndex; i++)
1117 * Fill an array with a float value.
1119 * @param a the array to fill
1120 * @param val the value to fill it with
1122 public static void fill(float[] a, float val)
1124 fill(a, 0, a.length, val);
1128 * Fill a range of an array with a float value.
1130 * @param a the array to fill
1131 * @param fromIndex the index to fill from, inclusive
1132 * @param toIndex the index to fill to, exclusive
1133 * @param val the value to fill with
1134 * @throws IllegalArgumentException if fromIndex > toIndex
1135 * @throws ArrayIndexOutOfBoundsException if fromIndex < 0
1136 * || toIndex > a.length
1138 public static void fill(float[] a, int fromIndex, int toIndex, float val)
1140 if (fromIndex > toIndex)
1141 throw new IllegalArgumentException();
1142 for (int i = fromIndex; i < toIndex; i++)
1147 * Fill an array with a double value.
1149 * @param a the array to fill
1150 * @param val the value to fill it with
1152 public static void fill(double[] a, double val)
1154 fill(a, 0, a.length, val);
1158 * Fill a range of an array with a double value.
1160 * @param a the array to fill
1161 * @param fromIndex the index to fill from, inclusive
1162 * @param toIndex the index to fill to, exclusive
1163 * @param val the value to fill with
1164 * @throws IllegalArgumentException if fromIndex > toIndex
1165 * @throws ArrayIndexOutOfBoundsException if fromIndex < 0
1166 * || toIndex > a.length
1168 public static void fill(double[] a, int fromIndex, int toIndex, double val)
1170 if (fromIndex > toIndex)
1171 throw new IllegalArgumentException();
1172 for (int i = fromIndex; i < toIndex; i++)
1177 * Fill an array with an Object value.
1179 * @param a the array to fill
1180 * @param val the value to fill it with
1181 * @throws ClassCastException if val is not an instance of the element
1184 public static void fill(Object[] a, Object val)
1186 fill(a, 0, a.length, val);
1190 * Fill a range of an array with an Object value.
1192 * @param a the array to fill
1193 * @param fromIndex the index to fill from, inclusive
1194 * @param toIndex the index to fill to, exclusive
1195 * @param val the value to fill with
1196 * @throws ClassCastException if val is not an instance of the element
1198 * @throws IllegalArgumentException if fromIndex > toIndex
1199 * @throws ArrayIndexOutOfBoundsException if fromIndex < 0
1200 * || toIndex > a.length
1202 public static void fill(Object[] a, int fromIndex, int toIndex, Object val)
1204 if (fromIndex > toIndex)
1205 throw new IllegalArgumentException();
1206 for (int i = fromIndex; i < toIndex; i++)
1212 // Thanks to Paul Fisher (rao@gnu.org) for finding this quicksort algorithm
1213 // as specified by Sun and porting it to Java. The algorithm is an optimised
1214 // quicksort, as described in Jon L. Bentley and M. Douglas McIlroy's
1215 // "Engineering a Sort Function", Software-Practice and Experience, Vol.
1216 // 23(11) P. 1249-1265 (November 1993). This algorithm gives n*log(n)
1217 // performance on many arrays that would take quadratic time with a standard
1221 * Performs a stable sort on the elements, arranging them according to their
1224 * @param a the byte array to sort
1226 public static void sort(byte[] a)
1228 qsort(a, 0, a.length);
1232 * Performs a stable sort on the elements, arranging them according to their
1235 * @param a the byte array to sort
1236 * @param fromIndex the first index to sort (inclusive)
1237 * @param toIndex the last index to sort (exclusive)
1238 * @throws IllegalArgumentException if fromIndex > toIndex
1239 * @throws ArrayIndexOutOfBoundsException if fromIndex < 0
1240 * || toIndex > a.length
1242 public static void sort(byte[] a, int fromIndex, int toIndex)
1244 if (fromIndex > toIndex)
1245 throw new IllegalArgumentException();
1247 throw new ArrayIndexOutOfBoundsException();
1248 qsort(a, fromIndex, toIndex - fromIndex);
1252 * Finds the index of the median of three array elements.
1254 * @param a the first index
1255 * @param b the second index
1256 * @param c the third index
1257 * @param d the array
1258 * @return the index (a, b, or c) which has the middle value of the three
1260 private static int med3(int a, int b, int c, byte[] d)
1263 ? (d[b] < d[c] ? b : d[a] < d[c] ? c : a)
1264 : (d[b] > d[c] ? b : d[a] > d[c] ? c : a));
1268 * Swaps the elements at two locations of an array
1270 * @param i the first index
1271 * @param j the second index
1272 * @param a the array
1274 private static void swap(int i, int j, byte[] a)
1282 * Swaps two ranges of an array.
1284 * @param i the first range start
1285 * @param j the second range start
1286 * @param n the element count
1287 * @param a the array
1289 private static void vecswap(int i, int j, int n, byte[] a)
1291 for ( ; n > 0; i++, j++, n--)
1296 * Performs a recursive modified quicksort.
1298 * @param array the array to sort
1299 * @param from the start index (inclusive)
1300 * @param count the number of elements to sort
1302 private static void qsort(byte[] array, int from, int count)
1304 // Use an insertion sort on small arrays.
1307 for (int i = from + 1; i < from + count; i++)
1308 for (int j = i; j > from && array[j - 1] > array[j]; j--)
1309 swap(j, j - 1, array);
1313 // Determine a good median element.
1314 int mid = from + count / 2;
1316 int hi = from + count - 1;
1319 { // big arrays, pseudomedian of 9
1321 lo = med3(lo, lo + s, lo + 2 * s, array);
1322 mid = med3(mid - s, mid, mid + s, array);
1323 hi = med3(hi - 2 * s, hi - s, hi, array);
1325 mid = med3(lo, mid, hi, array);
1330 // Pull the median element out of the fray, and use it as a pivot.
1331 swap(from, mid, array);
1333 c = d = from + count - 1;
1335 // Repeatedly move b and c to each other, swapping elements so
1336 // that all elements before index b are less than the pivot, and all
1337 // elements after index c are greater than the pivot. a and b track
1338 // the elements equal to the pivot.
1341 while (b <= c && (comp = array[b] - array[from]) <= 0)
1350 while (c >= b && (comp = array[c] - array[from]) >= 0)
1366 // Swap pivot(s) back in place, the recurse on left and right sections.
1369 span = Math.min(a - from, b - a);
1370 vecswap(from, b - span, span, array);
1372 span = Math.min(d - c, hi - d - 1);
1373 vecswap(b, hi - span, span, array);
1377 qsort(array, from, span);
1381 qsort(array, hi - span, span);
1385 * Performs a stable sort on the elements, arranging them according to their
1388 * @param a the char array to sort
1390 public static void sort(char[] a)
1392 qsort(a, 0, a.length);
1396 * Performs a stable sort on the elements, arranging them according to their
1399 * @param a the char array to sort
1400 * @param fromIndex the first index to sort (inclusive)
1401 * @param toIndex the last index to sort (exclusive)
1402 * @throws IllegalArgumentException if fromIndex > toIndex
1403 * @throws ArrayIndexOutOfBoundsException if fromIndex < 0
1404 * || toIndex > a.length
1406 public static void sort(char[] a, int fromIndex, int toIndex)
1408 if (fromIndex > toIndex)
1409 throw new IllegalArgumentException();
1411 throw new ArrayIndexOutOfBoundsException();
1412 qsort(a, fromIndex, toIndex - fromIndex);
1416 * Finds the index of the median of three array elements.
1418 * @param a the first index
1419 * @param b the second index
1420 * @param c the third index
1421 * @param d the array
1422 * @return the index (a, b, or c) which has the middle value of the three
1424 private static int med3(int a, int b, int c, char[] d)
1427 ? (d[b] < d[c] ? b : d[a] < d[c] ? c : a)
1428 : (d[b] > d[c] ? b : d[a] > d[c] ? c : a));
1432 * Swaps the elements at two locations of an array
1434 * @param i the first index
1435 * @param j the second index
1436 * @param a the array
1438 private static void swap(int i, int j, char[] a)
1446 * Swaps two ranges of an array.
1448 * @param i the first range start
1449 * @param j the second range start
1450 * @param n the element count
1451 * @param a the array
1453 private static void vecswap(int i, int j, int n, char[] a)
1455 for ( ; n > 0; i++, j++, n--)
1460 * Performs a recursive modified quicksort.
1462 * @param array the array to sort
1463 * @param from the start index (inclusive)
1464 * @param count the number of elements to sort
1466 private static void qsort(char[] array, int from, int count)
1468 // Use an insertion sort on small arrays.
1471 for (int i = from + 1; i < from + count; i++)
1472 for (int j = i; j > from && array[j - 1] > array[j]; j--)
1473 swap(j, j - 1, array);
1477 // Determine a good median element.
1478 int mid = from + count / 2;
1480 int hi = from + count - 1;
1483 { // big arrays, pseudomedian of 9
1485 lo = med3(lo, lo + s, lo + 2 * s, array);
1486 mid = med3(mid - s, mid, mid + s, array);
1487 hi = med3(hi - 2 * s, hi - s, hi, array);
1489 mid = med3(lo, mid, hi, array);
1494 // Pull the median element out of the fray, and use it as a pivot.
1495 swap(from, mid, array);
1497 c = d = from + count - 1;
1499 // Repeatedly move b and c to each other, swapping elements so
1500 // that all elements before index b are less than the pivot, and all
1501 // elements after index c are greater than the pivot. a and b track
1502 // the elements equal to the pivot.
1505 while (b <= c && (comp = array[b] - array[from]) <= 0)
1514 while (c >= b && (comp = array[c] - array[from]) >= 0)
1530 // Swap pivot(s) back in place, the recurse on left and right sections.
1533 span = Math.min(a - from, b - a);
1534 vecswap(from, b - span, span, array);
1536 span = Math.min(d - c, hi - d - 1);
1537 vecswap(b, hi - span, span, array);
1541 qsort(array, from, span);
1545 qsort(array, hi - span, span);
1549 * Performs a stable sort on the elements, arranging them according to their
1552 * @param a the short array to sort
1554 public static void sort(short[] a)
1556 qsort(a, 0, a.length);
1560 * Performs a stable sort on the elements, arranging them according to their
1563 * @param a the short array to sort
1564 * @param fromIndex the first index to sort (inclusive)
1565 * @param toIndex the last index to sort (exclusive)
1566 * @throws IllegalArgumentException if fromIndex > toIndex
1567 * @throws ArrayIndexOutOfBoundsException if fromIndex < 0
1568 * || toIndex > a.length
1570 public static void sort(short[] a, int fromIndex, int toIndex)
1572 if (fromIndex > toIndex)
1573 throw new IllegalArgumentException();
1575 throw new ArrayIndexOutOfBoundsException();
1576 qsort(a, fromIndex, toIndex - fromIndex);
1580 * Finds the index of the median of three array elements.
1582 * @param a the first index
1583 * @param b the second index
1584 * @param c the third index
1585 * @param d the array
1586 * @return the index (a, b, or c) which has the middle value of the three
1588 private static int med3(int a, int b, int c, short[] d)
1591 ? (d[b] < d[c] ? b : d[a] < d[c] ? c : a)
1592 : (d[b] > d[c] ? b : d[a] > d[c] ? c : a));
1596 * Swaps the elements at two locations of an array
1598 * @param i the first index
1599 * @param j the second index
1600 * @param a the array
1602 private static void swap(int i, int j, short[] a)
1610 * Swaps two ranges of an array.
1612 * @param i the first range start
1613 * @param j the second range start
1614 * @param n the element count
1615 * @param a the array
1617 private static void vecswap(int i, int j, int n, short[] a)
1619 for ( ; n > 0; i++, j++, n--)
1624 * Performs a recursive modified quicksort.
1626 * @param array the array to sort
1627 * @param from the start index (inclusive)
1628 * @param count the number of elements to sort
1630 private static void qsort(short[] array, int from, int count)
1632 // Use an insertion sort on small arrays.
1635 for (int i = from + 1; i < from + count; i++)
1636 for (int j = i; j > from && array[j - 1] > array[j]; j--)
1637 swap(j, j - 1, array);
1641 // Determine a good median element.
1642 int mid = from + count / 2;
1644 int hi = from + count - 1;
1647 { // big arrays, pseudomedian of 9
1649 lo = med3(lo, lo + s, lo + 2 * s, array);
1650 mid = med3(mid - s, mid, mid + s, array);
1651 hi = med3(hi - 2 * s, hi - s, hi, array);
1653 mid = med3(lo, mid, hi, array);
1658 // Pull the median element out of the fray, and use it as a pivot.
1659 swap(from, mid, array);
1661 c = d = from + count - 1;
1663 // Repeatedly move b and c to each other, swapping elements so
1664 // that all elements before index b are less than the pivot, and all
1665 // elements after index c are greater than the pivot. a and b track
1666 // the elements equal to the pivot.
1669 while (b <= c && (comp = array[b] - array[from]) <= 0)
1678 while (c >= b && (comp = array[c] - array[from]) >= 0)
1694 // Swap pivot(s) back in place, the recurse on left and right sections.
1697 span = Math.min(a - from, b - a);
1698 vecswap(from, b - span, span, array);
1700 span = Math.min(d - c, hi - d - 1);
1701 vecswap(b, hi - span, span, array);
1705 qsort(array, from, span);
1709 qsort(array, hi - span, span);
1713 * Performs a stable sort on the elements, arranging them according to their
1716 * @param a the int array to sort
1718 public static void sort(int[] a)
1720 qsort(a, 0, a.length);
1724 * Performs a stable sort on the elements, arranging them according to their
1727 * @param a the int array to sort
1728 * @param fromIndex the first index to sort (inclusive)
1729 * @param toIndex the last index to sort (exclusive)
1730 * @throws IllegalArgumentException if fromIndex > toIndex
1731 * @throws ArrayIndexOutOfBoundsException if fromIndex < 0
1732 * || toIndex > a.length
1734 public static void sort(int[] a, int fromIndex, int toIndex)
1736 if (fromIndex > toIndex)
1737 throw new IllegalArgumentException();
1739 throw new ArrayIndexOutOfBoundsException();
1740 qsort(a, fromIndex, toIndex - fromIndex);
1744 * Finds the index of the median of three array elements.
1746 * @param a the first index
1747 * @param b the second index
1748 * @param c the third index
1749 * @param d the array
1750 * @return the index (a, b, or c) which has the middle value of the three
1752 private static int med3(int a, int b, int c, int[] d)
1755 ? (d[b] < d[c] ? b : d[a] < d[c] ? c : a)
1756 : (d[b] > d[c] ? b : d[a] > d[c] ? c : a));
1760 * Swaps the elements at two locations of an array
1762 * @param i the first index
1763 * @param j the second index
1764 * @param a the array
1766 private static void swap(int i, int j, int[] a)
1774 * Swaps two ranges of an array.
1776 * @param i the first range start
1777 * @param j the second range start
1778 * @param n the element count
1779 * @param a the array
1781 private static void vecswap(int i, int j, int n, int[] a)
1783 for ( ; n > 0; i++, j++, n--)
1788 * Compares two integers in natural order, since a - b is inadequate.
1790 * @param a the first int
1791 * @param b the second int
1792 * @return < 0, 0, or > 0 accorting to the comparison
1794 private static int compare(int a, int b)
1796 return a < b ? -1 : a == b ? 0 : 1;
1800 * Performs a recursive modified quicksort.
1802 * @param array the array to sort
1803 * @param from the start index (inclusive)
1804 * @param count the number of elements to sort
1806 private static void qsort(int[] array, int from, int count)
1808 // Use an insertion sort on small arrays.
1811 for (int i = from + 1; i < from + count; i++)
1812 for (int j = i; j > from && array[j - 1] > array[j]; j--)
1813 swap(j, j - 1, array);
1817 // Determine a good median element.
1818 int mid = from + count / 2;
1820 int hi = from + count - 1;
1823 { // big arrays, pseudomedian of 9
1825 lo = med3(lo, lo + s, lo + 2 * s, array);
1826 mid = med3(mid - s, mid, mid + s, array);
1827 hi = med3(hi - 2 * s, hi - s, hi, array);
1829 mid = med3(lo, mid, hi, array);
1834 // Pull the median element out of the fray, and use it as a pivot.
1835 swap(from, mid, array);
1837 c = d = from + count - 1;
1839 // Repeatedly move b and c to each other, swapping elements so
1840 // that all elements before index b are less than the pivot, and all
1841 // elements after index c are greater than the pivot. a and b track
1842 // the elements equal to the pivot.
1845 while (b <= c && (comp = compare(array[b], array[from])) <= 0)
1854 while (c >= b && (comp = compare(array[c], array[from])) >= 0)
1870 // Swap pivot(s) back in place, the recurse on left and right sections.
1873 span = Math.min(a - from, b - a);
1874 vecswap(from, b - span, span, array);
1876 span = Math.min(d - c, hi - d - 1);
1877 vecswap(b, hi - span, span, array);
1881 qsort(array, from, span);
1885 qsort(array, hi - span, span);
1889 * Performs a stable sort on the elements, arranging them according to their
1892 * @param a the long array to sort
1894 public static void sort(long[] a)
1896 qsort(a, 0, a.length);
1900 * Performs a stable sort on the elements, arranging them according to their
1903 * @param a the long array to sort
1904 * @param fromIndex the first index to sort (inclusive)
1905 * @param toIndex the last index to sort (exclusive)
1906 * @throws IllegalArgumentException if fromIndex > toIndex
1907 * @throws ArrayIndexOutOfBoundsException if fromIndex < 0
1908 * || toIndex > a.length
1910 public static void sort(long[] a, int fromIndex, int toIndex)
1912 if (fromIndex > toIndex)
1913 throw new IllegalArgumentException();
1915 throw new ArrayIndexOutOfBoundsException();
1916 qsort(a, fromIndex, toIndex - fromIndex);
1920 * Finds the index of the median of three array elements.
1922 * @param a the first index
1923 * @param b the second index
1924 * @param c the third index
1925 * @param d the array
1926 * @return the index (a, b, or c) which has the middle value of the three
1928 private static int med3(int a, int b, int c, long[] d)
1931 ? (d[b] < d[c] ? b : d[a] < d[c] ? c : a)
1932 : (d[b] > d[c] ? b : d[a] > d[c] ? c : a));
1936 * Swaps the elements at two locations of an array
1938 * @param i the first index
1939 * @param j the second index
1940 * @param a the array
1942 private static void swap(int i, int j, long[] a)
1950 * Swaps two ranges of an array.
1952 * @param i the first range start
1953 * @param j the second range start
1954 * @param n the element count
1955 * @param a the array
1957 private static void vecswap(int i, int j, int n, long[] a)
1959 for ( ; n > 0; i++, j++, n--)
1964 * Compares two longs in natural order, since a - b is inadequate.
1966 * @param a the first long
1967 * @param b the second long
1968 * @return < 0, 0, or > 0 accorting to the comparison
1970 private static int compare(long a, long b)
1972 return a < b ? -1 : a == b ? 0 : 1;
1976 * Performs a recursive modified quicksort.
1978 * @param array the array to sort
1979 * @param from the start index (inclusive)
1980 * @param count the number of elements to sort
1982 private static void qsort(long[] array, int from, int count)
1984 // Use an insertion sort on small arrays.
1987 for (int i = from + 1; i < from + count; i++)
1988 for (int j = i; j > from && array[j - 1] > array[j]; j--)
1989 swap(j, j - 1, array);
1993 // Determine a good median element.
1994 int mid = from + count / 2;
1996 int hi = from + count - 1;
1999 { // big arrays, pseudomedian of 9
2001 lo = med3(lo, lo + s, lo + 2 * s, array);
2002 mid = med3(mid - s, mid, mid + s, array);
2003 hi = med3(hi - 2 * s, hi - s, hi, array);
2005 mid = med3(lo, mid, hi, array);
2010 // Pull the median element out of the fray, and use it as a pivot.
2011 swap(from, mid, array);
2013 c = d = from + count - 1;
2015 // Repeatedly move b and c to each other, swapping elements so
2016 // that all elements before index b are less than the pivot, and all
2017 // elements after index c are greater than the pivot. a and b track
2018 // the elements equal to the pivot.
2021 while (b <= c && (comp = compare(array[b], array[from])) <= 0)
2030 while (c >= b && (comp = compare(array[c], array[from])) >= 0)
2046 // Swap pivot(s) back in place, the recurse on left and right sections.
2049 span = Math.min(a - from, b - a);
2050 vecswap(from, b - span, span, array);
2052 span = Math.min(d - c, hi - d - 1);
2053 vecswap(b, hi - span, span, array);
2057 qsort(array, from, span);
2061 qsort(array, hi - span, span);
2065 * Performs a stable sort on the elements, arranging them according to their
2068 * @param a the float array to sort
2070 public static void sort(float[] a)
2072 qsort(a, 0, a.length);
2076 * Performs a stable sort on the elements, arranging them according to their
2079 * @param a the float array to sort
2080 * @param fromIndex the first index to sort (inclusive)
2081 * @param toIndex the last index to sort (exclusive)
2082 * @throws IllegalArgumentException if fromIndex > toIndex
2083 * @throws ArrayIndexOutOfBoundsException if fromIndex < 0
2084 * || toIndex > a.length
2086 public static void sort(float[] a, int fromIndex, int toIndex)
2088 if (fromIndex > toIndex)
2089 throw new IllegalArgumentException();
2091 throw new ArrayIndexOutOfBoundsException();
2092 qsort(a, fromIndex, toIndex - fromIndex);
2096 * Finds the index of the median of three array elements.
2098 * @param a the first index
2099 * @param b the second index
2100 * @param c the third index
2101 * @param d the array
2102 * @return the index (a, b, or c) which has the middle value of the three
2104 private static int med3(int a, int b, int c, float[] d)
2106 return (Float.compare(d[a], d[b]) < 0
2107 ? (Float.compare(d[b], d[c]) < 0 ? b
2108 : Float.compare(d[a], d[c]) < 0 ? c : a)
2109 : (Float.compare(d[b], d[c]) > 0 ? b
2110 : Float.compare(d[a], d[c]) > 0 ? c : a));
2114 * Swaps the elements at two locations of an array
2116 * @param i the first index
2117 * @param j the second index
2118 * @param a the array
2120 private static void swap(int i, int j, float[] a)
2128 * Swaps two ranges of an array.
2130 * @param i the first range start
2131 * @param j the second range start
2132 * @param n the element count
2133 * @param a the array
2135 private static void vecswap(int i, int j, int n, float[] a)
2137 for ( ; n > 0; i++, j++, n--)
2142 * Performs a recursive modified quicksort.
2144 * @param array the array to sort
2145 * @param from the start index (inclusive)
2146 * @param count the number of elements to sort
2148 private static void qsort(float[] array, int from, int count)
2150 // Use an insertion sort on small arrays.
2153 for (int i = from + 1; i < from + count; i++)
2155 j > from && Float.compare(array[j - 1], array[j]) > 0;
2158 swap(j, j - 1, array);
2163 // Determine a good median element.
2164 int mid = from + count / 2;
2166 int hi = from + count - 1;
2169 { // big arrays, pseudomedian of 9
2171 lo = med3(lo, lo + s, lo + 2 * s, array);
2172 mid = med3(mid - s, mid, mid + s, array);
2173 hi = med3(hi - 2 * s, hi - s, hi, array);
2175 mid = med3(lo, mid, hi, array);
2180 // Pull the median element out of the fray, and use it as a pivot.
2181 swap(from, mid, array);
2183 c = d = from + count - 1;
2185 // Repeatedly move b and c to each other, swapping elements so
2186 // that all elements before index b are less than the pivot, and all
2187 // elements after index c are greater than the pivot. a and b track
2188 // the elements equal to the pivot.
2191 while (b <= c && (comp = Float.compare(array[b], array[from])) <= 0)
2200 while (c >= b && (comp = Float.compare(array[c], array[from])) >= 0)
2216 // Swap pivot(s) back in place, the recurse on left and right sections.
2219 span = Math.min(a - from, b - a);
2220 vecswap(from, b - span, span, array);
2222 span = Math.min(d - c, hi - d - 1);
2223 vecswap(b, hi - span, span, array);
2227 qsort(array, from, span);
2231 qsort(array, hi - span, span);
2235 * Performs a stable sort on the elements, arranging them according to their
2238 * @param a the double array to sort
2240 public static void sort(double[] a)
2242 qsort(a, 0, a.length);
2246 * Performs a stable sort on the elements, arranging them according to their
2249 * @param a the double array to sort
2250 * @param fromIndex the first index to sort (inclusive)
2251 * @param toIndex the last index to sort (exclusive)
2252 * @throws IllegalArgumentException if fromIndex > toIndex
2253 * @throws ArrayIndexOutOfBoundsException if fromIndex < 0
2254 * || toIndex > a.length
2256 public static void sort(double[] a, int fromIndex, int toIndex)
2258 if (fromIndex > toIndex)
2259 throw new IllegalArgumentException();
2261 throw new ArrayIndexOutOfBoundsException();
2262 qsort(a, fromIndex, toIndex - fromIndex);
2266 * Finds the index of the median of three array elements.
2268 * @param a the first index
2269 * @param b the second index
2270 * @param c the third index
2271 * @param d the array
2272 * @return the index (a, b, or c) which has the middle value of the three
2274 private static int med3(int a, int b, int c, double[] d)
2276 return (Double.compare(d[a], d[b]) < 0
2277 ? (Double.compare(d[b], d[c]) < 0 ? b
2278 : Double.compare(d[a], d[c]) < 0 ? c : a)
2279 : (Double.compare(d[b], d[c]) > 0 ? b
2280 : Double.compare(d[a], d[c]) > 0 ? c : a));
2284 * Swaps the elements at two locations of an array
2286 * @param i the first index
2287 * @param j the second index
2288 * @param a the array
2290 private static void swap(int i, int j, double[] a)
2298 * Swaps two ranges of an array.
2300 * @param i the first range start
2301 * @param j the second range start
2302 * @param n the element count
2303 * @param a the array
2305 private static void vecswap(int i, int j, int n, double[] a)
2307 for ( ; n > 0; i++, j++, n--)
2312 * Performs a recursive modified quicksort.
2314 * @param array the array to sort
2315 * @param from the start index (inclusive)
2316 * @param count the number of elements to sort
2318 private static void qsort(double[] array, int from, int count)
2320 // Use an insertion sort on small arrays.
2323 for (int i = from + 1; i < from + count; i++)
2325 j > from && Double.compare(array[j - 1], array[j]) > 0;
2328 swap(j, j - 1, array);
2333 // Determine a good median element.
2334 int mid = from + count / 2;
2336 int hi = from + count - 1;
2339 { // big arrays, pseudomedian of 9
2341 lo = med3(lo, lo + s, lo + 2 * s, array);
2342 mid = med3(mid - s, mid, mid + s, array);
2343 hi = med3(hi - 2 * s, hi - s, hi, array);
2345 mid = med3(lo, mid, hi, array);
2350 // Pull the median element out of the fray, and use it as a pivot.
2351 swap(from, mid, array);
2353 c = d = from + count - 1;
2355 // Repeatedly move b and c to each other, swapping elements so
2356 // that all elements before index b are less than the pivot, and all
2357 // elements after index c are greater than the pivot. a and b track
2358 // the elements equal to the pivot.
2361 while (b <= c && (comp = Double.compare(array[b], array[from])) <= 0)
2370 while (c >= b && (comp = Double.compare(array[c], array[from])) >= 0)
2386 // Swap pivot(s) back in place, the recurse on left and right sections.
2389 span = Math.min(a - from, b - a);
2390 vecswap(from, b - span, span, array);
2392 span = Math.min(d - c, hi - d - 1);
2393 vecswap(b, hi - span, span, array);
2397 qsort(array, from, span);
2401 qsort(array, hi - span, span);
2405 * Sort an array of Objects according to their natural ordering. The sort is
2406 * guaranteed to be stable, that is, equal elements will not be reordered.
2407 * The sort algorithm is a mergesort with the merge omitted if the last
2408 * element of one half comes before the first element of the other half. This
2409 * algorithm gives guaranteed O(n*log(n)) time, at the expense of making a
2410 * copy of the array.
2412 * @param a the array to be sorted
2413 * @throws ClassCastException if any two elements are not mutually
2415 * @throws NullPointerException if an element is null (since
2416 * null.compareTo cannot work)
2419 public static void sort(Object[] a)
2421 sort(a, 0, a.length, null);
2425 * Sort an array of Objects according to a Comparator. The sort is
2426 * guaranteed to be stable, that is, equal elements will not be reordered.
2427 * The sort algorithm is a mergesort with the merge omitted if the last
2428 * element of one half comes before the first element of the other half. This
2429 * algorithm gives guaranteed O(n*log(n)) time, at the expense of making a
2430 * copy of the array.
2432 * @param a the array to be sorted
2433 * @param c a Comparator to use in sorting the array; or null to indicate
2434 * the elements' natural order
2435 * @throws ClassCastException if any two elements are not mutually
2436 * comparable by the Comparator provided
2437 * @throws NullPointerException if a null element is compared with natural
2438 * ordering (only possible when c is null)
2440 public static <T> void sort(T[] a, Comparator<? super T> c)
2442 sort(a, 0, a.length, c);
2446 * Sort an array of Objects according to their natural ordering. The sort is
2447 * guaranteed to be stable, that is, equal elements will not be reordered.
2448 * The sort algorithm is a mergesort with the merge omitted if the last
2449 * element of one half comes before the first element of the other half. This
2450 * algorithm gives guaranteed O(n*log(n)) time, at the expense of making a
2451 * copy of the array.
2453 * @param a the array to be sorted
2454 * @param fromIndex the index of the first element to be sorted
2455 * @param toIndex the index of the last element to be sorted plus one
2456 * @throws ClassCastException if any two elements are not mutually
2458 * @throws NullPointerException if an element is null (since
2459 * null.compareTo cannot work)
2460 * @throws ArrayIndexOutOfBoundsException if fromIndex and toIndex
2462 * @throws IllegalArgumentException if fromIndex > toIndex
2464 public static void sort(Object[] a, int fromIndex, int toIndex)
2466 sort(a, fromIndex, toIndex, null);
2470 * Sort an array of Objects according to a Comparator. The sort is
2471 * guaranteed to be stable, that is, equal elements will not be reordered.
2472 * The sort algorithm is a mergesort with the merge omitted if the last
2473 * element of one half comes before the first element of the other half. This
2474 * algorithm gives guaranteed O(n*log(n)) time, at the expense of making a
2475 * copy of the array.
2477 * @param a the array to be sorted
2478 * @param fromIndex the index of the first element to be sorted
2479 * @param toIndex the index of the last element to be sorted plus one
2480 * @param c a Comparator to use in sorting the array; or null to indicate
2481 * the elements' natural order
2482 * @throws ClassCastException if any two elements are not mutually
2483 * comparable by the Comparator provided
2484 * @throws ArrayIndexOutOfBoundsException if fromIndex and toIndex
2486 * @throws IllegalArgumentException if fromIndex > toIndex
2487 * @throws NullPointerException if a null element is compared with natural
2488 * ordering (only possible when c is null)
2490 public static <T> void sort(T[] a, int fromIndex, int toIndex,
2491 Comparator<? super T> c)
2493 if (fromIndex > toIndex)
2494 throw new IllegalArgumentException("fromIndex " + fromIndex
2495 + " > toIndex " + toIndex);
2497 throw new ArrayIndexOutOfBoundsException();
2499 // In general, the code attempts to be simple rather than fast, the
2500 // idea being that a good optimising JIT will be able to optimise it
2501 // better than I can, and if I try it will make it more confusing for
2502 // the JIT. First presort the array in chunks of length 6 with insertion
2503 // sort. A mergesort would give too much overhead for this length.
2504 for (int chunk = fromIndex; chunk < toIndex; chunk += 6)
2506 int end = Math.min(chunk + 6, toIndex);
2507 for (int i = chunk + 1; i < end; i++)
2509 if (Collections.compare(a[i - 1], a[i], c) > 0)
2511 // not already sorted
2520 && Collections.compare(a[j - 1], elem, c) > 0);
2526 int len = toIndex - fromIndex;
2527 // If length is smaller or equal 6 we are done.
2532 T[] dest = (T[]) new Object[len];
2533 T[] t = null; // t is used for swapping src and dest
2535 // The difference of the fromIndex of the src and dest array.
2536 int srcDestDiff = -fromIndex;
2538 // The merges are done in this loop
2539 for (int size = 6; size < len; size <<= 1)
2541 for (int start = fromIndex; start < toIndex; start += size << 1)
2543 // mid is the start of the second sublist;
2544 // end the start of the next sublist (or end of array).
2545 int mid = start + size;
2546 int end = Math.min(toIndex, mid + size);
2548 // The second list is empty or the elements are already in
2549 // order - no need to merge
2551 || Collections.compare(src[mid - 1], src[mid], c) <= 0)
2553 System.arraycopy(src, start,
2554 dest, start + srcDestDiff, end - start);
2556 // The two halves just need swapping - no need to merge
2558 else if (Collections.compare(src[start], src[end - 1], c) > 0)
2560 System.arraycopy(src, start,
2561 dest, end - size + srcDestDiff, size);
2562 System.arraycopy(src, mid,
2563 dest, start + srcDestDiff, end - mid);
2568 // Declare a lot of variables to save repeating
2569 // calculations. Hopefully a decent JIT will put these
2570 // in registers and make this fast
2573 int i = start + srcDestDiff;
2575 // The main merge loop; terminates as soon as either
2577 while (p1 < mid && p2 < end)
2580 src[(Collections.compare(src[p1], src[p2], c) <= 0
2584 // Finish up by copying the remainder of whichever half
2587 System.arraycopy(src, p1, dest, i, mid - p1);
2589 System.arraycopy(src, p2, dest, i, end - p2);
2592 // swap src and dest ready for the next merge
2596 fromIndex += srcDestDiff;
2597 toIndex += srcDestDiff;
2598 srcDestDiff = -srcDestDiff;
2601 // make sure the result ends up back in the right place. Note
2602 // that src and dest may have been swapped above, so src
2603 // contains the sorted array.
2606 // Note that fromIndex == 0.
2607 System.arraycopy(src, 0, a, srcDestDiff, toIndex);
2612 * Returns a list "view" of the specified array. This method is intended to
2613 * make it easy to use the Collections API with existing array-based APIs and
2614 * programs. Changes in the list or the array show up in both places. The
2615 * list does not support element addition or removal, but does permit
2616 * value modification. The returned list implements both Serializable and
2619 * @param a the array to return a view of (<code>null</code> not permitted)
2620 * @return a fixed-size list, changes to which "write through" to the array
2622 * @throws NullPointerException if <code>a</code> is <code>null</code>.
2625 * @see Arrays.ArrayList
2627 public static <T> List<T> asList(final T... a)
2629 return new Arrays.ArrayList(a);
2633 * Returns the hashcode of an array of long numbers. If two arrays
2634 * are equal, according to <code>equals()</code>, they should have the
2635 * same hashcode. The hashcode returned by the method is equal to that
2636 * obtained by the corresponding <code>List</code> object. This has the same
2637 * data, but represents longs in their wrapper class, <code>Long</code>.
2638 * For <code>null</code>, 0 is returned.
2640 * @param v an array of long numbers for which the hash code should be
2642 * @return the hash code of the array, or 0 if null was given.
2645 public static int hashCode(long[] v)
2650 for (int i = 0; i < v.length; ++i)
2652 int elt = (int) (v[i] ^ (v[i] >>> 32));
2653 result = 31 * result + elt;
2659 * Returns the hashcode of an array of integer numbers. If two arrays
2660 * are equal, according to <code>equals()</code>, they should have the
2661 * same hashcode. The hashcode returned by the method is equal to that
2662 * obtained by the corresponding <code>List</code> object. This has the same
2663 * data, but represents ints in their wrapper class, <code>Integer</code>.
2664 * For <code>null</code>, 0 is returned.
2666 * @param v an array of integer numbers for which the hash code should be
2668 * @return the hash code of the array, or 0 if null was given.
2671 public static int hashCode(int[] v)
2676 for (int i = 0; i < v.length; ++i)
2677 result = 31 * result + v[i];
2682 * Returns the hashcode of an array of short numbers. If two arrays
2683 * are equal, according to <code>equals()</code>, they should have the
2684 * same hashcode. The hashcode returned by the method is equal to that
2685 * obtained by the corresponding <code>List</code> object. This has the same
2686 * data, but represents shorts in their wrapper class, <code>Short</code>.
2687 * For <code>null</code>, 0 is returned.
2689 * @param v an array of short numbers for which the hash code should be
2691 * @return the hash code of the array, or 0 if null was given.
2694 public static int hashCode(short[] v)
2699 for (int i = 0; i < v.length; ++i)
2700 result = 31 * result + v[i];
2705 * Returns the hashcode of an array of characters. If two arrays
2706 * are equal, according to <code>equals()</code>, they should have the
2707 * same hashcode. The hashcode returned by the method is equal to that
2708 * obtained by the corresponding <code>List</code> object. This has the same
2709 * data, but represents chars in their wrapper class, <code>Character</code>.
2710 * For <code>null</code>, 0 is returned.
2712 * @param v an array of characters for which the hash code should be
2714 * @return the hash code of the array, or 0 if null was given.
2717 public static int hashCode(char[] v)
2722 for (int i = 0; i < v.length; ++i)
2723 result = 31 * result + v[i];
2728 * Returns the hashcode of an array of bytes. If two arrays
2729 * are equal, according to <code>equals()</code>, they should have the
2730 * same hashcode. The hashcode returned by the method is equal to that
2731 * obtained by the corresponding <code>List</code> object. This has the same
2732 * data, but represents bytes in their wrapper class, <code>Byte</code>.
2733 * For <code>null</code>, 0 is returned.
2735 * @param v an array of bytes for which the hash code should be
2737 * @return the hash code of the array, or 0 if null was given.
2740 public static int hashCode(byte[] v)
2745 for (int i = 0; i < v.length; ++i)
2746 result = 31 * result + v[i];
2751 * Returns the hashcode of an array of booleans. If two arrays
2752 * are equal, according to <code>equals()</code>, they should have the
2753 * same hashcode. The hashcode returned by the method is equal to that
2754 * obtained by the corresponding <code>List</code> object. This has the same
2755 * data, but represents booleans in their wrapper class,
2756 * <code>Boolean</code>. For <code>null</code>, 0 is returned.
2758 * @param v an array of booleans for which the hash code should be
2760 * @return the hash code of the array, or 0 if null was given.
2763 public static int hashCode(boolean[] v)
2768 for (int i = 0; i < v.length; ++i)
2769 result = 31 * result + (v[i] ? 1231 : 1237);
2774 * Returns the hashcode of an array of floats. If two arrays
2775 * are equal, according to <code>equals()</code>, they should have the
2776 * same hashcode. The hashcode returned by the method is equal to that
2777 * obtained by the corresponding <code>List</code> object. This has the same
2778 * data, but represents floats in their wrapper class, <code>Float</code>.
2779 * For <code>null</code>, 0 is returned.
2781 * @param v an array of floats for which the hash code should be
2783 * @return the hash code of the array, or 0 if null was given.
2786 public static int hashCode(float[] v)
2791 for (int i = 0; i < v.length; ++i)
2792 result = 31 * result + Float.floatToIntBits(v[i]);
2797 * Returns the hashcode of an array of doubles. If two arrays
2798 * are equal, according to <code>equals()</code>, they should have the
2799 * same hashcode. The hashcode returned by the method is equal to that
2800 * obtained by the corresponding <code>List</code> object. This has the same
2801 * data, but represents doubles in their wrapper class, <code>Double</code>.
2802 * For <code>null</code>, 0 is returned.
2804 * @param v an array of doubles for which the hash code should be
2806 * @return the hash code of the array, or 0 if null was given.
2809 public static int hashCode(double[] v)
2814 for (int i = 0; i < v.length; ++i)
2816 long l = Double.doubleToLongBits(v[i]);
2817 int elt = (int) (l ^ (l >>> 32));
2818 result = 31 * result + elt;
2824 * Returns the hashcode of an array of objects. If two arrays
2825 * are equal, according to <code>equals()</code>, they should have the
2826 * same hashcode. The hashcode returned by the method is equal to that
2827 * obtained by the corresponding <code>List</code> object.
2828 * For <code>null</code>, 0 is returned.
2830 * @param v an array of integer numbers for which the hash code should be
2832 * @return the hash code of the array, or 0 if null was given.
2835 public static int hashCode(Object[] v)
2840 for (int i = 0; i < v.length; ++i)
2842 int elt = v[i] == null ? 0 : v[i].hashCode();
2843 result = 31 * result + elt;
2848 public static int deepHashCode(Object[] v)
2853 for (int i = 0; i < v.length; ++i)
2858 else if (v[i] instanceof boolean[])
2859 elt = hashCode((boolean[]) v[i]);
2860 else if (v[i] instanceof byte[])
2861 elt = hashCode((byte[]) v[i]);
2862 else if (v[i] instanceof char[])
2863 elt = hashCode((char[]) v[i]);
2864 else if (v[i] instanceof short[])
2865 elt = hashCode((short[]) v[i]);
2866 else if (v[i] instanceof int[])
2867 elt = hashCode((int[]) v[i]);
2868 else if (v[i] instanceof long[])
2869 elt = hashCode((long[]) v[i]);
2870 else if (v[i] instanceof float[])
2871 elt = hashCode((float[]) v[i]);
2872 else if (v[i] instanceof double[])
2873 elt = hashCode((double[]) v[i]);
2874 else if (v[i] instanceof Object[])
2875 elt = hashCode((Object[]) v[i]);
2877 elt = v[i].hashCode();
2878 result = 31 * result + elt;
2884 public static boolean deepEquals(Object[] v1, Object[] v2)
2888 if (v2 == null || v1.length != v2.length)
2891 for (int i = 0; i < v1.length; ++i)
2898 if (e1 == null || e2 == null)
2902 if (e1 instanceof boolean[] && e2 instanceof boolean[])
2903 check = equals((boolean[]) e1, (boolean[]) e2);
2904 else if (e1 instanceof byte[] && e2 instanceof byte[])
2905 check = equals((byte[]) e1, (byte[]) e2);
2906 else if (e1 instanceof char[] && e2 instanceof char[])
2907 check = equals((char[]) e1, (char[]) e2);
2908 else if (e1 instanceof short[] && e2 instanceof short[])
2909 check = equals((short[]) e1, (short[]) e2);
2910 else if (e1 instanceof int[] && e2 instanceof int[])
2911 check = equals((int[]) e1, (int[]) e2);
2912 else if (e1 instanceof long[] && e2 instanceof long[])
2913 check = equals((long[]) e1, (long[]) e2);
2914 else if (e1 instanceof float[] && e2 instanceof float[])
2915 check = equals((float[]) e1, (float[]) e2);
2916 else if (e1 instanceof double[] && e2 instanceof double[])
2917 check = equals((double[]) e1, (double[]) e2);
2918 else if (e1 instanceof Object[] && e2 instanceof Object[])
2919 check = equals((Object[]) e1, (Object[]) e2);
2921 check = e1.equals(e2);
2930 * Returns a String representation of the argument array. Returns "null"
2931 * if <code>a</code> is null.
2932 * @param v the array to represent
2933 * @return a String representing this array
2936 public static String toString(boolean[] v)
2940 CPStringBuilder b = new CPStringBuilder("[");
2941 for (int i = 0; i < v.length; ++i)
2948 return b.toString();
2952 * Returns a String representation of the argument array. Returns "null"
2953 * if <code>a</code> is null.
2954 * @param v the array to represent
2955 * @return a String representing this array
2958 public static String toString(byte[] v)
2962 CPStringBuilder b = new CPStringBuilder("[");
2963 for (int i = 0; i < v.length; ++i)
2970 return b.toString();
2974 * Returns a String representation of the argument array. Returns "null"
2975 * if <code>a</code> is null.
2976 * @param v the array to represent
2977 * @return a String representing this array
2980 public static String toString(char[] v)
2984 CPStringBuilder b = new CPStringBuilder("[");
2985 for (int i = 0; i < v.length; ++i)
2992 return b.toString();
2996 * Returns a String representation of the argument array. Returns "null"
2997 * if <code>a</code> is null.
2998 * @param v the array to represent
2999 * @return a String representing this array
3002 public static String toString(short[] v)
3006 CPStringBuilder b = new CPStringBuilder("[");
3007 for (int i = 0; i < v.length; ++i)
3014 return b.toString();
3018 * Returns a String representation of the argument array. Returns "null"
3019 * if <code>a</code> is null.
3020 * @param v the array to represent
3021 * @return a String representing this array
3024 public static String toString(int[] v)
3028 CPStringBuilder b = new CPStringBuilder("[");
3029 for (int i = 0; i < v.length; ++i)
3036 return b.toString();
3040 * Returns a String representation of the argument array. Returns "null"
3041 * if <code>a</code> is null.
3042 * @param v the array to represent
3043 * @return a String representing this array
3046 public static String toString(long[] v)
3050 CPStringBuilder b = new CPStringBuilder("[");
3051 for (int i = 0; i < v.length; ++i)
3058 return b.toString();
3062 * Returns a String representation of the argument array. Returns "null"
3063 * if <code>a</code> is null.
3064 * @param v the array to represent
3065 * @return a String representing this array
3068 public static String toString(float[] v)
3072 CPStringBuilder b = new CPStringBuilder("[");
3073 for (int i = 0; i < v.length; ++i)
3080 return b.toString();
3084 * Returns a String representation of the argument array. Returns "null"
3085 * if <code>a</code> is null.
3086 * @param v the array to represent
3087 * @return a String representing this array
3090 public static String toString(double[] v)
3094 CPStringBuilder b = new CPStringBuilder("[");
3095 for (int i = 0; i < v.length; ++i)
3102 return b.toString();
3106 * Returns a String representation of the argument array. Returns "null"
3107 * if <code>a</code> is null.
3108 * @param v the array to represent
3109 * @return a String representing this array
3112 public static String toString(Object[] v)
3116 CPStringBuilder b = new CPStringBuilder("[");
3117 for (int i = 0; i < v.length; ++i)
3124 return b.toString();
3127 private static void deepToString(Object[] v, CPStringBuilder b, HashSet seen)
3130 for (int i = 0; i < v.length; ++i)
3137 else if (elt instanceof boolean[])
3138 b.append(toString((boolean[]) elt));
3139 else if (elt instanceof byte[])
3140 b.append(toString((byte[]) elt));
3141 else if (elt instanceof char[])
3142 b.append(toString((char[]) elt));
3143 else if (elt instanceof short[])
3144 b.append(toString((short[]) elt));
3145 else if (elt instanceof int[])
3146 b.append(toString((int[]) elt));
3147 else if (elt instanceof long[])
3148 b.append(toString((long[]) elt));
3149 else if (elt instanceof float[])
3150 b.append(toString((float[]) elt));
3151 else if (elt instanceof double[])
3152 b.append(toString((double[]) elt));
3153 else if (elt instanceof Object[])
3155 Object[] os = (Object[]) elt;
3156 if (seen.contains(os))
3161 deepToString(os, b, seen);
3171 public static String deepToString(Object[] v)
3175 HashSet seen = new HashSet();
3176 CPStringBuilder b = new CPStringBuilder();
3177 deepToString(v, b, seen);
3178 return b.toString();
3182 * Inner class used by {@link #asList(Object[])} to provide a list interface
3183 * to an array. The name, though it clashes with java.util.ArrayList, is
3184 * Sun's choice for Serialization purposes. Element addition and removal
3185 * is prohibited, but values can be modified.
3187 * @author Eric Blake (ebb9@email.byu.edu)
3188 * @status updated to 1.4
3190 private static final class ArrayList<E> extends AbstractList<E>
3191 implements Serializable, RandomAccess
3193 // We override the necessary methods, plus others which will be much
3194 // more efficient with direct iteration rather than relying on iterator().
3197 * Compatible with JDK 1.4.
3199 private static final long serialVersionUID = -2764017481108945198L;
3202 * The array we are viewing.
3205 private final E[] a;
3208 * Construct a list view of the array.
3209 * @param a the array to view
3210 * @throws NullPointerException if a is null
3214 // We have to explicitly check.
3216 throw new NullPointerException();
3221 * Returns the object at the specified index in
3224 * @param index The index to retrieve an object from.
3225 * @return The object at the array index specified.
3227 public E get(int index)
3233 * Returns the size of the array.
3243 * Replaces the object at the specified index
3244 * with the supplied element.
3246 * @param index The index at which to place the new object.
3247 * @param element The new object.
3248 * @return The object replaced by this operation.
3250 public E set(int index, E element)
3258 * Returns true if the array contains the
3261 * @param o The object to look for.
3262 * @return True if the object was found.
3264 public boolean contains(Object o)
3266 return lastIndexOf(o) >= 0;
3270 * Returns the first index at which the
3271 * object, o, occurs in the array.
3273 * @param o The object to search for.
3274 * @return The first relevant index.
3276 public int indexOf(Object o)
3278 int size = a.length;
3279 for (int i = 0; i < size; i++)
3280 if (ArrayList.equals(o, a[i]))
3286 * Returns the last index at which the
3287 * object, o, occurs in the array.
3289 * @param o The object to search for.
3290 * @return The last relevant index.
3292 public int lastIndexOf(Object o)
3296 if (ArrayList.equals(o, a[i]))
3302 * Transforms the list into an array of
3303 * objects, by simplying cloning the array
3304 * wrapped by this list.
3306 * @return A clone of the internal array.
3308 public Object[] toArray()
3310 return (Object[]) a.clone();
3314 * Copies the objects from this list into
3315 * the supplied array. The supplied array
3316 * is shrunk or enlarged to the size of the
3317 * internal array, and filled with its objects.
3319 * @param array The array to fill with the objects in this list.
3320 * @return The array containing the objects in this list,
3321 * which may or may not be == to array.
3323 public <T> T[] toArray(T[] array)
3325 int size = a.length;
3326 if (array.length < size)
3327 array = (T[]) Array.newInstance(array.getClass().getComponentType(),
3329 else if (array.length > size)
3332 System.arraycopy(a, 0, array, 0, size);
3338 * Returns a copy of the supplied array, truncating or padding as
3339 * necessary with <code>false</code> to obtain the specified length.
3340 * Indices that are valid for both arrays will return the same value.
3341 * Indices that only exist in the returned array (due to the new length
3342 * being greater than the original length) will return <code>false</code>.
3343 * This is equivalent to calling
3344 * <code>copyOfRange(original, 0, newLength)</code>.
3346 * @param original the original array to be copied.
3347 * @param newLength the length of the returned array.
3348 * @return a copy of the original array, truncated or padded with
3349 * <code>false</code> to obtain the required length.
3350 * @throws NegativeArraySizeException if <code>newLength</code> is negative.
3351 * @throws NullPointerException if <code>original</code> is <code>null</code>.
3353 * @see #copyOfRange(boolean[],int,int)
3355 public static boolean[] copyOf(boolean[] original, int newLength)
3358 throw new NegativeArraySizeException("The array size is negative.");
3359 return copyOfRange(original, 0, newLength);
3363 * Copies the specified range of the supplied array to a new
3364 * array, padding as necessary with <code>false</code>
3365 * if <code>to</code> is greater than the length of the original
3366 * array. <code>from</code> must be in the range zero to
3367 * <code>original.length</code> and can not be greater than
3368 * <code>to</code>. The initial element of the
3369 * returned array will be equal to <code>original[from]</code>,
3370 * except where <code>from</code> is equal to <code>to</code>
3371 * (where a zero-length array will be returned) or <code>
3372 * <code>from</code> is equal to <code>original.length</code>
3373 * (where an array padded with <code>false</code> will be
3374 * returned). The returned array is always of length
3375 * <code>to - from</code>.
3377 * @param original the array from which to copy.
3378 * @param from the initial index of the range, inclusive.
3379 * @param to the final index of the range, exclusive.
3380 * @return a copy of the specified range, with padding to
3381 * obtain the required length.
3382 * @throws ArrayIndexOutOfBoundsException if <code>from < 0</code>
3383 * or <code>from > original.length</code>
3384 * @throws IllegalArgumentException if <code>from > to</code>
3385 * @throws NullPointerException if <code>original</code> is <code>null</code>.
3387 * @see #copyOf(boolean[],int)
3389 public static boolean[] copyOfRange(boolean[] original, int from, int to)
3392 throw new IllegalArgumentException("The initial index is after " +
3393 "the final index.");
3394 boolean[] newArray = new boolean[to - from];
3395 if (to > original.length)
3397 System.arraycopy(original, from, newArray, 0,
3398 original.length - from);
3399 fill(newArray, original.length, newArray.length, false);
3402 System.arraycopy(original, from, newArray, 0, to - from);
3407 * Returns a copy of the supplied array, truncating or padding as
3408 * necessary with <code>(byte)0</code> to obtain the specified length.
3409 * Indices that are valid for both arrays will return the same value.
3410 * Indices that only exist in the returned array (due to the new length
3411 * being greater than the original length) will return <code>(byte)0</code>.
3412 * This is equivalent to calling
3413 * <code>copyOfRange(original, 0, newLength)</code>.
3415 * @param original the original array to be copied.
3416 * @param newLength the length of the returned array.
3417 * @return a copy of the original array, truncated or padded with
3418 * <code>(byte)0</code> to obtain the required length.
3419 * @throws NegativeArraySizeException if <code>newLength</code> is negative.
3420 * @throws NullPointerException if <code>original</code> is <code>null</code>.
3422 * @see #copyOfRange(byte[],int,int)
3424 public static byte[] copyOf(byte[] original, int newLength)
3427 throw new NegativeArraySizeException("The array size is negative.");
3428 return copyOfRange(original, 0, newLength);
3432 * Copies the specified range of the supplied array to a new
3433 * array, padding as necessary with <code>(byte)0</code>
3434 * if <code>to</code> is greater than the length of the original
3435 * array. <code>from</code> must be in the range zero to
3436 * <code>original.length</code> and can not be greater than
3437 * <code>to</code>. The initial element of the
3438 * returned array will be equal to <code>original[from]</code>,
3439 * except where <code>from</code> is equal to <code>to</code>
3440 * (where a zero-length array will be returned) or <code>
3441 * <code>from</code> is equal to <code>original.length</code>
3442 * (where an array padded with <code>(byte)0</code> will be
3443 * returned). The returned array is always of length
3444 * <code>to - from</code>.
3446 * @param original the array from which to copy.
3447 * @param from the initial index of the range, inclusive.
3448 * @param to the final index of the range, exclusive.
3449 * @return a copy of the specified range, with padding to
3450 * obtain the required length.
3451 * @throws ArrayIndexOutOfBoundsException if <code>from < 0</code>
3452 * or <code>from > original.length</code>
3453 * @throws IllegalArgumentException if <code>from > to</code>
3454 * @throws NullPointerException if <code>original</code> is <code>null</code>.
3456 * @see #copyOf(byte[],int)
3458 public static byte[] copyOfRange(byte[] original, int from, int to)
3461 throw new IllegalArgumentException("The initial index is after " +
3462 "the final index.");
3463 byte[] newArray = new byte[to - from];
3464 if (to > original.length)
3466 System.arraycopy(original, from, newArray, 0,
3467 original.length - from);
3468 fill(newArray, original.length, newArray.length, (byte)0);
3471 System.arraycopy(original, from, newArray, 0, to - from);
3476 * Returns a copy of the supplied array, truncating or padding as
3477 * necessary with <code>'\0'</code> to obtain the specified length.
3478 * Indices that are valid for both arrays will return the same value.
3479 * Indices that only exist in the returned array (due to the new length
3480 * being greater than the original length) will return <code>'\0'</code>.
3481 * This is equivalent to calling
3482 * <code>copyOfRange(original, 0, newLength)</code>.
3484 * @param original the original array to be copied.
3485 * @param newLength the length of the returned array.
3486 * @return a copy of the original array, truncated or padded with
3487 * <code>'\0'</code> to obtain the required length.
3488 * @throws NegativeArraySizeException if <code>newLength</code> is negative.
3489 * @throws NullPointerException if <code>original</code> is <code>null</code>.
3491 * @see #copyOfRange(char[],int,int)
3493 public static char[] copyOf(char[] original, int newLength)
3496 throw new NegativeArraySizeException("The array size is negative.");
3497 return copyOfRange(original, 0, newLength);
3501 * Copies the specified range of the supplied array to a new
3502 * array, padding as necessary with <code>'\0'</code>
3503 * if <code>to</code> is greater than the length of the original
3504 * array. <code>from</code> must be in the range zero to
3505 * <code>original.length</code> and can not be greater than
3506 * <code>to</code>. The initial element of the
3507 * returned array will be equal to <code>original[from]</code>,
3508 * except where <code>from</code> is equal to <code>to</code>
3509 * (where a zero-length array will be returned) or <code>
3510 * <code>from</code> is equal to <code>original.length</code>
3511 * (where an array padded with <code>'\0'</code> will be
3512 * returned). The returned array is always of length
3513 * <code>to - from</code>.
3515 * @param original the array from which to copy.
3516 * @param from the initial index of the range, inclusive.
3517 * @param to the final index of the range, exclusive.
3518 * @return a copy of the specified range, with padding to
3519 * obtain the required length.
3520 * @throws ArrayIndexOutOfBoundsException if <code>from < 0</code>
3521 * or <code>from > original.length</code>
3522 * @throws IllegalArgumentException if <code>from > to</code>
3523 * @throws NullPointerException if <code>original</code> is <code>null</code>.
3525 * @see #copyOf(char[],int)
3527 public static char[] copyOfRange(char[] original, int from, int to)
3530 throw new IllegalArgumentException("The initial index is after " +
3531 "the final index.");
3532 char[] newArray = new char[to - from];
3533 if (to > original.length)
3535 System.arraycopy(original, from, newArray, 0,
3536 original.length - from);
3537 fill(newArray, original.length, newArray.length, '\0');
3540 System.arraycopy(original, from, newArray, 0, to - from);
3545 * Returns a copy of the supplied array, truncating or padding as
3546 * necessary with <code>0d</code> to obtain the specified length.
3547 * Indices that are valid for both arrays will return the same value.
3548 * Indices that only exist in the returned array (due to the new length
3549 * being greater than the original length) will return <code>0d</code>.
3550 * This is equivalent to calling
3551 * <code>copyOfRange(original, 0, newLength)</code>.
3553 * @param original the original array to be copied.
3554 * @param newLength the length of the returned array.
3555 * @return a copy of the original array, truncated or padded with
3556 * <code>0d</code> to obtain the required length.
3557 * @throws NegativeArraySizeException if <code>newLength</code> is negative.
3558 * @throws NullPointerException if <code>original</code> is <code>null</code>.
3560 * @see #copyOfRange(double[],int,int)
3562 public static double[] copyOf(double[] original, int newLength)
3565 throw new NegativeArraySizeException("The array size is negative.");
3566 return copyOfRange(original, 0, newLength);
3570 * Copies the specified range of the supplied array to a new
3571 * array, padding as necessary with <code>0d</code>
3572 * if <code>to</code> is greater than the length of the original
3573 * array. <code>from</code> must be in the range zero to
3574 * <code>original.length</code> and can not be greater than
3575 * <code>to</code>. The initial element of the
3576 * returned array will be equal to <code>original[from]</code>,
3577 * except where <code>from</code> is equal to <code>to</code>
3578 * (where a zero-length array will be returned) or <code>
3579 * <code>from</code> is equal to <code>original.length</code>
3580 * (where an array padded with <code>0d</code> will be
3581 * returned). The returned array is always of length
3582 * <code>to - from</code>.
3584 * @param original the array from which to copy.
3585 * @param from the initial index of the range, inclusive.
3586 * @param to the final index of the range, exclusive.
3587 * @return a copy of the specified range, with padding to
3588 * obtain the required length.
3589 * @throws ArrayIndexOutOfBoundsException if <code>from < 0</code>
3590 * or <code>from > original.length</code>
3591 * @throws IllegalArgumentException if <code>from > to</code>
3592 * @throws NullPointerException if <code>original</code> is <code>null</code>.
3594 * @see #copyOf(double[],int)
3596 public static double[] copyOfRange(double[] original, int from, int to)
3599 throw new IllegalArgumentException("The initial index is after " +
3600 "the final index.");
3601 double[] newArray = new double[to - from];
3602 if (to > original.length)
3604 System.arraycopy(original, from, newArray, 0,
3605 original.length - from);
3606 fill(newArray, original.length, newArray.length, 0d);
3609 System.arraycopy(original, from, newArray, 0, to - from);
3614 * Returns a copy of the supplied array, truncating or padding as
3615 * necessary with <code>0f</code> to obtain the specified length.
3616 * Indices that are valid for both arrays will return the same value.
3617 * Indices that only exist in the returned array (due to the new length
3618 * being greater than the original length) will return <code>0f</code>.
3619 * This is equivalent to calling
3620 * <code>copyOfRange(original, 0, newLength)</code>.
3622 * @param original the original array to be copied.
3623 * @param newLength the length of the returned array.
3624 * @return a copy of the original array, truncated or padded with
3625 * <code>0f</code> to obtain the required length.
3626 * @throws NegativeArraySizeException if <code>newLength</code> is negative.
3627 * @throws NullPointerException if <code>original</code> is <code>null</code>.
3629 * @see #copyOfRange(float[],int,int)
3631 public static float[] copyOf(float[] original, int newLength)
3634 throw new NegativeArraySizeException("The array size is negative.");
3635 return copyOfRange(original, 0, newLength);
3639 * Copies the specified range of the supplied array to a new
3640 * array, padding as necessary with <code>0f</code>
3641 * if <code>to</code> is greater than the length of the original
3642 * array. <code>from</code> must be in the range zero to
3643 * <code>original.length</code> and can not be greater than
3644 * <code>to</code>. The initial element of the
3645 * returned array will be equal to <code>original[from]</code>,
3646 * except where <code>from</code> is equal to <code>to</code>
3647 * (where a zero-length array will be returned) or <code>
3648 * <code>from</code> is equal to <code>original.length</code>
3649 * (where an array padded with <code>0f</code> will be
3650 * returned). The returned array is always of length
3651 * <code>to - from</code>.
3653 * @param original the array from which to copy.
3654 * @param from the initial index of the range, inclusive.
3655 * @param to the final index of the range, exclusive.
3656 * @return a copy of the specified range, with padding to
3657 * obtain the required length.
3658 * @throws ArrayIndexOutOfBoundsException if <code>from < 0</code>
3659 * or <code>from > original.length</code>
3660 * @throws IllegalArgumentException if <code>from > to</code>
3661 * @throws NullPointerException if <code>original</code> is <code>null</code>.
3663 * @see #copyOf(float[],int)
3665 public static float[] copyOfRange(float[] original, int from, int to)
3668 throw new IllegalArgumentException("The initial index is after " +
3669 "the final index.");
3670 float[] newArray = new float[to - from];
3671 if (to > original.length)
3673 System.arraycopy(original, from, newArray, 0,
3674 original.length - from);
3675 fill(newArray, original.length, newArray.length, 0f);
3678 System.arraycopy(original, from, newArray, 0, to - from);
3683 * Returns a copy of the supplied array, truncating or padding as
3684 * necessary with <code>0</code> to obtain the specified length.
3685 * Indices that are valid for both arrays will return the same value.
3686 * Indices that only exist in the returned array (due to the new length
3687 * being greater than the original length) will return <code>0</code>.
3688 * This is equivalent to calling
3689 * <code>copyOfRange(original, 0, newLength)</code>.
3691 * @param original the original array to be copied.
3692 * @param newLength the length of the returned array.
3693 * @return a copy of the original array, truncated or padded with
3694 * <code>0</code> to obtain the required length.
3695 * @throws NegativeArraySizeException if <code>newLength</code> is negative.
3696 * @throws NullPointerException if <code>original</code> is <code>null</code>.
3698 * @see #copyOfRange(int[],int,int)
3700 public static int[] copyOf(int[] original, int newLength)
3703 throw new NegativeArraySizeException("The array size is negative.");
3704 return copyOfRange(original, 0, newLength);
3708 * Copies the specified range of the supplied array to a new
3709 * array, padding as necessary with <code>0</code>
3710 * if <code>to</code> is greater than the length of the original
3711 * array. <code>from</code> must be in the range zero to
3712 * <code>original.length</code> and can not be greater than
3713 * <code>to</code>. The initial element of the
3714 * returned array will be equal to <code>original[from]</code>,
3715 * except where <code>from</code> is equal to <code>to</code>
3716 * (where a zero-length array will be returned) or <code>
3717 * <code>from</code> is equal to <code>original.length</code>
3718 * (where an array padded with <code>0</code> will be
3719 * returned). The returned array is always of length
3720 * <code>to - from</code>.
3722 * @param original the array from which to copy.
3723 * @param from the initial index of the range, inclusive.
3724 * @param to the final index of the range, exclusive.
3725 * @return a copy of the specified range, with padding to
3726 * obtain the required length.
3727 * @throws ArrayIndexOutOfBoundsException if <code>from < 0</code>
3728 * or <code>from > original.length</code>
3729 * @throws IllegalArgumentException if <code>from > to</code>
3730 * @throws NullPointerException if <code>original</code> is <code>null</code>.
3732 * @see #copyOf(int[],int)
3734 public static int[] copyOfRange(int[] original, int from, int to)
3737 throw new IllegalArgumentException("The initial index is after " +
3738 "the final index.");
3739 int[] newArray = new int[to - from];
3740 if (to > original.length)
3742 System.arraycopy(original, from, newArray, 0,
3743 original.length - from);
3744 fill(newArray, original.length, newArray.length, 0);
3747 System.arraycopy(original, from, newArray, 0, to - from);
3752 * Returns a copy of the supplied array, truncating or padding as
3753 * necessary with <code>0L</code> to obtain the specified length.
3754 * Indices that are valid for both arrays will return the same value.
3755 * Indices that only exist in the returned array (due to the new length
3756 * being greater than the original length) will return <code>0L</code>.
3757 * This is equivalent to calling
3758 * <code>copyOfRange(original, 0, newLength)</code>.
3760 * @param original the original array to be copied.
3761 * @param newLength the length of the returned array.
3762 * @return a copy of the original array, truncated or padded with
3763 * <code>0L</code> to obtain the required length.
3764 * @throws NegativeArraySizeException if <code>newLength</code> is negative.
3765 * @throws NullPointerException if <code>original</code> is <code>null</code>.
3767 * @see #copyOfRange(long[],int,int)
3769 public static long[] copyOf(long[] original, int newLength)
3772 throw new NegativeArraySizeException("The array size is negative.");
3773 return copyOfRange(original, 0, newLength);
3777 * Copies the specified range of the supplied array to a new
3778 * array, padding as necessary with <code>0L</code>
3779 * if <code>to</code> is greater than the length of the original
3780 * array. <code>from</code> must be in the range zero to
3781 * <code>original.length</code> and can not be greater than
3782 * <code>to</code>. The initial element of the
3783 * returned array will be equal to <code>original[from]</code>,
3784 * except where <code>from</code> is equal to <code>to</code>
3785 * (where a zero-length array will be returned) or <code>
3786 * <code>from</code> is equal to <code>original.length</code>
3787 * (where an array padded with <code>0L</code> will be
3788 * returned). The returned array is always of length
3789 * <code>to - from</code>.
3791 * @param original the array from which to copy.
3792 * @param from the initial index of the range, inclusive.
3793 * @param to the final index of the range, exclusive.
3794 * @return a copy of the specified range, with padding to
3795 * obtain the required length.
3796 * @throws ArrayIndexOutOfBoundsException if <code>from < 0</code>
3797 * or <code>from > original.length</code>
3798 * @throws IllegalArgumentException if <code>from > to</code>
3799 * @throws NullPointerException if <code>original</code> is <code>null</code>.
3801 * @see #copyOf(long[],int)
3803 public static long[] copyOfRange(long[] original, int from, int to)
3806 throw new IllegalArgumentException("The initial index is after " +
3807 "the final index.");
3808 long[] newArray = new long[to - from];
3809 if (to > original.length)
3811 System.arraycopy(original, from, newArray, 0,
3812 original.length - from);
3813 fill(newArray, original.length, newArray.length, 0L);
3816 System.arraycopy(original, from, newArray, 0, to - from);
3821 * Returns a copy of the supplied array, truncating or padding as
3822 * necessary with <code>(short)0</code> to obtain the specified length.
3823 * Indices that are valid for both arrays will return the same value.
3824 * Indices that only exist in the returned array (due to the new length
3825 * being greater than the original length) will return <code>(short)0</code>.
3826 * This is equivalent to calling
3827 * <code>copyOfRange(original, 0, newLength)</code>.
3829 * @param original the original array to be copied.
3830 * @param newLength the length of the returned array.
3831 * @return a copy of the original array, truncated or padded with
3832 * <code>(short)0</code> to obtain the required length.
3833 * @throws NegativeArraySizeException if <code>newLength</code> is negative.
3834 * @throws NullPointerException if <code>original</code> is <code>null</code>.
3836 * @see #copyOfRange(short[],int,int)
3838 public static short[] copyOf(short[] original, int newLength)
3841 throw new NegativeArraySizeException("The array size is negative.");
3842 return copyOfRange(original, 0, newLength);
3846 * Copies the specified range of the supplied array to a new
3847 * array, padding as necessary with <code>(short)0</code>
3848 * if <code>to</code> is greater than the length of the original
3849 * array. <code>from</code> must be in the range zero to
3850 * <code>original.length</code> and can not be greater than
3851 * <code>to</code>. The initial element of the
3852 * returned array will be equal to <code>original[from]</code>,
3853 * except where <code>from</code> is equal to <code>to</code>
3854 * (where a zero-length array will be returned) or <code>
3855 * <code>from</code> is equal to <code>original.length</code>
3856 * (where an array padded with <code>(short)0</code> will be
3857 * returned). The returned array is always of length
3858 * <code>to - from</code>.
3860 * @param original the array from which to copy.
3861 * @param from the initial index of the range, inclusive.
3862 * @param to the final index of the range, exclusive.
3863 * @return a copy of the specified range, with padding to
3864 * obtain the required length.
3865 * @throws ArrayIndexOutOfBoundsException if <code>from < 0</code>
3866 * or <code>from > original.length</code>
3867 * @throws IllegalArgumentException if <code>from > to</code>
3868 * @throws NullPointerException if <code>original</code> is <code>null</code>.
3870 * @see #copyOf(short[],int)
3872 public static short[] copyOfRange(short[] original, int from, int to)
3875 throw new IllegalArgumentException("The initial index is after " +
3876 "the final index.");
3877 short[] newArray = new short[to - from];
3878 if (to > original.length)
3880 System.arraycopy(original, from, newArray, 0,
3881 original.length - from);
3882 fill(newArray, original.length, newArray.length, (short)0);
3885 System.arraycopy(original, from, newArray, 0, to - from);
3890 * Returns a copy of the supplied array, truncating or padding as
3891 * necessary with <code>null</code> to obtain the specified length.
3892 * Indices that are valid for both arrays will return the same value.
3893 * Indices that only exist in the returned array (due to the new length
3894 * being greater than the original length) will return <code>null</code>.
3895 * This is equivalent to calling
3896 * <code>copyOfRange(original, 0, newLength)</code>.
3898 * @param original the original array to be copied.
3899 * @param newLength the length of the returned array.
3900 * @return a copy of the original array, truncated or padded with
3901 * <code>null</code> to obtain the required length.
3902 * @throws NegativeArraySizeException if <code>newLength</code> is negative.
3903 * @throws NullPointerException if <code>original</code> is <code>null</code>.
3905 * @see #copyOfRange(T[],int,int)
3907 public static <T> T[] copyOf(T[] original, int newLength)
3910 throw new NegativeArraySizeException("The array size is negative.");
3911 return copyOfRange(original, 0, newLength);
3915 * Copies the specified range of the supplied array to a new
3916 * array, padding as necessary with <code>null</code>
3917 * if <code>to</code> is greater than the length of the original
3918 * array. <code>from</code> must be in the range zero to
3919 * <code>original.length</code> and can not be greater than
3920 * <code>to</code>. The initial element of the
3921 * returned array will be equal to <code>original[from]</code>,
3922 * except where <code>from</code> is equal to <code>to</code>
3923 * (where a zero-length array will be returned) or <code>
3924 * <code>from</code> is equal to <code>original.length</code>
3925 * (where an array padded with <code>null</code> will be
3926 * returned). The returned array is always of length
3927 * <code>to - from</code>.
3929 * @param original the array from which to copy.
3930 * @param from the initial index of the range, inclusive.
3931 * @param to the final index of the range, exclusive.
3932 * @return a copy of the specified range, with padding to
3933 * obtain the required length.
3934 * @throws ArrayIndexOutOfBoundsException if <code>from < 0</code>
3935 * or <code>from > original.length</code>
3936 * @throws IllegalArgumentException if <code>from > to</code>
3937 * @throws NullPointerException if <code>original</code> is <code>null</code>.
3939 * @see #copyOf(T[],int)
3941 public static <T> T[] copyOfRange(T[] original, int from, int to)
3944 throw new IllegalArgumentException("The initial index is after " +
3945 "the final index.");
3946 Class elemType = original.getClass().getComponentType();
3947 T[] newArray = (T[]) Array.newInstance(elemType, to - from);
3948 if (to > original.length)
3950 System.arraycopy(original, from, newArray, 0,
3951 original.length - from);
3952 fill(newArray, original.length, newArray.length, null);
3955 System.arraycopy(original, from, newArray, 0, to - from);
3960 * Returns a copy of the supplied array, truncating or padding as
3961 * necessary with <code>null</code> to obtain the specified length.
3962 * Indices that are valid for both arrays will return the same value.
3963 * Indices that only exist in the returned array (due to the new length
3964 * being greater than the original length) will return <code>null</code>.
3965 * This is equivalent to calling
3966 * <code>copyOfRange(original, 0, newLength, newType)</code>. The returned
3967 * array will be of the specified type, <code>newType</code>.
3969 * @param original the original array to be copied.
3970 * @param newLength the length of the returned array.
3971 * @param newType the type of the returned array.
3972 * @return a copy of the original array, truncated or padded with
3973 * <code>null</code> to obtain the required length.
3974 * @throws NegativeArraySizeException if <code>newLength</code> is negative.
3975 * @throws NullPointerException if <code>original</code> is <code>null</code>.
3977 * @see #copyOfRange(U[],int,int,Class)
3979 public static <T,U> T[] copyOf(U[] original, int newLength,
3980 Class<? extends T[]> newType)
3983 throw new NegativeArraySizeException("The array size is negative.");
3984 return copyOfRange(original, 0, newLength, newType);
3988 * Copies the specified range of the supplied array to a new
3989 * array, padding as necessary with <code>null</code>
3990 * if <code>to</code> is greater than the length of the original
3991 * array. <code>from</code> must be in the range zero to
3992 * <code>original.length</code> and can not be greater than
3993 * <code>to</code>. The initial element of the
3994 * returned array will be equal to <code>original[from]</code>,
3995 * except where <code>from</code> is equal to <code>to</code>
3996 * (where a zero-length array will be returned) or <code>
3997 * <code>from</code> is equal to <code>original.length</code>
3998 * (where an array padded with <code>null</code> will be
3999 * returned). The returned array is always of length
4000 * <code>to - from</code> and will be of the specified type,
4001 * <code>newType</code>.
4003 * @param original the array from which to copy.
4004 * @param from the initial index of the range, inclusive.
4005 * @param to the final index of the range, exclusive.
4006 * @param newType the type of the returned array.
4007 * @return a copy of the specified range, with padding to
4008 * obtain the required length.
4009 * @throws ArrayIndexOutOfBoundsException if <code>from < 0</code>
4010 * or <code>from > original.length</code>
4011 * @throws IllegalArgumentException if <code>from > to</code>
4012 * @throws NullPointerException if <code>original</code> is <code>null</code>.
4014 * @see #copyOf(T[],int)
4016 public static <T,U> T[] copyOfRange(U[] original, int from, int to,
4017 Class<? extends T[]> newType)
4020 throw new IllegalArgumentException("The initial index is after " +
4021 "the final index.");
4022 T[] newArray = (T[]) Array.newInstance(newType.getComponentType(),
4024 if (to > original.length)
4026 System.arraycopy(original, from, newArray, 0,
4027 original.length - from);
4028 fill(newArray, original.length, newArray.length, null);
4031 System.arraycopy(original, from, newArray, 0, to - from);