1 /*
2 * Copyright (c) 1997, 2011, Oracle and/or its affiliates. All rights reserved.
3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
4 *
5 * This code is free software; you can redistribute it and/or modify it
6 * under the terms of the GNU General Public License version 2 only, as
7 * published by the Free Software Foundation. Oracle designates this
8 * particular file as subject to the "Classpath" exception as provided
9 * by Oracle in the LICENSE file that accompanied this code.
10 *
11 * This code is distributed in the hope that it will be useful, but WITHOUT
12 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
14 * version 2 for more details (a copy is included in the LICENSE file that
15 * accompanied this code).
16 *
17 * You should have received a copy of the GNU General Public License version
18 * 2 along with this work; if not, write to the Free Software Foundation,
19 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
20 *
21 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
22 * or visit www.oracle.com if you need additional information or have any
543 rangeCheck(a.length, fromIndex, toIndex);
544 Object[] aux = copyOfRange(a, fromIndex, toIndex);
545 mergeSort(aux, a, fromIndex, toIndex, -fromIndex);
546 }
547
548 /**
549 * Tuning parameter: list size at or below which insertion sort will be
550 * used in preference to mergesort.
551 * To be removed in a future release.
552 */
553 private static final int INSERTIONSORT_THRESHOLD = 7;
554
555 /**
556 * Src is the source array that starts at index 0
557 * Dest is the (possibly larger) array destination with a possible offset
558 * low is the index in dest to start sorting
559 * high is the end index in dest to end sorting
560 * off is the offset to generate corresponding low, high in src
561 * To be removed in a future release.
562 */
563 @SuppressWarnings({ "unchecked", "rawtypes" })
564 private static void mergeSort(Object[] src,
565 Object[] dest,
566 int low,
567 int high,
568 int off) {
569 int length = high - low;
570
571 // Insertion sort on smallest arrays
572 if (length < INSERTIONSORT_THRESHOLD) {
573 for (int i=low; i<high; i++)
574 for (int j=i; j>low &&
575 ((Comparable) dest[j-1]).compareTo(dest[j])>0; j--)
576 swap(dest, j, j-1);
577 return;
578 }
579
580 // Recursively sort halves of dest into src
581 int destLow = low;
582 int destHigh = high;
583 low += off;
730
731 /** To be removed in a future release. */
732 private static <T> void legacyMergeSort(T[] a, int fromIndex, int toIndex,
733 Comparator<? super T> c) {
734 rangeCheck(a.length, fromIndex, toIndex);
735 T[] aux = copyOfRange(a, fromIndex, toIndex);
736 if (c==null)
737 mergeSort(aux, a, fromIndex, toIndex, -fromIndex);
738 else
739 mergeSort(aux, a, fromIndex, toIndex, -fromIndex, c);
740 }
741
742 /**
743 * Src is the source array that starts at index 0
744 * Dest is the (possibly larger) array destination with a possible offset
745 * low is the index in dest to start sorting
746 * high is the end index in dest to end sorting
747 * off is the offset into src corresponding to low in dest
748 * To be removed in a future release.
749 */
750 @SuppressWarnings({ "rawtypes", "unchecked" })
751 private static void mergeSort(Object[] src,
752 Object[] dest,
753 int low, int high, int off,
754 Comparator c) {
755 int length = high - low;
756
757 // Insertion sort on smallest arrays
758 if (length < INSERTIONSORT_THRESHOLD) {
759 for (int i=low; i<high; i++)
760 for (int j=i; j>low && c.compare(dest[j-1], dest[j])>0; j--)
761 swap(dest, j, j-1);
762 return;
763 }
764
765 // Recursively sort halves of dest into src
766 int destLow = low;
767 int destHigh = high;
768 low += off;
769 high += off;
770 int mid = (low + high) >>> 1;
2815
2816 // Misc
2817
2818 /**
2819 * Returns a fixed-size list backed by the specified array. (Changes to
2820 * the returned list "write through" to the array.) This method acts
2821 * as bridge between array-based and collection-based APIs, in
2822 * combination with {@link Collection#toArray}. The returned list is
2823 * serializable and implements {@link RandomAccess}.
2824 *
2825 * <p>This method also provides a convenient way to create a fixed-size
2826 * list initialized to contain several elements:
2827 * <pre>
2828 * List<String> stooges = Arrays.asList("Larry", "Moe", "Curly");
2829 * </pre>
2830 *
2831 * @param a the array by which the list will be backed
2832 * @return a list view of the specified array
2833 */
2834 @SafeVarargs
2835 public static <T> List<T> asList(T... a) {
2836 return new ArrayList<>(a);
2837 }
2838
2839 /**
2840 * @serial include
2841 */
2842 private static class ArrayList<E> extends AbstractList<E>
2843 implements RandomAccess, java.io.Serializable
2844 {
2845 private static final long serialVersionUID = -2764017481108945198L;
2846 private final E[] a;
2847
2848 ArrayList(E[] array) {
2849 if (array==null)
2850 throw new NullPointerException();
2851 a = array;
2852 }
2853
2854 public int size() {
|
1 /*
2 * Copyright (c) 1997, 2012, Oracle and/or its affiliates. All rights reserved.
3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
4 *
5 * This code is free software; you can redistribute it and/or modify it
6 * under the terms of the GNU General Public License version 2 only, as
7 * published by the Free Software Foundation. Oracle designates this
8 * particular file as subject to the "Classpath" exception as provided
9 * by Oracle in the LICENSE file that accompanied this code.
10 *
11 * This code is distributed in the hope that it will be useful, but WITHOUT
12 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
14 * version 2 for more details (a copy is included in the LICENSE file that
15 * accompanied this code).
16 *
17 * You should have received a copy of the GNU General Public License version
18 * 2 along with this work; if not, write to the Free Software Foundation,
19 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
20 *
21 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
22 * or visit www.oracle.com if you need additional information or have any
543 rangeCheck(a.length, fromIndex, toIndex);
544 Object[] aux = copyOfRange(a, fromIndex, toIndex);
545 mergeSort(aux, a, fromIndex, toIndex, -fromIndex);
546 }
547
548 /**
549 * Tuning parameter: list size at or below which insertion sort will be
550 * used in preference to mergesort.
551 * To be removed in a future release.
552 */
553 private static final int INSERTIONSORT_THRESHOLD = 7;
554
555 /**
556 * Src is the source array that starts at index 0
557 * Dest is the (possibly larger) array destination with a possible offset
558 * low is the index in dest to start sorting
559 * high is the end index in dest to end sorting
560 * off is the offset to generate corresponding low, high in src
561 * To be removed in a future release.
562 */
563 @SuppressWarnings({"unchecked", "rawtypes"})
564 private static void mergeSort(Object[] src,
565 Object[] dest,
566 int low,
567 int high,
568 int off) {
569 int length = high - low;
570
571 // Insertion sort on smallest arrays
572 if (length < INSERTIONSORT_THRESHOLD) {
573 for (int i=low; i<high; i++)
574 for (int j=i; j>low &&
575 ((Comparable) dest[j-1]).compareTo(dest[j])>0; j--)
576 swap(dest, j, j-1);
577 return;
578 }
579
580 // Recursively sort halves of dest into src
581 int destLow = low;
582 int destHigh = high;
583 low += off;
730
731 /** To be removed in a future release. */
732 private static <T> void legacyMergeSort(T[] a, int fromIndex, int toIndex,
733 Comparator<? super T> c) {
734 rangeCheck(a.length, fromIndex, toIndex);
735 T[] aux = copyOfRange(a, fromIndex, toIndex);
736 if (c==null)
737 mergeSort(aux, a, fromIndex, toIndex, -fromIndex);
738 else
739 mergeSort(aux, a, fromIndex, toIndex, -fromIndex, c);
740 }
741
742 /**
743 * Src is the source array that starts at index 0
744 * Dest is the (possibly larger) array destination with a possible offset
745 * low is the index in dest to start sorting
746 * high is the end index in dest to end sorting
747 * off is the offset into src corresponding to low in dest
748 * To be removed in a future release.
749 */
750 @SuppressWarnings({"rawtypes", "unchecked"})
751 private static void mergeSort(Object[] src,
752 Object[] dest,
753 int low, int high, int off,
754 Comparator c) {
755 int length = high - low;
756
757 // Insertion sort on smallest arrays
758 if (length < INSERTIONSORT_THRESHOLD) {
759 for (int i=low; i<high; i++)
760 for (int j=i; j>low && c.compare(dest[j-1], dest[j])>0; j--)
761 swap(dest, j, j-1);
762 return;
763 }
764
765 // Recursively sort halves of dest into src
766 int destLow = low;
767 int destHigh = high;
768 low += off;
769 high += off;
770 int mid = (low + high) >>> 1;
2815
2816 // Misc
2817
2818 /**
2819 * Returns a fixed-size list backed by the specified array. (Changes to
2820 * the returned list "write through" to the array.) This method acts
2821 * as bridge between array-based and collection-based APIs, in
2822 * combination with {@link Collection#toArray}. The returned list is
2823 * serializable and implements {@link RandomAccess}.
2824 *
2825 * <p>This method also provides a convenient way to create a fixed-size
2826 * list initialized to contain several elements:
2827 * <pre>
2828 * List<String> stooges = Arrays.asList("Larry", "Moe", "Curly");
2829 * </pre>
2830 *
2831 * @param a the array by which the list will be backed
2832 * @return a list view of the specified array
2833 */
2834 @SafeVarargs
2835 @SuppressWarnings("varargs")
2836 public static <T> List<T> asList(T... a) {
2837 return new ArrayList<>(a);
2838 }
2839
2840 /**
2841 * @serial include
2842 */
2843 private static class ArrayList<E> extends AbstractList<E>
2844 implements RandomAccess, java.io.Serializable
2845 {
2846 private static final long serialVersionUID = -2764017481108945198L;
2847 private final E[] a;
2848
2849 ArrayList(E[] array) {
2850 if (array==null)
2851 throw new NullPointerException();
2852 a = array;
2853 }
2854
2855 public int size() {
|