Dependency order

/**
 * Dependency order over a directed graph: the order to recompute things in so
 * that each is computed after everything it depends on — the formulas of a
 * grid, the nodes of a flow, the constraints of a layout.
 *
 * A graph is held in compressed sparse rows, two typed arrays, so a traversal
 * touches memory in order and allocates nothing per node. An edge `from → to`
 * means `to` depends on `from`: `from` comes first.
 *
 * Nodes and positions among the edges are 32-bit integers, so a graph holds up
 * to 2^31 − 2 nodes and 2^31 − 1 edges. A node that is not in the graph — in an
 * edge, or among those said to have changed — is a mistake in the caller, and
 * throws a `RangeError`.
 */

export interface Graph {
  /** For node n, its targets are `targets[offsets[n] … offsets[n + 1])`. */
  readonly offsets: Int32Array;
  readonly targets: Int32Array;
}

const MAX_NODES = 2 ** 31 - 2;
const MAX_EDGES = 2 ** 31 - 1;

/** A graph of `nodeCount` nodes from a flat list of edges, `[from0, to0, from1, …]`, in O(V + E). */
export function graphFrom(nodeCount: number, edges: ArrayLike<number>): Graph {
  if (!Number.isInteger(nodeCount) || nodeCount < 0 || nodeCount > MAX_NODES) {
    throw new RangeError(`A graph holds a whole number of nodes, at most 2^31 − 2, not ${nodeCount}.`);
  }
  const edgeCount = edges.length / 2;
  if (!Number.isInteger(edgeCount)) {
    throw new RangeError(`Edges are two nodes each; ${edges.length} is not a multiple of two.`);
  }
  if (edgeCount > MAX_EDGES) throw new RangeError(`A graph holds at most 2^31 − 1 edges, not ${edgeCount}.`);
  const offsets = new Int32Array(nodeCount + 1);
  for (let i = 0; i < edges.length; i += 2) {
    const from = edges[i]!;
    const to = edges[i + 1]!;
    // One comparison each refuses negatives, fractions and what is not a number.
    if (from >>> 0 !== from || from >= nodeCount || to >>> 0 !== to || to >= nodeCount) {
      throw new RangeError(`Edge ${i / 2}, ${from} → ${to}, names a node that is not among ${nodeCount}.`);
    }
    offsets[from + 1]! += 1;
  }
  for (let node = 0; node < nodeCount; node += 1) offsets[node + 1]! += offsets[node]!;
  const targets = new Int32Array(edgeCount);
  const next = offsets.slice(0, nodeCount);
  for (let i = 0; i < edges.length; i += 2) {
    const from = edges[i]!;
    targets[next[from]!] = edges[i + 1]!;
    next[from]! += 1;
  }
  return { offsets, targets };
}

/**
 * Every node, each after all the nodes it depends on — or `null` when the graph
 * has a cycle and no such order exists. O(V + E).
 */
export function topologicalOrder({ offsets, targets }: Graph): Int32Array | null {
  const count = offsets.length - 1;
  const pending = new Int32Array(count);
  for (let i = 0; i < targets.length; i += 1) pending[targets[i]!]! += 1;

  // The order doubles as the queue: nodes are appended as they become ready.
  const order = new Int32Array(count);
  let ready = 0;
  for (let node = 0; node < count; node += 1) {
    if (pending[node] === 0) order[ready++] = node;
  }
  for (let done = 0; done < ready; done += 1) {
    const node = order[done]!;
    for (let i = offsets[node]!; i < offsets[node + 1]!; i += 1) {
      const target = targets[i]!;
      pending[target]! -= 1;
      if (pending[target] === 0) order[ready++] = target;
    }
  }
  return ready === count ? order : null;
}

/**
 * The nodes of one cycle, each depending on the one before and the first on the
 * last — what to show people when their formulas refer to each other — or
 * `null` when there is none. O(V + E).
 */
export function findCycle({ offsets, targets }: Graph): Int32Array | null {
  const count = offsets.length - 1;
  // 0 unvisited, 1 on the current path, 2 finished.
  const state = new Uint8Array(count);
  const path = new Int32Array(count);
  const cursor = new Int32Array(count);

  for (let root = 0; root < count; root += 1) {
    if (state[root] !== 0) continue;
    let depth = 0;
    path[0] = root;
    cursor[0] = offsets[root]!;
    state[root] = 1;
    while (depth >= 0) {
      const node = path[depth]!;
      const next = cursor[depth]!;
      if (next === offsets[node + 1]) {
        state[node] = 2;
        depth -= 1;
        continue;
      }
      const target = targets[next]!;
      cursor[depth] = next + 1;
      if (state[target] === 1) return path.slice(path.indexOf(target), depth + 1);
      if (state[target] === 0) {
        depth += 1;
        path[depth] = target;
        cursor[depth] = offsets[target]!;
        state[target] = 1;
      }
    }
  }
  return null;
}

interface Scratch {
  /** Each node's position in the order. */
  readonly rank: Int32Array;
  /** 1 for a node already found in the call under way; all 0 between calls. */
  readonly seen: Uint8Array;
  /** The nodes found so far, each waiting its turn to have its edges followed. */
  readonly queue: Int32Array;
}

const scratches = new WeakMap<Int32Array, Scratch>();

function scratchFor(order: Int32Array): Scratch {
  let scratch = scratches.get(order);
  if (scratch === undefined) {
    const rank = new Int32Array(order.length);
    for (let position = 0; position < order.length; position += 1) rank[order[position]!] = position;
    scratch = { rank, seen: new Uint8Array(order.length), queue: new Int32Array(order.length) };
    scratches.set(order, scratch);
  }
  return scratch;
}

/**
 * What must be recomputed when `changed` nodes change: those nodes and
 * everything that depends on them, in the order `order` has them.
 *
 * The first call for an order makes scratch space the size of the graph. After
 * it, a call allocates only what it returns, and costs the k nodes it returns,
 * their edges, and the O(k log k) of sorting them into the order — not the size
 * of the graph.
 */
export function affectedBy(graph: Graph, order: Int32Array, changed: ArrayLike<number>): Int32Array {
  const { offsets, targets } = graph;
  const count = offsets.length - 1;
  if (order.length !== count) {
    throw new RangeError(`An order of ${order.length} nodes is not an order of this graph's ${count}.`);
  }
  const { rank, seen, queue } = scratchFor(order);
  let found = 0;
  for (let i = 0; i < changed.length; i += 1) {
    const node = changed[i]!;
    if (node >>> 0 !== node || node >= count) {
      // Leave no marks behind for the next call to trip on.
      for (let j = 0; j < found; j += 1) seen[queue[j]!] = 0;
      throw new RangeError(`Changed node ${node} is not among ${count}.`);
    }
    if (seen[node] === 0) {
      seen[node] = 1;
      queue[found++] = node;
    }
  }
  for (let head = 0; head < found; head += 1) {
    const node = queue[head]!;
    for (let i = offsets[node]!; i < offsets[node + 1]!; i += 1) {
      const target = targets[i]!;
      if (seen[target] === 0) {
        seen[target] = 1;
        queue[found++] = target;
      }
    }
  }
  // Unmarking as they are read out costs only the result, where a count of
  // calls would one day pass what its marks could hold.
  const affected = new Int32Array(found);
  for (let i = 0; i < found; i += 1) {
    const node = queue[i]!;
    seen[node] = 0;
    affected[i] = rank[node]!;
  }
  // Sorting positions in the order, then reading the order back, sorts the nodes.
  // In place: the array was made just above, for this.
  // oxlint-disable-next-line unicorn/no-array-sort
  affected.sort();
  for (let i = 0; i < found; i += 1) affected[i] = order[affected[i]!]!;
  return affected;
}