quantile.js

import quantileSorted from "./quantile_sorted.js";
import quickselect from "./quickselect.js";

/**
 * [分位数](https://en.wikipedia.org/wiki/Quantile)计算函数：
 * 本实现基于总体分位数算法，假设已知完整数据集。遵循维基百科
 * [总体分位数](http://en.wikipedia.org/wiki/Quantile#Quantiles_of_a_population)算法。
 *
 * @param {Array<number>} x 数值型数据数组（需包含至少一个元素）
 * @param {Array<number> | number} p 分位点或分位点数组（取值范围[0,1]）
 * @returns {number} 分位数值或分位数数组
 * @example
 * quantile([3, 6, 7, 8, 8, 9, 10, 13, 15, 16, 20], 0.5); // => 9
 */
function quantile(x, p) {
    const copy = x.slice(); // 创建数据副本避免修改原数组

    if (Array.isArray(p)) {
        // 多分位点优化处理：重新排列数组元素实现高效选择
        multiQuantileSelect(copy, p);
        // 初始化结果数组
        const results = [];
        // 遍历每个分位点进行计算
        for (let i = 0; i < p.length; i++) {
            results[i] = quantileSorted(copy, p[i]);
        }
        return results;
    } else {
        // 单分位点快速选择
        const idx = quantileIndex(copy.length, p);
        quantileSelect(copy, idx, 0, copy.length - 1);
        return quantileSorted(copy, p);
    }
}

/**
 * 分位数选择函数（基于快速选择算法）
 * @param {Array} arr 目标数组
 * @param {number} k 目标索引
 * @param {number} left 左边界
 * @param {number} right 右边界
 */
function quantileSelect(arr, k, left, right) {
    if (k % 1 === 0) {
        // 整数索引直接快速选择
        quickselect(arr, k, left, right);
    } else {
        // 非整数索引处理相邻两个元素
        k = Math.floor(k);
        quickselect(arr, k, left, right);
        quickselect(arr, k + 1, k + 1, right);
    }
}

/**
 * 多分位点选择优化算法
 * @param {Array} arr 目标数组
 * @param {Array} p 分位点数组
 */
function multiQuantileSelect(arr, p) {
    const indices = [0]; // 初始化索引集合
    for (let i = 0; i < p.length; i++) {
        indices.push(quantileIndex(arr.length, p[i]));
    }
    indices.push(arr.length - 1);
    indices.sort(compare); // 索引排序

    const stack = [0, indices.length - 1]; // 使用栈结构进行分段处理

    while (stack.length) {
        const r = Math.ceil(stack.pop());
        const l = Math.floor(stack.pop());
        if (r - l <= 1) continue;

        const m = Math.floor((l + r) / 2);
        // 对中间分位点进行选择操作
        quantileSelect(
            arr,
            indices[m],
            Math.floor(indices[l]),
            Math.ceil(indices[r])
        );

        stack.push(l, m, m, r); // 压入新的处理区间
    }
}

// 数值比较函数
function compare(a, b) {
    return a - b;
}

/**
 * 分位数索引计算函数
 * @param {number} len 数组长度
 * @param {number} p 分位点
 * @returns {number} 计算后的索引值
 */
function quantileIndex(len, p) {
    const idx = len * p;
    // 边界条件处理
    if (p === 1) {
        return len - 1; // 末位索引
    } else if (p === 0) {
        return 0; // 首位索引
    } else if (idx % 1 !== 0) {
        return Math.ceil(idx) - 1; // 非整数索引处理
    } else if (len % 2 === 0) {
        return idx - 0.5; // 偶数长度中间位置
    } else {
        return idx; // 奇数长度直接返回
    }
}

export default quantile;