stats.mean-median

import { type CentralTendency, type Fraction } from "./stats_mean_median_types.ts";

function gcd(a: number, b: number): number {
  a = Math.abs(a);
  b = Math.abs(b);
  while (b !== 0) {
    const t = a % b;
    a = b;
    b = t;
  }
  return a;
}

function fraction(numerator: number, denominator: number): Fraction {
  const g = gcd(numerator, denominator) || 1;
  // `+ 0` turns -0 into 0 so a zero mean prints the same everywhere.
  return { numerator: numerator / g + 0, denominator: denominator / g };
}

/**
 * Mean, median and mode of a list of integers.
 *
 * Mean and median are exact fractions; their float forms come from a single
 * correctly rounded division, so every language returns the same double.
 */
export function meanMedianMode(values: readonly number[]): CentralTendency {
  if (!Array.isArray(values)) throw new TypeError("values must be a list of integers");
  if (values.length === 0) throw new RangeError("values must not be empty");
  for (const v of values) {
    if (typeof v !== "number" || !Number.isInteger(v)) {
      throw new TypeError(`values must be integers, received ${v}`);
    }
    if (!Number.isSafeInteger(v)) {
      throw new RangeError(`values must be safe integers (magnitude at most 9007199254740991), received ${v}`);
    }
  }

  // Sum in BigInt so an overflow is detected rather than silently rounded.
  let total = BigInt(0);
  for (const v of values) total += BigInt(v);
  if (total > BigInt(Number.MAX_SAFE_INTEGER) || total < -BigInt(Number.MAX_SAFE_INTEGER)) {
    throw new RangeError("sum exceeds the safe integer range");
  }
  const sum = Number(total);
  const count = values.length;

  // Numeric sort on a copy: the default sort compares as strings (10 < 9).
  const sorted = [...values].sort((a, b) => a - b);
  let median: Fraction;
  if (count % 2 === 1) {
    median = { numerator: sorted[(count - 1) / 2] + 0, denominator: 1 };
  } else {
    const pair = BigInt(sorted[count / 2 - 1]) + BigInt(sorted[count / 2]);
    const two = BigInt(2);
    if (pair % two === BigInt(0)) {
      median = { numerator: Number(pair / two) + 0, denominator: 1 };
    } else {
      if (pair > BigInt(Number.MAX_SAFE_INTEGER) || pair < -BigInt(Number.MAX_SAFE_INTEGER)) {
        throw new RangeError("median exceeds the safe integer range");
      }
      median = { numerator: Number(pair), denominator: 2 };
    }
  }

  // Runs of equal values in the sorted copy give frequencies in ascending
  // value order, so the modes come out sorted without a second sort.
  let modes: number[] = [];
  let modeFrequency = 0;
  let i = 0;
  while (i < count) {
    let j = i;
    while (j < count && sorted[j] === sorted[i]) j++;
    const run = j - i;
    if (run > modeFrequency) {
      modeFrequency = run;
      modes = [sorted[i] + 0];
    } else if (run === modeFrequency) {
      modes.push(sorted[i] + 0);
    }
    i = j;
  }

  const mean = fraction(sum, count);
  return {
    count,
    sum: sum + 0,
    mean,
    meanValue: sum / count + 0,
    median,
    medianValue: median.numerator / median.denominator + 0,
    modes,
    modeFrequency,
  };
}