1 line
7.2 KiB
Plaintext
1 line
7.2 KiB
Plaintext
{"version":3,"file":"nthBy-BuKDKHln.cjs","names":["purryOrderRulesWithArgument"],"sources":["../src/internal/quickSelect.ts","../src/nthBy.ts"],"sourcesContent":["/**\n * A simple implementation of the *QuickSelect* algorithm.\n *\n * @see https://en.wikipedia.org/wiki/Quickselect\n */\n\nimport { swapInPlace } from \"./swapInPlace\";\nimport type { CompareFunction } from \"./types/CompareFunction\";\n\n/**\n * Perform QuickSelect on the given data. Notice that the data would be cloned\n * shallowly so that it could be mutated in-place, and then discarded once the\n * algorithm is done. This means that running this function multiple times on\n * the same array might be slower then sorting the array before.\n *\n * @param data - The data to perform the selection on.\n * @param index - The index of the item we are looking for.\n * @param compareFn - The compare function to use for sorting.\n * @returns The item at the given index, or `undefined` if the index is out-of-\n * bounds.\n */\nexport const quickSelect = <T>(\n data: readonly T[],\n index: number,\n compareFn: CompareFunction<T>,\n): T | undefined =>\n index < 0 || index >= data.length\n ? // Quickselect doesn't work with out-of-bound indices\n undefined\n : quickSelectImplementation(\n // We need to clone the array because quickSelect mutates it in-place.\n [...data],\n 0 /* left */,\n data.length - 1 /* right */,\n index,\n compareFn,\n );\n\n/**\n * The actual implementation, called recursively.\n */\nfunction quickSelectImplementation<T>(\n // eslint-disable-next-line @typescript-eslint/prefer-readonly-parameter-types -- Intentional!\n data: T[],\n left: number,\n right: number,\n index: number,\n compareFn: CompareFunction<T>,\n): T {\n if (left === right) {\n return data[left]!;\n }\n\n const pivotIndex = partition(data, left, right, compareFn);\n\n return index === pivotIndex\n ? // Once a pivot is chosen it's location is final, so if it matches the\n // index we found out item!\n data[index]!\n : quickSelectImplementation(\n data,\n // We continue by recursing into the partition where index would be\n index < pivotIndex ? left : pivotIndex + 1,\n index < pivotIndex ? pivotIndex - 1 : right,\n index,\n compareFn,\n );\n}\n\nfunction partition<T>(\n // eslint-disable-next-line @typescript-eslint/prefer-readonly-parameter-types -- Intentional!\n data: T[],\n left: number,\n right: number,\n compareFn: CompareFunction<T>,\n): number {\n const pivot = data[right]!;\n\n let i = left;\n for (let j = left; j < right; j++) {\n if (compareFn(data[j]!, pivot) < 0) {\n // Move items smaller then the pivot to the start of the array.\n swapInPlace(data, i, j);\n i += 1;\n }\n }\n\n swapInPlace(data, i, right);\n\n // The location of the pivot by the end of the partition function.\n return i;\n}\n","import {\n purryOrderRulesWithArgument,\n type OrderRule,\n} from \"./internal/purryOrderRules\";\nimport { quickSelect } from \"./internal/quickSelect\";\nimport type { CompareFunction } from \"./internal/types/CompareFunction\";\nimport type { IterableContainer } from \"./internal/types/IterableContainer\";\nimport type { NonEmptyArray } from \"./internal/types/NonEmptyArray\";\n\n/**\n * Retrieves the element that would be at the given index if the array were sorted according to specified rules. This function uses the *QuickSelect* algorithm running at an average complexity of *O(n)*. Semantically it is equivalent to `sortBy(data, ...rules).at(index)` which would run at *O(nlogn)*.\n *\n * See also `firstBy` which provides an even more efficient algorithm and a stricter return type, but only for `index === 0`. See `takeFirstBy` to get all the elements up to and including `index`.\n *\n * @param data - The input array.\n * @param index - The zero-based index for selecting the element in the sorted order. Negative indices count backwards from the end.\n * @param rules - A variadic array of order rules defining the sorting criteria. Each order rule is a projection function that extracts a comparable value from the data. Sorting is based on these extracted values using the native `<` and `>` operators. Earlier rules take precedence over later ones. Use the syntax `[projection, \"desc\"]` for descending order.\n * @returns The element at the specified index in the sorted order, or `undefined` if the index is out of bounds.\n * @signature\n * R.nthBy(data, index, ...rules);\n * @example\n * R.nthBy([2,1,4,5,3,], 2, identity()); // => 3\n * @dataFirst\n * @category Array\n */\nexport function nthBy<T extends IterableContainer>(\n data: T,\n index: number,\n ...rules: Readonly<NonEmptyArray<OrderRule<T[number]>>>\n): T[number] | undefined;\n\n/**\n * Retrieves the element that would be at the given index if the array were sorted according to specified rules. This function uses the *QuickSelect* algorithm running at an average complexity of *O(n)*. Semantically it is equivalent to `sortBy(data, ...rules)[index]` which would run at *O(nlogn)*.\n *\n * See also `firstBy` which provides an even more efficient algorithm and a stricter return type, but only for `index === 0`. See `takeFirstBy` to get all the elements up to and including `index`.\n *\n * @param index - The zero-based index for selecting the element in the sorted order. Negative indices count backwards from the end.\n * @param rules - A variadic array of order rules defining the sorting criteria. Each order rule is a projection function that extracts a comparable value from the data. Sorting is based on these extracted values using the native `<` and `>` operators. Earlier rules take precedence over later ones. Use the syntax `[projection, \"desc\"]` for descending order.\n * @returns The element at the specified index in the sorted order, or `undefined` if the index is out of bounds.\n * @signature\n * R.nthBy(index, ...rules)(data);\n * @example\n * R.pipe([2,1,4,5,3,], R.nthBy(2, identity())); // => 3\n * @dataLast\n * @category Array\n */\nexport function nthBy<T extends IterableContainer>(\n index: number,\n ...rules: Readonly<NonEmptyArray<OrderRule<T[number]>>>\n): (data: T) => T[number] | undefined;\n\nexport function nthBy(...args: readonly unknown[]): unknown {\n return purryOrderRulesWithArgument(nthByImplementation, args);\n}\n\nconst nthByImplementation = <T>(\n data: readonly T[],\n compareFn: CompareFunction<T>,\n index: number,\n): T | undefined =>\n quickSelect(\n data,\n // Allow negative indices gracefully\n index >= 0 ? index : data.length + index,\n compareFn,\n );\n"],"mappings":"0FAqBa,GACX,EACA,EACA,IAEA,EAAQ,GAAK,GAAS,EAAK,OAEvB,IAAA,GACA,EAEE,CAAC,GAAG,EAAK,CACT,EACA,EAAK,OAAS,EACd,EACA,EACD,CAKP,SAAS,EAEP,EACA,EACA,EACA,EACA,EACG,CACH,GAAI,IAAS,EACX,OAAO,EAAK,GAGd,IAAM,EAAa,EAAU,EAAM,EAAM,EAAO,EAAU,CAE1D,OAAO,IAAU,EAGb,EAAK,GACL,EACE,EAEA,EAAQ,EAAa,EAAO,EAAa,EACzC,EAAQ,EAAa,EAAa,EAAI,EACtC,EACA,EACD,CAGP,SAAS,EAEP,EACA,EACA,EACA,EACQ,CACR,IAAM,EAAQ,EAAK,GAEf,EAAI,EACR,IAAK,IAAI,EAAI,EAAM,EAAI,EAAO,IACxB,EAAU,EAAK,GAAK,EAAM,CAAG,IAE/B,EAAA,EAAY,EAAM,EAAG,EAAE,CACvB,GAAK,GAOT,OAHA,EAAA,EAAY,EAAM,EAAG,EAAM,CAGpB,ECvCT,SAAgB,EAAM,GAAG,EAAmC,CAC1D,OAAOA,EAAAA,EAA4B,EAAqB,EAAK,CAG/D,MAAM,GACJ,EACA,EACA,IAEA,EACE,EAEA,GAAS,EAAI,EAAQ,EAAK,OAAS,EACnC,EACD"} |