collections.sort-by

import { type SortDirection } from "./collections_sort_by_types.ts";

/** An open record, the manifest's `record`: a JSON-ish map whose shape is not known ahead of time. */
type SortableRecord = Readonly<Record<string, unknown>>;

// The type ranks that give mixed values a total order. Absent sorts last in
// both directions, so it is ranked above every present value and then excluded
// from the direction flip below.
const RANK_BOOL = 0;
const RANK_NUMBER = 1;
const RANK_STRING = 2;
const RANK_ABSENT = 3;

function rankOf(value: unknown, key: string): number {
  // Absent and null are the same thing: a document that omits a field and one
  // that nulls it mean the same to every reader.
  if (value === undefined || value === null) return RANK_ABSENT;
  if (typeof value === "boolean") return RANK_BOOL;
  if (typeof value === "number") return RANK_NUMBER;
  if (typeof value === "string") return RANK_STRING;
  throw new TypeError(`cannot sort by the list or map at "${key}"`);
}

/**
 * Compare two strings by Unicode code point.
 *
 * JavaScript's `<` compares UTF-16 code units, while Python and Rust compare
 * code points; they disagree above U+FFFF. Spelling the comparison out makes
 * the order identical in all three languages for every string, not just ASCII.
 */
function compareStrings(a: string, b: string): number {
  const ca = Array.from(a);
  const cb = Array.from(b);
  const shared = Math.min(ca.length, cb.length);
  for (let i = 0; i < shared; i++) {
    const x = ca[i].codePointAt(0) as number;
    const y = cb[i].codePointAt(0) as number;
    if (x !== y) return x < y ? -1 : 1;
  }
  return ca.length === cb.length ? 0 : ca.length < cb.length ? -1 : 1;
}

/**
 * Stably sort `records` by `key`, ascending or descending.
 *
 * Ties keep their input order in both directions, which is what lets a user
 * sort by one column and then another and get the multi-column sort they
 * expect rather than a reshuffle.
 */
export function sortBy(
  records: readonly SortableRecord[],
  key: string,
  direction: SortDirection = "asc",
): readonly SortableRecord[] {
  if (!Array.isArray(records)) {
    throw new TypeError("sortBy needs a list of records");
  }
  if (typeof key !== "string" || key.length === 0) {
    throw new TypeError("sortBy needs a non-empty key name");
  }
  if (direction !== "asc" && direction !== "desc") {
    throw new RangeError(`direction must be "asc" or "desc", received "${direction}"`);
  }

  // Rank every record up front. Raising mid-comparison would make the error
  // depend on which comparisons this engine's sort happened to perform.
  const ranks = records.map((record) =>
    rankOf(record === null || record === undefined ? undefined : record[key], key),
  );
  const sign = direction === "desc" ? -1 : 1;

  const order = records.map((record, index) => ({ record, index }));
  order.sort((a, b) => {
    const ra = ranks[a.index];
    const rb = ranks[b.index];
    // Absent values sink to the bottom whichever way the sort runs: nobody
    // wants the rows they know nothing about at the top of a descending table.
    if (ra === RANK_ABSENT || rb === RANK_ABSENT) {
      if (ra === rb) return 0;
      return ra === RANK_ABSENT ? 1 : -1;
    }
    let base: number;
    if (ra !== rb) {
      base = ra < rb ? -1 : 1;
    } else if (ra === RANK_STRING) {
      base = compareStrings(a.record[key] as string, b.record[key] as string);
    } else if (ra === RANK_NUMBER) {
      const x = a.record[key] as number;
      const y = b.record[key] as number;
      base = x < y ? -1 : x > y ? 1 : 0;
    } else {
      const x = a.record[key] as boolean;
      const y = b.record[key] as boolean;
      base = x === y ? 0 : x ? 1 : -1;
    }
    return base * sign;
  });

  return order.map((entry) => entry.record);
}