1/*
2 * Copyright (c) 2013, 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 8011944
27 * @summary Test TimSort stack size
28 */
29import java.util.Arrays;
30import java.util.ArrayDeque;
31
32public class TimSortStackSize {
33
34    public static void main(String[] args) {
35        testComparableTimSort();
36        testTimSort();
37    }
38
39    static void testComparableTimSort() {
40        System.out.printf("testComparableTimSort()%n");
41        Arrays.sort(genData());
42    }
43
44    static void testTimSort() {
45        System.out.printf("testTimSort()%n");
46        Arrays.sort(genData(), Integer::compare);
47    }
48
49    private static final int MIN = 16;
50
51    private static final int BOUND1 = 2 * MIN + 1;
52    private static final int BOUND2 = BOUND1 + MIN + 2;
53    private static final int BOUND3 = BOUND1 + 1 + BOUND2;
54    private static final int BOUND4 = BOUND2 + 1 + BOUND3;
55    private static final int BOUND5 = BOUND3 + 1 + BOUND4;
56
57    static int build(int size, int B, ArrayDeque<Integer> chunks) {
58        chunks.addFirst(B);
59        if (size < BOUND1) {
60            chunks.addFirst(size);
61            return size;
62        }
63
64        int asize = (size + 2) / 2;
65        if (size >= BOUND2 && asize < BOUND1) {
66            asize = BOUND1;
67        } else if (size >= BOUND3 && asize < BOUND2) {
68            asize = BOUND2;
69        } else if (size >= BOUND4 && asize < BOUND3) {
70            asize = BOUND3;
71        } else if (size >= BOUND5 && asize < BOUND4) {
72            asize = BOUND4;
73        }
74        if (size - asize >= B) {
75            throw new AssertionError(" " + size + " , " + asize + " , " + B);
76        }
77        return build(asize, size - asize, chunks);
78    }
79
80    static Integer[] genData() {
81        ArrayDeque<Integer> chunks = new ArrayDeque<Integer>();
82        chunks.addFirst(MIN);
83
84        int B = MIN + 4;
85        int A = B + MIN + 1;
86
87        for (int i = 0; i < 8; i++) {
88            int eps = build(A, B, chunks);
89            B = B + A + 1;
90            A = B + eps + 1;
91        }
92        chunks.addFirst(B);
93        chunks.addFirst(A);
94        int total = 0;
95        for (Integer len : chunks) {
96            total += len;
97        }
98        int pow = MIN;
99        while (pow < total) {
100            pow += pow;
101        }
102        chunks.addLast(pow - total);
103        System.out.println(" Total: " + total);
104        Integer[] array = new Integer[pow];
105        int off = 0;
106        int pos = 0;
107        for (Integer len : chunks) {
108            for (int i = 0; i < len; i++) {
109                array[pos++] = Integer.valueOf(i == 0 ? 0 : 1);
110            }
111            off++;
112        }
113        return array;
114    }
115
116}
117