Histogram Quantile Buckets

export interface Histogram { readonly bounds: readonly number[]; readonly counts: readonly number[]; readonly total: number; }

export function observe(bounds: readonly number[], samples: readonly number[]): Histogram {
  const sorted = [...bounds].sort((a, b) => a - b);
  const cumulative = new Array<number>(sorted.length + 1).fill(0);
  for (const sample of samples) {
    let i = 0;
    while (i < sorted.length && sample > (sorted[i] as number)) i += 1;
    cumulative[i] += 1;
  }
  for (let i = 1; i < cumulative.length; i++) cumulative[i] += cumulative[i - 1] as number;
  return { bounds: sorted, counts: cumulative, total: samples.length };
}

export function quantile(hist: Histogram, q: number): number {
  if (q < 0 || q > 1) throw new RangeError('q must be in [0, 1]');
  const target = q * hist.total;
  let prev = 0;
  for (let i = 0; i < hist.counts.length; i++) {
    const count = hist.counts[i] as number;
    if (count >= target) {
      const upper = i < hist.bounds.length ? (hist.bounds[i] as number) : prev * 2;
      const lower = i === 0 ? 0 : (hist.bounds[i - 1] as number);
      const bucketCount = count - prev;
      if (bucketCount === 0) return upper;
      return lower + ((target - prev) / bucketCount) * (upper - lower);
    }
    prev = count;
  }
  return hist.bounds[hist.bounds.length - 1] ?? 0;
}