{"version":3,"file":"quantile.js","sourceRoot":"","sources":["../../../src/utils/transform/quantile.ts"],"names":[],"mappings":";AAAA,4CAA4C;;;AAE5C;;;;;;;;;;;;GAYG;AACH,SAAgB,cAAc,CAAC,CAAW,EAAE,CAAS;IACnD,IAAM,GAAG,GAAG,CAAC,CAAC,MAAM,GAAG,CAAC,CAAC;IACzB,IAAI,CAAC,CAAC,MAAM,KAAK,CAAC,EAAE;QAClB,MAAM,IAAI,KAAK,CAAC,4CAA4C,CAAC,CAAC;KAC/D;SAAM,IAAI,CAAC,GAAG,CAAC,IAAI,CAAC,GAAG,CAAC,EAAE;QACzB,MAAM,IAAI,KAAK,CAAC,mCAAmC,CAAC,CAAC;KACtD;SAAM,IAAI,CAAC,KAAK,CAAC,EAAE;QAClB,8CAA8C;QAC9C,OAAO,CAAC,CAAC,CAAC,CAAC,MAAM,GAAG,CAAC,CAAC,CAAC;KACxB;SAAM,IAAI,CAAC,KAAK,CAAC,EAAE;QAClB,+CAA+C;QAC/C,OAAO,CAAC,CAAC,CAAC,CAAC,CAAC;KACb;SAAM,IAAI,GAAG,GAAG,CAAC,KAAK,CAAC,EAAE;QACxB,wDAAwD;QACxD,OAAO,CAAC,CAAC,IAAI,CAAC,IAAI,CAAC,GAAG,CAAC,GAAG,CAAC,CAAC,CAAC;KAC9B;SAAM,IAAI,CAAC,CAAC,MAAM,GAAG,CAAC,KAAK,CAAC,EAAE;QAC7B,qEAAqE;QACrE,sCAAsC;QACtC,OAAO,CAAC,CAAC,CAAC,GAAG,GAAG,CAAC,CAAC,GAAG,CAAC,CAAC,GAAG,CAAC,CAAC,GAAG,CAAC,CAAC;KAClC;SAAM;QACL,kDAAkD;QAClD,4DAA4D;QAC5D,OAAO,CAAC,CAAC,GAAG,CAAC,CAAC;KACf;AACH,CAAC;AAxBD,wCAwBC;AAED;;;;;GAKG;AACH,SAAgB,IAAI,CAAU,GAAQ,EAAE,CAAS,EAAE,CAAS;IAC1D,IAAM,GAAG,GAAG,GAAG,CAAC,CAAC,CAAC,CAAC;IACnB,GAAG,CAAC,CAAC,CAAC,GAAG,GAAG,CAAC,CAAC,CAAC,CAAC;IAChB,GAAG,CAAC,CAAC,CAAC,GAAG,GAAG,CAAC;AACf,CAAC;AAJD,oBAIC;AAED;;;;;;;;;;;;;;;GAeG;AACH,SAAgB,WAAW,CAAC,GAAa,EAAE,CAAC,EAAE,IAAa,EAAE,KAAc;IACzE,IAAI,GAAG,IAAI,IAAI,CAAC,CAAC;IACjB,KAAK,GAAG,KAAK,IAAI,GAAG,CAAC,MAAM,GAAG,CAAC,CAAC;IAEhC,OAAO,KAAK,GAAG,IAAI,EAAE;QACnB,8FAA8F;QAC9F,IAAI,KAAK,GAAG,IAAI,GAAG,GAAG,EAAE;YACtB,IAAM,CAAC,GAAG,KAAK,GAAG,IAAI,GAAG,CAAC,CAAC;YAC3B,IAAM,CAAC,GAAG,CAAC,GAAG,IAAI,GAAG,CAAC,CAAC;YACvB,IAAM,CAAC,GAAG,IAAI,CAAC,GAAG,CAAC,CAAC,CAAC,CAAC;YACtB,IAAM,CAAC,GAAG,GAAG,GAAG,IAAI,CAAC,GAAG,CAAC,CAAC,CAAC,GAAG,CAAC,CAAC,GAAG,CAAC,CAAC,CAAC;YACtC,IAAI,EAAE,GAAG,GAAG,GAAG,IAAI,CAAC,IAAI,CAAC,CAAC,CAAC,GAAG,CAAC,GAAG,CAAC,CAAC,GAAG,CAAC,CAAC,CAAC,GAAG,CAAC,CAAC,CAAC;YAChD,IAAI,CAAC,GAAG,CAAC,GAAG,CAAC,GAAG,CAAC;gBAAE,EAAE,IAAI,CAAC,CAAC,CAAC;YAC5B,IAAM,OAAO,GAAG,IAAI,CAAC,GAAG,CAAC,IAAI,EAAE,IAAI,CAAC,KAAK,CAAC,CAAC,GAAG,CAAC,CAAC,GAAG,CAAC,CAAC,GAAG,CAAC,GAAG,EAAE,CAAC,CAAC,CAAC;YACjE,IAAM,QAAQ,GAAG,IAAI,CAAC,GAAG,CAAC,KAAK,EAAE,IAAI,CAAC,KAAK,CAAC,CAAC,GAAG,CAAC,CAAC,CAAC,GAAG,CAAC,CAAC,GAAG,CAAC,CAAC,GAAG,CAAC,GAAG,EAAE,CAAC,CAAC,CAAC;YACzE,WAAW,CAAC,GAAG,EAAE,CAAC,EAAE,OAAO,EAAE,QAAQ,CAAC,CAAC;SACxC;QAED,IAAM,CAAC,GAAG,GAAG,CAAC,CAAC,CAAC,CAAC;QACjB,IAAI,CAAC,GAAG,IAAI,CAAC;QACb,IAAI,CAAC,GAAG,KAAK,CAAC;QAEd,IAAI,CAAC,GAAG,EAAE,IAAI,EAAE,CAAC,CAAC,CAAC;QACnB,IAAI,GAAG,CAAC,KAAK,CAAC,GAAG,CAAC;YAAE,IAAI,CAAC,GAAG,EAAE,IAAI,EAAE,KAAK,CAAC,CAAC;QAE3C,OAAO,CAAC,GAAG,CAAC,EAAE;YACZ,IAAI,CAAC,GAAG,EAAE,CAAC,EAAE,CAAC,CAAC,CAAC;YAChB,CAAC,EAAE,CAAC;YACJ,CAAC,EAAE,CAAC;YACJ,OAAO,GAAG,CAAC,CAAC,CAAC,GAAG,CAAC;gBAAE,CAAC,EAAE,CAAC;YACvB,OAAO,GAAG,CAAC,CAAC,CAAC,GAAG,CAAC;gBAAE,CAAC,EAAE,CAAC;SACxB;QAED,IAAI,GAAG,CAAC,IAAI,CAAC,KAAK,CAAC;YAAE,IAAI,CAAC,GAAG,EAAE,IAAI,EAAE,CAAC,CAAC,CAAC;aACnC;YACH,CAAC,EAAE,CAAC;YACJ,IAAI,CAAC,GAAG,EAAE,CAAC,EAAE,KAAK,CAAC,CAAC;SACrB;QAED,IAAI,CAAC,IAAI,CAAC;YAAE,IAAI,GAAG,CAAC,GAAG,CAAC,CAAC;QACzB,IAAI,CAAC,IAAI,CAAC;YAAE,KAAK,GAAG,CAAC,GAAG,CAAC,CAAC;KAC3B;AACH,CAAC;AA1CD,kCA0CC;AAyBD,SAAS,QAAQ,CAAC,CAAM,EAAE,CAAM;IAC9B,IAAM,IAAI,GAAG,CAAC,CAAC,KAAK,EAAE,CAAC;IAEvB,IAAI,KAAK,CAAC,OAAO,CAAC,CAAC,CAAC,EAAE;QACpB,uEAAuE;QACvE,mEAAmE;QACnE,mBAAmB,CAAC,IAAI,EAAE,CAAC,CAAC,CAAC;QAC7B,8BAA8B;QAC9B,IAAM,OAAO,GAAa,EAAE,CAAC;QAC7B,8BAA8B;QAC9B,KAAK,IAAI,CAAC,GAAG,CAAC,EAAE,CAAC,GAAG,CAAC,CAAC,MAAM,EAAE,CAAC,EAAE,EAAE;YACjC,OAAO,CAAC,CAAC,CAAC,GAAG,cAAc,CAAC,IAAI,EAAE,CAAC,CAAC,CAAC,CAAC,CAAC,CAAC;SACzC;QACD,OAAO,OAAO,CAAC;KAChB;SAAM;QACL,IAAM,GAAG,GAAG,aAAa,CAAC,IAAI,CAAC,MAAM,EAAE,CAAC,CAAC,CAAC;QAC1C,cAAc,CAAC,IAAI,EAAE,GAAG,EAAE,CAAC,EAAE,IAAI,CAAC,MAAM,GAAG,CAAC,CAAC,CAAC;QAC9C,OAAO,cAAc,CAAC,IAAI,EAAE,CAAC,CAAC,CAAC;KAChC;AACH,CAAC;AA4DQ,4BAAQ;AA1DjB,SAAS,cAAc,CAAC,GAAG,EAAE,CAAC,EAAE,IAAI,EAAE,KAAK;IACzC,IAAI,CAAC,GAAG,CAAC,KAAK,CAAC,EAAE;QACf,WAAW,CAAC,GAAG,EAAE,CAAC,EAAE,IAAI,EAAE,KAAK,CAAC,CAAC;KAClC;SAAM;QACL,CAAC,GAAG,IAAI,CAAC,KAAK,CAAC,CAAC,CAAC,CAAC;QAClB,WAAW,CAAC,GAAG,EAAE,CAAC,EAAE,IAAI,EAAE,KAAK,CAAC,CAAC;QACjC,WAAW,CAAC,GAAG,EAAE,CAAC,GAAG,CAAC,EAAE,CAAC,GAAG,CAAC,EAAE,KAAK,CAAC,CAAC;KACvC;AACH,CAAC;AAED,SAAS,mBAAmB,CAAC,GAAG,EAAE,CAAC;IACjC,IAAM,OAAO,GAAG,CAAC,CAAC,CAAC,CAAC;IACpB,KAAK,IAAI,CAAC,GAAG,CAAC,EAAE,CAAC,GAAG,CAAC,CAAC,MAAM,EAAE,CAAC,EAAE,EAAE;QACjC,OAAO,CAAC,IAAI,CAAC,aAAa,CAAC,GAAG,CAAC,MAAM,EAAE,CAAC,CAAC,CAAC,CAAC,CAAC,CAAC,CAAC;KAC/C;IACD,OAAO,CAAC,IAAI,CAAC,GAAG,CAAC,MAAM,GAAG,CAAC,CAAC,CAAC;IAC7B,OAAO,CAAC,IAAI,CAAC,OAAO,CAAC,CAAC;IAEtB,IAAM,KAAK,GAAG,CAAC,CAAC,EAAE,OAAO,CAAC,MAAM,GAAG,CAAC,CAAC,CAAC;IAEtC,OAAO,KAAK,CAAC,MAAM,EAAE;QACnB,IAAM,CAAC,GAAG,IAAI,CAAC,IAAI,CAAC,KAAK,CAAC,GAAG,EAAE,CAAC,CAAC;QACjC,IAAM,CAAC,GAAG,IAAI,CAAC,KAAK,CAAC,KAAK,CAAC,GAAG,EAAE,CAAC,CAAC;QAClC,IAAI,CAAC,GAAG,CAAC,IAAI,CAAC;YAAE,SAAS;QAEzB,IAAM,CAAC,GAAG,IAAI,CAAC,KAAK,CAAC,CAAC,CAAC,GAAG,CAAC,CAAC,GAAG,CAAC,CAAC,CAAC;QAClC,cAAc,CAAC,GAAG,EAAE,OAAO,CAAC,CAAC,CAAC,EAAE,IAAI,CAAC,KAAK,CAAC,OAAO,CAAC,CAAC,CAAC,CAAC,EAAE,IAAI,CAAC,IAAI,CAAC,OAAO,CAAC,CAAC,CAAC,CAAC,CAAC,CAAC;QAE/E,KAAK,CAAC,IAAI,CAAC,CAAC,EAAE,CAAC,EAAE,CAAC,EAAE,CAAC,CAAC,CAAC;KACxB;AACH,CAAC;AAED,SAAS,OAAO,CAAC,CAAC,EAAE,CAAC;IACnB,OAAO,CAAC,GAAG,CAAC,CAAC;AACf,CAAC;AAED,SAAS,aAAa,CAAC,GAAG,EAAE,CAAC;IAC3B,IAAM,GAAG,GAAG,GAAG,GAAG,CAAC,CAAC;IACpB,IAAI,CAAC,KAAK,CAAC,EAAE;QACX,4CAA4C;QAC5C,OAAO,GAAG,GAAG,CAAC,CAAC;KAChB;SAAM,IAAI,CAAC,KAAK,CAAC,EAAE;QAClB,6CAA6C;QAC7C,OAAO,CAAC,CAAC;KACV;SAAM,IAAI,GAAG,GAAG,CAAC,KAAK,CAAC,EAAE;QACxB,0DAA0D;QAC1D,OAAO,IAAI,CAAC,IAAI,CAAC,GAAG,CAAC,GAAG,CAAC,CAAC;KAC3B;SAAM,IAAI,GAAG,GAAG,CAAC,KAAK,CAAC,EAAE;QACxB,sEAAsE;QACtE,uEAAuE;QACvE,OAAO,GAAG,GAAG,GAAG,CAAC;KAClB;SAAM;QACL,kDAAkD;QAClD,4CAA4C;QAC5C,OAAO,GAAG,CAAC;KACZ;AACH,CAAC","sourcesContent":["// from https://github.com/simple-statistics\n\n/**\n * This is the internal implementation of quantiles: when you know\n * that the order is sorted, you don't need to re-sort it, and the computations\n * are faster.\n *\n * @param {Array<number>} x sample of one or more data points\n * @param {number} p desired quantile: a number between 0 to 1, inclusive\n * @returns {number} quantile value\n * @throws {Error} if p ix outside of the range from 0 to 1\n * @throws {Error} if x is empty\n * @example\n * quantileSorted([3, 6, 7, 8, 8, 9, 10, 13, 15, 16, 20], 0.5); // => 9\n */\nexport function quantileSorted(x: number[], p: number) {\n  const idx = x.length * p;\n  if (x.length === 0) {\n    throw new Error('quantile requires at least one data point.');\n  } else if (p < 0 || p > 1) {\n    throw new Error('quantiles must be between 0 and 1');\n  } else if (p === 1) {\n    // If p is 1, directly return the last element\n    return x[x.length - 1];\n  } else if (p === 0) {\n    // If p is 0, directly return the first element\n    return x[0];\n  } else if (idx % 1 !== 0) {\n    // If p is not integer, return the next element in array\n    return x[Math.ceil(idx) - 1];\n  } else if (x.length % 2 === 0) {\n    // If the list has even-length, we'll take the average of this number\n    // and the next value, if there is one\n    return (x[idx - 1] + x[idx]) / 2;\n  } else {\n    // Finally, in the simple case of an integer value\n    // with an odd-length list, return the x value at the index.\n    return x[idx];\n  }\n}\n\n/**\n * 交换数组位置\n * @param arr T[]\n * @param i number\n * @param j number\n */\nexport function swap<T = any>(arr: T[], i: number, j: number): void {\n  const tmp = arr[i];\n  arr[i] = arr[j];\n  arr[j] = tmp;\n}\n\n/**\n * Rearrange items in `arr` so that all items in `[left, k]` range are the smallest.\n * The `k`-th element will have the `(k - left + 1)`-th smallest value in `[left, right]`.\n *\n * Implements Floyd-Rivest selection algorithm https://en.wikipedia.org/wiki/Floyd-Rivest_algorithm\n *\n * @param {Array<number>} arr input array\n * @param {number} k pivot index\n * @param {number} [left] left index\n * @param {number} [right] right index\n * @returns {void} mutates input array\n * @example\n * var arr = [65, 28, 59, 33, 21, 56, 22, 95, 50, 12, 90, 53, 28, 77, 39];\n * quickselect(arr, 8);\n * // = [39, 28, 28, 33, 21, 12, 22, 50, 53, 56, 59, 65, 90, 77, 95]\n */\nexport function quickselect(arr: number[], k, left?: number, right?: number): void {\n  left = left || 0;\n  right = right || arr.length - 1;\n\n  while (right > left) {\n    // 600 and 0.5 are arbitrary constants chosen in the original paper to minimize execution time\n    if (right - left > 600) {\n      const n = right - left + 1;\n      const m = k - left + 1;\n      const z = Math.log(n);\n      const s = 0.5 * Math.exp((2 * z) / 3);\n      let sd = 0.5 * Math.sqrt((z * s * (n - s)) / n);\n      if (m - n / 2 < 0) sd *= -1;\n      const newLeft = Math.max(left, Math.floor(k - (m * s) / n + sd));\n      const newRight = Math.min(right, Math.floor(k + ((n - m) * s) / n + sd));\n      quickselect(arr, k, newLeft, newRight);\n    }\n\n    const t = arr[k];\n    let i = left;\n    let j = right;\n\n    swap(arr, left, k);\n    if (arr[right] > t) swap(arr, left, right);\n\n    while (i < j) {\n      swap(arr, i, j);\n      i++;\n      j--;\n      while (arr[i] < t) i++;\n      while (arr[j] > t) j--;\n    }\n\n    if (arr[left] === t) swap(arr, left, j);\n    else {\n      j++;\n      swap(arr, j, right);\n    }\n\n    if (j <= k) left = j + 1;\n    if (k <= j) right = j - 1;\n  }\n}\n\n/**\n * The [quantile](https://en.wikipedia.org/wiki/Quantile):\n * this is a population quantile, since we assume to know the entire\n * dataset in this library. This is an implementation of the\n * [Quantiles of a Population](http://en.wikipedia.org/wiki/Quantile#Quantiles_of_a_population)\n * algorithm from wikipedia.\n *\n * Sample is a one-dimensional array of numbers,\n * and p is either a decimal number from 0 to 1 or an array of decimal\n * numbers from 0 to 1.\n * In terms of a k/q quantile, p = k/q - it's just dealing with fractions or dealing\n * with decimal values.\n * When p is an array, the result of the function is also an array containing the appropriate\n * quantiles in input order\n *\n * @param {Array<number>} x sample of one or more numbers\n * @param {Array<number> | number} p the desired quantile, as a number between 0 and 1\n * @returns {number} quantile\n * @example\n * quantile([3, 6, 7, 8, 8, 9, 10, 13, 15, 16, 20], 0.5); // => 9\n */\nfunction quantile(x: number[], p: number): number;\nfunction quantile(x: number[], p: number[]): number[];\nfunction quantile(x: any, p: any): any {\n  const copy = x.slice();\n\n  if (Array.isArray(p)) {\n    // rearrange elements so that each element corresponding to a requested\n    // quantile is on a place it would be if the array was fully sorted\n    multiQuantileSelect(copy, p);\n    // Initialize the result array\n    const results: number[] = [];\n    // For each requested quantile\n    for (let i = 0; i < p.length; i++) {\n      results[i] = quantileSorted(copy, p[i]);\n    }\n    return results;\n  } else {\n    const idx = quantileIndex(copy.length, p);\n    quantileSelect(copy, idx, 0, copy.length - 1);\n    return quantileSorted(copy, p);\n  }\n}\n\nfunction quantileSelect(arr, k, left, right) {\n  if (k % 1 === 0) {\n    quickselect(arr, k, left, right);\n  } else {\n    k = Math.floor(k);\n    quickselect(arr, k, left, right);\n    quickselect(arr, k + 1, k + 1, right);\n  }\n}\n\nfunction multiQuantileSelect(arr, p) {\n  const indices = [0];\n  for (let i = 0; i < p.length; i++) {\n    indices.push(quantileIndex(arr.length, p[i]));\n  }\n  indices.push(arr.length - 1);\n  indices.sort(compare);\n\n  const stack = [0, indices.length - 1];\n\n  while (stack.length) {\n    const r = Math.ceil(stack.pop());\n    const l = Math.floor(stack.pop());\n    if (r - l <= 1) continue;\n\n    const m = Math.floor((l + r) / 2);\n    quantileSelect(arr, indices[m], Math.floor(indices[l]), Math.ceil(indices[r]));\n\n    stack.push(l, m, m, r);\n  }\n}\n\nfunction compare(a, b) {\n  return a - b;\n}\n\nfunction quantileIndex(len, p) {\n  const idx = len * p;\n  if (p === 1) {\n    // If p is 1, directly return the last index\n    return len - 1;\n  } else if (p === 0) {\n    // If p is 0, directly return the first index\n    return 0;\n  } else if (idx % 1 !== 0) {\n    // If index is not integer, return the next index in array\n    return Math.ceil(idx) - 1;\n  } else if (len % 2 === 0) {\n    // If the list has even-length, we'll return the middle of two indices\n    // around quantile to indicate that we need an average value of the two\n    return idx - 0.5;\n  } else {\n    // Finally, in the simple case of an integer index\n    // with an odd-length list, return the index\n    return idx;\n  }\n}\n\nexport { quantile };\n"]}