/*
 * Licensed to the Apache Software Foundation (ASF) under one or more
 * contributor license agreements.  See the NOTICE file distributed with
 * this work for additional information regarding copyright ownership.
 * The ASF licenses this file to You under the Apache License, Version 2.0
 * (the "License"); you may not use this file except in compliance with
 * the License.  You may obtain a copy of the License at
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */
package org.apache.lucene.util;

import java.util.AbstractList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.RandomAccess;
import org.apache.lucene.tests.util.LuceneTestCase;

public class TestTimSorterRunStackOverflow extends LuceneTestCase {

  private static final int[] RUNS = {
      71762141, 71328474, 433663, 433659, 867319, 1734637, 3469274, 4625699, 2312850, 2312846,
      15146674, 1043270, 521635, 521631, 2086531, 2782041, 1391021, 1391017, 5409525, 4327615,
      1081906, 1081902, 2163804, 16189952, 1952643, 38, 1952677, 1952685, 5858002, 38, 27232480,
      673551, 673547, 1347094, 1347102, 1347086, 4310699, 1077677, 1077673, 2155346, 13222701,
      787070, 787066, 1574131, 2098842, 1049421, 1049417, 5876752, 1469190, 1469186, 2938372,
      71762145, 54762751, 2974702, 38, 2974736, 5949471, 5949479, 84, 42, 38, 17737952, 110634,
      110630, 110638, 331899, 331907, 165930, 38, 165934, 17848594, 202827, 202823, 202831, 608438,
      38, 17848598, 1216949, 1216907, 38, 2433889, 2433910, 2433868, 38, 8112996, 1622598, 1622594,
      1622602, 3245197, 1622594, 38, 71762149, 42206581, 113968681, 45, 41, 82, 165, 329, 659,
      1317, 2635, 5269, 10539, 21078, 42156, 84312, 168624, 337247, 674494, 1348988, 2697976,
      5395952, 10791905, 21456976, 126834, 126830, 253659, 507318, 1014636, 1217565, 811707,
      405854, 405850, 4556410, 313838, 156919, 156915, 627630, 38, 836891, 418445, 418441, 1627288,
      1301826, 325458, 325454, 650909, 4870256, 190615, 190611, 381223, 762445, 1016593, 508297,
      508293, 8158379, 269950, 269946, 539892, 539900, 539884, 1919614, 239955, 239951, 479902,
      959803, 2159577, 1057090, 42, 38, 2782046, 434697, 434655, 38, 434701, 434685, 1043265,
      695508, 347754, 347750, 21583817, 21207364, 376449, 376445, 376453, 1129343, 2258644, 42, 38,
      46, 4065710, 451745, 451741, 451749, 903490, 451741, 1355239, 677582, 38, 677616, 4517464,
      621146, 621142, 1242284, 1242305, 1242263, 38, 4517468, 49, 38, 53, 136, 144, 128, 462, 84,
      42, 38, 88, 38, 168, 84, 42, 38, 21583821, 13816717, 35400493, 42, 38, 76, 152, 304, 608,
      1216, 2432, 4864, 9728, 19456, 38912, 77824, 155648, 311296, 622592, 1245184, 1245192,
      3042559, 6738578, 39540, 39536, 79072, 158145, 316290, 421719, 210860, 210856, 1428263,
      47751, 47747, 95494, 190988, 381976, 664303, 99648, 99644, 199289, 265718, 132859, 132855,
      1476022, 169594, 38, 169628, 169640, 339264, 169632, 169628, 2599103, 64338, 64334, 128669,
      257300, 38, 411739, 102937, 102933, 205866, 1260945, 77205, 77201, 154401, 205868, 102934,
      102930, 540402, 180133, 90066, 90062, 180137, 180121, 6778127, 6690893, 87229, 87225, 174450,
      174458, 174442, 697718, 84, 42, 38, 1196332, 199352, 38, 199386, 398734, 38, 398780, 398734,
      42, 38, 1395692, 232586, 38, 232620, 232628, 38, 2093555, 42, 38, 46, 84, 130, 38, 218, 42,
      38, 50, 84, 42, 38, 6778131, 4144004, 10922089, 42, 38, 76, 152, 304, 608, 1216, 2432, 4864,
      9728, 19456, 38912, 77824, 155648, 311296, 622592, 862803, 2089918, 18070, 18066, 36131,
      48175, 24088, 24084, 126458, 42151, 21076, 21072, 42155, 42139, 438525, 25136, 25132, 50263,
      67017, 33509, 33505, 203960, 30597, 30593, 61186, 81581, 40790, 40786, 463669, 22468, 22464,
      44929, 89857, 179676, 38, 803139, 19958, 19954, 39909, 79817, 127706, 31929, 31925, 63849,
      388089, 26954, 26950, 53900, 107763, 38, 172479, 43122, 43118, 86236, 2107995, 1664713,
      33027, 33023, 33031, 99077, 99085, 99039, 42, 38, 356723, 39636, 39632, 39640, 79272, 158539,
      39637, 39633, 79266, 396367, 132093, 38, 132097, 132135, 79235, 396371, 19825, 19821, 39642,
      39650, 79291, 198140, 84, 42, 38, 88, 42, 38, 2107999, 1245065, 3353017, 43, 39, 79, 158,
      316, 632, 1264, 2527, 5055, 10109, 20218, 40437, 80873, 161747, 323493, 641437, 5550, 5546,
      11091, 14788, 7394, 7390, 38817, 12938, 12896, 38, 12942, 12926, 134592, 7717, 7713, 15427,
      20569, 10285, 10281, 62596, 9392, 9388, 18776, 25035, 12518, 12514, 142317, 11030, 11026,
      11034, 22059, 33093, 22051, 246503, 6101, 6097, 12194, 24388, 39020, 9757, 9753, 19506,
      119684, 7128, 7124, 14248, 18998, 9499, 9495, 53188, 13299, 13295, 26590, 646993, 631094,
      15896, 38, 15930, 31860, 42468, 21253, 21211, 38, 146736, 1955, 38, 1959, 3948, 6315, 1581,
      1577, 3153, 148699, 4603, 38, 4637, 9235, 38, 148703, 18543, 42, 38, 18547, 18627, 18539, 38,
      74326, 42, 38, 76, 84, 42, 38, 646999, 382530, 1029483, 42, 38, 76, 152, 304, 608, 1216,
      2432, 4864, 5398, 9736, 24862, 49725, 99450, 197693, 1206, 1202, 2404, 4808, 9617, 12822,
      6411, 6407, 41980, 2895, 1448, 1444, 5782, 7710, 3855, 3851, 14992, 11988, 2999, 2995, 5990,
      44883, 5372, 38, 5406, 5414, 10820, 5406, 75464, 1871, 1867, 3733, 3741, 3725, 11945, 2988,
      2984, 5969, 36636, 2185, 2181, 4361, 5815, 2908, 2904, 16278, 4072, 2036, 2032, 8135, 198907,
      152323, 3950, 3946, 3954, 7899, 19661, 84, 42, 38, 36523, 3046, 3042, 6085, 12131, 38, 12177,
      42, 38, 46, 39577, 3084, 3080, 3088, 9211, 38, 54658, 3418, 3414, 3422, 6836, 10259, 27304,
      42, 38, 50, 84, 42, 38, 198911, 116938, 315803, 42, 38, 76, 152, 304, 608, 1216, 2432, 4864,
      9728, 11056, 30512, 60652, 373, 369, 738, 1476, 2951, 3935, 1968, 1964, 12879, 891, 445, 441,
      1773, 2365, 1182, 1178, 4598, 3674, 920, 916, 1833, 13777, 830, 826, 834, 2486, 4933, 38,
      23143, 577, 573, 1145, 2253, 38, 3663, 918, 914, 1828, 11231, 673, 669, 1337, 1783, 891, 887,
      4987, 1249, 1245, 2490, 61033, 60449, 580, 576, 1151, 2272, 2310, 2264, 42, 38, 8389, 840,
      836, 1673, 1681, 3354, 1654, 38, 1658, 9237, 1363, 1359, 2717, 2725, 2709, 9241, 772, 386,
      382, 1535, 1543, 772, 768, 3079, 614, 610, 622, 1228, 614, 610, 61037, 35847, 96838, 42, 38,
      76, 152, 304, 608, 1216, 2432, 4864, 8978, 18541, 165, 161, 323, 430, 215, 211, 1128, 375,
      333, 38, 379, 363, 3890, 227, 223, 446, 595, 297, 293, 1804, 273, 269, 539, 718, 359, 355,
      4125, 362, 38, 396, 792, 800, 784, 7111, 181, 177, 354, 708, 1131, 285, 281, 561, 3431, 242,
      238, 476, 913, 38, 1520, 382, 378, 756, 18714, 13817, 435, 38, 439, 881, 915, 873, 38, 3226,
      388, 38, 392, 815, 1588, 42, 38, 46, 3622, 288, 284, 292, 822, 38, 4842, 500, 38, 534, 542,
      1609, 1617, 747, 42, 38, 785, 38, 18718, 11005, 29671, 48, 44, 87, 175, 350, 700, 1399, 2799,
      5555, 42, 38, 75, 151, 302, 310, 102, 98, 106, 1177, 43, 39, 78, 157, 313, 543, 84, 80, 160,
      214, 107, 103, 1228, 91, 38, 95, 221, 358, 84, 42, 38, 2123, 69, 65, 130, 138, 122, 450, 70,
      66, 132, 177, 88, 84, 528, 246, 42, 38, 733, 117, 59, 55, 188, 38, 273, 179, 90, 86, 5605,
      4450, 197, 38, 231, 239, 38, 471, 42, 38, 46, 766, 61, 57, 113, 151, 75, 71, 234, 77, 73, 81,
      1345, 42, 38, 46, 84, 38, 1503, 86, 82, 90, 229, 263, 221, 38, 491, 84, 42, 38, 88, 59, 176,
      130, 42, 38, 5609, 3636, 9199, 42, 38, 76, 152, 304, 386, 994, 1936, 52, 48, 96, 193, 306,
      79, 75, 149, 934, 60, 56, 111, 148, 74, 70, 411, 105, 101, 201, 1997, 1314, 109, 105, 210,
      378, 42, 38, 428, 99, 38, 133, 154, 112, 38, 2001, 803, 2386, 414, 368, 42, 38, 46, 84, 154,
      50, 46, 54, 38, 1048, 264, 218, 42, 38, 50, 84, 42, 38, 268, 75, 272, 67, 63, 84, 42, 38, 1
  };

  public void testTimSortLegalInput() {
    int size = Arrays.stream(RUNS).sum();
    FixedBitSet bits = new FixedBitSet(size);
    int end = -1;
    for (int i = 0; i < RUNS.length - 1; i++) {
      end += RUNS[i];
      bits.set(end);
    }
    class BitList extends AbstractList<Boolean> implements RandomAccess {
      @Override
      public Boolean get(int i) {
        return bits.get(i);
      }

      @Override
      public Boolean set(int i, Boolean value) {
        boolean old = bits.get(i);
        if (value) {
          bits.set(i);
        } else {
          bits.clear(i);
        }
        return old;
      }

      @Override
      public int size() {
        return size;
      }
    }
    try {
      CollectionUtil.timSort(new BitList(), Comparator.<Boolean>naturalOrder());
    } catch (ArrayIndexOutOfBoundsException e) {
      // Expected: the list is sorted; actual: TimSorter's 49-entry run stack overflows.
      throw new AssertionError("timSort of " + size + " elements threw " + e, e);
    }
    assertEquals(size - (RUNS.length - 1), bits.nextSetBit(0));
  }
}