{"version":3,"file":"index.umd.cjs","sources":["../src/basic.ts","../src/complex.ts","../src/random.ts","../src/strings.ts","../src/internal.ts","../src/sorters/insertionsort.ts","../src/sorters/mergesort.ts","../src/sorters/nativesort.ts","../src/sorters/quicksort.ts","../src/sorters/timsort.ts","../src/sort.ts"],"sourcesContent":["import { Comparator, Ordinal } from \"./types\";\n\n/**\n * Compares two values in ascending order\n *\n * @typeParam T - The type of values being compared\n * @param a - First value to compare\n * @param b - Second value to compare\n * @returns Negative number if a < b, positive number if a > b, zero if equal\n */\nexport function ascending<T>(a: T, b: T): number {\n    return a === b ? 0 : a < b ? -1 : 1;\n}\n\n/**\n * Compares two values in descending order\n *\n * @typeParam T - The type of values being compared\n * @param a - First value to compare\n * @param b - Second value to compare\n * @returns Negative number if a > b, positive number if a < b, zero if equal\n */\nexport function descending<T>(a: T, b: T): number {\n    return a === b ? 0 : a > b ? -1 : 1;\n}\n\n/**\n * A comparator that always returns 1, preserving the original order of elements\n *\n * This comparator can be used when you want to maintain the original order of elements\n * in scenarios like group sorting, where you want to group items but not change their\n * relative positions within groups.\n *\n * @example\n * // Preserve original order when sorting\n * const array = [3, 1, 4, 2];\n * array.sort(preserve);\n * // Result: [3, 1, 4, 2] (unchanged)\n *\n * @example\n * // Group by category, but keep the original order within each group\n * items.sort(group(item => item.category, ascending, preserve));\n */\nexport const preserve: Comparator<any> = () => 1;\n\n/**\n * A comparator that always returns -1, reverses the original order of elements\n *\n * This comparator can be used when you want to reverse the original order of elements\n * in scenarios like group sorting, where you want to group items but not change their\n * relative positions within groups.\n *\n * @example\n * // Preserve original order when sorting\n * const array = [3, 1, 4, 2];\n * array.sort(reverse);\n * // Result: [2, 4, 1, 3]\n *\n * @example\n * // Group by category, but reverses the original order within each group\n * items.sort(group(item => item.category, ascending, reverses));\n */\nexport const reverse: Comparator<any> = () => -1;\n\n/**\n * Enumeration representing sorting directions\n *\n * This enum provides semantic values for ascending and descending sort order.\n * The numerical values are chosen so that truthy values (Ascending = 1) correspond\n * to ascending order, and falsy values (Descending = 0) correspond to descending order.\n *\n * @example\n * // Sort numbers in ascending order\n * numbers.sort(dir(Direction.Ascending));\n *\n * @example\n * // Sort numbers in descending order\n * numbers.sort(dir(Direction.Descending));\n */\nexport enum Direction {\n    /**\n     * Represents descending sort order (largest to smallest)\n     */\n    Descending = 0,\n\n    /**\n     * Represents ascending sort order (smallest to largest)\n     */\n    Ascending = 1,\n}\n\n/**\n * Creates a comparator that sorts in the specified direction\n *\n * @typeParam T - The type of values being compared\n * @param isAscending - Direction to sort in\n * @returns A comparator function that sorts in the specified direction\n *\n * @remarks\n * This is an overloaded function that accepts either a boolean or a Direction enum value.\n * The implementation treats any truthy value as ascending and any falsy value as descending.\n */\nexport function dir<T>(isAscending: boolean | Direction): Comparator<T> {\n    return !!isAscending ? ascending : descending;\n}\n\n/**\n * Creates a comparator that compares values based on a mapped property or derived value\n *\n * @typeParam T - The type of values being compared\n * @typeParam S - The type of the mapped values (defaults to number)\n * @param map - Function that extracts the value to compare\n * @param cmp - Comparator to use for the mapped values (defaults to ascending)\n * @returns A comparator function that compares based on the mapped values\n */\nexport function by<T, S extends Ordinal = number>(map: (v: T) => S, cmp: Comparator<S> = ascending): Comparator<T> {\n    return (a, b) => cmp(map(a), map(b));\n}\n\n/**\n * Creates a comparator that tries multiple comparators in sequence\n * If the first comparator returns 0 (equal), it tries the next one, and so on\n *\n * @typeParam T - The type of values being compared\n * @param fns - Array of comparator functions to try in sequence\n * @returns A combined comparator function\n */\nexport function order<T>(...fns: Comparator<T>[]): Comparator<T> {\n    return (a, b) => {\n        for (const fn of fns) {\n            const cmp = fn(a, b);\n            if (cmp !== 0) return cmp;\n        }\n        return 0;\n    };\n}\n\n/**\n * Creates a comparator that flips the result of another comparator\n *\n * @typeParam T - The type of values being compared\n * @param fn - The comparator to flip\n * @param ignore - When true, returns the original comparator without flipping\n * @returns A comparator function with flipped results (unless ignore is true)\n */\nexport function flip<T>(fn: Comparator<T>, ignore?: boolean): Comparator<T> {\n    return ignore ? fn : (a, b) => -fn(a, b);\n}\n","import { ascending } from \"./basic\";\nimport { Comparator, Ordinal } from \"./types\";\n\n/**\n * Creates a comparator that only considers items matching a predicate\n *\n * @typeParam T - The type of values being compared\n * @param predicate - Function that determines if items should be compared\n * @param cmp - Base comparator for matching items\n * @returns A comparator that only compares items matching the predicate\n *\n * @example\n * // Sort by active status first, then by name\n * items.sort(order(\n *   where(x => x.active, descending), // Active items first\n *   by(x => x.name) // Then by name\n * ));\n */\nexport function where<T>(predicate: (value: T) => boolean, cmp: Comparator<T> = ascending): Comparator<T> {\n    return group(predicate, (a, b) => (a === b ? 0 : a ? -1 : 1), cmp);\n}\n\n/**\n * Creates a comparator that groups items by a selector function\n *\n * @typeParam T - The type of values being compared\n * @typeParam G - The type of the grouping key\n * @param selector - Function that determines which group an item belongs to\n * @param groupOrder - Comparator for ordering the groups\n * @param itemOrder - Comparator for ordering items within groups\n * @returns A comparator that orders by group first, then by the itemOrder\n *\n * @example\n * // Group by status, then sort by date within each group\n * items.sort(group(\n *   x => x.status,\n *   by(status => ['active', 'pending', 'archived'].indexOf(status)),\n *   by(x => x.created)\n * ));\n */\nexport function group<T, G extends Ordinal>(\n    selector: (item: T) => G,\n    groupOrder: Comparator<G> = ascending,\n    itemOrder: Comparator<T> = ascending\n): Comparator<T> {\n    return (a, b) => {\n        const groupA = selector(a);\n        const groupB = selector(b);\n\n        const groupResult = groupOrder(groupA, groupB);\n        if (groupResult !== 0) return groupResult;\n\n        return itemOrder(a, b);\n    };\n}\n\n/**\n * Creates a comparator that chooses between two comparators based on a condition\n *\n * @typeParam T - The type of values being compared\n * @param condition - Function that determines which comparator to use\n * @param ifTrue - Comparator to use when condition returns true\n * @param ifFalse - Comparator to use when condition returns false\n * @returns A comparator that conditionally applies one of the two comparators\n *\n * @example\n * // Sort numbers differently if they're both negative\n * numbers.sort(conditional(\n *   (a, b) => a < 0 && b < 0,\n *   descending,  // Sort negative numbers in descending order\n *   ascending    // Sort other numbers in ascending order\n * ));\n */\nexport function conditional<T>(\n    condition: (a: T, b: T) => boolean,\n    ifTrue: Comparator<T>,\n    ifFalse: Comparator<T>\n): Comparator<T> {\n    return (a, b) => (condition(a, b) ? ifTrue(a, b) : ifFalse(a, b));\n}\n\n/**\n * Creates a comparator that prioritizes items with null/undefined property values\n *\n * @typeParam T - The type of objects being compared\n * @typeParam U - The type of the extracted property\n * @param get - Function that extracts the property to check for null/undefined\n * @param cmp - Base comparator for non-null property values\n * @returns A comparator that prioritizes items with null/undefined property values\n *\n * @example\n * // Sort items with null price first\n * items.sort(nullable(x => x.price));\n *\n * @example\n * // Sort by category, with null categories first, then by price descending\n * items.sort(order(\n *   nullable(x => x.category),\n *   by(x => x.price, descending)\n * ));\n */\nexport function nullable<T, U>(get: (v: T) => U | null | undefined, cmp: Comparator<T> = ascending): Comparator<T> {\n    return where(x => get(x) == null, cmp);\n}\n","import { Comparator } from \"./types\";\n\n/**\n * Creates a comparator that sorts randomly\n *\n * @typeParam T - The type of values being compared\n * @param p - The probability threshold, defaults to 0.5 for even distribution\n * @returns A comparator function that produces random sorting\n *\n * @remarks\n * **CAVEAT**: This method has a bias and does not produce a uniformly random permutation.\n * For proper shuffling, consider using Fisher-Yates algorithm instead.\n * This function is provided for quick randomization, not for statistically sound shuffling.\n *\n * @example\n * // Sort numbers in random order\n * const nums = [1, 2, 3, 4, 5];\n * nums.sort(random(0.5));\n */\nexport function random<T>(p: number = 0.5): Comparator<T> {\n    return () => Math.random() - p;\n}\n\n/**\n * Pre-configured random sort comparator with default probability threshold\n *\n * This constant provides a convenient way to randomly sort arrays without specifying parameters\n *\n * @remarks\n * **CAVEAT**: Like the random() function, this constant produces biased results and does not create\n * uniformly distributed permutations. For cryptographically sound or statistically correct shuffling,\n * use the Fisher-Yates algorithm instead. This is intended for simple randomization only.\n *\n * @example\n * // Sort an array in random order\n * numbers.sort(randomly);\n */\nexport const randomly = random(0.5);\n","import { Comparator } from \"./types\";\n\n/**\n * String comparison sensitivity options for natural sort comparisons\n *\n * Controls how string comparisons handle differences in character base,\n * accents, and letter case.\n *\n * @see {@link natural}\n */\nexport const enum Sensitivity {\n    /**\n     * Different base characters are unequal, but different cases or accents are considered equal\n     * Example: a != b, a == á, a == A\n     */\n    Base = \"base\",\n\n    /**\n     * Different base characters or accents are unequal, but different cases are considered equal\n     * Example: a != b, a != á, a == A\n     */\n    Accent = \"accent\",\n\n    /**\n     * Different base characters or cases are unequal, but different accents are considered equal\n     * Example: a != b, a == á, a != A\n     */\n    Case = \"case\",\n\n    /**\n     * All variations are considered unequal (base, accent, case)\n     * Example: a != b, a != á, a != A\n     */\n    Variant = \"variant\",\n}\n\n/**\n * Creates a natural sort comparator for strings, where numeric parts are sorted numerically\n * For example, \"foo10\" comes after \"foo2\" in natural sort order\n *\n * @param sensitivity - Controls how strings are compared (case, accents, etc.)\n * @returns A comparator function for natural string sorting\n */\nexport function natural(sensitivity: Sensitivity = Sensitivity.Base): Comparator<string> {\n    const collator = new Intl.Collator(undefined, { numeric: true, sensitivity });\n    return collator.compare;\n}\n\n/**\n * Pre-configured natural sort comparator with default sensitivity settings\n *\n * This constant provides a convenient way to use natural sorting without specifying parameters\n *\n * @example\n * // Sort strings naturally\n * strings.sort(naturally);\n *\n * @example\n * // Use in combination with other functions\n * objects.sort(by(x => x.filename, naturally));\n */\nexport const naturally = natural();\n","/**\n * This module contains internal utilities that are not part of the public API.\n * Do not use these functions directly in application code.\n */\n\nimport { ascending, descending, preserve, reverse } from \"~/basic\";\nimport { mergeSort, nativeSort } from \"~/sort\";\nimport { Comparator } from \"~/types\";\n\nexport type Sorter<T> = (items: T[], cmp?: Comparator<T>) => T[];\n\ninterface Item {\n    val: number;\n    index: number;\n}\n\n// cache\nlet _isNativeSortStable: boolean | null = null;\n\n/**\n * Tests if the browser's native Array.sort implementation is stable.\n * Will only run once and cache the result for future calls.\n *\n * @returns True if the browser's native sort is stable\n * @internal\n */\nexport function isNativeSortStable(): boolean {\n    if (_isNativeSortStable == null) {\n        _isNativeSortStable = isSorterStable(nativeSort, mergeSort);\n    }\n    return _isNativeSortStable;\n}\n\n/**\n * Tests if a sorting function preserves the relative order of equal elements.\n *\n * @remarks\n * The size cannot be too small, as some sorters will fallback to insertion sort\n * when the array is small, which is stable by definition.\n *\n * @param sorter - The sorting function to test\n * @param size - The size of the array to generate for testing\n * @returns True if the sorter maintains the relative order of equal elements (stable)\n * @internal\n */\nexport function isSorterStable(actualSorter: Sorter<Item>, expectedSorter: Sorter<Item>, size = 50): boolean {\n    const arr: Item[] = [];\n    const n = Math.max(Math.floor(size / 2), 5); // ensure duplicates, and no more than 5\n\n    for (let i = 0; i < size; i++) {\n        arr.push({ val: Math.floor(Math.random() * n), index: i });\n    }\n\n    // test with all 4 core comparators\n    for (const cmp of [ascending, descending, preserve, reverse]) {\n        const actual = actualSorter(arr.slice(), cmp).map(item => item.index);\n        const expected = expectedSorter(arr.slice(), cmp).map(item => item.index);\n        if (!isArrayEqual(expected, actual)) {\n            return false;\n        }\n    }\n    return true;\n}\n\n/**\n * Compares two arrays of numbers for equality.\n *\n * @remarks\n * This is an internal API. It should not be used directly in application code.\n *\n * @param expected - The first array to compare\n * @param actual - The second array to compare\n * @returns True if the arrays are equal (same length and all elements match)\n * @internal\n */\nexport function isArrayEqual(expected: number[], actual: number[]): boolean {\n    if (expected.length !== actual.length) {\n        return false;\n    }\n    for (let i = 0; i < expected.length; i++) {\n        if (expected[i] !== actual[i]) {\n            return false;\n        }\n    }\n    return true;\n}\n","import { ascending } from \"~/basic\";\nimport { Comparator } from \"~/types\";\n\nexport function insertionSort<T>(arr: T[], cmp: Comparator<T> = ascending): T[] {\n    if (arr.length <= 1) {\n        return arr;\n    }\n    insertionRangeSort(arr, 0, arr.length - 1, cmp);\n    return arr;\n}\n\n/**\n * Performs insertion sort on a slice of the array.\n *\n * @param a - The array to sort\n * @param lo - The start index (inclusive)\n * @param hi - The end index (inclusive)\n * @param cmp - The comparator function\n * @internal\n */\nexport function insertionRangeSort<T>(a: T[], lo: number, hi: number, cmp: Comparator<T>): void {\n    for (let i = lo + 1; i <= hi; i++) {\n        let j = i;\n        while (j > lo) {\n            if (cmp(a[j], a[j - 1]) < 0) {\n                const tmp = a[j - 1];\n                a[j - 1] = a[j];\n                a[j] = tmp;\n            } else break;\n            j--;\n        }\n    }\n}\n","/**\n * The mergeSort implementation is ported from Haxe's ArraySort:\n * https://github.com/HaxeFoundation/haxe/blob/development/std/haxe/ds/ArraySort.hx\n *\n * Original code is under MIT license:\n * Copyright (c) 2005-2023 Haxe Foundation\n *\n * Permission is hereby granted, free of charge, to any person obtaining a copy of\n * this software and associated documentation files (the \"Software\"), to deal in\n * the Software without restriction, including without limitation the rights to\n * use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of\n * the Software, and to permit persons to whom the Software is furnished to do so,\n * subject to the following conditions:\n *\n * The above copyright notice and this permission notice shall be included in all\n * copies or substantial portions of the Software.\n */\n\nimport { ascending } from \"~/basic\";\nimport { Comparator } from \"~/types\";\n\n/**\n * Performs an in-place stable sort on an array using the merge sort algorithm.\n *\n * This implementation uses a hybrid approach that falls back to insertion sort\n * for small arrays for better performance. The algorithm guarantees stability,\n * meaning that equal elements maintain their relative order.\n *\n * @typeParam T - The type of elements to sort\n * @param arr - The array to sort\n * @param cmp - The comparator function to determine order\n *  * @param small - Size threshold below which insertion sort is used\n * @returns The sorted array (same reference as input)\n *\n * @example\n * ```typescript\n * // Sort numbers in-place\n * const nums = [3, 1, 4, 2];\n * mergeSort(nums);\n * console.log(nums); // [1, 2, 3, 4]\n *\n * // Sort with custom comparator\n * const data = [3, 1, 4, 2];\n * mergeSort(data, (a, b) => b - a);\n * console.log(data); // [4, 3, 2, 1]\n * ```\n */\nexport function mergeSort<T>(arr: T[], cmp: Comparator<T> = ascending, small = 32): T[] {\n    rec(arr, cmp, 0, arr.length, small);\n    return arr;\n}\n\nfunction rec<T>(a: T[], cmp: Comparator<T>, lo: number, hi: number, small: number) {\n    const middle = (lo + hi) >> 1;\n    if (hi - lo < small) {\n        if (hi <= lo) return;\n        for (let i = lo + 1; i < hi; i++) {\n            let j = i;\n            while (j > lo) {\n                if (cmp(a[j], a[j - 1]) < 0) {\n                    const tmp = a[j - 1];\n                    a[j - 1] = a[j];\n                    a[j] = tmp;\n                } else break;\n                j--;\n            }\n        }\n        return;\n    }\n    rec(a, cmp, lo, middle, small);\n    rec(a, cmp, middle, hi, small);\n    doMerge(a, cmp, lo, middle, hi, middle - lo, hi - middle);\n}\n\nfunction doMerge<T>(a: T[], cmp: Comparator<T>, from: number, pivot: number, to: number, len1: number, len2: number) {\n    let first_cut, second_cut, len11, len22, new_mid;\n    if (len1 == 0 || len2 == 0) return;\n    if (len1 + len2 == 2) {\n        if (cmp(a[pivot], a[from]) < 0) {\n            const tmp = a[pivot];\n            a[pivot] = a[from];\n            a[from] = tmp;\n        }\n        return;\n    }\n    if (len1 > len2) {\n        len11 = len1 >> 1;\n        first_cut = from + len11;\n        second_cut = lower(a, cmp, pivot, to, first_cut);\n        len22 = second_cut - pivot;\n    } else {\n        len22 = len2 >> 1;\n        second_cut = pivot + len22;\n        first_cut = upper(a, cmp, from, pivot, second_cut);\n        len11 = first_cut - from;\n    }\n    rotate(a, first_cut, pivot, second_cut);\n    new_mid = first_cut + len22;\n    doMerge(a, cmp, from, first_cut, new_mid, len11, len22);\n    doMerge(a, cmp, new_mid, second_cut, to, len1 - len11, len2 - len22);\n}\n\nfunction rotate<T>(a: T[], from: number, mid: number, to: number): void {\n    if (from == mid || mid == to) return;\n    let n = gcd(to - from, mid - from);\n    while (n-- != 0) {\n        const val = a[from + n];\n        const shift = mid - from;\n        let p1 = from + n;\n        let p2 = from + n + shift;\n        while (p2 != from + n) {\n            a[p1] = a[p2];\n            p1 = p2;\n            if (to - p2 > shift) p2 += shift;\n            else p2 = from + (shift - (to - p2));\n        }\n        a[p1] = val;\n    }\n}\n\nfunction gcd(m: number, n: number): number {\n    while (n != 0) {\n        const t = m % n;\n        m = n;\n        n = t;\n    }\n    return m;\n}\n\nfunction upper<T>(a: T[], cmp: Comparator<T>, from: number, to: number, val: number): number {\n    let len = to - from;\n    let half;\n    let mid;\n    while (len > 0) {\n        half = len >> 1;\n        mid = from + half;\n        if (cmp(a[val], a[mid]) < 0) {\n            len = half;\n        } else {\n            from = mid + 1;\n            len = len - half - 1;\n        }\n    }\n    return from;\n}\n\nfunction lower<T>(a: T[], cmp: Comparator<T>, from: number, to: number, val: number): number {\n    let len = to - from;\n    let half;\n    let mid;\n    while (len > 0) {\n        half = len >> 1;\n        mid = from + half;\n        if (cmp(a[mid], a[val]) < 0) {\n            from = mid + 1;\n            len = len - half - 1;\n        } else {\n            len = half;\n        }\n    }\n    return from;\n}\n","import { ascending } from \"~/basic\";\nimport { Comparator } from \"~/types\";\n\nexport function nativeSort<T>(arr: T[], cmp: Comparator<T> = ascending): T[] {\n    return arr.sort(cmp);\n}\n","import { ascending } from \"~/basic\";\nimport { Comparator } from \"~/types\";\n\n/**\n * Implements a highly optimized QuickSort algorithm to sort arrays in-place.\n *\n * This implementation includes several optimizations:\n * - Median-of-three pivot selection to avoid worst-case performance on sorted/reversed arrays\n * - 3-way partitioning for efficient handling of arrays with duplicate values\n * - Small array optimization using insertion sort for subarrays below a threshold size\n *\n * While this implementation is generally faster than mergeSort for most data distributions,\n * it does not guarantee stability (equal elements may not maintain their original order).\n *\n * @typeParam T - The type of elements to sort\n * @param arr - The array to sort\n * @param cmp - The comparator function to determine order\n * @param small - Size threshold below which insertion sort is used\n * @returns The sorted array (same reference as input)\n *\n * @example\n * ```typescript\n * // Sort numbers in-place\n * const nums = [3, 1, 4, 2];\n * quickSort(nums);\n * console.log(nums); // [1, 2, 3, 4]\n *\n * // Sort with custom comparator\n * const data = [3, 1, 4, 2];\n * quickSort(data, (a, b) => b - a);\n * console.log(data); // [4, 3, 2, 1]\n * ```\n *\n * @remarks\n * The algorithm performs particularly well on:\n * - Random data distributions\n * - Arrays with many duplicate values (using 3-way partitioning)\n * - Nearly sorted arrays (using median-of-three pivot selection)\n *\n * For fully reversed data arrays, benchmarks show that the native JavaScript\n * sort and mergeSort tend to perform better. Consider using those alternatives\n * if you're primarily sorting reversed data.\n */\nexport function quickSort<T>(arr: T[], cmp: Comparator<T> = ascending, small = 16): T[] {\n    if (arr.length <= 1) {\n        return arr;\n    }\n    quickSortHelper(arr, 0, arr.length - 1, cmp, small);\n    return arr;\n}\n\nfunction quickSortHelper<T>(a: T[], lo: number, hi: number, cmp: Comparator<T>, small: number): void {\n    if (lo < hi) {\n        // If the array is small, use insertion sort\n        // This is a common optimization for quicksort to improve performance on small arrays\n        if (hi - lo < small) {\n            for (let i = lo + 1; i <= hi; i++) {\n                let j = i;\n                while (j > lo) {\n                    if (cmp(a[j], a[j - 1]) < 0) {\n                        const tmp = a[j - 1];\n                        a[j - 1] = a[j];\n                        a[j] = tmp;\n                    } else break;\n                    j--;\n                }\n            }\n            return;\n        }\n\n        // Choose pivot using median of three\n        // This is a common optimization to avoid worst-case scenarios when the array is already sorted or nearly sorted\n        const pivotIndex = medianOfThree(a, lo, hi, cmp);\n        const pivot = a[pivotIndex];\n\n        // Move pivot to starting position\n        const tmp = a[lo];\n        a[lo] = a[pivotIndex];\n        a[pivotIndex] = tmp;\n\n        // 3-way partitioning to handle duplicates\n        // Partition the array into three sections: < pivot, = pivot, > pivot\n        // This is a Dijkstra's Dutch National Flag algorithm adaptation\n        // that efficiently handles arrays with many duplicate values by\n        // creating three partitions instead of two.\n\n        let lt = lo; // Less than: arr[lo..lt-1] < pivot\n        let gt = hi; // Greater than: arr[gt+1..hi] > pivot\n        let i = lo + 1; // Current element to examine: arr[lt..i-1] = pivot\n\n        while (i <= gt) {\n            const comp = cmp(a[i], pivot);\n            if (comp < 0) {\n                // Current element is less than pivot, move to left section\n                const tmp = a[lt];\n                a[lt] = a[i];\n                a[i] = tmp;\n                lt++;\n                i++;\n            } else if (comp > 0) {\n                // Current element is greater than pivot, move to right section\n                const tmp = a[i];\n                a[i] = a[gt];\n                a[gt] = tmp;\n                gt--;\n                // Don't increment i here since we need to examine the swapped element\n            } else {\n                // Current element equals pivot, keep in middle section\n                i++;\n            }\n        }\n\n        // Recursively sort the left and right sections\n        quickSortHelper(a, lo, lt - 1, cmp, small);\n        quickSortHelper(a, gt + 1, hi, cmp, small);\n    }\n}\n\n/**\n * Selects a good pivot using the median-of-three method.\n *\n * This function finds the median value among the first, middle, and last elements\n * of the array segment. Using this median as the pivot helps avoid the worst-case\n * O(n²) performance for already sorted or reverse-sorted arrays.\n *\n * @param arr - The array being sorted\n * @param lo - The lower bound of the current segment\n * @param hi - The upper bound of the current segment\n * @param cmp - The comparator function\n * @returns The index of the selected pivot (positioned at hi-1)\n */\nfunction medianOfThree<T>(arr: T[], lo: number, hi: number, cmp: Comparator<T>): number {\n    const mid = Math.floor((lo + hi) / 2);\n\n    // Sort lo, mid, hi elements\n    if (cmp(arr[mid], arr[lo]) < 0) {\n        const tmp = arr[lo];\n        arr[lo] = arr[mid];\n        arr[mid] = tmp;\n    }\n\n    if (cmp(arr[hi], arr[lo]) < 0) {\n        const tmp = arr[lo];\n        arr[lo] = arr[hi];\n        arr[hi] = tmp;\n    }\n\n    if (cmp(arr[hi], arr[mid]) < 0) {\n        const tmp = arr[mid];\n        arr[mid] = arr[hi];\n        arr[hi] = tmp;\n    }\n\n    // Move pivot (median) to hi-1 position\n    const tmp = arr[mid];\n    arr[mid] = arr[hi - 1];\n    arr[hi - 1] = tmp;\n\n    return hi - 1; // Return index of pivot\n}\n","import { ascending } from \"~/basic\";\nimport { Comparator } from \"~/types\";\n\n/**\n * Implements the TimSort algorithm to sort arrays in-place without galloping optimization.\n *\n * TimSort is a hybrid stable sorting algorithm derived from merge sort and\n * insertion sort, designed to perform well on many kinds of real-world data.\n * It was implemented by Tim Peters for Python's sorting function in 2002, and\n * is now used in Java, Android, and many other platforms as the standard sorting\n * algorithm.\n *\n * Key features of this implementation:\n * - Natural run detection and merging for optimal performance on partially sorted data\n * - Adaptive strategy that adjusts to the characteristics of the input data\n * - Small array optimization using insertion sort\n * - Maintains stability (equal elements preserve their relative order)\n *\n * @typeParam T - The type of elements to sort\n * @param arr - The array to sort (will be modified in-place)\n * @param cmp - The comparator function to determine order (defaults to ascending)\n * @returns The sorted array (same reference as input)\n *\n * @example\n * ```typescript\n * // Sort numbers in-place\n * const nums = [3, 1, 4, 2];\n * timSort(nums);\n * console.log(nums); // [1, 2, 3, 4]\n *\n * // Sort with custom comparator\n * const data = [3, 1, 4, 2];\n * timSort(data, (a, b) => b - a);\n * console.log(data); // [4, 3, 2, 1]\n * ```\n *\n * @remarks\n * This is a simplified TimSort implementation without galloping mode optimization.\n * It still performs well on:\n * - Partially sorted arrays\n * - Arrays with repeated patterns\n * - Real-world data with pre-existing order\n * - Arrays with distinct sections that are internally ordered\n */\nexport function timSort<T>(arr: T[], cmp: Comparator<T> = ascending): T[] {\n    if (arr.length <= 1) {\n        return arr;\n    }\n\n    // Determine the size of the smallest merge unit (run).\n    // This is based on the same logic used in Python and Java implementations.\n    const minRun = getMinimumRunLength(arr.length);\n\n    // Step 1: Sort small runs using insertion sort\n    for (let lo = 0; lo < arr.length; lo += minRun) {\n        const hi = Math.min(lo + minRun - 1, arr.length - 1);\n        for (let i = lo + 1; i <= hi; i++) {\n            let j = i;\n            while (j > lo) {\n                if (cmp(arr[j], arr[j - 1]) < 0) {\n                    const tmp = arr[j - 1];\n                    arr[j - 1] = arr[j];\n                    arr[j] = tmp;\n                } else break;\n                j--;\n            }\n        }\n    }\n\n    // Step 2: Merge sorted runs\n    // Start with runs of length minRun and double the size on each pass\n    for (let size = minRun; size < arr.length; size *= 2) {\n        for (let left = 0; left < arr.length; left += 2 * size) {\n            const mid = Math.min(arr.length - 1, left + size - 1);\n            const right = Math.min(arr.length - 1, left + 2 * size - 1);\n\n            // Only merge if there are at least two runs\n            if (mid < right) {\n                merge(arr, left, mid, right, cmp);\n            }\n        }\n    }\n\n    leftArr.length = 0;\n    rightArr.length = 0;\n    return arr;\n}\n\n/**\n * Calculates the minimum run length for the TimSort algorithm.\n *\n * Returns a value between 16 and 32, chosen to minimize the number of comparisons.\n * This formula is based on the original TimSort implementation by Tim Peters.\n *\n * @param n - The length of the array\n * @returns The minimum run length\n * @internal\n */\nfunction getMinimumRunLength(n: number): number {\n    let r = 0;\n    while (n >= MIN_MERGE) {\n        r |= n & 1;\n        n >>= 1;\n    }\n    return n + r;\n}\n\n/**\n * Minimum size of a run (a sorted sequence)\n * This value is used to determine when to use insertion sort\n * as an optimization for small arrays.\n */\nconst MIN_MERGE = 32;\n\n// optimization: keep these arrays outside of merge to avoid a lot of allocations\nconst leftArr: unknown[] = [];\nconst rightArr: unknown[] = [];\n\n/**\n * Merges two adjacent runs in-place.\n *\n * @param arr - The array containing the runs\n * @param left - Start index of the first run\n * @param mid - End index of the first run (inclusive)\n * @param right - End index of the second run (inclusive)\n * @param cmp - The comparator function\n * @internal\n */\nfunction merge<T>(arr: T[], left: number, mid: number, right: number, cmp: Comparator<T>): void {\n    // If the runs are already in order, no need to merge\n    if (cmp(arr[mid + 1], arr[mid]) >= 0) {\n        return;\n    }\n\n    // Size of the two runs\n    const len1 = mid - left + 1;\n    const len2 = right - mid;\n\n    // Create temporary arrays\n    if (leftArr.length < len1) {\n        leftArr.length = len1;\n    }\n    if (rightArr.length < len2) {\n        rightArr.length = len2;\n    }\n\n    // Copy data to temporary arrays\n    for (let i = 0; i < len1; i++) {\n        leftArr[i] = arr[left + i];\n    }\n    for (let i = 0; i < len2; i++) {\n        rightArr[i] = arr[mid + 1 + i];\n    }\n\n    // Initial indices for the left, right, and merged arrays\n    let i = 0; // Index for leftArr\n    let j = 0; // Index for rightArr\n    let k = left; // Index for the merged array\n\n    // Standard merge process without galloping\n    while (i < len1 && j < len2) {\n        if (cmp(rightArr[j] as T, leftArr[i] as T) > 0) {\n            // Taking element from left run\n            arr[k++] = leftArr[i++] as T;\n        } else {\n            // Taking element from right run\n            arr[k++] = rightArr[j++] as T;\n        }\n    }\n\n    // Copy the remaining elements from leftArr, if any\n    while (i < len1) {\n        arr[k++] = leftArr[i++] as T;\n    }\n\n    // Copy the remaining elements from rightArr, if any\n    while (j < len2) {\n        arr[k++] = rightArr[j++] as T;\n    }\n}\n","import { ascending } from \"./basic\";\nimport { isNativeSortStable } from \"./internal\";\nimport { Comparator } from \"./types\";\nimport { insertionRangeSort, insertionSort } from \"~/sorters/insertionsort\";\nimport { mergeSort } from \"~/sorters/mergesort\";\nimport { nativeSort } from \"~/sorters/nativesort\";\nimport { quickSort } from \"~/sorters/quicksort\";\nimport { timSort } from \"~/sorters/timsort\";\n\n/**\n * Sorts elements in an array in-place.\n *\n * This function applies a stable sort algorithm. It uses the browser's native\n * Array.sort if it's stable, or falls back to timSort otherwise.\n * The sort is performed in-place, modifying the original array.\n *\n * @typeParam T - The type of elements to sort\n * @param arr - The array to sort\n * @param cmp - The comparator function to determine order\n * @returns The sorted array (same reference as input)\n *\n * @example\n * ```typescript\n * // Sort numbers\n * sort([3, 1, 4, 2]); // [1, 2, 3, 4]\n *\n * // Sort with a custom comparator\n * sort([3, 1, 4, 2], (a, b) => b - a); // [4, 3, 2, 1]\n * ```\n */\nexport function sort<T>(arr: T[], cmp: Comparator<T> = ascending): T[] {\n    if (isNativeSortStable()) {\n        return arr.sort(cmp);\n    }\n    return timSort(arr, cmp);\n}\n\nexport { nativeSort, mergeSort, quickSort, timSort, insertionSort, insertionRangeSort, isNativeSortStable };\n"],"names":["Direction","Sensitivity","i","tmp"],"mappings":";;;;AAUgB,WAAA,UAAa,GAAM,GAAc;AAC7C,WAAO,MAAM,IAAI,IAAI,IAAI,IAAI,KAAK;AAAA,EACtC;AAUgB,WAAA,WAAc,GAAM,GAAc;AAC9C,WAAO,MAAM,IAAI,IAAI,IAAI,IAAI,KAAK;AAAA,EACtC;AAmBa,QAAA,WAA4B,MAAM;AAmBlC,QAAA,UAA2B,MAAM;AAiBlC,MAAA,8BAAAA,eAAL;AAIHA,eAAAA,WAAA,gBAAa,CAAb,IAAA;AAKAA,eAAAA,WAAA,eAAY,CAAZ,IAAA;AATQA,WAAAA;AAAAA,EAAA,GAAA,aAAA,CAAA,CAAA;AAuBL,WAAS,IAAO,aAAiD;AAC7D,WAAA,CAAC,CAAC,cAAc,YAAY;AAAA,EACvC;AAWgB,WAAA,GAAkC,KAAkB,MAAqB,WAA0B;AACxG,WAAA,CAAC,GAAG,MAAM,IAAI,IAAI,CAAC,GAAG,IAAI,CAAC,CAAC;AAAA,EACvC;AAUO,WAAS,SAAY,KAAqC;AACtD,WAAA,CAAC,GAAG,MAAM;AACb,iBAAW,MAAM,KAAK;AACZ,cAAA,MAAM,GAAG,GAAG,CAAC;AACf,YAAA,QAAQ,EAAU,QAAA;AAAA,MAAA;AAEnB,aAAA;AAAA,IACX;AAAA,EACJ;AAUgB,WAAA,KAAQ,IAAmB,QAAiC;AACjE,WAAA,SAAS,KAAK,CAAC,GAAG,MAAM,CAAC,GAAG,GAAG,CAAC;AAAA,EAC3C;ACjIgB,WAAA,MAAS,WAAkC,MAAqB,WAA0B;AAC/F,WAAA,MAAM,WAAW,CAAC,GAAG,MAAO,MAAM,IAAI,IAAI,IAAI,KAAK,GAAI,GAAG;AAAA,EACrE;AAoBO,WAAS,MACZ,UACA,aAA4B,WAC5B,YAA2B,WACd;AACN,WAAA,CAAC,GAAG,MAAM;AACP,YAAA,SAAS,SAAS,CAAC;AACnB,YAAA,SAAS,SAAS,CAAC;AAEnB,YAAA,cAAc,WAAW,QAAQ,MAAM;AACzC,UAAA,gBAAgB,EAAU,QAAA;AAEvB,aAAA,UAAU,GAAG,CAAC;AAAA,IACzB;AAAA,EACJ;AAmBgB,WAAA,YACZ,WACA,QACA,SACa;AACb,WAAO,CAAC,GAAG,MAAO,UAAU,GAAG,CAAC,IAAI,OAAO,GAAG,CAAC,IAAI,QAAQ,GAAG,CAAC;AAAA,EACnE;AAsBgB,WAAA,SAAe,KAAqC,MAAqB,WAA0B;AAC/G,WAAO,MAAM,CAAK,MAAA,IAAI,CAAC,KAAK,MAAM,GAAG;AAAA,EACzC;ACpFgB,WAAA,OAAU,IAAY,KAAoB;AAC/C,WAAA,MAAM,KAAK,OAAA,IAAW;AAAA,EACjC;AAgBa,QAAA,WAAW,OAAO,GAAG;AC3BhB,MAAA,gCAAAC,iBAAX;AAKHA,iBAAA,MAAO,IAAA;AAMPA,iBAAA,QAAS,IAAA;AAMTA,iBAAA,MAAO,IAAA;AAMPA,iBAAA,SAAU,IAAA;AAvBIA,WAAAA;AAAAA,EAAA,GAAA,eAAA,CAAA,CAAA;AAiCF,WAAA,QAAQ,cAA2B,QAAsC;AAC/E,UAAA,WAAW,IAAI,KAAK,SAAS,QAAW,EAAE,SAAS,MAAM,aAAa;AAC5E,WAAO,SAAS;AAAA,EACpB;AAea,QAAA,YAAY,QAAQ;AC5CjC,MAAI,sBAAsC;AASnC,WAAS,qBAA8B;AAC1C,QAAI,uBAAuB,MAAM;AACP,4BAAA,eAAe,YAAY,SAAS;AAAA,IAAA;AAEvD,WAAA;AAAA,EACX;AAcO,WAAS,eAAe,cAA4B,gBAA8B,OAAO,IAAa;AACzG,UAAM,MAAc,CAAC;AACf,UAAA,IAAI,KAAK,IAAI,KAAK,MAAM,OAAO,CAAC,GAAG,CAAC;AAE1C,aAAS,IAAI,GAAG,IAAI,MAAM,KAAK;AAC3B,UAAI,KAAK,EAAE,KAAK,KAAK,MAAM,KAAK,OAAO,IAAI,CAAC,GAAG,OAAO,EAAA,CAAG;AAAA,IAAA;AAI7D,eAAW,OAAO,CAAC,WAAW,YAAY,UAAU,OAAO,GAAG;AACpD,YAAA,SAAS,aAAa,IAAI,MAAM,GAAG,GAAG,EAAE,IAAI,CAAQ,SAAA,KAAK,KAAK;AAC9D,YAAA,WAAW,eAAe,IAAI,MAAM,GAAG,GAAG,EAAE,IAAI,CAAQ,SAAA,KAAK,KAAK;AACxE,UAAI,CAAC,aAAa,UAAU,MAAM,GAAG;AAC1B,eAAA;AAAA,MAAA;AAAA,IACX;AAEG,WAAA;AAAA,EACX;AAagB,WAAA,aAAa,UAAoB,QAA2B;AACpE,QAAA,SAAS,WAAW,OAAO,QAAQ;AAC5B,aAAA;AAAA,IAAA;AAEX,aAAS,IAAI,GAAG,IAAI,SAAS,QAAQ,KAAK;AACtC,UAAI,SAAS,CAAC,MAAM,OAAO,CAAC,GAAG;AACpB,eAAA;AAAA,MAAA;AAAA,IACX;AAEG,WAAA;AAAA,EACX;AClFgB,WAAA,cAAiB,KAAU,MAAqB,WAAgB;AACxE,QAAA,IAAI,UAAU,GAAG;AACV,aAAA;AAAA,IAAA;AAEX,uBAAmB,KAAK,GAAG,IAAI,SAAS,GAAG,GAAG;AACvC,WAAA;AAAA,EACX;AAWO,WAAS,mBAAsB,GAAQ,IAAY,IAAY,KAA0B;AAC5F,aAAS,IAAI,KAAK,GAAG,KAAK,IAAI,KAAK;AAC/B,UAAI,IAAI;AACR,aAAO,IAAI,IAAI;AACP,YAAA,IAAI,EAAE,CAAC,GAAG,EAAE,IAAI,CAAC,CAAC,IAAI,GAAG;AACnB,gBAAA,MAAM,EAAE,IAAI,CAAC;AACnB,YAAE,IAAI,CAAC,IAAI,EAAE,CAAC;AACd,YAAE,CAAC,IAAI;AAAA,QAAA,MACJ;AACP;AAAA,MAAA;AAAA,IACJ;AAAA,EAER;ACeO,WAAS,UAAa,KAAU,MAAqB,WAAW,QAAQ,IAAS;AACpF,QAAI,KAAK,KAAK,GAAG,IAAI,QAAQ,KAAK;AAC3B,WAAA;AAAA,EACX;AAEA,WAAS,IAAO,GAAQ,KAAoB,IAAY,IAAY,OAAe;AACzE,UAAA,SAAU,KAAK,MAAO;AACxB,QAAA,KAAK,KAAK,OAAO;AACjB,UAAI,MAAM,GAAI;AACd,eAAS,IAAI,KAAK,GAAG,IAAI,IAAI,KAAK;AAC9B,YAAI,IAAI;AACR,eAAO,IAAI,IAAI;AACP,cAAA,IAAI,EAAE,CAAC,GAAG,EAAE,IAAI,CAAC,CAAC,IAAI,GAAG;AACnB,kBAAA,MAAM,EAAE,IAAI,CAAC;AACnB,cAAE,IAAI,CAAC,IAAI,EAAE,CAAC;AACd,cAAE,CAAC,IAAI;AAAA,UAAA,MACJ;AACP;AAAA,QAAA;AAAA,MACJ;AAEJ;AAAA,IAAA;AAEJ,QAAI,GAAG,KAAK,IAAI,QAAQ,KAAK;AAC7B,QAAI,GAAG,KAAK,QAAQ,IAAI,KAAK;AACrB,YAAA,GAAG,KAAK,IAAI,QAAQ,IAAI,SAAS,IAAI,KAAK,MAAM;AAAA,EAC5D;AAEA,WAAS,QAAW,GAAQ,KAAoB,MAAc,OAAe,IAAY,MAAc,MAAc;AAC7G,QAAA,WAAW,YAAY,OAAO,OAAO;AACrC,QAAA,QAAQ,KAAK,QAAQ,EAAG;AACxB,QAAA,OAAO,QAAQ,GAAG;AACd,UAAA,IAAI,EAAE,KAAK,GAAG,EAAE,IAAI,CAAC,IAAI,GAAG;AACtB,cAAA,MAAM,EAAE,KAAK;AACjB,UAAA,KAAK,IAAI,EAAE,IAAI;AACjB,UAAE,IAAI,IAAI;AAAA,MAAA;AAEd;AAAA,IAAA;AAEJ,QAAI,OAAO,MAAM;AACb,cAAQ,QAAQ;AAChB,kBAAY,OAAO;AACnB,mBAAa,MAAM,GAAG,KAAK,OAAO,IAAI,SAAS;AAC/C,cAAQ,aAAa;AAAA,IAAA,OAClB;AACH,cAAQ,QAAQ;AAChB,mBAAa,QAAQ;AACrB,kBAAY,MAAM,GAAG,KAAK,MAAM,OAAO,UAAU;AACjD,cAAQ,YAAY;AAAA,IAAA;AAEjB,WAAA,GAAG,WAAW,OAAO,UAAU;AACtC,cAAU,YAAY;AACtB,YAAQ,GAAG,KAAK,MAAM,WAAW,SAAS,OAAO,KAAK;AAC9C,YAAA,GAAG,KAAK,SAAS,YAAY,IAAI,OAAO,OAAO,OAAO,KAAK;AAAA,EACvE;AAEA,WAAS,OAAU,GAAQ,MAAc,KAAa,IAAkB;AAChE,QAAA,QAAQ,OAAO,OAAO,GAAI;AAC9B,QAAI,IAAI,IAAI,KAAK,MAAM,MAAM,IAAI;AACjC,WAAO,OAAO,GAAG;AACP,YAAA,MAAM,EAAE,OAAO,CAAC;AACtB,YAAM,QAAQ,MAAM;AACpB,UAAI,KAAK,OAAO;AACZ,UAAA,KAAK,OAAO,IAAI;AACb,aAAA,MAAM,OAAO,GAAG;AACjB,UAAA,EAAE,IAAI,EAAE,EAAE;AACP,aAAA;AACD,YAAA,KAAK,KAAK,MAAa,OAAA;AAAA,YACtB,MAAK,QAAQ,SAAS,KAAK;AAAA,MAAA;AAEpC,QAAE,EAAE,IAAI;AAAA,IAAA;AAAA,EAEhB;AAEA,WAAS,IAAI,GAAW,GAAmB;AACvC,WAAO,KAAK,GAAG;AACX,YAAM,IAAI,IAAI;AACV,UAAA;AACA,UAAA;AAAA,IAAA;AAED,WAAA;AAAA,EACX;AAEA,WAAS,MAAS,GAAQ,KAAoB,MAAc,IAAY,KAAqB;AACzF,QAAI,MAAM,KAAK;AACX,QAAA;AACA,QAAA;AACJ,WAAO,MAAM,GAAG;AACZ,aAAO,OAAO;AACd,YAAM,OAAO;AACT,UAAA,IAAI,EAAE,GAAG,GAAG,EAAE,GAAG,CAAC,IAAI,GAAG;AACnB,cAAA;AAAA,MAAA,OACH;AACH,eAAO,MAAM;AACb,cAAM,MAAM,OAAO;AAAA,MAAA;AAAA,IACvB;AAEG,WAAA;AAAA,EACX;AAEA,WAAS,MAAS,GAAQ,KAAoB,MAAc,IAAY,KAAqB;AACzF,QAAI,MAAM,KAAK;AACX,QAAA;AACA,QAAA;AACJ,WAAO,MAAM,GAAG;AACZ,aAAO,OAAO;AACd,YAAM,OAAO;AACT,UAAA,IAAI,EAAE,GAAG,GAAG,EAAE,GAAG,CAAC,IAAI,GAAG;AACzB,eAAO,MAAM;AACb,cAAM,MAAM,OAAO;AAAA,MAAA,OAChB;AACG,cAAA;AAAA,MAAA;AAAA,IACV;AAEG,WAAA;AAAA,EACX;AC9JgB,WAAA,WAAc,KAAU,MAAqB,WAAgB;AAClE,WAAA,IAAI,KAAK,GAAG;AAAA,EACvB;ACsCO,WAAS,UAAa,KAAU,MAAqB,WAAW,QAAQ,IAAS;AAChF,QAAA,IAAI,UAAU,GAAG;AACV,aAAA;AAAA,IAAA;AAEX,oBAAgB,KAAK,GAAG,IAAI,SAAS,GAAG,KAAK,KAAK;AAC3C,WAAA;AAAA,EACX;AAEA,WAAS,gBAAmB,GAAQ,IAAY,IAAY,KAAoB,OAAqB;AACjG,QAAI,KAAK,IAAI;AAGL,UAAA,KAAK,KAAK,OAAO;AACjB,iBAASC,KAAI,KAAK,GAAGA,MAAK,IAAIA,MAAK;AAC/B,cAAI,IAAIA;AACR,iBAAO,IAAI,IAAI;AACP,gBAAA,IAAI,EAAE,CAAC,GAAG,EAAE,IAAI,CAAC,CAAC,IAAI,GAAG;AACnBC,oBAAAA,OAAM,EAAE,IAAI,CAAC;AACnB,gBAAE,IAAI,CAAC,IAAI,EAAE,CAAC;AACd,gBAAE,CAAC,IAAIA;AAAAA,YAAA,MACJ;AACP;AAAA,UAAA;AAAA,QACJ;AAEJ;AAAA,MAAA;AAKJ,YAAM,aAAa,cAAc,GAAG,IAAI,IAAI,GAAG;AACzC,YAAA,QAAQ,EAAE,UAAU;AAGpB,YAAA,MAAM,EAAE,EAAE;AACd,QAAA,EAAE,IAAI,EAAE,UAAU;AACpB,QAAE,UAAU,IAAI;AAQhB,UAAI,KAAK;AACT,UAAI,KAAK;AACT,UAAI,IAAI,KAAK;AAEb,aAAO,KAAK,IAAI;AACZ,cAAM,OAAO,IAAI,EAAE,CAAC,GAAG,KAAK;AAC5B,YAAI,OAAO,GAAG;AAEJA,gBAAAA,OAAM,EAAE,EAAE;AACd,YAAA,EAAE,IAAI,EAAE,CAAC;AACX,YAAE,CAAC,IAAIA;AACP;AACA;AAAA,QAAA,WACO,OAAO,GAAG;AAEXA,gBAAAA,OAAM,EAAE,CAAC;AACb,YAAA,CAAC,IAAI,EAAE,EAAE;AACX,YAAE,EAAE,IAAIA;AACR;AAAA,QAAA,OAEG;AAEH;AAAA,QAAA;AAAA,MACJ;AAIJ,sBAAgB,GAAG,IAAI,KAAK,GAAG,KAAK,KAAK;AACzC,sBAAgB,GAAG,KAAK,GAAG,IAAI,KAAK,KAAK;AAAA,IAAA;AAAA,EAEjD;AAeA,WAAS,cAAiB,KAAU,IAAY,IAAY,KAA4B;AACpF,UAAM,MAAM,KAAK,OAAO,KAAK,MAAM,CAAC;AAGhC,QAAA,IAAI,IAAI,GAAG,GAAG,IAAI,EAAE,CAAC,IAAI,GAAG;AACtBA,YAAAA,OAAM,IAAI,EAAE;AACd,UAAA,EAAE,IAAI,IAAI,GAAG;AACjB,UAAI,GAAG,IAAIA;AAAAA,IAAA;AAGX,QAAA,IAAI,IAAI,EAAE,GAAG,IAAI,EAAE,CAAC,IAAI,GAAG;AACrBA,YAAAA,OAAM,IAAI,EAAE;AACd,UAAA,EAAE,IAAI,IAAI,EAAE;AAChB,UAAI,EAAE,IAAIA;AAAAA,IAAA;AAGV,QAAA,IAAI,IAAI,EAAE,GAAG,IAAI,GAAG,CAAC,IAAI,GAAG;AACtBA,YAAAA,OAAM,IAAI,GAAG;AACf,UAAA,GAAG,IAAI,IAAI,EAAE;AACjB,UAAI,EAAE,IAAIA;AAAAA,IAAA;AAIR,UAAA,MAAM,IAAI,GAAG;AACnB,QAAI,GAAG,IAAI,IAAI,KAAK,CAAC;AACjB,QAAA,KAAK,CAAC,IAAI;AAEd,WAAO,KAAK;AAAA,EAChB;ACnHgB,WAAA,QAAW,KAAU,MAAqB,WAAgB;AAClE,QAAA,IAAI,UAAU,GAAG;AACV,aAAA;AAAA,IAAA;AAKL,UAAA,SAAS,oBAAoB,IAAI,MAAM;AAG7C,aAAS,KAAK,GAAG,KAAK,IAAI,QAAQ,MAAM,QAAQ;AACtC,YAAA,KAAK,KAAK,IAAI,KAAK,SAAS,GAAG,IAAI,SAAS,CAAC;AACnD,eAAS,IAAI,KAAK,GAAG,KAAK,IAAI,KAAK;AAC/B,YAAI,IAAI;AACR,eAAO,IAAI,IAAI;AACP,cAAA,IAAI,IAAI,CAAC,GAAG,IAAI,IAAI,CAAC,CAAC,IAAI,GAAG;AACvB,kBAAA,MAAM,IAAI,IAAI,CAAC;AACrB,gBAAI,IAAI,CAAC,IAAI,IAAI,CAAC;AAClB,gBAAI,CAAC,IAAI;AAAA,UAAA,MACN;AACP;AAAA,QAAA;AAAA,MACJ;AAAA,IACJ;AAKJ,aAAS,OAAO,QAAQ,OAAO,IAAI,QAAQ,QAAQ,GAAG;AAClD,eAAS,OAAO,GAAG,OAAO,IAAI,QAAQ,QAAQ,IAAI,MAAM;AAC9C,cAAA,MAAM,KAAK,IAAI,IAAI,SAAS,GAAG,OAAO,OAAO,CAAC;AAC9C,cAAA,QAAQ,KAAK,IAAI,IAAI,SAAS,GAAG,OAAO,IAAI,OAAO,CAAC;AAG1D,YAAI,MAAM,OAAO;AACb,gBAAM,KAAK,MAAM,KAAK,OAAO,GAAG;AAAA,QAAA;AAAA,MACpC;AAAA,IACJ;AAGJ,YAAQ,SAAS;AACjB,aAAS,SAAS;AACX,WAAA;AAAA,EACX;AAYA,WAAS,oBAAoB,GAAmB;AAC5C,QAAI,IAAI;AACR,WAAO,KAAK,WAAW;AACnB,WAAK,IAAI;AACH,YAAA;AAAA,IAAA;AAEV,WAAO,IAAI;AAAA,EACf;AAOA,QAAM,YAAY;AAGlB,QAAM,UAAqB,CAAC;AAC5B,QAAM,WAAsB,CAAC;AAY7B,WAAS,MAAS,KAAU,MAAc,KAAa,OAAe,KAA0B;AAExF,QAAA,IAAI,IAAI,MAAM,CAAC,GAAG,IAAI,GAAG,CAAC,KAAK,GAAG;AAClC;AAAA,IAAA;AAIE,UAAA,OAAO,MAAM,OAAO;AAC1B,UAAM,OAAO,QAAQ;AAGjB,QAAA,QAAQ,SAAS,MAAM;AACvB,cAAQ,SAAS;AAAA,IAAA;AAEjB,QAAA,SAAS,SAAS,MAAM;AACxB,eAAS,SAAS;AAAA,IAAA;AAItB,aAASD,KAAI,GAAGA,KAAI,MAAMA,MAAK;AAC3B,cAAQA,EAAC,IAAI,IAAI,OAAOA,EAAC;AAAA,IAAA;AAE7B,aAASA,KAAI,GAAGA,KAAI,MAAMA,MAAK;AAC3B,eAASA,EAAC,IAAI,IAAI,MAAM,IAAIA,EAAC;AAAA,IAAA;AAIjC,QAAI,IAAI;AACR,QAAI,IAAI;AACR,QAAI,IAAI;AAGD,WAAA,IAAI,QAAQ,IAAI,MAAM;AACrB,UAAA,IAAI,SAAS,CAAC,GAAQ,QAAQ,CAAC,CAAM,IAAI,GAAG;AAExC,YAAA,GAAG,IAAI,QAAQ,GAAG;AAAA,MAAA,OACnB;AAEC,YAAA,GAAG,IAAI,SAAS,GAAG;AAAA,MAAA;AAAA,IAC3B;AAIJ,WAAO,IAAI,MAAM;AACT,UAAA,GAAG,IAAI,QAAQ,GAAG;AAAA,IAAA;AAI1B,WAAO,IAAI,MAAM;AACT,UAAA,GAAG,IAAI,SAAS,GAAG;AAAA,IAAA;AAAA,EAE/B;ACrJgB,WAAA,KAAQ,KAAU,MAAqB,WAAgB;AACnE,QAAI,sBAAsB;AACf,aAAA,IAAI,KAAK,GAAG;AAAA,IAAA;AAEhB,WAAA,QAAQ,KAAK,GAAG;AAAA,EAC3B;;;;;;;;;;;;;;;;;;;;;;;;;;;;;"}