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}