{"version":3,"file":"quickSelect-B4eZ0JeB.js","names":[],"sources":["../src/internal/quickSelect.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"],"mappings":"8CAqBA,MAAa,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,EAAY,EAAM,EAAG,EAAE,CACvB,GAAK,GAOT,OAHA,EAAY,EAAM,EAAG,EAAM,CAGpB"}