1 line
7.2 KiB
Text
1 line
7.2 KiB
Text
|
{"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 de
|