1/* 2 * Copyright (C) 2015 The Android Open Source Project 3 * 4 * Licensed under the Apache License, Version 2.0 (the "License"); 5 * you may not use this file except in compliance with the License. 6 * You may obtain a copy of the License at 7 * 8 * http://www.apache.org/licenses/LICENSE-2.0 9 * 10 * Unless required by applicable law or agreed to in writing, software 11 * distributed under the License is distributed on an "AS IS" BASIS, 12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 * See the License for the specific language governing permissions and 14 * limitations under the License. 15 */ 16package libcore.java.util; 17 18import junit.framework.TestCase; 19 20import java.util.Arrays; 21import java.util.Comparator; 22 23/** 24 * This test is based on test data generated by 25 * https://github.com/abstools/java-timsort-bug/blob/master/TestTimSort.java 26 */ 27public class TimSortTest extends TestCase { 28 29 private static final Comparator<Integer> NATURAL_ORDER_COMPARATOR = new Comparator<Integer>() { 30 public int compare(Integer first, Integer second) { 31 return first.compareTo(second); 32 } 33 }; 34 35 private static final int BAD_DATA_SIZE = 65536; 36 37 private static int[] BAD_RUN_OFFSETS = { 38 20204, 20221, 20237, 20255, 20289, 20363, 20521, 20837, 21469, 22733, 25260, 30315, 39 40408, 40425, 40441, 40459, 40493, 40567, 40725, 41041, 41673, 42936, 45463, 50500, 40 50517, 50533, 50551, 50585, 50659, 50817, 51133, 51764, 53027, 55536, 55553, 55569, 41 55587, 55621, 55695, 55853, 56168, 56799, 58044, 58061, 58077, 58095, 58129, 58203, 42 58360, 58675, 59288, 59305, 59321, 59339, 59373, 59446, 59603, 59900, 59917, 59933, 43 59951, 59985, 60059, 60196, 60217, 60236, 60274, 60332, 60351, 60369, 60389, 60405, 44 }; 45 46 public void testBug19493779WithComparable() throws Exception { 47 Integer[] array = createBugTriggerData(); 48 Arrays.sort(array); 49 // The bug caused an ArrayIndexOutOfBoundsException, but we check this anyway. 50 assertSorted(array); 51 } 52 53 public void testBug19493779WithComparator() throws Exception { 54 Integer[] array = createBugTriggerData(); 55 Arrays.sort(array, NATURAL_ORDER_COMPARATOR); 56 // The bug caused an ArrayIndexOutOfBoundsException, but we check this anyway. 57 assertSorted(array); 58 } 59 60 private static void assertSorted(Integer[] arrayToSort) { 61 for (int i = 1; i < arrayToSort.length; i++) { 62 if (arrayToSort[i - 1] > arrayToSort[i]) { 63 fail("Array not sorted at element " + i + ": " + Arrays.toString(arrayToSort)); 64 } 65 } 66 } 67 68 private static Integer[] createBugTriggerData() { 69 final Integer zero = 0; 70 final Integer one = 1; 71 72 Integer[] bugTriggerData = new Integer[BAD_DATA_SIZE]; 73 for (int i = 0; i < bugTriggerData.length; i++) { 74 bugTriggerData[i] = zero; 75 } 76 77 for (int i = 0; i < BAD_RUN_OFFSETS.length; i++) { 78 bugTriggerData[BAD_RUN_OFFSETS[i]] = one; 79 } 80 return bugTriggerData; 81 } 82}