1 /* Arrays.java -- Utility class with methods to operate on arrays
2 Copyright (C) 1998, 1999, 2000, 2001, 2002, 2003 Free Software Foundation, Inc.
4 This file is part of GNU Classpath.
6 GNU Classpath is free software; you can redistribute it and/or modify
7 it under the terms of the GNU General Public License as published by
8 the Free Software Foundation; either version 2, or (at your option)
11 GNU Classpath is distributed in the hope that it will be useful, but
12 WITHOUT ANY WARRANTY; without even the implied warranty of
13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
14 General Public License for more details.
16 You should have received a copy of the GNU General Public License
17 along with GNU Classpath; see the file COPYING. If not, write to the
18 Free Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
21 Linking this library statically or dynamically with other modules is
22 making a combined work based on this library. Thus, the terms and
23 conditions of the GNU General Public License cover the whole
26 As a special exception, the copyright holders of this library give you
27 permission to link this library with independent modules to produce an
28 executable, regardless of the license terms of these independent
29 modules, and to copy and distribute the resulting executable under
30 terms of your choice, provided that you also meet, for each linked
31 independent module, the terms and conditions of the license of that
32 module. An independent module is a module which is not derived from
33 or based on this library. If you modify this library, you may extend
34 this exception to your version of the library, but you are not
35 obligated to do so. If you do not wish to do so, delete this
36 exception statement from your version. */
41 import java
.io
.Serializable
;
42 import java
.lang
.reflect
.Array
;
45 * This class contains various static utility methods performing operations on
46 * arrays, and a method to provide a List "view" of an array to facilitate
47 * using arrays with Collection-based APIs. All methods throw a
48 * {@link NullPointerException} if the parameter array is null.
51 * Implementations may use their own algorithms, but must obey the general
52 * properties; for example, the sort must be stable and n*log(n) complexity.
53 * Sun's implementation of sort, and therefore ours, is a tuned quicksort,
54 * adapted from Jon L. Bentley and M. Douglas McIlroy's "Engineering a Sort
55 * Function", Software-Practice and Experience, Vol. 23(11) P. 1249-1265
56 * (November 1993). This algorithm offers n*log(n) performance on many data
57 * sets that cause other quicksorts to degrade to quadratic performance.
59 * @author Original author unknown
60 * @author Bryce McKinlay
61 * @author Eric Blake <ebb9@email.byu.edu>
65 * @status updated to 1.4
70 * This class is non-instantiable.
79 * Perform a binary search of a byte array for a key. The array must be
80 * sorted (as by the sort() method) - if it is not, the behaviour of this
81 * method is undefined, and may be an infinite loop. If the array contains
82 * the key more than once, any one of them may be found. Note: although the
83 * specification allows for an infinite loop if the array is unsorted, it
84 * will not happen in this implementation.
86 * @param a the array to search (must be sorted)
87 * @param key the value to search for
88 * @return the index at which the key was found, or -n-1 if it was not
89 * found, where n is the index of the first value higher than key or
90 * a.length if there is no such value.
92 public static int binarySearch(byte[] a
, byte key
)
95 int hi
= a
.length
- 1;
99 mid
= (low
+ hi
) >> 1;
100 final byte d
= a
[mid
];
106 // This gets the insertion point right on the last loop.
113 * Perform a binary search of a char array for a key. The array must be
114 * sorted (as by the sort() method) - if it is not, the behaviour of this
115 * method is undefined, and may be an infinite loop. If the array contains
116 * the key more than once, any one of them may be found. Note: although the
117 * specification allows for an infinite loop if the array is unsorted, it
118 * will not happen in this implementation.
120 * @param a the array to search (must be sorted)
121 * @param key the value to search for
122 * @return the index at which the key was found, or -n-1 if it was not
123 * found, where n is the index of the first value higher than key or
124 * a.length if there is no such value.
126 public static int binarySearch(char[] a
, char key
)
129 int hi
= a
.length
- 1;
133 mid
= (low
+ hi
) >> 1;
134 final char d
= a
[mid
];
140 // This gets the insertion point right on the last loop.
147 * Perform a binary search of a short array for a key. The array must be
148 * sorted (as by the sort() method) - if it is not, the behaviour of this
149 * method is undefined, and may be an infinite loop. If the array contains
150 * the key more than once, any one of them may be found. Note: although the
151 * specification allows for an infinite loop if the array is unsorted, it
152 * will not happen in this implementation.
154 * @param a the array to search (must be sorted)
155 * @param key the value to search for
156 * @return the index at which the key was found, or -n-1 if it was not
157 * found, where n is the index of the first value higher than key or
158 * a.length if there is no such value.
160 public static int binarySearch(short[] a
, short key
)
163 int hi
= a
.length
- 1;
167 mid
= (low
+ hi
) >> 1;
168 final short d
= a
[mid
];
174 // This gets the insertion point right on the last loop.
181 * Perform a binary search of an int array for a key. The array must be
182 * sorted (as by the sort() method) - if it is not, the behaviour of this
183 * method is undefined, and may be an infinite loop. If the array contains
184 * the key more than once, any one of them may be found. Note: although the
185 * specification allows for an infinite loop if the array is unsorted, it
186 * will not happen in this implementation.
188 * @param a the array to search (must be sorted)
189 * @param key the value to search for
190 * @return the index at which the key was found, or -n-1 if it was not
191 * found, where n is the index of the first value higher than key or
192 * a.length if there is no such value.
194 public static int binarySearch(int[] a
, int key
)
197 int hi
= a
.length
- 1;
201 mid
= (low
+ hi
) >> 1;
202 final int d
= a
[mid
];
208 // This gets the insertion point right on the last loop.
215 * Perform a binary search of a long array for a key. The array must be
216 * sorted (as by the sort() method) - if it is not, the behaviour of this
217 * method is undefined, and may be an infinite loop. If the array contains
218 * the key more than once, any one of them may be found. Note: although the
219 * specification allows for an infinite loop if the array is unsorted, it
220 * will not happen in this implementation.
222 * @param a the array to search (must be sorted)
223 * @param key the value to search for
224 * @return the index at which the key was found, or -n-1 if it was not
225 * found, where n is the index of the first value higher than key or
226 * a.length if there is no such value.
228 public static int binarySearch(long[] a
, long key
)
231 int hi
= a
.length
- 1;
235 mid
= (low
+ hi
) >> 1;
236 final long d
= a
[mid
];
242 // This gets the insertion point right on the last loop.
249 * Perform a binary search of a float array for a key. The array must be
250 * sorted (as by the sort() method) - if it is not, the behaviour of this
251 * method is undefined, and may be an infinite loop. If the array contains
252 * the key more than once, any one of them may be found. Note: although the
253 * specification allows for an infinite loop if the array is unsorted, it
254 * will not happen in this implementation.
256 * @param a the array to search (must be sorted)
257 * @param key the value to search for
258 * @return the index at which the key was found, or -n-1 if it was not
259 * found, where n is the index of the first value higher than key or
260 * a.length if there is no such value.
262 public static int binarySearch(float[] a
, float key
)
264 // Must use Float.compare to take into account NaN, +-0.
266 int hi
= a
.length
- 1;
270 mid
= (low
+ hi
) >> 1;
271 final int r
= Float
.compare(a
[mid
], key
);
277 // This gets the insertion point right on the last loop
284 * Perform a binary search of a double array for a key. The array must be
285 * sorted (as by the sort() method) - if it is not, the behaviour of this
286 * method is undefined, and may be an infinite loop. If the array contains
287 * the key more than once, any one of them may be found. Note: although the
288 * specification allows for an infinite loop if the array is unsorted, it
289 * will not happen in this implementation.
291 * @param a the array to search (must be sorted)
292 * @param key the value to search for
293 * @return the index at which the key was found, or -n-1 if it was not
294 * found, where n is the index of the first value higher than key or
295 * a.length if there is no such value.
297 public static int binarySearch(double[] a
, double key
)
299 // Must use Double.compare to take into account NaN, +-0.
301 int hi
= a
.length
- 1;
305 mid
= (low
+ hi
) >> 1;
306 final int r
= Double
.compare(a
[mid
], key
);
312 // This gets the insertion point right on the last loop
319 * Perform a binary search of an Object array for a key, using the natural
320 * ordering of the elements. The array must be sorted (as by the sort()
321 * method) - if it is not, the behaviour of this method is undefined, and may
322 * be an infinite loop. Further, the key must be comparable with every item
323 * in the array. If the array contains the key more than once, any one of
324 * them may be found. Note: although the specification allows for an infinite
325 * loop if the array is unsorted, it will not happen in this (JCL)
328 * @param a the array to search (must be sorted)
329 * @param key the value to search for
330 * @return the index at which the key was found, or -n-1 if it was not
331 * found, where n is the index of the first value higher than key or
332 * a.length if there is no such value.
333 * @throws ClassCastException if key could not be compared with one of the
335 * @throws NullPointerException if a null element in a is compared
337 public static int binarySearch(Object
[] a
, Object key
)
339 return binarySearch(a
, key
, null);
343 * Perform a binary search of an Object array for a key, using a supplied
344 * Comparator. The array must be sorted (as by the sort() method with the
345 * same Comparator) - if it is not, the behaviour of this method is
346 * undefined, and may be an infinite loop. Further, the key must be
347 * comparable with every item in the array. If the array contains the key
348 * more than once, any one of them may be found. Note: although the
349 * specification allows for an infinite loop if the array is unsorted, it
350 * will not happen in this (JCL) implementation.
352 * @param a the array to search (must be sorted)
353 * @param key the value to search for
354 * @param c the comparator by which the array is sorted; or null to
355 * use the elements' natural order
356 * @return the index at which the key was found, or -n-1 if it was not
357 * found, where n is the index of the first value higher than key or
358 * a.length if there is no such value.
359 * @throws ClassCastException if key could not be compared with one of the
361 * @throws NullPointerException if a null element is compared with natural
362 * ordering (only possible when c is null)
364 public static int binarySearch(Object
[] a
, Object key
, Comparator c
)
367 int hi
= a
.length
- 1;
371 mid
= (low
+ hi
) >> 1;
372 final int d
= Collections
.compare(key
, a
[mid
], c
);
378 // This gets the insertion point right on the last loop
387 * Compare two boolean arrays for equality.
389 * @param a1 the first array to compare
390 * @param a2 the second array to compare
391 * @return true if a1 and a2 are both null, or if a2 is of the same length
392 * as a1, and for each 0 <= i < a1.length, a1[i] == a2[i]
394 public static boolean equals(boolean[] a1
, boolean[] a2
)
396 // Quick test which saves comparing elements of the same array, and also
397 // catches the case that both are null.
401 if (null == a1
|| null == a2
)
404 // If they're the same length, test each element
405 if (a1
.length
== a2
.length
)
417 * Compare two byte arrays for equality.
419 * @param a1 the first array to compare
420 * @param a2 the second array to compare
421 * @return true if a1 and a2 are both null, or if a2 is of the same length
422 * as a1, and for each 0 <= i < a1.length, a1[i] == a2[i]
424 public static boolean equals(byte[] a1
, byte[] a2
)
426 // Quick test which saves comparing elements of the same array, and also
427 // catches the case that both are null.
431 if (null == a1
|| null == a2
)
434 // If they're the same length, test each element
435 if (a1
.length
== a2
.length
)
447 * Compare two char arrays for equality.
449 * @param a1 the first array to compare
450 * @param a2 the second array to compare
451 * @return true if a1 and a2 are both null, or if a2 is of the same length
452 * as a1, and for each 0 <= i < a1.length, a1[i] == a2[i]
454 public static boolean equals(char[] a1
, char[] a2
)
456 // Quick test which saves comparing elements of the same array, and also
457 // catches the case that both are null.
461 if (null == a1
|| null == a2
)
464 // If they're the same length, test each element
465 if (a1
.length
== a2
.length
)
477 * Compare two short arrays for equality.
479 * @param a1 the first array to compare
480 * @param a2 the second array to compare
481 * @return true if a1 and a2 are both null, or if a2 is of the same length
482 * as a1, and for each 0 <= i < a1.length, a1[i] == a2[i]
484 public static boolean equals(short[] a1
, short[] a2
)
486 // Quick test which saves comparing elements of the same array, and also
487 // catches the case that both are null.
491 if (null == a1
|| null == a2
)
494 // If they're the same length, test each element
495 if (a1
.length
== a2
.length
)
507 * Compare two int arrays for equality.
509 * @param a1 the first array to compare
510 * @param a2 the second array to compare
511 * @return true if a1 and a2 are both null, or if a2 is of the same length
512 * as a1, and for each 0 <= i < a1.length, a1[i] == a2[i]
514 public static boolean equals(int[] a1
, int[] a2
)
516 // Quick test which saves comparing elements of the same array, and also
517 // catches the case that both are null.
521 if (null == a1
|| null == a2
)
524 // If they're the same length, test each element
525 if (a1
.length
== a2
.length
)
537 * Compare two long arrays for equality.
539 * @param a1 the first array to compare
540 * @param a2 the second array to compare
541 * @return true if a1 and a2 are both null, or if a2 is of the same length
542 * as a1, and for each 0 <= i < a1.length, a1[i] == a2[i]
544 public static boolean equals(long[] a1
, long[] a2
)
546 // Quick test which saves comparing elements of the same array, and also
547 // catches the case that both are null.
551 if (null == a1
|| null == a2
)
554 // If they're the same length, test each element
555 if (a1
.length
== a2
.length
)
567 * Compare two float arrays for equality.
569 * @param a1 the first array to compare
570 * @param a2 the second array to compare
571 * @return true if a1 and a2 are both null, or if a2 is of the same length
572 * as a1, and for each 0 <= i < a1.length, a1[i] == a2[i]
574 public static boolean equals(float[] a1
, float[] a2
)
576 // Quick test which saves comparing elements of the same array, and also
577 // catches the case that both are null.
581 if (null == a1
|| null == a2
)
584 // Must use Float.compare to take into account NaN, +-0.
585 // If they're the same length, test each element
586 if (a1
.length
== a2
.length
)
590 if (Float
.compare(a1
[i
], a2
[i
]) != 0)
598 * Compare two double arrays for equality.
600 * @param a1 the first array to compare
601 * @param a2 the second array to compare
602 * @return true if a1 and a2 are both null, or if a2 is of the same length
603 * as a1, and for each 0 <= i < a1.length, a1[i] == a2[i]
605 public static boolean equals(double[] a1
, double[] a2
)
607 // Quick test which saves comparing elements of the same array, and also
608 // catches the case that both are null.
612 if (null == a1
|| null == a2
)
615 // Must use Double.compare to take into account NaN, +-0.
616 // If they're the same length, test each element
617 if (a1
.length
== a2
.length
)
621 if (Double
.compare(a1
[i
], a2
[i
]) != 0)
629 * Compare two Object arrays for equality.
631 * @param a1 the first array to compare
632 * @param a2 the second array to compare
633 * @return true if a1 and a2 are both null, or if a1 is of the same length
634 * as a2, and for each 0 <= i < a.length, a1[i] == null ?
635 * a2[i] == null : a1[i].equals(a2[i]).
637 public static boolean equals(Object
[] a1
, Object
[] a2
)
639 // Quick test which saves comparing elements of the same array, and also
640 // catches the case that both are null.
644 if (null == a1
|| null == a2
)
647 // If they're the same length, test each element
648 if (a1
.length
== a2
.length
)
652 if (! AbstractCollection
.equals(a1
[i
], a2
[i
]))
662 * Fill an array with a boolean value.
664 * @param a the array to fill
665 * @param val the value to fill it with
667 public static void fill(boolean[] a
, boolean val
)
669 fill(a
, 0, a
.length
, val
);
673 * Fill a range of an array with a boolean value.
675 * @param a the array to fill
676 * @param fromIndex the index to fill from, inclusive
677 * @param toIndex the index to fill to, exclusive
678 * @param val the value to fill with
679 * @throws IllegalArgumentException if fromIndex > toIndex
680 * @throws ArrayIndexOutOfBoundsException if fromIndex < 0
681 * || toIndex > a.length
683 public static void fill(boolean[] a
, int fromIndex
, int toIndex
, boolean val
)
685 if (fromIndex
> toIndex
)
686 throw new IllegalArgumentException();
687 for (int i
= fromIndex
; i
< toIndex
; i
++)
692 * Fill an array with a byte value.
694 * @param a the array to fill
695 * @param val the value to fill it with
697 public static void fill(byte[] a
, byte val
)
699 fill(a
, 0, a
.length
, val
);
703 * Fill a range of an array with a byte value.
705 * @param a the array to fill
706 * @param fromIndex the index to fill from, inclusive
707 * @param toIndex the index to fill to, exclusive
708 * @param val the value to fill with
709 * @throws IllegalArgumentException if fromIndex > toIndex
710 * @throws ArrayIndexOutOfBoundsException if fromIndex < 0
711 * || toIndex > a.length
713 public static void fill(byte[] a
, int fromIndex
, int toIndex
, byte val
)
715 if (fromIndex
> toIndex
)
716 throw new IllegalArgumentException();
717 for (int i
= fromIndex
; i
< toIndex
; i
++)
722 * Fill an array with a char value.
724 * @param a the array to fill
725 * @param val the value to fill it with
727 public static void fill(char[] a
, char val
)
729 fill(a
, 0, a
.length
, val
);
733 * Fill a range of an array with a char value.
735 * @param a the array to fill
736 * @param fromIndex the index to fill from, inclusive
737 * @param toIndex the index to fill to, exclusive
738 * @param val the value to fill with
739 * @throws IllegalArgumentException if fromIndex > toIndex
740 * @throws ArrayIndexOutOfBoundsException if fromIndex < 0
741 * || toIndex > a.length
743 public static void fill(char[] a
, int fromIndex
, int toIndex
, char val
)
745 if (fromIndex
> toIndex
)
746 throw new IllegalArgumentException();
747 for (int i
= fromIndex
; i
< toIndex
; i
++)
752 * Fill an array with a short value.
754 * @param a the array to fill
755 * @param val the value to fill it with
757 public static void fill(short[] a
, short val
)
759 fill(a
, 0, a
.length
, val
);
763 * Fill a range of an array with a short value.
765 * @param a the array to fill
766 * @param fromIndex the index to fill from, inclusive
767 * @param toIndex the index to fill to, exclusive
768 * @param val the value to fill with
769 * @throws IllegalArgumentException if fromIndex > toIndex
770 * @throws ArrayIndexOutOfBoundsException if fromIndex < 0
771 * || toIndex > a.length
773 public static void fill(short[] a
, int fromIndex
, int toIndex
, short val
)
775 if (fromIndex
> toIndex
)
776 throw new IllegalArgumentException();
777 for (int i
= fromIndex
; i
< toIndex
; i
++)
782 * Fill an array with an int value.
784 * @param a the array to fill
785 * @param val the value to fill it with
787 public static void fill(int[] a
, int val
)
789 fill(a
, 0, a
.length
, val
);
793 * Fill a range of an array with an int value.
795 * @param a the array to fill
796 * @param fromIndex the index to fill from, inclusive
797 * @param toIndex the index to fill to, exclusive
798 * @param val the value to fill with
799 * @throws IllegalArgumentException if fromIndex > toIndex
800 * @throws ArrayIndexOutOfBoundsException if fromIndex < 0
801 * || toIndex > a.length
803 public static void fill(int[] a
, int fromIndex
, int toIndex
, int val
)
805 if (fromIndex
> toIndex
)
806 throw new IllegalArgumentException();
807 for (int i
= fromIndex
; i
< toIndex
; i
++)
812 * Fill an array with a long value.
814 * @param a the array to fill
815 * @param val the value to fill it with
817 public static void fill(long[] a
, long val
)
819 fill(a
, 0, a
.length
, val
);
823 * Fill a range of an array with a long value.
825 * @param a the array to fill
826 * @param fromIndex the index to fill from, inclusive
827 * @param toIndex the index to fill to, exclusive
828 * @param val the value to fill with
829 * @throws IllegalArgumentException if fromIndex > toIndex
830 * @throws ArrayIndexOutOfBoundsException if fromIndex < 0
831 * || toIndex > a.length
833 public static void fill(long[] a
, int fromIndex
, int toIndex
, long val
)
835 if (fromIndex
> toIndex
)
836 throw new IllegalArgumentException();
837 for (int i
= fromIndex
; i
< toIndex
; i
++)
842 * Fill an array with a float value.
844 * @param a the array to fill
845 * @param val the value to fill it with
847 public static void fill(float[] a
, float val
)
849 fill(a
, 0, a
.length
, val
);
853 * Fill a range of an array with a float value.
855 * @param a the array to fill
856 * @param fromIndex the index to fill from, inclusive
857 * @param toIndex the index to fill to, exclusive
858 * @param val the value to fill with
859 * @throws IllegalArgumentException if fromIndex > toIndex
860 * @throws ArrayIndexOutOfBoundsException if fromIndex < 0
861 * || toIndex > a.length
863 public static void fill(float[] a
, int fromIndex
, int toIndex
, float val
)
865 if (fromIndex
> toIndex
)
866 throw new IllegalArgumentException();
867 for (int i
= fromIndex
; i
< toIndex
; i
++)
872 * Fill an array with a double value.
874 * @param a the array to fill
875 * @param val the value to fill it with
877 public static void fill(double[] a
, double val
)
879 fill(a
, 0, a
.length
, val
);
883 * Fill a range of an array with a double value.
885 * @param a the array to fill
886 * @param fromIndex the index to fill from, inclusive
887 * @param toIndex the index to fill to, exclusive
888 * @param val the value to fill with
889 * @throws IllegalArgumentException if fromIndex > toIndex
890 * @throws ArrayIndexOutOfBoundsException if fromIndex < 0
891 * || toIndex > a.length
893 public static void fill(double[] a
, int fromIndex
, int toIndex
, double val
)
895 if (fromIndex
> toIndex
)
896 throw new IllegalArgumentException();
897 for (int i
= fromIndex
; i
< toIndex
; i
++)
902 * Fill an array with an Object value.
904 * @param a the array to fill
905 * @param val the value to fill it with
906 * @throws ClassCastException if val is not an instance of the element
909 public static void fill(Object
[] a
, Object val
)
911 fill(a
, 0, a
.length
, val
);
915 * Fill a range of an array with an Object value.
917 * @param a the array to fill
918 * @param fromIndex the index to fill from, inclusive
919 * @param toIndex the index to fill to, exclusive
920 * @param val the value to fill with
921 * @throws ClassCastException if val is not an instance of the element
923 * @throws IllegalArgumentException if fromIndex > toIndex
924 * @throws ArrayIndexOutOfBoundsException if fromIndex < 0
925 * || toIndex > a.length
927 public static void fill(Object
[] a
, int fromIndex
, int toIndex
, Object val
)
929 if (fromIndex
> toIndex
)
930 throw new IllegalArgumentException();
931 for (int i
= fromIndex
; i
< toIndex
; i
++)
937 // Thanks to Paul Fisher <rao@gnu.org> for finding this quicksort algorithm
938 // as specified by Sun and porting it to Java. The algorithm is an optimised
939 // quicksort, as described in Jon L. Bentley and M. Douglas McIlroy's
940 // "Engineering a Sort Function", Software-Practice and Experience, Vol.
941 // 23(11) P. 1249-1265 (November 1993). This algorithm gives n*log(n)
942 // performance on many arrays that would take quadratic time with a standard
946 * Performs a stable sort on the elements, arranging them according to their
949 * @param a the byte array to sort
951 public static void sort(byte[] a
)
953 qsort(a
, 0, a
.length
);
957 * Performs a stable sort on the elements, arranging them according to their
960 * @param a the byte array to sort
961 * @param fromIndex the first index to sort (inclusive)
962 * @param toIndex the last index to sort (exclusive)
963 * @throws IllegalArgumentException if fromIndex > toIndex
964 * @throws ArrayIndexOutOfBoundsException if fromIndex < 0
965 * || toIndex > a.length
967 public static void sort(byte[] a
, int fromIndex
, int toIndex
)
969 if (fromIndex
> toIndex
)
970 throw new IllegalArgumentException();
971 qsort(a
, fromIndex
, toIndex
- fromIndex
);
975 * Finds the index of the median of three array elements.
977 * @param a the first index
978 * @param b the second index
979 * @param c the third index
981 * @return the index (a, b, or c) which has the middle value of the three
983 private static int med3(int a
, int b
, int c
, byte[] d
)
986 ?
(d
[b
] < d
[c
] ? b
: d
[a
] < d
[c
] ? c
: a
)
987 : (d
[b
] > d
[c
] ? b
: d
[a
] > d
[c
] ? c
: a
));
991 * Swaps the elements at two locations of an array
993 * @param i the first index
994 * @param j the second index
997 private static void swap(int i
, int j
, byte[] a
)
1005 * Swaps two ranges of an array.
1007 * @param i the first range start
1008 * @param j the second range start
1009 * @param n the element count
1010 * @param a the array
1012 private static void vecswap(int i
, int j
, int n
, byte[] a
)
1014 for ( ; n
> 0; i
++, j
++, n
--)
1019 * Performs a recursive modified quicksort.
1021 * @param a the array to sort
1022 * @param from the start index (inclusive)
1023 * @param count the number of elements to sort
1025 private static void qsort(byte[] array
, int from
, int count
)
1027 // Use an insertion sort on small arrays.
1030 for (int i
= from
+ 1; i
< from
+ count
; i
++)
1031 for (int j
= i
; j
> 0 && array
[j
- 1] > array
[j
]; j
--)
1032 swap(j
, j
- 1, array
);
1036 // Determine a good median element.
1037 int mid
= count
/ 2;
1039 int hi
= from
+ count
- 1;
1042 { // big arrays, pseudomedian of 9
1044 lo
= med3(lo
, lo
+ s
, lo
+ 2 * s
, array
);
1045 mid
= med3(mid
- s
, mid
, mid
+ s
, array
);
1046 hi
= med3(hi
- 2 * s
, hi
- s
, hi
, array
);
1048 mid
= med3(lo
, mid
, hi
, array
);
1053 // Pull the median element out of the fray, and use it as a pivot.
1054 swap(from
, mid
, array
);
1056 c
= d
= from
+ count
- 1;
1058 // Repeatedly move b and c to each other, swapping elements so
1059 // that all elements before index b are less than the pivot, and all
1060 // elements after index c are greater than the pivot. a and b track
1061 // the elements equal to the pivot.
1064 while (b
<= c
&& (comp
= array
[b
] - array
[from
]) <= 0)
1073 while (c
>= b
&& (comp
= array
[c
] - array
[from
]) >= 0)
1089 // Swap pivot(s) back in place, the recurse on left and right sections.
1092 span
= Math
.min(a
- from
, b
- a
);
1093 vecswap(from
, b
- span
, span
, array
);
1095 span
= Math
.min(d
- c
, hi
- d
- 1);
1096 vecswap(b
, hi
- span
, span
, array
);
1100 qsort(array
, from
, span
);
1104 qsort(array
, hi
- span
, span
);
1108 * Performs a stable sort on the elements, arranging them according to their
1111 * @param a the char array to sort
1113 public static void sort(char[] a
)
1115 qsort(a
, 0, a
.length
);
1119 * Performs a stable sort on the elements, arranging them according to their
1122 * @param a the char array to sort
1123 * @param fromIndex the first index to sort (inclusive)
1124 * @param toIndex the last index to sort (exclusive)
1125 * @throws IllegalArgumentException if fromIndex > toIndex
1126 * @throws ArrayIndexOutOfBoundsException if fromIndex < 0
1127 * || toIndex > a.length
1129 public static void sort(char[] a
, int fromIndex
, int toIndex
)
1131 if (fromIndex
> toIndex
)
1132 throw new IllegalArgumentException();
1133 qsort(a
, fromIndex
, toIndex
- fromIndex
);
1137 * Finds the index of the median of three array elements.
1139 * @param a the first index
1140 * @param b the second index
1141 * @param c the third index
1142 * @param d the array
1143 * @return the index (a, b, or c) which has the middle value of the three
1145 private static int med3(int a
, int b
, int c
, char[] d
)
1148 ?
(d
[b
] < d
[c
] ? b
: d
[a
] < d
[c
] ? c
: a
)
1149 : (d
[b
] > d
[c
] ? b
: d
[a
] > d
[c
] ? c
: a
));
1153 * Swaps the elements at two locations of an array
1155 * @param i the first index
1156 * @param j the second index
1157 * @param a the array
1159 private static void swap(int i
, int j
, char[] a
)
1167 * Swaps two ranges of an array.
1169 * @param i the first range start
1170 * @param j the second range start
1171 * @param n the element count
1172 * @param a the array
1174 private static void vecswap(int i
, int j
, int n
, char[] a
)
1176 for ( ; n
> 0; i
++, j
++, n
--)
1181 * Performs a recursive modified quicksort.
1183 * @param a the array to sort
1184 * @param from the start index (inclusive)
1185 * @param count the number of elements to sort
1187 private static void qsort(char[] array
, int from
, int count
)
1189 // Use an insertion sort on small arrays.
1192 for (int i
= from
+ 1; i
< from
+ count
; i
++)
1193 for (int j
= i
; j
> 0 && array
[j
- 1] > array
[j
]; j
--)
1194 swap(j
, j
- 1, array
);
1198 // Determine a good median element.
1199 int mid
= count
/ 2;
1201 int hi
= from
+ count
- 1;
1204 { // big arrays, pseudomedian of 9
1206 lo
= med3(lo
, lo
+ s
, lo
+ 2 * s
, array
);
1207 mid
= med3(mid
- s
, mid
, mid
+ s
, array
);
1208 hi
= med3(hi
- 2 * s
, hi
- s
, hi
, array
);
1210 mid
= med3(lo
, mid
, hi
, array
);
1215 // Pull the median element out of the fray, and use it as a pivot.
1216 swap(from
, mid
, array
);
1218 c
= d
= from
+ count
- 1;
1220 // Repeatedly move b and c to each other, swapping elements so
1221 // that all elements before index b are less than the pivot, and all
1222 // elements after index c are greater than the pivot. a and b track
1223 // the elements equal to the pivot.
1226 while (b
<= c
&& (comp
= array
[b
] - array
[from
]) <= 0)
1235 while (c
>= b
&& (comp
= array
[c
] - array
[from
]) >= 0)
1251 // Swap pivot(s) back in place, the recurse on left and right sections.
1254 span
= Math
.min(a
- from
, b
- a
);
1255 vecswap(from
, b
- span
, span
, array
);
1257 span
= Math
.min(d
- c
, hi
- d
- 1);
1258 vecswap(b
, hi
- span
, span
, array
);
1262 qsort(array
, from
, span
);
1266 qsort(array
, hi
- span
, span
);
1270 * Performs a stable sort on the elements, arranging them according to their
1273 * @param a the short array to sort
1275 public static void sort(short[] a
)
1277 qsort(a
, 0, a
.length
);
1281 * Performs a stable sort on the elements, arranging them according to their
1284 * @param a the short array to sort
1285 * @param fromIndex the first index to sort (inclusive)
1286 * @param toIndex the last index to sort (exclusive)
1287 * @throws IllegalArgumentException if fromIndex > toIndex
1288 * @throws ArrayIndexOutOfBoundsException if fromIndex < 0
1289 * || toIndex > a.length
1291 public static void sort(short[] a
, int fromIndex
, int toIndex
)
1293 if (fromIndex
> toIndex
)
1294 throw new IllegalArgumentException();
1295 qsort(a
, fromIndex
, toIndex
- fromIndex
);
1299 * Finds the index of the median of three array elements.
1301 * @param a the first index
1302 * @param b the second index
1303 * @param c the third index
1304 * @param d the array
1305 * @return the index (a, b, or c) which has the middle value of the three
1307 private static int med3(int a
, int b
, int c
, short[] d
)
1310 ?
(d
[b
] < d
[c
] ? b
: d
[a
] < d
[c
] ? c
: a
)
1311 : (d
[b
] > d
[c
] ? b
: d
[a
] > d
[c
] ? c
: a
));
1315 * Swaps the elements at two locations of an array
1317 * @param i the first index
1318 * @param j the second index
1319 * @param a the array
1321 private static void swap(int i
, int j
, short[] a
)
1329 * Swaps two ranges of an array.
1331 * @param i the first range start
1332 * @param j the second range start
1333 * @param n the element count
1334 * @param a the array
1336 private static void vecswap(int i
, int j
, int n
, short[] a
)
1338 for ( ; n
> 0; i
++, j
++, n
--)
1343 * Performs a recursive modified quicksort.
1345 * @param a the array to sort
1346 * @param from the start index (inclusive)
1347 * @param count the number of elements to sort
1349 private static void qsort(short[] array
, int from
, int count
)
1351 // Use an insertion sort on small arrays.
1354 for (int i
= from
+ 1; i
< from
+ count
; i
++)
1355 for (int j
= i
; j
> 0 && array
[j
- 1] > array
[j
]; j
--)
1356 swap(j
, j
- 1, array
);
1360 // Determine a good median element.
1361 int mid
= count
/ 2;
1363 int hi
= from
+ count
- 1;
1366 { // big arrays, pseudomedian of 9
1368 lo
= med3(lo
, lo
+ s
, lo
+ 2 * s
, array
);
1369 mid
= med3(mid
- s
, mid
, mid
+ s
, array
);
1370 hi
= med3(hi
- 2 * s
, hi
- s
, hi
, array
);
1372 mid
= med3(lo
, mid
, hi
, array
);
1377 // Pull the median element out of the fray, and use it as a pivot.
1378 swap(from
, mid
, array
);
1380 c
= d
= from
+ count
- 1;
1382 // Repeatedly move b and c to each other, swapping elements so
1383 // that all elements before index b are less than the pivot, and all
1384 // elements after index c are greater than the pivot. a and b track
1385 // the elements equal to the pivot.
1388 while (b
<= c
&& (comp
= array
[b
] - array
[from
]) <= 0)
1397 while (c
>= b
&& (comp
= array
[c
] - array
[from
]) >= 0)
1413 // Swap pivot(s) back in place, the recurse on left and right sections.
1416 span
= Math
.min(a
- from
, b
- a
);
1417 vecswap(from
, b
- span
, span
, array
);
1419 span
= Math
.min(d
- c
, hi
- d
- 1);
1420 vecswap(b
, hi
- span
, span
, array
);
1424 qsort(array
, from
, span
);
1428 qsort(array
, hi
- span
, span
);
1432 * Performs a stable sort on the elements, arranging them according to their
1435 * @param a the int array to sort
1437 public static void sort(int[] a
)
1439 qsort(a
, 0, a
.length
);
1443 * Performs a stable sort on the elements, arranging them according to their
1446 * @param a the int array to sort
1447 * @param fromIndex the first index to sort (inclusive)
1448 * @param toIndex the last index to sort (exclusive)
1449 * @throws IllegalArgumentException if fromIndex > toIndex
1450 * @throws ArrayIndexOutOfBoundsException if fromIndex < 0
1451 * || toIndex > a.length
1453 public static void sort(int[] a
, int fromIndex
, int toIndex
)
1455 if (fromIndex
> toIndex
)
1456 throw new IllegalArgumentException();
1457 qsort(a
, fromIndex
, toIndex
- fromIndex
);
1461 * Finds the index of the median of three array elements.
1463 * @param a the first index
1464 * @param b the second index
1465 * @param c the third index
1466 * @param d the array
1467 * @return the index (a, b, or c) which has the middle value of the three
1469 private static int med3(int a
, int b
, int c
, int[] d
)
1472 ?
(d
[b
] < d
[c
] ? b
: d
[a
] < d
[c
] ? c
: a
)
1473 : (d
[b
] > d
[c
] ? b
: d
[a
] > d
[c
] ? c
: a
));
1477 * Swaps the elements at two locations of an array
1479 * @param i the first index
1480 * @param j the second index
1481 * @param a the array
1483 private static void swap(int i
, int j
, int[] a
)
1491 * Swaps two ranges of an array.
1493 * @param i the first range start
1494 * @param j the second range start
1495 * @param n the element count
1496 * @param a the array
1498 private static void vecswap(int i
, int j
, int n
, int[] a
)
1500 for ( ; n
> 0; i
++, j
++, n
--)
1505 * Compares two integers in natural order, since a - b is inadequate.
1507 * @param a the first int
1508 * @param b the second int
1509 * @return < 0, 0, or > 0 accorting to the comparison
1511 private static int compare(int a
, int b
)
1513 return a
< b ?
-1 : a
== b ?
0 : 1;
1517 * Performs a recursive modified quicksort.
1519 * @param a the array to sort
1520 * @param from the start index (inclusive)
1521 * @param count the number of elements to sort
1523 private static void qsort(int[] array
, int from
, int count
)
1525 // Use an insertion sort on small arrays.
1528 for (int i
= from
+ 1; i
< from
+ count
; i
++)
1529 for (int j
= i
; j
> 0 && array
[j
- 1] > array
[j
]; j
--)
1530 swap(j
, j
- 1, array
);
1534 // Determine a good median element.
1535 int mid
= count
/ 2;
1537 int hi
= from
+ count
- 1;
1540 { // big arrays, pseudomedian of 9
1542 lo
= med3(lo
, lo
+ s
, lo
+ 2 * s
, array
);
1543 mid
= med3(mid
- s
, mid
, mid
+ s
, array
);
1544 hi
= med3(hi
- 2 * s
, hi
- s
, hi
, array
);
1546 mid
= med3(lo
, mid
, hi
, array
);
1551 // Pull the median element out of the fray, and use it as a pivot.
1552 swap(from
, mid
, array
);
1554 c
= d
= from
+ count
- 1;
1556 // Repeatedly move b and c to each other, swapping elements so
1557 // that all elements before index b are less than the pivot, and all
1558 // elements after index c are greater than the pivot. a and b track
1559 // the elements equal to the pivot.
1562 while (b
<= c
&& (comp
= compare(array
[b
], array
[from
])) <= 0)
1571 while (c
>= b
&& (comp
= compare(array
[c
], array
[from
])) >= 0)
1587 // Swap pivot(s) back in place, the recurse on left and right sections.
1590 span
= Math
.min(a
- from
, b
- a
);
1591 vecswap(from
, b
- span
, span
, array
);
1593 span
= Math
.min(d
- c
, hi
- d
- 1);
1594 vecswap(b
, hi
- span
, span
, array
);
1598 qsort(array
, from
, span
);
1602 qsort(array
, hi
- span
, span
);
1606 * Performs a stable sort on the elements, arranging them according to their
1609 * @param a the long array to sort
1611 public static void sort(long[] a
)
1613 qsort(a
, 0, a
.length
);
1617 * Performs a stable sort on the elements, arranging them according to their
1620 * @param a the long array to sort
1621 * @param fromIndex the first index to sort (inclusive)
1622 * @param toIndex the last index to sort (exclusive)
1623 * @throws IllegalArgumentException if fromIndex > toIndex
1624 * @throws ArrayIndexOutOfBoundsException if fromIndex < 0
1625 * || toIndex > a.length
1627 public static void sort(long[] a
, int fromIndex
, int toIndex
)
1629 if (fromIndex
> toIndex
)
1630 throw new IllegalArgumentException();
1631 qsort(a
, fromIndex
, toIndex
- fromIndex
);
1635 * Finds the index of the median of three array elements.
1637 * @param a the first index
1638 * @param b the second index
1639 * @param c the third index
1640 * @param d the array
1641 * @return the index (a, b, or c) which has the middle value of the three
1643 private static int med3(int a
, int b
, int c
, long[] d
)
1646 ?
(d
[b
] < d
[c
] ? b
: d
[a
] < d
[c
] ? c
: a
)
1647 : (d
[b
] > d
[c
] ? b
: d
[a
] > d
[c
] ? c
: a
));
1651 * Swaps the elements at two locations of an array
1653 * @param i the first index
1654 * @param j the second index
1655 * @param a the array
1657 private static void swap(int i
, int j
, long[] a
)
1665 * Swaps two ranges of an array.
1667 * @param i the first range start
1668 * @param j the second range start
1669 * @param n the element count
1670 * @param a the array
1672 private static void vecswap(int i
, int j
, int n
, long[] a
)
1674 for ( ; n
> 0; i
++, j
++, n
--)
1679 * Compares two longs in natural order, since a - b is inadequate.
1681 * @param a the first long
1682 * @param b the second long
1683 * @return < 0, 0, or > 0 accorting to the comparison
1685 private static int compare(long a
, long b
)
1687 return a
< b ?
-1 : a
== b ?
0 : 1;
1691 * Performs a recursive modified quicksort.
1693 * @param a the array to sort
1694 * @param from the start index (inclusive)
1695 * @param count the number of elements to sort
1697 private static void qsort(long[] array
, int from
, int count
)
1699 // Use an insertion sort on small arrays.
1702 for (int i
= from
+ 1; i
< from
+ count
; i
++)
1703 for (int j
= i
; j
> 0 && array
[j
- 1] > array
[j
]; j
--)
1704 swap(j
, j
- 1, array
);
1708 // Determine a good median element.
1709 int mid
= count
/ 2;
1711 int hi
= from
+ count
- 1;
1714 { // big arrays, pseudomedian of 9
1716 lo
= med3(lo
, lo
+ s
, lo
+ 2 * s
, array
);
1717 mid
= med3(mid
- s
, mid
, mid
+ s
, array
);
1718 hi
= med3(hi
- 2 * s
, hi
- s
, hi
, array
);
1720 mid
= med3(lo
, mid
, hi
, array
);
1725 // Pull the median element out of the fray, and use it as a pivot.
1726 swap(from
, mid
, array
);
1728 c
= d
= from
+ count
- 1;
1730 // Repeatedly move b and c to each other, swapping elements so
1731 // that all elements before index b are less than the pivot, and all
1732 // elements after index c are greater than the pivot. a and b track
1733 // the elements equal to the pivot.
1736 while (b
<= c
&& (comp
= compare(array
[b
], array
[from
])) <= 0)
1745 while (c
>= b
&& (comp
= compare(array
[c
], array
[from
])) >= 0)
1761 // Swap pivot(s) back in place, the recurse on left and right sections.
1764 span
= Math
.min(a
- from
, b
- a
);
1765 vecswap(from
, b
- span
, span
, array
);
1767 span
= Math
.min(d
- c
, hi
- d
- 1);
1768 vecswap(b
, hi
- span
, span
, array
);
1772 qsort(array
, from
, span
);
1776 qsort(array
, hi
- span
, span
);
1780 * Performs a stable sort on the elements, arranging them according to their
1783 * @param a the float array to sort
1785 public static void sort(float[] a
)
1787 qsort(a
, 0, a
.length
);
1791 * Performs a stable sort on the elements, arranging them according to their
1794 * @param a the float array to sort
1795 * @param fromIndex the first index to sort (inclusive)
1796 * @param toIndex the last index to sort (exclusive)
1797 * @throws IllegalArgumentException if fromIndex > toIndex
1798 * @throws ArrayIndexOutOfBoundsException if fromIndex < 0
1799 * || toIndex > a.length
1801 public static void sort(float[] a
, int fromIndex
, int toIndex
)
1803 if (fromIndex
> toIndex
)
1804 throw new IllegalArgumentException();
1805 qsort(a
, fromIndex
, toIndex
- fromIndex
);
1809 * Finds the index of the median of three array elements.
1811 * @param a the first index
1812 * @param b the second index
1813 * @param c the third index
1814 * @param d the array
1815 * @return the index (a, b, or c) which has the middle value of the three
1817 private static int med3(int a
, int b
, int c
, float[] d
)
1819 return (Float
.compare(d
[a
], d
[b
]) < 0
1820 ?
(Float
.compare(d
[b
], d
[c
]) < 0 ? b
1821 : Float
.compare(d
[a
], d
[c
]) < 0 ? c
: a
)
1822 : (Float
.compare(d
[b
], d
[c
]) > 0 ? b
1823 : Float
.compare(d
[a
], d
[c
]) > 0 ? c
: a
));
1827 * Swaps the elements at two locations of an array
1829 * @param i the first index
1830 * @param j the second index
1831 * @param a the array
1833 private static void swap(int i
, int j
, float[] a
)
1841 * Swaps two ranges of an array.
1843 * @param i the first range start
1844 * @param j the second range start
1845 * @param n the element count
1846 * @param a the array
1848 private static void vecswap(int i
, int j
, int n
, float[] a
)
1850 for ( ; n
> 0; i
++, j
++, n
--)
1855 * Performs a recursive modified quicksort.
1857 * @param a the array to sort
1858 * @param from the start index (inclusive)
1859 * @param count the number of elements to sort
1861 private static void qsort(float[] array
, int from
, int count
)
1863 // Use an insertion sort on small arrays.
1866 for (int i
= from
+ 1; i
< from
+ count
; i
++)
1868 j
> 0 && Float
.compare(array
[j
- 1], array
[j
]) > 0;
1871 swap(j
, j
- 1, array
);
1876 // Determine a good median element.
1877 int mid
= count
/ 2;
1879 int hi
= from
+ count
- 1;
1882 { // big arrays, pseudomedian of 9
1884 lo
= med3(lo
, lo
+ s
, lo
+ 2 * s
, array
);
1885 mid
= med3(mid
- s
, mid
, mid
+ s
, array
);
1886 hi
= med3(hi
- 2 * s
, hi
- s
, hi
, array
);
1888 mid
= med3(lo
, mid
, hi
, array
);
1893 // Pull the median element out of the fray, and use it as a pivot.
1894 swap(from
, mid
, array
);
1896 c
= d
= from
+ count
- 1;
1898 // Repeatedly move b and c to each other, swapping elements so
1899 // that all elements before index b are less than the pivot, and all
1900 // elements after index c are greater than the pivot. a and b track
1901 // the elements equal to the pivot.
1904 while (b
<= c
&& (comp
= Float
.compare(array
[b
], array
[from
])) <= 0)
1913 while (c
>= b
&& (comp
= Float
.compare(array
[c
], array
[from
])) >= 0)
1929 // Swap pivot(s) back in place, the recurse on left and right sections.
1932 span
= Math
.min(a
- from
, b
- a
);
1933 vecswap(from
, b
- span
, span
, array
);
1935 span
= Math
.min(d
- c
, hi
- d
- 1);
1936 vecswap(b
, hi
- span
, span
, array
);
1940 qsort(array
, from
, span
);
1944 qsort(array
, hi
- span
, span
);
1948 * Performs a stable sort on the elements, arranging them according to their
1951 * @param a the double array to sort
1953 public static void sort(double[] a
)
1955 qsort(a
, 0, a
.length
);
1959 * Performs a stable sort on the elements, arranging them according to their
1962 * @param a the double array to sort
1963 * @param fromIndex the first index to sort (inclusive)
1964 * @param toIndex the last index to sort (exclusive)
1965 * @throws IllegalArgumentException if fromIndex > toIndex
1966 * @throws ArrayIndexOutOfBoundsException if fromIndex < 0
1967 * || toIndex > a.length
1969 public static void sort(double[] a
, int fromIndex
, int toIndex
)
1971 if (fromIndex
> toIndex
)
1972 throw new IllegalArgumentException();
1973 qsort(a
, fromIndex
, toIndex
- fromIndex
);
1977 * Finds the index of the median of three array elements.
1979 * @param a the first index
1980 * @param b the second index
1981 * @param c the third index
1982 * @param d the array
1983 * @return the index (a, b, or c) which has the middle value of the three
1985 private static int med3(int a
, int b
, int c
, double[] d
)
1987 return (Double
.compare(d
[a
], d
[b
]) < 0
1988 ?
(Double
.compare(d
[b
], d
[c
]) < 0 ? b
1989 : Double
.compare(d
[a
], d
[c
]) < 0 ? c
: a
)
1990 : (Double
.compare(d
[b
], d
[c
]) > 0 ? b
1991 : Double
.compare(d
[a
], d
[c
]) > 0 ? c
: a
));
1995 * Swaps the elements at two locations of an array
1997 * @param i the first index
1998 * @param j the second index
1999 * @param a the array
2001 private static void swap(int i
, int j
, double[] a
)
2009 * Swaps two ranges of an array.
2011 * @param i the first range start
2012 * @param j the second range start
2013 * @param n the element count
2014 * @param a the array
2016 private static void vecswap(int i
, int j
, int n
, double[] a
)
2018 for ( ; n
> 0; i
++, j
++, n
--)
2023 * Performs a recursive modified quicksort.
2025 * @param a the array to sort
2026 * @param from the start index (inclusive)
2027 * @param count the number of elements to sort
2029 private static void qsort(double[] array
, int from
, int count
)
2031 // Use an insertion sort on small arrays.
2034 for (int i
= from
+ 1; i
< from
+ count
; i
++)
2036 j
> 0 && Double
.compare(array
[j
- 1], array
[j
]) > 0;
2039 swap(j
, j
- 1, array
);
2044 // Determine a good median element.
2045 int mid
= count
/ 2;
2047 int hi
= from
+ count
- 1;
2050 { // big arrays, pseudomedian of 9
2052 lo
= med3(lo
, lo
+ s
, lo
+ 2 * s
, array
);
2053 mid
= med3(mid
- s
, mid
, mid
+ s
, array
);
2054 hi
= med3(hi
- 2 * s
, hi
- s
, hi
, array
);
2056 mid
= med3(lo
, mid
, hi
, array
);
2061 // Pull the median element out of the fray, and use it as a pivot.
2062 swap(from
, mid
, array
);
2064 c
= d
= from
+ count
- 1;
2066 // Repeatedly move b and c to each other, swapping elements so
2067 // that all elements before index b are less than the pivot, and all
2068 // elements after index c are greater than the pivot. a and b track
2069 // the elements equal to the pivot.
2072 while (b
<= c
&& (comp
= Double
.compare(array
[b
], array
[from
])) <= 0)
2081 while (c
>= b
&& (comp
= Double
.compare(array
[c
], array
[from
])) >= 0)
2097 // Swap pivot(s) back in place, the recurse on left and right sections.
2100 span
= Math
.min(a
- from
, b
- a
);
2101 vecswap(from
, b
- span
, span
, array
);
2103 span
= Math
.min(d
- c
, hi
- d
- 1);
2104 vecswap(b
, hi
- span
, span
, array
);
2108 qsort(array
, from
, span
);
2112 qsort(array
, hi
- span
, span
);
2116 * Sort an array of Objects according to their natural ordering. The sort is
2117 * guaranteed to be stable, that is, equal elements will not be reordered.
2118 * The sort algorithm is a mergesort with the merge omitted if the last
2119 * element of one half comes before the first element of the other half. This
2120 * algorithm gives guaranteed O(n*log(n)) time, at the expense of making a
2121 * copy of the array.
2123 * @param a the array to be sorted
2124 * @throws ClassCastException if any two elements are not mutually
2126 * @throws NullPointerException if an element is null (since
2127 * null.compareTo cannot work)
2130 public static void sort(Object
[] a
)
2132 sort(a
, 0, a
.length
, null);
2136 * Sort an array of Objects according to a Comparator. The sort is
2137 * guaranteed to be stable, that is, equal elements will not be reordered.
2138 * The sort algorithm is a mergesort with the merge omitted if the last
2139 * element of one half comes before the first element of the other half. This
2140 * algorithm gives guaranteed O(n*log(n)) time, at the expense of making a
2141 * copy of the array.
2143 * @param a the array to be sorted
2144 * @param c a Comparator to use in sorting the array; or null to indicate
2145 * the elements' natural order
2146 * @throws ClassCastException if any two elements are not mutually
2147 * comparable by the Comparator provided
2148 * @throws NullPointerException if a null element is compared with natural
2149 * ordering (only possible when c is null)
2151 public static void sort(Object
[] a
, Comparator c
)
2153 sort(a
, 0, a
.length
, c
);
2157 * Sort an array of Objects according to their natural ordering. The sort is
2158 * guaranteed to be stable, that is, equal elements will not be reordered.
2159 * The sort algorithm is a mergesort with the merge omitted if the last
2160 * element of one half comes before the first element of the other half. This
2161 * algorithm gives guaranteed O(n*log(n)) time, at the expense of making a
2162 * copy of the array.
2164 * @param a the array to be sorted
2165 * @param fromIndex the index of the first element to be sorted
2166 * @param toIndex the index of the last element to be sorted plus one
2167 * @throws ClassCastException if any two elements are not mutually
2169 * @throws NullPointerException if an element is null (since
2170 * null.compareTo cannot work)
2171 * @throws ArrayIndexOutOfBoundsException if fromIndex and toIndex
2173 * @throws IllegalArgumentException if fromIndex > toIndex
2175 public static void sort(Object
[] a
, int fromIndex
, int toIndex
)
2177 sort(a
, fromIndex
, toIndex
, null);
2181 * Sort an array of Objects according to a Comparator. The sort is
2182 * guaranteed to be stable, that is, equal elements will not be reordered.
2183 * The sort algorithm is a mergesort with the merge omitted if the last
2184 * element of one half comes before the first element of the other half. This
2185 * algorithm gives guaranteed O(n*log(n)) time, at the expense of making a
2186 * copy of the array.
2188 * @param a the array to be sorted
2189 * @param fromIndex the index of the first element to be sorted
2190 * @param toIndex the index of the last element to be sorted plus one
2191 * @param c a Comparator to use in sorting the array; or null to indicate
2192 * the elements' natural order
2193 * @throws ClassCastException if any two elements are not mutually
2194 * comparable by the Comparator provided
2195 * @throws ArrayIndexOutOfBoundsException if fromIndex and toIndex
2197 * @throws IllegalArgumentException if fromIndex > toIndex
2198 * @throws NullPointerException if a null element is compared with natural
2199 * ordering (only possible when c is null)
2201 public static void sort(Object
[] a
, int fromIndex
, int toIndex
, Comparator c
)
2203 if (fromIndex
> toIndex
)
2204 throw new IllegalArgumentException("fromIndex " + fromIndex
2205 + " > toIndex " + toIndex
);
2207 // In general, the code attempts to be simple rather than fast, the
2208 // idea being that a good optimising JIT will be able to optimise it
2209 // better than I can, and if I try it will make it more confusing for
2210 // the JIT. First presort the array in chunks of length 6 with insertion
2211 // sort. A mergesort would give too much overhead for this length.
2212 for (int chunk
= fromIndex
; chunk
< toIndex
; chunk
+= 6)
2214 int end
= Math
.min(chunk
+ 6, toIndex
);
2215 for (int i
= chunk
+ 1; i
< end
; i
++)
2217 if (Collections
.compare(a
[i
- 1], a
[i
], c
) > 0)
2219 // not already sorted
2228 && Collections
.compare(a
[j
- 1], elem
, c
) > 0);
2234 int len
= toIndex
- fromIndex
;
2235 // If length is smaller or equal 6 we are done.
2240 Object
[] dest
= new Object
[len
];
2241 Object
[] t
= null; // t is used for swapping src and dest
2243 // The difference of the fromIndex of the src and dest array.
2244 int srcDestDiff
= -fromIndex
;
2246 // The merges are done in this loop
2247 for (int size
= 6; size
< len
; size
<<= 1)
2249 for (int start
= fromIndex
; start
< toIndex
; start
+= size
<< 1)
2251 // mid is the start of the second sublist;
2252 // end the start of the next sublist (or end of array).
2253 int mid
= start
+ size
;
2254 int end
= Math
.min(toIndex
, mid
+ size
);
2256 // The second list is empty or the elements are already in
2257 // order - no need to merge
2259 || Collections
.compare(src
[mid
- 1], src
[mid
], c
) <= 0)
2261 System
.arraycopy(src
, start
,
2262 dest
, start
+ srcDestDiff
, end
- start
);
2264 // The two halves just need swapping - no need to merge
2266 else if (Collections
.compare(src
[start
], src
[end
- 1], c
) > 0)
2268 System
.arraycopy(src
, start
,
2269 dest
, end
- size
+ srcDestDiff
, size
);
2270 System
.arraycopy(src
, mid
,
2271 dest
, start
+ srcDestDiff
, end
- mid
);
2276 // Declare a lot of variables to save repeating
2277 // calculations. Hopefully a decent JIT will put these
2278 // in registers and make this fast
2281 int i
= start
+ srcDestDiff
;
2283 // The main merge loop; terminates as soon as either
2285 while (p1
< mid
&& p2
< end
)
2288 src
[(Collections
.compare(src
[p1
], src
[p2
], c
) <= 0
2292 // Finish up by copying the remainder of whichever half
2295 System
.arraycopy(src
, p1
, dest
, i
, mid
- p1
);
2297 System
.arraycopy(src
, p2
, dest
, i
, end
- p2
);
2300 // swap src and dest ready for the next merge
2304 fromIndex
+= srcDestDiff
;
2305 toIndex
+= srcDestDiff
;
2306 srcDestDiff
= -srcDestDiff
;
2309 // make sure the result ends up back in the right place. Note
2310 // that src and dest may have been swapped above, so src
2311 // contains the sorted array.
2314 // Note that fromIndex == 0.
2315 System
.arraycopy(src
, 0, a
, srcDestDiff
, toIndex
);
2320 * Returns a list "view" of the specified array. This method is intended to
2321 * make it easy to use the Collections API with existing array-based APIs and
2322 * programs. Changes in the list or the array show up in both places. The
2323 * list does not support element addition or removal, but does permit
2324 * value modification. The returned list implements both Serializable and
2327 * @param a the array to return a view of
2328 * @return a fixed-size list, changes to which "write through" to the array
2331 * @see Arrays.ArrayList
2333 public static List
asList(final Object
[] a
)
2335 return new Arrays
.ArrayList(a
);
2339 * Inner class used by {@link #asList(Object[])} to provide a list interface
2340 * to an array. The name, though it clashes with java.util.ArrayList, is
2341 * Sun's choice for Serialization purposes. Element addition and removal
2342 * is prohibited, but values can be modified.
2344 * @author Eric Blake <ebb9@email.byu.edu>
2345 * @status updated to 1.4
2347 private static final class ArrayList
extends AbstractList
2348 implements Serializable
, RandomAccess
2350 // We override the necessary methods, plus others which will be much
2351 // more efficient with direct iteration rather than relying on iterator().
2354 * Compatible with JDK 1.4.
2356 private static final long serialVersionUID
= -2764017481108945198L;
2359 * The array we are viewing.
2362 private final Object
[] a
;
2365 * Construct a list view of the array.
2366 * @param a the array to view
2367 * @throws NullPointerException if a is null
2369 ArrayList(Object
[] a
)
2371 // We have to explicitly check.
2373 throw new NullPointerException();
2377 public Object
get(int index
)
2387 public Object
set(int index
, Object element
)
2389 Object old
= a
[index
];
2394 public boolean contains(Object o
)
2396 return lastIndexOf(o
) >= 0;
2399 public int indexOf(Object o
)
2401 int size
= a
.length
;
2402 for (int i
= 0; i
< size
; i
++)
2403 if (this.equals(o
, a
[i
]))
2408 public int lastIndexOf(Object o
)
2412 if (this.equals(o
, a
[i
]))
2417 public Object
[] toArray()
2419 return (Object
[]) a
.clone();
2422 public Object
[] toArray(Object
[] array
)
2424 int size
= a
.length
;
2425 if (array
.length
< size
)
2427 Array
.newInstance(array
.getClass().getComponentType(), size
);
2428 else if (array
.length
> size
)
2431 System
.arraycopy(a
, 0, array
, 0, size
);