1 /*
2  * Copyright (c) 2002, 2014, 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.
8  *
9  * This code is distributed in the hope that it will be useful, but WITHOUT
10  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
11  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
12  * version 2 for more details (a copy is included in the LICENSE file that
13  * accompanied this code).
14  *
15  * You should have received a copy of the GNU General Public License version
16  * 2 along with this work; if not, write to the Free Software Foundation,
17  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
18  *
19  * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
20  * or visit www.oracle.com if you need additional information or have any
21  * questions.
22  */
23 
24 /*
25  * @test
26  * @bug 4726380 8037097
27  * @summary Check that different sorts give equivalent results.
28  * @run testng Correct
29  * @key randomness
30  */
31 
32 package test.java.util.Arrays;
33 
34 import java.util.*;
35 
36 import org.testng.annotations.Test;
37 import org.testng.annotations.DataProvider;
38 import static org.testng.Assert.fail;
39 import static org.testng.Assert.assertEquals;
40 
41 import android.platform.test.annotations.LargeTest;
42 
43 public class Correct {
44 
45     static final Random rnd = new Random();
46     static final int ITERATIONS = 1000;
47     static final int TEST_SIZE = 1000;
48 
49     @Test
testDefaultSort()50     public void testDefaultSort() {
51         for (int i=0; i<ITERATIONS; i++) {
52             int size = rnd.nextInt(TEST_SIZE) + 1;
53             Integer[] array1 = getIntegerArray(size);
54             Integer[] array2 = Arrays.copyOf(array1, array1.length);
55             Arrays.sort(array1, array1.length/3, array1.length/2);
56             stupidSort(array2, array2.length/3, array2.length/2);
57             assertEquals(array1, array2, "Arrays did not match. size=" + size);
58         }
59     }
60 
61     @LargeTest
62     @Test(dataProvider = "Comparators")
testComparatorSort(Comparator<Integer> comparator)63     public void testComparatorSort(Comparator<Integer> comparator) {
64         for (int i=0; i<ITERATIONS; i++) {
65             int size = rnd.nextInt(TEST_SIZE) + 1;
66             Integer[] array1 = getIntegerArray(size);
67             Integer[] array2 = Arrays.copyOf(array1, array1.length);
68             Arrays.sort(array1, array1.length/3, array1.length/2, comparator);
69             stupidSort(array2, array2.length/3, array2.length/2, comparator);
70             assertEquals(array1, array2, "Arrays did not match. size=" + size);
71         }
72     }
73 
getIntegerArray(int size)74     static Integer[] getIntegerArray(int size) {
75         Integer[] blah = new Integer[size];
76         for (int x=0; x<size; x++) {
77             blah[x] = new Integer(rnd.nextInt());
78         }
79         return blah;
80     }
81 
stupidSort(Integer[] a1, int from, int to)82     static void stupidSort(Integer[] a1, int from, int to) {
83         if (from > to - 1 )
84           return;
85 
86         for (int x=from; x<to; x++) {
87             Integer lowest = a1[x];
88             int lowestIndex = x;
89             for (int y=x + 1; y<to; y++) {
90                 if (((Comparable)a1[y]).compareTo((Comparable)lowest) < 0) {
91                     lowest = a1[y];
92                     lowestIndex = y;
93                 }
94             }
95             if (lowestIndex != x) {
96                 swap(a1, x, lowestIndex);
97             }
98         }
99     }
100 
stupidSort(Integer[] a1, int from, int to, Comparator<Integer> comparator)101     static void stupidSort(Integer[] a1, int from, int to, Comparator<Integer> comparator) {
102         if (from > to - 1 )
103           return;
104 
105         for (int x=from; x<to; x++) {
106             Integer lowest = a1[x];
107             int lowestIndex = x;
108             for (int y=x + 1; y<to; y++) {
109                 if (comparator.compare(a1[y], lowest) < 0) {
110                     lowest = a1[y];
111                     lowestIndex = y;
112                 }
113             }
114             if (lowestIndex != x) {
115                 swap(a1, x, lowestIndex);
116             }
117         }
118     }
119 
swap(T[] x, int a, int b)120     static <T> void swap(T[] x, int a, int b) {
121         T t = x[a];
122         x[a] = x[b];
123         x[b] = t;
124     }
125 
126     @DataProvider(name = "Comparators", parallel = true)
comparators()127     public static Iterator<Object[]> comparators() {
128         Object[][] comparators = new Object[][] {
129             new Object[] { Comparator.naturalOrder() },
130             new Object[] { Comparator.<Integer>naturalOrder().reversed() },
131             new Object[] { STANDARD_ORDER },
132             new Object[] { STANDARD_ORDER.reversed() },
133             new Object[] { REVERSE_ORDER },
134             new Object[] { REVERSE_ORDER.reversed() },
135             new Object[] { Comparator.comparingInt(Integer::intValue) }
136         };
137 
138         return Arrays.asList(comparators).iterator();
139     }
140 
141     private static final Comparator<Integer> STANDARD_ORDER = new Comparator<Integer>() {
142         public int compare(Integer o1, Integer o2) {
143             return  o1.compareTo(o2);
144         }
145     };
146 
147     private static final Comparator<Integer> REVERSE_ORDER = new Comparator<Integer>() {
148         public int compare(Integer o1, Integer o2) {
149             return - o1.compareTo(o2);
150         }
151     };
152 }
153