001 /* Arrays.java -- Utility class with methods to operate on arrays
002 Copyright (C) 1998, 1999, 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007,
003 Free Software Foundation, Inc.
004
005 This file is part of GNU Classpath.
006
007 GNU Classpath is free software; you can redistribute it and/or modify
008 it under the terms of the GNU General Public License as published by
009 the Free Software Foundation; either version 2, or (at your option)
010 any later version.
011
012 GNU Classpath is distributed in the hope that it will be useful, but
013 WITHOUT ANY WARRANTY; without even the implied warranty of
014 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
015 General Public License for more details.
016
017 You should have received a copy of the GNU General Public License
018 along with GNU Classpath; see the file COPYING. If not, write to the
019 Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
020 02110-1301 USA.
021
022 Linking this library statically or dynamically with other modules is
023 making a combined work based on this library. Thus, the terms and
024 conditions of the GNU General Public License cover the whole
025 combination.
026
027 As a special exception, the copyright holders of this library give you
028 permission to link this library with independent modules to produce an
029 executable, regardless of the license terms of these independent
030 modules, and to copy and distribute the resulting executable under
031 terms of your choice, provided that you also meet, for each linked
032 independent module, the terms and conditions of the license of that
033 module. An independent module is a module which is not derived from
034 or based on this library. If you modify this library, you may extend
035 this exception to your version of the library, but you are not
036 obligated to do so. If you do not wish to do so, delete this
037 exception statement from your version. */
038
039
040 package java.util;
041
042 import gnu.java.lang.CPStringBuilder;
043
044 import java.io.Serializable;
045 import java.lang.reflect.Array;
046
047 /**
048 * This class contains various static utility methods performing operations on
049 * arrays, and a method to provide a List "view" of an array to facilitate
050 * using arrays with Collection-based APIs. All methods throw a
051 * {@link NullPointerException} if the parameter array is null.
052 * <p>
053 *
054 * Implementations may use their own algorithms, but must obey the general
055 * properties; for example, the sort must be stable and n*log(n) complexity.
056 * Sun's implementation of sort, and therefore ours, is a tuned quicksort,
057 * adapted from Jon L. Bentley and M. Douglas McIlroy's "Engineering a Sort
058 * Function", Software-Practice and Experience, Vol. 23(11) P. 1249-1265
059 * (November 1993). This algorithm offers n*log(n) performance on many data
060 * sets that cause other quicksorts to degrade to quadratic performance.
061 *
062 * @author Original author unknown
063 * @author Bryce McKinlay
064 * @author Eric Blake (ebb9@email.byu.edu)
065 * @see Comparable
066 * @see Comparator
067 * @since 1.2
068 * @status updated to 1.4
069 */
070 public class Arrays
071 {
072 /**
073 * This class is non-instantiable.
074 */
075 private Arrays()
076 {
077 }
078
079
080 // binarySearch
081 /**
082 * Perform a binary search of a byte array for a key. The array must be
083 * sorted (as by the sort() method) - if it is not, the behaviour of this
084 * method is undefined, and may be an infinite loop. If the array contains
085 * the key more than once, any one of them may be found. Note: although the
086 * specification allows for an infinite loop if the array is unsorted, it
087 * will not happen in this implementation.
088 *
089 * @param a the array to search (must be sorted)
090 * @param key the value to search for
091 * @return the index at which the key was found, or -n-1 if it was not
092 * found, where n is the index of the first value higher than key or
093 * a.length if there is no such value.
094 */
095 public static int binarySearch(byte[] a, byte key)
096 {
097 if (a.length == 0)
098 return -1;
099 return binarySearch(a, 0, a.length - 1, key);
100 }
101
102 /**
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.
109 *
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>.
120 */
121 public static int binarySearch(byte[] a, int low, int hi, byte key)
122 {
123 if (low > hi)
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 " +
128 "of bounds.");
129 int mid = 0;
130 while (low <= hi)
131 {
132 mid = (low + hi) >>> 1;
133 final byte d = a[mid];
134 if (d == key)
135 return mid;
136 else if (d > key)
137 hi = mid - 1;
138 else
139 // This gets the insertion point right on the last loop.
140 low = ++mid;
141 }
142 return -mid - 1;
143 }
144
145 /**
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.
152 *
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.
158 */
159 public static int binarySearch(char[] a, char key)
160 {
161 if (a.length == 0)
162 return -1;
163 return binarySearch(a, 0, a.length - 1, key);
164 }
165
166 /**
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.
173 *
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>.
184 */
185 public static int binarySearch(char[] a, int low, int hi, char key)
186 {
187 if (low > hi)
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 " +
192 "of bounds.");
193 int mid = 0;
194 while (low <= hi)
195 {
196 mid = (low + hi) >>> 1;
197 final char d = a[mid];
198 if (d == key)
199 return mid;
200 else if (d > key)
201 hi = mid - 1;
202 else
203 // This gets the insertion point right on the last loop.
204 low = ++mid;
205 }
206 return -mid - 1;
207 }
208
209 /**
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.
216 *
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.
222 */
223 public static int binarySearch(short[] a, short key)
224 {
225 if (a.length == 0)
226 return -1;
227 return binarySearch(a, 0, a.length - 1, key);
228 }
229
230 /**
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.
237 *
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>.
248 */
249 public static int binarySearch(short[] a, int low, int hi, short key)
250 {
251 if (low > hi)
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 " +
256 "of bounds.");
257 int mid = 0;
258 while (low <= hi)
259 {
260 mid = (low + hi) >>> 1;
261 final short d = a[mid];
262 if (d == key)
263 return mid;
264 else if (d > key)
265 hi = mid - 1;
266 else
267 // This gets the insertion point right on the last loop.
268 low = ++mid;
269 }
270 return -mid - 1;
271 }
272
273 /**
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.
280 *
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.
286 */
287 public static int binarySearch(int[] a, int key)
288 {
289 if (a.length == 0)
290 return -1;
291 return binarySearch(a, 0, a.length - 1, key);
292 }
293
294 /**
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.
301 *
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>.
312 */
313 public static int binarySearch(int[] a, int low, int hi, int key)
314 {
315 if (low > hi)
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 " +
320 "of bounds.");
321 int mid = 0;
322 while (low <= hi)
323 {
324 mid = (low + hi) >>> 1;
325 final int d = a[mid];
326 if (d == key)
327 return mid;
328 else if (d > key)
329 hi = mid - 1;
330 else
331 // This gets the insertion point right on the last loop.
332 low = ++mid;
333 }
334 return -mid - 1;
335 }
336
337 /**
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.
344 *
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.
350 */
351 public static int binarySearch(long[] a, long key)
352 {
353 if (a.length == 0)
354 return -1;
355 return binarySearch(a, 0, a.length - 1, key);
356 }
357
358 /**
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.
365 *
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>.
376 */
377 public static int binarySearch(long[] a, int low, int hi, long key)
378 {
379 if (low > hi)
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 " +
384 "of bounds.");
385 int mid = 0;
386 while (low <= hi)
387 {
388 mid = (low + hi) >>> 1;
389 final long d = a[mid];
390 if (d == key)
391 return mid;
392 else if (d > key)
393 hi = mid - 1;
394 else
395 // This gets the insertion point right on the last loop.
396 low = ++mid;
397 }
398 return -mid - 1;
399 }
400
401 /**
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.
408 *
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.
414 */
415 public static int binarySearch(float[] a, float key)
416 {
417 if (a.length == 0)
418 return -1;
419 return binarySearch(a, 0, a.length - 1, key);
420 }
421
422 /**
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.
429 *
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>.
440 */
441 public static int binarySearch(float[] a, int low, int hi, float key)
442 {
443 if (low > hi)
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 " +
448 "of bounds.");
449 // Must use Float.compare to take into account NaN, +-0.
450 int mid = 0;
451 while (low <= hi)
452 {
453 mid = (low + hi) >>> 1;
454 final int r = Float.compare(a[mid], key);
455 if (r == 0)
456 return mid;
457 else if (r > 0)
458 hi = mid - 1;
459 else
460 // This gets the insertion point right on the last loop
461 low = ++mid;
462 }
463 return -mid - 1;
464 }
465
466 /**
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.
473 *
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.
479 */
480 public static int binarySearch(double[] a, double key)
481 {
482 if (a.length == 0)
483 return -1;
484 return binarySearch(a, 0, a.length - 1, key);
485 }
486
487 /**
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.
494 *
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>.
505 */
506 public static int binarySearch(double[] a, int low, int hi, double key)
507 {
508 if (low > hi)
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 " +
513 "of bounds.");
514 // Must use Double.compare to take into account NaN, +-0.
515 int mid = 0;
516 while (low <= hi)
517 {
518 mid = (low + hi) >>> 1;
519 final int r = Double.compare(a[mid], key);
520 if (r == 0)
521 return mid;
522 else if (r > 0)
523 hi = mid - 1;
524 else
525 // This gets the insertion point right on the last loop
526 low = ++mid;
527 }
528 return -mid - 1;
529 }
530
531 /**
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)
539 * implementation.
540 *
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
547 * elements of a
548 * @throws NullPointerException if a null element in a is compared
549 */
550 public static int binarySearch(Object[] a, Object key)
551 {
552 if (a.length == 0)
553 return -1;
554 return binarySearch(a, key, null);
555 }
556
557 /**
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.
564 *
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.
572 */
573 public static int binarySearch(Object[] a, int low, int hi, Object key)
574 {
575 return binarySearch(a, low, hi, key, null);
576 }
577
578 /**
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.
587 *
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
596 * elements of a
597 * @throws NullPointerException if a null element is compared with natural
598 * ordering (only possible when c is null)
599 */
600 public static <T> int binarySearch(T[] a, T key, Comparator<? super T> c)
601 {
602 if (a.length == 0)
603 return -1;
604 return binarySearch(a, 0, a.length - 1, key, c);
605 }
606
607 /**
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.
615 *
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
626 * elements of a
627 * @throws IllegalArgumentException if <code>low > hi</code>
628 * @throws ArrayIndexOutOfBoundsException if <code>low < 0</code> or
629 * <code>hi > a.length</code>.
630 */
631 public static <T> int binarySearch(T[] a, int low, int hi, T key,
632 Comparator<? super T> c)
633 {
634 if (low > hi)
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 " +
639 "of bounds.");
640 int mid = 0;
641 while (low <= hi)
642 {
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);
648 if (d == 0)
649 return mid;
650 else if (d > 0)
651 hi = mid - 1;
652 else
653 // This gets the insertion point right on the last loop
654 low = ++mid;
655 }
656 return -mid - 1;
657 }
658
659
660 // equals
661 /**
662 * Compare two boolean arrays for equality.
663 *
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]
668 */
669 public static boolean equals(boolean[] a1, boolean[] a2)
670 {
671 // Quick test which saves comparing elements of the same array, and also
672 // catches the case that both are null.
673 if (a1 == a2)
674 return true;
675
676 if (null == a1 || null == a2)
677 return false;
678
679 // If they're the same length, test each element
680 if (a1.length == a2.length)
681 {
682 int i = a1.length;
683 while (--i >= 0)
684 if (a1[i] != a2[i])
685 return false;
686 return true;
687 }
688 return false;
689 }
690
691 /**
692 * Compare two byte arrays for equality.
693 *
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]
698 */
699 public static boolean equals(byte[] a1, byte[] a2)
700 {
701 // Quick test which saves comparing elements of the same array, and also
702 // catches the case that both are null.
703 if (a1 == a2)
704 return true;
705
706 if (null == a1 || null == a2)
707 return false;
708
709 // If they're the same length, test each element
710 if (a1.length == a2.length)
711 {
712 int i = a1.length;
713 while (--i >= 0)
714 if (a1[i] != a2[i])
715 return false;
716 return true;
717 }
718 return false;
719 }
720
721 /**
722 * Compare two char arrays for equality.
723 *
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]
728 */
729 public static boolean equals(char[] a1, char[] a2)
730 {
731 // Quick test which saves comparing elements of the same array, and also
732 // catches the case that both are null.
733 if (a1 == a2)
734 return true;
735
736 if (null == a1 || null == a2)
737 return false;
738
739 // If they're the same length, test each element
740 if (a1.length == a2.length)
741 {
742 int i = a1.length;
743 while (--i >= 0)
744 if (a1[i] != a2[i])
745 return false;
746 return true;
747 }
748 return false;
749 }
750
751 /**
752 * Compare two short arrays for equality.
753 *
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]
758 */
759 public static boolean equals(short[] a1, short[] a2)
760 {
761 // Quick test which saves comparing elements of the same array, and also
762 // catches the case that both are null.
763 if (a1 == a2)
764 return true;
765
766 if (null == a1 || null == a2)
767 return false;
768
769 // If they're the same length, test each element
770 if (a1.length == a2.length)
771 {
772 int i = a1.length;
773 while (--i >= 0)
774 if (a1[i] != a2[i])
775 return false;
776 return true;
777 }
778 return false;
779 }
780
781 /**
782 * Compare two int arrays for equality.
783 *
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]
788 */
789 public static boolean equals(int[] a1, int[] a2)
790 {
791 // Quick test which saves comparing elements of the same array, and also
792 // catches the case that both are null.
793 if (a1 == a2)
794 return true;
795
796 if (null == a1 || null == a2)
797 return false;
798
799 // If they're the same length, test each element
800 if (a1.length == a2.length)
801 {
802 int i = a1.length;
803 while (--i >= 0)
804 if (a1[i] != a2[i])
805 return false;
806 return true;
807 }
808 return false;
809 }
810
811 /**
812 * Compare two long arrays for equality.
813 *
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]
818 */
819 public static boolean equals(long[] a1, long[] a2)
820 {
821 // Quick test which saves comparing elements of the same array, and also
822 // catches the case that both are null.
823 if (a1 == a2)
824 return true;
825
826 if (null == a1 || null == a2)
827 return false;
828
829 // If they're the same length, test each element
830 if (a1.length == a2.length)
831 {
832 int i = a1.length;
833 while (--i >= 0)
834 if (a1[i] != a2[i])
835 return false;
836 return true;
837 }
838 return false;
839 }
840
841 /**
842 * Compare two float arrays for equality.
843 *
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]
848 */
849 public static boolean equals(float[] a1, float[] a2)
850 {
851 // Quick test which saves comparing elements of the same array, and also
852 // catches the case that both are null.
853 if (a1 == a2)
854 return true;
855
856 if (null == a1 || null == a2)
857 return false;
858
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)
862 {
863 int i = a1.length;
864 while (--i >= 0)
865 if (Float.compare(a1[i], a2[i]) != 0)
866 return false;
867 return true;
868 }
869 return false;
870 }
871
872 /**
873 * Compare two double arrays for equality.
874 *
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]
879 */
880 public static boolean equals(double[] a1, double[] a2)
881 {
882 // Quick test which saves comparing elements of the same array, and also
883 // catches the case that both are null.
884 if (a1 == a2)
885 return true;
886
887 if (null == a1 || null == a2)
888 return false;
889
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)
893 {
894 int i = a1.length;
895 while (--i >= 0)
896 if (Double.compare(a1[i], a2[i]) != 0)
897 return false;
898 return true;
899 }
900 return false;
901 }
902
903 /**
904 * Compare two Object arrays for equality.
905 *
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]).
911 */
912 public static boolean equals(Object[] a1, Object[] a2)
913 {
914 // Quick test which saves comparing elements of the same array, and also
915 // catches the case that both are null.
916 if (a1 == a2)
917 return true;
918
919 if (null == a1 || null == a2)
920 return false;
921
922 // If they're the same length, test each element
923 if (a1.length == a2.length)
924 {
925 int i = a1.length;
926 while (--i >= 0)
927 if (! AbstractCollection.equals(a1[i], a2[i]))
928 return false;
929 return true;
930 }
931 return false;
932 }
933
934
935 // fill
936 /**
937 * Fill an array with a boolean value.
938 *
939 * @param a the array to fill
940 * @param val the value to fill it with
941 */
942 public static void fill(boolean[] a, boolean val)
943 {
944 fill(a, 0, a.length, val);
945 }
946
947 /**
948 * Fill a range of an array with a boolean value.
949 *
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
957 */
958 public static void fill(boolean[] a, int fromIndex, int toIndex, boolean val)
959 {
960 if (fromIndex > toIndex)
961 throw new IllegalArgumentException();
962 for (int i = fromIndex; i < toIndex; i++)
963 a[i] = val;
964 }
965
966 /**
967 * Fill an array with a byte value.
968 *
969 * @param a the array to fill
970 * @param val the value to fill it with
971 */
972 public static void fill(byte[] a, byte val)
973 {
974 fill(a, 0, a.length, val);
975 }
976
977 /**
978 * Fill a range of an array with a byte value.
979 *
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
987 */
988 public static void fill(byte[] a, int fromIndex, int toIndex, byte val)
989 {
990 if (fromIndex > toIndex)
991 throw new IllegalArgumentException();
992 for (int i = fromIndex; i < toIndex; i++)
993 a[i] = val;
994 }
995
996 /**
997 * Fill an array with a char value.
998 *
999 * @param a the array to fill
1000 * @param val the value to fill it with
1001 */
1002 public static void fill(char[] a, char val)
1003 {
1004 fill(a, 0, a.length, val);
1005 }
1006
1007 /**
1008 * Fill a range of an array with a char value.
1009 *
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
1017 */
1018 public static void fill(char[] a, int fromIndex, int toIndex, char val)
1019 {
1020 if (fromIndex > toIndex)
1021 throw new IllegalArgumentException();
1022 for (int i = fromIndex; i < toIndex; i++)
1023 a[i] = val;
1024 }
1025
1026 /**
1027 * Fill an array with a short value.
1028 *
1029 * @param a the array to fill
1030 * @param val the value to fill it with
1031 */
1032 public static void fill(short[] a, short val)
1033 {
1034 fill(a, 0, a.length, val);
1035 }
1036
1037 /**
1038 * Fill a range of an array with a short value.
1039 *
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
1047 */
1048 public static void fill(short[] a, int fromIndex, int toIndex, short val)
1049 {
1050 if (fromIndex > toIndex)
1051 throw new IllegalArgumentException();
1052 for (int i = fromIndex; i < toIndex; i++)
1053 a[i] = val;
1054 }
1055
1056 /**
1057 * Fill an array with an int value.
1058 *
1059 * @param a the array to fill
1060 * @param val the value to fill it with
1061 */
1062 public static void fill(int[] a, int val)
1063 {
1064 fill(a, 0, a.length, val);
1065 }
1066
1067 /**
1068 * Fill a range of an array with an int value.
1069 *
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
1077 */
1078 public static void fill(int[] a, int fromIndex, int toIndex, int val)
1079 {
1080 if (fromIndex > toIndex)
1081 throw new IllegalArgumentException();
1082 for (int i = fromIndex; i < toIndex; i++)
1083 a[i] = val;
1084 }
1085
1086 /**
1087 * Fill an array with a long value.
1088 *
1089 * @param a the array to fill
1090 * @param val the value to fill it with
1091 */
1092 public static void fill(long[] a, long val)
1093 {
1094 fill(a, 0, a.length, val);
1095 }
1096
1097 /**
1098 * Fill a range of an array with a long value.
1099 *
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
1107 */
1108 public static void fill(long[] a, int fromIndex, int toIndex, long val)
1109 {
1110 if (fromIndex > toIndex)
1111 throw new IllegalArgumentException();
1112 for (int i = fromIndex; i < toIndex; i++)
1113 a[i] = val;
1114 }
1115
1116 /**
1117 * Fill an array with a float value.
1118 *
1119 * @param a the array to fill
1120 * @param val the value to fill it with
1121 */
1122 public static void fill(float[] a, float val)
1123 {
1124 fill(a, 0, a.length, val);
1125 }
1126
1127 /**
1128 * Fill a range of an array with a float value.
1129 *
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
1137 */
1138 public static void fill(float[] a, int fromIndex, int toIndex, float val)
1139 {
1140 if (fromIndex > toIndex)
1141 throw new IllegalArgumentException();
1142 for (int i = fromIndex; i < toIndex; i++)
1143 a[i] = val;
1144 }
1145
1146 /**
1147 * Fill an array with a double value.
1148 *
1149 * @param a the array to fill
1150 * @param val the value to fill it with
1151 */
1152 public static void fill(double[] a, double val)
1153 {
1154 fill(a, 0, a.length, val);
1155 }
1156
1157 /**
1158 * Fill a range of an array with a double value.
1159 *
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
1167 */
1168 public static void fill(double[] a, int fromIndex, int toIndex, double val)
1169 {
1170 if (fromIndex > toIndex)
1171 throw new IllegalArgumentException();
1172 for (int i = fromIndex; i < toIndex; i++)
1173 a[i] = val;
1174 }
1175
1176 /**
1177 * Fill an array with an Object value.
1178 *
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
1182 * type of a.
1183 */
1184 public static void fill(Object[] a, Object val)
1185 {
1186 fill(a, 0, a.length, val);
1187 }
1188
1189 /**
1190 * Fill a range of an array with an Object value.
1191 *
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
1197 * type of a.
1198 * @throws IllegalArgumentException if fromIndex > toIndex
1199 * @throws ArrayIndexOutOfBoundsException if fromIndex < 0
1200 * || toIndex > a.length
1201 */
1202 public static void fill(Object[] a, int fromIndex, int toIndex, Object val)
1203 {
1204 if (fromIndex > toIndex)
1205 throw new IllegalArgumentException();
1206 for (int i = fromIndex; i < toIndex; i++)
1207 a[i] = val;
1208 }
1209
1210
1211 // sort
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
1218 // quicksort.
1219
1220 /**
1221 * Performs a stable sort on the elements, arranging them according to their
1222 * natural order.
1223 *
1224 * @param a the byte array to sort
1225 */
1226 public static void sort(byte[] a)
1227 {
1228 qsort(a, 0, a.length);
1229 }
1230
1231 /**
1232 * Performs a stable sort on the elements, arranging them according to their
1233 * natural order.
1234 *
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
1241 */
1242 public static void sort(byte[] a, int fromIndex, int toIndex)
1243 {
1244 if (fromIndex > toIndex)
1245 throw new IllegalArgumentException();
1246 if (fromIndex < 0)
1247 throw new ArrayIndexOutOfBoundsException();
1248 qsort(a, fromIndex, toIndex - fromIndex);
1249 }
1250
1251 /**
1252 * Finds the index of the median of three array elements.
1253 *
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
1259 */
1260 private static int med3(int a, int b, int c, byte[] d)
1261 {
1262 return (d[a] < d[b]
1263 ? (d[b] < d[c] ? b : d[a] < d[c] ? c : a)
1264 : (d[b] > d[c] ? b : d[a] > d[c] ? c : a));
1265 }
1266
1267 /**
1268 * Swaps the elements at two locations of an array
1269 *
1270 * @param i the first index
1271 * @param j the second index
1272 * @param a the array
1273 */
1274 private static void swap(int i, int j, byte[] a)
1275 {
1276 byte c = a[i];
1277 a[i] = a[j];
1278 a[j] = c;
1279 }
1280
1281 /**
1282 * Swaps two ranges of an array.
1283 *
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
1288 */
1289 private static void vecswap(int i, int j, int n, byte[] a)
1290 {
1291 for ( ; n > 0; i++, j++, n--)
1292 swap(i, j, a);
1293 }
1294
1295 /**
1296 * Performs a recursive modified quicksort.
1297 *
1298 * @param array the array to sort
1299 * @param from the start index (inclusive)
1300 * @param count the number of elements to sort
1301 */
1302 private static void qsort(byte[] array, int from, int count)
1303 {
1304 // Use an insertion sort on small arrays.
1305 if (count <= 7)
1306 {
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);
1310 return;
1311 }
1312
1313 // Determine a good median element.
1314 int mid = from + count / 2;
1315 int lo = from;
1316 int hi = from + count - 1;
1317
1318 if (count > 40)
1319 { // big arrays, pseudomedian of 9
1320 int s = count / 8;
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);
1324 }
1325 mid = med3(lo, mid, hi, array);
1326
1327 int a, b, c, d;
1328 int comp;
1329
1330 // Pull the median element out of the fray, and use it as a pivot.
1331 swap(from, mid, array);
1332 a = b = from;
1333 c = d = from + count - 1;
1334
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.
1339 while (true)
1340 {
1341 while (b <= c && (comp = array[b] - array[from]) <= 0)
1342 {
1343 if (comp == 0)
1344 {
1345 swap(a, b, array);
1346 a++;
1347 }
1348 b++;
1349 }
1350 while (c >= b && (comp = array[c] - array[from]) >= 0)
1351 {
1352 if (comp == 0)
1353 {
1354 swap(c, d, array);
1355 d--;
1356 }
1357 c--;
1358 }
1359 if (b > c)
1360 break;
1361 swap(b, c, array);
1362 b++;
1363 c--;
1364 }
1365
1366 // Swap pivot(s) back in place, the recurse on left and right sections.
1367 hi = from + count;
1368 int span;
1369 span = Math.min(a - from, b - a);
1370 vecswap(from, b - span, span, array);
1371
1372 span = Math.min(d - c, hi - d - 1);
1373 vecswap(b, hi - span, span, array);
1374
1375 span = b - a;
1376 if (span > 1)
1377 qsort(array, from, span);
1378
1379 span = d - c;
1380 if (span > 1)
1381 qsort(array, hi - span, span);
1382 }
1383
1384 /**
1385 * Performs a stable sort on the elements, arranging them according to their
1386 * natural order.
1387 *
1388 * @param a the char array to sort
1389 */
1390 public static void sort(char[] a)
1391 {
1392 qsort(a, 0, a.length);
1393 }
1394
1395 /**
1396 * Performs a stable sort on the elements, arranging them according to their
1397 * natural order.
1398 *
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
1405 */
1406 public static void sort(char[] a, int fromIndex, int toIndex)
1407 {
1408 if (fromIndex > toIndex)
1409 throw new IllegalArgumentException();
1410 if (fromIndex < 0)
1411 throw new ArrayIndexOutOfBoundsException();
1412 qsort(a, fromIndex, toIndex - fromIndex);
1413 }
1414
1415 /**
1416 * Finds the index of the median of three array elements.
1417 *
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
1423 */
1424 private static int med3(int a, int b, int c, char[] d)
1425 {
1426 return (d[a] < d[b]
1427 ? (d[b] < d[c] ? b : d[a] < d[c] ? c : a)
1428 : (d[b] > d[c] ? b : d[a] > d[c] ? c : a));
1429 }
1430
1431 /**
1432 * Swaps the elements at two locations of an array
1433 *
1434 * @param i the first index
1435 * @param j the second index
1436 * @param a the array
1437 */
1438 private static void swap(int i, int j, char[] a)
1439 {
1440 char c = a[i];
1441 a[i] = a[j];
1442 a[j] = c;
1443 }
1444
1445 /**
1446 * Swaps two ranges of an array.
1447 *
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
1452 */
1453 private static void vecswap(int i, int j, int n, char[] a)
1454 {
1455 for ( ; n > 0; i++, j++, n--)
1456 swap(i, j, a);
1457 }
1458
1459 /**
1460 * Performs a recursive modified quicksort.
1461 *
1462 * @param array the array to sort
1463 * @param from the start index (inclusive)
1464 * @param count the number of elements to sort
1465 */
1466 private static void qsort(char[] array, int from, int count)
1467 {
1468 // Use an insertion sort on small arrays.
1469 if (count <= 7)
1470 {
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);
1474 return;
1475 }
1476
1477 // Determine a good median element.
1478 int mid = from + count / 2;
1479 int lo = from;
1480 int hi = from + count - 1;
1481
1482 if (count > 40)
1483 { // big arrays, pseudomedian of 9
1484 int s = count / 8;
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);
1488 }
1489 mid = med3(lo, mid, hi, array);
1490
1491 int a, b, c, d;
1492 int comp;
1493
1494 // Pull the median element out of the fray, and use it as a pivot.
1495 swap(from, mid, array);
1496 a = b = from;
1497 c = d = from + count - 1;
1498
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.
1503 while (true)
1504 {
1505 while (b <= c && (comp = array[b] - array[from]) <= 0)
1506 {
1507 if (comp == 0)
1508 {
1509 swap(a, b, array);
1510 a++;
1511 }
1512 b++;
1513 }
1514 while (c >= b && (comp = array[c] - array[from]) >= 0)
1515 {
1516 if (comp == 0)
1517 {
1518 swap(c, d, array);
1519 d--;
1520 }
1521 c--;
1522 }
1523 if (b > c)
1524 break;
1525 swap(b, c, array);
1526 b++;
1527 c--;
1528 }
1529
1530 // Swap pivot(s) back in place, the recurse on left and right sections.
1531 hi = from + count;
1532 int span;
1533 span = Math.min(a - from, b - a);
1534 vecswap(from, b - span, span, array);
1535
1536 span = Math.min(d - c, hi - d - 1);
1537 vecswap(b, hi - span, span, array);
1538
1539 span = b - a;
1540 if (span > 1)
1541 qsort(array, from, span);
1542
1543 span = d - c;
1544 if (span > 1)
1545 qsort(array, hi - span, span);
1546 }
1547
1548 /**
1549 * Performs a stable sort on the elements, arranging them according to their
1550 * natural order.
1551 *
1552 * @param a the short array to sort
1553 */
1554 public static void sort(short[] a)
1555 {
1556 qsort(a, 0, a.length);
1557 }
1558
1559 /**
1560 * Performs a stable sort on the elements, arranging them according to their
1561 * natural order.
1562 *
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
1569 */
1570 public static void sort(short[] a, int fromIndex, int toIndex)
1571 {
1572 if (fromIndex > toIndex)
1573 throw new IllegalArgumentException();
1574 if (fromIndex < 0)
1575 throw new ArrayIndexOutOfBoundsException();
1576 qsort(a, fromIndex, toIndex - fromIndex);
1577 }
1578
1579 /**
1580 * Finds the index of the median of three array elements.
1581 *
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
1587 */
1588 private static int med3(int a, int b, int c, short[] d)
1589 {
1590 return (d[a] < d[b]
1591 ? (d[b] < d[c] ? b : d[a] < d[c] ? c : a)
1592 : (d[b] > d[c] ? b : d[a] > d[c] ? c : a));
1593 }
1594
1595 /**
1596 * Swaps the elements at two locations of an array
1597 *
1598 * @param i the first index
1599 * @param j the second index
1600 * @param a the array
1601 */
1602 private static void swap(int i, int j, short[] a)
1603 {
1604 short c = a[i];
1605 a[i] = a[j];
1606 a[j] = c;
1607 }
1608
1609 /**
1610 * Swaps two ranges of an array.
1611 *
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
1616 */
1617 private static void vecswap(int i, int j, int n, short[] a)
1618 {
1619 for ( ; n > 0; i++, j++, n--)
1620 swap(i, j, a);
1621 }
1622
1623 /**
1624 * Performs a recursive modified quicksort.
1625 *
1626 * @param array the array to sort
1627 * @param from the start index (inclusive)
1628 * @param count the number of elements to sort
1629 */
1630 private static void qsort(short[] array, int from, int count)
1631 {
1632 // Use an insertion sort on small arrays.
1633 if (count <= 7)
1634 {
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);
1638 return;
1639 }
1640
1641 // Determine a good median element.
1642 int mid = from + count / 2;
1643 int lo = from;
1644 int hi = from + count - 1;
1645
1646 if (count > 40)
1647 { // big arrays, pseudomedian of 9
1648 int s = count / 8;
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);
1652 }
1653 mid = med3(lo, mid, hi, array);
1654
1655 int a, b, c, d;
1656 int comp;
1657
1658 // Pull the median element out of the fray, and use it as a pivot.
1659 swap(from, mid, array);
1660 a = b = from;
1661 c = d = from + count - 1;
1662
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.
1667 while (true)
1668 {
1669 while (b <= c && (comp = array[b] - array[from]) <= 0)
1670 {
1671 if (comp == 0)
1672 {
1673 swap(a, b, array);
1674 a++;
1675 }
1676 b++;
1677 }
1678 while (c >= b && (comp = array[c] - array[from]) >= 0)
1679 {
1680 if (comp == 0)
1681 {
1682 swap(c, d, array);
1683 d--;
1684 }
1685 c--;
1686 }
1687 if (b > c)
1688 break;
1689 swap(b, c, array);
1690 b++;
1691 c--;
1692 }
1693
1694 // Swap pivot(s) back in place, the recurse on left and right sections.
1695 hi = from + count;
1696 int span;
1697 span = Math.min(a - from, b - a);
1698 vecswap(from, b - span, span, array);
1699
1700 span = Math.min(d - c, hi - d - 1);
1701 vecswap(b, hi - span, span, array);
1702
1703 span = b - a;
1704 if (span > 1)
1705 qsort(array, from, span);
1706
1707 span = d - c;
1708 if (span > 1)
1709 qsort(array, hi - span, span);
1710 }
1711
1712 /**
1713 * Performs a stable sort on the elements, arranging them according to their
1714 * natural order.
1715 *
1716 * @param a the int array to sort
1717 */
1718 public static void sort(int[] a)
1719 {
1720 qsort(a, 0, a.length);
1721 }
1722
1723 /**
1724 * Performs a stable sort on the elements, arranging them according to their
1725 * natural order.
1726 *
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
1733 */
1734 public static void sort(int[] a, int fromIndex, int toIndex)
1735 {
1736 if (fromIndex > toIndex)
1737 throw new IllegalArgumentException();
1738 if (fromIndex < 0)
1739 throw new ArrayIndexOutOfBoundsException();
1740 qsort(a, fromIndex, toIndex - fromIndex);
1741 }
1742
1743 /**
1744 * Finds the index of the median of three array elements.
1745 *
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
1751 */
1752 private static int med3(int a, int b, int c, int[] d)
1753 {
1754 return (d[a] < d[b]
1755 ? (d[b] < d[c] ? b : d[a] < d[c] ? c : a)
1756 : (d[b] > d[c] ? b : d[a] > d[c] ? c : a));
1757 }
1758
1759 /**
1760 * Swaps the elements at two locations of an array
1761 *
1762 * @param i the first index
1763 * @param j the second index
1764 * @param a the array
1765 */
1766 private static void swap(int i, int j, int[] a)
1767 {
1768 int c = a[i];
1769 a[i] = a[j];
1770 a[j] = c;
1771 }
1772
1773 /**
1774 * Swaps two ranges of an array.
1775 *
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
1780 */
1781 private static void vecswap(int i, int j, int n, int[] a)
1782 {
1783 for ( ; n > 0; i++, j++, n--)
1784 swap(i, j, a);
1785 }
1786
1787 /**
1788 * Compares two integers in natural order, since a - b is inadequate.
1789 *
1790 * @param a the first int
1791 * @param b the second int
1792 * @return < 0, 0, or > 0 accorting to the comparison
1793 */
1794 private static int compare(int a, int b)
1795 {
1796 return a < b ? -1 : a == b ? 0 : 1;
1797 }
1798
1799 /**
1800 * Performs a recursive modified quicksort.
1801 *
1802 * @param array the array to sort
1803 * @param from the start index (inclusive)
1804 * @param count the number of elements to sort
1805 */
1806 private static void qsort(int[] array, int from, int count)
1807 {
1808 // Use an insertion sort on small arrays.
1809 if (count <= 7)
1810 {
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);
1814 return;
1815 }
1816
1817 // Determine a good median element.
1818 int mid = from + count / 2;
1819 int lo = from;
1820 int hi = from + count - 1;
1821
1822 if (count > 40)
1823 { // big arrays, pseudomedian of 9
1824 int s = count / 8;
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);
1828 }
1829 mid = med3(lo, mid, hi, array);
1830
1831 int a, b, c, d;
1832 int comp;
1833
1834 // Pull the median element out of the fray, and use it as a pivot.
1835 swap(from, mid, array);
1836 a = b = from;
1837 c = d = from + count - 1;
1838
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.
1843 while (true)
1844 {
1845 while (b <= c && (comp = compare(array[b], array[from])) <= 0)
1846 {
1847 if (comp == 0)
1848 {
1849 swap(a, b, array);
1850 a++;
1851 }
1852 b++;
1853 }
1854 while (c >= b && (comp = compare(array[c], array[from])) >= 0)
1855 {
1856 if (comp == 0)
1857 {
1858 swap(c, d, array);
1859 d--;
1860 }
1861 c--;
1862 }
1863 if (b > c)
1864 break;
1865 swap(b, c, array);
1866 b++;
1867 c--;
1868 }
1869
1870 // Swap pivot(s) back in place, the recurse on left and right sections.
1871 hi = from + count;
1872 int span;
1873 span = Math.min(a - from, b - a);
1874 vecswap(from, b - span, span, array);
1875
1876 span = Math.min(d - c, hi - d - 1);
1877 vecswap(b, hi - span, span, array);
1878
1879 span = b - a;
1880 if (span > 1)
1881 qsort(array, from, span);
1882
1883 span = d - c;
1884 if (span > 1)
1885 qsort(array, hi - span, span);
1886 }
1887
1888 /**
1889 * Performs a stable sort on the elements, arranging them according to their
1890 * natural order.
1891 *
1892 * @param a the long array to sort
1893 */
1894 public static void sort(long[] a)
1895 {
1896 qsort(a, 0, a.length);
1897 }
1898
1899 /**
1900 * Performs a stable sort on the elements, arranging them according to their
1901 * natural order.
1902 *
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
1909 */
1910 public static void sort(long[] a, int fromIndex, int toIndex)
1911 {
1912 if (fromIndex > toIndex)
1913 throw new IllegalArgumentException();
1914 if (fromIndex < 0)
1915 throw new ArrayIndexOutOfBoundsException();
1916 qsort(a, fromIndex, toIndex - fromIndex);
1917 }
1918
1919 /**
1920 * Finds the index of the median of three array elements.
1921 *
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
1927 */
1928 private static int med3(int a, int b, int c, long[] d)
1929 {
1930 return (d[a] < d[b]
1931 ? (d[b] < d[c] ? b : d[a] < d[c] ? c : a)
1932 : (d[b] > d[c] ? b : d[a] > d[c] ? c : a));
1933 }
1934
1935 /**
1936 * Swaps the elements at two locations of an array
1937 *
1938 * @param i the first index
1939 * @param j the second index
1940 * @param a the array
1941 */
1942 private static void swap(int i, int j, long[] a)
1943 {
1944 long c = a[i];
1945 a[i] = a[j];
1946 a[j] = c;
1947 }
1948
1949 /**
1950 * Swaps two ranges of an array.
1951 *
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
1956 */
1957 private static void vecswap(int i, int j, int n, long[] a)
1958 {
1959 for ( ; n > 0; i++, j++, n--)
1960 swap(i, j, a);
1961 }
1962
1963 /**
1964 * Compares two longs in natural order, since a - b is inadequate.
1965 *
1966 * @param a the first long
1967 * @param b the second long
1968 * @return < 0, 0, or > 0 accorting to the comparison
1969 */
1970 private static int compare(long a, long b)
1971 {
1972 return a < b ? -1 : a == b ? 0 : 1;
1973 }
1974
1975 /**
1976 * Performs a recursive modified quicksort.
1977 *
1978 * @param array the array to sort
1979 * @param from the start index (inclusive)
1980 * @param count the number of elements to sort
1981 */
1982 private static void qsort(long[] array, int from, int count)
1983 {
1984 // Use an insertion sort on small arrays.
1985 if (count <= 7)
1986 {
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);
1990 return;
1991 }
1992
1993 // Determine a good median element.
1994 int mid = from + count / 2;
1995 int lo = from;
1996 int hi = from + count - 1;
1997
1998 if (count > 40)
1999 { // big arrays, pseudomedian of 9
2000 int s = count / 8;
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);
2004 }
2005 mid = med3(lo, mid, hi, array);
2006
2007 int a, b, c, d;
2008 int comp;
2009
2010 // Pull the median element out of the fray, and use it as a pivot.
2011 swap(from, mid, array);
2012 a = b = from;
2013 c = d = from + count - 1;
2014
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.
2019 while (true)
2020 {
2021 while (b <= c && (comp = compare(array[b], array[from])) <= 0)
2022 {
2023 if (comp == 0)
2024 {
2025 swap(a, b, array);
2026 a++;
2027 }
2028 b++;
2029 }
2030 while (c >= b && (comp = compare(array[c], array[from])) >= 0)
2031 {
2032 if (comp == 0)
2033 {
2034 swap(c, d, array);
2035 d--;
2036 }
2037 c--;
2038 }
2039 if (b > c)
2040 break;
2041 swap(b, c, array);
2042 b++;
2043 c--;
2044 }
2045
2046 // Swap pivot(s) back in place, the recurse on left and right sections.
2047 hi = from + count;
2048 int span;
2049 span = Math.min(a - from, b - a);
2050 vecswap(from, b - span, span, array);
2051
2052 span = Math.min(d - c, hi - d - 1);
2053 vecswap(b, hi - span, span, array);
2054
2055 span = b - a;
2056 if (span > 1)
2057 qsort(array, from, span);
2058
2059 span = d - c;
2060 if (span > 1)
2061 qsort(array, hi - span, span);
2062 }
2063
2064 /**
2065 * Performs a stable sort on the elements, arranging them according to their
2066 * natural order.
2067 *
2068 * @param a the float array to sort
2069 */
2070 public static void sort(float[] a)
2071 {
2072 qsort(a, 0, a.length);
2073 }
2074
2075 /**
2076 * Performs a stable sort on the elements, arranging them according to their
2077 * natural order.
2078 *
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
2085 */
2086 public static void sort(float[] a, int fromIndex, int toIndex)
2087 {
2088 if (fromIndex > toIndex)
2089 throw new IllegalArgumentException();
2090 if (fromIndex < 0)
2091 throw new ArrayIndexOutOfBoundsException();
2092 qsort(a, fromIndex, toIndex - fromIndex);
2093 }
2094
2095 /**
2096 * Finds the index of the median of three array elements.
2097 *
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
2103 */
2104 private static int med3(int a, int b, int c, float[] d)
2105 {
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));
2111 }
2112
2113 /**
2114 * Swaps the elements at two locations of an array
2115 *
2116 * @param i the first index
2117 * @param j the second index
2118 * @param a the array
2119 */
2120 private static void swap(int i, int j, float[] a)
2121 {
2122 float c = a[i];
2123 a[i] = a[j];
2124 a[j] = c;
2125 }
2126
2127 /**
2128 * Swaps two ranges of an array.
2129 *
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
2134 */
2135 private static void vecswap(int i, int j, int n, float[] a)
2136 {
2137 for ( ; n > 0; i++, j++, n--)
2138 swap(i, j, a);
2139 }
2140
2141 /**
2142 * Performs a recursive modified quicksort.
2143 *
2144 * @param array the array to sort
2145 * @param from the start index (inclusive)
2146 * @param count the number of elements to sort
2147 */
2148 private static void qsort(float[] array, int from, int count)
2149 {
2150 // Use an insertion sort on small arrays.
2151 if (count <= 7)
2152 {
2153 for (int i = from + 1; i < from + count; i++)
2154 for (int j = i;
2155 j > from && Float.compare(array[j - 1], array[j]) > 0;
2156 j--)
2157 {
2158 swap(j, j - 1, array);
2159 }
2160 return;
2161 }
2162
2163 // Determine a good median element.
2164 int mid = from + count / 2;
2165 int lo = from;
2166 int hi = from + count - 1;
2167
2168 if (count > 40)
2169 { // big arrays, pseudomedian of 9
2170 int s = count / 8;
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);
2174 }
2175 mid = med3(lo, mid, hi, array);
2176
2177 int a, b, c, d;
2178 int comp;
2179
2180 // Pull the median element out of the fray, and use it as a pivot.
2181 swap(from, mid, array);
2182 a = b = from;
2183 c = d = from + count - 1;
2184
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.
2189 while (true)
2190 {
2191 while (b <= c && (comp = Float.compare(array[b], array[from])) <= 0)
2192 {
2193 if (comp == 0)
2194 {
2195 swap(a, b, array);
2196 a++;
2197 }
2198 b++;
2199 }
2200 while (c >= b && (comp = Float.compare(array[c], array[from])) >= 0)
2201 {
2202 if (comp == 0)
2203 {
2204 swap(c, d, array);
2205 d--;
2206 }
2207 c--;
2208 }
2209 if (b > c)
2210 break;
2211 swap(b, c, array);
2212 b++;
2213 c--;
2214 }
2215
2216 // Swap pivot(s) back in place, the recurse on left and right sections.
2217 hi = from + count;
2218 int span;
2219 span = Math.min(a - from, b - a);
2220 vecswap(from, b - span, span, array);
2221
2222 span = Math.min(d - c, hi - d - 1);
2223 vecswap(b, hi - span, span, array);
2224
2225 span = b - a;
2226 if (span > 1)
2227 qsort(array, from, span);
2228
2229 span = d - c;
2230 if (span > 1)
2231 qsort(array, hi - span, span);
2232 }
2233
2234 /**
2235 * Performs a stable sort on the elements, arranging them according to their
2236 * natural order.
2237 *
2238 * @param a the double array to sort
2239 */
2240 public static void sort(double[] a)
2241 {
2242 qsort(a, 0, a.length);
2243 }
2244
2245 /**
2246 * Performs a stable sort on the elements, arranging them according to their
2247 * natural order.
2248 *
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
2255 */
2256 public static void sort(double[] a, int fromIndex, int toIndex)
2257 {
2258 if (fromIndex > toIndex)
2259 throw new IllegalArgumentException();
2260 if (fromIndex < 0)
2261 throw new ArrayIndexOutOfBoundsException();
2262 qsort(a, fromIndex, toIndex - fromIndex);
2263 }
2264
2265 /**
2266 * Finds the index of the median of three array elements.
2267 *
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
2273 */
2274 private static int med3(int a, int b, int c, double[] d)
2275 {
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));
2281 }
2282
2283 /**
2284 * Swaps the elements at two locations of an array
2285 *
2286 * @param i the first index
2287 * @param j the second index
2288 * @param a the array
2289 */
2290 private static void swap(int i, int j, double[] a)
2291 {
2292 double c = a[i];
2293 a[i] = a[j];
2294 a[j] = c;
2295 }
2296
2297 /**
2298 * Swaps two ranges of an array.
2299 *
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
2304 */
2305 private static void vecswap(int i, int j, int n, double[] a)
2306 {
2307 for ( ; n > 0; i++, j++, n--)
2308 swap(i, j, a);
2309 }
2310
2311 /**
2312 * Performs a recursive modified quicksort.
2313 *
2314 * @param array the array to sort
2315 * @param from the start index (inclusive)
2316 * @param count the number of elements to sort
2317 */
2318 private static void qsort(double[] array, int from, int count)
2319 {
2320 // Use an insertion sort on small arrays.
2321 if (count <= 7)
2322 {
2323 for (int i = from + 1; i < from + count; i++)
2324 for (int j = i;
2325 j > from && Double.compare(array[j - 1], array[j]) > 0;
2326 j--)
2327 {
2328 swap(j, j - 1, array);
2329 }
2330 return;
2331 }
2332
2333 // Determine a good median element.
2334 int mid = from + count / 2;
2335 int lo = from;
2336 int hi = from + count - 1;
2337
2338 if (count > 40)
2339 { // big arrays, pseudomedian of 9
2340 int s = count / 8;
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);
2344 }
2345 mid = med3(lo, mid, hi, array);
2346
2347 int a, b, c, d;
2348 int comp;
2349
2350 // Pull the median element out of the fray, and use it as a pivot.
2351 swap(from, mid, array);
2352 a = b = from;
2353 c = d = from + count - 1;
2354
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.
2359 while (true)
2360 {
2361 while (b <= c && (comp = Double.compare(array[b], array[from])) <= 0)
2362 {
2363 if (comp == 0)
2364 {
2365 swap(a, b, array);
2366 a++;
2367 }
2368 b++;
2369 }
2370 while (c >= b && (comp = Double.compare(array[c], array[from])) >= 0)
2371 {
2372 if (comp == 0)
2373 {
2374 swap(c, d, array);
2375 d--;
2376 }
2377 c--;
2378 }
2379 if (b > c)
2380 break;
2381 swap(b, c, array);
2382 b++;
2383 c--;
2384 }
2385
2386 // Swap pivot(s) back in place, the recurse on left and right sections.
2387 hi = from + count;
2388 int span;
2389 span = Math.min(a - from, b - a);
2390 vecswap(from, b - span, span, array);
2391
2392 span = Math.min(d - c, hi - d - 1);
2393 vecswap(b, hi - span, span, array);
2394
2395 span = b - a;
2396 if (span > 1)
2397 qsort(array, from, span);
2398
2399 span = d - c;
2400 if (span > 1)
2401 qsort(array, hi - span, span);
2402 }
2403
2404 /**
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.
2411 *
2412 * @param a the array to be sorted
2413 * @throws ClassCastException if any two elements are not mutually
2414 * comparable
2415 * @throws NullPointerException if an element is null (since
2416 * null.compareTo cannot work)
2417 * @see Comparable
2418 */
2419 public static void sort(Object[] a)
2420 {
2421 sort(a, 0, a.length, null);
2422 }
2423
2424 /**
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.
2431 *
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)
2439 */
2440 public static <T> void sort(T[] a, Comparator<? super T> c)
2441 {
2442 sort(a, 0, a.length, c);
2443 }
2444
2445 /**
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.
2452 *
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
2457 * comparable
2458 * @throws NullPointerException if an element is null (since
2459 * null.compareTo cannot work)
2460 * @throws ArrayIndexOutOfBoundsException if fromIndex and toIndex
2461 * are not in range.
2462 * @throws IllegalArgumentException if fromIndex > toIndex
2463 */
2464 public static void sort(Object[] a, int fromIndex, int toIndex)
2465 {
2466 sort(a, fromIndex, toIndex, null);
2467 }
2468
2469 /**
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.
2476 *
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
2485 * are not in range.
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)
2489 */
2490 public static <T> void sort(T[] a, int fromIndex, int toIndex,
2491 Comparator<? super T> c)
2492 {
2493 if (fromIndex > toIndex)
2494 throw new IllegalArgumentException("fromIndex " + fromIndex
2495 + " > toIndex " + toIndex);
2496 if (fromIndex < 0)
2497 throw new ArrayIndexOutOfBoundsException();
2498
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)
2505 {
2506 int end = Math.min(chunk + 6, toIndex);
2507 for (int i = chunk + 1; i < end; i++)
2508 {
2509 if (Collections.compare(a[i - 1], a[i], c) > 0)
2510 {
2511 // not already sorted
2512 int j = i;
2513 T elem = a[j];
2514 do
2515 {
2516 a[j] = a[j - 1];
2517 j--;
2518 }
2519 while (j > chunk
2520 && Collections.compare(a[j - 1], elem, c) > 0);
2521 a[j] = elem;
2522 }
2523 }
2524 }
2525
2526 int len = toIndex - fromIndex;
2527 // If length is smaller or equal 6 we are done.
2528 if (len <= 6)
2529 return;
2530
2531 T[] src = a;
2532 T[] dest = (T[]) new Object[len];
2533 T[] t = null; // t is used for swapping src and dest
2534
2535 // The difference of the fromIndex of the src and dest array.
2536 int srcDestDiff = -fromIndex;
2537
2538 // The merges are done in this loop
2539 for (int size = 6; size < len; size <<= 1)
2540 {
2541 for (int start = fromIndex; start < toIndex; start += size << 1)
2542 {
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);
2547
2548 // The second list is empty or the elements are already in
2549 // order - no need to merge
2550 if (mid >= end
2551 || Collections.compare(src[mid - 1], src[mid], c) <= 0)
2552 {
2553 System.arraycopy(src, start,
2554 dest, start + srcDestDiff, end - start);
2555
2556 // The two halves just need swapping - no need to merge
2557 }
2558 else if (Collections.compare(src[start], src[end - 1], c) > 0)
2559 {
2560 System.arraycopy(src, start,
2561 dest, end - size + srcDestDiff, size);
2562 System.arraycopy(src, mid,
2563 dest, start + srcDestDiff, end - mid);
2564
2565 }
2566 else
2567 {
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
2571 int p1 = start;
2572 int p2 = mid;
2573 int i = start + srcDestDiff;
2574
2575 // The main merge loop; terminates as soon as either
2576 // half is ended
2577 while (p1 < mid && p2 < end)
2578 {
2579 dest[i++] =
2580 src[(Collections.compare(src[p1], src[p2], c) <= 0
2581 ? p1++ : p2++)];
2582 }
2583
2584 // Finish up by copying the remainder of whichever half
2585 // wasn't finished.
2586 if (p1 < mid)
2587 System.arraycopy(src, p1, dest, i, mid - p1);
2588 else
2589 System.arraycopy(src, p2, dest, i, end - p2);
2590 }
2591 }
2592 // swap src and dest ready for the next merge
2593 t = src;
2594 src = dest;
2595 dest = t;
2596 fromIndex += srcDestDiff;
2597 toIndex += srcDestDiff;
2598 srcDestDiff = -srcDestDiff;
2599 }
2600
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.
2604 if (src != a)
2605 {
2606 // Note that fromIndex == 0.
2607 System.arraycopy(src, 0, a, srcDestDiff, toIndex);
2608 }
2609 }
2610
2611 /**
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
2617 * RandomAccess.
2618 *
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
2621 *
2622 * @throws NullPointerException if <code>a</code> is <code>null</code>.
2623 * @see Serializable
2624 * @see RandomAccess
2625 * @see Arrays.ArrayList
2626 */
2627 public static <T> List<T> asList(final T... a)
2628 {
2629 return new Arrays.ArrayList(a);
2630 }
2631
2632 /**
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.
2639 *
2640 * @param v an array of long numbers for which the hash code should be
2641 * computed.
2642 * @return the hash code of the array, or 0 if null was given.
2643 * @since 1.5
2644 */
2645 public static int hashCode(long[] v)
2646 {
2647 if (v == null)
2648 return 0;
2649 int result = 1;
2650 for (int i = 0; i < v.length; ++i)
2651 {
2652 int elt = (int) (v[i] ^ (v[i] >>> 32));
2653 result = 31 * result + elt;
2654 }
2655 return result;
2656 }
2657
2658 /**
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.
2665 *
2666 * @param v an array of integer numbers for which the hash code should be
2667 * computed.
2668 * @return the hash code of the array, or 0 if null was given.
2669 * @since 1.5
2670 */
2671 public static int hashCode(int[] v)
2672 {
2673 if (v == null)
2674 return 0;
2675 int result = 1;
2676 for (int i = 0; i < v.length; ++i)
2677 result = 31 * result + v[i];
2678 return result;
2679 }
2680
2681 /**
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.
2688 *
2689 * @param v an array of short numbers for which the hash code should be
2690 * computed.
2691 * @return the hash code of the array, or 0 if null was given.
2692 * @since 1.5
2693 */
2694 public static int hashCode(short[] v)
2695 {
2696 if (v == null)
2697 return 0;
2698 int result = 1;
2699 for (int i = 0; i < v.length; ++i)
2700 result = 31 * result + v[i];
2701 return result;
2702 }
2703
2704 /**
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.
2711 *
2712 * @param v an array of characters for which the hash code should be
2713 * computed.
2714 * @return the hash code of the array, or 0 if null was given.
2715 * @since 1.5
2716 */
2717 public static int hashCode(char[] v)
2718 {
2719 if (v == null)
2720 return 0;
2721 int result = 1;
2722 for (int i = 0; i < v.length; ++i)
2723 result = 31 * result + v[i];
2724 return result;
2725 }
2726
2727 /**
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.
2734 *
2735 * @param v an array of bytes for which the hash code should be
2736 * computed.
2737 * @return the hash code of the array, or 0 if null was given.
2738 * @since 1.5
2739 */
2740 public static int hashCode(byte[] v)
2741 {
2742 if (v == null)
2743 return 0;
2744 int result = 1;
2745 for (int i = 0; i < v.length; ++i)
2746 result = 31 * result + v[i];
2747 return result;
2748 }
2749
2750 /**
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.
2757 *
2758 * @param v an array of booleans for which the hash code should be
2759 * computed.
2760 * @return the hash code of the array, or 0 if null was given.
2761 * @since 1.5
2762 */
2763 public static int hashCode(boolean[] v)
2764 {
2765 if (v == null)
2766 return 0;
2767 int result = 1;
2768 for (int i = 0; i < v.length; ++i)
2769 result = 31 * result + (v[i] ? 1231 : 1237);
2770 return result;
2771 }
2772
2773 /**
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.
2780 *
2781 * @param v an array of floats for which the hash code should be
2782 * computed.
2783 * @return the hash code of the array, or 0 if null was given.
2784 * @since 1.5
2785 */
2786 public static int hashCode(float[] v)
2787 {
2788 if (v == null)
2789 return 0;
2790 int result = 1;
2791 for (int i = 0; i < v.length; ++i)
2792 result = 31 * result + Float.floatToIntBits(v[i]);
2793 return result;
2794 }
2795
2796 /**
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.
2803 *
2804 * @param v an array of doubles for which the hash code should be
2805 * computed.
2806 * @return the hash code of the array, or 0 if null was given.
2807 * @since 1.5
2808 */
2809 public static int hashCode(double[] v)
2810 {
2811 if (v == null)
2812 return 0;
2813 int result = 1;
2814 for (int i = 0; i < v.length; ++i)
2815 {
2816 long l = Double.doubleToLongBits(v[i]);
2817 int elt = (int) (l ^ (l >>> 32));
2818 result = 31 * result + elt;
2819 }
2820 return result;
2821 }
2822
2823 /**
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.
2829 *
2830 * @param v an array of integer numbers for which the hash code should be
2831 * computed.
2832 * @return the hash code of the array, or 0 if null was given.
2833 * @since 1.5
2834 */
2835 public static int hashCode(Object[] v)
2836 {
2837 if (v == null)
2838 return 0;
2839 int result = 1;
2840 for (int i = 0; i < v.length; ++i)
2841 {
2842 int elt = v[i] == null ? 0 : v[i].hashCode();
2843 result = 31 * result + elt;
2844 }
2845 return result;
2846 }
2847
2848 public static int deepHashCode(Object[] v)
2849 {
2850 if (v == null)
2851 return 0;
2852 int result = 1;
2853 for (int i = 0; i < v.length; ++i)
2854 {
2855 int elt;
2856 if (v[i] == null)
2857 elt = 0;
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]);
2876 else
2877 elt = v[i].hashCode();
2878 result = 31 * result + elt;
2879 }
2880 return result;
2881 }
2882
2883 /** @since 1.5 */
2884 public static boolean deepEquals(Object[] v1, Object[] v2)
2885 {
2886 if (v1 == null)
2887 return v2 == null;
2888 if (v2 == null || v1.length != v2.length)
2889 return false;
2890
2891 for (int i = 0; i < v1.length; ++i)
2892 {
2893 Object e1 = v1[i];
2894 Object e2 = v2[i];
2895
2896 if (e1 == e2)
2897 continue;
2898 if (e1 == null || e2 == null)
2899 return false;
2900
2901 boolean check;
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);
2920 else
2921 check = e1.equals(e2);
2922 if (! check)
2923 return false;
2924 }
2925
2926 return true;
2927 }
2928
2929 /**
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
2934 * @since 1.5
2935 */
2936 public static String toString(boolean[] v)
2937 {
2938 if (v == null)
2939 return "null";
2940 CPStringBuilder b = new CPStringBuilder("[");
2941 for (int i = 0; i < v.length; ++i)
2942 {
2943 if (i > 0)
2944 b.append(", ");
2945 b.append(v[i]);
2946 }
2947 b.append("]");
2948 return b.toString();
2949 }
2950
2951 /**
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
2956 * @since 1.5
2957 */
2958 public static String toString(byte[] v)
2959 {
2960 if (v == null)
2961 return "null";
2962 CPStringBuilder b = new CPStringBuilder("[");
2963 for (int i = 0; i < v.length; ++i)
2964 {
2965 if (i > 0)
2966 b.append(", ");
2967 b.append(v[i]);
2968 }
2969 b.append("]");
2970 return b.toString();
2971 }
2972
2973 /**
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
2978 * @since 1.5
2979 */
2980 public static String toString(char[] v)
2981 {
2982 if (v == null)
2983 return "null";
2984 CPStringBuilder b = new CPStringBuilder("[");
2985 for (int i = 0; i < v.length; ++i)
2986 {
2987 if (i > 0)
2988 b.append(", ");
2989 b.append(v[i]);
2990 }
2991 b.append("]");
2992 return b.toString();
2993 }
2994
2995 /**
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
3000 * @since 1.5
3001 */
3002 public static String toString(short[] v)
3003 {
3004 if (v == null)
3005 return "null";
3006 CPStringBuilder b = new CPStringBuilder("[");
3007 for (int i = 0; i < v.length; ++i)
3008 {
3009 if (i > 0)
3010 b.append(", ");
3011 b.append(v[i]);
3012 }
3013 b.append("]");
3014 return b.toString();
3015 }
3016
3017 /**
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
3022 * @since 1.5
3023 */
3024 public static String toString(int[] v)
3025 {
3026 if (v == null)
3027 return "null";
3028 CPStringBuilder b = new CPStringBuilder("[");
3029 for (int i = 0; i < v.length; ++i)
3030 {
3031 if (i > 0)
3032 b.append(", ");
3033 b.append(v[i]);
3034 }
3035 b.append("]");
3036 return b.toString();
3037 }
3038
3039 /**
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
3044 * @since 1.5
3045 */
3046 public static String toString(long[] v)
3047 {
3048 if (v == null)
3049 return "null";
3050 CPStringBuilder b = new CPStringBuilder("[");
3051 for (int i = 0; i < v.length; ++i)
3052 {
3053 if (i > 0)
3054 b.append(", ");
3055 b.append(v[i]);
3056 }
3057 b.append("]");
3058 return b.toString();
3059 }
3060
3061 /**
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
3066 * @since 1.5
3067 */
3068 public static String toString(float[] v)
3069 {
3070 if (v == null)
3071 return "null";
3072 CPStringBuilder b = new CPStringBuilder("[");
3073 for (int i = 0; i < v.length; ++i)
3074 {
3075 if (i > 0)
3076 b.append(", ");
3077 b.append(v[i]);
3078 }
3079 b.append("]");
3080 return b.toString();
3081 }
3082
3083 /**
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
3088 * @since 1.5
3089 */
3090 public static String toString(double[] v)
3091 {
3092 if (v == null)
3093 return "null";
3094 CPStringBuilder b = new CPStringBuilder("[");
3095 for (int i = 0; i < v.length; ++i)
3096 {
3097 if (i > 0)
3098 b.append(", ");
3099 b.append(v[i]);
3100 }
3101 b.append("]");
3102 return b.toString();
3103 }
3104
3105 /**
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
3110 * @since 1.5
3111 */
3112 public static String toString(Object[] v)
3113 {
3114 if (v == null)
3115 return "null";
3116 CPStringBuilder b = new CPStringBuilder("[");
3117 for (int i = 0; i < v.length; ++i)
3118 {
3119 if (i > 0)
3120 b.append(", ");
3121 b.append(v[i]);
3122 }
3123 b.append("]");
3124 return b.toString();
3125 }
3126
3127 private static void deepToString(Object[] v, CPStringBuilder b, HashSet seen)
3128 {
3129 b.append("[");
3130 for (int i = 0; i < v.length; ++i)
3131 {
3132 if (i > 0)
3133 b.append(", ");
3134 Object elt = v[i];
3135 if (elt == null)
3136 b.append("null");
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[])
3154 {
3155 Object[] os = (Object[]) elt;
3156 if (seen.contains(os))
3157 b.append("[...]");
3158 else
3159 {
3160 seen.add(os);
3161 deepToString(os, b, seen);
3162 }
3163 }
3164 else
3165 b.append(elt);
3166 }
3167 b.append("]");
3168 }
3169
3170 /** @since 1.5 */
3171 public static String deepToString(Object[] v)
3172 {
3173 if (v == null)
3174 return "null";
3175 HashSet seen = new HashSet();
3176 CPStringBuilder b = new CPStringBuilder();
3177 deepToString(v, b, seen);
3178 return b.toString();
3179 }
3180
3181 /**
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.
3186 *
3187 * @author Eric Blake (ebb9@email.byu.edu)
3188 * @status updated to 1.4
3189 */
3190 private static final class ArrayList<E> extends AbstractList<E>
3191 implements Serializable, RandomAccess
3192 {
3193 // We override the necessary methods, plus others which will be much
3194 // more efficient with direct iteration rather than relying on iterator().
3195
3196 /**
3197 * Compatible with JDK 1.4.
3198 */
3199 private static final long serialVersionUID = -2764017481108945198L;
3200
3201 /**
3202 * The array we are viewing.
3203 * @serial the array
3204 */
3205 private final E[] a;
3206
3207 /**
3208 * Construct a list view of the array.
3209 * @param a the array to view
3210 * @throws NullPointerException if a is null
3211 */
3212 ArrayList(E[] a)
3213 {
3214 // We have to explicitly check.
3215 if (a == null)
3216 throw new NullPointerException();
3217 this.a = a;
3218 }
3219
3220 /**
3221 * Returns the object at the specified index in
3222 * the array.
3223 *
3224 * @param index The index to retrieve an object from.
3225 * @return The object at the array index specified.
3226 */
3227 public E get(int index)
3228 {
3229 return a[index];
3230 }
3231
3232 /**
3233 * Returns the size of the array.
3234 *
3235 * @return The size.
3236 */
3237 public int size()
3238 {
3239 return a.length;
3240 }
3241
3242 /**
3243 * Replaces the object at the specified index
3244 * with the supplied element.
3245 *
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.
3249 */
3250 public E set(int index, E element)
3251 {
3252 E old = a[index];
3253 a[index] = element;
3254 return old;
3255 }
3256
3257 /**
3258 * Returns true if the array contains the
3259 * supplied object.
3260 *
3261 * @param o The object to look for.
3262 * @return True if the object was found.
3263 */
3264 public boolean contains(Object o)
3265 {
3266 return lastIndexOf(o) >= 0;
3267 }
3268
3269 /**
3270 * Returns the first index at which the
3271 * object, o, occurs in the array.
3272 *
3273 * @param o The object to search for.
3274 * @return The first relevant index.
3275 */
3276 public int indexOf(Object o)
3277 {
3278 int size = a.length;
3279 for (int i = 0; i < size; i++)
3280 if (ArrayList.equals(o, a[i]))
3281 return i;
3282 return -1;
3283 }
3284
3285 /**
3286 * Returns the last index at which the
3287 * object, o, occurs in the array.
3288 *
3289 * @param o The object to search for.
3290 * @return The last relevant index.
3291 */
3292 public int lastIndexOf(Object o)
3293 {
3294 int i = a.length;
3295 while (--i >= 0)
3296 if (ArrayList.equals(o, a[i]))
3297 return i;
3298 return -1;
3299 }
3300
3301 /**
3302 * Transforms the list into an array of
3303 * objects, by simplying cloning the array
3304 * wrapped by this list.
3305 *
3306 * @return A clone of the internal array.
3307 */
3308 public Object[] toArray()
3309 {
3310 return (Object[]) a.clone();
3311 }
3312
3313 /**
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.
3318 *
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.
3322 */
3323 public <T> T[] toArray(T[] array)
3324 {
3325 int size = a.length;
3326 if (array.length < size)
3327 array = (T[]) Array.newInstance(array.getClass().getComponentType(),
3328 size);
3329 else if (array.length > size)
3330 array[size] = null;
3331
3332 System.arraycopy(a, 0, array, 0, size);
3333 return array;
3334 }
3335 }
3336
3337 /**
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>.
3345 *
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>.
3352 * @since 1.6
3353 * @see #copyOfRange(boolean[],int,int)
3354 */
3355 public static boolean[] copyOf(boolean[] original, int newLength)
3356 {
3357 if (newLength < 0)
3358 throw new NegativeArraySizeException("The array size is negative.");
3359 return copyOfRange(original, 0, newLength);
3360 }
3361
3362 /**
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>.
3376 *
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>.
3386 * @since 1.6
3387 * @see #copyOf(boolean[],int)
3388 */
3389 public static boolean[] copyOfRange(boolean[] original, int from, int to)
3390 {
3391 if (from > 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)
3396 {
3397 System.arraycopy(original, from, newArray, 0,
3398 original.length - from);
3399 fill(newArray, original.length, newArray.length, false);
3400 }
3401 else
3402 System.arraycopy(original, from, newArray, 0, to - from);
3403 return newArray;
3404 }
3405
3406 /**
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>.
3414 *
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>.
3421 * @since 1.6
3422 * @see #copyOfRange(byte[],int,int)
3423 */
3424 public static byte[] copyOf(byte[] original, int newLength)
3425 {
3426 if (newLength < 0)
3427 throw new NegativeArraySizeException("The array size is negative.");
3428 return copyOfRange(original, 0, newLength);
3429 }
3430
3431 /**
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>.
3445 *
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>.
3455 * @since 1.6
3456 * @see #copyOf(byte[],int)
3457 */
3458 public static byte[] copyOfRange(byte[] original, int from, int to)
3459 {
3460 if (from > 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)
3465 {
3466 System.arraycopy(original, from, newArray, 0,
3467 original.length - from);
3468 fill(newArray, original.length, newArray.length, (byte)0);
3469 }
3470 else
3471 System.arraycopy(original, from, newArray, 0, to - from);
3472 return newArray;
3473 }
3474
3475 /**
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>.
3483 *
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>.
3490 * @since 1.6
3491 * @see #copyOfRange(char[],int,int)
3492 */
3493 public static char[] copyOf(char[] original, int newLength)
3494 {
3495 if (newLength < 0)
3496 throw new NegativeArraySizeException("The array size is negative.");
3497 return copyOfRange(original, 0, newLength);
3498 }
3499
3500 /**
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>.
3514 *
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>.
3524 * @since 1.6
3525 * @see #copyOf(char[],int)
3526 */
3527 public static char[] copyOfRange(char[] original, int from, int to)
3528 {
3529 if (from > 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)
3534 {
3535 System.arraycopy(original, from, newArray, 0,
3536 original.length - from);
3537 fill(newArray, original.length, newArray.length, '\0');
3538 }
3539 else
3540 System.arraycopy(original, from, newArray, 0, to - from);
3541 return newArray;
3542 }
3543
3544 /**
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>.
3552 *
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>.
3559 * @since 1.6
3560 * @see #copyOfRange(double[],int,int)
3561 */
3562 public static double[] copyOf(double[] original, int newLength)
3563 {
3564 if (newLength < 0)
3565 throw new NegativeArraySizeException("The array size is negative.");
3566 return copyOfRange(original, 0, newLength);
3567 }
3568
3569 /**
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>.
3583 *
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>.
3593 * @since 1.6
3594 * @see #copyOf(double[],int)
3595 */
3596 public static double[] copyOfRange(double[] original, int from, int to)
3597 {
3598 if (from > 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)
3603 {
3604 System.arraycopy(original, from, newArray, 0,
3605 original.length - from);
3606 fill(newArray, original.length, newArray.length, 0d);
3607 }
3608 else
3609 System.arraycopy(original, from, newArray, 0, to - from);
3610 return newArray;
3611 }
3612
3613 /**
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>.
3621 *
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>.
3628 * @since 1.6
3629 * @see #copyOfRange(float[],int,int)
3630 */
3631 public static float[] copyOf(float[] original, int newLength)
3632 {
3633 if (newLength < 0)
3634 throw new NegativeArraySizeException("The array size is negative.");
3635 return copyOfRange(original, 0, newLength);
3636 }
3637
3638 /**
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>.
3652 *
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>.
3662 * @since 1.6
3663 * @see #copyOf(float[],int)
3664 */
3665 public static float[] copyOfRange(float[] original, int from, int to)
3666 {
3667 if (from > 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)
3672 {
3673 System.arraycopy(original, from, newArray, 0,
3674 original.length - from);
3675 fill(newArray, original.length, newArray.length, 0f);
3676 }
3677 else
3678 System.arraycopy(original, from, newArray, 0, to - from);
3679 return newArray;
3680 }
3681
3682 /**
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>.
3690 *
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>.
3697 * @since 1.6
3698 * @see #copyOfRange(int[],int,int)
3699 */
3700 public static int[] copyOf(int[] original, int newLength)
3701 {
3702 if (newLength < 0)
3703 throw new NegativeArraySizeException("The array size is negative.");
3704 return copyOfRange(original, 0, newLength);
3705 }
3706
3707 /**
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>.
3721 *
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>.
3731 * @since 1.6
3732 * @see #copyOf(int[],int)
3733 */
3734 public static int[] copyOfRange(int[] original, int from, int to)
3735 {
3736 if (from > 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)
3741 {
3742 System.arraycopy(original, from, newArray, 0,
3743 original.length - from);
3744 fill(newArray, original.length, newArray.length, 0);
3745 }
3746 else
3747 System.arraycopy(original, from, newArray, 0, to - from);
3748 return newArray;
3749 }
3750
3751 /**
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>.
3759 *
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>.
3766 * @since 1.6
3767 * @see #copyOfRange(long[],int,int)
3768 */
3769 public static long[] copyOf(long[] original, int newLength)
3770 {
3771 if (newLength < 0)
3772 throw new NegativeArraySizeException("The array size is negative.");
3773 return copyOfRange(original, 0, newLength);
3774 }
3775
3776 /**
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>.
3790 *
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>.
3800 * @since 1.6
3801 * @see #copyOf(long[],int)
3802 */
3803 public static long[] copyOfRange(long[] original, int from, int to)
3804 {
3805 if (from > 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)
3810 {
3811 System.arraycopy(original, from, newArray, 0,
3812 original.length - from);
3813 fill(newArray, original.length, newArray.length, 0L);
3814 }
3815 else
3816 System.arraycopy(original, from, newArray, 0, to - from);
3817 return newArray;
3818 }
3819
3820 /**
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>.
3828 *
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>.
3835 * @since 1.6
3836 * @see #copyOfRange(short[],int,int)
3837 */
3838 public static short[] copyOf(short[] original, int newLength)
3839 {
3840 if (newLength < 0)
3841 throw new NegativeArraySizeException("The array size is negative.");
3842 return copyOfRange(original, 0, newLength);
3843 }
3844
3845 /**
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>.
3859 *
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>.
3869 * @since 1.6
3870 * @see #copyOf(short[],int)
3871 */
3872 public static short[] copyOfRange(short[] original, int from, int to)
3873 {
3874 if (from > 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)
3879 {
3880 System.arraycopy(original, from, newArray, 0,
3881 original.length - from);
3882 fill(newArray, original.length, newArray.length, (short)0);
3883 }
3884 else
3885 System.arraycopy(original, from, newArray, 0, to - from);
3886 return newArray;
3887 }
3888
3889 /**
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>.
3897 *
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>.
3904 * @since 1.6
3905 * @see #copyOfRange(T[],int,int)
3906 */
3907 public static <T> T[] copyOf(T[] original, int newLength)
3908 {
3909 if (newLength < 0)
3910 throw new NegativeArraySizeException("The array size is negative.");
3911 return copyOfRange(original, 0, newLength);
3912 }
3913
3914 /**
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>.
3928 *
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>.
3938 * @since 1.6
3939 * @see #copyOf(T[],int)
3940 */
3941 public static <T> T[] copyOfRange(T[] original, int from, int to)
3942 {
3943 if (from > 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)
3949 {
3950 System.arraycopy(original, from, newArray, 0,
3951 original.length - from);
3952 fill(newArray, original.length, newArray.length, null);
3953 }
3954 else
3955 System.arraycopy(original, from, newArray, 0, to - from);
3956 return newArray;
3957 }
3958
3959 /**
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>.
3968 *
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>.
3976 * @since 1.6
3977 * @see #copyOfRange(U[],int,int,Class)
3978 */
3979 public static <T,U> T[] copyOf(U[] original, int newLength,
3980 Class<? extends T[]> newType)
3981 {
3982 if (newLength < 0)
3983 throw new NegativeArraySizeException("The array size is negative.");
3984 return copyOfRange(original, 0, newLength, newType);
3985 }
3986
3987 /**
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>.
4002 *
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>.
4013 * @since 1.6
4014 * @see #copyOf(T[],int)
4015 */
4016 public static <T,U> T[] copyOfRange(U[] original, int from, int to,
4017 Class<? extends T[]> newType)
4018 {
4019 if (from > to)
4020 throw new IllegalArgumentException("The initial index is after " +
4021 "the final index.");
4022 T[] newArray = (T[]) Array.newInstance(newType.getComponentType(),
4023 to - from);
4024 if (to > original.length)
4025 {
4026 System.arraycopy(original, from, newArray, 0,
4027 original.length - from);
4028 fill(newArray, original.length, newArray.length, null);
4029 }
4030 else
4031 System.arraycopy(original, from, newArray, 0, to - from);
4032 return newArray;
4033 }
4034 }