Sorting a view

/**
 * The order records are shown in, where that is not the order they are kept in:
 * sorted by a column, say. The order is a list of places — for each row of the
 * view, where its record is in the data — in one typed array, so that sorting a
 * hundred thousand records moves numbers and no record.
 *
 * - Sorting is stable: records that compare equal keep the order they are kept in.
 * - Nothing is last: a record with no value for what is sorted by comes after
 *   every record that has one, whichever way the rest are sorted.
 * - An edit does not move anything. When a value that is sorted by is changed,
 *   the row stays where it is until the view is sorted again: a row that jumps
 *   away as it is typed in takes the person's place with it.
 * - Records added are shown where they were added, and records removed leave
 *   the rest in their order.
 */
import type { AnyRecord, RecordChange } from "./record-changes.ts";
import type { Schema } from "./schema.ts";

/** For each row of the view, the place of its record in the data. */
export type ViewOrder = Uint32Array;

/** A comparison of two values, neither of them absent: negative when the first comes first. */
export type Compare = (a: unknown, b: unknown) => number;

const absent = (value: unknown) => value === null || value === undefined || value === "";

/** How values of a schema's kind are put in order. */
export function compareFor(schema: Schema, locale?: string): Compare {
  switch (schema.kind) {
    case "number":
      return (a, b) => (a as number) - (b as number);
    case "boolean":
      // No before yes.
      return (a, b) => Number(a) - Number(b);
    case "choice": {
      // In the order the choices are offered, which is the order that means something.
      const place = new Map(schema.options.map((option, index) => [option.value, index]));
      const last = schema.options.length;
      return (a, b) => (place.get(a as string) ?? last) - (place.get(b as string) ?? last);
    }
    case "date":
      // ISO dates are in order as text.
      return (a, b) => (a === b ? 0 : (a as string) < (b as string) ? -1 : 1);
    default: {
      // As people sort names: without regard to case or accent, and with "2" before "10".
      const collator = new Intl.Collator(locale, { numeric: true, sensitivity: "base" });
      return (a, b) => collator.compare(String(a), String(b));
    }
  }
}

/**
 * The order that shows `rows` sorted by one field. `direction` is 1 for
 * ascending and -1 for descending; records with nothing in the field come last
 * either way.
 */
export function sortedOrder(
  rows: readonly AnyRecord[],
  key: string,
  compare: Compare,
  direction: 1 | -1 = 1,
): ViewOrder {
  const order = new Uint32Array(rows.length);
  for (let index = 0; index < order.length; index += 1) order[index] = index;
  // Typed arrays sort in place, and stably: equal records keep the order they are kept in.
  // oxlint-disable-next-line unicorn/no-array-sort
  return order.sort((i, j) => {
    const a = rows[i]![key];
    const b = rows[j]![key];
    const none = Number(absent(a)) - Number(absent(b));
    if (none !== 0 || absent(a)) return none;
    return direction * compare(a, b);
  });
}

/** For each record in the data, the row of the view it is shown in: the order, turned about. */
export function placesIn(order: ViewOrder): Uint32Array {
  const places = new Uint32Array(order.length);
  for (let row = 0; row < order.length; row += 1) places[order[row]!] = row;
  return places;
}

/**
 * The order after a change to the records, with every row that is still there
 * where it was. Records inserted are shown before the row that held the record
 * they were put in front of — at the end, when they were put at the end.
 */
export function orderAfter(order: ViewOrder, change: RecordChange): ViewOrder {
  switch (change.kind) {
    case "cells":
      return order;
    case "insert": {
      const added = change.rows.length;
      const next = new Uint32Array(order.length + added);
      // The row that showed the record now pushed along: the new ones go in front of it.
      let at = order.length;
      for (let row = 0; row < order.length; row += 1) {
        if (order[row] === change.at) {
          at = row;
          break;
        }
      }
      for (let row = 0, to = 0; row <= order.length; row += 1) {
        if (row === at) for (let index = 0; index < added; index += 1) next[to++] = change.at + index;
        if (row < order.length) next[to++] = order[row]! >= change.at ? order[row]! + added : order[row]!;
      }
      return next;
    }
    case "remove": {
      // For each place in the data, how many removed records came before it — or that it was one.
      const gone = new Uint8Array(order.length);
      for (const run of change.runs) gone.fill(1, run.at, Math.min(run.at + run.rows.length, order.length));
      const before = new Uint32Array(order.length);
      let removed = 0;
      for (let place = 0; place < order.length; place += 1) {
        before[place] = removed;
        removed += gone[place]!;
      }
      const next = new Uint32Array(order.length - removed);
      for (let row = 0, to = 0; row < order.length; row += 1) {
        const place = order[row]!;
        if (gone[place] === 0) next[to++] = place - before[place]!;
      }
      return next;
    }
  }
}