← snapshot

import type { SnapshotDto } from "./types";

export interface GraphNode {
  id: string;
  lane: number;
  row: number;
  provenance: SnapshotDto["provenance"];
  /** Edges to parents: [parentRow, parentLane] pairs resolved after layout. */
  parents: string[];
}

export interface GraphLayout {
  nodes: GraphNode[];
  byId: Map<string, GraphNode>;
  laneCount: number;
}

/**
 * Greedy lane assignment over a newest-first snapshot list (the log's
 * order). A node inherits the lane its first-expecting child reserved for
 * it (first-parent priority); otherwise it opens the lowest free lane.
 * Fast-forward-only history keeps this narrow.
 */
export function layoutGraph(entries: SnapshotDto[]): GraphLayout {
  const nodes: GraphNode[] = [];
  const byId = new Map<string, GraphNode>();
  // lane -> the snapshot id that lane is waiting to see (its next parent).
  const expecting: (string | null)[] = [];

  entries.forEach((snapshot, row) => {
    let lane = expecting.findIndex((id) => id === snapshot.id);
    if (lane === -1) {
      lane = expecting.findIndex((id) => id === null);
      if (lane === -1) {
        lane = expecting.length;
        expecting.push(null);
      }
    }

    const node: GraphNode = {
      id: snapshot.id,
      lane,
      row,
      provenance: snapshot.provenance,
      parents: snapshot.parents,
    };
    nodes.push(node);
    byId.set(snapshot.id, node);

    // This lane now waits for the first parent; other parents open lanes
    // only if nothing is already expecting them.
    const [first, ...rest] = snapshot.parents;
    expecting[lane] = first ?? null;
    for (const parent of rest) {
      if (!expecting.includes(parent)) {
        const free = expecting.findIndex((id) => id === null);
        if (free === -1) expecting.push(parent);
        else expecting[free] = parent;
      }
    }
    // Collapse duplicate expectations (two children of one parent merge).
    for (let i = 0; i < expecting.length; i++) {
      for (let j = i + 1; j < expecting.length; j++) {
        if (expecting[j] !== null && expecting[j] === expecting[i]) {
          expecting[j] = null;
        }
      }
    }
  });

  return { nodes, byId, laneCount: Math.max(1, expecting.length) };
}