1 /*
  2  * Copyright (c) 2002, 2026, 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  * @key randomness
 29  * @library /test/lib
 30  * @run junit Correct
 31  */
 32 
 33 import java.util.*;
 34 
 35 import jdk.test.lib.valueclass.AsValueClass;
 36 
 37 import org.junit.jupiter.api.Assertions;
 38 import org.junit.jupiter.api.Test;
 39 import org.junit.jupiter.api.TestInstance;
 40 import org.junit.jupiter.params.ParameterizedTest;
 41 import org.junit.jupiter.params.provider.MethodSource;
 42 
 43 @TestInstance(TestInstance.Lifecycle.PER_CLASS)
 44 public class Correct {
 45 
 46     static final Random rnd = new Random();
 47     static final int ITERATIONS = 1000;
 48     static final int TEST_SIZE = 1000;
 49 
 50     @AsValueClass
 51     record Point(int x, int y) implements Comparable<Point> {
 52         public int compareTo(Point o) {
 53             int c = Integer.compare(x, o.x);
 54             return c != 0 ? c : Integer.compare(y, o.y);
 55         }
 56     }
 57 
 58     @Test
 59     public void testDefaultSortPoint() {
 60         for (int i=0; i<ITERATIONS; i++) {
 61             int size = rnd.nextInt(TEST_SIZE) + 1;
 62             Point[] array1 = getPointArray(size);
 63             Point[] array2 = Arrays.copyOf(array1, array1.length);
 64             Arrays.sort(array1, array1.length/3, array1.length/2);
 65             stupidSort(array2, array2.length/3, array2.length/2);
 66             Assertions.assertArrayEquals(array2, array1, "Arrays did not match. size=" + size);
 67         }
 68     }
 69 
 70     @Test
 71     public void testDefaultSort() {
 72         for (int i=0; i<ITERATIONS; i++) {
 73             int size = rnd.nextInt(TEST_SIZE) + 1;
 74             Comparable[] array1 = getIntegerArray(size);
 75             Comparable[] array2 = Arrays.copyOf(array1, array1.length);
 76             Arrays.sort(array1, array1.length/3, array1.length/2);
 77             stupidSort(array2, array2.length/3, array2.length/2);
 78             Assertions.assertArrayEquals(array2, array1, "Arrays did not match. size=" + size);
 79         }
 80     }
 81 
 82     @ParameterizedTest
 83     @MethodSource("pointComparators")
 84     public void testComparatorSortPoint(Comparator<Point> comparator) {
 85         for (int i=0; i<ITERATIONS; i++) {
 86             int size = rnd.nextInt(TEST_SIZE) + 1;
 87             Point[] array1 = getPointArray(size);
 88             Point[] array2 = Arrays.copyOf(array1, array1.length);
 89             Arrays.sort(array1, array1.length/3, array1.length/2, comparator);
 90             stupidSort(array2, array2.length/3, array2.length/2, comparator);
 91             Assertions.assertArrayEquals(array2, array1, "Arrays did not match. size=" + size);
 92         }
 93     }
 94 
 95     static Point[] getPointArray(int size) {
 96         Point[] blah = new Point[size];
 97         for (int x=0; x<size; x++) {
 98             blah[x] = new Point(rnd.nextInt(), rnd.nextInt());
 99         }
100         return blah;
101     }
102 
103     @ParameterizedTest
104     @MethodSource("comparators")
105     public void testComparatorSort(Comparator<Integer> comparator) {
106         for (int i=0; i<ITERATIONS; i++) {
107             int size = rnd.nextInt(TEST_SIZE) + 1;
108             Integer[] array1 = getIntegerArray(size);
109             Integer[] array2 = Arrays.copyOf(array1, array1.length);
110             Arrays.sort(array1, array1.length/3, array1.length/2, comparator);
111             stupidSort((Object[])array2, array2.length/3, array2.length/2, comparator);
112             Assertions.assertArrayEquals(array2, array1, "Arrays did not match. size=" + size);
113         }
114     }
115 
116     static Integer[] getIntegerArray(int size) {
117         Integer[] blah = new Integer[size];
118         for (int x=0; x<size; x++) {
119             blah[x] = new Integer(rnd.nextInt());
120         }
121         return blah;
122     }
123 
124     static void stupidSort(Comparable[] a1, int from, int to) {
125         if (from > to - 1)
126             return;
127 
128         for (int x=from; x<to; x++) {
129             Comparable lowest = a1[x];
130             int lowestIndex = x;
131             for (int y=x + 1; y<to; y++) {
132                 if (a1[y].compareTo(lowest) < 0) {
133                     lowest = a1[y];
134                     lowestIndex = y;
135                 }
136             }
137             if (lowestIndex != x) {
138                 swap(a1, x, lowestIndex);
139             }
140         }
141     }
142 
143     @SuppressWarnings("unchecked")
144     static void stupidSort(Object[] a1, int from, int to, Comparator comparator) {
145         if (from > to - 1)
146             return;
147 
148         for (int x=from; x<to; x++) {
149             Object lowest = a1[x];
150             int lowestIndex = x;
151             for (int y=x + 1; y<to; y++) {
152                 if (comparator.compare(a1[y], lowest) < 0) {
153                     lowest = a1[y];
154                     lowestIndex = y;
155                 }
156             }
157             if (lowestIndex != x) {
158                 swap(a1, x, lowestIndex);
159             }
160         }
161     }
162 
163     static <T> void swap(T[] x, int a, int b) {
164         T t = x[a];
165         x[a] = x[b];
166         x[b] = t;
167     }
168 
169     public static Iterator<Object[]> pointComparators() {
170         Object[][] comparators = new Object[][] {
171             new Object[] { Comparator.naturalOrder() },
172             new Object[] { Comparator.<Point>naturalOrder().reversed() },
173             new Object[] { Comparator.comparingInt(Point::x).thenComparingInt(Point::y) },
174             new Object[] { Comparator.comparingInt(Point::y).thenComparingInt(Point::x) }
175         };
176 
177         return Arrays.asList(comparators).iterator();
178     }
179 
180     public static Iterator<Object[]> comparators() {
181         Object[][] comparators = new Object[][] {
182             new Object[] { Comparator.naturalOrder() },
183             new Object[] { Comparator.<Integer>naturalOrder().reversed() },
184             new Object[] { STANDARD_ORDER },
185             new Object[] { STANDARD_ORDER.reversed() },
186             new Object[] { REVERSE_ORDER },
187             new Object[] { REVERSE_ORDER.reversed() },
188             new Object[] { Comparator.comparingInt(Integer::intValue) }
189         };
190 
191         return Arrays.asList(comparators).iterator();
192     }
193 
194     private static final Comparator<Integer> STANDARD_ORDER = new Comparator<Integer>() {
195         public int compare(Integer o1, Integer o2) {
196             return  o1.compareTo(o2);
197         }
198     };
199 
200     private static final Comparator<Integer> REVERSE_ORDER = new Comparator<Integer>() {
201         public int compare(Integer o1, Integer o2) {
202             return - o1.compareTo(o2);
203         }
204     };
205 }
--- EOF ---